Реферат Розподіл вантажоперевезень

n=top>

B7

6

6

7

8

15

B8

2

5

4

4

19

B9

17

3

5

6

6

B10

14

9

10

17

12

2. Рішення транспортної задачі розподільчим методом

Методика розрахунку

1) Розподіляємо вантаж по кожному стовпців клітці з найменшою відстанню. Після розподілу такі клітини називаються завантаженими (Таблиця 2.1).

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

віддалі кожної завантаженої клітини. Потім визначаємо потенціали інших стовпців і рядків, виходячи з того, що u + v = c, при цьому визначаємо потенціали тільки рядків і стовпців, що містять завантажені клітини. У разі, якщо кількість завантажених клітин виявиться менше числа m + n-1 (де m-число рядків, n-число стовпців), то необхідно штучно завантажити відсутню кількість клітин, для цього в них проставляють нуль завантаження і після цього з такою клітиною оперують як з завантаженою. Доцільно нуль ставити в таку клітину, для якої один з індексів вже визначений, а також по можливості в клітку з найменшою відстанню. p> 3) Після цього знаходимо такі незавантажені клітини, в яких сума індексів більше відстані, зазначеного у відповідних клітинах - такі клітини називаються потенційними. Цифру різниці між сумою індексів і відстанню називають потенціалом. Потенціал записуємо у відповідну незавантажених клітку в круглих дужках.

4) Знаходимо клітку з найбільшим потенціалом (ця умова є необов'язковим). Для обраної потенційної клітини В«будуємоВ» контур - замкнуту лінію, що складається з прямих горизонтальних і вертикальних ліній, всі вершини цієї лінії повинні знаходитися в завантажених клітинах, а також в обраному потенційної. Контур будуємо за правилом - від обраної потенційної клітини веду пряму горизонтальну або вертикальну лінію до такої завантаженої клітини, якій під прямим кутом відповідає ще одна закачана клітина, і так до тих пір, поки лінія не замкнеться у вихідній потенційної клітці.

5) Після цього всім вершин контуру поперемінно присвоюємо знаки В«-В» і В«+В», починаючи з обраної потенційної.

6) З завантажень, позначених знаком В«+В», вибираємо найменшу.

7) Дану величину віднімаємо від завантажень зі знаком В«+В» і додаємо до завантажень зі знаком В«-В».

Таблиця 2.1 - Початковий розподіл обсягу перевезень між відправниками та споживачами

Пот-ре-

бі-тель

Ін-індекси

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

Пот-реб-ність

у вантажі

A1

A2

A3

A4

A5

u

v

B1

В 

B2

B3