线性规划及其对偶问题

线性规划及其对偶问题1线性规划问题及其数学模型2线性规划问题的图解法3单纯形法4对偶问题5EXCEL求解线性规划6灵敏度分析1线性规划问题及其数学模型(1)线性规划问题例、生产组织与计划问题A,B各生产多少,可获最大利润?可用资源煤劳动力仓库AB123202单位利润4050306024解:设产品A,B产量分别为变量x1，x2可以建立如下的数学模型：MaxZ=40x1+50x2x1+2x2303x1+2x2602x224x1，x20s.t目标函数约束条件可用资源煤劳动力仓库AB123202单位利润4050306024例某建筑设计院设计每万ｍ２办公建筑和工业厂房需要的建筑师、结构工程师、设备工程师和电气工程师的平均人数列在表。问该院应如何安排设计任务，才能使设计费收入最大?专业建筑物建筑结构设备电器设计费收入（万元/万ｍ２）办公建筑532136工业厂房121220全院现有专业人数28261210解设办公建筑和工业厂房各承揽ｘ１、ｘ２万ｍ２。根据题意maxZ＝36x1＋20x25x1＋x2≤28s.t3x1＋2x2≤282x1＋x2≤12x1＋2x2≤10x1、x2≥02.9m钢筋架子100个，每个需用2.1m各1，原料长7.4m1.5m求：如何下料，使得残余料头最少。解：首先列出各种可能的下料方案；计算出每个方案可得到的不同长度钢筋的数量及残余料头长度；确定决策变量；根据下料目标确定目标函数；根据不同长度钢筋的需要量确定约束方程。例、合理下料问题设按第i种方案下料的原材料为xi根8,7,6,5,4,3,2,1100432030100002302010000002..4.18.02.01.109.03.01.087654321876543218765432187654321ixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxZMini为大于零的整数，组合方案123456782.9m211100002.1m021032101.5m10130234合计7.3m7.1m6.5m7.4m6.3m7.2m6.6m6.0m料长7.4m7.4m7.4m7.4m7.4m7.4m7.4m7.4m料头0.1m0.3m0.9m0.0m1.1m0.2m0.8m1.4m例、运输问题工厂123库存仓121350222430库334210需求401535运输单价求：运输费用最小的运输方案。解：设xij为i仓库运到j工厂的产品数量其中：i＝1，2，3j＝1，2，3MinZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13=50x21+x22+x23=30x31+x32+x33=10x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij0s.t(2)线性规划问题的特点决策变量：(x1…xn)T代表某一方案，决策者要考虑和控制的因素非负；目标函数：Z=ƒ(x1…xn)为线性函数，求Z极大或极小;约束条件：可用线性等式或不等式表示.具备以上三个要素的问题就称为线性规划问题。0,,,,,,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目标函数约束条件(3)线性规划模型一般形式隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,cj为确定值2线性规划问题的图解法20,.1XbAXtsCXZMinMax定义1：满足约束(2)的X=(X1…Xn)T称为线性规划问题的可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为线性规划问题的最优解。例1MaxZ=40X1+50X2X1+2X2303X1+2X2602X224X1,X20s.t解：(1)、确定可行域X1+2X2303X1+2X2602X224X10X202030100102030X2DABC2X224X1+2X2303X1+2X260X10X20可行域(2)、求最优解最优解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C点：X1+2X2=303X1+2X2=600203010102030X1X2DABC最优解Z=975可行解Z=0等值线例2、MaxZ=40X1+80X2X1+2X2303X1+2X2602X224X1,X20s.t解：(1)、确定可行域与上例完全相同。(2)、求最优解0203010102030DABC最优解Z=1200最优解：BC线段最优解：BC线段B点：X(1)=(6,12)C点：X(2)=(15,7.5)X=X(1)+(1-)X(2)(01)MaxZ=1200X1615X2127.5X==+(1-)X1=6+(1-)·15X2=12+(1-)·7.5X1=15-9X2=7.5+4.5(01)例3、MaxZ=2X1+4X22X1+X28-2X1+X22X1,X20s.tZ=08246X240X1-2X1+X222X1+X28X10X20可行域无界无有限最优解无有限最优解可行域无上界例4、MaxZ=3X1+2X2-X1-X21X1,X20无可行域无可行解-1X2-1X10s.tX20X10-X1-X21直观结论线性规划问题的解有四种情况唯一最优解无穷多最优解无有限最优解无可行解若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；若线性规划问题有最优解，则唯一最优解对应于可行域的一个顶点；无穷多个最优解对应于可行域的一条边；3单纯形法3.1线性规划问题的标准形式3.2线性规划问题的基本解3.3单纯形法的基本思想3.1线性规划问题的标准形式0,,,,,,.21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMinMax目标函数约束条件(1)线性规划模型一般形式价值系数决策变量技术系数右端常数0,b,,bbxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZMaxm21nmnmnmmnnnnnn0,,,.21221122222121112121112211(2)线性规划模型标准形式0.XbAXtsCXZMaxncccC21mnmmnnaaaaaaaaaA212222111211nxxxX21价值向量决策向量系数矩阵mbbbb21右端向量(3)线性规划模型矩阵形式对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:(4)一般型向标准型的转化目标函数目标函数为极小化约束条件分两种情况：大于、小于决策变量可能存在小于零的情况3.2线性规划问题的基本解302.1XbAXtsCXZMax(1)解的基本概念定义在线性规划问题中，约束方程组(2)的系数矩阵A(假定)的任意一个阶的非奇异(可逆)的子方阵B(即)，称为线性规划问题的一个基阵或基。mm0BnmmnmmmmmmmmnmmmnmmmaaaaaaaaaaaaaaaaaaA212122212222211211111211mmmmmmaaaaaaaaaB212222111211mnmmmmnmmnmmaaaaaaaaaN212221212111基阵非基阵TmBxxxX21TnmmNxxxX21基向量非基向量基变量非基变量NBANBXXXbAXbXXNBNBbNXBXNBNBNXbBXNBNXBbBX11NBXXXNNXNXBbBX11令0NX则01bBX定义在约束方程组(2)中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。定义在基本解中，若该基本解满足非负约束，即，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。01bBXB基本解中最多有m个非零分量。基本解的数目不超过个。!!!mnmnCmnNBNBNNNBNNBBNBNBXNBCCbBCXCNXBbBCXCXCXXCCCXZ)()(),(111101bBXB01NBCCBNNBX若B满足下列条件，称为最优基称为最优解例现有线性规划问题0,24261553.221212121xxxxxxtsxxZMax试求其基本解、基本可行解。解:(1)首先将原问题转化为标准型引入松弛变量x3和x40,,,2402615053.243214321432121xxxxxxxxxxxxtsxxZMax(2)求基本解由上式得10260153A2415b可能的基阵10260153A265312B061313B160314B021523B120524B100134B612121234!24!2!424C由于所有|B|≠0，所以有6个基阵和6个基本解。242615532121xxxx对于基阵265312B令03x04x则TX0043415246153131xxx对于基阵令02x04x则TX0304061313B为基本可行解，B13为可行基为基本可行解，B12为可行基246153411xxx对于基阵令02x03x则TX6005242155232xxx对于基阵令01x04x则TX045120160314B021523B242155422xxx对于基阵令01x03x则TX18030241543xx对于基阵令01x02x则TX241500120524B100134B为基本可行解，B24为可行基为基本可行解，B34为可行基0ABCDETX0043415TX0304TX6005TX241500TX18030TX045120所以，本问题存在6个基本解，其中4个为基可行解.(2)几点结论若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点);线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点);若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到;线性规划问题的基可行解(极点)的个数是有限的,不会超过个.mnC上述结论说明:线性规划的最优