1) Найдем оптимальное целочисленное решение данной задачи методом Гомори:
Значения базисных переменных не являются целыми.
Дополнительное ограничение целесообразно составлять для строки, содержащей в столбце базисных переменных наибольшую дробную часть.
Наибольшая дробная
часть у значения переменной
.
Определяем значения
и
:
Дополнительное ограничение имеет вид:
Приводим к канонической форме:
Вводим новую строку в симплекс-таблицу:
|
Базис |
B |
|
|
|
|
|
|
|
|
|
|
3 13/21 |
1 |
0 |
0 |
5/21 |
0 |
0 |
4/21 |
0 |
|
|
17/21 |
0 |
0 |
1 |
- 8/21 |
0 |
0 |
2/21 |
0 |
|
|
8/21 |
0 |
0 |
0 |
-1 5/21 |
1 |
0 |
- 4/21 |
0 |
|
|
6 17/21 |
0 |
1 |
0 |
13/21 |
0 |
0 |
2/21 |
0 |
|
|
17 1/21 |
0 |
0 |
0 |
-2 19/21 |
0 |
1 |
-1 11/21 |
0 |
|
|
- 17/21 |
0 |
0 |
0 |
- 13/21 |
0 |
0 |
- 2/21 |
1 |
|
|
86 4/21 |
0 |
0 |
0 |
7 8/21 |
0 |
0 |
1 19/21 |
0 |
Так как базисная
переменная
имеет отрицательное значение, то данную
задачу решаем двойственным симплекс-методом.
Переменную
вводим в число базисных вместо переменной
.
|
Базис |
B |
|
|
|
|
|
|
|
|
|
|
3 4/13 |
1 |
0 |
0 |
0 |
0 |
0 |
2/13 |
5/13 |
|
|
1 4/13 |
0 |
0 |
1 |
0 |
0 |
0 |
2/13 |
- 8/13 |
|
|
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
-2 |
|
|
6 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
20 11/13 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 1/13 |
-4 9/13 |
|
|
1 4/13 |
0 |
0 |
0 |
1 |
0 |
0 |
2/13 |
-1 8/13 |
|
|
76 7/13 |
0 |
0 |
0 |
0 |
0 |
0 |
10/13 |
11 12/13 |
Значения базисных переменных не являются целыми.
Дополнительное ограничение целесообразно составлять для строки, содержащей в столбце базисных переменных наибольшую дробную часть.
Наибольшая дробная
часть у значения переменной
.
Определяем значения
и
:
Дополнительное ограничение имеет вид:
Приводим к канонической форме:
Вводим новую строку в симплекс-таблицу:
|
|
В |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
х9 |
|
х1 |
3 4/13 |
1 |
0 |
0 |
0 |
0 |
0 |
2/13 |
5/13 |
0 |
|
х3 |
1 4/13 |
0 |
0 |
1 |
0 |
0 |
0 |
2/13 |
- 8/13 |
0 |
|
x5 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
-2 |
0 |
|
х2 |
6 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
х6 |
20 11/13 |
0 |
0 |
0 |
0 |
0 |
1 |
-1 1/13 |
-4 9/13 |
0 |
|
x4 |
1 4/13 |
0 |
0 |
0 |
1 |
0 |
0 |
2/13 |
-1 8/13 |
0 |
|
х9 |
- 11/13 |
0 |
0 |
0 |
0 |
0 |
0 |
- 12/13 |
- 4/13 |
1 |
|
F(х) |
76 7/13 |
0 |
0 |
0 |
0 |
0 |
0 |
10/13 |
11 12/13 |
0 |
Так как базисная
переменная
имеет отрицательное значение, то данную
задачу решаем двойственным симплекс-методом.
Переменную
вводим в число базисных вместо переменной
.
|
|
В |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
х9 |
|
х1 |
3 1/6 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1/3 |
1/6 |
|
х3 |
1 1/6 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
- 2/3 |
1/6 |
|
x5 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
-2 |
0 |
|
х2 |
6 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
|
х6 |
21 5/6 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
-4 1/3 |
-1 1/6 |
|
x4 |
1 1/6 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 2/3 |
1/6 |
|
x7 |
11/12 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1/3 |
-1 1/12 |
|
F(х) |
75 5/6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
11 2/3 |
5/6 |
Значения базисных переменных не являются целыми.
Дополнительное ограничение целесообразно составлять для строки, содержащей в столбце базисных переменных наибольшую дробную часть.
Наибольшая дробная
часть у значения переменной
.
Определяем значения
и
:
Дополнительное ограничение имеет вид:
Приводим к канонической форме:
Вводим новую строку в симплекс-таблицу:
|
|
В |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
х9 |
х10 |
|
х1 |
3 1/6 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1/3 |
1/6 |
0 |
|
х3 |
1 1/6 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
- 2/3 |
1/6 |
0 |
|
x5 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
-2 |
0 |
0 |
|
х2 |
6 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
х6 |
21 5/6 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
-4 1/3 |
-1 1/6 |
0 |
|
x4 |
1 1/6 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 2/3 |
1/6 |
0 |
|
x7 |
11/12 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1/3 |
-1 1/12 |
0 |
|
х10 |
- 11/12 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
- 1/3 |
- 11/12 |
1 |
|
F(х) |
75 5/6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
11 2/3 |
5/6 |
0 |
Так как базисная
переменная
имеет отрицательное значение, то данную
задачу решаем двойственным симплекс-методом.
Переменную
вводим в число базисных вместо переменной
.
|
|
В |
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
х8 |
х9 |
х10 |
|
х1 |
3 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
3/11 |
0 |
2/11 |
|
х3 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
- 8/11 |
0 |
2/11 |
|
x5 |
2 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
-2 |
0 |
0 |
|
х2 |
6 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
х6 |
23 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
-3 10/11 |
0 |
-1 3/11 |
|
x4 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
-1 8/11 |
0 |
2/11 |
|
x7 |
2 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
8/11 |
0 |
-1 2/11 |
|
x9 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4/11 |
1 |
-1 1/11 |
|
F(х) |
75 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
11 4/11 |
0 |
10/11 |
Значения базисных
переменных являются целыми, значит
найдено оптимальное целочисленное
решение:
.