第一讲线性规划及其对偶问题运筹学

运筹学主要内容第一讲线性规划及其对偶问题第二讲线性规划建模第三讲非线性规划:无约束问题第四讲非线性规划:约束极值问题第五讲原始对偶算法与拉格朗日松弛算法第五讲对策论（博弈论）第六讲信息经济学（机制设计）第六讲决策论第七讲整数规划扩展第八讲智能算法第一讲线性规划及其对偶问题1线性规划问题及其数学模型2线性规划问题的图解法3单纯形法4对偶问题5EXCEL求解线性规划6灵敏度分析1线性规划问题及其数学模型(1)线性规划问题例1、生产组织与计划问题A,B各生产多少,可获最大利润?可用资源煤劳动力仓库AB123202单位利润4050306024解:设产品A,B产量分别为变量x1，x2可以建立如下的数学模型：Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目标函数约束条件2.9m钢筋架子100个，每个需用2.1m各1，原料长7.4m1.5m求：如何下料，使得残余料头最少。解：首先列出各种可能的下料方案；计算出每个方案可得到的不同长度钢筋的数量及残余料头长度；确定决策变量；根据下料目标确定目标函数；根据不同长度钢筋的需要量确定约束方程。例2、合理下料问题设按第i种方案下料的原材料为xi根组合方案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例3、运输问题工厂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极大或极小;约束条件：可用线性等式或不等式表示.具备以上三个要素的问题就称为线性规划问题。目标函数约束条件(3)线性规划模型一般形式隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,cj为确定值2线性规划问题的图解法定义1：满足约束(2)的X=(X1…Xn)T称为线性规划问题的可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为线性规划问题的最优解。例1

MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t解：(1)、确定可行域

X1+2X230

3X1+2X2602X224X10X202030100102030X2DABC2X224X1+2X2303X1+2X260X10X20可行域(2)、求最优解最优解：X*=(15,7.5)Zmax=975Z=40X1+50X20=40X1+50X2(0,0)，(10,-8)C点：X1+2X2=30

3X1+2X2=600203010102030X1X2DABC最优解Z=975可行解Z=0等值线例2、MaxZ=40X1+80X2X1+2X2303X1+2X2602X224

X1,X20s.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)(01)MaxZ=1200

X1615

X2127.5X==+(1-)X1=6+(1-)·15X2=12+(1-)·7.5X1=15-9X2=7.5+4.5(01)例3、MaxZ=2X1+4X22X1+X28-2X1+X22X1,X20s.tZ=08246X240X1-2X1+X222X1+X28X10X20可行域无界无有限最优解无有限最优解可行域无上界例4、MaxZ=3X1+2X2-X1-X21X1,X20无可行域无可行解-1X2-1X10s.tX20X10-X1-X21直观结论线性规划问题的解有四种情况唯一最优解无穷多最优解无有限最优解无可行解若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；若线性规划问题有最优解，则唯一最优解对应于可行域的一个顶点；无穷多个最优解对应于可行域的一条边；3单纯形法3.1线性规划问题的标准形式3.2线性规划问题的基本解3.3单纯形法的基本思想3.1线性规划问题的标准形式目标函数约束条件(1)线性规划模型一般形式价值系数决策变量技术系数右端常数(2)线性规划模型标准形式价值向量决策向量系数矩阵右端向量(3)线性规划模型矩阵形式对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:(4)一般型向标准型的转化目标函数目标函数为极小化约束条件分两种情况：大于、小于决策变量可能存在小于零的情况3.2线性规划问题的基本解(1)解的基本概念定义在线性规划问题中，约束方程组(2)的系数矩阵A(假定)的任意一个阶的非奇异(可逆)的子方阵B(即)，称为线性规划问题的一个基阵或基。基阵非基阵基向量非基向量基变量非基变量令则定义在约束方程组(2)中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。定义在基本解中，若该基本解满足非负约束，即，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。基本解中最多有m个非零分量。基本解的数目不超过个。若B满足下列条件，称为最优基称为最优解例现有线性规划问题试求其基本解、基本可行解。解:(1)首先将原问题转化为标准型引入松弛变量x3和x4(2)求基本解由上式得可能的基阵由于所有|B|≠0，所以有6个基阵和6个基本解。对于基阵令则对于基阵令则为基本可行解，B13为可行基为基本可行解，B12为可行基对于基阵令则对于基阵令则对于基阵令则对于基阵令则为基本可行解，B24为可行基为基本可行解，B34为可行基0ABCDE所以，本问题存在6个基本解，其中4个为基可行解.(2)几点结论若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点);线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点);若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到;线性规划问题的基可行解(极点)的个数是有限的,不会超过个.上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得.3.3单纯形法(1)单纯形法的引入(2)表格单纯形法4线性规划的对偶理论4.1对偶问题4.2对偶问题的基本性质4.3影子价格4.4对偶单纯形法4.1对偶问题(1)对偶问题的提出例1、生产组织与计划问题A,B各生产多少,可获最大利润?可用资源煤劳动力仓库AB123202单位利润4050306024Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目标函数约束条件如果因为某种原因，不愿意自己生产，而希望通过将现有资源承接对外加工来获得收益，那么应如何确定各资源的使用价格？Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目标函数约束条件两个原则所得不得低于生产的获利要使对方能够接受设三种资源的使用单价分别为y1,y2,y3y1y2y3生产单位产品A的资源消耗所得不少于单位产品A的获利生产单位产品B的资源消耗所得不少于单位产品B的获利y1+3y240

2y1+2y2+2y350通过使用所有资源对外加工所获得的收益W=30y1+60y2+24y3根据原则2，对方能够接受的价格显然是越低越好，因此此问题可归结为以下数学模型：Min

W=30y1+60y2+24y3y1+3y2402y1+2y2+2y350y1,y2,y30s.t目标函数约束条件原线性规划问题称为原问题，此问题为对偶问题，y1,y2,y3称为影子价格(2)对偶问题的形式定义设原线性规划问题为则称下列线性规划问题为其对偶问题，其中yi(i=1,2,…,m)称为对偶变量。上述对偶问题称为对称型对偶问题。原问题简记为(P)，对偶问题简记为(D)对偶关系对应表原问题对偶问题目标函数类型MaxMin目标函数系数目标函数系数右边项系数与右边项的对应关系右边项系数目标函数系数变量数与约束数变量数n约束数n的对应关系约束数m变量数m原问题变量类型与

0

对偶问题约束类型变量

0约束

的对应关系无限制＝原问题约束类型与

0对偶问题变量类型约束

变量

0的对应关系＝无限制4.2对偶问题的基本性质定理1对偶问题的对偶就是原问题MaxW’=-Ybs.t.-YA≤-C Y≥0MinZ’=-CXs.t.-AX≥-b X≥0MaxZ=CXs.t.AX≤b X≥0MinW=Ybs.t.YA≥C Y≥0对偶的定义对偶的定义定理2(弱对偶定理)分别为(P),(D)的可行解，则有CbX，yXy证明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CXyAXyb推论2、(P)有可行解,但无有限最优解，则(D)无可行解。定理3、yX,分别为(P),(D)的可行解，且XyC=b,则它们是(P),(D)

的最优解。证明：对任X，有CXby=CXX最优推论1、(P),(D)都有可行解，则必都有最优解。定理4(主对偶定理)若一对对偶问题(P)和(D)都有可行解，则它们都有最优解，且目标函数的最优值必相等。证明：(1)当X*和Y*为原问题和对偶问题的一个可行解有原问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。(2)当X*为原问题的一个最优解，B为相应的最优基,通过引入松弛变量Xs,将问题(P)转化为标准型令令所以Y*是对偶问题的可行解，对偶问题的目标函数值为X*是原问题的最优解，原问题的目标函数值为推论：若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。一对对偶问题的关系，有且仅有下列三种：都有最优解，且目标函数最优值相等；两个都无可行解；一个问题无界，则另一问题无可行解。定理5

若X,Y分别为(P),(D)的可行解，则X,Y为最优解的充要条件是同时成立证:(必要性）原问题对偶问题y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于04.3影子价格对偶单纯形法的基本思想从原规划的一个基本解出发，此基本解不一定可行(正则解)，但它对应着一个对偶基可行解（检验数非正），所以也可以说是