3.2. Симплексні таблиці

Алгоритм знаходження оптимального плану за допомогою симплекс-таблиць:

1. Дані задачі, отримані після приведення її системи обмежень до невід’ємного одиничного базису (після визначення опорного плану), заносимо в симплекс-таблицю. У самому верхньому рядку таблиці записуємо імена стовпців Б, c_б, b і змінні x_j (j=1,..,n) задачі, указуючи під ними відповідні коефіцієнти c_j (j=1,..,n) цільової функції. У робочу (виділену) частину таблиці заносимо коефіцієнти a_ij (i=1,..,m; j=1,..,n) при змінних із системи обмежень. У першому стовпці таблиці записуємо базисні змінні (порядок їхнього запису визначається положенням одиниці відповідного одиничного вектора-стовпця), у другому – коефіцієнти цільової функції при цих базисних змінних, у третьому – вільні члени системи. У першій клітині нижнього рядка записуємо значення цільової функції на даному опорному плані (сума добутків елементів стовпця c_б на відповідні елементи стовпця b), в інших n клітинах – оцінки оптимальності. Оцінка оптимальності , що відповідає зміннійx_j, дорівнює сумі добутків елементів стовпця c_б на відповідні елементи a_ij стовпця коефіцієнтів при x_j мінус c_j.

2. Перевіряємо виконання критерію оптимальності. Якщо всі оцінки оптимальності недодатні (), то даний опорний план оптимальний – рішення закінчене. Якщо серед оцінок є додатні, то будуємо новий опорний план.

3. Найбільша додатна оцінка оптимальності визначає вільну змінну x_s, що вводиться до базису (ключовий стовпець s). Знаходимо мінімальне значення із симплексних відносин: . Якщо мінімуму нема, то задача не має розв’язку і обчислення закінчені. Якщо мінімум є, то обираємо рядок, на якому він досягається (будь-який, якщо їх декілька). Цей рядок є ключовим. Він вказує на базисну змінну, що виводиться з базису. За допомогою елементарних перетворень одержуємо новий опорний план.

4. Переходимо до п. 1 алгоритму.

Задача 3.2. Розв’язати симплексним методом задачу планування виробництва, математичну модель якої було побудовано в задачі 1.1 (с. 5).

Рішення

1. Приведемо дану задачу до канонічного виду. Для цього до лівої частини кожної нерівності додамо невід’ємні змінні x₅, x₆, x₇ і змінимо знак функції мети на протилежний. Таким чином одержимо задачу

2. Знайдемо вихідний опорний план.

Будуємо розширену матрицю системи обмежень

.

Ця матриця містить одиничний базис – три попарно різних одиничних вектори. Тому базисні змінні – це x₅, x₆, x₇; вільні змінні – x₁, x₂, x₃, x₄. Базисний розв’язок: . Він є вихідним опорним планом (усі його компоненти невід’ємні).

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

Заповнюємо першу симплексну таблицю.

Таблиця 3.1

Б	cб	b	x1	x2	x3	x4	x5	x6	x7
			–12	–7	–18	–10	0	0	0
x5	0	18	1	2	1	0	1	0	0
x6	0	30	1	1	2	1	0	1	0
x7	0	40	1	3	3	2	0	0	1
		0	12	7	18	10	0	0	0

В нижньому рядку першої клітини записано значення цільової функції на опорному плані : f() = 0 · 18 + 0 · 30 + 0 · 40 = 0 в інших 7 клітинах – оцінки оптимальності : c₁ = 0 · 1 + 0 · 1 + 0 · 1 – (–12) = 12; c₁ = 0 · 2 + 0 · 1 + 0 · 3 – (–7) = 7; ^{; ;}

^{; ;.}

Опорний план не є оптимальним, тому що серед оцінок в останньому рядку є додатні оцінки: 12, 7, 18, 10.

3. Переходимо до нового опорного плану. Змінну x₃ вводимо до базису, оскільки цій змінній відповідає максимальна додатна оцінка 18. Змінну x₇ виводимо з базису, тому що їй відповідає мінімальне значення із симплексних відносин: . За допомогою елементарних перетворень у третьому стовпці розширеної матриці будуємо одиничний вектор, в якому 1 знаходиться в ключовому рядку III.

.

Базисні змінні: x₃, x₅, x₆. Вільні змінні: x₁, x₂, x₄, x₇. Базисний розв’язок – новий опорний план.

Заповнюємо другу симплекс-таблицю.

Таблиця 3.2

Б	cб	b	x1	x2	x3	x4	x5	x6	x7
			–12	–7	–18	–10	0	0	0
x5	0	14/3	2/3	1	0	–2/3	1	0	–1/3
x6	0	10/3	1/3	–1	0	–1/3	0	1	–2/3
x3	–18	40/3	1/3	1	1	2/3	0	0	1/3
		–240	6	–11	0	–2	0	0	–6

Опорний план не є оптимальним, тому що в останньому рядку є додатна оцінка 6.

4. Переходимо до нового опорного плану. Змінну x₁ вводимо до базису, оскільки цій змінній відповідає додатна оцінка 6. Змінну x₅ виводимо з базису, тому що цій змінній відповідає мінімальне значення із симплексних відносин: . За допомогою елементарних перетворень у першому стовпці останньої матриці будуємо одиничний вектор, в якому 1 розташована в ключовому рядку I.

.

Базисні змінні: x₁, x₃, x₆. Вільні змінні: x₂, x₄, x₅, x₇. Базисний розв’язок – новий опорний план.

Заповнюємо третю симплекс-таблицю.

Таблиця 3.3

Б	cб	b	x1	x2	x3	x4	x5	x6	x7
			–12	–7	–18	–10	0	0	0
x1	–12	7	1	3/2	0	–1	3/2	0	–1/2
x6	0	1	0	–3/2	0	0	–1/2	1	–1/2
x3	–18	11	0	1/2	1	1	–1/2	0	1/2
		–282	0	–20	0	4	–9	0	–3

Опорний план не є оптимальним, тому що є додатна оцінка 4.

5. Переходимо до нового опорного плану. Змінну x₄ вводимо до базису, оскільки цій змінній відповідає додатна оцінка 4. Змінну x₃ виводимо з базису, тому що цій змінній відповідає мінімальне значення із симплексних відносин: . За допомогою елементарних перетворень у четвертому стовпці останньої матриці будуємо одиничний вектор, в якому 1 знаходиться в ключовому рядку III.

.

Базисні змінні: x₁, x₄, x₆. Вільні змінні: x₂, x₃, x₅, x₇. Базисний розв’язок – новий опорний план.

Заповнюємо четверту симплекс-таблицю.

Таблиця 3.4

Б	cб	b	x1	x2	x3	x4	x5	x6	x7
			–12	–7	–18	–10	0	0	0
x1	–12	18	1	2	1	0	1	0	0
x6	0	1	0	–3/2	0	0	–1/2	1	–1/2
x4	–10	11	0	1/2	1	1	–1/2	0	1/2
		–326	0	–22	–4	0	–7	0	–5

Опорний план є оптимальним, тому що в останньому рядку всі оцінки недодатні.

Оптимальне значення цільової функції: .

Повернемося до вихідної задачі: ,.

Відповідно до отриманого результату підприємство дістане прибуток у розмірі 326 грн, якщо виготовить 18 одиниць продукції першого виду і 11 одиниць продукції четвертого виду, а продукцію другого і третього видів взагалі не буде випускати.

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

,

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

Зауваження 3.3. (Геометрична інтерпретація симплексного методу). Опорному плану відповідає кутова точка многокутника розв’язків системи обмежень. Ідея симплексного методу – перебір кутових точок многокутника розв’язків з урахуванням зміни значення функції мети (кожний наступний розв’язок “кращий” за попередній, тобто при ). Такий перебір дозволяє скоротити число кроків при відшукуванні оптимуму.