线性规划及其对偶问题

线性规划及其对偶问题第1页，共153页，2023年，2月20日，星期日1线性规划问题及其数学模型(1)线性规划问题例、生产组织与计划问题A,B各生产多少,可获最大利润?可用资源煤劳动力仓库AB123202单位利润4050306024第2页，共153页，2023年，2月20日，星期日解:设产品A,B产量分别为变量x1，x2可以建立如下的数学模型：Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

0s.t目标函数约束条件可用资源煤劳动力仓库AB123202单位利润4050306024第3页，共153页，2023年，2月20日，星期日

例某建筑设计院设计每万ｍ２办公建筑和工业厂房需要的建筑师、结构工程师、设备工程师和电气工程师的平均人数列在表。问该院应如何安排设计任务，才能使设计费收入最大?专业建筑物建筑结构设备电器设计费收入（万元/万ｍ２

）办公建筑532136工业厂房121220全院现有专业人数28261210解设办公建筑和工业厂房各承揽ｘ１、ｘ２万ｍ２。根据题意maxZ＝36x1＋20x25x1＋x2≤28s.t3x1＋2x2≤282x1＋x2≤12x1＋2x2≤10x1、x2≥0第4页，共153页，2023年，2月20日，星期日2.9m钢筋架子100个，每个需用2.1m各1，原料长7.4m1.5m求：如何下料，使得残余料头最少。解：首先列出各种可能的下料方案；计算出每个方案可得到的不同长度钢筋的数量及残余料头长度；确定决策变量；根据下料目标确定目标函数；根据不同长度钢筋的需要量确定约束方程。例、合理下料问题第5页，共153页，2023年，2月20日，星期日设按第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第6页，共153页，2023年，2月20日，星期日例、运输问题工厂123库存仓121350222430库334210需求401535运输单价求：运输费用最小的运输方案。第7页，共153页，2023年，2月20日，星期日解：设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第8页，共153页，2023年，2月20日，星期日(2)线性规划问题的特点决策变量：(x1…

xn)T代表某一方案，

决策者要考虑和控制的因素非负；目标函数：Z=ƒ(x1

…

xn)为线性函数，求Z极大或极小;约束条件：可用线性等式或不等式表示.具备以上三个要素的问题就称为线性规划问题。第9页，共153页，2023年，2月20日，星期日目标函数约束条件(3)线性规划模型一般形式第10页，共153页，2023年，2月20日，星期日隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij,bi,cj为确定值第11页，共153页，2023年，2月20日，星期日2线性规划问题的图解法定义1：满足约束(2)的X=(X1…Xn)T称为线性规划问题的可行解，全部可行解的集合称为可行域。定义2：满足(1)的可行解称为线性规划问题的最优解。第12页，共153页，2023年，2月20日，星期日例1

MaxZ=40X1+50X2

X1+2X2303X1+2X2602X224

X1,X20s.t第13页，共153页，2023年，2月20日，星期日解：(1)、确定可行域

X1+2X230

3X1+2X2602X224X10X202030100102030X2DABC2X224X1+2X2303X1+2X260X10X20可行域第14页，共153页，2023年，2月20日，星期日(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等值线第15页，共153页，2023年，2月20日，星期日例2、MaxZ=40X1+80X2X1+2X2303X1+2X2602X224

X1,X20s.t第16页，共153页，2023年，2月20日，星期日解：(1)、确定可行域与上例完全相同。(2)、求最优解0203010102030DABC最优解Z=1200最优解：BC线段第17页，共153页，2023年，2月20日，星期日最优解：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)第18页，共153页，2023年，2月20日，星期日例3、MaxZ=2X1+4X22X1+X28-2X1+X22X1,X20s.tZ=08246X240X1-2X1+X222X1+X28X10X20可行域无界无有限最优解无有限最优解可行域无上界第19页，共153页，2023年，2月20日，星期日例4、MaxZ=3X1+2X2-X1-X21X1,X20无可行域无可行解-1X2-1X10s.tX20X10-X1-X21第20页，共153页，2023年，2月20日，星期日直观结论线性规划问题的解有四种情况唯一最优解无穷多最优解无有限最优解无可行解若线性规划问题有解，则可行域是一个凸多边形（或凸多面体）；若线性规划问题有最优解，则唯一最优解对应于可行域的一个顶点；无穷多个最优解对应于可行域的一条边；第21页，共153页，2023年，2月20日，星期日3单纯形法3.1线性规划问题的标准形式3.2线性规划问题的基本解3.3单纯形法的基本思想第22页，共153页，2023年，2月20日，星期日3.1线性规划问题的标准形式目标函数约束条件(1)线性规划模型一般形式第23页，共153页，2023年，2月20日，星期日价值系数决策变量技术系数右端常数(2)线性规划模型标准形式第24页，共153页，2023年，2月20日，星期日价值向量决策向量系数矩阵右端向量(3)线性规划模型矩阵形式第25页，共153页，2023年，2月20日，星期日对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:(4)一般型向标准型的转化目标函数目标函数为极小化约束条件分两种情况：大于、小于决策变量可能存在小于零的情况第26页，共153页，2023年，2月20日，星期日3.2线性规划问题的基本解(1)解的基本概念定义在线性规划问题中，约束方程组(2)的系数矩阵A(假定)的任意一个阶的非奇异(可逆)的子方阵B(即)，称为线性规划问题的一个基阵或基。第27页，共153页，2023年，2月20日，星期日基阵非基阵基向量非基向量基变量非基变量第28页，共153页，2023年，2月20日，星期日令则定义在约束方程组(2)中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。第29页，共153页，2023年，2月20日，星期日定义在基本解中，若该基本解满足非负约束，即，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。基本解中最多有m个非零分量。基本解的数目不超过个。第30页，共153页，2023年，2月20日，星期日若B满足下列条件，称为最优基称为最优解第31页，共153页，2023年，2月20日，星期日例现有线性规划问题试求其基本解、基本可行解。第32页，共153页，2023年，2月20日，星期日解:(1)首先将原问题转化为标准型引入松弛变量x3和x4(2)求基本解由上式得第33页，共153页，2023年，2月20日，星期日可能的基阵由于所有|B|≠0，所以有6个基阵和6个基本解。第34页，共153页，2023年，2月20日，星期日对于基阵令则对于基阵令则为基本可行解，B13为可行基为基本可行解，B12为可行基第35页，共153页，2023年，2月20日，星期日对于基阵令则对于基阵令则第36页，共153页，2023年，2月20日，星期日对于基阵令则对于基阵令则为基本可行解，B24为可行基为基本可行解，B34为可行基第37页，共153页，2023年，2月20日，星期日0ABCDE所以，本问题存在6个基本解，其中4个为基可行解.第38页，共153页，2023年，2月20日，星期日(2)几点结论若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点);线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点);若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到;线性规划问题的基可行解(极点)的个数是有限的,不会超过个.上述结论说明:线性规划的最优解可通过有限次运算在基可行解中获得.第39页，共153页，2023年，2月20日，星期日3.3单纯形法(1)单纯形法的引入(2)表格单纯形法第40页，共153页，2023年，2月20日，星期日

…n…j…m+1

…

k…

1-CBTb*amn…amj…amm+1

…0…am1bm*xmcm

…

…

…

…

…

…

…

…

…akn…akj…akm+1

…akk…ak1bk*xkck

…

…

…

…

…

…

…

…a1n…a1j…a1m+1…a1k…a11b1*x1c1xn…xj…xm+1xm…xk…x1b*XBCBcn…cj…cm+1cm…ck…c1cj→单纯形表ammmmaxZ＝c1x1十c2x2十……十cnxn

a11x1＋a12x2十……十a1nxn＝b1

a21x1＋a22x2十……十a2nxn＝b2……am1x1＋am2x2十……十amnxn＝bmxj≥0(j＝l、2、……，n)a1m第41页，共153页，2023年，2月20日，星期日x3x5x4000σ10

18000170/2100/3150/5maxZ＝10x1＋18x2（1）5x1＋2x2＋x3＝170s.t2x1＋3x2＋x4＝100（2）x1＋5x2＋x5＝150xj≥0（j＝1，2，3，4，5）主元第42页，共153页，2023年，2月20日，星期日x3x400x2100/2x3x5x4000σ10

18000170/2150/3100181/5001/53010σ1＝10－（0×23/5＋0×7/5－18×1/5）＝32/57/50111023/51－3/50－2/5σ32/5000－18/5550/2350/7150maxZ＝10x1＋18x2（1）5x1＋2x2＋x3＝170s.t2x1＋3x2＋x4＝100（2）x1＋5x2＋x5＝150xj≥0（j＝1，2，3，4，5）σ2＝18－－（0×0＋0×0－18×1）＝010＝100－（30×3）7/5＝2－（1/5×3）第43页，共153页，2023年，2月20日，星期日x3x400x2100/2x3x5x4000σ10

18000170/2150/3100181/5001/530107/50111023/51－3/50－2/5σ32/5000－18/5550/2350/7150x3x1x201018150/7005/7－3/7540/7001－23/711/7200/7010－1/72/7X*=(50/7,200/7,540/7,0,0)TZ*=4100/7σ000－32/7－6/7第44页，共153页，2023年，2月20日，星期日例某房地产公司欲开发一七通一平空地，总面积2500m2。公司原计划开发商业楼1000m2，住宅楼5250m2。请根据下列前提条件，确定其是否最佳开发方式。(1)根据规划要求：沿马路建商业房，为4层楼框架结构，其余为砖混住宅，为6层楼；容积率为2.5，建筑密度≤50%。(2)开发日期为2003年12月，建筑物完成时间不超过一年半。(3)根据预测，一年半以后商业楼平均造价为1400元/m2，砖混住宅平均造价为950元/m2，不计土地成本。(4)预计建筑物完成后商业楼及住宅均可全部售出，商业楼出售当时的平均售价为2400元/m2，住宅楼出售当时的平均售价为1700元/m2。(5)物业出售时的税费为总额的5%。(6)公司投入资金不超过650万元。第45页，共153页，2023年，2月20日，星期日分析：容积率＝总建筑面积/总占地面积建筑密度＝建筑基地总面积/总占地面积(1)总建筑面积2500×2.5=6250m2(2)建筑基地总面积2500×50%＝1250m2(3)商业楼每平方米的利润:(0.24－0.14一0.24×5%)=0.088(万元/m2)(4)住宅楼每平方米的利润:(0.17一0.095一0.17×5%)=0.0665(万元/m2)第46页，共153页，2023年，2月20日，星期日设商业楼建筑面积为x1m2;砖混住宅建筑面积为x2m2求x1、x2目标函数maxZ=0.088x1＋0.0665x2满足:x1＋x2≤6250x1/4+x2/6≤12500.14x1十0.095x2≤650x1、x2≥0(1)总建筑面积2500×2.5=6250m2(2)建筑基地总面积2500×50%＝1250m2(3)商业楼每平方米的利润:(0.24－0.14一0.24×5%)=0.088(万元/元m2)(4)住宅楼每平方米的利润:(0.17一0.095一0.17×5%)=0.0665(万元/m2)第47页，共153页，2023年，2月20日，星期日为了便于计算，变换一下约束条件及目标函数。（由于在整个价值最优程序中只是相对的价值是重要的，而不是它们绝对值。绝对值的值只影响目标函数的最后值，但不影响设计变量的最优值）因此，我们可以将其变换为:x1/4+x2/6≤1250转变为3x1十2x2≤150000.14x1十0.095x2≤650转变为1.4737x1十x2≤6842maxZ=0.088x1＋0.0665x2转变为maxZ‘=Z/0.0665＝1.323x1＋x2maxZ=0.088x1＋0.0665x2x1＋x2≤6250x1/4+x2/6≤12500.14x1十0.095x2≤650x1、x2≥0第48页，共153页，2023年，2月20日，星期日数学模型maxZ‘=1.323x1+x2x1＋x2≤62503x1十2x2≤150001.4737x1十x2≤6842x1、x2≥0x3x4x5000第49页，共153页，2023年，2月20日，星期日maxZ=1.323x1+x2x1＋x2≤62503x1十2x2≤150001.4737x1十x2≤6842x1、x2≥01.32310006250/115000/36842/1.4737x11.3230146430.6786000.678610710-0.035801-2.0358160700.321410-0.678600.102200-0.89784643/0.6786=68421607/0.3214=5000第50页，共153页，2023年，2月20日，星期日1.3230x1146430.6786000.678610710-0.035801-2.0358160700.321410-0.678600.102200-0.89784643/0.6786=68421607/0.3214=5000x211500003.111402.11140125000.11141-1.4602012501-2.11140-0.754200-0.318000-1.1136最优解:x1=1250,x2=5000,x4=1250,x3=x5＝0Z‘=6654即Z=0.0665×Z‘=442.5（万）第51页，共153页，2023年，2月20日，星期日例某项目经理部有三种住宅可以承建。三种住宅每百平方米的利润分别为6000元、8000元和5000元。承建时主要考虑木工和瓦工工时的安排。由于现在瓦工空闲，应尽量多安排；而可支配的木工工时虽然仅有26000个，但不允许有任何空闲。三种住宅每百平方米需用的瓦工和木工工时列在表中。另外，公司要求至少安排12000瓦工工时。问三种住宅各承建多少平方米．可使利润最大?

解设甲、乙、丙三种住宅各承建x1、、x2平方米，根据问题的要求，可得下列线性规划模型第52页，共153页，2023年，2月20日，星期日第53页，共153页，2023年，2月20日，星期日第54页，共153页，2023年，2月20日，星期日第55页，共153页，2023年，2月20日，星期日例某工程的混凝土量总计1500m3；分三种标号C20，C25，C30，其需要量为400m3、600m3、500m3。今供应32.5#水泥250t、42.5#水泥200t、，水泥单价及用量见表。试选择合理的配制方案，使水泥费用最省。第56页，共153页，2023年，2月20日，星期日设：由32.5#水泥配制的C20，C25，C30混凝土各为x1、x2、x3，由42.5#水泥配制的C20，C25，C30混凝土各为x4、x5、x6则32.5#水泥的总耗量为253x1＋302x2＋362x342.5#水泥的总耗量为211x4＋257x5＋302x6目标函数：minz＝2065（253x1＋302x2＋362x3）＋2192（211x4＋257x5＋302x6）253x1＋302x2＋362x3≤250211x4＋257x5＋302x6≤200x1＋x4≥400x2＋x5≥600x3＋x6≥500xi≥0解得：x1＝48x2＝600x3＝44x4＝252x5＝0x6＝486z＝28337.416（元）第57页，共153页，2023年，2月20日，星期日案例:建设监理公司监理工程师配置问题某建设监理公司(国家甲级)，侧重国家大中型项目的监理，仅在武汉市就正在监理七项工程，总投资均在5000万元以上。由于工程开工的时间不同，多工程工期之间相互搭接，具有较长的连续性，2002年监理的工程量与2003年监理的工程量大致相同。每项工程安排多少监理工程师进驻工地，一般是根据工程的投资，建筑规模，使用功能，施工的形象进度，施工阶段来决定的。监理工程师的配置数量是随之而变化的。由于监理工程师从事的专业不同，他们每人承担的工作量也是不等的。有的专业一个工地就需要三人以上，而有的专业一人则可以兼管三个以上的工地。第58页，共153页，2023年，2月20日，星期日因为从事监理业的专业多达几十个，仅以高层民用建筑为例就涉及到建筑学专业、工民建(结构)专业、给水排水专业、采暖通风专业、强电专业、弱电专业、自动控制专业、技术经济专业、总图专业、合同和信息管理人员等，这就需要我们合理配置这些人力资源。为了方便计算，我们把所涉及的专业技术人员按总平均人数来计算，工程的施工形象进度，按标准施工期和高峰施工期来划分。通常标准施工期需求的人数较容易确定。但高峰施工期比较难确定了。原因有两点:(1)高峰施工期各工地不是同时来到，是可以事先预测的，在同一个城市里相距不远的工地，就存在着各工地的监理工程师如何交错使用的运筹问题。第59页，共153页，2023年，2月20日，星期日(2)各工地总监在高峰施工期到来的时候要向公司要人，如果每个工地都按高峰施工期配置监理工程师的数量，将造成极大的人力资源浪费，这一点应该说主要是人为因素所造成的。因此，为了达到高峰施工期监理工程师配置数量最优，人员合理地交错使用，扼制人为因素，根据历年来的经验对高峰施工期的监理工程师数量在合理交错发挥作用的前提下限定了范围。另经统计测算得知，全年平均标准施工期占7个月，人年成本4万元;高峰施工期占5个月，人年成本7万元。第60页，共153页，2023年，2月20日，星期日另外在高峰施工期各工地所需监理工程师的数量要求第1和第2工地的总人数不少于14人;第2和第3工地的总人数不少于13人;第3和第4工地的总人数不少于11人;第4和第5工地的总人数不少于10人;第5和第6工地的总人数不少于9人;第6和第7工地的总人数不少于7人;第7和第1工地的总人数不少于14人。求2003年:1．高峰施工期公司最少配置多少个监理工程师?2．监理工程师年耗费的总成本是多少?第61页，共153页，2023年，2月20日，星期日已知条件汇总：为了达到高峰施工期监理工程师配置数量最优，人员合理地交错使用，扼制人为因素，根据历年来的经验对高峰施工期的监理工程师数量在合理交错发挥作用的前提下限定了范围。另经统计测算得知，全年平均标准施工期占7个月，人年成本4万元;高峰施工期占5个月，人年成本7万元。另外在高峰施工期各工地所需监理工程师的数量要求第1和第2工地的总人数不少于14人;第2和第3工地的总人数不少于13人;第3和第4工地的总人数不少于11人;第4和第5工地的总人数不少于10人;第5和第6工地的总人数不少于9人;第6和第7工地的总人数不少于7人;第7和第1工地的总人数不少于14人。求2003年:1．高峰施工期公司最少配置多少个监理工程师?2．监理工程师年耗费的总成本是多少?第62页，共153页，2023年，2月20日，星期日设xi为第i工地最少配置监理工程师人数约束条件:第1和第2工地的总人数不少于14人;第2和第3工地的总人数不少于13人;第3和第4工地的总人数不少于11人;第4和第5工地的总人数不少于10人;第5和第6工地的总人数不少于9人;第6和第7工地的总人数不少于7人;第7和第1工地的总人数不少于14人。x1≥5x2≥4x3≥4x4≥3x5≥3x6≥2x7≥2

x1、x2、x3、x4、x5、x6、x7≥0x1＋x2≥14x2＋x3≥13x3＋x4≥11x4＋x5≥10x5＋x6≥9x6＋x7≥7x7＋x1≥7Minz=x1+x2+x3+x4+x5+x6+x7第63页，共153页，2023年，2月20日，星期日2．监理工程师年耗费的总成本(4×7/12+7×5/12）×min（x1+x2+x3+x4+x5+x6+x7）第64页，共153页，2023年，2月20日，星期日4线性规划的对偶理论4.1对偶问题4.2对偶问题的基本性质4.3影子价格4.4对偶单纯形法第65页，共153页，2023年，2月20日，星期日4.1对偶问题(1)对偶问题的提出例1、生产组织与计划问题A,B各生产多少,可获最大利润?可用资源煤劳动力仓库AB123202单位利润4050306024第66页，共153页，2023年，2月20日，星期日Max

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

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

Z=

40x1+50x2x1+2x2

303x1+2x2

602x2

24x1，x2

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

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

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

0

对偶问题约束类型变量

0约束

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

0对偶问题变量类型约束

变量

0的对应关系＝无限制第71页，共153页，2023年，2月20日，星期日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对偶的定义对偶的定义第72页，共153页，2023年，2月20日，星期日定理2(弱对偶定理)分别为(P),(D)的可行解，则有CbX，yXy证明：由AXb,y0有yAXby由AyC,X0有yAXCX所以CXyAXyb第73页，共153页，2023年，2月20日，星期日推论2、(P)有可行解,但无有限最优解，则(D)无可行解。定理3、yX,分别为(P),(D)的可行解，且XyC=b,则它们是(P),(D)的最优解。证明：对任X，有CXby=CXX最优推论1、(P),(D)都有可行解，则必都有最优解。第74页，共153页，2023年，2月20日，星期日定理4(主对偶定理)若一对对偶问题(P)和(D)都有可行解，则它们都有最优解，且目标函数的最优值必相等。证明：(1)当X*和Y*为原问题和对偶问题的一个可行解有原问题目标函数值对偶问题目标函数值所以原问题的目标函数值有上界，即可找到有限最优解；对偶问题有下界，也存在有限最优解。第75页，共153页，2023年，2月20日，星期日(2)当X*为原问题的一个最优解，B为相应的最优基,通过引入松弛变量Xs,将问题(P)转化为标准型令令所以Y*是对偶问题的可行解，对偶问题的目标函数值为X*是原问题的最优解，原问题的目标函数值为第76页，共153页，2023年，2月20日，星期日推论：若一对对偶问题中的任意一个有最优解，则另一个也有最优解，且目标函数最优值相等。一对对偶问题的关系，有且仅有下列三种：都有最优解，且目标函数最优值相等；两个都无可行解；一个问题无界，则另一问题无可行解。第77页，共153页，2023年，2月20日，星期日从两图对比可明显看到原问题无界，

其对偶问题无可行解y1y2第78页，共153页，2023年，2月20日，星期日例4已知线性规划问题maxz=x1+x2-x1+x2+x3≤2-2x1+x2-x3≤1x1,x2,x3≥0试用对偶理论证明上述线性规划问题无最优解。第79页，共153页，2023年，2月20日，星期日上述问题的对偶问题为minw=2y1+y2-y1-2y2≥1y1+y2≥1y1-y2≥0y1，y2≥0由第1约束条件，可知对偶问题无可行解；原问题虽然有可行解，但无最优解。第80页，共153页，2023年，2月20日，星期日例5已知线性规划问题minw=2x1+3x2+5x3+2x4+3x5x1+x2+2x3+x4+3x5≥42x1-x2+3x3+x4+x5≥3xj≥0，j=1，2，…，5已知其对偶问题的最优解为y1*=4/5，y2*=3/5；z=5。试用对偶理论找出原问题的最优解。第81页，共153页，2023年，2月20日，星期日例5已知线性规划问题解：先写出它的对偶问题maxz=4y1+3y2y1+2y2≤2①y1-y2≤3②2y1+3y2≤5③y1+y2≤2④3y1+y2≤3⑤y1，y2≥0第82页，共153页，2023年，2月20日，星期日例5已知线性规划问题将y1*=4/5,y2*=3/5的值代入约束条件，得②=1/5<3，③=17/5<5，④=7/5<2它们为严格不等式；由互补松弛性得x2*=x3*=x4*=0。因y1，y2≥0；原问题的两个约束条件应取等式，故有x1*+3x5*=4，2x1*+x5*=3求解后得到x1*=1,x5*=1；故原问题的最优解为X*=(1，0，0，0，1)T；w*=5第83页，共153页，2023年，2月20日，星期日定理5若X,Y分别为(P),(D)的可行解，则X,Y为最优解的充要条件是同时成立证:(必要性）原问题对偶问题第84页，共153页，2023年，2月20日，星期日y1yiymym+1ym+jyn+m

x1xjxnxn+1xn+ixn+m

对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjym+j=0 yixn+i=0 (i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0第85页，共153页，2023年，2月20日，星期日影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于04.3影子价格变量yi*的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函的最优值的变化。第86页，共153页，2023年，2月20日，星期日第1章中例1的影价格及其经济解释。由表1-5可知cj23000θCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80-z-1400-3/2-1/80y1*=1.5，y2*=0.125，y3*=0。第87页，共153页，2023年，2月20日，星期日第1章中例1的影价格及其经济解释。

这说明是其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利1.5元；原材料A增加1kg，可多获利0.125元；原材料B增加1kg，对获利无影响。从图2-1可看到，设备增加一台时，代表该约束条件的直线由①移至①′，相应的最优解由(4，2)变为(4，2.5)，目标函数z=2×4+3×2.5=15.5，即比原来的增大1.5。又若原材料A增加1kg时，代表该约束方程的直线由②移至②′，相应的最优解从(4，2)变为(4.25，1.875)，目标函数z=２×4.25+3×1.875=14.125。比原来的增加0.125。原材料B增加1kg时，该约束方程的直线由③移至③′，这时的最优解不变。第88页，共153页，2023年，2月20日，星期日第1章中例1的影价格及其经济解释。

第89页，共153页，2023年，2月20日，星期日yi*的值代表对第i种资源的估价——影子价格。

这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。在该厂现有资源和现有生产方案的条件下，设备的每小时租费为1.5元，1kg原材料A的出让费为除成本外再附加0.125元，1kg原材料B可按原成本出让，这时该厂的收入与自己组织生产时获利相等。影子价格随具体情况而异，在完全市场经济的条件下，当某种资源的市场价低于影子价格时，企业应买进该资源用于扩大生产；而当某种资源的市场价高于企业影子价格时，则企业的决策者应把已有资源卖掉。可见影子价格对市场有调节作用。第90页，共153页，2023年，2月20日，星期日2.影子价格在经济管理中的应用影子价格在经济管理中的应用很多（1）影子价格能指示企业内部挖潜的方向1）影子价格越高的资源，表明它对目标增益影响越大，同时也表明这种资源对该企业来说越稀缺和越贵重，企业的管理者就应该重视对这种资源的管理，通过挖潜革新、降低消耗或及时补充该种资源，以保证给企业带来较大的收益。即对影子价格大于零的资源都应采取措施，增加投入，以保证生产正常进行，实现利润最大化。2）对影子价格为零的资源，企业的管理者也不应忽视，这种资源对该企业来说是相对富裕的。一方面，可以向别的企业转让这种资源或者以市场价出售，以免形成积压浪费；另一方面，通过企业内部的改造、挖潜和增加对影子价格大于零的资源的投入后，使原有的剩余资源又可以得到充分利用，而变为新的紧缺资源（变为影子价格大于零）。这样不断调整、补充，真正实现资源的合理利用。第91页，共153页，2023年，2月20日，星期日（2）影子价格在企业经营决策中的作用因为影子价格不是市场价格，它是根据企业本身的资源情况bi、消耗系数aij和产品的利润cj计算出来的一种价格，是新增资源所创造的价值，是边际价格。不同的企业，即使是相同的资源（例如钢材），其影子价格也不一定相同。就是同一企业，在不同的生产周期，资源的影子价格也不完全一样。因此，企业的决策者可以把本企业资源的影子价格与当时的市场价格进行比较。1）当i种资源的影子价格高于市场价格时，则企业可以买进该种资源；2）当某种资源的影子价格低于市场价格时（特别是当影子价格为零时），则企业可以卖出该种资源，以获得较大的利润。3）随着资源的买进和卖出，它的影子价格也将发生变化，直到影子价格与市场价格保持同等水平时，才处于平衡状态。所以我们说影子价格又是一种机会成本，它在决定企业的经常策略中起着十分重要的作用。第92页，共153页，2023年，2月20日，星期日

式中：cj表示单位j种产品的价值（或利润）m∑aijyii=1表示生产第j种产品所消耗的各项资源的影子价格的总和，它可以称为第j种产品的隐含成本，检验数бj称作是第j种产品的相对价值系数。

mбj=cj—

CBB-1Pj=cj—∑aijyi(j=1,2,…,n).i=1由于（3）影子价格在新产品开发决策中的应用企业在新产品投产之前，可以用影子价格，通过分析产品使用资源的经济效果，以决定新产品是否应该投产。б<0，产品所能提供的单件利润小于其隐含成本，产品不值得投产；б>0，产品B所能提供的单件利润大于其隐含成本，产品值得投产第93页，共153页，2023年，2月20日，星期日例MaxZ=10x1+18x2;5x1+2x2≤170;2x1+3x2≤100;s.t.x1+5x2≤150;x1、x2≥0.计算产品A和B的相对价值系数：mбA=CA—∑aijyii=1=10—(1×0+2×32/7＋3×6/7)=—12/7<0;解说明产品A所能提供的单件利润小于其隐含成本，相对价值系数бA<0，故产品A不值得投产。第94页，共153页，2023年，2月20日，星期日mбB=CB—∑aijyi=18－(2×0+1×32/7+4×6/7)=10>0.i=1说明产品B所能提供的单件利润大于其隐含成本，相对价值系数бB>0，故产品B值得投产。第95页，共153页，2023年，2月20日，星期日

（4）利用影子价格分析现有产品价格变动对资源紧缺情况的影响前例中，当产品的利润不是（10，18），而是（15，18），则从最优单纯形表可以重新算影子价格为

Y*=CBB-1=（0，15，18）

=（0，57/7，—9/7）由于y3*=-9/7<0，说明现有的解不是最优解，还须继续迭代求新的最优解。而y2*=57/7比原来增大了，说明第二种资源更紧缺了。1-23/711/7

05/7-3/70-1/72/7

maxZ=10x1+18x2;5x1+2x2+x3=170;2x1-3x2+x4=100;s.t.x1+5x2+x5=150;x1,x2≥0;第96页，共153页，2023年，2月20日，星期日（5）利用影子价格分析工艺改变后对资源的影响前例中，使煤炭节约2%，则带来的收益为y2*b2·2%=32/7×100×2%=64/7（万元）

值得指出的是，以上的分析都是在最优基不变的条件下进行的如果最优基有变化，则应结合下一章将要讨论的灵敏度分析方法来进行分析。

maxZ=10x1+18x2;5x1+2x2+x3=170;2x1-3x2+x4=100;s.t.x1+5x2+x5=150;x1,x2≥0;第97页，共153页，2023年，2月20日，星期日

例已知某工厂计划生产Ⅰ、Ⅱ、Ⅲ三种产品，各产品需要在A,B,C设备上加工，有关数据见表．

试回答:(1)如何充分发挥设备能力，使生产盈利最大?(2)若为了增加产量，可借用别的工厂的设备B，每月可借用60台时，借金1.8万元，问借用B设备是否合算?(3)若另有两种新产品Ⅳ、V，其中Ⅳ需用设备A一l2台时，B一5台时，C一l0台时，单位产品盈利2.1千元;新产品V需用设备A一4台时，B一4台时，C一l2台时，单位产品盈利1.87千元，如A,B,C设备台时不增加，分别回答这两种新产品投产在经济上是否合算?(4）对产品工艺重新迸行设计，改进结构，改进后生产每件产品I，需用设备A一9台时，设备B一12台时，设备C一4台时，单位产品盈利4.5千元，问这对原计划有何影响?Ⅰ

Ⅱ

Ⅲ

设备有效台时（每月）ABC8102251310810300400420单位产品利润（千元）322.9第98页，共153页，2023年，2月20日，星期日解设产品Ⅰ、Ⅱ、Ⅲ的产量分别为x1，x2，x3，其数学模型为maxZ=3x1十2x2十2.9x38x1十2x2十10x3≤30010x1十5x2十8x3≤400，s·t2x1十13x2十10x3≤300，x1、x2、x3≥0在上述线性规划问题的约束条件中加入松变量x4，x5，x6。得maxZ=3x1十2x2十2.9x38x1十2x2十10x3＋x4＝30010x1十5x2十8x3＋x5＝400，s·t2x1十13x2十10x3＋x6＝300，x1、x2、x3、x4，x5，x6≥0列出初始单纯形表，并求解第99页，共153页，2023年，2月20日，星期日第100页，共153页，2023年，2月20日，星期日故原线性规划问题的最优解X*=（338/15，116/5,22/3,0,0，0)，目标函数最优值(1)由单纯形表知:设备B的影子价格为：4/15(千元/台时)18（千元）/60（台时）=0.3＞4/15，故借用B设备并不合算借用别的工厂的设备B，每月可借用60台时，借金1.8万元则借用设备的租金为:第101页，共153页，2023年，2月20日，星期日(2)设Ⅳ及V生产的产量分别为x7，x8，则其各自在最终单纯形表对应的列向量故生产产品Ⅳ在经济上不合算第102页，共153页，2023年，2月20日，星期日所以生产产品V在经济上合算·由单纯性表知:第103页，共153页，2023年，2月20日，星期日故线性规划最优解X*=（107/4,31/2,0,0,0,0，55/4)T目标函数最优值Z*=136.9625第104页，共153页，2023年，2月20日，星期日对偶单纯形法的基本思想从原规划的一个基本解出发，此基本解不一定可行(正则解)，但它对应着一个对偶基可行解（检验数非正），所以也可以说是从一个对偶基可行解出发；然后检验原规划的正则解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个正则解，此正则解对应着另一个对偶基可行解（检验数非正）。如果得到的正则解的分量皆非负则该正则解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的正则解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。4.4对偶单纯形法第105页，共153页，2023年，2月20日，星期日前节讲到原问题与对偶问题的解之间的对应关系时指出：在单纯形表中进行迭代时，在b列中得到的是原问题的基可行解，而在检验数行得到的是对偶问题的基解。通过逐步迭代，当在检验数行得到对偶问题的解也是基可行解时，根据性质(2)、(3)可知，已得到最优解。即原问题与对偶问题都是最优解。根据对偶问题的对称性，可以这样考虑：若保持对偶问题的解是基可行解，即cj−CBB-1Pj≤0，而原问题在非可行解的基础上，通过逐步迭代达到基可行解，这样也得到了最优解。其优点是原问题的初始解不一定是基可行解，可从非基可行解开始迭代。第106页，共153页，2023年，2月20日，星期日4.4

对偶单纯形法设原问题为

maxz=CX

AX=b

X≥0又设B是一个基。不失一般性，令B=(P1，P2，…，Pm)，它对应的变量为XB=(x1，x2，…,xm)。当非基变量都为零时，可以得到XB=B-1b。若在B-1b中至少有一个负分量，设(B-1b)i＜0，并且在单纯形表的检验数行中的检验数都为非正，即对偶问题保持可行解，它的各分量是(1)对应基变量x1，x2，…,xm的检验数是σi=ci−zi=ci

−

CBB-1Pj=0，i=1,2,…,m(2)对应非基变量xm+1，…，xn的检验数是σj=cj−

zj=cj−CBB-1Pj≤0，j=m+1,…,n第107页，共153页，2023年，2月20日，星期日4.4

对偶单纯形法每次迭代是将基变量中的负分量xl取出，去替换非基变量中的xk，经基变换，所有检验数仍保持非正。从原问题来看，经过每次迭代，原问题由非可行解往可行解靠近。当原问题得到可行解时，便得到了最优解。第108页，共153页，2023年，2月20日，星期日4.4

对偶单纯形法对偶单纯形法的计算步骤如下：(1)根据线性规划问题，列出初始单纯形表。检查b列的数字，若都为非负，检验数都为非正，则已得到最优解。停止计算。若检查b列的数字时，至少还有一个负分量，检验数保持非正，那么进行以下计算。(2)确定换出变量。按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l对应的基变量xi为换出变量(3)确定换入变量。在单纯形表中检查xl所在行的各系数αlj(j=1,2,…，n)。若所有αlj≥0，则无可行解，停止计算。若存在αlj＜0(j=1,2,…，n),计算第109页，共153页，2023年，2月20日，星期日4.4

对偶单纯形法对偶单纯形法的计算步骤如下：按θ规则所对应的列的非基变量xk为换入变量，这样才能保持得到的对偶问题解仍为可行解。(4)以αlk为主元素，按原单纯形法在表中进行迭代运算，得到新的计算表。重复步骤(1)～(4)。第110页，共153页，2023年，2月20日，星期日4.4

对偶单纯形法例6用对偶单纯形法求解minw=2x1+3x2+4x3x1+2x2+x3≥32x1−x2+3x3≥4x1，x2，x3≥0解：先将此问题化成下列形式，以便得到对偶问题的初始可行基maxz=−2x1−

3x2−

4x3−x1−

2x2−

x3+x4=−3−2x1+x2−

3x3+x5=−4xj≥0，j=1,2,…,5第111页，共153页，2023年，2月20日，星期日4.4

对偶单纯形法例6的初始单纯形表，见表2-6。从表2-6看到，检验数行对应的对偶问题的解是可行解。因b列数字为负，故需进行迭代运算。

第112页，共153页，2023年，2月20日，星期日4.4

对偶单纯形法换出变量的确定：换入变量的确定：按上述对偶单纯形法计算步骤(3)，即在单纯形表中检查xl所在行的各系数αlj(j=1,2,…，n)。若所有αlj≥0，则无可行解，停止计算。按上述对偶单纯形法计算步骤(2)，即按min｛(B-1b)i｜(B-1b)i＜0＝(B-1b)l对应的基变量xi为换出变量。计算min(−3,−4)=−4故x5为换出变量。故x1为换入变量。换入、换出变量的所在列、行的交叉处“−2”为主元素。按单纯形法计算步骤进行迭代，得表2-7。第113页，共153页，2023年，2月20日，星期日4.4

对偶单纯形法第114页，共153页，2023年，2月20日，星期日4.4

对偶单纯形法表2-8中，b列数字全为非负，检验数全为非正，故问题的最优解为X*=(11/5，2/5，0，0，0)T若对应两个约束条件的对偶变量分别为y1和y2，则对偶问题的最优解为Y*=(y1*,y2*)=(8/5,1/5)第115页，共153页，2023年，2月20日，星期日4.4

对偶单纯形法从以上求解过程可以看到对偶单纯形法有以下优点：(1)初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。(2)当变量多于约束条件，对这样的线性规划问题用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。(3)在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法，这样可使问题的处理简化。对偶单纯形法的局限性主要是，对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。第116页，共153页，2023年，2月20日，星期日5EXCEL求解线性规划第117页，共153页，2023年，2月20日，星期日6线性规划灵敏度分析6.1目标函数系数的灵敏度分析6.2右端项的灵敏度分析第118页，共153页，2023年，2月20日，星期日6线性规划灵敏度分析以前讨论线性规划问题时，假定αij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；αij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：(1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；(2)或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。后一个问题将在第8节参数线性规划中讨论。第119页，共153页，2023年，2月20日，星期日6线性规划灵敏度分析显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别