No.1 线性规划 1、某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下： 产品 项目 A B C D  单位产值 (元) 168 140 1050 406  单位成本 (元) 42 28 350 140  单位纺纱用时 (h) 3 2 10 4  单位织带用时 (h) 0 0 2 0.5  工厂有供纺纱的总工时7200h，织带的总工时1200h。 (1) 列出线性规划模型，以便确定产品的数量使总利润最大； (2) 如果组织这次生产具有一次性的投入20万元，模型有什么变化？对模型的解是否有影响？（所谓一次性投入就是与产量无关的初始投资） 2、将下列线性规划化为极大化的标准形式 3、用单纯形法解下面的线性规划  No.2 两阶段法和大M法 1、用两阶段法解下面问题：  2、用大M法解下面问题，并讨论问题的解。  No.3 线性规划的对偶问题 1、写出下列线性规划问题的对偶问题： (1)  (2)  2、写出下问题的对偶问题，解对偶问题，并证明原问题无可行解 3、用对偶单纯形法求下面问题  No.4 线性规划的灵敏度分析 1、下表是一线性规划最优解的单纯形表  Cj ( 21 9 4 0 0 0  CB XB b x1 x2 x3 x4 x5 x6  21 x1 4 1 0 1/3 2/3 0 1/3  0 x5 2 0 0 (2/3 (4/3 1 1/3  9 x2 23 0 1 1/3 (1/3 0 (2/3    zj 21 9 10 11 0 1    cj ( zj 0 0 (6 (11 0 (1  原问题为max型，x4，x5为松驰变量，x6为剩余变量，回答下列问题： (1)资源1、2、3的边际值各是多少？(x4，x5是资源1、2的松驰变量，x6是资源3的剩余变量) (2)求C1, C2 和C3的灵敏度范围； (3)求(b1，(b2的灵敏度范围。 No.5 运输问题 1、分别用西北角法、最低费用法和运费差额法，求下面运输问题(见表)的初始可行解，并计算其目标函数。(可不写步骤) 2、以上题中最低费用法所得的解为初始基础可性解，用表上作业法（踏石法）求出最优解。（要求列出每一步的运费矩阵和基础可行解矩阵） 销地 产地 B1 B2 B3 B4 B5 产量  A1 6 9 4 8 5 20  A2 10 6 12 8 7 30  A3 6 5 9 20 9 40  A4 2 13 6 14 3 60  销量 25 15 35 45 30   No.6 指派问题 1、有4个工人。要指派他们分别完成4项工作。每人做各项工作所消耗的时间(h) 如下表，问如何分派工作，使总的消耗时间最少？ 消耗 工作 工人 A B C D  甲 3 3 5 3  乙 3 2 5 2  丙 1 5 1 6  丁 4 6 4 10  2、学生A、B、C、D的各门成绩如下表，现将此4名学生派去参加各门课的单项竞赛。竞赛同时举行，每人只能参加一项。若以他们的成绩为选派依据，应如何指派最有利？ 得分 课程 学生 数学 物理 化学 外语  A 89 92 68 81  B 87 88 65 78  C 95 90 85 72  D 75 78 89 96   No.7 动态规划 1、某公司有9个推销员在全国三个不同市场里推销货物，这三个市场里推销员人数与收益的关系如下表，做出各市场推销人员数的分配方案，使总收益最大。 推销员 市场 0 1 2 3 4 5 6 7 8 9  1 20 32 47 57 66 71 82 90 100 110  2 40 50 60 71 82 93 104 115 125 135  3 50 61 72 84 97 109 120 131 140 150  2、设某工厂要在一台机器上生产两种产品，机器的总运转时间为5小时。生产这两种产品的任何一件都需占用机器一小时。设两种产品的售价与产品产量成线性关系，分别为(12(x1)和(13(2x2)。这里x1和x2分别为两种产品的产量。假设两种产品的生产费用分别是4x1和3x2，问如何安排两种产品的生产量使该机器在5小时内获利最大。 No.8 最短路问题 1、求下图中v1到所有点的最短路径及其长度。(要求最短路用双线在图中标出，保留图中的标记值) 2、将右图看作无向图，写出边权邻接矩阵，用Prim算法求最大生成树，并画出该树图。 No.9 网络流问题 1、求下面网络s到t的最大流和最小截，从给定的可行流开始标号法。(要求每得到一个可行流后，即每次增广之后，重新画一个图，标上增广后的可行流，再进行标号法)  No.10 随机服务系统：输入过程 1、对一服务系统进行观察，总观察时间为102.7分钟，到达系统的累计人数为40人，顾客累计的排队等待时间为44.8分钟，顾客累计的服务时间为79.6分钟，求 系统中平均排队长度； (2)平均同时接受服务的人数。 2、某选举站对甲、乙二人进行选举，选票中只能选其中一人才有效。假设投票的人流服从泊松分布，投甲票的人的到达率为(1 =4人/小时，投乙票的人的到达率为(2 =2人/小时；再假设所有投票人的票都是有效的，而选举结果的统计是在一个与选民不见面的屋里与投票过程同时进行的。问选举开始后半小时统计结果为： (1)甲得三票，乙得1票的概率； (2)总票数为5的概率； (3)甲得全票的概率。 No.11 随机服务系统：标准服务系统 1、某自动交换台有4条外线，打外线的呼叫强度为2次/分钟，为泊松流，平均通话时长为2分钟。当4条外线全忙时，用户呼叫将遇忙音。假设用户遇忙音后立即停止呼叫。问 (1)用户拨外线遇忙的概率为多大？ (2)一小时内损失的话务量为多少？ (3)外线的利用率为多少？ (4)过负荷为100%时，外线的利用率为多少？ 2、某车间机器发生故障为一泊松流，平均4台/小时。车间只有一名维修工，平均7分钟处理一台故障。若为该维修工增加一特殊工具可使平均故障处理时间降到5分钟，但这一特殊工具的使用费用为5元/分钟。机器故障停工每台每分钟损失5元，问购置这台特殊工具是否合适？ 3、有M/M/n：(/(/FIFO(先到先服务)系统，输入业务量为(，求： 当n=1, 2 , 3时的等待概率D，和平均逗留队长Ld 的公式。 No.12 存储论 1、某工厂每年需某种原料1000kg，一次定购费为200元，定购量Q与单价k的关系为 0 ( Q < 500kg， k1 =2元/kg 500 ( Q < 1000kg， k2 =1.5元/kg 1000 ( Q, k3 =1.2元/kg 已知原料存储费也与Q有关 0 ( Q < 500kg， Cs1 =2元/kg.年 500 ( Q < 1000kg， Cs2 =1.5元/kg.年 1000kg ( Q, Cs3 =1.2元/kg.年 求最佳订货量Qm，并求该订货量下的全年总费用C(Qm)。 2、推导连续进货、允许缺货模型的最佳订货量Q0和最佳订货周期T0的公式。 附录：爱尔兰损失表 En(A) n B 0.005 0.01 0.05 0.1 0.2 0.3  1 0.005 0.010 0.053 0.111 0.250 0.429  2 0.105 0.153 0.381 0.595 1.000 1.449  3 0.349 0.455 0.899 1.271 1.930 2.633  4 0.701 0.869 1.525 2.045 2.945 3.891  5 1.132 1.361 2.218 2.881 4.010 5.189  6 1.622 1.909 2.960 3.758 5.109 6.514  7 2.157 2.501 3.738 4.666 6.230 7.857  8 2.730 3.128 4.543 5.597 7.369 9.213  9 3.333 3.783 5.370 6.546 8.522 10.579  10 3.961 4.461 6.216 7.511 9.685 11.953  11 4.610 5.160 7.076 8.487 10.857 13.333  12 5.279 5.876 7.950 9.474 12.036 14.719  13 5.964 6.607 8.835 10.470 13.222 16.109  14 6.663 7.352 9.730 11.473 14.413 17.503  15 7.376 8.108 10.633 12.484 15.608 18.899  16 8.100 8.875 11.544 13.500 16.807 20.300  17 8.834 9.652 12.461 14.522 18.010 21.702  18 9.578 10.437 13.385 15.548 19.216 23.105  19 10.331 11.230 14.315 16.579 20.424 24.510  20 11.092 12.031 15.249 17.613 21.635 25.917  21 11.860 12.838 16.189 18.651 22.848   22 12.635 13.651 17.132 19.692 24.064   23 13.416 14.470 18.080 20.737 25.281   24 14.204 15.295 19.031 21.784 26.499   25 14.997 16.125 19.985 22.833 27.720   26 15.795 16.959 20.943 23.885 28.941   27 16.598 17.797 21.904 24.939 30.164   28 17.406 18.640 22.867 25.995 31.388   29 18.218 19.487 23.833 27.053 32.614   30 19.034 20.337 24.802 28.113 33.840   31 19.854 21.191 25.773 29.174 35.067   32 20.678 22.048 26.746 30.237 36.295   33 21.505 22.909 27.721 31.301 37.524   34 22.336 23.772 28.698 32.367 38.754   35 23.169 24.638 29.677 33.434 39.985   36 24.006 25.507 30.657 34.503 41.216   37 24.846 26.378 31.640 35.572 42.448   38 25.689 27.252 32.624 36.643 43.680   39 26.534 28.129 33.609 37.715 44.913   40 27.382 29.007 34.596 38.787 46.147    习题课1 1、某工厂生产用2单位A和1单位B混合而成的成品出售，市场无限制。A和B可以在该工厂的3个车间中的任何车间生产，生产每单位的A和B在各车间消耗的工时如下表。 消耗工时 车间1 车间2 车间3  A 2 1 1.5  B 1 2 1.5  可用工时 100 120 100  试建立使成品数量最大的线性规划模型。 2、某饮料工厂按照一定的配方将A、B、C三种原料配成三种饮料出售。配方规定了这三种饮料中A和C的极限成分，具体见下表， 饮料品种 规 格 每升售价(元) 需求量  甲 (1) A≥60％，C≤20％ 6.80 1500  乙 (2) A≥15％，C≤60％ 5.70 3000  丙 (3) C≤50％ 4.50 无限制  A、B、C三种原料每月的供应量和每升的价格如下表。 供应量(升/月) 价格(元/升)  A 2000 7.00  B 2500 5.00  C 1200 4.00  饮料甲、乙、丙分别由不同比例的A、B、C调兑而成，设调兑后不同成分的体积不变，求最大收益的生产方案。 3、将下列线性规划化为标准形式  4、求上题的对偶规划。 习题课2 1．用连续型动态规划求解下题  2．求下面网络的中心和中位点（图中每条边上标的是两点间的距离）。 3．存货问题 （1）某小型超市洗发水日销售量为几何分布 px=p(1–p)x, x=0,1,2,…。缺货损失费为每瓶1元，当日售不出去经计算损失0.1元，若p=0.5，问最佳日进货量为多少？ （2）某小型超市食用油日销售量为负指数分布，日均销售量统计值为100公斤，当a=1, b=0.25，求最佳日进货量。 （3）若食用油日销售量为正态分布，均值为100，方差49，a, b同上，求最佳日进货量。 标准正态分布表： Z ((Z) Z ((Z) Z ((Z)  0.00 0.500000 0.95 0.828944 1.70 0.955434  0.50 0.691463 1.00 0.841345 1.80 0.964070  0.60 0.725747 1.10 0.864334 1.90 0.971283  0.70 0.758036 1.20 0.884930 2.00 0.977250  0.75 0.773373 1.30 0.903200 2.25 0.987776  0.80 0.788145 1.40 0.919243 2.50 0.993790  0.85 0.802338 1.50 0.933193 2.75 0.997020  0.90 0.815940 1.60 0.945201 3.00 0.998650