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

4

Введение

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

1. Л.В. Канторович первым отчетливо заявил, что нестрогие неравенства типичны для большинства практических задач и для их учета в математике нет общих эффективных методов. Он же предложил несколько приемов решения нового класса экстремальных задач.

2. После второй мировой войны независимо от Л.В. Канторовича задачи обнаружил (1947 год) американский математик Д. Данциг и предложил эффективный метод их решения, известный теперь как симплекс-метод. С начала 50-х годов новый раздел экстремальных задач стал называться линейным программированием и явился первым разделом современной теории экстремальных задач, которая отличается от классической теории экстремальных задач наличием в ней методов решения задач с нестрогими неравенствами и порождаемыми последними замкнутыми множествами.

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

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

3. Двойственный симплекс-метод.

4. Показать на примере решение задачи симплекс-методом.

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

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

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

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

1.1 Различные виды решения задач линейного программирования

,

∑ = с1х1+с2х2+с3х3+….→ max

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

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

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

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

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

Переменные:

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

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

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

.

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

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

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

(2)

(3)

(4)

2.2 Правила при составлении симплекс-таблицы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 Формирование матрицы.

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

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

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

Глава 3. Двойственный симплекс-метод

Использование идей двойственности в сочетании с общей идеей симплекс-метода позволило разработать еще один метод решения задач ЛП – двойственный симплекс-метод. Впервые этот метод был предложен Лемке в 1954г. Решение задачи ЛП двойственным симплекс-методом сводится к отысканию оптимального плана прямой задачи последовательным переходом от одного базиса к другому. Двойственный симплекс-метод, как и симплекс-метод, используется при нахождении решения задачи линейного программирования, записанной в форме основной задачи, для которой среди векторов , составленных из коэффициентов при неизвестных в системе уравнений, имеется m единичных. Двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами. В обычном симплексном алгоритме план всегда должен быть допустимым. Допустимый план — это такой план, который удовлетворяет всем ограничениям задачи при обязательном условии неотрицательности неизвестных, то есть любые числа в итоговом столбце положительны. План называется недопустимым (или условно-оптимальным), если в итоговом столбце имеются отрицательные числа, зато оценки целевой строки соответствуют целевой функции, то есть являются положительными при решении на максимум и отрицательными при решении на минимум. В процессе решения двойственным методом план является недопустимым. При использовании двойственного метода сначала применяют обычную симплекс-процедуру и добиваются того, чтобы все оценки соответствовали цели решения задачи, причем пока не обращают внимания на знаки чисел в итоговом столбце. Только когда такой условно-допустимый план достигнут, смотрят на эти знаки. Если в итоговом столбце оказались отрицательные числа, план изменяется так, чтобы недопустимость уменьшилась, а затем и исчезла, но чтобы двойственные оценки продолжали соответствовать при этом цели решения задачи. Возможность придавать в процессе решения отрицательные значения неизвестным, входящим в план, в случае, если ограничения заданы неравенствами, позволяет избавиться от искусственных неизвестных, это сокращает размеры задачи, а значит, и вычислений.

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

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

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

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

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

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

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

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

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

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

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

3.2 Правила составления двойственной задачи.

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

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

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

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

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

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

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

.

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

.

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

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

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

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

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

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

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

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

если , то .

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

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

3.4 Примеры решения задач.

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

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

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

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

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

,

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

,

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

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

.

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

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

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

СТ (0)                                РС

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

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

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

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

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

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

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

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

СТ(1)

СТ(2)

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

, , .

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

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

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

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

(1)

(2)

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

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

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

(3)

(4)

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

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

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

СТ(0)

СТ(1)

СТ(2)

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

, ,

Заключение.

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

Задачи проекта:

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

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

3.      Двойственный симплекс-метод 

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

При написании работы использовалась литература, указанная в библиографическом списке.

Библиографический список:

1. Зайченко Ю.П., Шумилова С.А. « Исследование операций».Учебное пособие.- 149 с.

2. А.Н. Карасев, Н.Ш. Кремер, Т.Н. Савельева «Математические методы в экономике»,Учебник.-М.2006. 245 с.

3. Лищенко «Линейное и нелинейное программирование», М. 2007. 312 с.

4. Орлов А.И. «Теория принятия решений». Учебное пособие. - М.: Издательство "Март", 2004. 110 с.