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

4 4

∑	= ∑ = 190.
=1	=1

Будуємо початковий опорний план за методом північно-західного кута:

		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

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

А1	α1=0	А2	α2=2	А3	α3=9	А4	α4=-7

В1	β1=1	В2	β2=2	В3	β3=-1	В4	β4=6

Рисунок 2.1 – План перевезень

За відповідними маршрутами вказується вартість перевезень Сij одиниці вантажу з і-го пункту до j-го. Приймаємо 1 = 0 і за (1.3) визначаємо потенціали

1 = 0, 11 = 1, 1 − 1 = 11, 1 = 1,21 = 3, 1 = 2 = 21, 2 = −2;22 = 4, 2 − 2 = 22, 2 = 2 тощо.

Розраховуємо елементи матриці оцінок за співвідношенням (1.4):

С = − ( − );12 = 12 − 2 + 1 = 2 − 2 + 0 = 0,

13 = 13 − 3 + 1 = 9 + 1 − 0 = 10,14 = 14 − 4 + 1 = 7 + 6 − 0 = 13 тощо.

Отже,

			1		1 2 3 4
	С1	=	2		0	0	1013
					‖ 0	0	0	9 ‖
				3
					−4−7 0			0
			4		−6−6−3			0

Оскільки в С1 мають місце від’ємні елементи, план х0 не є оптимальним.

У матриці х0, починаючи з елемента х32, що відповідає в матриці оцінок найбільшому від’ємному елементу, будуємо ланцюжок. Змінюючи елементи, що надходять до ланцюжка, на величину Θ=min{5,5}=5, будуємо новий план х1:

				1 2 3 4						1		3 4
											2
		1		60 0 0 0					1	60 0		0 0
		2							2
	=		‖	10 5 40 0	‖	,		=		10		45 0	‖
0							1			‖	5
		3		0 0 0 35					3	0		5 35
		4 0 0 0 35							4	0 0 0 35

Отриманий план є виродженим. Оскільки при розрахунках оперуємо не виродженим планом, один із нулів ланцюжка замінюємо величиною ≠ 0. У випадку виродженості при побудові початкового опорного плану вводимо =за тією комунікацією, яка необхідна для визначення потенціалів і .

Виконаємо перетворення у матриці С1, попередньо відмічаючи в ній нулі, що відповідають базисним змінним ≠ 0 плану х1 і будуємо матрицю оцінок С2.

	1	1 2 3 4								1
		̅	0 10	13							1 2		3	4
											0 0		10 6
	2	0								2
С =		̅	̅ ̅	9	‖	,	С	2	=		‖ 0 0 0			2 ‖
1		‖ 0	0 0	̅
	3	−4−7 0								3	3 0	7		0
	4			0						4
				̅							1 1		4	0
		−6−6−3 0

У матриці оцінок С2 нема від’ємних елементів, отже, план х1 є оптимальним. Вартість перевезення в умовних одиницях

= ∑ ∑ = 60 1 + 10 3 + 45 1 + 5 4 + 35 3 + 35 1 = 295.

=1 =1

1. Знайдіть розвязок Т-задачі:

а)

						B1			B2			B3			B4				ai
			A1			1			8			2			3				30
C=			A2			4			7			5			1				50
			A3			5			3			4			4				20
			bj			15			15			40			30
б)
					B1			B2			B3			B4			B5			ai
		A1			2			6			3			4			8			40
		A2			1			5			6			9			7			30
		A3			3			4			1			6			10			35
		bj			20			34			16			10			15

2. Виконайте розв’язання Т-задачі, наведеної в прикладі, замінивши С12 на 5 (замість 2). З одночасним виконанням обмежень по рядках або стовпчиках завжди закреслюйте рядок.

2.3 Задачі про призначення

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

Задачі про призначення - клас оптимізаційних задач, який є частковим випадком Т-задач. Тут роботи є «початковими пунктами», а верстати «пунктами призначення». Пропозиція у кожному початковому пункті дорівнює 1, тобто = 1 . Аналогічно попит у кожному пункті призначення дорівнює 1, тобто = 1 , Вартість «перевезень» (закріплення) роботи і до верстата j дорівнює . Якщо будь-яку роботу не можна виконувати на будь-якому верстаті, то відповідно вартість припускається рівній дуже великому числу М. Модель такої задачі можна проілюструвати таблицею 2.2.

Задачу про призначення можна сформулювати так.

Нехай xij=0, якщо j-а робота не виконується і-им верстатом, та xij=1, якщо j-а робота виконується і-им верстатом.

Таблиця 2.2 – Матрична модель задачі
Види робіт			Верстати
1	С11	С12	…	С1j			…	С1n		1
2	С21	С22	…	С2j			…	С2n		1
…
і	Сі1	Сі2	…	Сij			…	Сin		1
…
m	Сm1	Сm2	…	Сmj			…	Сmn		1
bi	1	1	…		1		…	1
Тоді виникає потреба мінімізувати
			= ∑ ∑								(2.5)
					=1 =1
за обмежень
			∑					̅̅̅̅̅̅			(2.6)
						= 1, = 1,
			=1
			∑					̅̅̅̅̅			(2.7)
						= 1, = 1,
			=1
						= 0 або 1					(2.8)

. Нехай умови задачі про призначення задані таблицею з трьома роботами і трьома верстатами (табл. 2.3).

Таблиця 2.3 – Початкові дані задачі

робіт					Верстати
		1																			1
		1			1						2						3
						5					7						9
Види
					14
		2																			1
		3									10						12				1
					15						13						16
		bj			1						1						1

Початкове розв’язання (отримане за правилом північно-західного кута) буде виродженим. Ця особливість характерна для задачі про призначення незалежно від методу,

що	використовується		для	отримання
початкового		базису.		Розв’язання

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

′ = ∑ ∑ = ∑ ∑( − − ) .

Мінімізація початкової функції Z призведе до того ж розв’язку, що й мінімізація Z’. З цього можна зробити такий висновок. Якщо можна побудувати нову матрицю Cіj з нульовими елементами або їх множина відповідає припустимому розв'язанню, то таке розв'язання буде оптимальним, оскільки вартість не може бути від'ємною. У таблиці 2.4 нульові елементи отримано відніманням найменшого елемента у кожному рядку (стовпчику) із відповідного рядка (стовпчика). Якщо спочатку розглянути рядки, то отримаємо Cіj - матрицю, що подана таблицею 2.4.

Таблиця 2.4 – Проміжні результати задачі

			1	2	3
	‖С ‖ =	1	0	2	4	P1=5
		2	4	0	2	P2=10
		3	2	0	3	P3=13

Віднімаючи q3=2 із третього стовпчика, останню матрицю можна перетворити так, щоб вона не мала більше нулів, Так отримаємо таблицю 2.5.

Таблиця 2.5 – Припустимі значення

			1	2	3
	‖С ‖ =	1	0	2	2
		2	4	0	0
		3	2	0	1

У таблиці 2.5 виділені елементи, що відповідають припустимому (а, отже, оптимальному) призначенню (1.1), (2.3), (3.2) з вартістю 5+12+ 3=30. Підкреслимо, що ця вартість дорівнює р2+р2+р3+q3. Але не завжди вдається визначити припустиме значення досить просто, як у наведеному прикладі. Тому є інші правила для знаходження оптимального розв'язання.

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

Для цього необхідно відмітити точкою:

1) усі рядки, де немає жодного відміченого точкою нуля;

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

3)усі рядки, що містять відмічені точкою нулі, хоч в одному з відмічених точкою стовпців.

Дії 2 і 3 повторюються по черзі доти, доки є що відмічати. Після цього необхідно закреслити кожний невідмічений рядок і кожний відмічений стовпчик.

Потім взяти найменше число із тих клітинок, через які не проведені прямі. Відняти його з кожного числа не закреслених стовпчиків і додати до кожного числа закреслених рядків. Це ілюструється на прикладі.

Нехай початкова матриця має вигляд (табл. 2.6).

Таблиця 2.6 – Початкова матриця

	1	2	3	4
1	1	64	6	3
2	9	7	10	9
3	3	2	0	0
4	3	2	0	0

Виконуючи ті ж початкові кроки, що наведені в попередньому прикладі, отримаємо таблицю 2.7.

Таблиця 2.7 – Проміжні результати

	1	2	3	4
1	1	4	6	3
2	9	7	10	9
3	4	5	11	7
4	3	2	0	0

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

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

Таблиця 2.8 – Чергові проміжні результати

	1	2	3	4
1	1	4	6	3
2	9	7	10	9
3	4	5	11	7
4	3	2	0	0

За наступним кроком обирається найменший не викреслений елемент. Цей елемент віднімається із кожного не викресленого елемента і додається до кожного елемента, що розташований на перетині проведених прямих. Внаслідок отримаємо таблицю 2.9, що відповідає оптимальному призначенню (1.1), (2.3), (3.2), (4.4). Відповідні сумарні витрати дорівнюють 1 + 10+5+5=21.

Таблиця 2.9 – Оптимальне призначення

	1	2	3	4
1	0	2	1	1
2	3	0	0	2
3	0	0	3	2
4	4	2	0	0

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

1.Використайте метод розв'язання Т-задачі та задачі про призначення (табл. 1.3). Покажіть, що буде отриманий такий же розв’язок задачі.

2.Знайдіть розв’язок задачі про призначення.

а)

	1	2	3	4	5
1	3	8	2	10	3
2	8	7	2	9	7
3	6	4	2	7	5
4	8	4	2	3	5
5	9	10	6	9	10

б)

	1	2	3	4	5
1	3	9	2	3	7
2	6	1	5	6	6
3	9	4	7	10	3
4	2	5	4	2	1
5	9	6	2	4	6

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

1.Яка особливість математичної моделі Т-задачі?

2.Що називається опорним планом Т-задачі?

3.Чи можна Т-задачу збалансувати?

4.Чи використовуються для балансування Т-моделі як фіктивні початкові пункти, тік і фіктивні пункти призначення?

5.Чи може не мати збалансована Т-модель припустимих розвозів?

6.Які різновиди Т-задач ви знаєте?

7.Дайте обґрунтування методу потенціалів.

8.Дайте визначення потенціалів.

9.У чому особливість алгоритму методу потенціалів?

10.Чому задачі про призначення є часткою ЗЛП?

11.У чому полягає особливість пошуку опорного плану?

12.Чи будь-який базисний розв’язок задачі про призначення вироджений?

13.У чому суть угорського методу?

ПЕРЕЛІК ПОСИЛАНЬ

1.Гвоздинський А.М. Оптимізаційні задачі в організаційному управлінні. Детерміновані моделі: Навч. Посібник. Частина 1.. – Харків: ХТУРЕ, 1997.-116 с.

2.Бондаренко М.Ф., Гвоздинський А.М. Оптимізаційні задачі в системах прийняття рішень. Підручник. – Харків: ХТУРЕ, 1998. – 2016 с.

3.Коюда П.М. Ларіонов Ю.І. Математичне програмування. Навч. Посібник. – Харків: ХТУРЕ, 1997. – 167 с.

4.Гвоздинський А.М., Губін В.О., Павленко Е.П. Оптимізаційні задачі в організаційному управлінні. Мережні моделі. Частина 3.. – Харків: ХТУРЕ,

1997, - 108 с.