5. Вирішення розподільної задачі за допомогрою методу найбільших різниць

Постановка задачі.

Порт, упродовж планового періоду, повинен розподілити три вантажопотоки (j=1,3) між трьома вантажними комплексами (i=1,3).

Заплановані об’єми виробництва за кожним напрямком складають Qi:

Відомо:

- пропускна здатність причального комплексу Пj, т.

- витрати терміналу Сij, дол.

- продуктивність терміналу за спеціалізацією Рij, т.

Економіко-математичний вигляд задачі:

Z = min (43)

i= (44)

j= (45)

i= ; j= (46)

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

Цільова функція (43) мінімізує витрати з опрацювання вантажопотоків по терміналам.

Вираз (44) – обмеження першої групи, характеризують використання вантажопотоків кожного типу.

Вираз (45) – обмеження другої групи відображають використання пропускної спроможності термінала.

Обмеження третьої групи (46) являють собою умови невід'ємності змінних.

Позначення змінних задачі наведено в таблиці 5.1.

Таблиця 5.1. – Позначення змінних задачі.

Вантажопотік	Причальні комплекси
	1	2	3
1	Х11	Х12	Х13
2	Х21	Х22	Х23
3	Х31	Х32	Х33

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

Цільова функція:

Z = 19x₁₁ + 48x₁₂ + 15x₂₁ + 32x₂₃ + 61x₃₂ + 28x₃₃ min;

Обмеження першої групи, яке характеризує використання вантажопотоків кожного типу:

x11 + x12 = 8;

x21 + x23 = 2;

x32 + x33 = 7.

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

981,996x₁₁ + 818,33х₂₁ ≤ 8265,65;

654,664х₁₂ + 1145,662х₃₂ ≤ 10723,005;

818,33х₂₃ + 490,998х₃₃ ≤ 7148,67;

Обмеження третьої групи, які є умовою невід'ємності змінних:

x₁₁ ≥ 0, x₁₂ ≥ 0;

x₂₁ ≥ 0, x₂₃ ≥ 0;

x₃₂ ≥ 0, x₃₃ ≥ 0.

i=1,2,3; j=1,2,3.

Таблиця 5.2. – Підготовка вихідних даних для розв’язку.

Вантажопотік	Причальний комплекс						Кіл-ть вант. Qi тис т	Si	Резерв △Qi млн т
	1		2		3
1		19		48		0	8
	981,996		818,33		0
2		15		0		32	2
	654,664		0		1145,662
3		0		61		28	7
	0		818,33		490,998
Пj	8265,65		10723,005		7148,67		Розміщ. Інф. в осередку раб. Т.
Si							Пij хij Cij
Резерв П

Таблиця 5.3. – Матриця відповідності між транспортними характеристиками вантажів і спеціалізацією причалів.

Вантажопотік i (i=1,2,3)	Причальний комплекс j (j=1,2,3)
	j=1	j=2	j=3
i=1	1	1	0
i=2	1	0	1
i=3	0	1	1
Примітка: "1" - вантажопотік відповідає спеціалізації причалу; "0" - вантажопотік не відповідає спеціалізації причалу.

Алгоритм метода «Найбільших різниць».

1. Визначення середнього значення собівартості вантажопереробки 1 тони вантажу і-го вантажопотоку:

(47)

2. Визначення значення вантажообробки з максимальною собівартістю (max S_l – базовий вантажопотік. )

(48)

{0,37;0,026;0,067}=0,067(S3)

В даному випадку базовий вантажопотік третій.

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

(49)

4. Визначення величини оцінки δ(«дельта») для кожного осередка основного блоку робочої таблиці.

(50)

δ₁₁ = 0*981,996-19 = -19

δ₁₂ = 0,074*818,33-48 = 12,56

δ₂₁ = 0*654,664-15 = -15

δ₂₃ = 0,057*1145,662-32 = 33,3

δ₃₂ = 0,074*818,33-61 = 0

δ₃₃ = 0,057*490,998-28 = 0

5. Складаємо план закріплення вантажів за вантажними комплексами, починаємо с клітинки, в якій забезпечується максимальне значення оцінки δij з урахуванням знаку. При цьому значення параметру управління визначається наступним чином:

X_ij = min {Qi; П_j/P_ij}

Клітка для якої таким чином визначається величина xij є зайнятою.

Так, найбільше значення δij міститься в осередку δ23 = 33,3. Значення змінної для даного осередку знаходиться наступним чином:

Якщо х_ij = Qi, тобто і-ий вантажопотік повністю закріплюється за j-им вантажним комплексом, то рядок, що відповідає даному вантажопотоку, повністю виключається з подальшого розгляду. При цьому можливий резерв пропускної здатності ∆Пj, який знаходиться за формулою:

(51)

∆П`3 = 7148,67-2*1145,662 = 4887,346

∆П`2=10723,005-8*818,33 = 4176,365

∆П`2 =4176,36-5,103*818,33 = 0

Q`₁ = 7 – 5,103 = 1,897

∆П`3 =4887,346-1,897*490,998 = 3955,922

При такому розподілу значення цільової функції приймає наступне значення:

Z = 32*2+48*8+61*5,103+28*1,897= 812,399 тис.долл.

Таблиця 3 – Розв’язання задачі

Вантажопотік	Причальний комплекс									Кіл-ть вант. Qi тис т			Si			Резерв △Qi млн т
	1		2				3
1	-19	19		12,56		48			0			8			0,037			0
				8
	981,996			818,33				0
2	-15	15				0		33,3	32			2			0,026			0
							2
	654,664			0				1145,662
3		0		0		61		0	28			7			0,067			0
				5,103				1,897
	0			818,33				490,998
Пj	8265,65		10723,005				7148,67			Розміщ. Інф. в осередку раб. Т.
Si	0		0,074				0,057			Пij хij Cij
Резерв П	8265,65		0				3955,922

Висновок: В результаті розрахунків перший вантажопотік йде на другий причальний комплекс і складає 8,00 млн. т. Другий вантажопотік йде на третій причальний комплекс і складає 2 млн. т. Третій вантажопотік розподіляється між 2 та 3 причальними комплексами і складають 5,103 і 1,897 млн. т. відповідно.