Метод искусственного базиса
Симплекс-метод применяется для решения задач ЛП, представленных в специальной форме:
(16)
Характерная особенность задачи (16) – известное базисное допустимое решение
Чтобы применить симплекс-метод для решения задачи ЛП в произвольной форме, необходимо привести эту задачу к виду (16), т. е. выделить начальное допустимое базисное решение. Для этого в симплекс-метод вводят подготовительный этап. Один из методов для реализации подготовительного этапа называется методом искусственного базиса и состоит в следующем [1,2,3].
Вычислительная схема метода искусственного базиса.
Шаг 1. Приводим задачу ЛП к канонической форме с неотрицательными правыми частями :
(17)
Шаг 2. В каждую i-ю строку ограничений (17) вводим искусственную неотрицательную переменную и строим вспомогательную задачу ЛП вида:
(18)
В задаче (18) – допустимое базисное решение и задача (18) легко может быть сведена к виду (16). Для этого целевую функцию необходимо выразить через свободные переменные :
Шаг 3. Для вспомогательной задачи (18) строим симплексную таблицу
b | … | |||
… | ||||
… | ||||
… | … | …………………. | ||
… |
и находим оптимальное решение вспомогательной задачи с помощью симплекс-метода.
Шаг 4. Если и все переменные являются небазисными, то m переменных из войдут в базис и система ограничений, соответствующих симплексной таблице, будет иметь вид
(19)
Так как переменные , то их исключили из системы (19), не нарушив при этом равенств. Выражая целевую функцию основной задачи через небазисные переменные системы (19), получим исходную задачу (17) в виде (16).
Шаг 5. Если , но в базисе остались искусственные переменные , для которых (вырожденный случай), то проводим для каждой искусственной переменной из базиса следующее преобразование симплексной таблицы.
Выбираем ведущим столбцом столбец такой переменной , для которой элемент индексной строки , а элемент столбца . В этом случае строка искусственной переменной будет ведущей и после стандартного преобразования симплексной таблицы (шаг 6 из прямого симплекс-метода) искусственная переменная выведется из базиса. В результате получим симплексную таблицу, соответствующую шагу 4.
Шаг 6. Если , то допустимого решения в исходной задаче (17) не существует (не могут все искусственные переменные быть равными нулю в задаче (18), а значит система ограничений задачи (17) несовместна) – процесс решения исходной задачи (17) завершается.
Дата добавления: 2020-10-01; просмотров: 405;