运筹学期末习题课
三、已知线性规划问题 max z = (c1 + t1 ) x1 + c 2 x 2 + c3 x3 + 0 x 4 + 0 x5 a11 x1 + a12 x 2 + a13 x3 + x 4 = b1 + 3t 2 st. a 21 x1 + a 22 x 2 + a 23 x3 + x5 = b2 + t 2 x j ≥ 0 ( j = 1, ,5) 当 t1 ＝ t 2 ＝0 时，用单纯形法求得最终表如下： x1 x3 5/2 x1 5/2 cj − zj 0 1 0 x2 1/2 -1/2 -4 x3 1 0 0 x4 1/2 -1/6 -4 x5 0 1/3 -2
根据以上计算结果，分析并回答以下问题： （1）最优生产方案和最大总利润是什么？按此方案生产，现有的原料是否 还有剩余？哪一种有剩余？余多少？ （2）如果市场上甲原料的价格为 4.5（百元/公斤） ，那么从市场上购得 1000 公斤的甲原料扩大生产是否合算（即总利润是否增加）？为什么？ （ 3） 若 D 产品的价格系数增大到 34 （百元/公斤） ， 原最优解会否发生变化？ 为什么？ （4）在原考虑的 A、B、C、D 四种型号产品基础上，如果又提出产品 E， 它对甲、乙、丙的消耗系数分别为 5、6、2，价格系数为 74（百元/公斤） ，那么 原最优方案是否要改变，为什么？ （5）若在本题已有已知条件基础上，还要考虑各产品的生产准备费用（视 为固定成本） ，其中 A 产品的生产准备费为 1000（百元） ，B 产品的生产准备费 为 800（百元） ，C 产品的生产准备费为 950（百元） ，D 产品的生产准备费为 750 （百元） ，而且由于某些原因，A、B、C 三种产品至多生产其中的两种。写出考 虑这些新增条件下（不考虑产品 E） ，使生产利润最大的生产计划模型（不解） 。 五、某化学制药厂有 m 种有害副产品，它们的数量为 bi(i=1,…,m)。按照 规定，必须经过处理，制成 n 种无害物后才能废弃。设 aij 为每制成一单位第 j （j=1,…n）种无害物可以处理掉第 i 种有害物的数量，cj 为制成一单位第 j 种 无害物的费用。 1．现欲求各无害物的产量 xj 以使总的处理费用为最小， 请写出此问题的 线性规划模型； 2．写出此问题的对偶规划模型，并解释对偶规划模型的经济意义。 六 给出线性规划问题 max z = 2 x1 + 3 x 2 + x3 1 1 1 3 x1 + 3 x 2 + 3 x3 ≤ 1 4 7 1 x1 + x 2 + x 2 ≤ 3 3 3 3 x j ≥ 0 ( j = 1,2,3) 用单纯形法求解得最终单纯形表见下表。 2 3 1 CB 基 B x1 x2 x3 2 x1 1 1 0 -1
0 x4 4
0 x5 -1
3
x2 cj − zj
2
0 0
1 0
2 -3
-1 -5
1 -1
试分析下列各种条件下最优解(基)的变化： (1)目标函数中变量x 3 的系数变为 6； (2)分别确定目标函数中变量x l 和x 2 的系数c 1 、c 2 在什么范围内变动时最优解 不变； 1 2 （3）约束条件右端项由 3 变为 3 ； 1 （4）增加一个新的变量 x6 , P6 = 1 , c6 = 7 ； 十六、 某服装厂设计了一款新式女装准备推向全国，如直接大批生产与销 售，主观估计成功与失败概率各为 0.5，其分别的获利为 1200 万元与-500 万元， 如果取消生产销售计划，则损失设计与准备费用 40 万元。为稳妥起见，可先小 批试销，试销的投入需 45 万元，根据历史资料与专家估计，试销成功与失败的 概率分别为 0.6 和 0.4，又据过去情况大批生产销售为成功的例子中，试销成功 的占 84%，大批生产销售失败的事例中试销成果的占 36%。试根据以上数据， 先计算在试销成功与失败两种情况下， 进行大批量生产与销售时成功与失败的各 自概率，再画出决策树按 EMV 准则确定最优决策。 十三、某航空公司在 A 市到 B 市的航线上用波音 737 客机执行飞行任务。 已知该机有效载客量为 138 人。按民用航空有关条例，旅客因有事或误机，机票 可免费改签一次，也有在飞机起飞前退票的。为避免由此发生的空座损失，该航 空公司决定每个航班超量售票（即每班售出票数为 138+S 张） 。但由此会发生持 票登机旅客多于座位数的情况，这种情况下，航空公司规定，对超员旅客愿改乘 本公司后续航班的，机票免费（即退回原机票款） ；若换乘其他航空公司航班的， 按机票价的 150%退款。据统计前一类旅客（改乘本公司）占超员中的 80%，后 一类（换乘他公司）占 20%。又据该公司长期统计，每个航班旅客退票和改签发 生的人数 i 的概率 p（i）如表 3 所示。
OBJECTIVE FUNCTION VALUE 1) 19923.08 VARIABLE X1 X2 X3 X4 ROW 2) VALUE 230.769226 100.000000 1238.461548 0.000000 SLACK OR SURPLUS 0.000000 REDUCED COST 0.000000 0.000000 0.000000 4.384615 DUAL PRICES 1.384615
1
40 30 5 10 60 40 6 40 80 50 7 70 D 20 C
60
A
20 50
2
B
70 40
3
4
30
十．一双代号网络计划如图，图中箭线下不带括弧的数值表示正常工作时间，括 弧内的数值表示最短工作时间，箭线上的数值表示直接费率（赶工单位时间增加 的费用） ，箭线上没有数字表示该工作不能赶工（即在现有条件下不能缩短工作 时间） 。设起始时间为 0，要求：
要求：1. 确定 c1 , c 2 , c3 , b1 , b2 , a11 , a12 , a13 , a 21 , a 22 , a 23 的值； 2. 当 t 2 ＝0 时， t1 在什么范围内变化上述最优解不变； 3. 当 t1 ＝0 时， t 2 在什么范围内变化上述最优基不变。 四、某公司准备以甲、乙、丙三种原料生产 A、B、C、D 四种型号的产品， 每一单位产品对各原料的消耗系数、价格系数及原料成本等已知条件如下表：
C4 4(3) A 4
4
E2 3(2) G7 3(2)
1
2
6
7
D9 3(2) B8 8(6)
5
F3 4(2) H9 4(3)
3
(1) 对上述网络计划进行审查时，发现少了一项工作 M，它的紧前工作为 A， 紧后工作为 G，M 工作所需时间为 5 天，且不能赶工。画出增加 M 后的网络计 划（可在原图上添加） ； (2) 在图上标出（增加 M 后）正常工作时间下的关键线路（用双线或其它色 笔）并写出以下时间参数 ①工作D的最早完成时间EF 2-5 = ②工作H的最迟开始时间LS 3-7 = ③工作E的自由时差FF 4-6 = ④工作A的总时差TF 1-2 = ⑤此时的计算工期= (3) 如果要求工期比原计划提前 2 天，并要求以尽可能小的总费用实现该工 期，哪些工作应赶工，赶工几天？ 调整后该网络计划有几条关键线路（要求具 体说明调整的过程和调整后各条关键线路） 十二、某施工单位提交的一项目的网络计划如下图所示，箭线下面的数字为 该工作（工序）的正常工作时间（天） ，要求工期 18 天。
表3 i p(i) 0.06 5 0.04 6 0.03 7 0.02 8 0.01
试确定该航空公司从 A 市到 B 市的航班每班应多售出的机票张数 S，使预期的 收益最大。 九、 某汽车公司有两家汽车配件制造厂 A 和 B， 负责向两个服务配送中心 C 和 D 供应汽车配件。运送的道路网络及各路段的允许通过容量如下图所示。设 配件制造厂的供应数量无限制，求向 C、D 的供应量最大的运送方案和相应的最 大供应量（求解的主要过程可在图上标出） 。
产品 原料 甲 乙 丙 单位产品价格 （百元/公斤） A 1 .5 4 2 45 B 2 1 3 35 C 4 2 1 40 D 3 1 2 30 原料成本 （百元/公斤） 4 5 2 原料限量 （公斤） 5500 3500 2000
1．为解决“在现有原料量限制下，如何安排A、B、C、D四种产品的产量， 使总利润（这里利润简化为销售收入与原料成本之差）最大”这一问题，可建立 一线性规划模型，令x 1 、x 2 、x 3 、x 4 依次表示各型号产品的计划产量，试列出这 个模型，并记该模型为模型 1； 2．利用一解线性规划的程序解上述问题（模型 1） ，得到的部分结果如下：
2
C 5
4
A
1
4 E6
G 8
6
3
B
3
H D 6
5
3
1．监理工程师在审查该图时发现工作 D 的紧前工作除 B 外还应有 A，请在 图中把这一关系正确表示出来，并指出该网络计划的关键线路（在图上用双线或 色笔标出）和（计算）工期； 2．当上述网络计划尚未实施时，建设单位提出需增加工作 M，它的紧前工 作为 A 和 B，紧后工作为 E 和 G，M 工作所需时间为 9 天。画出增加 M 后的网 络计划，并指出此时的关键线路（在图上用双线或色笔标出）和（计算）工期； 3．增加工作 M 后，如工期仍要求 18 天，施工单位经分析后，考虑有些工 作可以适当赶工，并估算出赶工 1 天所需增加的费用（直接费率） ，如下表所示 （表中未列出的工作不能赶工） ：
工作名称 正常时间 最短时间 直接费率 （百元／天）
A B C D E G
4 3 5 6 6 8
2 2 4 4 4 7
6 3 2 1 2 3
给出使工期仍为 18 天且增加赶工费最少的方案 （要求写出每步调整的工作， 调整的天数及最后方案的网络计划， 并在最后方案的网络计划中标出关键线路） 。