Приклад розв’язування задачі

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

(min)

Розв’язання

Зводимо задачу до канонічного вигляду:

Запишемо рівняння у векторній формі:

Р₁х₁ + Р₂х₂ + Р₃х₃ + Р₄х₄ + Р₅х₅ = Р₀

, , , , ,

Серед векторів є тільки один одиничний, тому вводимо штучну змінну :

.

До цільової функції також вводимо відповідні штучні змінні із коефіцієнтом :

.

Складемо першу симплекс-таблицю (таблиця 2.36):

Таблиця 2.36 – Перша симплекс-таблиця

і	Базис	Сбаз	План			-3			М
х1	х2	х3	х4	х5	х6
	x6	М	7	1	1	-5	-1	0	1	7
	х5	0	6	1	0	2	0	1	0
	m+1	-	0	-1	-3	3	0	0	0
	m+2	-	7М	М	М	-5М	-М	0	0

Заповнимо оцінкові рядки (m+1) та (m+2) за формулою при цьому розділяючи значення без та с коефіцієнтом :

,

і т.д.

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

Оскільки для розв’язування задачі використовується метод штучного базису, то спочатку на оптимальність перевіряють за (m+2)-им рядком (це відбувається доти доки з базису не будуть виведені всі штучні змінні).

За (m+2)-им рядком видно, що умова оптимальності не виконується оскільки цей ряд містить додатні числа. Виберемо серед них найбільше за абсолютною величиною. У першому та у другому стовпчику стоять числа 2, які є найбільшими серед тих, що не задовольняють умову оптимальності. Виберемо одне з них навмання. Нехай це буде другий стовпчик .

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

Розв’язувальним елементом є число 1.

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

Таблиця 2.37 – Друга симплекс-таблиця

і	Базис	Сбаз	План
х1	х2	х3	х4	х5
	х2	3	7	1	1	-5	-1	0	7
	х5	0	6	1	0	2	0	1	6
	m+1	-	21	2	0	-12	-3	0

Так як у базисі більше нема штучної змінної, то перевіряти на оптимальність будемо за (m+1)-им рядком. Розв’язувальним елементом є число 1.

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

Таблиця 2.38 – Третя симплекс-таблиця

і	Базис	Сбаз	План
х1	х2	х3	х4	х5
	х2	3	1	0	1	-7	-1	-1
	х1	1	6	1	0	2	0	1
	m+1	-	9	0	0	-16	-3	-3

Оскільки усі елементи (m+1)- го рядкавід’ємні (тобто виконується умова оптимальності), то ми отримали оптимальний розв’язок: , , , .

Приклад 2. Знайти максимум функції:

Обмеження:

Розв’язання

Зводимо задачу до канонічного вигляду:

Запишемо рівняння у векторній формі:

Р₁х₁ + Р₂х₂ + Р₃х₃ + Р₄х₄ + Р₅х₅ = Р₀

, , , , ,

Серед векторів є тільки один одиничний, тому вводимо дві штучні змінні , :

,

До цільової функції також вводимо відповідні штучні змінні із коефіцієнтом :

.

Складемо першу симплекс-таблицю (таблиця 2.39):

Таблиця 2.39 – Перша симплекс-таблиця

і	Базис	Сбаз	План						–М	–М
х1	х2	х3	х4	х5	х6	х7
	x6	–М	8	-7	1	-1	0	0	1	0
	х4	0	33	3	2	0	1	0	0	0	11
	х7	–М	54	9	1	0	0	-1	0	1	6
	m+1	-	0	-7	-5	0	0	0	0	0
	m+2	-	-87М	-2М	-2М	М	0	М	0	0

Заповнимо оцінкові рядки (m+1) та (m+2) за формулою при цьому розділяючи значення без та с коефіцієнтом :

,

і т.д.

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

Оскільки для розв’язування задачі використовується метод штучного базису, то спочатку на оптимальність перевіряють за (m+2)-им рядком (це відбувається доти доки з базису не будуть виведені всі штучні змінні).

За (m+2)-им рядком видно, що умова оптимальності не виконується оскільки цей ряд містить від’ємні числа. Виберемо серед них найбільше за абсолютною величиною. У першому та у другому стовпчику стоять числа 2, які є найбільшими серед тих, що не задовольняють умову оптимальності. Виберемо одне з них навмання. Нехай це буде перший стовпчик .

Обчислимо стовпчик та виберемо з цих чисел найменше (перше співвідношення не обчислювали оскільки число (-7) від’ємне).

Розв’язувальним елементом є число 9.

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

Таблиця 2.40 – Друга симплекс-таблиця

і	Базис	Сбаз	План						–М
х1	х2	х3	х4	х5	х6
	х6	-М	50	0		-1	0		1	28,125
	х4	0	15	0		0	1		0	9
	х1	7	6	1		0	0		0	54
	m+1	-	42	0		0	0		0
	m+2	-	-50М	0		М	0		0

Оскільки в п’ятому рядку таблиці присутні від’ємні значення, то переходимо до наступної симплекс-таблиці. Аналогічно до попереднього заповнимо третю симплекс-таблицю (таблиця 2.41).

Таблиця 2.41 – Третя симплекс-таблиця

і	Базис	Сбаз	План						-М
х1	х2	х3	х4	х5	х6
	х6	-М	34	0	0	-1			1
	х2	5	9	0	1	0			0
	х1	7	5	1	0	0			0
	m+1	-	80	0	0	0			0
	m+2	-	-34М	0	0	0			0

Оскільки усі елементи 5-го рядка додатні, тобто умова оптимальності виконується, але одна із штучних змінних ще не виведена з базису, то задача немає розв’язку.

Завдання для індивідуальної та самостійної роботи студентів

Номер варіант визначається за вказівкою викладача.

1.	16.
2.	17.
3.	18.
4.	19.
5.	20.
6.	21.
7.	22.
8.	23.
9.	24.
10.	25.
11.	26.
12.	27.
13.	28.
14.	29.
15.	30.

Дата добавления: 2017-02-01