транспортная

[Солныфко]

Не могу решить задачку, может кто головастый)
Решение транспортной задачи разбитием е на состовляющие недопускается. Как решить не понимаю. Помогите!
У трех поставщиков в разных количествах имеются три разных товара. Эти товары необходимо доставить пяти получателям в соответствии с потребностью каждого получателя в каждом из товаров. Составить план перевозок, обеспечивающий минимальную общую стоимость перевозок. Данные о тарифах перевозки по товара представлены в таблице 1, данные о возможости поставки товаров поставщиками представлены в таблице 2, данные о потребности товаров представлены в таблице 3, данные о пропускной способности маршрутов представлены в таблице 4.
Табл 1
Тарифы перевозки от поставщиков к покупателям
Поставщики Получатели
В1 В2 В3 В4 В5
Товар 1 А1 7 3 8 2 7
А2 4 3 1 5 6
А3 5 2 3 2 8
Товар 2 А1 2,4 1,9 4,3 4,5 1,8
А2 2,3 1,7 4,4 3,8 2
А3 2,2 1,6 4,8 2,2 4
Товар 3 А1 2,3 1,7 4 6,1 7
А2 2 1,4 4,3 4 2,5
А3 2 1,5 4,3 3 4
Табл 2
Поставщики Товар 1 Товар 2 Товар 3
А1 140 1840 850
А2 360 1200 1160
А3 180 1150 640

Табл3
Данные о потребности товаров
Товар Получатели
В1 В2 В3 В4 В5
Товар 1 140 120 230 180 60
Товар 2 360 1000 600 750 940
Товар 3 180 500 500 500 450

Табл4
Данные о пропускной способности каналов
Поставщики Получатели
В1 В2 В3 В4 В5
А1 1200 900 1000 850 770
А2 1200 1000 1100 900 1440
А3 950 1300 1000 870 660

[Utkin]

Есть такая вещь как венгерский алгоритм
http://ru.wikipedia.org/wiki/Венгерский_алгоритм

ЗЫ. Ну и ник, чего-то в последнее время много шепелявых, современная стоматология ни к черту.

[Солныфко]

Всё равно не понимаю как учесть и пропускную способность и разные виды товаров и др.
З.ы. Шипилявство норм)

[Utkin]

Там дан частный случай для двухмерных матриц. Что Вам мешает получить более обобщенную формулу и решать задачи независимо от размерности таблицы? Смысл алгоритма

если из всех элементов некоей строки или столбца вычесть одно и то же число y, общая стоимость уменьшится на y, а оптимальное решение не изменится;
если есть решение нулевой стоимости, оно оптимально.

Эти правила универсальны и не зависят от числа параметров.

[Солныфко]

Нэпонятно, давай по-русски))))

[sabbathist]

http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match

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