3.3.1 Алгоритм розв’язання розподільної задачі

Крок 1. Скласти початковий варіант розподілу вагонів таким чином, щоб кожен вантаж відправлявся в тих вагонах, для яких норма завантаження є максимальною (у разі наявності співпадаючих норм – у менш дефіцитних вагонах). Кількість вагонів кожного типу, що використовуються під завантаження, визначається за формулою x_ij=B_j/p_ij (округлити у більшу сторону). Кількість зайнятих вагонів і завантаженого в них вантажу записується у відповідній клітинці через дріб (див. табл. 3.2).

Таблиця 3.2

	Вантаж 1 600	Вантаж 2 128	Вантаж 3 500	Вантаж 4 100	Зайнято вагонів	Ri Надл. (+) Нед. (-)	Мітка
Вагони 1 типу 30 штук	27	13	15	7	0	+30
Вагони 2 типу 35 штук	30 20/600	16	17	8	20	+15
Вагони 3 типу 25 штук	30	21 7/128	22 23/500	10 10/100	40	-15	*
j		1,313	1,294	1,250

Крок 2. Визначити кількість зайнятих вагонів кожного типу , надлишки (+) і недстачі (-): .Якщо всі R_i0 розрахунок закінчено – дане рішення є оптимальним.

Крок 3. Класифікувати рядки на надлишкові та недостатні. Недостатніми є всі рядки в яких Ri<0, а також рядки в яких Ri=0 і які відповідають наступній вимозі: поточне значення завантаження в одному зі стовпців дорівнює поточному значенню завантаження в клітинці на перетинанні цього стовпця й одного з недостатніх рядків, при цьому дана клітинка повинна бути зайнятою. Всі недостатні рядки позначаються зірочкою (*) в останньому стовпці. Якщо всі рядки недостатні, то це кінець рішення – вивезти весь вантаж неможливо. Дане рішення забезпечує максимальне вивезення вантажу.

Крок 4. Для кожного стовпця що має x_ij>0 (зайняту клітинку) у недостатньому рядку визначити відношення , де у чисельнику узяте максимальне значення завантаження по стовпцю в цілому, а в знаменнику – максимальне значення серед надлишкових рядків. Отримані значення_j записати в нижній рядок.

Крок 5. Визначити мінімальне значення серед _j: =min_j

Крок 6. Перетворити матрицю завантажень розділивши всі значення в недостатніх рядках наЗначення з надлишкових рядків переноситься без змін (див. табл. 3.3).

Крок 7. В одному з надлишкових рядків матриці знайти клітинку st, для якої величина поточного завантаження дорівнювала максимальній в стовпці. Ця клітинка розглядається як допустима й у неї переноситься додатний обсяг вантажу x_st. При цьому необхідно враховувати, що поява нових від’ємних балансів і погіршення використання ресурсів не допускається. Кількість вагонів, що використовуються, визначається за фактичними значеннями завантаження p_ij.

У табл. 3.3 виконано перерозподіл вантажу 4 в обсязі 100 т з вагонів типу 3 у вагони типу 2. Під цей вантаж необхідно зайняти 13 вагонів типу 2, що менше їх надлишку в 15 одиниць.

Таблиця 3.3

	Вантаж 1 600	Вантаж 2 128	Вантаж 3 500	Вантаж 4 100	Зайнято вагонів	Ri Надл. (+) Нед. (-)	Мітка
Вагони 1 типу 30 штук	27	13	15	7	0	+30
Вагони 2 типу 35 штук	30 20/600	16	17	8 13/100	33	+2
Вагони 3 типу 25 штук	24	16,8 7/128	17,6 23/500	8	30	-5	*
j		1,050	1,035

Крок 8. Перейти до кроку 2.

Таблиця 3.4

	Вантаж 1 600	Вантаж 2 128	Вантаж 3 500	Вантаж 4 100	Зайнято вагонів	Ri Надл. (+) Нед. (-)	Мітка
Вагони 1 типу 30 штук	27	13	15	7	0	+30
Вагони 2 типу 35 штук	30 20/600	16	17 2/34	8 13/100	35	-0	*
Вагони 3 типу 25 штук	23,188	16,232 7/128	17 22/466	7,727	29	-4	*
j	1,111	1,249	1,333	1,143

У табл. 3.4 перенесено вантаж 3 з вагонів 3-го типу у вагони 2-го типу. Завантажити можна тільки 2 вагони (мається в надлишку) тобто 34 тонни. Кількість зайнятих вагонів 3-го типу при цьому зменшиться тільки на один.

Таблиця 3.5

	Вантаж 1 600	Вантаж 2 128	Вантаж 3 500	Вантаж 4 100	Зайнято вагонів	Ri Надл. (+) Нед. (-)	Мітка
Вагони 1 типу 30 штук	27 6/150	13	15	7	6	+24
Вагони 2 типу 35 штук	27 15/450	14,401	15,302 7/104	7,201 13/100	35	0
Вагони 3 типу 25 штук	20,872	14,610 7/128	15,302 18/396	6,955	25	0
j

Отримане рішення є оптимальним тому що всі R_i0.

Для перевезень використано 66 вагонів.