математика

11

Складемо базисний план методом північно-західного кута.

Додамо перемінної x11 максимальне можливе значення x11 min 60,20 20. Після цей попит першого споживача цілком удоволений, у результаті чого перший стовпець випадає з подальшого розгляду. У таблиці постачань знаходимо новий «північно-західний» кут і надаємо значення x12 40,110 40. Перша стоку закрита. Далі закривається елемент 2,3 і т.д. У результаті виходить вихідне рішення.

	20	110	40	110
60	1	2	5	3
	20	40	-	-
120	1	6	5	2
	-	70	40	10
160	6	3	7	4
	-	-	-	100

Сумарні транспортні витрати відповідно до даного плану:

L0 1 20 2 40 6 70 5 40 2 10 4 100 1140 .

Істотним недоліком методу північно-західного кута є те, що план побудований без обліку значень коефіцієнтів витрат задачі.

Більш ефективне базисне рішення може бути отримано методом мінімальних елементів. У цьому випадку спочатку заповнюються клітки з мінімальними коефіцієнтами витрат. У даному випадку таких

кліток дві: (1,1)	і (2,1). Максимально можливі	постачання
x11 min 60,20 20	і x21 min 120,20 20. Тому	що вони

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

C12 C24	2коефіцієнти			. Тому що можливе значення				x24 100
більше, ніж			x12 60, те	спочатку	заповнюється клітка (2,4) і т.д.
Виходить опорний план:
			20	110		40		110
60			1/-	2/60		5/-		3/-
120			1/20	6/-		5/-		2/100
100			6/-	3/50		7/40		4/10

Транспортні витрати даної моделі:

L0 1 20 2 60 3 50 2 100 7 40 4 10 810 ,

що значно менше, ніж у методі північно-західного кута. Перевіримо ефективність даного плану методом потенціалів.

Якщо xIJ 0, то xIJ – вільна перемінна. Кожному пункту відправлення ставиться у відповідності потенціал UI . Потенціали

		12
знаходяться із системи рівнянь	UI VJ	CIJ для базисних
перемінних.
У нашому випадку:
U1 V2 2,
U2 V1 1,
U2 V4 2,
U3 V2 3,
U3 V3 7,
U3 V4	4.

Нехай U1 1, тоді V2 1, U3 2, V3 5, V4 2, U2 0, V1 1. Для вільних перемінних знайдемо непрямі вартості:

CIJ UI VJ ,

C11 U1 V1 2,

C13 U1 V3 3,

C14 U1 V4 3,

C22 U2 V2 1,

C23 U2 V3 5,

C31 U3 V1 3 .

Для вільних невідомих знаходимо коефіцієнти

IJ CIJ CIJ

11 1 2 1 0, 13 5 3 2 0, 14 3 3 0, 22 6 1 5 0,23 5 5 0, 31 6 3 3 0.

Якщо IJ 0, то дана клітка повинна бути закрита. Це можна зробити за рахунок клітки (1,2).

Новий план прийме вид

	20	110	40	110
60	1/20	2/40	5/-	3/-
120	1/-	6/-	5/10	2/110
100	6/-	3/70	7/30	4/-

Транспортні витрати даного плану:

L0 1 20 2 40 5 10 2 110 3 70 7 30 790 .

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

U1 V1 1, U1 V2 2, U2 V3 5, U2 V4 2, U3 V2 3, U3 V3 7, U1 1, V1 0, V2 1, U3 2, V1 5, U2 0, V4 2, U1 2

C13 1 5 6, 13 5 6 0

C14 1 2 3, 14 3 3 0

C21 0 0 0, 21 1 0 1 0

13

C22 0 2 1, 22 6 1 5 0

C31 2 0 2 , 31 6 2 4 0

C34 2 2 4 , 34 4 4 0

Клітка (1,3) повинна бути закрита. Закриємо її клітками (2,3) і

(2,4).

З першого рядка 10 переведемо з клітки (1,1) на (2,1), а 30 з (1,2)

на (3,2).

	20	110	40	110
60	1/10	2/10	5/40	3/-
120	1/10	6/-	5/-	2/110
100	6/-	3/100	7/-	4/-

Транспортні витрати:

L0 1 10 2 10 1 10 2 110 3 100 5 40 760 .

Перевірка плану на оптимальність:

U1 V1 1, U1 V2 2

U2 V1 1, U2 V4 2, U3 V2 3

U1 1, V1 0, V3 4, U2 1, V4 1, U3 2

C14 1 1 2, 14 3 2 1 0

C22 1 1 2, 22 6 2 4 0

C23 1 4 5, 23 5 5 0

C31 2 0 2, 22 6 2 4 0

C33 2 4 6, 33 7 6 1 0

C34 2 1 3, 34 4 3 1 0

Тому що всі ij 0, те запропонований план є оптимальним.

5. Метод динамічного програмування.

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

Розглянемо операцію , що складається з m кроків. Нехай ефективність операції характеризується показником W, що для стислості будемо називати виграшем. Припустимо, що виграш W за всю операцію складається з виграшів на кожнім етапі:

14

m

W Wi ,

i 1

де Wi – виграш на i-м кроці.

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

керування операцією в цілому:

x x1, x2,...,xm .

Керування x*, при якому досягається максимум W, називається оптимальним керуванням. Оптимальне керування складається із сукупності оптимальних крокових керувань

x* x1*, x2*,...,xm* .

Максимальний виграш, що при цьому досягається:

W max W x .

x

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

Задача про розподіл ресурсів.

Планується розподіл початкової суми 0 між підприємствами П1, П2,…,Пn. Передбачається, що виділення підприємству Пк суми xk дає доход f xk . Будемо вважати, що:

1.Доход, отриманий від вкладення засобів у підприємство Пк, не залежить від вкладених коштів в інші підприємства.

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

3.Загальний доход дорівнює сумі доходів, отриманих від розподілу всіх засобів по всіх підприємствах.

Нехай Z – сукупний загальний доход від розподілу всіх засобів по всіх підприємствах:

n	,	x1, x2,...,xn 0,	x1	x2 ... xn	0.
Z f xk
k 1
Отже, повернемося до рішення задачі.
Позначимо	x1 –	внесок у перше підприємство,		x2 -в друге,	x3 – у

третє і x4 – у четверте. При цьому

x1 x2 x3 x4 200 .

Розіб'ємо операцію на 4 етапи. Перший етап – вкладення в перше підприємство, другий – у друге і т.д.

15

Позначимо 0 – гроші, не вкладені до першого етапу, 1 0 x1 – до

другого етапу, 2	1 x2 – до третього етапу,	3	2 x3 – до
четвертого етапу.

Позначимо Z4* 3 максимальний доход, що може бути отриманий на

4-м етапі, якщо до четвертого етапу дійдуть засобу 3, x4* – відповідне оптимальне керування, Z3* 2 – максимальний доход із третього і четвертого етапів, якщо до третього етапу доходять засобу 2 , x3* –

відповідне оптимальне керування, Z2* 1 – максимальний доход із другого, третього і четвертого етапів разом, якщо до другого етапу надійдуть засобу 1, x2* – відповідне оптимальне керування, Z1* 0 –

максимальний доход із всієї операції, x1* – відповідне оптимальне керування.

Очевидно, що Z4* 3 f4 3 ,

Z3* 2 max f3 x3 Z4* 2 x3 ,

0 x3 2

Z2* 1 max f2 x2 Z3* 1 x2 ,

0 x2 1

Z1* 0 max f1 x1 Z2* 0 x1 .

0 x1 0

Рішення задачі почнемо з четвертого етапу.

Якщо до четвертого етапу надійшли засобу 3, то вони повинні бути вкладені. Тому

Z4* 40 4, x4* 40 40,

Z4* 80 6, x4* 80 80,

Z4* 120 8, x4* 120 120,

Z4* 160 13, x4* 160 160,

Z4* 200 16, x4* 200 200.

Третій етап:

Z3* 2 max f3 x3 Z4* 2 x3 .

0 x3 2

Якщо до третього етапу надійшли засобу в розмірі 2 40, то вони можуть бути або вкладені (у цьому випадку на 4-й етап гроші не надійдуть, і прибуток буде дорівнює 3+0=3), або переведені на 4-й етап (у цьому випадку прибуток дорівнює 0+4=4).

Z3* 40 4, x3* 40 0.

			Z	*	0 4,	max
2	40:	0,		3
		x3		*
			Z		3 0.
		40,		3

16

Якщо 2 80, то для x3 можливо 3 варіанти:

						0,	Z3* 0 6,
	2	80 :	x	3		40,	Z*	4 4,	max
							3
							*
								4 0.
						80,	Z3

Аналогічно, одержуємо:

2 120:

2 160:

2 200:

Другий етап:

0,	0 8,
	3 6,	max
40,
	4 4,
80,
	7 0.
120,
0,	0 13,	max
	3 8,
40,
	4 6,
80,
	7 4,
120,
	11 0.
160,
0,	16,
	13 3,
40,
	4 8,
80,
	7 6,
120,
	11 4,
160,
	18.	max
200,

		0,	0 4,
1	40:
			6 0.	max
		40,
		0,	0 8,
1	80:		6 4,	max
		40,
			9 0.
		80,

17

1 120:

1 160 :

1 200 :

0,	0 13,
	6 8,
40,
	9 4,
80,
	11 0.
120,
0,	0 13,
	6 9,
40,
	9 8,
80,
	11 4,
120,
	13.
160,
0,	0 18,
	6 13,
40,
	9 9,
80,
	11 7,
120,
	13 4,
160,
	15.
200,

max

max

max

На першому етапі можливий тільки один варіант 0 200:

		0,	0 19,
			8 16,	max
		40,
0	200 :		10 13,
		80,
			11 10,
		120,
			12 6,
		160,
			18.
		200,

Тому що		x* 40,	те	на другий етап надходять засобу в розмірі
		1
1 160,		x2* 160 80,		отже, до	третього етапу надійдуть засобу в
розмірі	80 тис. грн.		x3* 80 40,		отже на останній етап надійдуть
засобу	в	розмірі	x4* 40 40.		Разом, максимальний прибуток за

підсумками всієї операції складає 24 при керуванні 40,80, 40, 40 .

Результати обчислень по всіх етапах приведемо в таблиці:

18

4-й етап

3-й етап

2-й етап

1-й етап

	Z	*	3		x*	3		Z*	2		x*	2		Z*	1		x*	1		Z*	0		x*	0
		4			4			3			3			2			2			1			1
40		4			40			4			0			6			40
80		6			80			7			40			10			40
120		8			120			9			40			13			40(80)
160		13			160			13			0			16			80						40
200		16			200			18			200			19			40			24

19

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ

1.Вентцель Е.С. Исследование операций. – М.: Советское радио, 1972.

– 553 с.

2.Один Г. Теорія игр. – М.: Мир, 1971.

3.Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. – М.: Наука, 1987.