Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Нахождение решения расширенной задачи

Если получен опорный план Х= расширенной задачи, то значение целевой функции , тогда . Выражения для вычислений z₀ и ∆ состоят из двух независимых частей одна из которых зависит от М, а другая нет.

Симплексная таблица для решения расширенной задачи содержит на одну строку больше, чем обычная симплекс-таблица. Исходные данные расширенной задачи заносят в таблицу. Вычисленные значения z₀ и ∆ заносят сразу в две строки таблицы. В строку (m+1) помещают слагаемые этих выражений, не содержащие М. В строку (m+2) помещают коэффициенты при М из выражений для z₀ и ∆.

При переходе от одного опорного плана к другому в состав базисных переменных включают переменную, которая соответствует наибольшему по абсолютной величине отрицательному числу из строки (m+2).

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

Вычислительный процесс ведут по (m+2) строке, при этом могут возникнуть следующие ситуации:

1) все искусственные переменные исключены из базиса, тогда базис соответствует некоторому опорному плану исходной задачи и определение ее оптимального плана продолжают по (m+1) строке;

2) не все искусственные переменные исключены, но строка (m+2) не содержит больше отрицательных элементов в столбцах переменных . В этом случае рассматривают строку (m+2) и столбец и элемент, расположенный на их пересечении:

· если этот элемент отрицателен, то задача не имеет решения;

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

Если исходная задача содержит несколько переменных с коэффициентом «1», то их следует включить в искусственный базис.