2.2. Характеристика методів оптимізації

2.2.1. Методи лінійного програмування.

Завдання лінійного програмування полягає в наступному: знайти значення змінних які задовольняють систему рівнянь

(2.1)

є невід'ємними:

(2.2)

і дають найменше значення цільової функції

Будь-яке рішення системи рівнянь (2.1), що задовільняє нерівності (2.2), називається допустимим; допустиме рішення, що дає найменше значення цільової функції, вважається оптимальним.

Припустимо, що система (2.1) сумісна і серед її рівнянь немає лінійно-залежних. Для того щоб така система мала безліч рішень, необхідно і достатньо, щоб число рівнянь m в ній було менше числа невідомих n , тобто n -m = k > 0. Отже, в системі (2.1) знайдеться m змінних (базисних), які можна виразити через інші k змінних (вільних). Надаючи вільним змінним різні значення і обчислюючи по них базисні, можна отримати різні рішення системи (2.1).

Нехай в системі (2.1) змінні якимось чином розділені на базисні і вільні. Приймемо, що всі вільні змінні дорівнюють нулю, і визначимо із системи відповідні значення базисних змінних. Якщо жодна з них не буде негативною, то ми отримаємо допустиме рішення, у якого k змінних дорівнюють нулю. Таке рішення називається опорним.

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

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

Розглядаючи деякий набір чисел на ітерації ν визначають вектор у деякому змісті більш близький до рішення задачі, ніж на ітерації ν-1.

Методи лінійного програмування діляться на кінцеві та ітеративні. Кінцевий метод дозволяє отримати точне рішення задачі за кінцеву кількість кроків.

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

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

Теорія подвійності приводить довільну задачу лінійного програмування (наприклад, задачу з умовами - нерівностями)

(2.3)

у відповідність із наступною задачею лінійного програмування:

. (2.4)

Вихідна задача (2.3) називається прямою, а задача (2.4) - двоїстої (сполученої). Таким чином, задача (3) і (4) складають єдину двоїсту пару, аналіз яких визначає вибір оптимального плану і підрахунок його економічних показників. Одним із основних кінцевих методів є симплексний метод, тобто метод послідовного поліпшення плану. Рішення задачі починається з аналізу деякого початкового опорного плану прямої задачі. У процесі переходу від одного опорного плану до іншого послідовне поліпшення плану дозволяє за кінцеву кількість кроків прийти до рішення задачі чи до встановлення факту її нерозв'язності. Вектор у цьому методі являє собою опорний план задачі.

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

До кінцевих методів також відноситься і метод послідовного скорочення невязок; вектор містить дві групи компонентів: і

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

Ітеративні методи рішення умовних лінійних екстремальних задач створені в основному в теорії ігор і в опуклому програмуванні.

2.2.2. Динамічне програмування

Для точного рішення задач цілочислового програмування з малою кількістю «істотних» обмежень (не більше двох-трьох) часто виявляються корисними принципи динамічного програмування. Наприклад, нехай є задача за і . Тут - цілі додатні числа.

Функція Беллмана - функція цілочисельного аргументу z для являє собою оптимальне значення цільової функції задачі, в якій параметри n і b замінені на k і z. Функція Беллмана задовольняє наступне рекурентне співвідношення (рівняння Беллмана): де max береться пo h, що задовольняє умови . Враховуючи, що , можна послідовно знайти з рівняння значення всіх функцій для . Знаючи величини , легко послідовно розрахувати складові шуканого рішення .

Виберемо з умов . Знаючи , розрахуємо із співвідношення і т.д.

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

Якщо ж розв’язувати цю задачу повним перебором, то необхідна кількість операцій . За великих n і b і динамічне програмування істотно спрощує рішення задачі.

Загальна схема динамічного програмування ефективно використовується в тих цілочисельних задачах, у яких вдається виразити послідовність рекурентно пов'язаних між собою функцій Беллмана через можливо меншу кількість аргументів. Ці аргументи зазвичай визначаються «істотними» обмеженнями задачі.

Розглянемо приклад використання динамічного програмування для вибору оптимального параметричного ряду силових головок для компонування АЛ. Процес оптимізації параметричного ряду полягає в перерозподілі головного параметра і величини випуску кожного типорозміру виробу відповідно до функції попиту з метою відшукання мінімуму критерія приведених витрат З_j. Позначимо П - головний параметр оптимізації; - мінімальне і максимальне значення П ; П_i - значення головного параметра для i-го типорозміру; k - число типорозмірів; М – максимальна кількість типорозмірів у розглядаючому діапазоні зміни головного параметра оптимізації П.

Приведені витрати на виготовлення та експлуатацію силових головок параметричного ряду, що містить типорозмірів , можна записати у вигляді

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

Значення у діапазоні () вибираються не довільно, а відповідно до низки необхідних значень (попиту) типорозмірів Типорозмір із максимальним значенням головного параметра обов’язково присутній у кожному параметричному ряду, тобто

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

Позначимо – мінімум наведених затрат, що відповідають оптимальному ряду із k типорозмірів, для забезпечення попиту в силових головках із параметрами. Оптимальному ряду для діапазону () будуть відповідати затрати . Очевидно, що

(2.5)

Легко знайти рекурентне співвідношення, що зв'язує і для

(2.6)

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

Алгоритм рішення задачі полягає в наступному. На першому кроці визначаються значення за формулою (2.5) для i = 1, 2, 3, ... , М (графа 1а, табл. 2.1). Оптимальний параметричний ряд містить один типорозмір ) (графа 1 б).

Оптимальний ряд із одного типорозміру для діапазону зміни параметра оптимізації (), очевидно, містить типорозмір і йому відповідають затрати .

Таблиця 2.1. Приклад застосування методу динамічного програмування

Типорозмір	№ кроку
	1		2		3
	1 а	1 б	2 а	2 б	3 а	3 б
хі	gі(хі)	П1,і	g2(хі)	П2,і	g3(хі)	П3,і
х1	g1(х1)	х1	-	-	-	-
х2	g2(х2)	х2	g2(х2)	х1	-	-
х3	g3(х3)	х3	g2(х3)	П2+3	g3(х3)	х3
х4	g4(х4)	х4	g2(х4)	П2+4	g3(х4)	П3+4
.	.	.	.	.	.	.
хм	g1(хM)	хМ	g2(хM)	П2, М	g3(хM)	П3,М

Примітка: 1а, 2а, 3а – мінімальні затрати, що відповідає оптимальному ряду із k типорозмірів; 1б, 2б, 3б – параметри силових заготовок розглядаючого ряду.

На другому кроці за формулою (6) визначаються значення значення , і=2, 3, …, М (графа 2а), і значення х_j, за яких досягається мінімум (6) (графа 2б). Ці значення залежать від номера і. Позначимо їх. Оптимальний ряд на другому кроці містить два типорозміри: . Мінімум затрат дорівнює . На третьому кроці знову використовується формула (2.6) і значення мінімальних затрат, отриманих на другому кроці з графи 2а. Значення функцій заносимо в графу 3а, а значення , за яких досягається мінімум функції (6), - у графу 3б. Оптимальний ряд на третьому кроці містить три типорозміри: Розглянемо порядок їх відшукання, користуючись даними табл. 1.

По-перше, останній типорозмір завжди дорівнює максимальному в даному діапазоні: Типорозмір знаходиться в останньому рядку графи 3б таблиці 2.1. Типорозмір і знаходиться в рядку 2б із номером i, для якого . Для отримання оптимального ряду із k типорозмірів необхідно зробити k кроків. Параметри визначаються переглядом даних табл. 2.1 у зворотному порядку, як це зроблено для k = 3. Розрахунок закінчується за отримання на черговому кроці затрат, більших, ніж на попередньому кроці, тобто при k = k_опт для якого .

2.2.3. Метод гілок і меж

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

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

Розглянемо більш чіткий опис методу. Нехай потрібно знайти мінімум f (x), де х G, G - деяка кінцева множина.

Виділимо наступні етапи рішення задачі.

1. На множині планів G визначається нижня оцінка , тобто .

2. Множина планів розбивається на дерево підмножин (розгалужень) за такою схемою:

0-й крок. Множина певним способом розбивається на кінцеву кількість (зазвичай непересічних) підмножин.

-й крок (). Є множини , які ще не піддавались розгалуженню. Вибір найбільш перспективної множини здійснюється за наступним правилом:

Ділимо множину на кінцеву кількість підмножин

,

які заново позначаються через .

3. Перевіряються елементи розбиття. Нехай перевіряється безліч . Воно відсікається в одному з двох випадків: 1) якщо ; 2) якщо і знайдений такий елемент , що причому в 2-му випадку за приймаємо.

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

Цей алгоритм допускає зручне представлення у вигляді дерева варіантів.

Приклад застосування методу гілок і меж для вибору оптимальних структурно-компонувальних схем технологічних систем наведено в [11, С.162-169].