Двойственные  задачи

    Для решения задачи реализации симплекс-метода в  случае всех отрицательных  свободных членов мы должны прибегнуть к решению двойственной задачи. Это позволяет  получить решение  по оптимальному решению  двойственной задачи, имеющей допустимое начальное решение.

Экономическая интерпретация двойственных задач.

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

         Экономическая интерпретация  задачи, двойственной задаче об использовании  ресурсов. Ранее рассмотрена задача об использовании ресурсов (экономико-математическая модель и содержательная интерпретация этой задачи I представлены в левой части табл. 6.1). В приведенной модели b_i (i = 1, 2, ..., m) обозначает запас ресурса S_i , a_ij - число единиц ресурса S_i потребляемого при производстве единицы продукции P_j(j = 1, 2, ..., n); C_j - прибыль (выручка) от реализации единицы продукции P_j (или цена продукции P_j). 
Предположим, что некоторая организация решила закупить ресурсы S₁, S₂, ..., S_m предприятия и необходимо установить оптимальные цены на эти ресурсы у₁, у₂, ..., y_m

         Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах b₁, b₂, ..., b_m по ценам соответственно у₁, у₂, ..., y_m были минимальны, т.е 
Z = b₁у₁ + b₂ у₂ + ... + b_m у_m min . 
С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции Р₁ расходуется a₁₁ единиц ресурса S₁, a₂₁ единиц ресурса S₂, ..., a_i1 единиц ресурса S_i ..., а_m1 единиц ресурса S_m по цене соответственно у₁, у₂, ..., у_i ..., y_m. Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции Р₁ должны быть не менее ее цены c₁, т.е. 
a₁₁ у₁ + a₂₁ у₂ +…+ a_m1 у_m>= c₁  
Аналогично можно составить ограничения в виде неравенств по каждому виду продукции Р₁, Р₂, ..., Р_m.

         Экономико-математическая модель и содержательная интерпретация  полученной таким образом двойственной задачи II приведены в правой части  табл. 6.1.

    Цены  ресурсов у₁, у₂, ..., у_m в экономической литературе получили различные названия: учетные, неявные, теневые.

    Смысл этих названий состоит в том, что  это условные, "ненастоящие" цены. В отличие от "внешних" цен c₁, с₂, ..., c_n на продукцию, известных, как правило, до начала производства, цены ресурсов у₁, у₂, ..., у_n являются внутренними, ибо они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их чаще называют оценками ресурсов.

Свойства  двойственных задач.

    Рассмотрим  формально две задачи I и II линейного  программирования, представленные в  табл. 6.1, абстрагируясь от содержательной интерпретации параметров, входящих в их экономико-математические модели. Обе задачи обладают следующими свойствами: 
1. В одной задаче ищут максимум линейной функции, в другой - минимум. 
2. Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой. 
3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида "<=", а в задаче минимизации - все неравенства вида ">=". 
4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу:  
для задачи I A =

для задачи II А' = 

5. Число неравенств  в системе ограничений  одной задачи совпадает  с числом переменных  в другой задаче. 
6. Условия неотрицательности переменных имеются в обеих задачах. 
Две задачи I и II линейного программирования, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами. В дальнейшем для простоты будем называть их просто двойственными задачами. 
Исходя из определения, можно предложить следующий алгоритм составления двойственной задачи. 
1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду "<=", а если минимум - к виду ">=". Для этого неравенства, в которых данное требование не выполняется, умножить на -1. 
2. Составить расширенную матрицу системы А_1, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.  
3. Найти матрицу А'₁, транспонированную к матрице А₁. 
4. Сформулировать двойственную задачу на основании полученной матрицы A'₁ и условия неотрицательности переменных.

Решение задач с помощью  симплексных таблиц

    В этом разделе описано использование  симплексных таблиц для решения  задач. Использование симплексных  таблиц весьма удобно для ручного  расчёта задач. Для заполнения первой симплексной таблицы надо привести систему к каноническому виду. Затем если надо ищется первоначальное допустимое решение или задачу надо решать M-методом. Кроме того, систему представляют в расширенном виде.

    Обратите  внимание, что коэффициенты при переменных в функции меняют знак! Все введённые  переменные имеют тот же знак, что  и свободные члены иначе надо использовать M-метод (или заранее  отыскать ПДБР). Далее эти данные заносятся в первую симплексную таблицу, общий вид которой представлен ниже.

(2.20) 

    Теперь, поясним, что есть что. Каждая строка - это уравнение в расширенной системе (смотрите формулу 2.19). В столбце "Базис" перечисляются все базисные (основные) переменные, их число равно числу уравнений в системе ограничений. Следующий столбец, "Свободные член" заполняется значениями свободных членов уравнения. В самую верхнюю строку (под надписью "переменные") выписываются все переменные. Самая нижняя строка, начиная с c₁, заполняется значениями коэффициентов при переменных, которые написаны вверху таблицы, из уравнения функции (с обратным знаком, как в расширенной системе), если в уравнении функции такой переменной нет, то пишем ноль. Ячейки "a" заполняются так. Если вверху столбца написана основная переменная, то на пересечении этого столбца со строкой, в которой написана та же переменная, ставим 1, во все остальные ячейки столбца пишем 0. Если же вверху столбца неосновная переменная, то в ячейки записываются её коэффициенты из соответствующего уравнения, если её нет в этом уравнении, то пишем 0. В ячейку c₀, на первом шаге просто пишем ноль.

    Далее надо провести проверку на оптимальность  решения. Это делается легко, если задача на минимум то решение оптимально, если все c, кроме c₀, имеют отрицательные знаки, если же задача на максимум, то когда положительные знаки.

    Если  решение не оптимально, ищем разрешающий столбец (индекс s), он определяется коэффициентом при переменной в уравнении функции, то есть нижней строкой, начиная c₁. Для задачи на минимум это любой столбец, где c максимальный, положительный элемент, а для задачи на максимум, минимальный, отрицательный элемент. Далее проводим расчёт оценочных отношений и заполняем соответствующий столбец. Расчет производится в соответствии со следующим правилом:

    если  b_i и a_is имеют разные знаки, то g_i равно бесконечности

    если  b_i равно нулю и a_is меньше нуля, то g_i равно бесконечности

    если  b_i равно нулю и a_is больше нуля, то g_i равно нулю

    если  a_is равно нулю, то g_i равно бесконечности

    иначе g_i равно частному от деления b_i на a_is

    После того, как столбец с g заполнен. Выбирается разрешающая строка (индекс q). Это строка, в которой самое минимальное оценочное отношение (но не ноль и не бесконечность). На пересечении разрешающих строки и столбца находится разрешающий элемент - a_qs.