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