Характеристика симплекс-метода
Симплекс-метод представляет собой алгоритм решения задачи, то есть четко описанную процедуру последовательных эквивалентных преобразований исходной математической модели методом Гаусса. В результате этих преобразований получают либо такую форму модели, из которой непосредственно извлекается оптимальный план (если он существует), либо такую форму, из которой непосредственно обнаруживается неразрешимость задачи (если оптимальный план не существует). В последовательности преобразований модели выделяют этапы. Результатом этапа является такая форма записи модели, с которой непосредственно связан один из допустимых планов задачи – так называемый текущий опорный план. Текущий опорный план геометрически представляет собой одну из вершин многогранной области допустимых планов. Движению по этапам симплекс-метода соответствует переход от одного текущего опорного плана к другому, от одной вершины области к соседней. При каждом таком переходе значение целевой функции улучшается (во всяком случае, не ухудшается). Цепочка преобразований последовательно приближает нас к оптимальному плану. Мы приходим либо к ситуации, когда текущим опорным планом становится оптимальный план, оптимальная вершина области допустимых планов, либо к ситуации, когда по четко сформулированным признакам мы непосредственно убеждаемся в неразрешимости задачи. Симплекс-метод непосредственно применяется к задаче линейного программирования в канонической форме, с ограничениями-равенствами и неотрицательными переменными. Любую задачу линейного программирования можно привести в канонической форме. Симплекс-метод – это универсальный алгоритм, кот может решать любую ЗЛП. Общая схема: 1. Необходимо привести задачу к канонической форме. Симплексная таблица для такой задачи – это таблица, заполненная следующим образом:
Текущий опорный план. Все переменные разбиваются на 2 группы: группу базисных и группу небазисных переменных. Базисные переменные, перечисленные в столбце Текущее значение целевой функции равно d. Для выяснения вопроса об оптимальности текущего опорного плана следует рассмотреть величины В том случае, если в данном разрешающем столбце наименьшее отношение возникает для нескольких его элементов (в этом случае такие наименьшие отношения, разумеется, равны друг другу), в качестве разрешающего следует выбрать один из таких элементов (любой). В том случае, если в разрешающем столбце среди его элементов вообще нет положительных, разрешающий элемент не может быть определен. Такая ситуация говорит о том, что целевая функция задачи неограниченна. Для любого допустимого плана в этом случае существует другой допустимый план с более высоким значением целевой функции. Любой план может быть улучшен, самого лучшего, оптимального плана не существует. Продолжать его поиск не имеет смысла. Процесс решения задачи на этом заканчивается. Таким образом, мы получили еще один признак конца процедуры решения задачи. Далее мы преобразовываем таблицу. Для этого делим ключевую строку на ключевой элемент. В преобразованной строке на месте разрешающего элемента оказывается 1. Далее преобразование осуществляется отдельно с каждой строкой. Для этого следует из преобразуемой строки вычесть преобразованную разрешающую строку, умноженную предварительно на подходящее число. Таким подходящим для каждой преобразуемой строки является свое число. Оно находится на пересечении преобразуемой строки и разрешающего столбца. В результате преобразования на месте этого подходящего числа оказывается 0.
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... ![]() ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (790)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |