第1章 线性规划 (2)—03,04,05讲

《第1章 线性规划 (2)—03,04,05讲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、手机：13551284516院系：交通与汽车学院，交通运输系主讲:罗建运筹学邮箱：luo06_jian2000@126.com第1章线性规划复习1、线性规划问题的数学模型包含三个组成要素：决策变量目标函数约束条件2、线性规划数学模型的标准型，以及与非标准型的转化。3、图解法的一般步骤。本堂课的主要内容1、图解法的几何意义；2、单纯形法的概念；3、单纯形法的几何语言；4、单纯形法的代数形式5、单纯型表格。重点及难点：单纯形表1、图解法的几何意义；凸集（Convexset）概念：设K是n维欧氏空间的一个点集，

2、若K中的任意两点x(1),x(2)的连线上的一切点x仍在K中，则称K为凸集。即：若K中的任意两点x(1),x(2)∈K，存在0<=<=1使得x=x(1)+(1-)x(2)∈K,则称K为凸集例（凸集）例（非凸集）两个基本概念：凸组合(Convexcombination)：设x(1),x(2)…..x(k)是n维欧氏空间中的k个点，若存在数u1,u2,….uk且0≤ui≤1(i=1,2,…k),ui=1,使得x=u1x(1)+u2x(2)+…..+ukx(k)成立，则称x为x(1),x(2)…..x(

3、k)的凸组合。两个基本概念：顶点：设K是凸集,若K中的点x不能成为K中任何线段上的内点，则称x为凸集K的顶点。即：若K中的任意两点x(1),x(2)，不存在数（0<<1）使得x=x(1)+(1-)x(2)成立，则称x为凸集K的一个顶点。例：多边形上的点是顶点圆周上的点都是顶点1、图解法的几何意义；以例子1.1为例：1、图解法的几何意义；以例子1.1为例：8个顶点中(0,6)、(2,6)、(4,3)、(4,0)、(0,0)位于可行域的边界上，是可行解。称为顶点可行解；（0,9）、(4,6)、(6,0

4、)称为顶点非可行解。2、单纯形法的概念LP（线性规划）解的基本概念标准型：MaxZ=CXAX=bX≥0s.t.（1）（2）2）基：标准型中，A的秩为m，是矩阵A的满秩子矩阵，则B是线性规划问题的一个基（基矩阵）。则B中的列向量为基向量，与基向量对应的决策变量称为基变量，其它变量称为非基变量。1）可行解满足（1）、（2）的解2、单纯形法的概念3）基解令非基变量为0，则由约束方程确定的唯一解为基本解，简称基解。4）基可行解若基解X≥0，则称为基可行解。结论：1、LP的基可行解对应于可行域的顶点。2、若可行域有

5、界，LP的目标函数一定可以在其可行域的顶点上达到最优，即一定存在一个基可行解是最优解。可行解基解基可行解2、单纯形法的概念求解例1.1的基、基变量、基解、基可行解和可行基。2、单纯形法的概念求解例1.1的基、基变量、基解、基可行解和可行基。2、单纯形法的概念求解例1.1的基、基变量、基解、基可行解和可行基。基变量：2、单纯形法的概念求解例1.1的基、基变量、基解、基可行解和可行基。令解得，解得，基解2、单纯形法的概念求解例1.1的基、基变量、基解、基可行解和可行基。基解基解中所有变量取值为非负，故也是基可

6、行解；对应的基是一个可行基2、单纯形法的概念2.1单纯形法的几何意义；单纯形法：按照一种规则的方式，从一个顶点向相邻的一个顶点转换，直到找到一个最优解为止。单纯形法的基本方法基本方法：确定初始基可行解检验是否最优？转到另一更好的基可行解停YN方法前提：模型化为标准型例：煤电油例MaxZ=7x1+12x29x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1,x2≥0s.t.1.化为标准型MaxZ=7x1+12x29x1+4x2+x3=3604x1+5x2+x4=2003x1+10x2+x

7、5=300x1,…,x5≥0s.t.2.确定一基可行解令B=(P3,P4,P5)，得:x3=360-9x1-4x2x4=200-4x1-5x2(1)x5=300-3x1-10x2∴基可行解X(0)=(0,0,360,200,300)T3.进基、出基（1）进基∵　存在正系数的非基变量∴X(0)不是最优，令x2进基（2）出基(1)式中，令x1=0，得:x3=360-4x2x4=200-5x2x5=300-10x2分别令x3,x4,x5=0，得x2=90,40,30x5出基保证可行性代数形式故得新基变量XB=(

8、x2,x3,x4)。将(1)化为:4x2+x3=360-9x15x2+x4=200-4x1(2)10x2=300-3x1–x5x3=240-7.8x1+0.4x5x4=50-2.5x1+0.5x5(3)x2=30-0.3x1–0.1x5得新基可行解X(1)=(0,30,240,50,0)T2.确定一基可行解令B=(P3,P4,P5)，得:x3=360-9x1-4x2x4=200-4x1-5x2(1)x5=300-3x1-10x