问题：

max z＝3x1＋2x2

---

---

答案：

× 用图解法解其相应的线性规划问题。图5．5．1中的阴影部分为相应线性规划问题的可行域。目标函数z＝3x1＋2x2,即 是斜率为－3／2的－族平行线,由线性规划的性质知,其最值只可能在可行域的顶点取得,易知x1＝0,x2＝0为可行解,将直线3x1＋2x2＝0沿其法线方向逐渐向上平移,直至B点,B点坐标为(13／4,5／2)。 目标函数的最优值 当凑整为X1＝(3,2)T时,为可行解,z＝13。当凑整为X2＝(3,3)T时,为菲可行解。当凑整为X3＝(4,2)T时,为非可行解。当凑整为X4＝(4,3)T时,为非可行解。下面用分支定界法来解整数规划问题。令 ＝59／4,显然x1＝0,x2＝0为可行解。因为 ,所以0≤z*≤59／4。将原问题分解为下述两个问题： 对于(B1)和(B2),用图解法求解,在图5．5．1的基础上,增加两条直线x1＝3和x1＝4,得到两个区域OADFO和GECG,分别为(B1)和(B2)的可行域,从图中可以看出：(B1)在D点取得最优值,D点坐标为(3,8／3)。 (B2)在E点取得最优值,E点坐标为(4,1),为整数点。maxz2＝3×4＋2×1＝14因为 ,所以14≤z*≤43／3,且z*为整数,则z*＝14,x1＝4,x2＝1为最优整数解。