Теоремы ТЗ

1. ТЕОРЕМЫ тз

1. Вырожденность системы
ограничений закрытой ТЗ
2. Существование допустимого плана
3. Существование опорного плана

2. 1. Вырожденность системы ограничений закрытой ТЗ

m
x
i 1
ij
n
x
j 1
ij
a
i
i
bj ,
j 1, n, (1)
ai , i 1, m. ( 2)
b
j
j
D,
(3)

3.

Суммируя ограничения (1), получим:
m
x
j
i 1
ij
bj ,
j
x
ij
D,
i, j
Суммируя ограничения (2), получим:
n
x
i
j 1
ij
ai ,
i
Ранг системы (1, 2) равен
x
ij
D.
i, j
r=m+n–1

4. 2. Существование допустимого плана

Пусть xij
ai b j
D
; i 1, m; j 1, n.
m
m
m
ai b j
i 1
i 1
D
xij
b j
a
i 1
i
D
bj ,
j 1, n,
m
n
n
ai b j
j 1
j 1
D
xij
ai
b
j 1
D
j
ai i 1, m.

5. 3. Существование опорного плана Пример цикла из загруженных клеток (Δx = ± 25)

–
25
+
70
+
40
–
50

6. Уменьшается число загруженных клеток РЕДУКЦИЯ

95
15
25