Составители:
Рубрика:
26
Уравнение (37) получено алгебраическими операциями из уравне-
ний (32), поэтому любое решение для системы (32) удовлетворяет и
(37). Следовательно, уравнение (37) надо добавить в систему (32) и
решать ее симплекс-методом для получения нового решения, учитыва-
ющего ограничение на целочисленность переменных и определяемого
уравнением (37).
Для упрощения решения преобразуем (37) в уравнение, выраженное
через дробные части входящих в него коэффициентов
t
s
i
a
и свободного
члена
s
k
b
, вычитанием (11) из (8). Получим
11 2 2
(
) ( ) ... ( )
nn
s
si i si i si i k
fx fx fx f−+− ++− =−
, (38)
где
[
]
tt t
si si si
fa a=−
,
[].
ss s
kk k
fbb
=−
(39)
Алгоритм отсечения
1. Найти оптимальное решение задачи с целочисленной функцией
(31) и линейными ограничениями (32), не учитывая (33), но требуя по-
ложительности
x
k
j
.
2. Прекратить вычисления, если текущее решение – целочислен-
ное. В противном случае выбрать дробную небазисную переменную, со-
ставить ограничение (38) из уравнения, содержащего эту небазисную пе-
ременную в текущем оптимальном решении. Добавить к исходной зада-
че линейного программирования 2 это новое ограничение и вернуться
к шагу 1.
13. Решение целочисленных задач
линейного программирования методом отсечений
(пример решения)
Рассмотрим задачу: максимизировать 21x
1
+ 11x
2
при ограничении
7x
1
+ 4x
2
+ x
3
= 13, (40)
где x
1
, x
2
, x
3
– неотрицательные целые. Переменная x
3
– дополняющая,
поскольку не входит в целевую функцию. Выразим целевую в соответ-
ствии с принятой схемой
x
0
– 21x
1
– 11x
2
= 0. (41)
Страницы
- « первая
- ‹ предыдущая
- …
- 24
- 25
- 26
- 27
- 28
- …
- следующая ›
- последняя »
