1第一章线性及单纯形法

第1章线性规划与单纯形法本章要点：1.线性规划问题的数学模型2.线性规划问题的基本理论3.线性规划问题的求解例1.1：美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件I，II产品时的获利情况，如表所示。问该公司应制造这两种家电各多少件，可使获取的总利润最大？项目III每天可用能力设备A（h）0515设备B（h）6224调试工序（h）115利润（元）21一、问题的提出1.1线性规划问题与及其数学模型Max解：设x1和x2分别表示美佳公司制造家电I和II的数量。则该问题可用线性规划模型表示如下：1.1线性规划问题与及其数学模型s.t.

表示“约束于”例1.2某工地租赁机械甲和乙来安装A、B、C三种构件。已知这两种机械每天的安装能力如表所示。而工程任务要求共安装250根A构件、300根B构件和700根C构件；又知机械甲每天租赁费为250元，机械乙每天租赁费为350元，试决定租赁机械甲和乙各多少天，才能使总租赁费最少？65A206机械乙108机械甲 CB每天安装能力（根）机械构件1.1线性规划问题与及其数学模型

设租赁甲X1天，机械乙X2天，为满足A、B、C的安装要求，则用数学模型可描述为：Min1.1线性规划问题与及其数学模型1.1线性规划问题与及其数学模型例1.3某公司1－4月份拟租用仓库。已知各月份所需仓库面积如下表，仓库租借费用随合同期而定，期限越长，折扣越大，如下表。可根据需要每月初办理租借合同，每份合同具体规定租用面积和期限。每次办理可签一份，也可签若干份面积和租期不同的合同。试确定签订租借合同的最优策略，使4个月总租借费用最少。月份1234所需仓库面积15102012合同期限1个月2个月3个月4个月单位面积租费28004500600073001.1线性规划问题与及其数学模型设xij为第i个月初签订的租期为j个月的仓库面积合同，因5月份后不需租仓库，故x24,x33,x34,x42,x43,x44均为零。则数学模型为：MinZ＝2800(x11+x21+x31+x41)(x12+x22+x32)(x13+x23)x14二、线性规划的数学模型规划问题的数学模型有三个组成要素：（1）（决策）变量：问题中的未知量，可由决策者决定；（2）目标函数：决策变量的函数，按优化目标加Max或Min;

（3）约束条件：决策变量取值时受到各种资源条件的限制；

线性规划数学模型：决策变量的取值是连续的，可以是整数、分数、小数或实数，目标函数是决策变量的线性函数，约束条件是含决策变量的线性等式或不等式。1.1线性规划问题与及其数学模型二、线性规划的数学模型

实际问题中“线性”的含义：（1）严格的比理性：如生产某产品对资源的消耗量和可获取的利润，同其生产数量严格成比例；（2）可叠加性：如生产多种产品时，可获取的总利润是各项产品的利润之和，对某资源的消耗量等于各产品对该资源的消耗量之和；（3）可分性：模型中的变量可取值小数、分数或实数；（4）确定性：模型中的参数cj，aij，bi均为确定的常数。1.1线性规划问题与及其数学模型线性规划问题的数学模型可表示为：Max(Min)1.1线性规划问题与及其数学模型xj

(j=1,…,n):规划问题中的n个变量，取值受m项资源限制；cj(j=1,…,n):价值系数；bi

(i=1,…,m):第i种资源的拥有量；aij(技术系数):变量xj取值1个单位时所消耗第i种资源的数量。线性规划模型可简写为：Max(或Min)1.1线性规划问题与及其数学模型用向量形式表达时，设

C=(c1,c2,…,cn),1.1线性规划问题与及其数学模型约束方程组系数矩阵则线性规划模型可用矩阵和向量描述为：1.1线性规划问题与及其数学模型

变量xj取值一般为非负，但数学意义上也可以有xj≤0,甚至xj无约束。线性规划模型的标准形式规定如下：1.1线性规划问题与及其数学模型

要求：目标函数求极大值，约束条件全为等式，约束条件右端常数项bi全为非负值，变量xj全为非负值。线性规划问题的标准型也可表示为：Max标准型的向量形式为:maxZ=CX非标准形式的线性规划可化为标准形式：（1）目标函数为求极小值时，即令z’=-z,求minz等价于求max(-z),即化为1.1线性规划问题与及其数学模型（2）约束条件右端项bi<0时，只需将等式或不等式两端同乘(-1),则右端项bi大于零。1.1线性规划问题与及其数学模型（3）约束条件为不等式。当为≤时，引入“松弛变量”使之变为等式，当为≥时，引入“剩余变量”使之变为等式，这些引入的变量在目标函数中系数为零。（4）取值无约束的变量。令x=x’-x’’,x’和x’’均≥0（5）对x≤0的情况，令x’=-x例:将下面的线性规划问题化成标准型MaxMax1.1线性规划问题与及其数学模型又例：将下述线性规划化为标准形式minz=x1+2x2+3x31.1线性规划问题与及其数学模型解：(1)令z’=-z(2)令x1’=-x1(3)令x3=x3’-x3’’,其中x3’和x3’’均≥0，引入松弛变量x4、x5，则标准形式为：maxz’=x1’-2x2-3x3’+3x3’’+0x4+0x51.2图解法图解法：适用于两个决策变量的情形鞍面法： 1992年中国沈阳化工学院尚毅教授发明内点法：1984年美国籍印度数学家Karmarker发明椭球法：1979年苏联数学家Khachiyan发明单纯形法：1952年美国斯坦福大学教授Dantzig发明，可以解决1.5万至2万个决策变量的问题1.2图解法

图解法：只有2个变量的线性规划模型，可以在平面上作图的方法求解。最优解：可行域中使得目标函数达到最优的可行解称为最优解。可行域：通常线性规划问题含有多个可行解，全部可行解的集合称为可行域。可行解：一个线性规划问题有解，是指能找出一组xj

（xj=1,…,n），满足约束条件，则这组xj为问题的可行解。1.2图解法一、图解法max z=x1+3x2 x1+x2≤6s.t.-x1+2x2≤8 x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2问题：

——

多边形，而且是“凸”形的多边形。

最优解在什么位置获得？

——

在边界，而且是在某个顶点获得。

线性规划的可行域是一个什么形状？1.2图解法图解法求解步骤：（1）建立直角坐标系；（2）根据线性规划问题的约束条件和非负条件画出可行域；（3）作出目标函数等值线Z=c（c为一常数），并使其平移求得最优解。1.2图解法线性规划的解的特殊情况唯一解X1X2X1X222X1X221无穷解例max

z=x1+x2s.t.2x1+2x2<=4x1>=0,x2>=0无界解（少了约束条件）例maxz=x1+2x2s.t.x1>=1x2>=21.2图解法无可行解（有矛盾约束）例minz=x1-x2s.t.x1>=2x1<=1X1X222无可行解域1.3单纯形法基本原理Max(i=1,2,…m)(1)(2)(3)1.概念可行解：满足上面模型中的（2）和（3）式的解X；最优解：满足上面模型中的（1）的可行解X；基（矩阵）：A为约束方程组的m×n阶系数矩阵，其秩为m，若B是A中的m×m阶满秩子矩阵，则B是线性规划问题的一个基（矩阵）。设B=[P1，P2，….，Pm]，则

Pj(j=1,..,m)为基向量，与Pj对应的变量xj为基变量。非基变量：X中除基变量外的变量；基解：在方程AX=b中，令所有非基变量xm+1=…=xn=0，由m个约束方程可解出m个基变量的唯一解Xb=(x1,…,xm)T，加上非基变量的0值得到线性规划问题的基解：X=(x1,…,xm,0,…,0)T。一般m<n，故基解的个数≤Cnm

；基可行解：满足变量非负，即满足（3）式的基解。可行基：对应于基可行解的基称为可行基。例：设线性规划问题如下，试找出其全部基解，指出其中的基可行解，并确定最优解。maxz=2x1+3x2+x3x1+x3=5x1+2x2+x4=10x2+x5=4x1,x2,x3,x4,x5

≥0s.t.解：全部基解如表所示，打为基可行解，*为最优解。序号x1x2x3x4x5z基可行解10051045

20452017

35005410

40550-1205100-50415652.5001.517.5

7540-302282430019*总结：各种解之间的关系如下图所示：基解可行解最优解基可行解1.概念凸集：设C是一个点集，若C中任意两点X1，X2都满足：则称C为凸集。

简单地讲，如果C中任意两点的连线上所有点也都是集合C中的点，则C为凸集。例：以下哪些是凸集？(a)(b)(c)(d)答：(a)(b)是凸集，(c)(d)不是凸集1.概念顶点：C为凸集，点X∈C，若C中不存在两点X1,X2,满足：则称X为凸集C的顶点。

简单地讲，如果C中不存在任意两点X1,X2,使X成为这两点连线上的点，则X为凸集C的顶点。2.基本定理定理1：若线性规划问题存在可行解，则问题的可行域是凸集。定理2：线性规划问题的基可行解X对应线性规划问题可行域（凸集）的顶点。定理3：若线性规划问题有最优解，一定存在一个基可行解是最优解。基本结论：线性规划问题的所有可行解构成的集合是凸集；线性规划问题的每一个基可行解都有对应可行域的一个顶点；若线性规划问题有最优解，必定在可行域的某个顶点上达到。1.3单纯形法原理1.单纯形法的基本思路若线性规划问题存在最优解，一定有一个基可行解是最优解。因此，先找出一个（初始）基可行解，判断它是否为最优解，若不是，则转换到相邻的基可行解，并使目标函数值不断增大，直到找到最优解。如何确定初始基可行解？对于标准型的线性规划问题：max

其约束方程组系数矩阵A中总会存在一个m阶单位矩阵：如何确定初始基可行解？

当约束条件均为≤时，引入m个松弛变量，则松弛变量系数矩阵即为m阶单位矩阵。若约束条件均为≥时，可以人为产生一个单位矩阵。

单位矩阵中，每个列向量Pj(j=1,…,m)都为基向量，其对应的变量xj为基变量，其它变量xm+1,…,xn为非基变量。令所有非基变量为0，可找到一个解：X=(x1,…,xm,xm+1,…,xn)T=(b1,b2,…,bm,0,…,0)T则X为一个基可行解，可作为初始基可行解。如何确定初始基可行解？例：请对下面线性规划问题确定一个初始基可行解。Max解：先化成标准型Max因为存在2阶单位矩阵，对应基变量为x4和x5，令其它非基变量x1,x2,x3都为0，解方程得到一个初始基可行解：X=(0,0,0,1,3)T对于标准型的线性规划问题：max其单纯形法的求解步骤如下：1.4单纯形法计算步骤1.4单纯形法计算步骤（1）求初始基可行解，列出初始单纯形表为检验基可行解是否最优，要与相邻基可行解进行比较。每次计算出一个新的基可行解，就要重画一个单纯形表。非基变量xj下的数字是对应Pj向量由基向量线性组合时的系数，即：Pj=a1jP1+a2jP2+…+amjPm表11.4单纯形法计算步骤检验数(cj-zj)用来检验基可行解是否为最优解。2.最优性检验若所有检验数(cj-zj)≤0，且基变量中不含人工变量时，表中基可行解即为最优解，计算结束。若存在(cj-zj)>0，转下一步。1.4单纯形法计算步骤3.转换到相邻的目标函数值更大的基可行解，列出新的单纯形表（1）确定换入基的变量。只要检验数σj>0,即(cj-zj)>0,对应的变量xj可作为换入基的变量，当有两个以上检验数大于0，一般最大检验数值对应的变量xk作为换入变量。（2）确定换出基的变量。根据下面公式确定换出变量xl

alk称为主元素，它决定了从一个基可行解到相邻基可行解的转移去向。1.4单纯形法计算步骤（3）用换入变量xk替换基变量中换出变量xl，得到一个新的基矩阵，对应这个基矩阵可以找出新的基可行解，相应地可画出新的单纯形表，如下表所示。表21.4单纯形法计算步骤

要使新表（表2）中的基矩阵仍然是单位矩阵，必须对旧表进行行的初等变换，然后将变换结果填入新表中。（1）将旧表主元素所在l行数字除以主元素alk，得到新表的值

（2）将新表中刚计算得到的第l行数字乘上(-aik)加到旧表的第i行数字上，得到的值写入新表相应行中，即计算新表各检验数，进行最优解检验。重复直至结束。例：用单纯形法求解下面线性规划问题解：先将线性规划问题化为标准形式：其约束条件系数矩阵为：P3,P4,P5构成单位矩阵，即构成一个基，对应变量x3,x4,x5为基变量，令非基变量x1,x2=0,得到一个初始基可行解：X=(0,0,15,24,5)T列出初始单纯形表cj→21000CB基bx1x2x3x4x50x315051000x424[6]20100x5511001cj-zj21000表中有大于零的检验数，其基可行解不是最优解。由于σ1>σ2>0，故x1为换入变量。将b列除以P1（换入变量对应列）的同行数字并取最小值：以此确定6为主元素，其对应的x4为换出变量。用x1替换基变量x4，得到一个新的基P3,P1,P5,列出新的单纯形表如下,计算出新的基可行解。cj→21000CB基bx1x2x3x4x50x315051002x1412/601/600x510[4/6]0-1/61cj-zj01/30-1/30

由于还存在大于零的检验数σ2

，故重复上述步骤，x2为换入变量，x5为换出变量，计算得到新的单纯形表如下：cj→21000CB基bx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj000-1/4-1/2

此时检验数全部小于或等于0

，且基变量不含人工变量，表中基可行解为最优解，即：X=(7/2,3/2,15/2,0,0)T，代入得目标函数值为z=17/21.5单纯形法的进一步讨论（1）人工变量法（大M法）线性规划问题约束条件系数矩阵中含有单位矩阵时，以它作为初始基，求初始基可行解并作出初始单纯形表。若其约束条件系数矩阵不含单位矩阵如何处理？Max加入人工变量化标准形式如下:例：MaxMaxx6,x7是人为添加的，即人工变量，添加后P4,P6,P7构成单位矩阵，可以求初始基可行解。在最优解中人工变量全部必须为0，以满足约束条件。在目标函数中“-M”为任意大的负值（M>0），称为“罚因子”，只要人工变量取值大于零，目标函数就不可能最优。在单纯形法迭代过程中，M可作为一个数学符号一起运算。

此时x4,x6,x7为基变量，令非基变量x1,x2,x3,x5均为0，求得初始基可行解X=(0,0,0,4,0,1,9)T,建立初始单纯形表，迭代过程如下表。θi6 [6] 0 4 0 3 -3 11 -2 1 -1 0 -1 1 03 3 0 2 1 1 -1 0x4x2x700-Mcj-zj 6M-304M+103M-4M01--1基 b x1 x2 x3 x4 x5 x6 x7CBCj -3 0 1 0 0 -M -M4 1 1 1 1 0 0 01 -2 [1] -1 0 -1 1 09 0 3 1 0 0 0 1x4x6x70-M-Mcj-zj-2M-34M10-M00413基 b x1 x2 x3 x4 x5 x6 x7CBCj -3 0 1 0 0 -M -Mx4x2x100-3cj-zj-9/20 0 0 0 1 -1/2 1/2 -1/21 1 0 [2/3] 0 1/2 -1/2 1/63 0 1 1/3 0 0 0 1/300303/2-M-3/2-M+1/2θi--93/23/2 3/2 0 1 0 3/4 -3/4 1/45/2 -1/21 0 0 -1/4 1/4 1/4000 01-1/21/2-1/2x4x2x3001cj-zj000-3/4-M+3/4-M-1/4最优解X=(0,5/2,3/2,0,0,0,0)T（2）两阶段法

用人工变量