17. Двойственный симплекс-метод. Псевдорешение. Предпосылки применения алгоритма двойственного симплекс-метода.

Он применяется для решения ЗЛП, у которых свободные члены нетривиальных систем ограничений могут быть отрицательными числами.

Z= c_1 x_1+c_2 x_2+…+c_n x_n+c_0→max X_1+ a_(1,m+1) X_(m+1)….a_1n x_n=b_1 * X_2+ a_(2,m+1) X_(m+1)… a_2n x_n=b_2 ……………………………….. X_m+ a_(m,m+1) X_(m+1)…a_mn X_n==b_n xi≥0

Предположим что Хi может быть отрицательным. Исключим из Z базисные переменные и и приведем задачу к виду:

Z+∆m1Xn+∆_(m+1) X_(n+1) ∆_(m+2) X_(n+2) ∆_n X_n= ∆_0

∆j-оценка свободных переменных xj

Решение  X=(b_1, b_2…b_n,0…0) называется псевдорешением (псевдопланом) задачи * если все ∆j≥0

Если для псевдорешения имеется хотя бы одна bi≤0 что aij≥0, то исходная задача решений не имеет.

Если для псевдорешения для любых bi≤0 в соотв. уравнении существует aij≤0 то можно перейти к новому псевдоплану. При этом значение Z не уменьшается.

Алгоритм:

1.Если все bi≥0 ,то X=( , … ,0…0) оптимальное решение (*)

2. Если существует bi<0, так что aij≥0, то решений нет

3. Выбираем разрешающую строку с наиб. gо модулю bi <0 далее находим min по всем коэф-там строки (-∆j/aij)=- ∆r/air => air разр.

18. Постановка задачи целочисленного программирования. Примеры задач с экономическим содержанием.

Задача линейного целочисленного программирования формулируется следующим образом:

найти такое решение (план) X = (X1 , х2 , . . . , хn ) , при котором линейная функция Z= c_1 x_1+c_2 x_2+…+c_n x_n принимает максимальное или минимальное значение при ограничениях Суммa a_ij X_jа=bi , i=1,2 …,m, j=1,2,…,n xj≥0 – целые числа

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

машин в управляющем комплексе и многие другие.

19. Сформулируйте алгоритм метода гомори решения задач целочисленного программирования

Алгоритм Гомори — алгоритм, который используется для решения полностью целочисленных задач линейного программирования. Алгоритм включает в себя:

1. Решение задачи одним из методов группы симплекс-методов или группы методов внутренней точки без учёта требования целочисленности. Если полученное оптимальное решение целочисленно, то задача решена.

2. Составляется дополнительное ограничение для переменной , которая в оптимальном плане имеет максимальное дробное значение, хотя должна быть целой. Тогда величины коэффициентов элементов , вычисляются так:

где — целая часть числа . Тогда дополнительное ограничение формируется следующим образом:

Оно будет целым неотрицательным при целых неотрицательных и После составления ограничения оно вводится в систему линейных ограничений и задача решается заново при исходных ограничениях и дополнительном ограничении. Если получено целочисленное решение, задача решена. В противном случае необходимо повторить второй этап.