9.Вырожденность задач линейного программирования. Правило устранения зацикливания.

решение в котором нулей оказывается больше, чем свободных переменных называется вырожденной системой

факт существования вырожденной системы может привести так называнию зацикливанию, когда должно произойти увеличение целевой функции при переходе к новому опорному плану, а увеличении не происходит.

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

12. Двойственный симплекс-метод.

1. Приводим задачу к каноническому виду и приводим систему к ед базису (Ж-Г).+ свободные члены не обязательно

2. Переносим условия задачи в симплекс таблицу

3. Освобождаемся от отрицательных свободных членов, выбирая разрешающий элемент по следующиму правилу:

- рассмотрим строку с наибольшим по абсолютной величине отриц. Свободным членом и смотрим, есть ли отриц коэффициенты

-если нет, то задача не имеет решений

-если есть, то для столбцов, содержащих их, находим, наименьшее + отношение свободных членов к соответствующим элементам столбцов

-умножаем эти наименьшие отношения на соотв оценки индексной строки и выбираем min значение

- по выбранному произведению выбираем разрешающий элемент.

8.Симплекс-метод решения задач линейного программирования. Определение исходного опорного решения. Вторая часть симплекс-метода. Симплекс-таблицы.

Решение состоит из 2-х частей

1. Нахождение исходного опорного решения

2. Последовательный переход от полученного опорного решения к новому улучшенному опорному решению.

1. Часть

• Систему приводим к ед базису (Ж-Г)

• Если появились отрицательные свободные члены, то от них избавляются

• Систему снова приводят к ед базису с помощью симплекс преобразований

• Если существует хотя бы 1 отрицательный свободный член, то базисное решение не явл оптимальным:

- в системе приведенной к ед базису, среди отриц. Свободных членов выбираем наибольший по абсолютной величине и уравнение которое ему соотв * на (-1). Затем + почленно к тем уравнениям системы, в которых св члены отриц. В результате получаем преобразованную систему. В которой все свободные члены>=0, но нарушен ед базис:

• Выбираем уравнение в котором нет базисных переменных, смотрим есть ли в нем +коэффициенты(если есть, то берем 1 из них и столбец, содержащий этот коэфф берем за разрешающий)

• В разрешающею строку выбираем по наименьшему + отношению свободных членов к + элементам разрешающего столбца

• Разрешающий элемент принадлежит уравнению, где нет базисных переменных, после 1 шага симплексного преобразования система будет приведена к ед базису и получено опорное решение

• Разрешающий элемент не принадлежит уравнению, которое не содержит базисную переменную, но принадлежит уравнению где свободный член>0. Если мы сделаем шаг симплексного преобразования, то система будет приведена к ед базису. От этого шага поменяется только состав базисных переменных. В этом случае продолжаем работать с интерес нас уравнением, выбирая разрешающий элемент по нашему правилу, до тех пор, пока не придем к первому случаю, либо установим, что система несовместна

• Разрешающий элемент расположен не в интер нас уравнении, а в другом где свободный член =0. В этом случае, если провести итерацию симплекс преобразований, то свободный член в интер нас уравнении не изменится. В этом случае рекомендуется попробовать выбрать др разрешающий элемент и для которого будет выполнен 1 или 2 случай.