Составители:
Рубрика:
105
,,...,,0,,...,
,0,...,0,,0,...,0,0
''
11
'
11
'
11
1
'
121
mmnssnsnssnn
nkskk
bxbxxbxbx
xxbxxxx
=====
======
+++++−−++
+−
которому соответствует новое значение целевой функции:
'''
'
11
'
11
'
22
'
11
'
...
......
skmmn
ssnssnnn
bcbc
bcbcbcbcF
++
+++++=
+
+++−−+++
или, учитывая формулу пересчета свободных членов, имеем:
.)(...
...)()(
)(...)(
,111
,111111
'
βαβ
αβαβ
αβαβ
kmkmmn
ksssnsksn
ksssnkn
cbc
bcbc
bcbcF
+−+
+−+−+
+−++−=
+
+++++
−−−++
(3.5)
Правая часть этого равенства дополнена членом
c
n+s
(
b
s
-
βα
sk
), который в силу
определения числа
sk
s
b
α
β
=
равен нулю и поэтому
не изменяет значения
F'.
Равенство
можно записать в виде:
∑
∑
−−=
++
i
kikin
i
iin
ccbcF
)(
'
αβ
или учитывая, что
∑
i
ii
bc
=
F —
значение целевой функции при исходном опорном решении
и
∑
∆=−
+
i
kkkiin
cc
α
—
двойственная
оценка
k-ro
столбца, имеем:
F' = F
-
β∆
k
. (3.6)
Формула (3.6) дает связь между значениями целевой функции на двух смежных
опорных решениях. Так как число
β
, являющееся значением новой базисной переменной
х
k
,
положительно то из формулы (3.6) видно, что увеличение значения целевой функции
получится только в том случае, когда оценка
∆
k
отрицательна и целевая функция
уменьшится только при положительной оценке
∆
k
.
Отсюда и получается правило:
при решении задачи максимизации в качестве
ключевого столбца надо брать тот столбец, для которого оценка ∆
k
отрицательна и в
котором имеются положительные элементы.
В случае задачи минимизации можно
сохранить то же правило, что и в случае максимизации, если оценки
∆
j
брать с
противоположными знаками, т. е. если в нижнюю строку записать величины
∑
−=∆−=
i
ijijjj
cc
.
αω
Из равенства (3.6) находим:
β
FF
k
−
−=∆
'
. (3.7)
Таким образом, число
∆
K
.
характеризует изменение целевой функции
F,
приходящееся
на единицу значения новой базисной переменной
x
k
=
β
.
Слово «двойственная оценка»
объясняется тем, что выражения оценок
∑
=−=∆
i
jijij
njcc
,...,2,1,
α
в исходной симплексной таблице являются значениями левых частей ограничений —
неравенств
∑
≥−
i
jiji
cy
0
α
, при
y
i
=
c
i
,
двойственной задачи, о которой речь пойдет ниже. В
Страницы
- « первая
- ‹ предыдущая
- …
- 103
- 104
- 105
- 106
- 107
- …
- следующая ›
- последняя »
