《线性规划概论与图解法.pptx》由会员分享，可在线阅读，更多相关《线性规划概论与图解法.pptx（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章线性规划与单纯形方法1.2 1.2 线性规划基本概念线性规划基本概念1.3 1.3 线性规划问题的数学模型线性规划问题的数学模型1.4 1.4 线性规划问题解的概念线性规划问题解的概念1.1 1.1 线性规划（概论）线性规划（概论）第1页/共68页线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）1.1 线性规划（概论）第2页/共68页线性规划（概论）线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐
2、克（Dantzig）19511951年提出单纯形算法（年提出单纯形算法（SimplerSimpler）第3页/共68页线性规划（概论）线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simpler）19631963年年DantzigDantzig写成写成“Linear Programming and Linear Programming and ExtensionExtension”第4页/共68页线性规划（概论）线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐克（Dantzi
3、g）1951年提出单纯形算法（Simpler）1963年Dantzig写成“Linear Programming and Extension”19791979年苏联的年苏联的KhachianKhachian提出提出“椭球法椭球法”第5页/共68页线性规划（概论）线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simpler）1963年Dantzig写成“Linear Programming and Extension”1979年苏联的Khachian提出“椭球法”19841984年印度的年印度的Karmarkar
4、Karmarkar提出提出“投影梯度法投影梯度法”第6页/共68页线性规划（概论）线性规划（Linear Programming)创始人：1947年美国人G.B.丹齐克（Dantzig）1951年提出单纯形算法（Simpler）1963年Dantzig写成“Linear Programming and Extension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展
5、。性代数的应用和发展。第7页/共68页生产计划问题如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。1.2 1.2 线性规划基本概念线性规划基本概念第8页/共68页例1.1 生产计划问题（资源利用问题）胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？第9
6、页/共68页解：将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以以下下几个步骤：几个步骤：第10页/共68页解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量第11页/共68页解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50 x1+30 x2第12页/共68页解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量
7、2确定目标函数：家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件：4x1+3x2 120（木工工时限制）（木工工时限制）2x1+x2 50 （油漆工工时限制）（油漆工工时限制）第13页/共68页解：将一个实际问题转化为线性规划模型有以下几个步骤：1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件：4x1+3x2 120（木工工时限制）2x1+x2 50 （油漆工工时限制）4变量取值限制：一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）x1 0,
8、x2 0 第14页/共68页解：将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以以下下几个步骤：几个步骤：1确定决策变量：x1=生产桌子的数量 x2=生产椅子的数量2确定目标函数：家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件：4x1+3x2120（木工工时限制）（木工工时限制）2x1+x2 50 （油漆工工时限制）（油漆工工时限制）4变量取值限制：一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）x1 0,x2 0 第15页/共68页数学模型 max S=50 x1+30 x2 s.t.4x1
9、+3x2 120 2x1+x2 50 x1,x2 0线性规划数学模型三要素：决策变量、约束条件、目标函数第16页/共68页例1.2 营养配餐问题 假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？1.3 线性规划问题的数学模型第17页/共68页各种食物的营养成分表第18页/共68页解解：设x xj j为第j种食品每天的购入量，则配餐问题的线性规划模型为：min S=14x1+6x2+3x3+2x4 s.t.1000 x1+800
10、 x2+900 x3+200 x4 3000 50 x1+60 x2+20 x3+10 x4 55 400 x1+200 x2+300 x3+500 x4 800 x1，x2，x3，x4 0第19页/共68页其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题生产工艺优化问题第20页/共68页线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn(=,)b1 a21x1+a22x2+.+a2nxn(=,)b2 .am1x1+am2x2+.+amnxn(=,)bm x1,x2.xn 0第21页/共68页
11、线性规划问题隐含的假定：比例性假定可加性假定连续性假定确定性假定第22页/共68页线性规划问题隐含的假定：比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。第23页/共68页线性规划问题隐含的假定：连续性假定：线性规划问题中的决策变量应取连续值。连续性假定：线性规划问题中的决策变量应取连续值。确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含确定性假定：线性规划问题
12、中的所有参数都是确定的参数。线性规划问题不包含随机因素。随机因素。第24页/共68页线性规划问题的标准形式(1)：Max S=c1x1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn=b1 a21x1+a22x2+.+a2nxn=b2 .am1x1+am2x2+.+amnxn=bm x1,x2.xn 0其中：bi 0(i=1,2,.m)第25页/共68页线性规划问题的标准形式(2)：n Max S =Max S =c cj jx xj j j=1 n s.t.aijxj=bi (i=1,2,.m)j=1 xj 0 (j=1,2,.n)其中：bi 0 (i=1,2,.m)第
13、26页/共68页线性规划标准型的矩阵形式(3)（矩阵表达型）：Max S =CX s.t.AX =b X 0其中：第27页/共68页如何将一般问题化为标准型：1.若目标函数是求最小值 Min S=CX 则令 S=-S,变为 Max S=-CX2.若约束条件是不等式若约束条件是“”不等式,将原条件变为：n aijxj+xs=bi j=1 xs 0是新引入的非负松驰变量第28页/共68页如何将一般问题化为标准型：3.若约束条件是“”不等式，则变为 n aijxj-xt=bi j=1 X Xt t 0是引入的非负松驰变量4.若约束条件右面的某一常数项 bi0这时只要在bi相对应的约束方程两边乘上-1
14、。第29页/共68页如何将一般问题化为标准型：5.若变量 xj无非负限制，引进两个非负变量xj xj”0 令xj=xj-xj”通过以上步骤，任何形式的线性规划总可以化成标准型。第30页/共68页例1.3 将下列问题化成标准型:Min S =-x1+2x2-3x3s.t.x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3=5 x1,x2 0 x3 无非负限制第31页/共68页标准型：Max Z =x1-2x2+3x3-3x4s.t.x1+x2+x3-x4 +x5 =7 x1-x2+x3-x4 -x6=2 -3x1+x2+2x3-2x4 =5 x1,x2,x3,x4,x5,x6 0
15、注：标准型还不一定是便于求解的形式。第32页/共68页课堂练习：请阅读P1 P3 中的例1.1、例1.2、例1.4。之后完成P31 1.1(1)(2)(4)；1.2。请独立完成：P34 1.8第33页/共68页1.4 线性规划问题解的概念线性规划问题的解：（1）满足约束条件的变量的值，称为可行解。（2）使目标函数取得最优值的可行解，称为最优解。第34页/共68页线性规划问题图解法：例 1.1的数学模型 max S=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1 x2 0第35页/共68页x2504030201010203040 x14x4x1 1+3x+3x2
16、 2 120 120由由 4x4x1 1+3x+3x2 2 120 120 x x1 1 0 x 0 x2 2 0 0围成的区域围成的区域max S=50 xmax S=50 x1 1+30 x+30 x2 2 s.t.4x s.t.4x1 1+3x+3x2 2 120 120 2x 2x1 1+x+x2 2 50 50 x x1 1 x x2 2 0 0第36页/共68页x2504030201010203040 x12x2x1 1+x+x2 2 5050由由 2x2x1 1+x+x2 2 50 50 x x1 1 0 x 0 x2 2 0 0围成的区域围成的区域max S=50 xmax S
17、=50 x1 1+30 x+30 x2 2 s.t.4x s.t.4x1 1+3x+3x2 2 120 120 2x 2x1 1+x+x2 2 50 50 x x1 1 x x2 2 0 0第37页/共68页x2504030201010203040 x x1 12x1+x2 504x1+3x2 120可行域可行域同时满足：同时满足：2x2x1 1+x+x2 2 50 504x4x1 1+3x+3x2 2 120 120 x x1 1 0 x 0 x2 2 0 0的区域的区域可行域max S=50 xmax S=50 x1 1+30 x+30 x2 2 s.t.4x s.t.4x1 1+3x+3
18、x2 2 120 120 2x 2x1 1+x+x2 2 50 50 x x1 1 x x2 2 0 0第38页/共68页x2504030201010203040 x1可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由约束条可行域是由约束条件围成的区域，该件围成的区域，该区域内的每一点都区域内的每一点都是可行解，它的全是可行解，它的全体组成问题的解集体组成问题的解集合。合。该问题的可行域是该问题的可行域是由由OO，QQ1 1，QQ2 2，QQ3 3作为顶点的凸多边作为顶点的凸多边形形max S=50 xmax S=50 x1 1+30 x+30 x2 2 s.
19、t.4x s.t.4x1 1+3x+3x2 2 120 120 2x 2x1 1+x+x2 2 50 50 x x1 1 x x2 2 0 0第39页/共68页x2504030201010203040 x1可行域可行域目标函数是以S作为参数的一组平行线x2=S/30-（5/3）x1max S=50 xmax S=50 x1 1+30 x+30 x2 2 s.t.4x s.t.4x1 1+3x+3x2 2 120 120 2x 2x1 1+x+x2 2 50 50 x x1 1 x x2 2 0 0第40页/共68页x2504030201010203040 x1可行域可行域当S值不断增加时，该直
20、线x2=S/30-（5/3）x1沿着其法线方向向右上方移动。max S=50 xmax S=50 x1 1+30 x+30 x2 2 s.t.4x s.t.4x1 1+3x+3x2 2 120 120 2x 2x1 1+x+x2 2 50 50 x x1 1 x x2 2 0 0第41页/共68页x2504030201010203040 x1可行域可行域当该直线移到当该直线移到QQ2 2点时，点时，S S（目标函数）（目标函数）值达到最大：值达到最大：Max S=50*15+30*20=1350此时最优解=（15，20）Q2（15，20）max S=50 xmax S=50 x1 1+30 x
21、+30 x2 2 s.t.4x s.t.4x1 1+3x+3x2 2 120 120 2x 2x1 1+x+x2 2 50 50 x x1 1 x x2 2 0 0第42页/共68页二个重要结论：二个重要结论：1。满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。2。最优解必定能在凸多边形的某一个顶点上取得，这一事实也可以推广到更多变量的场合。第43页/共68页解的讨论：解的讨论：最优解是唯一解；第44页/共68页解的讨论解的讨论：1。最优解是唯一解2。无穷多组最优解：例1.1的目标函数由 max S=50 x1+30 x2变成：max S=40 x1+30 x2 s.
22、t.4x1+3x2 120 2x1+x2 50 x1,x2 0第45页/共68页x2504030201010203040 x1可行域可行域目标函数是同约束条件：4x1+3x2 120平行的直线x2=S/30-（4/3）x1max S=40 xmax S=40 x1 1+30 x+30 x2 2 s.t.4x s.t.4x1 1+3x+3x2 2 120 120 2x 2x1 1+x+x2 2 50 50 x x1 1 x x2 2 0 0第46页/共68页x2504030201010203040 x1可行域可行域当S的值增加时，目标函数同约束条件：4x1+3x2 120重合，Q1与Q2之间都是
23、最优解。Q1（25，0）Q2（15，20）第47页/共68页解的讨论：u最优解是唯一解；u无穷多组最优解：无界解：例：max S=x1 +x2 s.t.-2x1+x2 40 x1-x2 20 x1 x2 0第48页/共68页x2504030201010203040 x1该可行域无界，该可行域无界，目标函数值可增目标函数值可增加到无穷大，称加到无穷大，称这种情况为无界这种情况为无界解或无最优解。解或无最优解。-2x-2x1 1+x+x2 2 40 40 x x1 1-x-x2 2 20 20第49页/共68页解的讨论：解的讨论：无可行解：例：max S=2x1+3x2 s.t.x1+2x2 8
24、x1 4 x2 3 -2x1+x2 4 x1,x2 0该问题可行域为空集，该问题可行域为空集，即无可行解，也不存即无可行解，也不存在最优解。在最优解。第50页/共68页解的情况：1。有可行解2。有唯一最优解3。有无穷最优解4。无最优解5。无可行解第51页/共68页课堂练习：P34 1.7(偶数号)第52页/共68页线性规划问题解的概念线性规划标准型的矩阵形式：Max S =C X （1-9）s.t.A X=b （1-10）X 0 （1-11）其中第53页/共68页解、可行解、最优解1。满足约束条件（1-10）的X，称为 线性规划问题的解。2。满足约束条件（1-10）与（1-11）的X，称为线性
25、规划的问题可行解。3。使目标函数（1-9）取得最优的可行解X 称为线性规划的问题最优解。Max S =CX Max S =CX （1-91-9）s.t.AX=b s.t.AX=b （1-101-10）X X 0 0 （1-111-11）第54页/共68页基、基向量、基变量1。设 r(A)=m,并且B是A的m 阶非奇异 的子矩阵（det(B)0),则称矩阵 B为线性规划问题的一个基。2。设矩阵 B=（P1，P2 .Pm)是一个基，其列向量 Pj 称为对应基B的基向量。3。与基向量 Pj 相对应的变量xj就称为 基变量，其余的就称为非基变量。第55页/共68页基础解.基础可行解.可行基1。对于某一
26、特定的基对于某一特定的基B B，非基变量取，非基变量取 0 0 值的解，称为基础解。值的解，称为基础解。2。满足非负约束条件的基础解，称满足非负约束条件的基础解，称 为基础可行解。为基础可行解。3。与基础可行解对应的基，称为可与基础可行解对应的基，称为可 行基。行基。第56页/共68页为了理解基础解.基础可行解.最优解的概念，用下列例子说明：例例1.41.4：max S=2x1+3x2 （1-12 ）s.t.-2x1+3x2 6 （1-13-1）3x1 -2x2 6 （1-13-2）x1 +x2 4 （1-13-3）x1,x2 0 （1-14 ）第57页/共68页将该问题化为标准形式如下：ma
27、x S=2x1+3x2 s.t.-2x1+3x2+x3 =6 3x1 -2x2 +x4 =6 x1 +x2 +x5=4 x1,x2,x3,x4,x5 0 其约束条件的系数矩阵为：第58页/共68页找出三个向量构成基，其对应的变量为基变量，令其他的变量（非基变量）均为零。可以解出基变量的值，即为基解。之后，确定这些基解是否是可行解。将可行的（基础可行解）代入目标函数，求出相应的目标函数值。可使目标函数最优的，就是最优解。在下面的表中，最优解用星号标出。第59页/共68页基基基解基解可行可行？S S标标记记x x1 1x x2 2x x3 3x x4 4x x5 5P P1 1P P2 2P P3
28、 34 43 3-2-20 00 0否否1717A AP P1 1P P2 2P P4 43 33 30 04 40 0是是15*15*Q Q3 3P P1 1P P2 2P P5 54 42 20 00 05 5是是1414Q Q2 2P P1 1P P3 3P P5 54 40 04 40 01515是是8 8Q Q1 1P P1 1P P4 4P P5 56 60 00 0-8-8 1515否否1212B BP P2 2P P3 3P P4 40 03 36 616160 0是是9 9Q Q4 4P P2 2P P4 4P P5 50 06 60 01616-15-15否否1818C C
29、P P3 3P P4 4P P5 50 00 01212 1616 1515是是0 0O O第60页/共68页x x2 2x x1 1OO5x5x2 2=15=154x4x1 1 =16=162x2x1 1 +2x+2x2 2=12=12A AQQ1 1QQ2 2QQ3 3QQ4 4max S=2xmax S=2x1 1+3x+3x2 2 s.t.s.t.2x2x1 1+2x+2x2 2 12 12 4x 4x1 1 16 16 5x5x2 2 1515 x1,x2 x1,x2 0 0B BC C第61页/共68页本问题解的情况：基础解：点（点（O,A,B,C,QO,A,B,C,Q1 1,Q,Q2 2,Q,Q3 3,Q,Q4 4）可行域：由点（由点（OO，QQ1 1，QQ2 2，QQ3 3，QQ4 4）围）围 成的区域。成的区域。基础可行解：点（点（OO，QQ1 1，QQ2 2，QQ3 3，QQ4 4）最优解：QQ3 3第62页/共68页解的集合：非可行解可可行行解解第63页/共68页解的集合：基基础础解解第64页/共68页解的集合：可可行行解解基基础础解解基基础础可可行行解解第65页/共68页解的集合：可可行行解解基基础础解解基基础础最最优优解解基基础础可可行行解解第66页/共68页课堂练习：P34 1.9第67页/共68页感谢您的观看！第68页/共68页