3.5 Признак неогр-ти целевой ф-ции на множестве планов

Если в f-строке симплексн таблицы есть хотя б одно отриц число, кот-му соотв-ет столбец неположит чисел, то максимум f(x)=+∞. Если в f-строке есть хотя б одно положит число, кот-му соотв-ет столбец неположит чисел, то минимум f(x)=-∞.

Пусть в f-строке симп табл 1 <0 и числа соотв-го ему s-го столбца неположит-ны( <0, i=1,m. Своб переменную будем увелич-ть, остальн своб переменные зафиксируем на 0( =0, j≠s). Задача 7-9 тогда имеет вид:

f= - (max) (10)

= - , i=1,m (11)

≥0, j=1,n (12)

Т. к. <0, то при увелич-и целевая ф-ция (10) также будет возрастать, а т. к. также ≤0, то при увелич-и переменных базисн перем-ые тоже будут возрастать, при этом ограничения (11), (12) никогда не нарушатся. Т.о. целевую ф-цию можно бесконечно увеличивать.

3.6 (Б) Алгоритм симплекс -метода решения злп

1. преобразовать задачу к канонической форме;

2. найти начальный опорный план и записать задачу в симпл. таблицу;

3 Найденный опорный план исследовать на оптимальность

А) если в f строке симплексной таблицы нет отрицательных чисел(за исключением стоящего в единичном столбце), то на этом плане целевая функция достигает максимума, т.е. план является оптимальным(если задача решается на минимум , то условием оптимальности опорного плана является отсутствие положительных чисел в f строке). Если в строке нет нулевых элементов то оптимальный план является единственным, а если есть хотя бы один ноль, то оптимальных планов бесконечное множество.

Б) если в f строке есть хотя бы одно отрицательное число , которому соответствует столбец неположительных чисел, то максимум равен +бесконечности, а если, хотя бы одно положительное число, которому соответсвует столбец неположительных, то минимум равен –бесконечности

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

Составляют симплекс отношения – отношения чисел в единичном столбце к соответствующим положительным числам разрешающего столбца. Минимальном симплексному отношению соответствует разрешающая строка. Число на пересечении разрешающей строки и столбца называют разрешающим элементом.

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