第1-4章线性规划及对偶理论2

1、第第1页页夫夫 运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 于于 千千 里里 之之 外外运运 筹筹 学学 课课 件件线线 性性 规规 划划Linear ProgrammingLinear Programming第第2页页本章内容本章内容o线性规划问题的数学建模线性规划问题的数学建模o图解法图解法o单纯形法原理单纯形法原理o单纯形法的计算步骤单纯形法的计算步骤oWinQSB软件求解软件求解第第3页页教学说明教学说明o教学目标教学目标：掌握：掌握LP的建模方法，熟练地使用的建模方法，熟练地使用单纯形法求解模型，借助单纯形法求解模型，借助WinQSB软件求解软件求解问题问题o重点与难点重点与难点：

2、重点是：重点是LP的建模与解法；难点的建模与解法；难点是单纯形法的原理是单纯形法的原理o教学方法教学方法：配合课件和：配合课件和WinQSB软件，课堂件，课堂讲授为主，案例研讨为辅讲授为主，案例研讨为辅o思考题、讨论题、作业思考题、讨论题、作业：教材第：教材第1-3章习题章习题 o学时分配学时分配：8学时学时 第第4页页线性规划的产生与发展线性规划的产生与发展o1939年苏联的经济学家康托洛维奇在年苏联的经济学家康托洛维奇在生生产组织与计划中的数学方法产组织与计划中的数学方法一书中，首次一书中，首次用线性规划方法解决了生产组织与运输问题。用线性规划方法解决了生产组织与运输问题。o1947年美国

3、数学家年美国数学家G.B.Dantzig提出了提出了线性规划的数学模型，并给出了求解该模型线性规划的数学模型，并给出了求解该模型的单纯形法（的单纯形法（Simplex method)。这标。这标志着线性规划这一运筹学的重要分支的诞生。志着线性规划这一运筹学的重要分支的诞生。o计算机的发展促进了计算机的发展促进了LP计算理论的发展，计算理论的发展，使其应用更加广泛和深入。使其应用更加广泛和深入。第第5页页线性规划的应用范围线性规划的应用范围o生产中的组织与计划问题生产中的组织与计划问题o运输问题运输问题o合理下料问题合理下料问题o配料问题配料问题o生产布局问题生产布局问题特点：在现有条件下，统筹

4、安排，使总的经特点：在现有条件下，统筹安排，使总的经济效益最好，或者是总成本最省。济效益最好，或者是总成本最省。某工厂制造某工厂制造A、B两种产品，它们的原材料单位消耗、两种产品，它们的原材料单位消耗、单位利润以及资源现有量如下表：单位利润以及资源现有量如下表：问如何组织生产，使工厂获得最大利润？问如何组织生产，使工厂获得最大利润？例1：生产组织与计划问题生产组织与计划问题AB资源现有量资源现有量（吨）（吨）钢材钢材23600煤煤21400单位利润单位利润（万元）（万元）205产品产品资源资源资源资源 消耗消耗11 线性规划的数学建模第第7页页建立数学模型步骤1.假设决策变量：设假设决策变量：

5、设A、B两种产品各生产两种产品各生产个单位；个单位；21,xx2.建立目标函数：利润函数是建立目标函数：利润函数是 ，求它的最大值，即求它的最大值，即21520 xxS21520maxxxS3.现有资源的限制条件：现有资源的限制条件：4002600322121xxxx4.决策变量必须有非负限制：决策变量必须有非负限制：0, 021xx第第8页页数学模型12121212max20523600. .24000,0Sxxxxstxxxx目标函数系统约束非负限制 注意：目标函数和约束条件中变量的次数都是一注意：目标函数和约束条件中变量的次数都是一次的，这样的模型称为线性规划数学模型。次的，这样的模型称

6、为线性规划数学模型。第第9页页生产计划安排问题的一般描述nmmnmmmnnnbbbacccAacccAacccABBB21212222212111211121资源资源产品产品消耗消耗资源现有量资源现有量单位产品利润单位产品利润求解使工厂获得最大利润的生产方案。求解使工厂获得最大利润的生产方案。第第10页页生产计划安排问题的一般数学模型解：设解：设 表示生产产品表示生产产品的单位数，则有如下的数学模型：的单位数，则有如下的数学模型：(1,2, )jxjn(1,2, )jBjn11max 1,2,s.t.0 1,2,njjjnijjijjSb xc xaimxjn第第11页页设有某种物资从设有某种

7、物资从A、B、C三个产地调出，运往甲、三个产地调出，运往甲、乙、丙三个需求地，其调运量及运价如下表。求运乙、丙三个需求地，其调运量及运价如下表。求运费最省的调运方案。费最省的调运方案。 甲甲 乙乙 丙丙 调出量调出量 A 2 4 5 7 B 1 3 4 4 C 3 2 3 9 调入量调入量 6 8 6 （20）调出调出调入调入运价运价例2：运输问题第第12页页设设 表示从表示从i 地调往地调往j 地的调运量地的调运量ijx111213212223313233111213212223313233112131122232132333min245343237496860 1,2,3; 1,2,3ij

8、Sxxxxxxxxxxxxxxxxxxxxxxxxxxxxij第第13页页产销平衡运输问题的一般描述产量产量销量销量产地产地销地销地运价运价nBBB21mAAA21mnmmnnccccccccc212222111211nbbb21maaa21njjmiiba11求解使运输总成本最低的方案。求解使运输总成本最低的方案。第第14页页设设 表示从表示从i 地调往地调往j 地的调运量地的调运量njmixnjbxmiaxxcSijmijijnjiijijminjij, 2 , 1, 2 , 10, 2 , 1, 2 , 1min1111ijx产销平衡运输问题的一般模型例例3：合理配载问题：合理配载问题o

9、某货船的前舱、中舱、后舱的载重分别为某货船的前舱、中舱、后舱的载重分别为2 000吨、吨、3 000吨、吨、1 000吨，容积分别为吨，容积分别为100 000立方米、立方米、135 000立方米、立方米、30 000立方米；立方米；顾客托运的货物顾客托运的货物A、B、C的重量、体积、运费等的重量、体积、运费等资料已知。为了保持货船的稳定，要求三个货舱资料已知。为了保持货船的稳定，要求三个货舱载货率必须平衡。问如何装载，使收入最大？载货率必须平衡。问如何装载，使收入最大？111213212223313233+)+800(+x )+500(+ijxijZxxxxxxxxxxxxxxxxxxxxx

10、x1121311222321323331121311222解：设 为第 种货物装入 仓的吨数max =600()载重约束：+2000 +3000 +1000容积约束：60+50+25100 000 60+50+111213212223313233+x+2000300010000 =1,2,3i jxxxxxxxxxxxxxxxxxxxxxxi3213233311213112223213233325135 000 60+50+2530 000货物约束：6000 4000 2000+货船稳定约束：非负约束：; =1,2,3j例例4：连续投资问题：连续投资问题o某地区今后三年内可以有某地区今后三年内

11、可以有A、B、C、D四个项目的四个项目的投资选择，总资金量为投资选择，总资金量为3000万元。其中项目万元。其中项目A在在三年内每年年初投资，当年年底可回收本利和为三年内每年年初投资，当年年底可回收本利和为120；项目；项目B第一年年初投资，第二年年底可回第一年年初投资，第二年年底可回收本利和为收本利和为150，但投资额不超过，但投资额不超过2000万元；万元；项目项目C第二年年初投资，第三年年底可回收本利和第二年年初投资，第三年年底可回收本利和为为160，但投资额不超过，但投资额不超过1500万元；项目万元；项目D第第三年年初投资，当年年底可收回本利和为三年年初投资，当年年底可收回本利和为1

12、40，投资额不超过投资额不超过1000万元。问如何安排投资，使第万元。问如何安排投资，使第三年年底本利和的金额最大？三年年底本利和的金额最大？13324311211232111343122121max 1.21.61.43000 1.2 1.21.52000 i jxjiZxxxxxxxxxxxxxx解：设为第 年初对 项目的投资额年初投资约束：项目投资约束：32431500 10000 =1,2,3,4; =1,2,3i jxxij非负约束：第第19页页思考题1：配料问题 某化工厂要用三种原料混合配置三种不同规格的产品，各产品的规格、单价见下表：产品规格单价（元/公斤）A原料不少于50%原料

13、不超过25%50B原料不少于25%原料不超过50%35C不限25第第20页页问如何安排生产使得生产利润最大？原料日最大供应量单价(元/公斤)10065100256035原料的单价与每天最大供应量见下表：原料的单价与每天最大供应量见下表：3 , 2 , 1, 3 , 2 , 1, 060100100003030. .10401030152515max) 3 , 2 , 1,(33231332221231211123222123222113121113121133312221131211jixxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxZjixjiijij种原料的数量为种产品的第设

14、用于生产第第第22页页思考题2：人力资源分配问题 某个中型百货商场对售货人员（周工资400元）的需求经统计如下表 为了保证销售人员充分休息，销售人员每周连续工作5天，休息2天。问应如何安排销售人员的工作时间，使得人力总成本最小？星期一二三四五六日人数12151214161819第第24页页思考题3：合理下料问题o要制作要制作100套钢筋架子，每套有长套钢筋架子，每套有长2.9m、2.1m和和1.5m的钢筋各一根。已知原材料的钢筋各一根。已知原材料长长7.4m，应如何切割，使用原材料最节省，应如何切割，使用原材料最节省，试建立线性规划模型并求解。试建立线性规划模型并求解。课堂练习：课堂练习：o三

15、种产品要分别经过三种产品要分别经过A,B两道工序。两道工序。 产品产品可在可在A,B的任何设备上加工；产品的任何设备上加工；产品可在可在A的任何设的任何设备上加工后，只能在备上加工后，只能在B1设备上加工；产品设备上加工；产品只能只能在在A2和和B2设备上加工。设备上加工。 试安排最优生产计划，使该厂获利最大。试安排最优生产计划，使该厂获利最大。第第26页页12 线性规划问题解的性质 两个变量的线性规划问题的图解法两个变量的线性规划问题的图解法几个基本概念：几个基本概念： 满足所有约束条件的解称为满足所有约束条件的解称为LP问题的可行解；所问题的可行解；所有可行解的集合称为可行解集。有可行解的

16、集合称为可行解集。 使目标函数达到最优的可行解称为使目标函数达到最优的可行解称为LP问题的最优问题的最优解。解。 问题：线性规划是一个带有约束条件的极值问问题：线性规划是一个带有约束条件的极值问题，能否用微积分方法求解题，能否用微积分方法求解?第第27页页例例1 1：用图解法求解下面的：用图解法求解下面的LPLP问题问题0, 08234.52max21212121xxxxxxtsxxS目标函数等值线1x2x此点为LP的最优解o41x4332x8221 xx65221 xx155221 xxD可行域max Smin S第第28页页得到这个最优解：得到这个最优解：2112232283LPmax19

17、xxxxxS的目标函数最优值为 本问题有唯一最优解。本问题有唯一最优解。第第29页页例例2 2 ：用图解法解下面的线性规划：用图解法解下面的线性规划0, 08234.2max21212121xxxxxxtsxxS AB目标函数等值线1x2xO8221 xx431224xxD可行域max Smin S第第30页页得到得到LP的最优解及目标函数最优值：的最优解及目标函数最优值：1212212112282:33284:42LPmax8xxxAxxxxxBxxS的最优值均为 除除A、B两个最优解外，两个最优解外，AB线段上的所有点都是线段上的所有点都是LP的最优解。本问题有无穷多最优解。的最优解。本问

18、题有无穷多最优解。第第31页页例例3 3：用图解法解下面的线性规划：用图解法解下面的线性规划0, 0331.2min21212121xxxxxxtsxxS1x2xo无界的可行解集1S3S 此题有可行解，此题有可行解，但无最优解但无最优解112SD可行域max Smin S第第32页页例例4 4：用图解法解下面的线性规划：用图解法解下面的线性规划0, 011.3max21212121xxxxxxtsxxS无可行解1x2xo 本题无可行解，更本题无可行解，更无最优解无最优解第第33页页o有唯一最优解，这个最优解一定在可行解集有唯一最优解，这个最优解一定在可行解集合的某一顶点上达到合的某一顶点上达到

19、o有无穷多最优解，最优解充满一个线段，可有无穷多最优解，最优解充满一个线段，可以用它的两个端点作为代表以用它的两个端点作为代表o有可行解，但无最优解（无界解）有可行解，但无最优解（无界解）o无可行解无可行解 小结：小结：LP图解法有如下四种情况图解法有如下四种情况第第34页页线性规划问题解的关系线性规划问题解的关系线性规划线性规划问题的解问题的解无可行解无可行解 有可行解有可行解唯一最优解唯一最优解无最优解无最优解有最优解有最优解无穷多最优解无穷多最优解第第35页页 线性规划问题的标准形式1 12211 11221121 1222221 12212LP:min(max)( , )( , )s.

20、t.( , )0,0,0nnnnnnmmmnnmnSc xc xc xa xa xa xba xa xa xba xaxaxbxxx 问题的一般形式为第第36页页将一般的将一般的LPLP转化为转化为LPLP标准形：标准形：1 12211 11221121 1222221 12212max.0,0,0nnnnnnmmmnnmnSc xc xc xa xa xa xba xa xa xbsta xaxaxbxxx第第37页页规定: 求目标函数的最大值为标准形，即目标函数为求目标函数的最大值为标准形，即目标函数为maxS 。如果问题是求。如果问题是求 minS 时，可令时，可令求求 ，相当于求，相当

21、于求minS 。SSmaxS第第38页页规定:1 12211 122110kkknnknkkknnnkna xa xa xbxa xa xaxxbx若，则增加一个变量，使其变为等式，称为松弛变量，它在目标函数中的系数为零。 以等式约束为标准形。设第以等式约束为标准形。设第k 个等式为个等式为 1 12211 122110rrrnnrnrrrnnnrna xa xa xbxa xa xa xxbx若，则可减去一个松弛变量，使其变为等式，即，同样，在目标函数中的系数也是零。第第39页页(3) LP中所有的变量都有非负限制。如果实际问题中的LP里某个变量无非负限制，可如下处理:(4) 若约束条件为等

22、式，但右端项为负值，则在等式两边同时乘以-1即可 0,0,jjijiijjjixxxxxxxxxx若 无非负限制，则引入令代入约束条件中，这时所有的变量都有了若 为非正限制，则引入0，令 =-,代入约束条件中，这时所有的变量都有了非非负限制。负限制。规定:第第40页页将下列线性规划模型化为标准形将下列线性规划模型化为标准形12312312312312min 35262316s.t.510,0Sxxxxxxxxxxxxx x123412345123461234max 352623316s.t.55100 =1,2,6iSxxxxxxxxxxxxxxxxxxxi 第第41页页根据以上的规定，根据以

23、上的规定，LPLP的标准形为：的标准形为：1 12211 11221121 1222221 12212max.0,0,0nnnnnnmmmnnmnSc xc xc xa xa xa xba xa xa xbsta xaxaxbxxx第第42页页两种缩写形式：两种缩写形式：max,1,2,.0,1,2,njjjnijjijjSc xa xb imstxjn第第43页页矩阵表示法：矩阵表示法：mnmmnnaaaaaaaaaA212222111211ncccC21设mbbbb21nxxxx21LPmaxs.t.0SCxAxbx则问题可表为3. LP3. LP问题解的性质问题解的性质 几个概念几个概念

24、 凸集：若连接凸集：若连接n维点集维点集S 中任意两点中任意两点 的线段的线段仍在仍在S 内，则称内，则称S 为凸集。即为凸集。即)2()1(,xx., 10 ,)1 (|)2()1 ()2()1 (SSxxxxxx凸集凸集不是凸集极点 极点：若凸集极点：若凸集S 中的点中的点x，不能成为，不能成为S 中任何线段中任何线段的内点，则称的内点，则称x为为S 的极点。的极点。 设设 为为LP的一个可行解，若的一个可行解，若或或 的非零分量对应的的非零分量对应的A中列向量线性无关，则称中列向量线性无关，则称它为它为基础可行解基础可行解。由这些列向量组成的矩阵称为。由这些列向量组成的矩阵称为基矩基矩阵

25、阵，与这些列向量对应的变量称为，与这些列向量对应的变量称为基变量基变量，其余的变，其余的变量称为量称为非基变量非基变量。)0()0(2)0(1)0(nxxxx0)0(x)0(x使目标函数值达到最优值的可行解称为使目标函数值达到最优值的可行解称为最优解最优解；使目标函数达到最优值的使目标函数达到最优值的基础可行解基础可行解称为称为基础最基础最优解优解。可行解集基础可行解最优解基础最优解线性规划解的关系线性规划解的关系第第47页页目标函数目标函数约束条件约束条件行列式行列式0基矩阵基矩阵右边常数右边常数=10987654321xxxxxxxxxx247xxx 为基变量其余变量为非基变量第第48页页

26、 几个重要定理（单纯形法的理论依据）几个重要定理（单纯形法的理论依据）定理定理1 线性规划问题的可行解集为凸集线性规划问题的可行解集为凸集，即连，即连接线性规划问题任意两个可行解的线段上的点接线性规划问题任意两个可行解的线段上的点仍为可行解。仍为可行解。定理定理2 可行解集可行解集S 中的点中的点x是极点的充要条件是极点的充要条件是是x为基础可行解（简单地说，凸多边形的顶为基础可行解（简单地说，凸多边形的顶点就是基础可行解）。点就是基础可行解）。定理定理3 线性规划的目标函数的最优值，一定线性规划的目标函数的最优值，一定可在极点上达到。可在极点上达到。第第49页页1 13 3 单纯形方法单纯形

27、方法(Simplex method)(Simplex method)x1x2O单纯形法的解题思路：单纯形法的解题思路： 用消去法解用消去法解LPLP问题问题12121212max2543s.t.280,0Sxxxxxxxx解：引入松弛变量解：引入松弛变量将其化为标准形式将其化为标准形式12132412512345max254328,0Sxxxxxxxxxxxxxx345,x xx 123453134542512121 0 1 0 0 0 1 0 1 0 1 2 0 0 1 341 0 00 1 0 30 0 182 0 0Ap p p p pR AxxBp p pxxxxxxx第一步：求一个可

28、行解系数矩阵 显然（非齐次方程有解条件）， 其中令 001200 4 25038xSxx 第第52页页012 25Sxx第二步：判优目标函数中非目标系数存在正基变量的系数可数 目标函数值未达到最优以用来检验线性规划是否已得由此得出，到最优解2312242225122 34301 38208822 minxxxxxxxxxxxxxx2第三步：换基迭代 的目标系数的值较大应引入 ，将其转换为基变量，称其为 原来的基变量中必有一个要换出，变为非基变量，称为3 4取值满足两个不等式的 的换入变值，换个写法：变量量换出 43124514141112141443 8,3 , 1 24 382 322030

29、 4 2525 325002 xxxxxxxxxxxxSxxxxxxxS 由此确定换出变量为将基变量用非基变量表示为（ ）令得此时，（）=15+115 141311124115145354224154 25 4404 3202224 2 =min,2, 1 12223 320220 SxxxxxxxxxxxxxxxxxxxxxxxxS 第四步：判优15+， 入基出基45212192192max193 xxSxSx判优：目标函数中非基变量的系数均小于零最优解为，第第55页页2. 2. 单纯形方法理论推导单纯形方法理论推导max0SCxAxbx设设A是是 的矩阵，且的矩阵，且R(A)=m （m04

30、010换换出出行行将将3化为化为15/311801/301/31011/3303005/304/3乘乘以以3/5后后得得到到103/51/518011/52/540011Z=0Z=40Z=701218,max70.4xSx最优解为第第70页页单纯形法的计算步骤单纯形法的计算步骤学习要点：学习要点：1. 线性规划解的概念以及线性规划解的概念以及3个基本定理个基本定理2. 熟练掌握单纯形法的解题思路及求解步骤熟练掌握单纯形法的解题思路及求解步骤第第71页页问题:表1中我们选取了 入基,如果选取 入基结果又如何呢?2x1x路径1路径2结论：结论：1.每一个单纯每一个单纯形表对应一个极点，形表对应一个

31、极点，表一对应黄点；表二表一对应黄点；表二对应绿点；表三对应对应绿点；表三对应蓝点。蓝点。 2.一般来说，一般来说，路径不同，迭代次数路径不同，迭代次数可能不同。可能不同。第第72页页(1)如果单纯形表中的基变量取值皆为正数，称这个如果单纯形表中的基变量取值皆为正数，称这个基可行解为基可行解为非退化解非退化解。若。若LP的所有基可行解都是非退的所有基可行解都是非退化的，则化的，则LP经过有限次迭代可达到最优经过有限次迭代可达到最优.(2)如果单纯形表中的基变量取值有的为零时，称为如果单纯形表中的基变量取值有的为零时，称为LP的的退化解退化解，此时称，此时称LP是退化的，理论上认为这种是退化的，

32、理论上认为这种线性规划在迭代过程中可能产生循环，从而得不到最线性规划在迭代过程中可能产生循环，从而得不到最优解。为避免循环，常采用优解。为避免循环，常采用1976年年R.G.Bland提出提出Bland法则：法则：a.单纯形表中有若干个检验数单纯形表中有若干个检验数 时，时，取下标号小的非基变量入基；取下标号小的非基变量入基； b. 用用 法则选取出基法则选取出基变量时，若比值相同，则选取下标号小的基变量出基。变量时，若比值相同，则选取下标号小的基变量出基。0j说明：说明：第第73页页(3) 当所有的检验数全部小于等于零时，若有某当所有的检验数全部小于等于零时，若有某个非基变量的检验数也是零，

33、则该线性规划有个非基变量的检验数也是零，则该线性规划有无无穷多组解穷多组解，否则有唯一解。将这个检验数为零的，否则有唯一解。将这个检验数为零的变量入基，得到另一个基础最优解。（变量入基，得到另一个基础最优解。（P31）(4) 当某非基变量的检验数大于零时，但当某非基变量的检验数大于零时，但 中中对应列系数已无正数，则表示无论引入该非基变对应列系数已无正数，则表示无论引入该非基变量多少，基变量不会向违反非负约束的方向发展，量多少，基变量不会向违反非负约束的方向发展，从而使目标函数可以无限制地增加，因此存在从而使目标函数可以无限制地增加，因此存在无无界解界解（P32）说明：说明：AB1第第74页页

34、例例2：解线性规划：解线性规划0,303310220222min52154152153154321xxxxxxxxxxxxxxxxxS解：注意到解：注意到 对应对应A中的列向量恰好构成三阶中的列向量恰好构成三阶单位方阵，可以作为第一个可行基。单位方阵，可以作为第一个可行基。423,xxx单纯形表单纯形表C 2 -1 1 -2 1 1 -1 -220 1030 2 0 1 0 1 1 1 0 0 2 3 0 0 1 3S=-50 7 0 0 0 8 1 2-2 010 0 0 -2 1 0 -3 1 1 0 0 2 0 -3 0 1 -3S=20 0 -7 0 0 -6324xxx54321xx

35、xxxBxBc314xxx1B b1x入基20 10 30min,213 102x 出基最优解为最优解为 最优值最优值S=-2012345100000 xxxxx第第76页页3. 3. 第一个可行解的求法（大第一个可行解的求法（大M M法）法）以上各例的系数矩阵以上各例的系数矩阵A 中，都存在一个中，都存在一个m 阶单位阶单位阵，因此很容易用单纯行法求解。但是大多数阵，因此很容易用单纯行法求解。但是大多数LP问题并不是这样。问题并不是这样。例例 3 ：12312312313123min3211423210Sxxxxxxxxxxxxxx ， ，解：化为标准形解：化为标准形123456712341

36、23561371234567max30021142321,0SxxxxxMxMxxxxxxxxxxxxxxxxxxxx45676767,(0)0LPx xx xAAx xM MxxM这里的是松弛变量，而是人工变量，它的作用是为了产生 中一个单位列向量，从而使 中出现一个三阶单位阵。需要注意的是：人工变量在目标函数中的系数不是零，而是在它们的前边冠以一个负的，对于求最大化问题，只有当时，才存在最大值，这种处理方法是对增加人工变量的一种惩罚，称是罚因子。第第78页页填写单纯形表：填写单纯形表：C3 -1 -1 0 0 -M -M0-M-M11 3 1 1 -2 1 1 0 0 0-4 1 2 0

37、-1 1 0-2 0 1 0 0 0 1S=-4M3-6M M-1 3M-1 0 -M 0 0467xxx1234567 xxxxxxxBxBc出基入基73, 111,23,111min,xx1B b第第79页页C3 -1 -1 0 0 -M -M0-M-110 1 1 3 -2 0 1 0 0 -10 1 0 0 -1 1 -2-2 0 1 0 0 0 1S=-M-11 M-1 0 0 -M 0 -3M+1463xxx1234567 xxxxxxxBxBc26,xx显然， 入基出基1B b第第80页页C3 -1 -1 0 0 -M -M 0-1-112 1 1 3 0 0 1 -2 2 -5

38、0 1 0 0 -1 1 -2-2 0 1 0 0 0 1S=-21 0 0 0 -1 -M+1 -M-1423xxx1234567 xxxxxxxBxBc14xx显然， 入基， 出基1B bC3 -1 -1 0 0 -M -M 3-1-1 4 1 9 1 0 0 1/3 -2/3 2/3 -5/30 1 0 0 -1 1 -20 0 1 2/3 -4/3 4/3 -7/3S= 20 0 0 -1/3 -1/3 -M+1/3 -M+2/3123xxx1234567 xxxxxxxBxBc1B b12341, min2.9xxSx 最优解最优值终止表终止表第第82页页说明：关于大说明：关于大M法

39、的几种情况法的几种情况（1） 上表称为终止表。在终止表中，如果基变上表称为终止表。在终止表中，如果基变量里不含有人工变量，或者量里不含有人工变量，或者基变量里含有人工变基变量里含有人工变量，但是人工变量取值为零，量，但是人工变量取值为零，则则LP一定有最优解；一定有最优解；（2） 在终止表中，如果基变量里含有人工变量，在终止表中，如果基变量里含有人工变量，且人工变量取值大于零，则且人工变量取值大于零，则LP无最优解（无最优解（P37）第第83页页1-4 WinQSB1-4 WinQSB软件应用软件应用第第84页页第第2章章 线性规划的对偶理论线性规划的对偶理论o对偶问题的提出对偶问题的提出o原

40、问题与对偶问题原问题与对偶问题o对偶问题的基本性质对偶问题的基本性质o影子价格影子价格o对偶单纯形法对偶单纯形法o灵敏度分析灵敏度分析第第85页页线性规划的对偶理论线性规划的对偶理论o教学目的与要求：了解对偶问题产生的经济背景，教学目的与要求：了解对偶问题产生的经济背景，熟练掌握对偶单纯形法和影子价格概念，熟练掌握熟练掌握对偶单纯形法和影子价格概念，熟练掌握灵敏度分析方法。灵敏度分析方法。o重点与难点：重点同上，难点是对偶理论。重点与难点：重点同上，难点是对偶理论。o教学方法：课堂讲授为主并配合课件和教学方法：课堂讲授为主并配合课件和WinQSB软软件。件。o思考题、讨论题、作业：教材第思考题

41、、讨论题、作业：教材第4章习题章习题 o参考资料：见绪论参考资料：见绪论o学时分配：学时分配：8学时学时 第第86页页2 21 1 对偶线性规划问题对偶线性规划问题 对偶问题的提出对偶问题的提出 内容一致，而从相反的角度提出的一对问题，称内容一致，而从相反的角度提出的一对问题，称为一对对偶问题。为一对对偶问题。第第87页页例例1：某工厂在计划期内安排生产甲、乙两种产品，：某工厂在计划期内安排生产甲、乙两种产品，这些产品分别需要在这些产品分别需要在A、B、C、D四种不同的设备上四种不同的设备上加工。产品在各台设备上需要加工的台时数如下表：加工。产品在各台设备上需要加工的台时数如下表：A B C

42、D甲甲 2 1 4 0乙乙 2 2 0 4产品产品设备设备已知已知A、B、C、D设备的有效台时数分别是设备的有效台时数分别是12、8、16、12。售出一单位甲产品获利。售出一单位甲产品获利2万元，一单位乙万元，一单位乙产品获利产品获利3万元。如何安排生产使工厂获利最大？万元。如何安排生产使工厂获利最大？122212121214,LP max23221228 4164120 x xZxxxxxxxxxx解：设分别为计划期内生产甲、乙产品的数量模型为从相反的角度提出问题：工厂决策者决定不生产甲、从相反的角度提出问题：工厂决策者决定不生产甲、乙两种产品，而对设备的有效台时数进行出租，用租乙两种产品，

43、而对设备的有效台时数进行出租，用租金的方法获得最大利润。应如何考虑？金的方法获得最大利润。应如何考虑？决策者要考虑给每一种设备出租一个台时的定价。决策者要考虑给每一种设备出租一个台时的定价。在何种价格下，决策者接受出租设备呢？在何种价格下，决策者接受出租设备呢？1234, ,y yyyA B C D设分别表示出租四种设备一个首先台时的价格。12341234,2402,22043.yyyyyyyy用生产单位甲产品的台时数出租，收取的租金应不低于生产单位甲产品所获得的利润，即同理其次1234,1281612Wyyyy四种设备的有效台时数全部出租后 获得的总租金是建立建立LP数学模型数学模型1234

44、1234123412341281612240222043,min ,0Wyyyyyyyyyyyyyyyy1212121212max 232212284164120Zxxxxxxxxxx，显然，当显然，当maxZ=minW时，时，对于决策者来说这两种方对于决策者来说这两种方案都是最优的。案都是最优的。第第91页页2.2.对偶线性规划的模型对偶线性规划的模型max 0ZCXAXbXmin 0WYbYACY第第92页页对偶线性规划的特点：对偶线性规划的特点：o一个规划中的每一个约束，对应对偶规划中的一个规划中的每一个约束，对应对偶规划中的一个决策变量；一个决策变量；o一个规划中目标函数系数恰为对偶规

45、划约束条一个规划中目标函数系数恰为对偶规划约束条件右端常数项；件右端常数项；o一个规划求最小化，而对偶规划求最大化；一个规划求最小化，而对偶规划求最大化； o目标函数求最小化搭配目标函数求最小化搭配 约束；目标函数约束；目标函数求最大化搭配求最大化搭配 约束；约束；o两个规划都有非负限制。两个规划都有非负限制。“ ”“ ”第第93页页例例1 1：写出下面原规划的对偶规划：写出下面原规划的对偶规划123123123123LP:max 222 423,0gyyyyyyyyyyyy1212121212LP:min 2324121 21,0Sxxxxxxxxxx第第94页页定理定理1 如果线性规划中第

46、如果线性规划中第k个约束条件是等式，则个约束条件是等式，则它的对偶规划中的第它的对偶规划中的第k个变量无非负限制，反个变量无非负限制，反之亦然。之亦然。第第95页页例例2 2：写出下面原规划的对偶规划：写出下面原规划的对偶规划12121212min 4553 25,0Sxxxxxxxx12121212 max 354 5250,gyyyyyyyy解：无非负限制第第96页页例例3 3：写出下面原规划的对偶规划：写出下面原规划的对偶规划12121212min 5625530,Sxxxxxxxx无限制12121212 max 535 2560gyyyyyyyy解：无限制，原规划与对偶规划的对应关系原

47、规划与对偶规划的对应关系1maxnjjjZc x1minmiiiWb y(1,2, )00jjjjxjnnxxx有 个变量自由（无约束）变量变量约束约束条件条件目标目标函数函数LP原问题原问题LP对偶问题对偶问题约束约束条件条件变量变量目标目标函数函数(1,2,)00iiiimy imyyy有 个变量自由（无约束）(1,2,)ijjiijjiijjima xb ima xba xb有 个约束(1,2, )ijiiijiiijiinjna yca yca yc有 个约束第第98页页练习：写出下列练习：写出下列LP问题的对偶问题模型问题的对偶问题模型1231231223123min842202 8

48、0 + 30,0,Zxxxxxxxxxxxxx自由变量1231212313123LPmax208032 8 4 + 20,0Wyyyyyyyyyyyyy 模型：自由变量,第第99页页3.3.对偶线性规划的性质对偶线性规划的性质LP max (1)0SCXAXbX：LP min (2)0gYbYACY：定理定理2(弱对偶定理弱对偶定理) 对偶规划对偶规划(1)，(2)有最优解的有最优解的充分必要条件是它们同时有可行解。充分必要条件是它们同时有可行解。 定理定理3(最优性定理最优性定理) 如果如果 分别是分别是(1)，(2)的的可行解，且可行解，且 则则 分别是分别是(1)，(2)的最的最优解。优

49、解。00,YXbYCX0000,YX第第100页页定理定理4 如果对偶规划如果对偶规划(1)，(2)中，有一个存在最优中，有一个存在最优解，那么另一个也一定有最优解。并且两个规划的解，那么另一个也一定有最优解。并且两个规划的目标函数的最优值相等。目标函数的最优值相等。注意：重点研究两个规划的最优解之间的关系注意：重点研究两个规划的最优解之间的关系122121212 LP max25156224 5,0Sxxxxxxxxx给定：12323123123 LP min1524562 521,0gyyyyyyyyyyy则对偶规划为：分别化为标准形分别化为标准形1234523124125max20005

50、156224501,2,5jSxxxxxxxxxxxxxxj123452341235max15245006252101,2,5igyyyyyyyyyyyyyi 2327217max21xxS12317min201412gyyy原问题的最优单纯形表原问题的最优单纯形表C2 1 0 0 002115/2 7/2 3/2 0 0 1 5/4 -15/2 1 0 0 1/4 -1/2 0 1 0 -1/4 3/2S=17/2 0 0 0 -1/4 -1/2312xxx12345 xxxxxBxBc*b对偶问题的最优单纯形表对偶问题的最优单纯形表b-15 -24 -5 0 0-24-5 1/4 1/2

51、-5/4 1 0 -1/4 1/4 15/2 0 1 1/2 -3/2g=-17/2-15/2 0 0 -7/2 -3/223yy12345 yyyyyByBb*C第第104页页重要结论：重要结论：给出一对对偶线性规划，只需解其中一给出一对对偶线性规划，只需解其中一个线性规划得出最优解和目标函数最优值。它的对个线性规划得出最优解和目标函数最优值。它的对偶规划的目标函数最优值与原规划的目标函数值相偶规划的目标函数最优值与原规划的目标函数值相同，而最优解可用原规划最优表中的松弛变量的检同，而最优解可用原规划最优表中的松弛变量的检验数乘以验数乘以“-1”得到。得到。第第105页页o例：线性规划问题例

52、：线性规划问题 其对偶问题的最优解为其对偶问题的最优解为 求原问题的求原问题的最优解。最优解。提示：运用对偶模型最优解之间的关系，分析松弛变提示：运用对偶模型最优解之间的关系，分析松弛变量取值，决定对应变量的值。量取值，决定对应变量的值。123413412341234max2562 822212,0Zxxxxxxxxxxxx x x x12*=4=1 yy，4.4.影子价格影子价格( Shadow price)( Shadow price)0,max11122121111112211nmnmnmnnnnnnxxbxaxabxaxabxaxaxcxcxcS根据最优性定理，根据最优性定理， 是原规

53、划约束条是原规划约束条件右端项，它代表件右端项，它代表第第i种资源的拥有量，种资源的拥有量，对偶变量对偶变量 表示对表示对一个单位第一个单位第i种资源种资源的估价。它不是该的估价。它不是该资源的市场价格，资源的市场价格，而是根据该资源在而是根据该资源在生产中做出的贡献生产中做出的贡献而作的估价，称为而作的估价，称为影子价格。影子价格。miiinjjjgybxcS11ibiy11221111112122111min,0mmmmmmnmnmnmgb yb yb ya ya yca yayca yaycyy 第第107页页关于影子价格的几个重要结论关于影子价格的几个重要结论: :（1）影子价格的求法

54、：对偶问题的最优解，即为原）影子价格的求法：对偶问题的最优解，即为原问题约束条件右端常数项的影子价格。问题约束条件右端常数项的影子价格。 具体做法：将原规划最优表中的松弛变量的检验具体做法：将原规划最优表中的松弛变量的检验数乘以数乘以-1，就得到了对应于原规划约束条件右端，就得到了对应于原规划约束条件右端常数项（即资源限制量）的影子价格。常数项（即资源限制量）的影子价格。第第108页页（2） 影子价格是一种边际价格（影子价格是一种边际价格（Boundary price）miiinjjjgybxcS11在上式中，对在上式中，对 求偏导数，得求偏导数，得ib., 2 , 1,miybSii这说明，

55、这说明， 的值相当于在给定的生产条件下，的值相当于在给定的生产条件下， 每增加一个单位时，目标函数每增加一个单位时，目标函数S 的增加量，即总的增加量，即总收入的变化率（总收入增加一个影子价格值）。收入的变化率（总收入增加一个影子价格值）。ibiy第第109页页（3） 影子价格是一种机会成本（影子价格是一种机会成本（Opportunity cost） 在纯市场经济条件下，当某种资源的市场价格在纯市场经济条件下，当某种资源的市场价格低于影子价格时，可以买进这种资源扩大生产；低于影子价格时，可以买进这种资源扩大生产；相反当市场价格高于影子价格，可卖出这种资源相反当市场价格高于影子价格，可卖出这种资

56、源获取更大的利润。获取更大的利润。注意：由于影子价格可为决策者提供决策依据，注意：由于影子价格可为决策者提供决策依据，因此各种资源的影子价格应当保密。因此各种资源的影子价格应当保密。第第110页页（4）影子价格大于零时，对应的松弛变量为非基）影子价格大于零时，对应的松弛变量为非基变量，其取值为零，则该约束条件为等式，这说变量，其取值为零，则该约束条件为等式，这说明此种资源已被充分利用。明此种资源已被充分利用。影子价格等于零时，对应的松弛变量为基变量，一影子价格等于零时，对应的松弛变量为基变量，一般地说，其取值大于零，则该约束条件不等式是成般地说，其取值大于零，则该约束条件不等式是成立的（立的（

57、“”关系）。这说明此资源是过剩资源，没关系）。这说明此资源是过剩资源，没有被充分利用。有被充分利用。影子价格等于零，不是说该资源没有价格，而是表影子价格等于零，不是说该资源没有价格，而是表明该资源是过剩资源，再买进此资源不会增加总收明该资源是过剩资源，再买进此资源不会增加总收入。入。第第111页页检验数的含义：检验数的含义：111jjBjBjjBjjjcC BpC BpxC Bpxc检验数，是影子价格，列向量为生产一个单位产品消耗每种资源的数量，因此就是按影子价格计算、生产一个单位产品所消耗的费用，称为隐含成本。是该产品的产值，于是检验数就是该产品产值与生产一个单位产品消耗的成本与之差。显然，

58、当产品的产值大于隐含成本时，安排生产此产品有利，否则应安排其他产品的生产。第第112页页4. 4. 对偶单纯形法对偶单纯形法定义定义1：将线性规划模型转化为标准形式后，对某：将线性规划模型转化为标准形式后，对某一确定的基矩阵一确定的基矩阵B，令非基变量等于零，根据系，令非基变量等于零，根据系统约束条件解出基变量，则这组解称为基矩阵统约束条件解出基变量，则这组解称为基矩阵B的的基解基解。满足非负约束条件的基解，称为。满足非负约束条件的基解，称为基可行基可行解解。 第第113页页12121212max2543s.t.280,0Sxxxxxxxx12132412512345max254328,0Sx

59、xxxxxxxxxxxxx试找出下列线性规划模型的基解，并判断是否可行？是否最优？第第114页页定义定义2：设：设 是线性规划是线性规划的一组基变量，其对应的基矩阵是的一组基变量，其对应的基矩阵是B，对应的基解，对应的基解为为 ，如果这组基对应的检验数全部小于等于零，如果这组基对应的检验数全部小于等于零，即即 ，则称这组基为该线性，则称这组基为该线性规划的一组规划的一组正则基正则基。 为为正则解正则解。 12,mx xxmax0SCXAXbX0X10BCC B A0X线性规划的对偶单纯形法是从第一个正则解开始线性规划的对偶单纯形法是从第一个正则解开始迭代的。迭代的。第第115页页对偶单纯形法的

60、迭代步骤对偶单纯形法的迭代步骤: :（1）从一个正则解开始，列出对偶单纯形表；）从一个正则解开始，列出对偶单纯形表；（2）如基变量的取值全部大于等于零，则线性规划）如基变量的取值全部大于等于零，则线性规划已取得最优解，计算结束；否则转（已取得最优解，计算结束；否则转（3）；）；（3）在基变量中，挑选取负值中最小的一个，作为）在基变量中，挑选取负值中最小的一个，作为出基变量（若最小负值相同，可由出基变量（若最小负值相同，可由Bland法则确法则确定）；定）；（4）在出基变量行中，如果非基变量的约束系数全）在出基变量行中，如果非基变量的约束系数全部非负，则原问题不存在可行解；否则转（部非负，则原问