Курсовая работа: Транспортная задача
и Bk равны. В этом случае, с экономической
точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка больше.
Так, например, в строке 2: C21 = C24, но заявка
b1 больше заявки b4, поэтому 4 единицы продукции
мы распределим в клетку (2,1).
Таблица № 3
ПН
ПО
|
В1
|
В2
|
В3
|
В4
|
В5
|
Запасы
аi
|
А1
|
10 |
8 |
5
42
|
6
6
|
9 |
48 |
А2
|
6
4
|
7 |
8 |
6 |
5
26
|
30 |
А3
|
8 |
7
27
|
10 |
8 |
7
0
|
27 |
А4
|
7
14
|
5 |
4 |
6
6
|
8 |
20 |
Заявки
bj
|
18 |
27 |
42 |
12 |
26 |
125 |
Способ минимальной стоимости по столбцу аналогичен предыдущему
способу. Их отличие состоит в том, что во втором способе мы распределяем продукцию
от пунктов Bi к пунктам Aj по минимальной стоимости
Cji.
Опорный план, составленный способами минимальных стоимостей,
обычно более близок к оптимальному решению. Так в нашем примере общие затраты на
транспортировку по плану, составленному первым способом F0 = 1039,
а по второму F0 = 723. Клетки таблицы, в которых стоят ненулевые
перевозки, являются базисными. Их число должно равняться m + n - 1. Необходимо
отметить также, что встречаются такие ситуации, когда количество базисных клеток
меньше чем m + n - 1. В этом случае распределительная задача называется вырожденной.
И следует в одной из свободных клеток поставить количество перевозок равное нулю.
Так, например, в таблице № 3:
m + n - 1 = 4 + 5 - 1 = 8,
а базисных клеток 7, поэтому нужно в одну из клеток строки 3
или столбца 2 поставить значение “0”. Например в клетку (3,5). Составляя план по
способам минимальных стоимостей в отличии от плана по способу северо-западного угла
мы учитываем стоимости перевозок Cij, но все же не можем утверждать,
что составленный нами план является оптимальным.
Распределительный метод оптимального плана
Теперь попробуем улучшить план, составленный способом северо-западного
угла. Перенесем, например, 18 единиц из клетки (1,1) в клетку (2,1) и чтобы не нарушить
баланса перенесём те же 18 единиц из клетки (2,3) в клетку (1,3). Получим новый
план. Подсчитав стоимость опорного плана (она ровняется 1039) и стоимость нового
плана (она ровняется 913) нетрудно убедиться, что стоимость нового плана на 126
единиц меньше. Таким образом, за счёт циклической перестановки 18 единиц груза из
одних клеток в другие нам удалось понизить стоимость плана:
Страницы: 1, 2, 3, 4, 5, 6, 7, 8 |