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

UptoLike

Рубрика: 

Линейное программирование
45
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 =c ij , (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 =c ij , (i, j ) ∈Ω B .
Если существует пара индексов (i, j )∉Ω B , для которой
                              u i0 +v 0j >cij ,
то существует базисное решение X =(xij ), для которого
                                   m                m
                                   ∑ ∑ cij xij ≤∑ ∑ c ij xij0 ,                                 (6)
                                   i =1 j =1       i =1 j =1

если для всех пар индексов                     (i, j )∉Ω B     выполнено          u i0 +v 0j ≤cij , то
 X =( x ij0 ), 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 ) . От-
метим, что каждые две рядом стоящие пары индексов должны иметь оди-
наковые номера строк или одинаковые номера столбцов. Сами пары, входя-
щие в цикл, называются элементами цикла..

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




                                                 45