Поняття двоїстості. Правила побудови двоїстих задач

Приклади розв’язування навчальнихзавдань

Приклад 3.1.

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

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

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

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

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

F = – y ₁ + 5 y ₂ ® min;

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

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

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

,

де , , , , .

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

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

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

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

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

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

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

Базис	С баз	План	–5				М	q
x1	x2	x3	x4	x5
x 5 x 4	– М 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
x 2 x 4	2 0	1 2	1 –1	1 0	–1 3	0 1	1 –3	— 2/3
Zj – Cj ³ 0				–2		2 + М
x 2 x 3	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			2/3	0 + М

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

Х ^* = (0; 5/3; 2/3; 0), Z _max = 10/3.

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

min F = max Z = 10/3,

,

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

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

Отже,

,

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

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

 

Приклад 3.2.

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

Z = x ₁ + 2 x ₂ + 2 x ₃ ® min;

Розв’язування. За відповідними правилами побудуємо двоїсту задачу:

F = y ₁ + 4 y ® mах;

Зауважимо, що задачі несиметричні, і тому змінна у ₁, що відповідає рівнянню в системі обмежень прямої задачі, може мати будь-який знак, а змінна у ₂ — лише невід’ємна.

Двоїста задача має дві змінні, а отже, її можна розв’язати графічно (рис. 3.1).

Рис. 3.1

Найбільшого значення цільова функція двоїстої задачі F досягає в точці В многокутника ABCD. Її координати:

тобто Y ^* = (–2/3; 4/3); mах F = 1 × (–2/3) + 4 × 4/3 = 14/3.

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

Підставимо Y ^* у систему обмежень двоїстої задачі і з’ясуємо, як виконуються обмеження цієї задачі:

Оскільки перше обмеження для оптимального плану двоїстої задачі виконується як строга нерівність, доходимо висновку, що перша змінна прямої задачі дорівнюватиме нулю х ₁ = 0 (перша частина другої теореми двоїстості).

Тепер проаналізуємо оптимальний план двоїстої задачі. Ос­кільки друга компонента плану у ₂ = 4/3 додатна, доходимо висновку, що друге обмеження прямої задачі для X ^* виконуватиметься як строге рівняння (друга частина другої теореми двоїстості).

Об’єднуючи здобуту інформацію, можна записати систему обмежень прямої задачі як систему двох рівнянь, в якій х ₁ = 0, та визначити решту змінних:

тобто X ^* = (0; 5/3; 2/3), min Z = 1 × 0 + 2 × 5/3 + 2 × 2/3 = 14/3.

Умова min Z = max F = 14/3 виконується, і тому X ^* = (0; 5/3; 2/3);
Y ^* = (–2/3; 4/3) є оптимальними планами відповідно прямої та двоїстої задач.

 

Приклад 3.2.

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

Z = 12 x ₁ – 4 x ₂ + 2 x ₃ ® min;

а) х = (8/7; 3/7; 0); б) х = (0; 1/5; 8/5); в) х = (1/3; 0; 1/3).

Розв’язування. Принцип розв’язування задач такого типу ґрунтується на використанні другої теореми двоїстості. Необхідно побудувати двоїсту задачу та припускаючи, що відповідний план Х є оптимальним, визначити оптимальний розв’язок двоїстої задачі. Якщо при цьому екстремальні значення цільових функцій збігатимуться, то припущення правильне. Протилежного висновку можна дійти в таких випадках.

1. Якщо запропонований план Х недопустимий, тобто не задовольняє систему обмежень прямої задачі.

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

3. Якщо визначений план двоїстої задачі допустимий, але для нього екстремальне значення цільової функції F не дорівнює зна­ченню функції Z, тобто не виконується умова першої теореми дво­їстості.

Запишемо двоїсту задачу до прямої задачі лінійного програмування:

F = y ₁ + 2 y ₂ ® max;

Перевіримо запропоновані плани на оптимальність.

1. X = (8/7; 3/7; 0). Підставимо його в систему обмежень прямої задачі:

Обидва обмеження виконуються і тому Х = (8/7; 3/7; 0) є допустимим планом прямої задачі. Припустимо тепер, що зазначений план є оптимальним планом прямої задачі. Тоді для нього Z = 12 × 8/7 + 4 × 3/7 + 2 × 0 = 12.

Скористаємося другою теоремою двоїстості та визначимо відповідний план двоїстої задачі. Оскільки x ₁ = 8/7 > 0; x ₂ = 3/7 > 0, то згідно з другою частиною другої теореми двоїстості можна записати перше та друге обмеження як рівняння і визначити у ₁ і у ₂:

Підставимо ці значення в третє обмеження системи двоїстої задачі:

;

.

Для визначених значень у ₁ = 4; у ₂ = 4 це обмеження не виконується, і тому відповідний план Y = (4; 4) є недопустимим планом двоїстої задачі. Унаслідок цього наше припущення, що Х = (8/7; 3/7; 0) є оптимальним планом вихідної задачі, виявилося помилковим.

2. Х = (0; 1/5; 8/5). Підставимо цей план в систему обмежень прямої задачі:

План допустимий і для нього Z = 12 × 0 – 4 × 1/5 + 2 × 8/5 = 12/5.

Визначимо відповідний план двоїстої задачі. Оскільки компоненти x ₃ та x ₂ додатні, то друге та третє обмеження двоїстої задачі можна записати як рівняння:

Перевіримо, що виконується перше обмеження двоїстої задачі для визначених значень у ₁ та у ₂: 2 × 8/5 + 2/5 = 18/5 < 12. Отже, перше обмеження виконується, і тому Y = (8/5; 2/5) є допустимим планом двоїстої задачі. Для нього F = 8/5 + 2 × 2/5 = 12/5 = Z. З огляду на викладене можна зробити висновок, що Y ^* = (8/5; 2/5) є оптимальним планом двоїстої задачі, а X ^* = (0; 1/5; 8/5) — оптимальним планом прямої задачі.

Наше припущення відносно запропонованого плану виявилося правильним.

3. Х = (1/3; 0; 1/3). Для цього плану обмеження прямої задачі виконуються так:

Оскільки Х = (1/3; 0; 1/3) є недопустимим планом, то він не може бути також оптимальним планом прямої задачі.

Отже, перевірка запропонованих планів на оптимальність дала такі результати: а) ні; б) так, Y ^* = (0; 1/5; 8/5), min Z = 12/5; в) ні.

 

3.2. Приклади та завдання для самостійної роботи

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

Z = –30 x ₁ + 10 x ₂ ® mах;

3.1

Z = 4 x ₁ + 3 x ₂ + x ₃ ® min;

3.2

Z = 3 x ₁ + 2 x ₂ + 5 x ₃ ® max;

3.3

Z = –3 x ₁ – 4 x ₂ – 5 x ₃ ® min;

3.4

Z = 2 x ₁ + 3 x ₂ ® max;

3.5

Z = 5 x ₁ + 2 x ₂ ® min;

3.6

Z = 5 x ₁ + 12 x ₂ – 4 x ₃ ® max;

3.7

Z = – x ₁ + x ₂ ® min;

3.8

Z = 5 x ₁ + 6 x ₂ ® max;

3.9

Z = 2 x ₁ – 2 x ₂ + 4 x ₃ ® min;

3.10

Z = 3 x ₁ + 6 x ₂ + 2 x ₃ ® max;

3.11

Z = x ₁ + 2 x ₂ – 3 x ₃ ® min;

3.12

Z = x ₁ + x ₂ ® max;

3.13

Z = 10 x ₁ + 40 x ₂ ® min;

3.14

Z = x ₁ + 2 x ₂ ® max;

3.15

Z = x ₁ + 2 x ₂ + 5 x ₃ ® min;

3.16

Z = x ₁ + 5 x ₂ + 3 x ₃ ® max;

3.17

У наведених нижче задачах до поставленої задачі лінійного програмування записати двоїсту і розв’язати її графічно. Визначити оптимальний план прямої задачі, застосовуючи другу теорему двоїстості.

Z = 2 x ₁ + 4 x ₂ + 24 x ₃ + 6 x ₄ ® min;

3.18

Z = 8 x ₁ + 2 x ₂ + x ₃ + x ₄ ® max;

3.19

Z = 2 x ₁ + x ₂ + 3 x ₃ ® min;

3.20

Z = 9 x ₁ + 8 x ₂ + 10 x ₃ ® max;

3.21

Z = – x ₁ + 8 x ₂ + 20 x ₃ + 6 x ₄ ® min;

3.22

Z = – x ₁ + x ₂ + x ₃ ® max;

3.23

Z = 8 x ₁ + 8 x ₂ + x ₃ ® min;

3.24

Z = x ₁ + 4 x ₂ + x ₃ ® max;

3.25

Z = 14 x ₁ + 15 x ₂ – 24 x ₃ ® min;

3.26

Z = x ₁ + 8 x ₂ + 10 x ₃ ® max;

3.27

У наведених задачах визначити, чи є для сформульованої задачі лінійного програмування оптимальними запропоновані плани.

Z = 5 x ₁ + 12 x ₂ + 4 x ₃ ® max;

3.28

а) х = (0; 4; 2); б) х = (14/5; 18/5; 0); в) х = (5/3; 7/3; 1/3).

Z = 4 x ₁ + 3 x ₂ + 5 x ₃ ® max;

3.29

а) х = (2; 3; 0); б) х = (3; 0; 1); в) х = (0; 1; 2).

Z = 2 x ₁ + 3 x ₂ ® min;

3.30

а) х = (10; 10/3); б) х = (20; 10); в) х = (10/3; 10/3).

Z = 8 x ₁ – 20 x ₂ + 6 x ₃ ® max;

3.31

а) х = (1; 1/3; 1); б) х = (2; 1; 0); в) х = (1/8; 0; 13/8).

Z = x ₁ + 10 x ₂ + 6 x ₃ + x ₄ ® min;

3.32

а) х = (16; 3; 0; 0); б) х = (4; 0; 0; 15); в) х = (0; 0; 4; 3).

 

3.2. Контрольні запитання до тем 1-3

1. Запишіть загальну математичну модель лінійного програмування.

2. Як звести задачу лінійного програмування до канонічної форми?

3. Які є форми запису задач лінійного програмування?

4. Дайте геометричну інтерпретацію задачі лінійного програ­му­вання.

5. Який розв’язок задачі лінійного програмування називається допустимим?

6. Поясніть, яка область називається областю допустимих планів.

7. Який план називається опорним?

8. Який опорний план називається невиродженим?

9. Сформулюйте основні аналітичні властивості розв’язків задачі
лінійного програмування.

10. Які задачі можна розв’язувати графічним методом?

11. За яких умов задача лінійного програмування з необмеженою областю допустимих планів має розв’язок?

12. Суть алгоритму графічного методу.

13. Для розв’язування яких математичних задач застосовується симплексний метод?

14. Суть алгоритму симплексного методу.

15. Сформулюйте умови оптимальності розв’язку задачі симплексним методом.

16. Як вибрати напрямний вектор-стовпець?

17. Як вибрати розв’язувальний елемент?

18. Суть методу Жордана—Гаусса.

19. Суть методу штучного базису.

20. У чому сутність двоїстості у лінійному програмуванні?

21. Розробіть просту економіко-математичну модель. Запишіть до неї двоїсту. Дайте економічну інтерпретацію двоїстих оцінок.

22. Які взаємоспряжені задачі називаються симетричними, а які — несиметричними? Чим вони відрізняються?

23. Скільки змінних та обмежень має двоїста задача відповідно до прямої?

24. Сформулюйте першу теорему двоїстості та дайте її економічне тлумачення.

25. Сформулюйте другу теорему двоїстості та дайте її економічне тлумачення.

26. Сформулюйте третю теорему двоїстості та дайте її економічне тлумачення.

27. Сформулюйте правила побудови двоїстих задач.

28. Як за розв’язком прямої задачі знайти розв’язок двоїстої?

29. Запишіть всі можливі види прямих і двоїстих задач.

Теми рефератів до тем 1-3

1. Опуклі множини.

2. Канонічні форми задач лінійного програмування.

3. Опорні плани задач лінійного програмування.

4. Аналітичні властивості розв’язків задач лінійного програмування.

5. Зацикленість алгоритму симплексного методу.

6. Обґрунтування алгоритму знаходження оптимального плану лінійної задачі.

7. Теореми двоїстості та їх використання в економічних дослідженнях.

8. Економічне обґрунтування нульових двоїстих оцінок.

9. Використання двоїстих оцінок для обґрунтування цін на ресурси і продукцію.

10. Історія виникнення та використання в економічних дослідженнях двоїстих оцінок.

11. Дискусія 70-х років з приводу двоїстих оцінок.

12. Академік Л. В. Канторович і його роль у розробці двоїстих оцінок.