《运筹学课后习题二.docx》由会员分享，可在线阅读，更多相关《运筹学课后习题二.docx（13页珍藏版）》请在三一文库上搜索。
1、习题二2.1 某人根据医嘱，每天需补充A、B、C三种营养，A不少于80单位，B不少于150单位, C不少于180单位.此人准备每天从六种食物中摄取这三种营养成分.已知六种食物每百克的营养成分含量及食物价格如表2-22所示.（1）试建立此人在满足健康需要的基础上花费最少的数学模型；（2）假定有一个厂商计划生产一中药丸，售给此人服用，药丸中包含有A, B, C三种营养成分.试为厂商制定一个药丸的合理价格，既使此人愿意购买，又使厂 商能获得最大利益，建立数学模型.表 2-22含量食物营养成分一二二四五六需要量A1325144081180B24930251215150C1872134100180食物单
2、价（元/100g）0.50.40.80.90.30.2【解】（1）设Xj为每天第j种食物的用量，数学模型为min Z = 0 5再 + 0 4勺 + 0 8弓 +。9心 + 0 3/ + 0 2为13 +25与 +14 心 + 4Q勒 + 8j +1% 之 8024/ + 9心 + 30% + 25a4 +12七+ 15蜂3 1501际+7+ 21码+ 34工邛+10工5 180工. 工,、后.工飞.Xj之0(2)设yi为第i种单位营养的价格，则数学模型为max w = 80必 +150乃 +180乃131yl +24乃 +18处三 0.525yl +9为 +7乃 0,414必 +30为 +
3、21 乃 0.8；40再 + 25匕+ 34为 0.98必 + 122 +10乃 10 4 a - 8xa +6药 + x4 0, x3 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乃
4、3yl + 6y广乃+川+乃之-2-2乃+ 2乃=3当+ 5%_%=6-6泗一乃+ 2%二-7对偶问题为:J1无约束；内40,Q0, 乂 40,丹之02. 3考虑线性规划nun Z =12近 +204彳+4与之4Xj + 5 町 22. +3. 7X，为之o(i)说明原问题与对偶问题都有最优解；(2)通过解对偶问题由最优表中观察出原问题的最优解;利用公式CbB”求原问题的最优解；(4)利用互补松弛条件求原问题的最优解.【解】(1)原问题的对偶问题为max vp = 4 yl 4- 2y2 + 7%+为+ 2乃W12，4凹+ 5乃+3%2。jjN0,J = L2.3(3) Cb=(7,4),45
5、351=,5254X = (7,4) 53L 51=525= (16/5,1/5)容易看出原问题和对偶问题都有可行解，如 X = (2, 1)、丫 = (1, 0, 1),由定理2.4知都有 最优解。(2)对偶问题最优单纯形表为C(j)42700R. H. S.Basisr c(i)y1y2y3y4y5y370-1/514/5-1/528/5y1417/50-3/52/5 14/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不等于零
6、知原问题第一、三个约束是紧的，解等式再 +4/ =42司 + 3x2=7得到原问题的最优解为X=(16/5 , 1/5)。2. 4证明下列线性规划问题无最优解min Z = xL - 2x2 - 2x32金 +马-= 3 2，旃NO,为无约束证明：首先看到该问题存在可行解，向如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西 + 药 15
7、51yl+ 6为 +10乃 20 为+乃+其=5A,乃，乃之0X H 0由原问题的最优解知，原问题约束的松弛变量不等于零(h ),XI、X3不等于零,r /0则对偶问题的约束、约束为等式，又由于句知y3=0；解方程1及+5坊=15V1 +为二 5得到对偶问题的最优解 Y=(5/2,5/2,0) ; w= 55/2 = 27.52. 6用对偶单纯形法求解下列线性规划(1) min 7 = 3 + 4 万 + 5 为L+2心+ 3与之8，2xj * 2xa + x3 10&%一之口【解】将模型化为min Z = 3 再 +4/ +5x3一金-2/ -+ “二 一8一2%-2与-电+马=-104之
8、0,/= 1,2，,4,5对偶单纯形表：Cj34500CbXbXiX2X3X4X5b0X412310一 80X5 2-2-10110C(j)-Z(j)3450000X40-1 5/211/2-33X111/201/25C0)-z(j)017/203/205X015/211/233Xi10-2112C(j)-Z(j)00111b列全为非负，最优解为x=(2, 3,0); Z = 18(2) nun Z =+ 4屯演+为2 4，2iV十礴 M 2 国之口，4之0【解】将模型化为min Z - 3百 +4演产一工一盯+勺=T42公+无口+2 = 2与之 0/ = 1,2,3,4L *3400bXbC
9、bX1X2X3X4X30-1-110-4X4021012Cj-Zj3400X1311-104X400-121-6Cj-Zj0130X131011-2X2401-2-16Cj-Zj0051出基行系数全部非负，最小比值失效，原问题无可行解。(3) min 2 = 2 再 +442. +3xa 10Tx + 3xj 15卜卜心之【解】将模型化为minZ = 2工1 + 4电I 2xr +3xa + - 24一五一 2%+玉=-10一/ 一 3后 +/ =-15勺之0,j = 1,2,3,4,5L 4Cj24000bXbCbXiX2X3X4X5X302310024X40-1-2010-10X50-1-
10、3001-15Cj -Zj24000X30101019X40-1/3001 2/30X241/31001/35Cj-Zj2/30004/3最优解 X=(0, 5); Z=20（4）min N = 2+3占 + 5均+6升近+ 2三+?与 +%之2，2公+ /一再 +3勺 工一3勺OJ = 1/- X【解】将模型化为min Z = 2甬 + 3 / +5马 + 6%或12k、- 3工3一工4 +工5 =I -24 +/ 弓 +3演十 - -3 巧 0j = L,6Cj235600bXbCbX1X2X3X4X5X6X50-1-2-3-410-2X60-21-1301-3Cj-Zj235600X23
11、1/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出基，则有Cj235600
12、bXbCbXiX2X3X4X5X6X50-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)若增加1kg原材料甲，
13、总利润增加多少.(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 为 +x3 200玉+2马+ 34V500w2公
14、+马+号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 元。92 A一，必二 一1为 二 0(2)由最优表可知，影子价格为55，故增加利润1.8元。(3)因为y2=0.4 ,所以叫价应不少于 1.6元。(4)依据最优表计算得g-3 2, Aca -l2k3 91
15、3Cl el,6f ca (-00, y, C3C2A2(5)依据最优表计算得与酒 4400, -400 100P -400).(6)变化后的检验数为=1, 4=-2, 5=0。故X2进基xi出基,得到最最优解 X=(0,200,0),即只生产产品B 200件，总利润为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-101400M
16、C(j)-Z(j)-500-510X22211100200X40-301-210100X60000-101400C(j)-Z(j)-20-1-300(7)设产品D的产量为X7,单件产品利润为 C7,只有当A -CsB月0时才有利于投产。,9 2、向(7/艺=超二,0 222T则当单位产品D的利润超过4.4元时才有利于投产。8.对下列线性规划作参数分析max Z = (3+24)了1 +(5-)心X1出基；科5时X4进基X2出基，用单纯形法计算。参数变化与目标值变化的关系如下 表所示。FromToFromToLeavingEnteringRange(Vector)(Vector)OBJValue
17、OBJ ValueSlopeVariableVariable10527525X2X425M52M830-1.52719.55X1X34-1.5-M19.5M-3目标值变化如下图所示。(p.= -1.519.5)Q1=5Z=52)3=口无27)max Z = 3x1-h 54/ 4 + z2 0科=0时最优解X=(4,3,0) , Z = 27;最优表:C(j)35000R. H. S.Basisr c（i）X1X2X3X4X5X13101004X250100.503X5000-3-110C(j)-Z(j)00-3-2.5027s=：y+y =b =+/)=矿%(+ B%替换最优表的右端常数，得
18、到下表。C(j)35000R.H.S.BasisC(i)X1X2X3X4X5X13101004 +心X250100.503X5000-3-115 aC(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/3 WX250101/203X300011/3-1/35 3C(j)-Z(j)000-3/2-10W (1 6时为最优解。(1 = 6时Z = 15 o 科6时X1出基X4进基得到下表：C(j)35000R.H.S.B
19、asisr C(i)X1X2X3X4X5X40-3001-1-12+2 科X253/21001/29-心X30101004+ iC(j)-Z(j)科=9时最优解X=(0, 0, 13, 6, 0), Z=0;科9时无可行解。 综合分析如下表所示。FromToFromToLeavingEnteringRange(Vector) (Vector)OBJ ValueOBJ ValueSlopeVariableVariable10027273X5X32062715-2X1X2369150-5X249InfinityInfeasible50-427153X16-4-Infinit yInfeasible目标值变化如下图所示。