第一学期数据建模决策课件chapter1lp

第一讲线性规划

(LinearProgramming,LP)概述线性规划问题的提出最早是1939年由前苏联数学家康托洛维奇在研究铁路运输的组织问题、工业生产的管理问题时提出来的。1947年，美国学者丹西格（G.B.Dantzig）提出了线性规划问题的单纯形方法。线性规划理论最为成熟、应用最为广泛

第一节线性规划问题及其数学模型一、问题提出例1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？

产品资源甲乙资源限制ABC120111300kg400kg250kg单位产品利润(元/件)50100决策变量：x1、x2——分别代表甲、乙两种产品的生产数量。目标函数：max

z=50x1+100x2约束条件：x1+x2≤300

2x1+x2≤400x2≤250即有：

max

z=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0称之为上述问题的数学模型。例2

靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小.工厂1工厂2200万m3500万m3决策变量：x1、x2——分别代表工厂1和工厂2处理污水的数量(万m3)。则目标函数：minz=1000x1+800x2约束条件：第一段河流（工厂1——工厂2之间）：

(2－x1)/500≤0.2%第二段河流：[0.8(2－x1)+(1.4－x2)]/700≤0.2%此外有：

x1≤2；x2≤1.4化简有：

minz=1000x1+800x2x1≥10.8x1+x2≥1.6x1≤2x2≤1.4x1、x2≥0称之为上述问题的数学模型。从上述两个例子，我们可以总结出线性规划的数学模型的一般形式。max(min)z=c1x1+c2x2+…+cnxn——目标函数

a11x1+a12x2+…+a1nxn=(≥,≤)b1

a21x1+a22x2+…+a2nxn=(≥,≤)b2——约束条件

…………………

am1x1+am2x2+…+amnxn=(≥,≤)bm

x1，x2，…，xn≥0模型特点：目标函数(Objectivefunction)与约束条件(Constraint)均为线性的；目标函数实现极大化或极小化。

第二节线性规划图解法

(GraphicalSolution)一、基本概念可行解(FeasibleSolution)——任一满足约束条件的一组决策变量的数值；可行域(FeasibleRegion)——所有可行解组成的集合，也称为可行解集；目标函数等值线(Objectivefunctionline)——为于同一直线上的点，具有相同的目标函数值；二、图解法步骤(Procedure)（1）画出线性规划问题的可行域；（2）画出两条目标函数等值线；（3）平行移动目标函数等值线，使目标函数在可行域范围内达到最优。三、图解法举例例1maxZ=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0x2x1z*=27500z1=50x1+100x2=0BOACDz2=14000该问题有唯一最优解x1=50；x2=250x1+x2≤3002x1+x2≤400x2≤250例2maxZ=50x1+50x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0x2x1z1=50x1+50x2=0B点和C点所代表的坐标同时为最优解，即该问题有无穷多最优解BOACDx1+x2≤3002x1+x2≤400x2≤250maxZ=50x1+100x2z*=27500z2=15000例3maxz=x1+x2x1－x2≥1

－x1+2x2≤0x1、x2≥0

问题有无界解

(unbounded)例4

minz=x1+x2x1－x2≥1

－x1+2x2≤0x1、x2≥0

有唯一最优解1－11z=32z=5OAx1－x2≥1－x1+2x2≤0例4maxz=x1+x2

－x1+2x2≥1x1+x2≤－2x1、x2≥0

问题无可行解

(nofeasiblesolution)直观结论可行域可以是个凸多边形，可能无界，也可能为空；若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到；若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即LP有无穷多最优解；若可行域非空有界，则一定有最优解。四、线性规划问题的标准形式(Standardform)规定如下形式的线性规划数学模型为LP标准形式。maxz=c1x1+c2x2+…+cnxn ——目标函数

a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2——约束条件

………

am1x1+am2x2+…+amnxn=bm

x1，x2，…，xn≥0特点：Z——max；约束条件为等号；变量非负；右端常数项大等于零。问题：n>

mwhy？上述标准形式的线性规划模型还可写成如下一些形式:(1)

(2)

(3)(5)(4)

五、化非标准形为标准形（1）若minf=cX此时可令：z=－f，则maxz=－minf=－cX，这样处理所得最优解不变；举例：

minz=－x1－x22x1+x2≤2

－x1+x2≤1x1、x2≥0maxf=x1+x2z=-1/2f=0f=1/2z=0f=-z=8/3（1/3，4/3）(2)约束条件为“≤”时，∑aijxj≤bi→∑aijxj+xn+i=bi

xn+i——松弛变量(slackvariable)；(3)约束条件为“≥”时，∑aijxj≥bi→∑aijxj

－xn+i=bi

xn+i——过剩变量(surplusvariable)；这样处理所得最优解不变；max

z=x1+10x2x1+2x2≤100x1、x2≥0max

z=x1+10x2x1+2x2+x3=100x1、x2≥0（4）若xk为无限制，则令xk=xk1－xk2，其中xk1、xk2≥0（5）若bi<0，则－bi>0举例:化下列线性规划为标准形

max

z=2x1+2x2－4x3x1+3x2－3x3≥30x1+2x2－4x3≤80x1、x2≥0，x3无限制max

z=2x1+2x2－4x3’+4x3”x1+3x2－3x3’+3x3”

–x4=30x1+2x2－4x3+4x3”+x5=80x1、x2、x3’、x3”

、x4、x5≥0第三节线性规划的计算机求解

(ComputerSolutionforLP)一、用计算机求解下列线性规划问题maxz=50x1+100x2x1+x2<=3002x1+x2<=400x2<=250x1、x2≥0二、派公司生产计划问题的LP模型与计算机求解派公司计划生产高中价位的高尔夫袋。生产过程为：1.切割并印染原材料；2.缝合；3.成型；4.检查和包装。各过程单位用时、总用时及产品单位利润如下表：如何生产使公司利润最大？过程生产耗时总时间标准袋高档袋切割并印染缝合成型检查和包装7/101/211/1015/62/31/4630600708135单位产品利润109解：很显然，若设x1、x2——分别代表标准袋和高档袋的生产数量,则问题的数学模型为：

max

z=10x1+9x2

7/10x1+x2<=6301/2x1+5/6x2<=600x1+

2/3x2<=7081/10x1+1/4x2<=135x1、x2≥0三、M&D公司问题问题描述:M&D公司生产两种产品A和B，根据现有库存水平和下个月的购买潜力分析，M&D管理层确定A和B的总产量至少达到350加仑。此外公司的一个主要客户订购了125加仑的产品A，该产量必须满足。产品A和产品B的制造时间分别是2小时/加仑和1小时/加仑，下个月的总工作时间是600小时。公司的目标是在满足客户要求的前提下，尽量降低成本。每加仑A的制造成本是2美元，每加仑B的制造成本是3美元。很显然，若设x1、x2——分别代产品A和产品B的生产数量,则问题的数学模型为：

minz=2x1+3x2x1>=125

x1+x2>=

350

2x1+

x2<=600x1、x2≥0第四节对偶问题(DualProblem)线性规划早期发展过程中的最为重要的理论成果之一就是线性规划的对偶问题及相关理论的提出。线性规划的对偶理论解释资源的影子价格、线性规划问题的敏度分析等的理论基础。一、对偶问题的提出例1

（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？

产品资源甲乙资源限制ABC120111300kg400kg250kg单位产品利润(元/件)50100决策变量：x1、x2——分别代表甲、乙两种产品的生产数量。即有数学模型（问题A）：问题Amax

z=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0称之为上述问题的数学模型。同样是上述问题，提问：企业不安排生产，而转让三种资源，应如何给三种资源定价？决策变量：y1、y2、y3——分别代表A、B、C三种资源的价格（最低转让净收入）。约束条件1：生产一件产品甲所耗资源数量转让所得净收入不能低于一件产品甲所获利润，即：

1y1+2y2≥50约束条件2：生产一件产品乙所耗资源数量转让所得净收入不能低于一件产品乙所获利润，即：

1y1+1y2+1y3≥100目标函数为：w=300y1+400y2+250y3即有

w=300y1+400y2+250y3y1+2y2≥50y1+y2+y3≥100y1、y2、y3≥0从数学和经济的角度分析，该问题的目标函数只能极小，即该问题的数学模型为：问题Bminw=300y1+400y2+250y3y1+2y2≥50y1+y2+y3≥100y1、y2、y3≥0称问题B为问题A的对偶问题，问题A为原问题。问题Amaxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0定义2.1

设有线性规划问题

maxz=CXAX≤bX≥0其对偶问题定义为

minw=YbYA≥CY≥0且前者称为原问题，后者称为对偶问题。二、对偶问题的定义具体的数量对应关系为原问题maxz=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2…………

am1x1+am2x2+…+amnxn≤bmx1，x2，…，xn≥0对偶问题

minw=b1y1+b2y2+…+bmym

a11y1+a21y2+…+am1ym≥c1a12y1+a22y2+…+am2ym≥c2…………

a1ny1+a2ny2+…+amnym≥cny1，y2，…，ym≥0根据对偶问题的定义不难推出，对于线性规划问题：

minw=Yb；YA≥C；Y≥0其对偶问题为：

maxz=CX；AX≤b；X≥0即两线性规划问题互为对偶。事实上，任一线性规划问题都有一个固定的线性规划问题与之对偶，且二者互为对偶关系，线性规划的这种性质称为对称性。更进一步有，对于线性规划问题：

maxz=CX；AX=b，X≥0其对偶问题为：

minw=Yb；YA≥C，Y无限制根据以上分析，线性规划原问题与对偶问题的数量关系可用下表描述。原问题（或对偶问题）对偶问题（或原问题）目标函数maxzminw目标函数变量n个≥0≤0无约束n个≥≤=约束条件约束条件m个≤≥=m个≥0≤0无约束变量约束条件右端常数项目标函数变量系数目标函数变量系数约束条件右端常数项例2.1写出下列线性规划问题的对偶问题

maxz=2x1+2x2－4x3 x1+3x2+3x3≤30 4x1+2x2+4x3≤80 x1、x2，x3≥0解：其对偶问题为minw=30y1+80y2y1+4y2≥23y1+2y2≥23y1+4y2≥－4y1、y2≥0例2.2写出下列线性规划问题的对偶问题

minz=2x1+8x2－4x3x1+3x2－3x3≥30

－x1+5x2+4x3=804x1+2x2－4x3≤50x1≤0、x2≥0，x3无限制解：其对偶问题为maxw=30y1+80y2+50y3

y1－y2+4y3≥23y1+5y2+2y3≤8

－3y1+4y2－4y3=－4y1≥0，y2无限制，y3≤0定理2.1(弱对偶定理)

设X(0)是原问题maxz=CX，AX≤b，X≥0的可行解

Y(0)是其对偶问题minw=Yb，YA≥C，Y≥0的可行解则CX（0）≤Y（0）b。原问题任一可行解对应的目标函数值不大于其对偶问题的任一可行解对应目标函数值???三、对偶问题基本定理定理2.2(最优性定理)

设X(0)是原问题maxz=CX，AX≤b，X≥0的可行解，

Y（0）是其对偶问题minw=Yb，YA≥C，Y≥0的可行,若CX（0）=Y（0）b，则X（0）、Y（0）分别是它们的最优解。定理2.3(对偶定理)

若原问题maxz=CX，AX≤b，X≥0有最优解，则其对偶问题minw=Yb，YA≥C，Y≥0一定有最优解，且二者的目标函数值相等。定理2.4(互补松弛定理)

原问题maxz=CX，AX≤b，X≥0及其对偶问题minw=Yb，YA≥C，Y≥0

的可行解X（0）、Y（0）是最优解的充要条件是

Y（0）XS=0；YSX（0）=0

其中，XS、YS分别是原问题松弛变量向量和对偶问题剩余变量向量。（一）资源的影子价格(ShadowPrice)

如前所述，若X*为线性规划maxz=CX，AX≤b，X≥0的最优解，则z*=CX*；若Y*为其对偶问题的最优解，则有w*=Y*b。根据对偶定理有

z*=w*

即z*=Y*b

因此即由此可以看出，对偶问题的最优解实际上是右端常数项的单位变化所引起的目标值的变化；四、对偶问题的经济意义若原问题描述的是资源有限条件下最优生产决策问题，则其对偶问题的最优解yi*(i=1,…，m)表示第i种资源在最优生产决策下的边际值，即若其他条件不变，增加单位第i种资源将会使目标函数值增加yi*。其经济意义是：yi*描述了第i种资源在具体生产中的一种估价，这种估价不同于该种资源的市场价格，而是该种资源在给定条件某生产的最优生产方案下的一种实际存在而又看不见的真实价值，因此称之为影子价格（shadowprice）。同一种资源在不同的生产条件或不同的范围可能有不同的影子价格；产品的市场价格变化，资源的影子价格也会发生变化；资源的数量结构不同，资源的影子价格也不同。资源的影子价格是针对具体生产或具体企业而言的与资源的市场价格比较以决定是否安排生产或转让资源或提高产品的价格；革新可以提高资源的影子价格；可以指导管理部门对紧缺资源进行“择优分配”；帮助预测产品的价格。因此，产品的价格应在“成本”和影子价格之间；影子价格的高低可以作为同类企业经济效益的评估标准之一。影子价格对于拥有资源的决策者有非常重要的作用对于目标函数极小化约束条件为大等号的问题

minz=CX，AX≥b，X≥0，其右端常数项可理解为需要完成的任务。因此，该类线性规划一般为描述完成一定任务使耗费的资源最小的问题。此时，其对偶问题的最优解yi*(i=1,…，m)表示第i种任务的边际成本，即单位任务的增加引起的资源耗费的增加量。（二）任务的边际成本

(MarginalCost)M&D公司生产两种产品A和B，根据现有库存水平和下个月的购买潜力分析，M&D管理层确定A和B的总产量至少达到350加仑。此外公司的一个主要客户订购了125加仑的产品A，该产量必须满足。产品A和产品B的制造时间分别是2小时/加仑和1小时/加仑，下个月的总工作时间是600小时。公司的目标是在满足客户要求的前提下，尽量降低成本。每加仑A的制造成本是2美元，每加仑B的制造成本是3美元。问题的线性规划模型为

minz=2x1+3x2x1>=125

x1+x2>=

350

2x1+

x2<=600x1、x2≥0无论对偶问题的最优解表示的是资源的影子价格还是任务的边际成本，只要为正，则表示右端常数项增加目标函数值增加，为负则表示右端常数项增加目标函数值减少。而对于极大化的问题，目标函数值增加表明目标函数得到改善，对于极小化的问题，目标函数减少表明目标函数得到改善。为了二者的统一，定义如下对偶价格。（三）对偶价格(DualPrice)定义2.2

线性规划问题某约束条件的右端常数项的单位增加量所引起的目标函数的改善量称为该右端常数项的对偶价格。因此，若对偶价格为正，则增加右端常数项，目标函数值得到改善；若对偶价格为负，则增加右端常数项，目标函数值将会“恶化”。（三）对偶价格(DualPrice)

第五节、灵敏度分析

(SensitivityAnalysis)灵敏度分析就是分析aij、bi、cj等因素中的一个或几个的变化给生产决策带来的影响。灵敏度分析的内容是：aij、bi、cj中一个或几个发生某一具体变化时，线性规划问题的最优决策相应会发生什么样的变化；aij、bi、cj在什么范围内变化，线性规划问题的最优解或最优基不变；灵敏度分析一般是在已得到线性规划问题最优基的基础上进行的。例

（生产计划问题）某工厂在计划期内用资源A、B、C安排生产甲、乙两种产品，有关数据如下：

maxz=5x1+4x2

x1+3x2<=902x1

+x2<=80

x1

+x2<=45x1、x2，x3≥0

产品资源甲乙资源限制ABC12131190kg80kg45kg单位产品利润(千元/件)54若x1、x2分别表示工厂生产甲、乙产品的数量，则使工厂获得最大利润的生产计划数学模型为：该问题的计算机求解结果如下目标函数最优值为：215变量最优解检验数

x1350

x2100约束松弛/剩余变量对偶价格

1250

201

303目标函数系数范围（最优解不变）变量下限当前值上限

x1458

x22.545右端常数项范围（对偶价格不变）约束下限当前值上限

16590

无上限

2

67.58090

3404550

maxz=5x1+4x2x1+3x2<=902x1

+x2<=80

x1

+x2<=45x1、x2，x3≥0

（一）、派公司的灵敏度分析

1、原问题计算机求解派公司计划生产高中价位的高尔夫袋。生产过程为：1.切割并印染原材料；2.缝合；3.成型；4.检查和包装。各过程单位用时、总用时及产品单位利润如下表：如何生产使公司利润最大？过程生产耗时总时间标准袋高档袋切割并印染缝合成型检查和包装7/101/211/1015/62/31/4630600708135单位产品利润109灵敏度分析与解答举例

解：很显然，若设S、D——分别代表标准袋和高档袋的生产数量,则问题的数学模型为：

maxz=10S+9D7/10S+D

<=6301/2S+5/6D

<=600S

+2/3D

<=7081/10S+1/4D

<=135S、D≥02.对派公司问题的修改——增加小型袋现管理层希望生产一种小巧的、击球者可以自己背着的高尔夫袋。设计部门计算后得出小型袋在各过程中所耗时间为：切割印染0.8h、缝合1h、成型1h、检验包装0.25h。单位利润：12.85美元/个；设L为小型袋的个数，则新的模型为：maxz=10S+9D+12.85L7/10S+D+0.8L

<=6301/2S+5/6D

+L<=600S

+2/3D+L<=7081/10S+1/4D+0.25L<=135S、D、L≥03.对派公司问题的修改——增加约束条件现管理层无法接受高档袋为零的事实。于是就增加约束条件，即高档袋至少是标准袋的30%，于是有新的模型为：maxz=10S+9D+12.85L7/10S+D+0.8L

<=6301/2S+5/6D

+L<=600S

+2/3D+L<=7081/10S+1/4D+0.25L<=135-0.3S+D>=0S、D、L≥0灵敏度分析与解答举例

二、牧草农场问题——极小化问题（P69）计算机求解与解释（科学管理的实际应用P77）三、电子通讯公司问题——等式约束（P73），自己看第六节线性规划的应用(ApplicationsofLP)线性规划是管理决策制定的最成功的数量方法之一。它广泛应用于化工、航空、钢铁、石油和其他工业。它研究的问题是多种多样的——生产计划、媒体选择、金融计划、资金预算、运输、工厂选择、生产组合、人员调配等等。例红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？时间所需售货员星期日星期一星期二星期三星期四星期五星期六28人15人24人25人19人31人28人一、人力资源分配问题解：设x1为星期一开始上班的人数，x2为星期二开始上班的人数，……，x7星期日开始上班的人数。我们就可得到如下的数学模型：

minx1+x2+x3+x4+x5+x6+x7x3+x4+x5+x6+x7≥28x4+x5+x6+x7+x1≥15x5+x6+x7+x1+x2≥24x6+x7+x1+x2+x3≥25x7+x1+x2+x3+x4≥19x1+x2+x3+x4+x5≥31x2+x3+x4+x5+x6≥28x1、x2、x3、x4、x5、x6、x7≥0该问题的最优解为：x1=8，x2=0，x3=12，x4=0，x5=11，x6=5，x7=0；目标函数的最小值为36。媒体被告知的潜在顾客数（人/次）广告费用（元/次）媒体最高使用次数（次）每次宣传的质量日间电视夜间电视日报周末新闻杂志电台广播10002000

10001001510254306590406020例

某房地产开发公司正在建造一个湖边小区，公司准备投入3万元进行广告媒体宣传，希望能够吸引周围的中高收入家庭前来购房。目前有5种媒体可供选择，相关信息如表所示。对于这次活动，公司有下列要求：至少进行10次电视广告；至少有5万名潜在顾客被告知；电视广告投入不超过18000元。如何进行媒体组合，才能使广告质量最高？二、媒体选择解问题中媒体组合实际上就是要决定每种媒体的使用次数。设x1、x2、x3、x4、x5分别表示表中日间电视、夜间电视、日报、周末新闻杂志、电台广播五种媒体的使用次数。该问题的线性规划模型为maxz=65x1+90x2+40x3+60x4+20x51500x1+3000x2+400x3+1000x4+100x5≤30000

1000x1+2000x2x3+2500x4+300x5≥50000x1+x2≥101500x1+3000x2≤18000x1≤15x2≤10

x3 ≤25

x4≤4

x5≤30

x1，x2，x3，x4，x5≥0这是一个有5个变量，9个约束条件的线性规划模型，求解结果如下：媒体最佳播放次数（次）广告费用（元）日间电视1015000日报2510000周末新闻杂志22000电台广播303000被告知的顾客数=61500人产品宣传质量=2370目标函数最优值为：2370变量最优解检验数

x1100

x20－65

x3250

x420

x5300约束松弛/剩余变量对偶价格

10

0.06

2115000

30－25

430000

550

6100

7016

820

9014包括：资本预算、资产分配、财政计划等（一）投资组合问题：从多种投资选择中选择具体的投资：股票和债券、基金、保险等；目标：预期收益极大化、风险最小化约束：投资类型、国家法律、公司政策、风险或效益限制等三、财政应用案例

Welte公司拥有100000美元，财务专家确定了如下5个投资机会，并预计了它们的年收益：1.在石油或钢铁行业投资不能超过50000每元；2.对政府债券的投资至少相当于对钢铁行业投资的25%；3.对太平洋石油的投资不能多于整个石油行业投资的60%求预期收益最大的投资方案。投资预期收益率（%）大西洋石油太平洋石油中西部钢铁Huber钢铁政府债券7.310.36.47.54.5设：Atl=大西洋石油投资；Pac=太平洋石油投资；

Mid=中西部钢铁投资；Hub=Huber钢铁投资；Gov=政府债券投资则问题的数学模型为：

Maxz=0.073Atl+0.103Pac+0.064Mid+0.075Hub+0.045GovAtl+Pac+Mid+Hub+Gov=100000总投资

Atl+Pac≤50000石油投资限制

Mid+Hub≤50000钢铁投资限制

-0.25Mid–0.25Hub+Gov≥0政府债券比例

-0.6Atl+0.4Pac≤0太平洋石油限制

Atl,Pac,Mid,Hub,Gov≥0(二)、金融计划案例某公司现有68名员工申请提前退休。公司必须在此后的8年内对这些员工分期支付一定数量的现金，如下表所示。 为了完成这项现金支付任务，公司的财务人员必须现在就为此制定一个投资计划。投资计划有政府债券投资和银行储蓄两种方式组成。年份（年）12345678合计现金支付(千元)4302102222312401952252552008注意:三种政府债券的票面价值均为1000元，债券到期时按票面价值进行支付，利率的计算也以票面的价值为基准。银行储蓄年利率为4%。如何安排投资计划，使公司以最小的投资额完成对退休员工的现金支付任务？政府债券投资有三种债券类型可供选择，如下表所示。债券价格（元）利率（%）到期年限111508.8755210005.50063135011.7507解：1．确定决策变量设F为完成投资计划所需要的总资金额。x1、x2、x3分别表示债券1、2、3的购买量；yi(i=1,…，8)表示第i年初银行储蓄的投资额。2．确定约束条件这类问题的一个典型特征就是每年现金支付的一般表达式为：年初可用资金额–当年用于债券和储蓄的资金额

=当年现金支付于是有

F–1.15x1–1x2–1.35x3–y1=430

（第1年）对于第二年，用于三种债券投资的第一年利息加上第一年储蓄利息为年初可用资金，第二年用于储蓄的资金为y2，因此有

0.08875x1+0.055x2+0.1175x3+1.04y1–y2=210（第2年）同理对于其它年份有0.08875x1+0.055x2+0.1175x3+1.04y2–y3=222（第3年）0.08875x1+0.055x2+0.1175x3+1.04y3–y4=231（第4年）0.08875x1+0.055x2+0.1175x3+1.04y4–y5=240（第5年）1.08875x1+0.055x2+0.1175x3+1.04y5–y6=195（第6年）

1.055x2+0.1175x3+1.04y6–y7=225（第7年）

1.1175x3+1.04y7–y8=255（第8年）因此事实上，y8的值应为0，若大于0，那么对应的投资计划必定不是最优的。3.确定目标函数目标就是使满足要求的投资额最小，即Minz=F综合有如下数学模型

Minz=FF–1.15x1–1x2–1.35x3–y1=4300.08875x1+0.055x2+0.1175x3+1.04y1–y2=2100.08875x1+0.055x2+0.1175x3+1.04y2–y3=2220.08875x1+0.055x2+0.1175x3+1.04y3–y4=2310.08875x1+0.055x2+0.1175x3+1.04y4–y5=2401.08875x1+0.055x2+0.1175x3+1.04y5–y6=1951.055x2+0.1175x3+1.04y6–y7=225

1.1175x3+1.04y7–y8=255x1，x2，x3≥0，yi≥0，i=1，…，8该线性规划模型的求解结果为目标函数最优值为：1728.794变量最优解检验数

F1728.794

0

x1144.9880

x2187.8560

x3228.1880

y1636.1480

y2501.6060

y3349.6820

y4182.6810

y500.064

y600.0126

y700.0213

y800.671即得到最佳投资计划如下表所示:债券购买量投资额(千元)年份储蓄额(千元)1144.9881.150×144.988=166.7361636.1482187.8561.000×187.856=187.8562501.6063228.1881.350×228.188=308.0543349.682总投资额F=1728794元4182.681

5～80

约束松弛/剩余变量对偶价格

10－1.000

20－0.962

30－0.925

40－0.889

50－0.855

60－0.760

70－0.719

80－0.671结果分析：前4年的储蓄额均大于0，可见从第6年起债券的利息和债券到期收入才能够完全满足当前现金支付需要。每一个约束条件的对偶价格均为负值，说明减少任何一年的现金支付都将有利于公司总投资额的降低。对偶价格的逐年降低也说明了，在前面年份减少现金支付将对总投资额的减少更为有效。从而暗示了公司可以适当减少前面年份的现金支付量，而在后面年份进行补足。

(一)制造或购买决策案例P98

某公司有Ⅰ，Ⅱ两种产品，预计两种产品的市场需求量分别为3000件和2000件。两种产品均由a、b、c三个部件组成，各部件生产消耗工时和自制/外购成本如下表所示。部件单位部件制造工时（分钟）自制成本（元/分钟）购买成本（元/小时）A1.00.500.60B产品Ⅰ3.03.754.00产品Ⅱ2.53.303.90C产品Ⅰ1.00.600.65产品Ⅱ1.50.750.78四、生产管理应用部件单位部件制造工时（分钟）自制成本（元/分钟）购买成本（元/小时）A1.00.500.60B产品Ⅰ3.03.754.00产品Ⅱ2.53.303.90C产品Ⅰ1.00.600.65产品Ⅱ1.50.750.78由于生产能力有限，公司只有200个正常制造工时和50个加班工时可用于这两种产品的生产。每个加班工时需额外支付9元。如何安排部件自制和外购的数量，从而使总成本（包括生产成本、外购成本和加工费用）最低？解：1．确定决策变量设xa、xb1、xb2、xc1、xc2分别表示a部件、用于产品Ⅰ的b部件、用于产品Ⅱ的b部件、用于产品Ⅱ的c部件、用于产品Ⅱ

的c部件的自制量。相应地，设ya、yb1、yb2、yc1、yc2分别为各部件的外购量。设y0为加班工时数。

2．确定约束条件a部件的需求量约束xa+ya=5000用于产品Ⅰ的b部件的需求量约束xb1+yb1=3000用于产品Ⅱ的b部件的需求量约束xb2+yb2=2000用于产品Ⅰ的c部件的需求量约束xc1+yc1=3000用于产品Ⅱ的c部件的需求量约束xc2+yc2=2000最大加班工时数约束y0≤50最大生产能力约束

xa+3xb1+2.5xb2+xc1+1.5xc2≤200×60+60y03．确定目标函数目标是使总成本最小，即Minz=0.5xa+0.6ya+3.75xb1+4yb1+3.3xb2+3.9yb2+0.6xc1+0.65yc1+0.75xc2+0.78yc2+9y0因此，该问题的数学模型为Minz=0.5xa+0.6ya+3.75xb1+4yb1+3.3xb2+3.9yb2+0.6xc1+0.65yc1+0.75xc2+0.78yc2+9y0xa+ya=5000xb1+yb1=3000xb2+yb2=2000xc1+yc1=3000xc2+yc2=2000y0≤50xa+3xb1+2.5xb2+xc1+1.5xc2

－60y0≤12000xa、xb1、xb2、xc1、xc2、yb1、yb2、yc1、yc2、y0≥0该线性规划模型的求解结果为目标函数最优值为：1728.794变量最优解检验数

xa5000

0.000

ya

00.017

xb1

667

0.000

ybl

23330.000

xb2

2000

0.000

yb2

0

0.392

xc1

0

0.033

yc1

3000

0.000

xc2

0

0.095

yc2

2000

0.000

y0

0

4.000约束松弛/剩余变量对偶价格

10－0.583

20－4.000

30－3.508

40－0.650

50－0.780

6500.000

700.083部件自制量（件）购买量（件）a50000b产品Ⅰ6672333产品Ⅱ20000c产品Ⅰ03000产品Ⅱ02000总成本=24，443.33元目标函数系数范围变量下限当前值上限

xa

无下限

0.5000.517

ya0.5830.600无上限

xb13.700

3.7503.850

ybl

3.9004.0004.050

xb2

无下限

3.3003.692

yb23.5083.900无上限

xc10.567

0.600无上限

yc1

无下限

0.6500.683

xc2

0.655

0.750无上限

yc2

无下限

0.7800.875

y0

5.000

9.000无上限右端常数项范围约束下限当前值上限

10.0005000

7000

2666.6673000无上限

30.00020002800

40.0003000

无上限

5

0.0002000

无上限

60.00050无上限

7

10000.00012000

19000(二)生产计划问题生产计划问题是线性规划应用最为广泛的领域之一;问题描述:一定时期内，经理必须决定生产水平，使公司能够满足生产需求，在受到产品生产量、劳动力水平以及存储空间上所有限制的同时，还要使生产成本最小。线性规划解决该类问题的优点：可重复利用已建立好的线性规划模型指定不同时期的生产计划。案例P100Bollinger电子公司接到未来三个月的两种产品的定单：生产部门分析，生产费用有以下方面：（1）生产成本；（2）库存储成本；（3）改变生产力水平所需费用。有关数据如下表组件需求生产成本(美元/件)存储成本(美元/件·月）改变生产力费用(美元/件)四月五月六月322A802B1000100030005005000300020100.30.15增加：0.5减少：0.2现要求制定一个未来3个月的生产计划，使总成本最小。Bollinger公司生产力、劳动力能力和库存能力月份生产能力(h)劳动力能力(h)库存能力（面积）四月五月六月400500600300300300100001000010000单位组件对生产机器、劳动力和存储的要求组件机器(h/单位)劳动力(h/单位)库存(面积/单位)322A802B0.100.080.050.0723决策变量（能描述问题）：

x1i=第i月生产322A的数量；i=1，2，3(四、五、六月)x2i=第i月生产802B的数量；i=1，2，3s1i=第i月末322A的存储量；i=1，2，3s2i=第i月末802B的存储量；i=1，2，3Ii=第i月生产量增加量；i=1，2，3Di=第i月生产量下降量；i=1，2，3

目标函数

minz=20x11+20x12+20x13+10x21+10x22+10x23

+0.3s11+0.3s12+0.3s13+0.15s21+0.15s22+0.15s23

+0.5I1+0.5I2+0.5I3+0.2D1+0.2D2+0.2D3约束条件（1）需求约束上月期末库存+本月生产量–本月期末库存=本月需求量第一个月：设期初库存为：322A：500；802B：200；这样有：

500+x11-s11=1000→x11-s11=500200+x21-s21=1000→x11-s11=800

第二个月

s11+x12–s12=3000s21+x22–s22=500第三个月

s12+x13–s13=5000s22+x23–s23=