第一章-线性规划与单纯形法

天津大学老教授协会2011考研辅导运筹学辅导§1线性规划模型第一章线性规划例1.1生产计划问题（资源利用问题）胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？解：将一个实际问题转化为线性规划模型有以下几个步骤：解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大maxz=50x1+30x2解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大maxz=50x1+30x23．确定约束条件：4x1+3x2120（木工工时限制）2x1+x250（油漆工工时限制）解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大maxz=50x1+30x23．确定约束条件：4x1+3x2120（木工工时限制）2x1+x250（油漆工工时限制）4．变量取值限制：一般情况，决策变量只取正值（非负值）x10,x20解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大maxz=50x1+30x23．确定约束条件：4x1+3x2120（木工工时限制）2x1+x250（油漆工工时限制）4．变量取值限制：一般情况，决策变量只取正值（非负值）x10,x20数学模型maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20线性规划数学模型三要素：决策变量、约束条件、目标函数线性规划模型的三要素3.约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示；1.决策变量：需决策的量，即待求的未知数；2.目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；建立线性规划问题的数学模型的例子例1.2营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？食品名称热量（千卡）蛋白质（克）钙（毫克）价格（元)猪肉10005040014鸡蛋800602006大米900203003白菜200105002各种食物的营养成分表解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，x3，x40线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn(=,)b1a21x1+a22x2+….+a2nxn(=,)b2………………….am1x1+am2x2+….+amnxn(=,)bmx1,x2….xn0§2线性规划问题图解法•图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。§2线性规划问题图解法（1）满足约束条件的变量的值，称为可行解。§2线性规划问题图解法（1）满足约束条件的变量的值，称为可行解。（2）使目标函数取得最优值的可行解，称为最优解。§2线性规划问题图解法（1）满足约束条件的变量的值，称为可行解。（2）使目标函数取得最优值的可行解，称为最优解。例1.1的数学模型maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20x2504030201010203040x14x1+3x2120由4x1+3x2120x10x20围成的区域x2504030201010203040x12x1+x250由2x1+x250x10x20围成的区域x2504030201010203040x12x1+x2504x1+3x2120可行域同时满足：2x1+x2504x1+3x2120x10x20的区域——可行域x2504030201010203040x1可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解集合。该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形x2504030201010203040x1可行域目标函数是以S作为参数的一组平行线x2=S/30-（5/3）x1x2504030201010203040x1可行域当S值不断增加时，该直线x2=S/30-（5/3）x1沿着其法线方向向右上方移动。x2504030201010203040x1可行域当该直线移到Q2点时，S（目标函数）值达到最大：MaxS=50*15+30*20=1350此时最优解=（15，20）Q2（15，20）二个重要结论：•满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。二个重要结论：•满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。•最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。解的讨论：最优解是唯一解；解的讨论：最优解是唯一解；无穷多组最优解：例1.1的目标函数由maxS=50x1+30x2变成：maxS=40x1+30x2s.t.4x1+3x21202x1+x250x1,x20x2504030201010203040x1可行域目标函数是同约束条件：4x1+3x2120平行的直线x2=S/30-（4/3）x1x2504030201010203040x1可行域当S的值增加时，目标函数同约束条件：4x1+3x2120重合，Q1与Q2之间都是最优解。Q1（25，0）Q2（15，20）解的讨论：无界解：例：maxS=x1+x2s.t.-2x1+x240x1-x220x1,x20x2504030201010203040x1该可行域无界，目标函数值可增加到无穷大，称这种情况为无界解或无最优解。解的讨论：无可行解：例：maxS=2x1+3x2s.t.x1+2x28x14x23-2x1+x24x1,x20该问题可行域为空集，即无可行解，也不存在最优解。解的情况：•有可行解⊙有唯一最优解⊙有无穷最优解⊙无最优解•无可行解§3线性规划问题的标准形式MaxS=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn=b1a21x1+a22x2+….+a2nxn=b2………………….am1x1+am2x2+….+amnxn=bmx1,x2….xn0其中：bi0(i=1,2,….m)线性规划问标准形的向量形式),,2,1(0),,2,1(.11njxmibxatsxcMaxSjinjjijnjjj线性规划标准型的矩阵形式MaxS=CXs.t.AX=bX0a11a12….a1nb1A=a21a22….a2nb=b2…………………………………….am1am2….amnbnc1x10c2x20C=X=0=……………..cnxn0如何将一般问题化为标准型：•若目标函数是求最小值MinS=CX令S’=-S,则MaxS’=-CX如何将一般问题化为标准型：•若目标函数是求最小值MinS=CX令S’=-S,则MaxS’=-CX•若约束条件是不等式如何将一般问题化为标准型：•若目标函数是求最小值MinS=CX令S’=-S,则MaxS’=-CX•若约束条件是不等式若约束条件是“”不等式naijxj+si=bij=1si0是非负的松驰变量如何将一般问题化为标准型：若约束条件是“”不等式naijxj-si=bij=1si0是非负的松驰变量如何将一般问题化为标准型：•若约束条件右面的某一常数项bi0这时只要在bi相对应的约束方程两边乘上-1。如何将一般问题化为标准型：•若约束条件右面的某一常数项bi0这时只要在bi相对应的约束方程两边乘上-1。•若变量xj无非负限制引进两个非负变量xj’xj”0令xj=xj’-xj”（可正可负）如何将一般问题化为标准型：•若约束条件右面的某一常数项bi0这时只要在bi相对应的约束方程两边乘上-1。•若变量xj无非负限制引进两个非负变量xj’xj”=0令xj=xj’-xj”（可正可负）任何形式的线性规划总可以化成标准型例1.3将下列问题化成标准型:MinS=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20x3无非负限制MaxS=x1-2x2+3x3’-3x3”s.t.x1+x2+x3’-x3”+x4=7x1-x2+x3’-x3”-x5=2-3x1+x2+2x3’-2x3”=5x1,x2,x3’,x3”,x4,x50§4单纯形方法一线性规划问题解的概念线性规划标准型的矩阵形式：MaxS=CX（1-9）s.t.AX=b（1-10）X0（1-11）a11a12….a1nb1A=a21a22….a2nb=b2………………………………………am1am2….amnbnc1x10c2x20C=X=0=……………..cnxn0•解、可行解、最优解⊙满足约束条件（1-10）的X，称为线性规划问题的解。•解、可行解、最优解⊙满足约束条件（1-10）的X，称为线性规划问题的解。⊙满足约束条件（1-10）与（1-11）的X，称为线性规划的问题可行解。•解、可行解、最优解⊙满足约束条件（1-10）的X，称为线性规划问题的解。⊙满足约束条件（1-10）与（1-11）的X，称为线性规划的问题可行解。⊙满足目标函数（1-9）的可行解X，称为线性规划的问题最优解。•基、基向量、基变量⊙设r(A)=m,并且B是A的m阶非奇异的子矩阵（det(B)0),则称矩阵B为线性规划问题的一个基。•基、基向量、基变量⊙设r(A)=m,并且B是A的m阶非奇异的子矩阵（det(B)0),则称矩阵B为线性规划问题的一个基。⊙矩阵B=（P1，P2….Pm)，其列向量Pj称为对应基B的基向量。•基、基向量、基变量⊙设r(A)=m,并且B是A的m阶非奇异的子矩阵（det(B)0),则称矩阵B为线性规划问题的一个基。⊙矩阵B=（P1，P2….Pm)，其列向量Pj称为对应基B的基向量。⊙与基向量Pj相对应的变量xj就称为基变量，其余的就称为非基变量。•基解.基可行解.可行基⊙对于某一特定的基B，非基变量取0值的解，称为基解。•基解.基可行解.可行基⊙对于某一特定的基B，非基变量取0值的解，称为基解。⊙满足非负约束条件的基解，称为基可行解。•基解.基可行解.可行基⊙对于某一特定的基B，非基变量取0值的解，称为基解。⊙满足非负约束条件的基解，称为基可行解。⊙与基可行解对应的基，称为可行基。为了理解基解.基可行解.最优解的概念，用下列例子说明：例1.4：maxS=2x1+3x2（1-12）s.t.-2x1+3x26（1-13-1）3x1-2x26（1-13-2）x1+x24（1-13-3）x1,x20（1-14）将其划为标准形式：例1.4：maxS=2x