运筹学第1章答案

1.2 工厂每月生产A、B、C三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如1－23所示． 表1－23 产品 资源 A B C 资源限量 材料(kg) 1.5 1.2 4 2500 设备(台时) 3 1.6 1.2 1400 利润(元/件) 10 14 12             根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大． 【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为 1.3 建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格及数量如表1－24所示： 表1－24 窗架所需材料规格及数量   型号A 型号B 每套窗架需要材料 长度（m） 数量(根) 长度(m) 数量(根) A1：1.7 2 B1：2.7 2 A2：1.3 3 B2：2.0 3 需要量（套） 200 150           问怎样下料使得（1）用料最少；（2）余料最少． 【解】 第一步：求下料，见下表。 方案 一 二 三 四 五 六 七 八 九 十 十一 十二 十三 十四 需要量 B1:2.7m 2 1 1 1 0 0 0 0 0 0 0 0 0 0 300 B2:2m 0 1 0 0 3 2 2 1 1 1 0 0 0 0 450 A1:1.7m 0 0 1 0 0 1 0 2 1 0 3 2 1 0 400 A2:1.3m 0 1 1 2 0 0 1 0 1 3 0 2 3 4 600 余料 0.6 0 0.3 0.7 0 0.3 0.7 0.6 1 0.1 0.9 0 0.4 0.8                                   第二步：建立线性规划数学模型 设xj（j=1,2,…，14）为第j种方案使用原材料的根数，则 （1）用料最少数学模型为 用单纯形法求解得到两个基本最优解 X(1)=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534 X(2)=( 0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534 （2）余料最少数学模型为 用单纯形法求解得到两个基本最优解 X(1)=( 0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料550根 X(2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650根 显然用料最少的方案最优。 1.4某企业需要制定1～6月份产品A的生产与销售。已知产品A每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。1～6月份产品A的单件成本与售价如表1－25所示。 表1－25 月份 1 2 3 4 5 6 产品成本(元/件) 销售价格(元/件) 300 330 320 360 360 300 350 340 350 420 410 340     （1）1～6月份产品A各生产与销售多少总利润最大，建立数学模型； （2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。 【解】设xj、yj（j＝1，2，…，6）分别为1～6月份的生产量和销售量，则数学模型为 （1） （2）目标函数不变，前6个约束右端常数800改为1000，第7～11个约束右端常数200改为0，第12个约束“≤200”改为“＝－200”。 1.5 某投资人现有下列四种投资机会, 三年内每年年初都有3万元（不计利息）可供投资： 方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20％，下一年可继续将本息投入获利； 方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50％，下一年可继续将本息投入获利，这种投资最多不超过2万元； 方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是60％，这种投资最多不超过1.5万元； 方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30％，这种投资最多不超过1万元． 投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型. 【解】是设xij为第i年投入第j项目的资金数，变量表如下   项目一 项目二 项目三 项目四 第1年 第2年 第3年 x11 x21 x31 x12 x23 x34           数学模型为 最优解X=(30000，0，66000，0，109200，0)；Z＝84720 1.6 炼油厂计划生产三种成品油，不同的成品油由半成品油混合而成，例如高级汽油可以由中石脑油、重整汽油和裂化汽油混合，辛烷值不低于94，每桶利润5元，见表1－26。 表1－26 成品油 高级汽油 一般汽油 航空煤油 一般煤油 半成品油 中石脑油 重整汽油 裂化汽油 中石脑油 重整汽油 裂化汽油 轻油、裂化油、重油、残油 轻油、裂化油、重油、残油按10:4:3:1调合而成 辛烷值 ≥94 ≥84     蒸汽压：公斤／平方厘米     ≤1   利润(元/桶) 5 4.2 3 1.5             半成品油的辛烷值、气压、及每天可供应数量见表1－27。 表1－27 半成品油 1中石脑油 2重整汽油 3裂化汽油 4轻油 5裂化油 6重油 7残油 辛烷值 80 115 105         蒸汽压：公斤／平方厘米       1.0 1.5 0.6 0.05 每天供应数量(桶) 2000 1000 1500 1200 1000 1000 800                 问炼油厂每天生产多少桶成品油利润最大，建立数学模型。 解 设xij为第i（i＝1,2,3,4）种成品油配第j(j=1,2,…,7)种半成品油的数量（桶）。 总利润： 高级汽油和一般汽油的辛烷值约束 航空煤油蒸气压约束 一般煤油比例约束 即 半成品油供应量约束 整理后得到 1.8 将下列线性规划化为形式 (1) 【解】（1）令 为松驰变量 ，则标准形式为 (2)  【解】（2）将绝对值化为两个不等式，则标准形式为 (3) 【解】方法1： 方法2：令 则标准型为 (4) 【解】令 ，线性规划模型变为 标准型为 1.9 设线性规划 取基 分别指出 对应的基变量和非基变量，求出基本解，并说明 是不是可行基． 【解】B1：x1，x3为基变量，x2，x4为非基变量,基本解为X=（15，0，20，0）T，B1是可行基。B2：x1,x4是基变量，x2,x3为非基变量，基本解X=（25，0，0，－40）T，B2不是可行基。 1.10分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点． (1) 【解】单纯形法： C(j) 1 3 0 0 b Ratio C(i) Basis　 X1 X2 X3 X4 0 X3 -2 [1] 1 0 2 2 0 X4 2 3 0 1 12 4 C(j)-Z(j) 1 3 0 0 0   3 X2 -2 1 1 0 2 M 0 X4 [8] 0 -3 1 6 0.75 C(j)-Z(j) 7 0 -3 0 6   3 X2 0 1 0.25 0.25 7/2   1 X1 1 0 -0.375 0.125 3/4   C(j)-Z(j) 0 0 -0.375 -0.875 45/4                   对应的顶点： 基可行解 可行域的顶点 X(1)=（0，0，2，12）、 X(2)=（0，2，0，6，）、 X(3)=（ 、 （0，0） （0，2）     最优解 (2) 【解】 单纯形法： C(j) -3 -5 0 0 0 b Ratio Basis　 C(i)　 X1 X2 X3 X4 X5 X3 0 1 2 1 0 0 6 3 X4 0 1 [4] 0 1 0 10 2.5 X5 0 1 1 0 0 1 4 4 C(j)-Z(j) -3 -5 0 0 0 0 X3 0 [0.5] 0 1 -0.5 0 1 2 X2 -5 0.25 1 0 0.25 0 2.5 10 X5 0 0.75 0 0 -0.25 1 1.5 2 C(j)-Z(j) -1.75 0 0 1.25 0 -12.5 X1 -3 1 0 2 -1 0 2 M X2 -5 0 1 -0.5 0.5 0 2 4 X5 0 0 0 -1.5 [0.5] 1 0 0 C(j)-Z(j) 0 0 3.5 -0.5 0 -16 X1 -3 1 0 -1 0 2 2 X2 -5 0 1 1 0 -1 2 X4 0 0 0 -3 1 2 0 C(j)-Z(j) 0 0 2 0 1 -16                   对应的顶点： 基可行解 可行域的顶点 X(1)=（0，0，6，10，4）、 X(2)=（0，2.5，1，0，1.5，）、 X(3)=（2，2，0，0，0） X(4)=（2，2，0，0，0） （0，0） （0，2.5） (2，2) （2，2）     最优解：X=（2，2，0，0，0）；最优值Z＝－16 该题是退化基本可行解，5个基本可行解对应4个极点。 1.11用单纯形法求解下列线性规划 (1) 【解】单纯形表： C(j) 3 4 1 0 0 R. H. S. Ratio　 Basis C(i) X1 X2 X3 X4 X5 X4 0 2 [3] 1 1 0 1 1/3 X5 0 1 2 2 0 1 3 3/2 C(j)-Z(j) 3 4 1 0 0 0   X2 4 [2/3] 1 1/3 1/3 0 1/3 1/2 X5 0 -1/3 0 4/3 -2/3 1 7/3 M C(j)-Z(j) 1/3 0 -1/3 -4/3 0 -4/3   X1 3 1 3/2 1/2 1/2 0 1/2   X5 0 0 1/2 3/2 -1/2 1 5/2   C(j)-Z(j) 0 -1/2 -1/2 -3/2 0 -3/2                     最优解：X=（1/2，0，0，0，5/2）；最优值Z＝3/2 (2)    【解】单纯形表： C(j) 2 1 -3 5 0 0 0 R. H. S. Ratio Basis C(i) X1 X2 X3 X4 X5 X6 X7 X5 0 1 5 3 -7 1 0 0 30 M X6 0 3 -1 [1] 1 0 1 0 10 10 X7 0 2 -6 -1 [4] 0 0 1 20 5 C(j)-Z(j) 2 1 -3 5 0 0 0     X5 0 9/2 -11/2 5/4 0 1 0 7/4 65 M X6 0 5/2 [1/2] 5/4 0 0 1 -1/4 5 10 X4 5 1/2 -3/2 -1/4 1 0 0 1/4 5 M C(j)-Z(j) -1/2 17/2 -7/4 0 0 0 -5/4     X5 0 32 0 15 0 1 11 -1 120 M X2 1 5 1 5/2 0 0 2 -1/2 10 10 X4 5 8 0 7/2 1 0 3 -1/2 20 M C(j)-Z(j) -43 0 -23 0 0 -17 3                           因为λ7＝3>0并且ai7<0(i=1,2,3)，故原问题具有无界解，即无最优解。 (3) 【解】 C(j) 3 2 -0.125 0 0 0 R. H. S. Ratio　 Basis C(i) X1 X2 X3 X4 X5 X6 X4 0 -1 2 3 1 0 0 4 M X5 0 [4] 0 -2 0 1 0 12 3 X6 0 3 8 4 0 0 1 10 10/3 C(j)-Z(j) 3 2 -1/8 0 0 0 0   X4 0 0 2 5/2 1 1/4 0 7 3.5 X1 3 1 0 -1/2 0 1/4 0 3 M X6 0 0 [8] 11/2 0 -3/4 1 1 1/8 C(j)-Z(j) 0 2 11/8 0 -3/4 0 9   X4 0 0 0 9/8 1 7/16 -1/4 27/4 6 X1 3 1 0 -1/2 0 1/4 0 3 M X2 2 0 1 [11/16] 0 -3/32 1/8 1/8 0.181818 C(j)-Z(j) 0 0 0 0 -9/16 -1/4 37/4                       X3进基、X2出基，得到另一个基本最优解。