Задача 3

Побудувати двоїсту задачу до заданої та знайти її розв’язок. Використовуючи теореми двоїстості знайти розв’язок прямої задачі. Задана пряма задача має вигляд:

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

Розв’язання

Двоїста задача утворюється за такими правилами:

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

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

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

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

Двоїстою до задачі

max Z=c₀ + (c, x),

Ax=b, x0,

(записаній у векторно-матричній формі) є

,

, y0,

де – матриця, транспонована до А; (с, x), (b, y) – скалярні добутки відповідних векторів.

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

max Z = – 5x1 + 2x2; (3.1)

(3.2)

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

min F = – y1 + 5y2; (3.3)

(3.4)

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

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

(3.6)

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

, (3.7)

де , , , , .

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

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

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

(3.9)

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

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

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

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

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

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

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

min F = max Z = 10/3. (3.12)

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

, (3.13)

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

. (3.14)

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

Отже,

, (3.15)

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

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

Перевіримо правильність рішення прямої задачі за допомогою MS Excel (див.рис.3.1-3.3).

Рисунок 3.1

Рисунок 3.2

Рисунок 3.3

Перевіримо правильність рішення двоїстої задачі за допомогою MS Excel (див.рис.3.4-3.6).

Рисунок 3.4

Рисунок 3.5

Рисунок 3.6