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

Ключевые слова:
двойственная задача, линейное программирование, прямая задача, теорема двойственности, графический метод, нормаль, линии уровня, оптимальное решение, система ограничений, строгое неравенство
Текст
Текст произведения (PDF): Читать Скачать

Двойственная задача, формулируемая  согласно  определенным правилам  из условий исходной задачи в стандартной форме, представляет собой некоторую сопоставимую задачу прямой (исходной) задаче линейного программирования; она является неким дополнительным, вспомогательным компонентом.  Взаимозависимость между задачами двойственной пары заключена в том, что решение одной из пары задач может быть произведено из решения другой.  
    Одновременный процесс поиска решение прямой и двойственной задач основан на применении теорем двойственности, которые допускают определение  взаимообусловленности  между оптимальными решениями двойственных задач [5, с.50]. Оптимальное решение одной из пары задач, или же его отсутствие,  возможно получить путем решения другой  задачи.
Приведем возможные ситуации, отражающие вариации решения исследуемой  пары задач: 
    1) оптимальным решением обладают обе задачи из пары двойственных;
    2) ввиду неограниченности целевой функции одна из пары задач не имеет решения, а другая не имеет решения вследствие несовместимости системы ограничений [2, с.48].
    Ознакомимся со следующими теоремами двойственности, базируясь на которых и построен алгоритм одновременного решения прямой и сопряженной ей задач:
-  1- я теорема двойственности. Одна из задач двойственной пары разрешима, что делает разрешимой и вторую задачу, причем оптимальные значения обеих целевых функций схожи. Если же целевая функция одной из задач не ограничена (сверху – для задачи максимизации, а  снизу  - для задачи минимизации), то в данном случае множество допустимых планов другой задачи пусто.
- 2-я теорема двойственности. Предположим, предложена для рассмотрения симметричная пара двойственных задач:

Z(X)=∑_(j=1)^n▒c_j  x_j              max,
∑_(j=1)^n▒〖a_ij x_j 〗  bi ,i = 1,2,…,m,    F(Y)=∑_(i=1)^m▒b_i  y_i              min,
∑_(i=1)^m▒〖a_ij y_i 〗  c j, j = 1,2,…,n,

x j  0, j = 1,2,…,n; y i  0, i = 1,2,…,m.

    С целью того, чтобы X=(x1,x2,…,xn), Y=(y1,y2,…,ym), как допустимые решения, существовали оптимальными решениями пары двойственных задач, необходимым и достаточным является выполнение следующих равенств:
    xj (∑_(i=1)^m▒〖a_ij y_i-c_j 〗) = 0, j = 1,2,…,n;

    yj (∑_(j=1)^n▒a_ij  x_j-b_i )= 0, i = 1,2,…,m.

    Таким образом, если i-е ограничение прямой задачи реализуется как строгое неравенство при подстановке рационального решения в систему ограничений, то i-я координата оптимального решения двойственной задачи равна нулю, и, наоборот, если i-я координата оптимального решения двойственной задачи от нуля отлична, то i-е ограничение прямой задачи удовлетворимо оптимальным решением как равенство.
    Приведем и проанализируем практический пример, основанный на потребности предприятия по выпуску садовой мебели минимизировать некоторые затраты своей производственной деятельности с целью наиболее наглядного представления, формирования понятия  составления и разрешения двойственной задачи.
    Условие: организация по изготовлению и продаже садовой мебели нуждается в некоторых ресурсах для их эксплуатации в производственном цикле своей экономической деятельности. Расходы ресурсов на фабрикацию каждого вида изделия, прибыль от продажи одного готового мебельного  продукта  и итоговое суммарное количество имеющихся на предприятии товаров, готовых к продаже, отражены в таблице, где положительное кол-во изделий – произведенная и готовая к реализации продукция, а отрицательное – списанные со «счета» организации изделия по причине производственного брака:
Вид мебели садовой    Затраты на изготовление одного мебельного изделия    Общее
кол-во изделий(шт.)
    Древесина (куб.м)    Металлические вставки (шт.)    Краска (л.)    Декоративные элементы (пачки)    
Кресло плетеное    4    2    -1    1    1
Стол обеденный    2    -1    -1    2    -2
Затраты на изготовление одного вида изделия
(тыс.ден.ед.)    24    8    -4    2    

    Предприятию необходимо  составление и последующее и осуществление такого плана производства и  продажи садовой мебели, при котором допустимо было бы сведение производственных затрат к минимальному значению.
Итак, сначала необходимо составить математическую модель задачи:
Z(X)=24x_1+8x_2-4x_3+2x_4→min;       
{█(      4x_1+2x_2-x_3+x_4=1 |y_1 ┤; @  3x_1+x_2-x_3-x_4=-2|y_2 ┤;)┤
xj 0, j=1,2,3,4.
Решение. Составим двойственную задачу для исходной
F(Y)=y_1-2y_2→max;
{█(4y_1+3y_2≤24;   (1)@2y_1+y_2≤8;      (2) @〖-y〗_1-y_2≤-4;   (3)@y_1-y_2≤2.   (4))┤
Решение задачи получим путем ее решения графическим методом. Рис.1 демонстрирует область допустимых решений задачи, нормаль n=(1,-2) линий уровня, линии уровня и оптимальное решение задачи Y* = (3,1).

    Y* = L3L4,
    +{█(-y_1-y_2=-4,   (L3);@y_1-y_2=2,   (L4);)┤
    -2y2=-2
    Y2=1, y1=3;
    Y* = (3, 1)
    F(Y*) = 3-2*1=1.
    Y* = (3, 1),  как оптимальное решение задачи, подставим в данную систему ограничений, и  получим, что как строгие неравенства выполняются  (1) и (4) ограничения системы:
{█(4*3+3*1<24→x_1=0;@2*3+1<8→x_2=0;                       @-3-1=-4                  @3-1=2.                             )┤
     Взаимосоответствующие координаты оптимального решения двойственной, т.е. исходной задачи, по второй теореме двойственности,  равны нулю: x1=x2=0, что следует из решения. Учитывая полученные значения, из системы ограничений исходной задачи  получим величины остальных искомых переменных:
    +{█(-x_3+x_4=1,@-x_3-x_4=-2)┤

    -2x3=-1;
    x3 =1/2, x4=3/2; X*=(0,0,1/2,3/2).
    Ответ: min Z(X)= 1тыс.ден.ед. при X*=(0,0,1/2,3/2). Тогда организация по производству садовой мебели организовала минимизированную структуру своих производственных издержек, что в денежном эквиваленте составило1 тысячу денежных единиц.
    Подводя итог, можно убедиться, что нахождение решения двойственной задачи позволяет определить, оптимально ли данное допустимое решение задачи ЛП без «свободного» сопоставления его с другими допустимыми решениями. 
    Нельзя не обратить внимание на тот факт, что двойственная задача , которая, казалось бы, имеет большее отношение к математической тематике, наряду со многими производственными функциями, макро- и микроэкономическими показателями, является актуальным методом, используемым в экономической теории; как показал практический пример, двойственная задача способствует разрешению производственных проблем, с которыми сталкивается ряд экономических агентов в своей хозяйственной деятельности, ведь такие вопросы, как максимизация прибыли от реализации продукции и минимизация при этом каких-либо затрат и издержек остаются наиболее востребованными среди широкого круга производителей. 
 

Список литературы

1. Александров Д.Г., Громыко В.В., Журавлева Г.П. Экономическая теория: макроэкономика -1, 2, метаэкономика, экономика трансформаций: учеб/ под общ. ред. Г.П. Журавлевой.- Москва: Издательско-торговая корпорация «Дашков и К°», 2016. – 919 с.

2. Болотникова О.В. Линейное программирование: симплекс – метод и двойственность: учеб. пособие / О.В. Болотникова, Д.В. Тарасов, Р.В. Тарасов. – Пенза: Изд-во ПГУ, 2015. -84 с.

3. Колемаев В. А. Математическая экономика: учебник. - Москва: Юнити-Дана, 2015. – 399 с.

4. Кундышева Е. С. Математика: Учебник для экономистов/ Е.С.Кундышева. – 4-е изд. – М.; Изадательско - торговая корпорация «Дашков и К°», 2015. ‒ 564 с.

5. Мокриевич, А.Г. М74 Основы линейного программирования: учебное пособие для самостоятельной работы / А.Г. Мокриевич, С.Ю. Бакоев. – пос. Персиановский: Донской ГАУ, 2015. – 106 с.

6. Орлова И.В., Тармаш А.Н., Федосеев В.В. Экономико-математические методы и прикладные модели: учебное пособие. - Москва: Юнити-Дана, 2015. – 302 с.

7. Шандра И. Г. Математическая экономика: учебник для студентов бакалавриата и магистратуры экономических вузов и факультетов. - Москва: Прометей, 2018. – 176 с.

Войти или Создать
* Забыли пароль?