3.3. Поняття про м-метод

Вище був викладений алгоритм одержання вихідного опорного плану у випадку, коли початковий базисний розв’язок недопустимий. Однак при розв’язанні задач за допомогою симплексних таблиць зручніше користатися М-методом, або методом штучного базису. Він полягає в наступному. Приводимо задачу до канонічного виду. Далі обидві частини кожного обмеження-рівності з від’ємною правою частиною множимо на (–1). Будуємо розширену задачу. Для цього в обмеження-рівності вводимо нові невід’ємні штучні змінні так, щоб нова задача вже мала невід’ємний одиничний базис. Додаємо ці штучні змінні у цільову функцію з коефіцієнтом М, де М – достатньо велике число (аналог ). Розв’язуємо розширену задачу звичайним симплексним методом, який має таку особливість: кожна оцінка оптимальності має вид, де– звичайні числа. Виконання критерію оптимальності перевіряємо за значеннями. Якщо в оптимальному розв’язку розширеної задачі всі штучнізмінні дорівнюють нулю, то відповідні значення інших змінних дають оптимальний розв’язок вихідної задачі. Якщо хоча б одна з них відмінна від нуля, то вихідна задача не має розв’язку.

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

1. Теоретичні основи симплекс-методу розв’язування задачі лінійного програмування: поняття базису, допустимого базису; взаємозв’язок між базисами та опорними планами.

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

3. Алгоритм симплекс-методу та його реалізація за допомогою симплекс-таблиць.

Лекція 4

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

Кожній задачі ЛП відповідає подвійна задача.

Задача I (вихідна)	Задача II (подвійна)

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

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

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

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

де – невід’ємні додаткові змінні вихідної та подвійної задачі відповідно.

В наступній табл. 4.1 відображено відповідність між змінними взаємно подвійних задач.

Таблиця 4.1

Змінні вихідної задачі I
початкові	додаткові
додаткові	початкові
Змінні подвійної задачі II

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

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

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

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

З

			Таблиця 4.2
Ресурс		Норми витрат ресурсів на одиницю продукції
вид	запас
S1	120	1		5	3	0
S2	300	3		0	6	1
Прибуток від 1 продукції, грн		7		3	6	12

адача 4.1. Сформулювати економічно, записати і розв’язати задачу, подвійну до задачі планування виробництва. Пояснити економічний зміст об’єктивно зумовлених оцінок ресурсів.

Рішення

1. Побудуємо математичну модель вихідної задачі (табл. 4.2).

Ця задача на максимізацію з нерівностями виду “ ≤ ”.

2. Складемо подвійну задачу. Для цього запишемо розширену матрицю А вихідної задачі. Знайдемо матрицю А^′, транспоновану до А.

. .

Сформулюємо подвійну задачу:

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

3. Розв’язуємо симплексним методом одну із задач, наприклад, вихідну задачу, тому що для неї легше отримати перший базисний розв’язок.

Одержуємо оптимальне рішення:

, .

Цьому рішенню відповідає нижченаведена симплекс-таблиця.

Таблиця 4.3

Б	cб	b	x1	x2	x3	x4	x5	x6
			–7	–3	–6	–12	0	0
x2	–3	24	1/5	1	3/5	0	1/5	0
x4	–12	300	3	0	6	1	0	1
		–3672	–148/5	0	–339/5	0	–3/5	–12

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

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

5. Об’єктивно зумовлені оцінки ресурсів є Ресурси S₁, S₂ за оптимальним планом використовуються цілком, тому що об’єктивно зумовлені оцінки цих ресурсів ненульові. При збільшенні (зменшенні) запасу ресурсів S₁ або S₂ на одиницю максимальний прибуток збільшиться (зменшиться) відповідно на 3/5 і 12 грн.