《2022年运筹学习题集2.docx》由会员分享，可在线阅读，更多相关《2022年运筹学习题集2.docx（66页珍藏版）》请在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 的产量为 x 3, D 的产量为 x 4,就有线性规划模型如下：max fx=168 4
2、2 x1 +140 28 x2 +1050 350 x3 +406 140 x4=126 x 1 +112 x2 +700 x3 +266 x43 x 1 2 x 2 10 x 3 4 x 4 7200s.t. 2 x 3 0 . 5 x 4 1200x i ,0 i ,1 2 , ,3 42、靠近某河流有两个化工厂,流经第一化工厂的河流流量为每天 500 万 m 3,在两个工厂之间有一条流量为 200 万 m3的支流；两化工厂每天排放某种有害物质的工业污水分别为 2 万 m3和万 m3；从第一化工厂排出的工业污水流到其次化工厂以前,有 20%可以自然净化； 环保要求河流中工业污水含量不能大于
3、 0.2%；两化工厂处理工业污水的成本分别为 1000 元/万 m3和 800 元/万 m3；现在要问在满意环保要求的条件下,每厂各应处理多少工业污水,使这两个工厂处理工业污水的总费用最小；列出线性规划模型；工厂 1 工厂 2 500 万 m3 200 万 m3解：设x 1、 x2 分别代表工厂1 和工厂2 处理污水的数量万 m3；就问题的目标可描述为min z=1000x1+800x 2x 11x 1 + x 2x 12x 2x1、x20 3、红旗商场是个中型的百货商场,它对售货人员的需求经过统计分析如表所示；为了保证售货人员充分休息,售货人员每周工作五天,休息两天,并要 求休息的两天是连续
4、的,问应当如何支配售货人员的作息,既满意了工作需要又使配备的售货人员的人数最少？只建模型,不求解名师归纳总结 - - - - - - -第 1 页,共 36 页精选学习资料 - - - - - - - - - 时间所需售货员人数星期日28 人x7星期一15 人星期二24 人星期三25 人星期四19 人星期五31 人星期六28 人解： 设 x 1 为星期一开头上班的人数,x2 为星期二开头上班的人数, ,星期日开头上班的人数；min x1+x 2+x 3+x4+x5+x6+x7 x 3+x4+x5+x6+x7 28 x 4+x5+x6+x7+x1 15 x 5+x6+x7+x 1+x 2 24
5、x 6+x7+x 1+x2+x 3 25 x 7+x1+x2+x3+ x4 19 x 1+x2+x3+x4+x5 31 x 2+x3+x4+x5+x6 28 x 1、 x2、 x3、 x 4、 x 5、 x6 、 x7 0 4、一个登山队员,他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等,每种物品的重量及重要性系数见表所示,能携带的最大重量为25 kg ,试挑选该队员所应携带的物品；7 序号1 2 3 4 5 6 物品食品氧气冰镐绳索帐篷照相器通信设材备重量 kg 5 5 2 5 10 2 3 重要性系数20 15 16 14 8 14 9 解：引入0 1 变量 xix
6、i1携带物品xix i i 1, , 70不携带物品就 0 1 规划模型为：max z 20x 1 15x2 16 x3 14x 4 8x5 14x6 9x 7 s.t. 5x1 5x2 2x3 5x4 10x 5 2x 6 3x7 25 xi 0 或 1, i 1, 0, , 7 标准化问题1、将以下线性规划化为标准形式名师归纳总结 - - - - - - -第 2 页,共 36 页精选学习资料 - - - - - - - - - minfx5x 13x 22x 3maxfx 5x 1,3 x22x32x 3x1x2x 3x3x 410s .t.x 1x 2x310s .106x 13x 2
7、7x 37x3156x 13 x27x315x 112x2x3x 3x 519|10x 112x 2x3|1910x 112x2x3x3x 619x 1,0x 20,x3不限x 1,x2,x 3x 3,x 4,x 5,x602、化以下线性规划为标准形 max z=2x1+2x 24x3 x 1 + 3x 23x3 30 x 1 + 2x 24x380 x 1、x 20,x3 无限制解：依据上述方法处理,得该线性规划问题的标准形为max z=2x 1+2x24x31+4x32 x 1 + 3x 23x31 + 3x32x4 = 30 x 1 + 2x 24x31 + 4x32 + x5 = 80
8、 x 1、x 2,x31,x32,x4,x5 0图解法1、用图解法求解下面线性规划；max z=2x1+2x2x2x 1x 2 1x 1 + 2x2 0x 1、x 2 0 解：图 1 3 中阴影部分就是该1 z=4 z=6 图 1 3 1x问题的可行域,明显该问题的可行域是无界的；两条虚线为目标函数等值线,它们对应的目标值分别为2 和 4,可以看出,目标函数等值线向右移动,O 1 A 2 问题的目标值会增大；但由于1 可行域无界,目标函数可以增大到无穷；称这种情形为无界解或无最优解；名师归纳总结 2、用图解法求解下述LP 问题；第 3 页,共 36 页maxz2x 13x 2x 12x28st
9、 . 4x 1164x 212xj0,j1,2- - - - - - -精选学习资料 - - - - - - - - - 解：可知, 目标函数在B4, 2 处取得最大值,故原问题的最优解为X*4,2T,目标函数最大值为* z2*43*214；3、 用 图解法求解以下线性规划问题： 1max z= x 1+3x 2 10 s.t. x 1+x 2 12 -2x 1+2x 2x 1x 27 x1, 0 x 210 最优解为2,8 7 10 x 16 -6 0 x 1,x 2 = 2,8 , max z=26 名师归纳总结 2 min z= x 1-3x 2第 4 页,共 36 页- - - - -
10、 - -精选学习资料 - - - - - - - - - s.t. 2x 1-x 24 x 1x 2+x 23 x 1x 25 4 x 1, x 20 5 3 0 2 3 4 x 1最优解为 x 1, x2 = 0, 5, min z=-15 3max z= x 1+2x 21 s.t. x 1-x 2x 1+2x 24 x 1x 23 x 1, 0 x22 0 1 2 3 4 x 1多个最优解,两个最优极点为x1,x 2= 2,1,和 x 1,x2=0 ,2, max 名师归纳总结 z=5 4min z= x 1+3x 24 第 5 页,共 36 页s.t. x 1+2x 22x 1+x 2
11、4 x 1, x 20 - - - - - - -精选学习资料 - - - - - - - - - x24 x 1=0 x 4=0 最优解为2 4 x 2=0 x 1x3=0 0 2 x 1, x 2 = 4, 0, min z=4 单纯形法1、用单纯形法求解max z=50x1+100x2 x 1 + x 2 300 2x1 + x 2400x 2250 x1、x20 解：第一将问题化为标准形式,然后将整个运算过程列在一个表中Cj50100000T,bCBX Bx1x2x3x4x50x3111003000x421010400 0x501001250z501000000 0x31010-150
12、0 100x42001-1150x201001250z50000-1002500050x1 x41010-150 50000-211100x201001250z00-500-5027500 Z*=27500由于 j0j=1, , 5,故 X*=50,250,0,50, 02、用单纯形法求解 max z=2x1+x2名师归纳总结 - - - - - - -第 6 页,共 36 页精选学习资料 - - - - - - - - - x 1 + x25 2x15x 2 10x1、x20 解：用单纯形表实现如表110表 110Cj2100bCBX Bx1x2x3x40x3-11105 0x42-5011
13、010/4minz210000x30-3/211/2102x11-5/201/25z060-1102=6 0,且 p20,故该线性规划有无界解无最优解；3、用单纯形法大M 法求解以下线性规划max z=3x12x2x3 x 12x2 + x3 114x 1 + x2 + 2x3 32x1 + x3 = 1 x1、x2、x30 解：化为标准形式max z=3x12x 2x3x 12x2 + x3 + x4= 11 x5 = 3 = 14x 1+ x 2 +2x3 2x 1+x3x1、x2、x3 、x4、x50 在其次、三个约束方程中分别加入人工变量max z=3x12x2x3M x6M x7x
14、12x2 + x3 + x4 x5 + x6= 114x 1+ x 2 +2x3 = 32x 1+ x3+x7 = 1x1、x2、x3、x4、x5、x6、x70 用单纯形进行运算,运算过程见表x6、x7,构造如下线性规划问题名师归纳总结 CjX B3-1-100-M-Mb第 7 页,共 36 页CBx1x2x3x4x5x6x70x41-21100011-Mx6-4120-1103-Mx7-201000110z3-6M-1+M-1+30-M004MM-2x43100-1100-Mx60100-11-21-1x3-201000110z1-1+M00-M0-3M+M+1100x431-2212-5-
15、 - - - - - -精选学习资料 - - - - - - - - - -1x20100-11-21-1x3-201000111000-1-M+1-M -12z3x11001/3-2/32/3-5/34-1x20100-1121-1x30012/3-4/34/3-7/39z000-1/3-1/3由于 j0j=1, , 7,且基变量中不含人工变量,故4、用单纯形法大 max z=3x1+2x 2M 法求解以下线性规划2x1+ x2 23x1 +4 x2 12 x1、x20 解: 化为标准形式后引入人工变量 x5 得到 max z=3x 1+2x 2M x52x1+ x2 +x3= 2x4+x5
16、 =123x1 +4 x2 x1、 、 x5 0 用单纯形法运算,过程列于表中；-M+1/ 3-M+2 / 32X*=4,1,9T, z*=2名师归纳总结 - - - - - - -从表中可以看出, 虽然检验数均小于或等于零,但基变量中含有非零的人工变量x5=4,所以原问题无可行解；CBxB3200-Mbx1x2x3x4x50x3211002-Mx5340-1112-z3+3M2+4M0-M012M2x2211002-Mx5-50-4-114-z-1-5M0-2-4M-M0-4+4M2、用单纯形法求解下述LP 问题；maxz2x 13x 2x 12x 28st . 4x 116412x2xj0
17、,j1,2解：第一将原问题转化为线性规划的标准型,引入放松变量x 3, x 4,x 5,第 8 页,共 36 页精选学习资料 - - - - - - - - - 可得：maxz2x 13x 28,5st . x 12x2x 34x 1x416124x 2x 51,2,xj0,j构造单纯形表,运算如下：名师归纳总结 jc2 3 0 0 0 i第 9 页,共 36 页cBXBb1x2x3xx45x0 x38 1 2 1 0 0 4 0 4x16 4 0 0 1 0 0 5x12 3 0 4 0 0 1 j2 3 0 0 0 2 0 x32 1 0 1 0 1/2 0 4x16 0 4 0 0 1
18、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 2 4 0 0 4 1 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 原问题的最优解为X*4,2,0,0,4T,目标函数最大值为* z2*43*214；LP 问题；3、用单纯形法求解下述maxz3x 14x 22x 1x240st . . x 13x 230x x 20- - - - - - -精选学习资料 - - -
19、- - - - - - 解：第一将原问题转化为线性规划的标准型,引入放松变量3x 、4x ,可得：max z3x 1,4x 2402x 1x2x 330st . x 13x2x 4x x 2,x 3x40构造单纯形表,运算如下：名师归纳总结 jc*3 4 0 0 i第 10 页,共 36 页c BXBb1xx2x3x40 3x40 2 1 1 0 40 0 x430 1 3 0 1 10 j3 4 0 0 18 0 3x30 5/3 0 1 -1/3 4 x210 1/3 1 0 1/3 30 j5/3 0 0 -4/3 3 1x18 1 0 3/5 -1/5 4 x24 0 1 -1/5 2
20、/5 j0 0 -1 -1 由此可得,最优解为X18, 4, 0, 0T,目标函数值为* z3*184*470；- - - - - - -精选学习资料 - - - - - - - - - 4、用单纯形法求解下述 LP 问题；max z 2.5 x 1 x 23 x 1 5 x 2 15st . 5 x 1 2 x 2 10x x 1 2 0解：引入放松变量 3x 、4x ,化为标准形式：max z 2.5 x 1 x 23 x 1 5 x 2 x 3 15st . 5 x 1 2 x 2 x 4 10x x 2 , x x 4 0构造单纯形表,运算如下：名师归纳总结 jc1 0 0 第 11
21、页,共 36 页c BXBb1x2xx34xi0 3x15 3 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 由单纯形表,可得两个最优解X12,0,9,0T、X220 /19,45 /19,0,0T,所以两点之间的全部解都是最优解,即最优解集合为：X11X2,其中 01；5、用单纯形法求解下述线性规划maxzx 12x 23x 32x 1x 28x 38st
22、 .x 13x 210x 3844x3x 1x 2x x 1 2,x 30解：引入放松变量x 、5x 和6x ,列单纯形表运算如下：- - - - - - -精选学习资料 - - - - - - - - - cBjcb1 2 3 0 0 0 iXB1xx23x4x5x6x0 x48 2 1 8 1 0 0 1 x51 0 4 3 10 0 1 0 1/3 0 x68 1 1 4 70 0 x 31 T4 j1 2 3 0 0 0 0 x424/5 -14/5 17/5 0 1 -4/5 0 3 3x2/5 1/10 -3/10 1 0 1/10 0 0 x648/5 7/5 -11/5 0 0
23、 2/5 1 48/7 j7/10 -11/10 0 0 -3/10 0 ,0 x416 0 -5 28 1 2 0 1 1x4 1 -3 10 0 1 0 0 x64 0 2 -14 0 -1 1 j0 1 -7 0 -1 0 0 x426 0 0 -7 1 -1/2 5/2 1 1x10 1 0 -11 0 -1/2 3/2 2 x22 0 1 -7 0 -1/2 1/2 j0 0 0 0 -1/2 -1/2 故,原问题的最优解为X*10 11 ,2x x 3,267,0,0z*6,其中x 30；7、用单纯形法求解下述LP 问题；min z3x 14x22x 1x2x 340st . x
24、13x2x 430x x 1 2,x 3,x40解：构造单纯形表运算如下：名师归纳总结 cBjcb 3 4 0 0 i第 12 页,共 36 页XB1x2x3x4x0 3x40 2 1 1 0 40 0 x430 1 3 0 1 10 - - - - - - -精选学习资料 - - - - - - - - - j 3 4 0 0 0 3x30 5/3 0 1 1/3 18 1/3 4 x210 1/3 1 0 30 j 5/3 0 0 4/3 3 1x18 1 0 3/5 1/5 2/5 4 x24 0 1 1/5 1 j0 0 1 故,最优解为X*18, 4, 0, 0T,目标函数值为* z
25、3*184*470；8、用大 M 法求解下述LP 问题maxz2x 13x 25x 3x 1x 2x 37st .2x 15x 2x 310x x 2,x 30解：先将原问题化为标准型,引入放松变量x ,得：maxz2x 13x 25x 3x 1x 2x 37st .2x 15x 2x 3x 410x x 2,x x 40再引入人工变量x 、x ,得：maxz2x 13x 25x 3Mx5Mx 6x 1x 2x3x 57st .2x 15x2x3x4x 610x x x3,x4,x 5,x 60构造单纯形表运算如下：名师归纳总结 cBjcb2 3 5 0 M M i第 13 页,共 36 页X
26、B1x2x3xx45xx6- - - - - - -精选学习资料 - - - - - - - - - x57 1 1 1 0 1 0 7 M x610 2 5 *1 ,1 0 1 5 M j3M+3-4M 2M-5 -M 0 0 4/2 x52 0 7/2 1/2 1/2 1 1/2 M 7 1/2 1/2 0 1/2 2 1x5 1 5/2 j0 7M/2+M/2-M/2+0 -3M/2-1 8 6 1 3 x24/7 0 1 1/7 1/7 2/7 -1/7 2 1x45/1 0 6/7 -1/7 5/7 1/7 7 j0 0 -50/7 -1/7 -M-16/ 7 -M+1/7 由此得,
27、原问题的最优解为X45 74, 0T,目标函数最优值为7102/7 ；9、用两阶段法求解下述 LP 问题名师归纳总结 maxz2x 13x 25x 3x ,得：第 14 页,共 36 页x 1x 2x 37st .2x 15x 2x 310x x 2,x 30解：先将原问题化为标准型,引入放松变量- - - - - - -精选学习资料 - - - - - - - - - maxz2x 13x 25x 3x 1 x 2 x 3 7st . 2 x 1 5 x 2 x 3 x 4 10x x 1 2 , x x 3 4 0再引入人工变量 x 、x ,得第一阶段的模型为：min z x 5 x 6x
28、 1 x 2 x 3 x 5 7st . 2 x 1 5 x 2 x 3 x 4 x 6 10x x x 3 , x 4 , x 5 , x 6 0构造单纯形表,运算如下：cBjcb0 0 0 0 1 1 iXB1x2x3x4x5xx61 5x7 1 1 1 0 1 0 7 6x1 10 2 5 1 1 0 1 5 j3 4 2 1 0 0 1 2 4/7 5x0 7/2 1/2 1/2 1 1/2 1x0 5 1 5/2 1/2 0 1/2 1/2 3 j4/7 0 7/2 0 3/2 1/2 1/2 x20 1 2/7 -1/7 1/7 1/7 2 1x45/7 1 0 6/7 -1/7
29、5/7 1/7 j0 0 0 0 1 1 由此可得第一阶段的最优解,转入其次阶段,单纯形表如下：名师归纳总结 c Bjcb2 3 5 0 i第 15 页,共 36 页XB1x2x3x4x3 2x4/7 0 1 1/7 1/7 - - - - - - -精选学习资料 - - - - - - - - - 2 1x45/7 1 0 6/7 -1/7 j0 *0 4-50/7 -1/7 由此得,原问题的最优解为X45 7, 0T,目标函数最优值为7102/7 ；10、求解下述 LP 问题max z 10 x 1 15 x 2 12 x 35 x 1 3 x 2 x 3 95 x 1 6 x 2 15
30、x 3 15st .2 x 1 x 2 x 3 5x x 1 2 , x 3 0解：用大 M 法求解；将原问题化为标准型,可得：max z 10 x 1 15 x 2 12 x 35 x 1 3 x 2 x 3 x 4 95 x 1 6 x 2 15 x 3 x 5 15st .2 x 1 x 2 x 3 x 6 5x j 0, j 1,2, ,7在第三个等式约束中引入一个人工变量 7x ,可得：max z 10 x 1 15 x 2 12 x 3 Mx 75 x 1 3 x 2 x 3 x 4 95 x 1 6 x 2 15 x 3 x 5 15st .2 x 1 x 2 x 3 x 6 x
31、 7 5x j 0, j 1,2, ,7用单纯形表求解,可得：cBjcb10 15 12 0 0 0 M iXB1xx2x3x45x6xx70 x49 5 3 1 1 0 0 0 9/5 5x0 15 5 6 15 0 1 0 0 - 名师归纳总结 第 16 页,共 36 页- - - - - - -精选学习资料 - - - - - - - - - 7x5 2 1 1 0 0 -1 1 5/2 M 10 j2M+10 M+15 M+12 0 0 -M 0 x79 1x9/5 1 3/5 1/5 1/5 0 0 0 0 5x24 0 9 16 1 1 0 0 3/2 7x7/5 0 -1/5 3/5 -2/5 0 -1 1 7/3