ВВЕДЕННЯ - Рішення оптимізаційної задачі лінійного програмування

В даний час оптимізація знаходить застосування в науці, техніці і в будь-якій іншій області людської діяльності.

Оптимізація - цілеспрямована діяльність, що полягає в отриманні якнайкращих результатів за відповідних умов.

Пошуки оптимальних рішень привели до створення спеціальних математичних методів і вже в 18 столітті були закладені математичні основи оптимізації (варіаційне числення, чисельні методи і др). Проте до другої половини 20 століть методи оптимізації в багатьох областях науки і техніки застосовувалися дуже рідко, оскільки практичне використання математичних методів оптимізації вимагало величезної обчислювальної роботи, яку без ЕОМ реалізувати було украй важко, а у ряді випадків - неможливо.

Постановка завдання оптимізації припускає існування конкуруючих властивостей процесу, наприклад:

кількість продукції - витрата сировини

кількість продукції - якість продукції

Вибір компромиcного варіанту для вказаних властивостей і є процедурою рішення оптимізаційної задачі.

При постановці завдання оптимізації необхідно:

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

Типовий приклад неправильної постановки завдання оптимізації:

"Отримати максимальну продуктивність при мінімальній собівартості".

Помилка полягає в тому, що ставиться завдання пошуку оптимальності 2-х величин, що суперечать один одному за своєю суттю.

Правильна постановка завдання могла бути наступна:

    А) отримати максимальну продуктивність при заданій собівартості; Б) отримати мінімальну собівартість при заданій продуктивності;

У першому випадку критерій оптимізації - продуктивність а в другому - собівартість.

    2. Наявність ресурсів оптимізації, під якими розуміють можливість вибору значень деяких параметрів об'єкту, що оптимізується. 3. Можливість кількісної оцінки величини, що оптимізується, оскільки тільки в цьому випадку можна порівнювати ефекти від вибору тих або інших дій, що управляють. 4. Облік обмежень.

Величина, що зазвичай оптимізується, пов'язана з економічністю роботи даного об'єкту (апарат, цех, завод). Варіант роботи об'єкту, що оптимізується, повинен оцінюватися якоюсь кількісною мірою - критерієм оптимальності.

Критерієм оптимальності називається кількісна оцінка якості об'єкту, що оптимізується.

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

Таким чином, завдання оптимізації зводиться до знаходження екстремуму цільової функції.

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

Лінійне програмування - один з перших і найбільш детально вивчених розділів математичного програмування. Саме лінійне програмування з'явилося тим розділом, з якого початку розвиватися сама дисципліна "математичне програмування". Термін "програмування" в назві дисципліни нічого спільного з терміном "програмування (тобто складання програм) для ЕОМ" не має, оскільки дисципліна "лінійне програмування" виникла ще до того часу, коли ЕОМ стали широко застосовуватися при рішенні математичних, інженерних, економічних і ін. завдань. Термін "лінійне програмування" виник в результаті неточного перекладу англійського "linear programming". Одне із значень слова "programming" - складання планів, планування. Отже, правильним перекладом "Linear programming" було б не "лінійне програмування", а "лінійне планування", що точніше відображає зміст дисципліни. Проте, термін лінійне програмування, нелінійне програмування і т. д. в наший літературі стали загальноприйнятими.

Отже, лінійне програмування виникло після Другої Світової Війни і став швидко розвиватися, привертаючи увагу математиків, економістів і інженерів завдяки можливості широкого практичного застосування, а так само математичній "стрункості".

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

Завданнями лінійного програмування називаються завдання, в яких лінійні як цільова функція, так і обмеження у вигляді рівності і нерівностей. Стисло завдання лінійного програмування можна сформулювати таким чином: знайти вектор значень змінних, що доставляють екстремум лінійної цільової функції при m обмеженнях у вигляді лінійної рівності або нерівностей.

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

Раціонального використання сировини і матеріалів; завдання оптимізації розкроу;

Оптимізації виробничої програми підприємств;

Оптимального розміщення і концентрації виробництва;

Складання оптимального плану перевезень, роботи транспорту;

Управління виробничими запасами;

І багато інших, що належать сфері оптимального планування.

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

Перші постановки завдань лінійного програмування були сформульовані відомим радянським математиком Л. В. Канторовичем, якому за ці роботи була присуджена Нобелівська премія по економіці.

Значний розвиток теорія і алгоритмічний апарат лінійного програмування отримали з винаходом і розповсюдженням ЕОМ і формулюванням американським математиком Дж. Данцингом симплекс-метода.

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

У розвиток і вдосконалення цих систем вкладена праця і талант багатьох матеметиков, закумульований досвід рішення тисяч завдань. Володіння апаратом лінійного програмування необхідне кожному фахівцеві в області математичного програмування. Лінійне програмування тісно пов'язане з іншими методами математичного програмування (наприклад, нелінійного програмування, де цільова функція нелінійна).

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

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

Похожие статьи




ВВЕДЕННЯ - Рішення оптимізаційної задачі лінійного програмування

Предыдущая | Следующая