Она строится по формальным пра вилам на базе другой задачи линейного программирования (ЛП), называемой основной. Например, если основная задача имеет вид Ах < Ь, X > О, (с Л') -> max, (1) то двойственная к ней задача также является задачей ЛП: А^у >с, у< О, {Ь, у) —> min. Здесь Х = (Х,,Х2, ... ,X^), 6 = (6р/?2' ••• '^,7)' С={С^,С2,... (2) О^ А = ^fl,l а,2 ... ai„^ (321 а22 ... «2/7 ' (б',х)= Х<^7-^.У' 7=1 • Ф,у) - iL^iyt^ А^ - транспонированная матрица А. Основная и двойственная к ней задачи образуют пару взаим но двойственных задач: двойственная задача к двойственной ока зывается основной задачей. Основная теорема двойственности Либо обе задачи двойственной пары разрешимы, и тогда (с, х *) = = {Ь, ;;*), либо обе задачи не имеют решения. Здесь х* >^* - опти мальные планы пары двойственных задач. Эта и ряд других теорем, относящихся к двойственным зада чам, играют важную роль при качественном анализе задач ЛП. Содержательный анализ двойственной задачи, в том числе и неизвестных у\, yj, ••• , У,^^, полностью определяется содержатель ным смыслом прямой задачи. Так, например, если основная задача (1) является задачей про изводственного планирования, где А - технологическая матри ца, Ь.- количество /-го ресурса, х . - объем выпускау-го продукта, i - 1,2, ... m,j = 1, 2, ... /7, то целью решения двойственной задачи (2) оказывается получение так называемых двойственных оценок ресурсов j^., которые также называют маргинальными (предельны ми) данными ресурсов. Маргинальные цены, очевидно, связаны только с производст вом и потому отличаются от обычных рыночных цен на ресурсы. Если маргинальные цены не превосходят рыночных (j^* < д., / = 1 , 2 , . . . , т), то производство, для которого они были рассчита ны, не сможет получить прибыль р от своей производственной деятельности: для любого плана выпуска х р{х) = {с, X) - {Ь, q) < {с, .Y*) - ф, q) < (с, л*) - {Ь, ;;*) = 0. И, наоборот, если ;;.* > ^., / = 1, 2, ... , т, то реализация опти мального производственного плана х* принесет положительную прибыль /7(х*) = {с, X*) - {Ь, q) = ф, у"^) - {Ь, q) = (b, y*-q) > О, размер которой ограничивается: а) средствами, выделяемыми на закупку ресурсов, Ь) объемом рынка ресурсов, с) технологичес кими условиями производства. Если записать прямую задачу линейного программирования в канонической форме: найти набор переменных л: = (Xj , ... , x j , удовлетворяющих условиям х.> 0,7 = 1, ... , л, 145 п HauXjubj, i=\,...,m (3) М п и максимизирующих целевую функцию С(х)= X с/Л'у, .М то ей соответствует следующая двойственная задача: найти набор переменных j^ = O'l , ••• ? У„)> удовлетворяющих условиям п H^ijyi^cj, j= l,..,,Az (4) /=1 и минимизирующих целевую функцию ^(У)- И,^У1- /=1 (В данном случае неотрицательность переменных в двойствен ной задаче не требуется.) Значения целевых функций прямой и двойственной задач свя заны неравенством п п ^CjXj<Y.biyi. (5) j=\ i=\ где Л' = (.Y, , ... , Л'J - произвольное допустимое решение прямой задачи; V - (V| , ... , j^,„) - произвольноедопустимое решение двойственной за дачи. Основная теорема двойственности в канонической форме за писывается следующим образом. Если существуют допустимые решения прямой и двойствен ной задач, то для обеих задач существуют и оптимальные реше ния, причем max £ = min £ Ь^у^. ^^^ Если хотя бы одна из задач не имеет допустимого решения, то ни одна из них не имеет оптимального решения. 146 Равенство ^ ^.i^J " ^^z-^/ является необходимым и достаточ- ным условием оптимальности допустимых решений прямой и двой ственной задач. Из теоремы двойственности вытекает ряд положений, которые позволяют устанавливать некоторые соотношения между целевой функцией и ресурсами, необходимыми для достижения цели. В частности, имеет место следующее важное утверждение. Если задача линейного программирования не вырождена и С(л'*) п представляет собой максимум ее линейной формы ^ ^j^j при заданных ограничениях, то г)с'(л'*) / дЬ. - у,*, / = 1,2, ... , т. Таким образом, с математической точки зрения оптимальные оцен ки определяют влияние свободных членов Ь^ условий-ограничений на оптимальную величину целевой функции. Иными словами, вычисление наряду с оптимальным планом л'* = (л*,*, А'2*, ... , л'^^*) связанных с ним оптимальных оценок v* = CVj*, J?*» ••• , .V„,*) позволяет ввести относи тельную важность отдельных ресурсов (Z?j *, Z?2*5 •••» ^,„*) Д^я достижения п поставленной цели (максимизации ^ ^J^J). . / • = 1 На основе установления такой взаимосвязи между л* и >'* можно исследовать влияние небольших отклонений ресурсов на изменение оптимального значения целевой функции, получать маргинальные оценки, идея которых уже рассмотрена, или дру гие рекомендации, полезные при разработке и корректировке пла нов в тех случаях, когда не может быть найдено строгое решение задачи оптимизации. Идеи теории двойственности находят важное применение в разработке численных методов линейного программирования (см.), позволяющих решать задачи с неопределенностью, не имеющие строгого оптимума, что особо важно для задач системного ана лиза.
Ви переглядаєте статтю (реферат): «ДВОЙСТВЕННАЯ ЗАДАЧА В ЛИНЕЙНОМ ПРОГРАММИ РОВАНИИ» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
