1、-5x20 1 5/14 -3/14 1 0 -1/7 2/73/210 0 5/14 25/1435/2T0T1T2 T0 表对应O点；T1 表对应B点；T2表对应A点，也是最优点。3. 求解： （10分） 用对偶单纯形法求解为：5 2 4 0 0x1 x2 x3 x4 x5x5-3 -1 -2 1 0-6 -3* -5 0 1-45 2 4 0 02-1* 0 -1/3 1 -1/32 1 5/3 0 -1/3-2/310/31 0 2/3 0 2/320/31 0 1/3 -1 1/30 1 1 2 -12/30 0 1/3 1 1/322/3 X*=（2/3，2，0）T；Z*=22/3
2、（注：用大M法、两阶段法求解均可）4. 写出线性规划问题： 的对偶规划。 （10分）原问题的对偶规划为：5. 有一最小化指派问题的系数矩阵如下，试求其最优解。 （10分）用匈牙利算法求解为： 变换后：再变换为： 再变换： Z*=286. 写出函数的梯度和海赛矩阵，并判断其凹凸性。（10分）的梯度矩阵为：的海赛矩阵为：这里H矩阵的各阶主子式均大于0，所以为严格凸函数。7. 某厂有4台设备，拟分给3个用户（工厂）使用，各用户利用设备提供的盈利如下表。问如何分配设备才能使总盈利最大？试建立其动态规划求解模型（可不求解）。 （10分） 用户设备台数34675根据题意，原问题用动态规划求解模型为：（1）
3、 按用户分为3阶段，K=（1，2，3，4），k=4为终了阶段；（2） xk：第k阶段初拥有待分配设备台数；x1=4，0x24，0x34，x4=0；（3） uk：第k阶段分配给第k用户的设备数，有：U1=0,1,2,3,4，U2=0,1,2,x2，U3=x3;（4） 状态转移方程：； （5） 阶段指标：见表，如： ；（6） 递推方程：（7） 边界条件：。v6v5v4v32,25,33,01,05,24,33,3v1v28. 证明下图所示v1至v6流为最大流。弧边数字为。 （10分）证明：对原流图用标号法找可扩充路有：（-，）（v1,3）标号过程进行不下去，即不存在v1-v6的可扩充路，根据可扩充
4、路定理，图示流即为最大流,maxQ=5。9.下图为求至的最小费用最大流时得到的某一流图，弧边数字为，试构造其费用有向图（流增量图）。 （10分）v1 4,4,1 v3 7,4,6 v58,5,4 3,0,2 2,0,3 5,5,2v2 v46,5,1由原流图可作出其费用有向图为： v1 -1 v3 6 v5 -6 -4 4 2 3 -2 -1 v2 1 v410. 某商行夏季订购一批西瓜，根据以往的经验，西瓜销售量可能为10000、15000、20000、25000kg。假定西瓜售价为0.35元/kg，商行支出成本为0.25元/kg。（1）建立益损矩阵； （3分）（2）分别用悲观法、乐观法、等
5、可能法和后悔值法确定西瓜订购数量。 （7分）解: （1）原问题的益损矩阵为；i Sj10000 15000 20000 25000100001500020000250001000 1000 1000 1000-250 1500 1500 1500-1500 250 2000 2000-2750 -1000 750 2500 （2）悲观准则： 乐观准则： 等可能准则： 后悔值准则：后悔值矩阵为： 则 （答题毕）2002级（B） 参考答案1. 求解线性规划问题： 的最优解。 （15分）图解过程如下：2. 写出下述线性规划的对偶规划。 （15分） ；无限制。对偶规划为 MaxZd=-7w1+14w2
6、 +3w3s.t. w1 +6w2+28w3 5 2w1-3w2+17w3 -6-w1 +w2 -4w3 =7-w1-7w2-2w3 =4w1无限制，w2，w30。3. 某一求目标函数极小值的线性规划问题，用单纯形法求解时得到某一步的单纯形表如下。问a1、a2、a3、c、d各为何值以及变量x属哪一类性质变量时，（1）现有的解为唯一最优解；（2）现有解为最优，但最优解有无穷多个；（3）存在可行解，但目标函数无界；（4）此线性规划问题无可行解。 （15分）基变量x1 x2 x3 x4 x5-1 3 1 0 0a1 4 0 1 0 a2 a3 0 0 1dcj-zj c 2 0 0 0（1）d0，c
7、0， x3，x4，x5为非人工变量； （2） d0，c=0，a1，a2中至少一个大于零，x3，x4，x5为非人工变量； （3） d0，c0，a10，a20 ，x3，x4，x5均为非人工变量； （4） d0，c0，a10，a20 ，a3=0， x5为人工变量。4. 用黄金分割法求解单变量函数寻优问题时，每迭代一次，寻优区间缩小多少倍？若要将区间缩小至原区间的10%以下，则至少要多少次迭代？ （10分）用黄金分割法求解单变量函数寻优问题时，每迭代一次，寻优区间是原区间的0.618倍。经n次迭代后，区间长度为：sn=0.618ns0。若要将区间缩小至原区间的10%以下，即sn/s00.1，则迭代次数
8、ln0.1/ln0.618=4.78。所以若要将区间缩小至原区间的10%以下，则至少要5次迭代。5. 某人外出旅行，需将五件物品装入包裹，但包裹总重量不超过13kg。物品重量及价值如表。问如何装这些物品使整个包裹价值最大？ （15分）（只建模，可不求解）物品重量（kg）价值（元）ABCDE0.5用动态规划求解时，其模型为：1. 按物品类别分为5阶段，K=（1,2,3,4,5,6），k=6为终了阶段；2. xk：k阶段的状态变量，即装第k项物品前剩余重量；有X1=13；X2=6,13；X3=1,3,6,8,13；X4=0,1,2,3,4,5,6,8,9,13；X5=0,1,2,3,4,5,6,7
9、,8,9,10,134；X6=03. uk：k阶段的决策变量，即装第k类物品的数量；U1=0,1,x1/7；U2=0,1,2,x2/5；U3=0,1,2,x3/4；U4=0,1,x4/3；U5=0,1,2,x5/14. 状态转移方程：5. 阶段指标见表， ；6. 递推方程（逆推）：7. 边界条件：6. 证明下图所示s-t流为最大流。弧边数字为（） （15分）21, 2124, 2436, 027, 030，3054，3078，5712，1260，5445，3375，4533，042，3069，57 t s 对原流图用标号法找增广链有 30，30 54，30 （+vs，12） 42，30 60，
10、54 （-，） s （+v4，12） t 75，45 69，57 33，0 45，33 （+vs，12） 78，57 （+v2，12）12，12标号过程进行不下去，即不存在s-t增广链，根据增广链定理，图示s-t流即为最大流。7. 已知某决策问题的收益矩阵D为： D= 分别用乐观法、悲观法、等可能法和后悔值法确定其最优决策。 （15分） 悲观准则： 则 解题毕。2003级（A） 1. 某昼夜服务的公交线路每天各时间所需司机和乘务人员数如下表。设司机和乘务人员分别在各时间段一开始时上班，并连续工作8小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又使司机和乘务人员配备最少？试建立求解
11、该问题的模型（可不求解）。 （10分）班次时间6:0010:0010:0014:14:0018:18:0022:22:002:2:006:所需人数6070502030设表示第班次开始上班的司机和乘务人员数（），则有： （1）用单纯形法求解； （10分）（2）写出其对偶问题； （5分）（3）求解对偶问题。 （5分）（1）用单纯形法求解：-3-2-1121*5*-1/58/5*32/51/5-3/53/52/518/55/8-1/83/81/8-1/41/4 该问题有无穷多最优解 ；Z*=12（2）其对偶问题为：（3）用对偶单纯形法求解对偶问题有：YBy1y2y3y4y5-1*-5*-9-8/5-
12、2/5-12 对偶问题最优解为 Y*=（0,1,0）T；W*=123. 线性规划的目标函数是，在用标准的单纯形法迭代过程中，得到下表，其中a，b是常数，部分数据有缺损。Cj -8x6a1/2（1）在所有的空格中填上适当的数（其中可含参数a、b）。 （5分）（2）判断在什么情况下此解为最优解？ （5分）（1）如下表-2+5a5/2（2）当 时，表中解为最优解。4. 某房地产公司计划在一住宅小区建设5栋不同类型的楼房B1、B2、B3、B4、B5。由3家建筑公司A1、A2、A3进行投标，允许每家建筑公司可承建12栋楼，通过投标得出建筑公司Ai对新楼Bj的预算费用Cij如下表，求使总费用最少的分配方案
13、。 （10分）B1B2B3B4B5A11511A21014A313设每家建筑公司承建2栋楼，虚设一栋楼B6，则有： 矩阵变换有： -1矩阵再变换有： 所以有： 或即：A1承建B1和B3楼；A2承建B2楼；A3承建B4和B5楼。总费用为38。5. 用最速下降法求 ，取初始点为。（迭代一次即可） （15分） 令 因此得 此时精度为：6. 某企业新来8名工人，拟分给3个作业班组，每个作业班组最多只分5名工人。各作业班组得到新工人后产量增加量如下表。问如何分配新工人才能使总产量增加最大？ （10分） 增加人数作业班组第一班组第二班组第三班组25172132223317.522.5（1）按作业班组分为3阶段，K=（1，2，3，4），k=4为终了阶段；（2）xk：第k阶段初拥有待分配新工人数；X1=8，X2=8,7,6,5,4
