管理定量分析》第三部分最优化课件.ppt

1、管理定量分析管理定量分析周立业周立业第三章第三章 最优化方法最优化方法v第一节第一节 线性规划概述线性规划概述v第二节第二节 线性规划问题的解法线性规划问题的解法v第第三三节节 线性规划问题的对偶问题线性规划问题的对偶问题 v第第四四节节 整数规划（运输、分配问题整数规划（运输、分配问题）v第五节第五节 动态规划动态规划 案例：河流污水处理费用优化案例：河流污水处理费用优化vA城市城市 排排2万立方米万立方米/天污水，到城市天污水，到城市B前前20%自然净化自然净化v问题：要求污水含量不大于问题：要求污水含量不大于0.2%，如何处理污，如何处理污水费用最少？水费用最少？支流支流200万立方米万

2、立方米/天天 主河流主河流500万立方米万立方米/天天vB城市城市 排排1.4万立方米万立方米/天污水天污水v处理成本：处理成本：A市市1000元元/万立方米；万立方米；B市市800元元/万立方米万立方米一、一、线性规划问题的提出线性规划问题的提出利用有限利用有限资源资源 某工厂在计划期内要安排生产某工厂在计划期内要安排生产、两两种产品，已知生产单位产品所需的设备台种产品，已知生产单位产品所需的设备台数及数及A、B两种原材料的消耗量，见表两种原材料的消耗量，见表1-1。该工厂每生产一件产品该工厂每生产一件产品可获利润可获利润2元，每元，每生产一件产品生产一件产品可获利润可获利润3元，问应如何安

3、元，问应如何安排生产计划使该工厂获得的利润最大？排生产计划使该工厂获得的利润最大？第一节第一节 线性规划概述线性规划概述产品资源资源限量设备(台时)128原材料A(g)4016000原材料B(g)0412000 如何制定生产计划，使两种产品总利润最大？如何制定生产计划，使两种产品总利润最大？利用有限资源：某鸡厂共饲养利用有限资源：某鸡厂共饲养1万只鸡，用大豆和万只鸡，用大豆和谷物混合喂养，已知鸡消耗饲料谷物混合喂养，已知鸡消耗饲料1kg/天，鸡至少天，鸡至少需要蛋白质、钙分别为需要蛋白质、钙分别为0.22、0.06 kg/天，每公斤天，每公斤大豆含蛋白质、钙为大豆含蛋白质、钙为50、0.2，每

4、公斤谷物含，每公斤谷物含蛋白质、钙为蛋白质、钙为10、0.1，大豆和谷物售价，大豆和谷物售价0.4、0.2元元/kg。0,1241648232max21212121xxxxxxxxZ 饲料饲料成分成分大豆大豆谷物谷物营养营养蛋白质蛋白质.kg50100.22钙钙.kg0.20.10.06售价售价.元元0.40.2设：每只鸡需要大豆设：每只鸡需要大豆x x1 1公斤，谷物公斤，谷物x x2 2公斤，公斤，0,106.0001.0002.022.01.05.02.04.0min2121212121xxxxxxxxxxZ设：养鸡场每天需要大豆设：养鸡场每天需要大豆x x1 1公斤，谷物公斤，谷物x

5、x2 2公斤公斤0,100001000006.0001.0002.01000022.01.05.02.04.0min2121212121xxxxxxxxxxZ二、线性规划的定义和数学描述（模型）1定义：对于求取一组变量xj(j=1,2,.,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划（LP）。2.配比问题和生产计划问题的线性规划模型配比问题和生产计划问题的线性规划模型的特点：的特点：用一组未知变量表示要求的方案，这组用一组未知变量表示要求的方案，这组未知变量称为决策变量；未知变量称为决策变量；存在一定的限制条件，且为

6、线性表达式；存在一定的限制条件，且为线性表达式；有一个目标要求（最大化，当然也可以有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线是最小化），目标表示为未知变量的线性表达式，称之为目标函数；性表达式，称之为目标函数；对决策变量有非负要求。对决策变量有非负要求。3LP的数学描述(数学模型)：（1）一般形式 njxbxaxaxabxaxaxabxaxaxaxcxcxcZjmnmnmmnnnnnn,2,1,0),(),(),(max(min)221122222121112121112211（2）紧缩形式）紧缩形式njxmibxatsxcZjnjijijnjjj,2,10,2,1)

7、,(.max(min)11（3）矩阵形式）矩阵形式其中其中 :0),(.max(min)XbAXtsCXZ),(21ncccCTnxxxX),(21Tmbbbb),(21mnmmmnnaaaaaaaaaaaaA32122322211131211（4）向量）向量矩阵形式：矩阵形式：0)(.)(1XbxPtsCXZMinMaxnjjj或其中：其中：),(,2,1),(2121nTmjjjjPPPAnjaaaP三、LP的标准型：1、LP标准型的概念 （1）什麽是LP的标准型？（2）LP标准型的特点 目标函数约定是极大化Max（或Min）;约束条件均用等式表示;决策变量限于取非负值;右端常数b均为非负

8、值;（3）数学表达式:有几种形式?为什麽?如何书写?2、LP问题的标准化（1）目标函数的标准化 CXZCXZZZmaxmin y 3 y=f(x)1 0 2 5 x -1 y=-f(x)-3 目标函数标准化示意图目标函数标准化示意图（2）约束条件的标准化&约束条件是类型 左边 加 非负松弛变量&约束条件是类型 左边 减 非负剩余变量&变量符号不限 引入新变量 21kkkxxx四、在管理中一些典型的线性规划应用四、在管理中一些典型的线性规划应用v1 1、合理利用线材问题：如何在保证生产的条件下，、合理利用线材问题：如何在保证生产的条件下，下料最少下料最少v2 2、配料问题：在原料供应量的限制下如

9、何获取最大、配料问题：在原料供应量的限制下如何获取最大利润利润v3 3、投资问题：从投资项目中选取方案，使投资回报、投资问题：从投资项目中选取方案，使投资回报最大最大v4 4、产品生产计划：合理利用人力、物力、财力等，、产品生产计划：合理利用人力、物力、财力等，使获利最大使获利最大v5 5、劳动力安排：用最少的劳动力来满足工作的需要、劳动力安排：用最少的劳动力来满足工作的需要v6 6、运输问题：如何制定调运方案，使总运费最小、运输问题：如何制定调运方案，使总运费最小v线性规划总结：线性规划总结：v（一）线性规划的组成：（一）线性规划的组成：v目标函数目标函数 Max F 或或 Min Fv约束

10、条件约束条件 s.t.(subject to)满足于满足于v决策变量决策变量 用符号来表示可控制的因素用符号来表示可控制的因素v（二）建模过程（二）建模过程1.理解要解决的问题，了解解题的目标和条件；理解要解决的问题，了解解题的目标和条件；2.定义决策变量（定义决策变量（x1，x2，xn），每一组值表），每一组值表示一个方案；示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件中必须遵循的约束条件

11、v（三）线性规划模型的一般形式（三）线性规划模型的一般形式目标函数：目标函数：约束条件：约束条件：njxbxaxaxabxaxaxabxaxaxaxcxcxcZjmnmnmmnnnnnn,2,1,0),(),(),(max(min)221122222121112121112211例题分析例题分析1：生产计划问题：生产计划问题v例例1.某工厂在计划期内要安排某工厂在计划期内要安排、两种产品的两种产品的生产，已知生产单位产品所需的设备台时及生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：两种原材料的消耗、资源的限制，如下表：问：工厂应分别生产多少单位问：工厂应分别

12、生产多少单位、产品才能使工产品才能使工厂获利最多？厂获利最多？例题分析例题分析1：生产计划问题：生产计划问题v解：工厂应分别生产解：工厂应分别生产、产品产品x1、x2单位，则所求的线性规划模型为：单位，则所求的线性规划模型为：0,2504002300.10050max212212121xxxxxxxtsxxZ例题分析例题分析2：食谱问题：食谱问题v例例1 已知某人每周所需的营养成分、所食用的食品及已知某人每周所需的营养成分、所食用的食品及单位食品所含营养如下表所示：单位食品所含营养如下表所示：营养成分营养成分 大米大米 白菜白菜 鸡蛋鸡蛋 猪肉猪肉 营养成分的需要量（周）营养成分的需要量（周）

13、蛋白质蛋白质某维生素某维生素某矿物质某矿物质 a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 b1 b2 b3单价（元）单价（元）c1 c2 c3 c4 问这个人每周应食用大米、白菜、鸡蛋和猪肉各多问这个人每周应食用大米、白菜、鸡蛋和猪肉各多少，能使生活费用最省？少，能使生活费用最省？例题分析例题分析2：食谱问题：食谱问题v解：设这个人每周应食用大米、白菜、解：设这个人每周应食用大米、白菜、鸡蛋、猪肉各为鸡蛋、猪肉各为x1、x2、x3、x4，则所，则所求的线性规划模型为：求的线性规划模型为：0,.min4321341433323213124243

14、23222121141431321211144332211xxxxbxaxaxaxabxaxaxaxabxaxaxaxatsxcxcxcxcZ例题分析例题分析3：人力资源分配问题：人力资源分配问题例例2 2某昼夜服务的公交线路每天各时间段内所需司机和乘务某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员能满足工作需要，又配备最少司机和乘

15、务人员?例题分析例题分析3：人力资源分配问题：人力资源分配问题解：设解：设 x xi i 表示从第表示从第i i班次开始上班的司机和乘务人员数班次开始上班的司机和乘务人员数(i=1,2,3,4,5,6),(i=1,2,3,4,5,6),这样我们建立如下的数学模型。这样我们建立如下的数学模型。0,302050607060.min654321655443322116654321xxxxxxxxxxxxxxxxxxtsxxxxxxZ例题分析例题分析4：合理下料问题：合理下料问题v例例4 假定现有一批某种型号的圆钢长假定现有一批某种型号的圆钢长8米，需要裁取长米，需要裁取长2.5米的毛坯米的毛坯100

16、根、长根、长1.3米的毛坯米的毛坯200根，问应该怎样选择根，问应该怎样选择下料方式才能既满足需要，又使总的用料最省？下料方式才能既满足需要，又使总的用料最省？v解：各种可能的裁剪方案如下表所示：解：各种可能的裁剪方案如下表所示：型号型号方案方案1 方案方案2 方案方案3 方案方案4需要根数需要根数2.5米米1.3米米 3 2 1 0 0 2 4 6 100 200余料余料(米米)0.5 0.4 0.3 0.2 例题分析例题分析4：合理下料问题：合理下料问题v设设 x1,x2,x3,x4 分别为上面分别为上面4种方案下料种方案下料的原材料根数。这样我们建立如下的数的原材料根数。这样我们建立如下

17、的数学模型。学模型。0,20064210023.min43214323214321xxxxxxxxxxtsxxxxZ例题分析例题分析5：投资问题：投资问题例例5 5 某部门现有资金某部门现有资金200200万元，今后五年内考虑给以下的项目万元，今后五年内考虑给以下的项目投资。已知：投资。已知：项目项目A A：从第一年到第五年每年年初都可投资，当年末能收回：从第一年到第五年每年年初都可投资，当年末能收回本利本利110%110%；项目项目B B：从第一年到第四年每年年初都可投资，次年末能收回：从第一年到第四年每年年初都可投资，次年末能收回本利本利125%125%，但规定每年最大投资额不能超过，但规

18、定每年最大投资额不能超过3030万元；万元；项目项目C C：需在第三年年初投资，第五年末能收回本利：需在第三年年初投资，第五年末能收回本利140%140%，但，但规定最大投资额不能超过规定最大投资额不能超过8080万元；万元；项目项目D D：需在第二年年初投资，第五年末能收回本利：需在第二年年初投资，第五年末能收回本利155%155%，但，但规定最大投资额不能超过规定最大投资额不能超过100100万元。万元。问应如何确定这些项目的每年投资额，使得第五年年末拥问应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？有资金的本利金额为最大？例题分析例题分析4：投资问题：投资问题v

19、解：解：设设 xij(i=15，j=14)表示第表示第 i 年初年初投资于投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目项目的金额。这样我们建立如下的决策变量：的金额。这样我们建立如下的决策变量：v 1 2 3 4 5 v A x11 x21 x31 x41 x51 v B x12 x22 x32 x42v C x33 v D x24例题分析例题分析5：投资问题：投资问题)4,3,2,1;5,4,3,2,1(0100080)4,3,2,1(3025.11.125.11.125.11.11.1200.55.14.125.11.1max2433232415122314241122

20、133323111242221121124334251jixxxixxxxxxxxxxxxxxxxxxxtsxxxxZiji投资问题（作业）投资问题（作业）某部门现有资金100万元，今后五年内考虑给以下的项目投资。已知：项目项目A A：五年内每年初均可投资，且金额不限，投资期限1年，年回报率7%；项目项目B B：五年内每年初均可投资，且金额不限，投资期限2年，年回报率10%（不计复利）；项目项目C C：五年内每年初均可投资，且金额不限，投资期限3年，年回报率12%（不计复利）；项目项目D D：只在第一年初有一次投资机会，最大投资额50万元，投资期限4年，年回报率20%（不计复利）；项目项目E

21、E：在第二年和第四年初有一次投资机会，最大投资额30万元，投资期限1年，年回报率30%；项目项目F F：在第四年初有一次投资机会，金额不限，投资期限2年，年回报率25%；假设当年投资金额及其收益均可用于下一年投资，问公司如何投资才能使得第五年末收回的本利金额最大？合理下料问题（作业）合理下料问题（作业）新华造纸厂接到三份订购卷纸的订单，其长和宽的要求如下表所示：该厂生产1米和2米两种标准宽度的卷纸。假定卷纸的长度无限制，即可以连接起来达到所需的长度，问如何切割才能使切割损失的面积最小？订单号码订单号码宽（米）宽（米）长（米）长（米）10.5100020.7300030.92000产品配套问题（

22、作业）产品配套问题（作业）假定一个工厂的甲、乙、丙三个车间生产同一产品，每件产品包含4个A零件和3个B零件。这两种零件由两种不同的原材料制成，而这两种原材料的现有数额分别是100千克和200千克。第个生产班的原材料需要量和零件产量如下表所示：问：这三个车间各应开多少班次才能使这种产品的配套数达到最大？车间车间第班进料数（千克）第班进料数（千克）每班产量（个数）每班产量（个数）第一种原料第二种原料A零件B零件甲8675乙5969丙3884计划生产问题（作业）计划生产问题（作业）某化工厂要用三种原料混合配置三种不同规格的产品，各产品的规格单价如下表所示：问：如何安排生产利润最大？产品产品规格规格单

23、价（元单价（元/公斤）公斤）甲原料A不少于50%，原料B不超过25%50乙原料A不少于25%，原料B不超过50%35丙不限25原料原料日最大供应量（公斤）日最大供应量（公斤）单价（元单价（元/公斤）公斤）A10065B10025C6035 设设K是是n维欧氏空间的一个维欧氏空间的一个点集，若任意两点点集，若任意两点X（1）K，X（2）K的连线上的一切点：的连线上的一切点：（01），则称），则称K为为。设设X（1）,X（2）,X（k）是是n维欧氏空维欧氏空间中的间中的K个点个点,若存在若存在k个数个数1,2,k,满足满足0i1,i=1,2,k；且；且 ，则称则称X=1X（1）+2X（2）+kX(

24、k)为为 X（1）,，X（2），X（k）的的。设设K是凸集，是凸集，X K；若；若X不能用不能用 X（1）K，X（2）K 的线性组合表示，即的线性组合表示，即 则称则称X为为K的一个的一个（也称极点或角点）（也称极点或角点）kii11：线性规划问题的可行解集线性规划问题的可行解集（即可行域）（即可行域）是凸集。是凸集。线性规划几何理论基本定理线性规划几何理论基本定理若若 ，则则X是是D的一个顶点的充分必要条件是的一个顶点的充分必要条件是X为线为线性规性规 划的基本可行解。划的基本可行解。若可行域非空有界，则线性规划问若可行域非空有界，则线性规划问题的目标函数一定可以在可行域的顶点上题的目标函数

25、一定可以在可行域的顶点上达到最优值。达到最优值。若目标函数在若目标函数在k个点处达到最优值个点处达到最优值（k2）,则在这些顶点的凸组合上也达到则在这些顶点的凸组合上也达到最优值。最优值。：满足约束条件和非负条件：满足约束条件和非负条件的决策变量的一组取值。的决策变量的一组取值。：所有可行解的集合。：所有可行解的集合。：LP问题可行解集构成问题可行解集构成n维空维空间的区域，可以表示为：间的区域，可以表示为：0,|XbAXXD4.:使目标函数达到最优值的可行解。使目标函数达到最优值的可行解。5.：最优解对应目标函数的取值。：最优解对应目标函数的取值。6.:求出问题的最优解和最优值。求出问题的最

26、优解和最优值。7.：设：设A是约束方程组是约束方程组mn的系数矩阵，的系数矩阵，A的的秩秩R(A)m，B是是A中中mm阶非奇异子式阶非奇异子式,即即|B|0,则称则称B是是LP问题的一个基。问题的一个基。8.基变量基变量:B=P1,P2,Pm,称称Pj(j=1,2,m)为基向量为基向量,与与Pj对应的变量对应的变量xj(j=1,2,m)称为基变量称为基变量,其余的其余的xm+1,xn为为非基变量非基变量。9.基本解基本解:令非基变量等于令非基变量等于0，从，从AXb中中解出的基变量所得的解称为解出的基变量所得的解称为LP关于基关于基B的的基本解。基本解。可行解与基本解的区别？可行解与基本解的区

27、别？设设AX=b是含是含n个决策变量、个决策变量、m个个约束条件的约束条件的LP的约束方程组，若的约束方程组，若B是是LP问问题的一个基，若令不与题的一个基，若令不与B的列相应的的列相应的n-m个个分量（非基变量）都等于零，所得方程组分量（非基变量）都等于零，所得方程组的解的解X=x1,x2,xm,0,0T称为称为，简称简称为为。10.11.12.n基本解的个数基本解的个数C Cm m基本可行解的非零分量均为正分量基本可行解的非零分量均为正分量个数不超过个数不超过mm最优解基本最优解1图解法图解法 线性规划的图解法就是用几何作图的方法线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程

28、。分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求解的思路是：先将约束条件加以图解，求得满足约束条件和非负条件的解的集合求得满足约束条件和非负条件的解的集合（即可行域），然后结合目标函数的要求从（即可行域），然后结合目标函数的要求从可行域中找出最优解。可行域中找出最优解。第二节第二节 线性规划问题的解法线性规划问题的解法 实施图解法，以求出实施图解法，以求出生产计生产计划（划（）,给出给出 例：例：0,1241648232max21212121xxxxxxxxZ由于线性规划模型中只有两个决策变量，因此由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了

29、。只需建立平面直角坐标系就可以进行图解了。建立平面直角坐标系建立平面直角坐标系 标出坐标原点标出坐标原点,坐标轴的指向和单位坐标轴的指向和单位长度。用长度。用x1轴表示产品轴表示产品A的产量，用的产量，用x2轴表示产品轴表示产品B的产量。的产量。对约束条件加以图解。对约束条件加以图解。画出目标函数等值线，结合目标函数画出目标函数等值线，结合目标函数的要求求出最优解：最优生产方案。的要求求出最优解：最优生产方案。最优解带入目标函数，得出最优值。最优解带入目标函数，得出最优值。约束条件的图解约束条件的图解:每一个约束不等式在平面直角坐标系中每一个约束不等式在平面直角坐标系中都代表一个半平面，只要都

30、代表一个半平面，只要，然后，然后。?以第一个约束条件以第一个约束条件:为例为例,说明图解过程。说明图解过程。8221 xx代表一个半平面代表一个半平面其边界其边界:及及 AOB1203x24123x185678221 xxQ48221 xx0,21xx8221 xx8221 xx设备全部占用所生产设备全部占用所生产、数量对应的点数量对应的点的集合。的集合。全部的设备都用来生产全部的设备都用来生产产品而不生产产品而不生产产品产品,那么那么产品的最大可能产量为产品的最大可能产量为8台台,计计算过程为：算过程为：x1+20 8 x1 8设备没有全部占用所设备没有全部占用所生产生产、数量对应数量对应的

31、点的集合。的点的集合。1203x2412 3x185 6 78221 xxQ4约束条件及约束条件及非负条件非负条件代表的公共部分图中阴影区，就是满足所代表的公共部分图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的在这个区域中的每一个点都对应着一个可行的生产方案。生产方案。另两个约束条件的另两个约束条件的边界直线边界直线CD、EF:4x116，4 x2 121242x1641x85678221 xxx13x241231020,21xx 令令 Z=2x1+3x2=c,其中其中，在图，在图 中画出直线中

32、画出直线 2x1+3x2=c,即对应着一个可行的生产结果，即对应着一个可行的生产结果，即使两种产品的总利润达到即使两种产品的总利润达到c。这样的直线有无数条，且相互平行，称这样的直这样的直线有无数条，且相互平行，称这样的直线为线为。画两条目标函数画两条目标函数，如令如令 c0和和c=6，可看出，可看出,即虚线即虚线 l1和和l2,箭头为产箭头为产 品的总利润递增的方向。品的总利润递增的方向。1242x1641x85678221 xxx13x24123102对应坐标对应坐标x1=4,x2=2 是最佳的产品组合是最佳的产品组合,4,2T就是线就是线性规划模型的性规划模型的使产品的总利润达到最大值使

33、产品的总利润达到最大值maxZ=2 4+3 2=14就是就是目标函数目标函数方向方向目标函数等值线，达到目标函数等值线，达到,E点就是点就是1242x1641x85678221 xxx13x24123102 尽管最优点的对应坐标可以直接从图中尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通确地看出一个解答是比较困难的。所以，通常总是常总是 比如比如C点对应的坐标值我们可以通过求点对应的坐标值我们可以通过求解下面的联立方程，即求直线解下面的联立方程，即求直线AB和和CD的交的交点来求得。点来求得。

34、直线直线AB:x1+2x2=8 直线直线CD:4x1=1612121228416412,0 xxxxx x12max23Zxx1242x1641x85678221 xxx13x24123102将例将例1-1稍作改动形成案例稍作改动形成案例1，仍使用图解法来求解。，仍使用图解法来求解。（案例（案例1）某工厂生产）某工厂生产A、B、C三种产品，三种产品，每吨的利润分别为每吨的利润分别为2000元、元、3000元、元、1000元，元，生产单位产品所需的工时及原材料如表生产单位产品所需的工时及原材料如表1-2所所示。应如何制定日生产计划，使三种产品的总示。应如何制定日生产计划，使三种产品的总利润最大？

35、利润最大？表表1-2 生产单位产品所需的工时及原材料表生产单位产品所需的工时及原材料表 12140材料材料B（kg）16104材料材料A（kg）8121设备（台）设备（台）资源资源限量限量 产品产品资源资源 设三种产品的产量分别是设三种产品的产量分别是x1、x2、x3吨，由于有三个决策变量，用图解法求吨，由于有三个决策变量，用图解法求解下面的线性规划时，必须首先建立空解下面的线性规划时，必须首先建立空间直角坐标系。间直角坐标系。结果结果 用图解法求解线性规划的各种可能的结果用图解法求解线性规划的各种可能的结果讨论讨论 12max23Zxx12121228416412,0 xxxxx x212m

36、axxxZ85678221xxx13x24123102 沿着箭头的方向平移目标函数等值线，沿着箭头的方向平移目标函数等值线，发现平移的最终结果是目标函数等值线将发现平移的最终结果是目标函数等值线将与可行域的一条边界线段与可行域的一条边界线段AB重合。重合。结果表明，该线性规划有结果表明，该线性规划有线段线段AB上的所有点都是最优上的所有点都是最优点，它们都使目标函数取得相同的最大值点，它们都使目标函数取得相同的最大值Zmax=14。121212242,0 xxxxx x12maxZxx2406x212543x1 如图中可行域是一个无界区域，如阴影区所示。虚如图中可行域是一个无界区域，如阴影区所

37、示。虚线为目表函数等值线，沿着箭头指的方向平移可以使目线为目表函数等值线，沿着箭头指的方向平移可以使目标函数值无限制地增大，但是找不到最优解。这种情况标函数值无限制地增大，但是找不到最优解。这种情况通常称为通常称为”。如果一个实际问题抽象成像例如果一个实际问题抽象成像例1-4这样的线性规划模这样的线性规划模型，比如是一个生产计划问题，其经济含义就是某些资源型，比如是一个生产计划问题，其经济含义就是某些资源是无限的，产品的产量可以无限大。此时应重新检查和修是无限的，产品的产量可以无限大。此时应重新检查和修改模型，否则就没有实际意义。改模型，否则就没有实际意义。注意，注意，。1947年G.B.Da

38、ntzig提出的单纯形法提供了方便、有效的通用算法求解线性规划 2需要解决的问题：需要解决的问题：(1)为了使目标函数逐步变优，怎么转移？为了使目标函数逐步变优，怎么转移？(2)目标函数何时达到最优目标函数何时达到最优 判断标准是什么？判断标准是什么？二、单纯形法原理（用代数方法求解二、单纯形法原理（用代数方法求解LP）例：例：0,1241648232max21212121xxxxxxxxZ123451231425max23000284164120,1,2,5jZxxxxxxxxxxxxxj对应的基变量是对应的基变量是 x3 x4 x51234512100()4001004001，APPPPP

39、TX(0,0,8,16,12)0(312415282164124xxxxxxx请解释结果的经济含义请解释结果的经济含义！12max23Zxx0)0(Z当前的目标函数值非基变量前面的系数均为正数，所以任何非基变量前面的系数均为正数，所以任何一个非基变量进基都能使一个非基变量进基都能使Z值增加值增加；12max23Zxx 选选x1为为（）x2进基意味着其取值从进基意味着其取值从0变成一个正数（经济变成一个正数（经济意义意义生产生产B产品），能否无限增大？产品），能否无限增大？当当x2增加时，增加时，x3、x4、x5如何变化？如何变化？现在的非基变量是哪些？现在的非基变量是哪些？具体如何确定换出变量

40、？具体如何确定换出变量？当当x2增加时，增加时，x3，x4，x5会减小，但有限度会减小，但有限度?必须大于等于必须大于等于0，以保持解的可行性！，以保持解的可行性！312415282164124xxxxxxx324528201601240 xxxxx2min(8/2,12/4)3x 。这种用来确定出基变量的规则称为这种用来确定出基变量的规则称为 。X（1）=（0,3,2,16,0）T由由321412528164412xxxxxxx315412520.516430.25xxxxxxx15920.75Zxx12max23Zxx 为什么？为什么？j Cj 2 3 0 0 0b xj x1 x2 x3

41、 x4 x5CB XB 0 x3 8 1 2 1 0 0 0 x4 16 4 0 0 1 0 0 x5 12 0 4 0 0 1 -Z 0 2 3 0 0 0 01122112211222222121111212111mnmnnnnnmmnnmnmmnnnnnnxcxcxcxcxcZbxxaxaxabxxaxaxabxxaxaxa-Z X1 X2 Xn Xn+1 Xn+2 Xn+m b01100001000010212121222221111211mnnnnmmnmmnnccccccbaaabaaabaaamnnnccc,21021212222211112110001100001000010z

42、baaabaaabaaanmmnmmnnmiijinjjacc1miiinbcz100其中，其中，j=1，2，n；njzcPCcaccjjjBjmiijinjj,2,1,1j CB XB Cj b xj 2 3 0 0 0 x1 x2 x3 x4 x5 j 0 0 0 X3 X4 X5 8 16 12 1 2 1 0 0 4 0 0 1 0 0 4 0 0 18/2-12/4 -Z 0 2 3 0 0 0 0 0 3 X3 X4 X2 2 16 3 1 0 1 0 -1/2 4 0 0 1 0 0 1 0 0 1/4 2/1 16/4 -Z -9 2 0 0 0 -3/4 2 0 3 X1 X

43、4 X2 2 8 3 1 0 1 0 -1/2 0 0 -4 1 2 0 1 0 0 1/4 -8/23/(1/4)-Z-13 0 0 -2 0 1/4 CB XB Cj b xj 2 3 0 0 0 x1 x2 x3 x4 x5 j 2 0 3 X1 X4 X2 2 8 3 1 0 1 0 -1/2 0 0 -4 1 2 0 1 0 0 1/4-8/23/(1/4)-Z-13 0 0 -2 0 1/4 2 0 3 X1 X5 X2 4 4 2 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 -Z-14 0 0 -3/2 -1/8 0已解决的问题：已解决的问题：

44、(1)为了使目标函数逐步变优，怎么转移？为了使目标函数逐步变优，怎么转移？通过顶点的转移，即进基与出基达到目的。通过顶点的转移，即进基与出基达到目的。(2)目标函数何时达到最优目标函数何时达到最优 判断标准是什么？判断标准是什么？检验数检验数 :1、若所有的检验数均、若所有的检验数均 ，则停止计算，可找到最优解；，则停止计算，可找到最优解；2、若有、若有 ，且，且 的系数列向量的系数列向量 ，则该问题无界，停止计算；则该问题无界，停止计算；3、若在最终表中有非基变量的检验数为、若在最终表中有非基变量的检验数为0，则该问题有无，则该问题有无穷多最优解。穷多最优解。j0j)1(0nkkkx0kP0

45、.XbAXtsCXMaxZ)(NBCCC)(NBXXX)(),(21NBPPPAn第三节第三节 线性规划问题的对偶问题线性规划问题的对偶问题（1）由约束条件）由约束条件 bNXBXXXNBAXNBNB)(可得可得 NNBNXBbBNXbBX111)(（2-1）（得令22)()()(11111111NNBBNNNBNBNNNBBNNNBNNBBNBNBXbBCZNBCCXNBCCbBCXCNXBCbBCXCNXBbBCXCXCXXCCCXZ 0)(1BBBXBBCC01BBBBBXBCXC代入式（代入式（2-2），并令），并令 1BCBXACbBXBCXCXNBCCbBCZBBBBNBNB)()

46、(111（2-4）cjjTBXTNXTBCBXbB1BB1NB1ZbBCB1NBCCBN1 CB XB xjbCB CN 0 例：要求制定一个生产计划方案，在劳动例：要求制定一个生产计划方案，在劳动力和原材料可能供应的范围内，使得产品力和原材料可能供应的范围内，使得产品的总利润最大的总利润最大。12max23Zxx12121228 416 412 ,0 xxxxx x 它的它的就是一个就是一个，使在平，使在平衡了设备资源和原材料的直接成本后，所确衡了设备资源和原材料的直接成本后，所确定的定的0,34224.121683213221321yyyyyyytsyyyMinW 若工厂自己不生产产品若工

47、厂自己不生产产品、，将现有的将现有的设备及原材料转而接受外来加工时，那么设备及原材料转而接受外来加工时，那么（包工及原材料的总价格最低）（包工及原材料的总价格最低）当原问题和对偶问题都取得最优解时，这当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：一对线性规划对应的目标函数值是相等的：Zmax=Wmin=14 考察原问题和对偶问题的解，给作决考察原问题和对偶问题的解，给作决策的管理者另一个自由度；策的管理者另一个自由度；0,)(30305.75.1713.068.027.06.0)(40003250175015001000.5.19.05.08.04321421432

48、143214321xxxxCxxxBxxxxAxxxxtsxxxxMinZ毫克维生素）（毫克维生素国际单位维生素 换一个角度，生产营养药丸的制药公司力换一个角度，生产营养药丸的制药公司力图使营养师相信，各种营养药丸勿须通过多种图使营养师相信，各种营养药丸勿须通过多种食品的转换就能供营养师调剂。食品的转换就能供营养师调剂。制药公司面对的问题是制药公司面对的问题是，以获得最大的收益，同时与，以获得最大的收益，同时与真正的食品竞争。真正的食品竞争。于是，营养药丸的单位成本于是，营养药丸的单位成本相应食品的市场平均价。相应食品的市场平均价。0,)(5.1303.03250)(9.0068.01750)

49、(5.05.727.01500)(8.05.176.01000.304000321321321321321321yyyIVyyyIIIyyyIIyyyIyyytsyyyMaxW丁食品市价的成本合成药丸丙食品市价的成本合成药丸乙食品市价的成本合成药丸甲食品市价的成本合成药丸（1）若原问题是）若原问题是 0,.21221122222112112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcMaxZ0,.21221122222112112211112211mnnmnnnnmmmmmyyycyayayacyayayacyayayatsyby

50、bybMinW 这两个式子的变换关系称为这两个式子的变换关系称为“”。(2)其对偶问题为其对偶问题为（2）对称形式的对偶关系的矩阵描述）对称形式的对偶关系的矩阵描述0.YCYAtsbYMinW(D)(D)0.XbAXtsCXMaxZ(L)(L)例例2-3 写出下面线性规划的对偶问题：写出下面线性规划的对偶问题：0,10251543.221212121xxxxxxtsxxMaxZ0,124253.101521212121yyyyyyt syyMinWnjxmibxat sxcMaxZjnjijijnjjj,2,10,2,1.11miynjcyat sxbMinWimijiijmiii,2,1,2