равління і планування, оптимального розміщення устаткування і ін
Завданнями лінійного програмування називаються завдання, в яких лінійні як цільова функція, так і обмеження у вигляді рівностей і нерівностей. Коротко задачу лінійного програмування можна сформулювати наступним чином: знайти вектор значень змінних, що доставляють екстремум лінійної цільової функції при m обмеженнях у вигляді лінійних рівностей або нерівностей.
Лінійне програмування є найбільш часто використовуваний метод оптимізації. До завдань лінійного програмування можна віднести завдання:
В· раціонального використання сировини та матеріалів; задачі оптимізації розкрою;
В· оптимізації виробничої програми підприємств;
В· оптимального розміщення і концентрації виробництва;
В· складання оптимального плану перевезень, роботи транспорту;
В· управління виробничими запасами;
В· і багато інших, що належать сфері оптимального планування.
Так, за оцінками американських експертів, близько 75% від загального числа застосовуваних оптимізаційних методів припадає на лінійне програмування. Близько чверті машинного часу, витраченого в останні роки на проведення наукових досліджень, було відведено вирішенню завдань лінійного програмування і їх численних модифікацій.
Перші постановки завдань лінійного програмування були сформульовані відомим радянським математиком Л.В. Канторовичем, якому за ці роботи була присуджена Нобелівська премія з економіки.
Значне розвиток теорія і алгоритмічний апарат лінійного програмування отримали з винаходом і поширенням ЕОМ і формулюванням американським математиком Дж. Дансингах симплекс-методу.
У розвиток і вдосконалення цих систем вкладена праця і талант багатьох математиків, акумульований досвід вирішення тисяч завдань. Володіння апаратом лінійного програмування необхідно кожному фахівцю в галузі математичного програмування. Лінійне програмування тісно пов'язане з іншими методами математичного програмування (наприклад, нелінійного програмування, де цільова функція нелінійна).
Завдання з нелінійної цільової функцією і лінійними обмеженнями називають завданнями нелінійного програмування з лінійними обмеженнями. Оптимізаційні задачі такого роду можна класифікувати на основі структурних особливостей нелінійних цільових функцій. Якщо цільова функція Е - квадратична функція, то ми маємо справу із завданням квадратичного програмування; якщо Е - це відношення лінійних функцій, то відповідне завдання носить назву завдання дробово-лінійного програмування, і т.д. Ділення оптимізаційних завдань на ці класи представляє значний інтерес, оскільки специфічні особливості тих чи інших завдань грають важливу роль при розробці методів їх вирішення.
1. Загальна постановка задачі лінійного програмування (ЛП)
В
Задача лінійного програмування (ЛП) полягає в знаходженні мінімуму (або максимуму...
