运筹学-4-整数规划.ppt

《运筹学-4-整数规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学运筹帷幄之中决胜千里之外整数规划IntegerProgramming第四章第四章整数规划本章主要内容：整数问题规划及其数学模型整数规划问题的求解0-1型整数规划问题指派问题第四章整数规划在很多场合，我们建立最优化模型时，实际问题要求决策变量只能取整数值而非连续取值。此时，这类最优化模型就称为整数规划（离散最优化）模型。整数规划的求解往往比线性规划求解困难得多，而且，一般来说不能简单地将相应的线性规划的解取整来获得。第四章整数规划线性规划模型：实际问题要求xi为整数！如机器的台数，人数等第四章整数规划例:胜利家具厂生产桌子和椅子两种家具。桌子售价5

2、0元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4个小时，油漆工2小时。生产一个椅子需要木工3个小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？第四章整数规划纯整数规划第四章整数规划例（背包问题）一个旅行者，为了准备旅行的必备物品，要在背包里装一些有用的东西，但他最多只能携带b公斤的东西，而每件物品都只能整件携带，于是他给每件物品规定了一个“价值”，以表示其有用程度。如果共有m件物品，第i件件物品的重量为bi，价值为ci，问题就变成：在携带

3、的物品总重量不超过b公斤的条件下，携带哪些物品可使总价值最大?第四章整数规划9解：Z表示所带物品的总价值携带物品的总重量数学模型：0-1规划第四章整数规划第四章整数规划解：数学模型：混合型整数规划第四章整数规划例工厂A1和A2生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij，见下表：B1B2B3B4年生产能力A12934400A28357600A37612200A44525200年需求量35040030

4、0150工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。第四章整数规划解：这是一个物资运输问题，特点是事先不能确定应该建A3还是A4中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：再设xij为由Ai运往Bj的物资数量，单位为千吨；z表示总费用，单位万元。则该规划问题的数学模型可以表示为：第四章整数规划混合整数规划问题第四章整数规划整数线性规划问题的种类：纯整数线性规划：指全部决策变量都必须取整数值的整数线性规划。混合整数线性规划：决策变量中有一部分

5、必须取整数值，另一部分可以不取整数值的整数线性规划。0-1型整数线性规划：决策变量只能取值0或1的整数线性规划。第四章整数规划纯整数规划的数学模型：0--1规划的数学模型：第四章整数规划例×√√√√Z=130√√√√，可行且Z=140不可行可行第四章整数规划（IP）（IP）问题的松弛问题第四章整数规划∩≤松弛问题的最优值是原整数规划的目标函数值的上界第四章整数规划例设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。第四章整数规划用图解法求出最优解为：x1＝3/2,x2=10/3，且有Z=29/6现求整数解(最优解):如用舍入取

6、整法可得到4个点即(1，3),(2，3),(1，4),(2，4)。显然，它们都不可能是整数规划的最优解。x1x2⑴⑵33(3/2,10/3)按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如右图所示。其中(2,2),(3,1)点的目标函数值最大，即为Z=4。第四章整数规划-分支定界法1）求整数规划的松弛问题最优解；若松弛问题的最优解满足整数要求，得到整数规划的最优解,否则转下一步；2）分支与定界：任意选一个非整数解的变量xi，在松弛问题中加上约束：xi≤[xi]和xi≥[xi]+1组成两个新的松

7、弛问题，称为分枝。新的松弛问题具有特征：当原问题是求最大值时，目标值是分枝问题的上界；当原问题是求最小值时，目标值是分枝问题的下界。检查所有分枝的解及目标函数值，若某分枝的解是整数并且目标函数值大于（max）等于其它分枝的目标值，则将其它分枝剪去不再计算，若还存在非整数解并且目标值大于(max)整数解的目标值，需要继续分枝，再检查，直到得到最优解。分支定界法的解题步骤：上界x1≤[x*01]x1≥[x*01]+1当所有的子问题均被关闭或剪枝后目标函数值最大的整数解既为所求的最优解一、分枝定界法的原理：1、分枝··················0123

8、45678·松弛问题的可行域增加x1≤3增加x1≥4L1L2x1≤3x1≥4父问题子问题结论1