Анализ решения задачи планирования сборки изделий ПКФ «Альтаир» на основе теории двойственности

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

     Задачей линейного программирования (ЗЛП) называется задача отыскания экстремума (максимума или минимума) линейной функции от нескольких переменных при линейных ограничениях на эти переменные.

В общем виде задача линейного программирования выглядит так:

F=c1x1+c2x2+ … +сnхnmin (max)-целевая функция                (1.1)

     Целевая функция в математическом виде выражает критерий оптимальности, то есть служит для выбора  наилучшего решения. Если используется максимизируемый критерий оптимальности (например, прибыль от производства продукции), то целевая функция стремится к максимуму. Если же в качестве критерия оптимальности выступают затраты (например, на кормление коров), то целевая функция стремится к минимуму.

     Система ограничений:

а11х1+а12х2+ …+а1nхn{, =, }b1

а21 х1+а22х2+ …+а2nхn{, =, }b2

                               ………                                                                                                                                                                                                                                        (1.2)

аm1х1+аm2x2+ …+аmnхn{, =, }bm;

xj>=0,(i=1…n) ;                                                 (1.3)

где

     аij, bi , cj –заданные постоянные величины;

      m – число уравнений, n – число переменных.

      Система ограничений вытекает из ограниченности материальных, трудовых ресурсов, технологических требований или же из здравого смысла. Например, для задачи планирования производства продукции ограничения вытекают из ограниченности на предприятии  материальных и трудовых ресурсов, используемых для производства этой продукции. Для задачи составления рациона ограничения заключаются в необходимости того, чтобы рацион был полноценным (содержал питательные вещества, витамины и микроэлементы, необходимые для жизнедеятельности коров).

     Ограничения (1.3) с математической точки зрения являются необязательными, но в моделях экономических задач они, как правило, всегда присутствуют. Это связано с экономическим смыслом переменных х1, х2, …, хn. Например, если под xi понимается количество продукции вида i, которое необходимо выпускать на предприятии, то очевидно, что оно не может быть отрицательным.

     Систему ограничений (1.2) называют функциональными ограничениями, а ограничения (1.3) – прямыми. Вместе ограничения (1.2) и (1.3) определяют область допустимых решений.

     Набор значений переменных х1, х2,…,хn, при котором выполняются все ограничения, называется допустимым решением или планом. Допустимое решение, при котором функция F принимает оптимальное значение, называется оптимальным.

     Каноническая форма записи. Задача линейного программирования в канонической форме должна удовлетворять следующие условия:

1.      минимизация целевой функции F равносильно максимизации целевой функции (-F). Так, если целевая функция исходной задачи исследуется на минимум, то есть F min, то можно рассматривать функцию с противоположным знаком, которая будет стремится к максимуму (max): - F (max);

2.   ограничения- неравенства вида  аi1х1+аi2х2+ …+аinхn< =bi преобразуются в ограничения – равенства путем прибавление к левым частям дополнительных переменных(балансовых) неотрицательных переменных хn+i>=0: аi1х1+аi2х2+ …+аinхn+ хn+i  =bi ,    i= ;

3.      ограничения- неравенства вида  аi1х1+аi2х2+ …+аinхn> =bi преобразуются в ограничения – равенства путем вычитания от левых частей дополнительных переменных(балансовых) неотрицательных переменных хn+i>=0: аi1х1+аi2х2+ …+аinхn+ хn+i  =bi , i=m1+1, m2 ;

4.      дополнительные переменных в целевую функцию вводятся с коэффициентами, равными нулю:cn+i=0,  i=1, m2;

5.      переменные любого знака заменяются разностью двух других неотрицательных переменных:xj=x1j-x2j, где x1j>=0, x2j>=0;

     В общем виде каноническая форма записи выглядит так:  

Равенства с ограничением вида <=:

F=c1x1+c2x2+ … +сnхnmin (max)-целевая функция                   (1.4)

а11х1+а12х2+ …+а1nхn+y 1n =b1

а21 х1+а22х2+ …+а2nхn+y2n =b2

         ………                                                                                                                                                                              (1.5)

аm1х1+аm2x2+ …+аmnхn+ymn =bm;

xj>=0,(i=1…n);                                                            (1.6)

где

       аij, bi , cj –заданные постоянные величины;

        m – число уравнений, n – число переменных;

        yj  - дополнительная переменная.

Равенства с ограничением вида ( >=):

F=c1x1+c2x2+ … +сnхnmin (max)-целевая функция         (1.7)

а11х1+а12х2+ …+а1nхn-y 1n =b1

а21 х1+а22х2+ …+а2nхn-y2n =b2

………                                                                                  (1.8)

аm1х1+аm2x2+ …+аmnхn-ymn =bm;

xj>=0, (i=1…n)                                                            (1.9) 

где

      аij, bi , cj –заданные постоянные величины;

        m – число уравнений;

   n – число переменных;

  yj  - дополнительная переменная.

     С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача при этом называется исходной, или прямой. Связь этих задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой (табл. 1.1).

Таблица 1.1 Двойственная задача

     Эта задача составляется по следующим правилам:

1.      поскольку исходная задача составляется на максимум, то двойственная - на минимум целевой функции;

2.      в исходной задаче ограничения имеют знаки неравенств «», а в двойственной – «»;

3.      каждому ограничению исходной задачи соответствует переменная двойственной задачи, а каждой переменной исходной задачи - ограничение двойственной задачи;

4.      матрица системы ограничений двойственной задачи является транспонированной матрицей системы ограничений исходной задачи;

5.      правые части ограничений в двойственной задаче равны коэффициентам при переменных в целевой функции исходной задачи;

6.      коэффициенты при переменных в целевой функции двойственной задачи равны правым частям ограничений исходной задачи;

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

     Экономический смысл двойственной задачи рассмотрим на примере. Допустим, что у предприятия есть возможность реализации всех ресурсов некоторой организации вместо того, чтобы организовывать свое производство. Необходимо установить прикидочные цены на ресурсы. Обозначим эти цены как z1, z2, …, zm. Они должны быть установлены исходя из несовпадающих интересов предприятия и покупающей организации.

     1-я теорема двойственности. Если существует единственное решение исходной задачи, то существует и единственное решение двойственной задачи, причем значения целевых функций на оптимальных решениях совпадают: max F = min FД.

     Эту теорему можно интерпретировать так: предприятию безразлично, производить ли продукцию по оптимальному плану X* и получить максимальную прибыль либо продать ресурсы по оптимальным ценам Z* и получить такую же сумму. Для всех других (неоптимальных) планов X и Z прибыль от выпуска продукции всегда меньше внутренней стоимости затраченных ресурсов. Таким образом, F < FД, а величина FД – F характеризует производственные потери.

     Следствие (теорема об оценках). Двойственная оценка zi* (теневая цена) показывает, как изменится целевая функция исходной задачи при изменении ресурса bi на одну единицу:  F = bizi*.

    Таким образом, по теневым ценам можно судить о том, насколько целесообразно изыскивать резервы для увеличения количества i-го ресурса: если соответствующая теневая цена равна нулю, то увеличение количества этого ресурса никак не повлияет на рост прибыли. С другой стороны, чем больше теневая цена ресурса, тем больше увеличится прибыль при увеличении количества этого ресурса на одну единицу. Поэтому тот ресурс, который имеет большую теневую цену, считается более дефицитным.

Однако эта теорема справедлива только тогда, когда при изменении количества ресурса bi значения переменных zi* в оптимальном плане двойственной задачи остаются неизменными. В отчете Excel
по устойчивости можно получить границы изменения bi (b– и b+),
в пределах которых теневая цена есть коэффициент увеличения (уменьшения) целевой функции исходной задачи при изменении доступного количества ресурсов.

     2-я теорема двойственности (теорема о дополняющей нежесткости). Оптимальные решения исходной и двойственной задач связаны соотношениями: zi*  yi* = 0, vj*  xj* = 0.

     Эта теорема означает, что между переменными исходной и двойственной задач существует следующая взаимосвязь (рис. 1.1):

                x1, x2, …, xn, y1, y2, …, ym

                v1, v2, …, vn, z1, z2, …, zm.

Рисунок 1.1- Взаимосвязь между переменными исходной и двойственной задач

     Рассмотрим связь yi* (остаток ресурса i-го вида) и zi*(теневую цену ресурса i-го вида).

      Если yi* = 0, то i-й ресурс использован полностью. Следовательно, он ограничивает дальнейшее увеличение целевой функции, является дефицитным. При увеличении количества этого ресурса может быть произведено больше продукции, следовательно, возрастет прибыль. Соответствующая теневая цена zi* > 0.

     Если же yi* > 0, то имеется остаток ресурса i-го вида, т. е. ресурс не дефицитен. Увеличение количества этого ресурса не вызовет увеличение прибыли. Соответствующая теневая цена zi* = 0.

     Рассмотрим связь xj* (оптимальный объем производства изделий
j-го типа) и vj* (производственные потери на одну единицу изделия
j-го типа).

     Если xj* > 0, то есть j-е изделие вошло в оптимальный план произ-
водства, то соответствующие потери для этого изделия составляют
0 : vj* = 0.

     Если же xj* = 0, то есть изделие не вошло в оптимальный план производства, то это произошло потому, что данный вид продукции убыточен, то есть соответствующие потери vj* > 0.

     Свойство нормированной стоимости. Нормированная стоимость vj* показывает, насколько уменьшится целевая функция при принудительном выпуске одной единицы продукции j-го типа.

Пусть, например, продукция k-го вида не вошла в оптимальный план производства, то есть xk* = 0. Однако существует некоторое плановое задание, предписывающее выпуск этого вида продукции в количестве Tk единиц. Тогда при производстве этого невыгодного вида продукции на него будут оттянуты ресурсы, и выгодной продукции будет выпущено меньше. Целевая функция (общая прибыль) уменьшится, причем это уменьшение можно количественно измерить: