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

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

max{F(x) = C^T x| Ax≤B, x_i≥0, i =1,n} (1)

и

min{F(y) = B^T y| A^T y≥C, y_j ≥0, j = 1,m}. (2)

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

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

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

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

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

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

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

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

Пусть предприятие располагает ресурсами b₁,b₂,...,b_m, которые могут использоваться для выпуска n видов продукции. Известны нормы потребления j-го ресурса на производство единицы i-й продукции – a_ij , а также прибыль от реализации единицы i-го вида продукции c_i (i = 1, n; j = 1,m) . Найти объем производства продукции каждого вида x*_i, максимизирующий суммарную прибыль предприятия F(x) = ∑c_ix_i , при этом расход ресурсов не должен превышать их наличия. Математическая модель задачи имеет вид

max{F(x)=∑c_ix_i|∑a_jix_i≤b_j, j=1,m; x_i≥0, i=1,n} (3)

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

max{F(x)=∑c_ix_i|∑a_jix_i=b_j, j=1,m; x_i≥0}.

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

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

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

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

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

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

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

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

min{F(y)=∑b_jy_j|∑a_ijy_j≥c_i, i=1,n; y_j0, j=1,m} (4)

Пока прибыль предприятия (задача 3) меньше общей ценности ресурсов (задача 4), решение обеих задач будет неоптимальным. Оптимум достигается в случае, когда прибыль становится равной общей ценности ресурсов, т.е. max F(x) = min F( y) .

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

F(x) = 3x₁ + 2x₂ (min) ;

x₁ + x₂ ≤ 5

2x₁ - x₂ ≤ 3

x₁ + 0.5x₂ ≥2

x_1,2 ≥ 0

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

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

тогда условие A^Ty≤C примет следующий вид:

- y₁ - 2y₂ + y₃ ≤ 3

- y₁ + y₂ + 0.5y₃ ≤ 2

y₁≥0, y₂≥0, y₃≥0 .

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

Таблица 1

базисные переменные	Свободные члены	Небазисные переменные
x1	x2
x3
x4			-1
x5	-2	-1	0.5
F

Таблица 2

базисные переменные	Свободные члены	Небазисные переменные
y1	y2	y3
y4		-1	-2
y5		-1		0.5
F				-2

В общем виде при минимизации F(x) в прямой задаче начальные симплекс-таблицы для прямой и двойственной задач можно представить в виде табл. 3 и 4.

Если в прямой задаче находится максимальное значение F(x) , то начальные симплекс-таблицы прямой и двойственной задач можно представить в виде табл. 5 и 6.

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

Возможны следующие случаи:

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

Первая теорема двойственности.

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

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

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

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

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

Теорема об оценках:

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

.

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

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

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

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

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

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

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

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

19) Этот метод относят к методам отсечения.

Требование дополнительно предъявляемое к постановке задачи для метода Гомори № 1 выглядит следующим образом: все компоненты плана должны быть целочисленными. Другими словами, даже к искусственным переменным предъявляется требование целочисленности.

Пусть

оптимальное решение -

задачи.

Проверим соблюдение условия целочисленности.

Если все компоненты плана целые, то = . В случае не целых

компонент

преобразуем систему ограничений.