Взаимно-двойственные задачи линейного программирования и их свойства

Рассмотрим формально две задачи I и II линейного программирования, представленные выше в таблице.

Обе задачи обладают следующими свойствами:

1. В одной задаче ищут максимум линейной функции, в другой – минимум.

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

3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида «<=», а в задаче минимизации – все неравенства вида «>=».

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

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче.

6. Условия неотрицательности переменных имеются в обеих задачах.

 

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

 

Исходя из определения, можно предложить следующий алгоритм составления двойственной задачи:

1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду «<=», а если минимум – к виду «>=». Для этого неравенства, в которых данное требование не выполняется, умножить на -1.

2. Составить расширенную матрицу А₁, в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.

3. Найти матрицу А₁^`, транспонированную к матрице А_1.

4. Сформулировать двойственную задачу на основании полученной матрицы А₁^` и условия неотрицательности переменных.

Пример.

F = -7х₁ + 2х₂ → max

При ограничениях

-3х₁ + 5х₂ ≥ 1,

   -х₁ + 4х₂ ≤ 24

     х₁ - х₂ ≥ 6

х₁, х₂ ≥ 0

Решение:

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

3х₁ - 5х₂ ≤ - 1,

   -х₁ + 4х₂ ≤ 24

    - х₁ + х₂ ≤- 6

2. Составим расширенную матрицу системы

          -7   2  F

3. Найдем матрицу А₁^`, транспонированную к А.

       3 -1  -1 -7

А₁^` = -5 4   1  2

-1 24 -6  Z

 

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

Z = -у₁ + 24у₂ -6у₃ → min

При ограничениях

 3у₁ -у₂ -у₃ ≥ -7

-5у₁ +4у₂ +у₃ ≥ 2

у₁, у_2, у₃ ≥ 0.

 

Теоремы двойственности

и

 их использование для анализа оптимальных решений

 

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

Теорема 1. Если одна из двойственных задач разрешима, то разрешима и другая, причем экстремальные значения целевых функций задач равны: max F(x) = min Z(y).

Если одна из двойственных задач неразрешима, то неразрешима и другая.

Теорема 2. Пусть Х=(х₁,х₂,…,х_n) – допустимое решение прямой задачи,

                            У=(у₁,у₂,…,у_m) – допустимое решение двойственной задачи.

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

                      

.

.

.

Если х_j ≠ 0, то соответствующее ограничение дв. задачи

– строгое равенство.

 

.

.

.

 

Если запас i-ого ресурса израсходован

не полностью, то у_i = 0.

 

 

Теорема об оценках.

Значения переменных у_i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов b_i системы ограничений – неравенств прямой задачи на величину ∆f(Х):

∆f(Х) =∆b_iy_i 

 

Пример использования теорем и свойств двойственных оценок для анализа оптимальных решений.

На станках трех видов С₁,С₂, С₃ последовательно обрабатываются детали четырех видов D₁, D₂, D₃, D₄. Известно, сколько часов каждая деталь изготавливается на каждом станке, сколько времени может отработать каждый станок и какая прибыль может быть получена при продаже одной детали каждого вида. Данные для решения задачи содержатся в таблице.

Станки	Сколько требуется часов работы станка для выпуска одной детали, час/дет.				Фонд времени станка, час
	D1	D2	D3	D4
С1	2	4	0	8	12
С2	7	2	2	6	8
С3	5	8	4	3	48
Прибыль на одну деталь, у.е./дет.	3	4	3	1	-

 

Симплекс-методом найден оптимальный план задачи по критерию «максимум прибыли», предусматривающий выпуск трех деталей второго вида и одной детали третьего вида.

 

х₁^*= 0

х₂^*= 3

х₃^*= 1

х₄^*= 0

Дать экономико-математический анализ оптимального плана.

 

Решение.

Обозначим х_j – объем выпуска деталей j- ого вида (j = 1,2,3,4) и запишем математическую модель задачи по критерию «максимум прибыли»:

 

max (3х₁ + 4х₂ + 3х₃ + х₄)

  2х₁ + 4х₂ + 8х₄  ≤ 12

   7х₁ + 2х₂ + 2х₃ + 6х₄ ≤ 8

   5х₁ + 8х₂ + 4х₃ + 3х₄ ≤ 48

   х₁, х₂, х₃, х₄ ≥ 0

 

Двойственная задача имеет вид:

min (12y₁ + 8y₂ + 48y₃)

  2y₁ + 7y₂ + 5y₃  ≥ 3

   4y₁ + 2y₂ + 8y₃   ≥4

   2y₂ + 4y₃ ≥ 3

   8y₁ + 6y₂ + 3y₃  ≥ 1

   y₁, y₂, y₃, ≥ 0

 

Для нахождения оценок y₁, y₂, y₃ используем вторую теорему двойственности.

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

     2*0 + 4*3 + 8*0  =12

   7*0 + 2*3 + 2*1 + 6*0 = 8

   5*0 + 8*3 + 4*1 + 3*0 = 28 < 48

Поскольку третье ограничение выполняется как строгое неравенство, то у₃ = 0.

Т.к. х₂ > 0 и х₃  > 0, то второе и третье ограничения двойственной задачи – строгие равенства:

   4y₁ + 2y₂ + 8y₃   = 4

   2y₂ + 4y₃ = 3

Итак, для получения двойственных оценок имеем систему линейных уравнений:

у*₃ = 0

4y*₁ + 2y*₂ + 8y*₃   = 4

 2y*₂ + 4y*₃ = 3,

т.е.                   у*₁ = 0,25;

                        у*₂ = 1,5;

                         у*₃ = 0.

 

 

Вычислим значения целевых функций прямой

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

F (х*) = Z (у*) = 15.

По первой теореме двойственности мы можем утверждать, что действительно найдены оптимальные значения двойственных переменных.

 

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

В пределах устойчивости двойственных оценок имеют место следующие свойства.

1. Величина двойственной оценки того или иного ресурса показывает на сколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на одну единицу.

В рассматриваемом примере увеличение фонда времени работы станка С₁ на 1 час привело бы к росту максимальной суммы прибыли на 0,25 у. е. (у*₁ = 0,25), а увеличение фонда рабочего времени третьего станка не повлияет на оптимальный план выпуска продукции и сумму прибыли.

2. Двойственные оценки отражают сравнительную дефицитность различных ресурсов в отношении принятого в задаче показателя эффективности.

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

В нашем примере недефицитным ресурсом является фонд рабочего времени станка С₃ поскольку у*₃ = 0.

Острее ощущается дефицитность ресурса С₂ (у*₂ = 1,5), он более дефицитен, чем ресурс С₁  (у*₁ = 0,25).

3. Двойственные оценки позволяют определять своеобразные «нормы заменяемости ресурсов»: имеются в виду не абсолютная заменяемость ресурсов, а относительная, т.е. заменяемость с точки зрения конечного эффекта и лишь в конкретных условиях данной задачи.

В нашем примере относительная заменяемость ресурсов определяется соотношением 0,25: 1,5 = 1: 6.

4. С помощью двойственных оценок можно определять выгодность производства новых изделий:

если

Предположим в нашем примере следует решить вопрос о целесообразности включения в программу производство деталей нового (пятого) вида при затратах ресурсов станков: 8, 2 и 3 соответственно и ожидаемой удельной прибыли 6 у.е.

∆₅ = 0,25 * 8 + 1,5 * 2 + 0 * 3 – 6 = - 1 < 0 – выгодно.