Реферат: Нахождение опорного плана транспортной задачи

Лист

Кп-км-п-44-2203-99

EpjXj  min x1..xn

при ограничениях:

E aij xj>=bi

…………..

E aij xj>=bm

X1….xn>=0

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

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

Пусть некоторый, однородный товар (продукт) хранится на M складах и потребляется в N пунктах (например, магазинах). Известны следующие параметры:

ai - запас продукта на -ом складе, ai>0, i=1,….,m

bj- потребность в продукте в -ом пункте, bj>0,j=1,….,n

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

m n

E ai = E bj (19)

i=1 j=1

Транспортная задача ставится как каноническая задача ЛП следующего специального вида:

m n

E E CijXij  min (20)

i=1 j=1

при условиях:

Лист

Кп-км-п-44-2203-99

n

E xij=ai,i=1,…,m (21)

J=1

n

E xij=bj,j=1,….,n (22)