ВУЗ:
Составители:
Рубрика:
Линейное программирование
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
Страницы
- « первая
- ‹ предыдущая
- …
- 41
- 42
- 43
- 44
- 45
- …
- следующая ›
- последняя »