Симплекс-метод

Симплекс-метод Симплексный метод основывается на следующем:  область допустимых решений задачи линейного программирования явля- ется выпуклым множеством с конечным числом угловых точек, т.е. многогранником или многоугольным множеством;  оптимальным решением задачи линейного программирования является од- на из угловых точек области допустимых решений;  угловые точки области допустимых решений алгебраически представляют некоторые базисные (опорные) решения системы ограничений задачи. Данный метод состоит в целенаправленном переборе опорных решений задачи линейного программирования. Он позволяет за конечное число шагов расчета либо найти оптимальное решение, либо установить его отсутствие. Основное содержание симплексного метода: 1) найти начальное опорное решение; 2) осуществить переход от одного опорного решения к другому, на ко тором значение целевой функции ближе к оптимальному; 3) определить критерии завершения процесса решения задачи, позволяющие своевременно прекратить перебор решений на оптимальном решении или сделать заключение об отсутствии решения. Рассмотрим задачу, для которой можно найти опорное решение (план). Нахождение первого опорного плана. I. Пусть задана ЗЛП: Z X c1 x1 c2 x2 max , ... cn xn a11 x1 a12 x2 ... a1n xn b1 , a21 x1 a22 x2 ... a2 n xn b2 ,        am1 x1 xj am 2 x2 ... amn xn bm . 0 , j 1, n . Приведѐм задачу к каноническому виду: 1 Z X c1 x1 c2 x2 ... cn xn 0 xn a11 x1 a12 x2 ... a1n xn xn a21 x1 a22 x2 ... a2 n xn xn 1 0 xn 2 max , ... 0 xn m имеет следующий b1 , 1 b2 , 2        am1 x1 a m 2 x2 ... amn xn xn bm . m 0 , j 1, n m . xj Векторная n m Z X форма данной задачи вид: max при условии cjxj j 1 x1 A1 x2 A2 ... xn An j 1, n m , где An 2 1 , An  m Так как b1 An на X xn 1 An a11 a21 ,  am1 A1 , A0  1 1 b2 An ... xn 1 A2 m An m A0 , x j a12 a22 , …,  am 2 An 0, a1n a2 n ,  amn An 1 1 ,  b1 b2 .  bm 2 ... bm An m A0 , то по определению опорного пла- 0,0,...,0, b1 , b2 ,..., bm - опорный план данной задачи. Этот план определяет- ся системой единичных векторов An 1 ,..., An m, которые образуют базис m – мер- ного пространства. II. Исследование опорного плана на оптимальность. Исследование опорного плана на оптимальность, а также дальнейший вычислительный процесс удобнее вести, если условия задачи и первоначальные данные, полученные после определения исходного опорного плана, записать в виде специальной симплекс – таблицы. Таблица содержит m n 3 столбцов и m 1 строк. 2 ХБ СБ В с1 с2 сn план A1 A2 An An … … An 1 m xn 1 b1 a11 a12 a1n 1 xn 2 b2 a 21 a 22 a 2n … … … … … … bm a m1 a m2 a mn 1 n 1 n m … … xn m 2 1 n индексная строка CБ Вплан , CБ А j c j . j Теорема (признак оптимальности опорного плана): Опорный план является оптимальным, если для любого j j j 1, n m 0. Терема: Если в индексной строке симплекс-таблицы содержится отрицательный элемент k, а среди чисел a ik нет положительных, то целевая функция неограни- ченна на множестве планов. Определение опорного (или оптимального) решения из симплекс-таблицы. Решение выписывают из столбцов Х Б и В – план. В Х Б записаны переменные не равные 0, в В-план – чему они равны, III. Z . Другие переменные равны 0. Переход к новому опорному плану. Переход от одного опорного плана к другому осуществляется исключением из исходного базиса какого-нибудь из векторов и введением нового вектора. В качества вектора вводимого в базис можно взять любой из векторов A j , для которого j 0 . Однако, для того, чтобы решение X (оптимальное) было найдено быстрее, рекомендуется выбирать A j таким, чтобы больший модуль из всех j j 0 имело наи- 0. 3 Алгоритм перехода к новому опорному решению состоит в следующем: Выбирают разрешающий элемент a qp . Для этого: I. a. Выбирают вектор A p , имеющий наименьшее отрицательное значение в индексной строке; столбец A p - разрешающий. b. Выбирают вектор, выводимый из базиса. Для этого находят отношение элементов столбца В-план к соответствующим положительным элементам разрешающего столбца. Из полученных соотношений выбирают наименьшее, соответствующая строка q называется разрешающей. c. На пересечении разрешающего столбца и строки находится разрешающий элемент a qp . Его обводят в рамку. С выбранным разрешающим элементом выполняют преобразования II. симплекс – таблицы. Получаем следующую таблицу и новое опорное решение: a. Из базиса вывести переменную, стоящую в столбце Х Б в q-ой строке; вместо неѐ в базис ввести переменную x p ; b. В новую таблицу на место разрешающего элемента записать 1; c. Другие элементы разрешающей строки разделить на разрешающий элемент; d. Другие элементы разрешающего столбца обнулить; e. Другие элементы таблицы пересчитать по правилу прямоугольника (метод Жордана-Гаусса); f. CБ Вплан ; g. Коэффициенты при Х Б записываем в целевую функцию. 4