Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ПРИМЕР
F() = 7x1 + 9x2
при ограничениях
-x1 + 3x2 6 -x1 + 3 x2 + x3 = 6
7x1 + x2 35 7x1 + x2 + x4 = 35
x1,х2 0, целые. x1,...,x4 0, целые.
Таблица 1
|
|
7 |
9 |
0 |
0 |
= |
|
|
3 4 |
0 0 |
-1 7 |
3 1 |
1 0 |
0 1 |
6 35 |
|
|
-7 |
-9 |
0 |
0 |
0 |
|
|
2 4 |
9 0 |
-1/3 22/3 |
1 0 |
1/3 -1/3 |
0 1 |
2 33 |
|
-10 |
0 |
3 |
0 |
18 |
||
|
2 1 |
9 7 |
0 1 |
1 0 |
7/22 -1/22 |
1/22 3/22 |
7/2 9/2 |
|
0 |
0 |
28/11 |
15/11 |
63 |
Так как полученное решение не является целочисленным, следует расширить данную таблицу путем введения некоторого отсечения. В качестве производящей строки можно выбрать любую строку таблицы. Обычно выбирается строка, соответствующая . Сейчас . Строке с базисной переменной х2 соответствует равенство x2 + 7/22x3 + 1/22x4 = 7/2.
Следовательно, уравнение отсечения Гомори имеет вид
- 7/22x3 - 1/22x4 + = -1/2
В результате получаем новую таблицу:
Таблица 2.
|
|
7 |
9 |
0 |
0 |
0 |
= |
|
|
2 1 5 |
9 7 0 |
0 1 0 |
1 0 0 |
7/22 -1/22 -7/22 |
1/22 3/22 -1/22 |
0 0 1 |
7/2 9/2 -1/2 |
|
0 |
0 |
28/11 |
15/11 |
0 |
63 |
||
|
2 1 3 |
9 7 0 |
0 1 0 |
1 0 0 |
0 0 1 |
0 1/7 1/7 |
1 -1/7 -22/7 |
3 32/7 11/7 |
|
0 |
0 |
0 |
1 |
8 |
59 |
Так как решение опять не является целочисленным, необходимо продолжить процесс введения отсечений. Строке с базисной переменной х1 соответствует ограничение:
- 1/7x4 - 6/7 + = -4/7
Таблица 3.
|
7 |
9 |
0 |
0 |
0 |
0 |
= |
||
|
2 1 3 6 |
9 7 0 0 |
0 1 0 0 |
1 0 0 0 |
0 0 1 0 |
0 1/7 1/7 -1/7 |
1 -1/7 -22/7 -6/7 |
0 0 0 1 |
3 32/7 11/7 -4/7 |
|
0 |
0 |
0 |
1 |
8 |
0 |
59 |
||
|
2 1 3 4 |
9 7 0 0 |
0 1 0 0 |
1 0 0 0 |
0 0 1 0 |
0 0 0 1 |
1 -1 -4 6 |
0 1 1 -7 |
3 4 1 4 |
|
0 |
0 |
0 |
0 |
2 |
7 |
55 |
В результате получили оптимальное целочисленное решение исходной задачи:
x1 = 4, x2 = 3, = 55.
Дадим геометрическую интерпретацию задачи. На рис. 1 показано, что введение двух ограничений позволяет получить новую экстремальную точку с координатами (4;3), в которой достигается оптимум исходной целочисленной задачи.
1 ОТСЕЧЕНИЕ: - 7/22x3 - 1/22x4 + = -1/2 или
- 7/22x3 - 1/22x4 -1/2
Тогда из таблицы 1 получим
-7/22(х1 - 3х2 + 6) - 1/22 (-7x1 - х2 + 35) -1/2
7(х1 - 3х2 + 6) + (-7x1 - х2 + 35) 11 х2 3.
2 ОТСЕЧЕНИЕ: - 1/7x4 - 6/7 + = -4/7 или
- 1/7x4 - 6/7 -4/7
Теперь из таблиц 1 и 2 получим
- 1/7(-7x1 - х2 + 35) - 6/7(7/22x3 + 1/22x4 - 1/2) -4/7
- 1/7(-7x1 - х2 + 35) - 6/7[ 7/22(х1 - 3х2 + 6) + 1/22(-7x1 - х2 + 35) - 1/2 ] -4/7 х1 + х2 7.
X2
X1
рис.1