Математическое программирование и моделирование экономических процессов. Коробов П.Н. - 203 стр.

UptoLike

ВУЗ: 

СПбГЛТУ | Санкт-Петербург

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

Рубрика: 

203
u
i
+
λ
ij
v
j
=c
ij
; (5.41)
для
х
=0 (свободные) справедливо неравенство
u
i
+
λ
ij
v
j
≤
c
ij
; (5.42)
Показатели потенциалов
и
i
и
v
j
,
которые нам надо вычислить, аналогичны
потенциалам строк и столбцов в транспортной задаче, но соотношения, связывающие их
друг с другом и с показателями
c
ij
зависят от значений
λ
ij
. В ламбда-задаче для базисных
клеток должно выполняться условие:
u
i
+
λ
ij
v
j
=
c
ij
. (5.43)
Отсюда потенциал строки может быть вычислен как разность между показателем
с
ij
в базисной клетке и произведением потенциала столбца на ламбду:
u
i
=
c
ij
-
λ
ij
v
j
, (5.44)
а потенциал столбца, равен частному от деления разности показателя
c
ij
(в базисной
клетке) и потенциала строки на ламбду:
.
ij
iij
j
uc
v
λ
−
= (5.45)
В
ламбда-задаче потенциал столбца B
n+1
(с резервом времени)
всегда
принимается равным нулю,
т. е. он принимается равным показателю
с
i,n+1
V
n+1
=
c
i,n+1
=0. (5.46)
Воспользовавшись зависимостями (5.44), (5.45) и значением (5.46), вычислим
потенциалы для проверки плана табл. 5.9 на оптимальность.
Если
v
n+1
=0, то
u
2
=0-0⋅1=0 и
u
3
=0-0⋅1=0;
2
3
10
4
1
1и
4
1
8
)1(1
;115
5
1
2
;
5
1
и
5
1
10
02
;
20
1
20
01
1
24
431
−=⋅−=
=
−−
=−=⋅−=
==
−
==
−
=
u
vu
vvv
Вычисленные значения потенциалов заносим в дополнительные столбец и строку
табл. 5.9.
Далее для непосредственной проверки плана на оптимальность вычисляются
характеристики ∆
ij
, для всех свободных клеток.
В ламбда-задаче характеристика свободной клетки вычисляется как разность
между показателем
c
ij
в этой клетке и суммой потенциала строки и потенциала столбца,
умноженного на ламбду,т. е.
∆
∆∆
∆
ij
=c
ij
-(u
i
+v
j
λ
λλ
λ
ij
). (5.47)
При минимизации целевой функции (5.28) оптимальное решение задачи
наступает при ∆
∆∆
∆
ij
≥
≥≥
≥
0 для всех свободных клеток.
Поскольку в ламбда-задаче столбец
B
n+1
(с резервом времени) заполняется заново
по результатам каждого распределения (каждого плана), для свободных клеток этого
столбца характеристики не вычисляются.
По формуле (5.47) вычислим характеристики ∆
ij
для свободных клеток плана табл.
5.9 нашего примера.

Страницы