求解整数线性规划问题 max z=7x1＋9x2 s．t．－x1＋3x2≤6 7x1＋x2≤35 x1 x2是非负整数．
整数,线性规划,是非
已帮助 人
-
先将原问题化为标准形式：
min x0=-7x1-9x2，
s．t．-x1+3x2+x3=6，
7x1+x2+x4=35，
x1，x2，x3，x4都是非负整数．
(注：由于本题的不等式约束中的系数和常数项都是整数，因此当x1，x2取整数值时，松弛变量x3，x4也必取整数值，如果不等式约束的系数和常数是分数值，可在两端同乘适当倍数，使之化为整数．否则，所得标准形式是混合整数线性规划问题)
用单纯形法求得上述问题的对应松弛问题的最优解，对应最优单纯形表如表7-3.
表7-3
x1 x2 x3 x4x0-630 0-frac{28}{11}-frac{15}{11}x2
x1frac{7}{2}
frac{9}{2}0 1 frac{7}{22} frac{1}{22}
1 0-frac{1}{22} frac{3}{22}表7-4
x1 x2 x3 x4 y1x0-630 0-frac{28}{11}-frac{15}{11} 0x2
x1
y1frac{7}{2}
frac{9}{2}
-frac{1}{2}0 1 frac{7}{22} frac{1}{22} 0
1 0-frac{1}{22} frac{3}{22} 0
0 0-frac{7}{22}*-frac{1}{22} 1
表7-4对应基解不是可行解，但为正则解．因此，按对偶单纯形法迭代一次，得表7-5．
表7-5
x1 x2 x3 x4 y1x0-590 0 0-1-8x2
x1
x33
frac{32}{7}
frac{11}{7}0 1 0 0 1
1 0 0 frac{1}{7}-frac{1}{7}
0 0 1 frac{1}{7}-frac{22}{7}表7-6
x1 x2 x3 x4 y1 y2x0-550 0 0 0-2-7x2
x1
x3
x43
4
1
40 1 0 0 1 0
1 0 0 0-1 1
0 0 1 0-4 1
0 0 0 1 6-7
表7-6是最优解表，且对应基解是整数解．至此，得出原问题的最优解为x1*=4，x2*=3．最优值为z*=55。