Материал: Основы математического моделирования. курс лекций. Перова А.В

2x1+4x2+5x3+x4 =26;

4x1+2x2-x5=16;

12x1+3x2+x3+x6=60; xj 0, j=1,6.

Составим расширенную задачу, вводя искусственную переменную x7 в первое ограничение. Эту же переменную вводим в целевую функцию с большим коэффициентом M. Расширенная задача имеет вид:

F=6x1+x2+x3+Mx7 min; 2x1+4x2+5x3+x4 =26; 4x1+2x2-x5+x7=16; 12x1+3x2+x3+x6=60;

xj 0, j=1,6.

Решение задачи приведено в табл. 7.

Таблица 7

75

В результате решения получен оптимальный план:

x1*=5; x2*=2; x3*=0; x4*=13; x5*=0; x6*=11; F(X*)=22.

ЛЕКЦИЯ 7 ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ

ПРОГРАММИРОВАНИИ

Каждой ЗЛП можно поставить в соответствие двойственную в соответствии с следующими правилами:

1)если целевая функция F исходной задачи стремится к минимуму, то целевая функция Ф двойственной задачи – к максимуму и наоборот;

2)число переменных двойственной задачи равно числу ограничений исходной, число ограничений двойственной задачи равно числу переменных исходной. Каждому i-му ограничению исходной задачи соответствует переменная yi двойственной задачи (двойственная переменная), а каждой j-й переменной исходной задачи соответствует j-е ограничение исходной задачи;

3)коэффициентами при переменных целевой функции двойственной задачи являются правые части ограничений исходной задачи, а правыми частями ограничений двойственной задачи являются коэффициенты при целевой функции в ис-

ходной задаче;

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

вограничениях исходной задачи;

5)для удобства построения двойственных задач рекомендуется в исходной задаче ограничения-неравенства запи-

сывать со знаком “ ” при максимизации и со знаком “ ” при минимизации;

6) каждому i-му ограничению – неравенству исходной задачи соответствует в двойственной задаче условие неотри-

76

цательности (yi 0), а ограничению -равенству - переменная yi произвольного знака;

7) неотрицательной переменной исходной задачи xj 0 соответствует в двойственной задаче j-е ограничение – неравенство, а произвольной переменной xj - равенство. При этом если двойственная задача подлежит минимизации, неравенство записывается со знаком “ ”, а если двойственная задача подлежит максимизации – со знаком “ ”.

Рассмотренные правила построения двойственных задач иллюстрируются табл. 8.

Соотношение двойственности является взаимным, то есть задача двойственная по отношению к двойственной совпадает с исходной.

Пример 5. Построить двойственную задачу к задаче определения производственного плана, приведенной в примере 1: определить, сколько продукции каждого вида xj необходимо изготовить, чтобы при заданной прибыли от реализации единицы продукции cj и заданных размерах имеющихся ресурсов bi максимизировать общую прибыль. Математическая модель задачи из примера 1 формулировалась следующим образом:

F=7x1+3x2+6x3+12x4 max; 3x1+x2+2x3+4x4 440; x1+8x2+6x3+2x4 200; x1+4x2+7x3+2x4 320;

xj 0, j=1,4.

Введя три двойственные переменные y1 , y2 , y3 , в соответствии с приведенными выше правилами построим двойственную задачу:

Ф=440у1+200y2+320у3 min; 3y1+y2+y3 7; y1+8y2+4y3 3; 2y1+6y2+7y3 6; 4y1+2y2+2y3 12;

77

yi 0, j=1,4.

Отсюда видно, что двойственная задача заключается в определении стоимости единицы ресурса yi, чтобы при заданных количествах ресурсов bi и заданной прибыли cj от реализации единицы продукции минимизировать общую стоимость ресурсов.Пара взаимодвойственных задач, в которых все ограничения записываются в виде неравенств, причем при максимизации знаки всех неравенств , а при минимизации , называется симметричной. Приведенная выше пара задач симметрична.

Таблица 8

Теорема двойственности. Если из пары двойственных задач одна имеет оптимальный план, то и вторая тоже имеет оптимальный план, причем оптимальные значения целевых функций обеих задач равны между собой:

maxF minФ* .

m m

При этом max F bi yi yibi . Отсюда следует, что

i 1 i 1

двойственная переменная yi является коэффициентом при bi и, следовательно, показывает, как изменится целевая функция при изменении i- го ресурса на единицу. В литературе двойственные переменные часто называют двойственными оцен-

78

ками. В отчетах EXCEL двойственная оценка называется те-

невой ценой.

Теорема равновесия. План x* (x1*,...,xn*) прямой зада-

чи и план y* (y1*,..., yn* ) соответствующей двойственной за-

дачи являются оптимальными при выполнении следующих условий:

-если при подстановке компонент оптимального плана

x* (x1*,...,x*n )в систему ограничений исходной задачи i-е

ограничение обращается в неравенство, то i-я компонента оп-

тимального плана двойственной задачи y*i равна нулю.

- если i-я компонента оптимального плана двойствен-

ной задачи y*i положительна, то i-е ограничение исходной

задачи удовлетворяется ее оптимальным решением как строгое равенство.

Таким образом, в парах соотношений

j 1

из знака строгого неравенства во одном соотношении каждой пары следует знак строгого равенства в другом.

Условия теоремы равновесия часто записывают в виде

n

y*i (bi a ij x*j ) 0,i 1, m.

j 1

и называют условиями дополняющей нежесткости.

79