线性规划习题答案
习题答案(2)
maxz,x,2x,x 给出线性规划问题 2.5123
x,x,x,2,123,xxx,,,1,123st. ,2x,x,x,2123,
,xx,0,,012,
(1) 写出其对偶问题;(2)利用对偶问题证明原问题目标函数值 z,1.
解:(1)对偶规划为:
minw,2y,y,2y123
y,y,2y,1,123, st.y,y,y,2,123,,y,y,y,1123,
,y,0,y,013,
T,,y,0,1,1(2) 由(1)易知是对偶规划的一个可行解,且, w,1
根据对偶理论 ,可以推知原目标函数值 z,1.maxz,w
maxz,2x,4x,x,x 给出线性规划问题 2.71234
x,3x,x,8,124,2x,x,612,,,,,6xxxst. ,234
,,,,9xxx123,
x,0,(j,1,2,3,4),j,
,TX,(2,2,4,0), 要求:(1)写出其对偶问题;(2)已知原问题最优解为试根据对偶理
论,直接写出对偶问题的最优解。
minw,8y,6y,6y,9y 解:(1)对偶规划为: 1234
y,2y,y,2,124,3y,y,y,y,41234,, st. y,y,1,34
,y,y,113,
,y,0,(i,1,2,3,4)i,
,,,,,Y,(y,y,y,y)(2)记为对偶规划的最优解,由互补松弛性质知, 1234
,,,,x,2,0,x,2,0,x,4,0X在中,因, 123
,Y从而使得对偶规划的前三个约束成为等式,即
,,,,y,2y,y,2124,,,,,3y,y,y,y,4 ,1234,,,,,yy134,
,TX,(2,2,4,0)又代入原规划中,第4个约束成为严格不等式,即
,,,x,x,x,8,9, 左边=右边 123
,y,0由互补松弛性质知: 4
43,故对偶规划的最优解为: Y,(,,1,0).55
minz,4x,12x,18x 用对偶单纯形法求解线性规划问题 2.9123
x,3x,3,13,2x,2x,5 ,23
,xi,0,(,1,2,3)i,
maxw,max(,z),,4x,12x,18x解:原规划化为标准规划为: 123
,x,3x,x,,3,134,xxx,2,2,,,5 st. ,235
,xi,0,(,1,2,3,4,5)i,
用对偶单纯形法列表计算如下:
c 0 0 ,18 ,4,12j
xx Cxxx 基 b351B24x 0 1 0 0 ,3,3 ,14
x[,2] 0 0 0 1 ,5 ,25
c,z 0 0 ,18 ,4,12jj
[,3] x 0 1 0 0 ,3 ,14
51x ,0 1 1 0 ,12222
c,z 0 0 ,6,6 ,4jj
11x , 1 0 1 0 ,18333
3111 x,,1 0 ,1222332
c,z 0 0 ,6 ,2,2jj
3,T,故最优解为: X,(0,,1),z,minz,36.2
某厂生产三种产品,其所需劳动力、材料等有关数据见下表。要求:A,B,C2.14
(1)确定获利最大的产品生产计划;(2)产品的利润在什么范围内变动时,上述最A
优计划不变;(3)如果设计一种新产品,单位劳动力消耗为8单位,材料消耗为2D
单位,每件可获利3元,问该种产品是否值得生产,(4)如果劳动力数量不增,材料不足时可以从市场购买,每单位0。4元。问该厂要不要购进原材料扩大生产,以购多少为宜。
消耗定额 产品 ABC 可用单位 资源
劳动力 6 3 5 45
材料 3 4 5 30
产品利润(元/件) 3 1 4
x,x,x解:(1)设A,B,C各生产件。有 123
minz,3x,x,4x 123
,6x,3x,5x,45123,3x,4x,5x,30st. ,123
,,0,(,1,2,3)xjj,
列表计算
xx xxx 35124x 45 6 3 5 1 0 4
x 30 4 [5] 0 1 35
c,z 3 1 4 0 0 jj
x 15 [3] -1 0 1 -1 4
341x 6 1 0 3555
3114c,z ,, 0 0jj555
111 x,,5 1 0 1333
12x ,3 0 1 1 355
13c,z ,,0 -2 0 jj55
获利最大的生产计划是各生产5件、0件、3件,最大利润为A,B,Cz,3,5,4,3,27
元。
x,x,x(2),c,,,则c,3,,时,最终表中非基变量的检验数为 24511
1,,,,(,,),(1,0,0),CB(PPP),245245B 1,(1,0,0),(3,,,4)B(PPP),245
111,,,,,,333,,= (1,0,0),(3,,4),12,,1,,,55,,
11131(1,0,0)-( 3,,,,,,,,),35353
11131(-2+ ,,,,,,,,,)35353
1,,,2,,0,3,3911,,解,,, 得,, ,,,0,5553,31,,,,,0,53,
391224即知的利润在[3,,3,],[,]上变动是,上述最优计划不变。 A5555
x(3) 设新产品的产量为。 D6
88,,,,14131,1 因为,,,, c,z,3,CB,3,(,),3,,,0,B66,,,,225555,,,,
2,,8,,,1,,4,,故应生产,最终表中应增加一列,即 ,DB,,,,,2,,5,,
最终表变为
xxx xxx356124
111 x,,5 1 0 [2] 1333
124x ,,3 0 1 1 3555
131c,z ,,0 -2 0 jj555
51111x ,,0 1 622666
13412x ,5 1 0 35151515
759171 ,,,, 0 0 10303030
551故最优计划为的产量各为0,0,5,最大利润为27元。 A,B,C,D,z,4,5,3,,222
3(4) 解法一 从(1)中的最终表知道,材料的影子价格为(已知的市,0.6,0.45
场价格)。故应再购进原材料,设再购单位(,,0)。 ,
1,,,,,,1/31/30,,,,,,13,,,,,, ,,,Bb,,,,2,1/52/5,,,,,,,,,,5,,
故最终表应变为
xx xxx 35124
1111x ,[,]5,,1 0 13333
212x , 3,,0 1 1 3555
13c,z ,,0 0 ,2jj55
当时,此表为最优表。 0,,,15
xx xxx 35124
x 1 0 1 ,15,,,3 ,15
631x 9 1 03555
974c,z , ,, 00jj555
当时,此表为最优表。 ,,15
z,3x,x,4x,0.4, 总之此时的目标函数应为。从而时,0,,,15123
21maxz,;时,。 ,,27maxz,,,,36,,1555
12 由, 解得。即应再购进原材料15单位,最大,,27,,,,36,,1555
利润为。 z,30
解法二 同解法一,应再购进原材料,设再购单位。于是原来线性(,,0),规划数学模型中,目标函数中增加了一项而第二个约束的右端增加了一项",0.4,",
。如果用灵敏度分析中“增加一个变量”的观点看,这相当于在原问题中增加了","
一个非负变量。故最终表中应增加一列 ,
01/31/301/3,,,,,,,,,,1 ,,,,,,,, ,,B,,,,,,,,11/52/512/5,,,,,,,,,,,,
相应的检验数为
00,,,,13231,1 0.4,,0.4(,),,,,CB,,,,,,,B,,,,1155555,,,,,,所以最终表应变为
xx xxx ,35124
1111x [],,5 1 0 13333
122x ,,3 0 1 1 3555
131c,z ,,0 0 ,2jj555
15 3 0 1 1 , ,1,1
631x 9 1 0 0 3555
3922c,z ,,,,0 0 jj5555
x,x,0,x,9,,,15,maxz,36,6,30故最优解为。 123
本文档为【线性规划习题答案】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。