Лекция 3

КОНТРОЛЬНЫЕ ВОПРОСЫ

Вырождение основной задачи линейного программирования

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

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

Пример4

Х₁+2Х₂£4

2Х₁+Х₂£4

Х₁ £2

Х₂£2

Хj³0, j=1,2

Zmax =X₁+X₂

Приводим к канонической форме

X₁+2X₂+X₃=4

2X₁+X₂+X₄=4

X₁+ +X₅=2

X₂+X₆=2

Xj³0, j=1,...,6

Zmax=X₁+X₂+0×X₃+0 ×X₄+0 ×X₅+0 ×X₆

Заполняем первую симплексную таблицу по алгоритму симплексного метода (табл.2.7.).

В оценочной строке две одинаковые отрицательные оценки, поэтому разрешающий столбец выбираем тот, который ближе к столбцу свободных членов. Минимальных симплексных отношений два, поэтому находим отношение элементов столбца Х₂ к элементам столбца Х₁. После пересчета минимальное отношение находится в третьей строке и равно 0, следовательно, разрешающий элемент равен 1. Далее идет обычный пересчет.

Таблица 2.7.

Первая симплексная таблица

1. Опишите общую схему расчетов симплексным методом
2. Какая система ограничений называется совместной?
3. Какое решение задачи называется допустимым?
4. Сформулируйте ключевую теорему симплексного метода.
5. Какие переменные задачи являются базисными, а какие – свободными?
6. Опишите схему нахождения первого опорного плана.
7. Когда задача имеет альтернативное решение?
8. Какое решение задачи называется вырожденным?
9. Когда задача линейного программирования не имеет решения, и по какой причине?