第2章-线性规划的图解法

会计学1第2章__线性规划的图解法

线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式继续返回第一节线性规划问题

及其数学模型第1页/共63页问题的提出例1:生产计划问题第2页/共63页产品I产品2如何安排生产使利润最大？第3页/共63页决策变量（Decisionvariables）目标函数（Objectivefunction）约束条件（Constraintconditions）可行域（Feasibleregion)最优解（Optimalsolution)基本概念问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。可行域中使目标函数达到最优的决策变量的值第4页/共63页是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。第1步-确定决策变量设——I的产量

——II的产量

——利润第5页/共63页第2步--定义目标函数MaxZ=x1+x2决策变量第6页/共63页

MaxZ=50

x1+100

x2价值系数第2步--定义目标函数第7页/共63页对我们有何限制?第8页/共63页第3步--表示约束条件

x1+x2

300

2

x1+x2

400

x2

250x1、x2

0第9页/共63页该计划的数学模型

目标函数MaxZ=50x1+100x2约束条件x1+x2

300

2x1+x2

400

x2

250x1、x2

0x1

x2第10页/共63页

例2:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：

产品甲产品乙设备能力/h设备A3265设备B2140设备C0375利润/（元/件）15002500

第11页/共63页

问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。

对设备A：两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3

x1

+2x2

≤65；对设备B：两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2x1

+x2

≤40；第12页/共63页

对设备C

：两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2

≤75；另外，产品数不可能为负，即x1,x2≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：

z

=1500x1

+2500x2

综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：第13页/共63页目标函数Maxz=1500x1+2500x2

约束条件

s.t.3x1+2x2≤652x1+x2≤403x2≤75

x1,x2≥0

第14页/共63页线性规划问题的共同特征一组决策变量X表示一个方案,一般X大于等于零。约束条件是线性等式或不等式。目标函数是线性的，求目标函数最大化或最小化第15页/共63页建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，…，xn

），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件第16页/共63页

线性规划模型的一般形式第17页/共63页线性规划问题的标准形式标准形式为:目标函数最大约束条件等式决策变量非负右端项非负第18页/共63页

标准形式可以简写为第19页/共63页线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:第20页/共63页1、极小化目标函数的问题：设目标函数为

Minf=c1x1

+c2x2

+…+cnxn

则可以令z

＝-f

，该极小化问题与下面的极大化问题有相同的最优解，即

Maxz=-c1x1

-c2x2-…-cnxn

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

Minf

＝-Maxz一般线性规划问题的标准形化第21页/共63页

2、约束条件不是等式的问题“”约束：加入非负松驰变量例：

目标函数MaxZ=2x1+3x2约束条件x1+

2x2

84x1

164x2

12x1、x2

0第22页/共63页

例：第23页/共63页例：将以下线性规划问题转化为标准形式

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

当“”

约束：减去非负剩余变量；

第24页/共63页其次考虑约束，有2个不等式约束，引进松弛变量x4≥0

，剩余变量x5

≥0。于是，我们可以得到以下标准形式：

Max

z=-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第25页/共63页3.变量无符号限制的问题：在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令

xj=xj’-xj”其中

xj’≥0，xj”≥0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。第26页/共63页

例：Max第27页/共63页

解：标准形为第28页/共63页4.右端项有负值的问题：在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn=-bi。第29页/共63页练习题：将以下线性规划问题转化为标准形式

Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

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

x1,x3,x4

≥0第30页/共63页解：首先，将目标函数转换成极大化：令z=-f=3x1–5x2–8x3+7x4

；其次考虑约束，有3个不等式约束，引进松弛变量x5,x6,x7

≥0

；由于x2无非负限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0

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

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

第32页/共63页例：将以下线性规划问题转化为标准形式

Minf=2x1-3x2+4x3s.t.3x1

+4x2-5x3≤62x1+x3≥8

x1+x2+x3=-9

x1,x2,x3

≥0

第33页/共63页解：首先,将目标函数转换成极大化：令z=-f=-2x1+3x2-4x3

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

≥0。第三个约束条件的右端值为负，在等式两边同时乘-1。第34页/共63页通过以上变换，可以得到以下标准形式的线性规划问题：

Maxz=-2x1+3x2-4x3s.t.3x1+4x2-5x3+x4=62x1+x3-x5=8-x1-x2-x3=9

x1,x2,x3,x4,x5

≥0第35页/共63页练习建立LP数学模型有两个煤厂A、B，每月分别供应三个居民区X、Y、Z。求运费最少的方案。第36页/共63页例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§2图解法

对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：第37页/共63页§2图解法

(1)分别取决策变量X1,X2

为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。第38页/共63页x2x1X2≥0X2=0x2x1X1≥0X1=0第39页/共63页（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。第40页/共63页100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第41页/共63页100100x2≤250x2=250200300200300第42页/共63页（3）把五个图合并成一个图，取各约束条件的公共部分，如图所示。第43页/共63页x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400第44页/共63页（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。第45页/共63页x1x2z=20000=50x1+100x2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第46页/共63页重要结论：如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；无穷多个最优解。若将例1中的目标函数变为maxz=50x1+50x2，则线段BC上的所有点都代表了最优解；第47页/共63页无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。第48页/共63页图解法的几点结论:

（由图解法得到的启示）可行域是有界或无界的凸多边形。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。第49页/共63页例2

某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？第50页/共63页解：目标函数：Minf=2x1+3x2

约束条件：

s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

采用图解法。如下图：得Q点坐标（250，100）为最优解。第51页/共63页100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q第52页/共63页

§3图解法的灵敏度分析

灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj

变化时，对最优解产生的影响。第53页/共63页

(1)

目标函数中的系数ci

的灵敏度分析

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

在z=x2(x2=z斜率为0

)到z=x1+x2(x2=-x1+z斜率为-1)之间时，原最优解x1=50，x2=100仍是最优解。第54页/共63页一般情况：

z=c1x1+c2x2

写成斜截式x2=-(c1/c2)x1+z/c2，目标函数等值线的斜率为-(c1/c2)，当-1-(c1/c2)0（*）时，原最优解仍是最优解。第55页/共63页假设产品Ⅱ的利润100元不变，即c2=100，代到式（*）并整理得

0c1

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

50c2

+第56页/共63页假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。