Решение ЗЛП симплекс-методом
Симплекс метод решения задач линейного программирования: типичный пример и алгоритм
Тема 2.4. Симплекс-метод линейного программирования.
При этом необходимо соблюдать принцип: Для решения ЗЛП симплекс-методом ее приводят к каноническому виду, то есть из ограничений — неравенств надо сделать ограничения — равенства. В целевой функции эти дополнительные переменные входят с нулевыми коэффициентами, то есть запись целевой функции не изменится. Каждую переменную, на которую не наложено условие неотрицательности, можно представить в виде разности двух неотрицательных переменных: Если ограничения задачи отображают наличие и расход ресурсов, то числовое значение дополнительной переменной в плане задачи, записанной в канонической форме, равно объему неиспользованного ресурса. Для решения задачи симплекс-методом будем использовать укороченные симплексные таблицы системы линейных уравнений и метод модифицированного жорданова исключения. Приведем стандартную форму системы неравенств 1 в каноническую форму системы уравнений путем введения дополнительных балансовых переменных x 3 , x 4 , x 5 , x 6. В экономическом смысле значения дополнительных переменных x 3 , x 4 , x 5 определяют остатки сырья после реализации продукции. Матрица полученной системы уравнений имеет вид:. Видно, что в матрице A базисным минором 4-го порядка является определитель, составленный из единичных коэффициентов при дополнительных переменных x 3 , x 4 , x 5 , x 6 , так как он отличен от нуля и равен 1. Это означает, что векторы-столбцы при этих переменных является линейно независимыми, то есть образуют базис , а соответствующие им переменные x 3 , x 4 , x 5 , x 6 являются базисными основными. Переменные x 1 , x 2 будут называться свободными неосновными. Если свободным переменным x 1 и x 2 задавать различные значения, то, решая систему относительно базисных переменных, получим бесконечное множество частных решений. Если свободным переменным задавать только нулевые значения, то из бесконечного множества частных решений выделяют базисные решения — опорные планы. Чтобы выяснить, могут ли переменные быть базисными, необходимо вычислить определитель, состоящий из коэффициентов при этих переменных. Если данный определитель не равен нулю, то эти переменные могут быть базисными. Тогда , то есть возможны 15 групп из 4-х базисных переменных или 15 базисных решений. Разрешим систему уравнений относительно базисных переменных x 3 , x 4 , x 5 , x Поэтому вместо переменной x 6 в качестве базисной надо взять другую переменную из числа свободных x 1 или x 2. Дальнейшее решение будем выполнять, используя укороченные симплексные таблицы, заполнив строки первой таблицы коэффициентами системы следующим образом табл. F —строка называется индексной. Чтобы получить допустимое решение опорный план , элемент b 4 надо сделать неотрицательным. Выбираем x 6 -строку с отрицательным свободным членом. В этой строке есть отрицательные элементы. Разрешающая строка определяет переменную x j , которая на следующем шаге выступает из базиса и станет свободной. Переменные x 1 и x 6 меняются местами. Совершаем шаг модифицированного жорданова исключения ШМЖИ с разрешающим элементом и составляем новую таблицу табл. Геометрически это соответствует вершине F 10; 0 многоугольника решений рис. Проверяем план на оптимальность. Меняем местами переменные x 2 и x 4. Выполняем шаг ШМЖИ, строим табл. В F -строке все коэффициенты неотрицательны, следовательно, опорный план является оптимальным. Геометрически соответствует точке D 9;6 см. Оптимальный план дает максимальное значение целевой функции у. Значения коэффициентов F -строки — ненулевые, поэтому полученный оптимальный план является единственным. F -строка позволяет представить целевую функцию через свободные переменные x 4 и x 5: Эту свободную переменную переводят в базис и, выполнив преобразования, получают второй оптимальный план с другим набором базисных переменных , то есть будем иметь альтернативный оптимум рис. Избежать зацикливания можно с помощью определенных мер, например, способом Креко. Задачи с зацикливанием встречаются редко. При сдаче лабораторной работы, студент делает вид, что все знает; преподаватель делает вид, что верит ему. I Решение тригонометрических уравнений как однородное II. Разрешение растровых изображений III. Решение ситуационных задач VI. Задание на следующее занятие: Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Составляем первый опорный план Задача остается прежней. Матрица полученной системы уравнений имеет вид:
Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Исторически общая задача линейного программирования была впервые поставлена в году Джорджом Бернардом Данцигом , Маршаллом Вудом и их сотрудниками в департаменте военно-воздушных сил США. В то время эта группа занималась исследованием возможности использования математических и смежных с ними методов для военных задач и проблем планирования. В дальнейшем для развития этих идей в ВВС была организована исследовательская группа под названием Project SCOOP. Первое успешное решение задачи линейного программирования на ЭВМ SEAC было проведено в январе года [2]. Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях. Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник возможно, бесконечный , называемый также полиэдральным комплексом. Зависимость от c порождает семейство параллельных гиперплоскостей. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k -мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено. В таких задачах первую фазу симплекс-метода можно вообще не проводить. Симплекс-метод, соответственно, делится на однофазный и двухфазный. Рассмотрим следующую задачу линейного программирования:. Теперь поставим эту задачу в эквивалентной усиленной форме. Необходимо максимизировать Z , где:. Разница между числом переменных и уравнений даёт нам число степеней свободы. Проще говоря, если мы рассматриваем вершину многогранника, то это число рёбер, по которым мы можем продолжать движение. Полученная точка будет вершиной в пересечении соответствующих непростым переменным гиперплоскостей. Для того, чтобы найти т. При этом начальное допустимое решение вычисляется однозначно: Теперь приведём шаги алгоритма. На каждом шаге мы будем менять множества простых и непростых векторов двигаться по рёбрам , и матрица будет иметь следующий вид:. Почему матрица будет иметь такой вид поясним в описании шагов алгоритма. Выбираем начальное допустимое значение, как указано выше. Выберем ребро, по которому мы будем перемещаться. Поскольку мы хотим максимизировать Z , то необходимо выбрать переменную, которая будет более всех уменьшать выражение. Для этого выберем переменную, которая имеет наибольший по модулю отрицательный коэффициент. Если таких переменных нет, то есть все коэффициенты этого выражения неотрицательны, то мы пришли в искомую вершину и нашли оптимальное решение. В противном случае начнём увеличивать эту непростую переменную, то есть перемещаться по соответствующему ей ребру. Эту переменную назовём входящей. Теперь необходимо понять, какая простая переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:. При фиксированных значениях непростых переменных система однозначно разрешима относительно простых, поэтому мы можем определить, какая из простых переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь перепишем матрицу B и вектор c B в соответствии с новыми наборами простых и непростых переменных, после чего вернёмся ко второму шагу. Поскольку число вершин конечно, то алгоритм однажды закончится. Найденная вершина будет являться оптимальным решением. Однако каждая итерация симплекс-метода является переходом от одной вершины к другой, и если неизвестно ни одной вершины, алгоритм вообще не может быть начат. Процесс нахождения исходной вершины не сильно отличается от однофазного симплекс-метода, однако может в итоге оказаться сложнее, чем дальнейшая оптимизация. Соответственно, будет создано некоторое количество дополнительных и вспомогательных переменных. Несмотря на то, что и дополнительные, и вспомогательные переменные создаются искусственно и используются для создания исходного базиса, их значения в решении сильно отличаются:. То есть ненулевое значение дополнительной переменной может но не должно сигнализировать о неоптимальности решения. Ненулевое значение вспомогательной переменной сигнализирует о недопустимости решения. После того, как было модифицировано условие, создаётся вспомогательная целевая функция. После этого проводится обыкновенный симплекс-метод относительно вспомогательной целевой функции. Когда будет найдено оптимальное значение вспомогательной целевой функции, могут возникнуть две ситуации:. Во втором случае мы имеем допустимый базис, или, иначе говоря, исходное допустимое решение. Можно проводить дальнейшую оптимизацию с учётом исходной целевой функции, при этом уже не обращая внимания на вспомогательные переменные. Это и является второй фазой решения. В остальном алгоритм похож на вышеописанный. В противном случае один из элементов выйдет на нулевое значение. Выводим соответствующий столбец из базиса. Во избежание получения больших ошибок время от времени матрица пересчитывается полностью. Этот процесс называется "повторением". При решении экономических задач часто матрица ограничений разреженная , в таком случае мультипликативный вариант получает дополнительные преимущества - можно хранить мультипликаторы в сжатом виде не хранить нули. Во избежание накопления ошибок округления может использоваться LU-разложение матрицы. При подавляющем числе ограничений типа "неравенство" может быть использован метод переменного базиса. Таким подходом удается решить задачи с десятками миллионов строк ограничений например, из теории игр. Для реализации двойственного метода необходимо перейти от задачи на минимум к задаче на максимум или наоборот путём транспонирования матрицы коэффициентов. При переходе от задачи на минимум целевая функция примет вид:. Если из пары двойственных задач одна обладает оптимальным планом, то и другая имеет решение, причем экстремальные значения линейных функций этих задач равны. Симплекс-метод удивительно эффективен на практике, но в Кли и Минти [4] привели пример, в котором симплекс-метод перебирал все вершины симплекса, что показывает экспоненциальную сходимость метода в худшем случае. С тех пор для каждого варианта метода был найден пример, на котором метод вел себя исключительно плохо. Наблюдения и анализ эффективности метода в практических приложениях привело к развитию других способов измерения эффективности. Симплекс-метод имеет среднюю полиномиальную сходимость при широком выборе распределения значений в случайных матрицах. Число ограничений больше влияет на вычислительную эффективность, чем число переменных, поэтому при формулировке задач линейного программирования нужно стремиться к уменьшению числа ограничений пусть даже путём роста числа переменных. Материал из Википедии — свободной энциклопедии. Метод Нелдера — Мида Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Линейное программирование методы и приложения. Государственное издательство Физико-математической литературы, Метод последовательного улучшения с базисом переменного размера для задач линейного программирования.. Для улучшения этой статьи желательно: Проставив сноски , внести более точные указания на источники. Страницы, использующие волшебные ссылки ISBN Википедия: Статьи без сносок Википедия: Навигация Персональные инструменты Вы не представились системе Обсуждение Вклад Создать учётную запись Войти. Пространства имён Статья Обсуждение. Просмотры Читать Править Править вики-текст История. В других проектах Викиучебник. Эта страница последний раз была отредактирована 11 мая в Текст доступен по лицензии Creative Commons Attribution-ShareAlike ; в отдельных случаях могут действовать дополнительные условия. Свяжитесь с нами Политика конфиденциальности Описание Википедии Отказ от ответственности Разработчики Соглашение о cookie Мобильная версия.
Тесты айкью 2014
Значение слова строптивый
Схемы вязки снудов
Как ухаживать за кожей в 29
Cenmax vigilant v 5a инструкция