Переход от одной формы модели к другой форме модели , различные формы моделей з.Л.П.
В зависимости от системы ограничения различают в Л.П. три формы модели 1) каноническая 2) стандартная форма 3) общая форма. Эти три формы эквиваленты между собой в том смысле , что от одной формы можно перейти к другой с помощью элементарных преобразований.
Стандартная форма модели З.Л.П. . Система задачи формируется : Найти вектор х, удовлетворяющий системе ограничений и условию не отрицательности.
а11х1+а12х2+…+а1nxn<=b1
a21x1+a22x2+…+a2nxn<=b2
….
am1x1+am2x2+…+amnxn<=bn
xj>=0 j=1,4; Z=c1x1+c2x2+..+cnxn->max
A-матрица (m*n) Z=cx->max Ax<=b x>=0 ; C=(C1 C2 …Cn) b(b1 b2..bm)
Каноническая тоже самое только в системе ограничений = и Ax=b.
Общая форма. Найти вектор Х, удовлетворяющий системе ограничений
a11x1+a12x2+...+a1nxn=b1
am1x1+amnxn=bm
Xj>=0 (j=1,l) l<n Для которого Z=с1х1+cnxn -> max
Для того что бы решать задачи Л.П. симплекс методом необходимо иметь каноническую форму модели, поэтому необходимо знать , как перейти от одной формы модели к другой .
Переход от стандартной формы к канонической форме.
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 – бесконечно много решений)
Приводим к единичному базису методом гауса. Приравняем все свободные переменные к 0, т.е. xm+1=xm+2=0 то получим первоначальное базисное решение.
Выражаем все базисные переменные через свободные.
Х1=b1-a1,m+1xm+1-..-a1,nxn>=0
Xm=bm-am,m+1-…-amnxn>=0
В функция цели вместо базисных переменных подставить их через переменные.
Z=c1(b1-..-a1nxn)+c2(b2-..-a2nxn)+cm(bm-..-amnxn)+cm+1xm+1+…+cnxn->max/
Переход от задачи max к min и наоборот.
Во всех формах моделях все сводится к max, но иногда необходимо найти min/
Z=f(x)
min
z1max
z1=f(x)
Чтобы перейти от задачи min к max достаточно поменять знак и ввести новое значение функции.
Графический метод решения л.П.
Понятие: допустимого , оптимального , опорного решений, понятие области допустимых решений.
Вектор Х называется допустимым решением , если он удовлетворяет системе ограничений и условиям не отрицательности если они есть.
Вектор Х называется оптимальным решением если он является допустимым , а функция цели в этом решении достигает своего оптимального значения. (max or min)
Опорным решением называется не отрицательное базисное решение системы ограничений.
x1+x3 –x4=1
x2+2x3+4x4=-2
x1 и х2 –базисные неизвестные. Х3,х4 - неизвестные .
Приравняем свободные к 0. , тогда базисные неизвестные получают значения равные х1=1 х2=-2 и получаем базисное решение. Оно является не опорным , т.к. х=-2. Данное решение допустимое , базисное, не опорное.
Областью допустимых решений называется – совокупность всех допустимых решений системы.