Графічний метод та симплекс-метод вирішення задач лінійного програмування -

1. Геометричний метод розв'язання задач ЛП

2.1 Ідея симплекс-методу

2.2 Реалізація симплекс-метода з прикладу

2.3 Таблична реалізація простого симплекс-методу

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

Тема моєї роботи стосується вирішення завдань, що виникають в економіці. При цьому постає питання про вибір найкращого в певному сенсі варіанта рішення. А на пошук можливого варіанта часто впливають різні фактори, що звужують рамки вибору. Інакше висловлюючись, потрібно вирішити завдання оптимізації, що полягає у необхідності вибору найкращого варіанта рішень серед деякого, зазвичай, обмеженого безлічі можливих варіантів.

Завдання оптимізації може бути сформульована мовою математики, якщо безліч доступних варіантів вдається описати з допомогою математичних співвідношень (рівностей, нерівностей, рівнянь), а кожне рішення - оцінити кількісно з допомогою деякого показника, званого критерієм оптимальності чи цільової функцією. Тоді найкращим рішенням буде те, що доставляє цільової функції найбільше чи найменше значення, залежно від змістовного змісту завдання. Так, наприклад, при інвестуванні обмеженої суми коштів у декілька проектів природною є завдання вибору тих проектів, які можуть принести у майбутньому найбільший прибуток. При доставці в магазини продукції від різних постачальників постає завдання мінімізації транспортних витрат.

Процес формалізації завдання називається побудовою її математичної моделі. Він складається із трьох етапів.

1. Вибір параметрів задачі, яких залежить рішення. Ці параметри називають керуючими змінними і позначають, формуючи їх вектор. Прийнятирішення – це означає задати конкретні значення змінних.

2. Побудова числового критерію, яким можна порівнювати різні варіанти решений. Такий критерій прийнято називати цільовою функцією та позначати через .

3. Опис усієї множини X допустимих значень змінних – обмежень, пов'язаних з наявністю матеріальних ресурсів, фінансових засобів, технологічними можливостями тощо.

Математична задача оптимізації полягає у знаходженні такого допустимого рішення, яке доставляє цільовій функції найбільше чи найменше значення серед усіх можливих рішень.

.

1. Геометричний метод розв'язання задач ЛП

Цей метод часто використовується під час вирішення завдань, у яких лише дві невідомі величини. Розберемо його на таких прикладах:

приклад 1.1. (Завдання про виробництво фарб).

Невелика фабрика виготовляє два види фарб: INT – для внутрішніх робіт та EXT – для зовнішніх робіт. У виробництві фарб використовуються два вихідні продукти А і В. Через малу площу складу максимально можливі добові запаси цих продуктів дорівнюють 6 т. і 8 т. відповідно. На виробництво 1 тонни фарби INT витрачається 1 тонна продукту А і 2 тонни продукту, а на виготовлення 1 тонни фарби EXT йде 2 тонни продукту А і 1 тонна продукту В. Фабрика продає фарбу за ціною 3 тис. дол. за тонну фарби INT і 2 тис. дол. за тонну фарби EXT. Вихідні дані зручно звести до таблиці:

---