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

第1页运筹帷幄之中决胜千里之外线性规划LinearProgramming第2页第一章线性规划及单纯形法★线性规划问题★线性规划模型★线性规划的图解法★可行域的性质★线性规划的基本概念★基础解、基础可行解★单纯形表第3页§1.1线性规划问题及其数学模型●生产计划问题●配料问题●背包问题●运输问题●指派问题●下料问题第4页1.生产计划问题（ProductionPlanning）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。第5页产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：maxz=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80001.5x1+3.0x2+3.5x3+1.0x4≤5000x1,x2,x3,x4≥0目标函数约束条件变量非负约束这个问题的最优解为：x1=294.12件，x2=1500件，x3=0，x4=58.82件最大利润为：z=12737.06元。第6页2.配料问题（MaterialBlending）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（％），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（％）如下表：T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。第7页T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276minz=115x1+97x2+82x3+76x4s.t.3.21x1+4.53x2+2.19x3+1.76x4≥320Cr的含量下限约束2.04x1+1.12x2+3.57x3+4.33x4≥210Mn的含量下限约束5.82x1+3.06x2+4.27x3+2.73x4≥430Ni的含量下限约束x1+x2+x3+x4=100物料平衡约束x1,x2,x3,x4≥0设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。这个问题的最优解为：x1=26.58,x2=31.57,x3=41.84，x4=0（公斤）,最低成本为z=9549.87元。第8页3.背包问题（KnapsackProblem）一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：物品1物品2物品3重量（公斤/件）104120价值（元/件）177235求背包中装入每种物品各多少件，使背包中物品总价值最高。第9页设三种物品的件数各为x1，x2，x3件，总价值为z。maxz=17x1+72x2+35x3s.t.10x1+41x2+20x3≤50x1，x2，x3≥0x1，x2，x3为整数这是一个整数规划问题（IntegerProgramming）。最优解为：x1=1，x2=0，x3=2件，最高价值z=87元。物品1物品2物品3重量（公斤/件）104120价值（元/件）177235第10页4.指派问题（AssignmentProblem）有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由第i个人完成第j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：项任务个人被指派完成第第项任务个人不从事第第ji1ji0xij1,0xn,...,2,1i1xn,...,2,1j1x.t.sxczmax(min)ijn1jijn1iijn1in1jijij第14页①每一个问题都有一组变量——称为决策变量，一般记为上述例子的共同点：②每个问题中都有决策变量需满足的一组约束条件——线性的等式或不等式。.,,,21nxxx).,2,1(,0nixi线性规划问题的数学模型通常要求决策变量取值非负，即第15页③都有一个关于决策变量的线性函数——称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linearprogramming)第16页16一般地，假设线性规划数学模型中，有m个约束，有n个决策变量xj,j=1,2…,n，目标函数的变量系数用cj表示,cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成112211112211211222221122max(min)(,)(,)(,)0,1,2,,nnnnnnmmmnnmjZcxcxcxaxaxaxbaxaxaxbaxaxaxbxjn或或或线性规划问题的数学模型第17页线性规划模型线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：0x,x,x9x4+x+x8xx+x+x2.t.sxx2+x3=zmin32132113212121≥≤≤112211112211211222221122max(min)(,)(,)(,)0,1,2,,nnnnnnmmmnnmjZcxcxcxaxaxaxbaxaxaxbaxaxaxbxjn或或或第18页线性规划的标准形式maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn＝b1a21x1+a22x2+……+a2nxn＝b2……am1x1+am2x2+……+amnxn＝bmx1,x2,……,xn≥0目标函数为极大化，约束条件全部为等号约束，右端常数项bj均为非负，所有变量全部是非负的，这样的线性规划模型称为标准形式第19页线性规划模型用矩阵和向量表示maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn＝b1a21x1+a22x2+……+a2nxn＝b2……am1x1+am2x2+……+amnxn＝bmx1,x2,……,xn≥0mn2m1mn22221n11211aaaaaaaaaAm21bbbbncccc...,21n21xxxX记第20页矩阵形式：向量形式：njaaaPmjjjj,,2,1,21其中0..max,2,111nnnxxxbxPxPtsCXz0..maxXbAXtsCXz第21页线性规划模型总结线性规划模型的结构目标函数：max，min约束条件：≥,=,≤变量符号：：≥0,≤0,Free线性规划的标准形式目标函数：max约束条件：=右端常数项：≥0变量符号：≥0FreeXbAXtsCXz,0)(),(..max(min)MaxZ=CXs.t.AX=bX≥0第22页线性规划问题的标准化▲极小化目标函数转化为极大化▲小于等于约束条件转化为等号约束▲大于等于约束条件转化为等号约束▲右端常数项小于等于0的标准化▲变量小于等于0的标准化▲变量没有符号限制（Free）的标准化第23页minz=2x1-3x2+x3令z’=-z，z’=-2x1+3x2-x3新的目标函数maxz’=-2x1+3x2-x3取得极大化的最优解时，这个最优解同时使原目标函数值取得最小化的最优解。但两个问题最优解的目标函数值相差一个负号。一、极小化目标函数问题转化为极大化目标函数第24页例如，对于以下两个线性规划问题minz=2x1+3x2s.t.x1+x2≤3x2≤1(A)x1,x2≥0maxz’=-2x1-3x2s.t.x1+x2≤3x2≤1(B)x1,x2≥0它们的最优解都是x1=2,x2=1，但(A)的最小化的目标函数值为minz=7，(B)的最大化的目标函数值为maxz’=-7第25页2x1+3x2-4x3≤5引进松弛变量(Slackvariable)2x1+3x2-4x3+x4=5如果有一个以上小于等于约束，要对于每一个约束引进不同的松弛变量。例如：2x1+3x2-4x3≤53x1-2x2+5x3≤8在两个约束中分别引进松弛变量x4，x5≥02x1+3x2-4x3+x4=53x1-2x2+5x3+x5=8二、小于等于约束条件转化为等号约束04x第26页例如：2x1+3x2-4x3≥53x1-2x2+5x3≥8在两个约束的左边分别减去剩余变量x4，x5≥02x1+3x2-4x3-x4=53x1-2x2+5x3-x5=8三、大于等于约束条件转化为等号约束第27页四、右端常数项小于等于0的标准化当右端常数项为小于等于0时，如：2x1-3x2+4x3≥-4只需不等式两边同乘以-1，再加上松弛变量即可-2x1+3x2-4x3≤4第28页五、变量小于等于0的的标准化六、变量没有符号限制(Free)的标准化代入模型令,0,0,xxxxx代入模型令,0,xxx第29页例如：minz=x1+2x2-3x3s.t.2x1+3x2-4x3≤53x1-2x2+5x3≥8x1≥0,x2:free,x3≥0先将目标函数转化为极大化，并在约束中引进松弛变量和剩余变量，把不等式约束变为等式Maxz’=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4=53x1-2x2+5x3-x5=8x1≥0,x2:free,x3,x4,x5≥0第30页Maxz’=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4=53x1-2x2+5x3-x5=8x1≥0,x2:free,x3,x4,x5≥0然后，令x2=x2’-x2”，其中x2’,x2”≥0,代入模型:Maxz’=-x1-2(x’2-x”2)+3x3s.t.2x1+3(x’2-x”2)-4x3+x4=53x1-2(x’2-x”2)+5x3-x5=8x1,x’2,x”2,x3,x4,x5≥0整理，得到标准形式：Maxz’=-x1-2x’2+x”2+3x3s.t.2x1+3x’2-3x”2-4x3+x4=53x1-2x’2+2x”2+5x3-x5=8x1,x’2,x”2,x3,x4,x5≥0第31页练习：minz=2x1-x2+4x3s.t.x1+x2-x3≤33x1-x2+2x3≥6x1-3x2-4x3≥-4x1≤0,x3≥0第32页对于模型中只有两个变量的线性规划问题，可以通过在平面上作图的方法求解。一个线性规划问题有解，是指能找出一组xj(j=1,2……,n)，满足约束条件，称这组xj为问题的可行解。通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域，可行域中使目标函数为最优的可行解为最优解。§1.2图解法第33页线性规划的图解maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行