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

Лист

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

Уравнение ( 11) и система ( 12 ) или эквивалентны. Задача линейного программирования вида:

mах (р, х)

Ах=B ( 13 )

х>0

называется задачей линейного программирования в канонической форме.

Чтобы привести задачу линейного программирования в стандартной фюрме к форме канонической, следует ввести дополнительные переменные ui,ui>=0,i=1,2,….,m , такие, что

E aij xj+ui=bi, i=1,….,m

Причем целевая функция при этом должна оставаться неизменной. Для этого запишем целевую функцию в виде:

EpjXj+0*u1+0*u2+…..0*um

Здесь коэффициенты при переменных u1,….,um полагаются равными нулю. Тогда задача (7) - (9) в каноническом виде принимает вид:

( n )

( E PjXj ) max x

( j=1 )

(14)

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

n

E aijxj+ui=bi, i=1,…..,m (15)

j=1

x1,…..,xn>=0 u1,…..um>=0 (16)

Стандартная задача линейного программирования на минимум

(матричная запись) записывается в виде:

(p,x) max x (17)

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

ax>=b

x>=0 (18)

или в записи в виде неравенств: