лекции. Лекции_МО_20. Лекции по методам оптимизации Тема Общая постановка задачи линейного программирования (2часа)

• Название: Лекции по методам оптимизации Тема Общая постановка задачи линейного программирования (2часа)
• Анкор: лекции
• Дата: 12.02.2022
• Размер: 254.78 Kb.
• Имя файла: Лекции_МО_20.docx
• Тип: Лекции; #359380
• страница: 6 из 9

Тема 5. Двойственность в задачах линейного программирова- ния

(2 часа)

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

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

В рассмотренной задаче, в ее модели обозначает запас ре- сурса - число единиц ресурса используемого при производстве единицы продукции ьприбыль (выручка) от реализации единицы продукции или цена продукции

Предположим, что некоторая организация решила закупить ресурсы предприятия и необходимо установить оптимальные цены

на эти ресурсы.

Очевидно, что закупающая организация заинтересована в том, чтобы затраты Z на все ресурсы в количествах y₁,y₂,…,y_mбыли минимальны, т.е.

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

изготовлении продукции

P₁ , должны быть не менее ее цены с₁:

a₁₁ y₁  a₂₁ y₂  ...  a_m1 y c₁ .

Аналогично можно составить ограничения и для остальных продукций .

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

Исходная задача	Двойственная задача
	Z b1 y1  b2 y2  ...  bmym min

Каждой задаче ЛП соответствует своя двойственная задача и обе они состав- ляют двойственнуюпару. Эти задачи обладают следующими свойствами:

1. 
   В одной задаче имеется максимум, а в другой минимум;
   
2. 
   Коэффициенты при переменных в целевой линейной функции одной зада- чи являются свободными членами системы ограничений другой задачи;
   
3. 
   Каждая из задач заданы в стандартной форме, причем в задаче максими- зации все неравенства вида «≤» а в задаче минимизации все неравенства имеют вид «≥»,
   

4. 
   Число неравенств системе ограничений одной задачи совпадает с числом переменных другой задачи, т.е. в исходной задаче n переменных и m ра- венств, а в двойственной m переменных и n неравенств;
   

5. 
   Матрица переменных исходной задачи
   


^{ a}11


^...
_A ^{ a}21



a


...

^a12 ^a22
a

...

...

...

...

^a1n ^



^a2n ^





a

 m1 m2 mn
И матрица коэффициентов при переменных двойственной задачи


^{ a}11



_{A } ^{ a}12

...


...

^a21

^a22

...

...

...

^am1 ^



^am2 ^



 

a a ... a

 1n 2n mn
являются транспонированными матрицами между собой, они получаются друг из друга заменой строк столбцами;

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

«≤». Для этого, неравенства, в которых данное требование не выполня- ется, умножить на -1.

2. 
   Составить расширенную матрицу системы A₁ , в которую включить
   

матрицу коэффициентов А, столбец свободных членов системы огра- ничений и строку коэффициентов при переменных линейной функции.

3. 
   Найти матрицу
   

^A₁^ , транспонированную к матрице

A₁ .

4. 
   Сформулировать двойственную задачу на основании полученной мат-
   

рицы

^A₁^ и условия не отрицательности переменных.

Приведем несколько теорем двойственности.
Опервойтеоремедвойственности.

Связь между оптимальными решениями двойственных задач устанав- ливается с помощью теорем двойственности. Рассмотрим основное неравенство теории двойственности. Пусть имеется пара двойствен-

ных задач I и II. Для любых двух допустимых решений

X (x₁, x₂ ,..., x_n)

и Y ( y₁, y₂ ,..., y_m)

исходной и двойственной задач спра-

ведливо неравенство:

F(X)  Z(Y)


или _^c_j^x_jj1

m




 _b_iy_i

i1


n
(1)

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

Теорема.Если

X^*  (x^* , x^* ,..., x^* ) и Y^*  ( y^* , y^* ,..., y^* )

- допустимые

1 2 n 1 2 m

решения взаимно двойственных задач и выполняется равенство
F( X^* )  Z(Y^* ) , (2)

то X^* - оптимальное решение исходной задачи I, Y^* - оптимальное

решение двойственной задачи II.
Перваядвойственнаятеорема:

Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных це- левых функций равны:

F_max  Z
min

или

F( X^* )  Z(Y^* )

(3)

Если линейная функция одной из задач не ограничена, то условия дру- гой задачи противоречивы.

Экономический смысл первой основной теоремы двойственности:

План производства

X^*  (x^* , x^* ,..., x^* ) и набор цен Y^*  ( y^* , y^* ,..., y^* )

ока-

1 2 n 1 2 m

зываются оптимальными тогда и только тогда, когда прибыль (вы-

ручка) о продукции, полученная при известных ценах c₁ , c₂ ,..., c_n,

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

ценам y^* , y^* ,..., y^* .

1 2 m

Другими словами, предприятию безразлично, производить ли продук-

цию по оптимальному плану

X^*  (x^* , x^* ,..., x^* )

и получить максималь-

1 2 n

ную прибыль F_max , либо продавать ресурсы по оптимальным ценам

Y^*  ( y^* , y^* ,..., y^* ) и возместить от продажи равные ей минимальные за-

1 2 m

траты на ресурсы

^Zmin _.

Вопросы для контроля

1. 
   Перечислите свойства двойственных задач.
   
2. 
   Каким образом связаны решения двойственных задач?
   

3. 
   Расскажите алгоритм составления задачи, двойственной по отношению к данной задаче.
   
4. 
   Расскажите достаточный признак оптимальности решений двойственных задач.
   
5. 
   Расскажите о первой теореме двойственности.