 |
Двоїстий симплекс-метод.
|
|
|
|
Двоїстий симплекс-метод, як і симплекс-метод, використовується при знаходженні розв’язок задачі лінійного програмування, записаної у формі основної задачі, для якої серед векторів Рj, складених з коефіцієнтів при невідомих у системі рівнянь, є т одиничних. Разом з тим двоїстий симплекс-метод можна застосовувати при рішенні задачі лінійного програмування, вільні члени системи рівнянь якої можуть бути будь-якими числами (при рішенні задачі симплексним методом ці числа передбачалися невід’ємними). Таку задачу і розглянемо тепер, попередньо припустивши, що одиничними є вектори P1, P2,...; Pт,тобто розглянемо задачу, що полягає у визначенні максимального значення функції
F=c1x1 + c2x2+... + cnxn (80)
при умовах
х1Р1+х2Р2+...+хтРт+ хт+1Рт+1+...+хпРп=Р0, (81)
xj ≥ 0 (j = 
) (82)
де
;
і серед чисел bi ≥ 0 (i = 
)є від’ємні.
У даному випадку Х= (b1; b2;...; bт; 0;...; 0) є розв’язок системи лінійних рівнянь (81). Однак це розв’язок не є планом задачі (80) - (82), так як серед його компонентів є від’ємні числа.
Оскільки вектори P1, P2,...; Pт – одиничні, кожний з векторів Pj ≥ 0 (j = ) можна представити у вигляді лінійної комбінації даних векторів, причому коефіцієнтами розкладання векторів Pj по векторах P1, P2,...; Pт служать числа xij = aij (i = ; j = ). Таким чином, можна знайти
Визначення 1.15. Розв’язок Х= (b1; b2;...; bт; 0;...; 0) системи лінійних рівнянь (81), обумовлений базисом P1, P2,...; Pт, називається псевдопланом задачі (80)-(82), якщо Δ j ≥ 0 для кожного j (j = ).
Теорема 1.13. Якщо в псевдоплані Х= (b1; b2;...; bт; 0;...; 0), обумовленому базисом P1, P2,...; Pт, є хоча б одне від’ємне число bi <0 таке, що всі aij ≥ 0 (j = ), то задача (80)-(82) взагалі не має планів.
Теорема 1.14. Якщо в псевдоплані Х= (b1; b2;...; bт; 0;...; 0), обумовленому базисом P1, P2,...; Pт, є від’ємні числа bi <0 такі, що для кожного з них існують числа aij < 0, то можна перейти до нового псевдоплану, при якому значення цільової функції задачі (80)-(82) не зменшиться.
|
|
|
Сформульовані теореми дають підставу для побудови алгоритму двоїстого симплекс-методу.
Отже, продовжимо розгляд задачі (80)-(82). Нехай Х= (b1; b2;...; bт; 0;...; 0) – псевдоплан цієї задачі. На основі вихідних даних складають симплекс-таблицю (табл. 1.47), у якій деякі елементи стовпця вектора Р0 є від’ємними числами. Якщо таких чисел немає, то в симплекс-таблиці записаний оптимальний план задачі (80)-(82), оскільки, по припущенню, всі Δ j ≥ 0. Тому для визначення оптимального плану задачі за умови, що він існує, варто зробити впорядкований перехід від одної симплекс-таблиці до іншої доти, поки зі стовпця вектора Р0 не будуть виключені від’ємні елементи. При цьому увесь час повинні залишатися невід’ємними всі елементи (т +1)-го рядка, тобто zj – cj ≥ 0 для кожного j (j = ).
Таким чином, після складання симплекс-таблиці перевіряють, чи є в стовпці вектора Р0 від’ємні числа. Якщо їх немає, то знайдено оптимальний план вихідної задачі. Якщо ж вони є (що ми і припускаємо), то вибирають найбільше по абсолютній величині від’ємне число. У тому випадку, коли таких чисел декілька, беруть яке-небудь одне з них: нехай це число bi. Вибір цього числа визначає вектор, що виключається з базису, тобто в цьому випадку з базису виводиться вектор Рi. Щоб визначити, який вектор варто ввести в базис, знаходимо min (–Δ j / aij), де aij < 0.
Нехай це мінімальне значення приймається при j = r; тоді в базис вводять вектор Рr Число arj є розв’язним елементом. Перехід до нової симплекс-таблиці роблять за звичайними правилами симплексного методу. Ітераційний процес продовжують доти, поки в стовпці вектора Р0 не буде більше від’ємних чисел. При цьому знаходять оптимальний план вихідної задачі, а отже, і двоїстої. Якщо на деякому кроці виявиться, що в i -му рядку симплекс-таблиці (табл. 1.47) у стовпці вектора Р0 стоїть від’ємне число bi, а серед інших елементів цього рядка немає від’ємних, то вихідна задача не має розв’язок.
|
|
|
Таким чином, пошук розв’язок задачі (80)-(82) двоїстим симплекс-методом включає наступні етапи:
1. Знаходять псевдоплан задачі.
2. Перевіряють цей псевдоплан на оптимальність. Якщо псевдоплан оптимальний, то знайдено розв’язок задачі. У протилежному випадку або встановлюють нерозв’язність задачі, або переходять до нового псевдоплану.
3. Вибирають розв’язний рядок за допомогою визначення найбільшого по абсолютній величині негативного числа стовпця вектора Р0 і розв’язний стовпець за допомогою знаходження найменшого по абсолютній величині відношення елементів (т +1)-го рядка до відповідних від’ємних елементів розв’язного рядка.
Таблиця 1.47
| i | Базис | Cб | P0 | c1 | c2 | ... | ce | ... | cт | cт+1 | ... | cr | ... | cn |
| P1 | P2 | ... | Pe | ... | Pт | Pт+1 | ... | Pr | ... | Pn | ||||
| . . . e . . . i . . . т m +1 | Р1 Р2 . . . Рe . . . Pi . . . Рт | c1 c2 . . . ce . . . ci . . . cт | b1 b2 . . . be . . . bi . . . bт F0 | . . . . . . . . . | . . . . . . . . . | ... ... . . . ... . . . ... . . . ... ... | . . . . . . . . . | ... ... . . . ... . . . ... . . . ... ... | . . . . . . . . . | a1m+1 a2m+1 . . . aem+1 . . . aim+1 . . . amm+1 Δ m+1 | ... ... . . . ... . . . ... . . . ... ... | a1r a2r . . . aer . . . air . . . amr Δ r | ... ... . . . ... . . . ... . . . ... ... | a1n a2n . . . aen . . . ain . . . amn Δ n |
4. Знаходять новий псевдоплан і повторюють всі дії починаючи з етапу 2.
1.105. Знайти максимальне значення функції F=х1+х2+ 2 х3 при умовах
х1, х2, х3 ≥ 0
Розв’язок. Запишемо вихідну задачу лінійного програмування у формі основної задачі: знайти максимум функції F=х1+х2+ 2 х3 при умовах
х1, х2, …, х5 ≥ 0
Помножимо друге і третє рівняння системи обмежень останньої задачі на –1 і переходимо до наступної задачі: знайти максимум функції
F=х1+х2+ 2 х3 (83)
при умовах
(84)
х1, х2, …, х5 ≥ 0 (85)
Складемо для останньої задачі двоїсту. Такою є задача, у результаті розв’язок якої потрібно знайти мінімальне значення функції
F*= 8 y1 –4 y2 –6 y3 (86)
при умовах
(87)
y1, y2, y3 ≥ 0 (88)
Вибравши як базис вектори Р3, Р4 і Р5,складемо симплексну таблицю (табл. 1.48) для вихідної задачі (83)-(85).
|
|
|
Таблиця 1.48
| i | Базис | C6 | Р0 | |||||
| Р1 | Р2 | Р3 | Р4 | Р5 | ||||
| Р3 Р4 Р5 | –4 –6 | –1 –1 | –2 |
З цієї таблиці бачимо, що планом двоїстої задачі (86)-(88) є Y= (2; 0; 0;). При цьому плані F*=16. Так як в стовпці вектора Р0 табл. 1.48 є два від’ємних числа (–4 і –6), а в 4-му рядку від’ємних чисел немає, то відповідно до алгоритму двоїстого симплекс-методу переходимо до нової симплекс-таблиці. (У даному випадку це можна зробити, так як в рядках векторів Р4 і Р5 є від’ємні числа. Якби вони були відсутні, то задача була б нерозв’язна). Вектор, що виключається з базису, визначається найбільшим по. абсолютній величині від’ємним числом, що стоїть в стовпці вектора Р0 У цьому випадку це число –6. Отже, з базису виключаємо вектор Р5 Щоб визначити, який вектор необхідно ввести в базис, знаходимо 
, де а3j < 0. Маємо
Отже, у базис уводимо вектор Р2. Переходимо до нової симплекс-таблиці (табл. 1.49).
Таблиця 1.49
| i | Базис | C6 | Р0 | |||||
| Р1 | Р2 | Р3 | Р4 | Р5 | ||||
| Р3 Р4 Р2 | –7 | 1/2 –3/2 1/2 1/2 | 1/2 1/2 –1/2 1/2 |
Із цієї таблиці видно, що отримано новий план двоїстої задачі Y =(2; 0; 1/2). При цьому плані значення її лінійної форми дорівнює F *=13. Таким чином, за допомогою алгоритму двоїстого симплекс-методу зроблений упорядкований перехід від одного плану двоїстої задачі до іншого.
Так як в стовпці вектора Р0 табл. 1.49 стоїть від’ємне число –7, то розглянемо елементи 2-го рядка. Серед цих чисел є одне від’ємне –3/2. Якби таке число було відсутнє, то вихідна задача була б нерозв’язна. У цьому випадку переходимо до нової симплекс-таблиці (табл. 1.50).
Таблиця 1.50
| i | Базис | C6 | Р0 | |||||
| Р1 | Р2 | Р3 | Р4 | Р5 | ||||
| Р3 Р1 Р2 | 8/3 14/3 2/3 32/3 | 1/3 –2/3 1/3 1/3 | 2/3 –1/3 –1/3 2/3 |
Як видно з табл. 1.50, знайдені оптимальні плани вихідної і двоїстої задач. Ними є Х*= (14/3; 2/3; 8/3; 0) і Y *=(2;1/3; 2/3). При цих планах значення лінійних форм вихідної і двоїстої задач рівні: Fтах = F*min =32/3.
|
|
|
|
|
|
