Симплекс-метод решения задач линейного программирования

Симплекс-метод решения задач линейного программирования. Для упрощения процесса решения исходные данные задачи линейного программирования при решении ее симплекс методом записываются в специальные симплекс-таблицы. Поэтому одна из модификаций симплекс метода получила название табличный симплекс метод. Задача линейного программирования в каноническом виде: F=a0,1x1+a0,2x2+...a0,nxn+b0→ max a1,1x1+a1,2x2+...a1,nxn+ xn+1=b1 a2,1x1+a2,2x2+...a2,nxn+xn+2=b2 ....................................... am,1x1+am,2x2+...am,nxn+xn+m=bm Исходная таблица для задачи имеет следующий вид: Таблица 1 - Симплекс-таблица Базис b x1 x2 ... xn-1 xn xn+1 xn+2 ... xn+m F b1 b2 ... bm -b0 a1,1 a2,1 ... am,1 -a0,1 a1,2 a2,2 ... am,2 -a0,2 ... ... ... ... ... a1,n-1 a2,n-1 ... am,n-1 -a0,n-1 a1,n a2,n ... am,n -a0,n Оценочное выражение - x1, x2, xn - исходные переменные, xn+1, xn+2, xn+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам. Подготовительный этап Приводим задачу линейного программирования к каноническому виду F=a0,1x1+a0,2x2+...a0,nxn +b0 → max a1,1x1+a1,2x2+...a1,nxn+xn+1=b1 a2,1x1+a2,2x2+...a2,nxn+xn+2=b2 ....................................... am,1x1+am,2x2+...am,nxn+xn+m=bm В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений. Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче Таблица 2 – Симплекс-таблица, соответствующая исходной задаче Базис b x1 x2 ... xn-1 xn xn+1 xn+2 ... xn+m b1 b2 ... bm a1,1 a2,1 ... am,1 a1,2 a2,2 ... am,2 ... ... ... ... a1,n-1 a2,n-1 ... am,n- a1,n a2,n ... am,n Оценочное выражение - F b0 -a0,1 -a0,2 ... -a0,n - 1 -a0,n1 Шаг 1. Проверка на допустимость. Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных, то найдено допустимое решение (решение, соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы, то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам. Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет. Если после перерасчета в столбце свободных членов остались отрицательные элементы, то переходим к первому шагу, если таких нет, то ко второму. Шаг 2. Проверка на оптимальность. На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находящихся в строке F (не беря в расчет элемент b0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение. Если в строке F есть отрицательные элементы, то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b0) a0,l=min{a0,i } l - столбец в котором он находится, будет ведущим. Для того, чтобы найти ведущую строку, находим отношение соответствующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны. bk/ak,l =min {bi/ai,l } при ai,l>0, bi>0 k - cтрока, для которой это отношение минимально - ведущая. Элемент ak,l ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис. Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2 Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена алгоритм завершает работу. Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение. Правила преобразований симплексной таблицы. При составлении новой симплекс-таблицы в ней происходят следующие изменения:  Вместо базисной переменной xk записываем xl; вместо небазисной переменной xl записываем xk.  ведущий элемент заменяется на обратную величину ak,l'= 1/ak,l  все элементы ведущего столбца (кроме ak,l) умножаются на -1/ak,l  все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l  оставшиеся элементы симплекс-таблицы преобразуются по формуле ai,j'= ai,j- ai,lx ak,j/ ak,l Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой «прямоугольника». Рис. 7 – Правило «прямоугольника» Пример решения задачи линейного программирования симплекс-методом. Преобразуемый элемент ai,j и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника». Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 7x 1 + 5x2 при следующих условиях-ограничений. 2x1 + 3x2≤19 2x1 + x2≤13 3x2≤15 3x1≤18 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). 2x1 + 3x2 + 1x3 + 0x4 + 0x5 + 0x6 = 19 2x1 + 1x2 + 0x3 + 1x4 + 0x5 + 0x6 = 13 0x1 + 3x2 + 0x3 + 0x4 + 1x5 + 0x6 = 15 3x1 + 0x2 + 0x3 + 0x4 + 0x5 + 1x6 = 18 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид: 22 31 10 01 00 00  A = 0 3 0 0 1 0  3 0 0 0 0 1  Решим систему уравнений относительно базисных переменных: x3, x4, x5, x6, Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,19,13,15,18) Таблица 3 – I симплекс-таблица, соответствующая исходной задаче Базис B x1 x2 x3 x4 x5 x6 x3 19 2 3 1 x4 13 2 1 1 x5 15 3 1 x6 18 3 1 F(X0) -7 -5 Переходим к основному алгоритму симплекс-метода. Итерация №0. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: Следовательно, 4-ая строка является ведущей. Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки. Таблица 4 – I симплекс-таблица, соответствующая исходной задаче, содержащая оценочный столбец Базис B x1 x2 x3 x4 x5 x6 min x3 19 2 3 1 91/2 x4 13 2 1 1 61/2 x5 15 3 1 x6 18 1 3 6 F(X1) 0 -5 -7 Получаем новую симплекс-таблицу: Таблица 5 – II симплекс-таблица, соответствующая исходной задаче Базис B x1 x2 x3 x4 x5 x6 -2 x3 7 3 1 /3 -2 x4 1 1 1 /3 x5 15 3 1 1 x1 6 1 /3 F(X1) 42 -5 21/3 Итерация №1. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки. Таблица 6 – II симплекс-таблица, соответствующая исходной задаче, содержащая оценочный столбец Базис B x1 x2 x3 x4 x5 x6 min -2 x3 7 3 1 /3 21/3 -2 x4 1 1 /3 1 1 x5 15 0 3 1 5 1 x1 6 1 /3 F(X2) 42 0 21/3 0 -5 Получаем новую симплекс-таблицу: Базис x3 x2 x5 x1 F(X2) Таблица 7 – III симплекс-таблица, соответствующая исходной задаче B x1 x2 x3 x4 x5 x6 4 1 -3 11/3 -2 1 1 1 /3 12 -3 1 2 1 6 1 /3 47 5 -1 Итерация №2. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x6, так как это наибольший коэффициент по модулю. Вычислим значения Di по строкам как частное от деления: bi / ai6 и из них выберем наименьшее: Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (11/3) и находится на пересечении ведущего столбца и ведущей строки. Таблица 8 – III симплекс-таблица, соответствующая исходной задаче, содержащая оценочный столбец Базис B x1 x2 x3 x4 x5 x6 min 1 x3 4 1 -3 1 /3 3 -2 x2 1 1 1 /3 x5 12 0 -3 1 2 6 1 x1 6 1 /3 18 F(X3) 47 0 5 -1 Получаем новую симплекс-таблицу: Таблица 9 – IV симплекс-таблица, соответствующая исходной задаче B x1 x2 x3 x4 x5 x6 3 1 3 /4 -2 /4 0 1 1 3 1 /2 -1/2 1 1 6 -1 /2 1 /2 1 -1 5 1 /4 3/4 3 3 50 /4 2 /4 Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план Окончательный вариант симплекс-таблицы: Таблица 10 – Симплекс-таблица, соответствующая конечной итерации Базис B x1 x2 x3 x4 x5 x6 3 1 x6 3 /4 -2 /4 1 1 -1 x2 3 1 /2 /2 1 1 x5 6 -1 /2 1 /2 1 -1 3 x1 5 1 /4 /4 3 3 F(X4) 50 /4 2 /4 Оптимальный план можно записать так: x2 = 3 x1 = 5 F(X) = 5•3 + 7•5 = 50 Базис x6 x2 x5 x1 F(X3)