Реферат Курсовая Конспект
Алгоритм симплекс-метода для задачи на минимум - раздел Образование, Конспект лекций МЕТОДЫ ОПТИМИЗАЦИИ Шаг 0. Подготовительный Этап. Приводим Задачу Лп К Специально...
|
Шаг 0. Подготовительный этап.
Приводим задачу ЛП к специальной форме (15).
Шаг 1. Составляем симплекс-таблицу, соответствующую специальной форме:
B | … | … | ||||
L | … | … | ||||
… | … | |||||
.. | .. | ………… | ||||
… | … | |||||
.. | .. | ………… | ||||
… | … |
Заметим, что этой таблице соответствует допустимое базисное решение задачи (15). Значение целевой функции на этом решении
Шаг 2. Проверка на оптимальность
Если среди элементов индексной строки симплекс – таблицы нет ни одного положительного элемента то, оптимальное решение задачи ЛП найдено: . Алгоритм завершает работу.
Шаг 3. Проверка на неразрешимость
Если среди есть положительный элемент , а в соответствующем столбце нет ни одного положительного элемента , то целевая функция L является неограниченной снизу на допустимом множестве. В этом случае оптимального решения не существует. Алгоритм завершает работу.
Шаг 4. Выбор ведущего столбца q
Среди элементов выбираем максимальный положительный элемент .Этот столбец объявляем ведущим (разрешающим).
Шаг 5. Выбор ведущей строки p
Среди положительных элементов столбца находим элемент , для которого выполняется равенство
.
Строку p объявляем ведущей (разрешающей). Элемент объявляем ведущим (разрешающим).
Шаг 6. Преобразование симплексной таблицы
Составляем новую симплекс-таблицу, в которой:
а) вместо базисной переменной записываем , вместо небазисной пере менной записываем ;
б) ведущий элемент заменяем обратной величиной ;
в) все элементы ведущего столбца (кроме ) умножаем на ;
г) все элементы ведущей строки (кроме ) умножаем на ;
д) оставшиеся элементы симплексной таблицы преобразуются по следующей схеме «прямоугольника».
Из элемента вычитается произведение трех сомножителей:
первый – соответствующий элемент ведущего столбца;
второй – соответствующий элемент ведущей строки;
третий – обратная величина ведущего элемента .
Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».
Шаг 7. Переход к следующей итерации осуществляется возвратом к шагу 2.
– Конец работы –
Эта тема принадлежит разделу:
Государственное образовательное учреждение высшего профессионального образования... Омский государственный технический университет...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм симплекс-метода для задачи на минимум
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов