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

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 31.07.2021

Просмотров: 1139

Скачиваний: 2

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
background image

 

91

2.10. 

Взаимно

 

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

 

задачи

 

линейного

 

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

 

Определение

Взаимно

 

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

 

задачами

 

линейного

 

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

  (

ЛП

)  

называется

 

пара

 

задач

  

вида

 

(1)

 

f(X) = 

n

j

1

γ

j

 x

j

 + 

γ

0

 (max), 

(2)

 

 

n

j

1

ij

 x

j

 

 b

, i 

 I 

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

(3)

 

 

n

j

1

ij

 x

j

 = b

, i 

 M \ I, 

(4)

 

 x

j

 

 0,                j

J

N=(1, 2, …, n}      

и

 

 

 

          (1’)      

φ

(Y) = 

m

i

1

b

i

 y

i

 + 

γ

0

 (min), 

                  (2’)

       

m

i

1

ij

 y

i

 

 

γ

, j 

 J 

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

          (3’)

      

m

i

1

ij

 y

i

 = 

γ

, j 

 N \ J,  

          (4’)        y

i

 

 0,                i

I

M=(1, 2, …, m}. 

 

Если

 

дана

 

задача

 

ЛП

то

 

для

 

нее

 

всегда

 

можно

 

построить

 

взаимно

 

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

 

задачу

 

ЛП

используя

 

следующие

 

правила

 
1

0

.

 

Одна

 

из

 

пары

 

взаимно

 

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

 

задач

 

ЛП

 

должна

 

быть

 

задачей

 

на

 

максимум

 

и

 

левая

 

часть

 

ее

 

системы

 

условий

 

не

 

больше

 

правой

,  

то

 

есть

 

между

 

левой

 

и

 

правой

 

частями

 

системы

 

условий

 

неравенство

 

вида

:  

 . 

Тогда

 

другая

 

из

 

пары

 

взаимно

 

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

 

задач

 

ЛП

 

должна

 

быть

 

задачей

 

на

 

минимум

 

и

 

левая

 

часть

 

ее

 

системы

 

условий

 

не

 

меньше

 

правой

то

 

есть

 

между

 

левой

 

и

 

правой

 

частями

 

системы

 

условий

 

неравенство

 

вида

:  

 .  

 

2

0

Для

 

каждой

 

из

 

пары

 

взаимно

 

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

 

задач

 

ЛП

 

можно

 

выписать

 

таблицу

в

 

которой

 

координаты

 

вектора

 

ограничений

входящие

 

в

 

неравенства

 

системы

 

условий

и

 

коэффициенты

 

целевой

 

функции

 

при

 

неотрицательных

 

переменных

 

отмечаются

 

звездочкой

При

 

этом

 

таблица

 

для

 

одной

 

из

 

взаимно

 

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

 

задач

 

ЛП

 

после

 

транспонирования

 

становится

 

таблицей

 

для

 

другой

 

из

 

взаимно

 

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

 

задач

 

ЛП

 

Пример

Для

  

задачи

 

ЛП

 

на

 

максимум

 

построить

 

взаимно

 

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

 

задачу

 

ЛП

  

на

 

минимум

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

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

Москва 2013г.


background image

 

92

f(x) =   x

1    

+ 2x

– x

(max)  

 

 x

1    

+ x

2

  –  2x

3

 

 3, 

 1   1 –2 3 *

1  

2 –1  1  *

 2x

– x

2  

+

  

x

3

  = 4, 

 2  –1  1 4

 1  –1    1   2 

–x

1  

+   x

2  

+ 4x

3

 

 5, 

–1  1  4 5 *

–2   1   4  –1

 

x

1

 

0.      1  2 –1 0

 3   4   5   0 

 

 * 

 

 

 

 * 

 

 

φ

(y) =   3y

1

+ 4y

+ 5y

3

 (min), 

 y

1

  +  2y

– y

3

  

 1, 

 y

1    

– y

2

  +  y

3

 = 

2, 

–2y

1

+ y

2   

+ 4y

3

 = 

–1, 

 

y

1

 

0, y

3

 

0. 

 

 

  

 

 

 

 

 

 

 

 

 

 

 

Отметим

что

 

число

 

переменных

 

одной

 

из

 

взаимно

 

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

   

задач

 

ЛП

 

равно

 

числу

 

ограничений

 

в

 

системе

 

условий

 

другой

 

из

 

взаимно

 

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

  

задач

 

ЛП

;  

 

неотрицательным

 

переменным

 

одной

 

из

 

взаимно

 

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

   

задач

 

ЛП

  

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

 

неравенства

 

в

 

системе

 

ограничений

 

другой

 

из

 

взаимно

 

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

 

задач

 

ЛП

 

координаты

 

вектора

 

ограничений

 

одной

 

из

 

взаимно

 

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

 

задач

 

ЛП

 

являются

 

коэффициентами

 

при

 

переменных

 

в

 

целевой

 

функции

 

другой

 

из

 

взаимно

 

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

  

задач

 

ЛП

.      

Важнейшие

 

частные

 

случаи

 

взаимно

 

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

 

задач

 

линейного

 

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

:

 

1.

 

Симметричная

 

пара

 

взаимно

 

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

  

задач

 

ЛП

  ( I = M, J = N):     

f(X) =   

n

j

1

γ

j

 x

j

 + 

γ

0

 (max),                   

φ

(Y) = 

m

i

1

b

i

 y

i

 + 

γ

0

 (min), 

n

j

1

ij

 x

j

 

 b

, i =1,2,…,m,                    

   

m

i

1

ij

 y

i

 

 

γ

, j =1,2,…,n,          

               x

j

 

 0,    j=1, 2, …, n.                                  y

i

 

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

2.

 

Несимметричная

 

пара

 

взаимно

 

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

  

задач

 

ЛП

  ( I = Ø, J = N):     

f(X) =   

n

j

1

γ

j

 x

j

 + 

γ

0

 (max),                   

φ

(Y) = 

m

i

1

b

i

 y

i

 + 

γ

0

 (min), 

n

j

1

ij

 x

j

 = b

, i =1,2,…,m,                    

   

m

i

1

ij

 y

i

 

 

γ

, j =1,2,…,n,          

               x

j

 

 0,    j=1, 2, …, n.                                 

 y

i

,  i=1, 2, …, m. 

Лемма

Если

   

векторы

 

α

 =(k

1

, …, k

n

)   

и

 

β

=(

1

, …,

m

)  

являются

 

допустимыми

 

решениями

 

взаимно

 

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

   

задач

 

ЛП

  (1) – (4) 

и

 (1’) – 

(4’) 

соответственно

то

 

выполняются

 

неравенства

(L

1

)         

      (

n

j

1

a

ij

 k

j

 ) 

i

 

 b

i

 

i

, i=1, 2, …, m

(L

2

)              

 (

m

i

1

a

ij

 

I

)k

j

 

 

γ

j

 k

j

, j=1, 2, …, n

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

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

Москва 2013г.


background image

 

93

 

Если

  i

I, 

то

 

n

j

1

a

ij

 k

j

  

 b

i

  

и

 

i

 

 0   

      (

n

j

1

a

ij

 k

j

 ) 

i

 

 b

i

 

i

Если

 

же

 , 

 M \ I, 

то

 

n

j

1

a

ij

  k

j

    =  b

i

   

и

 

для

     

 

i

справедливо

      (

n

j

1

a

ij

  k

j

 ) 

i

 = b

i

 

i

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

для

 

любых

  i = 1, 2, …, m  

выполняется

 

неравенство

    (L

1

) . 

Справедливость

 

неравенства

   (L

2

доказывается

 

аналогично

 

 

Основные

 

свойства

 

взаимно

 

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

  

задач

 

ЛП

 

1

0

.  

Если

   

векторы

 

α

 =(k

1

, …, k

n

)   

и

 

β

=(

1

, …, 

m

)  

являются

 

допустимыми

 

решениями

 

взаимно

 

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

   

задач

 

ЛП

  (1) – (4) 

и

 (1’) – (4’) 

соответственно

то

  f(

α

 

φ

(

β

). 

 

Значение

 

целевой

 

функции

 

ЗЛП

  (1) – (4) 

на

 

допустимом

 

векторе

 

α

 

=(k

1

, …, k

n

с

 

учетом

 

доказанной

 

леммы

 

можно

 

записать

 

в

 

виде

 

  f(

α

) = 

γ

1

k

1

 +…+ 

γ

т

k

n

 + 

γ

0

 

(

m

i

1

a

i1

 

i

) k

1

 +…+  (

m

i

1

a

in

 

i

) k

n

 + 

γ

0

 = 

=(a

11

1

+…+a

m1

m

)k

1

+…+(a

1n

1

+…+a

mn

m

)k

n

+

γ

0

 = =(a

11

k

1

+…+a

1n

k

n

)

 

1

+…+(a

m1

k

1

+…+a

mn

k

n

)

 

m

+

γ

0

 = 

=(

n

j

1

a

1j

 k

j

 ) 

1

 +…+  (

n

j

1

a

mj

 k

j

 ) 

m

 + 

γ

0

 =b

1

 

1

 +…+  b

m

 

m

 + 

γ

0

 

 

φ

(

β

). 

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

,   f(

α

 

φ

(

β

). 

 

2

0

.  

Если

   

векторы

 

α

0

 

и

 

β

0

   

являются

 

допустимыми

 

решениями

 

взаимно

 

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

  

задач

 

ЛП

  (1) – (4) 

и

 (1’) – (4’) 

соответственно

и

 f(

α

0

) = 

φ

(

β

0

), 

то

 

векторы

  

α

0

 

и

 

β

0

  – 

оптимальные

 

решения

 

этих

 

задач

 

соответственно

 

Для

 

произвольного

 

допустимого

 

решения

   

α

   

задачи

 

ЛП

  (1) – (4) 

по

 

свойству

  1

0

  

выполнятся

 

неравенство

  f(

α

 

φ

(

β

0

). 

Так

 

как

 

по

 

условию

 f(

α

0

) = 

φ

(

β

0

), 

то

    f(

α

 f(

α

0

и

 

по

 

определению

 

вектор

   

α

0

 

является

 

оптимальным

 

решением

 

ЗЛП

  (1) – (4). 

Оптимальность

 

вектора

  

β

0

 

доказывается

 

аналогично

 

3

0

.

 

Если

 

целевая

 

функция

 

одной

 

из

 

взаимно

 

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

   

задач

 

ЛП

 

неограниченна

 

на

 

множестве

 

допустимых

 

решений

 

этой

 

задачи

то

 

другая

  

взаимно

 

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

  

задача

 

ЛП

  

не

 

имеет

 

ни

 

одного

 

допустимого

 

решения

т

.

е

система

 

условий

 

этой

 

задачи

 

является

 

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

.   

 

Доказательство

 

проведем

 

от

 

противного

Пусть

   

целевая

 

функция

 – 

φ

(

β

)  

задачи

   

ЛП

  (1’) – (4’) 

неограниченна

 

снизу

 

на

 

множестве

 

допустимых

 

решений

а

   

задача

   

ЛП

 (1) – (4)  

имеет

 

допустимое

 

решение

    – 

α

.   

Тогда

 

по

 

свойству

 1

0

  

для

 

любого

 

допустимого

 

решения

 – 

β

  

задачи

 

ЛП

  (1’) – (4’) 

должно

 

выполняется

 

неравенство

:  f(

α

 

φ

(

β

). 

Это

 

неравенство

   

противоречит

 

неограниченности

 

снизу

 

целевой

 

функции

 

φ

(

β

на

 

множестве

 

допустимых

 

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

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

Москва 2013г.


background image

 

94

решений

 

этой

 

задачи

.  

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

задача

  

ЛП

  (1) – (4)  

не

 

имеет

 

ни

 

одного

 

допустимого

 

решения

т

е

.  

система

 

условий

 

этой

 

задачи

 

несовместна

 

 

Теоремы

 

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

 

Теорема

  1

Если

 

одна

 

из

 

взаимно

 

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

   

задач

 

ЛП

   

имеет

 

оптимальное

 

решение

то

 

и

 

другая

 

взаимно

 

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

 

задача

 

ЛП

   

имеет

 

оптимальное

 

решение

,  

при

 

этом

 

значения

 

целевых

 

функций

 

на

 

оптимальных

 

решениях

 

этих

 

задач

 

совпадают

Если

 

же

 

целевая

 

функция

 

одной

 

из

 

взаимно

 

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

 

задач

 

ЛП

 

неограниченна

 

на

 

множестве

 

допустимых

 

решений

то

 

вторая

 

из

 

взаимно

 

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

   

задач

 

ЛП

   

не

 

имеет

 

ни

 

одного

 

допустимого

 

решения

т

е

., 

система

 

условий

 

второй

 

задачи

 

несовместна

 

Доказательство

 

теоремы

 

следует

 

из

 

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

 

выше

 

свойств

.

 

 

Теорема

 

2

.  

Пусть

  

векторы

 

α

0

 =(x

1

0

, …, x

n

0

)   

и

 

β

0

=(y

1

0

, …, y

m

0

)  

являются

 

допустимыми

 

решениями

 

взаимно

 

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

   

задач

 

ЛП

  (1) – (4) 

и

 (1’) – 

(4’) 

соответственно

Для

 

того

чтобы

 

векторы

  

α

0

  

и

  

β

0

  

были

 

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

 

решениями

 

этих

 

задач

 

необходимо

 

и

 

достаточно

 

выполнение

 

следующих

 

равенств

x

j

0

 

(

m

i

1

a

ij

 y

i

0

 –

 

 

γ

j

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

y

i

0

 (

n

j

1

a

ij

 x

j

0

 – b

i

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

 

Необходимост

ь

Пусть

 

векторы

   

α

0

   

и

   

β

0

   

оптимальные

 

решения

 

взаимно

 

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

  

задач

 

ЛП

  (1) – (4) 

и

 (1’) – (4’) 

соответственно

Тогда

 

по

 

свойству

  2

0

 

выполняется

 

равенство

 f(

α

0

) = 

φ

(

β

0

), 

которое

 

можно

 

записать

 

в

 

виде

γ

1

x

1

0

 + … + 

γ

n

x

n

0

 + 

γ

 =  b

1

y

1

0

 + … + b

m

y

m

0

 + 

γ

0

Это

 

равенство

 

с

 

учетом

 

соотношения

 (L

2

) , 

т

е

. (

m

i

1

a

ij

 y

i

0

)x

j

0

 

 

γ

j

 x

j

0

, j=1, 2, …, n, 

равносильно

 

неравенству

(

m

i

1

a

i1

 y

i

0

 ) x

1

0

 + … +(

m

i

1

a

i

т

 y

i

0

 ) x

т

0

 

 b

1

y

1

0

 + … + b

m

y

m

0

   

 

(a

11

y

1

0

+…+a

m1

y

m

0

)x

1

0

+…+(a

1n

y

1

0

+…+a

mn

y

m

0

)x

n

0

+

γ

0

  

 b

1

y

1

0

 + … + b

m

y

m

0

    

 

(a

11

x

1

0

+…+a

1n

x

n

0

 – b

1

)y

1

0

+…+(a

m1

x

1

0

+…+a

mn

x

n

0

 – b

m

)y

m

 

 0   

 

(

n

j

1

a

1j

 x

j

 0

– b

1

) y

1

0

 +…+  (

n

j

1

a

mj

 x

j

0

 – b

m

) y

m

0

 0. 

В

 

то

 

же

 

время

из

 

условий

 

задач

 (1) – (4)  

и

  (1

) – (4

следует

что

 

каждое

 

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

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

Москва 2013г.


background image

 

95

слагаемое

 

в

 

последнем

 

неравенстве

 

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

Поэтому

 

и

 

все

 

выражение

 

в

 

левой

 

части

 

этого

 

неравенства

 

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

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

в

 

последнем

 

соотношении

 

должно

 

быть

 

равенство

т

е

.  

(

n

j

1

a

1j

 x

j

 0

– b

1

) y

1

0

 +…+  (

n

j

1

a

mj

 x

j

0

 – b

m

) y

m

0

= 0 

Однако

 

сумма

 

неположительных

 

слагаемых

 

может

 

равняться

 

нулю

 

только

 

тогда

когда

 

каждое

 

из

 

слагаемых

 

равно

 

нулю

т

е

y

i

0

 (

n

j

1

a

ij

 x

j

0

 – b

i

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

Таким

 

образом

необходимость

 

для

 

выполнения

 

второго

 

соотношения

 

в

 

утверждении

 

теоремы

 

доказана

Необходимость

 

для

 

выполнения

 

первого

 

соотношения

 

в

 

утверждении

 

теоремы

 

доказывается

 

аналогично

Достаточность

Пусть

 

выполняются

 

равенства

x

j

0

 

(

m

i

1

a

ij

 y

i

0

 – 

γ

j

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

y

i

0

 (

n

j

1

a

ij

 x

j

0

 – b

i

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

Тогда

   f(

α

0

) = 

γ

1

x

1

0

 + … + 

γ

n

x

n

0

 + 

γ

 = x

j

0

 

(

m

i

1

a

ij

 y

i

0

) + … +  x

j

0

 

(

m

i

1

a

ij

 y

i

0

) + 

γ

0

 = (a

11

y

1

0

+…+a

m1

y

m

0

)x

1

0

+…+(a

1n

y

1

0

+…+a

mn

y

m

0

)x

n

0

+

γ

0

  = 

 = (a

11

x

1

0

+…+a

1n

x

n

0

)y

1

0

+…+(a

m1

x

1

0

+…+a

mn

x

n

0

)y

m

γ

0

 =  

 = b

1

y

1

0

 + … + b

m

y

m

0

 + 

γ

0

.= 

φ

(

β

0

т

е

. f(

α

0

) = 

φ

(

β

0

). 

Откуда

 

с

 

учетом

 

свойства

 2

0

 

следует

что

 

векторы

  

α

0

  

и

  

β

0

  

оптимальные

 

решения

 

взаимно

 

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

  

задач

 

ЛП

  (1) – (4) 

и

 (1’) – (4’) 

соответственно

.

 

Пример

Дано

   

α

0

 = (1. 0 , –4) –  

оптимальное

 

решение

 

задачи

 

ЛП

 

на

 

минимум

f(X)   =   2 x

1

 – 4 

x

  (min) 

 

x

1

 – x

 

 

1, 

 

x

– 3 

x

2

 – 2 

x

9, 

 

x

 +  x

2

 – 2 

x

7, 

 

x

1

 

0 x

2

 

0  

 

Найти

 

оптимальное

 

решение

 

взаимно

 

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

 

задачи

 

ЛП

 

на

 

максимум

используя

 2-

ю

 

теорему

  

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

 

Перепишем

 

данную

 

задачу

 

ЛП

 

в

 

стандартной

 

форме

 

и

используя

 

выше

 

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

 

правила

найдем

 

взаимно

 

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

 

к

 

ней

 

задачу

 

ЛП

 

f(X)  =   2 x

1

 – 4 

x

  (min)

 – 

x

1

 +  x

 

 

–1,

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

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

Москва 2013г.