




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、运筹学作业精讲运筹学作业精讲第一单元某企业生产甲、乙两种产品,其单位利润分别为20元和30元。每生产一件甲产品需劳动力3个,原材料2千克,设备4小时;每生产一件乙产品需劳动力7个,原材料4千克,设备3小时。企业现有劳动力240个,原材料150千克,设备可用时间为250小时。问:如何安排生产计划,才能使所获总利润最大?写出线性规划模型;化成问:如何安排生产计划,才能使所获总利润最大?写出线性规划模型;化成标准形式;用图解法进行求解。标准形式;用图解法进行求解。解:设解:设 x x1 1和和x x2 2分别表示产品甲和乙的产量,分别表示产品甲和乙的产量,这样可以建立如下的数学模型。这样可以建立如下
2、的数学模型。目标函数:目标函数:Max20Max20 x x1 1 +30 +30 x x2 2约束条件:约束条件:s.t.3 s.t.3 x x1 1 +7 +7 x x2 2 240 240(劳动力限制)(劳动力限制) 2 2 x x1 1 + 4 + 4 x x2 2 150 150(原材料限制)(原材料限制) 4 4 x x1 1 + 3 + 3 x x2 2 250 250(设备限制)(设备限制) x x1 1,x x2 2 0 0(非负约束)(非负约束)化为标准型:化为标准型:目标函数:目标函数:Max20Max20 x x1 1 +30 +30 x x2 2约束条件:约束条件:s
3、.t.3 s.t.3 x x1 1 + 7 + 7 x x2 2 + +x x3 3= 240= 240 2 2 x x1 1 + 4 + 4x x2 2+x x4 4=150=150 4 4 x x1 1 + 3 + 3 x x2 2 + +x x5 5= 250= 250 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5 0 0阴影部分为可行域,阴影部分为可行域,虚线为目标函数线。虚线为目标函数线。由图可知最优解为由图可知最优解为约束约束2 2和约束和约束3 3的的交点,解得坐标为交点,解得坐标为(55,1055,10),故最),故最优生产计划为生产优生产计划为生产甲产
4、品甲产品5555件,乙件,乙产品产品1010件,最大件,最大利润为利润为202055+3055+301010 =1400 =1400元。元。第二单元某厂生产三种型号的铝锅,已知单耗数据如下。试制定最优生产计划使总收入最大。 解:设解:设 x x1 1、x x2 2、x x3 3分别表示大号、中号、小号铝锅的产量,分别表示大号、中号、小号铝锅的产量, 这样可以建立如下的数学模型。这样可以建立如下的数学模型。目标函数:目标函数:Max50Max50 x x1 1 +40 +40 x x2 2+30 +30 x x3 3约束条件:约束条件:s.t.6s.t.6x x1 1 +2 +2 x x2 2+
5、 4 + 4 x x3 3 400 400(铝板限制)(铝板限制) 4 4x x1 1 +8 +8 x x2 2+ 6 + 6 x x3 3 360 360(劳力限制)(劳力限制) 8 8x x1 1 +4 +4 x x2 2+10 +10 x x3 3 420 420 (机器限制)(机器限制) x x1 1,x x2 2,x x3 3 0 0(非负约束)(非负约束) 化为标准型:化为标准型:目标函数:目标函数:Max50Max50 x x1 1 +40 +40 x x2 2+30 +30 x x3 3约束条件:约束条件:s.t.6s.t.6x x1 1 + 2+ 2x x2 2+4 +4 x
6、 x3 3 + + x x4 4= 400= 400 4 4x x1 1 +8 +8 x x2 2+6 +6 x x3 3 + + x x5 5 =360 =360 8 8x x1 1 +4 +4 x x2 2+ 10 + 10 x x3 3 + + x x6 6= 420= 420 x x1 1,x x2 2,x x3 3,x x4 4,x x5 5,x x6 6 0 0 使用单纯形法求解:使用单纯形法求解:得到最优解(得到最优解(40,25,0,110,0,040,25,0,110,0,0),最优值),最优值30003000。即应该生产大号铝锅。即应该生产大号铝锅4040个,中号铝锅个,中
7、号铝锅2525个单位,小号铝锅产量为个单位,小号铝锅产量为0 0(不生产),最(不生产),最大利润为大利润为30003000元。元。 . 第三单元线性规划Maxz=5x1+5x2+13x3s.t.x1+x2+3x32012x1+4x2+10 x390 x1,x2,x30的最优表为:分析在下列条件下,最优解分别有什么变化(1)b2由90变为70。(2)c1由-5变为-10。(3)增加一个约束条件 4 x1 + 3 x2 + 6 x3 50。 解:解:(1 1)由最优基不变的条件)由最优基不变的条件 Max - Max -bibi/ /iriririr0D0DbrbrMin-Min-bibi/ /
8、iriririr00 得得-10 = -10/1D-10 = -10/1Db b2 2 b b2 2由由9090变为变为7070,超出了允许变化范围,继续计算,超出了允许变化范围,继续计算或者由或者由B B-1-1( (b b +D +Db b)=(20,-10)=(20,-10)T T可以知道最优基发生变化,继可以知道最优基发生变化,继续迭代。续迭代。最优解变为最优解变为x x1 1 =0 =0,x x2 2 = 5 = 5,x x3 3 = 5 = 5,x x4 4 = 0 = 0,x x5 5 = 0 = 0,最优值,最优值 z z* * = 90 = 90。2 2)c c1 1是非基变
9、量的系数,最优解不变的条件是:是非基变量的系数,最优解不变的条件是:D Dc c1 1 - - s s1 1, c c1 1由由-5-10-5-10,D Dc c1 1 = -5 0 = - = -5 0 = - s s1 1,不影响最优,不影响最优解。解。 (3 3)增加一个约束条件)增加一个约束条件4 4 x x1 1 + 3 + 3 x x2 2 + 6 + 6 x x3 3 50 50,原最优解不满足这个约束。,原最优解不满足这个约束。引入松弛变量,得到引入松弛变量,得到4 4 x x1 1 + 3 + 3 x x2 2 + 6 + 6 x x3 3 + + x x6 6 = 50 =
10、 50填入最优单纯形表,进一步求解,得到最优解为填入最优单纯形表,进一步求解,得到最优解为X=(0X=(0,1010,10/3)T10/3)T,最优值,最优值为为280/3280/3。 第四单元对于以下的运输问题,若各个销地少得到对于以下的运输问题,若各个销地少得到1 1个单位的产品,将要求得到赔偿,个单位的产品,将要求得到赔偿,金额分别为金额分别为9 9、1212、6 6、1212,问如何组织运输,才能使总费用最低。(建立运,问如何组织运输,才能使总费用最低。(建立运输模型,用最小元素法求初始解,并求出最优解)输模型,用最小元素法求初始解,并求出最优解)解:总产量为解:总产量为99+55+1
11、10=26499+55+110=264,总销量,总销量44+88+88+77=29744+88+88+77=297,产,产销不平衡且供不应求,增加一个虚拟产地销不平衡且供不应求,增加一个虚拟产地A4A4,其产量为,其产量为297-297-264=33264=33。由虚拟产地运往销地的费用即为赔偿金额。因此可以。由虚拟产地运往销地的费用即为赔偿金额。因此可以建立运输模型如下:建立运输模型如下:使用最小元素法求初始解:使用最小元素法求初始解:说明:每次选择最小元素,因此依次选择说明:每次选择最小元素,因此依次选择3 3(x x3333)、)、6 6(x x2222)、)、9 9(x x4141)、
12、)、1212(x x1111)、)、1515(x x1414)、)、2121(x x3232)、)、3333(x x1212)。)。)得到初始解得到初始解x x1111=11=11,x x1212=11=11,x x1414=77=77,x x2222=55=55,x x3232=22=22,x x3333=88=88,x x4141=33=33,其余运量为,其余运量为0 0,总运费为,总运费为30033003。 使用位势法计算各非基变量检验数,填入括号中:使用位势法计算各非基变量检验数,填入括号中: 令令u u1 1=0=0,由基变量满足,由基变量满足u ui i+ +v vj j= =c
13、cij ij,依次得到各位势,依次得到各位势v v1 1=12=12,v v2 2=33=33,v v4 4=15=15,u u4 4=-3=-3,u u2 2=-27=-27,u u3 3=-12=-12,v v3 3=15=15,再根据公式,再根据公式s sij ij = = c cij ij - - u ui i - - v vj j计算各非基变量检验数。计算各非基变量检验数。进行调整:选负检验数中最小的进行调整:选负检验数中最小的s s4242,那么,那么x x4242为主元,作为进基为主元,作为进基变量。以变量。以x x4242为起点找一条闭回路为起点找一条闭回路x x4242、x
14、x4141、x x1111、x x1212,取偶数标,取偶数标号格的最小运量号格的最小运量1111作为调整量,调整后运量为作为调整量,调整后运量为x x4242=11=11,x x4141=22=22,x x1111=22=22,x x1212=0=0(调整为非基变量),得到新的基本解,并重新(调整为非基变量),得到新的基本解,并重新用位势法计算检验数(令用位势法计算检验数(令v v2 2=0=0),如下表所示。),如下表所示。 所有非基变量检验数均非负,得到最优解为所有非基变量检验数均非负,得到最优解为x x1111=22=22,x x1414=77=77,x x2222=55=55,x x
15、3232=22=22,x x3333=88=88, x x4141=22=22,x x4242=11=11,其余运量为,其余运量为0 0,最,最小的总运费为小的总运费为28052805。 第五单元有一个工厂要确定明年各季度的生产计划,通过订货了解到各季度对产品的需求量dk分别为4000件、3000件、4000件和4000件。又知,工厂生产该产品的季度固定成本为10万元(但如果在某季度中,该种产品1件也不生产,则不需支付固定成本费),单位产品的可变成本为50元,由于设备的能力所限,每季度最多只能生产5000件。若产品销售不出,则每件每季度的存贮费为8元。假设本年底无存货转入下年,明年末也不需要留
16、有存货,问每季度的生产计划应如何安排(假设生产产量以千件为单位),才能使生产的总费用最省?解:首先建立动态规划模型解:首先建立动态规划模型(1 1)阶段)阶段k k:每个季度作为一个阶段,:每个季度作为一个阶段,k k=1,2,3,4=1,2,3,4(2 2)状态变量)状态变量s sk k:第:第k k个季度初的库存量(千件)个季度初的库存量(千件)(3 3)决策变量)决策变量u uk k:第:第k k个季度的生产量(千件)个季度的生产量(千件)(4 4)状态转移方程:)状态转移方程: s sk k+1+1= = s sk k+ + u uk k - - d dk k ( (需求,千件需求,千
17、件) )(即季(即季度末库存量度末库存量= =季度初库存量季度初库存量+ +季度生产量季度生产量 - - 季度销售量或需季度销售量或需求量)求量)(5 5)阶段指标:)阶段指标: g gk k ( (s sk k, , u uk k) =) =生产成本生产成本C(C(u uk k) + ) + 库存成本库存成本E(E(s sk k) )(6 6)最优指标函数)最优指标函数f fk k ( (s sk k) ):第:第k k个季度的状态为个季度的状态为s sk k时从该季时从该季度至计划结束的最低总费用(万元)度至计划结束的最低总费用(万元)(7 7)递推方程:)递推方程: f fk k ( (
18、s sk k)=min)=ming gk k ( (s sk k, , u uk k)+ )+ f fk k+1+1( (s sk k+1+1) )(8 8)终端条件:)终端条件:f f5 5( (s s5 5)=0)=0下面进行求解,采用逆序解法。下面进行求解,采用逆序解法。(1 1)k k=5=5,f f5 5( (s s5 5)=0 )=0 (2 2)k k=4=4,00s s4 444,u u4 4=4-=4-s s4 4,s s5 5= =s s4 4+ +u u4 4- -d d4 4(说明:第(说明:第4 4季度的需求为季度的需求为4 4千件,因此库存量不应超过千件,因此库存量不
19、应超过4 4且显然非负,且显然非负,所以有所以有00s s4 444;年底不需要有库存,所以生产量;年底不需要有库存,所以生产量u u4 4 = 4 - = 4 - s s4 4)(3 3)k k=3=3,00s s3 35+5-4-3=35+5-4-3=3,s s4 4= =s s3 3+ +u u3 3- -d d3 3= =s s3 3+ +u u3 3-4-4,Max(0, 4-Max(0, 4-s s3 3)u u3 3Min(5, 8-Min(5, 8-s s3 3) )(说明:前两季度总产量为(说明:前两季度总产量为5+5=105+5=10千件,需求量为千件,需求量为3+4=73
20、+4=7千件,所以第千件,所以第3 3季度初最大库存量季度初最大库存量=10-7=3=10-7=3千件;千件;在产量需求方面,为了满足需求,至少生产在产量需求方面,为了满足需求,至少生产d d3 3- -u u3 3=4 -=4 - u u3 3,且最大产量为且最大产量为5 5千件,后两个季度总需求为千件,后两个季度总需求为4+4=84+4=8千件,千件,产量不应该超过产量不应该超过8-8-s s3 3。因此有。因此有00s s3 333,Max(0, 4 - Max(0, 4 - s s3 3)u u3 3Min(5, 8-Min(5, 8-s s3 3) ))(4 4)k k=2=2,00
21、s s2 25-4=15-4=1,s s3 3= =s s2 2+ +u u2 2- -d d2 2= =s s2 2+ +u u2 2-3-3,Max(0, 3-Max(0, 3-s s2 2)u u2 2Min(5, Min(5, 11-11-s s2 2)(5 5)k k=1=1,s s1 1=0=0,s s2 2= =s s1 1+ +u u1 1- -d d1 1= =u u1 1-4-4,44u u1 155最优解为最优解为s s1 1=0, =0, u u1 1* *=5, =5, s s2 2=1, =1, u u2 2* *=5, s=5, s3 3=3, =3, u u3
22、3* *=5, =5, s s4 4=4=4,u u4 4* *=0=0即前即前3 3个季度均生产个季度均生产50005000件,第件,第4 4个季度不生产,最低总个季度不生产,最低总费用为费用为111.4111.4万元。万元。 第六单元某企业生产甲、乙两种产品。生产一件甲产品需要使用劳动力4小时,能源2个单位,销售利润为16万元;生产一件乙产品需要使用劳动力2小时,能源4个单位,销售利润为20万元。企业目前拥有劳动力可用时间22小时,能源20个单位。在制定生产计划时,决策者考虑下述4项目标:首先,乙产品的产量不低于甲产品的产量;其次加班费用比较高,尽量不要加班;第三,尽可能充分利用能源,但是
23、又不希望再购买;最后,利润尽量不少于112万元。求决策方案。(建立目标规划模型并用单纯形法求解)解:设 x1、x2分别表示甲产品和乙产品的产,以建立如下的目标规划模型:目标函数:Minf = P1 d1+ + P2 d2+ + P3(d3- + d3+) + P4 d4-约束条件: x1 x2 + d1- - d1+ = 0 4 x1 + 2x2 +d2- d2+ = 22 2 x1 + 4x2 +d3- d3+ = 20 16x1 + 20 x2 + d4-d4+ =112 x1,x2,di-, di+ 0,i = 1, 2, 3, 4(说明:目标1和2是不超过目标值,因此正偏差变量尽量小;
24、目标3是恰好达到目标值,因此要求正、负偏差变量都尽量小;目标4要求不少于目标值,因此是负偏差变量尽量小) 下面用单纯形法进行求解。列出单纯形表,取d1-、d2-、d3-、d4-为初始基变量。把最小化问题转为为最大化问题,所以目标函数系数均乘以-1;基变量的检验数应该为0,处理初始基本可行解对应的各级检验数。由于P1、P2优先级对应目标函数中不含di-,其检验数只需取系数负值,分别为(0,0,0,-1,0,0,0,0,0,0;0)和(0,0,0,0,0,-1,0,0,0,0;0)。 P3优先级对应的目标函数中含d3-,所以其检验数需要把第3个约束行加到取负值的这一行上,得到(2,4,0,0,0,
25、0,0,-2,0,0;20 )。P4优先级对应的目标函数中含d4-,所以其检验数需要把第4个约束行加到取负值的这一行上,得到(16,20,0,0,0,0,0,0,0,-1;112 )。列目标规划的初始单纯形表如下:下面进行计算。(1)k = 1,在初始单纯形表中基变量为(d1-,d2-,d3-,d4-) =(0,22,20,112); (2)因为P1与P2优先级的检验数均已经为非正,所以这个单纯形表对P1与P2优先级是最优单纯形表;(3)下面考虑P3优先级,第二列的检验数为4最大,此为进基变量,计算相应的比值 bi/aij 写在q列。通过比较,得到d3-对应的比值最小,于是取a32(标*号)为
26、转轴元进行矩阵行变换得到新的单纯形表如下。 (4)下面考虑P4优先级,第一列的检验数为6最大,此为进基变量,计算相应的比值 bi/aij 写在q列。通过比较,得到d4-对应的比值最小,于是取a41(标*号)为转轴元进行矩阵行变换得到新的单纯形表如下。 5 5)当前的单纯形表各优先级的检验数均满足了最优条件,故为当前的单纯形表各优先级的检验数均满足了最优条件,故为最优单纯形表。于是得到最优解最优单纯形表。于是得到最优解x x1 1=2=2,x x2 2=4=4。 第七单元下图为一个交通运输网络图,道路(即弧)旁的权数表示该道路的容量和目前的运输量(cij, fij),求出该交通运输网络的最大运输
27、能力(即网络最大流)。解:解:第一次标号。第一次标号。(1 1)首先给)首先给v vs s标号标号(0, +)(0, +); (2 2)看)看v vs s:在弧:在弧( (v vs s, , v v2 2) )上,上,f fs s2 2= =c cs s2 2=2=2,不具备标号条件。在弧,不具备标号条件。在弧( (v vs s, , v v1 1) )上,上,f fs s1 1=5=5c cs s1 1=8=8,故给,故给v v1 1标号标号( (v vs s, , l l( (v v1 1) ),其中,其中l l( (v v1 1) = min) = minl l( (v vs s), (
28、), (c cs s1 1- -f fs s1 1) = ) = min+, 8-5 = 3min+, 8-5 = 3。 (3 3)看)看v v1 1:在弧:在弧( (v v1 1, , v v2 2) )上,上,f f1212 =5 =5c c1212=6=6,给,给v v2 2标号标号( (v v1 1, , l l( (v v2 2) ),其中,其中l l( (v v2 2) ) = min= minl l( (v v1 1), (), (c c1212- -f f1212) = min3, 6-5 = 1) = min3, 6-5 = 1;在弧;在弧( (v v1 1, , v v3
29、3) )上,上,f f1313 =2 =20=20,故给,故给v v4 4标号标号(- (-v v1 1, , l l( (v v4 4) ),其中,其中l l( (v v4 4) = ) = minminl l( (v v1 1),),f f4141 = min3, 2 = 2 = min3, 2 = 2。 (4 4)看)看v v3 3:在弧:在弧( (v v3 3, , v vt t) )上,上,f f3t3t =5 =5c c3t3t=9=9,给,给v vt t标号标号( (v v3 3, , l l( (v vt t) ),其中,其中l l( (v vt t) ) = min= minl l( (v v3 3), (), (c c3t3t- -f f3t3t) = min3, 9-5 = 3) = min3, 9-5 = 3。因为。因为v vt t被标上号,根据标号法,被标上号,根据标号法,转入调整过程
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 河道改道施工方案
- 2025年辽宁省锦州市中考模拟练习英语试题(三)(原卷版+解析版)
- 基于Goldberg构式语法指导的高中英语双及物结构教学效果实证研究
- 消退素D1对2型糖尿病小鼠脂肪组织胰岛素抵抗作用的研究
- 问题导向式教学在小学信息技术课教学中的应用
- 浙江省2024-2025学年高中物理第十章课时训练3探究做功与物体速度变化的关系和验证机械能守恒定律含解析
- 代理工地合同范本
- 保温砌块采购合同范例
- 天加空调施工方案
- 产品租借合同范例
- 专题16 生活用电(3大模块知识清单+3个易混易错+5种方法技巧+典例真题解析)
- 痴呆的影像鉴别诊断
- 基于义务教育质量监测结果的德育改进对策研究
- 2024版质量管理培训
- 开展我为同学办实事活动
- 幼儿园大班健康《硬硬的壳香香的肉》课件
- 医科大学2024年12月五官科护理学作业考核试题答卷
- GB/T 44569.1-2024土工合成材料内部节点强度的测定第1部分:土工格室
- 《智能网联汽车智能传感器测试与装调》电子教案
- 机动车维修经营备案表
- 《公务员录用体检操作手册(试行)》
评论
0/150
提交评论