Navch._posibnuk_Ivaschyk

відповідних додатних елементів ключового стовпця (нульовий рядок не розглядаємо) і вибираємо найменше з цих відношень. Невідому, яка відповідає цьому відношенню, виключаємо з базису. Рядок, який відповідає цьому найменшому відношенню, називається ключовим рядком. На перетині ключового рядка і ключового стовпця знаходиться ключовий (генеральний) елемент. За допомогою генерального елемента і методу Жордана-Гауса переходимо до нової симплекс-таблиці.

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

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

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

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

Оскільки економістів цікавлять практичні рекомендації, які можна дати стосовно розв’язання задачі, то в якості прикладу застосування симплекс-методу візьмемо конкретну задачу про використання сировини.

Приклад 2.3. Для виготовлення двох видів продукції П1 та П2 використовуються три види сировини S1, S2 та S3. Запаси сировини, норми витрат сировини на виготовлення одиниці продукції кожного виду та дохід від одиниці продукції кожного виду наведені в таблиці:

Вид	Запаси	Витрати сировини на виготовлення
		одиниці продукції
сировини	сировини
		П1		П2
S1	275	4		5
S2	680	13		8
S3	60	1		1
Дохід від одиниці продукції		9		6

Необхідно знайти такий план виробництва, який забезпечить найбільший сумарний дохід.

71

♦ Розв’язування.

Побудуємо математичну модель задачі. Нехай x1 та х2 – загальна кількість відповідно продукції П1 та П2; Z – сумарний дохід, який отримаємо від реалізації виробленої продукції. Тоді математична модель задачі матиме вигляд:

Z = 9x1 + 6x2 (max),

4x1 + 5x2 ≤ 275,13x1 +8x2 ≤ 680,

x1 + x2 ≤ 60,x1 ≥ 0,

x ≥ 0.2

Приведемо задачу до канонічного виду:

Z = 9x1 + 6x2											(max),
4x + 5x				2	+ x			3		= 275,
	1
13x1 +8x2 + x4										= 680,
x	+ x	2	+ x			5	= 60,
1
	≥ 0,				i =1,5.
xi

Розв’яжемо цю задачу симплекс-методом. Заповнимо початкову таблицю:

Таблиця 2.1

	№		№	Базис	Опорний	Коефіцієнти при невідомих
	таблиці		рядка		план	х1↓	х2	х3	х4	х5
		0		Z	0	–9	–6	0	0	0
	1		1	х3	275	4	5	1	0	0
		2		х4←	680	13	8	0	1	0
		3		х5	60	1	1	0	0	1

Ітерація 1. В нульовий рядок заносимо інформацію про цільову функцію, а в рядки 1-3 дані з відповідних рівнянь системи обмежень. Для заповнення нульового рядка початкової симплекс-таблиці цільову функцію запишемо в такому ж вигляді, як обмеження задачі, тобто у вигляді рівняння Z −9x1 −6x2 = 0 (всі невідомі перенесемо в

ліву частину), і в подальшому нульовий рядок будемо заповнювати

72

так само, як і рядки 1-3, що відповідають обмеженням. В стовпчику «Базис» записуємо базисні невідомі з системи обмежень, а для нульового рядка базисною невідомою є Z. В стовпчику «Опорний план» записуємо значення базисних невідомих, коли вільні невідомі х1 та х2 дорівнюють нулю (праві частини рівнянь-обмежень та цільової функції). В наступних стовпчиках записуємо коефіцієнти при невідомих в цільовій функції та системі обмежень.

Випишемо з першої таблиці початковий опорний план

хопорн.=(0; 0; 275; 680; 60). Знайдемо значення цільової функції на цьому плані Z(хопорн.)=9·0+6·0=0. Перевіримо, чи даний опорний план є оптимальним. Для визначення ступеня оптимальності опорного

плану використовується нульовий рядок. Цільова функція досліджується на максимум, значить для оптимальності опорного плану в нульовому рядку не має бути від’ємних чисел. В нас в нульовому рядку є два від’ємних числа ((-9) та (-6)), значить досліджуваний опорний план не є оптимальним. Вибираємо найменше з цих чисел (-9) і стовпець, в якому знаходиться це число є ключовим, а невідому x1, яка відповідає цьому стовпцю потрібно ввести в базис. Ставимо біля цієї невідомої стрілочку (якщо цільова функція мінімізується і в нульовому рядку є додатні числа, то вибираємо найбільше з цих чисел і за ним визначаємо, яку невідому потрібно ввести в базис). Щоб визначити, яку з невідомих потрібно вивести з базису, складаємо відношення елементів стовпця «Опорний план» до відповідних додатних елементів ключового стовпця і вибираємо найменше з цих відношень:

275 : 4 = 68,75; 680:13 = 52,3; (min) 60:l=60.

Невідому, яка відповідає цьому найменшому відношенню (в нашому випадку х4) виводимо з базису. Ставимо біля цієї невідомої стрілочку, а рядок, якому відповідає це найменше відношення називається ключовим. На перетині ключового рядка і ключового стовпця знаходиться ключовий (генеральний) елемент, рівний 13.

Ітерація 2. Переходимо до другої симплекс-таблиці. Замість невідомої х4 в базис вводимо невідому x1. На місці ключового елемента нам потрібно отримати 1, а всі інші елементи в стовпці повинні дорівнювати нулю. Для цього ключовий рядок ділимо на ключовий (генеральний) елемент, тобто на 13, і результат записуємо на місці другого рядка табл. 2.2. Усі інші рядки табл. 2.2 заповнюємо

73

методом Жордана-Гауса, послідовно виключаючи невідому x1 з нульового, першого та третього рядків:

1)множимо почленно другий рядок на 9 і додаємо відповідні елементи нульового рядка табл. 2.1, результат записуємо на місці нульового рядка табл. 2.2;

2)множимо кожен елемент другого рядка на (–4) і додаємо відповідні елементи першого рядка табл. 2.1, результат записуємо на місці першого рядка табл. 2.2;

3)множимо кожен елемент другого рядка на (–1) і додаємо відповідні елементи третього рядка табл. 2.1, результат записуємо на місці третього рядка табл. 2.2.

Таблиця 2.2

№	№		Базис		Опорний					Коефіцієнти при невідомих
таблиці	рядка					план				х1		х2↓								х3		х4					х5
	0		Z			6120				0		−			6					0		9					0
						13															13
												13
	1		х3			855				0		33								1	−		4				0
						13						13
2																					13
	2		х1				680			1				8						0		1					0
						13						13									13
						100															−			1
	3		х5←							0				5						0							1
						13							13
																					13
Ми отримали новий опорний план:
		xопорн.				680		; 0;		855	;	0;			100
				=		13				13					13
																				.

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

Z (xопорн. ) = 9 68013 + 6 0 = 612013 = 470,77.

Перевіримо цей опорний план на оптимальність. В нульовому рядку є ще від’ємне число ( −136 ), значить вищезгаданий опорний план не є оптимальним. Невідому, яка відповідає цьому стовпцю (x2)

74

вводимо в базис. Ставимо біля цієї невідомої стрілочку. Складаємо відношення елементів стовпця «Опорний план» до відповідних додатних елементів ключового стовпця і вибираємо найменше з цих відношень:

	855	:		33			= 25,9;
	13		13
	680	:			8		= 85;
	13		13
	100	:		5			= 20 (min).
	13		13

Невідому, яка відповідає цьому найменшому відношенню (в нашому випадку х5) виводимо з базису. Ставимо біля цієї невідомої

стрілочку. Ключовий елемент – 135 .

Ітерація 3. Переходимо до третьої симплекс-таблиці. Замість невідомої х5 в базис вводимо невідому х2. Ключовий (третій) рядок

ділимо на 135 і результат записуємо на місці третього рядка табл. 2.3.

Знову використаємо метод Жордана-Гауса, послідовно виключаючи невідому х2 з нульового, першого та другого рядків:

1)множимо почленно третій рядок на 136 і додаємо відповідні елементи нульового рядка табл. 2.2, результат записуємо на місці нульового рядка табл. 2.3;

2)множимо кожен елемент третього рядка на (−1333 ) і додаємо відповідні елементи першого рядка табл. 2.2, результат записуємо на місці першого рядка табл. 2.3;

3)кожен елемент третього рядка множимо на (−138 ) і додаємо відповідні елементи другого рядка табл. 2.2, результат записуємо на місці другого рядка табл. 2.3.

75

							Таблиця 2.3
№	№	Базис	Опорний	Коефіцієнти при невідомих
таблиці	рядка		план	х1	х2	х3	х4			х5
	0	Z	480	0	0	0		3		6
								5		5
	1	х3	15	0	0	1	1			− 33
3							5			5
	2	х1	40	1	0	0		1		−		8
							5
										5
	3	х2	20	0	1	0	− 1			13
							5			5

В нульовому рядку останньої таблиці немає від’ємних чисел, а значить ми отримали оптимальний розв’язок: хопт=(40; 20; 15; 0; 0),

Zmax = 480.

Отже, максимальний дохід становитиме Zmax=480, якщо продукції П1 виготовити 40 одиниць (х1=40 ), а продукції П2 – 20 одиниць (х2=20).

Перевірка: Zmax= 9·40 + 6·20 = 360 +120 = 480.

Невідомі х4=0 та х5=0, а це означає, що сировина S2 та S3 використана повністю, х3=l5, значить сировина S1 є в залишку (недовикористана) 15 одиниць. ♦

Як зазначалось, при розв’язуванні задач лінійного

програмування можливі випадки, коли оптимального плану задачі лінійного програмування не існує (цільова функція необмежена) або існує неєдиний розв’язок задачі. Розглянемо ці випадки.

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

Z = 7x1 + 3x2 −12 (max),5x1 − 6x2 ≤ 30,

13x1 −8x2 ≤104,

x1 ≥ 0,x2 ≥ 0.

76

♦Розв’язування.

Запишемо задачу в канонічній формі:

				Z = 7x1 +3x2 −12											(max),
				5x		−6x	+ x = 30,
					1	2	3
				13x1 −8x2 + x4 =104,
					≥ 0,		i =1,4
				xi
і розв’яжемо симплекс-методом:
	№ таблиці	рядка№	Базис	Опорний план		Коефіцієнти при
							невідомих
						х1↓			х2						х3						х4
		0	Z	-12		–7			–3							0				0
	1	1	х3←	30		5			–6							1				0
		2	х4	104		13			–8							0				1
		0	Z	30		0	− 57 ↓									7				0
							5									5
	2	1	х1	6		1		− 6								1				0
							5									5
																13
		2	х4←	26		0			38						−					1
								5								5
		0	Z	66		0	0								− 5					3
																2				2
	3	1	х1	192		1	0								−		4				3
				19												19				19
		2	х2	65		0	1								−	13				3
				19												38					38

30:5=6 (min) :5 104:13=8

•7; •(-13)

: 385

• 575 ; • 65

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

від’ємне число (− 52 ), отже, невідому х3 потрібно ввести в базис. Але

ми бачимо, що в ключовому стовпчику, що відповідає змінній х3, немає додатних чисел, значить ні х1, ні х2 виключити з базису не можна. Це свідчить про те, що при таких обмеженнях оптимального плану задачі не існує ( Zmax = +∞).♦

77

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

Z = −16x1 −18x2 +13 (min),
−5x1 +3x2 ≤15,
		≤ 35,
7x1 −5x2
		≤ 72,
8x1 +9x2
x	≥ 0,
1
	≥ 0.
x2

♦ Розв’язування.

Приведемо задачу до канонічної форми (додамо до лівих частини перших трьох обмежень відповідно змінні х3, х4 та х5, щоб отримати рівності) і розв’яжемо її симплекс-методом:

№ таблиці	№рядка		Базис	Опорний план	Коефіцієнти при невідомих
					х1		х2		х3				х4		х5
		0	Z	13	16		18↓	0					0	0
1		1	х3←	15	–5		3	1					0	0
		2	х4	35	7		–5	0					1	0
		3	х5	72	8		9	0					0	1
		0	Z	–77	46↓		0		–6				0	0
		1	х2	5	−	5	1	1					0	0
2						3		3
		2	х4	60	−	4	0	5					1	0
						3		3
		3	х5←	27	23		0		–3				0	1
		0	Z	–131	0		0	0					0		–2
		1	х2	160		0	1		8				0		5
3				23				69						69
		2	х4	1416	0		0	103					1		4
				23				69						69
		3	х1	27	1		0	−		2			0		1
				23										23
								23

15:3=5 (min) :3

72:9=8

•(-18); •5; •(-9)

:23

•(–46); • 53 ; • 34

78

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

Z	min	= −131	при		x = 27		,	x	2	= 160	,	x	= 0,	x	4	= 1416	,	x = 0.
					1	23				23		3				23		5
		Перевірка:
								− 432 − 2880
	Zmin = −16		27	−18	160	+13 =							+13	= −144 +13 = −131.
			23		23					23

Але бачимо, що вільній невідомій x3 в нульовому рядку відповідає 0, що свідчить про те, що оптимальний розв’язок неєдиний. Введемо невідому x3 в базис замість невідомої x4, тому що найменше відношення елементів стовпця «Опорний план» до додатних елементів ключового стовпця відповідає рядку, в якому в базисі знаходиться змінна х4.

№ таблиці		№рядка		Опорний план	Коефіцієнти при невідомих
			Базис		х1	х2						х3								х4							х5
		0	Z	–131	0	0						0↓								0							–2
		1	х2	160	0	1						8								0							5				160				:		8	=60
				23					69																69								23
3																																			69
		2	х4←	1416	0	0				103										1					4							1416				:103			=41,24
				23							69																69							23		69			min
		3	х1	27	1	0				−			2							0							1
				23																					23
									23
		0	Z	-131	0	0			0											0							–2
		1	х2	224	0	1			0								−				8					7
4				103																103					103
		2	х3	4248	0	0			1											69						4
				103													103								103
		3	х1	675	1	0			0											9						5
				103													103								103
		В результаті симплекс-перетворень ми отримали новий
оптимальний план нашої задачі:
Z	min	= −131 при x = 675 ,				x	2	=	224 ,								x			= 4248 ,										x			4	= 0,					x = 0.
				1	103				103								3						103																5

79

	Перевірка:
Zmin	= −16	675		−18	224	+13 =	−10800 − 4032	+13 = −144 +13 = −131.
					103		23
	103
	Значення цільової					функції при обох планах однакове і рівне

(-131). Проте цими двома планами не вичерпується множина оптимальних розв’язків задачі. З геометричної інтерпретації розв’язування задач лінійного програмування відомо, що у випадку неєдиності розв’язку для двох змінних (на площині) кожна точка відрізка, який з’єднує дві оптимальні вершини многокутника допустимих розв’язків, також оптимальна. Якщо х(1) та х(2) оптимальні плани задачі, то координати кожної точки відрізка, що їх з’єднує, можна знайти за формулою: x(λ) = λx(1) + (1−λ)x(2) , де λ [0;1].♦

2.4. Метод штучного базису

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

n

∑aij x j ≤ bi , bi ≥ 0, i =1, m.

j =1

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

Метод штучного базису дає змогу з’ясувати, чи має система обмежень допустимі плани, а також вказує шляхи їх знаходження.

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

Z = c0 + c1x1 + c2 x2 +... + cn xn (max),

(2.21)

80