整数规划****题解答
练****br/>用割平面法解整数规划问题
解:不考虑整数约束条件求解伴随规划问题
将其标准化:
(1)采用M法
(增加了人工变量x4)
练****br/>(2)不增加人工变量,通过对约束方程组进行行变换得到
初始可行基
练****br/>cj
0
1
-2
0
0
CB
XB
b
x1
x2
x3
x4
x5
0
x1
13/2
1
0
0
-1/2
5/2
1
x2
5/2
0
1
0
-1/2
3/2
-2
x3
1/2
0
0
1
-1/2
1/2
-z
-3/2
0
0
0
-1/2
-1/2
练****br/>伴随规划问题的最优解不是整数解,构造割平面(由
最终表中任意一个不取整数值得基变量所对应的约束方程
进行构造,不妨选x3)
加入上面的最终单纯性表,得
练****br/>cj
0
1
-2
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
x6
0
x1
13/2
1
0
0
-1/2
5/2
0
1
x2
5/2
0
1
0
-1/2
3/2
0
-2
x3
1/2
0
0
1
-1/2
1/2
0
0
x6
-1/2
0
0
0
-1/2
-1/2
1
-z
-3/2
0
0
0
-1/2
-1/2
0
练****br/>练****br/>由对偶单纯性法可得
cj
0
1
-2
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
x6
0
x1
7
1
0
0
0
3
-1
1
x2
3
0
1
0
0
2
-1
-2
x3
1
0
0
1
0
1
-1
0
x4
1
0
0
0
1
1
-2
-z
-1
0
0
0
0
0
-1
练****br/>任务 1 2 3 4 5
人员
甲 4 8 7 15 12
乙 7 9 17 14 10
丙 6 9 12 8 7
丁 6 7 14 6 10
戊 6 9 12 10 6
用匈牙利法求解指派问题,其效率矩阵如下:
练****br/>解:第一步:对效率矩阵进行变换:
整数规划习题解答 ppt课件 来自淘豆网www.taodocs.com转载请标明出处.