(运筹学作业.docVIP

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 随机服