浙江大学最牛应用运筹学课件

1、浙江大学管理学院 杜 红 ,应用运筹学（2008复习版）,第三章 线性规划模型,建立线性规划问题模型 模型构建的一般思路： 确定该LP问题的目标是什么？ 实现目标取决于什么因素和条件？ 确定哪几个因素为决策变量？ 目标如何用决策变量来加以描述？ 约束条件如何表达？ 决策变量本身是否有限制条件？,第三章 线性规划模型,线性规划问题模型的一般形式： 目标函数： 约束条件：,X 0,第三章 线性规划模型,两个变量的线性规划问题的几何解释,Max z = X1+3X2 s.t. X1+ X26 -X1+2X28 X1 , X20,z=0,z=3,z=6,z=9,z=12,z=15.3,0 1 2 3 4 5 6,-8 -7 -6 -5 -4 -3 -2 -1,6 5 4 3 2 1,x1,x2,目标函数等值线 Z = X1+3X2,可行域,(4/3,14/3),例：求解以下线性规划问题,第三章 线性规划模型,对偶问题与影子价格 定义： 设以下线性规划问题 MAX Z = CTX s.t. AXb X0 为原始问题，则称以下问题 MIN W = bTY s.t. ATYC Y0 为原始问题的对偶

2、问题，最优值Y为影子价格,第三章 线性规划模型,对偶问题与原始问题的关系,对偶问题的性质 对偶问题的对偶是原问题。 若两个互为对偶问题之一有最优解，则另一个必有最优解，且目标函数值相等(Z*=W*)，最优解满足CX*=Y*b。 若X*,Y*分别是原问题和对偶问题的可行解，则 X*,Y*为最优解的充分必要条件是Y*XL=0和YSX*=0。,第三章 线性规划模型,原问题标准型： Max Z= CX AX + XL= b X,XL0,对偶问题标准型： Min W= Yb YA - YS= C Y,YS0,第三章 线性规划模型,原问题和对偶问题的互补松松弛关系：,第三章 线性规划模型,对偶问题解影子价格 根据对偶问题的性质有： Z* = W* = bi yi* 两边对bi求偏导数得到： Z* = yi* (i= 1,2, ,m) bi 即 yi* 表示每增加一个单位 bi 后 Z* 的增量,例3-9: 合理下料问题： 某工厂生产某一型号的机床，每台机床上分别需用2.9、2.1、1.5米长的轴1跟、2根和1根，这些轴需用同一种园钢制作，圆钢的长度为7.4米。如需要生产100台机床，问应如何安排下

3、料，才能使用料最省？试建立其线性规划模型。,第三章 线性规划模型,第三章 线性规划模型,问题分析： 对于每一根7.4米长的钢材，可有若干种下料方式把它截取成我们所需要的轴，如可以截取2根2.9米和1根1.5米，合计用料7.3米，余料为0.1米。可以列出全部的下料方式：,线性规划模型配套问题,思考题： 某厂生产一种产品，由两个B1零件和三个B2零件配套组装而成。该厂有A1，A2，A3三种机床可加工上述两种零件，每种机床的台数以及每台机床每个工作日全部用于加工某一种零部件的最大产量（即生产率：件/日）如下表所示。试求该产品产量最大的生产方案。,该题不是单纯要求两种零件产量越大越好，而是要求每个工作日按2:3的比例生产出来的B1和B2零件的套数达到最大。 决策变量：以Xij表示每台Ai(i=1,2,3)机床每个工作日加工Bj(j=1,2)零件的时间。Z为B1,B2零件按2:3比例配套的数量（套/日）。 约束条件：工时约束 X11+X12 = 1 (A1一天） X21+X22 = 1 (A2一天） X31+X32 = 1 (A3一天） 配套约束： Z = MIN(320X11+235X21+4

4、10X31)/2, (330X12+245X22+418X32)/3),Z = MIN(320X11+235X21+410X31)/2, (330X12+245X22+418X32)/3) 等价于 Z(320X11+235X21+410X31)/2 Z(330X12+245X22+418X32)/3 非负约束：Z,Xij0,Z为整数 目标函数： MAX Y = Z 求解结果： Y*=Z*=44,X11=0.13,X12=0.87,X21=1,X22=0 X31=0.25,X32=0.75, A1B1:8,A1B2:78,A2B1:70,A2B2:0,A3B1:10,A3B2:54 B1:88件；B2:132件,配料问题练习,某化工厂要用三种原料D,P,H混合配置三种不同规格的产品A,B,C。各产品的规格、单价如左表所示，各原料的单价及每天的最大供应量如右表所示，该厂应如何安排生产才能使利润最大？,配料问题练习答案,变量： 产品A中D,P,H含量分别为 X11,X12,X13 产品B中D,P,H含量分别为 X21,X22,X23 产品C中D,P,H含量分别为 X31,X32,X33 令：

5、X11+X12+X13=X1 X21+X22+X23=X2 X31+X32+X33=X3 根据规格条件有：X110.5X1; X120.25X1 X210.25X2; X220.5X2,配料问题答案,得到： - X11+ X12+X130 - X11+3X12- X130 -3X21+ X22+X230 - X21+ X22- X230 原材料供应条件： X11+X21+X31100 X12+X22+X32100 X13+X23+X3360 非负约束：Xij0, i,j=1,2,3 目标函数：max z = -15X11+25X12+15X13- 30X21+10X22-40X31-10X33,第四章 线性规划的扩展,整数线性规划(Integer Linear Programming, ILP) 问题定义： 决策变量是整数的线性规划 所有变量都取整数的规划称为纯整数规划 部分变量取整数的规划称为混合整数规划 整数规划与线性规划的关系 线性规划问题 整数规划问题,第四章 线性规划的扩展,整数规划与线性规划解的差异,X2,X1,A,B,线性规划解：A （2.6，3.8）, Z=17.8,整

6、数规划解： B （5，3 ）, Z=17.0,第四章 线性规划的扩展,0-1规划 一些变量的取值被限定为0或1。是整数规划的特例。 0-1规划的一般模型： s.t. Xj = 0,1 j=1,2,n （X=0,1 等价于 X1, X0 且取整数。） 0-1规划问题求解：思路与LP、IP问题一致。 0-1变量的灵活运用（选与不选或只能选几种等）。,例4-2 厂址选择问题 在N个地点中选r个（Nr）建厂，在第i个地点建厂（i=1，2，N）所需投资为 Ii 万元，占地Li亩，建成以后的生产能力为Pi 万吨。现在有总投资I万元，土地L亩，应如何选择厂址，使建成后总生产能力最大。,第四章 线性规划的扩展,设： 整数规划（0-1规划）模型为：,投资约束,土地约束,建厂约束,第四章 线性规划的扩展,例4.3 考虑固定成本的最小生产费用问题 某工厂有三种设备均可生产同一产品，第j种设备运行的固定成本为dj，运行的单位变动成本为cj，则生产成本与产量xj的关系为： j=1,2,3 如何使设备运行的总成本最小？,第四章 线性规划的扩展,引入01变量 yj ， 令 建立以下模型： 这里M是一个很大的正数。

7、当yj=0时，xj=0，即第j种设备不运行，相应的运行成本 djyj+cjxj=0 当yj1时，0xjM，实际上对xj没有限制，运行成本为 dj+cjxj 这是一个混合0-1规划问题,第四章 线性规划的扩展,练习题：建立线性规划模型,练习题 ：建立线性规划模型,决策变量确定：（是否投资需要决策） X11，X12，X21，X31 均为01变量 约束条件确定： 第一种产品的方案一和方案二最多只能选一： X11+X12 1 第二种产品、第三种产品可选也可不选： X21 1 ， X31 1 全部投资额应不超过550万 300X11+280X12+260X21+240X31 550,第一种产品 方案1 方案2 X11 X12,第二种产品 X21,第三种产品 X31,练习题：建立线性规划模型,目标函数确定：每年的收益和最大 每年的总收益包含两部分： 第一部分：项目投资收益，利用投资回收系数 第二部分：剩余资金的普通投资收益,第四章 线性规划的扩展,指派问题 n项任务（B1,B2,Bn)由n个人 (A1,A2,An) 去完成，每项任务交给一人，每人只有一项任务。第i个人Ai去做第j项任务Bj的工作效

8、率（如工时、成本或价值等）为Cij。问如何安排人员使总工作效率最好？ 设Xij表示Ai完成Bj工作，并令 1 当指派Ai去完成Bj工作 Xij = 0 当不指派Ai去完成Bj工作,第四章 线性规划的扩展,指派问题数学模型的标准型 MIN Z = （Cij0) （i= 1,2,n) (j= 1,2,n) Xij 皆为 0 或 1 由 Cij 组成的方阵 C = ( Cij )nn 称为效率矩阵,第四章 线性规划的扩展,指派问题标准型的求解匈牙利法 指派问题有以下性质： 若从效率矩阵C的任何一行（列）各元素中分别减去一个常数K（K可正可负）得到新矩阵D,则以D为效率矩阵的指派问题与原问题有相同的解，但最优值比原问题最优值小K。 用匈牙利法求解的条件： MIN、i=j 、Cij0,第四章 线性规划的扩展,匈牙利法的主要步骤： 第一步：变换效率矩阵，使在各行各列都出现零元素。 1、从矩阵C的每行元素减去该行的最小元素； 2、再从所得矩阵的每列中减去该列最小元素。 第二步：以最少数目的水平线和垂直线划去所有的零元素。如果所用的直线等于行或列数，则结束指派。否则继续。 第三步：找到没有被划去的最小

9、的元素，所有没有被划中的元素减去这一最小值。而被划中两次的元素（该元素行列都被划中）则要加上这一最小值。再返回到第一步。 第四步：最后根据零元素的位置，确定最优分配方案。,第四章 线性规划的扩展,运输问题 从产地到销地之间运送货物的最佳路径。 多个产地和多个销地； 每个产地的产量不同，每个销地的销量也不同； 各产销两地之间的运价不同。 如何组织调运，才能既满足各销地的要求，又使总的运输费用（或里程、时间等）最小。,第四章 线性规划的扩展,设有同一种货物从m个出发地1，2，m运往n个到达地1，2，n。第i个出发地的供应量（Supply）为si（si0）， 第j个到达地的需求量（Demand）为 dj（dj0）。 每单位货物从产地 i 运到销地 j 的运价为Cij。求一个使总运费最小的运输方案。 1 2 3 n 供应 1 c11 c1n s1 2 c21 成本 c2n s2 cij m cm1 cmn sm 需求 d1 dn ,出 发 地,到达地,第四章 线性规划的扩展,产销平衡的运输问题模型 令Xij为 从i地运到j地的数量 MIN Z = （Cij0) （i= 1,2,m) 供应约束 (j= 1,2,n) 需求约束 Xij0 由 Cij、Si、dj 组成的 (m+1)(n+1) 矩阵称为运输矩阵,第四章 线性规划的扩展,目标规划及有

《浙江大学最牛应用运筹学课件》由会员F****n分享，可在线阅读，更多相关《浙江大学最牛应用运筹学课件》请在金锄头文库上搜索。