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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Линейное программирование
47
Алгоритм метода потенциалов
Итерация 0.
0.1. Определяется начальный базис с помощью любого из алгоритмов по-
строения начальной базисной точки .
0.2. Вычисляется значение функции цели
∑
∈
=
Ωji
ijij
xcxL
,
00
)(
, Ω - множество
базисных индексов .
0.3. Полагаем к =0.
Итерация к+1.
Пусть на к-той итерации получена базисная точка
k
x
со значением целевой
функции )(
k
xL .
k+1.1. Полагают 0
1
=
u и определяют .),(,
1
Ω
∈
−
=
jiucv
1jj
Если некоторое
s
v вычислено, то определяют
Ω
∈
−
=
),(, sivcu
sisi
, и т.д., пока не будут вы-
числены все miu
i
,1, = и njv
j
,1, = .
k+1.2. Вычисляют оценки небазисных векторов .
ijjiij
cvu
−
+
=
∆
k+1.3. Выбирают
.max
,
00
ij
ji
ji
∆
∆
=
k+1.4. Если
,0
00
≤
ji
∆
то останов ,
k
x
- решение задачи .
k+1.5. По правилу вычеркивания определяют цикл, образованный парой
),(
00
ji вместе с базисными парами индексов .
Пусть
+
Ω
-множество четных элементов цикла ,
−
Ω
- множество нечетных
элементов цикла без
),(
00
ji
.
k+1.6. Определяют
k
ij
x
ji
−
∈
=
Ω
Θ
),(
min .
k+1.7. Полагают Θ=
+1
00
k
ji
x ,
−+
∈−= ΩΘ ),(,
1
jixx
k
ij
k
ij
,
++
∈+= ΩΘ ),(,
1
jixx
k
ij
k
ij
,
)(\),(,
1 +−+
∪∈= ΩΩΩ jixx
k
ij
k
ij
.
k+1.8. Определяют
ijji
cc
ij
xji
ll
0,),(
max
=
−
∈
=
Ω
и элемент
ll
ji
c
считают небазисным .
k+1.9. Вычисляют
00
)()(
1
ji
kk
xLxL Θ∆−=
+
.
k+1.10. Полагают к=к+1.
Пример . 3 
                                                                     Линейное программирование


                          Алгоритм метода потенциалов

Итерация 0.
0.1. Определяется начальный базис с помощью любого из алгоритмов по-
     строения начальной базисной точки.
0.2. Вычисляется значение функции цели L( x 0 ) = ∑ c ij x ij0 , Ω- множество
                                                                    i , j∈Ω
      базисных индексов.
0.3. Полагаем к=0.
Итерация к+1.
Пусть на к-той итерации получена базисная точка x k со значением целевой
функции L ( x k ) .
k+1.1. Полагают u1 =0 и определяют v j =c1j −u1 , (i, j ) ∈Ω . Если некоторое
v s вычислено, то определяют u i =c is −v s , (i, s ) ∈Ω , и т.д., пока не будут вы-
числены все u i , i =1, m и v j , j =1, n .
k+1.2. Вычисляют оценки небазисных векторов.
∆ij =u i +v j −c ij
k+1.3. Выбирают ∆i0 j 0 =max ∆ij .
                              i, j

k+1.4. Если ∆i0 j 0 ≤0, то останов, x k - решение задачи.
k+1.5. По правилу вычеркивания определяют цикл, образованный парой
(i 0 , j 0 ) вместе с базисными парами индексов.
Пусть Ω +-множество четных элементов цикла, Ω − - множество нечетных
элементов цикла без (i 0 , j 0 ) .
k+1.6. Определяют Θ = min                 x ijk .
                           (i , j )∈Ω −
k+1.7. Полагают                         x ik +j1 =Θ ,
                                          0 0

                              x kij+1   =x ijk −Θ , (i, j ) ∈Ω −,

                              x kij+1 =x ijk +Θ , (i, j ) ∈Ω +,

                         x kij+1 =x ijk , (i, j ) ∈Ω \ (Ω − ∪ Ω +) .
k+1.8. Определяют c il jl =             max          c ij и элемент c il jl считают небазисным.
                             (i , j )∈Ω −, xij =0


k+1.9. Вычисляют L( x k +1 ) =L( x k ) −Θ∆i0 j 0 .
k+1.10. Полагают к=к+1.

Пример. 3

                                                    47

Страницы