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

Размещено на http://www.allbest.ru/

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

План

1. Постановка и модель двойственной задачи

2. Методы решения

3. Теоремы теории двойственности и ее экономическое содержание

1. Постановка и модель двойственной задачи

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

Напомним, что в основе задачи линейного программирования рассматривается предприятие, имеющее ресурсы b_i, где i = 1, 2, …, m. Оно тратит их на изготовление готовой продукции и эту продукцию реализует. При этом ставится цель - получить максимум продукции в стоимостном выражении не перерасходуя ресурсы. Модель задачи выглядит следующим образом: двойственный симплекс линейный программирование

I) Ж = с₁х₁ + с₂х₂ + … + с_nх_n max.

II) a₁₁х₁ + а₁₂х₂ + … + а_1nх_n ? b₁,

a₂₁х₁ + а₂₂х₂ + … + а_2nх_n ? b₂,

………………………………

a_m1х₁ + а_m2х₂ + … + а_mnх_n ? b_m.

III) х_j ? 0, j = 1, 2, …, n.

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

Тогда, в так называемой двойственной модели, целевая функция будет описывать интерес покупающей стороны, система ограничений - интерес продающей стороны (необходимо оценить ресурсы, которые пошли бы на изготовление единицы продукции и стоимость этих ресурсов ограничить ценой реализованной единицы продукции). Третье условие (неотрицательность переменных величин) будет выполняться в силу того, что цена единицы ресурса не может быть отрицательной. Введя в качестве цены единицы ресурса величину u_i0 (i = 1, 2, …, m), ее еще называют оценкой ресурса (или двойственной оценкой), получим следующую модель:

I) F = b₁u₁ + b₂u₂ + … + b_mu_m min.

II) a₁₁u₁ + a₂₁u₂ + … + a_m1u_m c₁,

a₁₂u₁ + a₂₂u₂ + … + a_m2u_m c₂,

………………………………

a_1nu₁ + a_2nu₂ + … + a_mnu_m c_n.

III) u_i 0, i = 1, 2, …, m.

Сопоставим обе задачи:

- первая - задача на максимум (zmax), вторая - на минимум (Fmin);

- в первой система ограничений типа , во второй ;

- в первой задаче n неизвестных и m ограничений, во второй m неизвестных и n ограничений;

- коэффициенты в целевых функциях и величины в правых частях неравенств при переходе из одной задачи в другую меняются местами (в первой задаче c_j - коэффициенты целевой функции, во второй c_j - свободные члены; в первой задаче b_i - свободные члены, во второй b_i - коэффициенты целевой функции);

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

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

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

1) тип экстремума целевой функции меняется;

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

3) свободные члены исходной задачи становятся коэффициентами при переменных в целевой функции двойственной задачи;

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

Рассмотрим конкретный пример построения двойственной модели:

исходная задача:

I) Z = 6x₁ + 4x₂ max.

II) 2x₁ +4x₂ ? 8,

2x₁ +x₂ ? 6.

III) x₁ ? 0, x₂ ? 0.

двойственная задача:

I) F = 8u₁ + 6u₂ min.

II) 2u₁ + 2u₂ ? 6,

4u₁ + u₂ ? 4.

III) u₁ ? 0, u₂ ? 0.

Следует отметить, что:

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

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

2. Методы решения

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

Подготовленные для записи в симплекс таблицу модели будут выглядеть следующим образом:

исходная задача (введем y_i 0):

I) Ж = с₁х₁ + с₂х₂ + … + с_nх_n max.

II) y₁ = -a₁₁х₁ - а₁₂х₂ - … - а_1nх_n + b₁,

y₂ = -a₂₁х₁ - а₂₂х₂ - … - а_2nх_n + b₂,

…………………………………..

y_m = -a_m1х₁ - а_m2х₂ - … - а_mnх_n + b_m.

III) х_j ? 0, j = 1, 2, …, n.

двойственная задача (введем v_j 0):

I) F = b₁u₁ + b₂u₂ + … + b_mu_m min.

II) v₁ = a₁₁u₁ + a₂₁u₂ + … + a_m1u_m - c₁,

v₂ = a₁₂u₁ + a₂₂u₂ + … + a_m2u_m - c₂,

……………………………………

v_n = a_1nu₁ + a_2nu₂ + … + a_mnu_m - c_n.

III) u_i 0, i = 1, 2, …, m.

Обе модели записываются в двойственную симплекс-таблицу следующим образом (таблица 4):

Таблица 4 - Двойственная симплексная таблица

Замечания:

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

- прежде чем составлять модель двойственной задачи, необходимо у исходной модели «выровнять» знаки, т.е. если целевая функция стремится к max, то все знаки в системе ограничений должны быть ?, а если к min, то ?. Система приводится в соответствие путем домножения обеих частей «неподходящего» неравенства на (-1). Например, чтобы записать модель, двойственную к приведенной модели

I) Z = 4x₁ + 2x₂ + 3x₃ min.

II) -4x₁ - 3x₂ +x₃ ? -4,

5x₁ + x₂+2x₃ ? 6.

III) x₁ ? 0, x₂ ? 0, x₃ ? 0,

необходимо исходную переписать в виде:

I) Z = 4x₁ + 2x₂ + 3x₃ min.

II) 4x₁ + 3x₂ - x₃ ? 4,

5x₁ + x₂+2x₃ ? 6.

III) x₁ ? 0, x₂ ? 0, x₃ ? 0.

Тогда двойственная задача будет выглядеть так:

I) F = 4u₁+6u₂ max.

II) 4u₁ + 5u₂ ? 4,

3u₁ + u₂ ? 2,

-u₁ + 2u₂ ? 3.

III) u₁ ? 0; u₂ ? 0;

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

3. Основные теоремы теории двойственности и ее экономическое содержание

В качестве основной теоремы двойственности выделяют следующую формулировку: если одна из взаимно двойственных задач имеет оптимальное решение, то и другая также имеет оптимальное решение, при этом соответствующие им оптимальные значения целевых функций равны (т.е. max z = min F).

Кроме этого варианта возможны следующие взаимоисключающие случаи:

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

- обе из рассматриваемых задач имеют пустые допустимые множества (т.е. обе не имеют решения).

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

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

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

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

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

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

- абсолютные значения оценок можно трактовать как некоторые расчетные «цены» ресурсов и потребностей, выраженные в тех же единицах, что и критерий, а знак «+» или «-» при этих «ценах» показывает, ведет ли увеличение данного фактора к возрастанию или уменьшению значения критерия;

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

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

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

Размещено на Allbest.ru