清华大学《运筹学教程》胡运权主编课后习题答案(第一章)

第一章习题解答,1.1用图解法求解下列线性规划问题。并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。,1.2将下述线性规划问题化成标准形式。,1.3对下述线性规划问题找出所有基解，指出哪些是基可行解，并确定最优解。,所有基可行解中最优解为X=(0,3,0,0,3.5,0)T和X=(0,0,1.5,0,8,0)T,所有基可行解中最优解为X=(0,1/2,2,0)T和X=(0,0,1,1)T,1.4分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。,0点,A1点,A2点,所以最优解为X*=(1,3/2,0,0)T,l.5上题(1)中，若目标函数变为maxZ=cx1+dx2，讨论c,d的值如何变化，使该问题可行域的每个顶点依次使目标函数达到最优。,式中，1c13,4c26,-1a113,2a125,8b112,2a215,4a226,10b214,试确定目标函数最优值的下界和上界。,l.6考虑下述线性规划问题：,目标函数最优值的上界为：21,解：上界对应的模型如下（c,b取大，a取小）,目标函数最优值（下界）为：6.4,解：下界对应的模型如下（c,b取小，a取大）,l.7分别用单纯形法中的大M法和两阶段法求解下列线性规划问题，并指出属哪类解。,见下表。,方法一：大M法引入人工变量x6和x7,线性规划问题变为：,0,0,-M,4M-1,7M-4,0,1,0,2,1,4,0,0,0,-1,3,4,6,-M,1,0,0,1,3,3,-M,-M,0,0,-1,-4,0,1,0,1,3/2,4,0,-7M/3+4/3,0,-M,5M/3+1/3,0,-1/3,1,0,5/3,0,3,0,-4/3,0,-1,5/3,0,2,-M,1/3,0,0,1/3,1,1,-4,1,0,6/5,9/5,0,0,3,-M,-M+8/5,0,1/5,0,0,1,1,1,0,0,1,0,-4/5,0,-3/5,1,0,6/5,-1,3/5,0,1/5,0,1,3/5,-4,-M,0,0,-1,-4,-1/5,-3/5,-1,3,1,-M-1/5,-M+7/5,-1/5,0,0,0,1,1,1,0,0,1,0,-1/5,3/5,0,1,0,5/9,-1,2/5,-1/5,0,0,1,2/5,-4,0,-1,-M,0,-M,由于上表中所有检验数都小于等于零(且非基变量检验数都小于0)，因此已经得到唯一最优解，最优解为：,方法二：两阶段法,第一阶段：,0,0,-1,4,7,0,1,0,2,1,4,0,0,0,-1,3,4,6,-1,1,0,0,1,3,3,-1,-1,0,0,0,0,0,1,0,1,3/2,4,0,-7/3,0,-1,5/3,0,-1/3,1,0,5/3,0,3,0,-4/3,0,-1,5/3,0,2,-1,1/3,0,0,1/3,1,1,0,1,0,6/5,9/5,0,0,3,-1,-1,0,0,0,0,1,1,1,0,0,1,0,-4/5,0,-3/5,1,0,6/5,0,3/5,0,1/5,0,1,3/5,0,-M,0,0,0,0,-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，转入第二阶段。,0,1/5,0,0,1,1,0,0,1,0,0,-3/5,1,0,6/5,-1,0,1/5,0,1,3/5,-4,0,0,-1,-4,3,-1/5,0,0,0,1,1,0,0,1,0,3/5,0,1,0,5/9,-1,-1/5,0,0,1,2/5,-4,由于上表中所有检验数都小于等于零(且非基变量检验数都小于0)，因此已经得到唯一最优解，最优解为：,1,1.8已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表格，试求括弧中未知数al值。,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线性规划问题maxZCX,AXb，X0，设X0为问题的最优解。若目标函数中用C*代替C后，问题的最优解变为X*，求证(C*-C)(X*-X0)0,1.11考虑线性规划问题,模型中，为参数，要求：(1)组成两个新的约束(i)(i)+(ii)，(ii)(ii)一2(i)，根据(i)，(ii)以x1,x2为基变量，列出初始单纯形表；,解:,(2)在表中，假定0，则为何值时，x1,x2为问题的最优基变量；解：如果=0，则当3-a0且a-40时，即3a4时，x1,x2为问题的最优基变量；(3)在表中，假定3，则为何值时，x1,x2为问题的最优基。解：如果a=3，则当3+30且1-0时，即-11时，x1,x2为问题的最优基变量。,1.12线性规划问题maxZCX，AXb，X0，如X*是该问题的最优解，又0为某一常数，分别讨论下列情况时最优解的变化。(1)目标函数变为maxZCX；(2)目标函数变为maxZ(C+)X；(3)目标函数变为maxZC/*X，约束条件变为AXb。,解:(1)最优解不变;(2)C为常数时最优解不变，否则可能发生变化。(3)最优解变为:X*。,1.13某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如下表所示。,要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。(建立这个问题的线性规划模型，不求解),1.14某医院护士值班班次、每班工作时间及各班所需护士数如下页表格所示。,(1)若护士上班后连续工作8h，该医院最少需多少名护士，以满足轮班需要；,解：,(2)若除22：00上班的护士连续工作8h外(取消第6班)，其他班次护士由医院排定上1-4班的其中两个班，则该医院又需多少名护士满足轮班需要。,解:,1.15艘货轮分前、中、后三个舱位，它们的容积与最大允许载重量见后面的表格。现有3种货物待运，已知有关数据列于后面的表格。又为了航运安全，前、中、后舱的实际载重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比例的偏差不超过15，前、后舱之间不超过10。问该货轮应装载A，B，C各多少件运费收入才最大?试建立这个问题的线性规划模型。,解：设xij表示第i种商品在第j舱的数量。,1-16时代服装公司生产款新的时装，据预测今后6个月的需求量如下表所示。每件时装用工2h和10元原材料费，售价40元。该公司1月初有4名工人，每人每月可工作200h，月薪2000元。该公司可于任何个月初新雇工人，但每雇1人需次性额外支出1500元，也可辞退工人，但每辞退1人需补偿1000元。如当月生产数超过需求，可留到后面月份销售，但需付库存费每件每月5元。当供不应求时，短缺数不需补上。试帮助该公司决策，如何使6个月的总利润达到最大。,解：设xi表示第i个月的工人数量，yi表示第i个月生产产品的数量。pi表示第i个月初新雇工人数量，di表示第i个月初解雇工人数量。ppi表示第i个月月末的库存量，ddi表示第i个月的短缺量。,1.17童心玩具厂下一年度的现金流(万元)如下表所示，表中负号表示该月现金流出大于流人，为此该厂需借款。借款有两种方式：一是于上一年末借一年期贷款，一次得全部贷款额，从1月底起每月还息1，于12月归还本金和最后一次利息；二是得到短期贷款，每月初获得，于月底归还，月息1.5。当该厂有多余现金时，