ММДО_МУ по ПЗ(+)

		Cj		C1	C2	C3	C4	C5	C6	C7	C8
i		Ci	x=P0	P1	P2	P3	P4	P5	P6	P7	P8
1	P6	M	6	3	2	-1	0	0	1	0	0	2
2	P7	M	6	6	1	0	-1	0	0	1	0	1
3	P8	M	1	0	1	0	0	1	0	0	1	1
4	Zj		13M	9M	4M	-M	-M	-M	M	M	M
5	Zi-ci=∆			9M-15	4M-33	-M	-M	-M	0	0	0

Оскільки задача на мінімізацію, то ведучий стовпчик визначається за максимумом останнього рядка. Це P1=Pk. Ведучий рядок визначається за min . Згідно з таблицею 1.6 це другий рядок, тобто P7=P1, x1k=6.

Виконуючи перерахування симплекс-таблиці 1.6 за допомогою формул (1.37), (1.38), складаємо симплекс таблицю 1.7.

У цій таблиці максимальним елементом останнього рядка є P2, min у третьому рядку. Отже, ведучий стовпчик Pk=P2, ведучий рядок P1=P8, ведучий елемент P23=P1k=1.

Таблиця 1.7 – Проміжний план М-задачі

				Cj			15			33				0	0		0			M			M		M
i				Ci		x=P0	P1			P2				P3	P4		P5			P6			P7		P8
1		P6		M		3	0			11/2				-1	1/2		0			1			-1/2		0	2
2		P1		15		1	1			1/6				0	-1/6		0			0			1/6		0	6
3		P8		M		1	0			1				0	0		-1			0			0		1	1
4		Zj				4M	15			5/2M+5/2				-M	M/2-5/2		-M			M			-M/2+5/2		M
5		Zi-ci=∆					0			5/2M-61/2				-M	M/2-5/2		-M			0			-3/2M+5/2		0
		Після виконання необхідних обчислень маємо таблицю 1.8
		Таблиця 1.8 – Наступний проміжний план
				Cj				15			33	0	0			0			M			M		M
i				Ci		x=P0		P1			P2	P3	P4			P5			P6			P7		P8
1		P6		M		11/2		0			0	-1	1/2			11/2			1			1/2		-11/2		1
2		P1		15		5/6		1			0	0	-1/6			1/6			0			½		-1/6		5
3		P2		33		1		0			1	0	0			-1			0			0		1
4		Zj				3/2M		15			33	-M	M/2-15/6			3/2M-			M			M/2+15/2		-
						+45/2										61/2								3/2M-
																								61/2
5		Zi-ci=∆						0			0	-M	M/2-15/6			3/2M-			0			15/2+M/2		-
																61/2								5/2M-
																								61/2

Тут ведучий стовпчик P5=Pk, min=1, ведучий рядок P6. Перерахувавши таблицю 1.8, отримаємо таблицю 1.9.

Таблиця 1.9 – Кінцевий опорний план М-задачі

		Cj		15	33	0	0	0	M	M	M
i		Ci	x=P0	P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	1	0	0	-2/3	1/3	1	2/3	-1/3	-1	1/3
2	P1	15	4/6	1	0	1/9	-2/9	9	-1/9	2/9	0	-
3	P2	33	2	0	1	-2/3	1/3	0	2/3	-1/3	0	2/3
4	Zj		76	15	33	-61/3	46/6	0	61/3	-46/6	0
5	Zi-ci=∆			0	0	-61/3	46/6	0	61/3-M	-46/6-M	-M

У таблиці 1.9 всі штучні змінні виведені із базису. Далі продовжується розв’язання задачі за допомогою звичайного симплекс-методу.

Виконавши ще одну ітерацію, перерахувавши таблицю 1.9, склавши ще одну таблицю (це ми доручаємо виконати читачеві), досягаємо оптимального плану

41 = 3 , 2 = 1, 4 = 3, тобто = (4/3, 1,0,3).

= 53

1. Знайти графічним методом простір рішень для такої сукупності нерівностей 1 + 2 ≤ 4, 1 + 3 2 ≤ 12, − 1 + 2 ≥ 1, 1 + 2 ≤ 6, 1, 2 ≥ 0.

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

2. Зведіть лінійну оптимізаційну модель до стандартної форми:

максимізувати = 2 1 + 3 2 + 5 3,

за обмежень	1 + 2 − 3 ≥ −5,
	−6 1 + 7 2 − 9 3 ≤ 4,
	1 + 2 + 3 = 10,
	1, 2 ≥ 0.

3. Максимізувати = 2 1 − 4 2 + 5 3 − 6 4,

за обмежень

1 + 4 2 − 2 3 + 8 4 ≤ 2, − 1 + 2 2 + 3 3 + 4 4 ≤ 1,1, 2, 3, 4 ≥ 0.

Визначне максимальну кількість можливих базисних рішень; ідентифікуйте припустимі екстремальні точки; знайдіть припустиме базисне рішення.

1.5 Контрольні запитання і завдання

1.Сформулюйте загальну задачу математичного програмування (ЗМП).

2.У яких формах можна записати ЗЛП?

3.Назвіть необхідні і достатні умови того, що ЗЛП має розв’язок.

4.Чи можливо, щоб оптимальний розв’язок знаходився в середині ОПР?

5.Наведіть алгоритм графічного методу розв’язання ЗЛП.

6.Що геометрично визначає нерівність вигляду 11 1 + 12 2 ≤ на площині?

7.Що потрібно знайти для реалізації методу послідовного поліпшення

плану?

8.Що є ознакою необмеженості цільової функції за припустимою множиною рішень?

9.Опишіть алгоритм симплекс-методу.

10.Яке призначення методу штучної бази?

11.Як визначити оптимальність припустимого базисного розв’язку?

2СПЕЦІАЛЬНІ МЕТОДИ РОЗВ’ЯЗАННЯ ЗЛП

2.1Знаходження початкового опорного плану транспортної задачі.

Мета заняття - закріплення лекційного матеріалу та набуття практичних навичок знаходження початкового опорного плану транспортної задачі.

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

Т-задачу можна розв'язати розподільним методом, методами потенціалів, диференціальних рент, розв'язувальних додатків тощо.

Розв'язання Т-задачі за допомогою ручних методів полягає у виконанні таких етапів: визначення початкового опорного плану задачі, оцінка цього плану, перехід до наступного, кращого, плану шляхом заміни однієї із базисних змінних на вільну.

Існує декілька простих методів знаходження початкового опорного плану Т-задачі: північно-західного кута (діагональний), мінімальної вартості, подвійних позначок, Фотеля тощо.

Згідно з правилом північно-західного кута, спочатку знаходять величину

11 = min{ 1, 1}.		Якщо 1 > 1, то 11 = 1 і перший стовпчик закритий для
розрахунку інших		елементів,				тобто			= 0, = 2,3, … , . Якщо						< , то
								1						1	1
11 = 1	і 1 = 0 для = 2,3, … , .
Потім обчислюють 12 = min{ 1								− 11, 2} за 1 > 1,						21 = min{ 2, 1 −
11} за	1 < 1.	Цей		продовжується					доти, доки на якомусь етапі не
вичерпаються ресурси am і не задовольнятся потреби bn.
Під час підготовки до заняття необхідно використовувати таку літературу:
[2, с. 75-79; 3, с. 84-87; 4, с. 3-8].
	Дано: матрицю транспортних витрат											= ‖		̅̅̅̅̅̅	̅̅̅̅̅
														‖, = 1, , = 1, ,
обсяги виробництва ai, обсяги споживання bj.
					B1		B2	B3		B4		ai
			A1		1		2	9		7		60
	C=
			A2		3		4	1		5		55
			A3		6		4	8		3		40
			A4		2		3	3		1		35
			bj		70		5	45		70

Перевіряємо умови балансу:

∑ = ∑ : 190 = 190
=1	=1
Будуємо початковий опорний план Х0:
	1	1 2 3 4
0 =	2	60 0 0 0
		‖10 5 40 0 ‖
	3	0 0 5 35
	4	0 0 0 35
11 = min{60,70} = 60,		21 = min{55,70 − 60} = 10
22 = min{5,55 − 10} = 5,		23 = min{45,55 − 10 − 5} = 40
33 = min{40,45 − 40} = 5,		34 = min{70,45 − 5} = 35, 44 = 35.

Отриманий план не вироджений, оскільки r=4+4-1=7.

Початковий опорний план можна знайти за допомогою мінімального елемента. Цей метод дозволяє отримати опорний план з урахуванням матриці вартості перевезень = ‖ ‖. План будуємо так, щоб перевезення xij виконувалися, можливо, за маршрутами з мінімальною вартістю. Після цього елементи матриці С

	B1	B2	B3	B4	ai
A1	1	2	9	7	60
A2	3	4	1	5	55

	A3	6	4	8	3	40
	A4	2	3	3	1	35
C=
	bj	70	5	45	70

нумеруємо, починаючи з мінімального у порядку збільшення, а потім у такому ж порядку визначаємо елементи матриці Х:

11 = min{60,70} = 60,		23 = min{55,45} = 45,
44	= min{35,70} = 35,	12 = 0,	41 = 0,
21	= min{55,70 − 60} = 10, 42 = 0,
43	= 0, 34 = min{40,75 − 35} = 35,		22 = 0,
32	= min{40 − 35,5} = 5.

Елементи матриці Х, що відповідають С24, С31, С14, С33, С13, не розглядаються, тому що вичерпані всі ресурси і задоволені всі потреби.

Будуємо опорний план Х0,			заповнюючи хij у порядку отриманої
нумерації:
		1	1 2 3 4
0	=	2	60 0 0 0
			‖10 0 45 0 ‖
		3	0 5 0 35
		4	0 0 0 35

Побудований план вироджений, оскільки кількість ненульових елементів≠ 0 дорівнює 6, а r=m+n-1.

При визначенні оптимального плану Т-задачі за допомогою методу апроксимації Фогеля на кожній ітерації за всіма стовпчиками і за всіма рядками знаходять різницю між двома записаними в них мінімальними елементами. Ці різниці записують у спеціально відведених рядку і стовпчику у таблиці умов задачі. Серед зазначених різниць обирають мінімальну, У рядку (або у стовпчику), якому дана різниця відповідає, визначають мінімальний тариф. Клітинку, в який він записаний, заповнюють на даній ітерації.

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

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

Наближений метод Фогеля є евристичним і призводить до кращого початкового розв’язання, ніж розглянутий вище метод. Тому його зручно

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

Початкову транспортну матрицю подамо у таблиці 2.1.

Таблиця 2.1 – Початкова транспортна матриця

	B1		B2		B3	B4	ai			Стовпчики
A1	60 1			2	3	4	60	1	1	1	–	–	–
A2	10 3			4	45 1	5	55	2	1	1	–	–	–
A3		6	3	4	8	35 3	40	1	1	1	1	–	–
A4		2		3	3	35 1	35	1	1	1	2	–	–
bj	70		5		45	70
	1		1		2	2
Рядки	1		1		–	2
	–		1		–	2
	–		1		–	2
	–		3		–	–
	–		–		–	–

Ця таблиця заповнюється таким алгоритмом:

1.Обчислення штрафу для кожного рядка (стовпчика), віднімаючи найменший елемент цього рядка (стовпчика) із наступного за ним за величиною елемента того ж рядка (стовпчика). Різниці по рядках запишемо праворуч у стовпчики різниць, різниці по стовпчиках – знизу у рядку різниць. Наприклад, для рядка А1, різниця дорівнює А1В2-А1В1=2-1=1 тощо.

2.Пошук рядка або стовпчика з найбільшим штрафом, а якщо таких декілька, то можна обирати серед них будь-який рядок або стовпчик. У нашому прикладі максимальна різниця має місце у рядку А7 і дорівнює 2, а також у стовпчику В3 і дорівнює 2. В обраному рядку або стовпчику вибираємо (максимальну різницю обведемо рамкою) змінні з мінімальною вартістю і до цієї клітинки заносимо максимально можливу кількість ресурсів (залежно від потреби у стовпчику або від наявності у рядку). Якщо задовільнена потреба, то виводимо з розрахунку відповідний стовпчик, а якщо вичерпані ресурси – відповідний рядок. Якщо обмеження за потребою і наявним ресурсом виконуються одночасно, то викреслюємо або рядок, або стовпчик, а в залишку стовпчика (рядка) записуємо нульовий попит (обсяг виробництва). Рядок (або стовпчик) з нульовим обсягом попиту більше не використовується в обчисленнях.

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

Для визначення оптимального плану Т-задачі розроблено декілька методів, наприклад, метод потенціалів, метод диференціальних рент.

2.2 Метод потенціалів

Мета заняття – закріплення теоретичного матеріалу та набуття практичних навичок розв’язання Т-задач методом потенціалів.

Загальний принцип визначення оптимального плану Т-задачі методом потенціалів аналогічний принципу розв'язання ЗЛП симплексним методом, а саме: з початку знаходять опорний план транспортної задачі, а потім його послідовно покращують до одержання оптимального плану. Для визначення опорного плану = ‖ ‖ транспортної задачі можна скористатись одним із

методів, описаних вище. Ці методи гарантують одержання зайнятих у початковому плані n+m-l клітинок, причому в деяких з них можуть стояти нулі.

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

Якщо

для деякого

опорного

плану

= ‖

̅̅̅̅̅̅

̅̅̅̅̅

‖( = 1, ,

= 1, )

транспортної задачі існують такі числа

, , … ,

, , , … , , що

−

=

при

> 0

(2.1)

1

2

1

2

−

≤ при

= ,

(2.2)

̅̅̅̅̅̅

̅̅̅̅̅

то

= ‖

‖

–

оптимальний

план транспортної

для всіх = 1, і = 1, ,

задачі.

Числа 1 і 1

̅̅̅̅̅̅

̅̅̅̅̅

називають потенціалами відповідно до

( = 1, ,

= 1, )

пунктів відправлення і відповідно до пунктів призначення. Алгоритм знаходження розв’язання транспортної задачі полягає у такому: нехай за допомогою одного з розглянутих вище методів знайдений опорний план Т-

задачі. Для кожного з пунктів		призначення і	відправлення визначають
̅̅̅̅̅̅	̅̅̅̅̅
потенціали 1 і 1 ( = 1, , = 1, ). Ці числа знаходять із системи рівнянь
− =			(2.3)
де – тарифи, що знаходяться		у заповнених	клітинках таблиці умов

транспортної задачі.

Оскільки кількість заповнених клітинок дорівнює n+m-1, то система (2.3) з n+m невідомими містить n+m-1 рівнянь. Оскільки кількість невідомих перевищує на одиницю кількість рівнянь, одне з невідомих можна припустити рівним будь-якому числу, наприклад 1 = 0, і знайти послідовно із рівняння (2.3) значення останніх невідомих. Після того, як потенціали знайдені, для

кожної 3 вільних клітинок визначають числа	= −		− . Якщо серед

чисел нема додатних, то знайдений опорний план є оптимальним. Якщо ж для деякої вільної клітинки 1 > 0, то початковий опорний план не є оптимальним і необхідно перейти до нового опорного плану. Для цього розглядаються всі вільні клітинки, для яких 1 > 0, і серед даних чисел обирають максимальне. Клітинку, якій це число відповідає, необхідно заповнити.

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

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

За правильною побудовою опорного плану для будь-якої вільної клітинки можна побудувати лише один цикл. Після того, як він побудований, слід перейти до іншого опорного плану. Для цього перемістити вантажі у межах клітинок, пов'язаних з даною вільною клітинкою. Це переміщення здійснюють за такими правилами:

а) кожній 3 клітинок, пов'язаних з даною вільною клітинкою, приписують певний знак: для вільної клітинки - знак плюс, а всім іншим клітинкам – по черзі знаки мінус і плюс;

б) у дану вільну клітинку розміщують менше з чисел , що знаходиться в мінусових клітинках. Одночасно це число додають до відповідних чисел, що знаходяться в плюсових клітинках. Клітинка, що раніше була вільною, буде зайнятою, а мінусова клітинка, де знаходилося найменше з чисел - вільною.

Внаслідок зазначених вище переміщень вантажів у межах клітинок, пов'язаних циклом З даною вільною клітинкою, визначають новий опорний план транспортної задачі.

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

Слід зазначити, що за зсувом за циклом перерахунку кількість зайнятих клітинок залишається незмінним, а саме рівним n+m-1. Тому, якщо в мінусових

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

Отриманий план Т-задачі перевіряють на оптимальність. Для цього визначають потенціали пунктів відправлення і призначення та знаходять числа= − − для всіх вільних клітинок. Якщо ж додатні числа мають місце, то слід перейти до нового опорного плану. Внаслідок ітераційного отримання плану після кінцевого числа отримують оптимальний план задачі. Отже, процес знаходження розв'язку транспортної задачі за допомогою методу

потенціалів має такі етапи:

1)знаходять опорний план. Кількість зайнятих клітинок при цьому має бути рівним n+m-1;

2)знаходять потенціали і відповідно до пунктів призначення і

відправлення; 3) для кожної вільної клітинки визначають число . Якщо серед чисел

нема додатних, то досягнуто оптимальний план Т-задачі, якщо ж вони є, то переходять до нового опорного плану;

4) серед додатних чисел обирають максимальне, будують для вільної клітинки, якій воно відповідає, цикл перерахунку і здійснюють зсув за циклом перерахунку;

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

Але слід зазначити, що при визначенні опорного плану або у процесі розв'язання задачі можна отримати вироджений опорний план.

Щоб запобігти у цьому випадку зациклення, слід відповідні нульові елементи опорного плану замінити на як завгодно малі додатні числа і розв'язувати задачу як не вироджену. В оптимальному плані такої задачі необхідно вважати рівним нулю.

Алгоритм методу потенціалів розв’язання Т-задачі складає ряд етапів: попереднього і кінцевого числа ітерацій.

На попередньому етапі будують початковий опорний план Х0. Потім для цього плану розраховують матрицю оцінок

			С = ‖		− ( − )‖		(2.4)
де і – потенціали пунктів відправлення Аі і пунктів призначення Вj.
Попередні потенціали обирають так, щоб для зв’язаних комунікаціями
пар пунктів,	для яких			≠ 0 у плані Х0, різниця потенціалів дорівнювала ,
тобто −		= .

Якщо матриця Сі не містить від’ємних елементів, то Х0 – оптимальний план. У протилежному випадку Х0 – не оптимальний план і його можна покращити.

1.Визначаємо початковий опорний план Х0 за допомогою одного з описаних засобів.

2.Обчислюємо оціночну матрицю Сі. Для розрахунку елементів матриці необхідно спочатку визначити всі потенціали і . Будуємо схему перевезень,

що відповідає початковому опорному плану Х0, тобто з’єднуємо комунікаціями пункти відправлення і призначення, для яких ≠ 0. Користуючись (1.3), визначаємо послідовно всі потенціали пунктів відправлення і призначення Вj, призначаючи для зручності 1 = 0. Потім згідно з (1.4) знаходимо елементи матриці С1, що відповідають базисним елементам плану Х0 і мають бути зайнятими нулями.

(k+1

1.Якщо в оціночній матриці С(k+1) всі елементи додатні, план Х(k) – оптимальний, в іншому випадку слід приступити до його поліпшення.

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

3. Будуємо новий план Х(k+1), додаючи до всіх парних елементів ланцюжка і віднімаючи від непарних. Елементи матриці Х(k), що не надходять до ланцюжка, переміщуються до матриці Х(k+1) без змін.

4. За допомогою подібних перетворень матриці C(k) знаходимо матрицю оцінок C(k+1) для нового плану Х(k+1). Для цього підкреслюємо у матриці C(k) всі елементи, що відповідають ненульовим елементам матриці Х(k+1) (вони обов’язково дорівнюють 0). У матриці C(k) закреслюємо рядок, що містить елемент Сst. Якщо у цьому рядку є підкреслені елементи, то закреслюємо відповідні цим елементам стовпчики. Якщо ж у кожному закресленому стовпчику є підкреслені елементи, закреслюємо відповідні їм рядки доти, доки дана процедура може виконуватися. Після цього до всіх елементів закреслених рядків додаємо |Сst|, а від елементів закреслених стовпчиків віднімаємо |Сst|. Отримуємо нову матрицю оцінок. Якщо у матриці C(k+1) нема від'ємних елементів, то план Х(k+1) – оптимальний, інакше переходимо до наступної ітерації. На цьому ітерації завершуються.

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

Розв’язання почнемо з перевірки умов балансу: