Рішення. 1. Приведемо дану задачу до канонічного виду

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

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

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

.

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

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

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

Таблиця 3.1

Б	cб	b	x 1	x 2	x 3	x 4	x 5	x 6	x 7
–12	–7	–18	–10
x 5
x 6
x 7

В нижньому рядку першої клітини записано значення цільової функції на опорному плані : 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	x 1	x 2	x 3	x 4	x 5	x 6	x 7
–12	–7	–18	–10
x 5		14/3	2/3			–2/3			–1/3
x 6		10/3	1/3	–1		–1/3			–2/3
x 3	–18	40/3	1/3			2/3			1/3
	–240		–11		–2			–6

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

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

.

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

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

Таблиця 3.3

Б	cб	b	x 1	x 2	x 3	x 4	x 5	x 6	x 7
–12	–7	–18	–10
x 1	–12			3/2		–1	3/2		–1/2
x 6				–3/2			–1/2		–1/2
x 3	–18			1/2			–1/2		1/2
	–282		–20			–9		–3

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

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

.

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

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

Таблиця 3.4

Б	cб	b	x 1	x 2	x 3	x 4	x 5	x 6	x 7
–12	–7	–18	–10
x 1	–12
x 6				–3/2			–1/2		–1/2
x 4	–10			1/2			–1/2		1/2
	–326		–22	–4		–7		–5

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

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

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

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

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

,

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

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

Дата добавления: 2014-11-06