管理运筹学课件

管理运筹学绪论线性规划（运输问题）整数规划动态规划存储论排队论对策论决策分析第一章绪论

运筹学（OperationalResearch)直译为“运作研究”运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

运筹学有广泛应用运筹学的产生和发展§1决策、定量分析与管理运筹学决策过程（问题解决的过程）：1）提出问题：认清问题2）寻求可行方案：建模、求解3）确定评估目标及方案的标准或方法、途径4）评估各个方案：解的检验、灵敏性分析等5）选择最优方案：决策6）方案实施：回到实践中7）后评估：考察问题是否得到完满解决1）2）3）：形成问题；4）5）分析问题：定性分析与定量分析。构成决策。§2运筹学的分支线性规划非线性规划整数规划图与网络模型存储模型排队论排序与统筹方法决策分析动态规划预测***多目标规划、随机规划、模糊规划等§3运筹学在工商管理中的应用生产计划：生产作业的计划、日程表的编排、合理下料、配料问题、物料管理等库存管理：多种物资库存量的管理，库存方式、库存量等运输问题：确定最小成本的运输线路、物资的调拨、运输工具的调度以及建厂地址的选择等人事管理：对人员的需求和使用的预测，确定人员编制、人员合理分配，建立人才评价体系等市场营销：广告预算、媒介选择、定价、产品开发与销售计划制定等财务和会计：预测、贷款、成本分析、定价、证券管理、现金管理等***设备维修、更新，项目选择、评价，工程优化设计与管理等运筹学方法使用情况(美1983)运筹学方法在中国使用情况(随机抽样)运筹学的推广应用前景据美劳工局1992年统计预测:

运筹学应用分析人员需求从1990年到2005年的增长百分比预测为73%,增长速度排到各项职业的前三位.结论:运筹学在国内或国外的推广前景是非常广阔的工商企业对运筹学应用和需求是很大的在工商企业推广运筹学方面有大量的工作要做§4如何学习运筹学MBA学员学习运筹学要把重点放在结合实际的应用上，不要被一些概念、理论的困难吓倒，要用好计算机这个强有力的工具。MBA学员学习运筹学要充分发挥自己实践经验丰富和理论联系实际能力强的优势。MBA学员学习运筹学要把注意力放在“入口”和“出口”两头，中间过程尽可能让计算机软件去完成：

“入口”即结合实际问题建立运筹学模型；

“出口”即解决问题的方案或模型的解。MBA学员必须尽快学会使用运筹学教学软件，并借助它来学好本课程。第二章

线性规划的图解法在管理中一些典型的线性规划应用合理利用线材问题：如何下料使用材最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小线性规划的组成：目标函数Maxf或Minf约束条件s.t.(subjectto)

满足于决策变量用符号来表示可控制的因素§1问题的提出例1.某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗以及资源的限制，如下表：问题：工厂应分别生产多少单位甲、乙产品才能使工厂获利最多？线性规划模型：目标函数：Maxz=50x1+100x2

约束条件：s.t.x1+

x2≤3002x1+x2≤400

x2≤250x1,x2≥0对偶线性规划模型一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cn

xn

约束条件：s.t.a11x1+a12x2+…+a1n

xn

≤（=,≥）b1

a21x1+a22x2+…+a2n

xn

≤（=,≥）b2

…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn

≥0标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn

约束条件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+

amnxn

=bm

x1，x2，…，xn

≥0可以看出，线性规划的标准形式有如下四个特点：目标最大化、约束为等式、决策变量均非负、右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:线性规划标准型1.极小化目标函数的问题：设目标函数为

Minf=c1x1

+c2x2

+…+cnxn

(可以)令z＝-f，则该极小化问题与下面的极大化问题有相同的最优解，即

Maxz=-c1x1

-c2x2-…-cnxn

但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即

Minf＝-Maxz线性规划标准型2、约束条件不是等式的问题：设约束条件为

ai1x1+ai2x2+…+ainxn

≤bi可以引进一个新的变量s，使它等于约束右边与左边之差

s=bi–(ai1x1

+ai2x2

+…+

ainxn

)

显然，s

也具有非负约束，即s≥0，

这时新的约束条件成为

ai1x1+ai2x2+…+ainxn+s=bi线性规划标准型当约束条件为

ai1x1+ai2x2+…+ainxn

≥bi时，类似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn-s=bi

线性规划标准型为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。

线性规划标准型

例：将以下线性规划问题转化为标准形式

Minf=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

线性规划标准型解：首先,将目标函数转换成极大化：令z=-f=-3.6x1+5.2x2-1.8x3

其次考虑约束，有2个不等式约束，引进松弛变量x4，x5

≥0。于是，我们可以得到以下标准形式的线性规划问题：

Maxz=-3.6x1

+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9

x1+x2+x3=38

x1,x2,x3,x4,x5

≥0线性规划标准型3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令

xj

=xj’-

xj”其中

xj’≥0，xj”≥0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。线性规划标准型4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi

线性规划标准型例2.3：将以下线性规划问题转化为标准形式Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0线性规划标准型解：首先，将目标函数转换成极大化：令z=-f=3x1–5x2–8x3+7x4

；

其次考虑约束，有3个不等式约束，引进2个松弛变量和1个剩余变量

x5,x6,x7

≥0；由于x2无非负限制，引入两个非负变量，可令x2=x2’-x2”,其中x2’≥0，x2”≥0；

由于第3个约束右端项系数为-58，于是把该式两端乘以-1。于是，我们可以得到以下标准形式的线性规划问题：

线性规划标准型

Maxz=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0

线性规划标准型§2线性规划的图解法例1.目标函数：

Maxz=50x1+100x2约束条件：

s.t.

x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：

x1=50，

x2=250

最优目标值z=27500线性规划图解法的步骤对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解，其步骤如下：

(1)分别取决策变量x1

,

x2

为坐标向量建立直角坐标系。

（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。若各半平面交出来的公共区域存在，显然，其中的点满足所有的约束条件，称这样的点为此线性规划的可行解，全体可行解的集合称为可行集或可行域。若这样的公共区域不存在，则该线性规划问题无可行解。

（3）任意给定目标函数一个确定的值，作出对应的目标函数等值线，并确定该族等值线平行移动时目标函数值增加的方向。然后平移目标函数的等值线，使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无穷远处，此时称无有限最优解）。此时，目标函数等值线与可行域的交点即此线性规划的最优解（一个或多个），此目标函数的值即最优值。进一步讨论线性规划的标准化内容之一：——引入松驰变量（含义是资源的剩余量）

例1中引入s1，s2，s3

模型化为目标函数：Maxz=50x1+100x2+0s1+0s2+0s3

约束条件：s.t.x1+x2+

s1=3002x1+x2+s2=400x2+s3=

250x1,x2,s1,s2,s3≥0

对于最优解

x1=50

x2=250，s1=0s2=50s3=0

说明：生产50单位甲产品和250单位乙产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。

进一步讨论（续）解的性质：

1）线性规划的最优解如果存在，则必定有一个顶点（极点）是最优解；2）有的线性规划问题存在无穷多个最优解的情况；3）有的线性规划问题存在无有限最优解的情况，也称无解；4）有的线性规划问题存在无可行解的情况。§3图解法的灵敏度分析灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci

,aij

,bj

变化时，对最优解产生的影响。3.1目标函数中的系数ci

的灵敏度分析考虑例1的情况，

ci的变化只影响目标函数等值线的斜率，目标函数z=50x1+100x2

在

z=x2(x2=z斜率为0

)

到

z=x1+x2(x2=-x1+z斜率为-1

)之间时，原最优解

x1=50，x2=100仍是最优解。一般情况：

z=c1x1+c2x2

写成斜截式

x2=-(c1/c2)x1+z/c2

目标函数等值线的斜率为-(c1/c2)

当-1-(c1/c2)0（*）时，原最优解仍是最优解假设产品乙的利润100元不变，即c2=100，代到式（*）并整理得

0c1

100假设产品甲的利润50元不变，即c1=50，代到式（*）并整理得

50c2

+假若产品甲、乙的利润均改变，则可直接用式（*）来判断。假设产品甲、乙的利润分别为60元、55元，则

-2-(60/55)

-1那麽，最优解为

z=x1+x2

和

z=2x1+x2

的交点x1=100，x2=200。§3图解法的灵敏度分析（续）3.2约束条件中右边系数bj

的灵敏度分析当约束条件中右边系数

bj变化时，线性规划的可行域发生变化，可能引起最优解的变化。考虑例1的情况：假设设备台时增加10个台时，即b1变化为310，这时可行域扩大，最优解为

x2=250

和

x1+x2=310

的交点

x1=60，x2=250。

变化后的总利润-变化前的总利润=增加的利润(50×60+100×250)-(50×50+100×250)=500，500/10=50元

说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。假设原料A增加10千克时，即b2变化为410，这时可行域扩大，但最优解仍为

x2=250

和

x1+x2=300

的交点x1=50，x2=250。

此变化对总利润无影响，该约束条件的对偶价格为0。解释：原最优解没有把原料A用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。在一定范围内，当约束条件右边常数增加1个单位时1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；3）若约束条件的对偶价格等于0，则其最优目标函数值不变。3.2约束条件中右边系数

bj

的灵敏度分析(续)线性规划问题的计算机求解(1)管理运筹学软件1.0版使用说明：（演示例1）一、系统的进入与退出：1、在WINDOWS环境下直接运行main.exe文件，或者在DOS下UCDOS中文平台环境下运行，也可直接运行各可执行程序。2、退出系统的方法可以在主菜单中选退出项，也可按Ctrl+Break键直接退出。3、在WINDOWS环境下直接运行软件，如果出现乱码，那是因为启用了全屏幕方式，解决办法是按ALT+ENTER键，即可转换成非全屏的界面（一般就会消除乱码，如果还是乱码，可以点击菜单的“汉”选项）；若要每次启动程序都没有乱码，则需要修改屏幕设置的相应属性。具体方法是：在非全屏界面下点击菜单的“属性”选项，再选择“窗口”选项，然后选中其中的“窗口”项，并取消“启动时恢复设置”项，这样就可保证每次运行软件时以非全屏方式显示。

二、输入部分：1、线性规划、整数规划的目标函数和约束的输入必须按由小到大的序号顺序输入，同时约束变量必须放在运算符的左侧。如（x1+x2-x3=0，不能输为x2-x3+x1=0；x1-x2+x3=0，不能输为x1+x3=x2）2、输入的约束中不包括“≥”或“≤”，而是用“>”或“<”代替，这不会影响求解。如对于约束X1≥2,则输入X1>2,而不是X1≥2。线性规划问题的计算机求解(1)续线性规划问题的计算机求解(2)结果考察：（演示例1）1、当目标函数的系数ci单一变化时，只要不超过其上、下限，最优解不变；2、当约束条件中右边系数bj变化时，当其不超过上、下限，对偶价格不变（最优解仍是原来几个线性方程的解）；

3、当有多个系数变化时，需要进一步讨论。百分之一百法则：对于所有变化的目标函数决策系数（约束条件右边常数值），当其所有允许增加的百分比与允许减少的百分比之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原来几个线性方程的解）

*允许增加量=上限-现在值

c1的允许增加量为100-50=50

b1的允许增加量为325-300=25*允许减少量=现在值-下限

c2的允许减少量为100-50=50

b3的允许减少量为250-200=50*允许增加的百分比=增加量/允许增加量*允许减少的百分比=减少量/允许减少量线性规划问题的计算机求解(2)续线性规划问题的计算机求解(3)例：

c1变为74,c2变为78,则(74-50)/50+(100-78)/50=92%，故最优解不变。

b1变为315,b3变为240,则(315-50)/25+(250-240)/50=80%，故对偶价格不变（最优解仍是原来几个线性方程的解）。在使用百分之一百法则进行灵敏度分析时，要注意：1）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允许增加（减少）百分比均看作0；2）百分之一百法则是充分条件，但非必要条件；3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只有重新求解。考虑前面例题的对偶问题：

若设备和原料都用于外协加工，工厂收取加工费。试问：设备工时和原料A、B各如何收费才最有竞争力？

设y1，y2，y3分别为每设备工时、原料A、B每单位的收取费用。线性规划对偶问题

Maxz=50x1+100x2s.t.x1+x2≤3002x1+x2≤400

x2≤250

x1,x2≥0Minf=300y1+400y2+250y3s.t.y1+2y2≥50（不少于甲产品的利润）

y1+y2+y3≥100（不少于乙产品的利润）

y1,y2,y3≥0线性规划对偶问题对偶定义对称形式：互为对偶

(LP)Maxz=cT

x(DP)Minf=bT

y

s.t.

Ax≤bs.t.AT

y≥c

x≥0y≥0

“Max--

≤”“Min--≥”线性规划对偶问题

一对对称形式的对偶规划之间具有下面的对应关系。(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，≤”和“min，≥”相对应。线性规划对偶问题(2)从约束系数矩阵看：一个模型中为Ａ，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。线性规划对偶问题非对称形式的对偶规划一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划:（1）将模型统一为“max，≤”或“min，≥”

的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；线性规划对偶问题（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。

下面对关系（2）作一说明。对于关系（3）可以给出类似的解释。设原规划中第一个约束为等式：

a11x1+…+a1nxn=b1

那么，这个等式与下面两个不等式等价线性规划对偶问题

a11x1+…+a1nxn≥b1a11x1+…+a1nxn≤b1这样，原规划模型可以写成

maxZ=c1x1+∧+cnxn

a11x1+∧+a1nxn≤b1-a11x1-∧-a1nxn≤-b1

Mam1x1+∧+amnxn≤bmxj≥0,j=1,2,∧,m

线性规划对偶问题此时已转化为对称形式，直接写出对偶规划

minf=b1y1’-b1y1’’+b2y2+∧+bmym

a11y1’-a11y1’’∧+am1ym≥c1a12y1’-a12y1’’∧+am2ym≥c2

Ma1ny1’-a1ny1’’∧+amnym≥cn

y1’,,y1’’,y2,∧,ym≥0,y1这里，把y1看作是y1=y1’-y1’’,于是y1没有非负限制，关系（2）的说明完毕。线性规划对偶问题例3.1写出下面线性规划的对偶规划模型：

maxZ=x1-x2+5x3-7x4x1+3x2-2x3+x4=252x1+7x3+2x4≥-602x1+2x2-4x3≤30-5≤x4≤10,x1,x2,≥0,x3没有非负限制解先将约束条件变形为“≤”形式线性规划对偶问题

x1+3x2-2x3+x4=25-2x1-7x3-2x4≤602x1+2x2-4x3≤30x4≤10-x4≤5x1≥0,x2≥0,x3,x4没有非负限制再根据非对称形式的对应关系，直接写出对偶规划线性规划对偶问题minf

=25y1+60y2+30y3+10y4+5y5y1-2y2+2y3≥13y1+2y3≥-1-2y1-7y2-4y3=5y1-2y2+y4-y5=-7y1没有非负限制，y2,y3,y4,y5≥0线性规划对偶问题影子价格——是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。若x*,y*

分别为（LP）和（DP）的最优解，那么，

cT

x*=bT

y*。

根据

f=

bTy*=b1y1*+b2y2*++bmym*

可知

f/bi

=

yi*

yi*

表示

bi

变化1个单位对目标f

产生的影响，称yi*

为bi的影子价格。线性规划对偶问题影子价格的经济含义(1)影子价格是对现有资源实现最大效益时的一种估价企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。线性规划对偶问题(2)影子价格表明资源增加对总效益产生的影响,根据理论“设x0和y0分别为原规划（P）和对偶规划（D）的可行解，当cx0=bty0时，x0,y0分别是两个问题的最优解”可知，在最优解的情况下，有关系：

Z*=f*=b1y1*+b2y2*∧+bmym*根因此，可以将z*看作是bi,i=1,2,…,m的函数，对bi求偏导数可得到：﹠z*

=yi*i=1,2,∧,m﹠bi这说明，如果右端常数增加一个单位，则目标函数值的增量将是：

yi*,i=1,2,∧,m线性规划对偶问题

影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。线性规划对偶问题

需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。

线性规划对偶问题线性规划在工商管理中的应用(1)一、人力资源分配的问题例1．某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：

设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?解：设xi

表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6

约束条件：s.t.x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0线性规划在工商管理中的应用(1)续线性规划在工商管理中的应用(2)一、人力资源分配的问题例2．福安商场是个中型的百货商场，它对售货员的需求经过统计分析如右表：为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？解：设xi(i=1～7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6+x7

约束条件：s.t.x1+x2+x3+x4+x5≥28

x2+x3+x4+x5+x6≥15

x3+x4+x5+x6+x7≥24

x4+x5+x6+x7+x1≥25x5+x6+x7+x1+x2≥19x6+x7+x1+x2+x3≥31

x7+x1+x2+x3+x4≥28

x1,x2,x3,x4,x5,x6,x7≥0线性规划在工商管理中的应用(2)续线性规划在工商管理中的应用(3)二、生产计划的问题例3．明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？解：设x1,x2,x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，

x4,x5

分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。求

xi的利润：利润=售价-各成本之和可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。这样我们建立如下的数学模型。目标函数：Max15x1+10x2+7x3+13x4+9x5

约束条件：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0线性规划在工商管理中的应用(3)续线性规划在工商管理中的应用(4)二、生产计划的问题例4．永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成B工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？解：设xijk

表示第i种产品，在第j种工序上的第k种设备上加工的数量。利润=[（销售单价-原料单价）*产品件数]之和-（每台时的设备费用*设备实际使用的总台时数）之和。这样我们建立如下的数学模型:

Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123

s.t.5x111+10x211≤6000（设备A1）7x112+9x212+12x312≤10000（设备

A2）6x121+8x221≤4000（设备B1）4x122+11x322≤7000（设备B2）7x123≤4000（设备B3）

x111+x112-x121-x122-x123=0（Ⅰ产品在A、B工序加工的数量相等）

x211+x212-x221=0（Ⅱ产品在A、B工序加工的数量相等）

x312-x322=0（Ⅲ产品在A、B工序加工的数量相等）

xijk≥0,i=1,2,3;j=1,2;k=1,2,3线性规划在工商管理中的应用(4)续线性规划在工商管理中的应用(5)三、套裁下料问题例5．某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解：共可设计下列8种下料方案，我们只考虑前5种。设x1,x2,x3,x4,x5分别为上面前5种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5

约束条件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0线性规划在工商管理中的应用(5)续线性规划在工商管理中的应用(6)四、配料问题例6．某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？解：设xij

表示第i种（甲、乙、丙）产品中原料j的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；

对于乙：x21，x22，x23；

对于丙：x31，x32，x33；

对于原料1：x11，x21，x31；

对于原料2：x12，x22，x32；

对于原料3：x13，x23，x33；

目标函数：利润最大，利润=收入-原料支出约束条件：规格要求4个；供应量限制3个。线性规划在工商管理中的应用(6)续线性规划在工商管理中的应用(6续)例6．（续）目标函数：Maxz=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

约束条件：

s.t.0.5x11-0.5x12-0.5x13≥0（原材料1不少于50%）-0.25x11+0.75x12-0.25x13≤0（原材料2不超过25%）0.75x21-0.25x22-0.25x23≥0（原材料1不少于25%）-0.5x21+0.5x22-0.5x23≤0（原材料2不超过50%）

x11+x21+x31≤100(供应量限制）

x12+x22+x32≤100

(供应量限制）

x13+x23+x33≤60(供应量限制）

xij≥0,i=1,2,3;j=1,2,3线性规划在工商管理中的应用(7)五、投资问题例8．某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本利155%，但规定最大投资额不能超过100万元；据测定每万元每次投资的风险指数如下表：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？解：1）确定决策变量：连续投资问题设xij(i=1～5，j=1～4)表示第i年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下的决策变量：

Ax11

x21

x31

x41

x51

Bx12

x22

x32

x42Cx33

Dx24线性规划在工商管理中的应用(7)续线性规划在工商管理中的应用(7续)2）约束条件：第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是

x11+x12=200；第二年：B次年末才可收回投资，故第二年年初有资金1.1x11，于是x21+x22+x24=1.1x11；第三年：年初有资金1.1x21+1.25x12，于是x31+x32+x33=1.1x21+1.25x12；第四年：年初有资金1.1x31+1.25x22，于是

x41+x42=1.1x31+1.25x22；第五年：年初有资金1.1x41+1.25x32，于是

x51=1.1x41+1.25x32；B、C、D的投资限制：xi2≤30(i=1、2、3、4)，x33≤80，x24≤1003）目标函数及模型：a)Maxz=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+x12=200

x21+x22+x24=1.1x11；

x31+x32+x33=1.1x21+1.25x12；

x41+x42=1.1x31+1.25x22；

x51=1.1x41+1.25x32；

xi2≤30(i=1、2、3、4)，x33≤80，x24≤100

xij≥0(i=1、2、3、4、5；j=1、2、3、4）

b)Minf=(x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24s.t.x11+x12=200

x21+x22+x24=1.1x11；

x31+x32+x33=1.1x21+1.25x12；

x41+x42=1.1x31+1.25x22；

x51=1.1x41+1.25x32；

xi2≤30(i=1、2、3、4)，x33≤80，x24≤1001.1x51+1.25x42+1.4x33+1.55x24≥330

xij≥0(i=1、2、3、4、5；j=1、2、3、4）线性规划在工商管理中的应用(7续)运输问题（1）§1运输模型例1、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？运输问题（1）续解：产销平衡问题：总产量=总销量设xij

为从产地Ai运往销地Bj的运输量，得到下列运输量表：

Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1、2；j=1、2、3）运输问题（2）设xij

为从产地Ai运往销地Bj的运输量，得到下列一般运输量问题的模型：

mnMinf=

cijxij

i=1j=1n

s.t.

xij=si

i=1,2,…,m

j=1

m

xij=dj

j=1,2,…,ni=1

xij

≥0(i=1,2,…,m;j=1,2,…,n)一般运输模型：产销平衡

A1、A2、…、Am

表示某物资的m个产地；B1、B2、…、Bn

表示某物质的n个销地；si

表示产地Ai的产量；dj

表示销地Bj的销量；cij

表示把物资为从产地Ai运往销地Bj的单位运价。变化：

1）有时目标函数求最大如求利润最大或营业额最大等；2）当某些运输线路上的能力有限制时，模型中可直接加入（等式或不等式）约束；3）产销不平衡时，可加入虚设的产地（销大于产时）或销地（产大于销时）。运输问题（2）续运输问题（3）§2运输问题的计算机求解例2、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的销地运输费用为0运输问题（3）续例3、某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示，问：应如何调运可使总运输费用最小？解：增加一个虚设的产地运输费用为0运输问题（4）§3运输问题的应用一、产销不平衡的运输问题例4、石家庄北方研究院有一、二、三三个区。每年分别需要用煤3000、1000、2000吨，由河北临城、山西盂县两处煤矿负责供应，价格、质量相同。供应能力分别为1500、4000吨，运价为：

由于需大于供，经院研究决定一区供应量可减少0--200吨，二区必须满足需求量，三区供应量不少于1700吨，试求总费用为最低的调运方案。运输问题（4）续§3运输问题的应用解：根据题意，作出产销平衡与运价表：这里M代表一个很大的正数，其作用是强迫相应的x31、x33、x34取值为0。

运输问题（5）§3运输问题的应用一、产销不平衡的运输问题例5、设有A、B、C三个化肥厂供应1、2、3、4四个地区的农用化肥。假设效果相同，有关数据如下表：

试求总费用为最低的化肥调拨方案。运输问题（5）续§3运输问题的应用解：根据题意，作出产销平衡与运价表：

最低要求必须满足，因此把相应的虚设产地运费取为M，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为0。对应4”的销量50是考虑问题本身适当取的数据，根据产销平衡要求确定D的产量为50。

运输问题（6）§3运输问题的应用二、生产与储存问题例6、某厂按合同规定须于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表。如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。试求在完成合同的情况下，使该厂全年生产总费用为最小的决策方案。运输问题（6）续§3运输问题的应用解：设xij为第i季度生产的第j季度交货的柴油机数目，那末应满足：

交货：x11

=10生产：x11+x12+x13+x14≤25

x12+x22

=15x22+x23+x24≤35x13+x23+x33

=25x33+x34≤30x14+x24+x34+x44=20x44≤10

把第i季度生产的柴油机数目看作第i个生产厂的产量；把第j季度交货的柴油机数目看作第

j个销售点的销量；成本加储存、维护等费用看作运费。可构造下列产销平衡问题：目标函数：Minf=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+11.25x23+11.4x24+11.0x33+11.15x34+11.3x44运输问题（7）§3运输问题的应用二、生产与储存问题例7、光明仪器厂生产电脑绣花机是以产定销的。已知1至6月份各月的生产能力、合同销量和单台电脑绣花机平均生产费用见下表：

已知上年末库存103台绣花机，如果当月生产出来的机器当月不交货，则需要运到分厂库房，每台增加运输成本0.1万元,每台机器每月的平均仓储费、维护费为0.2万元。在7--8月份销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产机器每台增加成本1万元。问应如何安排1--6月份的生产，可使总的生产费用（包括运输、仓储、维护）最少？解：这个生产存储问题可化为运输问题来做。考虑：各月生产与交货分别视为产地和销地1）1--6月份合计生产能力（包括上年末储存量）为743台，销量为707台。设一假想销地销量为36；2）上年末库存103台，只有仓储费和运输费，把它列为的0行；3）6月份的需求除70台销量外，还要80台库存，其需求应为70+80=150台；4）1--6表示1--6月份正常生产情况，1’--6’表示1--6月份加班生产情况。运输问题（7）续§3运输问题的应用运输问题（8）§3运输问题的应用产销平衡与运价表：运输问题（9）例8、腾飞电子仪器公司在大连和广州有两个分厂生产同一种仪器，大连分厂每月生产400台，广州分厂每月生产600台。该公司在上海和天津有两个销售公司负责对南京、济南、南昌、青岛四个城市的仪器供应。另外因为大连距离青岛较近，公司同意大连分厂向青岛直接供货，运输费用如下图，单位是百元。问应该如何调运仪器，可使总运输费用最低？图中1-广州、2-大连、3-上海、4-天津、5-南京、6-济南、7-南昌、8-青岛三、转运问题：

在原运输问题上增加若干转运站。运输方式有：产地转运站、转运站销地、产地产地、产地销地、销地转运站、销地产地等。运输问题（9）续解：设xij

为从i到j的运输量，可得到有下列特点的线性规划模型：

目标函数：Minf=所有可能的运输费用（运输单价与运输量乘积之和）约束条件：对产地（发点）i：输出量-输入量=产量

对转运站（中转点）：输入量-输出量=0对销地（收点）j：输入量-输出量=销量运输问题（10）例8．（续）目标函数：

Minf=2x13+3x14+3x23+x24+4x28+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48

约束条件：

s.t.x13+x14≤600(广州分厂供应量限制）

x23+x24+x28≤450(大连分厂供应量限制）-x13-x23+x35+x36+x37+x38=0（上海销售公司，转运站）-x14-x24+x45+x46+x47+x48=0（天津销售公司，转运站）

x35+x45=200（南京的销量）

x36+x46=150（济南的销量）

x37+x47=350（南昌的销量）

x38+x48+x28=300（青岛的销量）