Переход от канонической к стандартной

Переход от стандартной формы к канонической форме.

1) ai1x1+ai2x2+…+ainxn<=bi (2)

ai1x1+ai2x2+..+ainxn+ainxi+n=b xn+i>=0, i=1,m – балансовые переменные. (1)

Можно доказать, что все решения системы 1 равны решениям неравенства 2 и в этом сысле они эквивалентны. Функцию цели эти переменные(xn+i) могут быть введены с коэффициентами =0 => z=c1x1+..+cnxn+oXn+1+..+oxn+m->max

Осуществляется двумя способами.

1. а=b (a>=b a<=b) -> a1x1+a2x2=b a1x1+a2x2>=b

a1x1+a2x2<=b

2. Z=c1x1+…+cnxn->max

a11x1+…+a1nxn=b1

a21x1+…+a2nxn=b2

am1x1+…+amnxn=bm (m<n – бесконечно много решений)

1. Приводим к единичному базису методом гауса. Приравняем все свободные переменные к 0, т.е. xm+1=xm+2=0 то получим первоначальное базисное решение.

2. Выражаем все базисные переменные через свободные.

Х1=b1-a1,m+1xm+1-..-a1,nxn>=0

Xm=bm-am,m+1-…-amnxn>=0

3. В функция цели вместо базисных переменных подставить их через переменные.

Z=c1(b1-..-a1nxn)+c2(b2-..-a2nxn)+cm(bm-..-amnxn)+cm+1xm+1+…+cnxn->max/