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

ДВОЙСТВЕННАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ЕСЛЯМ А.

Студентка группы Лог-12

ИГИЛИК С.И.

Научный руководитель, магистр

Карагандинский экономический университет Казпотребсоюза,

г.Караганда, Республика Казахстан

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

Ключевые слова. Двойственная задача, анализ, линейное программирование, математическая модель.

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

Математическая модель задачи:
         Определим максимальное значение целевой функции  = 8+6 при нижеприведённых условиях-ограничений:
[pic 1][pic 2][pic 3][pic 4]

         Вводя дополнительные переменные (переход к канонической форме), приведем систему неравенств к системе уравнений, чтобы построить первый опорный план:
[pic 5]

      Что касается основных переменных, мы решаем систему уравнений: ,  
Предполагая, что свободные переменные равны 0, получаем первый опорный план: 
 = (0,0,19,16) [pic 6][pic 7][pic 8]

Таблица 1. Опорный план №1.

         Перейдем к основному алгоритму симплекс-метода. 
         Нынешний опорный план является неоптимальным, так как в индексной строке находятся отрицательные коэффициенты. 
         В качестве разрешающего выберем столбец, который соответствует переменной , поскольку это наибольший коэффициент по модулю. 
         Вычислим значения по строкам как частное от деления:  . Из них выберем наименьшее:
         Таким образом, 2-ая строка является разрешающей. Разрешающий элемент равен (4) и расположен на пересечении разрешающих столбца и строки. [pic 16][pic 17][pic 18][pic 19]