运筹学目标规划与整数规划.ppt
Page:1QSC华东理工大学 工商经济学院运筹学运运筹筹学学目目标标规规划划Page:2QSC华东理工大学 工商经济学院运筹学多目标决策问题多目标决策问题实际问题决策经常面临的问题：实际问题决策经常面临的问题：方案优劣并不以单一准则为目标，而是以多重准则为目标方案优劣并不以单一准则为目标，而是以多重准则为目标约束条件并不完全符合严格的刚性条件，具有一定的弹性约束条件并不完全符合严格的刚性条件，具有一定的弹性可能的弹性约束可能的弹性约束：最好等于最好等于最好不大于最好不大于最好不小于最好不小于Page:3QSC华东理工大学 工商经济学院运筹学弹性约束的处理方法弹性约束的处理方法实际量dd+=目标值负偏差变量负偏差变量正偏差变量正偏差变量最好等于：最好等于：最好不大于：最好不大于：最好不小于：最好不小于：Page:4QSC华东理工大学 工商经济学院运筹学顾客访问策略顾客访问策略目标：目标：访问时间最好不超过680小时；访问时间最好不少于600小时；销售收入尽量不少于70,000；访问老顾客数最好不少于200个；访问新顾客数最好不少于120个Page:5QSC华东理工大学 工商经济学院运筹学模型模型顾客访问策略顾客访问策略Page:6QSC华东理工大学 工商经济学院运筹学目标规划解的几何分析目标规划解的几何分析X100300200600500400X21002003004005001(1)(2)(3)(4)(5)Page:7QSC华东理工大学 工商经济学院运筹学目标规划的求解目标规划的求解-序贯算法序贯算法Page:8QSC华东理工大学 工商经济学院运筹学第一级目标第一级目标X100300200600500400X21002003004005001(1)Page:9QSC华东理工大学 工商经济学院运筹学第二级目标第二级目标X100300200600500400X21002003004005001(1)(2)Page:10QSC华东理工大学 工商经济学院运筹学第三级目标第三级目标X100300200600500400X21002003004005001(1)(2)(3)Page:11QSC华东理工大学 工商经济学院运筹学X100300200600500400X21002003004005001(1)(2)(3)(4)第四级目标第四级目标Page:12QSC华东理工大学 工商经济学院运筹学X100300200600500400X21002003004005001(1)(2)(3)(4)(5)第五级目标第五级目标Page:13QSC华东理工大学 工商经济学院运筹学目标规划的求解目标规划的求解-多阶段算法多阶段算法Page:14QSC华东理工大学 工商经济学院运筹学初始单纯形表初始单纯形表Page:15QSC华东理工大学 工商经济学院运筹学单纯形表运算单纯形表运算Page:16QSC华东理工大学 工商经济学院运筹学单纯形表运算单纯形表运算Page:17QSC华东理工大学 工商经济学院运筹学运运筹筹学学整整数数线线性性规规划划Page:18QSC华东理工大学 工商经济学院运筹学整数线性规划问题的一般形式整数线性规划问题的一般形式Page:19QSC华东理工大学 工商经济学院运筹学整数线性规划问题的分类整数线性规划问题的分类全全整数线性规划整数线性规划混合整数线性规划混合整数线性规划0-1整数线性规划整数线性规划Page:20QSC华东理工大学 工商经济学院运筹学整数规划与其松弛问题整数规划与其松弛问题当当放弃整数约束时得到的线性规放弃整数约束时得到的线性规划称为整数规划的松弛问题。划称为整数规划的松弛问题。整数规划的可行域是松弛问题的整数规划的可行域是松弛问题的可行域，反之不成立。可行域，反之不成立。Page:21QSC华东理工大学 工商经济学院运筹学全整数规划的求解全整数规划的求解-GomoryGomory割平面方法割平面方法132X2X1 22.5154整数点整数点松弛问题最优解松弛问题最优解Page:22QSC华东理工大学 工商经济学院运筹学松弛问题的最优解松弛问题的最优解Page:23QSC华东理工大学 工商经济学院运筹学GomoryGomory定理定理在在松弛问题的最优单纯形表中，假如有一常数松弛问题的最优单纯形表中，假如有一常数项项 不是整数，且对应的方程为：不是整数，且对应的方程为：分解分解 和和 成最大整数与正分数之和：成最大整数与正分数之和：Page:24QSC华东理工大学 工商经济学院运筹学则则包含了整数规划的所有整数可行解，但不包括包含了整数规划的所有整数可行解，但不包括松弛问题的最优解松弛问题的最优解Page:25QSC华东理工大学 工商经济学院运筹学例题求解例题求解选择第一个方程：选择第一个方程：分解为：分解为：Page:26QSC华东理工大学 工商经济学院运筹学在在原松弛问题中加入约束：原松弛问题中加入约束：即即形成松弛问题形成松弛问题2Page:27QSC华东理工大学 工商经济学院运筹学Page:28QSC华东理工大学 工商经济学院运筹学132X2X1 22.5154整数点整数点松弛问题松弛问题2的最优解的最优解割平面割平面Page:29QSC华东理工大学 工商经济学院运筹学选择第四个方程（具有最大分数部分）：选择第四个方程（具有最大分数部分）：分解为：分解为：Page:30QSC华东理工大学 工商经济学院运筹学在在松弛问题松弛问题2中加入约束：中加入约束：即即形成松弛问题形成松弛问题3Page:31QSC华东理工大学 工商经济学院运筹学得到最优解得到最优解Page:32QSC华东理工大学 工商经济学院运筹学割平面：割平面：132X2X1 22.5154松弛问题松弛问题3的最优解的最优解松弛问题松弛问题2的最优解的最优解Page:33QSC华东理工大学 工商经济学院运筹学如果选择第二个方程：如果选择第二个方程：分解为：分解为：Page:34QSC华东理工大学 工商经济学院运筹学在在松弛问题松弛问题2中加入约束：中加入约束：即即形成松弛问题形成松弛问题3Page:35QSC华东理工大学 工商经济学院运筹学没有找到整数解，没有找到整数解，继续做下去继续做下去Page:36QSC华东理工大学 工商经济学院运筹学混合整数规划的求解混合整数规划的求解-分枝定界方法分枝定界方法分枝：分枝：当当 不符合整数要求时，构造不符合整数要求时，构造两个约束条件：两个约束条件：加入松弛问题分别形成两个子问题（分枝）加入松弛问题分别形成两个子问题（分枝）定界：定界：当子问题获得整数规划的一个可行当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个界限解，则它的目标函数值就构成一个界限Page:37QSC华东理工大学 工商经济学院运筹学例例132X254X1 231S解解S得：得：Page:38QSC华东理工大学 工商经济学院运筹学132X254X1 231S2对对S分枝：分枝：构造约束：构造约束：和和形成分枝问题形成分枝问题S1和和S2，得解得解B和和CS1Page:39QSC华东理工大学 工商经济学院运筹学SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9Page:40QSC华东理工大学 工商经济学院运筹学132X254X1 231S2对对S1分枝：分枝：构造约束：构造约束：和和形成分枝问题形成分枝问题S11和和S12，得解得解DS12S11无可行解无可行解Page:41QSC华东理工大学 工商经济学院运筹学SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解无可行解S12D:x1=33/14,x2=2Z=61/14Page:42QSC华东理工大学 工商经济学院运筹学132X254X1 231S2对对S12分枝：分枝：构造约束：构造约束：和和形成分枝问题形成分枝问题S121和和S122，得解得解E和和FS121S122Page:43QSC华东理工大学 工商经济学院运筹学SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9S11无可行解无可行解S12D:x1=33/14,x2=2Z=61/14S122F:x1=2,x2=2Z=4S121E:x1=3,x2=1Z=4Page:44QSC华东理工大学 工商经济学院运筹学0-10-1整数规划整数规划变量只能取变量只能取0或或1的整数线性规划的整数线性规划Page:45QSC华东理工大学 工商经济学院运筹学0-10-1规划的应用规划的应用-项目投资预算项目投资预算Page:46QSC华东理工大学 工商经济学院运筹学模型模型变量假设变量假设:模型模型:Page:47QSC华东理工大学 工商经济学院运筹学0-10-1规划的应用规划的应用-工厂工厂-销售点配置问题销售点配置问题生产厂生产厂顾客需求顾客需求销售点销售点45DCBA7IIIII213IPage:48QSC华东理工大学 工商经济学院运筹学工厂工厂-销售点配置问题销售点配置问题-问题描述问题描述问题问题:为使经营成本最低为使经营成本最低,应开设那些工厂及销售点应开设那些工厂及销售点?Page:49QSC华东理工大学 工商经济学院运筹学工厂工厂-销售点配置问题销售点配置问题-模型参数Page:50QSC华东理工大学 工商经济学院运筹学工厂工厂-销售点配置问题销售点配置问题-模型Page:51QSC华东理工大学 工商经济学院运筹学0-10-1规划的求解规划的求解隐枚举方法隐枚举方法Page:52QSC华东理工大学 工商经济学院运筹学最优解（最优解（x1,x2,x3)=(1,0,1);z=8隐枚举方法求解过程隐枚举方法求解过程Page:53QSC华东理工大学 工商经济学院运筹学经典指派问题经典指派问题n个员工分配作个员工分配作n项工作，一致项工作，一致的的i个员工作的个员工作的j项工作的成本为项工作的成本为cij，i=1,n;j=1,n。求最佳求最佳分配方案。分配方案。Page:54QSC华东理工大学 工商经济学院运筹学指派问题的数学模型指派问题的数学模型s.t.Page:55QSC华东理工大学 工商经济学院运筹学指派问题的解应对应于成本矩阵的不同指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小行与不同列，且总成本最小Page:56QSC华东理工大学 工商经济学院运筹学例例cijPage:57QSC华东理工大学 工商经济学院运筹学指派问题的性质指派问题的性质定理：定理：对于指派问题，成本矩阵的任一对于指派问题，成本矩阵的任一行行(或列或列)减去减去(或加上或加上)一个相同的数得一个相同的数得到的新指派问题与原问题同解到的新指派问题与原问题同解Page:58QSC华东理工大学 工商经济学院运筹学Page:59QSC华东理工大学 工商经济学院运筹学指派问题的求解指派问题的求解-匈牙利方法匈牙利方法成本矩阵的每一行及每一列减去该行或成本矩阵的每一行及每一列减去该行或列的最小数，使每行每列至少有一个列的最小数，使每行每列至少有一个0。如果划去这些如果划去这些0所需要的直线数不少于所需要的直线数不少于n，则此时就可以求得最优解。则此时就可以求得最优解。Page:60QSC华东理工大学 工商经济学院运筹学例题求解例题求解Page:61QSC华东理工大学 工商经济学院运筹学Page:62QSC华东理工大学 工商经济学院运筹学一般指派问题一般指派问题最大化指派问题最大化指派问题人数和工作数不等的指派问题人数和工作数不等的指派问题一个人可做几项工作的指派问题一个人可做几项工作的指派问题某项工作一定不能由某人做的指派问题某项工作一定不能由某人做的指派问题Page:63QSC华东理工大学 工商经济学院运筹学最大化指派问题最大化指派问题最大化指派问题最大化指派问题最大值最大值最最小小化化指指派派问问题题Page:64QSC华东理工大学 工商经济学院运筹学人数和工作数不等的指派问题人数和工作数不等的指派问题Page:65QSC华东理工大学 工商经济学院运筹学一个人可做几项工作的指派问题一个人可做几项工作的指派问题A1可同时做可同时做三项工作三项工作Page:66QSC华东理工大学 工商经济学院运筹学某项工作一定不能由某人做的指派问题某项工作一定不能由某人做的指派问题A1不能做不能做B4;A3不能做不能做B3
