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

Структура и свойства двойственной задачи

Любую задачу максимизации ЛП с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b 1 ,b 2 ,…,b m между различными потребителями, например, между некоторыми технологическими процессами, которые представляются столбцамиA 1 ,A 2 ,…A n матрицы ограничений задачи. Любое допустимое решение задачи ЛПx 1 ,x 2 ,…x n дает конкретное распределение, указывающее ту долю каждого из ресурсов, которая должна быть использована при осуществлении соответствующего технологического процесса.

Рассмотрим пример. Завод производит три вида продукции x 1 ,x 2 иx 3 , каждый из которых требует затрат времени на обработку на токарном, фрезерном и сверлильном станках. Количество машинного времени для каждого из станков ограничено. Пустьc 1 ,c 2 ,c 3 – прибыль от реализации единицы соответствующего вида продукции. Необходимо определить, какое количество каждого вида продукции необходимо производить в течение недели, чтобы получить максимальную прибыль.

Формально эта задача записывается так:

максимизировать (c 1 x 1 +c 2 x 2 +c 3 x 3) (1)

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

a 11 x 1 + a 12 x 2 + a 13 x 3 ≤ b 1 ;

a 21 x 1 + a 22 x 2 + a 23 x 3 ≤ b 2 ;

a 31 x 1 +a 32 x 2 +a 33 x 3 ≤b 3 , (2)

где a 1 j ,a 2 j ,a 3 j – время, необходимое для обработки единицыj-го вида продукции соответственно на токарном, фрезерном и сверлильном станках (j= 1, 2, 3);b 1 ,b 2 ,b 3 – недельный ресурс машинного времени соответственно для токарного, фрезерного и сверлильного станков.

Обозначим y 1 ,y 2 иy 3 –цену единицы времени работы на токарном, фрезерном и сверлильном станках. Тогдаa 11 y 1 +a 21 y 2 +a 31 y 3 – можно трактовать как расходы на изготовление единицы продукции первого вида;a 12 y 1 +a 22 y 2 +a 32 y 3 – расходы на изготовление единицы продукта второго вида и т. д.

Предположим, что цены ресурсов y 1 ,y 2 ,…,y m выбраны так, что выполняются следующие соотношения:

a 11 y 1 + a 21 y 2 + a 31 y 3 ≥ с 1 ;

a 12 y 1 + a 22 y 2 + a 32 y 3 ≥ с 2 ;

a 13 y 1 +a 23 y 2 +a 33 y 3 ≥ с 3 . (3)

Поскольку b 1 ,b 2 иb 3 – использованный ресурс машинного времени для каждого из станков, тоb 1 y 1 +b 2 y 2 +b 3 y 3 – суммарные расходы на производство.

Требуется найти такие y 1 ,y 2 иy 3 , удовлетворяющие условиям (3), при которых минимизируются суммарные расходы на производство:

минимизировать g(y 1 ,y 2 ,y 3)=b 1 y 1 +b 2 y 2 +b 3 y 3 (4)

при условиях

y 1 ≥0;y 2 ≥0;y 3 ≥0.

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

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

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

максимизировать

при условиях

(7)

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

минимизировать

при условиях

(10)

В матричном виде пара двойственных задач записывается следующим образом:

максимизировать

при условиях

минимизировать

при условиях

A T y≥c; (15)

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

если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот;

коэффициенты целевой функции прямой задачи c 1 ,c 2 ,…,c n становятся свободными членами ограничений двойственной задачи;

свободные члены ограничений прямой задачи b 1 ,b 2 ,…,b m становятся коэффициентами целевой функции двойственной задачи;

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

знаки неравенств в ограничениях изменяются на обратные;

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

Переменные y 1 ,y 2 ,…,y m двойственной задачи иногда называют теневыми ценами.

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

задаче при малом количестве переменных имеется большое количество ограничений (m n).

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

ТЕОРЕМА 1. Если -допустимые решения прямой и двойственной задач, т. е. то

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

ТЕОРЕМА 2 (основная теорема двойственности). Если -допустимые решения прямой и двойственной задач и если , то – оптимальные решения пары двойственных задач.

ТЕОРЕМА 3. Если в оптимальном решении прямой задачи (5) – (7) i -ое ограничение выполняется как строгое неравенство, то оптимальное значение соответствующей двойственной переменной равно нулю, т. е.

где - i -ая строка матрицы А.

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

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

ТЕОРЕМА 4. Если в оптимальном решении двойственной задачи ограничение j выполняется как строгое неравенство, то оптимальное значение соответствующей переменной прямой задачи должно быть равно нулю, т. е. если то

Дадим экономическую интерпретацию теоремы 4.

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

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

Таким образом, теорема 4 выражает принцип рентабельности оптимально организованного производства.

Из нее вытекает также, что то

(20)

Предположим, что среди переменных x 1 ,x 2 ,…,x n прямой задачи есть множество изmпеременных, которые в оптимальном решении имеют ненулевое значение. Пусть, например, таковыми оказались первые по порядкуmпеременных.

Тогда на основании уравнения (22) получают mусловий рентабельности:

(21)

Приведем еще две важные теоремы теории двойственности.

ТЕОРЕМА 5 (теорема существования). Прямая и двойственная задачи имеют оптимальные решения тогда, и только тогда, когда обе они имеют допустимые решения.

ТЕОРЕМА 6 (теорема двойственности). Допустимый вектор x 0 оптимален тогда, и только тогда, когда в двойственной задаче имеется такое допустимое решение y 0 , что

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

i=1, 2, …,m;j=1, 2, …,n,

где n– количество переменных прямой задачи;m– количество ее ограничений; - соответствующие элементы индексной строки прямой и двойственной задач соответственно. При этом, еслиn+i, где 1 ≤i≤mбольше числа векторов-столбцов матрицы ограничений расширенной формы соответствующей задачи, то элементы находятся путем циклической перестановки элементов индексной строки, начиная с элемента

Общий случай двойственности

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

Пусть прямая ЛП-задача задана в виде:

максимизировать

при условиях

Тогда двойственная задача по отношению к (24)-(26) (или сопряженная с ней) состоит в минимизации линейной формы:

минимизировать

при условиях

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

Если переменная x j прямой задачи предполагается неотрицательной, то j-е условие системы ограничений (28) является неравенством.

Если на x j не накладывается такое ограничение, то j-е ограничение двойственной задачи будет равенством.

Аналогичным образом связаны знаки переменных двойственной задачи y i и соответствующие им ограничения прямой задачи. Заметим, что если положитьm 1 =mиn 1 =n, то получим частный случай пары двойственных задач с ограничениями в форме неравенств.

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

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

Математическая модель ЗЛП:

1.Максимум или минимум целевой функции(критерий оптимальности).

2.Система ограничений в форме линейных уравнений и неравенств.

3.Неотрицательность переменных.

Решение, удовлетворяющее системе ограничений и требованиям неотрицательности решений является допустимым, а решения, удовлетворяющие одновременно с этим и условиям min/max являются оптимизированными.

Общий вид ЗЛП

Max(min)F(x)=c1x1+c2x2+…cnxn

A11x1+a12x2+…a1nxn<=b1

A21x1+a22x2+…a2nxn<=b2

Am1x1+am2x2+…amnxn<=bnm, x1,x2,…xn>=0

Свойства ЗЛП:

1.Допустимое множество решений ЗЛП либо пустое, либо является выпуклым многогранником.

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

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

Графический метод решения ЗЛП

Если число неизвестных равно 2, то ее можно решить графическим методом. Найти решение X=(x1,x2)? Удовлетворяющее условию max(min)z=c1x1+c2x2. При ограничениях сумм j от 1 до n (aij*xj)<=bj, x1, x2 >=0.

Каждое из неравенств 2 определяет на координатной плоскости полуплоскость, а система неравенств 2 и 3 в случае ее совместимости – пересечение плоскостей. Это будет выпуклое множество, которое может быть представлено как:

1.Выпуклый многоугольник.

2.Выпуклая неограниченная многоугольная область.

3.Отрезок.

5.Одна точка.

6.Пустое множество.

Геометрическая интерпретация целевой функции:

Z=C 1 X 1 +C 2 X 2 (1)

При фиксированных значениях Z=Z 0 определяет линию z0=c1x1+c2x.

При изменении Z получим семейство параллельных прямых, называемых линиями уровня.

Вектор С=(С 1 , С 2) с координатами при x1 и x2 перпендикулярен каждой из линий уровня.

Вектор С показывает направления наибольшего возрастания (убывания) целевой функции.

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

1.Задача имеет единственное решение.

2.Задача имеет бесконечное множество решений(альтернативный оптимум).

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

Симплекс-метод

Построение начального опорного плана

Рассмотрим 3 случая.

1) Пусть система ограничений имеет вид

X i + ij X j =b i , b i =>0,(i=1,m)

X 0 =(0,0,…,0,b i)

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

Ij X j <=b i , b i >=0

Дополнительную переменную вводят с коэффициентом равным 0

Ij X j +X n+1 =b i , b i >=0

X 0 =(0,…,0,b 1 ,...,b m)

Ij X j >=b i , b i >=0

Ij X j -X n+i =b i

Max(min)Z= j X j -(+)M i

Симплексные таблицы

Признак оптимальности опорного плана. Задача максимизации

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

Рассмотрим переход к нехудшему опорному плану на примере задачи ЛП на макс.

Если в индексной строке dj < 0, то план не оптимален и его можно улучшить. Среди отрицательных оценок находят максимальную по абсолютной величине.

Если задача на минимум, то разрешающий столбец Max|dj|=|dj 0 |

Переменную Xj 0, следует ввести в базис. Для определения переменной, выводимой из базиса, находят отношения: B i /A ij , A ij >0

Min = B i 0 /A i 0 j 0

НА пересечении разрешающей строки и разреш столбца находиться разр элемент.

1.Элементы строки I 0 новой таблицы равны соответствующим элементам разрешающей строки предыдущей таблицы деленной на разреш элемент.

2.Все элементы столбцы J 0 равны 0, за исключением разрешающего элемента.

3.Все остальные элементы новой таблицы высчитываются по правилу: произведение главной диагонали минус произведение побочной диагонали деленной на разрешающий элемент.

Три признака:

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

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

3.Признак несовместности системы ограничений. Если в оптимальном плане М-задачи не все искусственные переменные равны 0, то система ограничений исходной задачи несовместна.

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

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

Прямая - maxZ = Xj>=0

Двойственная minZ = Xj>=0

Пара двойственных задач может быть экономически интерпретирована:

Прямая – Сколько и какой продукции Xj надо произвести чтобы при заданных стоимостях единицы продукции Cj объемах ресурсов Bi и нормах расхода Aij максимизироваит выпуск продукции в стоимостном выражениии.

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

Правила построения:

1.Упорядочивается запись исходной задачи, т.е. если целевая функция задачи максимизируется, то ограничения неравенства должны быть > или =(для минимиз < или =) Достигается умножением ограничений на -1.

2.Если прямая задача решается на максимум, то двойственная на минимум.

3.Каждому ограничению прямой задачи соответствует переменная двойственной задачи и наоборот.

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

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

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

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

Транспортная задача

Представим транспортную задачу по критерию стоимости в виде таблицы

В таблице указаны поставщики А1… , у которых имеется в наличии соответственно а 1 … единиц однородного груза. Данный груз должен быть доставлен n потребителям, в количествах в 1 … единиц, заданы стоимости с ij перевозок груза от i поставщика j потребителю. Требуется спланировать перевозки(указать, сколько единиц груза должно быть отправлено от I того поставщика j потребителю, так чтобы максимально удовлетворить спрос потребителя и чтобы суммарные затрата на перевозки были при этом минимальными).

c 1 – цена.

Задачи, где суммарные запасы грузов поставщиков равны суммарным потребностям, называются закрытыми.

I != I – то задача открытая.

При решении транспортных задач важное значение имеет теорема о ранге матрицы:

Ранг матрицы транспортной задачи на 1 меньше числа уравнений(r=m+n-1).

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

1.Определение исходного опорного плана.

2.Оценка этого плана.

3.Переход к следующему плану путем однократной замены одной из базисных переменных на свободную.

Существуют различные способы реализации этапов решения транспортной задачи:

Правило северо-западного угла

Правило минимального элемента

Метод Фогеля4

Метод потенциалов

Метод потенциалов

Перейдем к построению оптимального плана перевозок. По данному опорному плану, у которого число занятых клеток m+n-1. Каждому поставщику и каждому потребителю передается число, называемое потенциалом. Потенциалы выбираются так, чтобы их сумма для каждой загруженной грузом клетки была равна тарифу перевозки единицы груза. Так если клетка (I,k) – базисная(занятая), то u i +v k =C ik где у итое потенциал итого поставщика.

Тогда вычисляем оценки свободных клеток по формуле: S ij =C ij -(U i +V j)

Если для свободных клеток все оценки S ij больше или ровны 0, то полученный план перевозок оптимален. При наличии хотя бы одной оценки S ij < 0 число базисных вводят в клетку, для которой оценка S ij минимальной. Для такой клетки строится цикл и производится перемещение груза так, чтобы баланс цикла сохранялся.

U 3 =
В заполненой клетке таріф равен сумме потенциалов

F=320+150+140+150+1020+120=1900

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

Теорема 1 (Первая теорема двойственности) . Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и

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

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

Примечание: утверждение, обратное по отношению ко второй части первой теоремы двойственности, в общем случае неверно.

Теорема 2 . Компоненты оптимального плана двойственной задачи (обладающие условием неотрицательности ) равны абсолютным значениям коэффициентов

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

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

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

. (7.2)

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

Пример 9.1. На основе решения примера 5.2 (файл «Алгоритм и примеры симплекс-метода») определим двойственным симплекс- методом оптимальное решение двойственной задачи.

Данная двойственная пара является симметричной. Задачи записаны в стандартной форме, приведем их к каноническому виду:

Установим соответствие между переменными взаимно двойственных задач.

На основе решения примера 5.2. симплекс-таблица последней итерации (таблица 5.10) имеет вид:

Таблица 9.3

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

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

Следовательно, , .

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

В соответствии с теоремой 1, .

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

Пример 9.2. На основе решения исходной задачи найти оптимальное решение двойственной задачи используя двойственный симплекс-метод.

Данная двойственная пара является несимметричной. Приведем к каноническому виду двойственную задачу.

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

Установим соответствие между переменными взаимно двойственных задач.

Таблица 9.4

Соответствие переменных двойственной пары

Решим исходную задачу симплекс-методом.

Используя метод Жордана-Гаусса, выделим в системе ограничений исходной задачи в качестве базисных переменные и (примечание: не использовать в качестве базисных фиктивные переменные).

В результате преобразований получим следующую матрицу коэффициентов:

.

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

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

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

В результате решения симплекс-методом преобразованной исходной задачи на последней итерации получим следующую симплекс-таблицу:

Таблица 9.5

Симплекс-таблица оптимального решения исходной задачи

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

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

Симметричная двойственная задача

Рассмотрим задачу линейного программирования с неотрицательными переменными и неравенствами системы ограничений следующего вида:
(1.1) ;
(1.2)
Здесь , , есть некоторые числа. Все строки системы (1.2) являются неравенствами со знаками .

(2.1) ;
(2.2)
Здесь все строки системы (2.2) являются неравенствами со знаками . Матрица коэффициентов системы ограничений (2.2) является транспонированной матрицей системы (1.2). Она содержит строк и столбцов. Двойственная задача имеет переменных . Все переменные неотрицательные.

Исходную задачу (1) часто называют прямой задачей, а задачу (2) - двойственной. Если за исходную взять задачу (2), то задача (2) будет прямой задачей, а задача (1) - двойственной. Задачи (1) и (2) называются симметричными двойственными задачами .

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

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

;

Исходная задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки . Первое и третье неравенства содержат знак . Умножим их на -1 :

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

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

;

Несимметричная двойственная задача

Задача на максимум

Рассмотрим каноническую задачу линейного программирования на максимум с неотрицательными переменными и равенствами системы ограничений:
(3.1) ;
(3.2)
Здесь , , есть некоторые числа. Все строки системы (3.2) являются равенствами. Все переменные являются неотрицательными.

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

Отличие несимметричной пары задач (3) и (4) от симметричной пары (1) и (2) в том, что система ограничений (3.2) содержит только равенства, а в системе (4.2) отсутствуют условия неотрицательности переменных.

Задача на минимум

Теперь рассмотрим каноническую задачу линейного программирования на минимум:
(5.1) ;
(5.2)

Двойственная задача имеет вид:
(6.1) ;
(6.2)

Система ограничений (6.2) отличается от (4.2) тем, что неравенства имеют знаки .

Связь с симметричной парой двойственных задач

Покажем, что несимметричную пару задач (3)-(4) можно получить из симметричной пары (1)-(2).

Итак, пусть мы имеем прямую задачу с целевой функцией
(3.1)
и системой ограничений
(3.2)
Каждое равенство можно представить двумя неравенствами:

Неравенства со знаками умножим на -1 :

Система ограничений имеет неравенств.

По формулам (1)-(2) получаем двойственную задачу:
;


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

Сделаем подстановки
.
Поскольку и , то переменные могут быть как положительными, так и отрицательными.

И мы получаем двойственную задачу (4):
(4.1) ;
(4.2)

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

Тем же способом можно из задачи (5) получить двойственную задачу (6) и из задачи (6) получить двойственную задачу (5).

Смешанная задача

Теперь рассмотрим смешанную задачу.

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

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

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

И наконец, пусть мы имеем прямую задачу (2) на минимум, но отсутствует ограничение . Тогда двойственная задача имеет вид (1) за одним исключением - -я строка системы ограничений является равенством.

Все это позволяет нам сформулировать правила составления двойственных задач.

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

1. Для исходной задачи на максимум, все неравенства системы ограничений приводим к виду:
.
Для исходной задачи на минимум, все неравенства приводим к виду:
.
Если требуется поменять знак, то умножаем обе части неравенств на -1 .
2. Составляем двойственную задачу тем же способом, как для симметричной пары задач.
3. Если в исходной задаче, -я строка системы ограничений является равенством, то вычеркиваем условие неотрицательности -й переменной двойственной задачи.
4. Если в исходной задаче, отсутствует условие неотрицательности для -й переменной, , то в -й строке двойственной задачи меняем знак неравенства на знак равенства.

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

Дана задача линейного программирования:
;

Составить двойственную задачу.

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

;

Эта задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки . Третье неравенства содержат знак . Поэтому умножим его на -1 :

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

Матрица коэффициентов системы ограничений имеет вид:

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

Составим двойственную задачу как для симметричной пары.
;

Поскольку в исходной задаче 1, 2 и 4-я строка системы ограничений являются равенствами, то в двойственной задаче переменные , и могут иметь любой знак. Неотрицательной переменной является только . Поэтому условия неотрицательности переменных имеют вид:
.

Поскольку в исходной задаче переменные и могут иметь произвольные знаки, то 3-я и 4-я строки системы ограничений двойственной задачи являются равенствами.

Таким образом, двойственная задача имеет вид:
;

Из четвертого уравнения . Заменим переменную ее значением и умножим третью строку на -1 .

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

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

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

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

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

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

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

,

,

i=1,..,m; j=1,..,n.

Назовем эту задачу прямой. Тогда двойственной по отношению к ней будет задача:

,

i=1,..,m; j=1,..,n.

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

1. Каждому ограничению прямой задачи соответствует переменная двойственной задачи.

2. Каждой переменной прямой задачи соответствует ограничение двойственной задачи.

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

4. Вид экстремума двойственной задачи противоположен виду экстремума прямой задачи;

5. Векторы В и С в прямой и двойственной задачах меняются местами;

6. Матрица A двойственной задачи получается путем транспонирования матрицы А прямой задачи;

7. Все ограничения двойственной задачи имеют вид для задачи максимизации и вид для задачи минимизации линейной формы.

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

Для случая несимметричной задачи:

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

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

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

Пример Дана задача линейного программирования (слева от каждого ограничения стоит ассоциированная с ним двойственная переменная). Данная задача относится к несимметричной.

,

Сформулируем для этой задачи двойственную задачу. Целевая функция двойственной задачи представляет собой линейную форму, полученную как произведение вектора b=(10,20,60,80) на вектор переменных двойственной задачи Y =(). Кроме того, поскольку в прямой задаче целевая функция максимизируется, в двойственной она минимизируется. С учетом сделанных замечаний получим,

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

А поскольку к тому же, прямая задача является задачей поиска максимума, то первое ограничение имеет вид:

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

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

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

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

,

,

,

Не ограничена в знаке, .

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

,

.

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

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

,

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

.

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

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

Рассмотрим смешанную задачу.

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

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

Каноническая форма задачи имеет вид:

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

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

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

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

Теорема. Для оптимальности допустимых решений необходимо и достаточно, чтобы они удовлетворяли системе уравнений

.

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

Пример Решим симметричную задачу. Пусть исходная задача имеет вид

Решив задачу графическим методом, получим

Составим для нее двойственную задачу

Так целевые функции в точке оптимума равны, то

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

Подставим в ограничения значения . Получим

.

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

.

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

Решим ту же задачу, однако считая, что известно решение

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

.

Решая данную систему уравнений, получим

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

Рассмотрим экономическую интерпретацию двойственной задачи.

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

То двойственные переменные показывают, как изменится целевая функция при изменении ресурса на единицу