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

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_{1 -} x₂ ? 3

x₁ + 0.5x₂ ?2

x_1,2 ? 0

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

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

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

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

y_{1 -} 2y₂ + y₃ ? 3

y₁ + y₂ + 0.5y₃ ? 2

y₁?0, y₂?0, y₃?0.

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

Таблица 1

Таблица 2

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

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

2. Метод последовательных уступок. Алгоритм метода. Пример применения метода к решению задачи многокритериальной оптимизации выпуска продукции предприятием

Суть метода последовательных уступок.

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

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

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

При решении многокритериальной задачи методом последовательных уступок вначале производится качественный анализ относительной важности частных критериев; на основании такого анализа критерии располагаются и нумеруются в порядке убывания важности, так что главным является критерий K₁, менее важен. K₂, затем следуют остальные частные критерии К₃, К₄., K_S. Максимизируется первый по важности критерий K₁ и определяется его наибольшее значение Q₁. Затем назначается величина "допустимого" снижения (уступки) ₁>0 критерия K₁ и ищется наибольшее значение Q₂ второго критерия K₂ при условии, что значение первого критерия должно быть не меньше, чем Q₁-₁. Снова назначается величина уступки ₂>0, но уже по второму критерию, которая вместе с первой используется при нахождении условного максимума третьего критерия, и т.д. Наконец, максимизируется последний по важности критерий Ks при условии, что значение каждого критерия К_r из S-1 предыдущих должно быть не меньше соответствующей величины Q_r-_r; получаемые в итоге стратегии считаются оптимальными.

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

1) найти Q₁=

2) найти Q₂=

3) найти Q_S=

Если критерий K_S на множестве стратегий, удовлетворяющих ограничениям задачи S), не достигает своего наибольшего значения Q_s, то решением многокритериальной задачи считают максимизирующую последовательность стратегий {u^k} из указанного множества (lim K_S (u^k) = Q_S). k->

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

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

Величины уступок _r последовательно назначаются в результате изучения взаимосвязи частных критериев.

Вначале решается вопрос о назначении величины допустимого снижения _r первого критерия от его наибольшего значения Q₁. Практически для этого задают несколько величин уступок ¹₁, ²₁, ³₁… и путем решения 2) в задаче (1) определяют соответствующие макс. значения Q₂ (¹₁), Q₂ (²₁), Q₂ (³₁), и второго критерия. Иногда, если это не слишком сложно, отыскивается функция Q₂ (₁). Результаты расчетов для наглядности Представляем графически (Рис 1)

Рис. 1.

Он показывает, что вначале даже небольшие величины уступок позволяют получить существенный выигрыш по второму критерию; с дальнейшим увеличением уступки выигрыш растет все медленнее. На основе анализа полученных данных и решают вопрос о назначении величины уступки ₁, а затем находят Q₂ (₁).

Далее рассматривают пару критериев K₂ и K₃ вновь назначают "пробные" величины уступок Q₂ (²₂),,. и, решая 3) в задаче (1), отыскивают наибольшие значения третьего критерия Q₃ (¹₂), Q₃ (²₂),. Полученные данные анализируют, назначают ₂, переходят к следующей паре критериев К₃, K₄ и т.д.

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

Таким образом, хотя формально при использовании метода последовательных уступок достаточно решить лишь S задач (1), однако для назначения величин уступок с целью выяснения взаимосвязи частных критериев фактически приходится решать существенно большее число подобных задач.

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

Пример 1.

Пусть множество UR³ - многогранник, изображенный на рис.2, K₁ (u) =u1, K₂ (u) =u_2, K₃ (u) =u₃. Здесь решением 3 из задачи (1) является любая точка треугольника ABC (на рисунке он заштрихован), но эффективны лишь точки отрезка АС.

Решение.

Справедливо, однако, утверждение: если u* - единственная (с точностью до эквивалентности) стратегия, являющаяся решением S) из задачи (1), то она эффективна.

Действительно, предположим, что стратегия u* неэффективна, так что существует стратегия u'>u*. Но стратегия u' также удовлетворяет всем ограничениям S) задачи (1) и доставляет критерию K_S значение Q_s; иначе говоря, u' оказывается решением этой задачи, что противоречит условию единственности u*. Утверждение доказано.

Рис. 2.

Можно доказать так же, что если URⁿ замкнуто и ограничено, К_r непрерывны на U, а стратегия, являющаяся решением S) задачи (1), единственна с точностью до эквивалентности, то любая максимизирующая последовательность, служащая решением S), эффективна.

Задача № 1.