ВУЗ:
Составители:
Рубрика:
93
i
n
j
jij
bxa
≤
∑
=
1
, mi ,1= ,
0≥
j
x ,
nj
,1
=
,
j
x − целые, nj ,1= .
Отметим, что для применения первого алгоритма Гомори
все ко эффициенты и правые части ограничений исходной задачи
должны быть приведены к целочисленному виду.
Первоначально решается задача L
0
. Пусть решение
)0(
x
этой задачи не является целочисленным. Согласно общему алго-
ритму, следует определить дополнительное ограничение (1-е
правильное отсечение). Пусть последняя симплекс-таблица зада-
чи L
0
имеет следующий вид:
Базис
Своб.
член
1
x
′
...
m
x
′
1
x
′′
...
n
x
′′
1
x
′
1
b
1...0
11
a
...
n
a
1
"""
...
""
...
"
m
x
′
m
b
0...1
1m
a
...
mn
a
f
0
b
0...0
1
c
...
n
c
Здесь через
i
x
′
, mi ,1= , обозначены базисные переменные,
а через
j
x
′′
, nj ,1= , − свободные переменные. Такая система
обозначений выбрана из соображений удобства.
Строки симплекс-таблицы, которым соответствуют неце-
лые значения базисных переменных, т.е. нецелые
i
b , называют
производящими. Каждая производящая строка задает правильное
отсечение, которое определяется следующим образом: i-я произ-
водящая строка записывается в виде
}{][}){]([)01(
1
ii
n
j
jijij
bbxaa
i
x +=
∑
′′
++
′
+
=
,
Страницы
- « первая
- ‹ предыдущая
- …
- 91
- 92
- 93
- 94
- 95
- …
- следующая ›
- последняя »
