运筹学基础及应用(1)

运筹学基础及其matlab应用嘿，朋友！想象一下这样一个场景，你正在筹备一场盛大的生日派对。

从邀请名单的确定，到场地的布置，再到美食的准备，每一个环节都需要精心策划，这时候，你有没有觉得自己就像一位指挥千军万马的将军，在排兵布阵，力求让这场派对完美无缺？其实啊，这背后隐藏的就是运筹学的奥秘。

就拿邀请名单来说吧，你得考虑哪些朋友之间关系好，把他们安排在相邻的位置，能让气氛更融洽；哪些朋友可能不太合得来，得适当隔开，免得闹出不愉快。

这可不就是在做资源的优化配置嘛！再说说场地布置。

你得根据场地的大小，合理安排桌椅、舞台、音响设备等等。

要是安排不好，可能就会显得拥挤杂乱，大家玩得也不痛快。

这像不像在解决一个复杂的空间布局问题？还有美食准备，得考虑大家的口味偏好，预算限制，以及食物的供应量。

既要让大家吃得开心，又不能浪费，这也是一门学问呢！而这时候，Matlab 就像是我们的得力助手。

它就像一个超级智能的军师，能帮助我们快速地分析和解决这些问题。

比如说，通过输入各种参数和条件，Matlab 能迅速给出最优的座位安排方案，让大家都能舒适又愉快地交流。

它还能根据预算和口味需求，计算出最合适的美食采购清单。

你可能会问，这是不是太复杂啦？其实不然。

举个简单的例子，就好比你在玩拼图游戏，每一块拼图都有它合适的位置，而运筹学和Matlab 就是帮你找到那些最合适的位置，让整个画面完美呈现。

咱们在日常生活中，处处都能见到运筹学的影子。

比如说，你每天早上规划上学或者上班的路线，怎么能最快到达目的地，这也是一种简单的运筹。

还有，你安排自己的学习时间，什么时候复习语文，什么时候做数学题，怎样才能让学习效率最高，这也是在运用运筹学的知识。

再比如，超市在进货的时候，要考虑哪些商品畅销，应该多进一些；哪些商品销量一般，要控制进货量。

这也是在进行资源的优化配置，运用了运筹学的原理。

说到这，你是不是觉得运筹学其实离我们并不遥远，而且还特别有用呢？总之，运筹学就像是我们生活中的智慧指南，而 Matlab 则是让这指南更加精准和高效的工具。

运筹学基础及应用P43例13 、混合配料问题:某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。

已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如表1-19所示。

问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大。

试建立这个问题的线性规划的数学模型。

表1-19甲乙丙原料成本(元/kg) 每月限制用量(kg) A 2.00 2000 ?60% ?30%B 1.50 2500C 1.00 1200 ?20% ?50% ?60%0.50 0.40 0.30 加工费(元/kg)3.40 2.85 2.25 售价(元/kg)P44例14、投资项目的组合问题:兴安公司有一笔30万元的资金，考虑今后三年内用于下列项目的投资:(1) 三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年投资;(2) 只允许第一年初投入，于第二年末收回，本利合计为投资额的150%，但此类投资限额不超过15万元;(3) 允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元;(4) 允许于第三年初投入，年末收回，可获利40%，但限额为10万元。

试为该公司确定一个使第三年末本利和为最大的投资组合方案。

P44例15、生产、库存与设备维修综合计划的安排:红光厂有2台车床，1台钻床，1台磨床，承担4中产品的生产任务(已知生产各种产品所需的设备台时及生产单位产品的售价如表,,20所示(对各种产品今后三个月的市场最大需求(小于最大需求量时即可全部销出)及各产品在今后三个月的生产成本分别如表1,21和表1,22所示(上述设备在1~3月内各需进行一次维修,具体安排为:2台车床于2月份、3月份各维修一台,钻床安排在2月份维修,磨床安排在3月份维修.各设备每月工作22天.每天2班,每班8h,每次维修占用半各月时间.又生产出来的产品当月销售不出去(超过最大需求量)时,可在以后各月销售,但需付每件每月储存费5元.但规定每月底各种产品储存量均不得超过100件.1月初各产品无库存,要求3月底各产品均库存50件.试安排该厂各月的生产计划,使总的利润为最大.表,,20 a值单位:h iji ? ? ? ? j车床 ,., ,., ,.,钻床 ,., ,., ,.,磨床 ,., ,., ,.,售价(元,件) ,, ,, ,, ,,表 1,21 最大需求量单位:件 K ? ? ? ? j1月 200 300 200 200 2月 300 200 0 300 3月 300 100 400 0表,,22 产品成本单位:元,件K ? ? ? ? j,月 ,, ,, ,, ,, ,月 ,, ,, ,, ,, ,月 ,, ,, ,, ,,P81例1、某食品公司经销的主要产品之一是糖果。

第五版运筹学基础与应用-大题模拟试题及答案计算题一1. 下列线性规划问题化为标准型。

(10分) 123min +5-2Z x x x =-123123121236235100,0,x x x x x x x x x x x +-≤-+≥+=≥≤符号不限2. 写出下列问题的对偶问题 (10分)123min 42+3Z x x x =+123123121234+56=78910111213140,0x x x x x x x x x x x --+≥+≤≤≥无约束，3. 用最小元素法求下列运输问题的一个初始基本可行解(10分)4．某公司有资金10万元，若投资用于项目(1,2,3)i i i x =的投资额为时，其收益分别为11122()4,()9,g x x g x x ==33()2,g x x =问应如何分配投资数额才能使总收益最大？(15分)满满5．求图中所示网络中的最短路。

（15分）计算题二1、某工厂拥有A,B,C三种类型的设备，生产甲、乙两种产品，每件产品在生产中需要使用的机时数，每件产品可以获得的利润，以及三种设备可利用的机时数见下表：求：（1）线性规划模型；（5分）（2）利用单纯形法求最优解；（15分）4.如图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。

现在有一个人要从1v 出发，经过这个交通网到达8v，要寻求使总路程最短的线路。

（15分）5. 某项工程有三个设计方案。

据现有条件，这些方案不能按期完成的概率分别为0.5,0.7,0.9,即三个方案均完不成的概率为0.5×0.7×0.9=0.315。

为使这三个方案中至少完成一个的概率尽可能大，决定追加2万元资金。

当使用追加投资后，上述方案完不成的概率见下表，问应如何分配追加投资，才能使其中至少一个方案完成的概率为最大。

(15分)计算题三1、某工厂要制作100套专用钢架，每套钢架需要用长为2.9m , 2.1m , 1.5m的圆钢各一根。

运筹学基础及丨、V:用习题解答习题一 P461.1(a)2 = 3。

(b)用亂解法找+到满足所打约柬条仲的公：it•范W，所以该问题无可行解。

1.2(a)约束方程组的系数矩阵最优解A.=(o，i a o,7，o，o)r(b)约束方程组的系数矩阵 f I 2 3 4、4 = l2 2 I 2,最优解1 = (^,0，11，0^ V55 )"1.3(a)(1)图解法⑵单纯形法首先在各约朿条件上添加松弛变铽，将问题转化为标准形式max z = 10a-, +5a'2 +0x3 +0a4[3a-. +4 义2 + A3 = 9 si.<[5a-j + 2X2 + a'4 = 8则A，P4组成个猫《=令 A = ;c2 = 0得-站可行解a_ = (0.0.9,8)，山此列出初始单纯形表cr 2 >0， 0 - minj 2Ax2xi =~，a-3 =0, a 4最优解即为严+2X2=24的解x =卩，2V 最大值z : IA"i + X y =5I 2 2 /新的单纯形农为A', Xo X A14 14_5_ _25M ~T?q.qcO ，表明已找到问题垴优解.(b)(1)图解法17(2)单纯形法苘先在外约朿条件.h 添加松弛变M ，将问题转化为标准形式 max z = 2.v, + x 2 + Ox 3 + 0.v 4 + Oa 5 5a'2 + = 15 6.y, + 2x 2 + .v 4 = 240 00 --2 *^4o A :5、Q 0 一4(7,^2 <0,表明已找到问题最优解^ =1，X 2=- , A-32L估• 17Hi Z =——21.6(a)在约朿条件中添加松弛变量或剩余变量，且令k = jc 2 -a :； (a*2 > 0,.v ； > o)Xx = ~X->该问题转化为max z' = -3a, - x 2 + .v 2 - 2a 3 + 0.v 4 + (Xv 5 2x | + 3a -2 - 3a 2+ 4a 3 +a 4 =12攀 M I4a'| +x 2 -A*2 -2a*3 —^5 =8 3a*, -X 2 +X 2 — 3a*3 = 6A*,, A '2，X 2, x 3，A-4 , A 3 ^ 0-K 约朿系数矩陴为23 -34 I 0 4 丨-1-20-13 -丨丨一3 0 0在A 屮人为地添加两列单位向虽/>7，2 3 -3 4 1 0 0 0 4 丨-1 -2 t) -1 丨 0 3-1 I -3 0 0 0 1令 max z'= -3a -i - x 2 +x 2- 2.v 3 + Oa:., + 0.v 5 - Mx 6 - Mx 7 得初始单纯形表15最大a 4 = 0，x 5SS ^ Xi x 2x 4 x 5 x 6-2 0 0M -M4 10 -I 0 00 0 0-3 + 7M -J 1 -2-5M 0 -M 0 0-I-5(b)在约朿条件中添加松弛变M 或剩余变M ，.R 令a:3 (jc 3>0,.x ；>0)该问题转化为max z • = 一3^ - 5.v 2 + x ?- x ? + 0,v 4 + Ox 5 x, + 2X 2 + x^- x^-x 4 =6 2.v, + x 2- 3jc 3 - 3^：3 + a*5 = 16 x 2+ 5 a*3 一 5a*3= 10 •v p A ：2，“x 4，A 5^0艽约柬系数矩阵为213-30-1 115-50 0v/ft A 屮人为地添加两列单位向觉p 7, 121-1-1010、2 13-30 100 115 -5 0 0 01、 /令 max z , = -3a*, 一 5,v 2 + .v 3 一 x 3 + 0x 4 + 0x s 一 Mx b - Mx 1衍初始单纯形表0 0 -M - M X. X, X,X, X, X, X, x n-A/ x 616-M x 7 10-3 + 2A/ 5 + 3M 1+6M -1-6M -M 0 0 0(a)解1:大\1法在上述线性规划问题中分别减去剩余变萤x 4，x 6,〜再加上人工变蛩15，17，'，得max z = 2x t - x2 + 2x3 + 0,v4 - Mx s + 0,v6 - Mx7 + 0a8- Mx^-3 + 7M -J 1 -2-5M 0 -M 0 0A', + X 2 + A ：3 - + JC 5 = 6 -2x l + jc 3 — a*6 + x 1 —2 2x z — j c 3 - a *8+ j c 9 =0a-,,.v 2,a*3,j:4,a:5,^6,x 7,x 8,a-9 >0，r,其中MS 个任意人的正数-据此可列出单纯形表22MMMjc, x 2x 4X5 X6 A-M x s 6 -M x 7一2 —Ma 、00 0 0[2]0 M 02-M 3A/-1 2 + A/ -M 1/2 -1/2 0 0-1/2 -1/2x s-M x,—Ix\ [1]1/2^ 5M 3 … ^… A/ I 1 3A/ 2-M0 ----- + — - M0 -M 0 ------------------ 一十 ---2 2 2 2 2 2-M jr 5 3 2 .v 3 2 -I x 2 I 3/2 -3/2 1/2 -1/2 -11-1/2 1/2 -1/2 1/20 0 0 1 1 03/40 0?>M +3 -5M -3 M-3M4Af+5 0 ■M22 2x, 3/4 A 3 7/2 7/40 00 1 0| 43/8 - 8 8-5/4 -M8山单纯形表计算结果可以ft 出，ct 4 >0且％<0(/ =丨，2，3),所以该线性规划问题有无界解 解2:两阶段法。