运筹学第05章整数规划与分配问题(20141010版)

《运筹学第05章整数规划与分配问题(20141010版)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学基础毕德春辽东学院信息技术学院第5章整数规划与分配问题整数规划问题的数学模型第1节整数规划问题的数学模型1整数规划问题的提出例：某服务部门各时段（每2小时为一时段）需要的服务员人数如下表，按规定，服务员连续工作8小时（即4个时段）为一班，现要求安排服务员的工作时间，使服务部门服务员总数最小。时段12345678服务员最少数目108911138531.1.1引例第1节整数规划问题的数学模型│整数规划问题的提出解：设第j时段开始时上班的服务员人数为xj，由于第j时段开始时上班的服务员将在第(j+3)时段结束时下班，故决策变量只需考虑x1,x2,x3,

2、x4,x5，此问题的数学模型为：1.1.1引例第1节整数规划问题的数学模型│整数规划问题的提出此类问题数学模型的一般形式为：求一组变量X1,X2,…,Xn，使1.1.1引例第1节整数规划问题的数学模型│整数规划问题的提出例：某单位有5个拟选择的投资项目，其所需投资额与期望收益如下表。由于各项目之间有一定联系，A、C、E之间必须选择一项且仅需选择一项；B和D之间需选择也仅需选择一项；又由于C和D两项目密切相关，C的实施必须以D的实施为前提条件，该单位共筹集资金15万元，问应该选择哪些项目投资，使期望收益最大？项目所需投资额（万元）期望收益（万元）A610

3、B48C27D46E591.1.1引例第1节整数规划问题的数学模型│整数规划问题的提出解：决策变量：设目标函数：期望收益最大约束条件：投资额限制条件6x1+4x2+2x3+4x4+5x515项目A、C、E之间必须且只需选择一项：x1+x3+x5=1项目C的实施要以项目D的实施为前提条件：x3x4项目B、D之间必须且只需选择一项：x2+x4=1归纳起来，其数学模型为：1.1.1引例第1节整数规划问题的数学模型│整数规划问题的提出上例表明，利用0-1变量处理一类“可供选择条件”的问题非常简明方便。下面再进一步分别说明对0-1变量的应用。假定现有m种资源

4、对可供选择的n个项目进行投资的数学模型为：求一组决策变量X1,X2,…,Xn，使1.1.1引例第1节整数规划问题的数学模型│整数规划问题的提出根据变量取整数的情况，将整数规划分为：（1）纯整数规划，所有变量都取整数.（2）混合整数规划，一部分变量取整数,一部分变量取实数（3）0-1整数规划,所有变量均取0或11.1.2整数规划问题分类第1节整数规划问题的数学模型│整数规划问题的提出2整数规划问题的求解思考考虑纯整数问题：整数问题的松弛问题：1.2.1整数规划问题与其松弛问题第1节整数规划问题的数学模型│整数规划问题的求解思考“舍入取整”法：即先不考虑整

5、数性约束，而去求解其相应的LP问题（称为松驰问题），然后将得到的非整数最优解用“舍入取整”的方法。这样能否得到整数最优解？1.2.2求解ILP问题方法的思考第1节整数规划问题的数学模型│整数规划问题的求解思考例：设整数规划问题如下首先不考虑整数约束，得到线性规划问题（松弛问题）。1.2.2求解ILP问题方法的思考第1节整数规划问题的数学模型│整数规划问题的求解思考用图解法求出最优解x1＝3/2,x2=10/3且有Z=29/6。现求整数解（最优解）：如用“舍入取整法”可得到4个点即(1，3)(2，3)(1，4)(2，4)。显然，它们都不可能是整数规划的最

6、优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。x1x2⑴⑵33(3/2,10/3)1.2.2求解ILP问题方法的思考第1节整数规划问题的数学模型│整数规划问题的求解思考因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。常用的求解整数规划的方法有：割平面法和分支定界法，对于0－1规划问题采用隐枚举法和匈牙利法。1.2.2求解ILP问题方法的思考第1节整数规划问题的数学模型│整数规划问题的求解思考第2

7、节分配问题与匈牙利法1分派问题在实际中经常会遇到这样的问题，有n项不同的任务，需要n个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。2.1.1分派问题的含义第2节分配问题与匈牙利法│分派问题分配第i个人去完成第j项任务不分配第i个人去完成第j项任务例：有一份说明书，要分别译成英、日、德、俄四种文字，交甲、乙、丙、丁四个人去完成。因各人专长不同，他们完成翻译不

8、同文字所需的时间（h）如下表，应如何分配，使这四个人分别完成这四项任务总的时间为最小？2.1.