Практичне заняття 2.2

Тема: Розв’язування задачі лінійного програмування симплексним методом

 

Мета заняття: отримання навичок розв’язування задач лінійного програмування симплекс-методом

Приклад 1

Максимізувати функцію , при обмеженнях:

Розв’язок: Зводимо цільову функцію та систему обмежень до канонічної форми, шляхом введення додаткових змінних:

,

при обмеженнях:

Будуємо симплекс-таблицю:

Таблиця 2.1

 

Заповнюємо елементи індексного рядка:  

Інші елементи індексного рядка заповнюються нулями.

Значення цільової функції при цьому буде наступним:

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

Позначаємо розв’язуючий рядок стрілкою. На перетині РС та РР  знаходиться РЕ, який дорівнює 1.

Виконуємо симплекс-перетворення (п.1,2,3). Результати записуємо в таблицю 2.2.

Таблиця 2.2

Значення цільової функції при цьому буде:

Так як в індексному рядку є від’ємні елементи, то це говорить про те, що є можливість покращення оптимального плану.

Вибираємо розв’язуючий стовпчик – ним буде перший стовпчик . Позначаємо його стрілкою. Тепер вибираємо розв’язуючий рядок:  Отже РЕ буде елемент х₁₃=1. Виконуємо симплекс-перетворення, результати записуємо в таблицю 2.3.

Таблиця 2.3

 

Оскільки в індексній стрічці усі ∆_j>0, то це значить знайдено оптимальний план. Максимальне значення цільової функції:

 

Приклад 2

Нехай необхідно мінімізувати функцію , на яку накладено наступні обмеження:

Розв’язок: Зводимо цільову функцію та систему обмежень до канонічної форми, шляхом введення додаткових змінних :

при обмеженнях:

Так як змінні  та  є від’ємними, то необхідно ввести штучні змінні  та . Тоді цільова функція та обмеження будуть мати вигляд:

Надалі, використовуючи алгоритм симплекс-методу, який докладно показаний в прикладі 1, знайдемо оптимальний розв’язок задачі (таблиці 2.4, 2.5, 2.6).

Таблиця 2.4

Сі			8	11	0	0	0	M	M
	Вх	аі0	А1	А2	А3	А4	А5	А6	А7
М	X6	380	1	1	-1	0	0	1	0
0	X4	830	4/5	1	0	1	0	0	0
М	X7	83	0	1	0	0	-1	0	1
	∆j	0	-8	-11	0	0	0	0	0
М-рядок		463	1	2	-1	0	-1	0	0

 

Таблиця 2.5

Сі			8	11	0	0	0	M	M
	Вх	аі0	А1	А2	А3	А4	А5	А6	А7
M	X6	297	1	0	-1	0	1	1	0
0	X4	747	4/5	0	0	1	1	0	0
11	X2	83	0	1	0	0	-1	0	0
	∆j	913	-8	0	0	0	-11	0	0
М-рядок		297	1	0	-1	0	1	0	0

 

Таблиця 2.6

 

Так як в індексному рядку не має додатних елементів, то це означає, що отримано оптимальний план:  Мінімум цільової функції при цьому рівний