Контрольні питання до змістового модуля і

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. Надайте геометричну інтерпретацію методу Гоморрі.

Змістовий модуль ІІ

Двоїстість у лінійному програмуванні. Елементи теорії ігор

2.1. Двоїста задача лінійного програмування

З кожною ЗЛП пов’язана інше лінійна задача, яку називають двоїстою (першу задачу називають вихідною).

Пара двоїстих задач має наступний вигляд:

Вихідна задача Двоїста задача

Правила складання двоїстих задач:

1. Якщо цільова функція вихідної задачі формулюється на максимум, а цільова функція двоїстої задачі – на мінімум, при цьому в задачі на максимум всі нерівності в обмеженнях приводять до вигляду “ ”, а в задачі на мінімум – до вигляду “ ”.

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

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

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

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

6. Передбачається, що змінні в обох задачах є невід’ємними.

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

Зауваження. Двоїста задача до двоїстої буде вихідною.

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

а) у всіх обмеженнях вільні члени містяться в правій частині нерівностей (рівностей), члени з невідомими – в лівій;

б) всі нерівності обмежень вихідної задачі повинні бути записані так, щоб знаки нерівностей в них були направлені в один і той же бік;

в) знаки нерівностей системи обмежень пов’язані з оптимізацією цільової функції таким чином: ;

Між взаємно двоїстими ЗЛП має місце взаємозв’язок, який виходить з теорем двоїстості.

Теореми двоїстості

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

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

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

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

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

Приклад 2.1.1. Записати двоїсту задачу для ЗЛП (1.2.1) (1.2.2).

(1.2.1)

max z = x₁ + 4x₂ (1.2.2)

Виписати розв’язок двоїстої задачі.

Розв’язання.

Оскільки початкова задача на максимум, то у всіх обмеженнях системи (1.2.1) повинен бути знак “ ”. Для цього обидві частини третьої нерівності помножимо на (–1). Таким чином, отримаємо:

(2.1.1)

max z = x₁ + 4x₂ (2.1.2)

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

.

По отриманій матриці складемо нову систему обмежень, причому в нерівностях обмежень буде знак “ ” і в правій частині цих нерівностей стоятимуть коефіцієнти цільової функції (2.1.2), тобто 1 і 4:

Коефіцієнтами нової цільової функції будуть числа, що стоять в правій частині обмежень вихідної задачі (2.1.1), причому цільова функція мінімізується: min f = – 5y₁ + 6y₂ – 7y₃ .

Отже, двоїста задача має вигляд (2.1.3) (2.1.4):

(2.1.3)

min f = – 5y₁ + 6y₂ – 7y₃ . (2.1.4)

Вихідна і двоїста ЗЛП мають різний економічний сенс. Вирішуючи одну задачу, можна, не вирішуючи іншу, виписати її розв’язок. Розв’язок двоїстої задачі y₁, y₂, y₃ знаходиться в z-рядку останньої симплексної таблиці в додаткових стовпцях із зворотним знаком (а саме, в стовпцях р₃, р₄, р₅). Потрібно пам’ятати, що розв’язок виписується з урахуванням додатності змінних. У нашому випадку розв’язок двоїстої ЗЛП має вигляд:

y₁ = 0, y₂ = 9/2, y₃ = 1/2.

При підстановці отриманого розв’язку в цільову функцію двоїстої задачі (2.1.4) повинно вийде число, що стоїть на перетині z-рядка останньої симплексної таблиці і стовпця р₀. Перевіримо: min f = max z.

Приклад 2.1.2. Побудувати двоїсту задачу для ЗЛП

min z = –7 x₁ + 3x₂ .

Розв’язання.

Оскільки вихідна задача на мінімум, то в системі обмежень повинні бути знаки “ ”. Таким чином, після відповідних перетворень система обмежень вихідної задачі прийме вигляд:

Цільова функція при цьому залишається без перетворень, а саме: min z = -7x₁+3x₂.

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

По отриманій матриці складемо нову систему обмежень, причому в нерівностях обмежень буде знак “ ” і в правій частині нерівностей стоятимуть коефіцієнти з цільової функції вихідної задачі, при цьому нова цільова функція повинна максимізуватися і складатися з коефіцієнтів, що стоять в правій частині нерівностей вихідної задачі. Таким чином, двоїста задача матиме вигляд:

max f = y₁ – 5y₂ + 6y₃ .