运筹学基础及应用第五版胡运权第一章.ppt
《运筹学基础及应用第五版胡运权第一章.ppt》由会员分享,可在线阅读,更多相关《运筹学基础及应用第五版胡运权第一章.ppt(103页珍藏版)》请在三一办公上搜索。
1、1一般线性规划问题的数学模型,2图解法,3单纯形法原理,4单纯形法的计算步骤,5单纯形法的进一步讨论,6改进单纯形法,7应用举例及Matlab求解方法,第一章 线性规划及单纯形法,1一般线性规划问题的数学模型,例如图所示,如何截取x使铁皮所围成的容积最大?,一、问题的提出,某企业计划生产、两种产品。这两种产品都要分别在A、B、C、D四种不同设备上加工。生产每件产品需占用各设备分别为2、1、4、0h,生产每件产品,需占用各设备分别为2、2、0、4h。已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12h,又知每生产一件产品企业能获得2元利润,每生产一件产品企业能获得3元利润,问企
2、业应安排生产两种产品各多少件,使总的利润收入为最大。,1一般线性规划问题的数学模型,需满足条件:,实现目的:,二、线性规划问题的数学模型,三个组成要素:,1.决策变量:是决策者为实现规划目标采取的方案、措施,是问题中要确定的未知量。,2.目标函数:指问题要达到的目的要求,表示为决策变量的函数。,3.约束条件:指决策变量取值时受到的各种可用资源的限制,表示为含决策变量的等式或不等式。,一般线性规划问题的数学模型:,目标函数:,约束条件:,简写形式:,矩阵形式表示为:,其中:,三、线性规划问题的标准形式,标准形式:,标准形式特点:,4.决策变量取值非负。,1.目标函数为求极大值;,2.约束条件全为
3、等式;,约束条件右端常数项全为非负值;,一般线性规划问题如何化为标准型:,1.目标函数求极小值:,令:,即化为:,2.约束条件为不等式:,(1)当约束条件为“”时,如:,可令:,显然,(2)当约束条件为“”时,如:,可令:,显然,称为松弛变量。,称为剩余变量。,松弛变量和剩余变量统称为松弛变量,(3)目标函数中松弛变量的系数,由于松弛变量和剩余变量分别表示未被充分利用的资源以及超用的资源,都没有转化为价值和利润,因此在目标函数中系数为零。,3.取值无约束的变量,如果变量 x 代表某产品当年计划数与上一年计划数之差,显然 x 的取值可能是正也可能是负,这时可令:,其中:,例.将下述线性规划模型化
4、为标准型,解:令,得标准形式为:,求解线性规划问题:就是从满足约束方程组和约束不等式的决策变量取值中,找出使得目标函数达到最大的值。,四、线性规划问题的解,可行解:满足约束条件的解称为可行解,可行解的集合称为可行域。,最优解:使目标函数达到最大值的可行解。,基:约束方程组的一个满秩子矩阵称为规划问题的一个基,基中的每一个列向量称为基向量,与基向量对应的变量称为基变量,其他变量称为非基变量。,基解:在约束方程组中,令所有非基变量为0,可以解出基变量的唯一解,这组解与非基变量的0共同构成基解。,基可行解:满足变量非负的基解称为基可行解,可行基:对应于基可行解的基称为可行基,例4 说明什么是基、基
5、变量、基解、基可行解和可行基,实现目的:,为了便于建立 n 维空间中线性规划问题的概念及便于理解求解一般线性规划问题的单纯形法的思路,先介绍图解法。,求解下述线性规划问题:,2.线性规划问题的图解法,画出线性规划问题的可行域:,目标函数的几何意义:,最优解的确定:,图解法的步骤:,建立坐标系,将约束条件在图上表示;确立满足约束条件的解的范围;绘制出目标函数的图形;确定最优解。,无穷多最优解的情况:,目标函数与某个约束条件恰好平行,无界解(或无最优解)的情况:,可行域上方无界,无可行解的情况:,约束条件不存在公共范围,图解法的启示:,求解线性规划问题时,解的情况有:唯一最优解,无穷多最优解,无界
6、解,无可行解;若线性规划问题可行域存在,在可行域是一个凸集;若线性规划问题最优解存在,在最优解或最优解之一一定能够在可行域的某个顶点取得;解题思路是,先找凸集的任一顶点,计算其目标函数值。比较其相邻顶点函数值,若更优,则逐点转移,直到找到最优解。,3单纯形法原理,凸集:如果集合 C 中任意两个点,其连线上的所有点也都是集合C 中的点。,上图中(1)(2)是凸集,(3)(4)不是凸集,顶点:如果对于凸集 C 中的点 X,不存在C 中的任意其它两个不同的点,使得 X 在它们的连线上,这时称 X 为凸集的顶点。,一、线性规划问题基本定理,定理一 若线性规划问题存在可行解,则问题的可行 域是凸集。,定
7、理二 线性规划问题的基本可行解 X 对应线性规划 问题可行域(凸集)的顶点。,定理三 若线性规划问题有最优解,一定存在一个基 可行解是最优解。,从上述三个定理可以看出,要求线性规划问题的最优解,只要比较可行域(凸集)各个顶点对应的目标函数值即可,最大的就是我们所要求的最优解。,定理1:若LP模型存在可行解,则可行域为凸集。,证明:设 max z=CX st.AX=b X0,并设其可行域为C,若X1、X2为其可行解,且X1X2,则 X1C,X2 C,即AX1=b,AX2=b,X10,X20,,又 X为X1、X2连线上一点,即 X=X1+(1-)X2,(01),AX=AX1+(1-)AX2=b+(
8、1-)b=b,(01),且 X 0,X C,C为凸集。,三个基本定理:,引理:线性规划问题的可行解X=(x1,x2,xn)T 为基本可行解的充要条件是X的正分量所对应的系数列向量线性独立。,证:(1)必要性:X基本可行解X的正分量所对应的系数列向量线性独立 可设X=(x1,x2,xk,0,0,0)T,若X为基本可行解,显然,由基本可行解定义可知x1,x2,xk所对应的系数列向量P1,P2,Pk应该线性独立。,(2)充分性:X的正分量所对应的系数列向量线性独立 X为基本可行解若A的秩为m,则X的正分量的个数km;当k=m时,则x1,x2,xk的系数列向量P1,P2,Pk恰好构成基,X为基本可行解
9、。当km时,则必定可再找出m-k个列向量与P1,P2,Pk一起构成基,X为基本可行解。,证:等价于 X非基本可行解X非凸集顶点(1)必要性:X非基本可行解 X非凸集顶点 不失一般性,设X=(x1,x2,xm,0,0,0)T,为非基本可行解,X为可行解,,pjxj=b,,j=1,n,即 pjxj=b(1),j=1,m,又 X是非基本可行解,P1,P2,Pm线性相关,即有1P1+2P2+mPm=0,其中1,2,m不全为0,两端同乘0,得1P1+2P2+mPm=0,(2),定理2:线性规划模型的基本可行解对应其可行域的顶点。,由(1)+(2)得(x1+1)P1+(x2+2)P2+(xm+m)Pm=b
10、由(1)-(2)得(x1-1)P1+(x2-2)P2+(xm-m)Pm=b,令X1=(x1+1,x2+2,xm+m,0,0)T X2=(x1-1,x2-2,xm-m,0,0)T取充分小,使得 xj j0,则 X1、X2均为可行解,但 X=0.5X1+(1-0.5)X2,X是X1、X2连线上的点,X非凸集顶点。,(2)充分性:X非凸集顶点 X非基本可行解,设X=(x1,x2,xr,0,0,0)T为非凸集顶点,则必存在Y、Z两点,使得,X=Y+(1-)Z,(01),且Y、Z为可行解或者 xj=yj+(1-)zj(01),(j=1,2,n),yj0,zj0,0,1-0,当xj=0,必有yj=zj=0
11、,pjyj=,j=1,n,pjyj=b(1),j=1,r,pjzj=,j=1,n,pjzj=b(2),j=1,r,(yj-zj)pj=0,j=1,r,(1)-(2),得,即,(y1-z1)P1+(y2-z2)P2+(yr-zr)Pr=0,Y、Z为不同两点,yj-zj不全为0,P1,P2,Pr线性相关,X非基本可行解。,z1=CX1=CX0-C=zmax-C,z2=CX2=CX0+C=zmax+C z0=zmax z1,z0=zmax z2,z1=z2=z0,即 X1、X2也为最优解,若X1、X2仍不是顶点,可如此递推,直至找出一个顶点为最优解。从而,必然会找到一个基本可行解为最优解。,定理3:
12、若线性规划模型有最优解,则一定存在一个基本可行解为最优解。,证:设 X0=(x10,x20,xn0)T 是线性规划模型的一个最优解,z0=zmax=CX0若X0非基本可行解,即非顶点,只要取充分小,则必能找出X1=X0-0,X2=X0+0,即X1、X2为可行解,,单纯形法的计算步骤:,初始基本可行解,新的基本可行解,最优否?,STOP,Y,N,二、确定初始基可行解,线性规划问题的最优解一定会在基可行解中取得,我们先找到一个初始基可行解。然后设法转换到另一个基可行解,直到找到最优解为止。,设给定线性规划问题:,因此约束方程组的系数矩阵为:,由于该矩阵含有一个单位子矩阵,因此,用这个单位阵做基,就
13、可以求出一个基可行解:,其标准形为:,三、从初始基可行解转换为 另一个基可行解,对初始可行解的系数矩阵进行初等行变换,构造出一个新的单位矩阵,其各列所对应的变量即为一组新的基变量,求出其数值,就是一个新的基可行解。,从一个基本可行解向另一个基本可行解转换,不失一般性,设基本可行解X0=(x10,x20,xm0,0,0)T,前m个分量为正值,秩为m,其系数矩阵为,P1 P2 Pm Pm+1 Pj Pn b 1 0 0a 1,m+1 a1j a 1n b1 0 1 0 a 2,m+1 a2j a 2nb2 0 0 1a m,m+1 amj a mn bm,pjxj0=,j=1,n,pixi0=b(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 基础 应用 第五 版胡运权 第一章
链接地址:https://www.31ppt.com/p-5849561.html