Двоїстість в оптимізаційних задачах

 В  той же час коефіцієнт  дорівнює кількості ресурсу i-го виду, використаного на підтримку j-го виду діяльності;

А мінлива представляє осудні витрати (осудну вартість) одиниці ресурсу i. Таким чином, величина відповідає сумарній вартості всіх ресурсів, необхідних для виробництва j-го виду діяльності.

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

Вартість всіх ресурсів, використаних для виробництва одиниці продукції j-го виду діяльності < Доходу від реалізації одиниці продукції j-го виду діяльності

Таким чином, умова оптимальності, в задачі оптимізації, говорить про те, що прибуток від неї перевищує можливі витрати, що витрачаються на її підтримку[9,13].

3.4 Аналіз стійкості  двоїстих оцінок

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

L max (b1, b2, …, bm).

Теорема. В оптимальному плані двоїстої задачі значення змінної ui чисельно дорівнює частинній похідній функції L max (b1, b2, …, bm) за відповідним аргументом bi:

.

Це означає, що зміна значень величини bi приведе до збільшення або зменшення L max (b1, b2, …, bm) при незмінної |ui| у відповідному оптимальному плані двоїстої задачі.

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

План двоїстої задачі не змінюється для всіх значень bi + Dbi, при яких стовпець вектора Р0 останньої симплекс-таблиці не містить від’ємних чисел, тобто коли серед компонентів вектора немає від’ємних.

 

 

 

 

b1 + Db1

b2 + Db2

…………

bm + Dbm

 

В-1 – матриця, зворотна матриці В, укладеної з компонентів векторів базису, який визначає оптимальний план задачі[13].

3.5 Приклад розв’язування двоїстої задачі графічним методом

За описаними в попередньому параграфі правилами побудуємо двоїсту задачу:

 

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

Двоїста задача має дві змінні, а отже, її можна розв’язати графічно (зображено на рис. 3.1).

Рис. 3.1. Графічний розв’язок двоїстої задачі

 

Найбільшого значення цільова функція двоїстої задачі F досягає в точці В багатокутника ABCD. Її координати визначимо розв’язанням системи рівнянь:

Отже,

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

Підставимо у систему обмежень двоїстої задачі і з’ясуємо, як виконуються обмеження цієї задачі:

Оскільки перше обмеження для оптимального плану двоїстої задачі виконується як строга нерівність, то перша змінна прямої задачі дорівнюватиме нулю (перша частина теореми двоїстості).

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

Об’єднуючи здобуту інформацію, можна записати систему обмежень прямої задачі як систему двох рівнянь, в якій , та визначити решту змінних:

тобто

Умова виконується, і тому є оптимальними планами відповідно прямої та двоїстої задачі[6].

 

 

 

 

 

 

 

 

 

 

 

 

 

РОЗДІЛ 4

ПРАКТИЧНА РЕАЛІЗАЦІЯ ЗАДАЧІ ОПТИМАЛЬНОГО РОЗПОДІЛУ РЕСУРСІВ ІЗ ЗАСТОСУВАННЯМ ТЕОРІЇ ДВОЇСТОСТІ

4.1 Економіко-математична постановка задачі оптимального розподілу ресурсів

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

Для виготовлення трьох видів пива: «Львівське», «Оболонь» та «Балтика» використовують три різні види сировини: дріжджі, хміль та солод. Кожен з видів сировини може бути використаний в кількості, не більшій ніж 180, 210 та 244 кг відповідно. Норми витрат кожного з видів сировини на одиницю продукції даного виду та ціна одиниці продукції кожного з видів наведені в таблиці 4.1.

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

Таблиця 4.1

Норми затрат сировини на одиницю продукції

Вид сировини	«Львівське»	«Оболонь»	«Балтика»
Дріжджі	4	2	1
Хміль	3	1	3
Солод	1	2	5
Ціна одиниці продукції(грн)	10	14	12

 

Нехай виготовляють х1 виробів «Львівське», х2 виробів «Оболонь» та х3 виробів «Балтика». Для визначення оптимального плану виробництва потрібно розв’язати задачу на максимізацію цільової функції

F=10 х1+14 х2+12 х3,

при таких умовах:                     

                                                           

Припишемо до кожного з видів сировини двоїсту оцінку, яка відповідно дорівнює . Тоді загальна оцінка сировини, яка йде на виготовлення продукції, становитиме:

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

 

Отримали симетричну пару двоїстих задач. Розв’язання прямої задачі дає оптимальний план виготовлення виробів «Львівське», «Оболонь» та «Балтика», а розв’язання двоїстої – оптимальну систему оцінок сировини, яка використовується для виготовлення цих виробів. Щоб розв’язати ці задачі, необхідно спочатку знайти розв’язок однієї з них. Розв’яжемо пряму задачу (її система обмежень містить лише нерівності виду « »). Її розв’язання наведено в таблиці 4.2.

 

 

 

 

Таблиця 4.2

Остання симплексна таблиця із оптимальним планом

 

і	Базис	Сб	Х0	10	14	12	0	0	0
				х1	х2	х3	х4	х5	х6
1	х2	14	82		1	0		0
2	х5	0	80		0	0		1
3	х3	12	16		0	1		0
			1340		0	0		0

 

З даної таблиці видно, що оптимальним планом виготовлення виробів є такий план, при якому виготовляються 82 виробів «Оболонь» та 16 виробів «Балтика». В цьому випадку залишається невикористаним 80 кг хмелю, а загальна вартість виробів дорівнює 1340 грн. З таблиці 4.2 також видно, що оптимальний розв’язок двоїстої задачі має вигляд:  Змінні та є умовними двоїстими оцінками сировини, дріжджів та солоду відповідно. Ці оцінки відмінні від нуля, а сировина дріжджі і солод повністю використовується при оптимальному плані виготовлення продукції. Двоїста оцінка одиниці хмелю дорівнює нулю. Цей вид сировини не повністю використовується при оптимальному плані виробництва продукції.

Таким чином, додатну двоїсту оцінку мають лише ті види сировини, які повністю використовуються при оптимальному плані виробництва продукції. Тому двоїсті оцінки визначають дефіцитність сировини що використовує підприємство. Більш того, величина даної двоїстої оцінки показує, на скільки зростає максимальне значення цільової функції прямої задачі при збільшенні кількості сировини відповідного виду на 1 кг. Так, збільшення кількості дріжджів на 1 кг призведе до появи можливості знайти новий оптимальний план виготовлення виробів, при якому загальна вартість виготовленої продукції зросте на 5,75 грн і становитиме 1340+5,75=1345,75 грн. При цьому числа, що стоять в стовпці вектора х4 наведено в (табл. 4.2), показують, що таке збільшення загальної вартості виготовленої продукції може бути досягнуто за рахунок збільшення випуску пива «Оболонь» на од. та скорочення випуску пива «Балтика» на од. Внаслідок цього використання хмелю зменшиться на кг. Аналогічно, збільшення на 1 кг солоду дозволить знайти новий оптимальний план виготовлення виробів, при якому загальна вартість виготовленої продукції зросте на 1,25 грн і становитиме 1340+1,25=1341,25 грн. Це буде досягнуто внаслідок збільшення випуску пива «Балтика» на од. та зменшенні виготовлення пива «Оболонь» на од., причому об’єм хмелю зросте на кг.

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

При підстановці оптимальних двоїстих оцінок в систему обмежень двоїстої задачі матимемо:

Перше обмеження двоїстої задачі виконується як строга нерівність. Це означає, що двоїста оцінка сировини, що йде на виготовлення одного виробу «Львівське», вища ціни цього виробу, отже, випускати ці вироби невигідно. Його виготовлення й непередбачено оптимальним планом прямої задачі. Друге й третє обмеження двоїстої задачі виконуються як строгі рівності. Це означає, що двоїста оцінка сировини, що використовується для виготовлення пива «Оболонь» та «Балтика» відповідно, дорівнюють їх цінам. Тому випускати ці два види продукції по двоїстим оцінкам економічно вигідно. Їх виготовлення й передбачено оптимальним планом прямої задачі.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.2 Програмна реалізація розв’язку задачі оптимального розподілу ресурсів в середовищі MS Excel

Розв’язок поставленої вище задачі можливо здійснити за допомогою програмного пакету MS EXCEL:         Умови задачі оптимального розподілу ресурсів зображено на рис. 4.1. 

 

 

Рис. 4.1. Умова задачі оптимального розподілу ресурсів

Згідно з умовою змінні значення позначені наступним чином:

B1: D1 – вид продукції;  
A2: A4 – вид ресурсу;  
B2: D4 - витрати ресурсів на одиницю продукції;  
B6: D6 - ціни на продукцію;  
B8: D8 - змінні;  
F2: F4 - запас ресурсів;  
G6 - значення цільової функції. 

 

 

Для того, щоб записати двоїсту задачу до даної потрібно перезаписати умову, як зображено на рис. 4.2.

 
Рис. 4.2. Умова двоїстої задачі

Для того щоб розв’язати дану задачу потрібно встановити курсор на клітинку цільової функції, тобто G4. У головному меню вибрати надстройку під назвою «пошук рішення». Виконавши цю операцію на екрані з’являється вікно, в якому потрібно вказати наступні позначення:

1. Цільова комірка – G4;  
2. Включити кнопку «мінімальне значення»;  
3. Вказати змінювані клітинки (розташування змінних) - $B$2:$D$2;  
4. Записати обмеження.

Обмеження можна записати в цьому ж вікні, але краще вибрати кнопку «додати» і у вікні «додати» записати їх послідовно. Одне обмеження на невід’ємність зміних:

$B$2:$D$2>=0,

а також три обмеження, що свідчать про те, що витрати не можуть бути більшими ніж запаси, що є у наявності:                                   

$G$6>=$F$6,

$G$7>=$F$7,

$G$8>=$F$8.

Приклад запису параметрів «пошуку рішень» зображений на рис. 4.3.

Рис.4.3. Параметри «пошуку рішень»

Тепер електронна модель сформована і можна розв’язувати задачу. Для цього потрібно повернутися до вікна «пошук рішення» і натиснути «виконати». Якщо електронна модель сформована правильно, то буде отримано повідомлення, що завдання виконане. Результат розв’язку

знаходиться на аркуші EXCEL (див. рис. 4.4.).

Рис. 4.4. Результати розв’язку задачі

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