单纯形法图解法及原理实用教案.ppt

1决策(juécè)(juécè)变量：XiXi为第i i班开始上班的人数 i=1,…,6 i=1,…,6目标函数：Min Z= X1+X2+X3+X4+X5+X6Min Z= X1+X2+X3+X4+X5+X6约束条件： X6 + X1 >= 60 X6 + X1 >= 60 X1 + X2 >= 70 X1 + X2 >= 70 X2 + X3 >= 60 X2 + X3 >= 60 X3 + X4 >= 50 X3 + X4 >= 50 X4 + X5 >= 20 X4 + X5 >= 20 X5 + X6 >= 30 X5 + X6 >= 30 Xi>=0,1=1,…,6 Xi>=0,1=1,…,6第1页/共35页第一页，共36页2线性规划模型隐含的假设：比例性： 决策变量变化引起目标的改变量与决策变量改变量成正比可加性： 每个决策变量对目标和约束(yuēshù)(yuēshù)的影响独立于其它变量。

连续性： 每个决策变量取连续值确定性： 线性规划中的参数aij , bi , ciaij , bi , ci为确定值 第2页/共35页第二页，共36页3第二节 单纯形法原理(yuánlǐ)----图解法§图解法：是用画图的方式求解线性规划的一种方法§只能用于求解两个变量(biànliàng)(biànliàng)的LPLP问题第3页/共35页第三页，共36页41 1）作出可行域2 2）作出一条目标(mùbiāo)(mùbiāo)函数的等值线3 3）平行移动目标(mùbiāo)(mùbiāo)函数的等值线，求出最优解图解法基本(jīběn)步骤：第4页/共35页第四页，共36页5例1.1.数学模型 max Z=50xmax Z=50x1 1+30x+30x2 2 s.t. 4x s.t. 4x1 1+3x+3x2 2   120 120 2x 2x1 1+x+x2 2   50 50 x x1 1,x,x2 2   0 0第5页/共35页第五页，共36页。

6x2504030201010203040x14x4x1 1+3x+3x2 2     120 120由由 4x1+3x2 4x1+3x2     120 120 x1 x1     0 x2 0 x2     0 0围成的区域围成的区域(qūyù)(qūyù)第6页/共35页第六页，共36页7x2504030201010203040x12x1+x2  504x1+3x2  120可行可行(kěxíng(kěxíng) )域域同时同时(tóngshí)(tóngshí)满足：满足：4x1+3x2 4x1+3x2     120 120 2x1+x2 2x1+x2     50 50x1 x1     0 x2 0 x2     0 0的区域的区域————可行域可行域第7页/共35页第七页，共36页8x2504030201010203040x1可行可行(kěxíng(kěxíng) )域域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成(zǔ chénɡ)问题的解集合。

该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形第8页/共35页第八页，共36页9x2504030201010203040x1可行可行(kěxíng(kěxíng) )域域目标函数(hánshù)是以Z作为参数的一组平行线x2 = Z/30-（5/3）x1第9页/共35页第九页，共36页10x2504030201010203040x1可行可行(kěxíng(kěxíng) )域域当Z值不断增加时，该直线x2 = Z/30-（5/3）x1沿着其法线(fǎ xiàn)方向向右上方移动第10页/共35页第十页，共36页11x2504030201010203040x1可行可行(kěxíng(kěxíng) )域域当该直线移到Q2点时，Z（目标函数(hánshù)）值达到最大：Max Z=50*15+30*20=1350此时最优解=（15，20）Q2（15，20）有唯一(wéi yī)(wéi yī)最优解 第11页/共35页第十一页，共36页12例 2 解 线 性 规 划(xiàn xìnɡ ɡuī huá)有唯一(wéi (wéi yī)yī)最优解 第12页/共35页第十二页，共36页。

13对于线性规划问题，我们定义：可行解：满足全部约束条件的决策向量 X Rn可行域：全部可行解构成的集合(jíhé)它是 n 维欧 氏空间Rn 中的点集，而且是一个“凸 多面体”)最优解：使目标函数达到最优值（最大值或最小 值，并且有界）的可行解无界解：若求极大化则目标函数在可行域中无上 界；若求极小化则目标函数在可行域中 无下界 第13页/共35页第十三页，共36页14有无穷(wúqióng)(wúqióng)多最优解 例 3 解 线 性 规 划(xiàn xìnɡ ɡuī huá)Z=0Z=0Z=-2Z=-2第14页/共35页第十四页，共36页15例 4 解 线 性 规 划(xiàn xìnɡ ɡuī huá)有无(yǒu wú)(yǒu wú)界解 第15页/共35页第十五页，共36页16例5 5： MaxZ=3XMaxZ=3X1 1-2X-2X2 2 X X1 1 + X+ X2 2 <=1 <=1 2X 2X1 1 + 2X+ 2X2 2 >=8 >=8 X X1 1,X,X2 2 >=0 >=0无可行(kěxíng)解第16页/共35页第十六页，共36页。

17结论： 1 1、线性规划问题的可行域为凸集 2 2、若有最优解一定可以(kěyǐ)(kěyǐ)在其可行域的顶点上得到线性规划问题解的几种情况(qíngkuàng)(qíngkuàng)： 1 1、有唯一最优解 2 2、有无穷多最优解 3 3、无可行解 4 4、无最优解第17页/共35页第十七页，共36页18第三节 单纯形法 ----原理(yuánlǐ)§单纯形法：单纯形法是求解线性规划(xiàn (xiàn xìnɡ ɡuī huá)xìnɡ ɡuī huá)的主要算法，19471947年由美国斯坦福大学教授丹捷格（G.B.DanzigG.B.Danzig）提出尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对 的““市场””占有率 第18页/共35页第十八页，共36页19定义1：基(基阵) ——由A中一个子矩阵B是可逆矩阵，则方阵B称为(chēnɡ wéi)LP问题的一个基A= (P1 … Pm Pm+1 … Pn )=(BN) 基向量 非基向量…X= (X1 … Xm Xm+1 … Xn )T=(XB XN)T 基变量 非基变量 XB XN…线性规划问题(wèntí)解的概念第19页/共35页第十九页，共36页。

20例1、 X1+2X2 +X3 =30=30 3X1+2X2 +X4 =60 2X2 +X5=24 X1 … X5  0 01 2 1 0 03 2 0 1 00 2 0 0 1P1 P2 P3 P4 P5A=第20页/共35页第二十页，共36页21AX=b的求解(qiú jiě)A=(BN)X=(XB XN )T XB XN(BN) = bBXB +NXN=bBXB =b-NXNXB = B-1 b - B-1N XN第21页/共35页第二十一页，共36页22定义2：基本解——对应于基B，X=为AX=b的一个解B-1 b 0定义3：基本可行解——基B，基本解X=若B-1 b 0 0，称基B B为可行基 最优解、最优基 B-1 b 0※ ※ 基本解中最多有m m个非零分量。

※ ※ 基本解的数目不超过Cnm = 个n!m!(n-m)!第22页/共35页第二十二页，共36页23X1X2X3X4X5X=b=306024B=(P3 P4 P5)=I 可逆 基 N=(P1 P2)X3=30-( X1+2 X2)X4=60-(3X1+2 X2)X5 =24 -2 X2例1 1：第23页/共35页第二十三页，共36页24令X1 = X2 =0, X3=30, X4=60, X5=24X= = = XN 0 XB B-1 b00306024 1 2 1又：Ｂ1 =(P1 P2 P3 )= 3 2 0 0 2 0|B1|=6≠0, B可逆第24页/共35页第二十四页，共36页。

25X1=12-(1/3 X4 -1/3 X5)X2=12-(1/2 X5 )X3 =-6-(- 1/3 X4 -2/3 X5 )令X4=X5=0 X=(12, 12, -6, 0, 0)TZ=40X1 +50X2 =40[12-(1/3 X4 -1/3 X5)] +50[12- 1/2 X5 ] = 1080+(- 40/3 X4 -35/3 X5 )基本(jīběn)解，但不可行第25页/共35页第二十五页，共36页26例2：给定约束条件 -X3+X4 =0=0 X2 +X3 +X4 =3 -X1 +X2 +X3+X4 =2 Xj  0 0 ( j=1,2,3,4 )求出基变量(biànliàng)是X1 , X3 , X4的基本解，是不是可行解？第26页/共35页第二十六页，共36页27 0 -1 1解：B=(P1 P3 P4)= 0 1 1 -1 1 1 0 1 -1 0B-1= -1/2 1/2 0 3 1/2 1/2 0 2b=第27页/共35页第二十七页，共36页。

28 X1 X3 = B-1 b X4 XB = 0 1 -1 0 1 = -1/2 1/2 0 3 = 3/2 1/2 1/2 0 2 3/2∴∴X=(1, 0, 3/2, 3/2)T 是 第28页/共35页第二十八页，共36页29定义1：凸集——D是n维欧氏空间的一个集合(jíhé) X(1), X(2)∈∈D,若任一个满足 X=  X(1)+(1- ) X(2) (0      1) 有X∈∈D线性规划(xiàn xìnɡ ɡuī huá)(xiàn xìnɡ ɡuī huá)问题的几何意义( (例2)2)第29页/共35页第二十九页，共36页。

30￿￿￿X(1)￿,￿X(2)￿,￿…￿,X(k)￿是n维欧氏空间(kōngjiān)中的k个点，若有一组数￿￿￿￿µ1￿,￿µ2￿,￿…￿,￿µk￿满足￿￿￿￿￿￿￿￿￿￿￿0￿￿µi￿1￿(i=1,…￿,k)定义(dìngyì)2  µ i =1ki=1有点(yǒudiǎn) x= µ1 X(1) + … + µk X(k)则称点X为 X(1) , X(2) , … ,X(k) 的凸组合凸组合第30页/共35页第三十页，共36页31￿￿￿凸集D,￿点￿XD，若找不到两个(liǎnɡ￿ɡè)不同的点X(1)￿,￿X(2)￿D￿使得￿￿￿￿X=￿X(1)￿+(1-￿￿)￿X(2)￿￿(0<￿<1)￿￿￿￿则称X为￿D的顶点定义(dìngyì)3顶点(dǐngdiǎn)第31页/共35页第三十一页，共36页32定理1 1：LPLP问题的可行(kěxíng)(kěxíng)解域一定是凸集引理1 1：线性规划问题的可行解X X为基可 行解的充分必要条件是：X X的非 零分量(>=0)(>=0)所对应的系数(xìshù)(xìshù)矩阵 A A的列向量是线性无关。

第32页/共35页第三十二页，共36页33定理2 2：线性规划问题(wèntí)(wèntí)的基可行解对应线性 规划问题(wèntí)(wèntí)可行域（凸集）的顶点引理2 2：D D为有界凸多面集， X X D D，X X必可表 为D D的顶点(dǐngdiǎn)(dǐngdiǎn)的凸组合 定理(dìnglǐ)3：可行域有界，最优值必可在顶点得到第33页/共35页第三十三页，共36页34定理2：LP有最优解，必定可以在可行域(凸多面集)的顶点(dǐngdiǎn)得到定理3：可行域中点X是顶点 X是基本可行解可行解基本解定理1：LP问题(wèntí)的可行域一定是凸集(凸多面集)第34页/共35页第三十四页，共36页35感谢您的观赏(guānshǎng)第35页/共35页第三十五页，共36页内容(nèiróng)总结1决策变量变化引起目标的改变量与决策变量改变量成正比每个决策变量对目标和约束的影响独立(dúlì)于其它变量的区域——可行域O（0，0）Max Z=50*15+30*20=1350单纯形法：单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。

Pn )=(BN)定义2：基本解——对应于基B，X=若B-1 b0，称基B为可行基感谢您的观赏第三十六页，共36页。