《管理运筹学课后答案》由会员分享,可在线阅读,更多相关《管理运筹学课后答案(50页珍藏版)》请在金锄头文库上搜索。
1、第一章第一章1. 建立线性规划问题要具备三要素:决策变量、约束条件、目标函数。决策变量(Decision Variable)是决策问题待定的量值,取值一般为非负;约束条件(Constraint Conditions)是指决策变量取值时受到的各种资源条件的限制,保障决策方案的可行性;目标函数(Objective Function)是决策者希望实现的目标,为决策变量的线性函数表达式,有的目标要实现极大值,有的则要求极小值。2.(1)设立决策变量;(2)确定极值化的单一线性目标函数;(3)线性的约束条件:考虑到能力制约,保证能力需求量不能突破有效供给量;(4)非负约束。3.(1)唯一最优解:只有一个
2、最优点(2)多重最优解:无穷多个最优解(3)无界解:可行域无界,目标值无限增大(4)没有可行解:线性规划问题的可行域是空集无界解和没有可行解时,可能是建模时有错。4. 线性规划的标准形式为:目标函数极大化,约束条件为等式,右端常数项bi0 , 决策变量满足非负性。如果加入的这个非负变量取值为非零的话,则说明该约束限定没有约束力,对企业来说不是紧缺资源,所以称为松弛变量;剩余变量取值为非零的话,则说明“”型约束的左边取值大于右边规划值,出现剩余量。5. 可行解:满足约束条件AX =b,X0的解,称为可行解。基可行解:满足非负性约束的基解,称为基可行解。可行基:对应于基可行解的基,称为可行基。最优
3、解:使目标函数最优的可行解,称为最优解。最优基:最优解对应的基矩阵,称为最优基。6. 计算步骤:第一步,确定初始基可行解。第二步,最优性检验与解的判别。第三步,进行基变换。第四步,进行函数迭代。判断方式:唯一最优解:所有非基变量的检验数为负数,即j 0 ,但其对应的系数列向量 Pk 中,每一个元素 aik (i=1,2,3,m)均非正数,即有进基变量但找不到离基变量。无可行解:当引入人工变量,最末单纯型发表中的基变量含有非零的人工变量,即人工变量不能全出基,则无可行解。7. 单纯形法需要有一个单位矩阵作为初始基。当约束条件都是“”时,加入松弛变量就形成了初始基,但实际问题中往往出现“”或“”型
4、的约束,这就没有现成的单位矩阵。需要采用人造基的办法,无单位列向量的等式中加入人工变量,从而得到一个初始基。人工变量只有取 0 时,原来的约束条件才是它本来的意义。为保证人工变量取值为 0,令其价值系数为-M(M 为无限大的正数,这是一个惩罚项)。如果人工变量不为零,则目标函数就不能实现最优,因此必须将其逐步从基变量中替换出。对最小化问题,在目标函数中人工变量的系数取 M。8.9. 10.(1)C10,C20,且 d0(2)C1=0,C20 或 C2=0,C10 (3)C1 0,d0,a20,d/43/a2(4)C20,a1 0(5)x1为人工变量,且 C1为包含 M 的大于 0 数,d/43
5、/a2;或者 x2为人工变量,且 C2为包含 M 的大于 0 数,a10,d0。 11. 12. 设 xij为电站向某城市分配的电量,建立模型如下:13. 设 x1为产品A的产量, x2为产品B的产量,x3为副产品C的销售量, x4为副产品C的销毁量,问题模型如下:第二章1.(2)甲生产 20 件,乙生产 60 件,材料和设备 C 充分利用,设备 D 剩余 600 单位(3)甲上升到 13800 需要调整,乙下降 60 不用调整。(4)非紧缺资源设备 D 最多可以减少到 300,而紧缺资源材料最多可以增加到 300,紧缺资源设备 C 最多可以增加到 360。2.设第一次投资项目i为xi,第二次
6、投资项目i设为xi ,第三次投资项目 i设为xi 。3.设每种家具的产量为 4.设每种产品生产xi5(1)设xi为三种产品生产量通过 Lindo 计算得 x1= 33, x2= 67, x3= 0, Z = 733(2)产品丙每件的利润增加到大于6.67时才值得安排生产;如产品丙每件的利润增加到 50/6,通过Lindo计算最优生产计划为:x1=29 , x2= 46 , x3= 25 , Z = 774.9 。(3)产品甲的利润在6,15范围内变化时,原最优计划保持不变。(4)确定保持原最优基不变的q的变化范围为-4,5。(5)通过 Lindo 计算,得到 x1= 32, x2= 58, x
7、3= 10, Z = 707第三章1.原问题和对偶问题从不同的角度来分析同一个问题,前者从产品产量的角度来考察利润,后者则从形成产品本身所需要的各种资源的角度来考察利润,即利润是产品生产带来的,同时又是资源消耗带来的。对偶变量的值 yi 表示第i种资源的边际价值,称为影子价值。可以把对偶问题的解Y定义为每增加一个单位的资源引起的目标函数值的增量。2.若以产值为目标,则 yi是增加单位资源 i 对产值的贡献,称为资源的影子价格(Shadow Price)。即有“影子价格=资源成本+影子利润”。因为它并不是资源的实际价格,而是企业内部资源的配比价格,是由企业内部资源的配置状况来决定的,并不是由市场
8、来决定,所以叫影子价格。可以将资源的市场价格与影子价格进行比较,当市场价格小于影子价格时,企业可以购进相应资源,储备或者投入生产;当市场价格大于影子价格时,企业可以考虑暂不购进资源,减少不必要的损失。 3.(1)最优性定理:设,分别为原问题和对偶问题的可行解,且 C = bT,则 ,a分别为各自的最优解。(2)对偶性定理:若原问题有最优解,那么对偶问题也有最优解,而且两者的目标函数值相等。(3)互补松弛性:原问题和对偶问题的可行解 X*、 Y*为最优解的充分必要条件是,。(4)对偶问题的最优解对应于原问题最优单纯形法表中,初始基变量的检验数的负值。若 YS对应原问题决策变量 x 的检验数; Y
9、 则对应原问题松弛变量xS 的检验数。 4.表示三种资源的影子利润分别为 0.89、4.89 和 0,应优先增加设备 C 台时以及增加材料可获利更多;14.8912,所以设备 C 可以进行外协加工,200.89210,所以暂不外购材料。5. (1)求出该问题的最优解和最优值;x1= x2= x4= 0, x3= 2, x5= 6, Z = 4(2)该问题的对偶问题的最优解和最优值:y1= 2 ,y2= 0 , w = 4(3) 分别为 2、0,对产值贡献的大小;第一种资源限量由 2 变为 4,最优解不会改变。(4)代加工产品丁的价格不低于 22+03=4。46. (1)设四种产品产量为xi,i
10、= 1,2,3,4(2) 影子价格分别为 2、1.25、2.5。对比市场价格和影子价格,当市场价低于影子价格时购进。(3)原料丙可利用量在900,1100 范围内变化,原最优生产方案中生产产品的品种不变(即最优基不变)。(4)若产品 B 的价格下降了 0.5 元,生产计划不需要调整。第四章1.纯整数规划、0-1 规划、混合整数规划。2. (1)首先不考虑整数条件,求解整数规划相应的线性规划问题。若相应的线性规划问 题没有可行解,停止计算,这时原整数规划也没有可行解。(2)定界过程。对于极大化的整数规划问题,当前所有未分枝子问题中最大的目标函数 值为整数规划问题上界;在满足整数约束的子问题的解中
11、,最大的目标函数值为整数规划问 题的下界。当上下界相同时,则已得最优解;否则,转入剪枝过程。(3)剪枝过程。在下述情况下剪除这些分枝:若某一子问题相应的线性规划问题无可行解;在分枝过程中,求解某一线性规划所得到的目标函数值 Z 不优于现有下界。(4)分枝过程。当有多个待求分枝时,应先选取目标函数值最优的分枝继续进行分枝。 选取一个不符合整数条件的变量 xi作为分枝变量,若 xi的值是 bi* ,构造两个新的约束条件:xibi* 或 xibi*+1,分别并入相应的数学模型中,构成两个子问题。对任一个子问题, 转步骤(1)。 最整数解为: x1=4, x2=2, z = 3404. 解:设,tij
12、 为个人对于个任务的时间耗费矩阵,则目标函数为:约束条件为:解之得: x12= 1 , x21= 1 , x33= 1, x44= 1 ,其余均为0,z=70,即任务A由乙完成,任务B由甲完成,任务C由丙完成,任务D由丁完成。 5. 解:设在第i天应聘的雇员人数为xi。数学模型为:解得:x1=0,x2=4,x3=32, x4=10, x5=34,x6=10,x7=4, Z=94。第五章1. 解:建立目标约束。(1)装配线正常生产设生产A, B,C型号的电脑为x1, x2 , x3(台), d1 为装配线正常生产时间未利用数, d1+ 为装配线加班时间,希望装配线正常生产,避免开工不足,因此装配
13、线目标约束为(2)销售目标 优先满足老客户的需求,并根据三种电脑的纯利润分配不同的权因子,A, B,C三种型号的电脑每小时的利润是,因此,老客户的销售目标约束为 再考虑一般销售。类似上面的讨论,得到 (3)加班限制首先是限制装配线加班时间,不允许超过200h,因此得到其次装配线的加班时间尽可能少,即写出目标规划的数学模型经过Lingo计算得到x1 = 100,x2= 55,x3=80。装配线生产时间为1900h,满足装配线加班不超过200h的要求。能够满足老客户的需求,但未能达到销售目标。销售总利润为1001000+551440+802520=380800(元)。2. 解:假设三个工厂对应的生
14、产量分别为300,200,400。(1)求解原运输问题由于总生产量小于总需求量,虚设工厂4,生产量为100个单位,到各个用户间的运费单价为0。用LINGO软件求解,得到总运费是2950元,运输方案如下表所示。(2)下面按照目标的重要性的等级列出目标规划的约束和目标函数。设xij工厂i(i =1,2,3)调配给用户j( j = 1,2,3,4)的运量, cij表示从工厂i 到用户j的单位产品的运输费用,aj( j = 1,2,3,4)表示第j个用户的需求量,bi(i =1,2,3)表示第i个工厂的生产量。i)供应约束应严格满足,即ii)供应用户1的产品中,工厂3的产品不少于100个单位,即;iii)需求约束。各用户的满足率不低于80,即应尽量满足各用户的需求,即iv)新方案的总运费不超过原方案的10(原运输方案的运费为2950元),即v)工厂2到用户4的路线应尽量避免运输任务,即vi)用户1和用户3的满足率应尽量保持平衡,即vii)力求总运费最少,即目标函数为经8次运算,得到最终的计算结果,见下表。总运费