《2022年运筹学习题集03 .pdf》由会员分享，可在线阅读，更多相关《2022年运筹学习题集03 .pdf（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模1、某织带厂生产A、 B 两种纱线和C、 D 两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下：产品项目A B C D 单位产值(元 ) 168 140 1050 406 单位成本(元 ) 42 28 350 140 单位纺纱用时(h) 3 2 10 4 单位织带用时(h) 0 0 2 工厂有供纺纱的总工时7200h ，织带的总工时1200h ，列出线性规划模型。解：设A 的产量为x1， B 的产量为x2， C 的产量为x3， D 的产量为x4，则有线性规划模型如下：max f(x)=(16842) x1 +(14028) x2 +(1050350) x
2、3 +(406140) x4=126 x1 +112 x2 +700 x3 +266 x4s.t. 4, 3,2, 1, 012005.02720041023434321ixxxxxxxi2、靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500 万 m3，在两个工厂之间有一条流量为200 万 m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2 万 m3和万 m3。从第一化工厂排出的工业污水流到第二化工厂以前，有 20%可以自然净化。 环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000 元/万 m3和 800 元/万 m3。现在要问在满足环保要求
3、的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。列出线性规划模型。解：设x1、 x2分别代表工厂1 和工厂2 处理污水的数量(万 m3)。则问题的目标可描述为min z=1000 x1+800 x2x11x1 + x2x12x2x1、x20 3、红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？只建模型，不求解工厂 1 工厂 2 200 万 m3500 万 m3精选学习资料 - - - - -
4、 - - - - 名师归纳总结 - - - - - - -第 1 页，共 36 页时间所需售货员人数星期日28 人星期一15 人星期二24 人星期三25 人星期四19 人星期五31 人星期六28 人解： 设 x1为星期一开始上班的人数，x2为星期二开始上班的人数，x7星期日开始上班的人数。min x1+x2+x3+x4+x5+x6+x7x3+x4+x5+x6+x7 28 x4+x5+x6+x7+x1 15 x5+x6+x7+x1+x2 24 x6+x7+x1+x2+x3 25 x7+x1+x2+x3+ x4 19 x1+x2+x3+x4+x5 31 x2+x3+x4+x5+x6 28 x1、
5、x2、 x3、 x4、 x5、 x6、 x7 0 4、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见表所示，能携带的最大重量为25 kg ，试选择该队员所应携带的物品。序号1 2 3 4 5 6 7 物品食品氧气冰镐绳索帐篷照相器材通信设备重量kg 5 5 2 5 10 2 3 重要性系数20 15 16 14 8 14 9 解：引入0 1 变量xiiiixxx不携带物品携带物品01 i 1， 7则 0 1 规划模型为：max z 20 x1 15x2 16x3 14x4 8x5 14x6 9x7 s.t. 5x1 5x2 2
6、x3 5x4 10 x5 2x6 3x7 25 xi 0 或 1， i 1， 0， 7 标准化问题1、将以下线性规划化为标准形式精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 36 页不限321321321321321,0, 019|1210|1573610.235)(minxxxxxxxxxxxxtsxxxxf0,19121019121015773610. .2235)(max654332163321533213321433213321xxxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxf2、化以下线性规划为标准形max
7、 z=2x1+2x24x3x1 + 3x23x3 30 x1 + 2x24x380 x1、x20，x3无限制解：按照上述方法处理，得该线性规划问题的标准形为max z=2x1+2x24x31+4x32x1 + 3x23x31 + 3x32x4 = 30 x1 + 2x24x31 + 4x32 + x5 = 80 x1、x2，x31，x32，x4，x5 0图解法1、用图解法求解下面线性规划。max z=2x1+2x2x1x2 1x1 + 2x2 0 x1、x2 0 解：图 1 3 中阴影部分就是该问题的可行域，显然该问题的可行域是无界的。两条虚线为目标函数等值线，它们对应的目标值分别为2 和 4
8、，可以看出，目标函数等值线向右移动，问题的目标值会增大。但由于可行域无界，目标函数可以增大到无穷。称这种情况为无界解或无最优解。2、用图解法求解下述LP 问题。121212max2328416. 4120,1,2jzxxxxxstxxj1 1 1 z=4 2 z=6 OA 图 1 3 2x1x精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 36 页解：可知， 目标函数在B(4, 2) 处取得最大值，故原问题的最优解为*(4,2)TX，目标函数最大值为*2*43*214z。3、 用 图解法求解以下线性规划问题： 1max z= x1+3x
9、2s.t. x1+x2 10 -2x1+2x2 12 x17 x1, x2 0 x210 (2,8) 6 x1-6 0 7 10 最优解为x1,x2 = 2,8 ， max z=26 (2) min z= x1-3x2精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 36 页s.t. 2x1-x24 x1+x23 x25 x14 x1, x20 x25 3 x10 2 3 4 最优解为 x1， x2 = 0， 5， min z=-15 3max z= x1+2x2s.t. x1-x21 x1+2x24 x13 x1, x20 x22 x1
10、0 1 2 3 4 多个最优解，两个最优极点为x1，x2= 2，1，和 (x1，x2)=(0 ，2)， max z=5 4min z= x1+3x2s.t. x1+2x24 2x1+x24 x1, x20 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 36 页x2x1=0 4 x4=0 2 x3=0 x2=0 x10 2 4 最优解为x1， x2 = 4， 0， min z=4 单纯形法1、用单纯形法求解max z=50 x1+100 x2x1 + x2 3002x1 + x2400 x2250 x1、x20 解：首先将问题化为标准形
11、式，然后将整个计算过程列在一个表中Cj50100000bCBXBx1x2x3x4x50 x3111003000 x421010400 0 x501001250z501000000 0 x31010-1500 x42001-1150100 x201001250z50000-1002500050 x11010-1500 x400-21150100 x201001250z00-500-5027500由于 j0j=1， 5 ，故 X*=50，250，0，50， 0T，Z*=275002、用单纯形法求解max z=2x1+x2精选学习资料 - - - - - - - - - 名师归纳总结 - - - -
12、 - - -第 6 页，共 36 页x1 + x252x15x2 10 x1、x20 解：用单纯形表实现如表110表 110Cj2100bCBXBx1x2x3x40 x3-11105 0 x42-5011010/4(min)z210000 x30-3/211/2102x11-5/201/25z060-1102=6 0，且 p20，故该线性规划有无界解无最优解。3、用单纯形法大M 法求解以下线性规划max z=3x12x2x3x12x2 + x3 114x1 + x2 + 2x3 32x1+ x3= 1x1、x2、x30 解：化为标准形式max z=3x12x2x3x12x2 + x3 + x4
13、= 114x1+ x2 +2x3 x5 = 32x1+x3= 1x1、x2、x3、x4、x50 在第二、三个约束方程中分别加入人工变量x6、x7，构造如下线性规划问题max z=3x12x2x3Mx6Mx7x12x2 + x3 + x4= 114x1+ x2 +2x3 x5 + x6= 32x1+ x3+x7 = 1x1、x2、x3、x4、x5、x6、x70 用单纯形进行计算，计算过程见表Cj3-1-100-M-MbCBXBx1x2x3x4x5x6x70 x41-21100011-Mx6-4120-1103-Mx7-20100011z3-6M-1+M-1+3M0-M004M0 x43-2010
14、0-110-Mx60100-11-21-1x3-20100011z1-1+M00-M0-3M+1M+10 x43001-22-512精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 36 页-1x20100-11-21-1x3-20100011z1000-1-M+1-M-123x11001/3-2/32/3-5/34-1x20100-1121-1x30012/3-4/34/3-7/39z000-1/3-1/3-M+1/3-M+2/ 32由于 j0j=1， 7 ，且基变量中不含人工变量，故X*=4，1，9T， z*=24、用单纯形法大M 法
15、求解以下线性规划max z=3x1+2x22x1+ x2 23x1 +4 x2 12x1、x20 解: 化为标准形式后引入人工变量x5得到max z=3x1+2x2Mx52x1+ x2 +x3= 23x1 +4 x2 x4+x5 =12x1、 x5 0 用单纯形法计算，过程列于表中。从表中可以看出， 虽然检验数均小于或等于零，但基变量中含有非零的人工变量x5=4，所以原问题无可行解。3200-MbCBxBx1x2x3x4x50-Mx3x52314100-101212-z3+3M2+4M0-M012M2-Mx2x52-5101-40-10124-z-1-5M0-2-4M-M0-4+4M2、用单纯
16、形法求解下述LP 问题。121212max2328416. 4120,1,2jzxxxxxstxxj解： 首先将原问题转化为线性规划的标准型，引入松弛变量x3, x4,x5，精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 36 页可得：121231425max2328416. 4120,1,2,5jzxxxxxxxstxxxj构造单纯形表，计算如下：jc2 3 0 0 0 iBcBXb1x2x3x4x5x0 3x8 1 2 1 0 0 4 0 4x16 4 0 0 1 0 0 5x12 0 4 0 0 1 3 j2 3 0 0 0 0
17、3x2 1 0 1 0 1/2 2 0 4x16 4 0 0 1 0 4 3 2x3 0 1 0 0 1/4 j2 0 0 0 3/4 2 1x2 1 0 1 0 1/2 0 4x8 0 0 4 1 2 4 3 2x3 0 1 0 0 1/4 12 j0 0 2 0 1/4 2 1x4 1 0 0 1/4 0 0 5x4 0 0 2 1/2 1 3 2x2 0 1 1/2 1/8 0 j0 0 3/2 1/8 0 原问题的最优解为*(4,2,0,0,4)TX，目标函数最大值为*2*43*214z。3、用单纯形法求解下述LP 问题。12121212max34240. . 330,0zxxxxst
18、xxx x精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 36 页解：首先将原问题转化为线性规划的标准型，引入松弛变量3x、4x，可得：121231241234max z34240. 330,0 xxxxxstxxxx xxx构造单纯形表，计算如下：jc3 4 0 0 iBcBXb1x2x3x4x0 3x40 2 1 1 0 40 0 4x30 1 3 0 1 10 j3 4 0 0 0 3x30 5/3 0 1 -1/3 18 4 2x10 1/3 1 0 1/3 30 j5/3 0 0 -4/3 3 1x18 1 0 3/5 -1/
19、5 4 2x4 0 1 -1/5 2/5 j0 0 -1 -1 由此可得，最优解为*(18, 4, 0, 0)TX，目标函数值为*3*184*470z。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 36 页4、用单纯形法求解下述LP 问题。12121212max2.53515. 5210,0zxxxxstxxx x解：引入松弛变量3x、4x，化为标准形式：121231241234max2.53515. 5210,0zxxxxxstxxxx xx x构造单纯形表，计算如下：jc1 0 0 iBcBXb1x2x3x4x0 3x15 3
20、5 1 0 5 0 4x10 5 2 0 1 2 j1 0 0 0 3x9 0 19/5 1 3/5 45/19 1x2 1 2/5 0 1/5 5 j0 0 0 1/2 1 2x45/19 0 1 5/19 3/19 1x20/19 1 0 2/19 5/19 j0 0 0 1/2 由单纯形表，可得两个最优解(1)(2,0,9,0)TX、(2)(20 /19,45 /19,0,0)TX，所以两点之间的所有解都是最优解，即最优解集合为：(1)(2)(1)XX，其中01。5、用单纯形法求解下述线性规划123123123123123max232883104.48,0zxxxxxxxxxstxxxx
21、 xx解：引入松弛变量4x、5x和6x，列单纯形表计算如下：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 36 页jc1 2 3 0 0 0 iBcBXb1x2x3x4x5x6x0 4x8 2 1 8 1 0 0 1 0 5x4 1 3 10 0 1 0 1/3 0 6x8 1 1 4 0 0 1 j1 2 3 0 0 0 0 4x24/5 -14/5 17/5 0 1 -4/5 0 3 3x2/5 1/10 -3/10 1 0 1/10 0 4 0 6x48/5 7/5 -11/5 0 0 2/5 1 48/7 j7/10 -11
22、/10 0 0 -3/10 0 0 4x16 0 -5 28 1 2 0 1 1x4 1 -3 10 0 1 0 0 6x4 0 2 -14 0 -1 1 j0 1 -7 0 -1 0 0 4x26 0 0 -7 1 -1/2 5/2 1 1x10 1 0 -11 0 -1/2 3/2 2 2x2 0 1 -7 0 -1/2 1/2 j0 0 0 0 -1/2 -1/2 故，原问题的最优解为*3333(10 11 ,27,267,0,0)TXxx xx，*6z，其中30 x。7、用单纯形法求解下述LP 问题。121231241234min z34240. 330,0 xxxxxstxxxx x
23、xx解：构造单纯形表计算如下：jc 3 4 0 0 iBcBXb1x2x3x4x0 3x40 2 1 1 0 40 0 4x30 1 3 0 1 10 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 36 页j 3 4 0 0 0 3x30 5/3 0 1 1/3 18 4 2x10 1/3 1 0 1/3 30 j5/3 0 0 4/3 3 1x18 1 0 3/5 1/5 4 2x4 0 1 1/5 2/5 j0 0 1 1 故，最优解为*(18, 4, 0, 0)TX，目标函数值为*3*184*470z。8、用大 M 法求解下述
24、LP 问题123123123123max2357.2510,0zxxxxxxstxxxx xx解：先将原问题化为标准型，引入松弛变量4x，得：12312312341234max2357.2510,0zxxxxxxstxxxxx xx x再引入人工变量5x、6x，得：12356123512346123456max2357.2510,0zxxxMxMxxxxxstxxxxxx x xxxx构造单纯形表计算如下：jc2 3 5 0 M M iBcBXb1x2x3x4x5x6x精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 36 页M 5x7
25、 1 1 1 0 1 0 7 M 6x10 2 5 1 1 0 1 5 j3M+2 3-4M 2M-5 -M 0 0 M 5x2 0 7/2 1/2 1/2 1 1/2 4/7 2 1x5 1 5/2 1/2 1/2 0 1/2 j0 7M/2+8 M/2-6 M/2+1 0 -3M/2-1 3 2x4/7 0 1 1/7 1/7 2/7 -1/7 2 1x45/7 1 0 6/7 -1/7 5/7 1/7 j0 0 -50/7 -1/7 -M-16/7 -M+1/7 由此得，原问题的最优解为*454(, 0)77TX，目标函数最优值为102/7。9、用两阶段法求解下述LP 问题1231231
26、23123max2357.2510,0zxxxxxxstxxxx xx解：先将原问题化为标准型，引入松弛变量4x，得：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 36 页12312312341234max2357.2510,0zxxxxxxstxxxxx xx x再引入人工变量5x、6x，得第一阶段的模型为：56123512346123456min7.2510,0zxxxxxxstxxxxxx x xxxx构造单纯形表，计算如下：jc0 0 0 0 1 1 iBcBXb1x2x3x4x5x6x1 5x7 1 1 1 0 1 0 7
27、 1 6x10 2 5 1 1 0 1 5 j3 4 2 1 0 0 1 5x2 0 7/2 1/2 1/2 1 1/2 4/7 0 1x5 1 5/2 1/2 1/2 0 1/2 j0 7/2 1/2 1/2 0 3/2 3 2x4/7 0 1 1/7 1/7 2/7 -1/7 2 1x45/7 1 0 6/7 -1/7 5/7 1/7 j0 0 0 0 1 1 由此可得第一阶段的最优解，转入第二阶段，单纯形表如下：jc2 3 5 0 iBcBXb1x2x3x4x3 2x4/7 0 1 1/7 1/7 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -
28、第 15 页，共 36 页2 1x45/7 1 0 6/7 -1/7 j0 0 -50/7 -1/7 由此得，原问题的最优解为*454(, 0)77TX，目标函数最优值为102/7。10、求解下述LP 问题123123123123123max101512539561515.25,0zxxxxxxxxxstxxxx xx解：用大M 法求解。将原问题化为标准型，可得：123123412351236max101512539561515.250,1,2,7jzxxxxxxxxxxxstxxxxxj在第三个等式约束中引入一个人工变量7x，可得：12371234123512367max1015125395
29、61515.250,1,2,7jzxxxMxxxxxxxxxstxxxxxxj用单纯形表求解，可得：jc10 15 12 0 0 0 M iBcBXb1x2x3x4x5x6x7x0 4x9 5 3 1 1 0 0 0 9/5 0 5x15 5 6 15 0 1 0 0 - 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 36 页M 7x5 2 1 1 0 0 -1 1 5/2 j2M+10 M+15 M+12 0 0 -M 0 10 1x9/5 1 3/5 1/5 1/5 0 0 0 9 0 5x24 0 9 16 1 1 0 0 3
30、/2 M 7x7/5 0 -1/5 3/5 -2/5 0 -1 1 7/3 j0 9-M/5 3M/5+10 -2M/5-2 0 -M 0 10 1x3/2 1 39/80 0 3/16 -1/80 0 0 12 3x3/2 0 9/16 1 1/16 1/16 0 0 -M 7x1/2 0 -43/80 0 -7/16 -3/80 -1 1 j0 27/8-43M/80 0 -21/8-7M/16 -5/8-3M/8 -M 0 所有变量的检验数均为负数或零，单纯形表计算完毕，但人工变量7x仍在基变量中，故原问题无可行解。写对偶问题1、写出以下线性规划问题的对偶问题max z=2x1+2x24
31、x3x1 + 3x2 + 3x3 304x1 + 2x2 + 4x380 x1、 x2，x30解：其对偶问题为min w=30y1+ 80y2y1+ 4y2 2 3y1 + 2y2 2 3y1 + 4y2 4 y1、 y2 0 2、写出以下线性规划问题的对偶问题min z=2x1+8x24x3x1 + 3x23x3 30 x1 + 5x2 + 4x3 = 804x1 + 2x24x350精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 36 页x1 0、x20，x3无限制解：其对偶问题为max w=30y1+80 y2+50 y3y1y
32、2 + 4 y3 2 3y1+5y2 + 2y3 8 3y1 + 4y2 4y3 = 4 y1 0， y2无限制，y3 0 对偶的性质1、 已知线性规划问题max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4202x1 + x2 + 3x3 +2x420 x1、 x2，x3，x40其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。解：其对偶问题为min w=20y1+ 20y2y1 + 2y2 1 12y1 + y2 2 22y1 +3y2 3 33y1 +2y2 4 4y1、 y2 0 将 y1*=6/5 ， y2*=1/
33、5 代入上述约束条件，得1、 2为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*0 ，y2*0，故原问题的两个约束条件应取等式，所以2x3*+3x4* = 203x3* +2x4* = 20解得 x3* = x4* = 4。故原问题的最优解为X*= 0， 0， 4， 4T 2、已知线性规划123123123max3421022160,1,2,3jzxxxxxxxxxxj的最优解为*(6,2,0)TX，试利用互补松弛定理，求对偶问题的最优解。解：原问题的对偶问题为：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 3
34、6 页1212121212min1016232241,0wyyyyyyyyy y將*(6,2,0)TX代入原问题的约束条件，可得：*1*262*210 02*62*216 0yy1又由*112*212*1120 230 2240 1xyyxyyxyy2将结论 1和 2结合起来，可解得*121yy。3、已知线性规划问题12341341234max25628.222120,1,2,3,4jzxxxxxxxstxxxxxj其对偶问题的最优解为*14y、*21y，试用对偶理论求解原问题的最优解。解：原问题的对偶问题为：12122121212min81222221.526,0wyyyyystyyyyyy
35、将对偶问题的最优解代入约束条件，可得：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 36 页*1*2*3*42* 42*12 02* 41 0415 042*16 0 xxxx1又由*1134*212340 280 22212yxxxyxxxx2将结论 1和 2结合起来，可得：*34*348212xxxx，解得*3*444xx即原问题的最优解为*(0,0,4,4)TX。对偶单纯形法1、用对偶单纯形法求下面问题0,753802. .64)(min21212121xxxxxxtsxxxf解：Cj4 6 0 0 min( zj - cj)
36、/ai*j CBXBbx1x2x3x4ai*j0 22 =c22 u2+v2 =4 1+1 = 20 23 =c23 u2+v3 =3 1+6 = 20 34 =c34 u3+v4 =9 2+4 = 30 由于23 = 20 ，故表中基可行解不是最优解，并以x23为第一个顶点作闭回路，如下销地产地B1 B2B3 B4产量A1 20 5 25 50 3 7 6 4 A220 x2320 2 4 3 3 A320 10 30 8 3 8 9 销量4020 15 25 该闭回路上，偶数顶点上的基变量最小值为5，以该调整量进行调整得到如表销地产地B1 B2B3 B4产量A1 25 25 50 3 7
37、6 4 A215 5 20 2 4 3 3 A320 10 30 8 3 8 9 销量4020 15 25 4、用最小元素法给出运输问题的初始可行解，检验解的最优性，如果不是最优解，改良成最优解。甲乙丙丁产量A 10 6 7 12 4 B 16 10 5 9 9 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 27 页，共 36 页C 5 4 10 10 4 销量5 2 4 6 解：用最小元素法求得初始解：甲乙丙丁产量A 3 1 4 B 4 5 9 C 2 2 4 销量5 2 4 6 用位势法计算u 和 v：甲乙丙丁ui A (10) (12) 0
38、 B (5) (9) -3 C (5) (4) -5 vj 10 9 8 12 计算非基本变量的检验数：甲乙丙丁ui A -3(6) -1(7) 0 B 9(16) 4(10) -3 C 7(10) 3(10) -5 vj 10 9 8 12 以(A 乙)作为调入格，用闭回路调整法计算(A 乙)的新运量：甲乙丙丁产量A 1 2 1 4 B 4 5 9 C 4 4 销量5 2 4 6 用位势法计算非基变量的检验数：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 28 页，共 36 页甲乙丙丁ui A (10) (6) -1(7) (12) 0 B 9
39、(16) 7(10) (5) (9) -3 C (5) 3(4) 7(10) 3(10) -5 vj 10 6 8 12 以(A 丙)作为调入格，用闭回路调整法计算(A 丙)的新运量：甲乙丙丁产量A 1 2 1 4 B 3 6 9 C 4 4 销量5 2 4 6 用位势法计算非基变量的检验数：甲乙丙丁ui A 1(12) 0 B 8(16) 6(10) -2 C 3(4) 8(10) 4(10) -5 vj 10 6 7 11 所有非基变量检验均为正数，故已得到最优解，运输成本最小值为118. 5、用 Vogel 法求出初始解，检验解的最优性，如果不是最优解，改良成最优解。甲乙丙丁产量A 10
40、 6 7 12 4 B 16 10 5 9 9 C 5 4 10 10 4 销量5 2 4 6 解：甲乙丙丁产量精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 29 页，共 36 页A 1 2 1 4 B 3 6 9 C 4 4 销量5 2 4 6 用位势法计算u 和 v：甲乙丙丁ui A (10) (6) (7) 0 B (5) (9) -2 C (5) -5 vj 10 6 7 11 非基变量检验数为：甲乙丙丁ui A 1(12) 0 B 8(16) 6(10) -2 C 3(4) 8(10) 4(10) -5 vj 10 6 7 11 所有非
41、基变量检验均为正数，故已得到最优解，运输成本最小值为118. 6、用 Vogel 法求出初始解，检验解的最优性，如果不是最优解，改良成最优解。甲乙丙丁产量A 3 7 6 4 5 B 2 4 3 2 2 C 4 3 8 5 3 销量3 3 2 2 解：先用Vogel 法求得初始解：甲乙丙丁产量A 3 2 5 B 2 0 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 30 页，共 36 页C 0 3 3 销量3 3 2 2 用位势法计算u 和 v：甲乙丙丁ui A 3 4 0 B 3 2 -2 C 4 3 1 vj 3 2 5 4 非基变量检验数
42、为：甲乙丙丁ui A 5(7) 1(6) 0 B 1(2) 4(4) -2 C 2(8) 0(5) 1 vj 3 2 5 4 所有检验数均为正数或零，故已得到最优解，最小运输成本为32。因为非基变量检验数中有0，故原问题有无穷多最优解。指派问题1、有 4 个工人。要指派他们分别完成4 项工作。每人做各项工作所消耗的时间 (h) 如下表，问如何分派工作，使总的消耗时间最少？消耗工作工人A B C D 甲3 3 5 3 乙3 2 5 2 丙1 5 1 6 丁4 6 4 10 解：变换效率矩阵如下：3 3 5 3 逐(0) 0* 2 0* 逐(0) 0* 2 0* 3 2 5 2 行1 0 3 0
43、列1 (0) 3 0* 1 5 1 6 标0* 4 (0) 5 标0* 4 (0) 5 4 6 4 10 记0* 2 0* 6 记0* 2 0* 6 每行每列都有两个以上的0 未找到最优解精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 31 页，共 36 页4(0) 0* 2 0* 重0* (0) 2 0* 81 (0) 3 0* 新1 0* 3 (0) 50* 4 (0) 5 标0* 4 (0) 5 10* 2 0* 6 记(0) 2 0* 6 2637划线过程(发现有4 条直线 ) 找到最优解答：容易看出，共有四个最优解：甲B，乙D，丙A，丁C
44、；甲D，乙B，丙A，丁C；甲B，乙D ，丙C，丁A；甲D ，乙B，丙C，丁A ； OBJ=10 。隐枚举法1、用隐枚举法求解max z 4x1 3x2 2x310,13344352.32132321321或xxxxxxxxxxxts解：原模型变为：max z 4x1 3x2 2x310,22341334435232132132321321或xxxxxxxxxxxxxx求解过程如表所示。点过滤条件约束z 值4x1 3x2 2x3 2 0， 0， 0T 0， 0， 1T 2 0， 1， 0T 0， 1， 1T5 4x1 3x2 2x3 5 1， 0， 0T 1， 0， 1T 1， 1， 0T7 4
45、x1 3x2 2x3 7 1， 1， 1T9 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 32 页，共 36 页所以该0 1 规划最优解为9, 1*3*2*1zxxx。割平面法1、用割平面法求解下面整数规划。2197maxxxz且为整数0,35763.212121xxxxxxts下表为最优表jc7 9 0 0 b CB XBx1 x2 x3x4 9 x20 1 7/22 1/22 7/2 7 x11 0 1/22 3/22 9/2 cj zj 0 0 28/11 15/11 解：线性规划的最优解为：63max,0,2/7, 2/94321zxx
46、xx由最终表中得：27221227432xxx将系数和常数项分解成整数和非负真分式之和，上式化为；213221227432xxx移项后得：即：21221227212212274343xxxx只要把增加的约束条件加到B 问题的最优单纯形表中。jc7 9 0 0 0 b CB XBx1 x2x3x4x59 x20 1 7/22 1/22 0 7/2 7 x11 0 1/22 3/22 0 9/2 0 x50 0 7/22* 1/22 1 1/2 cj zj 0 0 28/11 15/11 0 这时得到的为非可行解，用对偶单纯形法进行求解。进行迭代得到：表 4 4 jc7 9 0 0 0 b CB
47、XBx1 x2x3x4x59 x20 1 0 0 1 3 7 x11 0 0 1/7 1/7 32/7 0 x30 0 1 1/7 22/7 11/7 cj zj 0 0 0 1 8 由计算结果知还没有得到整数解，重新再寻找割平面方程。由 x1行得：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 33 页，共 36 页7327171541xxx将系数和常数项分解成整数和非负真分数之和：74476715541xxxx得到新的约束条件：74767154xx747671654xxx在的最优单纯形表中加上此约束，用对偶单纯形法求解：jc7 9 0 0 0
48、0 b CB XBx1 x2x3x4x5 x6 9 x20 1 0 0 1 0 3 7 x11 0 0 1/7 1/7 0 32/7 0 x30 0 1 1/7 22/7 0 11/7 0 x60 0 0 1/7* 6/7 1 4/7 cj zj 0 0 0 1 8 0 9 x20 1 0 0 1 0 3 7 x11 0 0 0 1 1 4 0 x30 0 1 0 4 1 1 0 x40 0 0 1 6 7 4 cj zj 0 0 0 0 2 7 则最优解为3,4*2*1xx，最优目标函数值为z*=55 。2、用割平面法求解1212121212max264520. .,0,zxxxxxxstx
49、 xx xZjc1 1 0 0 iBcBXb1x2x3x4x1 1x5/3 1 0 5/6 1/6 1 2x8/3 0 1 2/3 1/3 j0 0 1/6 1/6 解：切割方程342110333xx，化简得342xx。将切割方程加入松弛问题，代入单纯形表可得：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 34 页，共 36 页jc1 1 0 0 0 BcBXb1x2x3x4x5x1 1x5/3 1 0 5/6 1/6 0 1 2x8/3 0 1 2/3 1/3 0 0 5x-2 0 0 -1 -1 1 j0 0 -1/6 -1/6 0 1 1x
50、0 1 0 0 -1 5/6 1 2x4 0 1 0 1 -2/3 0 3x2 0 0 1 1 -1 j0 0 0 0 -1/6 得到最优解为*(0, 4, 2, 0, 0)TX，是整数解，故原问题的最优解为*10 x、*24x，最优值为*4z。不确定型决策1、用不确定性决策的几个准则进行分析决策。乐观系数为自然状态损益值需求量大S1需求量一般S2需求量小S3行动方案大批量生产A136 14 -8 中批量生产A220 16 0 小批量生产A3 14 10 3 解：一、悲观法自然状态损益值需求量大S1需求一般S2需求量小S3悲观法乐观法minijjrmaxijjr行动方案大批量生产A136 14