Транспортная задача

Date: 2015-10-07; view: 411.

Пусть необходимо перевезти однородный груз из пунктов его пр-ва или хранения в пункты его потребления. При этом ставиться задача свести к минимуму транспортные расходы.

Пусть есть пункты поставки

И там находиться ед груза:

Пункты потребления

Их потребности составляют:

стоимость перевозки ед товара из пункта в

План перевозок можно задать в таблице:

- кол-во груза, которое нужно перевезти из пункта в

Если выполняется условие: . То задача наз-ся сбалансированной. Поэтому:

Стоимость перевозки из i-го пункта в j-ый равна

Т.о.: на мн-ве решений системы ограничений (*).

В общем случае, мн-во допустимых решений представляет собой пересечение полуплоскостей. Такое мн-во является выпуклым.

1. В случае если эта область является многоугольником (ограничено), то оптимальное решение всегда сущ-ет. Максимальное (минимальное) значение ф-ции достигается в какой-либо вершине этого многоугольника, т.е достаточно определить вершины многоугольника и выделить ту из них, для которой значение ф-ции является наибольшим (либо наименьшим).

2. Если мн-во допустимых решений не содержит ни одной точки, то задача не имеет решений.

3. Если образует неограниченную многоугольную область то

a. решение находиться в какой-либо вершине области решений

b. заданная ф-ция не ограничена сверху (снизу). Можно выяснить по расположению линий уровня в конкретном случае при изменении значений ф-ций.