Автоматизация технологического проектирования. Смирнов О.Л. - 25 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

25
12. Решение целочисленных задач линейного
программирования методом отсечений
(теоретическое обоснование)
Пусть решена задача линейного программирования симплекс-мето-
дом и получена каноническая форма целевой функции и ограничитель-
ных равенств для оптимального базиса, т. е. оптимальной вершины сим-
плекса, и некоторые небазисные переменные
j
k
x
из исходной постанов-
ки задачи оказались нецелочисленными:
11 2 2
0
... ;
nn
ii ii i i
xcxcx cx c
++ ++ =
(31)
11 2 2
... , 1, ..., ;
jnnj
kjiijii jiik
xaxax axb j m
++ ++ = =
(32)
0
j
k
x ≥
и должны быть целыми. (33)
Обоснование метода.
Выбираем нецелочисленное
s
k
x
,
11 2 2
...
snn
s
ksiisii siik
xaxax axb++ ++ =
, (34)
в котором некоторые
t
s
i
a
и
k
– дробные.
Обозначим через [D] – целую, а через [f] – дробную части рацио-
нального числа.
Из условий
0
s
k
x ≥
и
[
]
t
t
si si
aa
≤
следует
11 2 2
[ ] [ ] ... [ ] .
snns
ksiisii siik
xaxax axb
++ ++ ≤
(35)
Поскольку
1
, ...,
n
ii
xx
и
s
k
x
– целые, то и
11 22
[] []
s
ksiisii
xaxax
++ +
+
... [ ]
n
n
si i
ax
+
– целое.
Тогда
11 2 2
[ ] [ ] ... [ ] [ ].
snns
ksiisii siik
xaxax axb
++ ++ ≤
(36)
Добавим в левую часть (36) дополнительную переменную х, тогда
11 22
[ ] [ ] ... [ ] [ ].
snns
ksiisii sii k
xaxax axxb
++ ++ +=
(37)

Страницы