Постановка задачі лінійного програмування

Тема 10. Чисельні методи оптимізації

Постановка задачі

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

Проблеми оптимізації виникають:

- під час керування різними технологічними процесами, агрегатами, установками, де потрібно досягти максимальної продуктивності праці за умови найкращої якості та мінімальних затрат;

- під час проектування різних інженерних конструкцій, пристроїв, схем, коли потрібно підібрати таку комбінацію їх параметрів, яка б за мінімальної матеріаломісткості відповідала б найкращим експлуатаційним характеристикам проектованого об’єкта;

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

При постановці задачі оптимізації, система оптимізації замінюється її моделлю (рисунок 34).

 

 

Рисунок 34 – Модель технічної системи

 

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

В задачах конструювання оптимізуються параметри системи , а в діючих об’єктах і процесах оптимізуются характеристики режиму .

В багатьох прикладних задачах вибір параметрів системи не може бути довільним. В зв’язку з цим задачі оптимізації поділяються на 2 типи: безумовні та умовні.

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

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

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

Класична задача отримання оптимальних планів зводиться до такого:

1) задана деяка функція (10.1)

для якої потрібно знайти максимум (мінімум);

2) множина параметрів системи Х задається з допомогою системи рівнянь та нерівностей; (10.2)

Такі задачі або не розв’язуються класичними методами взагалі, або застосування їх приводить до дуже великої трудоємкості. Їх розвязок здійснюється методами математичного програмування. Якщо (10.1) – лінійна функція, то це робиться засобами лінійного програмування. Якщо (10.1) або (10.2) мають нелінійності, то такі задачі розв’язуються методами динамічного програмування.

Якщо розв’язок такої задачі потребує цілих значень Х, для їх отримання застосовують дискретне програмування.

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

 

Постановка задачі лінійного програмування

Задача лінійного програмування (ЗЛП) формулюється так:

Знайти вектор , що мінімізує функцію

при таких обмеженнях:

(10.3)

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

при обмеженнях:

 

(10.4)

 

Модель (10.3) можна привести до канонічної форми (10.4), скориставшись твердженнями:

a)

b) ;

c) розв’язок системи (10.3) з від’ємними значеннями можна звести до системи (10.4) з невід’ємними , якщо від’ємні компоненти вектора Х замінити різницею двох додатніх:

d) якщо то його можна замінити на рівність шляхом додавання в ліву частину невід’ємної змінної .

Канонічна модель в матричній формі має вигляд: при обмеженнях .