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

 

 

 

 

ВВЕДЕНИЕ

 

 

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. В середине XX века был создан специальный математический аппарат, помогающий эффективно распределять эти ресурсы. Соответствующий раздел математики называется математическим программированием. Слово “программирование" здесь и в аналогичных терминах (“линейное программирование, динамическое программирование” и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово “планирование”. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу. И вот для решения таких задач стали использовать разные виды оптимизации. Оптимизация - это выбор наилучшего варианта из множества возможных. Если критерий выбора известен и вариантов немного, то решение может быть найдено путем перебора и сравнения всех вариантов. Однако часто бывает так, что число возможных вариантов настолько велико, что полный перебор практически невозможен. В таких случаях приходится формулировать задачу на языке математики и применять специальные методы поиска оптимального решения, т.е. методы оптимизации. Все задачи оптимизации делятся на два больших класса:

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

— задачи оптимального управления.

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

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

Основной целью задачи дискретной оптимизации – является нахождение лучшего решения из конечного, но достаточно большого их числа.

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

Исходя из цели, сформируем следующие задачи:

— ознакомиться с теоретическим описанием двойственности в оптимизационных задачах;

— решить вручную задачу одним из методов оптимизации;

— реализовать алгоритм метода на любом языке программирования.

 

 

 

 

 

 

1 ТЕОРЕТИЧЕСКОЕ ОПИСАНИЕ ДВОЙСТВЕННОСТИ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

 

 

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

 

С экономической точки зрения двойственную задачу можно интерпретировать так: какова должна быть цена единицы каждого из ресурсов, чтобы при заданных количествах ресурсов bi и величинах стоимости единицы продукции Cj минимизировать общую стоимость затрат? А исходную задачу определим следующим, образом: сколько и какой продукции xj(j =1,2,…, n) необходимо произвести, чтобы при заданных стоимостях Cj (j=1,2,…, n) единицы продукции и размерах имеющихся ресурсов bi(i=1,2,…, n) максимизировать выпуск продукции в стоимостном выражении. Большинство задач линейного программирования изначально определяются как исходные или двойственные задачи. Сделав вывод можно говорить о паре двойственных задач линейного программирования.

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

 

                                                    F=c1x1+c2x2+…cnxn                                         (1.1)

 

При условиях

 

 

 

Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи задается на максимум, а целевая функция двойственной на минимум.

2. Матрица

 

A=

 

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

 

AT=

 

в двойственной задаче получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов – строками).

3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи – числу переменных в исходной задаче.

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

5. Если переменная xj исходной задачи может принимать только лишь положительные значения, то j-е условие в системе двойственной задачи является неравенством вида «>». Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i – соотношение в системе исходной задачи является неравенством, то i-я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

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

Двойственная задача тесно связана задачей линейного программирования. Задача первоначальная называется исходной. Решение двойственной задачи может быть получено из решения исходной и наоборот. Связующим фактом этих двух задач являются коэффициенты Cj функции исходной задачи. Данные коэффициенты называются свободными членами системы ограничений двойственной задачи. Коэффициенты Bi системы ограничений исходной задачи называются коэффициентами двойственной задачи. Транспонированная матрица коэффициентов системы ограничений исходной задачи является матрицей коэффициентов системы ограничений двойственной задачи.

Рассмотрим задачу использования ресурсов. У предприятия есть t видов ресурсов в количестве bi (i=1, 2,…, m) единиц, из которых выпускается n видов продукции. На изготовление 1 ед. i-й продукции тратится aij ед. t-гo ресурса, ее стоимость составляет Cj ед. Необходимо определить план выпуска продукции, обеспечивающий ее максимальный выпуск в стоимостном выражении. Примем за xj (j=1,2,…, n) количество ед. j-й продукций и составляет максимальное значение линейной функции

 

                                            Z=C1x1+C2x2+ … +Cnxn                                          (1.2)

 

Определим ресурсы, которые потребуются для изготовления товара. Обозначим за единицу стоимости ресурсов единицу стоимости выпускаемого товара. А через уi (j=1,2,…, m) стоимость единицы i-го ресурса. Т.е. стоимость всех затраченных ресурсов, которые используются для изобретения единицы j-й продукции, составляет. Цена израсходованных ресурсов не должна превышать цены окончательного товара.

 

Задача линейного программирования.

 

Важную роль в линейном программировании имеет понятие двойственности. Рассмотрим две задачи линейного программирования:

 

                                    max{F(x) = CT x| Ax≤B, xi≥0, i =1,n}                             (1.3)

 

и

 

                                  min{F(y) = BT y| AT y≥C, yj ≥0, j = 1,m}                          (1.4)

 

Задачу (1.3) называют прямой, а связанную с ней задачу (1.4) – двойственной. Вместе они образуют симметрическую пару двойственных задач. Число переменных двойственной задачи равно количеству ограничений прямой. Кроме того, при переходе от прямой задачи к двойственной вектора B и C меняют местами, матрица A коэффициентов системы ограничений прямой задачи транспонируется, а знак неравенств в ограничениях меняют на противоположный. Смысл экстремума F(x) противоположен смыслу экстремума F(y) . Связь между задачами (1.3) и (1.4) взаимна, т.е. если прямой считать задачу (1.4), то в качестве двойственной ей будет соответствовать задача (1.3). Возможность перехода от прямой задачи к двойственной (и наоборот) устанавливается теоремой двойственности: если одна из задач (1.3) или (1.4) имеет оптимальное решение, то и другая также имеет оптимальное решение, причем оптимальные значения функции цели прямой и двойственной задач совпадают, т.е.

 

                                                   max F(x) = min F( y)                                        (1.5)

 

При этом выполняются следующие правила:

1. Если на переменную xi прямой задачи наложено условие неотрицательности, то i-е условие системы ограничений двойственной задачи является неравенством и наоборот.

2. Если на переменную xi прямой задачи не наложено условие неотрицательности, то i-е ограничение двойственной задачи записывается в виде строгого равенства.

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

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

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

Пусть предприятие располагает ресурсами b1,b2,...,bm, которые могут использоваться для выпуска n видов продукции. Известны нормы потребления j-го ресурса на производство единицы i-й продукции – aij , а также прибыль от реализации единицы i-го вида продукции ci (i = 1, n; j = 1,m) . Найти объем производства продукции каждого вида x*i, максимизирующий суммарную прибыль предприятия F(x) = ∑cixi , при этом расход ресурсов не должен превышать их наличия. Математическая модель задачи имеет вид

 

                                max{F(x)=∑cixi|∑ajixi≤bj, j=1,m; xi≥0, i=1,n}                    (1.6)

 

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

Рассмотрим задачу:

 

                                     max{F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0}                         (1.7)

 

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

а) насколько можно увеличить запас некоторого ресурса, чтобы улучшить оптимальное значение F;

б) насколько можно сократить запас некоторого ресурса, чтобы сохранить при этом оптимальное значение F;

в) увеличение объёма какого из ресурсов наиболее выгодно;

г) какому из ресурсов отдать предпочтение при вложении дополнительных средств;

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

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

Сформулируем задачу, двойственную к рассматриваемой задаче рационального использования ресурсов. Пусть некоторая организация может закупить все ресурсы bj, которыми располагает предприятие. Необходимо определить оптимальные цены y*j ( j = 1,m) на единицу этих ресурсов при условии, что покупатель стремиться минимизировать общую оценку ресурсов. При этом общая ценность ресурсов должна быть не меньше прибыли, которую может получить предприятие при организации собственного производства. Математическая модель задачи имеет вид