Министерство сельского хозяйства РФ
Федеральное бюджетное образовательное учреждение высшего
профессионального образования
Иркутский государственный аграрный университет
Экономический факультет
Кафедра информатики
Реферат на тему: «Двойственные задачи линейного программирования».
Выполнил: студент 2 курса
экономического факультета
напр. 080101.65
«Экономическая безопасность»
Мезенцев Вячеслав
Проверила: Бузина Т.С.
Иркутск – 2015
Двойственные задачи линейного программирования
Важную роль в линейном программировании имеет понятие двойственности. Рассмотрим две задачи линейного программирования:
max{F(x) = CTx| Ax≤B, xi≥0, i =1,n} (1)
и
min{F(y) = BTy| ATy≥C, yj≥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. Если на переменную xiпрямой задачи наложено условие неотрицательности, то i-е условие системы ограничений двойственной задачи является неравенством и наоборот.
2. Если на переменную xi прямой задачи не наложено условие неотрицательности, то i-е ограничение двойственной задачи записывается в виде строгого равенства.
3. Если в прямой задаче имеются ограничения равенства, то на соответствующие переменные двойственной задачи не накладывается условие неотрицательности.
Линейное программирование находит широкое применение при решении многих практических задач организационно-экономического управления. Цель, как правило, заключается в том, чтобы максимизировать прибыль либо минимизировать расходы.
Рассмотрим задачу рационального использования ресурсов.
Пусть предприятие располагает ресурсами b1,b2,...,bm, которые могут использоваться для выпуска n видов продукции. Известны нормы потребления j-го ресурса на производство единицы i-й продукции – aij, а также прибыль от реализации единицы i-го вида продукции ci(i = 1, n; j = 1,m) . Найти объем производства продукции каждого вида x*i, максимизирующий суммарную прибыль предприятия F(x) = ∑cixi, при этом расход ресурсов не должен превышать их наличия. Математическая модель задачи имеет вид
max{F(x)=∑cixi|∑ajixi≤bj, j=1,m; xi≥0, i=1,n} (3)
Метод искусственного базиса используется для нахождения допустимого базисного решения задачи линейного программирования, когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу:
max{F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0}.
Под чувствительностью модели понимается зависимость оптимального решения от изменения параметров исходной задачи. Выполняя анализ модели на чувствительность, можно выяснить:
а) насколько можно увеличить запас некоторого ресурса, чтобы улучшить оптимальное значение F;
б) насколько можно сократить запас некоторого ресурса, чтобы сохранить при этом оптимальное значение F;
в) увеличение объёма какого из ресурсов наиболее выгодно;
г) какому из ресурсов отдать предпочтение при вложении дополнительных средств;
д) в каких пределах допустимо изменять коэффициенты целевой функции, чтобы не произошло изменение оптимального решения.
Ограничения, проходящие через точку оптимума, называются активными, или связывающими. Ресурсы, с которыми ассоциируются эти ограничения, относятся к разряду дефицитных. Остальные ресурсы недефицитны, а соответствующие им ограничения – неактивные или несвязывающие. Сокращение объема дефицитного ресурса никогда не улучшает значения целевой функции. Анализ на чувствительность придает модели динамичность, свойственную реальным процессам.
Сформулируем задачу, двойственную к рассматриваемой задаче рационального использования ресурсов. Пусть некоторая организация может закупить все ресурсы bj, которыми располагает предприятие. Необходимо определить оптимальные цены y*j( j = 1,m) на единицу этих ресурсов при условии, что покупатель стремиться минимизировать общую оценку ресурсов. При этом общая ценность ресурсов должна быть не меньше прибыли, которую может получить предприятие при организации собственного производства. Математическая модель задачи имеет вид
min{F(y)=∑bjyj|∑aijyj≥ci, i=1,n; yj0, j=1,m} (4)
Пока прибыль предприятия (задача 3) меньше общей ценности ресурсов (задача 4), решение обеих задач будет неоптимальным. Оптимум достигается в случае, когда прибыль становится равной общей ценности ресурсов, т.е. max F(x) = min F( y) .
Пример 1.Построить двойственную задачу к следующей задаче, заданной в общей форме:
F(x) = 3x1 + 2x2 (min) ;
x1 + x2 ≤ 5
2x1 - x2 ≤ 3
x1 + 0.5x2 ≥2
x1,2≥ 0
Приведем условие к стандартной форме (2). Так как требуется найти минимум целевой функции, то неравенства в системе ограничений должны быть вида ≥. Первое и второе неравенства умножим на (-1), тогда
Двойственная задача будет иметь 3 переменные, так как прямая содержит три ограничения. В соответствии с указанными выше правилами запишем двойственную задачу в виде
тогда условие ATy≤C примет следующий вид:
- y1 - 2y2+ y3≤ 3
- y1 + y2+ 0.5y3≤ 2
y1≥0, y2≥0, y3≥0 .
Составим начальные симплекс-таблицы для прямой и двойственной задач (табл. 1 и 2).
Таблица 1
| базисные переменные | Свободные члены | Небазисные переменные | |
| x1 | x2 | ||
| x3 | 5 | 1 | 1 |
| x4 | 3 | 2 | -1 |
| x5 | -2 | -1 | 0.5 |
| F | 0 | 3 | 2 |
Таблица 2
| базисные переменные | Свободные члены | Небазисные переменные | ||
| y1 | y2 | y3 | ||
| y4 | 3 | -1 | -2 | 1 |
| y5 | 2 | -1 | 1 | 0.5 |
| F | 0 | 5 | 3 | -2 |
В общем виде при минимизации F(x) в прямой задаче начальные симплекс-таблицы для прямой и двойственной задач можно представить в виде табл. 3 и 4.
Если в прямой задаче находится максимальное значение F(x) , то начальные симплекс-таблицы прямой и двойственной задач можно представить в виде табл. 5 и 6.
Список используемой литературы:
Интернет-ресурс (studopedia.net)
Учебное пособие “Компьютерное моделирование” Боев В.Д., Сыпченко Р.П., Издательство Интернет-Университет Информационных Технологий, 2010 г.
6
studfiles.net
Каждой задаче ЛП можно некоторым образом сопоставить другую задачу ЛП, называемую двойственной по отношению к исходной (прямой):
| Прямая задача (ПЗ) | Двойственная задача (ДЗ) |
ДЗ по отношению к прямой составляют согласно правилам:
1) ЦФ ПЗ задаётся на max, тогда ЦФ ДЗ – на min, и наоборот;
2) матрица, составленная из коэффициентов в
системе ограничений ПЗ, и аналогичная матрица в ДЗ получаются друг из друга транспонированием;
3) число переменных в ДЗ (т) равно числу соотношений (ограничений) в ПЗ, а число ограничений ДЗ (п) – числу переменных в ПЗ;
4) коэффициенты при неизвестных в ЦФ ДЗ – свободные члены (bi), а правые части в ограничениях ДЗ (cj) – коэффициенты при неизвестных в ЦФ ПЗ;
5) если переменная xj ПЗ может принимать только положительные значения (xj ³ 0), то j-е условие ПЗ – условие неравенства вида «³». Если i-е соотношение в ПЗ – неравенство, то i-я переменная ДЗ zi³ 0.
Если ПЗ имеет решение, то и ДЗ тоже имеет решение, причём max(min)L1 = min(max)L2. Поэтому достаточно для отыскания оптимума решить одну какую-либо из задач двойственной пары, обычно решают ту, которая проще.
Оптимальный план двойственной задачи позволяет оценить степень дефицитности ресурсов, потребляемых при выполнении оптимального плана исходной задачи.
Свойства двойственной задачи ЛП
Свойство 1. max(min)L1 = min(max)L2
Исходя из первого свойства ДЗ, можно провести следующую интерпретацию двойственной задачи
Другими словами двойственная переменная является коэффициентом пропорциональности, который умножается на и показывает зависимость ЦФ от изменения величины ресурсов на одну единицу. Таким образом, величина двойственной переменной показывает, на сколько возрастет максимальное значение ЦФ прямой задачи при увеличении количества соответствующего ресурса на единицу. Двойственные переменные оценивают степень влияния изменений в величине выделяемых ресурсов на конечные результаты их использования. Поэтому эти переменные и называют двойственными оценками.
Если ресурс в ПЗ используется не полностью, то соответствующая величина двойственной переменной (оценки) в ДЗ равна “0”, и, наоборот, если ресурс используется полностью, то его увеличение или уменьшение влияет на значение ЦФ в ПЗ.
Свойство 2.
При подстановке оптимальных значений двойственных переменных в систему ограничений двойственной задачи возможны следующие ситуации:
Ограничение вида “а” говорит о том, что суммарная оценка всех используемых ресурсов на производство единицы продукции равна стоимость единицы продукции.
Ограничение вида “б” говорит о том, что двойственная оценка всех видов ресурсов на производство одной единицы продукции вида выше цены этой продукции. Значит, ее выпускать невыгодно.
Анализ соотношений “а” и “б” позволяет следующим образом проинтерпретировать взаимоотношение покупателя ресурса и организации, имеющей (производящей) данный ресурс. Покупатель стремится минимизировать стоимость ресурса, однако ее нельзя сделать меньше стоимости той продукции, которую собирается выпускать покупатель, т.к. в этом случае организации будет выгоднее самой наладить производство соответствующей продукции, а не продавать ресурсы.
Свойство 3.
Как и в прямой задаче в двойственной задаче должны вводиться дополнительные (вспомогательные) переменные
,
— дополнительные двойственные переменные
Если основные переменные (переменные в ПЗ) равны нулю, то дополнительные двойственные переменные положительные значения и их величины показывают насколько уменьшится значение ЦФ в ПЗ при принудительном выпуске единицы продукции соответствующего вида.
Свойство 4.
Данное свойство решений ПЗ и ДЗ связано с анализом чувствительности оптимальных решений указанных задач к изменению исходных данных рассматриваемых задач. Исходными данными как в ПЗ, так ДЗ являются матрица, векторы .
В этом случае исследование чувствительности решений ПЗ ЛП сводится к определению таких границ изменения компонент данных векторов, при которых сохраняется сам оптимальный план производства продукции (в ПЗ это определение ), либо его структура (номенклатура выпускаемых изделий, в ПЗ это определение ).
Оптимальные значения двойственные переменные сохраняют в том же интервале, что и соответствующие им коэффициенты в ПЗ. Кроме того, оптимальный план ДЗ не меняется при изменении свободных членов ПЗ ( ) в интервалах, в рамках которых структура оптимального плана ПЗ сохраняется.
Пример. Для производства изделий А, В, С используются три различных вида ресурсов. Каждый из видов ресурсов может быть использован в количестве соответственно не большем 180, 210, 244 ед. Известны затраты каждого из видов ресурсов на единицу продукции и цена единицы продукции каждого вида (табл.2.10).
Определить план производства, при котором обеспечивается максимальный доход, и оценить дефицитность каждого из видов ресурсов, используемых для производства продукции.
Таблица 2.5.1.
| Вид ресурса | Норма расхода ресурса (ед. изм.) на единицу продукции | |
| А | В | С |
| Цена продукции |
Оценки, приписываемые каждому из видов ресурсов, должны быть такими, чтобы оценка всех используемых ресурсов была минимальной, а суммарная оценка ресурсов на производство единицы продукции каждого вида – не меньше цены единицы продукции данного вида.
Решение.
Решение ПЗ даёт оптимальный план производства изделий А, В, С, а решение ДЗ – оптимальную систему оценок ресурсов, используемых для производства этих изделий:
Исходя из анализа оптимальных двойственных оценок можно сделать следующие выводы.
§ Ресурсы первого и третьего вида используются полностью. Полному использованию этих ресурсов соответствуют полученные оптимальные оценки, отличные от нуля, т.е. положительные двойственные оценки имеют ресурсы, полностью потребляемые при оптимальном плане производства. Значит, ресурс второго вида недоиспользуется (на 80 ед.). Таким образом, двойственные оценки определяют дефицитность используемых ресурсов.
§ Более того, величина двойственной оценки показывает, на сколько возрастает максимальное значение ЦФ ПЗ при увеличении количество соответствующего ресурса на 1 ед. Так, увеличение количества ресурса первого вида на 1 ед. приведёт к тому, что появится возможность найти новый оптимальный план производства изделий, при которой общий доход возрастает на 5,75 д.е. и станет равным 1340+5,75=1345,75 д.е. Анализ полученных оптимальных значений новой ПЗ показывает, что это увеличение общего дохода достигается за счёт увеличения производства изделий В на 0,625 ед. и сокращения выпуска изделий С на 0,25 ед. Вследствие этого использование ресурса второго вида уменьшается на 0,125 ед.
Точно также увеличение на 1 ед.количества ресурсов третьего вида позволит перейти к новому оптимальному плану производства, при котором доход возрастает на 1,25 д.е. и составит 1340+1,25=1341,25 д.е., что достигается за счёт увеличения выпуска изделий С на 0,25 ед. и уменьшения выпуска В на 0,25 ед., причём объём используемого ресурса второго вида возрастает на 0,625 ед.
§ При подстановке оптимальных двойственных оценок в систему ограничений ДЗ получаем:
Gt; 10;
2 · 5,75 + 1,25 = 14;
5,75 + 5 · 1,25 = 12.
Первое ограничение выполняется как строгое неравенство, т.е. двойственная оценка всех ресурсов на производство единицы изделия А выше цены этого изделия и, следовательно, выпускать его невыгодно. Его производство и не предусмотрено оптимальным планом ПЗ.
При одновременном изменении ресурсов всех видов на величину Dbi (i=1...m) можно оценить их суммарное влияние на значение ЦФ (при условии неизменности двойственных оценок в новой ДЗ относительно оценок в первоначальной ДЗ):
,
где Dbi – величина возможного (при сохранении оптимального плана первоначальной ДЗ) изменения (увеличения или уменьшения) ресурса i-го вида.
www.ronl.ru
Постановка задачи линейного программирования и двойственная задача линейного программирования.
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции. Тем не менее, время показало, что для многих задач, возникающих под влиянием запросов практики, классические методы недостаточны. В связи с развитием техники, ростом промышленного производства и с появлением ЭВМ все большую роль начали играть задачи отыскания оптимальных решений в различных сферах человеческой деятельности. Основным инструментом при решении этих задач стало математическое моделирование — формальное описание изучаемого явления и исследование с помощью математического аппарата.
Искусство математического моделирования состоит в том, чтобы учесть как можно больше факторов по возможности простыми средствами. Именно в силу этого процесс моделирования часто носит итеративный характер. На первой стадии строится относительно простая модель и проводится ее исследование, позволяющее понять, какие из существенных свойств изучаемого объекта не улавливаются данной формальной схемой. Затем происходит уточнение, усложнение модели.
В большинстве случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важна и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной — происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно описывается линейными моделями.
Основные формы задачи ЛП.
Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа.
Стандартная задача ЛП.
или, в матричной записи,
где 
—
матрица коэффициентов. Вектор 
называется
вектором коэффициентов линейной формы, 
—
вектором ограничений.
Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач ЛП.
Каноническая задача ЛП.
или, в матричной записи,
Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.
Общая задача ЛП.
В этой задачи часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности:
Здесь 
. Ясно,
что стандартная задача получается как частный случай общей при 
; каноническая — при 
.
Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.
При изучении задач ЛП сложилась определенная
терминалогия. Линейная форма 
,
подлежащая максимизации (или минимизации) , называется целевой функцией. Вектор
, удовлетворяющий всем
ограничениям задачи ЛП, называется допустимым вектором, или планом. Задача ЛП,
для которой существуют допустимые векторы, называется допустимой задачей.
Допустимый вектор 
, доставляющий
наибольшее значение целевой функции по сравнению с любым другим допустимым
вектором 
, т.е. 
, называется решением задачи,
или оптимальным планом. Максимальное значение 
целевой
функции называется значением задачи.
Двойственная задача линейного программирования.
Рассмотрим задачу ЛП
(1)
или, в матричной записи,
(2)
Задачей, двойственной к (1) (двойственной задачей),
называется задача ЛП от 
переменных
вида
(3)
или, в матричной записи,
(4)
где 
.
Правила построения задачи (3) по форме записи задачи
(1) таковы: в задаче (3) переменных 
столько
же, сколько строк в матрице 
задачи
(1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части
ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме
в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве
целевой функции в (3) выступает линейная форма, коэффициентами которой задаются
вектором правой части ограничений задачи (1), при этом максимизация меняется на
минимизацию. На двойственные переменные накладывается
условие неотрицательности. Задача (1), в отличии от двойственной задачи (3)
называется прямой.
Теорема двойственности. Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение.
Теорема равновесия. Пусть 
— оптимальные планы прямой (1)
и двойственной (3) задач соответственно. Тогда если 
то
www.referatmix.ru
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции. Тем не менее, время показало, что для многих задач, возникающих под влиянием запросов практики, классические методы недостаточны. В связи с развитием техники, ростом промышленного производства и с появлением ЭВМ все большую роль начали играть задачи отыскания оптимальных решений в различных сферах человеческой деятельности. Основным инструментом при решении этих задач стало математическое моделирование — формальное описание изучаемого явления и исследование с помощью математического аппарата.
Искусство математического моделирования состоит в том, чтобы учесть как можно больше факторов по возможности простыми средствами. Именно в силу этого процесс моделирования часто носит итеративный характер. На первой стадии строится относительно простая модель и проводится ее исследование, позволяющее понять, какие из существенных свойств изучаемого объекта не улавливаются данной формальной схемой. Затем происходит уточнение, усложнение модели.
В большинстве случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важна и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной — происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно описывается линейными моделями.Основные формы задачи ЛП.
Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа.
Стандартная задача ЛП.
или, в матричной записи,
где — матрица коэффициентов. Вектор
называется вектором коэффициентов линейной формы,
— вектором ограничений.
Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач ЛП.
Каноническая задача ЛП.
или, в матричной записи,
Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.
Общая задача ЛП.
В этой задачи часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности:
Здесь . Ясно, что стандартная задача получается как частный случай общей при
; каноническая — при
.
Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.
При изучении задач ЛП сложилась определенная терминалогия. Линейная форма , подлежащая максимизации (или минимизации) , называется целевой функцией. Вектор
, удовлетворяющий всем ограничениям задачи ЛП, называется допустимым вектором, или планом. Задача ЛП, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор
, доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором
, т.е.
, называется решением задачи, или оптимальным планом. Максимальное значение
целевой функции называется значением задачи.Двойственная задача линейного программирования.
Рассмотрим задачу ЛП
(1)
или, в матричной записи,
(2)
Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от переменных
вида
(3)
или, в матричной записи,
(4)
где .
Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных столько же, сколько строк в матрице
задачи (1). Матрица ограничений в (3) — транспортированная матрица
. Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные
накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.
Теорема двойственности. Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение.
Теорема равновесия. Пусть — оптимальные планы прямой (1) и двойственной (3) задач соответственно. Тогда если
то
bukvasha.ru
Каждой задаче ЛП можно некоторым образом сопоставить другую задачу ЛП, называемую двойственной по отношению к исходной (прямой):
| Прямая задача (ПЗ) | Двойственная задача (ДЗ) |
ДЗ по отношению к прямой составляют согласно правилам:
1) ЦФ ПЗ задаётся на max, тогда ЦФ ДЗ – на min, и наоборот;
2) матрица, составленная из коэффициентов в
системе ограничений ПЗ, и аналогичная матрица в ДЗ получаются друг из друга транспонированием;
3) число переменных в ДЗ (т) равно числу соотношений (ограничений) в ПЗ, а число ограничений ДЗ (п) – числу переменных в ПЗ;
4) коэффициенты при неизвестных в ЦФ ДЗ – свободные члены (bi), а правые части в ограничениях ДЗ (cj) – коэффициенты при неизвестных в ЦФ ПЗ;
5) если переменная xj ПЗ может принимать только положительные значения (xj ³ 0), то j-е условие ПЗ – условие неравенства вида «³». Если i-е соотношение в ПЗ – неравенство, то i-я переменная ДЗ zi³ 0.
Если ПЗ имеет решение, то и ДЗ тоже имеет решение, причём max(min)L1 = min(max)L2. Поэтому достаточно для отыскания оптимума решить одну какую-либо из задач двойственной пары, обычно решают ту, которая проще.
Оптимальный план двойственной задачи позволяет оценить степень дефицитности ресурсов, потребляемых при выполнении оптимального плана исходной задачи.
Свойства двойственной задачи ЛП
Свойство 1. max(min)L1 = min(max)L2
Исходя из первого свойства ДЗ, можно провести следующую интерпретацию двойственной задачи
Другими словами двойственная переменная является коэффициентом пропорциональности, который умножается на и показывает зависимость ЦФ от изменения величины ресурсов на одну единицу. Таким образом, величина двойственной переменной показывает, на сколько возрастет максимальное значение ЦФ прямой задачи при увеличении количества соответствующего ресурса на единицу. Двойственные переменные оценивают степень влияния изменений в величине выделяемых ресурсов на конечные результаты их использования. Поэтому эти переменные и называют двойственными оценками.
Если ресурс в ПЗ используется не полностью, то соответствующая величина двойственной переменной (оценки) в ДЗ равна “0”, и, наоборот, если ресурс используется полностью, то его увеличение или уменьшение влияет на значение ЦФ в ПЗ.
Свойство 2.
При подстановке оптимальных значений двойственных переменных в систему ограничений двойственной задачи возможны следующие ситуации:
Ограничение вида “а” говорит о том, что суммарная оценка всех используемых ресурсов на производство единицы продукции равна стоимость единицы продукции.
Ограничение вида “б” говорит о том, что двойственная оценка всех видов ресурсов на производство одной единицы продукции вида выше цены этой продукции. Значит, ее выпускать невыгодно.
Анализ соотношений “а” и “б” позволяет следующим образом проинтерпретировать взаимоотношение покупателя ресурса и организации, имеющей (производящей) данный ресурс. Покупатель стремится минимизировать стоимость ресурса, однако ее нельзя сделать меньше стоимости той продукции, которую собирается выпускать покупатель, т.к. в этом случае организации будет выгоднее самой наладить производство соответствующей продукции, а не продавать ресурсы.
Свойство 3.
Как и в прямой задаче в двойственной задаче должны вводиться дополнительные (вспомогательные) переменные
,
— дополнительные двойственные переменные
Если основные переменные (переменные в ПЗ) равны нулю, то дополнительные двойственные переменные положительные значения и их величины показывают насколько уменьшится значение ЦФ в ПЗ при принудительном выпуске единицы продукции соответствующего вида.
Свойство 4.
Данное свойство решений ПЗ и ДЗ связано с анализом чувствительности оптимальных решений указанных задач к изменению исходных данных рассматриваемых задач. Исходными данными как в ПЗ, так ДЗ являются матрица, векторы .
В этом случае исследование чувствительности решений ПЗ ЛП сводится к определению таких границ изменения компонент данных векторов, при которых сохраняется сам оптимальный план производства продукции (в ПЗ это определение ), либо его структура (номенклатура выпускаемых изделий, в ПЗ это определение ).
Оптимальные значения двойственные переменные сохраняют в том же интервале, что и соответствующие им коэффициенты в ПЗ. Кроме того, оптимальный план ДЗ не меняется при изменении свободных членов ПЗ ( ) в интервалах, в рамках которых структура оптимального плана ПЗ сохраняется.
Пример. Для производства изделий А, В, С используются три различных вида ресурсов. Каждый из видов ресурсов может быть использован в количестве соответственно не большем 180, 210, 244 ед. Известны затраты каждого из видов ресурсов на единицу продукции и цена единицы продукции каждого вида (табл.2.10).
Определить план производства, при котором обеспечивается максимальный доход, и оценить дефицитность каждого из видов ресурсов, используемых для производства продукции.
Таблица 2.5.1.
| Вид ресурса | Норма расхода ресурса (ед. изм.) на единицу продукции | |
| А | В | С |
| Цена продукции |
Оценки, приписываемые каждому из видов ресурсов, должны быть такими, чтобы оценка всех используемых ресурсов была минимальной, а суммарная оценка ресурсов на производство единицы продукции каждого вида – не меньше цены единицы продукции данного вида.
Решение.
Решение ПЗ даёт оптимальный план производства изделий А, В, С, а решение ДЗ – оптимальную систему оценок ресурсов, используемых для производства этих изделий:
Исходя из анализа оптимальных двойственных оценок можно сделать следующие выводы.
§ Ресурсы первого и третьего вида используются полностью. Полному использованию этих ресурсов соответствуют полученные оптимальные оценки, отличные от нуля, т.е. положительные двойственные оценки имеют ресурсы, полностью потребляемые при оптимальном плане производства. Значит, ресурс второго вида недоиспользуется (на 80 ед.). Таким образом, двойственные оценки определяют дефицитность используемых ресурсов.
§ Более того, величина двойственной оценки показывает, на сколько возрастает максимальное значение ЦФ ПЗ при увеличении количество соответствующего ресурса на 1 ед. Так, увеличение количества ресурса первого вида на 1 ед. приведёт к тому, что появится возможность найти новый оптимальный план производства изделий, при которой общий доход возрастает на 5,75 д.е. и станет равным 1340+5,75=1345,75 д.е. Анализ полученных оптимальных значений новой ПЗ показывает, что это увеличение общего дохода достигается за счёт увеличения производства изделий В на 0,625 ед. и сокращения выпуска изделий С на 0,25 ед. Вследствие этого использование ресурса второго вида уменьшается на 0,125 ед.
Точно также увеличение на 1 ед.количества ресурсов третьего вида позволит перейти к новому оптимальному плану производства, при котором доход возрастает на 1,25 д.е. и составит 1340+1,25=1341,25 д.е., что достигается за счёт увеличения выпуска изделий С на 0,25 ед. и уменьшения выпуска В на 0,25 ед., причём объём используемого ресурса второго вида возрастает на 0,625 ед.
§ При подстановке оптимальных двойственных оценок в систему ограничений ДЗ получаем:
Gt; 10;
2 · 5,75 + 1,25 = 14;
5,75 + 5 · 1,25 = 12.
Первое ограничение выполняется как строгое неравенство, т.е. двойственная оценка всех ресурсов на производство единицы изделия А выше цены этого изделия и, следовательно, выпускать его невыгодно. Его производство и не предусмотрено оптимальным планом ПЗ.
При одновременном изменении ресурсов всех видов на величину Dbi (i=1...m) можно оценить их суммарное влияние на значение ЦФ (при условии неизменности двойственных оценок в новой ДЗ относительно оценок в первоначальной ДЗ):
,
где Dbi – величина возможного (при сохранении оптимального плана первоначальной ДЗ) изменения (увеличения или уменьшения) ресурса i-го вида.
www.ronl.ru
Постановка задачи линейного программирования и двойственная задача линейного программирования.
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции. Тем не менее, время показало, что для многих задач, возникающих под влиянием запросов практики, классические методы недостаточны. В связи с развитием техники, ростом промышленного производства и с появлением ЭВМ все большую роль начали играть задачи отыскания оптимальных решений в различных сферах человеческой деятельности. Основным инструментом при решении этих задач стало математическое моделирование — формальное описание изучаемого явления и исследование с помощью математического аппарата.
Искусство математического моделирования состоит в том, чтобы учесть как можно больше факторов по возможности простыми средствами. Именно в силу этого процесс моделирования часто носит итеративный характер. На первой стадии строится относительно простая модель и проводится ее исследование, позволяющее понять, какие из существенных свойств изучаемого объекта не улавливаются данной формальной схемой. Затем происходит уточнение, усложнение модели.
В большинстве случаев первой степенью приближения к реальности является модель, в которой все зависимости между переменными, характеризующими состояние объекта, предполагаются линейными. Здесь имеется полная аналогия с тем, как весьма важна и зачастую исчерпывающая информация о поведении произвольной функции получается на основе изучения ее производной — происходит замена этой функции в окрестности каждой точки линейной зависимостью. Значительное количество экономических, технических и других процессов достаточно хорошо и полно описывается линейными моделями.
Основные формы задачи ЛП.
Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа.
Стандартная задача ЛП.
или, в матричной записи,
где 
— матрица коэффициентов. Вектор 
называется вектором коэффициентов линейной формы, 
— вектором ограничений.
Стандартная задача важна ввиду наличия большого числа прикладных моделей, сводящихся наиболее естественным образом к этому классу задач ЛП.
Каноническая задача ЛП.
или, в матричной записи,
Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.
Общая задача ЛП.
В этой задачи часть ограничений носит характер неравенств, а часть является уравнениями. Кроме того, не на все переменные наложено условие неотрицательности:
Здесь 
. Ясно, что стандартная задача получается как частный случай общей при 
; каноническая — при 
.
Все три перечисленные задачи эквивалентны в том смысле, что каждую из них можно простыми преобразованиями привести к любой из двух остальных.
При изучении задач ЛП сложилась определенная терминалогия. Линейная форма 
, подлежащая максимизации (или минимизации) , называется целевой функцией. Вектор 
, удовлетворяющий всем ограничениям задачи ЛП, называется допустимым вектором, или планом. Задача ЛП, для которой существуют допустимые векторы, называется допустимой задачей. Допустимый вектор 
, доставляющий наибольшее значение целевой функции по сравнению с любым другим допустимым вектором 
, т.е. 
, называется решением задачи, или оптимальным планом. Максимальное значение 
целевой функции называется значением задачи.
Двойственная задача линейного программирования.
Рассмотрим задачу ЛП
(1)
или, в матричной записи,
(2)
Задачей, двойственной к (1) (двойственной задачей), называется задача ЛП от 
переменных 
вида
(3)
или, в матричной записи,
(4)
где 
.
Правила построения задачи (3) по форме записи задачи (1) таковы: в задаче (3) переменных 
столько же, сколько строк в матрице 
задачи (1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные накладывается условие неотрицательности. Задача (1), в отличии от двойственной задачи (3) называется прямой.
Теорема двойственности. Если взаимодвойственные задачи (2), (4) допустимы, то они обе имеют решение и одинаковое значение.
Теорема равновесия. Пусть 
— оптимальные планы прямой (1) и двойственной (3) задач соответственно. Тогда если 
то
topref.ru
С каждой задачей линейного программирования можно связать некоторую другую задачу, называемой двойственной. Первоначальную задачу при этом называют исходной. Исходная и двойственная ей задачи образуют пару задач, называемую в линейном программировании двойственной парой. Следует заметить, что за исходную задачу можно взять любую задачу из этой пары, для дальнейшего решения это несущественно. Важным свойством присущим любой паре двойственных задач является то, что значения целевых функций оптимальных планов обеих задач равны между собой.
Рассмотрим двойственную задачу в общей постановке.
1. Пусть ограничения исходной задачи имеют вид:
а11х1+а12х2+…+а1nxn ≤ b1
а21х1+а22х2+…+а2nxn ≤ b2
………………………….
am1х1+аm2х2+…+аmnxn ≤ bm
xi ≥ 0, i=1,2,…,n
На множестве решений этой системы требуется максимизировать функцию
F = c1x1+c2x2+…+cnxn.
Двойственной для этой задачи будет задача с ограничениями:
а11z1+а21z2+…+аm1zm ≤ c1
а12z1+а22z2+…+аm2zm ≤ c2
………………………….
a1nz1+а2nz2+…+аmnzn ≤ cn
yi ≥ 0, i=1,2,…,m
и минимизируемой целевой функцией
Fg = b1z1+b2z2+…+bmzm.
Сравнивая обе задачи, нетрудно заметить, что:
1. Матрица из коэффициентов при переменных в исходной задаче
и аналогичная матрица в двойственной задаче
получаются друг из друга простой заменой строк столбцами с сохранением их порядка. Такая операция получила название транспонирования.
2. В исходной задаче n переменных и m ограничений, в двойственной – m переменных
и n ограничений.
3. Каждому i-му ограничению исходной задачи соответствует переменная двойственной задачи (Zi), которую определяют как двойственную переменную. Первому ограничению исходной задачи соответствует двойственная переменная Z1, второму – Z2, ограничению m — Zm.
4. Каждой переменной исходной задачи соответствует ограничение двойственной задачи. В исходной системе n переменных: х1, х2,…, хn. Следовательно, двойственная задача должна иметь n ограничений.
5. В правых частях систем ограничений каждой из задач стоят коэффициенты целевой функции, взятой из другой задачи.
6. В систему ограничений исходной задачи входят неравенства типа ≤, причем в задаче требуется максимизировать целевую функцию F. В систему ограничений двойственной задачи входят неравенства типа ≥.
7. Максимизация целевой функции исходной задачи заменяется минимизацией целевой функции двойственной задачи, при этом:
max F = min Fд (2.23)
Следующая таблица значительно облегчает процесс составления математической модели двойственной задачи.
| x1 | x2 | x3 | …………… | xn | ||
| z1 | a11 | a12 | a13 | …………… | a1n | b1 |
| z2 | a21 | a22 | a23 | …………… | a2n | b2 |
| z3 | a31 | a32 | a33 | …………… | a3n | y3 |
| ………… | ………… | ………… | ………… | …………… | ………… | …………. |
| zm | am1 | am2 | am3 | …………… | amn | bm |
| C1 | C2 | C3 | …………… | Cn | ci bi |
В первой строке таблицы записываются все переменные исходной задачи, в первом столбце записываются все переменные двойственной задачи. В последней строке стоят коэффициенты целевой функции исходной задачи, в последнем столбце — коэффициенты целевой функции двойственной задачи. В прямоугольнике, который получился в результате ограничения указанными строками и столбцами, записаны коэффициенты при переменных исходной задачи – это матрица исходной задачи.
Чтобы получить, например, первое ограничение двойственной задачи, надо найти сумму произведений чисел, стоящих в столбце под х1, на соответствующие переменные первого столбца:
а11z1+a21z2+…+am1zm,
при условии, что эта сумма не меньше с1, т.е:
а11z1+a21z2+…+am1zm ≥ с1.
Аналогично составляются и остальные ограничения для двойственной задачи.
Выражение для целевой функции получается как сумма произведений переменных первого столбца на соответствующие числовые значения последнего столбца.
Если система ограничений исходной задачи на максимум, кроме неравенств типа ≤, содержит неравенства типа ≥, то перед построением двойственной задачи левые и правые части неравенств типа ≥ необходимо умножить на -1. А в задаче на минимум неравенства типа ≤ умножаем на -1. Если в исходной задаче имеются ограничения, заданные равенствами, то каждое из них заменяется двумя ограничениями – неравенствами, а затем в зависимости от типа задач поступают, как было сказано выше.
Рассмотрим на примере, как составляется двойственная задача. Пусть имеется исходная задача:
F = 4x1+5x2+9x3 → max
x1+x2+2x3 ≤ 16 (2.24)
7x1+5x2+3x3 ≤ 25
xj ≥ 0 (j=1,2,3)
Построим для нее двойственную задачу. Из рассмотрения системы ограничений исходной задачи очевидно, что двойственная задача будет содержать две переменных и три ограничения. При определении коэффициентов двойственных переменных будем исходить из того, что они могут быть получены из матрицы, являющейся транспонированной относительно матрицы коэффициентов при переменных исходной задачи.
Матрица коэффициентов исходной задачи:
Следовательно, транспонированная матрица:
Правые части ограничений в двойственной задаче равны коэффициентами при переменных в целевой функции исходной задачи, а коэффициенты при двойственных переменных в целевой функции равны правым частям ограничений исходной задачи.
Таким образом для рассматриваемой исходной задачи (2.24) можно записать двойственную задачу:
Fд = 16z1+25z2 → min
z1+7z2 ≥ 4
z1+5z2 ≥ 5
2z1+3z2 ≥ 9
zi ≥ 0 (i=1,2)
В общем виде можно записать, что исходной задаче:
(2.25)
xj ≥ 0; i=1,…m; j=1,…n
Соответствует двойственная задача:
(2.26)
zi ≥ 0; i=1,…m; j=1,…n
Сформулированное понятие двойственность находит широкое практическое применение. Это, во-первых, связано с упрощением получения решения задачи линейного программирования, которое может быть сведено к решению двойственной задачи. Такое сведение особенно выгодно тогда, когда число ограничений исходной задачи велико и значительно превышает число переменных. Нужно заметить, что объем вычислений в задачах линейного программирования при использовании для решения симплексного метода прежде всего определяется числом ограничений.
Во-вторых, использование двойственных переменных дает возможность оценивать устойчивость оптимального плана, полученного в результате решения задачи линейного программирования. Важность и практическая значимость этого анализа определяют необходимость его детального рассмотрения.
www.ronl.ru
