现在我们解这个问题,设x1,x2分别为甲、乙两 种货物的托运箱数(当然都是非负整数)。这是 个(纯)整数线性规划问题,用数学式可表示为: maxz=20x1+10x2① 5x1+4X,≤24 ② x1+5x2≤13③(5.1) ≥0 x1,x,整数
• 现在我们解这个问题，设x1，x2分别为甲、乙两 种货物的托运箱数(当然都是非负整数)。这是一 个(纯)整数线性规划问题，用数学式可表示为： max z =20x1 +10x2 ① 5x1 +4x2≤24 ② 2x1 +5x2≤13 ③ (5.1) x1，x2≥0 ④ x1，x2整数 ⑤
它和线性规划问题的区别仅在于最后的条件⑤。现在我 们暂不考虑这一条件,即解①~④(以后我们称这样的问 题为与原问题相应的线性规划问题), 很容易求得最优解为x1=4.8,x2=0,maxz96 z=96 AC
它和线性规划问题的区别仅在于最后的条件⑤。现在我 们暂不考虑这一条件，即解①～④(以后我们称这样的问 题为与原问题相应的线性规划问题)， 很容易求得最优解为:x1=4.8，x2=0，max z=96
但x1是托运甲种货物的箱数,现在它不是整数,所以 不合条件⑤的要求。 是不是可以把所得的非整数的最优解经过“化整” 就可得到合于条件⑤的整数最优解呢?如将(x1=4.8, x2=O)凑整为(x1=5,ⅹ2=0),这样就破坏了条件②(关 于体积的限制),因而它不是可行解;如将(x148 x2=0)舍去尾数0.8,变为(x14,x2=0),这当然满足 各约束条件,因而是可行解,但不是最优解,因为 当x1=4,x2=0,时z-80 非整数的最优解在C(48,0)点达到
但x1是托运甲种货物的箱数，现在它不是整数，所以 不合条件⑤的要求。 • 是不是可以把所得的非整数的最优解经过“化整” 就可得到合于条件⑤的整数最优解呢?如将(x1 =4.8， x2 =0)凑整为(x1 =5，x2 =0)，这样就破坏了条件②(关 于体积的限制)，因而它不是可行解；如将(x1 =4.8， x2 =0)舍去尾数0.8，变为(x1 =4，x2 =0)，这当然满足 各约束条件，因而是可行解，但不是最优解，因为 当x1 =4，x2 =0, 时z=80. • 非整数的最优解在C(4.8，0)点达到
但当x1=4,x2=1(这也是可行解)时,z-90 本例还可以用图解法来说明。见图5 96 △C 0 345 7
但当x1 =4，x2 =1(这也是可行解)时，z=90。 本例还可以用图解法来说明。见图 5-1
图中画(+)号的点表示可行的整数解。凑整的 (5,0)点不在可行域内,而C点又不合于条件 ⑤。为了满足题中要求,表示目标函数的z的 等值线必须向原点平行移动,直到第一次遇 到带“+"号B点(x=4,x2=1)为止。这样,z的 等值线就由z=96变到z=90,它们的差值 △z=96-90=6 表示利润的降低,这是由于变量的不可分性 (装箱)所引起的
• 图中画(+)号的点表示可行的整数解。凑整的 (5，0)点不在可行域内，而C点又不合于条件 ⑤。为了满足题中要求，表示目标函数的z的 等值线必须向原点平行移动，直到第一次遇 到带“+”号B点(x1 =4，x2 =1)为止。这样，z的 等值线就由z=96变到z=90，它们的差值 • Δz=96-90=6 • 表示利润的降低，这是由于变量的不可分性 (装箱)所引起的