17. Яким чином з математичної постановки задачі лп скласти двоїсту задачу?

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

Якщо пряма задача лінійного програмування подана в стандарт­ному вигляді, то двоїста задача утворюється за такими правилами:

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

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

3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки.

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

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

6. Матриця

,

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

утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків — рядками.

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

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

Пряма задача	Двоїста задача
Cиметричні задачі
max F = CX AX   B X   0	min Z = BY ATY   C Y   0
min F = CX AX   B X   0	max Z = BY ATY   C Y   0

Несиметричні задачі

max F = CX AX = B X   0	min Z = BY ATY   C Y
min F = CX AX = B X   0	max Z = BY ATY   C Y

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

Кожну з двох спряжених задач можна розв’язати окремо, проте встановлені теоремами двоїстості залежності між оптимальними планами прямої та двоїстої задач уможливлюють знаходження розв’язку двоїстої задачі за наявності оптимального плану прямої, і навпаки/

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

max Z = – 5x₁ + 2x₂;

Розв’язання. Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і в системі обмежень є нерівності, то їх слід звести до виду « ». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилеж­ний. Отримаємо:

max Z = – 5x₁ + 2x₂;

Тепер за відповідними правилами складемо двоїсту задачу:

min F = – y₁ + 5y₂;

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

1. max Z = – 5x₁ + 2x₂ + 0x₃ + 0x₄;

2. Векторна форма запису системи обмежень має вигляд:

,

де , , , , .

У системі векторів для утворення початкового одиничного базису відсутній один вектор. Тому введемо штучну змінну в перше обмеження.

3. Розширена задача лінійного програмування буде такою:

max Z = – 5x₁ + 2x₂ + 0x₃ + 0x₄ – Мx₅;

У цій задачі х₄ та х₅ — базисні змінні, а х₁, х₂, х₃ — вільні. Нехай х₁ = х₂ = х₃ = 0, тоді х₄ = 5; х₅ = 1.

Перший опорний план задачі:

X₀ = (0; 0; 0; 5; 1), Z₀ = – M.

4. Подальше розв’язування прямої задачі подано у вигляді симплексної таблиці:

Базис	Сбаз	План	–5	2	0	0	– М	
			x1	x2	x3	x4	x5
 x5 x4	–М 0	1 5	1 2	1 3	– 1 0	0 1	1 0	1 5/3
Zj – cj  0		0 –М	5 –М	–2 –М	0 М	0 0	0 0
x2  x4	2 0	1 2	1 –1	1 0	–1 3	0 1	1 –3	– 2/3
Zj – cj  0		2	7	0	– 2	0	2 М
x2 x3	2 0	5/3 2/3	2/3 –1/3	1 0	0 1	1/3 1/3	0 –1
Zj – cj  0		10/3	19/3	0	0	2/3	0 М

З останньої симплекс-таблиці запишемо оптимальний план прямої задачі:

Х* = (0; 5/3; 2/3; 0), Z_max = 10/3.

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

min F = max Z = 10/3.

Компоненти вектора Y^* (оптимальний план двоїстої задачі) визначимо за формулою:

,

де та міститься в стовпчику «с_баз» останньої симплекс-таблиці;

.

Матриця D^{– 1} також міститься в останній симплекс-таблиці у стовпчиках змінних «x₅» та «x₄», які утворювали початковий базис.

Отже,

,

min F = – 1  0 + 5  2/3 = 10/3.

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