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

Тема 4.

Для изучения данного раздела дисциплины необходимы знания, полученные при изучении темы 3.

Изучив данную тему, студент должен:

• знать основные положения теории двойственности;
• уметь записывать двойственную задачу для любых постановок исходной задачи;
• иметь общие представления об анализе решения ЗЛП с помощью теории двойственности и анализе решения ЗЛП на основе отчетов MS EXCEL;
• использовать отчеты, полученные с помощью MS Excel, для анализа на чувствительность.

Цель изучения – получить представление о теории двойственности и осознать ее экономическую значимость.

В данном разделе вводится важное понятие теории линейного программирования – понятие двойственности. Двойственная задача – это вспомогательная задача линейного программирования (ЛП), формулируемая с помощью определённых правил непосредственно из условий исходной (прямой) задачи. Часто рассматриваются формулировки двойственной задачи, соответствующие различным формам записи прямой задачи. Однако опыт показывает, что на начальной стадии изучения ЛП детали различных формулировок двойственной задачи нередко затрудняют восприятие материала. Кроме того, практическое использование теории двойственности не требует знания деталей различных формулировок двойственной задачи. Здесь даётся обобщённая формулировка двойственной задачи ЛП, которая применима к любой форме представления прямой задачи. Это объясняется тем, что использование симплексного и других методов решения задач ЛП требует приведения ограничений любой задачи ЛП к стандартной (канонической) форме, поэтому двойственная задача будет сформулирована в соответствии со стандартной формой ограничений прямой задачи.

4.1. Определение и экономический смысл двойственной злп

Пусть прямая задача записана с ограничениями в каноническом виде: ; (4.1) ; (4.2) . (4.3) Задачей, двойственной к ЗЛП (4.1)–(4.3), называется следующая ЗЛП: ; (4.4) ; (4.5) не ограничены в знаке, i = 1… m. (4.6) Двойственная ЗЛП строится по следующим правилам: 1) Каждому ограничению прямой задачи соответствует переменная двойственной задачи, т.е. число переменных двойственной задачи равно числу ограничений прямой задачи. 2) Каждой переменной прямой задачи соответствует ограничение двойственной задачи, т.е. число ограничений двойственной задачи равно числу переменных прямой задачи. 3) Матрица функциональных ограничений двойственной задачи получается путем транспонирования матрицы функциональных ограничений прямой задачи. 4) Вектор целевой функции прямой задачи становится вектором правой части ограничений двойственной задачи, а векторправой части прямой задачи – вектором целевой функции двойственной задачи. 5) Если ЦФ прямой задачи максимизируется, то ЦФ двойственной задачи минимизируется, а ограничения имеют вид ≥, и наоборот.

Прямая задача	Двойственная задача
P =	Q = –не ограничен в знаке	(4.7)
P =	Q = не ограничен в знаке	(4.8)

Пример 4.1. Пусть прямая задача записана в виде основной ЗЛП:

(4.9)

Приведем ограничения задачи (4.9) к канонической форме:

(4.10)

Тогда двойственная задача (ДЗ) будет иметь вид:

.

(4.11)

Пример 4.2. Прямая задача: Прямая задача с ограничениями в канонической форме: S₁ ≥ 0 Двойственная задача: y_1,2 не ограничены в знаке. Ограничение , т.е., является более жестким, чем условие неограниченностиу₁ в знаке, поэтому двойственная задача может быть записана в следующем виде: у₂ не ограничена в знаке. Пример 4.3. Прямая задача: min(5X₁ – 2X₂); –X₁ + X₂ ≥ –3; 2X₁ + 3X₂ ≤ 5; X_1,2 ≥ 0. Прямая задача с ограничениями в канонической форме: min(5X₁ – 2X₂ + 0S₁ + 0S₂); –X₁ + X₂ – S₁ = –3; 2X₁ + 3X₂ + S₂ = 5; Двойственная задача: max(–3У₁ + 5У₂); –У₁ + 2У₂ ≤ 5; У₁ + 3У₂ ≤ –2; –У₁ + 0У₂ ≤ 0; 0У₁ + У₂ ≤ 0. У_1,2 не ограничены в знаке. Отбрасывая избыточные ограничения, получаем: max(–3У₁ + 5У₂); –У₁ + 2У₂ ≤ 5; У₁ + 3У₂ ≤ –2; У₁ ≥ 0, У₂ ≤ 0. Пример 4.4. Прямая задача: max(5X₁ + 6X₂); X₁ + 2X₂ = 5; –X₁ + 5X₂ ≥ 3; 4X₁ + 7X₂ ≤ 8. X₁ не ограничена в знаке, X₂ ≥ 0. Прямая задача с ограничениями в канонической форме: max(5– 5 + 6X₂ + 0S₁ + 0S₂); + 2X₂ = 5; + 5X₂ – S₁ = 3; 4 + 7X₂ + S₂ = 8; Двойственная задача: min(5У₁ + 3У₂ + 8У₃); У₁ – У₂ + 4У₃ ≥ 5; –У₁ + У₂ – 4У₃ ≥ –5; 2У₁ + 5У₂ + 7У₃ ≥ 6; 0У₁ – У₂ + 0У₃ ≥ 0; 0У₁ + 0У₂ + У₃ ≥ 0. У_1,2,3 не ограничены в знаке. Заметим, что первое и второе ограничения двойственной задачи можно заменить одним ограничением в виде равенства, избыточные ограничения на У₂ и У₃ можно отбросить. В итоге получаем: min(5У₁ + 3У₂ + 8У₃); У₁ – У₂ + 4У₃ = 5; 2У₁ + 5У₂ + 7У₃ ≥ 6; У₁ не ограничена в знаке; У₂ ≤ 0, У₃ ≥ 0. Очевидно, что задача, двойственная к двойственной, совпадает с прямой.

Источник

5. Двойственная задача линейного программирования. Экономическая интерпретация двойственной задачи линейного программирования.

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

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

На основе тех же исходных данных может быть поставлена еще одна задача:

Сопоставим обе задачи. Первая из них — задача на максимум, вторая — задача на минимум; в соответствии с этим изменился и характер ограничений (знак неравенств). В первой задаче n неизвестных и k ограничений, во второй — k неизвестны х и n ограничений. Коэффициенты в целевых функциях и величины в правых частях неравенств при переходе от одной задачи к другой меняются местами. Кроме того, при этом переходе транспонируется матрица ограничений А.

Обе задачи образуют двойственную пару задач. Первую из них называют прямой задачей, а вторую —двoйсmвeннoй.

Общие правила построения двойственной задачи:

1) каждому ограничению исходной задачи соответствует двойственная переменная;

2) матрицы ограничений взаимно транспонированы;

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

4) каждому ограничению-неравенству исходной задачи соответствует в двойственной задаче условие неотрицательности соответствующей двойственной переменной, а равенству — произвольная двойственная переменная.

В линейном программировании доказывается следующая основная теорема двойственности.

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

1.5.1. Экономическая интерпретация двойственной задачи

Для экономической интерпретации двойственной задачи будем полагать, например, что прямая задача — задача распределения ресурсов. Предположим, что в производстве используется kразличных видов ресурсов, объем которых ограничен величинамиb_i. Может производитьсяnвидов продукции, величина выпуска которых характеризуется переменнымих_i. Известны нормы затрат каждого ресурса на единицу каждого вида продукции —а_ij,а также стоимостная оценка единицы продукции —с_j.

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

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

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

Теорема 1.9.Пусть x_i*. х_n* и у₁*. y_k* — оптимальные планы двойственных задач. Тогда

1.Если a_i1,x_i* +. +а_inх_n* i(i), то у_i* = 0.

2. Если уi* >0 (i),то a_i1x₁* +. +а_inх_n* =b_i

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

З.Если а_1jy₁* +. +a_kjy_k* >с_j(j),то х_j*=0.

4.Если х_j* > 0 (j),то а_1jу₁* +. + a_kjy_k* =с_j.

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

Источник

2.7. Двойственная задача линейного программирования. Экономическая интерпретация

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

(2.7.1)

(2.7.2)

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

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

(2.7.3)

(2.7.4)

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

Задачи (2.7.1), (2.7.2) и (2.7.3), (2.7.4) называются парой взаимно двойственных задач линейного программирования.

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

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

Поясним экономический смысл двойственной модели.

Пусть в качестве управляющих переменных исходной модели рассматривается число изделий, производимых некоторым предприятием, а параметрами – количество ресурсов -го типа, используемых для изготовления изделий. Через обозначено количество ресурсов -го типа, идущее на изготовление одного изделия-го вида, (– прибыль от реализации одного изделия-го вида). Тогда исходная модель (2.7.1), (2.7.2) соответствует задаче определения оптимального плана производства продукции, обеспечивающего максимальную прибыль.

Пусть предприятие решило прекратить производство изделий и продать ресурсы, идущие на их изготовление. Обозначим через цены на единицу ресурсов -го вида,. Цены на ресурсы должны удовлетворять следующим двум условиям: во-первых, они не должны быть слишком высокими, иначе ресурсы невозможно будет продать; а во-вторых, цены на ресурсы должны быть такими, чтобы прибыль от их реализации была больше прибыли от реализации готовой продукции. Первое условие выражается формулой (2.7.3), второе условие – ограничениями (2.7.4). В левой части каждого из неравенств (2.7.4) стоит прибыль от продажи ресурсов всех типов, идущих на изготовление-го изделия, в правой части – прибыль от продажи-го изделия,. Таким образом, двойственная задача (2.7.3) – (2.7.4) соответствует следующей экономической проблеме: по каким минимальным ценам следует продавать ресурсы, чтобы прибыль от их реализации была больше прибыли, полученной от реализации продукции, изготавливаемой с использованием этих ресурсов. Значения переменных часто называют теневыми ценами.

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

Источник