第一章、线性规划及单纯形方法

1、LinearProgramming,第一章线性规划及单纯形法,线性规划问题线性规划模型线性规划的图解法可行域的性质线性规划的基本概念基础解、基础可行解单纯形表,1.1线性规划问题及其数学模型,生产计划问题配料问题背包问题运输问题指派问题下料问题,1.生产计划问题（ProductionPlanning）,某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：,求使得总利润最大的生产计划。,设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：,maxz=5.24x1+7.

2、30 x2+8.34x3+4.18x4s.t.1.5x1+1.0 x2+2.4x3+1.0 x420001.0 x1+5.0 x2+1.0 x3+3.5x480001.5x1+3.0 x2+3.5x3+1.0 x45000 x1,x2,x3,x40,目标函数,约束条件,变量非负约束,这个问题的最优解为：x1=294.12件，x2=1500件，x3=0，x4=58.82件最大利润为：z=12737.06元。,2.配料问题（MaterialBlending）,某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料

3、的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：,要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。,minz=115x1+97x2+82x3+76x4s.t.3.21x1+4.53x2+2.19x3+1.76x4320Cr的含量下限约束2.04x1+1.12x2+3.57x3+4.33x4210Mn的含量下限约束5.82x1+3.06x2+4.27x3+2.73x4430Ni的含量下限约束x1+x2+x3+x4=100物料平衡约束x1,x2,x3,x40,设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。,这个问题的最优解为：x1=

4、26.58,x2=31.57,x3=41.84，x4=0（公斤）,最低成本为z=9549.87元。,3.背包问题（KnapsackProblem）,一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：,求背包中装入每种物品各多少件，使背包中物品总价值最高。,设三种物品的件数各为x1，x2，x3件，总价值为z。maxz=17x1+72x2+35x3s.t.10 x1+41x2+20 x350 x1，x2，x30 x1，x2，x3为整数这是一个整数规划问题（IntegerProgramming）。最优解为：x1=1，x2=0，x3=2件，最高价值z=87

5、元。,4.指派问题（AssignmentProblem）,有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由第i个人完成第j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：,张、王、李、赵四位老师被分配教语文、数学、物理、化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教这四门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。,例题,设：,maxz=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90 x32+74x33+

6、65x34+93x41+61x42+83x43+75x44s.t.x11+x12+x13+x14=1(1)x21+x22+x23+x24=1(2)x31+x32+x33+x34=1(3)x41+x42+x43+x44=1(4)x11+x21+x31+x41=1(5)x12+x22+x32+x42=1(6)x13+x23+x33+x43=1(7)x14+x24+x34+x44=1(8)xij=0,1,最优解为：x14=1，x23=1，x32=1，x41=1，maxz=336即张老师教化学，王老师教语文，李老师教数学，赵老师教语文。,四门课的总分可以达到336分。,每一个问题都有一组变量称为决策变

7、量，一般记为,上述例子的共同点：,每个问题中都有决策变量需满足的一组约束条件线性的等式或不等式。,线性规划问题的数学模型,通常要求决策变量取值非负，即,都有一个关于决策变量的线性函数称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。,将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linearprogramming),一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj,j=1,2,n，目标函数的变量系数用cj表示,cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi

8、称为资源限量。则线性规划数学模型的一般表达式可写成,线性规划问题的数学模型,线性规划模型,线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：,线性规划的标准形式,maxz=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1,x2,xn0目标函数为极大化，约束条件全部为等号约束，右端常数项bj均为非负，所有变量全部是非负的，这样的线性规划模型称为标准形式,线性规划模型用矩阵和向量表示,maxz=c1x1+c2x2+cnxns.t.a

9、11x1+a12x2+a1nxnb1a21x1+a22x2+a2nxnb2am1x1+am2x2+amnxnbmx1,x2,xn0,记,矩阵形式：,向量形式：,其中,线性规划模型总结,线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,0,Free线性规划的标准形式目标函数：max约束条件：=右端常数项：0变量符号：0,MaxZ=CXs.t.AX=bX0,线性规划问题的标准化,极小化目标函数转化为极大化小于等于约束条件转化为等号约束大于等于约束条件转化为等号约束右端常数项小于等于0的标准化变量小于等于0的标准化变量没有符号限制（Free）的标准化,minz=2x1-3x2+

10、x3令z=-z，z=-2x1+3x2-x3新的目标函数maxz=-2x1+3x2-x3取得极大化的最优解时，这个最优解同时使原目标函数值取得最小化的最优解。但两个问题最优解的目标函数值相差一个负号。,一、极小化目标函数问题转化为极大化目标函数,例如，对于以下两个线性规划问题,minz=2x1+3x2s.t.x1+x23x21(A)x1,x20,maxz=-2x1-3x2s.t.x1+x23x21(B)x1,x20,它们的最优解都是x1=2,x2=1，但(A)的最小化的目标函数值为minz=7，(B)的最大化的目标函数值为maxz=-7,2x1+3x2-4x35引进松弛变量(Slackvaria

11、ble)2x1+3x2-4x3+x4=5如果有一个以上小于等于约束，要对于每一个约束引进不同的松弛变量。例如：2x1+3x2-4x353x1-2x2+5x38在两个约束中分别引进松弛变量x4，x502x1+3x2-4x3+x4=53x1-2x2+5x3+x5=8,二、小于等于约束条件转化为等号约束,例如：2x1+3x2-4x353x1-2x2+5x38在两个约束的左边分别减去剩余变量x4，x502x1+3x2-4x3-x4=53x1-2x2+5x3-x5=8,三、大于等于约束条件转化为等号约束,四、右端常数项小于等于0的标准化,当右端常数项为小于等于0时，如：2x1-3x2+4x3-4只需不等

12、式两边同乘以-1，再加上松弛变量即可-2x1+3x2-4x34,五、变量小于等于0的的标准化,六、变量没有符号限制(Free)的标准化,例如：minz=x1+2x2-3x3s.t.2x1+3x2-4x353x1-2x2+5x38x10,x2:free,x30先将目标函数转化为极大化，并在约束中引进松弛变量和剩余变量，把不等式约束变为等式Maxz=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4=53x1-2x2+5x3-x5=8x10,x2:free,x3,x4,x50,Maxz=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4=53x1-2x2+5x3-x5=8x10,x

13、2:free,x3,x4,x50然后，令x2=x2-x2”，其中x2,x2”0,代入模型:Maxz=-x1-2(x2-x”2)+3x3s.t.2x1+3(x2-x”2)-4x3+x4=53x1-2(x2-x”2)+5x3-x5=8x1,x2,x”2,x3,x4,x50整理，得到标准形式：Maxz=-x1-2x2+x”2+3x3s.t.2x1+3x2-3x”2-4x3+x4=53x1-2x2+2x”2+5x3-x5=8x1,x2,x”2,x3,x4,x50,练习：minz=2x1-x2+4x3s.t.x1+x2-x333x1-x2+2x36x1-3x2-4x3-4x10,x30,对于模型中只有两

14、个变量的线性规划问题，可以通过在平面上作图的方法求解。一个线性规划问题有解，是指能找出一组xj(j=1,2,n)，满足约束条件，称这组xj为问题的可行解。通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域，可行域中使目标函数为最优的可行解为最优解。,1.2图解法,线性规划的图解,maxz=x1+3x2s.t.x1+x26-x1+2x28x10,x20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,问题：1、线性规划的最优解是否可能位于可行域的内部？又是否可能位于可行域的边界上？,线性规划的图解,maxz=x1+3x2s.t.x1+x26-x1+2x28x10,x

15、20,可行域,目标函数等值线,最优解,z=6,z=3,z=9,z=12,问题：2、若目标函数改为maxz=x1+x2，可行域不变，那么线性规划的最优解在哪里取得？,线性规划可行域和最优解的几种情况,1、可行域封闭唯一最优解,2、可行域封闭多个最优解,3、可行域开放唯一最优解,4、可行域开放多个最优解,5、可行域开放目标函数无界,6、无可行解,图解法得到的启示,（1）解的情况：唯一最优解；无穷多最优解；无界解；无可行解（2）若可行域存在，则可行域是一个凸集（3）若最优解存在，则一定在可行域（凸集）的某个顶点处取得（4）解题思路：找出凸集的任意顶点，该点的目标函数值与相邻顶点的比较，若该点函数值大

16、，则该点为最优解；否则转到目标函数值更大的顶点，如此重复下去，直到找到最优解,1.3单纯形法原理,理论方法算法步骤单纯形表算例,一、基本概念,可行解：满足AX=b,且X0的解称为可行解。,最优解：使目标函数达到最大值的可行解称为最优解。,其中A为mn阶矩阵,基：设B是系数矩阵A的一个mn阶的满秩子矩阵，称B是(LP)的一个基。,可行域：全部可行解的集合称为可行域。,基本概念,不失一般性，设,B中每一个向量称为基向量，与基向量对应的变量称为基变量,其余的变量称为非基变量.,基解：令所有的非基变量为零所得到的唯一的解,基可行解：满足非负约束条件X0的基解,可行基：对应与基可行解的基,求解mm的线性

17、方程组，令非基变量等于0，得到基变量的一组解，连同等于0的非基变量这n个变量的值称为线性规划的一个基解,如果一个基解中的所有变量都是非负的这个基解称为基可行解。,例1考虑问题,系数矩阵,基,maxZ=2x1+3x2+x3s.t.x1+x35x1+2x2+x410 x2+x54xi0(i=1,5),例2,maxZ=2x1+3x2+x3s.t.x1+x35x1+2x2+x410 x2+x54xi0(i=1,5),例2,至少n-m个,问：基解中零的个数至少有多少个？,maxz=x1+2x2s.t.x1+x23x21x1,x20,maxz=x1+2x2s.t.x1+x2+x3=3x2+x4=1x1,x

18、2,x3,x40,x1=0,x2=0 x3=3,x4=1基可行解,x1=0,x4=0 x2=1,x3=2基可行解,x2=0,x3=0 x1=3,x4=1基可行解,x3=0,x4=0 x1=2,x2=1基可行解,x1=0,x3=0 x2=3,x4=-2是基解，但不是可行解,O,A,B,x3=0,x4=0,x2=0,x1=0,C,D,可行域,例3,二、凸集和顶点,1.凸集：如果集合C中任意两点x1，x2，其连线上的所有点也都是集合C中的点，则称C为凸集，其中x1，x2的连线可以表示为：x1（1）x2(01)数学解析式为：任意x1C，x2C，有x1（1）x2C(01)，则C为凸集。,2.顶点如果集合

19、C中不存在任何两个不同的点x1，x2，使x为这两点连线上的一个点，即对任何不同的x1C，x2C，不存在x=x1（1）x2(01)，则称x为凸集的顶点。,凸集和顶点,三、几个基本定理,定理1线性规划问题的可行域是凸集证：设X1、X2为可行域C内的任意两点,则,有,故C为凸集,对于,三、几个基本定理,引理线性规划问题的可行解为基可行解的充要条件是它的正分量所对应的系数列向量线性无关。,证：(1)必要性,设可行解,若X为基本可行解，则取正值的变量必是基变量，它们所对应的约束矩阵A中的列向量A1,Ak是基向量，故必线性无关。,三、几个基本定理,引理线性规划问题的可行解为基可行解的充要条件是它的正分量所

20、对应的系数列向量线性无关。,证：,（2）充分性,因为A的秩为m,则可以从其余向量中找,构成一个基，其对应的解为X,故X为基可行解.,出m-k个与,定理2LP的基可行解对应可行域的顶点,证(1)充分性：,由引理知线性相关,即存在一组不全为零的数,使得,假设顶点X不是基可行解,不妨设它的前k个分量为正,则有,用反证法,2020/7/4,51,(2)必要性,仍用反证法,因此X不是基可行解。,2020/7/4,53,定理3若线性规划问题有最优解,一定存在一个基可行解是最优解,总结几个基本定理,定理1若线性规划问题存在可行解，则问题的可行域是凸集。引理线性规划问题的可行解X(x1,x2,xn)T为基可行

21、解的充要条件是X的正分量所对应的系数列向量是线性无关的。定理2线性规划问题的基可行解X对应线性规划问题可行域的顶点。定理3若线性规划问题有最优解，一定存在一个基可行解是最优解。,问题：,1.可行域顶点的个数是否有限？,2.最优解是否一定在可行域顶点上达到？,3.如何找到顶点？,4.如何从一个顶点转移到另一个顶点?,maxZ=6x1+5x2x1+3x2902x1+x2752x1+2x280 x1,x20,maxZ=6x1+5x2x1+3x2+x3902x1+x2+x4752x1+2x2+x580 xi0，i=1,5,找一个基可行解，X(0)（0，0，90，75，80），Z=0(1)Z6x1+5x

22、2，x1的系数C16大于C2=5；选择x1为新的基变量。X3=90-(x1+3x2)当x3=0，X2=0时，x1=90X4=75-(2x1+x2)当x4=0，X2=0时，x1=37.5X5=80-(2x1+2x2)当x5=0，X2=0时，x1=40,最小,选择x4为换出变量即x40,四、单纯形法迭代原理,线性规划的代数解法,例,Z中x2的系数C22大于0；选择x2为新的基变量。x3=52.5-(2.5x2-0.5x4)当x3=0，x4=0时，x2=21x1=75/2-(0.5x2+0.5x4)当x1=0，x4=0时，x2=75x5=5-(x2-x4)当x5=0，x4=0时，x2=5所以选择x5

23、为换出变量,x2为换入变量,最小,则X(1)（37.5，0，52.5，0，5）T，Z2252x2-3x4,(2）仍然用非基变量表示基变量x3=52.5-(2.5x2-0.5x4)x1=75/2-(0.5x2+0.5x4)x5=5-(x2-x4),(3)用非基变量表示基变量x3=40-(1.5x4-2.5x5)x1=35-(x4-0.5x5)x2=5-(x5-x4),则X(2)（35,5,40,0,0)T,X(2)为最优解,Z235-x4-2x5,单纯形法原理示意图,顶点4，最优解,初始顶点1,顶点2,顶点3,其实，不必搜索可行域的每一个顶点，只要从一个顶点出发，沿着使目标函数改善的方向，到达下

24、一个相邻的顶。如果相邻的所有顶点都不能改善目标函数，这个顶点就是最优顶点。用这样的搜索策略，可以大大减少搜索顶点的个数。按照这样的搜索策略建立的算法，叫做单纯形法。,目标函数改善,目标函数改善,目标函数改善,单纯形法,1.确定初始基可行解设标准线性规划问题的系数矩阵为：,注：当约束条件均为号时，松弛变量系数矩阵即为单位矩阵；当约束条件或时,构造人工基.,令非基变量等于0，即可得初始基可行解：,定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基.,代入约束方程组有,设初始基可行解为,2、从一个基可行解转换为相邻的另一个基可行解,2020/7/4,62,则,故X(1)是一个可行解,202

25、0/7/4,63,3、最优性检验,讨论,1.4单纯形法计算步骤,1.将非标准型线性规划化为标准型2.确定初始基可行解：一般设松弛变量为初时基可行解3.判断：若所有的非基变量的检验数j0，则此解为LP的最优解，若存在某一非基变量的检验数j0，则问题还没有达到最优解，需进行改进4.迭代：选换入变量maxcj-zj/cj-zj0假设xk为换入变量；选换出变量minbi/aik，aik0，假设选取xl为换出变量；然后迭代，使得alk1，其余aik为0,1.4单纯形法计算步骤,单纯形法的计算步骤如下：第1步：求初始基可行解，列出初始单纯形表。对非标准型的线性规划问题首先要化成标准形式。由于总可以设法使约

26、束方程的系数矩阵中包含一个单位矩阵，以此作为基求出问题的一个初始基可行解。为了书写规范和便于计算，对单纯形法的计算设计了一种表格，称为单纯形表(见表1-5),第4步：重复第2，3两步，一直到计算结束为止。,单纯形表求解线性规划问题,maxZ=6x1+5x2x1+3x2902x1+x2752x1+2x280 x1,x20,maxZ=6x1+5x2x1+3x2+x3902x1+x2+x4752x1+2x2+x580 xi0,i=1,.,5,例,x1为换入变量即新的基变量。,所以把x4换出基变量，作为非基变量，。,所以把x5换出为非基变量，x2为换入变量即新的基变量。,此时所有的检验数都小于等于0，

27、所以该解为最优解。,最优解为X（35，5，40，0，0）T，Z*235,Step0获得一个初始的单纯形表，确定基变量和非基变量Step1检查基变量在目标函数中的系数是否等于0，在约束条中的系数是否是一个单位矩阵。Step2如果表中非基变量在目标函数中的系数全为负数，则已得到最优解。停止。否则选择系数为正数且值最大的变量进基，转step3。Step3如果进基变量在约束条件中的系数全为负数或0，则可行域开放，目标函数无界。停止。否则选取左边常数和正的系数的最小比值，对应的基变量离基，转step4。Step4确定进基变量的列和离基变量的行交叉的元素为“主元”，对单纯形表进行行变换，使主元变为1，主元

28、所在列的其他元素变为0。将离基的基变量的位置用进基的非基变量代替。转step2。,单纯形表的算法描述,1.maxZ=3x1+9x2x1+3x221-x1+x24x1,x20,maxZ=3x1+9x2x1+3x2+x321-x1+x2+x44xi0,举例,所以把x4换出为非基变量，x2为换入变量即新的基变量。,所以把x3换出为非基变量，x1为换入变量即新的基变量。,此时所有的检验数都小于等于0，所以该解为最优解。,最优解为X（9/4，25/4，0，0）T，Z*63,由于非基变量x4的检验数0，所以我们可以把它作为换入基变量来考虑。,此时所有的检验数都小于等于0，所以该解为最优解。Z*=63,1.

29、maxZ=x1+x2-2x1+x24x1-x22x1,x20,maxZ=x1+x2-2x1+x2+x34x1-x2+x42xi0,举例,所以把x3换出为非基变量，x2为换入变量即新的基变量。,可以看出，x1的检验数为3，大于0，但是x1的系数列向量中的所有元素（-2,-1）T，都小于0，所以该题为无界解.,1.5单纯形法的进一步讨论,一、人工变量法（大M法）约束条件：“”：则减去一个剩余变量后，再加一个人工变量.“”：则加一个人工变量.目标函数：人工变量的系数为“M”，即罚因子.若线性规划问题有最优解则人工变量必为0.,例题,人工变量,二、两阶段法,基本思想第一阶段：通过求解辅助问题的最优基可行解得到原问题的初始基可行解.第二阶段：求原问题的最优解.算例,1.5单纯形法的进一步讨论,第一阶段构造辅助问题：给原问题加入人工变量，并构造一个仅含人工变量的目标函数（求极小化），人工变量的系