运筹学作业的参

来源：纷纭教育

第三章作业的参

P99 3、用Gomory割平面法求解下面的ILP问题.

mins.t.zx15x2x12x28x1x24xi0,整数，i1,2.

注：要先将问题化成标准形式解：将原问题标准化

mins.t.zx15x2x12x2x3x1x28x44

xi0,整数，i1,2,3,4.将第二个等式乘以(1)加到第一个等式，可得线性方程组的典式

minzx15x2s.t.3x2x3x44x1x2x44xi0,整数，i1,2,3,4.

所以，其松驰问题（P0）的第一张单纯形表为

x1 x2 x3 x4 RHS

z -1 5 0 0 0

x3 0 3 1 1 4 x1 1 -1 0 -1 4

把零行化成检验行，得

x1 x2 x3 x4 RHS 0 4 3 0 1 0 -1 1 -1 4 4 4 z x3 0 x1 1 -1 以x2为进基变量，x3为离基变量，旋转得

x1 x2 0 0 1 x3

x4 RHS

x2 0 x1 1 0 4743 3 3 1143 3 3 12163 3 3 所以，松驰问题（P0）的最优解为x0(所以由第一行生成的割平面条件为

1,,0,0)T，它不是整数向量。 33注：在得到割平面时，111x3x4把新增变量的系数333. 要

变为1 对应的割平面为

111x3x4s1333.

把它加入到松驰问题（P0）的最优单纯形表中，得到改进的松弛问题（P1）的

单纯形表为

x1 x2 x3 x4 s1 RHS 474z 0 0   0  333 114注：对改进的松弛问题 x0 1 0 2 333是用对偶单纯形方法 1216求解  x1 0 0 1 333

111   1  s1 0 0 333

利用对偶单纯形方法求解. 以s1为离基变量，x3为进基变量，旋转得

x1 x2 x3 x4 s1 RHS 0 0 1 0 0 0 1 -1 -4 0 -1 1 1 1 -3 0 1 5 1 z

x2 0 x1 1 0 x3 0 0 所以，松弛问题（P1）的最优解为x1(5,1,1,0,0)T。因此，原问题的最优解为

x*(5,1)T,最优值为0.

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文