运筹学课件目标规划与整数规划

运筹学目标规划多目标决策问题实际问题决策经常面临的问题：方案优劣并不以单一准则为目标，而是以多重准则为目标约束条件并不完全符合严格的刚性条件，具有一定的弹性可能的弹性约束：

最好等于最好不大于最好不小于弹性约束的处理方法实际量＋d－－d+=目标值负偏差变量正偏差变量最好等于：最好不大于：最好不小于：顾客访问策略目标：访问时间最好不超过680小时；访问时间最好不少于600小时；销售收入尽量不少于70,000；访问老顾客数最好不少于200个；访问新顾客数最好不少于120个模型－顾客访问策略目标规划解的几何分析X100300200600500400X21002003004005001(1)(2)(3)(4)(5)目标规划的求解---序贯算法第一级目标X100300200600500400X21002003004005001(1)第二级目标X100300200600500400X21002003004005001(1)(2)第三级目标X100300200600500400X21002003004005001(1)(2)(3)X100300200600500400X21002003004005001(1)(2)(3)(4)第四级目标X100300200600500400X21002003004005001(1)(2)(3)(4)(5)第五级目标…………目标规划的求解---多阶段算法初始单纯形表单纯形表运算单纯形表运算…运筹学整数线性规划整数线性规划问题的一般形式整数线性规划问题的分类全整数线性规划混合整数线性规划0-1整数线性规划整数规划与其松弛问题当放弃整数约束时得到的线性规划称为整数规划的松弛问题。整数规划的可行域是松弛问题的可行域，反之不成立。全整数规划的求解---Gomory割平面方法132X2X122.5154整数点松弛问题最优解松弛问题的最优解Gomory定理在松弛问题的最优单纯形表中，假如有一常数项不是整数，且对应的方程为：分解和成最大整数与正分数之和：则包含了整数规划的所有整数可行解，但不包括松弛问题的最优解例题求解选择第一个方程：分解为：在原松弛问题中加入约束：即形成松弛问题2132X2X122.5154整数点松弛问题2的最优解割平面选择第四个方程（具有最大分数部分）：分解为：在松弛问题2中加入约束：即形成松弛问题3得到最优解割平面：132X2X122.5154松弛问题3的最优解松弛问题2的最优解如果选择第二个方程：分解为：在松弛问题2中加入约束：即形成松弛问题3没有找到整数解，继续做下去混合整数规划的求解---分枝定界方法分枝：当不符合整数要求时，构造两个约束条件：加入松弛问题分别形成两个子问题（分枝）定界：当子问题获得整数规划的一个可行解，则它的目标函数值就构成一个界限例132X254X1231S解S得：132X254X1231S2对S分枝：构造约束：和形成分枝问题S1和S2，得解B和CS1SA:x1=3/2,x2=10/3Z=29/6S2C:x1=1,x2=7/3Z=10/3S1B:x1=2,x2=23/9Z=41/9132X254X1231S2对S1分枝：构造约束：和形成分枝问题S11和S12，得解DS12S11无可行解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/14132X254X1231S2对S12分枝：构造约束：和形成分枝问题S121和S122，得解E和FS121S122SA: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=40-1整数规划变量只能取0或1的整数线性规划0-1规划的应用-项目投资预算模型变量假设:模型:0-1规划的应用-工厂-销售点配置问题生产厂顾客需求销售点45DCBA7IIIII213I工厂-销售点配置问题-问题描述问题:为使经营成本最低,应开设那些工厂及销售点?工厂-销售点配置问题-模型参数工厂-销售点配置问题-模型0-1规划的求解—隐枚举方法最优解（x1,x2,x3)=(1,0,1);z=8隐枚举方法求解过程经典指派问题n个员工分配作n项工作，一致的i个员工作的j项工作的成本为cij，i=1,…,n;j=1,…,n。求最佳分配方案。指派问题的数学模型s.t.指派问题的解应对应于成本矩阵的不同行与不同列，且总成本最小例cij指派问题的性质定理：对于指派问题，成本矩阵的任一行(或列)减去(或加上)一个相同的数得到的新指派问题与原问题同解指派问题的求解-匈牙利方法成本矩阵的每一行及每一列减去该行或列的最小数，使每行每列至少有一个0。如果划去这些0所需要的直线数不少于n，则此时就可以求得最优解。例题求解一般指派问题最大化指派问题人数和工作数不等的指派问题一个人可