SHPORA.net :: PDA | |
|
Main FAQ гуманитарные науки естественные науки математические науки технические науки СИМПЛЕКСНЫЙ МЕТОД Симплексный метод (метод последовательного улучшения плана) решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (убывает) для задачи на max (на min) при условии, что данная задача имеет оптимальный план и каждый ее опорный план является невырожденным. Указанный переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно непосредственно записать. Пусть векторная форма данной задачи имеет следующий вид: (10.24) при условиях (10.25) (10.26) где ; – единичные векторы, образующие базис m-мерного пространства. Пусть . Допустим, что Теорема 10.5 (условие оптимальности). Опорный план задачи (10.24) – (10.26) является оптимальным, если для любого j, . Теорема 10.6. Если опорный план Х0 задачи (10.24) – (10.26) невырожден и , но среди чисел есть положительные (не все ), то существует такой опорный план , что . Теорема 10.7. Если для некоторого j = k и среди чисел нет положительных , то целевая функция (10.24) задачи (10.24) – (10.26) не ограничена на множестве ее планов. Сформулированные теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану. Нахождение оптимального плана симплексным методом включает следующие этапы. 1. Находят опорный план. 2. Составляют симплекс-таблицу (см. табл. 10.3 ). Базисные переменные … … … … … … … … 1 0 … 0 … 0 … … 0 1 … 0 … 0 … … … … … … … … … … … … … … … … 0 0 … 1 … 0 … … … … … … … … … … … … … … … … 0 0 … 0 … 1 … … 0 0 … 0 … 0 … … Таблица 10.3 3. Выясняют, имеется ли хотя бы одно отрицательное число . Если нет, то найденный опорный план оптимален. Если же среди чисел имеются отрицательные, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану. 4. Находят направляющие столбец и строку. Направляющий столбец определяется из условия , где максимум берется по тем j, для которых , а , а направляющая строка – минимальным из отношений компонент столбца вектора к положительным компонентам направляющего столбца. 5. По формулам определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов по векторам нового базиса и числа . Все эти числа записываются в новой симплекс таблице (табл. 10.4). 6. Проверяют найденный опорный план на оптимальность. Если он не является оптимальным и необходимо перейти к новому опорному плану, то возвращаются к этапу 4, а в случае получения оптимального плана или установления неразрешимости процесс решения задачи завершают. Таблица 10.4 Базисные переменные … … … … … … … … 1 0 … … 0 … 0 … 0 1 … … 0 … 0 … … … … … … … … … … … … … … … 0 0 … … 0 … 1 … … … … … … … … … … … … … … … 0 0 … … 1 … 0 … 0 0 … … 0 … 0 … |