运筹学课后习题二

1、习题二2.1 某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150单位,C不少于180单位.此人准备每天从六种食物中摄取这三种营养成分.已知六种食物每百克的营养成分含量及食物价格如表2-22所示.（1）试建立此人在满足健康需要的基础上花费最少的数学模型；（2）假定有一个厂商计划生产一中药丸，售给此人服用，药丸中包含有A,B,C三种营养成分.试为厂商制定一个药丸的合理价格，既使此人愿意购买，又使厂商能获得最大利益，建立数学模型.表2-22含量食物营养成分一二二四五六需要量A1325144081180B24930251215150C1872134100180食物单价（元/1

2、00g）0.50.40.80.90.30.2【解】（1）设Xj为每天第j种食物的用量，数学模型为minZ=05再+04勺+08弓+。9心+03/+02为13+25与+14心+4Q勒+8j+1%之8024/+9心+30%+25a4+12七+15蜂31501际+7+21码+34工邛+10工5180工.工,、后.工飞.Xj之0(2)设yi为第i种单位营养的价格，则数学模型为maxw=80必+150乃+180乃131yl+24乃+18处三0.525yl+9为+7乃0,414必+30为+21乃0.8；40再+25匕+34为0.98必+122+10乃 10 4 a - 8xa +6药 + x4 0, x3

3、 1 乃+ 6此一觊之2外2I 十 6*4 -4当-5乃+居=-3 八无约束匕二0,为之0(4)max Z - -2x. +3及 + 6a - 7匕 I 13 T3Al - 2f +x3 - 6/=96k1+5药一玉之6(5) & + 2K.一弓 + 2犬* M 25 10人之0,54无约束【解】maxZ = -2为 +3 町 +60一 7号3公-2町+后- 6/ = 96/+5应一/36一瓦 4 2 马x3 + 2 x4 M -2X135s+5y4+10乃3yl+6y广乃+川+乃之-2-2乃+2乃=3当+5%_%=6-6泗一乃+2%二-7对偶问题为:J1无约束；内40,Q0,乂40,丹之02

4、.3考虑线性规划nunZ=12近+204彳+4与之4Xj+5町22.+3.7X，为之o(i)说明原问题与对偶问题都有最优解；(2)通过解对偶问题由最优表中观察出原问题的最优解;利用公式CbB”求原问题的最优解；(4)利用互补松弛条件求原问题的最优解.【解】(1)原问题的对偶问题为maxvp=4yl4-2y2+7%+为+2乃W12，4凹+5乃+3%2。jjN0,J=L2.3(3) Cb=(7,4),45351=,5254X = (7,4) 53L 51=525= (16/5,1/5)容易看出原问题和对偶问题都有可行解，如X=(2,1)、Y=(1,0,1),由定理2.4知都有最优解。(2)对偶问题

5、最优单纯形表为C(j)42700R.H.S.BasisrC(i)y1y2y3y4y5y370-1/514/5-1/528/5y1417/50-3/52/514/5C(j)-Z(j)0-11/50-16/5-1/5w=42.4对偶问题的最优解Y=(4/5,0,28/5),由定理2.6,原问题的最优解为X=(16/5,1/5),Z=42.4(4)由yi、y3不等于零知原问题第一、三个约束是紧的，解等式再+4/=42司+3x2=7得到原问题的最优解为X=(16/5,1/5)。2.4证明下列线性规划问题无最优解minZ=xL-2x2-2x32金+马-=32，旃NO,为无约束证明：首先看到该问题存在可行

6、解，向如x=(2,1,1),而上述问题的对偶问题为max和=3凹+2乃2凹+为工1-2乃2271+3乃=-28之0，乃无约束由约束条件知y10知y11,对偶问题无可行解，因此原问题也无最优解(无界解)。2.5已知线性规划masZ=15而+20今+5号占+5勺+弓55演+6马+为工63.+10西+药1551yl+6为+10乃20为+乃+其=5A,乃，乃之0XH0由原问题的最优解知，原问题约束的松弛变量不等于零(h),XI、X3不等于零,r/0则对偶问题的约束、约束为等式，又由于句知y3=0；解方程1及+5坊=15V1+为二5得到对偶问题的最优解Y=(5/2,5/2,0);w=55/2=27.52

7、. 6用对偶单纯形法求解下列线性规划(1) min7=3+4万+5为L+2心+3与之8，2xj*2xa+x310&%一之口【解】将模型化为minZ=3再+4/+5x3一金-2/-+“二一8一2%-2与-电+马=-104之0,/=1,2，,4,5对偶单纯形表：Cj34500CbXbXiX2X3X4X5b0X412310一80X52-2-10110C(j)-Z(j)3450000X40-15/211/2-33X111/201/25C0)-z(j)017/203/205X015/211/233Xi10-2112C(j)-Z(j)00111b列全为非负，最优解为x=(2,3,0);Z=18(2) nu

8、nZ=+4屯演+为24，2iV十礴M2国之口，4之0【解】将模型化为minZ-3百+4演产一工一盯+勺=T42公+无口+2=2与之0/=1,2,3,4L*3400bXbCbX1X2X3X4X30-1-110-4X4021012Cj-Zj3400X1311-104X400-121-6Cj-Zj0130X131011-2X2401-2-16Cj-Zj0051出基行系数全部非负，最小比值失效，原问题无可行解。(3)min2=2再+442.+3xa10Tx+3xj15卜卜心之【解】将模型化为minZ=2工1+4电I2xr+3xa+-24一五一2%+玉=-10一/一3后+/=-15勺之0,j=1,2,3

9、,4,5L4Cj24000bXbCbXiX2X3X4X5X302310024X40-1-2010-10X50-1-3001-15Cj-Zj24000X30101019X40-1/30012/30X241/31001/35Cj-Zj2/30004/3最优解X=(0,5);Z=20（4）minN=2+3占+5均+6升近+2三+?与+%之2，2公+/一再+3勺工一3勺OJ=1/-X【解】将模型化为minZ=2甬+3/+5马+6%或12k、-3工3一工4+工5=I-24+/弓+3演十-3巧0j=L,6Cj235600bXbCbX1X2X3X4X5X6X50-1-2-3-410-2X60-21-1301

10、-3Cj-Zj235600X231/213/22-1/201X60-5/20-5/211/21-4Cj-Zj1/201/203/20X23-11013/5-1/53/5-7/5X35101-2/5-1/5-2/58/5Cj-Zj0001/58/51/5X121-10-13/51/5-3/57/5X3501111/5-2/51/51/5Cj-Zj0001/58/51/5Xi2101-2/5-1/5-2/58/5X2301111/5-2/51/51/5Cj-Zj0001/58/51/5原问题有多重解：X=(7/5,0,1/5,);最优解X=(8/5,1/5,0);Z=19/5如果第一张表X6出基，

11、则有Cj235600bXbCbXiX2X3X4X5X6X50-1-2-3-410-2X60-21-1301-3Cj-Zj235600X500-5/2-5/2-11/21-1/2-1/2Xi21-1/21/2-3/20-1/23/2Cj-Zj024901X2301111/5-2/51/51/5Xi2101-7/5-1/5-2/58/5Cj-Zj00223/54/53/57.某工厂利用原材料甲、乙、丙生产产品A、B、C,有关资料见表2-23.表2-23每月可供原材料(Kg)ABC广品材料消耗原材料甲211200乙123500丙221600每件产品利润413(1)怎样安排生产，使利润最大.(2)若增

12、加1kg原材料甲，总利润增加多少.(3)设原材料乙的市场价格为1.2元/Kg,若要转卖原材料乙，工厂应至少叫价多少，为什么？(4)单位产品利润分别在什么范围内变化时，原生产计划不变.(5)原材料分别单独在什么范围内波动时，仍只生产A和C两种产品.(6)由于市场的变化，产品B、C的单件利润变为3元和2元，这时应如何调整生产计划.(7)工厂计划生产新产品D,每件产品D消耗原材料甲、乙、丙分别为2kg,2kg及1kg,每件产品D应获利多少时才有利于投产.【解】(1)设xX2、X3分别为产品A、B、C的月生产量，数学模型为maxZ=4x+x2+3%2Q1为+x3200玉+2马+34V500w2公+马+

13、号600百之0,为之0,均之0最优单纯形表:C(j)413000R.H.S.RatioXbCbXiX2X3X4X5X6Xi411/503/5-1/5020X3303/51-1/52/50160X60000-101400C(j)-Z(j)0-8/50-9/5-2/50Z=560最优解X=(20,0,160),Z=560。工厂应生产产品A20件，产品C160种，总利润为560元。92A一，必二一1为二0(2)由最优表可知，影子价格为55，故增加利润1.8元。(3)因为y2=0.4,所以叫价应不少于1.6元。(4)依据最优表计算得g-32,Aca-l2k3913Clel,6fca(-00,y,C3C

14、2A2(5)依据最优表计算得与酒440(-400100P-400).(6)变化后的检验数为=1,4=-2,5=0。故X2进基xi出基,得到最最优解X=(0,200,0),即只生产产品B200件，总利润为600元。C(j)432000R.H.S.RatioXbCbX1X2X3X4X5X6X1411/503/5-1/5020100X3203/51-1/52/50160800/3X60000-101400MC(j)-Z(j)010-200560X225103-10100MX33-301-210100100X60000-101400MC(j)-Z(j)-500-510X22211100200X40-3

15、01-210100X60000-101400C(j)-Z(j)-20-1-300(7)设产品D的产量为X7,单件产品利润为C7,只有当A-CsB月0时才有利于投产。,9 2、向(7/艺=超二,0 222T则当单位产品D的利润超过4.4元时才有利于投产。8.对下列线性规划作参数分析maxZ=(3+24)了1+(5-)心X1出基；科5时X4进基X2出基，用单纯形法计算。参数变化与目标值变化的关系如下 表所示。FromToFromToLeavingEnteringRange(Vector)(Vector)OBJValueOBJValueSlopeVariableVariable10527525X2X

16、425M52M830-1.52719.55X1X34-1.5-M19.5M-3目标值变化如下图所示。(p.= -1.519.5)Q1=5Z=52)3=口无27)maxZ=3x1-h54/4+z20科=0时最优解X=(4,3,0),Z=27;最优表:C(j)35000R.H.S.Basisrc（i）X1X2X3X4X5X13101004X250100.503X5000-3-110C(j)-Z(j)00-3-2.5027s=：y+y=b=+/)=矿%(+B%替换最优表的右端常数，得到下表。C(j)35000R.H.S.BasisC(i)X1X2X3X4X5X13101004+心X250100.503X5000-3-115aC(j)-Z(j)00-3-2.50科4时问题不可行，一4Wp0时最优基不变。科=4时Z=15。科0时X5出基X3进基得到下表：C(j)35000R.H.S.BasisC(i)X1X2X3X4X5X13100-1/31/34-2/3WX250101/203X300011/3-1/353C(j)-Z(j)000-3/2-10W(16时为最优解。(1=6时Z=15o科6时X1出基X4进基得到下表：C(j)35000R.H.S.BasisrC(i)X1X2X3X4X5X40-3001-1-12