student from 01.09.2017 until now
Rostov-na-Donu, Rostov-on-Don, Russian Federation
UDK 51 Математика
GRNTI 27.01 Общие вопросы математики
OKSO 01.04.01 Математика
BBK 221 Математика
TBK 611 Математика
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
dual problem, linear programming, direct problem, duality theorem, graphical method, normal, level lines, optimal solution, constraint system, strict inequality
Двойственная задача, формулируемая согласно определенным правилам из условий исходной задачи в стандартной форме, представляет собой некоторую сопоставимую задачу прямой (исходной) задаче линейного программирования; она является неким дополнительным, вспомогательным компонентом. Взаимозависимость между задачами двойственной пары заключена в том, что решение одной из пары задач может быть произведено из решения другой.
Одновременный процесс поиска решение прямой и двойственной задач основан на применении теорем двойственности, которые допускают определение взаимообусловленности между оптимальными решениями двойственных задач [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* = L3L4,
+{█(-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. 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.
