Методы оптимизации. Харчистов Б.Ф. - 92 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

92
ний целочисленности. Задача L
k
+1
получается в результате добав-
ления к ограничениям задачи
k
L
(k+1)-го правильного отсечения.
Алгоритм решения целочисленной задачи ЛП методом от-
сечений заключается в следующем.
1. Решается задача ЛП L
0
.
Если задача L
0
не имеет решения, то исходная задача не
имеет целочисленного решения и вычисления завершаются.
2. Находится решение
)0(
x .
Если решение
)0(
x является целочисленным, то полагается
)(,
)0()0(
xff xx ==
∗∗
и вычисления завершаются.
Если решение
)0(
x не является целочисленным, то полага-
ется k = 1 и осуществляется переход к п. 3.
3. Определяется k-е правильное отсечение, составляется
задача L
k
.
4. Решается задача ЛП L
k
.
Если задача L
k
не имеет решения, то исходная задача не
имеет целочисленного решения и вычисления завершаются.
5. Находится решение
)(
k
x .
Если решение
)(
k
x является целочисленным, то полагается
)(,
)()(
kk
xff xx ==
∗∗
и вычисления завершаются.
Если решение
)(
k
x не является целочисленным, то полага-
ется k = k +1 и осуществляется переход к п. 3.
Конкретные способы построения правильных отсечений
приводят к конкретным вычислительным алгоритмам.
На практическом занятии рассматривается первый (дроб-
ный) алгоритм Гомори, предназначенный для решения полно-
стью целочисленных задач ЛП. Рассмотрим полностью целочис-
ленн ую задачу ЛП:
max)(
1
→
∑
=
=
n
j
jj
xcxf ,

Страницы