Курсовая работа: Транспортная задача
Будем заполнять таблицу перевозками постепенно начиная с левой
верхней ячейки ("северо-западного угла" таблицы). Будем рассуждать при
этом следующим образом. Пункт В1 подал заявку на 18 единиц груза.
Удовлетворим эту заявку за счёт запаса 48, имеющегося в пункте А1,
и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В1
удовлетворена, а в пункте А1 осталось ещё 30 единиц груза. Удовлетворим
за счёт них заявку пункта В2 (27 единиц), запишем 27 в клетке
(1,2); оставшиеся 3 единицы пункта А1 назначим пункту В3.
В составе заявки пункта В3 остались неудовлетворёнными 39 единиц.
Из них 30 покроем за счёт пункта А2, чем его запас будет исчерпан,
и ещё 9 возьмём из пункта А3. Из оставшихся 18 единиц пункта А3
12 выделим пункту В4; оставшиеся 6 единиц назначим пункту В5,
что вместе со всеми 20 единицами пункта А4 покроет его заявку.
На этом распределение запасов закончено; каждый пункт назначения получил груз, согласно
своей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему
запасу, а в столбце - заявке.
Таким образом, нами сразу же составлен план перевозок, удовлетворяющий
балансовым условиям. Полученное решение является опорным решением транспортной задачи:
Таблица № 2
ПН
ПО
|
В1
|
В2
|
В3
|
В4
|
В5
|
Запасы
аi
|
А1
|
10
18
|
8
27
|
5
3
|
6 |
9 |
48 |
А2
|
6 |
7 |
8
30
|
6 |
5 |
30 |
А3
|
8 |
7 |
10
9
|
8
12
|
7
6
|
27 |
А4
|
7 |
5 |
4 |
6 |
8
20
|
20 |
Заявки
bj
|
18 |
27 |
42 |
12 |
26 |
125 |
Составленный нами план перевозок, не является оптимальным по
стоимости, так как при его построении мы совсем не учитывали стоимость перевозок
Сij.
Другой способ - способ минимальной стоимости по строке - основан
на том, что мы распределяем продукцию от пункта Ai не в любой
из пунктов Bj, а в тот, к которому стоимость перевозки минимальна.
Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов
и находим минимальную стоимость перевозки из оставшихся пунктов Bj. Во
всем остальном этот метод схож с методом северо-западного угла. В результате, опорный
план, составленный способом минимальной стоимости по строке выглядит, так как показано
в таблице № 3. При этом методе может получиться, что стоимости перевозок Cij
и Cik от пункта Ai к пунктам Bj
Страницы: 1, 2, 3, 4, 5, 6, 7, 8 |