Abstract and keywords
Abstract (English):
This article provides an analysis of the simultaneous process of solving a pair of direct and dual problems; on the part of the possible and potential use, an analysis is given of the need for a task. On the basis of the direct (initial problem), a study is carried out to construct and then find a solution to the dual problem.1

Keywords:
dual problem, linear programming, direct problem, duality theorem, graphical method, normal, level lines, optimal solution, constraint system, strict inequality
Text
Publication text (PDF): Read Download

Двойственная задача, формулируемая  согласно  определенным правилам  из условий исходной задачи в стандартной форме, представляет собой некоторую сопоставимую задачу прямой (исходной) задаче линейного программирования; она является неким дополнительным, вспомогательным компонентом.  Взаимозависимость между задачами двойственной пары заключена в том, что решение одной из пары задач может быть произведено из решения другой.  
    Одновременный процесс поиска решение прямой и двойственной задач основан на применении теорем двойственности, которые допускают определение  взаимообусловленности  между оптимальными решениями двойственных задач [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 тысячу денежных единиц.
    Подводя итог, можно убедиться, что нахождение решения двойственной задачи позволяет определить, оптимально ли данное допустимое решение задачи ЛП без «свободного» сопоставления его с другими допустимыми решениями. 
    Нельзя не обратить внимание на тот факт, что двойственная задача , которая, казалось бы, имеет большее отношение к математической тематике, наряду со многими производственными функциями, макро- и микроэкономическими показателями, является актуальным методом, используемым в экономической теории; как показал практический пример, двойственная задача способствует разрешению производственных проблем, с которыми сталкивается ряд экономических агентов в своей хозяйственной деятельности, ведь такие вопросы, как максимизация прибыли от реализации продукции и минимизация при этом каких-либо затрат и издержек остаются наиболее востребованными среди широкого круга производителей. 
 

References

1. Alexandrov D.G., Gromyko V.V., Zhuravlev G.P. Economic theory: macroeconomic-1, 2, metaeconomy, economy of transformations: studies / under a general edition of G.P. Zhuravleva. - Moscow: Publishing and trade corporation "Dashkov and Co", 2016. - 919 pages.

2. Bolotnikova O.V., Linear programming: simplex - method and duality: studies. manual / O.V. Bolotnikova, D.V. Tarasov, R.V. Tarasov. - Penza: PGU Publishing House, 2015. -84 p.

3. Kolemayev V. A. Mathematical methods and models of a research of operations: textbook. - Moscow: Unity Dana, 2015. - 592 pages.

4. Kundysheva E.S. Mathematics: A Textbook for Economists / E.S. Kundysheva. - 4th ed. - M .; Izadatelsko - trade corporation "Dashkov and K °", 2015. - 564 p.

5. Mokrievich, A.G. M74 Fundamentals of linear programming: a manual for independent work / A.G. Mokrievich, S.Yu. Bakoev - pos. Persianovsky: Donskoy State Agrarian University, 2015. - 106 p.

6. Orlova I.V., Tarmash A.N., Fedoseyev V.V. Economic-mathematical methods and application models: manual. - Moscow: Unity Dana, 2015. - 302 pages.

7. Shandra I. G. Mathematical economy: the textbook for students of a bachelor degree and magistracy of economic higher education institutions and faculties. - Moscow: Prometheus, 2018. - 176 pages.

Login or Create
* Forgot password?