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

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

Математическая формулировка замкнутой транспортной модели: требуется найти

,

при условиях

; (ограничения по потреблению)	(8.25)
; (ограничения по производству)	(8.26)
(условие замкнутости ).	(8.27)

.

Если условие (8.27) имеет форму неравенства (производство продукта не меньше его потребления), то транспортная модель называется незамкнутой или открытой.

Незамкнутая транспортная модель (например, часть продукции остается на складе) легко приводится к замкнутой введением дополнительного, фиктивного узла (n+1) потребления с потребностью и транспортными расходами .