Транспортная задача, метод потенциалов Опции

[Kylich]

Знающие люди, объясните пожалуйста как циклить положительные числа?
Вот задача:
Три пункта поставки груза(тонн)-А1=230, А2=250, А3=170
Пять пунктов потребления груза(тонн)- В1=140, В2=90, В3=160, В4=110, В5=150.
Стоимость доставки одной тонны груза в тыс. руб от каждого поставщика, к каждому потребителю задана матрица

(40 19 25 25 35)
C= (49 26 27 18 38)
(46 27 36 40 45)
Найти минимальные затраты.
Вот составленная таблица

Опорный план,метод северо-западного угла

S=40*140+19*90+27*160+18*90+20*40+45*150=20.800
вот теперь потенциалы

6 уравнений с 7 неизвестными
b1-a1=40 b2-a1=19 b3-a2=27 b4-a2=18 b4-a3=40 b5-a3=45
находим
b1=40 a1=0
b2=19 a2=-1
b3=26 a3=-23
b4=17
b5=22

теперь вычисляем для каждой клетки число
a13=1 a25=-17
a14=-8 a31=-29
a15=-13 a32=15
a21=-10 a33=-33
a22=-8
Ну и теперь надо избавиться от положительных чисел (15 и 1), чтобы план стал оптимальным, а для этого нужен цикл

..... Вот и всё, дальше не понимаю.


Сообщение отредактировано: Kylich - 4.10.2009 19:20

[amega]

и так, у нас есть матрца, которой задаются веса ребер графа:

и сам граф:


делаем первый цикл и находим первую отправку:
-помечаем певие временые метки:
a1=0
затем помечаем временные метки вершин б (их потенциалы):
б1=40; б2=19; б3=25; б4=25; б5=35
-во втором шаге выбираем временную метку с наименшым потенциалом - a2=0!
помечаем потенциалы вершин б, И ПОМНИМ что потенциалы могут только уменшатся
-и осталась вершина а3, также помечаем вершины б;
после 1 круга у нас получился такой граф:

и видим что точка с минимальным потенциалом а2 - б4=18, и мы может перевести 18 единиц, после чего ребро графа станет насыщеним!
помечаем первый путь:

перерисовуем наш граф(убираем перенасыщеное ребро)


Делаем 2 шаг нашего цикла:
-помечаем а1=0
помечаем вершины б своимы потенциалами,
делаем тоже самое для а2 и а3 и помним что потенциал вершин может только уменшатся!!!
наш граф с потенциалами после 2 круга

видим точка а1-б2=19 с мешим потенциалом, значит наш следующий путь а1-б2


наше ребро исчерпало свою пропускную способность

как можно было заметить что в 1 и во втором шаге мы уменшили потрености, потомучто мы уже перевезли по 2 путям и соответсвенно уменшилось.

вот повторяем эти шаги и мы решим задачу(если правильно будут шаги делатся)

Сообщение отредактировано: amega - 4.10.2009 21:31

[Kylich]

Наверное я не правильно задал свой вопрос? Я хотел узнать,как избавиться от положительных чисел,чтобы план стал оптимальным, а не нахождение рёбер графа.Извините, но чего-то я не понимаю.

[amega]

ой сори.. прсто я не дочитал что это на метод северо-западного угла, а его на расматривали:)
вот выше я показал как транспортная задача решается с помощью алгоритма часных потоков..

[Kylich]

Аmega очень странно,что такое не рассматривали.Обычно эту задачу решают по плану состоящих из 3 действий:
1план транспортной задачи
2.опорный план тз
3.оптимальный план тз
Хотя,если честно не знаю как обычно решают эту задачу. я пытаюсь решить эту задачу по книге "Математическое программирование в примерах и задачах" автор- А.Л. Акулич
А то, что вам объяснили по алгоритму частных потоков...это даже,наверное намного сложнее понять,чем нахождение этих планов.

Сообщение отредактировано: Kylich - 6.10.2009 13:37