5.5. Алгоритм двоїстого симплекс-методу

Розв’язування задачі двоїстим симплекс-методом здійснюємо поетапно:

1. Знаходимо псевдоплан задачі 0,…,0).

2. Складаємо симплекс-таблицю і перевіряємо цей псевдоплан на оптимальність. Якщо цей план оптимальний, тобто всі і серед чисел немає від’ємних, то знайдено розв’язок задачі.

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

3. Знаходимо розв’язуваний рядок. Для цього визначаємо найбільше за абсолютною величиною від’ємне число стовпця вектора Розв’язувальний стовпець ─ це мінімальне значення за абсолютною величиною з відношень елементів рядка до відповідних від’ємних елементів розв’язувального рядка

для всіх <0.

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

5. Повторюємо всі дії починаючи з етапу 2.

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

Розглянемо алгоритм двоїстого симплекс-методу на прикладі.

5.6. Приклад

Побудувати двоїсту задачу до заданої прямої задачі. Розв’язати пряму задачу двоїстим симплекс-методом і за знайденим розв’язком прямої задачі одержати розв’язок двоїстої.

Пряма задача

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

Розв’язання. Запишемо двоїсту задачу до заданої. Для цього:

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

2. Складемо цільову функцію двоїстої задачі

Число змінних двоїстої задачі дорівнює числу обмежень прямої.

3. Запишемо матрицю коефіцієнтів при змінних одержаної системи і транспонуємо її

4. Запишемо систему обмежень двоїстої задачі:

Розв’яжемо пряму задачу. Для цього зведемо її до канонічної форми:

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

Запишемо систему обмежень у векторній формі:

де

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

Етап 1. Знайдемо псевдоплан прямої задачі, зведеної до канонічної форми. Помножимо перше і третє рівняння системи обмежень на (─1) і отримаємо таку задачу:

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

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

Етап 2. Складаємо симплекс-таблицю (табл. 7)

Таблиця 7

	Базис			─6	─4
1		0	─3	─2	─1	1	0	0
2		0	1	1	─1	0	1	0
3		0	─1	1	─2	0	0	1
			0	6	4	0	0	0

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

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

Етап 3. Щоб перейти до наступного псевдоплану, треба вибрати розв’язуваний рядок і розв’язуваний стовпець. Вектор, що підлягає виведенню з базису, визначаємо так: серед від’ємних чисел стовпця вибираємо найбільше за абсолютною величиною значення. В нашому прикладі це 3. Таким чином, з базису виводимо вектор . Рядок є розв’язуваним, його вилучаємо з базису.

Далі визначаємо, який вектор треба ввести в базис. Обчислюємо відношення компонент рядка до відповідних від’ємних компонент вектора, який вводимо в базис , і серед них обираємо найменше значення за абсолютною величиною

для всіх <0.

Маємо

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

Таблиця 8

	Базис			─6	─4
1 2		─6 0	1,5 ─0,5	1 0	0,5 ─1,5	─0,5 0,5	0 1	0 0
3		0	─2,5	0	─2,5	0,5	0	1
			─9	0	1	3	0	0

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

Оскільки в стовпці два від’ємних числа (─0,5 і ─2,5), то вибираємо (─2,5), що стоїть у рядку вектора . Вибираємо розв’язуваний рядок і розв’язуваний стовпчик . Переходимо до нової симплекс-таблиці (табл. 9).

Таблиця 9

	Базис			─6	─4
1		─6	1	1	0	─0,4	0	─0,2
2		0	1	0	0	0,2	1	─0,6
3		─4	1	0	1	─0,2	0	0,4
			─10	0	0	3,2	0	0,4

Оскільки, всі оцінки а в стовпці немає від’ємних чисел, то в табл. 9 знайдено оптимальний план прямої та двоїстої задач. = (1, 1, 0, 1, 0) та = (3,2; 0; 0,4). На цих планах значення цільових функцій прямої та двоїстої задач рівні:

Шукане мінімальне значення задачі буде

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

Застосування двоїстого симплекс-методу особливо ефективне під час аналізу моделі на чутливість.