[运筹学](中科大)答案解析

2+3 -5 0 -M -cj θ b XCB B M α x1 x2 x3 x4 x5 x6 2+1/2 -5/2 -1/2 1/2 0 - x1 5 θ 1 1/2 -M x6 2 0 [7/2] 1/2 -1/2 1 4/7 8+5θ-6-θ1+θ/2+ -θ/2-M/2-1 0 -z 0 /2+7M/2 /2+M/2 M/2

2+3 -5 0 -M -M cj θ b XCB B α xx1 x2 3 x4 x5 x6 2+45/6/7 1 0 -1/7 1/7 5/7 x1 θ 3 7 x3 4/7 0 1/7 -50/7-61 1/7 -1/7 -M+1/7-2/7 -M-16/7-5 0 -1/7+θ-z 0 θ/7 /7 θ/7 θ/7 .

5061时，最优解不变。 77775061当7，即时，

7777当7，即2+3 -5 0 -M -M cj θ b XCB B α xx1 x2 3 x4 x5 x6 2+45/6/7 1 0 -1/7 1/7 5/7 15/2 x1 θ 3 7 x3 4/7 0 [1/7] -50/7-61 1/7 -1/7 -M+1/7-2/7 -M-16/7-54 0 -1/7+θ-z 0 θ/7 /7 θ/7 θ/7

2+-5 3 0 -M -M cj θ b XCB B α xx1 2 x3 x4 x5 x6 2+0 -6 -1 1 -1 x1 3 θ -5 1 x2 4 0 1 7 40+61 7+-1 -M-7-θ 2 -M+12 -z 0 0 θ Tθ +θ 因此模型(3)的最优解为(3,4,0)，目标函数值为 z314

.

模型（1）的最优解为(3,29/7,0)，目标函数值为 z3145/7

T（4）变化第一个约束条件时：

cj b CB -M -M 2 -5 3 0 -M -M α x1 x2 1 1 -5+2M XB x5 x6 10+s 7 x3 -5 1 3-4M x4 -1 0 x5 1 0 0 x6 0 1 0 5+s/2 7 [2] 1 2+3M -z M

5s/27，即s4时

cj b CB 2 2 -5 3 0 -M -M α x1 x2 1/2 1/2 XB x1 5+s/2 x3 -5/2 [7/2] x4 -1/2 x5 1/2 x6 0 - 4/7-s/1 -M x6 2-s/2 0 1/2 -1/2 1 7 -6+M/8+7M/1+ -M/2-0 -z 0 2 2 M/2 1

cj b CB 2 2 -5 3 0 -M -M α x1 x2 6/7 XB x1 45/7+s/x3 0 x4 -1/7 x5 1/7 x6 5/7 1 .

7 3 x3 4/7-s/7 0 1/7 1 0 1/7 -1/7 -1/7 -M+1/7 2/7 -M-16/ -z 0 -50/7 7

此时最优解为(

变化第二个约束条件时：

cj b CB -M -M 2 -5 3 0 -M -M 45s4sT102s ,0,)，目标函数最大值为z777α x1 x2 1 1 -5+2M XB x5 x6 10 7+t x3 -5 1 3-4M x4 -1 0 x5 1 0 0 x6 0 1 0 5 7+t [2] 1 2+3M -z M

57t，即t2

cj b CB 2 2 -5 3 0 -M -M α x1 x2 1/2 1/2 XB x1 5 x3 -5/2 [7/2] x4 -1/2 x5 1/2 x6 0 - 4/7+2t/1 -M x6 2+t 0 1/2 -1/2 1 7 .

-6+M/8+7M/1+ -M/2-0 -z 0 2 2 M/2 1

cj b CB XB 45/7+5t2 2 -5 3 0 -M -M α x1 x2 6/7 1 x3 0 x4 x5 x6 x1 /7 4/7+2t/-1/7 1/7 5/7 1/7 0 1 1/7 -1/7 2/7 3 x3 7 0 -1/7 -M+1/7 -M-16/ -z 0 -50/7 7 此时最优解为(455t42tT10216t ,0,)，目标函数最大值为 z777很明显当扩大第二项约束时最有利。

.

3、已知线性规划问题：（2000,2004）

Min z2x1x22x3x1x2x34 s.. tx1x2kx36x0,x0,x无约束231***其最优解为：x15;x20;x31

（1） 写出该问题的对偶问题，并求出对偶问题的最优解； （2） 求出k的值 解：（1）

Max w4y16y2y1y22yy1 12s.. ty1ky22y1无约束，y20由zw及互补松弛性质得

**y1y224y16y212

得到y10,y22，得到k=1.

4、设有线性规划问题（2002）

Min z2x12x24x32x13x25x323xx7x3 123s.. tx14x26x35x20,x30,x1无约束试求（1）该问题的对偶问题

（2）写出该问题的标准型，并写出单纯性法求解的初始单纯型表。 解：

.

Max w2y13y25y32y13y2y323yy4y2 123s.. t5y17y26y34y10,y20,y3无约束5(y4y5)0y60y7My8My9Max w2y13y2y4y5y822y13y23yy4(yy)yy2124569s.. t6(y4y5)y745y17y2,y4,y5,y6,y70y1,y2

5、设有线性规划问题：（2002）

MaxZ2x14x2x3x4x13x2x482x1x26s..tx2x3x46xxx9123xj0,(j1,2,3,4)*

已知该问题的最优解为：X[2,2,4,0]，试根据对偶理论直接求出其对偶问题的最优解。 解：对偶问题为

TMin W8y16y26y39y4y12y2y423yyyy41234s..ty3y41yy113yi0(i1,2,3,4)

*由互补松弛性得y40，y1y31，8y16y26y316，y31

解的y10,y25/3,y31,y40

四、指派问题

1、一个公司要分派5个推销员去5个地区推销某种产品，5个推销员在各个地区推销这种

.

产品的预期利润如下表所示，问应如何分派这5个推销员才能使得公司总的利润最大。（2003，2005）

A B C D E甲15 10 12 10 12乙11 12 9 9 9 丙10 20 15 17 13丁18 17 9 9 13戊7 13 10 13 12解：引入变量xij，并令

1 当第i个推销员去第j个地区推销产品 xij0 当第i个推销员不去第j个地区推销产品 则该问题的数学模型为：

max zcijxijijxiij1,j1,2,...,51,i1,2,...,5xj

ijxij1或0该模型的目标函数可变化为

min zbijxijijxiij1,j1,2,...,51,i1,2,...,5xj

ijxij1或0其中bij20cij。 然后采用匈牙利法求解。

.

5 10 8 10 850 5 3 5 30 5 3 5 09 8 11 11 1181 0 3 3 31 0 3 3 0(bij)10 0 5 3 7010 0 5 3 710 0 5 3 4 2 3 1 1 711 2 0 0 61 2 0 0 33 7 10 7 830 4 7 4 50 4 7 4 2 3 5 3 5 ◎ 0 5 0 2 0  5 ◎ 2  1  3 3 1 0 0 0 01    ◎10 ◎ 5 3 410 0 2 0 410 ◎ 2  4 1 2 ◎  34 5 0 0 5  ◎ 6◎ 4 7 4 20 4 4 1 2◎ 4 4 1 2因此相应的解矩阵为：

0 0 1 0 0 0 0 0 0 10 1 0 0 0 0 0 0 1 01 0 0 0 0

1、 分配甲乙丙丁四个人去完成五项任务，每人完成各项任务的时间如下表所示，由于任务

数多于人数，故规定其中一人可兼完成两项任务，其余三人每人完成一项，试确定总花费时间最小的指派方案。（2001，2004）

甲 乙 丙 丁 A 35 49 44 34 B 39 48 37 52 C 41 36 38 46 D 52 30 50 33 E 47 43 42 55

.

五、非线性规划问题

1、设有如下的非线性规划问题：（2000，2004，2009）

Min f(X)(x12)2(x21)2g1(X)x2x120s.. tg2(X)2x1x20

（1） 用图解法求上述问题的最优解

（2） 简述库恩-塔克条件，并用（1）的结果说明其几何意义 解：

2(x2)f(X)12(x1)22x1g1(X)11g2(X)12(x12)2x11rr120112(x21)r1(x2x12)0r2(2x1x2)0r1,r20

.

22r1x1r2402x22r1r202 r1(x2x1)0r(2xx)0122r1,r20解得

r1r22/3,x1x21

2、 试用动态规划方法求解下面的非线性规划问题（2001，2000）

Min f(Z)xi2i110

10x16is.. ti1x0,(i1,2,...,10)i解：具体计算过程参考p207或p208

f1s122/3f22s22/4f33s2

....2/10f1010s1010*161/510*24/5

六、简答及建模问题（新的题型方向）

一 简答题

.

1. 简述对偶问题的对称性定理、弱对偶性定理、对偶定理。 对称性定理：对偶问题的对偶是原问题。

弱对偶性定理：若X是原问题的可行解，Y是对偶问题的可行解，则存在CX≦Yb。

对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数数值相等。

2. 为什么排队论中假定顾客到达服从泊松发布，而服务时间服从负指数分布？ 顾客到达服从泊松分布：

（1） 在不相重叠的时间区间内顾客到达数是相互的（顾客到达是随机的） （2） 对充分小的t，在时间区间[t,tt)内有一个顾客到达的概率与t无关，

而约与区间长t成正比；

（3） 对于充分小的t，在时间区间[t,tt)内有两个或两个以上顾客到达的概

率极小，以至于可以忽略。

这三个条件是符合实际情况的，由此推出的概率分布为泊松分布。

服务时间服从负指数分布：对一顾客的服务时间定义为在忙期相继离开系统的两顾客的间隔时间。相继到达相继离开的间隔时间与输入过程为泊松流是一致的，可以推出为且同负指数分布。

3. 概括中国邮递员问题的解决思路：

问题是：在一个有奇点的图中，要求增加一些重复边，使新图不含奇点，并且重复边的总权为最小。

.

思路：找奇点，增加重复边，确定第一个可行方案；调整方案，去掉偶数条重复边，使重复边总权下降到最小。

二 分析解答题

1. 设备更新问题（动态规划）

某车间生产过程中必须使用某台设备，每年年初，车间领导决定是购置新设备还是通过维修继续使用旧设备。若购置新设备，需支付购置费，购买单价如下表第二行所示，旧设备报废无残值；设备在使用的生命周期内每年需支付一定的维修费用，且年度维修费用随着设备使用年限的增长而增长，如下表第四行所示。请制定2011-2015年的设备更新计划，使得总费用最小。（忽略货币的时间价值）

答案：{ 1, 0, 1, 0, 0}

.

(0,56)(0,40)(1,56)(0,28)(1,43)(0,49)(1,59)(0,18)(0,48)(0,38)(1,54)(1,32)(1,47)(0,53)(1,63)(1,12)(0,53)(0,41)(1,57)(0,31)(1,46)(0,52)(1,62)(1,25)(0,55)(0,45)(1,61)(1,39)(1,54)(0,60) (1,70)

2. 报童通过订购报纸进行零售以获利。已知，报童订购报纸的单位成本为c，销售单价p，若报纸未卖出，则低价处理的单价为q。已知pcq。根据过去的售卖经验得知，报童每日卖出r份报纸的概念为P(r)。请问，为使得收益最大化，报童每天的最佳订购量Q为多少？

答案：记报童每天购进n份报纸时的平均收入为G(n)，如果这天的需求量r≤n，则他售出r份，退回n-r份；如果这天的需求量r>n，则n份将全部售出．考虑到需求量为r的概率是f(r)，所以

G(n)abrbcnrfrr0nrn1abnfr 1

问题归结为在f(r)，a，b，c已知时，求n使G(n)最大．

通常需求量r的取值和购进量n都相当大，将r视为连续变量更便于分析和

.

计算，这时概率f(r)转化为概率密度函数p(r)，(1)式变成

Gnabrbcnrprdrnabnprdr 2 0n计算

ndGabnpnbcprdrabnpnabprdr0ndn

bcprdrabprdr0nndG令0.得到dnprdrab 3 prdrbc0nn使报童日平均收入达到最大的购进量n应满足(3)式．因为p(r)dr1，所以(3)

0式又可表为

n0prdrab 4 ac根据需求量的概率密度p(r)的图形很容易从(3)式确定购进量n．在图2中用P1，P2分别表示曲线p(r)下的两块面积，则(3)式可记作

Pab1 5 P2bcP1p(r)dr因为当购进n份报纸时，

0n是需求量r不超过n的概率，即卖不完的概

P2p(r)dr是需求量r超过n的概率，率：

n即卖完的概率，所以（3）式表明，购进的份数 应该使卖不完和卖完的概率之比，恰好等

于卖出一份赚的钱a-b与退回一份赔b-c之比.显然，当报童与报社签订的合同使报童每份赚钱和赔钱之比越大时，报童购进的份数就应该越多.

.

3. 某投资公司邀请你出资一万元参加如下游戏，游戏规则如下：首先，提供给你100万元的原始资本，该游戏分为50轮。在每一轮中，盈利与亏损的可能性都为50%。若盈利，净盈利额为投资额的1.6倍；若亏损，净亏损额为投资额的全部。为保证游戏可持续进行，每轮游戏以当时总资产的一半作为投资额，请问：（1）你的期望收益大约是多少？（2）你是否愿意参加此游戏？ 答案：

设xt为第t轮的初始资金，则

xt10.5xt0.5xt*1.6*0.50.9xt

那么，游戏结束50轮时期望收益为

x51(0.9)50*1000.0052*100=0.521

不愿意

4. 机组问题建模（0-1整数规划）

某发电站负责对本地区供电，该地区的总体用电需求每天呈有规律变化，具体表现为：

0-t1时段：需求量为D1； t1-t2时段：需求量为D2； t2-24点时段：需求量为D3。

该电站有发电机组N组，第j个机组的发电能力固定且为Sj（j=1，2，……，N）。已知S1S2KSNmax{D1,D2,D3}。供电系统运行要求发电能力与用电需求相匹配，不宜超额发电，每单位超额发电将浪费成本（包括发电成本、消解成本）

.

为w。因此，电站将灵活调整各个发电机组的开关状态，以实现发电能力与需求的匹配。此外，工程师告知，对于任一机组，一旦开动，在p小时内不得关闭；而一旦关闭，在q小时内不得重新启动。

请问，如何决定各个机组在各个时点的开闭状态，以实现最小浪费。 答案：

设xit为第i个机组t时段的发电状态，则

0，关闭 xit1，开启那么

min zw*(xit*SiD1D2D3)t0i124Ns.. txit*SiD1;t0i1t2Nt1N xit*SiD2;tt1i124N xit*SiD3;tt2i1

xitxit1xie,et1,K,mintp,24, i1,K,N; xit1xit1xie,et1,K,mintq,24, i1,K,N; xit0,1, i1,K,N,t1,K,24.