Введение
Линейное программирование наука о методах исследования и отыскания экстремальных значений линейной функции, на параметры которой наложены линейные ограничения.
Методы решения задач линейного программирования относятся к вычислительной математике. С ростом мощности компьютеров необходимость применения изощренных методов вычисления снижается, поскольку во многих случаях время счета перестает быть лимитирующим фактором, поскольку весьма мало (доли секунд). Можно выделить лишь три таких метода.
1. Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа 2Х1 + 5Х2 ≤ 10, то, очевидно, 0 ≤ Х1 ≤ 10/2 = 5 и 0 ≤ Х2 ≤ 10/2 = 5. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.
Проведем перебор точек параллелепипеда с шагом 1/10n последовательно при n=2,3,…, вычисляя значения целевой функции и проверяя наличие ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено!
2. Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)
3. Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Он был предложен американцем Г. Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум.
Такой многогранник ограничений можно назвать функцией, которая для задачи линейного программирования является целевой, а ограничения, записываемые в виде линейных уравнений или неравенств, называются системой ограничений.
Общей задачей для линейного программирования является нахождение неотрицательного решения системы линейных ограничений, которое оптимизирует линейную целевую функцию:
f(x1,x2,…,xn)=c1x1+c2x2+…+cnxn→ max (min)
Выделяют две формы задач линейного программирования:
1. стандартная форма
2. каноническая форма
Планом называется вектор x=(x1,x2,…,xn) Rn, удовлетворяющий условиям (1)-(3). Множество всех допустимых решений задачи будем обозначать через X .допустимое решение xX, при котором целевая функция достигает наибольшего (max) или наименьшего значения (min), называется оптимальным решением задачи линейного программирования. Базисное неотрицательное решение x=(x1,x2,…,xr,0,…,0) , где r- ранг системы ограничений, называется опорным решением.
1. Обыкновенные и модифицированные жордановы исключения
Для рассмотрения сути симплекс метода в задачах линейного программирования необходимо остановиться на понятии «обыкновенные и модифицированные жордановы исключения».
Пусть дана система из m линейных функций y1,…,ymот n неизвестных x1,x2,…,xn: yi=∑ aijxj(1.1), где aij– постоянные величины( i=1,m; j=1,n).
Представим систему (1.1) в форме таблицы 1.3, которую в дальнейшем будем называть жордановой.
Таблица 1.3
| x1 … xj … xs … xn | |
| y1=…yi=…yj=…ym= | a11 … a1j … a1s … a1n………………………………….ai1 … aij … ais … ain…………………………………ak1 … akj … aks … akn…………………………………am1 … amj … ams … amn |
Перейдём к обычной записи системы путём умножения элементов aiji-й строки на соответствующие неизвестные xj, стоящие в верхней заглавной строке, затем полученные произведения складываем и приравниваем к yi.
Выбираем из (1.1) k-е уравнение yk=∑akjxj(1.2), и, положим, коэффициент при xs отличен от нуля. Выразим xs:
xs=∑
Такая операция называется шагом жорданова исключения произведенным над табл.1.3 с разрешающим элементом aksс k-й разрешающей строкой и s-м разрешающим столбцом. Далее для выяснения как изменятся остальные элементы в табл. 1.3. подставляем значение xsиз в остальные равенства системы
Система запишется в виде
yi=∑ ( i=1,…,m)
Преобразованную систему переписываем в форме жордановой таблицы (табл. 1.4)
Таблица 1.4
| x1 … yк… xn | |
| y1=…xs =…ym= | b11 … … b1n……………………… … … ………………………bm1 … … bmn |
Сопоставляя табл. 1.3 и 1.4, необходимо обратить внимание, что шаг обыкновенного жорданова исключения с разрешающим элементом aksпереводит одну таблицу в другую по схеме из четырех правил:
1. разрешающий элемент (РЭ) заменяется обратной величиной;
2. остальные элементы разрешающей строки делятся на РЭ и меняют знаки;
3. остальные элементы разрешающего столбца делятся на РЭ;
4. прочие элементы вычисляются по формуле (1.5).
На практике удобно пользоваться правилом прямоугольника:
…………………….………
………aij ……… ais………
……………………………
…….. akj……… aks………
……………………………
Тогда из формулы непосредственно следует, что преобразованный элемент bij равен разности произведений элементов, расположенных на главной и побочной диагоналях, деленной на РЭ.
2. Идея симплекс метода
Симплекс-метод, называемый также методом улучшения плана, является одним из универсальных методов решения задач линейного программирования.
Если задача линейного программирования записана в каноническом виде
f=∑ ci xj (max)
∑ aij xj = ai0 (i=1,…,m)
xj>0 (j= 1,…,n)
Тогда, если оптимальный план задачи существует, то он совпадает по крайней мере с одним из опорных решений системы. Это опорное решение отыскивается симплекс-методом в процессе упорядоченного перебора только опорных решений системы.В связи с этим симплекс-метод и называют методом последовательного улучшения плана. Поиск начального опорного плана составляет первый этап симплекс-метода. На втором этапе среди опорных планов отыскивается оптимальный.
Рассмотрим суть симплекс-метода. Если в системе m<n и все m уравнений линейно независимы, иначе ранг системы равен m. Тогда система имеет бесконечное множество решений. Систему можно разрешить относительно m переменных, которым в матрице системы соответствуют линейно независимые векторы-столбцы. Обозначив эти переменные через x1,…,xm,выразим их через свободные переменные xm+1,…,xn
xi = bi0 -∑ bij xm+1 (i=1,..,m)
Подставив значения xi в целевую функцию, получаем:
f=b00- ∑ b0jxm+j
Значения базисных переменных xiи целевой функции f полностью определяются значениями свободных переменных xm+j.
Положим, что все bi0>0. Тогда план x0=(b10;…;bm0;0…;0), полученный при нулевых значениях свободных переменных xm+j, будет невырожденным опорным, а отвечающее ему значение функции f равно, как видно b00.
Опорный план x0 соответствует базису Б0={x1;…;xm}.Для получения другого опорного плана преобразовывают базис Б0 в новый базис Б1 , удаляя из Б0 одну переменную и вводявместо нее другую из группы свободных. При этом в базисе Б1 опорному плану x1 соответствует значение f(x1), не меньшееf(x0). Действуя таким образом, переходят к близкому к оптимальному плану. Ввиду того что опорных планов не более С ,через конечное число шагов либо приходят к оптимальному плану, либо устанавливают, что задача неразрешима.
линейное программирование симплекс задача
3. Построение начального опорного решения
Решение задач линейного программирования вручную наиболее рационально можно выполнять именно в табличной форме. В таблицу вписывают систему ограничительных уравнений и целевую функцию в виде выражений, разрешенных относите льно начального базиса Бо= {х1; ...; хт} (табл. 2.). Левый столбец занимают базисные переменные и целевая функция, а верхнюю строку — свободные переменные . Нижнюю строку, в которую вписаны коэффициенты целевой функции f, называют f- строкой или строкой целевой функции.. За столбцом базисных переменных следует столбец свободных членов. Иногда f-строку помещают сразу же за заглавной строкой, а столбец свободных членов в конце; таблицы. Таблицы описанного вида называются симплексными.
Таблица 2
| базисные переменные | 1 | свободные переменные-xm+1 … -xm+s… -xn |
| x1= … xk= … xm= | b10…bk0…bm0 | b11 … b1s … b1,n-m……………………………………bk1 … bks … bk,n-m……………………………………bm1 … bms … bm,n-m |
| f= | b00 | b01 …b0s…b0,n-m |
Используются и другие формы симплексных таблиц, но принятая нами форма является наиболее компактной и наглядной. В ней содержится вся необходимая информация о ходе решения задачи. Если, как предполагалось выше, все bi0>0, то при нулевых значениях верхних (свободных) переменных столбец свободных членов дает значения базисных переменных опорного плана xо= (b10;…;bm0;0; ... 0) и соответствующее значение b00 целевой функции: f(х0) = b00.