07级工管运筹学期末习题课
一、考虑线性规划问题（P ）max 0
z CX
AX b
X ==??
≥?
（1） 若12,X X 均为（P ）的可行解，[0,1]λ∈，证明12(1)X X λλ+-也是（P ）
的可行解；
（2） 写出（P ）的对偶模型（仍用矩阵式表示）。
二、有三个线性规划：
(Ⅰ) [Min] z =CX (Ⅱ) [Min] z =C
X (Ⅲ) [Min] z =CX
约束条件AX =b 约束条件AX =b 约束条件AX =b
X
0 X
0 X
已知 X 是(Ⅰ)的最优解，X 是(Ⅱ)的最优解，X *是(Ⅲ)的最优解，Y
是(Ⅰ)的对偶问题的最优解，
试证：（1）()()'-'-≤**C C X X 0； (2) C X X Y b b ()()***-≤-。
三、已知线性规划问题
??
?
??=≥+=++++=++++++++=)5,,1(03.00)(max 2
253232221212
143132121115
43322111 j x t b x x a x a x a t b x x a x a x a st x x x c x c x t c z j 当1t ＝2t ＝0时，用单纯形法求得最终表如下：
要求：1. 确定
23222113121121321,,,,,,,,,,a a a a a a b b c c c 的值；
2. 当2t ＝0时，1t 在什么范围内变化上述最优解不变；
1x 2x 3x 4x 5x 3
x
5/2
0 1/2 1 1/2 0 1x 5/2 1 -1/2 0 -1/6 1/3 j j z c -
-4
-4
-2
3. 当1t ＝0时，2t 在什么范围内变化上述最优基不变。
四、某公司准备以甲、乙、丙三种原料生产A 、B 、C 、D 四种型号的产品，每一单位产品对各原料的消耗系数、价格系数及原料成本等已知条件如下表：
1．为解决“在现有原料量限制下，如何安排A 、B 、C 、D 四种产品的产量，使总利润（这里利润简化为销售收入与原料成本之差）最大”这一问题，可建立一线性规划模型，令x 1、x 2、x 3、x 4依次表示各型号产品的计划产量，试列出这个模型，并记该模型为模型1；
2．利用一解线性规划的程序解上述问题（模型1），得到的部分结果如下：
OBJECTIVE FUNCTION VALUE
1)
VARIABLE VALUE REDUCED COST X1 X2 X3 X4
ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4)
RANGES IN WHICH THE BASIS IS UNCHANGED
RIGHTHAND SIDE RANGES
ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE
2 3 4
根据以上计算结果，分析并回答以下问题：
（1）最优生产方案和最大总利润是什么按此方案生产，现有的原料是否还有剩余哪一种有剩余余多少
（2）如果市场上甲原料的价格为（百元/公斤），那么从市场上购得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．写出此问题的对偶规划模型，并解释对偶规划模型的经济意义。 六、一复合系统的结构如下图示意，它由4个部件串联组成。第k 个部件的功能由该部件专用的元件E k 完成，为提高系统的可靠性，第k 个部件可由x k 个相同的元件E k 并联构成，若每个元件的可靠度为p k ，则第k 个部件的可靠度为k
x k k p r )1(1--=。
已知4种元件的可靠度及价格见下表：
要求设计中所用元件的总费用不超过150元，又因空间限制，第3、4个部件最多由3个元件并联，应如何设计使整个串联系统的总可靠性最大要求：
1．以x k (k =1,2,3,4)为变量，列出该问题的数学规划模型。
2．若用动态规划方法求解，选取状态变量s k 为安排至第k 个部件前的总可用费用，x k 为决策变量，写出以下表达式： （1）第1阶段状态集合1S ；
（2）第3阶段状态为s 3时的允许决策集合)(33s D ；
（3）状态转移方程； （4）阶段指标),(k k k x s v ；
（5）递推方程（逆序递推，含终端条件）。
3．按动态规划方法计算第3阶段状态为75时的最优指标函数f 3（75）和最优决策x *3(75)。
七、某投资者拟对A 与B 两种基金进行投资，投资期限5年。该投资的收益有两部分：一是长期的至第5年末的红利收入，年利率分别为I A =和I B =，计复利且5年间利率不变（例如，第1年初投入A 基金1元，5年后红利收入(1+5元）；二是短期的每年利息收入，两种基金在不同年份的利率i Ak 和i Bk 见下表（例如，第1年初投入A 基金1元，除5年后的红利收入外，一年后还有元的利息收入）。
该投资者第1年初投入资金50000元，以后第2至5年初每年还再投入10000元（不包括已投资的利息收入），收益计算方法相同（如第2年初投入A 基金1
元，第5年末红利收入(1+4元，同时第2至5年末还有年利息）。所有投入基金的资金（包括年利息）在第5年末之前不得支取。现投资者需决定每年初的资金（当年投入资金加已投资金的短期年利息）对基金A 和B 的分配额，以使第5年末总收入最大。
八、某汽车公司有两家汽车配件制造厂A 和B ，负责向两个服务配送中心C 和D 供应汽车配件。运送的道路网络及各路段的允许通过容量如下图所示。设配件制造厂的供应数量无限制，求向C 、D 的供应量最大的运送方案和相应的最大供应量（求解的主要过程可在图上标出）。
九、某工程所有关键工序组成的网络图如下图所示，图中弧（即关键工序）上的数字为各工序压缩工时所需的费用（单位：百元/天）。现该工程需将工期压缩一天，试求出使总压缩费用最小的压缩方案（即应在哪些工序上压缩），以
十、某施工单位提交的一项目的网络计划如下图所示，箭线下面的数字为该工作（工序）的正常工作时间（天），要求工期18天。
1．监理工程师在审查该图时发现工作D的紧前工作除B外还应有A，请在图中把这一关系正确表示出来，并指出该网络计划的关键线路（在图上用双线或色笔标出）和（计算）工期；
2．当上述网络计划尚未实施时，建设单位提出需增加工作M，它的紧前工作为A和B，紧后工作为E和G，M工作所需时间为9天。画出增加M后的网络计划，并指出此时的关键线路（在图上用双线或色笔标出）和（计算）工期；
3．增加工作M后，如工期仍要求18天，施工单位经分析后，考虑有些工作可以适当赶工，并估算出赶工1天所需增加的费用（直接费率），如下表所示（表中未列出的工作不能赶工）：
给出使工期仍为18天且增加赶工费最少的方案（要求写出每步调整的工作，调整的天数及最后方案的网络计划，并在最后方案的网络计划中标出关键线路）。
十一、某航空公司在A市到B市的航线上用波音737客机执行飞行任务。已知该机有效载客量为138人。按民用航空有关条例，旅客因有事或误机，机票可免费改签一次，也有在飞机起飞前退票的。为避免由此发生的空座损失，该航空公司决定每个航班超量售票（即每班售出票数为138+S张）。但由此会发生持票登机旅客多于座位数的情况，这种情况下，航空公司规定，对超员旅客愿改乘本公司后续航班的，机票免费（即退回原机票款）；若换乘其他航空公司航班的，按机票价的150%退款。据统计前一类旅客（改乘本公司）占超员中的80%，后一类（换乘他公司）占20%。又据该公司长期统计，每个航班旅客退票和改签发生的人数i的概率p（i）如表3所示。
表3
试确定该航空公司从A市到B市的航班每班应多售出的机票张数S，使预期的收益最大。
十二、某牙科诊所有1名牙医。统计表明牙医以平均每小时看3名病人的效率工作，平均每小时在诊所内的病人为14人。若可设病人到达的平均间隔和牙医每看1名病人的平均工作时间均服从负指数分布，（1）求病人的平均达到率；（2）如果某病人上午10：10到达，那么预计这名病人最可能何时能离开
十三、某公司近期向市场推出了一种新产品——多功能复印-打印机。该产品的多功能很受顾客欢迎，但一旦需停下来维修则要同时耽误多项工作，因此，顾客要求尽量缩短维修等待时间。
为此，公司的技术服务部在每个销售区域设置了一位技术服务代表专门负责该产品的维修服务工作。假设顾客要求维修的电话是完全随机地到达，平均每天到达3个，而当技术服务代表连续工作时，平均每天完成4项维修任务。
（1）该服务系统能否看作一个M/M/1排队系统为什么
（2）假设该系统可看作一个标准的M/M/1排队系统，求出系统的服务强度（技术服务代表的繁忙率）和顾客的平均等待（不包括维修）时间。
（3）现公司希望将顾客的平均等待时间降为不超过4
1
天，为此需将每个技术服务代表的服务区域缩小为达到率不超过多少这时每个技术服务代表的服务
强度将降为多少
十四、 某服装厂设计了一款新式女装准备推向全国，如直接大批生产与销售，主观估计成功与失败概率各为，其分别的获利为1200万元与-500万元，如果取消生产销售计划，则损失设计与准备费用40万元。为稳妥起见，可先小批试销，试销的投入需45万元，根据历史资料与专家估计，试销成功与失败的概率分别为和，又据过去情况大批生产销售为成功的例子中，试销成功的占84%，大批生产销售失败的事例中试销成果的占36%。试根据以上数据，先计算在试销成功与失败两种情况下，进行大批量生产与销售时成功与失败的各自概率，再画出决策树按EMV 准则确定最优决策。
十五、甲乙二人玩一种游戏，甲有两个球，乙有三个球，在互不知道的情况下将球分别投入A 、B 两个箱中(每人都不允许有剩余球)。设甲投入两箱中球数分别为1n 和2n ，乙投入两个箱中球数分别为1m 和2m ；若,11m n >甲赢)1(1+m ,若,22m n >甲赢)1(2+m ；若,11m n <甲输)1(1+n ，若,22m n <甲输)1(2+n ；在其它情况下双方无输赢（即值为0），试将此问题表示成一个二人零和对策，即写出甲、乙的可选策略和甲的损益矩阵（不必求解）。
十六、离某国总统选举日还剩两天，民意测验表明尚有大约10%的选民未确定态度，主要集中在S 和T 两市。
甲、乙两候
选人都认为争取这10%的选民对于选举的成功是至关重要的，各自制定三个备选策略s 1，s 2和s 3进行最后的竞选活动。s 1为两天花在S 市；s 2为两天花在T 市；s 3为S 和T 市各一天。竞选班子估计在各局势的结局下，候选人甲多得的选票数（以百万计）如下表：
1．为求解该矩阵对策问题，可先尽量将问题简化。可将上表所示的得失矩阵中去掉1列，请指出可去掉哪一列为什么
2．请列出上述去掉1列后的矩阵相应的线性规划模型，只列出其中一个人（如乙的）经变量变换（变换后的变量等于原变量除以目标值V，并设变换后的甲、乙变量向量分别为X 和Y ）简化后的模型即可。
3．用单纯形法对乙的模型（经变量变换简化后的Max型）求解，已得到其
j
请填完此表，指出该表相应的最优解和最优值，并将此还原为甲、乙的最优混合策略。