运筹学全套配套课件朱道立 ch06.ppt

《运筹学全套配套课件朱道立 ch06.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、了解整数规划在经济和管理中的基本应用方法。第六章整数规划教学要求：掌握线性整数规划的建模方法，特别是0-1变量的运用；掌握分支定界求解方法的基本原理；了解割平面求解方法的基本原理；1目录整数规划实例与模型0－1整数规划的建模方法分支定界法割平面法指派问题应用举例和Excel求解2目录整数规划实例与模型0－1整数规划的建模方法分支定界法割平面法指派问题应用举例和Excel求解3应用与实例在现实生活中，经常遇到一些需要变量取整数才有实际意义的问题，例如制定计划、规划时需要确定工人的人数，设备的台数等。许多有名的最优化问题，如旅行商问题、背包问

2、题、下料问题、工序安排问题等，也都可以归结为整数规划问题。4应用与实例——具体实例现有一位于城市B5的工厂，其年生产量是30000件，产品被运往A1，A2，A3三个城市的销售中心。经预测该厂产品的需求量将会增长，工厂决定将在B1，B2，B3，B4四个城市中的一个或多个城市中新建工厂以增加生产力(如有图）。综合考虑在这四个城市中新建工厂的年固定成本和生产能力，以及每件产品从每个工厂送到每个销售中心的运费。问如何选择新的厂址，才能使该工厂每年的总成本最小。B1B2B3B4B5A3A2A15首先做如下假设：如果在B1建新厂，y1=1；否则，y1=0。如

3、果在B2建新厂，y2=1；否则，y2=0。如果在B3建新厂，y3=1；否则，y3=0。如果在B4建新厂，y4=1；否则，y4=0。xij：表示从工厂i到销售中心j的运输量；i=1,…,5；j=1,2,3。利用已知的数据，年运输成本为：TC1=5x11+2x12+3x13+4x21+3x22+4x23+9x31+7x32+5x33+10x41+4x42+2x43+8x51+4x52+3x536TC2=175y1+300y2+375y3+500y4；总成本为：TC=TC1+TC2；生产能力的约束条件为：从新工厂B1运到A1，A2，A3三个城市销售中心

4、的总量应小于等于B1的生产能力，所以约束条件为：x11+x12+x13≤10y1B1的生产能力；同理可得：x21+x22+x23≤20y2B2的生产能力；x31+x32+x33≤30y3B3的生产能力；x41+x42+x43≤40y4B4的生产能力；x51+x52+x53≤30B5的生产能力；三个销售中心的需求量为：x11+x21+x31+x41+x51=30A1的需求量；x12+x22+x32+x42+x52=20A2的需求量；x13+x23+x33+x43+x53=20A3的需求量；建新工厂的年固定成本为：7所以选址模型为：minTC=TC1

5、+TC2s.t．x11+x12+x13≤10y1；x21+x22+x23≤20y2；x31+x32+x33≤30y3；x41+x42+x43≤40y4；x51+x52+x53≤30；x11+x21+x31+x41+x51=30；x12+x22+x32+x42+x52=20；x13+x23+x33+x43+x53=20；xij≥0，对所有的i，j；y1，y2，y3，y4=0，18整数规划的一般模型9目录整数规划实例与模型0－1整数规划的建模方法分支定界法割平面法指派问题应用举例和Excel求解10实例分析某电冰箱厂正在考虑随后4年内有不同资金要求的

6、投资方案。面对每年有限的资金，工厂领导需要选择最好的方案，使资金预算方案的当前估算净值最大化。每种方案的现金估算净值（现金估算净值为第一年开始时的净现金流的值）、资金需求和4年内拥有的资金见下表：11实例分析x1表示扩建工厂的变量，=1表示扩建工厂，＝0表示不扩建同理，变量x2,x3,x4依次表示扩建仓库、更新机器、新产品研制。变量第1年的可用资金为40千元，所以相应的约束条件为：同理得到后三年的约束条件。约束条件当前估算净值最大，即max目标函数120－1整数规划的标准型和解法必须≤必须大于等于0解法全枚举法（不展开论述）隐枚举法（重点讲述）标

7、准型13隐枚举法求解步骤（一）（1）令全部都是自由变量且取0值，检验解是否可行。若可行，已得最优解；若不可行，进行步骤（2）。（2）将某一变量转为固定变量，令其取值为1或0，使问题分成两个子域。令一个子域中的自由变量都取0值，加上固定变量取值，组成此子域的解。（3）计算此解的目标函数值，与已求出的可行解最小目标函数值比较。如果前者大，则不必检验其是否可行而停止分枝，若子域都检验过，转步骤（7），否则转步骤（6）。因继续分枝即使得到可行解，其目标函数值也较大，不会是最优解；如前者小，进行步骤（4）。对第一次算出的目标函数值，不必进行比较，直接转到步

8、骤（4）。（4）检验解是否可行。如可行，已得一个可行解，计算并记下它的z值，并停止分枝，若子域都检验过，转步骤（7），否则转步骤（6）。