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

UptoLike

ВУЗ: 

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

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

Рубрика: 

91
10. МЕТОДЫ ОТСЕЧЕНИЙ
Методы отсечений относятся к численным методам реше-
ния дискретных задач оптимизации (методам дискретного про-
граммирования). Они предназначены для решения целочислен-
ных задач линейного программирования (ЛП). Идея методов от-
сечения состоит в следующем.
Первоначально решается обычная ("непрерывная") задача
ЛП, полученная из исходной задачи отбрасыванием требования
целочисленности. Если по лученное решение является целочис-
ленным, то оно будет также решением исходной задачи. Если
нет, то к ограничениям исходной задачи добавляется новое ли-
нейное ограничение, обладающее двумя свойствами:
1) полученное нецелочисленное решение ему не удовлетворяет;
2) все целочисленные точки допустимо го множества исходной
задачи ему удовлетворяют.
Такое ограничение называется правильным отсечением.
Затем решается расширенная непрерывная задача ЛП, т.е.
непрерывная задача с добавленным ограничением. Если полу-
ченное решение не является целочисленным, добавляется новое
правильное отсечение и т.д. Процесс повторяется до тех пор, по-
ка решение очередной расширенной непрерывной задачи ЛП не
окажется целочисленным. Таким о бразом, решение целочислен-
ной задачи ЛП св одится к решению некоторой последовательно-
сти обычных задач ЛП.
Геометрически добавление каждого такого линейного ог-
раничения означает проведение гиперплоскости, отсекающей от
многогранника допустимых решений очередной непрерывной
задачи ЛП оптимальную точк у с нецелочисленными координата-
ми, но не затрагивающей ни одной из целочисленных точек этого
многогранника. Поэтому методы, опирающиеся на эту идею, по-
лучили название методов отсечений.
Обозначим через
k
L и
)(
k
x , k=0,1,..., соответственно k-ю
расширенную непрерывную задачу ЛП и ее решение. Отметим,
что
0
L представляет соб ой исходную задачу без учета требо ва-

Страницы