Navch._posibnuk_Ivaschyk

3.Далі необхідно представити результати розв’язків.

3.1.Сервис, Сценарии...

На екрані появляється діалогове вікно «Диспетчер сценариев». 3.2. Отчет...

На екрані появляється діалогове вікно «Отчет по сценарию».

3.3.Структура.

3.4.ОК.

На екрані появляється звіт «Структура сценария» (табл. 3.6): Таблиця 3.6

B	C	D	E	F	G	H	I
Структура	сценария
		Текущие	фінанси=10000	фінанси=10500	фінанси=11000	фінанси=11500	фінанси=120
		значения:					00
			Модельпоиска	Модельпоиска	Модельпоиска	Модельпоиска	Модель
			решения	решения	решения	решения	поиска
							решения
Изменяемые ячейки:
	$B$3	500	500	500	500	500	500
	$C$3	0	0	0	0	0	0
	$D$3	1100	600	725	850	975	1100
	$E$3	800	800	800	800	800	800
Ячейки	результата:
	$F$6	10000	7000	7750	8500	9250	10000
	$F$9	102	77	83,25	89,5	95,75	102
	$F$10	4420	3420	3670	3920	4170	4420
	$F$11	12000	10000	10500	11000	11500	12000
Примечания: столбец «Текущие значения» представляет значения изменяемых ячеек в
момент создания Итогового отчета по Сценарию. Изменяемые ячейки для каждого
сценария выделены серым цветом.

В звіті представлені результати розв’язку задачі для всіх значень фінансів по всіх п’яти варіантах. Для зручності представлення результатів у вигляді діаграм виконаємо редагування звіту за таким алгоритмом:

1.У випадку, коли весь звіт «Структура сценария» не вміщується на екрані, то зменшуємо вікно масштабу.

2.Викидаємо стовпці А, B і D.

3.Викидаємо рядки 4,5 і 10

4.Вводимо слова: Прод1 ... Прод4 в комірки С6:С9, Прибуток в С11, види ресурсів: трудові, сировина, фінанси в комірки С12:С14.

5.Збільшити ширину стовпця С.

6.У випадку отримання дробових результатів, заокруглюємо їх.

7.Забрати зауваження.

Після такого редагування звіт матиме вигляд:

131

						Таблиця 3.7
	C	E	F	G	H	I
1
2
3		фінанси=1000	фінанси=10500	фінанси=11000	фінанси=11500	фінанси=12000
6	Прод1	500	500	500	500	500
7	Прод2	0	0	0	0	0
8	Прод3	600	725	850	975	1100
9	Прод4	800	800	800	800	800
11	Прибуток	7000	7750	8500	9250	10000
12	Трудові	77	83,25	89,5	95,75	102
13	Сировина	3420	3670	3920	4170	4420
14	Фінанси	10000	10500	11000	11500	12000

3.5.Питання для самоконтролю

1.Сформулюйте правила побудови двоїстої задачі.

2.В чому полягає різниця між симетричною та несиметричною парою взаємоспряжених задач?

3.Скільки змінних та обмежень має двоїста задача відповідно до прямої?

4.Сформулюйте основні теореми двоїстості.

5.Запишіть всі можливі види прямих та двоїстих задач.

6.Як за розв’язком прямої задачі знайти розв’язок двоїстої?

7.Яка суть двоїстого симплекс-методу?

8.Дайте економічну інтерпретацію двоїстих оцінок.

9.Як визначити дефіцитність (недефіцитність) ресурсу?

10.Як визначити рентабельність (нерентабельність) продукції, що виготовляється?

132

Розділ 4. Транспортна задача

4.1.Постановка транспортної задачі та її математична модель

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

Сформулюємо визначення транспортної задачі. Деяку однорідну продукцію, яка знаходиться в m постачальників A1, A2, …, Am кількістю a1, a2, …, am одиниць відповідно, потрібно перевезти n споживачам B1, B2, …, Bn в кількостях b1, b2, …, bn одиниць. Відома матриця вартостей перевезення одиниці продукції від i-го постачальника до j-го споживача:

c11

c21

...

cm1

c	...	c
12		1n
c22	...	c2n
...	...	...	.
cm2	...
		cmn

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

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

m

∑ai

i=1

n

= ∑bj . (4.1)

j=1

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

Побудуємо математичну модель транспортної задачі. Оскільки наперед невідомо, скільки вантажу потрібно перевезти з пункту Аi до пункту Вj, щоб план перевезень був оптимальним, то позначимо його через xij. Вартість перевезення всього вантажу від постачальників до споживачів позначимо Z.

133

Умову транспортної задачі можна записати у вигляді таблиці:

Постачальники

A1

A2

…

Am

	Споживачі	B1	B2	…	Bn
	Потреби	b1	b2	…	bn
	Запаси
	a1	c11	c12	…	c1n
		x11	x12		x1n
	a2	c21	c22	…	c2n
		x21	x22		x2n
	…	…	…	…	…
	am	cm1	cm2	…	cmn
		xm1	xm2		xmn

Тоді цільова функція матиме вигляд:

Z = c11x11 + c12 x12 +... + c1n x1n + c21x21 + c22 x22 +... + c2n x2n +... + cm1xm1 +

+ cm2 xm2 +... + cmn xmn		(min)
m	n
або Z = ∑∑cij xij		(min)	(4.2)
i=1	j=1

Для складання обмежень транспортної задачі скористаємося такими міркуваннями:

1)кількість вантажу, який потрібно перевезти до пункту Вj з усіх пунктів постачання, рівна х1j +х2j +... + xmj, а споживачеві Вj потрібно bj одиниць вантажу, тому, враховуючи те, що всі потреби повинні бути задоволеними, можемо записати обмеження стосовно потреб:

x1 j + x2 j +... + xmj = bj ,	j =		;
		1, n

2)кількість вантажу, який треба вивезти з пункту постачання Аi до всіх споживачів, дорівнює хi1 +хi2 +... + xin, а постачальник має аi одиниць вантажу і всі вантажі мають бути вивезені, тому обмеження стосовно запасів матимуть вигляд:

xi1 + xi2 +... + xin = ai , i =1, m.

В загальному випадку систему обмежень запишемо таким чином:

134

x

+ x

21

+... + x

m1

= b

,

11

1

x12 + x22 +... + xm2

= b2 ,

.................................

+ x

+... + x

= b

,

x

2n

mn

1n

n

x11 + x12 +... + x1n

= a1 ,

x

21

+ x

22

+... + x

2n

= a

2

,

.................................

xm1 + xm2 +... + xmn = am ,

≥ 0, i =1, m,

j =1, n,

xij

або

m

∑ x

= b

,

j =1, n;

ij

j

i =1

n

i =1, m;

(4.3)

∑ xij = ai ,

j =1

x

≥ 0, i

=

, j =

.

1, m

1, n

ij

Ми отримали математичну модель транспортної задачі (4.2)-(4.3), де хij – кількість продукції, що перевозиться від i-го постачальника до j-го споживача; сij – вартість перевезення одиниці продукції від і-го постачальника до j-гo споживача; аі – запаси продукції і-го постачальника; bj – попит на продукцію j-го споживача.

Тепер, виходячи з економічної постановки транспортної задачі, можемо cформулювати її математичну задачу: серед всіх невід’ємних розв’язків системи рівнянь (4.3) знайти такий, при якому оптимізуюча форма (4.2) набуде найменшого значення.

Транспортна задача є задачею лінійного програмування, яку можна розв’язати симплекс-методом, але при розв’язуванні транспортної задачі симплексним методом ми б отримали симплекстаблиці великих розмірів, оскільки число невідомих дорівнює m n . Специфічна структура цієї задачі дозволяє використати для її розв’язання ефективніший метод – метод потенціалів, який ми розглянемо в п. 4.3.

135

4.2. Методи побудови початкового опорного плану

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

Розглянемо методи знаходження цього плану:

1. Діагональний метод (північно-західного кута).

Побудову початкового опорного плану за методом північнозахідного кута починають із заповнення лівої верхньої клітинки таблиці A1B1 (х11), в яку записують менше з двох чисел а1 та b1. Далі переходять до наступної клітинки в рядку або стовпчику і заповнюють її і т.д., закінчуючи останньою правою клітинкою

таблиці AmBn (хmn).

Розглянемо алгоритм побудови початкового опорного плану транспортної задачі методом північно-західного кута:

1.Перевірка транспортної задачі на закритість. Якщо вона відкрита, то приводимо її до задачі закритого типу (п. 4.4).

2.Першою заповнюємо верхню ліву клітинку.

Заповнення клітинки AiBj таблиці здійснюємо за такими правилами:

а) якщо аi<bj, тобто запаси менші від потреб, то в цю клітинку записуємо весь об’єм запасу вантажу аi, перераховуємо потреби споживача Bj, постачальника Ai вилучаємо з розгляду (наприклад, поставивши у всіх клітинках рядочка, крім заповненої, прочерки) і переходимо до заповнення наступної клітинки Ai+1Bj;

б) якщо аi>bj, тобто запаси більші від потреб, то в цю клітинку записуємо весь об’єм потреб вантажу bj, перераховуємо запаси постачальника Ai, вилучаємо з розгляду споживача Bj (ставимо у всіх клітинках стовпчика, крім заповненої, прочерки) і переходимо до заповнення наступної клітинки AiBj+1;

в) якщо аi=bj, тобто запаси рівні потребам, то в цю клітинку записуємо весь об’єм потреб чи запасів, вилучаємо з розгляду постачальника Ai і споживача Bj (ставимо в усіх клітинках стовпчика і рядка, крім заповненої, прочерки) і переходимо до заповнення наступної клітинки Ai+1Bj+1.

3. Серед незаповнених клітинок (без обсягу вантажу і прочерків) знову вибираємо верхню ліву клітинку таблиці і заповнюємо її за правилами, поданими в п. 2. Так продовжуємо до тих пір, доки не заповнимо всі клітинки таблиці.

136

4. З одержаної таблиці виписуємо початковий опорний план транспортної задачі та обчислюємо значення цільової функції при цьому плані.

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

Приклад 4.1. Методом північно-західного кута (діагональним) знайти початковий опорний план перевезення однорідного вантажу від постачальників А1, А2, A3 з запасами а1=200, a2=150, а3=175 до споживачів В1, B2, В3, В4 з потребами в цьому вантажі b1=140, b2=125, b3=90, b4=170, якщо відома вартість перевезення одиниці вантажу від постачальників до споживачів:

	2	8	6	1
	3	7	5	2
cij =					.
	4	9	3	6

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

Перевіримо, чи транспортна задача є закритою. Обчислимо:

3			4
∑ai	= 200	+150 +175 = 525;	∑bj	=140 +125 +90 +170 = 525.
i=1			j=1
	4	3
Оскільки ∑ai		= ∑bj , то окреслена транспортна задача закритого типу.
	i=1	j=1

Першою заповнюємо клітинку А1В1 числом 140, як min(200;140). В результаті такої дії потреби споживача В1 задовольнилися, а у постачальника А1 залишилось ще 60 одиниць вантажу (200–140). Оскільки споживачеві В1 більше не потрібно вантажу, то ставимо прочерки в усіх інших клітинках стовпчика, зокрема в клітинках А2В1 та А3В1. Далі переходимо до сусідньої клітинки в рядку чи стовпчику, але оскільки в клітинці А2В1 вже стоїть прочерк, то наступною будемо заповнювати клітинку А1В2. У постачальника А1 ще залишилось 60 одиниць вантажу, а споживачеві В2 потрібно 125, тому в клітинку А1В2 записуємо менше з цих чисел – 60. Оскільки постачальник А1 більше вантажу не має, то ставимо прочерки в незаповнених клітинках рядочка А1В3 та А1В4. Переходимо до сусідньої клітинки по стовпчику – А2В2 (оскільки в сусідній клітинці рядочка А1В3 стоїть прочерк) і заповнюємо її. Постачальник А2 має 150 одиниць вантажу, а споживачеві В2 ще потрібно 65 (60 одиниць вантажу він вже отримав від постачальника A1), тому в клітинку А2В2 записуємо менше з цих чисел – 65. Оскільки споживачу В2 більше вантажу не

137

треба, то ставимо прочерки в клітинках стовпця, що залишились незаповненими, зокрема в клітинці А3В2. Переходимо до сусідньої клітинки по рядочку – А2В3. У постачальника А2 ще залишилось 85 одиниць вантажу (65 одиниць він віддав споживачеві В2), а споживачеві В3 потрібно 90, тому в клітинку А2В3 заносимо менше з цих чисел – 85. Оскільки постачальник А2 вантажу більше не має, то ставимо прочерки в незаповнених клітинках рядочка – в клітинці А2В4. Незаповненими залишилися ще дві клітинки – А3В3 та А3В4. Оскільки в сусідній з А2В3 клітинці по рядочку – прочерк, то заповнюємо сусідню клітинку по стовпчику – А3В3. Постачальник А3 має 175 одиниць вантажу, а споживачеві В3 ще потрібно 5 (85 одиниць вантажу він вже отримав від постачальника А2), тому в клітинку А2В2 записуємо 5. Залишилась незаповненою одна клітинка

– А3В4. У постачальника А3 залишилось 170 одиниць вантажу (5 одиниць він віддав споживачеві В3), споживачеві В4 потрібно 170, тому в клітинку А3В4 записуємо 170. Наша таблиця матиме вигляд:

Постачальники

A1

A2

A3

Споживачі		B1		B2		B3	B4
Потреби		140		125		90	170
Запаси
200	2		8		6		1
		140		60		–	–
150	3		7		5		2
		–		65		85	–
	4
175			9		3		6
		–		–		5	170

Ми отримали початковий опорний план:

140		60	0	0
xопорн. =	0	65	85	0	.
	0	0	5	170

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

Z=2·140+8·60+7·65+5·85+3·5+6·170=280+480+455+425+15+1020=2675. ♦

138

2. Метод найменшої вартості.

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

Алгоритм методу найменшої вартості побудови початкового опорного плану транспортної задачі розглянемо на прикладі.

Приклад 4.2. Методом найменшої вартості знайти початковий опорний план перевезення однорідного вантажу від постачальників А1, А2, A3 з запасами а1=200, a2=150, а3=175 до споживачів В1, B2, В3, В4 з потребами в цьому вантажі b1=140, b2=125, b3=90, b4=170, якщо відома вартість перевезення одиниці вантажу від постачальників до споживачів:

	2	8	6	1
cij =	3	7	5	2 .
4		9	3	6

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

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

–це клітинка A1B4 з вартістю перевезення 1. Перший постачальник має 200 одиниць вантажу, а споживачеві В4 треба 170, тому записуємо в цій клітинці менше з цих чисел – 170. Оскільки споживачеві більше не потрібно вантажу, то в усіх решту клітинках

зазначеного стовпця ставимо прочерки, зокрема в клітинках A2B4 та А3В4. Тоді вибираємо клітинку з найменшою вартістю перевезень одиниці вантажу серед тих, які залишились (крім заповненої A1B4 і тих клітинок, в яких стоять прочерки). Це клітинка A1B1, вартість перевезення в якій 2. Постачальник А1 ще має 30 одиниць вантажу (він мав 200, з яких 170 віддав споживачу В4), а споживачеві В1 потрібно 140, тому записуємо в цій клітинці 30, а в усіх клітинках

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

139

найменшою вартістю – 3. Постачальник А2 має 150 одиниць вантажу, а споживачеві ще треба 110 (30 одиниць вантажу він вже отримав від першого постачальника). Забираємо в постачальника А2 цих 110 одиниць вантажу і записуємо в окресленій клітинці, а в усіх незаповнених клітинках стовпця ставимо прочерки (в цьому стовпчику незаповненою залишилась тільки клітинка A3B1, тому прочерк ставимо в ній). В постачальника А2 ще залишилось 40 одиниць вантажу (150–110). Наступна клітинка серед незаповнених з найменшою вартістю перевезення 3 – це клітинка А3В3. Споживачеві В3 потрібно 90 одиниць вантажу, а постачальник А3 ще має 175, тому пишемо в клітинці А3В3 менше з цих чисел, тобто 90, і оскільки споживачеві більше не потрібно вантажу, а в стовпчику, що йому відповідає, залишилась єдина незаповнена клітинка А2В3, то ставимо в цій клітинці прочерк. Залишилося дві незаповнених клітинки А2В2 та А3В2. Менша вартість перевезення одиниці вантажу в клітинці А2В2, тому заповнюємо спочатку її. В постачальника А2 ще є 40 одиниць вантажу, а споживачеві В2 треба 125, тому пишемо в цій клітинці 40 і переходимо до останньої незаповненої клітинки нашої таблиці А3В2. Постачальник має 85 одиниць вантажу (він мав 175, але 90 одиниць віддав споживачеві В3) і споживачеві В2 треба стільки ж (йому було потрібно 125 одиниць вантажу, але 40 одиниць він взяв у постачальника А2), тому записуємо в цій клітинці 85. Наша таблиця має вигляд:

-Постачальники

A1

A2

A3

Споживачі		B1		B2		B3	B4
Потреби		140		125		90	170
Запаси	2		8		6		1
200
		30		–		–	170
	3
150			7		5		2
		110		40		–	–
175	4		9		3		6
		–		85		90	–

Ми отримали початковий опорний план:

140