天大历年试题分类

一、线性规划 二、运输问题 三、多目标规划 四、动态规划 五、图论

六、网络计划技术 七、决策论 八、存储论 九、排队论 十、对策论 十一、模拟技术

一、线性规划

（一）选择填空题 （二）线性规划建模 （三）互补松弛应用 （四）灵敏度分析 （五）证明题

（一）选择填空题

1．下面给出某线性规划问题的单纯形初表和终表（Min型）： CB XB B-1b 0 x1 7 0 x4 12 0 x6 10 σ CB XB B-1b x2 x6 σj j 0 1 -3 0 2 0 x1 x2 x3 x4 x5 x6 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 x1 x2 x3 x4 x5 x6 2/5 0 1/10 0 1/5 1 3/10 0 1 0 -1/2 1

(1)初表的出基变量为 ，进基变量为 。

(2)最优基逆B*?1???

(3)填完终表。

(4)最优解X*?

(5)对偶问题最优解y*?

(6)若原问题增加一个新的非负变量，则对偶问题的最优目标值将（变大、不变、变小） 。（2007）

解：1．(1)出基变量为x4；进基变量为x3。

?2?5?1*?1 (2)B???5??1??(3) CB XB B-1b 1?0?10?30?。 ?10?1?1??2?x1 x2 x3 x4 x5 x6 1 x2 4 2/5 1 0 1/10 4/5 0 -3 x3 5 1/5 0 1 3/10 2/5 0 0 x6 11 1 0 0 -1/2 10 1 σj 1/5 0 0 4/5 12/5 0

(4) X*?(4(5) Y?((6) 变小

*511)T

450)

151．用图解法解线性规划时，以下几种情况中不可能出现的是（ ）。

A．可行域（约束集合）有界，无有限最优解（或称无解界） B．可行域（约束集合）无界，有唯一最优解

C．可行域（约束集合）是空集，无可行解

D．可行域（约束集合）有界，有多重最优解 （2006）

解：1． A

2．根据线性规划的互补松弛定理，安排生产的产品机会成本一定（ ）利润。 A． 小于 B． 等于 C． 大于 D． 大于等于 （2006）

解：2． B

1．用大M法求解Max型线形规划时，人工变量在目标函数中的系数均为____________，若最优解的_______________中含有人工变量，则原问题无解。（2005）

解：1、-M 基变量

*1. 设线性规划问题maxcxAx?bx?0有最优解x和影子价格y,则线性规划问题

??*max?2cxAx?bx?0?的最优解= ，影子价格= 。

（2004）

解：1. x* 2y*

3. 某工程公司拟从1、2、3、4四个项目中选择若干项目。若令

?1，第i个项目被选中xi??，i?1，??4

?0，第i个项目未选中请用xi的线性表达式表示下列要求：（1）若项目2被选中，则项目4不能被选中： （2）只有项目1被选中，项目3才能被选中： 。（2004）

解：3. x2?x4?1,x1?x3?0

一、简答（18%）

（1）请简述影子价格的定义。

（2）在使用单纯型表求解型线性规划时，资源的影子价格在单纯型表的什么位置上？ （3）写出影子价格的数学表达式并用其定义加以验证 （4）试述运输问题中检验数的经济意义（2003）

解：一、简答

⑴当各资源增加一单位时引起的总收入的增量，影子价格大于零的资源一定没有剩余，有剩余一定为零。

⑵松弛变量检验数的负值，对偶问题的最优解。 ⑶CBB-1

B是原问题{maxz=CX∣AX≤b,X≥0}最优基 **Z= CBB-1b=Yb ****

Z=y1b1+y2b2?ymbm

?z*=y3* ?b⑷表明增加一个单位的运量会引起总运输费用的变化

1． 线性规划原问题中约束的个数与其对偶问题中的 变量 个数相等。若原问题第j个约束

为等式，则对偶问题第j个 变量 自由。（2002） 解：

2． 设线性规划问题max:{cx|Ax≤bx≥0}有最优解，且最优解值z>0；如果c和b分别被v>1

所乘，则改变后的问题 也有 （也有、不一定有）最优解；若有最优解，其最优解 大于 (大于、小于、等于)z。（2002）

1．下列数学模型中 a 是线性规划模型。(2001)

(a)maxZ?4x1?2x2?3x3

?7x1?3x2?6x3?150?s.t.?4x1?4x2?5x3?120 ?x,x,x?0?123 解：

?7x?6x2?8x35x1?9x2?2x3?(b)maxZ?min?1?

43???5x1?5x2?3x3?300?s.t.?6x1?9x2?8x3?500 ?x,x,x?0?123

2．下列图形（阴影部分）中 b 是凸集。(2001)

（a） （b） （c） 解：

3．标准形式的线性规划问题，其可行解 b 是基本可行解，最优解 a 是可行解，最优解 a 能在可行域的某顶点达到。(2001)

（a）一定 （b）不一定 （c）一定不 解：

4．目标函数取极小（min Z）的线性规划问题可以转化为目标函数取极大 b 的线性规划问题求解，原问题的目标函数值等于 c 。(2001)

（a）max Z （b）max（-Z） （c）-max（-Z） （d）-max Z （a）最小元素法 （b）比回路法 1. 线性规划单纯形算法的基本步骤是：（1） （2） (3) 每次迭代保持解的 ，改善解值的 。对偶单纯形法每次迭代保持解的 ，改善解值的 。（2000）

解：确定一个初始基可行解；检验一个基可行解是否为最优解；寻找一个更好基可行解；可行性；最优性。

2. 设有线性规划问题?min?f?CX,X?R??X|AX?b,X?0?，有一可行基B（为A中的前m列），记相应基变量为X?，价格系数为CB，相应于非基变量为XN，价格系数为CN，则相应于B的基本可行解为X= ；用非基变量来表示基变量的表达式为XB= ；用非基变量表示目标函数的表达式为f= ，B为最优基的条件是 。（2000）

?B?1b??1?1?1?1?1解：??,Bb?BNXN,CBBb?(CN?CBBN)XN,CN?CBBN?0

?0?

3. 线性规划（Min型）问题有多重最优解时，其最优单纯形表上的特征为： （2000）

解：所有检验数?j?0,而某一个非基变量xk检验数?j?0. 6. 某足球队要从1，2，3，4，5号五名队员中挑选若干名上场。令

?1第i号上场 xi??1，2，3，4，5?0第i号不上场，i＝请用xi的线性表达式表示下列要求：（1）从1，2，3中至多选2名： （2）如果

2号和3号都上场，则5号不上场： （3）只有4号上场,1号才上场：(2000) 解：x1?x2?x3?2,x4?x5?0,x1?x4?1.

1．某工程公司拟从四个项目中选择若干项目，若令

?1,第i个项目被选中xi??i?1,2,3,4.

?0,第i个项目末被选中请用xi的线性表达式表示下列要求：

（1）从1，2，3项目中至少选择一个： ，

（2）只有项目2被选中，项目4才能被选中 。（1999）

解：1、x1+x2+x3≥1

x2≥x4

2．考虑线形规划问题

maxZ?5x1?12x2?4x3?x1?2x2?x3?5?s..t?2x1?x2?3x3?2?x,x,x?0?123

用单纯型法求解，得其终表如下： Cj 5 12 4 0 -M CB XB B-1b x1 x2 x3 x4 x5 12 x2 8/5 0 1 -1/5 2/5 -1/5 5 x1 9/5 1 0 7/5 1/5 2/5 2?j 0 0 -3/5 -29/5 -M+ 5其中x4位松弛变量，x5为人工变量。 （1）上述模型的对偶模型为 ， （2）对偶模型的最优解为 ，

（3）当两种资源分别单独增加一个单位时，目标函数值分别增加 和 ，

?（4）最优基的逆矩阵B?1????? ?（5）如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？（1999）

解：2．（1）

minW?5y1?2y2?y1?2y2?5?2y?y?12 ?12??y1?3y2?4??y1?0,y2无符号限制292（2）Y*=（，-）

55292（3），-

55?2?5（4）??1??5

1???5? 2??5?（5）变小

1．下面给出某线形规划的单纯形初表（表1）与某一中间表（表2）（Min型）：

表1 0 1 -3 0 2 0 CB XB B-1b x1 x2 x3 x4 x5 x6 0 x1 7 0 x4 12 0 x6 10 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 ?j

x2 x6 表2 2/5 0 1/10 4/5 1/5 1 3/10 2/5 1 0 -1/2 10 ?j 1) 初表的出基变量为__________，进基变量为_________。

2) 填完表2，该表是否是终表?_________。若是，最优值Z?________ 3) 此线形规划对偶问题的最优解Y?_______

**

(1998)

解：1.下面给出某线形规划的单纯形初表（表1）与某一中间表（表2）（Min型）：

表1 0 1 -3 0 2 0 -1CB XB Bb x1 x2 x3 x4 x5 x6 0 x1 7 0 x4 12 0 x6 10 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 0 1 -3 0 2 0 表2 2/5 1 0 1/10 4/5 0 1/5 0 1 3/10 2/5 0 ?j ?

1 x2 4 -3 x3 5 0 x6 11 1 0 0 -1/2 10 1 1/5 0 0 4/5 12/5 0 ?j

4) 初表的出基变量为_____x4_____，进基变量为___x3______。

5) 填完表2，该表是否是终表?____是_____。若是，最优值Z?__-11______

*?14?此线形规划对偶问题的最优解Y*???,?,0?

?55? 解： 解： 解： 解：

解： 解：

（二）线性规划建模 二（20分）、某化学制药厂有m种有害副产品，它们的数量为bi（i=1，?，m）。按照规定，必须经过处理，制成n种无害物后才能废弃。设aij为每制成一单位第j（j=1，?，n）种无害物可以处理掉第i种有害物的数量，cj为制成一单位第j种无害物的费用。

1． 现欲求各无害物的产量xj以使总的处理费用为最小，请写出此问题的线性规划模型； 2． 写出此问题的对偶规划模型，并解释对偶规划模型的经济意义。（2007） 解：1．

minz??cjxjj?1n?a11x1?a12x2???a1nxn?b1?ax?ax???ax?b2112222nn2 ??s..t????ax?ax???ax?bmnnm?m11m22??x1,x2,?，xn?02．

maxz??yibii?1m?a11y1?a21y2???am1ym?c1?ay?ay???ay?c121222m2m2 ??s..t????ay?ay???ay?cmnmn?1n12n2??y1,y2,?，ym?0经济意义：yi为第i种有害副产品不经处理直接废弃的费用。

二（10%）、某大型企业每年需要进行多种类型的员工培训。假设共有需要培训的需求（如技术类、管理类）为6种，每种需求的最低培训人数为ai，i=1,?,6, 可供选择的培训方式（如内部自行培训、外部与高校合作培训）有5种，每种的最高培训人数为bj, j=1,?,5。又设若选择了第1种培训方式，则第3种培训方式也要选择。记xij为第i种需求由第j方式培训的人员数量，z为培训总费用。费用的构成包括固定费用和可变费用，第j种方式的固定费用为hj（与人数无关），

与人数xij相应的可变费用为cij（表示第j方式培训第i种需求类型的单位费用）。如果以成本费用为优化目标，请建立该培训问题的结构优化模型（不解）。（2006）

解：二、

?1设xij为第i种需求由第j种方式培训的人员数量，yj???0minz??yjhj???cijxij

j?1i?1j?1565选择j培训方式否则

6??x?bjyj(i?1,2,?,5)?i?1ij?5??xij?ai(i?1,2,?,6)?j?1? ?y1?y3?0?x?0(i?1,?6,j?1,2,?,5)?ij?yj?0或1(j?1,2,?,5)???1.某厂使用A、B两种原料生产甲、乙、丙三种产品，有关数据见下表： 甲 乙 丙 A B 生产成本（万元/吨） 销售价格（万元/吨） 1.0 0.5 0.4 0.6 0.6 0.5 8 5 18 30 20 35 原料成本（万元/吨） 5 7 原料可用数量（吨） 350 460 （1）请写出使总销售利润最大的线性规划模型（其中甲、乙、丙产产量分别记为x1,x2,x3,约束依A,B原料次序）:

(2)写出此问题的对偶规划模型（2003）

解：⒈①maxz=30x1+20x2+35x3-8x1-5x2-18x3-5(x1+0.4x2+0.6x3)-7(0.5x1+0.6x2+0.5x3) 目标函数maxz=13.5x1+8.8x2+10.5x3 约束条件 x1+0.4x2+0.6x3≤350 0.5x1+0.6x2+0.5x3≤460 x1≥0,x2≥0,x3≥0

②对偶规划模型

目标函数 minw=350y1+460y2 约束条件y1+0.5y2≥13.5 0.4y1+0.6y2≥8.8 0.6y1+0.5y2≥10.5 y1≥0,y2≥0 三、（10%）某服装厂制造大、中、小三种尺寸的防寒服，所用资源有尼龙绸、尼龙棉、劳动力和缝纫设备。缝制一件防寒服所需各种资源的数量如表（单位已适当给定）。不考虑固定

费用，则每种防寒服售出一件所得利润分别为10、12、13元，可用资源分别为：尼龙绸1500米，尼龙棉1000米，劳动力4000，设备3000小时。此外，每种防寒服不管缝制多少件，只要做都要支付一定的固定费用：小号为100元，中号为150元，大号为200元。现欲制定一生产计划使获得的利润为最大，请写出其数学模型（不解）。(2002) 型号 资源 尼龙绸 尼龙棉 劳动力 缝纫设备 小 1．6 1．3 4 2．8 中 1．8 1．5 4．5 3．8 大 1．9 1．6 5 4．2

解：三、解：设三种防寒服分别生产x1,x2,x3件。z表示获得的利润,y1,y2,y3分别表示0-1变量，yi=1表示做第xi种防寒服（i=1,2,3）

maxz?10x1?12x2?13x3?100y1?150y2?200y3

?1.6x1?1.8x2?1.9x3?1500??1.3x1?1.5x2?1.6x3?1000?4x1?4.5x2?5x3?4000??2.8x1?3.8x2?4.2x3?3000?s.t.?x1?10000y1 ?x?10000y2?2?x3?10000y3??x1,x2,x3?0??y1,y2,y3?0或1

（三）互补松弛应用

maxz?2x1?3x2??1???1二（8%）、线性规划问题???1???????12x?2x2?12x?2x2?8?164x2?124x

x,x2?0已知其最优解x1，x2 ? 0，而第1，4两种资源（相应于第1，4两约束）均有余量，应用互

补松弛定理求出原问题和对偶问题的最优解。（2005）

解：二 对偶问题

3.若产品x3值为生产，则x3应为基变量，?在单纯性表中?3?0，即C3至少应为?5????6??1?0?????6???4?????203

4.设新产品为x7，则?7?8???6?10

二（20％）

有一线性规划为 Maxz?c1x1?c2x2 s.t a11x1?a12x2?b1 a21x1 ?a22x2?b2 x1 ,x2 ?0

设 X3,X4 为引入的松弛变量。得到最优单纯形表如上表，要求： （1）利用最优解求c1,c2. （2）利用最优解求b1,b2

XB X1 X1 X2 X3 X4 1 0 3 -1 0 1 -1 1 0 0 -3 -1 解 1 2 -8 X2 ?J （3）C2 能变化多少而不至影响最优解；当 C2?1 时求最优解；

?1? （4）假定用b+λb代替b,其中b????1??(??????),求出使最优基保持不变的λ的范

????围.

（5）求出各资源的剩余量和影子价格。(1997) 解：二

maxz?c1x1?c2x2a11x1?a12x2?a13x3?b1a21x1?a22x2?a23x4?b2x1,x2,x3,x4?0

xB x1 x2 x1 1 0 0 x2 0 1 0 x3 3 -1 -3 x4 -1 1 -1 解 1 2 -8 ?j

（1）?3?C3?CBB?1P3 ?3?0??C1C2???3?? ??1???1?? ?1?

?1 ?1?0??C1C2???4?C4?CBBP4 C1?2,C2?3

3?b???3b1?b2?1?3?1??b1??1??3b1?b2??1??12?1??(2) Bb?? ???? ??????? ??11b2?b?b2?b?b?27???2????12????12?b?2??2(3) C2的变化影响检验数，设C2的变化量为?C

?3?0??2,3??C???3???0 即 6??3??C??0 ??1???1??4?0??2,3??C????0 ?2??3??C??0

?1?

?1??C?3 当C2=1时 CB XB Bb 2 X1 1 1 X2 2 ?1 2 1 0 0 X1 X2 X3 X4 1 0 3 -1 0 1 -1 1 0 0 -5 1 1 1 2 0 0 1 -1 1 0 -1 -4 0 ?J 2 X1 3 0 X4 2

?J

??fk?Sk??minVk?fk?1?Sk?1????? X???3,0,0?, 2 Z?2?3?0?1?6 ?f4?S4??1950?1180??3???3?1???2??1???1*B?b??b?????????????0

??11???7???1????????2????3???3?1???2???????????????0??11???7????????????2??7?91?3?????0?????1?2?2????4?????1

4??3???7???0???1???22（5）X1?1,X2?2 B?1???（4）

?3?1?1?11??1 ?X,XB???12?????X1,X2?

2?13???11? Max?2X1?3X2

13?1X?X??21222?37?1 s.t?X1?X2?

22?2?X1,X2?0?? 第一种资源剩余为0 第二种资源剩余为0

影子价格分别为-3，-1 解： 解：

解： 解：

（五）证明题

三（15分）、考虑下面两个线性规划：

(I)?Min?z?CX(II)?Min?z'?C'X约束条件AX?bX?0约束条件AX?b

X?0?C'?C?X'*?X*?0（2007） 已知X*是(I)的最优解，X'*是(II)的最优解，试证：解：三、

??因为所以所以CX*?CX'*C(X*?X'*)?0C'(X'*?X*)?0(1)

又因为C'X'*?C'X*(2)(2)?(1)得

(C'?C)(X'*?X*)?0maxz?CX三（11%）、考虑线性规划问题（P）?Ax?b??X?0

1．若X1,X2均为（P）的可行解，???0,1?，证明?X1?(1??)X2也是（P）的可行解；

2．写出（P）的对偶模型（仍用矩阵式表示）。（2006）

三、1证明：令?X1?(1??)X2?X3，若X3是（P）的可行解，则应满足

??AX3?b??(1)

?X3?0???(2)因为X1,X2均为(P)的可行解，?AX1?b?AX2?b即?；，?X?0X?0?1?2 所以AX3?A[?X1?(1??)X2]??AX1?(1??)AX2

??b?(1??)b?b即X3满足(1).又因为??[0,1],X1?0,X2?0,故有?X1?0,(1??)X2?0, 所以X3??X1?(1??)X2?0,

即X3满足(2).所以X3??X1?(1??)X2也是(P)的可行解.2．对偶模型

minw?bTY?ATY?CT ??Y无限制三（10%）、证明线性规划中的互补松弛定理：设（P）[max]z=CX,X?{X|AX?b,X?0},(D)[min]u=Yb,Y?{YA?b,Y?0},若X,Y分别是（P）（D）的可行解，Xs,Ys分别是其相应的松弛变量，则X,Y是（P），（D）的最优解的充要条件是：YXs?YsX?0；

并解释互补松弛定理的经济意义。（2004） 解： 三、

互补松弛定理的经济意义是：资源有剩余，则其影子价格为0，反之，影子价格为0说明资源恰好用完。

四、(21%)试证明线性规划原问题中第J个约束扩大K倍,其对偶规划最优解中第J个变量将缩小K倍（2003）

?a11?am1?????解：四、设原问题为maxZ=CX AX=b对偶????a?a?mn??1n?y1??C1????????≥??? ?ym??CN?????

?a11?am1?????J????a?a?mn??1n?x1??b1????????=??? ?xn??bn??????x1??b1???????????(kaj1,kaj2,?kajn) ?xj?=?kbj?

???????????xn??bn?????从而得出结论 二、（12%）有三个线性规划：

(?)?Min?z?CX(??)?Min?z??C?X(???)?Min?z?CX

约束条件AX＝b 约束条件AX＝b 约束条件AX＝b X ? 0 X?0 X?0是（ ?）的最优解 ，X??是（ ??）的最优解 ，Y?是（?）的对偶问题的最优解已知：X?，

试证：（1）(C??C)(X???X?)?0；（2）C(X??X)?Y?(b?b)。（2000） 解：(1)

因为所以所以(2)

CX'?CX''C(X'?X'')?0C'(X''?X')?0(1)

又因为C'X''?C'X'(2)(2)?(1)得(C''?C')(X''?X')?0设Y是(ΙΙΙ)的对偶问题的最优解C(X??X)?CX??CX?Y?b?Yb?Y?b?Y'b?Y?(b?b)2.在使用单纯形法求解线性规划问题

maxZ?CX?AX?b?

s.t.???X?0?时，设当前基B??P1,?,Pm?.证明：若xk为某非基变量，检验数

?k?ck?CBB?1Pk?0，

由此确定Pk为进基变量，则能保证新的基本可行解的目标值得以改善。(1998)

2.

证明：令 A?(B,N)C?(CB,CN)?XB?有(B,N)???b?BXB?NXN?b?XN??XB?B?1b?B?1NXN?X?令当前X??B? 即XN?(0,0?0)T ?0?带入目标函数??CBXB?CNXN?CBB?1b?(CN?CBB?1N)XN???CBB?1bxk入基后 即xk???0?0??????'?1?1??CBBb??CN?CBBN???????????0???0??????

?1?1?CBBb????cm?ck?cn??CBB?Pm?Pk?Pn?????????????0???CBB?1b??ck?CBB?1Pk??????k???一（14％）

对某线性规划问题 MaxZ?CX?AX?b ?

X?0?已确定一可行基本B,CB为基变量价格系数向量，A?(P1,P2,?,Pn)（1）请用数学方法证明，当所有非基变量检验数?j?cj?CBBPj?0时，当前基本可行解为最优。

（2）请从经济含义的角度出发，说明上述判断的正确性。(1997) 解：

一．

?1

（一）确定换出基的变量

因为总存在<0的bi，令br=min?bi?,其对应变量xr为换出基的变量

iCB C1 基 b x1 1 0 xr 0 1 xm 0 0 xm?1 a1.m?1 xn a1.n x1 b1 Cr xr br ar.m?1 ar.n Cm xm bm 0 0 0 0 1 am.m?1 am.n ?j Cm?1?zm?1 Cs?zs Cn?zn

（二）确定换入基变量

（1）为了使下一个表中第r行基变量为正值，因而只有对应arj<0的非基变量才可以考虑作为换入基的变量

???cj?zj?c?zarj?0??ss （2）为了使下一个表中对偶问题的解仍为可行解，令??min?jars???arj?称ars为主元素，xs为换入基的变量 设下一表中的检验数为cj?zj

??'?cj?zj?'?cj?zjcs?zs???cj?zj????cs?zs??arj??

arsars??arj??arj（a）对arj?0时，因cj?zj?0 故以cj?zjcj?zjarj?0 有因为主元素ars?0 所以

cs?zs?0 所ars???0

'（b）对arj?0 因

cj?zjarj?'cs?zs?0 故?cj?zj??0 ars

解： 解： 解： 解： 解： 解： 解： 解： 解：

二、运输问题

２．将非平衡运输问题化为平衡运输问题，在表上相当于增加一个虚设的 ，在模型中相当于增加若干个 变量。（2007）（2004） 解：2．产地或销地；松弛。

9．运用表上作业法求解运输问题时，计算检验数可以用 b ，确定初始方案可以用 a 。 （a）最小元素法 （b）比回路法

4. 用表上作业法求解m个发点和n个收点的平衡运输问题，其方案表上有数格的个数

为 ，空格的个数为 ；若从检验数为-2的某空格调整，调量为2，则调后可使总运费下降 。(2000) 解：m+n-1, (m-1)(n-1), 4.

3．用表上作业法求解某运输问题，若已计算出某空格的检验数为-2，则其经济意义是 ，若从该空格出发进行调整，该调整量为2，则调后可使总运费下降 。（1999）

解：3、该处每增运一个单位，将使总成本降低2

二、（13%）用表上作业法求解下面的平衡运输问题

minz???cijxij

i?1j?1mn?n??xij?ai,i?1,?,m?j?1?ms..t??xij?bj,j?1,?,n ?i?1?xij?0,i?1,?,m;j?1,?,n??时，计算某方案的空格[i,j]检验数?ij可采用位势法，其主要步骤如下：

（1）建立线形方程组Ui+Vj=Cij,其中Cij为所有有数个的运价，Ui，Vj分别称发地i和收地j的位势。

（2）令U1=0，求解得位势值Ui，Vj，i=1，??，m, j=1,??,n （3）?ij= Cij-(Ui+Vj)

试证明该方法的正确性，即证明空格[i,j]的检验数为

?ij= Cij-(Ui+Vj)

（1999） 解： 解： 解： 解： 解： 解：

三、多目标规划

2．目标规划模型的一个主要特点是引入了______________变量，模型的目标就是这些变量的极_____（大还是小）化，模型的约束中也要包括用这些变量表示的_____________约束。（2005）

解：2、偏差 小 目标（软）

3． 目标规划模型的一个主要特点是引入了偏差变量，模型的目标就是这些变量的极 小

（大还是小化），模型的约束中也要包括用这些变量表示的目标约束。(2002)

1. 目标规划模型的特点是引入了 变量，模型的目标函数是这些变量的极 （大还是小）化，模型的约束中也含有用这种变量表示的 约束。(2000) 解：偏差变量；极小；目标（软）. 解： 解： 解： 解：

四、动态规划 四（25分）、某投资者拟对A与B两种基金进行投资，投资期限5年。该投资的收益有两部分：一是长期的至第5年末的红利收入，年利率分别为IA=0.06和IB=0.04，计复利且5年间利率不变（例如，第1年初投入A基金1元，5年后红利收入（1+0.06）5元）；二是短期的每年利息收入，两种基金在不同年份的利率iAK和iBK见下表（例如，第1年初投入A基金1元，除5年后的红利收入外，一年后还有0.02元的利息收入）。 年份 基金 A B 1 0.020 0.050 2 0.023 0.050 3 0.024 0.055 4 0.026 0.045 5 0.030 0.055 该投资者第1年初投入资金50000元，以后第2至5年初每年还再投入10000元（不包括已投资的利息收入），收益计算方法相同（如第2年初投入A基金1元，第5年末红利收

4

入（1+0.06）元，同时第2至5年末还有年利息）。所有投入基金的资金（包括年利息）在第5年末之前不得支取。现投资者需决定每年初的资金（当年投入资金加已投资金的短期年利息）对基金A和B的分配额，以使第5年末总收入最大。 拟用动态规划方法解决此问题（按逆序递推），设：状态变量Sk为第k年初可分配的资金总量：决策变量xk为第k年初分配给基金A的资金量。

1． 写出：（1）状态转移方程；（2）阶段指标（提示：第5年的阶段指标因年末短期年

利息收入不再投入需单独表示）；（3）基本（递推）方程。

**

2． 求出最优指标f5(s5)和f4(s4)以及相应的最优决策x5(s5)和x4(s4)。（2007）

四、 解: 1．

(1) sk?1?xk?iAK?(sk?xk)?iBK?10000; s1?50000

(2) 阶段指标函数vk(sk,xk)?xk(1?0.06)6?k?(sk?xk)(1?0.04)6?kv5(s5,x5)?x5?iA5?(s5?x5)?iB5?x5(1?0.06)?(s5?x5)(1?0.04)

(3)　递推方程f6(s6)?0f5(s5)?max?x5?iA5?(s5?x5)?iB5?x5(1?0.06)?(s5?x5)(1?0.04)?f6(s6)?

0?x5?s5fk(sk)?maxxk(1?0.06)6?k?(sk?xk)(1?0.04)6?k?fk?1(sk?1)　　(k?1,2,3,4)0?xk?sk??sk?1?xk?iAK?(sk?xk)?iBK?100002．

f5(s5)?max?x5?iA5?(s5?x5)?iB5?x5(1?0.06)?(s5?x5)(1?0.04)?f6(s6)?0?x5?s5 ?max?0.03x5?0.055(s5?x5)?x5(1?0.06)?(s5?x5)(1?0.04)?0?0?x5?s5 ?max?1.095s5?0.005x5?0?x5?s5*当x5?0时，取得最大值，f5(s5)?1.095s50?x4?s4f4(s4)?max?x4(1?0.06)6?4?(s4?x4)(1?0.04)6?4?f5(s5)?22 ?max?x4(1?0.06)?(s4?x4)(1?0.04)?1.095s5? ?max?x4(1.06)2?(s4?x4)(1.04)2?1.095[x4?iA4?(s4?x4)?iB4?10000]?0?x4?s40?x4?s40?x4?s40?x4?s4

?max?1.1236x4?1.0816(s4?x4)?1.095[0.026x4?0.045(s4?x4)?10000]?? ?max?1.1309s4?0.0212x4?10950*当x4?s4时，取得最大值，f4(s4)?1.1521s4?10950四（18%）、某工厂生产N种产品，它们都要使用某种原材料，现该原材料共有a吨，若分配xj吨原材料给第j种产品，则可产生的收益为g（，j=1，?，jxj）

N。现工厂需拟定使总收益最大的原材料分配方案，试就以下1、2两小题选答一题。

1、（1）写出此问题的数学规划模型；

（2）拟用动态规划方法求解，请写出此问题的阶段变量，状态变量、决策变量、状态转移、阶段指标、指标函数、基本方程（不解）。

2、若工厂生产N=3种产品（分别称为A、B、C），共有原材料a=3吨，各种产品被分配该原材料后产生的收益见表1，请用动态规划方法求解使总收益最大的分配方案。 （2006）

表1 产 分 A B C 品 配 量 ( 吨 ) 0 1 2 3 0 10 17 20 0 6 17 18 0 8 11 11

解：四

2 阶段变量k=1，2，3 表示给3种产品分配原材料的过程

状态变量sk，表示给第k种产品分配原料时拥有的资源数 决策变量xk，表给第k中产品分配的原料量 状态转移方程：Sk?1?Sk?xk 阶段指标：vk为离散型，见下表

基本方程

k 3 ?fk(sk)?max?vk?fk?1(sk?1)? ??f4(s4)?0sk 0 1 2 3 xk 0 1 2 3 0 0 1 2 3 0 1 2 0 1 2 3 vk 0 10 17 20 0 0 6 0 6 17 0 6 17 18 0 8 11 11

vk+fk+1(sK+1) 0+0 10+0 17+0 20+0 0+0 0+10 6+0 0+17 6+10 17+0 0+20 6+17 17+10 18+0 0+27 8+17 11+10 11+0 27 0-2-1 27 17 0-2 或2-0 2-1 fk(sK) 0 10 17 20 0 10 pkn 0 1 2 3 0-0 0-1 2 0 1 1 3 0 1 2 3

?最大收益27，分配方案0-2-1，即给A分配0吨，B分配2吨，C分配1吨。

四（9%）、考虑下面的非线性整数规划 max z?x1x2g3(x3)

?x1?x2?x3?20 s.. t?x?0且为整数 i?1,2,3?i

?12?3x30?x3?3?3?x3?10 其中 g3(x3)??3?3?x310?x3?20?10现拟用动态规划方法解此问题（用通常的逆推解法），要求： (1) 写出以下表达式或集合的具体内容： ①本问题的状态转移方程

sk?1?

?fk(sk)??②递推方程 ?

?f(s)??44③第1阶段的状态集合S1???

④第2阶段状态为5时的允许决策x2的集合D2(5)={ }；

*(2) 计算第2阶段状态为12时的最优指标函数值f2(12)及相应的最优决策x2(12)。

（2005）

解：四 （1）

①Sk?1?Sk?xk

???12???3x3f4(S4)0?x3?3???3?x3?10当k?3时???3f4(S4)???fk(Sk)?maxvk,fk?1(Sk?1)???3②? ??x3f4(S4)10?x3?20???10??当k?1或2时?xk?fk?1(Sk?1)??f?4(s4)?1③ S1??20?

④ D2(5)??0,1,2,3,4,5? （2） 第2阶段k=12,则3段k=8 ?f3(S3)?3?1?3

f2(12)?max?3x2?0?x2?12

?

*f2(12)?36,x2?12

Ⅱ2

k 2 Sk 12 xk 0 1 2 3 4 5 6 7 8 9 10 11 12 * ?f2(12)?36x2(12)?12

vk 0 1 2 3 4 5 6 7 8 9 10 11 12 Vkfk+1(Sk+1) 0?3 1?3 2?3 3?3 4?3 5?3 6?3 7?3 8?3 9?3 10?3 11?3 12?3 Fk(Sk) 0 3 6 9 12 15 18 21 24 27 30 33 36 pnk 12

四（15%）、某工厂购进100台机器，准备用于生产A，B两种产品。若生产产品A，每台机器每年可收入45万，损坏率为65%，若生产产品B每台机器年收入35万，损坏率为35%，估计三年后将有新的机器出现，旧的机器将全部淘汰。请在下列两问中任选一问： 1、 试问每年就如何生产，使三年内的收入最多？运用动态规划方法具体计算求解。

2、 写出用动态规划方法求解时的阶段变量、状态变量、决策变量、状态转移、阶段指标、

指标函数、基本方程（递推公式），不必具体计算。但请简要说明当不能肯定三年后将有新的机器出现，而要求到第三年末保留一定数量的旧机器时求解过程将做何调整。（2004） 解：四、

阶段变量K=1,2,3表第K年，状态变量SK表第K年初的好机器数目，决策变量XK，表示第K年决定把XK台机器投入A产品的生产，状态转移方程SK+1=0.35XK+0.65（SK-XK）

Sk?1?0.35xk?0.65(Sk?xk)

阶段指标，VK=45XK+35（SK-XK）Vk?45xk?35(Sk?xk) 递推方程：?Vk?fk?1(Sk?1)??fk(Sk)?max?

?f4(S4)?0具体计算如下： k=3时：

f3(S3)?max?45x3?35(s3?x3)?0)?max?10x3?35s3??45s3(x3?s3)

*k=2时：

f2(S2)?max?45x2?35(s2?x2)?45?0.35x2?0.65(s2?x2)?)?max??3.5x2?64.25s2??64.25s2(x2?0)*

k=1时：

f1(S1)?max?45x1?35(s1?x1)?64.25?0.35x1?0.65(s1?x1)?)?max??9.275x1?76.7625s1??76.7625s1(x1?0)*

生产计划如下：

s1?100x1?0s2?65x2?0**

s3?42.25x3?42.25*

即前两年把所有机器投入B产品，最后一年全部投入A产品 最大收入：

f1(S1)=7676.25元

2.某工厂考虑设备n年的更新计划,在每年初需作出设备是更新还是继续使用的决策,设备使用一年产生的利润,设备使用一年的维修费,以及设备的更新费用都与设备已使用的年数(设备年龄t)有关.

设r(t)为t年龄设备使用一年的利润 u(t)为t年龄设备使用一年的维修费用 c(t)为t年龄设备当年更新的费用

用动态规划方法求出n年内每年的最佳决策而使n年总利润最大.试引入0-1变量表示决策变量,并由此统一表示动态规划有关的概念和式子(不必求解):阶段,状态变量,决策变量,状态转移,阶段指标.（2003）

解：⒉设阶段变量k=1,2?n,状态变量tk表示k年初设备的年龄 决策变量xk?0表示更新，xk?1表示继续使用 状态转移方程tk?xktk?1

阶段指标Vk(tk,xk)?r(tk)?u(tk)?(1?xk)c(tk)

?fk(tk)?max{r(tk)?u(tk)?(1?xk)c(tk)?fk?1(xktk?1)?递推方程?xk?0,1

?f(t)?0,k?1,2,?,n?n?1n?1 五、（10%）某厂计划用220万资金，购买生产同一种产品的四种型号的设备A、B、C、D，这四种型号的设备设计生产能力和价格如下表所示。每种型号的设备应购买过少台，使总生产能力最大。

设备型号 设计生产能力K（吨/台） i价格Pi（万元/台） A 150 70 B 180 75 C 200 80 D 210 85 建立该问题的动态规划模型：列出阶段变量、状态变量、决策变量、状态转移方程、阶段指标、递推方程（不解）。(2002)

解：五、阶段变量k=1,2,3,4 分别表示A,B,C,D四种型号的设备 状态变量：Sk表示在第k阶段还有Sk万元资金可供使用 决策变量：Xk表示购买k型号设备的台数

状态转移方程：Sk+1=Sk-CkXk(Ck为x型号设备的价格) 阶段指标：Vk(Xk,Sk)=RkXk(Rk为设备的设计生产能力) 递推方程：?

?fk(sk)?max?vk(xk,sk)?fk?1(sk?1)??max?Rkxk?fk?1(sk?ckxk)?

?f5(s5)?0,k?4,3,2,15．动态规划问题的研究对象是 b ，其求得的一般方法是 c 。(2001) （a）工程路线问题 （b）多段决策问题 （c）迭代求解 （d）单纯形法 解： 三、（12%）某瓷厂接受订制一个仿宋高级瓷瓶的任务，瓷瓶需要用电炉烧制，据技术分析，每个瓶出炉后合格率为1/2，各瓶合格与否相互独立（即一炉如装有n个瓷瓶，那么出炉后都不合格的概率为(1/2)n）。 制造一个瓷瓶的原料费为100元，烧一炉的费用为300元，现因厂中条件限制，只能烧3炉，每炉最多装四个瓷瓶，若3炉瓷瓶无1个合格，则因不能履行合同而被罚款1600元。试用动态规划方法确定一种生产方案（即每炉该装几个瓷瓶），使总的期望成本为最小。（2000）

解：阶段变量：k=1,2,3, 分别表示三次烧制过程。

状态变量：每次烧制前是否有合格品作为状态变量Sk，

?0,第k次烧制前有合格品 Sk??1,第k次烧制前无合格品?决策变量：Xk表示第次烧制的瓶数（0≤Xk≤4）。

?xk?3,xk?0阶段指标：Vk(xk,sk)??（百元为单位）

0,x?0k?

设fk(Sk)表示第k次烧制前的状态为Sk时，以后均采取最优策略的最低期望成本，则有fk(0) =0（k=1,2,3），f4(1) =16， 递推方程：

?fk(1)?minvk(xk,sk)?(0.5)xkfk?1(1)?minxk?3y?(0.5)xkfk?1(1)0?xk?40?xk?4,xk?My,y?0,1?? ?fk(0)?0,k?3,2,1?f(1)?16,4??当k=3时，f3(1)? x3 s3 0 1

当k=2时，f2(1)? x2 s2 0 1

0?x2?4,x2?My,y?0,10?x3?4,x3?My,y?0,1????min?x3?3y?(0.5)x3?16

?x3?3y?(0.5)x3?16 0 1 2 3 4 0 - - - - 16 12 9 8 8 minf3(s3) 0 8 x3 0 3或4 ?x2?3y?(0.5)x2?8?

x2?3y?(0.5)x2?8 0 1 2 3 4 0 - - - - 8 8 7 7 7.5 minf2(s2) 0 7 x2 0 2或3 当k=1时，f1(1)? x2 s2 1 0?x1?4,x1?My,y?0,1?x?3y?(0.5)1x1?7?

x1?3y?(0.5)x1?7 0 1 2 3 4 f2(s2) x2 7 7.5 6.75 6.875 7.4375 6.75 2 最优策略为第一阶段烧制2个，若无合格的第二阶段烧制2或3个，若还无合格的第三阶段烧制3或4个，最低期望成本为675元。

4．动态规划中的Bellman最优性原理是 。（1999） 解：4、对一个最优策略，无论前面的状态和决策如何，由前面决策所构成的状态，其后部子策略 是最优的。

三（12%）某大学生正在计划如何安排在7天时间里复习完4门考试课程，他要求每天只能安排一门课程的复习，每门课程至少需要复习一天。据他估计每门课程的复习时间与所能带来的成绩提高关系如下表。请在下面两小问众人选作一问。

(1) 用动态规划方法求出使其总成绩提高最多的复习天数安排计划。

(2) 不具体计算，但要写出本问题的阶段变量、状态变量、各阶段状态变量集（即状态变量取值范围）、决策变量、阶段指标、指标函数、基本方程（递推分式）。（1999）

估计的提高分数 1 2 3 4 1 4 3 5 2 2 4 5 6 4 3 5 6 8 7 4 8 7 8 8

解：三、阶段变量k=1,2,3,4,表给出课分配复习时间的过程

状态变量Sk表示第k天分配时间剩余的可利用天数 决策变量xk表经第k天分配的时间1≤xk≤Sk-(4-k) 阶段指标Vk（Sk，xk）（如表）

指标函数：Vkn=基本方程：

?Vk?knk

??fk(sk)?max?vk(xk,sk)?fk?1(sk?1)? ???f5(s5)?0,k?4,3,2,1状态变量集：5-k≤Sk≤7-(k-1) 5-k≤Sk≤8-k

k 4 sk 1 2 3 4 2 3 4 5 xk 1 2 3 4 1 1 2 1 2 3 1 2 3 4 1 1 2 1 2 vk 2 4 7 8 5 5 6 5 6 8 5 6 8 8 3 3 5 3 5 Vk+fk+1 2+0 4+0 7+0 8+0 5+2 5+4 6+2 5+7 6+4 8+2 5+8 6+7 8+4 8+2 3+7 3+9 5+7 3+12 5+9 fk(sk) 2 4 7 8 7 9 12 13 Pkn 1 2 3 4 1-1 1-2 1-3 1-4 2-3 3 2 3 4 5 10 12 15 1-1-1 1-1-2 2-1-1 1-1-3

6 3 1 2 3 4 6 3 5 6 7 6+7 3+13 5+12 6+9 7+7 17 2-1-3

k 1 sk 7 xk 1 2 3 4 vk 4 4 5 8 Vk+fk+1 fk 4+17 4+15 5+12 8+10 21 Pk 1-2

二（15%）某工厂欲对一新购置设备作一5年工作计划，决定每年初是继续使用还是更新该设备，以使5年的总收益最大。该设备工作的年收入，年维修费，更新费均与设备的年龄有关。设s表示设备年龄，R(s) ，U(s)和C(s)分别表示年收入，年维修费和更新费。

1) 用最短路模型来求解此问题（列出模型，不解）

2) 用动态规划模型来求解此问题（列出模型，不解）(1998)

解：二

最短路模型：

用点Vi表示第i年购进一台新设备，虚设一个点V6，表示第五年年底。 边 (Vi,Vj)表示第i年购进的设备一直使用到第j年年初（即第j-1年年底）。 边 (Vi,Vj)上的数字表示第i年初购进设备，一直使用到第j年年初所需支付的购买，维修的全部费用。

这样此设备更新问题就变为：求从V1到V6的最短路问题。 如图：

本文来源：https://www.bwwdw.com/article/rw66.html