Отримання оптимального розв’язку двоїстої задачі за допомогою симплекс-методу

Розглянемо можливості отримання оптимального розв’язку двоїстої задачі з оптимального розв’язку (за допомогою останньої симплекс-таблиці) прямої задачі.

Приклад.

Пряма задача.

Q= 3x₁+2x₂à Max,

x₁+2x₂<=6 x₁+2x₂+х₃=6 à y₁

2x₁+x₂<=8 2x₁+x₂ +х₄=8 à y₂

-x₁+x₂<=1 -x₁+x₂ +х₅=1 à y₃

x₂<=2 x₂ +х₆=2 à y₄

x₁ >=0 x₂ >=0 x_j>=0

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

Двоїста задача.

6y₁+ 8y₂ + y₃ + y₄ à Min,

y₁+ 2y₂ - y₃ >=3

2y₁+ y₂ + y₃ + y₄>=2

y₁>=0 y₂ >=0 y₃ >=0 y₄>=0.

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

			c₁	c₂	c₃	c₄	c₅	c₆
x_b	c_b	P₀
			P₁	P₂	P₃	P₄	P₅	P₆
x₂		4/3			2/3	-1/3
x₁		10/3			-1/3	2/3
x₅					-1
x₆		2/3			-2/3	1/3
Q		38/3			1/3	4/3

Початкові базові змінні: x₃, x₄, x₅, x₆.

Різниця між лівою та правою частинами обмеження двоїстої задачі, яке асоційоване з цією початковою змінною

Для визначення оптимальних значень змінних двоїстої задачі згідно до теорем двоїстості складаємо рівняння:

Коефіцієнт

при початковій базовій змінній в рядку прямої задачі

Це ж співвідношення в звичній формі: , .

Відповідні співвідношення для прикладу:

1/3 = y₁ - 0 à x₃

4/3 = y₂ - 0 à x₄

1/3 = y₃ - 0 à x₅

1/3 = y₄ - 0 à x₆

Наслідком з 1-ї теореми є те, що для будь-якої пари припустимих розв’язків прямої та двоїстої задачі:

Значення функції мети в задачі максимізації

Значення функції мети в задачі мінімізації

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

<== попередня сторінка	\|	наступна сторінка ==>
Зв’язок між розв’язками прямої та двоїстої задач	\|	Економічна інтерпретація задач лінійного програмування

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.005 сек.