解： 如果带第种物品 否 max=∑c j=1 s.t. ∑ax≤8 x,=0或1 (0=1~7) 这是一个0-1规划问题
解： = 否 如果带第 种物品 0 1 j xj 0或1 （ 1 ~ 7） . . max 7 1 7 1 = = = = = x j st a x b Z C x j j j j j j j 这是一个0-1规划问题
对P问题，可能会认为，只要求出不受整数约 束的解，然后“舍入化整”，就可得到整数最 优 解，是这样吗？ 其实，这样的方法常常是行不通的。 下面通过整数规划的求解来说明
对IP问题，可能会认为，只要求出不受整数约 束的解，然后“舍入化整”，就可得到整数最 优 解，是这样吗？ 其实，这样的方法常常是行不通的。 下面通过整数规划的求解来说明
图解法 类似于工维的线性规划问题的图解法，二维的整数规 ×2 划问题也有相应的图解法。 装载问题为例： max Z=20X1+10X2 s.t.5x1+4x2≤24 2X1+5x2≤13 1≥0，x2≥0.x1,X2为整 数 最优：x1=4,x2=1,Zmax=90 求解得：x1=4.8,x2=0,Zmax=96 考虑化整 X1=5,X2=0,不可行 X1=4,x2=0,Z=80
图解法 类似于二维的线性规划问题的图解法，二维的整数规 划问题也有相应的图解法。 装载问题为例： max Z = 20 x1 + 10 x2 s.t. 5x1 + 4x2 ≤ 24 2 x1 + 5x2 ≤ 13 x1 ≥ 0，x2 ≥ 0 .x1,x2为整 数 5 2 1 0 1 2 3 4 3 L1 L2 x1 x2 A B C 求解得：x1=4.8,x2=0,Zmax=96 考虑化整 x1=5,x2=0,不可行 x1=4,x2=0,Z=80 最优：x1=4,x2=1,Zmax=90
上例得到的启示1 (1)化整后未必是可行解 2 即使是可行解，也未必是最优解 3) 即使该方法结果可以得到最优解， 但如果有n个决策变量，则取舍方案有 2n种。当n=60时，260约等于1018，这使 计算机也难以实现。 所以，有必要讨论整数规划的求解方法
上例得到的启示１： （１）化整后未必是可行解 （２）即使是可行解，也未必是最优解 （３）即使该方法结果可以得到最优解， 但如果有n个决策变量，则取舍方案有 ２n种。当n=60时，2 60约等于1018，这使 计算机也难以实现。 所以，有必要讨论整数规划的求解方法