Графічний метод розв’язування злп

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

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

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

Приклад. Розв’язати графічним методом задачу лінійного програмування.

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

Нормаль: .

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

.

Знайдемо максимальне значення цільової функції

Відповідь: при опорному плані .

Симплексний метод

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

1) спосіб вибору початкового опорного плану допустимого базисного розв’язку;

2) правило переходу до кращого (не гіршого) розв’язку; 3) критерій перевірки оптимальності знайденого розв’язку (опорного плану).

Розглянемо симплексний метод на прикладі.

Приклад. Знайти оптимальний розв’язок ЗЛП:

Розв’язання. При використанні симплексного методу ЗЛП повинна бути приведена до канонічного вигляду, тобто система обмежень повинна бути записана у вигляді рівнянь. За допомогою нових змінних і , які додаємо до кожного обмеження, одержимо систему рівнянь. Ці нові змінні введемо у цільову функцію із нульовими коефіцієнтами і одержимо:

Позначимо: якщо вважати, що то а опорний план , тоді

Матриці мають вигляд:

За базисні вибираємо одиничні матриці

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

Таблиця 1.

і	Базис	Сбаз
1		0	5	3	1	-1	1	0
2		0	6	1	2	1	0	1
т + 1				-3	-4	-1	0	0

Оцінки в – ому рядку обчислюються за формулами:

(3)

Зауваження. Для таблиці 1 добуток матриць = 0, бо .

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

Вектор виводимо із базису. Для побудови таблиці 2 поділимо на число 2 всі елементи матриць від до в другому рядку.

Таблиця 2.

і	Базис	Сбаз							(-1)*(4)
1		0	5	3	1	-1	1	0
2		4	3	1/2	1	1/2	0	1/2
т + 1				-3	-4	-1	0	0
1		0	2	5/2	0	-3/2	1	-1/2
2		4	3	1/2	1	1/2	0	1/2
т + 1			12	-1	0	1	0	2

Опорний план , для якого , можна покращити, бо в рядку є оцінка Стовпець введемо в базис. Знайдемо ще направляючий рядок: Це буде перший рядок. Всі елементи в цьому рядку від до поділимо на і побудуємо таблицю 3.

Таблиця 3.

і	Базис	Сбаз							(-1/2)∙(1)
1		3	4/5	1	0	-3/5	2/5	-1/5
2		4	3	1/2	1	1/2	0	1/2
т + 1			12	-1	0	1	0	2
1		3	4/5	1	0	-3/5	2/5	-1/5
2		4	13/5	0	1	4/5	-1/5	3/5
т + 1			64/5	0	0	2/5	2/5	9/5

В – ому рядку всі оцінки , то одержаний опорний план є оптимальним, а значення цільової функції є максимальним.