Опорний конспект лекцій з курсу Дослідження операцій Тема 5 Лінійне програмування, Симплекс-метод, НУДПСУ

Лекція №5. ЛІНІЙНЕ ПРОГРАМУВАННЯ. Симплекс-метод

План

1. Загальна ідея симплекс-методу.

2. Алгоритм симплекс-методу.

3. Симплекс-таблиця.

4. Приклади.

2.5. Симплекс-метод

2.5.1. Загальна ідея симплекс-методу

Для початку роботи потрібно, щоб задана система обмежень виражалася рівностями, причому в цій системі обмежень повинні бути виділені базисні невідомі, тобто обрано базис, інші ж змінні називаються вільними.

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

2.5.2. Алгоритм симплекс-метода

Розглянемо систему лінійних обмежень і лінійну форму вигляду

Z_min = c₀ + c₁x₁ + … + c_nx_n, (2.38)

x_i ³ 0, i = 1,2,…,n. (2.39)

тобто обмеження мають форму рівностей.

Введемо умовні позначення:

х₁, x₂ ..., x_r– базисні змінні;

x_r+1, x_r+2,..., x_n– вільні змінні.

Тепер приведемо записану систему до вигляду, де виділено базисні змінні, тобто виразимо базисні змінні через вільні. Це можна зробити різними способами, зокрема, за допомогою метода Жордана-Гауса. Вирази для базисних змінних підставимо і в цільову функцію. Отримаємо наступну систему співвідношень

Z_min = g₀ – (g_r+1x_r+1 + g_r+2x_r+2 + … + g_nx_n). (2.41)

За останньою системою обмежень і цільовою функцією Z побудуємо табл. 2.3.

Таблиця 2.3. Симплекс-таблиця

Дана таблиця називається симплекс-таблицею. Всі подальші перетворення симплекс-методу пов'язані із зміною змісту саме цієї таблиці.

Алгоритм симплекс-методу зводиться до наступного:

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

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

3. На перетині вирішуючого рядка і вирішуючого стовпця знаходиться вирішуючий елемент.

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

5. Після знаходження вирішуючого елементу переходять до наступної таблиці. Невідомі змінні, що відповідають вирішуючому рядку і стовпцю, міняють місцями. При цьому базисна змінна стає вільною змінною і навпаки. Симплекс-таблиця перетворюється наступним чином (табл. 2.4). В таблиці 2.4 перетворення рядка і стовпця зроблені у припущенні, що вирішуючим елементом є a_1r+2.

6. Елемент табл. 2.4, що відповідає вирішуючому елементу табл. 2.3, дорівнює зворотній величині вирішуючого елементу.

7. Елементи рядка табл. 2.4, що відповідають елементам вирішуючого рядка табл. 2.3, знаходять шляхом ділення відповідних елементів табл. 2.3 на вирішуючий елемент

8. Елементи стовпця табл. 2.4, що відповідають елементам вирішуючого стовпця табл. 2.3, знаходять шляхом ділення відповідних елементів табл. 2.3 на вирішуючий елемент і беруться з протилежним знаком.

9. Решта елементів обчислюється за правилом прямокутника: у думках викреслюємо прямокутник в табл. 2.3, одна вершина якого співпадає з вирішуючим елементом, а інша – з елементом, образ якого шукаємо; останні дві вершини визначаються однозначно. Тоді шуканий елемент з табл. 2.4 дорівнюватиме відповідному елементу табл. 2.3 мінус дріб, в знаменнику якого стоїть вирішуючий елемент, а в чисельнику – добуток елементів з двох невикористаних вершин прямокутника.

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

11. Якщо у вирішуючому стовпці всі елементи негативні, то задача не має розв'язків (мінімум не досягається).

Зауваження.Для побудови симплекс-таблиці слід обов’язково всі співвідношення (2.40)-(2.41) привести саме до поданої форми: вільний член мінус дужки, в дужках – лінійна комбінація вільних змінних.

Таблиця 2.4. Перетворення симплекс-таблиці

Приклад 2.10. Розв'яжемо наступну задачу симплекс-методом

Z_max = 2x₁ – x₂ + 3x₃ – 2x₄ + x₅.

Приведемо завдання до вигляду, що допускає застосування симплекс-алгоритму, обравши в якості базисних змінних х₃, х₄, х₅. Отримаємо

х₃ = 1 – (– х₁ + х₂),

х₄ = 1 – (х₁ – х₂),

х₅ = 2 – (х₁ + х₂).

Підставимо у вираз Z_max величини x₃, x₄, x₅

Z_max = 6x₁ – 7x₂ + 3.

За алгоритмом цільова функція повинна прагнути до мінімуму

Z_min = – Z_max = – 6x₁ + 7x₂ – 3 = – 3 – (6x₁ – 7x₂).

Складемо початкову симплекс-таблицю

Розшукуємо в останньому рядку найменший позитивний елемент, в нашому прикладі він дорівнює +6, отже, перший стовпець коефіцієнтів буде вирішуючим. Визначимо відношення вільних членів до позитивних елементів вирішуючого стовпця. Мінімальне симплекс-відношення дорівнює 1, отже, вирішуючий елемент знаходиться на перетині рядка зі змінною x₄і стовпця – x₁.

Переходимо до наступної таблиці, використовуючи правило прямокутника

У останньому рядку немає позитивних елементів, отже, оптимальний розв'язок знайдено: Z_min = – 9; x = (1; 0; 2; 0; 1), Z_max = – Z_min = 9.

Контрольні запитання

1. Подайте загальну ідея симплекс-методу.

2. Наведіть алгоритм симплекс-методу.

3. Що таке симплекс-таблиця?

4. Як будується симплекс-таблиця?

З повагою ІЦ “KURSOVIKS”!