Зміст
Введення
1. Загальна постановка задачі лінійного програмування (ЛП)
2. Приведення завдання лінійного програмування до стандартній формі
3. Приклади економічних задач, що приводяться до завдань ЛП
4. Геометричний метод рішення задач ЛП
5. Симплексний метод вирішення завдань ЛЗ
6. Теореми двоїстості та їх використання в задачах ЛП
6. Транспортна задача і її рішення методом потенціалів
Висновок
Література
Введення
В даний час оптимізація знаходить застосування в науці, техніці і в будь-який інший галузі людської діяльності.
Оптимізація - цілеспрямована діяльність, що полягає в отриманні найкращих результатів при відповідних умовах .
Пошуки оптимальних рішень привели до створення спеціальних математичних методів і вже в 18 столітті були закладені математичні основи оптимізації (варіаційне числення, чисельні методи та ін.) Однак до другої половини 20 століття методи оптимізації під багатьох галузях науки і техніки застосовувалися дуже рідко, оскільки практичне використання математичних методів оптимізації вимагало величезної обчислювальної роботи, яку без ЕОМ реалізувати було вкрай важко, а в ряді випадків - неможливо.
Постановка задачі оптимізації припускає існування конкуруючих властивостей процесу, наприклад:
В· кількість продукції - витрата сировини
В· кількість продукції - якість продукції
Вибір компроміcсного варіанти для зазначених властивостей і являє собою процедуру розв'язання оптимізаційної задачі.
При постановці задачі оптимізації необхідно:
1 . Наявність об'єкта оптимізації і мети оптимізації. При цьому формулювання кожного завдання оптимізації повинна вимагати екстремального значення лише однієї величини, тобто одночасно системі не повинно приписуватися два і більше критеріїв оптимізації, тому практично завжди екстремум одного критерію не відповідає екстремуму іншого. Наведемо приклади.
Типовий приклад неправильної постановки завдання оптимізації:
"Отримати максимальну продуктивність при мінімальній собівартості ".
Помилка полягає в тому, що ставиться завдання пошуку оптимальності 2-х величин, що суперечать один одному за своєю суттю.
Правильна постановка завдання могла бути наступна:
а) отримати максимальну продуктивність при заданій собівартості;
б) отримати мінімальну собівартість при заданій продуктивності;
У першому випадку критерій оптимізації - продуктивність, а в другому - собівартість.
2 . Наявність ресурсів оптимізації, під якими розуміють можливість вибору значень деяких параметрів оптимизируемого об'єкта.
3 . Можливість кількісної оцінки оптимізується величини, оскільки тільки в цьому випадку можна порівнювати ефекти від вибору тих чи інших керуючих впливів.
4. Облік обмежень.
Зазвичай оптимізується величина пов'язана з економічністю роботи даного об'єкту (Апарат, цех, завод). Оптимизируемого варіант роботи об'єкта повинен оцінюватися якийсь кількісною мірою - критерієм оптимальності.
Критерієм оптимальності називається кількісна оцінка оптимизируемого якості об'єкта.
На підставі вибраного критерію оптимальності складається цільова функція, що представляє собою залежність критерію оптимальності від параметрів, які впливають на її значення. Вид критерію оптимальності або цільової функції визначається конкретним завданням оптимізації.
Таким чином, задача оптимізації зводиться до знаходження екстремуму цільової функції.
В залежності від своєї постановки, будь-яка з задач оптимізації може вирішуватися різними методами, і навпаки - будь-який метод може застосовуватися для вирішення багатьох завдань. Методи оптимізації можуть бути скалярними (оптимізація проводиться по одному критерію), векторними (оптимізація проводиться за багатьма критеріями), пошуковими (включають методи регулярного і методи випадкового пошуку), аналітичними (методи диференціального числення, методи варіаційного числення та ін), обчислювальними (засновані на математичному програмуванні, яке може бути лінійним, нелінійним, дискретним, динамічним, стохастичним, евристичним і т.д.), теоретико-ймовірнісними, теоретико-ігровими та ін Піддаватися оптимізації можуть завдання як з обмеженнями, так і без них.
Лінійне програмування - один з перших і найбільш докладно вивчених розділів математичного програмування. Саме лінійне програмування з'явилося тим розділом, з якого почала розвиватися сама дисципліна "математичне програмування". Термін "програмування" в назві дисципліни нічого спільного з терміном "Програмування (тобто складання програм) для ЕОМ" не має, так як дисципліна "лінійне програмування" виникла ще до того часу, коли ЕОМ стали широко застосовуватися при рішенні математичних, інженерних, економічних та ін задач. Термін В«лінійне програмування" виник в результаті неточного перекладу англійського "linear programming". Одне із значень слова "programming" - Складання планів, планування. Отже, правильним перекладом "linear programming" було б не В«лінійне програмування", а "лінійне планування", що більш точно відображає зміст дисципліни. Однак, термін лінійне програмування, нелінійне програмування і т.д. в нашій літературі стали загальноприйнятими.
Отже, лінійне програмування виникло після Другої Світової Війни і став швидко розвиватися, привертаючи увагу математиків, економістів та інженерів завдяки можливості широкого практичного застосування, а так само математичної "стрункості".
Можна сказати, що лінійне програмування застосовне для побудови математичних моделей тих процесів, в основу яких може бути покладена гіпотеза лінійного представлення реального світу: економічних завдань, завдань управління і планування, оптимального розміщення устаткування і ін
Завданнями лінійного програмування називаються завдання, в яких лінійні як цільова функція, так і обмеження у вигляді рівностей і нерівностей. Коротко завдання лінійного програмування можна сформулювати наступним чином: знайти вектор значень змінних, що доставляють екстремум лінійної цільової функції при m обмеженнях у вигляді лінійних рівностей або нерівностей.
Лінійне програмування являє собою найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:
В· раціонального використання сировини та матеріалів; задачі оптимізації розкрою;
В· оптимізації виробничої програми підприємств;
В· оптимального розміщення і концентрації виробництва;
В· складання оптимального плану перевезень, роботи транспорту;
В· управління виробничими запасами;
В· і багато інших, що належать сфері оптимального планування.
Так, по оцінками американських експертів, близько 75% від загального числа застосовуваних оптимізаційних методів доводиться на лінійне програмування. Близько чверті машинного часу, витраченого в останні роки на проведення наукових досліджень, було відведено вирішенню завдань лінійного програмування і їх численних модифікацій.
Перші постановки задач лінійного програмування були сформульовані відомим радянським математиком Л.В. Канторовичем, якому за ці роботи була присуджена Нобелівська премія з економіки.
Значне розвиток теорія і алгоритмічний апарат лінійного програмування одержали з винаходом і поширенням ЕОМ і формулюванням американським математиком Дж. Дансинг симплекс-методу.
У розвиток і вдосконалення цих систем вкладена праця і талант багатьох математиків, акумульований досвід вирішення тисяч завдань. Володіння апаратом лінійного програмування необхідно кожному фахівцеві в області математичного пр...
