文档介绍：该【[数学]规划论-吕世林】是由【wawa】上传分享，文档一共【32】页，该文档可以免费在线阅读，需要了解更多关于【[数学]规划论-吕世林】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。线性规划(linearprogramming)与单纯形法
例—生产支配问题
如何合理运用有限的人力,物力和资金,使得收到最好的经济效益。
如何合理运用有限的人力,物力和资金,以达到最经济的方式,完成生产支配的要求。
一线性规划问题及其数学模型
1问题的提出
某厂生产两种产品,须要三种资源,已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表:
产品A
产品B
资源限量
劳动力
设备
原材料
9
4
3
4
5
10
360
200
300
利润元/kg
70
120
问题:如何支配生产支配,使得获利最多?
步骤:
1、确定决策变量:设生产A产品x1kg,B产品x2kg
2、确定目标函数:maxZ=70X1+120X2
3、确定约束条件:人力约束9X1+4X2≤360
设备约束4X1+5X2≤200
原材料约束3X1+10X2≤300
非负性约束X1≥0X2≥0
以上两个问题的共同特征:
每一个问题都用一组决策变量表示某一方案,这组决策变量的值就代表一个具体方案。一般变量取值是非负且连续的。这些问题中的全部参数都是确定的,不包含随机因素。
存在确定的约束条件,可以用一组线性等式或线性不等式来表示。
都有一个要求达到的目标,可用决策变量的线性函数(目标函数)来表示,按问题的不同,要求目标函数实现最大化或最小化。
满足以上三个特征的数学模型称为线性规划的数学模型。
线性规划数学模型三要素:
决策变量、约束条件、目标函数
线性规划的一般模式:
目标函数:max(min)Z=c1x1+c2x2+c3x3+…+cnxn
约束条件:a11x1+a12x2+a13x3+…+a1nxn≤(=≥)b1
a21x1+a22x2+a23x3+…+a2nxn≤(=≥)b2
…………
am1x1+am2x2+am3x3+…+amnxn≤(=≥)bn
非负性约束:x1≥0,x2≥0,…,xn≥0
线性规划(LP)是在有限资源的条件下,合理支配和利用资源,以期取得最佳的经济效益的优化方法。
2线性规划图解法
已知:y=ax+b是一条直线,同理:
Z=70x1+120x2
→x2=70/120x1-Z/120也是一条直线,以Z为参数的一族等值线。
9x1+4x2≤360
→x1≤360/9-4/9x2
是直线x1=360/9-4/9x2下方的半平面。全部半平面的交集称之为可行域,可行域内的随意一点,就是满足全部约束条件的解,称之为可行解。
例1图示
.
9080604020
020406080100
x1
x2
9x1+4x2≤360
4x1+5x2≤200
3x1+10x2≤300
A
B
C
D
E
F
G
H
I
Z=70x1+120x2
概念
1、可行解:满足全部约束条件的解。
2、可行域:即可行解的集合。全部约束条件的交集,也就是各半平面的公共部分。满足全部约束条件的解的集合,称为可行域。
3、基解:约束条件的交点称为基解(直观)
4、基可行解:基解当中的可行解。
5、凸集:集合内随意两点的连线上的点均属于这个集合。如:实心球、三角形
结论
可行域是个凸集
可行域有有限个顶点
最优值在可行域的顶点上达到
无穷多解的情形
无界解情形
无解情形