运筹学第二章word精品.docx
《运筹学第二章word精品.docx》由会员分享，可在线阅读，更多相关《运筹学第二章word精品.docx（12页珍藏版）》请在冰点文库上搜索。
运筹学第二章word精品
第2次课2学时
本次课教学重点：
线型规划模型有关概念、图解法求解线型规划模型
本次课教学难点：
线型规划模型有关概念、各种解的情况分析本次课教学内容：
第二章线性规划的图解法
第一节问题的提出一、引例
例1.某工厂在计划期内要安排i、n两种产品的生产，已知生产单位产品所需的设备台时
及A、B两种原材料的消耗、资源的限制，如下表：
I
n
资源限制
设备
1
1
300台时
原料A
2
P1
400千克
原料B
0
1
250千克
单位产品获利
50元
100元
问题：
工厂应分别生产多少单位i、n产品才能使工厂获利最多?
解：
分析问题后可得数学模型：
目标函数：
MaxZ=50%100x2
约束条件：
s.tXi•X2-300
2x1x2乞400
x2乞250
%_0,x2_0
这是一个线性规划模型，因为：
目标函数是线性函数，约束条件是一些线性的等式或不等式。
若目标函数是非线性函数，或约束条件中有非线性的等式或不等式，则这样的问题称为非线性
规划。
二、一般建模过程
1•理解要解决的问题，了解解题的目标和条件；
2•定义决策变量（Xi,X2……,Xn），每一组值表示一个方案；
3•用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；
4•用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件
线性规划模型的一般形式
目标函数：
Max（Min）=c1x1c2x2
……CnXn
约束条件：
s.t
a〔1X[•a〔2x?
....
..amXn（,）d
a21x1a?
2X2
...a?
%：
：
（=,）b2
am1x1■am2X2■..
....amnxn—
为0,X20,..
....,Xn0
第二节图解法
对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。
下面通过例1详细讲解其方法
一、有关概念
1、可行解：
满足约束条件的解
2、可行域：
全体可行解的集合。
3、最优解：
使得目标函数值达到最优的可行解。
4、凸集
5、松弛变量
二、图解法求解线性规划
例1.目标函数：
MaxZ=50%•100x2
约束条件：
s.txAx2-300
2x1x2<400
x2乞250
Xi_0,X2_0
解：
（1）分别取决策变量x1,x2为坐标向量建立直角坐标系。
在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。
面。
300
x2=250
「/
l-///////////
Wzw2'250
nni
/////////z.
100200300
2-1所示。
（3）把五个图合并成一个图，取各约束条件的公共部分，如图
X2
Xi
图2-1
（4）目标函数Z=50Xi•100x2,当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为等值线”平行移动等值线，当移动到B点时，z在可行域内实现了最大化。
A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。
图2-2
综上得到最优解：
％=50,x2=250
最优目标值z=27500
三、线性规划问题解的情况
1、如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；
2、无穷多个最优解。
若将例1中的目标函数变为MaxZ^50x150x2，则线段BC上的所有点都代表了最优解；
3、无界解。
即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。
一般来说，这说明模型有错，忽略了一些必要的约束条件；
4、无可行解。
若在例1的数学模型中再增加一个约束条件4为*3X2_1200，则可行域为空域，不存在
满足约束条件的解，当然也就不存在最优解了。
例2.某公司由于生产需要，共需要A,B两种原料至少350吨（A,B两种材料有一定替代
B原料需要1小时，而公司总共有600
B原料的价格为3万元，试问在满足生A，B两种
性），其中A原料至少购进125吨。
但由于A,B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨个加工小时。
又知道每吨A原料的价格为2万元，每吨产需要的前提下，在公司加工能力的范围内，如何购买原料，使得购进成本最低？
=2x13x2
x1x2_350
2x1x2一600
x1_125
%_0,x2_0
米用图解法。
如下图:
得Q点坐标（250，100）为最优解。
教学组织
1、课堂讲授
2、多媒体图形演示作业布置：
1、P23.2（1,2）
第3次课2学时
本次课教学重点：
化标准型、灵敏度分析本次课教学难点：
灵敏度分析
本次课教学内容：
第三节图解法的灵敏度分析
am"•am2X2•……•a^Xnm（=,_）bm
%_0,X2一0,,xn_0
2、约束条件不是等式的问题：
（1）设约束条件为
耳必+耳2冷+••…+a（nX^-b|
可以引进一个新的变量Si，使它等于约束右边与左边之差
s弋-耳丙72冷......為人
显然，Si也具有非负约束，即s-0,这时新的约束条件成为
显然，Si也具有非负约束，即Si-0,这时新的约束条件成为
耳內a?
冷••….anXrs弋
3•右端项有负值的问题：
在标准形式中，要求右端项必须每一个分量非负。
当某一个右端项系数为负时，如hwo,
则把该等式约束两端同时乘以-1，得到：
一耳倔一a2x2一■■■■「■耳儲=一匕
为了使约束由不等式成为等式而引进的变量S,当不等式为“小于等于”时称为松弛变量
当不等式为“大于等于”时称为剩余变量”。
如果原问题中有若干个非等式约束，则将其转化
为标准形式时，必须对各个约束引进不同的松弛变量。
例：
将以下线性规划问题转化为标准形式
Minf=2x1-3x24x3
约束条件：
s.t
3为4x2-5x3乞6
2x1x3_8
%x2x3--9
MX一0
X1,X2,X3>0
解：
首先，将目标函数转换成极大化：
令z=-f=-2X-!
3x2-4x3
次考虑约束，有2个不等式约束，引进松弛变量X4,X5一0。
三个约束条件的右端值为负，在等式两边同时乘-1。
通过以上变换，可以得到以下标准形式的线性规划问题：
Maxz=-2xi3x2-4x3
约束条件：
s.t
3x14x2-5x3&=6
2x1X3-X5=8
_x^_x2_Xs=9
X1,X2,Xj,X4,x^-0
4.变量无符号限制的问题
在标准形式中，必须每一个变量均有非负约束。
当某一个变量Xj没有非负约束时，可以令
Xj=Xj'-Xj”其中Xj'》0,Xj”》0
即用两个非负变量之差来表示一个无符号限制的变量，当然Xj的符号取决于Xj，和Xj”的大
小。
灵敏度分析
灵敏度分析：
建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）ci,aij,bj
变化时，对最优解产生的影响。
1•目标函数中的系数ci的灵敏度分析
C的变化只影响目标函数等值线的斜率，不影响可行域。
考虑例1的情况，目标函数Z=50x100x2
在Z=x2（x2=z斜率为0）到Z=x1x2（x1x2=z斜率为-1）之间时,原最优解Xi=50,X2250仍是最优解。
cz
—般情况：
Z=Cixic2x2；写成斜截式x2-xi■
目标函数等值线的斜率为一9，当一1_一9_0（*）时，原最优解仍是最优解。
C2C2
1假设产品n的利润100元不变，即C2=100，代到式（*）并整理得
0_G_100
2假设产品I的利润50元不变，即C1=50，代到式（*）并整理得
50_c2_:
:
假若产品i、n的利润均改变，则可直接用式（*）来判断。
假设产品i、n的利润分别为60元、55元，贝U
60
--1
55
那么，最优解为x1x2和2x1x2的交点x^100,x^200。
2.约束条件中右边系数bj的灵敏度分析
当约束条件中右边系数bj变化时，线性规划的可行域发生变化，可能引起最优解的变化。
考虑例1的情况：
（1）假设设备台时增加10个台时，即b变化为310，这时可行域扩大，最优解为
X2=250和X1X2=310的交点X1=60,X2=250
变化后的总利润一变化前的总利润=增加的利润
（50X60+100X250）—（50X50+100X250）=500,
500/10=50元
说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称
为该约束条件的对偶价格。
（2）假设原料A增加10千克时，即b2变化为410,这时可行域扩大，但最优解仍为x2=250和x1x^310的交点为=60,x2=250。
此变化对总利润无影响，该约束条件的对偶价格为0。
解释：
原最优解没有把原料A用尽，有50千克的剩余，因此增加10千克值增加了库
存，而不会增加利润。
在一定范围内，当约束条件右边常数增加1个单位时
（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；
（2）若约束条件的对偶价格小于
3）若约束条件的对偶价格等于
0，则其最优目标函数值受到影响（变坏）
0，则最优目标函数值不变。
教学组织
1、课堂讲授
2、多媒体教学
3、课堂练习
作业布置：
1、P24.3（2，3），4
2、P25.6
升级会员 