Задачи линейного программирования транспортного типа. Горячев Л.В. - 4 стр.

UptoLike

ВУЗ: 

ДВФУ | Владивосток

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

Рубрика: 

4
Задачи (1)–(3) и (4)–(5) называют парой двойственных (сопряженных) задач.
Теорема
. Если одна из пары двойственных задач имеет решение, то сопряженная с ней задача
также разрешима и на оптимальных планах этих задач значения целевых функций совпадают.
Пара условий: x
j
≥ 0,
a
ij
y
i
≥ c
j
,j=1, 2,...,n называются сопряженными парами условий
для задач (1)–(3) и (4)–(5).
Теорема
. В каждой паре сопряженных условий на оптимальный планах: если одно свободное, то
другое — закрепленное.
Перечисленные свойства задач ЛП широко используются для анализа задач транспортного типа.
Рассмотрение начнем с простейших моделей. К их числу относится модель следующего типа:
n
j=1
c
j
x
j
− min
при условиях
n
j=1
x
j
= b, x
j
≥ 0,j=1, 2,...,n
В этой задаче система ограничений, кроме ограничений на знак переменных, состоит из одного урав-
нения. Поэтому опорный план содержит одну положительную компоненту, а оптимальный опорный
план легко находится. Действительно, пусть min{c
j
} = c
j
0
, тогда компоненты оптимального опор-
ного плана
x
∗
j
=
b
j
,j= j
0
0,j= j
0
К этой задаче приводится следующая:
n
j=1
c
j
x
j
− min
при условиях
n
j=1
a
j
x
j
= b, x
j
≥ 0,j=1, 2,...,n
Замена переменной y
j
= a
j
x
j
приводит нас к предыдущей модели. Таким образом, решение одно-
индексных транспортных задач (Т.З.) тривиально.
Простейшие двухлинейные Т.З. также не вызывают серьезных трудностей при анализе: найти
набор X = x
ij
, минимизирующий линейную форму
m
i=1
n
j=1
c
ij
x
ij
при условиях
n
j=1
a
ij
x
ij
= a
i
,x
ij
≥ 0,i=1, 2,...,m,j =1, 2,...,n
Эта задача распадается на m одноиндексных задач, решение которых тривиально. Оптимальный
план исходной задачи формируется из оптимальных решений частных задач. Другой простейшей
двухидексной задачей транспортного типа является задача: найти набор X = x
ij
, минимизирую-
щий
m
i=1
n
j=1
c
ij
x
ij
при условиях
m
i=1
n
j=1
a
ij
x
ij
= b, x
ij
≥ 0,i=1, 2,...,m,j =1, 2,...,n
4

Задачи (1)–(3) и (4)–(5) называют парой двойственных (сопряженных) задач.
   Теорема. Если одна из пары двойственных задач имеет решение, то сопряженная с ней задача
также разрешима и на оптимальных
                                      планах этих задач значения целевых функций совпадают.
   Пара условий: xj ≥ 0,     aij yi ≥ cj , j = 1, 2, . . . , n называются сопряженными парами условий
для задач (1)–(3) и (4)–(5).
   Теорема. В каждой паре сопряженных условий на оптимальный планах: если одно свободное, то
другое — закрепленное.
   Перечисленные свойства задач ЛП широко используются для анализа задач транспортного типа.
   Рассмотрение начнем с простейших моделей. К их числу относится модель следующего типа:
                                                   n
                                                   
                                                         cj xj − min
                                                   j=1

при условиях
                                     n
                                     
                                             xj = b, xj ≥ 0, j = 1, 2, . . . , n
                                     j=1

В этой задаче система ограничений, кроме ограничений на знак переменных, состоит из одного урав-
нения. Поэтому опорный план содержит одну положительную компоненту, а оптимальный опорный
план легко находится. Действительно, пусть min{cj } = cj0 , тогда компоненты оптимального опор-
ного плана                                   
                                               bj , j = j0
                                       x∗j =
                                               0, j = j0
К этой задаче приводится следующая:
                                                   n
                                                   
                                                         cj xj − min
                                                   j=1

при условиях
                                    n
                                    
                                          aj xj = b, xj ≥ 0, j = 1, 2, . . . , n
                                    j=1

Замена переменной yj = aj xj приводит нас к предыдущей модели. Таким образом, решение одно-
индексных транспортных задач (Т.З.) тривиально.
   Простейшие двухлинейные Т.З. также не вызывают серьезных трудностей при анализе: найти
набор X = xij , минимизирующий линейную форму
                                                    m 
                                                     n
                                                               cij xij
                                                     i=1 j=1

при условиях
                      n
                      
                            aij xij = ai ,     xij ≥ 0,     i = 1, 2, . . . , m, j = 1, 2, . . . , n
                      j=1

Эта задача распадается на m одноиндексных задач, решение которых тривиально. Оптимальный
план исходной задачи формируется из оптимальных решений частных задач. Другой простейшей
двухидексной задачей транспортного типа является задача: найти набор X = xij , минимизирую-
щий
                                        m n
                                               cij xij
                                                     i=1 j=1

при условиях
                     m 
                      n
                               aij xij = b,      xij ≥ 0,      i = 1, 2, . . . , m, j = 1, 2, . . . , n
                     i=1 j=1

Страницы