Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 29 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

Линейное программирование
31
i
n
j
jij
bxa =
∑
= 1
знакалюбогоy
i
−
0
≥
j
x
j
m
i
iij
cya ≥
∑
= 1
0
≤
j
x
j
m
i
iij
cya ≤
∑
= 1
знакалюбогоx
j
−
j
m
i
iij
cya =
∑
= 1
Замечание. Когда целевая функция в исходной задаче минимизирует-
ся, таблица прочитывается справа налево.
Данная таблица позволяет сформулировать несколько общих правил
построения двойственных задач.
• Каждому i-м у ограничению исходной задачи соответствует пере-
менная y
i
в ДЗ и, наоборот , каждому k-му ограничению ДЗ соответ-
ствует переменная x
k
исходной задачи .
• Матрицы ограничений в исходной и двойственной задачах взаимно
транспонированы.
• Правые части ограничений исходной задачи становятся коэффици -
ентами целевой функции в ДЗ, а коэффициенты целевой функции
исходной задачи - правыми частями ограничений в ДЗ.
• Если целевая функция в исходной задаче максимизировалась (ми-
нимизировалась), то в ДЗ целевая функция минимизируется (мак-
симизируется);
Используя данное правило построим ДЗ к ЗЛП, записанной в симмет-
ричной форме. В ДЗ целевая функция минимизируется : min
1
→
∑
=
m
i
ii
yb .
Все ограничения в симметричной форме задачи имеют вид
i
n
j
jij
bxa ≤
∑
= 1
, по-
этому на все переменные ДЗ будет присутствовать требование неотрицатель-
ности miy
i
,1,0 =≥ . На все переменные в симметричной форме присутст-
вует требование неотрицательности , поэтому ограничения ДЗ будут иметь
вид
∑
=
=≥
m
i
jiij
njcya
1
,1, . Итак, мы получили задачу
min
1
→
∑
=
m
i
ii
yb
∑
=
=≥
m
i
jiij
njcya
1
,1,
miy
i
,...,1,0
=
≥
. 
                                                                      Линейное программирование

                         n                                          y i −любого знака
                        ∑ a ij x j   =bi
                        j =1
                               x j ≥0                                  m
                                                                      ∑ a ij y i     ≥c j
                                                                       i =1
                               x j ≤0                                  m
                                                                      ∑ a ij y i ≤c j
                                                                       i =1
                   x j −любого знака                                    m
                                                                      ∑ a ij y i     =c j
                                                                       i =1
       Замечание. Когда целевая функция в исходной задаче минимизирует-
       ся, таблица прочитывается справа налево.
        Данная таблица позволяет сформулировать несколько общих правил
       построения двойственных задач.
       • Каждому i-му ограничению исходной задачи соответствует пере-
           менная yi в ДЗ и, наоборот, каждому k-му ограничению ДЗ соответ-
           ствует переменная xk исходной задачи.
       • Матрицы ограничений в исходной и двойственной задачах взаимно
           транспонированы.
       • Правые части ограничений исходной задачи становятся коэффици-
           ентами целевой функции в ДЗ, а коэффициенты целевой функции
           исходной задачи - правыми частями ограничений в ДЗ.
       • Если целевая функция в исходной задаче максимизировалась (ми-
           нимизировалась), то в ДЗ целевая функция минимизируется (мак-
           симизируется);
       Используя данное правило построим ДЗ к ЗЛП, записанной в симмет-
                                                                              m
ричной форме. В ДЗ целевая функция минимизируется :                           ∑ bi y i        → min .
                                                                              i =1
                                                                                       n
Все ограничения в симметричной форме задачи имеют вид                                 ∑ a ij x j   ≤bi , по-
                                                                                       j =1
этому на все переменные ДЗ будет присутствовать требование неотрицатель-
ности y i ≥0, i =1, m . На все переменные в симметричной форме присутст-
вует требование неотрицательности, поэтому ограничения ДЗ будут иметь
      m
вид   ∑ a ij y i ≥c j , j =1, n .    Итак, мы получили задачу
      i =1
                                               m
                                               ∑ bi y i → min
                                               i =1
                                           m
                                        ∑ a ij y i ≥c j , j =1, n
                                        i =1
                                           y i ≥0, i =1,..., m .


                                                      31

Страницы