Файл: Линейная_алгебра_УП_очная_ЭлРес.pdf

96

x

1 

– 3 

x

2

 – 2 

x

3 

≥

9, 

x

1

 + x

2

 – 2 

x

3 

≥

7, 

       x

1

≥

0,  x

2

≥

0.    

–1 1  0 –1 * 

–1

1  1  2 * 

1 –3 –2 9 * 

1 –3 1  0 * 



  1 1 –2 7 * 



  0 –2 –2 –4  



2 

0  –4  0  

–1

9 

7 

0  

* *       

* * *     

φ

(Y)  =  – y

1

 +  9y

2

 + 7y

3 

 (max)

 – 

y

1 

 +  y

2

 + y

3 

≤

2, 

y

1 

– 3y

2

 +  y

3 

≤

0, 

– 

2y

2

 – 2y

3 

=

–4, 

y

1

≥

0,  y

2

≥

0,  y

3

≥

0.   

Согласно

второй

тереме

двойственности

должны

выполняться

следующие

соотношения

: 

x

1

0

(–y

1

0 

+ y

2

0

  + y

3

0  

– 2)  = 0, 

x

2

0

(y

1

0

– 3y

2

0

 + y

3

0 

)  = 0, 

x

3

0

(–2y

2

0 

– 2y

3

0

 + 4)  = 0, 

y

1

0

(– x

1

0 

+ x

2

0  

+ 1)  = 0, 

y

2

0

(x

1

0 

– 3x

2

0

 – 2 x

3

0  

– 9)  = 0, 

y

3

0

(x

1

0  

+ x

2

0

 – 2 x

3

0  

– 7)  = 0. 

Подставляя

координаты

вектора

α

0

 = (1. 0 , –4) 

в

выписанные

соотношения

, 

получаем

систему

: 

–  y

1

0 

+ y

2

0

  + y

3

0   

=  2, 

– 2y

2

0  

– 2y

3

0

   = – 4, 

  y

3

0  

=  0. 

Откуда

следует

, 

что

β

0

=(0, 2, 0) 

является

оптимальным

решением

взаимно

двойственной

задачи

ЛП

к

данной

задаче

, 

так

как

этот

вектор

является

допустимым

решением

двойственной

задачи

и

значение

целевой

функции

на

этом

векторе

совпадает

со

значением

целевой

функции

исходной

задачи

на

ее

оптимальном

решении

, 

т

. 

е

. 

φ

(

β

0

) = f(

α

0

) = 18. 

■

Следствие

(

из

второй

теоремы

двойственности

). 

Пусть

вектор

α

0

 =(x

1

0

, 

…, x

n

0

)  

является

допустимым

решением

задач

ЛП

  (1) – (4). 

Тогда

вектор

α

0

является

оптимальным

решением

этой

задачи

тогда

и

только

тогда

, 

когда

среди

решений

системы

уравнений

: 





m

i

1

a

ij

 y

i

= 

γ

j

 , 

если

 x

j

0

>0,   j



J



N ={1, 2, …, n}; 

y

i

=0, 

если





n

j

1

a

ij

 x

j

0

 < b

i

 ,    i 



 I 



 M={1,2,…,m},

содержится

хотя

бы

одно

допустимое

решение

двойственной

задачи

. 

Пример

. 

Дана

задача

ЛП

: 

Для самостоятельной работы

студентов ЧОУ ВПО МБИ

Москва 2013г.

97

Является

ли

вектор

α

 = (1, 1, 1)  

оптимальным

решением

этой

задачи

? 

▲

Подставив

координаты

вектора

в

систему

условий

, 

убеждаемся

, 

что

этот

вектор

является

допустимым

решением

данной

задачи

. 

Применяя

ранее

сформулированные

правила

, 

строим

двойственную

задачу

: 

Согласно

следствию

, 

каждой

положительной

координате

допустимого

решения

задачи

на

максимум

соответствует

равенство

в

системе

ограничений

двойственной

задачи

на

минимум

, 

а

строгому

неравенству

при

подстановке

допустимого

решения

в

задачу

на

максимум

соответствует

нулевое

значение

двойственной

переменной

задачи

на

минимум

.. 

Таким

образом

, 

получаем

систему

: 

 y

1

 + y

2 

= 1, 

–y

1

 + y

2 

= 2,    



 Ø, 

–y

1

 – y

2 

= 3, 

 y

1 

= 0, 

которая

является

несовместной

и

поэтому

не

может

содержать

допустимых

решений

двойственной

задачи

. 

Поэтому

вектор

α

= (1, 1, 1) 

не

является

оптимальным

решением

исходной

задачи

.

■

Экономическое

содержание

исходной

задачи

линейного

программирования

, 

как

правило

, 

определяет

соответствующее

экономическое

содержание

двойственной

задачи

к

исходной

.  

Рассмотрим

, 

например

, 

следующую

ситуацию

. 

Имеется

m

видов

ресурсов

в

количествах

  b

1

, b

2

, … , b

m

единиц

каждого

ресурса

. 

На

основе

этих

ресурсов

можно

производить

продукцию

n

различными

технологическими

способами

. 

При

этом

за

единицу

времени

использования

 j-

го

технологического

способа

(j =1, 2, …, n)  

расходуется

      a

ij

единиц

    i-

го

ресурса

  (i  =1,  2,  …,  m) 

и

производится

продукция

, 

ценностью

γ

j

единиц

. 

Спрашивается

, 

как

оценить

имеющиеся

ресурсы

в

зависимости

от

технологических

возможностей

производства

продукции

? 

Определим

производственную

программу

  (

план

), 

как

вектор

α

 = (x

1

, …, 

x

j

, …, x

n

), 

где

      x

j

 – 

время

использования

    j-

го

технологического

способа

производства

продукции

, 

при

чем

    x

j

≥

 0 , (j =1, 2, …, n), 

так

как

этот

технологический

способ

либо

используется

при

производстве

продукции

, 

либо

f(X) =  

x

1

   +  2 x

2 

+ 3x

3 

(max)

 x

1

 –  x

2 

– x

3 

≤

1, 

x

1  

+  

x

2

   – 

x

3 

≤

1, 

       x

1

≥

0,  x

2

≥

0,  x

3

≥

0.

φ

(Y)   =     y

1

   +  y

2

 (min), 

     y

1

 +  y

2

≥

 1, 

   – y

1   

+ y

2

≥

 2, 

   – y

1 

– y

2

≥

 3, 

y

1

≥

0, y

2

≥

0. 

Для самостоятельной работы

студентов ЧОУ ВПО МБИ

Москва 2013г.

98

не

используется

.  

При

этом

общие

затраты

  i-

го

ресурса

не

должны

превышать

наличия

этого

ресурса

, 

т

. 

е

. 





n

j

1

a 

ij

  x

j

≤

  b

i 

, i ={1,2,…,m}, 

а

ценность

продукции

, 

производимой

по

программе

α

 = (x

1

, …, x

j

, …, x

n

)  

равна

   f(X) = 





n

j

1

γ

j

 x

j

. 

Определим

ценности

имеющихся

ресурсов

, 

как

вектор

β

 = (y

1

, …, y

i

, …, 

y

m

), 

где

  y

i

 – 

некоторая

единица

ценности

 i-

го

ресурса

 (i =1, 2, …, m), 

при

чем

y

i

≥

 0, 

так

как

этот

ресурс

имеет

ценность

при

использовании

некоторого

технологического

способа

, 

но

не

имеет

ценности

при

использовании

другого

технологического

способа

.  

Тогда

величина





m

i

1

a

ij

y

i

есть

ценность

всех

видов

ресурсов

, 

расходуемых

за

единицу

времени

при

использовании

 j-

го

технологического

способа

производства

продукции

. 

Очевидно

, 

что

эта

величина

не

может

быть

меньше

ценности

γ

j

продукции

, 

производимой

при

использовании

 j-

го

технологического

способа

за

единицу

времени

, 

т

. 

е

. 





m

i

1

a 

ij

 y

i

≥

γ

j 

, j ={1,2,…,n}, 

так

как

в

противном

случае

, 

часть

ценности

производимой

продукции

возникала

бы

из

  «

ничего

». 

При

этом

величина

φ

(Y) = 





m

i

1

b

i

  y

i

определяет

ценность

всех

имеющихся

ресурсов

. 

Так

как

в

сбалансированной

экономике

ценность

всей

производимой

продукции

при

любой

производственной

программе

α

не

может

превышать

ценности

всех

используемых

ресурсов

при

любом

векторе

оценок

β

, 

то

имеет

место

неравенство

  f(

α

) 

≤

φ

(

β

).  

Следовательно

, 

величина

Δ

(

α

,

β

) =  

φ

(

β

) – f(

α

)  

характеризует

потери

при

производстве

продукции

в

зависимости

от

выбора

векторов

производственной

программы

α

и

ценности

ресурсов

β

. 

Для

уменьшения

потерь

при

производстве

продукции

, 

эти

векторы

необходимо

выбирать

так

, 

чтобы

ценность

производимой

продукции

 – 





n

j

1

γ

j 

x

j

была

максимальная

, 

а

ценность

используемых

в

производстве

ресурсов

  – 





m

i

1

b

i

 y

i

 – 

минимальная

. 

Таким

образом

, 

приходим

к

паре

взаимно

двойственных

задач

линейного

программирования

: 

f(X) = 





n

j

1

γ

j

 x

j

  (max),                                        

φ

(Y) = 





m

i

1

b

i

 y

i

Для самостоятельной работы

студентов ЧОУ ВПО МБИ

Москва 2013г.

99





n

j

1

a 

ij

 x

j

≤

 b

i 

, i ={1,2,…,m},                              





m

i

1

a 

ij

 y

i

≥

γ

j 

, j ={1,2,…,n},   

x

j

≥

 0 , ( j =1, 2, …, n),                                          y

i

≥

 0,  (i =1, 2, …, m). 

Из

первой

теоремы

двойственности

следует

, 

что

при

оптимальной

программе

производства

продукции

α

0

 = (x

1

0

, …, x

j

0

, …, x

n

0

),   

и

при

оптимальном

векторе

ценности

ресурсов

β

0

 = (y

1

0

, …, y

i

0

, …, y

m

0

) 

производственные

потери

равны

нулю

. 

Из

второй

теоремы

двойственности

следуют

условия

на

оптимальную

производственную

программу

α

0

 = (x

1

0

, …, x

j

0

, …, x

n

0

),  

и

оптимальный

вектор

ценности

ресурсов

β

0

 = (y

1

0

, …, y

i

0

, …, y

m

0

) , 

которые

заключаются

в

следующем

.  

Если

ценность

    i–

го

ресурса

положительна

, 

т

. 

е

. y

i

0

 > 0, ,

то

этот

ресурс

используется

полностью

, 

т

. 

е

. 





n

j

1

a 

ij

 x

j

0

 = b

i

. 

Если

    i–

й

ресурс

используется

не

полностью

, 

т

. 

е

. 





n

j

1

a 

ij

  x

j

0

 < b

i

, 

то

его

ценность

равна

нулю

, 

т

. 

е

. y

i

0

 = 0. 

Если

при

производстве

продукции

используется

 j-

й

технологический

способ

, 

т

. 

е

.  x

j

0

 > 0 , 

то

ценность

расходуемых

в

единицу

времени

ресурсов

равна

ценности

производимой

продукции

, 

т

. 

е

. 





m

i

1

a 

ij

 y

i

0

 = 

γ

j 

. 

Если

при

    j-

м

технологическом

способе

производства

продукции

ценность

затрачиваемых

ресурсов

больше

ценности

производимой

продукции

, 

т

. 

е

. 





m

i

1

a 

ij

 y

i

0

 > 

γ

j 

, 

то

данный

технологический

способ

производства

продукции

не

используется

, 

т

. 

е

. x

j

0

 = 0. 

Ответьте

на

вопросы

1.

Напишите

пару

взаимно

двойственных

задач

линейного

программирования

. 

2.

Опишите

схему

формирования

двойственной

задачи

к

данной

задаче

. 

3.

Как

соотносятся

число

переменных

и

число

ограничений

для

пары

взаимно

двойственных

задач

линейного

программирования

? 

4.

Напишите

симметричную

пару

взаимно

двойственных

задач

 . 

5.

Сформулируйте

лемму

о

допустимых

решениях

пары

взаимно

двойственных

задач

. 

6.

Как

соотносятся

величины

целевых

функций

пары

взаимно

двойственных

задач

на

их

допустимых

решениях

? 

7.

Когда

допустимые

решения

пары

взаимно

двойственных

задач

линейного

Для самостоятельной работы

студентов ЧОУ ВПО МБИ

Москва 2013г.

100

программирования

являются

оптимальными

решениями

этих

задач

? 

8.

Какова

система

ограничений

одной

из

пары

взаимно

двойственных

задач

линейного

программирования

, 

если

целевая

функция

другой

задачи

не

ограничена

на

множестве

своих

допустимых

решений

? 

9.

Сформулируйте

 1-

ю

теорему

двойственности

. 

10.

Сформулируйте

и

докажите

 2-

ю

теорему

двойственности

. 

11.

Когда

можно

использовать

следствие

из

 2-

й

теоремы

двойственности

? 

12.

Опишите

схему

формирования

пары

взаимно

двойственных

задач

линейного

программирования

при

планировании

работы

предприятия

.  

13.

Как

используется

ресурс

, 

если

его

ценность

положительна

? 

14.

Если

ресурс

используется

не

полностью

, 

то

какова

ценность

этого

ресурса

? 

15.

Если

некоторый

технологический

способ

используется

при

производстве

продукции

, 

то

какова

ценность

расходуемых

при

этом

ресурсов

? 

16.

Если

технологический

способ

таков

, 

что

при

производстве

продукции

ценность

затрачиваемых

ресурсов

больше

ценности

производимой

продукции

, 

то

нужен

ли

данный

технологический

способ

производству

? 

Решите

самостоятельно

Задача

 1. 

Составить

двойственную

задачу

к

данной

задаче

: 

 f(X) = 3x

1

 – 2x

2

 +4x

3

  (max), 

3x

1

 – x

2

 + 4x

3

≤

 5, 

 x

1

 + x

2

 –5x

3

≥

 2, 

 x

1

 – x

2

 + 3x

3

≤

  4, 

 x

j

≥

 0, j=1, 2, 3. 

 f(X) = x

1

 + x

2

 +x

3

  (min), 

x

1

 – x

2

 + x

3

≤

 3, 

2x

1

 + 2x

2

 –5x

3

 = 4, 

 x

1

 – x

2

 + 5x

3

≤

  10,  

x

2

≥

 0. 

  f(X) = 3x

1

 – x

2

 +8x

3

  (max), 

x

1

 + x

2

 – x

3

≤

 5, 

2 x

1

 – x

2

 –x

3

≥

 5, 

 x

1

 + x

2

 – x

3

≥

  7, 

 x

1

≥

 0, x

3

≥

 0. 

Задача

 2. 

Зная

оптимальное

решение

данной

задачи

, 

найти

оптимальное

решение

двойственной

задачи

, 

используя

вторую

теорему

двойственности

. 

2.1.             f(X) = 4x

1

 + 12x

2

 +x

3

  (min), 

3 x

1

 + 2 x

2

 + x

3

≥

 3, 

Для самостоятельной работы

студентов ЧОУ ВПО МБИ

Москва 2013г.