• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

Розв’язання задачі розподілу вагонів під навантаження методом множників, що дозволяють

Попередньо необхідно звести вихідні дані в таблицю (див. табл. 3.1). У цій таблиці рядки відповідають типам вагонів, стовпці – вантажам; останні три стовпці відведені для суми вагонів кожного виду, які використовуються під завантаження, величини надлишків і недостач, а також міток. У кутах клітин записані дійсні технічні норми завантаження p_ij.

Таблиця 3.1

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

Таблиця 3.2

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

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

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

Крок 5. Визначити мінімальне значення серед l_j: l=minl_j

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

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

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

Таблиця 3.3

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

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

Таблиця 3.4

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

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

Таблиця 3.5

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

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

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

Читайте також:

1. IV. Перевірка розв’язання і відповідь
2. Rete-алгоритм
3. Алгоритм
4. Алгоритм
5. Алгоритм 1.
6. Алгоритм RLE
7. Алгоритм безпосередньої заміни
8. Алгоритм Берлекемпа-Мессі
9. Алгоритм відшукання оптимального плану.
10. Алгоритм Дейкстри.
11. Алгоритм Деккера.
12. Алгоритм Деккера.

Переглядів: 1682