Презентация на тему Транспортная задача

количествах

единиц, необходимо доставить в каждый из n пунктов назначения в количествах единиц. Стоимость перевозки единицы продукта из i-го (i= ) пункта отправления в j-й (j= ) пункт назначения равна и известна для всех компаний (i; j). Пусть – количество продукта, перевозимого по маршруту (i; j). Задача - определение таких величин для всех маршрутов (i; j), при которых суммарная стоимость перевозок минимальна.

j-му потребителю запланировано к перевозке ед.груза, то

стоимость перевозки составит .

грузы должны быть вывезены, т.е.
2.) Все

потребности должны быть удовлетворены, т.е.

оптимального плана начинают с определения опорного плана.

m+n уравнений.

отличные от 0 перевозки, называются занятыми, остальные незанятыми. Занятые

клетки соответствуют базисным неизвестным и для невырожденного опорного плана их должно быть m+n-1.

при которой нельзя построить замкнутый многоугольник или цикл, все

вершины которого будут лежать в занятых клетках).

только две соседние клетки расположены в одном столбце или

в одной строке таблице, причем последняя клетка находится в той же строке или столбце, что и первая.

переходят по столбцу (строке) к другой занятой клетке, в

которой делают поворот под прямым углом и движутся по строке (столбцу) к следующей занятой клетке и т.д., пытаясь возвратиться к первоначальной клетке.

определяют вершины цикла.

клеток, он не является опорным, т.к. ему соответствует линейно-зависимая

система векторов.
В этом случае в таблице всегда можно поставить замкнутый цикл, с помощью которого всегда уменьшают число занятых клеток до m+n-1.

а значит и цикличный, присоединить какую-либо незанятую клетку, то

план становится не опорным, появляется единственный цикл, все вершины которого за исключением одной, лежат в занятых клетках.