数据、模型与决策

Data,ModelandDecisions

数据、模型与决策

赵明霞山西大学经济与管理学院2

其它规划问题规划的组成：目标函数opt（optimize）maxz(f)或minz(f)约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素2023/2/422.1

整数规划2.2

目标规划2.3

动态规划42.1整数规划

§1整数规划的图解法

§2整数规划的计算机求解

§3整数规划的应用5求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。在整数规划中:如果所有的变量都为非负整数，则称为纯整数规划问题；如果只有一部分变量为非负整数，则称之为混合整数规划问题。如果所有的变量都为0-1变量，则称之为0-1规划。6§1整数规划的图解法例8-1.某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大?货物每件体积（立方英尺）每件重量（百千克）每件利润（百元）甲乙19527344023托运限制1365140

7解：设x1、

x2分别为甲、乙两种货物托运的件数，建立模型目标函数：Maxz=2x1+3x2

约束条件：s.t.195

x1+273x2≤13654

x1+40x2≤140

x1≤4x1，x2≥0为整数。如果去掉最后一个约束，就是一个线性规划问题。利用图解法，8得到线性规划的最优解为x1=2.44,x2=3.26,目标函数值为14.66。由图表可看出，整数规划的最优解为x1=4,x2=2,目标函数值为14。12341232x1+3x2=14.66x1x22x1+3x2=142x1+3x2=69性质1：任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于相应的线性规划的最大目标函数值；任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于相应的线性规划的最小目标函数值。10例8-2：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2

x1-3x2+2x3≤3x1,x2,x3≥0为整数例8-3：

Maxz=3x1+x2+3x3

s.t.-x1+2x2+x3≤44x2-3x3≤2x1-3x2+2x3≤3x3≤1x1,x2,x3≥0x1，x3

为整数

x3

为0-1变量用《管理运筹学》软件求解得：

x1=5x2=2x3=2用《管理运筹学》软件求解得：

x1=4x2=1.25x3=1z=16.25§2整数规划的计算机求解11§3整数规划的应用

一、投资场所的选择

例8-4:京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置Aj(j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1

，A2

，A3三个点至多选择两个；在西区由A4

，A5两个点中至少选一个；在南区由A6

，A7两个点中至少选一个；在北区由A8

，A9

，A10

三个点中至少选两个。

Aj

各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示(单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大?12解：设：0--1变量xi=1(Ai点被选用）或0(Ai点没被选用）。这样我们可建立如下的数学模型：Maxz=36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10s.t.100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10≤720

x1+x2+x3≤2

x4+x5≥1

x6+x7≥1

x8+x9+x10≥2xj≥0

且xj

为0--1变量，i=1,2,3,……,1013二、固定成本问题

例8-5:高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。14解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=1(当生产第i种容器,即xi＞0时)或0（当不生产第i种容器即xi=0时）。引入约束xi≤Myi

，i=1，2，3，M充分大，以保证当yi=0时，xi=0。

yi=0xi=0

这样我们可建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大

xj≥0yj

为0--1变量，i=1,2,315三、指派问题有n项不同的任务，恰好n个人可分别承担这些任务，但由于每人特长不同，完成各项任务的效率等情况也不同。现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人，使得完成n项任务的总的效率最高，这就是指派问题。例8-6．有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。16解：引入0—1变量xij，并令

xij=1(当指派第i人去完成第j项工作时)或0（当不指派第i人去完成第j项工作时)．这可以表示为一个0--1整数规划问题：Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一项工作)

x21+x22+x23+x24=1(乙只能干一项工作)

x31+x32+x33+x34=1(丙只能干一项工作)

x41+x42+x43+x44=1(丁只能干一项工作)

x11+x21+x31+x41=1(A工作只能一人干)

x12+x22+x32+x42=1(B工作只能一人干)

x13+x23+x33+x43=1(C工作只能一人干)

x14+x24+x34+x44=1(D工作只能一人干)

xij

为0--1变量，i,j=1,2,3,417四、分布系统设计例8-7．某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂。已知在A2，A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费:千元)如下表所示。

a)问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?

b)如果由于政策要求必须在A2，A3地建一个厂，应在哪几个地方建厂?18解：a)设xij为从Ai运往Bj的运输量(单位千箱)，

yk=1(当Ak被选中时)或0（当Ak没被选中时),k=2,3,4,5．这可以表示为一个整数规划问题：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4项为固定投资额，后面的项为运输费用。s.t.x11+x12+x13≤30(A1

厂的产量限制)

x21+x22+x23≤10y2(A2

厂的产量限制)

x31+x32+x33≤20y3(A3

厂的产量限制)

x41+x42+x43≤30y4(A4

厂的产量限制)

x51+x52+x53≤40y5(A5

厂的产量限制)

x11+x21+x31+x41+x51=30(B1

销地的限制)

x12+x22+x32+x42+x52=20(B2

销地的限制)

x13+x23+x33+x43+x53=20(B3

销地的限制)

xij≥0，i=1,2,3,4,5；j=1,2,3，yk为0--1变量，k=2,3,4,5。19五、投资问题(第4章）

例8-8．某公司在今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第四年每年年初需要投资，并于次年末回收本利115%，但要求第一年投资最低金额为4万元，第二、三、四年不限；项目B：第三年初需要投资，到第五年末能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元；

项目C：第二年初需要投资，到第五年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。

项目D：五年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?20解：1)设xiA、xiB、xiC、xiD(i＝1，2，3，4，5)分别表示第i年年初给项目A，B，C，D的投资额(元)；设yiA，yiB，是0—1变量，并规定取1时分别表示第i年给A、B投资，否则取0（i=1,3）。设yiC是非负整数变量，并规定：第2年投资C项目8万元时，取值为4；第2年投资C项目6万元时，取值3；第2年投资C项目4万元时，取值2；第2年投资C项目2万元时，取值1；第2年不投资C项目时，取值0；

这样我们建立如下的决策变量：

第1年第2年第3年第4年第5年

Ax1A

x2A

x3A

x4A

B

x3B

C

x2C=20000y2C

D

x1D

x2D

x3D

x4D

x5D

212）约束条件：第一年：年初有100000元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，于是x1A+x1D=100000；第二年：A的投资第二年末才可收回，故第二年年初的资金为1.06x1D，于是x2A+x2C+x2D=1.06x1D；第三年：年初的资金为1.15x1A+1.06x2D，于是x3A+x3B+x3D=1.15x1A+1.06x2D；第四年：年初的资金为1.15x2A+1.06x3D，于是x4A+x4D=1.15x2A+1.06x3D；第五年：年初的资金为1.15x3A+1.06x4D，于是x5D=1.15x3A+1.06x4D。关于项目A的投资额规定:x1A≥40000y1A

，x1A≤200000y1A

，200000是足够大的数；保证当

y1A=0时，x1A=0；当y1A=1时，x1A≥40000。关于项目B的投资额规定:x3B≥30000y3B

，x3B≤50000y3B

；保证当

y3B=0时，x3B=0；当y3B=1时，50000≥

x3B≥30000。关于项目C的投资额规定:x2C=20000y2C

，y2C=0，1，2，3，4。223）目标函数及模型：

Maxz=1.15x4A+1.40x2C+1.28x3B+1.06x5Ds.t.x1A+x1D=10；

x2A+x2C+x2D=1.06x1D；

x3A+x3B+x3D=1.15x1A+1.06x2D；

x4A+x4D=1.15x2A+1.06x3D；

x5D=1.15x3A+1.06x4D；

x1A≥4y1A

，

x1A≤10y1A

，

x3B≥3y3B

，

x3B≤5y3B

；

x2C=2y2C

，y2C≤4xiA

，xiB

，xiC

，xiD≥0(i=1、2、3、4、5）,y1A，y3B

为0-1变量,y2C整数

案例分析教材P199案例分析9-122023/2/42324练习教材P195习题2-1125

2.2目标规划§1目标规划问题举例§2目标规划问题求解§3复杂情况下的目标规划§4加权目标规划26§1目标规划问题举例多目标问题例1．企业生产例2．商务活动例3．投资例4．裁员例5．营销27§2目标规划问题求解

例9-6．一位投资商有一笔资金准备购买股票。资金总额为90000元，目前可选的股票有A和B两种（可以同时投资于两种股票）。其价格以及年收益率和风险系数如表1：股票价格（元）年收益（元）／年风险系数A2030.5B5040.2从上表可知，A股票的收益率为（3／20）×100％＝15％，股票B的收益率为4／50×100％＝8％，A的收益率比B大，但同时A的风险也比B大。这也符合高风险高收益的规律。试求一种投资方案，使得一年的总投资风险不高于700，且投资收益不低于10000元。28

显然，此问题属于目标规划问题。它有两个目标变量：一是限制风险，一是确保收益。在求解之前，应首先考虑两个目标的优先权。假设第一个目标（即限制风险）的优先权比第二个目标（确保收益）大，这意味着求解过程中必须首先满足第一个目标，然后在此基础上再尽量满足第二个目标。建立模型：设x1、x2分别表示投资商所购买的A股票和B股票的数量。首先考虑资金总额的约束：总投资额不能高于90000元。即20x1＋50x2≤90000。29一、约束条件再来考虑风险约束：总风险不能超过700。投资的总风险为0.5x1＋0.2x2。引入两个变量d1+和d1-,建立等式如下：

0.5x1+0.2x2=700+d1+-d1-

其中，d1+表示总风险高于700的部分，d1-表示总风险少于700的部分，d1+,d1-≥0。目标规划中把d1+、d1-这样的变量称为偏差变量。偏差变量的作用是允许约束条件不被精确满足。30

把等式转换，可得到

0.5x1+0.2x2-d1++d1-=700

再来考虑年收入:

年收入=3x1+4x2

引入变量d2+和d2-，分别表示年收入超过与低于10000的数量。于是，第2个目标可以表示为

3x1+4x2-d2++d2-=1000031二、有优先权的目标函数本问题中第一个目标的优先权比第二个目标大。即最重要的目标是满足风险不超过700。分配给第一个目标较高的优先权P1分配给第二个目标较低的优先权P232针对每一个优先权，应当建立一个单一目标的线性规划模型：首先建立具有最高优先权的目标的线性规划模型，求解；然后再按照优先权逐渐降低的顺序分别建立单一目标的线性规划模型，方法是在原来模型的基础上修改目标函数，并把原来模型求解所得的目标最优值作为一个新的约束条件加入到当前模型中，并求解。33三、建模1．针对优先权最高的目标建立线性规划建立线性规划模型如下：

Mind1+s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-≥0342．针对优先权次高的目标建立线性规划优先权次高（P2）的目标是总收益超过10000。建立线性规划如下：

Mind2-s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000

d1+＝0x1,x2,d1+,d1-,d2+,d2-≥035目标规划的这种求解方法可以表述如下：

1．确定解的可行区域。

2．对优先权最高的目标求解，如果找不到能满足该目标的解，则寻找最接近该目标的解。

3．对优先权次之的目标进行求解。注意：必须保证优先权高的目标不变。

4.重复第3步，直至所有优先权的目标求解完。

36四、目标规划模型的标准化例6中对两个不同优先权的目标单独建立线性规划进行求解。为简便，把它们用一个模型来表达，如下：

minP1（d1+）+P2（d2-）

s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-,d2+,d2-≥037管理运筹学软件运用注意事项决策变量个数：不包括偏差变量（2）优先级数：目标优先等级（2）目标约束个数：含偏差变量约束条件个数（2）绝对约束个数：不含偏差变量约束条件个数（1）38§3复杂情况下的目标规划例9-7．一工艺品厂商手工生产某两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品的单位利润分别为250元和125元。为了最大效率地利用人力资源，确定生产的首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过680工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为了保证库存需要，要求每周产品A和B的产量分别不低于200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A完成200件的重要性的2倍。试求如何安排生产？39解：本问题中有3个不同优先权的目标，不妨用P1、P2、P3表示从高至低的优先权。对应P1有两个目标：每周总耗费人力资源不能低于600工时,也不能超过680工时；对应P2有一个目标：每周的利润超过70000元；对应P3有两个目标：每周产品A和B的产量分别不低于200和120件。40采用简化模式，最终得到目标线性规划如下：

MinP1(d1+)+P1(d2－)+P2(d3-)+P3(d4-)+P3(2d5-)s.t.

2x1+3x2-d1++d1-=680对应第1个目标

2x1+3x2-d2++d2-=600对应第2个目标

250x1+125x2-d3++d3-＝70000对应第3个目标

x1-d4++d4-=200对应第4个目标

x2-d5++d5-=120对应第5个目标

x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-≥0罚数权重41

使用运筹学软件求解可得：x1=250；x2=60；d1+=0；d1-=0；d2+=80；d2-=0；d3+=0；d3-=0；d4+=50；d4-=0；d5+=0；d5-=60，目标函数120。可见，目标1、目标2、目标3和目标4达到了，但目标5有一些偏差。

42§4加权目标规划加权目标规划是另一种解决多目标决策问题的方法，其基本方法是:通过量化的方法分配给每个目标的偏离的严重程度一个罚数权重，然后建立总的目标函数，该目标函数表示的目标是要使每个目标函数与各自目标的加权偏差之和最小，假设所有单个的目标函数及约束条件都符合线性规划的要求，那么，整个问题都可以描述为一个线性规划的问题。43在例7中我们对每周总耗费的人力资源超过680工时或低于600工时的每工时罚数权重定为7；每周利润低于70000元时，每元的罚数权重为5；每周产品A产量低于200件时每件罚数权重为2，每周产品B产量低于120件时每件罚数权重为4。44则其目标函数化为：

min7d1++7d2-+5d3-+2d4-+4d5-

这就变成了一个普通的单一目标的线性规划问题

min7d1++7d2-+5d3-+2d4-+4d5-s.t.2x1+3x2-d1++d1-=6802x1+3x2-d2++d2-=680250x1+125x2-d3++d3-=70000x1-d4++d4-=200x2-d5++d5-=120x1,x2,d1+,d1-,d2-,d2+,d3+,d3-,d4+,d4-,d5+,d5-≥0。练习教材P212习题1-1045462.3动态规划§1多阶段决策过程最优化问题举例§2基本概念、基本方程与最优化原理§3动态规划的应用47§1多阶段决策过程最优化问题举例例10-1最短路径问题下图表示从起点A到终点E之间各点的距离。求A到E的最短路径。BACBDBCDEC41231231232216472483867561106375148用穷举法的计算量:如果从A到E的站点有k个，除A、E之外每站有3个位置则总共有3k-1×2条路径；计算各路径长度总共要进行(k+1)3k-1×2次加法以及3k-1×2-1次比较。随着k的值增加时，需要进行的加法和比较的次数将迅速增加；例如当k=20时，加法次数为4.2550833966227×1015

次，比较1.3726075472977×1014

次。若用1亿次/秒的计算机计算需要约508天。49讨论：

1、以上求从A到E的最短路径问题，可以转化为四个性质完全相同，但规模较小的子问题，即分别从Di

、Ci、Bi、A到E的最短路径问题。第四阶段：两个始点D1和D2，终点只有一个；表10-1分析得知：从D1和D2到E的最短路径唯一。

阶段4本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)ED1D210*6106EE50

第三阶段：有三个始点C1，C2，C3，终点有D1，D2，对始点和终点进行分析和讨论分别求C1，C2，C3到D1，D2

的最短路径问题：表10-2分析得知：如果经过C1，则最短路为C1-D2-E；如果经过C2，则最短路为C2-D2-E；如果经过C3，则最短路为C3-D1-E。

阶段3本阶段始点（状态）本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)D1D2C1C2C38+10=187+10=171+10=116+6=125+6=116+6=12121111D2D2D151第二阶段：有4个始点B1,B2,B3,B4，终点有C1,C2,C3。对始点和终点进行分析和讨论分别求B1,B2,B3,B4到C1,C2,C3

的最短路径问题：

表10-3

分析得知：如果经过B1，则走B1-C2-D2-E；如果经过B2，则走B2-C3-D1-E；如果经过B3，则走B3-C3-D1-E；如果经过B4，则走B4-C3-D1-E。

阶段2本阶段始点（状态）

本阶段各终点（决策）到E的最短距离本阶段最优终点（最优决策)C1C2C3B1B2B3B42+12=144+12=164+12=167+12=191+11=127+11=188+11=195+11=166+11=172+11=133+11=141+11=1212131412C2C3C3C352第一阶段：只有1个始点A，终点有B1,B2,B3,B4

。对始点和终点进行分析和讨论分别求A到B1,B2,B3,B4的最短路径问题：

表10-4最后，可以得到：从A到E的最短路径为AB4C3D1E

阶段1本阶段始点(状态)

本阶段各终点（决策）到E的最短距离本阶段最优终点(最优决策)B1B2B3B4A4+12=163+13=163+14=172+12=1414B453

以上计算过程及结果，可用图2表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。以上过程，仅用了22次加法，计算效率远高于穷举法。BACBDBCDEC4123123123321647248386751610601061211111213141412751254一、基本概念：

1、阶段k：表示决策顺序的离散的量，阶段可以按时间或空间划分。

2、状态sk：每个阶段开始时所处的自然状态或客观条件。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。

3、决策xk：从某一状态向下一状态过渡时所做的选择。决策是所在状态的函数，记为xk(sk)。

4、策略Pk,n(sk)：从第k阶段开始到最后第n阶段的决策序列，称k子策略。P1,n(s1)即为全过程策略。

5、指标函数rk(sk,xk)：衡量策略优劣的数量指标；最优指标函数fk(sk)，f1(s1)。

6、状态转移方程sk+1=Tk(sk,xk)：某一状态以及该状态下的决策，与下一状态之间的函数关系。§2基本概念、基本方程与最优化原理55二、基本方程

最优指标函数fk(sk)：从状态sk出发，对所有的策略Pk,n，过程指标rk,n的最优值，即56

对于可加性指标函数，上式可以写为

上式中“opt”表示“max”或“min”。对于可乘性指标函数，上式可以写为

以上式子称为动态规划最优指标的递推方程，是动态规划的基本方程。

终端条件：为了使以上的递推方程有递推的起点，必须要设定最优指标的终端条件，一般最后一个状态n+1下最优指标fn+1(sn+1)=0。57三、最优化原理作为整个过程的最优策略具有如下性质：不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，最优策略的任意子策略都是最优的。58一、资源分配问题

例10-2.某公司拟将某种设备5台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示，问这5台设备应如何分配给这3个工厂，使得所创造的总利润为最大？表10-5

工厂盈利设备台数

甲厂

乙厂

丙厂000013542710639111141211125131112§3动态规划的应用59解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分别编号为1、2、3厂。设

sk=分配给第k个厂至第3个厂的设备台数（k=1、2、3）。

xk=分配给第k个厂设备台数。已知s1=5,

并有

从sk

与xk

的定义，可知

以下我们从第三阶段开始计算。60

第三阶段:

显然将s3(s3=0,1,2,3,4,5)台设备都分配给第3工厂时，也就是s3=x3时，第3阶段的指标值（即第3厂的盈利）为最大，即

由于第3阶段是最后的阶段，故有其中x3可取值为0,1,2,3,4,5。其数值计算见表10－6。61表10－6

0

1

2

3

4

5

0

0－－－－－00

1－4－－－－41

2－－6－－－62

3－－－11－－113

4－－－－12－124

5－－－－－1212562

其中x*3表示取3子过程上最优指标值f3(s3)时的x3决策，例如在表10-6中可知当s3=4时，有r3(4,4)=12,有f3(4)=12此时x*3=4，即当s3=4时，此时取x3=4

（把4台设备分配给第3厂）是最优决策，此时阶段指标值（盈利）为12，最优3子过程最优指标值也为12。63第二阶段：当把s2=0,1,2,3,4,5台设备分配给第2工厂和第3工厂时，则对每个s2值，有一种最优分配方案，使最大盈利即最优2子过程最优指标函数值为因为s3=s2-x2上式也可写成64其数值计算如表10－7所示。

表10－7

0

1

2

3

4

5

0－－－－－00

10＋4

－－－－51

20＋6

5＋4－－－102

30＋11

5＋6

11＋0－－142

40＋12

11＋4

11＋0－161,2

50＋12

5＋12

11＋6

11＋4

11＋0

21265第一阶段：把台设备分配给第1，第2，第3厂时，最大盈利为其中可取值0,1,2,3,4,5。数值计算见表10－8

0

1

2

3

4

5

5

3＋169+1012+513+0210,266然后按计算表格的顺序推算，可知最优分配方案有两个：

1.由于x*1=0，根据s2=s1-x*1=5，查表10－7可知x*2=2，再由s3=s2-x*2=3，求得x*3=s3=3。即分配给甲厂0台，乙厂2台，丙厂3台。

2.由于x*1=2，根据s2=s1-x*1=3，查表10－7可知x*2=2，再由s3=s2-x*2=1,求得x*3=s3=1，即分配给甲厂2台，乙厂2台，丙厂1台。这两种分配方案都能得到最高的总盈利21万元。67二、背包问题设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。这个问题可以用整数规划模型来描述。设xi为第i种物品装入背包的件数（i=1,2,…,n），背包中物品的总价值为z，则

maxz=c1x1+c2x2+…+cnxns.t.w1x1+w2x2+…+wnxn≤Wx1,x2,…,xn0

且为整数。68

下面用动态规划逆序解法求解它。设阶段变量k：第k次装载第k种物品（k=1,2,…,n）状态变量sk：第k次装载时背包还可以装载的重量；决策变量xk：第k次装载第k种物品的件数；状态转移方程：sk+1=skwkxk；阶段指标：rk=ckxk；最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使用价值；递推方程： fk(sk)=max{ckxk+fk+1(sk+1)}=max{ckxk+fk+1(skwkxk)}；

xDk(sk)终端条件：fn+1(sn+1)=0。69

例10-3.某咨询公司有10个工作日可以去处理四种类型的咨询项目，每种类型的咨询项目中待处理的客户数量、处理每个客户所需工作日数以及所获得的利润如表10－9所示。显然该公司在10天内不能处理完所有的客户，它可以自己挑选一些客户，其余的请其他咨询公司去做，应如何选择客户使得在这10个工作日中获利最大？表10－9咨询项目类型待处理客户数处理每个客户所需工作日数处理每个客户所获利润

1

2

3

4

4

3

2

2

1

3

4

7

2

8

11

2070

解：用动态规划来求解此题。我们把此问题分成四个阶段：第一阶段我们决策将处理多少个第一种咨询项目类型中的客户，第二阶段决策将处理多少个第二种咨询项目类型中的客户，第三阶段、第四阶段我们也将作出类似的决策。我们设

sk＝分配给第k种咨询项目到第四种咨询项目的所有客户的总工作日（第k阶段的状态变量）。

xk=在第k种咨询项目中处理客户的数量（第k阶段的决策变量）。已知s1＝10并有71从第四阶段开始计算：显然将s4个工作日s4=(0,1,2……,10)尽可能分配给第四类咨询项目，即x4=[s4/7]时，第四阶段的指标值为最大，其中[s4/7]表示取不大于[s4/7]的最大整数，符号[]为取整符号，故有由于第四阶段是最后的阶段，故有72因为s4至多为10，其数值计算见表10－10。

表10－10

0

1

0

－

0

0

1－

0

0

2－

0

0

3－

0

0

4－

0

0

5

－

0

0

6－

0

0

7

0

20

1

8

0

20

1

9

0

20

1

10

0

20

173第三阶段：当把s3=(0,1,2……,10)个工作日分配给第四类和第三类咨询项目时，则对每个s3值，都有一种最优分配方案，使其最大盈利即最优3子过程最优指标函数值为

因为因为s3

至多为10，所以x3的取值可为0,1,2。其数值计算见表10－11。74

表10－11

012

0－－

0

01

－－

0

02－－

0

03－－

0

04

0＋0－

1115

0＋0－

1116

0＋0－

1117

11+0－2008

0＋20

11+0

2229

0＋20

11+0

22210

0＋20

11+0

22275第二阶段：同样以每个s2值都有一种最优分配方案，使其最大盈利即最优2子过程最优指标函数值为：因为，故有因为s2至多为10，所以x2的取值为0,1,2,3。其数值计算见表10－12。76表10-1277

第一阶段：我们已知，又因为，同样有

因为,故可取值为0,1,2,…,10。其数值计算见表10－13。表10－1378从表10－13可知f1(10)=28，x*1=0从而得s2=s1-x*1＝10－0＝10表10－12的s2=10的这一行可知x*2=1，由s3=s2-3x*1＝7查表10－11的s3=7的这一行可知x*3=0，最后由s4=s3-x*3＝7查表10-10的s4=7这一行得x*4=1综上所述得最优解为：x*1=0,x*2=1，x*3=0，x*4=1,最大盈利为28。现在我们不妨假设该咨询公司的工作计划有所改变，只有8个工作日来处理这四类咨询项目，那么该咨询公司如何选择客户使得获利最大呢？我们不必从头开始重做这个问题，而只要在第一阶段上把s1改成8，重新计算就可得到结果，如表10－14所示，这是动态规划的一个好处。79

表10－14

如上一样可从表10－14,10－12,10－11,10－10得到两组最优解如下：

它们的最优解（即最大盈利）都为22。一旦咨询的工作日不是减少而是增加，那么我们不仅要重新计算第一阶段，而且要在第二、第三、第四阶段的计算表上补上增加的工作日的新的信息，也可得到新的结果。80三、生产与存贮问题

例10-4.某公司为主要电力公司生产大型变压器，由于电力采取预订方式购买，所以该公司可以预测未来几个月的需求量。为确保需求，该公司为新的一年前四个月制定一项生产计划，这四个月的需求如表10－15所示。生产成本随着生产数量而变化。调试费为4，除了调度费