Вывод ограничения, отсекающего нецелочисленное решение.
Постановка задачи ЛП с ЦЧР
Σ сj*xj -> max (5)
Σ aij*xj = bj , i = 1,..,m (6)
xj ≥ 0 и целочисленные (7)
Пусть оптимальное решение существует и имеет конечное значение и
Пусть Σ aj*xj = b (8)
сумма нескольких уравнений из (6), каждое из которых умножено на свою постоянную.
Поэтому решение, удовлетворяющее (6), удовлетворяет и (8).
Пусть некоторые коэффициенты aj и b не целочисленные. Так как xj должны быть
целочисленными, то нецелочисленные aj и b надо заменить на целочисленные [aj] и [ b] ,
такие, что aj = [aj] + fj и b = [ b] + f, где 0 ≤ fj , f ≤ 1.
Тогда (8) станет неравенством Σ [aj]*xj ≤ [b] (9)
Покажем, что это так на примере 7*X1 +4.5*X2 = 31.5
Заменим 4.5 на 4 и 31.5 на 31, тогда 7*X1 +4*X2 = 28 ≤ 31.
Добавим слева в (9) неизвестную x. Получим Σ [aj]*xj + x = [b] (10).
Очевидно, что x - целочисленная.
Значит (10) - ограничение, отсекающее нецелочисленное решение.
При решении задачи ЦЛП удобнее использовать другую форму этого ограничения, получаемую вычитанием (8) из (10). Получаем Σ [aj]*xj - Σ aj*xj + x = b - [b] , или
Σ [-fj]*xj + x = -f (11)
Вывод ограничения из уравнения базисной переменной
Алгоритм определения оптимального целочисленного решения
1. Решить задачу ЛП симплекс-методом.
2. Если решение целочисленное, прекратить решение.
3. Добавить целочисленное ограничение, полученное из уравнения базисной переменной и перейти к п. 1.
Пусть уравнение базисной переменной имеет вид:
xk + Σ tij*xj = b, i - строка, j – небазисные переменные (18).
Пусть некоторые tij = [tij] + fij и b = [ b] + f нецелочисленные, тогда добавляется целочисленное ограничение, отсекающее нецелочисленное решение задачи:
xk + Σ [-fj]*xj + x = -f (19).
Пример
21*X1 + 11*X2 -> max
7*X1 + 4*X2 + X3 = 13
Получить целочисленное решение.
X0 - 21*X1 - 11*X2 = 0
X0 + X2 + 3*X3 = 39
X1 + 4/7*X2 + 1/7*X3 = 1 6/7
- 4/7*X2 - 1/7*X3 + X4 = - 6/7
X0 +2¾*X3 +7/4*X4 = 37 1/2
X1 + X4 = 1
X2 + 1/4*X3 - 1¾*X4 = 1 ½
- 1/4*X3 - ¼*X4 + X5 = - ½
X0 - X4 +11*X5 = 32
X1 + X4 = 1
X2 - 2*X4 + X5 = 1
X3 + X4 - 4*X5 = 2
X0 + X1 +11*X5 = 32
X1 + X4 = 1
2*X1 + X2 = 3
- X1 + X3 - 4*X5 = 1
Задания по целочисленному программированию
Пример 1
00
21x1 + 11x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
01
22x1 + 11x2 -> max
7x1 + 3x2 + x3 = 13 x1,x2,x3 => 0
02
21x1 + 12x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
03
21x1 + 11x2 -> max
7x1 + 3x2 + x3 = 13 x1,x2,x3 => 0
04
21x1 + 11x2 -> max
8x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
05
22x1 + 11x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
06
21x1 + 12x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
07
21x1 + 11x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
08
21x1 + 11x2 -> max
7x1 + 5x2 + x3 = 13 x1,x2,x3 => 0
09
21x1 + 11x2 -> max
8x1 + 3x2 + x3 = 13 x1,x2,x3 => 0
10
21x1 + 11x2 -> max
8x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
11
21x1 + 11x2 -> max
7x1 + 4x2 + x3 = 14 x1,x2,x3 => 0
12
21x1 + 11x2 -> max
7x1 + 4x2 + x3 = 15 x1,x2,x3 => 0
13
21x1 + 13x2 -> max
7x1 + 4x2 + x3 = 15 x1,x2,x3 => 0
14
23x1 + 11x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
15
21x1 + 11x2 -> max
7x1 + 5x2 + x3 = 13 x1,x2,x3 => 0
16
21x1 + 13x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
17
21x1 + 12x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
18
23x1 + 11x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
19
21x1 + 12x2 -> max
7x1 + 4x2 + x3 = 14 x1,x2,x3 => 0
20
21x1 + 11x2 -> max
7x1 + 4x2 + x3 = 16 x1,x2,x3 => 0
21
21x1 + 11x2 -> max
7x1 + 4x2 + x3 = 14 x1,x2,x3 => 0
22
20x1 + 11x2 -> max
7x1 + 4x2 + x3 = 15 x1,x2,x3 => 0
23
21x1 + 10x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
24
21x1 + 12x2 -> max
7x1 + 3x2 + x3 = 13 x1,x2,x3 => 0
25
21x1 + 14x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
26
21x1 + 12x2 -> max
7x1 + 4x2 + x3 = 17 x1,x2,x3 => 0
27
22x1 + 11x2 -> max
7x1 + 5x2 + x3 = 13 x1,x2,x3 => 0
28
21x1 + 12x2 -> max
9x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
29
21x1 + 11x2 -> max
7x1 + 4x2 + x3 = 13 x1,x2,x3 => 0
30
20x1 + 11x2 -> max
7x1 + 4x2 + x3 = 11 x1,x2,x3 => 0
31
21x1 + 11x2 -> max
7x1 + 4x2 + x3 = 15 x1,x2,x3 => 0
32
21x1 + 10x2 -> max
7x1 + 4x2 + x3 = 17 x1,x2,x3 => 0
Пример 2
00
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
01
3x1 + 4x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
02
4x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
03
3x1 + 3x2 + 14x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
04
3x1 + 3x2 + 13x3 -> max
-4x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
05
3x1 + 3x2 + 13x3 -> max
-3x1 + 7x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
06
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 8x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
07
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 5x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
08
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 4x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
09
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
10
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 8x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
11
4x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 9 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
12
3x1 + 4x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 9 0 ≤ x1,x2,x3 ≤ 5
13
3x1 + 3x2 + 14x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
14
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 9 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
15
3x1 + 3x2 + 13x3 -> max
-4x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 9 0 ≤ x1,x2,x3 ≤ 5
16
3x1 + 3x2 + 13x3 -> max
-3x1 + 7x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 9 0 ≤ x1,x2,x3 ≤ 5
17
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 8x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 9 0 ≤ x1,x2,x3 ≤ 5
18
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 9 7x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
19
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 9 6x1 – 4x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
20
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 9 6x1 – 3x2 + 8x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
21
5x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 9 0 ≤ x1,x2,x3 ≤ 5
22
3x1 + 5x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 9 0 ≤ x1,x2,x3 ≤ 5
23
3x1 + 3x2 + 15x3 -> max
-3x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 9 0 ≤ x1,x2,x3 ≤ 5
24
5x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 9 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
25
3x1 + 5x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 9 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
26
3x1 + 3x2 + 15x3 -> max
-3x1 + 6x2 + 7x3 ≤ 9 6x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
27
3x1 + 3x2 + 13x3 -> max
-5x1 + 6x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 9 0 ≤ x1,x2,x3 ≤ 5
28
3x1 + 3x2 + 13x3 -> max
-3x1 + 8x2 + 7x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 9 0 ≤ x1,x2,x3 ≤ 5
29
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 9x3 ≤ 8 6x1 – 3x2 + 7x3 ≤ 9 0 ≤ x1,x2,x3 ≤ 5
30
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 9 8x1 – 3x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
31
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 9 6x1 – 5x2 + 7x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
32
3x1 + 3x2 + 13x3 -> max
-3x1 + 6x2 + 7x3 ≤ 9 6x1 – 3x2 + 9x3 ≤ 8 0 ≤ x1,x2,x3 ≤ 5
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.