运筹学与最优化MATLAB编程 作者 吴祈宗 郑志勇 第9章和第10章.ppt

第9章　0-1整数规划 9.1　0-1整数规划的基本模型9.2　分枝定界法与隐枚举法9.3　bintprog函数(求解0-1整数规划)9.4　分派问题 在线教务辅导网： 教材其余课件及动画素材请查阅在线教务辅导网 QQ:349134187 或者直接输入下面地址： 9.1　0-1整数规划的基本模型 (1)aij0，表示第i个阶段第j个方案需要附加资金。(2)aij0，表示第i个阶段第j个方案产生资金。(1)bi0,表示第i个阶段附加资金的数量。(2)bi0,表示第i个阶段抽回资金的数量。 9.2　分枝定界法与隐枚举法 1.分枝定界法2.隐枚举法 1.分枝定界法 分枝定界法(branch and bound)是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题。分枝定界法也是求解0-1规划的主要算法。 2.隐枚举法 图　9-1 9.3　bintprog函数(求解0-1整数规划) bintprog函数是MATLAB主要的求解0-1规划的函数，该函数使用的是分枝定界法算法。函数求解问题的标准模型为： min fTx　　　　　　　 s.t.Ax≤b Aeqx=beq xj=0,或1，j=1,2,…,n 函数语法： x=bintprog(f) 9.4　分派问题 在现实世界，经常会遇到这样的问题：有n个人恰好可承担n项任务，一项任务由一个人完成，一个人只完成一项任务；由于每个人的专长不同，完成各项任务的效率也就不同，于是产生了应指派哪个人去完成哪项任务，才能使完成n项任务总的效率最高(所需总时间最少)的问题。这类问题称为指派问题或分派问题(assignment problem)。 表　9-1 9.4　分派问题 表　9-2 表　9-3 9.4　分派问题 表　9-4 9.4　分派问题 表　9-5 9.4　分派问题 表　9-6 9.4　分派问题 表　9-7 9.4　分派问题 第10章　目 标 规 划 10.1　目标规划模型10.2　fgoalattain函数 10.1　目标规划模型 10.1.1　问题提出10.1.2　目标规划模型的基本概念10.1.3　目标规划模型的一般形式10.1.4　利用linprog函数求解目标规划 10.1.1　问题提出 我们首先通过一个简单的例子来说明。 例：某公司分厂用一条生产线生产两种产品A和B ，每周生产线运行时间为60h，生产一台A产品需要4h，生产一台B产品需要6h。根据市场预测，A、B产品平均销售量分别为每周9台、8台，它们的销售利润分别为12万元、18万元。在制定生产计划时，经理考虑下述4项目标：首先，产量不能超过市场预测的销售量；其次，工人加班时间最少；第三，希望总利润最大。试建立这个问题的数学模型。 10.1.2　目标规划模型的基本概念 (1)正、负偏差变量d+，d-。(2)绝对约束和目标约束。(3)优先因子与权系数。(4)目标规划的目标函效。 10.1.4　利用linprog函数求解目标规划 利用linprog函数的求解步骤为： 设P=［1000,100,10,1］ f=P1(x4+x6)+P2x8+P3x9+P4(x3+2x5) =P4x3+P1x4+2P4x5+P1x6+P2x8+P3x9 =x3+1000x4+2x5+1000x6+100x8+10x9 调用linprog函数求解solvefgoalMyfun1.m 10.2　fgoalattain函数 MATLAB提供一种内置函数fgoalattain，为求解目标规划问题，但其目标规划模型相对简单。对每个目标只引入一个松弛变量γ，而且没有涉及同优先级式不同变量的权重问题。