Пряме та двоїсте завдання лінійного програмування. Розв'язання двоїстої задачі Розв'язання симетричних двоїстих задач

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

Зміст

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

Симетричне двоїсте завдання

Розглянемо задачу лінійного програмування з невід'ємними змінними та нерівностями системи обмежень наступного виду:
(1.1) ;
(1.2)
Тут є деякі числа. Усі рядки системи (1.2) є нерівностями зі знаками .

(2.1) ;
(2.2)
Тут усі рядки системи (2.2) є нерівностями зі знаками . Матриця коефіцієнтів системи обмежень (2.2) є матрицею транспонованої системи (1.2). Вона містить рядків та стовпців. Подвійне завдання має змінних. Усі змінні невід'ємні.

Вихідне завдання (1) часто називають прямим завданням, а завдання (2) - двоїстим. Якщо за вихідну взяти задачу (2), то завдання (2) буде пряме завдання, а завдання (1) - двоїсте. Завдання (1) та (2) називаються симетричними двоїстими завданнями.

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

Приклад складання симетричної двоїстої задачі

;

Вихідне завдання є завданням перебування мінімуму. Тому всі нерівності повинні мати знаки. Перша і третя нерівності містять знак. Помножимо їх на -1 :

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

Подвійне завдання має вигляд:
;

;

Несиметричне двоїсте завдання

Завдання на максимум

Розглянемо канонічну задачу лінійного програмування на максимум з невід'ємними змінними та рівностями системи обмежень:
(3.1) ;
(3.2)
Тут є деякі числа. Усі рядки системи (3.2) є рівностями. Усі змінні є невід'ємними.

Подвійне завдання має вигляд:
(4.1) ;
(4.2)
Тут усі рядки системи (4.2) є нерівностями зі знаками . Матриця коефіцієнтів системи обмежень (4.2) є транспонованою матрицею системи (3.2). Подвійне завдання має змінних. Змінні може бути як позитивними, і негативними.

Відмінність несиметричної пари завдань (3) і (4) від симетричної пари (1) і (2) у цьому, що система обмежень (3.2) містить лише рівності, а системі (4.2) відсутні умови неотрицательности змінних.

Завдання на мінімум

Тепер розглянемо канонічне завдання лінійного програмування на мінімум:
(5.1) ;
(5.2)

Подвійне завдання має вигляд:
(6.1) ;
(6.2)

Система обмежень (6.2) відрізняється (4.2) тим, що нерівності мають знаки .

Зв'язок із симетричною парою двоїстих завдань

Покажемо, що несиметричну пару задач (3)-(4) можна одержати із симетричної пари (1)-(2).

Отже, нехай ми маємо пряме завдання із цільовою функцією
(3.1)
та системою обмежень
(3.2)
Кожну рівність можна уявити двома нерівностями:

Нерівності зі знаками помножимо на -1 :

Система обмежень має нерівностей.

За формулами (1)-(2) отримуємо подвійне завдання:
;


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

Зробимо підстановки
.
Оскільки і то змінні можуть бути як позитивними, так і негативними.

І ми отримуємо подвійне завдання (4):
(4.1) ;
(4.2)

Якщо ми за вихідне завдання візьмемо (4), то, виконуючи всі дії у зворотному порядку, отримаємо подвійне завдання (3).

У такий же спосіб можна із завдання (5) отримати подвійне завдання (6) та із завдання (6) отримати подвійне завдання (5).

Змішане завдання

Тепер розглянемо змішане завдання.

Нехай ми маємо пряме завдання (1) на максимум, в системі обмежень якої рядок є рівністю. Тоді двояке завдання має вигляд (2) за одним винятком - змінна може бути як позитивною, так і негативною. Тобто відсутнє обмеження.

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

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

І нарешті, нехай ми маємо пряме завдання (2) на мінімум, але немає обмеження . Тоді двояке завдання має вигляд (1) за одним винятком - рядок системи обмежень є рівністю.

Усе це дозволяє сформулювати правила складання двоїстих завдань.

Правила складання двоїстих завдань

1. Для вихідного завдання на максимум, всі нерівності системи обмежень приводимо до вигляду:
.
Для вихідного завдання на мінімум, усі нерівності наводимо до вигляду:
.
Якщо потрібно змінити знак, то множимо обидві частини нерівностей на -1 .
2. Складаємо подвійне завдання тим самим способом, як симетричної пари завдань.
3. Якщо у вихідному завданні, рядок системи обмежень є рівністю, то викреслюємо умову невід'ємності змінної двоїстої задачі.
4. Якщо у вихідному завданні, відсутня умова невід'ємності для -ї змінної, то в -му рядку двоїстої задачі змінюємо знак нерівності на знак рівності.

Приклад складання змішаної двоїстої задачі

Дана задача лінійного програмування:
;

Скласти подвійне завдання.

Цільова функція має вільний член 5. Щоб привести її до вигляду (2.1), введемо змінну та додамо рівність . Тоді завдання набуде вигляду:

;

Це завдання є завданням на перебування мінімуму. Тому всі нерівності повинні мати знаки. Третя нерівність містить знак. Тому помножимо його на -1 :

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

Матриця коефіцієнтів системи обмежень має вигляд:

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

Складемо подвійне завдання як для симетричної пари.
;

Оскільки у вихідному завданні 1, 2 і 4-й рядок системи обмежень є рівностями, то в подвійному завданні змінні і можуть мати будь-який знак. Невід'ємною змінною є лише . Тому умови невід'ємності змінних мають вигляд:
.

Оскільки у вихідному завданні змінні і можуть мати довільні знаки, то 3-й та 4-й рядки системи обмежень двоїстої задачі є рівностями.

Таким чином, двояке завдання має вигляд:
;

З четвертого рівняння. Замінимо змінну її значенням і помножимо третій рядок на -1 .

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

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

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

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

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

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

Вирішення прямої задачі про оптимальну виробничу програму

Враховуючи високий рівень математичної підготовки переважної більшості користувачів даного ресурсу не наводитиму балансові рівняння з верхніми та нижніми обмеженнями та введенням для переходу до рівностей додаткових змінних. Тому відразу наведу позначення змінних, що використовуються у рішенні:
N – кількість видів виробів;
m-кількість видів використовуваної сировини;
b_ub - вектор наявних ресурсів розмірності m;
A_ub – матриця розмірності m×N, кожен елемент якої є витратою ресурсу виду i виробництва одиниці виробу виду j;
з - вектор прибутку від виробництва одиниці виробу кожного виду;
x – шукані обсяги виробів кожного виду (оптимальний план виробництва) що забезпечують максимальний прибуток.

Функція мети
maxF(x)=c×x

Обмеження
A×x≤b

Чисельні значення змінних:
N=5; m=4; b_ub =; A_ub = [, , ,]; c =.

Завдання
1.Знайти x для забезпечення максимального прибутку
2. Знайти використані ресурси під час виконання п.1
3. Знайти залишки ресурсів (якщо вони є) під час виконання п.1

Для визначення максимуму (за замовчуванням визначається мінімум коефіцієнти цільової функції потрібно записати з негативним знаком c = [-25, -35, -25, -40, -30] та проігнорувати знак мінус перед прибутком.

Використання при виведенні результатів позначення:
x- Масив значень змінних, що доставляють мінімум (максимум) цільової функції;
slack- Значення додаткових змінних. Кожна змінна відповідає обмеженню-нерівності. Нульове значення змінної означає, що відповідне обмеження є активно;
success- True, якщо функції вдалося знайти оптимальне рішення;
status- Статус рішення:
0 - пошук оптимального рішення завершився успішно;
1 – досягнуто ліміт на кількість ітерацій;
2 – завдання немає рішень;
3 – цільова функція не обмежена.
nit– кількість зроблених ітерацій.

Лістинг вирішення прямої задачі оптимізації

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog # завантаження бібліотеки ЛП c = [-25, -35,-25,-40,-30] # список коефіцієнтів функції мети b_ub = # список обсягів ресурсів A_ub = [, # матриця питомих значень ресурсів , , ] d=linprog(c, A_ub, b_ub) # пошук рішення for key,val in d.items(): print(key ,val) # висновок рішення if key=="x": q=#використані ресурси print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array(q) #залишки ресурсів print(" b_ub-A_ub*x", q1)

Результати розв'язання задачі
nit 3
status 0

success True
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [ 0. 0. 0. 90.90909091]
fun -5863.63636364
slack [ 0. 0. 0. 90.90909091]

Висновки

1. Знайдено оптимальний план за видами продукції
2. Знайдено фактичне використання ресурсів
3. Знайдено залишок не використаного четвертого виду ресурсу [ 0. 0 0.0 0.0 90.909]
4. Немає потреби у обчисленнях за п.3, тому що той же результат виводити в змінній slack

Вирішення двоїстої задачі про оптимальну виробничу програму

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

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

C - Вектор наявних ресурсів;
b_ub - Вектор прибутку від виробництва одиниці виробу кожного виду;
A_ub_T - транспонована матриця A_ub.

Функція мети
minF(x)=c×x

Обмеження
A_ub_T ×x≥ b_ub

Чисельні значення та співвідношення для змінних:
з =; A_ub_T transpose(A_ub); b_ub =.

Завдання:
Знайти x показує цінність виробника кожного виду ресурсів.

Особливості рішення з бібліотекою scipy. optimize
Для заміни обмежень згори на обмеження з низу необхідно помножити на мінус одиницю обидві частини обмеження – A_ub_T ×x≥ b_ub… Для цього вихідні дані записати у вигляді: b_ub = [-25, -35,-25,-40,-30]; A_ub_T = - scipy.transpose(A_ub).

Лістинг розв'язання двоїстої задачі оптимізації

#!/usr/bin/python # -*- coding: utf-8 -*- import scipy from scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,- 40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) для key,val in d.items(): print(key,val)

Результати розв'язання задачі
nit 7
Message Optimization виконано успішно.
fun 5863.63636364
x [2.27272727 1.81818182 6.36363636 0.]
slack [ 5.45454545 2.27272727 0. 0. 0. ]
status 0
success True

Висновки

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

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

1. Подвійне завдання розширює можливості планування випуску продукції, але засобами scipy. optimize вирішується за вдвічі більшу за пряму кількість ітерацій.
2. Змінна slack виводить інформацію про активність обмежень у вигляді нерівностей, які можуть бути використані, наприклад, для аналізу залишків сировини.
3. Пряме завдання є завданням максимізації, а подвійне - завданням мінімізації, і навпаки.
4. p align="justify"> Коефіцієнти функції мети в прямій задачі є обмеженнями в двоїстій задачі.
5. Обмеження у прямій задачі стають коефіцієнтами функції мети у подвійній.
6. Знаки нерівностей в обмеженнях змінюються протилежними.
7. Матриця системи рівностей транспонується.

Посилання

За допомогою цього онлайн-калькулятора можна отримати:

• вирішення двоїстої задачі лінійного програмування через розв'язання прямої задачі (симплексним методом, за теоремою двоїстості);
• оптимальний план двоїстої задачі; оцінки ресурсів (подвійні оцінки);
• визначення дефіцитних та недефіцитних (надлишкових) ресурсів;
• зміна цільової функції за зміни параметрів; обґрунтування ефективності оптимального плану;
• аналіз стійкості двоїстих оцінок (гранична зміна b i, c i); аналіз субоптимальних варіантів плану

Інструкція. Виберіть кількість змінних та кількість обмежень прямого завдання лінійного програмування, натисніть Далі. Отримане рішення зберігається у файлі Word та Excel. При цьому обмеження типу x i ≥ 0не враховуйте. Якщо пряме завдання ЛП не має рішення, але потрібно скласти двоїсте завданняабо одна зі змінних x i невизначена, можна використовувати цей калькулятор .

Основна ідея теорії двоїстості: для кожної задачі лінійного програмування (ЛП) існує деяка задача ЛП, вирішення якої тісно пов'язане з прямим. При цьому:

• матриця обмежень двоїстої задачі (ДЗ) є транспонована матриця прямої задачі;
• Вектор "цін" для прямої задачі є вектор правих частин обмежень задачі ДЗ і навпаки.

Загальні правила складання двоїстої задачі ():

Пряма	Подвійна
Цільова функція (max)	Права частина обмежень
Права частина обмежень	Цільова функція (min)
A – матриця обмежень	A T - матриця обмежень
i-е обмеження: ≤ 0, (≥ 0)	Змінна y i ≥ 0, (≤ 0)
i-е обмеження: = 0	Змінна y i ≠ 0
Змінна x j ≥ 0 (≤ 0)	j-е обмеження: ≤ 0 (≥ 0)
Змінна x j ≠ 0	j-е обмеження: = 0

Приклад. Визначимо максимальне значення цільової функції F(X) = 3x1+5x2+4x3 за наступних умов-обмежень.
0.1x 1 + 0.2x 2 + 0.4x 3 ≤1100
0.05x 1 + 0.02x 2 + 0.02x 3 ≤120
3x 1 + x 2 + 2x 3 ≤8000

Вирішимо пряме завдання симплексним методом.
Для побудови першого опорного плану систему нерівностей наведемо до системи рівнянь шляхом запровадження додаткових змінних.
0.1x 1 + 0.2x 2 + 0.4x 3 + 1x 4 + 0x 5 + 0x 6 = 1100
0.05x1+0.02x2+0.02x3+0x4+1x5+0x6=120
3x 1 + 1x 2 + 2x 3 + 0x 4 + 0x 5 + 1x 6 = 8000
Базисні змінні це змінні, які входять лише одне рівняння системи обмежень і до того ж з одиничним коефіцієнтом.
Розв'яжемо систему рівнянь щодо базисних змінних: x 4 , x 5 , x 6
Вважаючи, що вільні змінні дорівнюють 0, отримаємо перший опорний план: X1 = (0,0,0,1100,120,8000)
Оскільки завдання вирішується на максимум, то провідний стовпець вибирають за максимальним негативним числом та індексним рядком. Всі перетворення проводять доти, доки не вийдуть в індексному рядку позитивні елементи.
Переходимо до основного алгоритму симплекс-метода.

План	Базис	У	x 1	x 2	x 3	x 4	x 5	x 6	min
1	x 4	1100	0.1	0.2	0.4	1	0	0	5500
	x 5	120	0.05	0.02	0.02	0	1	0	6000
	x 6	8000	3	1	2	0	0	1	8000
Індексний рядок	F(X1)	0	-3	-5	-4	0	0	0	0

Ітерація №0
Поточний опорний план неоптимальний, оскільки в індексному рядку є негативні коефіцієнти
Як ведучий виберемо стовпець, відповідний змінної x 2 так як найбільший коефіцієнт по модулю.
Отже, перший рядок є провідним. Роздільний елемент дорівнює 0.2 і знаходиться на перетині провідного стовпця та провідного рядка. Формуємо наступну частину сімплексної таблиці. Замість змінної x до плану 1 увійде змінна x 2 . Рядок, що відповідає змінній x 2 у плані 1, отримана в результаті поділу всіх елементів рядка x 4 плану 0 на роздільну здатність елемент РЕ=0.2. На місці роздільного елемента в плані 1 отримуємо 1. >В інших клітинах стовпця x 2 плану 1 записуємо нулі.
Таким чином, у новому плані 1 заповнені рядок х 2 і стовпець х 2 .
Решта всіх елементів нового плану 1, включаючи елементи індексного рядка, визначаються за правилом прямокутника .
Для цього вибираємо зі старого плану чотири числа, які розташовані у вершинах прямокутника і завжди включають роздільну здатність елемент РЕ.
НЕ = СЕ - (А * В) / РЕ
СТЕ - елемент старого плану, РЕ - роздільна здатність елемент (0.2), А і В - елементи старого плану, що утворюють прямокутник з елементами СТЕ і РЕ.

План	Базис	У	x 1	x 2	x 3	x 4	x 5	x 6	min
2	x 2	5500	0.5	1	2	5	0	0	11000
	x 5	10	0.04	0	-0.02	-0.1	1	0	250
	x 6	2500	2.5	0	0	-5	0	1	1000
Індексний рядок	F(X2)	27500	-0.5	0	6	25	0	0	0

Ітерація №1
Поточний опорний план неоптимальний, оскільки в індексному рядку є негативні коефіцієнти. Як ведучий виберемо стовпець, відповідний змінної x 1, оскільки найбільший коефіцієнт по модулю.
Обчислимо значення D i за рядками як окреме від поділу і з них виберемо найменше:
Отже, другий рядок є провідним. Роздільний елемент дорівнює 0.04 і знаходиться на перетині провідного стовпця та провідного рядка. Формуємо наступну частину сімплексної таблиці. Замість змінної x до плану 2 увійде змінна x 1 . Рядок, відповідна змінної x 1 у плані 2, отримана в результаті розподілу всіх елементів рядка x 5 плану 1 на роздільну здатність елемент РЕ=0.04. На місці роздільного елемента в плані 2 отримуємо 1. В інших клітинах стовпця x 1 плану 2 записуємо нулі.
Таким чином, у новому плані 2 заповнені рядок х 1 і стовпець х 1 .
Решта всіх елементів нового плану 2, включаючи елементи індексного рядка, визначаються за правилом прямокутника.
Уявимо розрахунок кожного елемента у вигляді таблиці:

Приклад №2. Для виконання завдання необхідно, щоб одночасно злетіли 50 АК I-го виду, 30 АК 2-го виду та 45 АК 3-го виду. АК розташовані на аеродромах І та ІІ. У таблиці представлений середній час зльоту (в секундах) з відповідного аеродрому одного АК даного типу.

Номер аеродрому	Тип АК
	1	2	3
I	4	10	10
II	6	8	20

Як розмістити АК по аеродромах, щоб час послідовного зльоту всього наряду АК був мінімальним? Наскільки можна змінити час зльоту кожного АК, щоб у своїй оптимальне рішення залишилося колишнім.

Рішення. Позначимо через:
x 11 - АК 1-го типу на першому аеродромі,
x 12 - АК 1-го типу на другому аеродромі,
x 21 - АК 2-го типу на першому аеродромі,
x 22 - АК 2-го типу на другому аеродромі,
x 31 - АК 3-го типу на першому аеродромі,
x 32 - АК 3-го типу на другому аеродромі,

Обмеження
4x 11 + 6x 12 = 50
10x 21 + 8x 22 = 30
10x 31 + 20x 32 = 45
x 11, x 12, x 21, x 22, x 31, x 32 ≥ 0
x 11, x 12, x 21, x 22, x 31, x 32 -цілі числа

Цільова функція
4x 11 + 6x 12 + 10x 21 + 8x 22 +10x 31 + 20x 32 → min

Після знайденого рішення, відповіддю на перше запитання будуть значення змінних x 11 x 12 x 21 x 22 x 31 x 32 . Інформація про відповідь на друге питання буде розміщена у розділі Інтервали стійкості коефіцієнтів цільової функції.

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

Теорема 1 (Перша теорема двоїстості). Якщо одне із взаємно двоїстих завдань має оптимальне рішення, то його має і

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

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

Примітка:твердження, протилежне до другої частини першої теореми двоїстості, у випадку неправильно.

Теорема 2. Компоненти оптимального плану двоїстої задачі ( володіють умовою невід'ємності) рівні абсолютним значенням коефіцієнтів

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

Теорема 3. Позитивним (ненульовим) компонентам оптимального вирішення одного із завдань симетричної двоїстої паривідповідають нульові компоненти оптимального розв'язання іншого завдання, тобто. для будь-яких та :

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

. (7.2)

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

Приклад 9.1.На основі рішення прикладу 5.2 (файл «Алгоритм та приклади симплекс-метода») визначимо двоїстим симплекс-методом оптимальне рішення двоїстої задачі.

Вихідне завдання	Подвійне завдання

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

Вихідне завдання	Подвійне завдання

Встановимо відповідність між змінними взаємно двоїстими завданнями.

За підсумками рішення прикладу 5.2. симплекс-таблиця останньої ітерації (таблиця 5.10) має вигляд:

Таблиця 9.3

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

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

Отже, , .

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

Відповідно до теореми 1, .

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

Приклад 9.2.На основі вирішення вихідної задачі знайти оптимальне рішення двоїстої задачі використовуючи подвійний симплекс-метод.

Вихідне завдання	Подвійне завдання

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

Вихідне завдання	Подвійне завдання

Для встановлення відповідності змінних двоїстої пари введемо у вихідне завдання дві відсутні фіктивні змінні.

Вихідне завдання	Подвійне завдання

Встановимо відповідність між змінними взаємно двоїстими завданнями.

Таблиця 9.4

Відповідність змінних двоїстої пари

Вирішимо вихідне завдання симплекс-методом.

Використовуючи метод Жордана-Гаусса, виділимо в системі обмежень вихідного завдання як базисні змінні та ( примітка:не використовувати як базові фіктивні змінні).

В результаті перетворень отримаємо наступну матрицю коефіцієнтів:

.

Система обмежень вихідного завдання набуде наступного вигляду:

Виразимо базисні змінні через вільні, в результаті вихідне завдання набуде наступного вигляду:

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

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

Таблиця 9.5

Симплекс-таблиця оптимального вирішення вихідного завдання

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

за умов

(33)

(34)

Визначення 1.Завдання, яке полягає у знаходженні мінімального значення функції

за умов

(36)

(37)

називається подвійною запо відношенню до завдання (32) - (34). Завдання (32) – (34) та (35) – (37) утворюють пару завдань, які називаються в лінійному програмуванні двоїстою парою.Порівнюючи дві сформульовані завдання, бачимо, що двояке завдання складається відповідно до таких правил:

1. Цільова функція вихідного завдання (32) – (34) задається максимум, а цільова функція двоїстої (35) – (37) – мінімум.

2. Матриця

(38)

складена з коефіцієнтів при невідомих у системі обмежень (33) вихідного завдання (32) – (34), та аналогічна матриця

(39)

у двоїстої задачі (35) – (37) виходять друг з друга транспонуванням (тобто. заміною рядків стовпцями, а стовпців – рядками).

3. Число змінних у подвійному завданні (35) – (37) дорівнює числу обмежень у системі (33) вихідної задачі (32) – (34), а кількість обмежень у системі (36) двоїстої задачі – числу змінних у вихідному завданні.

4. Коефіцієнтами при невідомих у цільовій функції (35) двоїстої задачі (35) – (37) є вільні члени в системі (33) вихідної задачі (32) – (34), а правими частинами у співвідношеннях системи (36) двоїстої задачі – коефіцієнти при невідомих цільовій функції (32) вихідної задачі.

5. Якщо змінна x jвихідного завдання (32) – (34) може набувати лише позитивних значень, то j–е умова у системі (36) двоїстої завдання (35) – (37) є нерівністю виду “? ”. Якщо ж змінна x jможе приймати як позитивні, і негативні значення, то 1 – співвідношення в системі (54) є рівнянням. Аналогічні зв'язки мають місце між обмеженнями (33) вихідного завдання (32) – (34) та змінними двоїстого завдання (35) – (37). Якщо i- Співвідношення в системі (33) вихідного завдання є нерівністю, то i-я змінна двоїстої задачі. В іншому випадку змінна у j може приймати як позитивні, і негативні значення.

Подвійні пари завдань зазвичай поділяють на симетричні та несиметричні. У симетричній парі двоїстих завдань обмеження (33) прямої задачі та співвідношення (36) двоїстої задачі є нерівностями виду “ ”. Таким чином, змінні обох завдань можуть приймати тільки невід'ємні значення.

приклад 1.Скласти подвійне завдання стосовно завдання, що полягає у максимізації функції

(40)

за умов

(41)

Рішення.Для цього завдання

і

Число змінних у двоїстої задачі дорівнює числу рівнянь у системі (41), тобто дорівнює трьом. Коефіцієнтами цільової функції двоїстої завдання є вільні члени системи рівнянь (41), тобто. числа 12, 24, 18

Цільова функція вихідного завдання (40) – (42) досліджується на максимум, а система умов (41) містить лише рівняння. Тому в двоїстої задачі цільова функція досліджується на мінімум, а її змінні можуть набувати будь-яких значень (у тому числі й негативних). Оскільки всі три змінні вихідної задачі (40) – (42) приймають лише невід'ємні значення, то системі умов двоїстої завдання мають бути три нерівності виду “? ”. Отже, для задачі (40) – (42) подвійне завдання таке: знайти мінімум функції за умов

приклад 2.Для завдання, що полягає у максимізації функції

за умов

сформулювати подвійне завдання.

Рішення.Для цього завдання

,

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

Зв'язок між рішеннями прямої та двоїстої задач

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

за умов

(44)

Подвійне завдання: знайти мінімум функції

за умов

(47)

Кожне із завдань двоїстої пари (43) - (45) і (46), (47) фактично є самостійним завданням лінійного програмування і може бути вирішена незалежно одна від одної. Проте щодо оптимального плану однієї із завдань цим перебуває рішення й іншого завдання.

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

Лемма 1.Якщо Х – деякий план вихідної задачі (43) – (45), Y – довільний план двоїстої задачі (46), (47), то значення цільової функції вихідної задачі при плані Х завжди не перевищує значення цільової функції двоїстої задачі при плані Y, тобто.

Лемма 2.Якщо деяких планів X * і Y * завдань (43) – (45) і (46), (47), то X * – оптимальний план вихідної завдання, а Y * – оптимальний план двоїстої задачі.

Теорема 8(Перша теорема двоїстості). Якщо одне із завдань двоїстої пари (43) – (45) чи (46), (47) має оптимальний план, те й інша має оптимальний план і значення цільових функцій завдань за їх оптимальних планах рівні між собою, тобто.

Якщо ж цільова функція однієї задачі з двоїстої пари необмежена (для вихідної (43) - (45) - зверху, для двоїстої (46), (47) - знизу), то інше завдання взагалі не має планів.

Теорема 9(Друга теорема двоїстості). План завдання (43) – (45) та план Завдання (46), (47) є оптимальними планами цих завдань тоді і тільки тоді, коли для будь-якого виконується рівність

Геометрична інтерпретація двоїстих завдань

Якщо кількість змінних у прямій і двоїстої задачах, що утворюють цю пару, дорівнює двом, то, використовуючи геометричну інтерпретацію задачі лінійного програмування, можна легко знайти розв'язання цієї пари задач. При цьому має місце один із наступних трьох випадків, що взаємно виключають один одного: 1) обидві завдання мають плани; 2) плани має лише одне завдання; 3) кожному за завдання двоїстої пари безліч планів порожньо.

приклад 3.

скласти двоїсте завдання та знайти рішення обох завдань.

Рішення.Двоїм завданням стосовно вихідної є завдання, що полягає у визначенні мінімального значення функції за умов

Як у вихідній, і у двоїстої задачі число невідомих дорівнює двом. Отже, їх вирішення можна знайти, використовуючи геометричну інтерпретацію задачі лінійного програмування (рис. 7 та 8).

Як видно із рис. 8, максимальне значення цільова функція вихідної задачі приймає у точці Ст.Отже, Х * =(2, 6) є оптимальним планом, за якого . Мінімальне значення цільова функція двоїстої задачі набуває в точці Е(Рис. 8). Значить, Y* =(1; 4) є оптимальним планом двоїстої задачі, при якому Таким чином, значення цільових функцій вихідної та двоїстої задач при їх оптимальних планах рівні між собою.

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

приклад 4.

Знайти рішення двоїстої пари завдань.

Вихідне завдання;

Подвійне завдання:

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

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

Знаходження рішення двоїстих завдань. Розглянемо пару двоїстих завдань – основне завдання лінійного програмування (43) – (45) та двоїсте до неї завдання (46), (47).

Припустимо, що за допомогою симплексного методу знайдено оптимальний план X *Завдання (43) - (45) і цей план визначається базисом, освіченим .

Позначимо через вектор-рядок, складений з коефіцієнтів при невідомих у цільовій функції (43) задачі (43) – (45), а через – матрицю, зворотну матриці Рскладені з компонентів вектор базису. Тоді має місце таке твердження.

Теорема 10.Якщо основне завдання лінійного програмування має оптимальний план X * , є оптимальним планом двоїстої задачі.

Таким чином, якщо знайти симплексним методом оптимальний план задачі (43) - (45), то, використовуючи останню симплекс-таблицю, можна визначити і за допомогою співвідношення знайти оптимальний план двоїстої задачі (46), (47).

У тому випадку, коли серед векторів , складених з коефіцієнтів за невідомих у системі рівнянь (44), є тодиничних, вказану матрицю утворюють числа перших трядків останньої симплекс-таблиці, що стоять у стовпцях даних векторів.Тоді немає необхідності визначати оптимальний план двоїстої задачі множенням на , оскільки компоненти цього плану збігаються з відповідними елементами ( m+1)–й рядки стовпців одиничних векторів, якщо даний коефіцієнт , і дорівнюють сумі відповідного елемента цього рядка і якщо

Сказане вище має місце й у симетричної пари двоїстих завдань. У цьому оскільки система обмежень вихідної завдання містить нерівності виду “ ”, то компоненти оптимального плану двоїстої завдання збігаються з відповідними числами ( m+1)-й рядки останньої симплекс-таблиці вирішення вихідної задачі. Зазначені числа стоять у стовпцях векторів, що відповідають додатковим змінним.

приклад 15.Для завдання, що полягає у визначенні максимального значення функції за умов

скласти двоїсте завдання та знайти її рішення.

Рішення.Подвійне завдання стосовно вихідної полягає у знаходженні мінімуму функції за умов

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

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

Таблиця 12

i	Базис	З б	p 0	1	2	-1	0	0	-M
				p 1	p 2	p 3	p 4	p 5	p 6
1 2 3 4 5 1 2 3 4 1 2 3 4	p4 p5 p6 P4 p5 p1 P2 p5 p1	0 0 -M 0 0 1 2 0 1	12 17 4 0 -4 14 15 2 2 4 9 4 12	-1 1 2 -1 -2 0 0 1 0 0 0 1 0	4 1 -1 -2 1 7/2 3/2 -1/2 -5/2 1 0 0 0	-2 2 2 1 -2 -1 1 1 2 -2/7 13/7 6/7 9/7	1 0 0 0 0 1 0 0 0 2/7 -3/7 1/7 5/7	0 1 0 0 0 0 1 0 0 0 1 0 0	0 0 1 0 0 1/2 -1/2 1/2 1/2 1/7 -5/7 4/7 6/7

Економічна інтерпретація двоїстих завдань

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

Приклад 6.Для виробництва трьох видів виробів А ,Уі Звикористовується три різні види сировини. Кожен із видів сировини може бути використаний у кількості, відповідно не більшій за 180, 210 і 244 кг. Норми витрат кожного з видів сировини на одиницю продукції даного виду та ціна одиниці продукції кожного виду наведено у таблиці 13.

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

Таблиця 13

Вид сировини	Норми витрат сировини (кг) на одиницю продукції
Ціна одиниці виробленої продукції (крб.)

Рішення.Припустимо, що виробляється x 1 виробів А , виробів Ута виробів З.Для визначення оптимального плану виробництва потрібно вирішити задачу, що полягає в максимізації цільової функції 3 повинні задовольняти наступній системі нерівностей:

(52)

Як бачимо, завдання (48) – (50) і (51) – (53) утворюють симетричну пару двоїстих завдань. Рішення прямої задачі дає оптимальний план виробництва виробів. A, Уі З, а рішення двоїстої – оптимальну систему оцінок сировини, використовуваного виробництва цих виробів. Щоб визначити розв'язання цих завдань, слід спочатку знайти рішення будь-якої з них. Оскільки система обмежень завдання (48) – (50) містить лише нерівності виду “ ”, краще спочатку знайти розв'язання цього завдання. Її рішення наведено у таблиці 14.

З цієї таблиці видно, що оптимальним планом виробництва виробів є такий, при якому виготовляється 82 вироби Ута 16 виробів З.При цьому плані виробництва залишається невикористаним 80 кг сировини II виду, а загальна вартість виробів дорівнює 1340 руб. З таблиці 14 також видно, що оптимальним рішенням двоїстої задачі є

Таблиця 14

i	Базис	З б	p 0	10	14	12	0	0	0
				p 1	p 2	p 3	p 4	p 5	p 6
1 2 3	p 2 p 5 p 3	14 0 12	82 80 16 1340	19/8 23/8 -3/4 57/4	1 0 0 0	0 0 1 0	5/8 1/8 -1/4 23/4	0 1 0 0	-1/8 -5/8 1/4 5/4

Змінні та позначають умовні двоїсті оцінки одиниці сировини, відповідно I та III видів. Ці оцінки відмінні від нуля, а сировина 1 та III видів повністю використовується при оптимальному плані виробництва продукції. Подвійна оцінка одиниці сировини II виду дорівнює нулю. Цей вид сировини повністю використовується при оптимальному плані виробництва.

Таким чином, позитивну подвійну оцінку мають ті види сировини, які повністю використовуються при оптимальному плані виробництва виробів. Тому подвійні оцінки визначають дефіцитність сировини, що використовується підприємством. Більше того, величина цієї двоїстої оцінки показує, наскільки зростає максимальне значення цільової функції прямої задачі зі збільшенням кількості сировини відповідного виду на 1 кг. Так, збільшення кількості сировини I виду на 1 кг призведе до того, що з'явиться можливість знайти новий оптимальний план виробництва виробів, при якому загальна вартість продукції, що виготовляється, зросте на 5,75 руб. і стане рівною 1340+5,7 5= 1345,75 руб. При цьому числа, що стоять у стовпці вектора таблиці 14, показують, що зазначене збільшення загальної вартості продукції, що виготовляється, може бути досягнуто за рахунокзбільшення випуску виробів Уна 5/8 од. та скорочення випуску виробів Зна 1/4 од. Внаслідок цього використання сировини ІІ виду зменшиться на 1/8 кг. Так само збільшення на 1 кг сировини III виду дозволить знайти новий оптимальний план виробництва виробів, при якому загальна вартість продукції, що виготовляється, зросте на 1,25 руб. і становитиме 1340 +1,25 = 1341,25 руб. Це буде досягнуто внаслідок збільшення випуску виробів Зна 1/4 од. та зменшення виготовлення виробів на 1/8 од., причому обсяг використовуваної сировини II виду зросте на 5/8 кг.

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

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

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

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