Реферат Курсовая Конспект
Метод искусственного базиса - раздел Образование, Конспект лекций МЕТОДЫ ОПТИМИЗАЦИИ Симплекс-Метод Применяется Для Решения Задач Лп, Представленных В Специальной...
|
Симплекс-метод применяется для решения задач ЛП, представленных в специальной форме:
(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) завершается.
– Конец работы –
Эта тема принадлежит разделу:
Государственное образовательное учреждение высшего профессионального образования... Омский государственный технический университет...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Метод искусственного базиса
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов