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

Государственное образовательное учреждение высшего

профессионального образования

«Московский государственный технический университет им. Н.Э.Баумана»

Калужский филиал

Реферат

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

2008

Цель работы: изучить и научиться применять на практикесимплекс — метод для решения прямой и двойственной задачи линейного программирования

Теоретическая часть.

Математическая постановка задачи линейного программирования.

Из практики рассмотрения задач математическогопрограммирования следует, что в общем виде решить их практически невозможно.Целесообразно рассматривать отдельные классы (виды) задач. Для каждого такогокласса удается сформулировать алгоритм решения, приемлемый только для данногокласса задач. Наиболее разработанными в математическом программированииявляются задачи линейного программирования (ЛП).

В задачах линейного программирования целевая функциялинейна, а условия-ограничения содержат линейные равенства и линейныенеравенства. Переменные могут быть подчинены или не подчинены требованию неотрицательности.Одна и та же задача линейного программирования может быть записана в различнойформе. Если все ограничения имеют вид неравенств, то задача записана встандартной форме. Если все ее ограничения, кроме

представляют собой равенства, то задача линейногопрограммирования записана в канонической форме.

Общий вид задачи линейного программирования

/>,/>

Ограничения:

1. Правые части всех ограничений должны бытьнеотрицательными />. Если какой-нибудь изкоэффициентов />< 0, то необходимо коэффициентыограничения слева и справа домножить на "-1" и изменить знак данногоограничения на противоположный;

2. Все ограничения должны быть представлены в виде равенств,поэтому при переходе от неравенства к равенству используют аппаратдополнительных переменных.

Если исходные ограничения определяют расход некоторогоресурса (знак "/>"), то переменные /> следуетинтерпретировать как остаток, или неиспользованную часть ресурса. В этом случае/>–остаточная переменная и вводится в уравнение со знаком "+".

Если исходные ограничения определяют избыток некоторогоресурса (знак "/>"), то вводится избыточнаяпеременная /> знаком"-".

Переменные:

Все переменные должны быть неотрицательными, т.е. />.

Если переменная не имеет ограничения в знаке, то её нужно представитькак разность двух неотрицательных переменных: />, где />. Такую подстановку следуетиспользовать во всех ограничениях, содержащих эту переменную, а также в выражениидля целевой функции.

Если такая переменная попадает в оптимальное решение, то

/>.

Целевая функция:

Подлежит максимизации или минимизации. />

Система ограничений в виде равенств и неравенств образуетвыпуклое множество — выпуклый многогранник. Это множество может бытьограниченным и неограниченным. Целевая функция задачи линейногопрограммирования также является выпуклой функцией. Таким образом, задачалинейного программирования является частным случаем задачи выпуклогопрограммирования.

Рассмотрим систему ограничений задачи линейногопрограммирования в виде равенств

/> (1)

Система (1) линейных уравнений совместна, если она имеет, покрайней мере, одно решение. Система (1) называется избыточной, если одно изуравнений можно выразить в виде линейной комбинации остальных.

В системе (1) число переменных (неизвестных /> nбольше, чем число ограничений m. Будем считать, чторанг этой системы равен m (система неизбыточна) и чтосистема (1) совместна. Тогда m переменных из общего ихчисла образуют базисные переменные, а остальные /> переменных называют небазисными.Если система уравнений имеет решение, то она имеет и базисное решение. Решениесистемы уравнений (1) называют допустимым, если все его компонентынеотрицательны. Если система линейных уравнений обладает допустимым решением,то она имеет и базисное допустимое решение. Совокупность всех допустимыхрешений системы (1) есть выпуклое множество, т.е. множество решений задачилинейного программирования выпукло. Так как это множество образованоплоскостями (гиперплоскостями), то оно имеет вид выпуклого многогранника. Базисноедопустимое решение соответствует крайней точке выпуклого многогранника (егограни или вершине). Если существует оптимальное решение задачи линейного программирования,то существует базисное оптимальное решение.

Целевая функция задачи линейного программирования естьуравнение плоскости (или гиперплоскости для числа переменных больше трех).Максимальное или минимальное значение целевая функция задачи линейногопрограммирования достигает либо в вершине выпуклого многогранника, либо наодной из его граней. Таким образом, решение (решения) задачи линейногопрограммирования лежит в вершинах выпуклого многогранника и для его нахождениянадо вычислить значения целевой функции в вершинах выпуклого многогранника,определяемого условиями-ограничениями задачи.

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

Трудность построения математической модели заключается видентификации переменных и последующем представлении цели и ограничений в видематематических функций этих переменных. Если модель содержит только двепеременные, то задачу линейного программирования можно решить графически. Вслучае трёх переменных графическое решение становится менее наглядным, а прибольшем значении переменных – даже невозможным. Однако графическое решениепозволяет сделать выводы, которые служат основой для разработки общего методарешения задачи линейного программирования.

Первый шаг при использовании графического метода заключаетсяв геометрическом представлении допустимых решений, т.е. построении областидопустимых решений (ОДР.), в которой одновременно удовлетворяются всеограничения модели. При получении графического решения переменная /> откладываетсяпо горизонтальной оси, а /> – по вертикальной. Приформировании ОДР необходимо предотвратить получение недопустимых решений,которые связаны с необходимостью выполнения условия неотрицательностипеременных. Перед построением необходимо определить квадранты, в которых будетрасполагаться ОДР. Квадранты определяются знаками переменных /> и />. Условиянеотрицательности переменных /> и /> ограничивают область ихдопустимых значений первым квадрантом. Если переменная /> не ограниченна в знаке, тообласть ограничивается первым и вторым квадрантом, если />, то – первым ичетвёртым квадрантом. Другие границы пространства решений на плоскости />, /> изображеныпрямыми линиями, построенными по уравнениям ограничений при условии заменызнака /> назнак "=". При этом необходимо учитывать следующее: правые части всехограничений должны быть неотрицательными />. Если какое-нибудь ограничение />< 0, тонеобходимо коэффициенты соответствующего ограничения слева и справа до-множитьна "-1" и изменить знак неравенства данного ограничения напротивоположный. Области, в которых выполняются соответствующие ограничения ввиде неравенств, указываются стрелками, направленными в сторону допустимыхзначений переменных.

В результате построений получается многоугольник, которыйопределяет пространство решений. Если одно из ограничений имеет знак"=", то ОДР вырождается в отрезок.

В каждой точке, принадлежащей области или границаммногоугольника решений, все ограничения выполняются, поэтому все решения,соответствующие этим точкам, являются допустимыми. Пространство решенийсодержит бесконечное число таких точек, несмотря на это, можно найтиоптимальное решение. Для этого необходимо построить в плоскости переменных />,/>градиент целевойфункции. Определение оптимальной точки зависит от той задачи, которуюнеобходимо решить.

Если в целевой функции определена задача максимизации, тооптимальная точка будет располагаться в направлении увеличения градиента, еслизадача минимизации – то в направлении уменьшения градиента целевой функции. Дляопределения оптимальной точки будем перемещать целевую функцию в направленииувеличения (уменьшения) градиента до тех пор, пока она не сместиться в областьнедопустимых решений.

После нахождения оптимальной точки пространства решенийопределяют её координаты />,/>и значение целевой функции /> в ней.Правильность выбора оптимальной точки можно проверить расчётом целевой функциив вершинах многогранника решений. В ЗЛП область допустимых решений всегдаявляется выпуклым множеством, т.е. таким множеством, что наряду с любыми двумяточками, принадлежащими этому множеству, этому же множеству принадлежит иотрезок, соединяющий эти две точки. Любая функция наискорейшим образомувеличивается в направлении своего градиента.

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

Прямая задача.

Рассмотрим задачу линейного программирования в каноническойформе:

Найти максимум (минимум) функции /> при условиях

Предполагается, что решение этой задачи существует. Чтобынайти оптимальное решение, надо найти допустимые базисные решения, а из нихвыбрать оптимальное базисное решение.

Симплекс – метод – это алгебраический метод решения задачлинейного программирования. В процессе вычислений производитьсяпоследовательный обход вершин многогранника решений (ОДР.) с проверкой в каждойвершине условий оптимальности. При этом каждый переход в смежную вершинусопровождается улучшением целевой функции.

Вычислительные процедуры симплекс — метода.

При графическом методе решения ЗЛП оптимальному решениюсоответствует всегда одна из угловых (экстремальных) точек пространстварешений. Это результат положен в основу построения симплекс-метода.Симплекс-метод не обладает наглядностью геометрического представленияпространства решений.

Симплекс-метод реализует упорядоченный процесс, при котором,начиная с некоторой исходной допустимой угловой точки, осуществляютсяпоследовательные переходы от одной допустимой экстремальной точки к другой,пока не будет найдена точка оптимального решения.

Обозначим: />– общее количество переменных вЗЛП, представленной в канонической форме; /> - количество исходных переменных;/> - количество ограничений, /> - количестводополнительных переменных, тогда />.

Каждая вершина многогранника решений имеет /> -ненулевых переменных и (/>) — нулевых переменных.

Ненулевые переменные называются базисными, нулевыепеременные – небазисными.

Дополним систему равенств равенством целевой функции, приэтом будем считать, что /> является /> базиснойпеременной, которая всегда присутствует в базисе для любой вершины.

Для получения решения составляется начальный допустимыйбазис, в котором базисные переменные должны быть представлены в виде единичныхорт. Это означает, что уравнения, представляющие данную вершину должны включатькаждую базисную переменную только в одной строке с коэффициентом, равным 1.

При выборе начального допустимого базиса для составлениясимплекс-табли-цы на первом шаге СТ(0) исходные /> переменные приравниваются к нулюи являются небазисными, среди введённых дополнительных переменных выбираютсяпеременные с коэффициентами равными единице. Переменные /> в равенствах (2) — (4)являются базисными и в /> - строку входят с коэффициентами,равными 0. Для заполнения симплекс-таблицы необходимо целевую функциюпреобразовать к виду />. Таким образом, окончательнополучаем:

/>(1)

/>(2)

/>(3)

/>(4)

При составлении симплекс-таблицы придерживаются следующихправил:

в крайнем левом столбце располагаются базисные переменные и />;

в крайнем правом столбце располагаются правые частиограничений;

в первой строке располагаются переменные в определённомпорядке:

сначала />, потом небазисные переменные,базисные переменные располагаются в последних /> столбцах передправой частью (ПЧ). Запишем коэффициенты в СТ(0):

ПЧ

-/>

Оптимальность любой из вершин определяется коэффициентамипри небазисных переменных в /> – строке текущей симплекс-таблицы:

Для задачи максимизации данная вершина является оптимальной,если все коэффициенты при небазисных переменных в /> – строке являютсянеотрицательными (>0);

Для задачи минимизации данная вершина является оптимальной,если все коэффициенты при небазисных переменных в />– строке являются неположительными(< 0).

Если в задаче максимизации (минимизации) у одной небазиснойпеременной в /> – строке коэффициент<0(>0), то текущая точка не является оптимальной и необходимо изменитьбазис. Для этого выбирают небазисную переменную, имеющую максимально отрицательный(положительный) коэффициент в /> – строке. Выбранная небазиснаяпеременная будет включаться в новый базис, поэтому называется включаемойпеременной. Базисная переменная, которая будет выведена из базиса, называетсяисключаемой переменной.

Исключаемой переменой будет та базисная переменная, котораяпервой обратится в «0» при переходе в смежную вершину после вводавключаемой переменной.

Столбец включаемой переменной будем называть разрешающимстолцом.

Строку исключаемой переменной будем называть разрешающейстрокой.

Пересечение разрешающего столбца и строки определяютразрешающий элемент (РЭ).

Чтобы определить исключаемую переменную необходимо:

разделить правые части всех базисных переменных (кроме /> - строки) насоответствующие положительные коэффициенты разрешающего столбца;

выбрать из полученных отношений наименьшее.

Делить на «0» и отрицательную величину нельзя, т.к. это приводит к отсутствию пересекающейся вершины или к вершине вне ОДР.

Для перехода в смежную вершину необходимо сформироватьматрицу перехода B(0), которая определит связь междуСТ(0) и СТ(1): СТ(1) = В(0) СТ(0).

Для произвольной квадратной матрице размерности n, имеющей в качестве (n — 1) столбцаединичные орты, расположенные в соответствии с единичными ортами единичнойматрицы, и одного произвольного столбца с ненулевым элементом на главной диагонали,обратная матрица находится по следующему правилу:

Каждый элемент j – столбца делитсяна РЭ и меняет знак на противоположный, кроме разрешающего элемента.

Искусственный начальный базис. М – метод.

Если исходное ограничение записано в виде равенства"=" или имеет знак "/>", то нельзя сразу получитьдопустимое начальное базисное решение, т. к. при записи задачи в стандартнойформе, после введения дополнительных переменных может получиться вариант, когдаполученные уравнения не позволяют сформировать начальный допустимый базис ввиде единичных орт.

В этом случае для нахождения начального допустимого базисавводятся дополнительно искусственные переменные />. Искусственные переменные неимеют отношения к содержанию поставленной задачи, их введение допустимо тольков том случае, если соответствующая схема вычислений будет обеспечиватьполучение оптимального решения, в котором все искусственные переменные окажутсяравными нулю.

Переменные R определяют начальныйдопустимый базис с точки зрения возможного дальнейшего перехода в одну извершин ОДР. За использование искусственных переменных в целевой функциивводится штраф М. В задаче максимизации М отрицательное (М<<0), в задачеминимизации М положительное (М>>0).

/>/>

Свойство М: При сложении (вычитании) с любой конечнойвеличиной />,определяющей любое значение, которое может принимать каждая из переменныхисходной ЗЛП, её значение (переменной М) не меняется, а именно,

/> />

При составлении начальной симплекс-таблицы все переменныеначального допустимого базиса (дополнительные и искусственные) должнырасполагаться в последних m столбцах перед правойчастью.

Алгоритм получения оптимального решения:

1. Переход от неравенств к равенствам с учётом правилперехода — введение остаточных, избыточных, искусственных переменных икоэффициентов штрафа;

2. Определение числа базисных и небазисных переменных;

3. Получение /> - строки для заполнения СТ(0. Дляэтого необходимо целевую функцию преобразовать к виду />; для чего из соответствующихравенств ограничений выразить искусственные переменные /> и подставить в /> строку и привести крациональному виду;

4. Заполнение СТ(0). Перенесение коэффициентов /> - строки иравенств ограничений в соответствующие строки и столбцы симплекс-таблицы;

5. Исследование /> функции на условие оптимальности:

определение разрешающего столбца (по знаку и величинекоэффициентов небазисных переменных /> - строки);

определение включаемой переменной из небазисных переменных;

6. Определение разрешающей строки по условию допустимости:

определение минимального отношения при делении правых частейограничений на положительные коэффициенты разрешающего столбца;

определение исключаемой переменной из начального базиса;

7. Определение разрешающего элемента РЭ;

8. Получение B (0). Замена в матриценачального базиса коэффициентов исключаемой переменной на коэффициентывключаемой переменной; вычисление B (0) по соответствующемуправилу;

9. Определение элементов СТ(1) = В(0) СТ(0);

10. Исследование />-строки СТ(1) на условиеоптимальности.

Если условие не выполнено, то вычисления продолжаются инеобходимо повторить пункты 5-10.

Если условие оптимальности выполнено, то решение ЗЛПсимплекс-методом закончено, необходимо выделить оптимальные значения переменныхи оптимальное значение целевой функции.

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

Двойственная задача.

Двойственная задача (ДЗ) – это вспомогательная задачалинейного программирования, формулируемая с помощью определённых правилнепосредственно из условий прямой задачи. Заинтересованность в определенииоптимального решения прямой задачи путём решения двойственной к ней задачиобусловлена тем, что вычисления при решении ДЗ могут оказаться менее сложными,чем при ПЗ. Трудоёмкость вычислений при решении ЗЛП в большей степени зависитот числа ограничений, а не от количества переменных. Для перехода к ДЗнеобходимо, чтобы прямая задача была записана в стандартной канонической форме.При представлении ПЗ в стандартной форме в состав переменных /> включаютсятакже избыточные и остаточные переменные.

Двойственная задача имеет:

m переменных, соответствующих числуограничений прямой задачи;

n ограничений, соответствующих числупеременных прямой задачи.

Двойственная задача получается путём симметричногоструктурного преобразования условий прямой задачи по следующим правилам:

Каждому ограничению /> ПЗ соответствует переменная /> ДЗ;

Каждой переменной /> ПЗ соответствует ограничение /> ДЗ;

Коэффициенты при /> в ограничениях ПЗ становятсякоэффициентами левой части соответствующего ограничения ДЗ;

Коэффициенты /> при /> в целевой функции ПЗ становятсяпостоянными правой части ограничения ДЗ;

Постоянные ограничений /> ПЗ становятся коэффициентамицелевой функции ДЗ.

Рассмотрим правила составления двойственной задачи:

Прямая задачаДвойственная задача

Остановимся более подробно на определении областейдопустимых решений двойственных переменных при переходе от прямой задачи кдвойственной.

Области допустимых решений для двойственных переменных

Вид ограничений прямой задачи, а также дополнительные иискусственные переменные, образующие начальный допустимый базис, определяют ОДРдля соответствующих двойственных переменных.

1. Рассмотрим ограничение (2) прямой задачи:

/>Область допустимых решений ДП (/>) определяетсязнаками ограничений (8) и (9) двойственной задачи и знаком ограничения (2)прямой задачи. Для определения ОДР /> найдём ограничения ДЗ,соответствующие остаточным переменным ПЗ. Коэффициенты целевой функции дляостаточных переменных равны нулю (/>).Т. о., при решении задачи максимизацииограничениям прямой задачи, имеющим знак ограничения />, соответствуют неотрицательныедвойственные переменные: />.

2. Рассмотрим ограничение (3) прямой задачи:

/>.

При введении искусственных переменных в целевую функциювводятся коэффициенты штрафа М, поэтому для задачи максимизации получим:

/>.

Т. о., при решении задачи максимизации ограничениям прямойзадачи, имеющим знак равенства, соответствуют двойственные переменные, неограниченные в знаке />.

3. Рассмотрим ограничение (4) прямой задачи:

В целевой функции избыточные переменные имеют коэффициенты,равные нулю (/>), а искусственные переменныекоэффициенты, равные величине штрафа со своим знаком, в результате для задачимаксимизации получим:

Т. о., при решении задачи максимизации ограничениям прямойзадачи, имеющим знак />, соответствуют неположительныедвойственные переменные />.

4. Если в прямой задаче есть переменная, неограниченная взнаке, то в двойственной задаче получатся два ограничения, имеющие одинаковыекоэффициенты при двойственных переменных, но разные знаки ограничений. Дляудобства решения эти ограничения сворачивают в одно со знаком равенства (темсамым число ограничений двойственной задачи сводится к числу исходныхпеременных прямой задачи).

По аналогии можно записать условия двойственной задачи прирешении задачи минимизации. Для удобства пользования некоторые соотношения припереходе от прямой задаче к двойственной приведены в таблице.

Прямая задача Двойственная задача Целевая функция Ограничения Целевая функция Ограничения Переменные Максимизация

Минимизация

Максимизация

В двойственной задаче переменные могут быть неотрицательными(/>), не ограниченнымив знаке (/>),неположительными (/>). При решении ДЗ, как и ПЗ должнывыполняться условия неотрицательности ограничений и переменных. Для представлениядвойственной задачи в стандартной форме используются следующие подстановки:

если переменная /> не ограничена в знаке, то />;

если />, то />.

Такие подстановки следует использовать во всех ограничениях,содержащих эти переменные, а также в выражении для целевой функции.

После приведения ДЗ к стандартному виду используетсясимплекс — метод. Алгоритм получения решения тот же, что и для прямой задачи.

II. Практическая часть

1. Решение задачи линейного программирования графическимметодом.

Дана следующая задача линейного программирования (ЗЛП).

/>, />

1.1. Все ограничения задачи />.

1.2. Переменная /> ограниченна в знаке, поэтому />. Переменная /> не ограниченав знаке, поэтому вводим замену />, где />.

Область допустимых решений будет ограничиваться I и IV квадрантом.

1.3. Построение ограничений и градиента целевой функции />:

1.4. Область допустимых решений – отрезок AB.

1.5. Точка А – оптимальная. Координаты т. А:

/>/>; />; />.

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

Прямая задача.

Задачу линейного программирования для любой вершины вкомпактной форме можно представить в виде: />/>/>

Для получения используем алгоритм, приведённый втеоретической части.

1. Переход от неравенств к равенствам по правилам введениядополнительных переменных. Исходную задачу необходимо привести к стандартнойформе: введем замену по переменной />,/>и дополнительные переменные: />

/>, />

Полученный вид ЗЛП не позволяет сформировать начальныйдопустимый базис, т. к. нельзя выделить единичные орты во втором и третьемравенствах. Для получения начального допустимого базиса введём искусственныепеременные. В результате получим: />

/>, />

2. Общее число переменных определим по формуле: />=3+2+2=7, где /> - числоискусственных переменных. Число базисных переменных определяется числомограничений, т. к. />, то система имеет три базисныепеременные /> и/> небазисныепеременные />.

3. Получение/> — строки для СТ (0). Приведёмцелевую функцию к виду

/>.

Получим из (2): />, из (3): />

4. Формирование симплекс – таблицы на первом шаге:

/>/>Начальныйбазис

/>СТ(0) РС

ПЧ

1 -1-4M 3+3M -3M-3 M -12M

1 2 -2 1 4

3 -4 4 1 12

1 1 -1 -1 1

5. Определение разрешающего столбца.

При решении задачи максимизации выбираем в /> - строке максимальноотрицательный коэффициент: /> - включаемая переменная.

6. Определение разрешающей строки: /> – исключаемая переменная.

7. Разрешающий элемент РЭ = 1.

8. Получение матрицы перехода

/>, где В(0) — матрицаперехода

9. Определение элементов таблицы СТ(1) = В(0) СТ(0);

10. Исследование z-строки СТ(1) наусловие оптимальности:

/>СТ(1)

ПЧ z 1 4+7M -7M-4 -3M-1 1+4M -12M

1 -1 1 1 -1 4

-7 7 3 1 -3 12

1 1 -1 -1 1

СТ(2)

ПЧ z 1 5/7 M+4/7 M-5/7 48/7

10/7 1 1/7 -10/7 40/7

-1 1 3/7 1/7 -3/7 12/7

1 -4/7 1/7 4/7 12/7

/>/>

СТ(2) – оптимальная, т. к. коэффициенты при НБП/>.

/>, />, />.

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

Двойственная задача.

Составим двойственную задачу по условиям прямой задачи иопределим области допустимых решений ДП:

Прямая задачаДвойственная задача

/>(1)

/>(2)

Итак, получено: />, />, />.

2. Приведём запись двойственной задачи к канонической форме.На основании полученных ОДР двойственных переменных введём необходимыеподстановки: />.

Для удобства решения свернём ограничения (1) и (2) в одно сознаком равенства, а также введем в ограничения и целевую функцию избыточные,остаточные и искусственные переменные.

/> (3)

/>(4)

3. Решим ДЗ симплекс методом:

Из (3): выразим/>

Из (4) выразим: />

/>СТ(0)

ПЧ W 1 -4-M 7M-12 12-7M -M 4M

1 3 -3 -1 -1 1 1

-2 4 -4 1 1 3

СТ(1)

ПЧ W 1 -10/3M 7/3M-4 4/3M-4 -7/3M+4 5/3M+4

1/3 1 -1 -1/3 -1/3 1/3 1/3