1、运筹学期末习题参考范围及简要答案1.2. B1 B1， B2 B3 B4 B4， 产量A1 50 50A2 20 10 30 60A3 30 20 0 50A4 30 20 50需求 30 20 70 30 10 50 2103. 某厂、三种产品分别经过 A、B、C 三种设备加工。已知生产单位各种产品所需的设备台时，设备的现有加工能力及每件产品的预期利润见表： 设备能力(台.h)ABC1 1 110 4 52 2 6100600300单位产品利润(元) 10 6 41)建立线性规划模型，求获利最大的产品生产计划。2)产品每件的利润到多大时才值得安排生产？如产品每件利润增加到 50/6 元，求最
2、优计划的变化。3)产品的利润在多大范围内变化时，原最优计划保持不变。4)设备 A 的能力在什么范围内变化时，最优基变量不变。5)如有一种新产品，加工一件需设备 A、B、C 的台时各为1、4、3h，预期每件为 8 元，是否值得生产。6)如合同规定该厂至少生产 10 件产品，试确定最优计划的变化。解：1）建立线性规划模型为：MaxZ=10x1+6x2+4x3x1+x2+x310010x1+4x2+5x36002x1+2x2+6x3300xj0,j=1,2,3获利最大的产品生产计划为：X*=(x1,x2,x3,x4,x5,x6)=(100/3,200/3,0,0,0,100) Z*=2200/32）
3、产品每件利润到 20/3 才值得生产。如果产品每件利润增加到 50/6 元，最优计划的变化为：X*=(x1,x2,x3,x4,x5,x6)=(175/6,275/6,25,0,0,0) Z*=7753）产品的利润在6,15变化时，原最优计划保持不变。4）设备 A 的能力在60,150变化时，最优基变量不变。5）新产品值得生产。6）最优计划的变化为：X*=(x 1,x2,x3,x4,x5,x6)=(190/6,350/6,10,0,0,60 ) Z*=706.74.试建立一个动态规划模型。某工厂购进 100 台机器，准备生产 p1 , p2 两种产品。若生产产品 p1 ，每台机器每年可收入 45
4、 万元，损坏率为 65%；若生产产品 p2 ，每台机器每年可收入 35 万元，损坏率为 35%；估计三年后将有新 的机器出现，旧的机器将全部淘汰。试问每年应如何安排生产，使在三年内收入最多？解：(1)设阶段变量 k 表示年度，因此，阶段总数 n=3。(2)状态变量 sk 表示第 k 年度初拥有的完好机床台数， 同时也是第 k1 年度末时的完好机床数量。(3)决策变量 uk，表示第 k 年度中分配于生产产品 p1 的机器台数。于是 sk uk 便为该年度中分配于生产产品 p2 的机器台数（4） 状态转移方程为（5）允许决策集合,在第 k 段为（6）目标函数。设 gk(sk,uk)为第 k 年度的
5、产量，则gk(sk,uk) = 45uk + 35(skuk) , 因此，目标函数为（7）条件最优目标函数递推方程。令 fk(sk)表示由第 k 年的状态 sk 出发，采取最优分配方案到第 3 年度结束这段时间的产品产量，根据最优化原理有以下递推关系：（8）.边界条件为第一年，第二年机器全部用于生产 P2，第三年全部用于生产 P1，可使三年收入最多为 7676.25 万元5.求解决策问题。(65.03.1 kk uss ksU03kikusgR)(maxUuf )(65.03.)(3541kkkkk usfs )(s某种子商店希望订购一批种子。据已往经验，种子的销售量可能为500，1000，1
6、500 或 2000 公斤。假定每公斤种子的订购价为 6 元，销售价为 9 元，剩余种子的处理价为每公斤 3 元。要求：（1）建立损益矩阵；（2）用悲观法决定该商店应订购的种子数。（3）建立后悔矩阵，并用后悔值法决定商店应订购的种子数。解：（1）损益矩阵如下表所示：3 分销 售订 购S1500S21000S31500S42000A1 500A2 1000A3 1500A4 20001500015003000150030001500015003000450030001500300045006000（2）悲观法：A 1 ，订购 500 公斤。2 分（3）后悔矩阵如下表所示：3 分S1 S2 S3
7、S4 最大后悔值A1 0 1500 3000 4500 4500A2 1500 0 1500 3000 3000A3 3000 1500 0 1500 3000A4 4500 3000 1500 0 4500按后悔值法商店应取决策为 A2 或 A3 ，即订购 1000 公斤或 1500 公斤。2 分6.求下列网络计划图的各时间参数并找出关键路径。解：关键线路是：工序代号工序时间最早开工时间最早完工时间最晚开工时间最晚完工时间机动时间1-2 8 0 8 0 8 01-3 7 0 7 2 9 21-4 6 0 6 5 11 62-4 3 8 11 8 11 02-5 5 8 13 9 14 13-
8、4 2 7 9 9 11 23-6 3 7 10 15 18 84-5 3 11 14 11 14 04-6 7 11 18 11 18 04-7 4 11 15 22 26 115-7 9 14 23 17 26 36-7 8 18 26 18 26 068123457563793427831 2 4 1 6 71 2 46 7 第二部分：填空与判断一、判断1. 如果一个线性规划问题有可行解，那么它必有最优解。2对偶问题的对偶问题一定是原问题。3用单纯形法求解标准形式（求最小值）的线性规划问题时，与 0j对应的变量都可以被选作换入变量。4若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。5. 度为 0 的点称为悬挂点。二、填空1.线性规划的解有唯一最优解、无穷最优解、_无界解_和无可行解四种。2.在求运费最少的调度运输问题中，如果某一非基变量的检验数为 4，则说明_ 如果在该空格中增加一个运量运费将增加 4_。3.在用逆向解法求动态规划时， 的含义是：_从第 k 个阶段到第 n 个阶段的kfs最优解_。
