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

 

Содержание:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

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

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

Во второй главе рассматривается  решение двойственной задачи с помощью  программы MS Excel.

 

 

 

 

 

 

 

 

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

 

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

 

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

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

 

F=c₁x₁+c₂x₂+…c_nx_n

 

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

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

2. Матрица

 

 

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

 

 

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

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

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

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

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

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

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

 

Z=C₁x₁+C₂x₂+ … +C_nx_n

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

 

1.2 Основы теоремы двойственности

Пусть исходная ЗЛП имеет  вид 

(1)

(2)

(3)

причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

(4)

(5)

, , (6)

Задача (4)-(6) имеет предпочтительный план. Её начальный опорный план имеет вид 

Если некоторые из уравнений (2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема: Если в оптимальном  плане 

(7)

М-задачи (4)-(6) все искусственные  переменные , то план является оптимальным планом исходной задачи (1)-(3).

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

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

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

Теорема: Если в оптимальном  плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

Теорема: Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки неотрицательны, то такой план оптимален.

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

Теорема: Для любых  допустимых планов и прямой и двойственной ЗЛП справедливо неравенство , т.е.

(7) – основное неравенство теории  двойственности.

Теорема: (критерий оптимальности  Канторовича)

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

Теорема: (малая теорема  двойственности)

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

Теорема:

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

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

Теорема: (о дополняющей нежесткости )

Для того, чтобы планы  и пары двойственных задач были оптимальны, необходимо и достаточно выполнение условий:

(1)

(2)

Условия (1), (2) называются условиями дополняющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обращается в строгое неравенство, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство.

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

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

(3)

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

(54)

при условиях

(55)

(56)

где

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

В данном случае есть решение системы линейных уравнений (55). Однако это решение не является планом задачи (54) – (56), так как среди его компонент имеются отрицательные числа.

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

Определение:

Решение системы линейных уравнений (55), определяемое базисом , называется псевдопланом задачи (54) – (56), если для любого

Теорема:

Если в псевдоплане  , определяемом базисом , есть хотя бы одно отрицательное число такое, что все , то задача (54) – (56) вообще не имеет планов.

Теорема:

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

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

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

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

Пусть это минимальное значение принимается при , тогда в базис вводят вектор Р_r. Число является разрешающим элементов. Переход к новой симплекс–таблице производят по обычным правилам симплексного метода. Итерационный процесс продолжают до тех пор, пока в столбце вектора Р₀ не будет больше отрицательных чисел. При этом находят оптимальный план исходной задачи, а следовательно, и двойственной. Если на некотором шаге окажется, что в i–й строке симплекс–таблицы (табл. 15) в столбце вектора Р₀ стоит отрицательное число b_i, а среди остальных элементов этой строки нет отрицательных, то исходная задача не имеет решения.