第1章线性规划及对偶问题.ppt

《第1章线性规划及对偶问题.ppt》由会员分享，可在线阅读，更多相关《第1章线性规划及对偶问题.ppt（29页珍藏版）》请在优知文库上搜索。

1、第1章 线性规划及对偶问题教学要求与主要内容教学要求与主要内容：n教学要求：教学要求：n通过本章的学习，了解线性规划及其对偶问题的基本理论；通过本章的学习，了解线性规划及其对偶问题的基本理论；掌握线性规划求解的基本方法掌握线性规划求解的基本方法单纯形法单纯形法,了解对偶单了解对偶单纯形方法，熟悉灵敏度分析的方法；会建构线性规划模型，纯形方法，熟悉灵敏度分析的方法；会建构线性规划模型，并会用并会用“规划求解规划求解”模板进行求解。模板进行求解。n主要内容：主要内容：n1.1 线性规划模型线性规划模型n1.2 线性规划求解基本方法线性规划求解基本方法n1.2.1 图解法图解法n1.2.2 单纯形法

2、简介单纯形法简介n1.3 线性规划对偶问题线性规划对偶问题n1.4 线性规划应用举例线性规划应用举例n本章小结本章小结1.1 线性规划线性规划(Linear Programming)模型模型n1.1.1 问题的提出问题的提出产品甲产品甲 产品乙产品乙生产能力生产能力(小时小时)设备设备A A7 73 3210210设备设备B B4 45 5200200设备设备C C2 24 4180180计划利润计划利润(元元/件件)70706565设：产品甲生产设：产品甲生产x1，产品乙生产，产品乙生产x2目标：目标：Max z=70 x1+65x2约束条件：约束条件：设备设备A生产能力限制：生产能力限制：

3、7x1+3x2210设备设备B生产能力限制：生产能力限制：4x1+5x2200设备设备C生产能力限制：生产能力限制：2x1+4x21801212121212max70657321045200.24180,0zxxxxxxstxxx x产量非负限制：产量非负限制：x1，x20决策变量决策变量决策变量决策变量目标函数目标函数约束条件约束条件三要素：三要素：1.决策变量决策变量2.目标函数目标函数3.约束条件约束条件1.1.2 线性规划模型线性规划模型n1.适用条件：适用条件：n（1）优化条件）优化条件:问题目标最大化、最小化的要求；问题目标最大化、最小化的要求；n（2）约束条件）约束条件:问题目标

4、受一系列条件的限制；问题目标受一系列条件的限制；n（3）选择条件）选择条件:实现目标存在多种备选方案；实现目标存在多种备选方案；n（4）非负条件的选择）非负条件的选择:根据问题的实际意义决定是否非负。根据问题的实际意义决定是否非负。n2.构建线性规划模型的步骤构建线性规划模型的步骤n（1）科学选择决策变量）科学选择决策变量n（2）根据实际问题的背景材料，找出所有的约束条件）根据实际问题的背景材料，找出所有的约束条件n（3）明确目标要求）明确目标要求n（4）确定是否增加决策变量的非负条件）确定是否增加决策变量的非负条件 例2nMin z=2x1+6x2+5x3+4x4+3x5n 0.50 x1+

5、2.00 x2+3.00 x3+1.50 x4+0.80 x585n 0.10 x1+0.06x2+0.04x3+0.15x4+0.20 x55n 0.08x1+0.70 x2+0.35x3+0.25x4+0.02x518n x1x50饲料饲料 营养甲营养甲(克克/公斤公斤)营养乙营养乙(克克/公斤公斤)营养丙营养丙(克克/公斤公斤)成本成本(元元/公斤公斤)1 10 050500 010100 008082 22 22 200000 006060 070706 63 33 300000 004040 035355 54 41 150500 015150 025254 45 50 080800

6、 020200 002023 3需要需要85克克5克克18克克设设X1X2X3X4x5由决策变量、目标函数和约束条件构成的问题称为规划问题，如果决策变量为可由决策变量、目标函数和约束条件构成的问题称为规划问题，如果决策变量为可控连续变量，目标函数和约束条件则是决策变量的线性函数，则称为线性规划问控连续变量，目标函数和约束条件则是决策变量的线性函数，则称为线性规划问题。（题。（P12例例1.3）3.线性规划模型表示形式线性规划模型表示形式1 122()nnMax Min Zc xc xc x11 11221121 1222221 12212(.(,0nnnnmmmnnmna xa xa xba

7、xa xa xbsta xa xa xbx xx 或，）或，）或，）(1,2,)jxjn决策变量；决策变量；(1,2,)jcjn目标函数系数、价值系数或费用系数；目标函数系数、价值系数或费用系数；(1,2,)ib im右端项或资源常数；右端项或资源常数；(1,2,;1,2,)ija im jn 称为约束系数或技术系数。称为约束系数或技术系数。（1）一般形式：）一般形式：（2）集合形式：）集合形式：12nxxXx111212122212nnmmmnaaaaaaAaaa1()njjjMax Min Zc x1(1,2,).0(1,2,)nijjijja xb imstxjn 或，）1()njjjM

8、ax Min Zc x1(.0(1,2,)njjjjp xbstxjn 或，）12mbbbb12,(1,2,)jjjmjaapjna（3）向量形式：）向量形式：()Max Min ZCX(.0AXbstX 或，）（4）矩阵形式：）矩阵形式：12(,)nCc cc127065MaxZxx121212127321045200.241800,0 xxxxstxxxx【例例3】将线性规划模型一般表达式化为将线性规划模型一般表达式化为矩阵形式。矩阵形式。111221223132734524aaAaaaa12(,)TXx x12(,)(70,65)Cc c123210200180bbbb12(70,65)

9、xMaxZx.0AXbstX解解:12732104520024180 xxMaxZCX设设:1.1.3 线性规划标准形式线性规划标准形式1 122nnMaxZc xc xc x11 11221121 1222221 12212.,0nnnnmmmnnmna xa xa xba xa xa xbsta xa xa xbx xx线性规划标准模型的一般表达式线性规划标准模型的一般表达式：非标准形式标准化方法非标准形式标准化方法：1.目标函数目标函数1njjjMinZc xZZ 令 11()nnjjjjjjMaxZc xc x 2.约束条件为不等式约束条件为不等式:1 122iiinnia xa xa

10、 xb引进松驰变量引进松驰变量xs:1 122iiinnsia xa xa xxb1 122iiinnia xa xa xb引进剩余变量引进剩余变量xs:1 122iiinnsia xa xa xxb4.决策变量为自由变量决策变量为自由变量:jxuv令0,0uv 5.约束右端项为负约束右端项为负:1 122iiinnia xa xa xb两端乘两端乘-1:03.约束条件为不等式约束条件为不等式:12335MinZxxx121231231239234.3260,0,xxxxxstxxxxxx 无约束【例例4】将线性规划模型转化为标准式将线性规划模型转化为标准式解解:13(1)0,xx113231

11、3,0 xy xyyyy 令无约束无约束122335MinZyxyy 121223122392334.326,0ijyxyxyystyxyyx y 1223(2)()35MinZMaxZyxyy 1223(3)326yxyy 1223326yxyy(4)在第一、第三约束左端加上松弛变量在第一、第三约束左端加上松弛变量x4,x60，在第二约束左端减去剩余变量，在第二约束左端减去剩余变量x50 1223()35MaxZyxyy1241223512236245692334.326,0yxxyxyyxstyxyyxw x u v x x x作业：P7576习题1、2，P78:8(1)9(2)建模1.2

12、 线性规划基本解法线性规划基本解法n几个基本概念几个基本概念:n可行解：凡满足约束条件的决策变量的取值称为线性规划可行解：凡满足约束条件的决策变量的取值称为线性规划的可行解。的可行解。n可行域可行域：所有可行解的集合称为线性规划的可行域。：所有可行解的集合称为线性规划的可行域。n最优解最优解：使目标函数达到最优值的可行解称为线性规划的：使目标函数达到最优值的可行解称为线性规划的最优解最优解 n1.2.1 图解法图解法(graphical method)n步骤步骤:n(1)平面上画出直角坐标平面上画出直角坐标;n(2)图示约束条件图示约束条件,标出满足所有约束条件的公共区域标出满足所有约束条件的

13、公共区域(可行可行域域);n(3)图示目标函数的一根基线图示目标函数的一根基线(母线母线)按目标值要求按目标值要求,让基线平让基线平行移动行移动,直到与可行域相切为止直到与可行域相切为止,切点即为最优解切点即为最优解;n(4)求出切点坐标值求出切点坐标值,代入目标函数求得目标函数最优值代入目标函数求得目标函数最优值.可行域1232MaxZxx1212122108.,0 xxxxstx x【例例1.6】运用图解法求解线性规划问题运用图解法求解线性规划问题(5,0)3 22 618MaxZ 2x1+x2=10 x1+x2=8(2,6)x1108302 5 8x2(0,8)3x1+2x2=6四种结局

14、四种结局:x1x2唯一最优解x2x1无穷多最优解x1x2无界解x2x1无可行解1.2.2 单纯形法简介n最优解一定在可行域的顶点上最优解一定在可行域的顶点上,将顶点坐标代入目标函数有将顶点坐标代入目标函数有:n(0,0):z=30+20=0n(5,0):z=35+20=15n(0,8):z=30+28=16n(2,6):z=32+26=18n单纯形法的基本思路就是基本单纯形法的基本思路就是基本可行解的转移，先找到一个初可行解的转移，先找到一个初始基本可行解，如果不是最优始基本可行解，如果不是最优解，设法转移到另一个基本可解，设法转移到另一个基本可行解，并使目标函数值不断增行解，并使目标函数值不

15、断增加，直到找到最优解加，直到找到最优解。(5,0)(2,6)108302 5 8x2(0,8)x11.解的概念解的概念21 101101A123421 101011018xxxx2110:,1101NB设12:32MaxZxx例(1.6)121212210.8,0 xxstxxx x12343200MaxZxxxx12312514321080 xxxxxxxx标准化NB3124,NBxxXXxxAXb10,(3,2),(0,0)8NBbCC:(,)NNBBXAXbN BNXBXbX则(,)NNBNNBBBMaxZCXXMaxZCCC XC XXNBNXBXbNNBBmax ZC XC X1|

16、0,:0:NBBXXB b若:取则0AXbX:max ZCX一般地标准化n定义定义:nA为为mn阶矩阵阶矩阵,若若A的秩的秩为为m,B为为A中的任意中的任意mm阶子矩阵阶子矩阵,且行列式且行列式|B|0,则称则称B为线性规划为线性规划的一个的一个基基；n对应的对应的XB为为基变量基变量；nXN为为非基变量非基变量；0BXX称为称为基本解基本解n满足非负约束的基本解满足非负约束的基本解为为基本可行解；基本可行解；n与基本可行解对应的与基本可行解对应的B称称为为可行基。可行基。2.基变量、目标函数的非基变量表达基变量、目标函数的非基变量表达3124121228xxxxxx1200 xx 由于12343200MaxZxxxx12312416210.80 xxxstxxxxx基变量的非基变量表达：基变量的非基变量表达：31241021811xxxx312410:8xbbx故11221021(3,2)(0,0)811xxxx121021(0,0)(2,3)(0,0)811xx 111112341234212222(,)(,)(,)bxaac cc cc caabx3 14213134231231