第3章特殊线性规划问题.ppt

《第3章特殊线性规划问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三者特殊线性规划问题运输问题指派问题转运问题图与网络问题工程中有些线性规划问题要求解为整数如：人员、车辆等规划对象原有的计算方法得到的解存在非整数的可能P55，p56,p57第一节整数规划§1分支定界解法思路：设整数规划为A，对应的线性规划为B，先求解B，若其最优解符合A的整数条件，停止；若其最优解不符合A的整数条件，设B的最优目标函数值为，A的最优目标函数值。因为B是A放宽限制得到，可行域增大，所以是，而A的任意可行解的目标函数值都是的下界，即，逐步减少和增大，最终求得。下面以例来说明。（三节课）部分或全部决策

2、变量以整数计量的线性规划模型称之为整数规划。由于通过单纯形法求解出来的结果可能不为整数，这时如果决策变量的解值很大，则可就近取整，得近似解；如果决策变量的解值不大，取整会造成较大误差时，就不是最优解，甚至不是近似解。p57求解整数规划问题的方法：分枝定界法（BranchingandBound），是一种隐枚举法，其要点是：先暂不考虑决策变量为整数的要求，用单纯形法先求解一个最优解，以此为整数规划问题的上限（Max）或下限（Min）；而后选择其中一个非整数决策变量解值，按其两侧相邻的整数分解其可行域，然后分别在这两个缩小的

3、可行域内寻求最优整数解，以此为整数规划问题的下限（Max）或上限（Min）；随后，选择另外一个其目标函数大于下限（Max）或小于上限（Min）非整数决策变量解值，重复上述过程，直至获得最优整数解为止，取其中目标函数值最大（Max）或最小（Min）的整数解为最优整数解。求解整数规划的方法—分枝定界法先看一个实例：p58分枝定界法先不考虑整数约束，解相应的线性规划问题为了讨论方便，将原线性规划问题称为L1。L1的最优解为x1=2.25，x2=3.75，Z=41.25例L1的最优解为x1=2.25，x2=3.75不满足整数条

4、件划分可行域取x2≤3，x2≥4L2L3任取一个没有满足整数条件的变量L2的最优解为x1=1.8，x2=4，Z=41L3的最优解为x1=3，x2=3，Z=39L2L3已经得到整数解L2的最优解为x1=1.8，x2=4不满足整数条件划分可行域取x1≤1，x1≥2L4L5L4的最优解为x1=1，x2=4.44，Z=40.444L5无最优解L4的最优解为x1=1，x2=4.44不满足整数条件划分可行域取x2≤4，x2≥5L6L7L6的最优解为x1=1，x2=4，Z=37L7的最优解为x1=0，x2=5，Z=40所以最优解为x

5、=(0,5)T，最大值为40.LP1LP2LP3LP4LP5非整数解x1=2.25，x2=3.75，Z1=41.25；为分枝定界上限值。整数解x1=3，x2=3，Z2=39；为分枝定界下限值。整数解x1=0，x2=5，Z4=40；为最优整数解非整数解x1=1.8,x2=4,Z3=41；无可行解原问题LP1新问题LP2新问题LP3新问题LP5新问题LP4新问题LP7新问题LP6找到最优整数解或无可行解汇总例2：求解B：A：解：(1)B的最优解为x1=4.81，x2=1.82，不满足整数条件，设A的最优值为，则，又x1=x

6、2=0是A的一个可行解，这时，则(2)对于解x1=4.81(或x2=1.82)考虑x1≤4，x1≥5给问题B分别加上约束，将分解为两个子问题B1，B2（两枝）B1：Z1=349x1=4.00，x2=2.10B2：Z2=341x1=5.00，x2=1.57都不满足整数条件，则（3）分别对B1，B2进行分解，因Z1>Z2，故先分解B1为两枝。对于x2=2.10，增加条件x2≤2称为B3，增加条件x2≥3称为B4B3：Z3=340x1=4.00，x2=2B4：Z4=327x1=1.42，x2=3由于Z3>Z4所以不必要分解B

7、4，但Z3＜Z2所以有必要分解B2。则（4）分解B2，得B5：Z5=308x1=5.44，x2=1（x2≤1）B6：无可行解（x2≥2）∵Z5

8、6x20，1，2，3可能组合：7×4=28大型问题组合数会很大。总结：分枝定界法思路：首先不考虑解为整数的要求，用单纯形法求最优解，以此作为目标函数值的上限或下限；其次，选择其中一个非整数的变量，根据与两侧相近的整数划分可行域，在缩小的可行域内寻求最优整数解，以此作为目标函数值的上限或下限；不断重复以上过程，直到每一个可能进一步分