2.2 Решение частично целочисленной задачи
Максимизировать целевую функцию:
Y=-4x1-5x2-17x3+2x4 → max
При ограничениях:
-2x1+2x2-2x3+3x4 ≤ 3
3x1-3x3+5x4 ≥ 2
-x1-5x2-4x3-x4 ≤ -11
2x1+2x2+3x3 ≥ 10
x1,2,3,4 ≥ 0
x4 - целое
2.1.1 Решение задачи методом отсекающих плоскостей (метод Гомори)
Приведём решение исходной задачи симплекс-методом, опустив требование целочисленности. Оно представлено в таблице 2.53.
Таблица 2.53
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
|
X4 |
7/2 |
0 |
0 |
-3/4 |
1 |
1/2 |
0 |
1/2 |
-3/4 |
|
X6 |
229/8 |
0 |
0 |
21/16 |
0 |
23/8 |
1 |
29/8 |
-99/16 |
|
X2 |
5/8 |
0 |
1 |
13/16 |
0 |
-1/8 |
0 |
-3/8 |
5/16 |
|
X1 |
35/8 |
1 |
0 |
11/16 |
0 |
1/8 |
0 |
3/8 |
-13/16 |
|
Y |
-109/8 |
0 |
0 |
139/16 |
0 |
9/8 |
0 |
11/8 |
3/16 |
Значение переменной x4 не удовлетворяет требованиям целочисленности. Поэтому вводим дополнительное отсечение, исходя из данной строки.
Ограничения для частично-целочисленных задач по методу Гомори формируются в виде:
где
- дробная часть свободного члена базисной
переменной,
- коэффициент, рассчитываемый для
небазисных переменных.
Для
не подчиненных требованию целочисленности
коэффициент
рассчитывается по формуле:
Для
подчиненных требованию целочисленности
коэффициент
рассчитывается по формуле:
Вычислим отсекающую плоскость и представим ее в форме Таккера:
X9=-1/2-(-3/4*X3-1/2*X5-1/2*X7-3/4*X8)
Добавим в базис таблицы 2.53 полученное ограничение. Результат представлен в таблице 2.54.
Таблица 2.54
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X4 |
7/2 |
0 |
0 |
-3/4 |
1 |
1/2 |
0 |
1/2 |
-3/4 |
0 |
|
X6 |
229/8 |
0 |
0 |
21/16 |
0 |
23/8 |
1 |
29/8 |
-99/16 |
0 |
|
X2 |
5/8 |
0 |
1 |
13/16 |
0 |
-1/8 |
0 |
-3/8 |
5/16 |
0 |
|
X1 |
35/8 |
1 |
0 |
11/16 |
0 |
1/8 |
0 |
3/8 |
-13/16 |
0 |
|
X9 |
-1/2 |
0 |
0 |
-3/4 |
0 |
-1/2 |
0 |
-1/2 |
-3/4 |
1 |
|
Y |
-109/8 |
0 |
0 |
139/16 |
0 |
9/8 |
0 |
11/8 |
3/16 |
0 |
Используем двойственный симплекс-метод. Вводим в базис X8, выводим из базиса X9.
Таблица 2.55
|
БП |
СЧ |
X1 |
X2 |
X3 |
X4 |
X5 |
X6 |
X7 |
X8 |
X9 |
|
X4 |
4 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
-1 |
|
X6 |
131/4 |
0 |
0 |
15/2 |
0 |
7 |
1 |
31/4 |
0 |
-33/4 |
|
X2 |
5/12 |
0 |
1 |
2/4 |
0 |
-2/6 |
0 |
-7/12 |
0 |
5/12 |
|
X1 |
59/12 |
1 |
0 |
6/4 |
0 |
4/6 |
0 |
11/12 |
0 |
-13/12 |
|
X8 |
2/3 |
0 |
0 |
1 |
0 |
2/3 |
0 |
2/3 |
1 |
-4/3 |
|
Y |
-55/4 |
0 |
0 |
17/2 |
0 |
1 |
0 |
5/4 |
0 |
1/4 |
Полученное оптимальное решение удовлетворяет требованию целочисленности х4.
Ответ: Y=-55/4, X=(59/12;5/12;0;4;0;131/4;0;2/3;0).