清华大学《运筹学教程》课后习题答案第一章

第一章习题解答

1.1用图解法求解下列线性规划问题。并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。

清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章

1.2将下述线性规划问题化成标准形式。清华大学《运筹学教程》课后习题答案第一章

1.3对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。清华大学《运筹学教程》课后习题答案第一章x1x2x3x4x5x6是否基可行解Z(x1,x2,x3)061/3-7/6000否(x1,x2,x4)0100-700否(x1,x2,x5)03007/20是3(x1,x2,x6)7/4-400021/4否(x1,x3,x4)00-5/2800否(x1,x3,x5)001.5080是3(x1,x3,x6)10-0.5003否(x1,x4,x5)000350是0(x1,x4,x6)5/400-2015/4否(x1,x5,x6)3/400029/4是9/4(x2,x3,x6)016/3-7/6000否(x2,x4,x6)0100-700否(x2,x5,x6)03007/20是3(x3,x4,x6)00-5/2800否(x3,x5,x6)003/2080是3(x4,x5,x6)000350是0所有基可行解中最优解为X=(0,3,0,0,3.5,0)T和X=(0,0,1.5,0,8,0)T清华大学《运筹学教程》课后习题答案第一章x1x2x3x4是否基可行解Z(x1,x2)-411/200否(x1,x3)2/5011/50是43/5(x1,x4)-1/30011/6否(x2,x3)01/220是5(x2,x4)0-1/202否(x3,x4)0011是5所有基可行解中最优解为X=(0,1/2,2,0)T和X=(0,0,1,1)T清华大学《运筹学教程》课后习题答案第一章

1.4分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。

清华大学《运筹学教程》课后习题答案第一章1050009341008[5]20110500021/50[14/5]1-3/5108/512/501/5010-253/2015/14-3/1410110-1/72/700-5/14-25/140点A1点A2点所以最优解为X*=(1,3/2,0,0)T清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章l.5上题(1)中，若目标函数变为maxZ=cx1+dx2，讨论c,d的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。

最优值1)c<0d<0d=0d>0O点OA3线段A3点2)c=0d<0d>0OA1线段A3点3)c>0d<0d=0d>0A1点A1点A3点A2A3线段A2点A1A2线段A1点清华大学《运筹学教程》课后习题答案第一章

式中，1≤c1≤3,4≤c2≤6,-1≤a11≤3,2≤a12≤5,8≤b1≤12,2≤a21≤5,4≤a22≤6,10≤b2≤14,试确定目标函数最优值的下界和上界。

l.6考虑下述线性规划问题：

清华大学《运筹学教程》课后习题答案第一章

目标函数最优值的上界为：21

解：上界对应的模型如下（c,b取大，a取小）清华大学《运筹学教程》课后习题答案第一章

目标函数最优值（下界）为：6.4

解：下界对应的模型如下（c,b取小，a取大）清华大学《运筹学教程》课后习题答案第一章

l.7分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪—类解。清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章见下表。清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章方法一：大M法引入人工变量x6和x7,线性规划问题变为：清华大学《运筹学教程》课后习题答案第一章00-M4M-17M-4010214000-1346-M1001[3]3-M-M00-1-401013/240-7M/3+4/30-M5M/3+1/30-1/3105/3030-4/30-1[5/3]02-M1/3001/311-4106/59/5003-M清华大学《运筹学教程》课后习题答案第一章-M+8/501/50011[1]0010-4/50-3/5106/5-13/501/5013/5-4-M00-1-4-1/5-3/5-131-M-1/5-M+7/5-1/50001110010-1/53/50105/9-12/5-1/50012/5-40-1-M0-M由于上表中所有检验数都小于等于零(且非基变量检验数都小于0)，因此已经得到唯一最优解，最优解为：清华大学《运筹学教程》课后习题答案第一章方法二：两阶段法第一阶段：清华大学《运筹学教程》课后习题答案第一章00-147010214000-1346-11001[3]3-1-1000001013/240-7/30-15/30-1/3105/3030-4/30-1[5/3]02-11/3001/3110106/59/5003-1清华大学《运筹学教程》课后习题答案第一章-1000011[1]0010-4/50-3/5106/503/501/5013/50-M0000-1/5-3/5-1-1-M该模型最优解为X=（3/5，6/5，0，1，0，0）T，其基变量不含人工变量，说明原问题的一个基可行解为X=（3/5，6/5，0，1

）T，转入第二阶段。清华大学《运筹学教程》课后习题答案第一章01/5001[1]00100-3/5106/5-101/5013/5-400-1-43-1/50001100103/50105/9-1-1/50012/5-4由于上表中所有检验数都小于等于零(且非基变量检验数都小于0)，因此已经得到唯一最优解，最优解为：1清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章清华大学《运筹学教程》课后习题答案第一章

1.8已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表格，试求括弧中未知数a∼l值。项目X1X2X3X4X5X46(b)(c)(d)10X51-13(e)01Cj－Zja-1200X1(f)(g)2-11/20X54(h)(i)1

1/21Cj－Zj0-7(j)(k)(l)

b=2,c=4,d=-2,g=1,h=0,f=3,i=5,e=2,l=0,清华大学《运筹学教程》课后习题答案第一章

-7=-1-(c/b)*a

-7=-1-2a

a=3

j=2-(d/b)*a

j=2+3=5

k=-(1/b)*a

k=-3/2

清华大学《运筹学教程》课后习题答案第一章1.9若X(1)、X(2)均为某线性规划问题的最优解，证明在这两点连线上的所有点也是该问题的最优解。

清华大学《运筹学教程》课后习题答案第一章

1.10线性规划问题maxZ＝CX,AX＝b，X≥0，设X0为问题的最优解。若目标函数中用C*代替C后，问题的最优解变为X*，求证(C*-C)(X*-X0)≥0的可行解一定是问题的最优解，则是问题12**X*X*的可行解一定是问题的最优解，则是问题2100XX清华大学《运筹学教程》课后习题答案第一章

1.11考虑线性规划问题

模型中α，β为参数，要求：

(1)组成两个新的约束(i)’＝(i)+(ii)，(ii)’＝(ii)一2(i)，根据(i)’，(ii)’以x1,x2为基变量，列出初始单纯形表；清华大学《运筹学教程》课后习题答案第一章Cj→a21-4CBxBbx1x2x3x4ax13+3011-12x21-10-10j003-aa-4解:清华大学《运筹学教程》课后习题答案第一章

(2)在表中，假定β＝0，则α为何值时，x1,x2为问题的最优基变量；解：如果=0，则当3-a≥0且a-4≥0时，即3≤a≤4时，x1,x2为问题的最优基变量；

(3)在表中，假定α＝3，则β为何值时，x1,x2为问题的最优基。解：如果a=3，则当3+3≥0且1-≥0时，即

-1≤≤1时，x1,x2为问题的最优基变量。清华大学《运筹学教程》课后习题答案第一章

1.12线性规划问题maxZ＝CX，AX＝b，X≥0，如X*是该问题的最优解，又λ>0为某一常数，分别讨论下列情况时最优解的变化。

(1)目标函数变为maxZ＝λCX；

(2)目标函数变为maxZ＝(C+λ)X；

(3)目标函数变为maxZ＝C/λ*X，约束条件变为AX＝λb。

解:(1)最优解不变;(2)C为常数时最优解不变，否则可能发生变化。

(3)最优解变为:λX*。清华大学《运筹学教程》课后习题答案第一章

1.13某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如下表所示。饲料蛋白质(g)矿物质(g)维生素(mg)价格（元/kg）1310.50.2220.51.00.7310.20.20.446220.35180.50.80.8清华大学《运筹学教程》课后习题答案第一章

要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。(建立这个问题的线性规划模型，不求解)清华大学《运筹学教程》课后习题答案第一章

1.14某医院护士值班班次、每班工作时间及各班所需护士数如下页表格所示。班次工作时间所需护士数（人）16:0010:0060210:0014:0070314:0018:0060418:0022:0050522:002:002062:006:0030清华大学《运筹学教程》课后习题答案第一章

(1)若护士上班后连续工作8h，该医院最少需多少名护士，以满足轮班需要；解：

清华大学《运筹学教程》课后习题答案第一章

(2)若除22：00上班的护士连续工作8h外(取消第6班)，其他班次护士由医院排定上1-4班的其中两个班，则该医院又需多少名护士满足轮班需要。

解:清华大学《运筹学教程》课后习题答案第一章

1.15—艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量见后面的表格。现有3种货物待运，已知有关数据列于后面的表格。又为了航运安全，前、中、后舱的实际载重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过15％，前、后舱之间不超过10％。问该货轮应装载A，B，C各多少件运费收入才最大?试建立这个问题的线性规划模型。清华大学《运筹学教程》课后习题答案第一章商品数量（件）每件体积(m3/件)每件重量(t/件)运价（元/件）A6001081000B100056700C80075600项目前舱中舱后舱最大允许载重量（t）200030001500容积（m3）400054001500解：设xij表示第i种商品在第j舱的数量。清华大学《运筹学教程》课后习题答案第一章

1-16时代服装公司生产—款新的时装，据预测今后6个月的需求量如下表所示。每件时装用工2h和10元原材料费，售价40元。该公司1月初有4名工人，每人每月可工作200h，月薪2000元。该公司可于任何—个月初新雇工人，但每雇1人需—