版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、补充线性规划问题习题及解答1 某铜厂轧制的薄铜板每卷宽度为 100cm现在要在宽度上进 行切割以完成下列订货任务:24cm宽的75卷,40cm宽的50卷 和32cm宽的110卷,长度是一样的,试将这个要解决的切割方 案问题列成线性规划模型,使切余的边料最少。答:有下面八种切法案 一 、 数一 品-规 出 一三四五六七八需要数量(卷)24cm400112207540cm020101015032cm00312011110余料4204412122028设X1,X2,X3,X4,X5,X6 ,X7,X8分别表示八种下料方案切割的铜卷数,求解X1,X2,X3,X4,X5,X6,X7,X8使满足条件:4X
2、ix4X52X62x7752x2x4X6X8503X3 X42X5X7X8110X1,x2,x3,X4,X5, X6 ,X7 , X80取整数并使余料总数:Z= 4x1+20x2+4x3+4x4+12x5+12x6 +20x7 +28x8 取得最小值。近似最优解X1=25/4,x 3=20,X4=50其他为0,最优值z*=305。(不是整数解)2 某养鸡场养鸡10000只,用大豆和谷物饲料混合喂养,每天 每只平均吃混合饲料,其中应至少含有蛋白质和钙。已知大豆 中含50癥白质和1 勺钙,价格是元/kg,谷物中含有10%勺蛋白 质和的钙,价格是元/kg,粮食部门每周只保证供应谷物饲料 25000k
3、g, 大豆供应量不限,问应如何搭配两种饲料,才能使喂 养成本最低,建立该问题的数学模型。解:设每周用大豆X1公斤,谷物X2公斤,数学模型为厂50%x1 +10%x2X 7X 10000=7000蛋白质%x1+%x> X 7X 10000=140钙J x1 +x2 <X 7X 10000=35000 总量x2W 25000谷物限量x1 > 0,x2 > 0min z=x1 +图解最优解x仁,x2=, 最小值z*=。3. 家昼夜服务的饭店,24小时内需要服务员的人数如下起迄时间61014-1818-2222-2服务员的最少人数48107124每个服务员每天连续工作8小时,且
4、在表中时段开始上班,试求要求满足以上要求的最少上班人数,建立该问题的数学模型。解:设在j钟点上班的人数为 xj(j=1,2,,6),上班之后连续工作8小时,下班离开,每班中间不允许交接班离开。故有4人8人10人7人12人4人26时610 时1014时1418时1822时222 时x1x2x3x4x5x6据题意有26 时 x1+x6> 4610 时 x1+x2+> 81014 时 x2+x3> 101418 时x3+x4>71822 时 x4+x5> 12222 时x5+x6> 4min Z=x1+x2+x3+x4+x5+x6最优解 x1=4 , x2=10
5、, x4=8 , x5=4 ,其他 xj=0, 最优值 min z=26(人)4. 设有四个投资机会:甲:在三年内,投资人应在每年年初投资,每年每元可获利息元,每年取息后可重新将本息投入生息。乙:在三年内,投资人应在第一年年初投资,每两年每兀可获得利 息元,两年后取息,可重新将本息投入生息。丙:在三年内,投资人应在第二年年初投资,两年后每兀可获得利息元,这种投资最多不得超过15000元。丁:投资人应在第三年年初投资,一年内每元投资可获利息元,这种投资不得超过10000元。假定在这三年为期的投资中,开始时有30000元可供投资,投资人应怎样决定投资,才能在第三年底获得最高的收益, 试建立其数学模
6、型。 解:设xij为第i年初投放到j项目的资金数,其数学模型为:f max z=+x11+x12W 30000x21+x23Wx31+x34W +x23< 15000,x34< 10000xij >0 ,(i=1,2,3 ,j=1,2,3,4)最优解 x11=12500, x12=17500, x23=15000, x3 仁 16250, x34=10000, 其他为0;最优值z*=575005. 某一求目标函数最大值的线性规划问题,用单纯形法求解时得到的 某一步的单纯形表如下:b5旳001d一 2000问ai,a2,a3,c,d各为何值及变量 属于
7、那一类性质的变量时:(1)现有解为唯一最优解。(2)现有解为最优,但最优解有无穷多个。(3)存在可行解,但目标函数无界。(4)此问题无可行解。V 0, d > 0, X 3, X 4 ,x 5都不是人工变量;=0, d> 0 , a i, a2至少一个大于零,X3,x 4,x 5都不是人工变量;>0 , d>0 , a i< 0, a2< 0, X3,X4,X5都不是人工变量;< 0 , d >0且X3,x 4,x 5至少一个是人工变量。6. 某线性规划问题的初始单纯形表及迭代后的表格如下:求a,b,,k, l各个值一m.1ia_ 1200码bc
8、d106-13011A,g2一 110fhz11 .21407*3.AI初始表 当前表答:a=3,b=2, c=4, d=-2, e=2, f =3,g=1,h=0,i =5, j =5,k=-3/2,l =0minZ3x12x23x 34x4X12x23X33x43(1)X23x 34x45s.t.2x13x27X34x42X10,X2,X3无纟勺束,x407.写出下列线性规划问题的对偶问题:max w 3y1 5y2 2y3yi2y3 32% y2 3y32答:3% 3y2 7y333% 4y2 4y34y 0,目20,衣无约束(2)st.m nZCij x ijmi 1 j 1nmax
9、waiuix a i iji1,2, ,mi 1j 1m答:ui vjCijXijbj ji 11,2, ,nUi,Vj不限艮制Xij0i1,2,m; j 1,2,n(i 12.m;minnbjVjj 112.,n)&用对偶单纯形法求解下列线性规划问题min Z x1 x2(1)2X1 X2 4解:化成标准形式,列对偶单纯形表st. x1 7x2 7X1,x20cj-1-100bCBXBX1x2x3x40x3-2-110-40x4-1-701-7入=cj-zj-1-1000采用对偶单纯形迭代规则得最优表:-1X1107/131/1321/13-1x2011/13-2/1310/13入0
10、0-6/13-1/1331/13=cj-zj最优解 X=(21/13,10/13,0,0), 最优值 minZ= 31/13(maxZ' = -31/13)min Z 4x1 12x2 18x3(2)Xl 3X3 3 解:化成标准形式,列对偶单纯形表st.2x2 2x3 5xX2,X30cj-4-12-1800bCBXBx1x2x3x4x50X4-10-310-30X50(-2)-201-5入j=:cj-zj-4-12-18000X4-10(-3)10-3-12X20110-1/25/2入j=:cj-zj-40-60-6-18X31/301-1/301-12X21/3100-1/23/
11、2入j=:cj-zj-200-2-6最优解 X=(0,3/2,1,0,0),最优值 minZ=36(maxZ = 0- (3/2) x 12-1X 18=-36)9.设minZ3x15x2X32x44x5X1X2X33x4X56s.t.X1X22x3X4X53X1,X2,X3,X4,X50(1) 写出其对偶问题。(2) 求解对偶问题。(3) 从对偶解中求出原问题的解答:(1)对偶模型maxw6 y13 y 2y1y 23y1y 25s .t.y12 y 213 y1y22y1y24y10, y20(2) 求解对偶问题,图解法。得Y=(-3,1) ,w*=-15。(3) 利用互补松弛性求原问题解
12、,由yi,y2异于0,知原约束均为等式;又由对偶约束1,2,4式为严格不等式,故可得xi,x 2,x 4等于0。代入原约束方程组,解得X3=3,X5=3,即X*=(0,0,3,0,3)T ,最优值z =-1 X3 - 4 X 3= -15=w。10.从下面最优单纯形表中(最大化问题,约束条件均为“”连接)#1b営】1102012001104丄20-201161A)000-40一 9-5(1) 写出原问题与对偶问题的最优解。(2) 求二,二,并解释这两个数值的含义。b1X6(3) 如果以代价5增添第一种资源一个单位,是否值得2(4) 若有人原向你购买第三种资源,应要价多少才合算(5) 是否有其它
13、最优解,如果没有,说明为什么如果有,则求出另一 个最优解。解: 原问题最优解X*=(2,0,3/2,0,1,0)T,对偶问题最优解丫*=(4,0,9,0,0,0)。(2)在最优表上可以得到最优基的逆B1,20 1B 110 411 6根据最优表上 P ' =B-1Pj,可解得P=BP',从而得A474717100A2712711701017*270014717021314bBb27“70321114271117对偶解-单纯形因子CbB 1丫(4,0,9)再由检验数jCjC bB 1pj,0可得CjjCbB 1Pj解得 0(1,120,0,0),最优值z*=1 X2+0+2X (
14、3/2)=5 。在最优方案时,有yi 4 ,因为bi影子价格大于0,是稀缺资源,故在一定范围内每增加一个单位该种资源就会增加4个单位总收入(影子价格或边际收入为 4)。对C6,X6表示第三种资源剩余数量,该偏导数值表示资源剩余量X6对总收入的影响率。在初始方案时其值为 0,在最佳方案时其值为-9, 从另外角度说明引入该资源有利于减少短缺造成的损失或增加收入(影 子价格为9)(3)如果以代价5增添第一种资源一个单位,会增加4个单位总收2入,值得。(4) 若有人愿向你购买第三种资源,要价不低于其影子价格 9才合算。(5) 在最优表上,非基变量X2的检验数为0,故最优解不唯一。令 X2 进基,xi出
15、基,换基迭代得新最优解X*=(0,2,3/2,0,5) T ,最优值 z*=0+1x 2+2(3/2)=5。11.设max Z5x1 5x213x3x1 x2 3x3201st.12x1 4x2 10x3 902X1,X2,X30先用单纯形法求出最优解,再分析在下列各条件单独变化的情况下最优解的变化。(1) 约束条件(2)右端常数由90变为70。(2) 目标函数中X3的系数由13变为8。(3) 增加一个约束条件:2Xi 3X2 5X3 50解:先用单纯形法求出最优解MAX:-5X1 +5X2 +13X3ST:1 -1X1 +1X2 +3X3 +1X4= 202 12X1 +4X2 +10X3+
16、1X5 = 90得到了第一个可行基用最大检验数法I BAC5 5130 0bX1X2X3 X4 X51 X2520-1131 02 X5010160-2-41Cj-Zj-10000-2-50迭代次数=2最优解MAX Z= 100变量名 取值检验数X1 0X2 20X3 0X4 0X5 10约束标号对偶价格(1)(2)在最优基不变的条件下,变量在目标函数中的系数的取值区间变量名现系数系数取值区间X1(-,)X2(,)X3(-,)X4(-,)X5(,)在最优基不变的条件下,右端常数项的取值区间常数取值区间约束序号 现常数(1)(,)(2)(, )(1)约束条件(2)右端常数由90变为70,不影响最
17、优基,只须验证可行性。由最优表找到最优基的逆 B1,B 1b1 0 204 17020X5不可行,采用对偶单纯形迭代,x5出基,x3进基,I BAC-5 51300bX1X2X3 X4X51 X3135-8012-1/22 X2552310-53/2Cj-Zj-90-1600-1-1最优解变量名取值检验数X1 0X2 5X3 5X4 0X5 0MAX Z= 90 目标函数中非基变量 X3的系数C3由13变为8。检查检验数入3=C3-CbB-1Pb=8-(5,0)(3,10)t=8-15=-7<0,最优解,最优值不(3)增加一个约束条件:2x1 3x2 5X3 50,引进松弛变量X6作为一
18、个基变量,在最优表添加一行,迭代出单位矩阵和检验数形式,判断是 否最优解I BA C-5 5 13 00 0X1 X2 X3 X4 X5 X61X2520-1131002X5010160-2-4103X6050235001Cj-Zj -100 00 -2 -5 0 0I BA C -5 5 13 00 0b X1 X2 X3 X4 X5 X61 X2 5 20 -12 X5 0 10 160 -2 -43 X6 0 -10 50 (-4) -30 1Cj-Zj -100 00 -2 -5 0 0采用对偶单纯形迭代,x6出基,x3进基,I BA C-5 5 13 00 0X1 X2 X3 X4
19、X5 X61 X2 5 25/2 11/4 1 0 -5/4 0 3/42 X5 0 15 27/2 0 0 -5/2 1 -1/23 X3 13 5/2 -5/4 0 1 3/4 0 -1/4Cj-Zj -95 -5/2 00 -7/2 0 -1/2最优解MAX Z= 95变量名 取值检验数X1 0X2 25/2X3 5/2X4 0X5 15X6 0约束标号对偶价格(1)(2)(3)在最优基不变的条件下,变量在目标函数中的系数的取值区间变量名现系数系数取值区间X1(-,)X2(,)X3(,)X4(-,)X5(,)X6(-,)在最优基不变的条件卜,右端常数项的取值区间约束序号现常数常数取值区间
20、(1)(,)(2)(, )(3)(,)3x12x2 X3610X16x23X3125s.t.1X1X2X34202X1,X2,X30(1) 求在不影响最优基的条件下各个Cj的允许变化的范围。(2) 求在不影响最优基的条件下各个b的允许变化的范围。 解:列单纯形表求解得最优表,利用最优基不变时求解各系数区间MAX: 2X1 +5X2 +8X3ST:1 3X1 +2X2 -1X3 +1X4=6102 -1X1 +6X2 +3X3+1X5=1253 -1X1 +1X2+1/2X3+1X6 =420MAX: 2X1 +5X2 +8X3ST:1 3X1 +2X2 -1X3 +1X4=6102 -1X1 +6X2 +3X3+1X5=1253 -1X1 +1X2+1/2X3+1X6 =420得到了第一个可行基用最大检验数法I BAC 258 000b X1 X2X3 X4X5 X61X40 61032 -110 02X50 125 -16 301 0125/33X60 420 -11 1/200 1840Ci-zj0 258 000旋转元是A23用最大检验数法
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 老龄化背景下医患关系特点
- 糖尿病治疗策略研究
- 跨界融合下的医疗产业创新
- 高血压药物治疗对中年男性性功能的影响
- 人感染HN禽流感病毒标本采集、运送及保存
- ICU医院感染控制与监测
- 2027年寒假开学摸底考试七年级英语练习卷及答案解析
- 贫困患者医疗救助与关爱
- 妇科肿瘤治疗策略与案例分享
- 针刺配合耳穴贴压法治疗儿童孤独症
- 高甘油三酯血症管理专家共识(2025版)
- 体育场馆安全生产管理台账
- 2026年(完整版)院前急救知识培训题(含答案)
- 2026安徽省考评员培训考试题库及答案
- 凝心聚力共逐梦家校携手启新程
- 2026年度专项行动保密工作排查整治专项行动方案
- 桥梁伸缩缝更换工程施工组织方案
- 混凝土路面拆除及恢复施工方案
- 2026及未来5年中国航空飞行培训行业市场全景调研及前景战略研判报告
- 2025河南洛阳国裕集团招聘6人笔试参考题库附带答案详解(3卷合一版)
- 中医治疗慢性疲劳综合症中药治疗
评论
0/150
提交评论