Линейное программирование. 3

Содержание

Введение ……………………………………………………………………………. 2

Глава 1. Линейное программирование ……………………………………….. 3

      1.1.Методы решения задач линейного программирования……………3

Глава 2. Двойственность в линейном программировании…………………. 9

      2.1.Понятие двойственности………………………………………………. 9

2.2.Двойственный симплекс-метод……………………………….12      Глава 3. Решение задачи линейноного программирования двойственным симплекс-методом………………………………………………………………... 13

3.1. Постановка задачи …………………………………………………… 13

3.2.Аналитическое решение задачи …………………………………….. 16

3.3.Результаты вычислений ……………………………………………... 18

Заключение ……………………………………………………………………….. 19

Список используемой литературы ……………………………………………. 20

Приложение (листинг программы)

Введение

Целью курсового проекта является изучить литературу по выбранной теме и научиться применять на практике симплекс – метод для решения прямой и двойственной задачи линейного программирования, а также решить двойственную задачу линейного программирования с помощью программы  LDPTechs

Курсовой проект состоит из введения, трех глав и заключения.

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

Во второй главе рассматривается основные понятия двойственности и двойственный симплекс-метод.

В третьей главе используется постановка задачи линейного программирования двойственным симплекс-методом,а так же программная реализация двойственного симплекс-метода.
1. Линейное программирование

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

Задача ЛП в стандартной форме с m ограничениями и n переменными имеет следующий вид:

W = c1 x1 + c2 x2 + ... + cn xn  min (max)

при ограничениях

a11 x1 + a12 x2 + ... + a1n xn = b1;

a21 x1 + a22 x2 + ... + a2n xn = b2;

...

am1 x1 + am2 x2 + ... + amn xn = bm;

x1  0; x2  0;...; xn  0;

b1  0; b2  0;...; bm  0.

В матричной форме

W = c x  min (max)

при ограничениях

A x = b; x  0; b  0,

где

A - матрица размерности mxn,

x - вектор-столбец переменных размерности nx1,

b - вектор-столбец ресурсов размерности mx1,

с - вектор-строка оценок задачи ЛП 1xn.

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

Преобразования неравенств

Ограничения в виде неравенств можно преобразовать в равенства при помощи введения так называемых остаточных или избыточных переменных.

Уравнение из примера 1

4 x1 + 1,5 x2  24

можно преобразовать в равенство при помощи остаточной переменной

4 x1 + 1,5 x2 + x3 = 24.

Переменная x3 неотрицательна и соответствует разности правой и левой частей неравенства.

Аналогично

x1  2

можно преобразовать путем введения избыточной переменной x4:

x1 - x4 = 2 .

Преобразование неограниченных по знаку переменных

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

x = x+ - x-; x+ 0; x-  0.

Продолжение примера 2.1. Оптимизация размещения побочного производства лесничества

Приведем к стандартной форме следующую задачу ЛП:

W = x1 - 2 x2 + 3 x3  max;

x1 + x2 + x3  8;

x1 - x2 + x3  9;

3 x1 - x2 - 2 x3 = -17;

x1  0; x2  0,

где x3 - переменная, неограниченная по знаку.

Последовательность действий следующая:

1.                  Умножим обе части равенства на -1, так как все элементы матрицы ресурсов должны быть неотрицательными.

2.Заменим x3 на x4-x5, где x4 и x5  0.

3.Введем дополнительные остаточную x6 и избыточную x7 переменные в два первых неравенства.

4.Припишем нулевые значения оценок задачи ЛП при переменных x6 и x7. Значение целевой функции при этом не изменится.

После преобразований имеем стандартную форму задачи ЛП:

W = x1 - 2 x2 + 3 x4 - 3 x5  max;

x1 + x2 + x4 - x5 + x6 = 8;

x1 - x2 + x4 - x5 - x7 = 9;

-3 x1 + x2 + 2 x4 - 2 x5 = 17;

x1  0; x2  0; x4  0; x5  0; x6  0; x7  0.

1.2. Методы решения задач линейного программирования

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

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

          Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа  2Х1  + 5Х2   ≤ 10,       то, очевидно,  0 ≤ Х1  ≤ 10/2 = 5 и 0 ≤ Х2  ≤ 10/2 = 5. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.

Проведем перебор точек параллелепипеда с шагом 1/10n  последовательно при  n=2,3,…, вычисляя значения целевой функции и проверяя наличие ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до 1/10n .)   

        Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ∆ ; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2 , ∆/4 и т.д.)

          Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для  решения практически любой задачи оптимизации. Он был предложен американцем Г. Данцигом в 1951 г. Симплекс-метод состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. Разберем пример со стр.208 книги [3].

Рассмотрим задачу линейного программирования, сформулированную выше при рассмотрении оптимизации номенклатуры и объемов выпуска:

F = 15 Х1 + 12 Х2 +14 Х3 → max .

Х1 / 200  + Х2  / 300 + Х3  / 120 ≤ 100 ,       

Х1 / 300  + Х2  / 100 + Х3  / 100 ≤ 100 ,       

Х3 / 80 ≤ 100 .                                           

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

В соответствии с симплекс-методом введем т.н. "свободные переменные" Х4 , Х5 , Х6 , соответствующие недоиспользованным мощностям, т.е. перейдем к системе уравнений:

Х1 / 200+ Х2 / 300 + Х3 /120+Х4 =100 ,

Х1 / 300 +Х2  / 100+ Х3 /100+Х5 =100 ,

Х3 / 80 + Х6 = 100 ,

15 Х1 + 12 Х2+14 Х3 = F .

У этой системы имеется очевидное решение, соответствующее вершине многогранника допустимых значений переменных:

Х1 = Х2 = Х3 = 0,  Х4 = Х5  = Х6 =100,  F= 0.

В терминах исходной задачи это значит, что ничего не надо выпускать. Такое решение приемлемо только на период летних отпусков.

Выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это Х1 .

Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при только что выбранной переменной Х1:

100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞ .

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

Умножим первую строку на 200, чтобы получить Х1  с единичным коэффициентом:

Х1 + 2/3 Х2  + 2/1,2 Х3 + 200 Х4 = 20000 .

Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, получим    

7/900 Х2  + 4/900 Х3 - 2/3  Х4 + Х5 = 100/3.

Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, в правой части которой стоит      F, получим:

2 Х2 -11 Х3 - 3000 Х4  = F - 300000.

В результате система уравнений преобразуется к виду, в котором переменная Х1   входит только в первое уравнение:

Х1 + 2/3 Х2 +2/1,2 Х3 + 200 Х4 = 20000 ,

7/900 Х2  + 4/900 Х3 - 2/3 Х4 +Х5=100/3,

Х3 / 80+Х6  = 100 ,

2 Х2 -11 Х3 - 3000 Х4  = F -300000.

Очевидно, у новой системы имеется улучшенное по сравнению с исходным решение, соответствующее вершине в шестимерном пространстве:

Х1 = 20000, Х2 = Х3 = Х4 = 0,  Х5 = 100/3, Х6 =100,  F= 300000.

В терминах исходной задачи это значит, что надо выпускать только кухни. Такое решение приемлемо, если допустимо выпускать только один вид продукции.

Повторим описанную выше операцию. В строке с F имеется еще один положительный коэффициент - при Х2  (если бы положительных коэффициентов было несколько - мы взяли бы максимальный из них). На основе коэффициентов при  Х2  (а не при   Х1, как в первый раз) образуем частные от деления соответствующих свободных членов на эти коэффициенты:

20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞.

Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при  Х2  равнялся 1). Затем добавим обновленную строку ко всем строкам, содержащим Х2  , предварительно умножив их на подходящие числа, т.е. такие, чтобы все коэффициенты при Х2  стали бы после сложения равны 0, за исключением коэффициента второй строки, который уже стал равняться 1. Получим систему уравнений:

Х1 +9/7 Х3 + 1800/7 Х4 - 600/7 Х5=120000/7 ,

Х2   + 4/7 Х3 - 600/7 Х4 + 900/7Х5 = 30000/7,

Х3 / 80+Х6  = 100 ,

- 85/7 Х3-19800/7 Х4 -1800/7 Х5 = F - 308571.

Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль F достигает своего максимального значения, равного 308571, при Х3  = Х4  = Х5  = 0. Из остальных уравнений следует, что при этом Х1  = 120000/7 = 17143, Х2  = 30000/7 = 4286, Х6  = 100. Поскольку в строке с F не осталось ни одного положительного  коэффициента при переменных, то алгоритм симплекс-метода закончил свою работу, оптимальное решение найдено.

Практические рекомендации таковы: надо выпустить 17143 кухни, вчетверо меньше, т.е. 4286 кофемолок, самоваров не выпускать вообще. При этом прибыль будет максимальной и равной 308571. Все производственное оборудование будет полностью загружено, за исключением линии по сборке самоваров.

2. Двойственность в линейном программировании

2.1 Понятие двойственности

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

Основная идея теории двойственности: для каждой задачи ЛП существует некоторая задача ЛП, решение которой тесно связано с прямой. Между решениями прямой и двойственной задач имеется ряд важных соотношений, полезных при исследовании общих свойств оптимального решения ЗЛП и проверке оптимальности допустимого решения.

Двойственная задача к ЗЛП в стандартной форме: рассмотрим ЗЛП (в стандартной форме)

A*X = B,

X ≥ 0

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

Каждому i–му (i = 1,m) ограничению поставим в соответствие переменное ui, положительное, отрицательное или нуль (называемое двойственным переменным), и рассмотрим ЗЛП.

max W = U*B

U* AT ≤ C, AT*U ≤ C

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

где U есть, так называемый, вектор–строка (u1, u2, …, um).

Линейная задача (Д) тесно связана с линейной задачей (П):

- матрица ограничений (Д) есть транспонированная матрица задачи (П);

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

Данная таблица соответствий между прямой и двойственной задачами позволяет  записать непосредственно двойственную задачу для любой линейной задачи.

Теорема двойственности. Если X и U - соответственно допустимые решения произвольных прямой и двойственной задач, то Z = C*X ≥ W = U*B.

Следствие из теоремы. Если X*, U* - соответственно решения прямой и двойственной задач, удовлетворяющих равенству C*X* = U*B, то планыX* и  U*– оптимальные решения прямой и двойственной задач соответственно.

Теорема. Пусть заданы прямая и двойственная задачи:

а) если прямая и двойственная задачи имеют решения, то каждая из этих задач имеет оптимальное решение и

Z* = min(П) = max(Д) = W*

б) если одна из них имеет неограниченный оптимум, то другая не имеет решения.

Теорема. Два решения (X и U) соответственно прямой и двойственной задач оптимальны тогда и только тогда, если выполняется условие:

(U* Aj - cj)*xj = 0; j = 1, n,  где Aj  –  j–й столбец матрицы A.

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

Метод работает с теми же симплексными таблицами, что и прямой  метод, но исследование начинается с двойственно-допустимого решенияи сначала определяется переменная, подлежащая выводу из базиса, а затем переменная, вводимая в базис [1,3].

            Вычислительная схема

            Начинаем с симплексной таблицы

            Шаг 1. Если , i=1,...,5 то решение

                        оптимальное.

            Шаг 2. Выбираем среди номеров i, для которых  < 0 , номер

К  с максимальным по модулю значением

Строка K объявляется ведущей.

            Шаг 3. Если в строке

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

прямая задача не имеет допустимых решений. Процесс решения завершается.

            Шаг 4. Выбираем среди отрицательных элементов строки

элемент с номером  S , для для которого выполняется равенство

Столбец S объявляется ведущим, а элемент   - ведущим элементом.

            Шаг 5. Проводим стандартное преобразование симплексной таблицы (шаг 5 из прямого симплекс-метода).

            Пример

Решить задачу ЛП двойственным симплекс-методом

Приводим задачу к каноническому виду

            Знаки в ограничениях изменили на противоположные для того, чтобы переменные

можно было взять в качестве базисных. Симплексная таблица имеет вид

            Таблица двойственно-допустимая, но не оптимальная. Выбираем ведущую строку - эта строка переменной

ведущий столбец - это столбец переменной После преобразования таблица принимает вид

            Так как в cтолбце есть отрицательная величина

 то эту строку выбираем ведущей, а столбец переменной будет ведущим столбцом. После преобразования получаем таблицу,

которая является оптимальной. Соответствующее оптимальное решение

имеет вид

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

3.1. Постановка задачи

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

при условиях

Где

и среди чисел имеются отрицательные.

Поскольку векторы – единичные, каждый из векторов можно представить в виде линейной комбинации данных векторов, причем коэффициентами разложения векторов по векторам служат числа

Таким образом, можно найти:

На основе исходных данных составляют симплекс-таблицу, в которой некоторые элементы столбца вектора являются отрицательными числами. Поэтому для определения оптимального плана задачи при условии, что он существует, следует произвести упорядоченный переход от одной симплекс–таблицы к другой до тех пор, пока из столбца вектора P0 не будут исключены отрицательные элементы. При этом все время должны оставаться неотрицательными все элементы (т +1)–й строки, т.е. для любого

Таким образом, после составления симплекс-таблицы проверяют, имеются ли в столбце вектора Po отрицательные числа. Если их нет, то найден оптимальный план исходной задачи. Если же они имеются (что мы и предполагаем), то выбирают наибольшее по абсолютной величине отрицательное число. В том случае, когда таких чисел несколько, берут какое–нибудь одно из них: пусть это число bl. Выбор этого числа определяет вектор, исключаемый из базиса, т. е. в данном случае из базиса выводится вектор Pl. Чтобы определить, какой вектор следует ввести в базис, находим

, где

Пусть это минимальное значение принимается при j=r, тогда в базис вводят вектор Рr. Число является разрешающим элементов. Переход к новой симплекс–таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р0 не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i–й строке симплекс–таблицы в столбце вектора Р0 стоит отрицательное число bi, а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.

Таким образом, отыскание решения задачи двойственным симплекс-методом включает следующие этапы:

1. Находят псевдоплан задачи.

2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.

3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р0 и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)–и строки к соответствующим отрицательным элементам разрешающей строки.

3.2.Аналитическое решение задачи.

Составим двойственную задачу. Такой является задача, в результате решения которой требуется найти минимальное значение функции

Строим симплекс таблицу:

Итерация 0:

Условие допустимости выполняется, так как в графе «Решение» все значения положительные, но не выполняется условие оптимальности, так как -строка содержит отрицательный коэффициент. Продолжаем наши действия

Итерация 1: