с 01.09.2017 по настоящее время Ростов-на-Дону, Ростовская область, Россия
УДК 51 Математика
ГРНТИ 27.01 Общие вопросы математики
ОКСО 01.04.01 Математика
ББК 221 Математика
ТБК 611 Математика
В данной статье приводится анализ одновременного процесса решения пары прямой и двойственной задач; со стороны возможного и потенциального применения предоставляется разбор необходимости формирование и составления задачи. На основе прямой (исходной задачи) проводится исследование построения и последующего нахождения решения двойственной задачи.
двойственная задача, линейное программирование, прямая задача, теорема двойственности, графический метод, нормаль, линии уровня, оптимальное решение, система ограничений, строгое неравенство
Двойственная задача, формулируемая согласно определенным правилам из условий исходной задачи в стандартной форме, представляет собой некоторую сопоставимую задачу прямой (исходной) задаче линейного программирования; она является неким дополнительным, вспомогательным компонентом. Взаимозависимость между задачами двойственной пары заключена в том, что решение одной из пары задач может быть произведено из решения другой.
Одновременный процесс поиска решение прямой и двойственной задач основан на применении теорем двойственности, которые допускают определение взаимообусловленности между оптимальными решениями двойственных задач [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. Александров Д.Г., Громыко В.В., Журавлева Г.П. Экономическая теория: макроэкономика -1, 2, метаэкономика, экономика трансформаций: учеб/ под общ. ред. Г.П. Журавлевой.- Москва: Издательско-торговая корпорация «Дашков и К°», 2016. - 919 с.
2. Болотникова О.В. Линейное программирование: симплекс - метод и двойственность: учеб. пособие / О.В. Болотникова, Д.В. Тарасов, Р.В. Тарасов. - Пенза: Изд-во ПГУ, 2015. -84 с.
3. Колемаев В. А. Математическая экономика: учебник. - Москва: Юнити-Дана, 2015. - 399 с.
4. Кундышева Е. С. Математика: Учебник для экономистов/ Е.С.Кундышева. - 4-е изд. - М.; Изадательско - торговая корпорация «Дашков и К°», 2015. - 564 с.
5. Мокриевич, А.Г. М74 Основы линейного программирования: учебное пособие для самостоятельной работы / А.Г. Мокриевич, С.Ю. Бакоев. - пос. Персиановский: Донской ГАУ, 2015. - 106 с.
6. Орлова И.В., Тармаш А.Н., Федосеев В.В. Экономико-математические методы и прикладные модели: учебное пособие. - Москва: Юнити-Дана, 2015. - 302 с.
7. Шандра И. Г. Математическая экономика: учебник для студентов бакалавриата и магистратуры экономических вузов и факультетов. - Москва: Прометей, 2018. - 176 с.
