线性规划概论与图解法.ppt

《线性规划概论与图解法.ppt》由会员分享，可在线阅读，更多相关《线性规划概论与图解法.ppt（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第一章第一章 线性规划与单纯形方法线性规划与单纯形方法第一章第一章线性规划与单纯形方法线性规划与单纯形方法1.2 线性规划基本概念线性规划基本概念1.3 线性规划问题的数学模型线性规划问题的数学模型1.4 线性规划问题解的概念线性规划问题解的概念1.1 线性规划（概论）线性规划（概论）线性规划（线性规划（线性规划（线性规划（Linear Programming)Linear Programming)Linear Programming)Linear Programming)创始人：创始人：创始人：创始人：1947194719471947年美国人年美国人年美国人年美国人G.B.G.B.G.B.G

2、.B.丹齐克（丹齐克（丹齐克（丹齐克（DantzigDantzigDantzigDantzig）1.1 线性规划（概论）线性规划（概论）线性规划（概论）线性规划（概论）线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）1951195119511951年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（SimplerSimplerSimplerSimpler）线性规划（概论）线性规划（概论）线性规划（线性规划（Linear

3、 Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）19511951年提出单纯形算法（年提出单纯形算法（SimplerSimpler）1963196319631963年年年年DantzigDantzigDantzigDantzig写成写成写成写成“Linear Programming and“Linear Programming and“Linear Programming and“Linear Programming and Extension”Extension”Ext

4、ension”Extension”线性规划（概论）线性规划（概论）线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）19511951年提出单纯形算法（年提出单纯形算法（SimplerSimpler）19631963年年DantzigDantzig写成写成“Linear Programming and“Linear Programming and Extension”Extension”1979197919791979年苏联的年苏联的年苏联的

5、年苏联的KhachianKhachianKhachianKhachian提出提出提出提出“椭球法椭球法椭球法椭球法”线性规划（概论）线性规划（概论）线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）19511951年提出单纯形算法（年提出单纯形算法（SimplerSimpler）19631963年年DantzigDantzig写成写成“Linear Programming and“Linear Programming and Extensi

6、on”Extension”19791979年苏联的年苏联的KhachianKhachian提出提出“椭球法椭球法”1984198419841984年印度的年印度的年印度的年印度的KarmarkarKarmarkarKarmarkarKarmarkar提出提出提出提出“投影梯度法投影梯度法投影梯度法投影梯度法”线性规划（概论）线性规划（概论）线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzigDantzig）19511951年提出单纯形算法（年提出单纯形算法（

7、SimplerSimpler）19631963年年DantzigDantzig写成写成“Linear Programming and“Linear Programming and Extension”Extension”19791979年苏联的年苏联的KhachianKhachian提出提出“椭球法椭球法”19841984年印度的年印度的KarmarkarKarmarkar提出提出“投影梯度法投影梯度法”线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是

8、线说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。性代数的应用和发展。性代数的应用和发展。性代数的应用和发展。生产计划问题生产计划问题如如何何合合理理使使用用有有限限的的人人力力，物物力力和资金，使得收到最好的经济效益。和资金，使得收到最好的经济效益。如如何何合合理理使使用用有有限限的的人人力力，物物力力和和资资金金，以以达达到到最最经经济济的的方方式式，完完成生产计划的要求。成生产计划的要求。1.2 1.2 线性规划基本概念线性规划基本概念例例1.1 生产计划问题（资源利用问题）生产计划问题（资

9、源利用问题）胜胜利利家家具具厂厂生生产产桌桌子子和和椅椅子子两两种种家家具具。桌桌子子售售价价50元元/个个，椅椅子子销销售售价价格格30元元/个个，生生产产桌桌子子和和椅椅子子要要求求需需要要木木工工和和油油漆漆工工两两种种工工种种。生生产产一一个个桌桌子子需需要要木木工工4小小时时，油油漆漆工工2小小时时。生生产产一一个个椅椅子子需需要要木木工工3小小时时，油油漆漆工工1小小时时。该该厂厂每每个个月月可可用用木木工工工工时时为为120小小时时，油油漆漆工工工工时时为为50小小时时。问问该该厂厂如如何何组组织织生生产产才才能能使每月的销售收入最大？使每月的销售收入最大？解解：将将将将一一一一

10、个个个个实实实实际际际际问问问问题题题题转转转转化化化化为为为为线线线线性性性性规规规规划划划划模模模模型型型型有有有有以以以以下下下下几个步骤：几个步骤：几个步骤：几个步骤：解解：将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以以下下几个步骤：几个步骤：1确定决策变量：确定决策变量：x1=生产桌子的数量生产桌子的数量 x2=生产椅子的数量生产椅子的数量解解：将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以以下下几个步骤：几个步骤：1确定决策变量：确定决策变量：x1=生产桌子的数量生产桌子的数量 x2=生产椅子的数量生产椅子的数量2确定目标函数：确定

11、目标函数：家具厂的目标是销售收入最大家具厂的目标是销售收入最大家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50 x1+30 x2解解：将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以以下下几个步骤：几个步骤：1确定决策变量：确定决策变量：x1=生产桌子的数量生产桌子的数量 x2=生产椅子的数量生产椅子的数量2确定目标函数：确定目标函数：家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件：确定约束条件：4x1+3x2 120（木工工时限制）（木工工时限制）（木工工时限制）（木工工时限制）2x1+x2

12、50 （油漆工工时限制）（油漆工工时限制）（油漆工工时限制）（油漆工工时限制）解解：将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以以下下几个步骤：几个步骤：1确定决策变量：确定决策变量：x1=生产桌子的数量生产桌子的数量 x2=生产椅子的数量生产椅子的数量2确定目标函数：确定目标函数：家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件：确定约束条件：4x1+3x2 120（木工工时限制）（木工工时限制）2x1+x2 50 （油漆工工时限制）（油漆工工时限制）4变量取值限制：变量取值限制：一般情况，决策变量只取正值（非负

13、值）一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）x1 0,x2 0 解解：将将将将一一一一个个个个实实实实际际际际问问问问题题题题转转转转化化化化为为为为线线线线性性性性规规规规划划划划模模模模型型型型有有有有以以以以下下下下几个步骤：几个步骤：几个步骤：几个步骤：1确定决策变量：确定决策变量：x1=生产桌子的数量生产桌子的数量 x2=生产椅子的数量生产椅子的数量2确定目标函数：确定目标函数：家具厂的目标是销售收入最大家具厂的目标是销售收入最大家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50 x1+30 x2

14、3确定约束条件：确定约束条件：4x1+3x2 120（木工工时限制）（木工工时限制）（木工工时限制）（木工工时限制）2x1+x2 50 （油漆工工时限制）（油漆工工时限制）（油漆工工时限制）（油漆工工时限制）4变量取值限制：变量取值限制：一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）x1 0,x2 0 数学模型数学模型 max S=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0线性规划数学模型三要素：线性规划数学模型三要素：决策变量、约束条件、目标函数决

15、策变量、约束条件、目标函数例例1.2 营养配餐问题营养配餐问题 假定一个成年人每天需要从食物中假定一个成年人每天需要从食物中获得获得3000千卡的热量、千卡的热量、55克蛋白质和克蛋白质和800毫克的钙。如果市场上只有四种食品可毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费能在满足营养的前提下使购买食品的费用最小？用最小？1.3 线性规划问题的数学模型线性规划问题的数学模型各种食物的营养成分表解解：设设xj为为第第j种种食食品品每每天天的

16、的购购入入量量，则配餐问题的线性规划模型为：则配餐问题的线性规划模型为：min S=14x1+6x2+3x3+2x4 s.t.1000 x1+800 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其他典型问题：其他典型问题：合理下料问题合理下料问题运输问题运输问题生产的组织与计划问题生产的组织与计划问题投资证券组合问题投资证券组合问题分派问题分派问题生产工艺优化问题生产工艺优化问题线性规划问题的一般形式：线性规划问题的一般形式：Max(Min)S=c1x

17、1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn (=,)b1 a21x1+a22x2+.+a2nxn (=,)b2 .am1x1+am2x2+.+amnxn (=,)bm x1,x2.xn 0线性规划问题隐含的假定：线性规划问题隐含的假定：比例性假定比例性假定可加性假定可加性假定连续性假定连续性假定确定性假定确定性假定线性规划问题隐含的假定：线性规划问题隐含的假定：比例性假定：决策变量变化引起的目标比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约例，同样，每个决策变量的变化引起约束

18、方程左端值的改变量和该变量的改变束方程左端值的改变量和该变量的改变量成比例。量成比例。可加性假定：每个决策变量对目标函数可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数目标函数值是每个决策变量对目标函数贡献的总和。贡献的总和。线性规划问题隐含的假定：线性规划问题隐含的假定：连续性假定：线性规划问题中的决连续性假定：线性规划问题中的决策变量应取连续值。策变量应取连续值。确定性假定：线性规划问题中的所确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划有参数都是确定的参数。线性规划问题不包含随机因素

19、。问题不包含随机因素。线性规划问题的标准形式线性规划问题的标准形式(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)线性规划问题的标准形式线性规划问题的标准形式(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)线性规划标准型的矩阵形式线

20、性规划标准型的矩阵形式(3)（矩阵表达型）：（矩阵表达型）：Max S =CX s.t.AX =b X 0其中：其中：如何将一般问题化为标准型：如何将一般问题化为标准型：1.若目标函数是求最小值若目标函数是求最小值 2.Min S=CX 则则令令 S=-S,变为变为 Max S=-CX2.若约束条件是不等式若约束条件是不等式若约束条件是若约束条件是“”不等式不等式,将原条件变为：将原条件变为：n aijxj+xs=bi j=1 xs 0是新引入的非负松驰变量是新引入的非负松驰变量如何将一般问题化为标准型：如何将一般问题化为标准型：3.若约束条件是若约束条件是“”不等式，则变为不等式，则变为 n

21、 aijxj-xt=bi j=1 X Xt t 0是引入的非负松驰变量是引入的非负松驰变量4.若约束条件右面的某一常数项若约束条件右面的某一常数项 bi0这时只要在这时只要在bi相对应的约束方程两边乘相对应的约束方程两边乘上上-1。如何将一般问题化为标准型：如何将一般问题化为标准型：5.若变量若变量 xj无非负限制，引进两个非负无非负限制，引进两个非负变量变量xj xj”0 令令xj=xj-xj”通过以上步骤，任何形式的线性规通过以上步骤，任何形式的线性规划总可以化成标准型。划总可以化成标准型。例例1.3 将下列问题化成标准型将下列问题化成标准型:Min S =-x1+2x2-3x3s.t.x

22、1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3=5 x1,x2 0 x3 无非负限制无非负限制标准型：标准型：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注：标准型还不一定是便于求解的形式。注：标准型还不一定是便于求解的形式。课堂练习：课堂练习：请阅读请阅读P1 P3 中的例中的例1.1、例、例1.2、例例1.4。之后完成。之后完成P31 1.1(1)(2)(4)；1.2。请独立完成：请独立完成：P34 1.81.4 线性

23、规划问题解的概念线性规划问题解的概念线性规划问题的解：线性规划问题的解：（1）满足约束条件的变量的值，称）满足约束条件的变量的值，称为可行解。为可行解。（2）使目标函数取得最优值的可行）使目标函数取得最优值的可行解，称为最优解。解，称为最优解。线性规划问题图解法：线性规划问题图解法：例例 1.1的数学模型的数学模型 max S=50 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1 x2 0 x2504030201010203040 x14x4x1 1+3x+3x2 2 120 120由由由由 4x 4x1 1+3x+3x2 2 120 120 x x1 1 0 x

24、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 x2504030201010203040 x12x2x1 1+x+x2 2 50 50由由由由 2x 2x1 1+x+x2 2 50 50 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.

25、4x1 1+3x+3x2 2 120 120 2x 2x1 1+x+x2 2 50 50 x x1 1 x x2 2 0 0 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+3x2 2 120 120 2x

26、2x1 1+x+x2 2 50 50 x x1 1 x x2 2 0 0 x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由约束条可行域是由约束条可行域是由约束条可行域是由约束条件围成的区域，该件围成的区域，该件围成的区域，该件围成的区域，该区域内的每一点都区域内的每一点都区域内的每一点都区域内的每一点都是可行解，它的全是可行解，它的全是可行解，它的全是可行解，它的全体组成问题的解集体组成问题的解集体组成问题的解集体组成问题的解集合。合。合。合。该问题的可行域是该问题的可行域是该问题的可行域是该问题的可

27、行域是由由由由OO，QQ1 1，QQ2 2，QQ3 3作为顶点的凸多边作为顶点的凸多边作为顶点的凸多边作为顶点的凸多边形形形形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 x2504030201010203040 x1可行域可行域可行域可行域目标函数是以目标函数是以S作为作为参数的一组平行线参数的一组平行线x2=S/30-（5/3）x1max S=50 xmax S=50 x1 1+30 x+30 x2 2 s.t.4x

28、 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 x2504030201010203040 x1可行域可行域可行域可行域当当S值不断增加时，值不断增加时，该直线该直线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 x2504030201010203040

29、 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+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二个重要结论：二个重要结论：1。满足约束条件的可行域一般。满足约束条

30、件的可行域一般都构成凸多边形。这一事实可都构成凸多边形。这一事实可以推广到更多变量的场合。以推广到更多变量的场合。2。最优解必定能在凸多边形的。最优解必定能在凸多边形的某一个顶点上取得，这一事实某一个顶点上取得，这一事实也可以推广到更多变量的场合。也可以推广到更多变量的场合。解的讨论：解的讨论：最优解是唯一解最优解是唯一解；解的讨论解的讨论：1。最优解是唯一解。最优解是唯一解2。无穷多组最优解：。无穷多组最优解：例例1.1的目标函数由的目标函数由 max S=50 x1+30 x2变成：变成：max S=40 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0

31、 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 x2504030201010203040 x1可行域可行域可行域可行域当当S的值增加时，目的值增加时，目标函数同约束条件：标函数同约束条件：4x1+3x2 120重合，重合，Q1与与Q2之间

32、之间都是最优解。都是最优解。Q1（25，0）Q2（15，20）解的讨论：解的讨论：u最优解是唯一解最优解是唯一解；u无穷多组最优解无穷多组最优解：无界解：无界解：例：例：max S=x1 +x2 s.t.-2x1+x2 40 x1-x2 20 x1 x2 0 x2504030201010203040 x1该可行域无界，该可行域无界，该可行域无界，该可行域无界，目标函数值可增目标函数值可增目标函数值可增目标函数值可增加到无穷大，称加到无穷大，称加到无穷大，称加到无穷大，称这种情况为无界这种情况为无界这种情况为无界这种情况为无界解或无最优解。解或无最优解。解或无最优解。解或无最优解。-2x-2x1

33、 1+x+x2 2 4040 x x1 1-x-x2 2 2020解的讨论：解的讨论：无可行解：无可行解：例：例：max S=2x1+3x2 s.t.x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1,x2 0该问题可行域为空集，该问题可行域为空集，该问题可行域为空集，该问题可行域为空集，即无可行解，也不存即无可行解，也不存即无可行解，也不存即无可行解，也不存在最优解。在最优解。在最优解。在最优解。解的情况：解的情况：1。有可行解。有可行解2。有唯一最优解。有唯一最优解3。有无穷最优解。有无穷最优解4。无最优解。无最优解5。无可行解。无可行解课堂练习：课堂练习：P34 1.7(偶数

34、号偶数号)线性规划问题解的概念线性规划问题解的概念线性规划标准型的矩阵形式：线性规划标准型的矩阵形式：Max S =C X （1-9）s.t.A X=b （1-10）X 0 （1-11）其中其中解、可行解、最优解解、可行解、最优解1。满足约束条件（。满足约束条件（1-10）的）的X，称为称为 线性规划问题的解。线性规划问题的解。2。满足约束条件（满足约束条件（1-10）与（）与（1-11）的的X，称为线性规划称为线性规划的问题可行解的问题可行解。3。使目标函数（使目标函数（1-9）取得最优）取得最优的可行解的可行解X 称为线性规划的问题最优解。称为线性规划的问题最优解。Max S =CX Ma

35、x S =CX （1-91-9）s.t.AX=b s.t.AX=b （1-101-10）X X 0 0 （1-111-11）基、基向量、基变量基、基向量、基变量1。设。设 r(A)=m,并且并且B是是A的的m 阶非奇异阶非奇异 的子矩阵（的子矩阵（det(B)0),则称矩阵则称矩阵 B为线性规划问题的一个为线性规划问题的一个基基。2。设设矩阵矩阵 B=（P1，P2 .Pm)是一个基是一个基，其列向量其列向量 Pj 称为对应基称为对应基B的的基向量基向量。3。与基向量与基向量 Pj 相对应的变量相对应的变量xj就称为就称为 基变量基变量，其余的就称为，其余的就称为非基变量非基变量。基础解基础解.

36、基础可行解基础可行解.可行基可行基1。对于某一特定的基对于某一特定的基B，非基变量取非基变量取 0 值的解，称为基础解。值的解，称为基础解。2。满足非负约束条件的基础解，称满足非负约束条件的基础解，称 为基础可行解。为基础可行解。3。与基础可行解对应的基，称为可与基础可行解对应的基，称为可 行基。行基。为了理解基础解为了理解基础解.基础可行解基础可行解.最优解的最优解的概念，用下列例子说明：概念，用下列例子说明：例例1.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

37、0 （1-14 ）将该问题化为标准形式如下：max S=2x1+3x2 s.t.-2x1+3x2+x3 =6 3x1 -2x2 +x4 =6 x1 +x2 +x5=4 x1,x2,x3,x4,x5 0 其约束条件的系数矩阵为：找出三个向量构成基，其对应的变量为找出三个向量构成基，其对应的变量为基变量，令其他的变量（非基变量）均为零。基变量，令其他的变量（非基变量）均为零。可以解出基变量的值，即为基解。可以解出基变量的值，即为基解。之后，确定这些基解是否是可行解。将之后，确定这些基解是否是可行解。将可行的（基础可行解）代入目标函数，求出可行的（基础可行解）代入目标函数，求出相应的目标函数值。可使

38、目标函数最优的，相应的目标函数值。可使目标函数最优的，就是最优解。在下面的表中，最优解用星号就是最优解。在下面的表中，最优解用星号标出。标出。基基基解基解可行可行？S S标标记记x x1 1x x2 2x x3 3x x4 4x x5 5P P1 1P P2 2P P3 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

39、 P1 1P P4 4P P5 56 60 00 0-8-81515否否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 CP P3 3P P4 4P P5 50 00 01212 1616 1515是是0 0O Ox 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.

40、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本问题解的情况：本问题解的情况：基础解：基础解：点（点（点（点（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解的集合：解的集合：非非可可行行解解可可行行解解解的集合：解的集合：基基础础解解解的集合：解的集合：可可行行解解基基础础解解基基基基础础础础可可可可行行行行解解解解解的集合：解的集合：可可行行解解基基础础解解基基基基础础础础最最最最优优优优解解解解基基基基础础础础可可可可行行行行解解解解课堂练习：课堂练习：P34 1.9