运筹学作业辅导及答案北京外国语大学运筹学作业

1、题目 150 分线性规划Max z = 5 x1 + 5 x2 + 13 x3s.t. x1 + x2 + 3 x3 2012 x1 + 4 x2 + 10 x3 90 x1, x2, x3 0的最优表为：cj-551300iCBXBbx1x2x3x4x55x220-113100x510160-2-41-z-10000-2-50分析在下列条件下，最优解分别有什么变化1) b2由90变为 70。2) c1由-5 变为-10。3) 增加一个约束条件 4 x1 + 3 x2 + 6 x3 50。(出自第三单元)答案：1) 由最优基不变的条件Max -bi/ ir?ir0 Dbr Min-bi/ ir

2、 ?ir0得-10 = -10/1 Db2b2 由 90 变为 70，超出了允许变化范围，继续计算 或者由 B-1(b +Db)=(20,-10)T 可以知道最优基发生变化，继续迭代。 最优解变为 x1 =0，x2 = 5， x3 = 5，x4 = 0，x5 = 0，最优值 z* = 90。2) c1是非基变量的系数，最优解不变的条件是： Dc1 - s1，c1由-5 -10，Dc1 = -5 0 = - s1，不影响最优解。3) 增加一个约束条件 4 x1 + 3 x2 + 6 x3 50，原最优解不满足这个约束。引入 松弛变量，得到4 x1 + 3 x2 + 6 x3 + x6 = 50填

3、入最优单纯形表， 进一步求解，得到最优解为 X=(0，10，10/3)T，最优值为 280/3。某厂生产三种型号的铝锅，已知单耗数据如下：产品资源大号中号小号可用资源量铝板（张）624400劳力（小时）486360机器（台）8410420售价（元/个）504030试制定最优生产计划使总收入最大。（出自第二单元）题目 250 分答案：解：设 x1、x2、 x3 分别表示大号、中号、小号铝锅的产量， 这样可以建立如下的数学模型。目标函数： Max 50x1 +40 x2+30 x3约束条件： s.t. 6x1 +2 x2+ 4 x3 400（铝板限制）4x1 +8 x2+ 6 x3 360（劳力限

4、制）8x1 +4 x2+10 x3 420 （机器限制）x1，x2， x3 0（非负约束）化为标准型：目标函数： Max 50x1 +40 x2+30 x3约束条件： s.t. 6x1 + 2x2+ 4 x3 + x4 = 4004x1 +8 x2+ 6 x3 + x5 = 3608x1 +4 x2+ 10 x3+ x6 = 420x1，x2， x3，x4，x5，x6 0使用单纯形法求解：得到最优解（ 40,25,0,110,0,0），最优值 3000。即应该生产大号铝锅 40 个，中号 铝锅 25个单位，小号铝锅产量为 0（不生产），最大利润为 3000 元。题目 350 分有一个工厂要确定

5、明年各季度的生产计划，通过订货了解到各季度对产品的需求 量dk分别为 4000件、3000件、 4000件和 4000件。又知，工厂生产该产品的季 度固定成本为 10万元（但如果在某季度中，该种产品 1 件也不生产，则不需支付 固定成本费），单位产品的可变成本为 50 元，由于设备的能力所限，每季度最多 只能生产 5000件。若产品销售不出，则每件每季度的存贮费为 8 元。假设本年底 无存货转入下年， 明年末也不需要留有存货， 问每季度的生产计划应如何安排 （假 设生产产量以千件为单位），才能使生产的总费用最省？（出自第五单元） 答案： 解：首先建立动态规划模型（1）阶段 k：每个季度作为一个

6、阶段， k=1,2,3,4（2）状态变量 sk：第 k 个季度初的库存量（千件）（3）决策变量 uk：第 k 个季度的生产量（千件）（4）状态转移方程： sk+1= sk+ uk - dk （需求，千件 ）（即季度末库存量 =季度初库 存量 +季度生产量 - 季度销售量或需求量）（5）阶段指标： gk （sk, uk） =生产成本 C（uk） + 库存成本 E（sk）（6）最优指标函数 fk （sk） ：第 k 个季度的状态为 sk 时从该季度至计划结束的最低 总费用（万元）（7）递推方程： fk （sk）=mingk （sk, uk）+ fk+1（sk+1）（8）终端条件： f5（s5）=0

7、 下面进行求解，采用逆序解法。（1）k=5，f5（s5）=0（2）k=4，0s44，u4=4-s4，s5=s4+u4-d4（说明：第 4季度的需求为 4千件，因此库存量不应超过 4 且显然非负，所以有 0 s44；年底不需要有库存，所以生产量 u4 = 4 - s4）(3) k=3，0s35+5-4-3=3，s4=s3+u3-d3=s3+u3-4，Max(0, 4-s3)u3 Min(5, 8-s3)(说明：前两季度总产量为 5+5=10千件，需求量为 3+4=7 千件，所以第 3季度初 最大库存量 =10-7=3 千件；在产量需求方面， 为了满足需求，至少生产 d3-u3=4 - u3， 且

8、最大产量为 5 千件，后两个季度总需求为 4+4=8 千件，产量不应该超过 8-s3。 因此有 0s33，Max(0, 4 - s3)u3Min(5, 8-s3) )4)k=2，0s2 5-4=1，s3=s2+u2-d2=s2+u2-3，Max(0, 3-s2)u2Min(5, 11-s2)（ 5）k=1， s1=0， s2=s1+u1-d1=u1-4，4u15最优解为 s1=0, u1*=5, s2=1, u2*=5, s3=3, u3*=5, s4=4，u4*=0即前 3个季度均生产 5000件，第 4 个季度不生产，最低总费用为 111.4万元题目 450 分对于以下的运输问题，若各个销

9、地少得到 1 个单位的产品，将要求得到赔偿，金 额分别为 9、12、6、12，问如何组织运输，才能使总费用最低。(建立运输模型， 用最小元素法求初始解，并求出最优解)答案：解:总产量为 99+55+110=264，总销量 44+88+88+77=297，产销不平衡且供不应求， 增加一个虚拟产地 A4，其产量为 297-264=33。由虚拟产地运往销地的费用即为赔 偿金额。因此可以建立运输模型如下 :销地产地B1B2B3B4产量A1123391590A2306182755A32421330110销量44888877297使用最小元素法求初始解B1B2B3B4产量余额A112339159988.1

10、1A23061827550/A3242133011022.0/A4912612330/销量44888877297余额1133.110/0/说明 :每次选择最小元素， 因此依次选择 3(x33) 、6(x22)、9(x41)、12(x11)、15(x14)、21(x32)、33(x12)。)得到初始解 x11=11，x12=11，x14=77，x22=55，x32=22，x33=88， x41=33，其余运量为 0，总运费为 3003。使用位势法计算各非基变量检验数，填入括号中B1B2B3B4产量位势A11233915990A2306182755-27A32421330110-12A491261233-3销量44888877297位势12331515令 u1=0，由基变量满足 ui+vj=cij ，依次得到各位势 v1=12，v2=33 ，v4=15，u4=-3 ， u2=-27，u3=-12，v3=15，再根据公式 sij=cij-ui-vj 计算各非基变量检验数。 进行调整:选负检验数中最小的 s42，那么 x42为主元，作为进基变量。以x42为起 点找一条闭回路 x42、x41、x11、x12，取偶数标号格的最小运量 11 作为调整量， 调整后运