Линейное программирование. Азарнова Т.В - 42 стр.

UptoLike

Рубрика: 

Линейное программирование
44
Bijji
jicvu
=
+
),(,
, (5)
где
B
- множество базисных пар индексов . Заметим , что система (5) име-
ет
m
n
+
переменных и
1
+
n
m
уравнение. Ранг системы равен
1
+
n
m
.
Отсюда следует , что одну из переменных можно выбрать произвольно, на-
пример , 0
1
=
u , а все остальные переменные найти по цепочке .
Сформулируем теперь критерий оптимальности для транспортной задачи .
Пусть njmixX
ij
,1,,1),(
0
=== - некоторое базисное решение транспортной
задачи ,
B
- множество базисных пар индексов данного базисного решения,
miu
i
,1,
0
= и njv
j
,1,
0
= - произвольное решение системы
Bijji
jicvu
=
+
),(,
.
Если существует пара индексов
(
)
B
ji
, , для которой
ijji
cvu >+
00
,
то существует базисное решение
(
)
ij
xX
=
, для которого
∑∑
====
m
ij
ijij
m
ij
ijij
xcxc
11
0
11
, (6)
если для всех пар индексов
(
)
B
ji
, выполнено
ijji
cvu ≤+
00
, то
njmixX
ij
,1,,1),(
0
=== - решение задачи . Заметим , что для транспортной за -
дачи гарантируется построение новой базисной точки , так как эта задача при
соблюдении баланса всегда разрешима. Отметим также, что неравенство (6)
является нестрогим в связи с возможностью вырожденности базисных точек.
Как следует из алгоритма симплексного метода , если существует вектор
00
ji
A
с положительной оценкой, то вектор
00
ji
A
должен быть введен в базис.
Для введения вектора в базис нужно знать его текущие координаты. Заметим ,
что эти координаты являются коэффициентами разложения вектора
00
ji
A
по
текущему базису. В транспортной задачи для определения координат исполь-
зуется понятие цикла .
Определение. Говорят , что множество пар индексов
(
)
ji , образует
цикл, если их можно расположить, например , в следующей последователь-
ности: ),(),(),(...),(),(),(
000111000
jijijijijiji
kkk
. От -
метим , что каждые две рядом стоящие пары индексов должны иметь оди-
наковые номера строк или одинаковые номера столбцов. Сами пары , входя-
щие в цикл, называются элементами цикла ..
Рассмотрим пример цикла .
Линейное программирование


                                 u i +v j =cij , (i, j ) ∈Ω B ,            (5)
где Ω B - множество базисных пар индексов. Заметим, что система (5) име-
ет n +m переменных и m +n −1 уравнение. Ранг системы равен m +n −1 .
Отсюда следует, что одну из переменных можно выбрать произвольно, на-
пример, u1 =0 , а все остальные переменные найти по цепочке.
Сформулируем теперь критерий оптимальности для транспортной задачи.
Пусть X =( xij0 ), i =1, m, j =1, n - некоторое базисное решение транспортной
задачи, Ω B - множество базисных пар индексов данного базисного решения,
u i0 , i =1, m и v 0j , j =1, n - произвольное решение системы
                                   u i +v j =cij , (i, j ) ∈Ω B .
Если существует пара индексов (i , j )∉Ω B , для которой
                              u i0 +v 0j >cij ,
то существует базисное решение X =(x ij ), для которого
                                   m               m
                                  ∑ ∑ cij xij ≤∑ ∑ cij xij0 ,                                  (6)
                                  i =1 j =1       i =1 j =1

если для всех пар индексов                    (i, j )∉Ω B     выполнено          u i0 +v 0j ≤cij , то
 X =( xij0 ), i =1, m, j =1, n - решение задачи. Заметим, что для транспортной за-
дачи гарантируется построение новой базисной точки, так как эта задача при
соблюдении баланса всегда разрешима. Отметим также, что неравенство (6)
является нестрогим в связи с возможностью вырожденности базисных точек.
Как следует из алгоритма симплексного метода, если существует вектор
 Ai0 j0 с положительной оценкой, то вектор Ai0 j0 должен быть введен в базис.
Для введения вектора в базис нужно знать его текущие координаты. Заметим,
что эти координаты являются коэффициентами разложения вектора Ai0 j0 по
текущему базису. В транспортной задачи для определения координат исполь-
зуется понятие цикла.

      Определение. Говорят, что множество пар индексов (i, j ) образует
цикл, если их можно расположить, например, в следующей последователь-
ности: (i 0 , j 0 ) → (i 0 , j1 ) → (i1 , j1 ) → ... → (i k , j k ) → (i k , j 0 ) → (i 0 , j 0 ) . От-
метим, что каждые две рядом стоящие пары индексов должны иметь оди-
наковые номера строк или одинаковые номера столбцов. Сами пары, входя-
щие в цикл, называются элементами цикла..

         Рассмотрим пример цикла.




                                                44