线性规划.ppt

第一章第一章 线性规划与单纯形方法线性规划与单纯形方法.第一节第一节 线性规划问题及数学模型线性规划问题及数学模型线性规划（线性规划（线性规划（线性规划（Linear Programming)Linear Programming)Linear Programming)Linear Programming)创始人：创始人：创始人：创始人：1947194719471947年美国人年美国人年美国人年美国人G.B.G.B.G.B.G.B.丹齐克（丹齐克（丹齐克（丹齐克（DantzingDantzingDantzingDantzing）.线性规划（概论）线性规划（概论）线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzingDantzing）1951195119511951年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（SimplerSimplerSimplerSimpler）.线性规划（概论）线性规划（概论）线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzingDantzing）19511951年提出单纯形算法（年提出单纯形算法（SimplerSimpler）1963196319631963年年年年DantzingDantzingDantzingDantzing写成写成写成写成“Linear Programming and“Linear Programming and“Linear Programming and“Linear Programming and Extension”Extension”Extension”Extension”.线性规划（概论）线性规划（概论）线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzingDantzing）19511951年提出单纯形算法（年提出单纯形算法（SimplerSimpler）19631963年年DantzingDantzing写成写成“Linear Programming and“Linear Programming and Extension”Extension”1979197919791979年苏联的年苏联的年苏联的年苏联的KhachianKhachianKhachianKhachian提出提出提出提出“椭球法椭球法椭球法椭球法”.线性规划（概论）线性规划（概论）线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzingDantzing）19511951年提出单纯形算法（年提出单纯形算法（SimplerSimpler）19631963年年DantzingDantzing写成写成“Linear Programming and“Linear Programming and Extension”Extension”19791979年苏联的年苏联的KhachianKhachian提出提出“椭球法椭球法”1984198419841984年印度的年印度的年印度的年印度的KarmarkarKarmarkarKarmarkarKarmarkar提出提出提出提出“投影梯度法投影梯度法投影梯度法投影梯度法”.线性规划（概论）线性规划（概论）线性规划（线性规划（Linear Programming)Linear Programming)创始人：创始人：19471947年美国人年美国人G.B.G.B.丹齐克（丹齐克（DantzingDantzing）19511951年提出单纯形算法（年提出单纯形算法（SimplerSimpler）19631963年年DantzingDantzing写成写成“Linear Programming and“Linear Programming and Extension”Extension”19791979年苏联的年苏联的KhachianKhachian提出提出“椭球法椭球法”19841984年印度的年印度的KarmarkarKarmarkar提出提出“投影梯度法投影梯度法”线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。性代数的应用和发展。性代数的应用和发展。性代数的应用和发展。.1 1 线性规划发展史线性规划发展史线性规划（线性规划（线性规划（线性规划（Linear Programming)Linear Programming)Linear Programming)Linear Programming)创始人：创始人：创始人：创始人：1947194719471947年美国人年美国人年美国人年美国人G.B.G.B.G.B.G.B.丹齐克（丹齐克（丹齐克（丹齐克（DantzingDantzingDantzingDantzing）1951195119511951年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（年提出单纯形算法（SimplerSimplerSimplerSimpler）1963196319631963年年年年DantzingDantzingDantzingDantzing写成写成写成写成“Linear Programming and“Linear Programming and“Linear Programming and“Linear Programming and Extension”Extension”Extension”Extension”1979197919791979年苏联的年苏联的年苏联的年苏联的KhachianKhachianKhachianKhachian提出提出提出提出“椭球法椭球法椭球法椭球法”1984198419841984年印度的年印度的年印度的年印度的KarmarkarKarmarkarKarmarkarKarmarkar提出提出提出提出“投影梯度法投影梯度法投影梯度法投影梯度法”线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。性代数的应用和发展。性代数的应用和发展。性代数的应用和发展。.2 2 线性规划基本概念线性规划基本概念生产计划问题生产计划问题如如何何合合理理使使用用有有限限的的人人力力，物物力力和资金，使得收到最好的经济效益。和资金，使得收到最好的经济效益。如如何何合合理理使使用用有有限限的的人人力力，物物力力和和资资金金，以以达达到到最最经经济济的的方方式式，完完成生产计划的要求。成生产计划的要求。.例例1 生产计划问题（资源利用问题）生产计划问题（资源利用问题）某某家家具具厂厂生生产产桌桌子子和和椅椅子子两两种种家家具具。桌桌子子售售价价50元元/个个，椅椅子子销销售售价价格格30元元/个个，生生产产桌桌子子和和椅椅子子要要求求需需要要木木工工和和油油漆漆工工两两种种工工种种。生生产产一一个个桌桌子子需需要要木木工工4小小时时，油油漆漆工工2小小时时。生生产产一一个个椅椅子子需需要要木木工工3小小时时，油油漆漆工工1小小时时。该该厂厂每每个个月月可可用用木木工工工工时时为为120小小时时，油油漆漆工工工工时时为为50小小时时。问问该该厂厂如如何何组组织织生生产产才才能能使使每每月月的的销销售售收入最大？收入最大？.桌子桌子桌子桌子椅子椅子椅子椅子总工时总工时总工时总工时（小时）（小时）（小时）（小时）木工木工木工木工（小时）（小时）（小时）（小时）4 43 3120120油漆工油漆工油漆工油漆工2 21 15050价格价格价格价格（元（元（元（元/个）个）个）个）50503030解：解：将此问题列成图表如下：将此问题列成图表如下：将此问题列成图表如下：将此问题列成图表如下：.将将将将一一一一个个个个实实实实际际际际问问问问题题题题转转转转化化化化为为为为线线线线性性性性规规规规划划划划模模模模型型型型有有有有以以以以下下下下几几几几个步骤：个步骤：个步骤：个步骤：.将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以以下下几几个步骤：个步骤：1确定决策变量：确定决策变量：x1=生产桌子的数量生产桌子的数量 x2=生产椅子的数量生产椅子的数量.解解：将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以以下下几个步骤：几个步骤：1确定决策变量：确定决策变量：x1=生产桌子的数量生产桌子的数量 x2=生产椅子的数量生产椅子的数量2确定目标函数：确定目标函数：家具厂的目标是销售收入最大家具厂的目标是销售收入最大家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50 x1+30 x2.解解：将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以以下下几个步骤：几个步骤：1确定决策变量：确定决策变量：x1=生产桌子的数量生产桌子的数量 x2=生产椅子的数量生产椅子的数量2确定目标函数：确定目标函数：家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件：确定约束条件：4x1+3x2 120（木工工时限制）（木工工时限制）（木工工时限制）（木工工时限制）2x1+x2 50 （油漆工工时限制）（油漆工工时限制）（油漆工工时限制）（油漆工工时限制）.解解：将将一一个个实实际际问问题题转转化化为为线线性性规规划划模模型型有有以以下下几个步骤：几个步骤：1确定决策变量：确定决策变量：x1=生产桌子的数量生产桌子的数量 x2=生产椅子的数量生产椅子的数量2确定目标函数：确定目标函数：家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件：确定约束条件：4x1+3x2 120（木工工时限制）（木工工时限制）2x1+x2 50 （油漆工工时限制）（油漆工工时限制）4变量取值限制：变量取值限制：一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）一般情况，决策变量只取正值（非负值）x1 0,x2 0 .解解：将将将将一一一一个个个个实实实实际际际际问问问问题题题题转转转转化化化化为为为为线线线线性性性性规规规规划划划划模模模模型型型型有有有有以以以以下下下下几个步骤：几个步骤：几个步骤：几个步骤：1确定决策变量：确定决策变量：x1=生产桌子的数量生产桌子的数量 x2=生产椅子的数量生产椅子的数量2确定目标函数：确定目标函数：家具厂的目标是销售收入最大家具厂的目标是销售收入最大家具厂的目标是销售收入最大家具厂的目标是销售收入最大 max z=50 x1+30 x23确定约束条件：确定约束条件：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线性规划数学模型三要素：线性规划数学模型三要素：决策变量、约束条件、目标函数决策变量、约束条件、目标函数.一、问题的提出一、问题的提出例例例例2 2 某厂生产两种产品，下表给某厂生产两种产品，下表给某厂生产两种产品，下表给某厂生产两种产品，下表给出了单位产品所需资源及单位产品出了单位产品所需资源及单位产品出了单位产品所需资源及单位产品出了单位产品所需资源及单位产品利润利润利润利润 问：应如何安排生产计划，才能使问：应如何安排生产计划，才能使问：应如何安排生产计划，才能使问：应如何安排生产计划，才能使 总利润最大？总利润最大？总利润最大？总利润最大？解：解：解：解：1.1.决策变量：设产品决策变量：设产品决策变量：设产品决策变量：设产品I I、IIII的产量分的产量分的产量分的产量分 别为别为别为别为 x x1 1、x x2 22.2.目标函数：设总运费为目标函数：设总运费为目标函数：设总运费为目标函数：设总运费为z z，则有：，则有：，则有：，则有：max z=2 max z=2 x x1 1+3 +3 x x2 23.3.约束条件：约束条件：约束条件：约束条件：x1+2x2 8 4x1 16 4x2 12 x1，x203 线性规划问题的数学模型.例例3 营养配餐问题营养配餐问题 假定一个成年人每天需要从食物中假定一个成年人每天需要从食物中获得获得3000千卡的热量、千卡的热量、55克蛋白质和克蛋白质和800毫克的钙。如果市场上只有四种食毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购何选择才能在满足营养的前提下使购买食品的费用最小？买食品的费用最小？.各种食物的营养成分表每天需要每天需要每天需要每天需要 3000 55 800 .各种食物的营养成分表每天需要每天需要每天需要每天需要 3000 55 800 X1X2x3x4.解解：设设xj为为第第j种种食食品品每每天天的的购购入入量量，则配餐问题的线性规划模型为：则配餐问题的线性规划模型为：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.例例4合理下料问题合理下料问题 现做现做100套钢架，每套用长为套钢架，每套用长为2.9m,2.1m和和1.5m的原钢各一根。已知原料长为的原钢各一根。已知原料长为7.4m，问，问应如何下料，使用的原料最省。应如何下料，使用的原料最省。解：解：最简单的方法是在每根原料上截取最简单的方法是在每根原料上截取最简单的方法是在每根原料上截取最简单的方法是在每根原料上截取2.9m,2.1m,1.5m2.9m,2.1m,1.5m的元钢各一根组成一套，需的元钢各一根组成一套，需的元钢各一根组成一套，需的元钢各一根组成一套，需100100根，每根省下料头根，每根省下料头根，每根省下料头根，每根省下料头0.9m0.9m，就浪费了。若改为套裁，可以节约原料。几种套裁方案如就浪费了。若改为套裁，可以节约原料。几种套裁方案如就浪费了。若改为套裁，可以节约原料。几种套裁方案如就浪费了。若改为套裁，可以节约原料。几种套裁方案如下表：下表：下表：下表：.下料下料下料下料 方案方案方案方案 数（根）数（根）数（根）数（根）长度长度长度长度 2.9 2.9 2.1 2.1 1.5 1.5 1 1 2 2 0 0 1 1 0 0 3 3 2 2 0 0 1 1 0 0 1 1 3 3 0 0 2 2 2 2 合计合计合计合计（m)m)料头料头料头料头(m)(m)7.1 7.1 0.3 0.3 7.4 7.4 0 07.3 7.3 0.10.1 6.6 6.6 0.8 0.87.27.20.20.2.设各种方案下料的根数为设各种方案下料的根数为设各种方案下料的根数为设各种方案下料的根数为xi,i=1,2,3,4,5其数学模型为：其数学模型为：min S=0.3x1+0 x2+0.1x3+0.8x4+0.2x5(or minS=x1+x2+x3+x4+x5)s.t.x1+2x2+2x3=100 2x1+x4 +2x5=100 3x1+x3+3x4+2x5=100 x1，x2，x3，x4，x5 0.例例5 运输问题运输问题 设有两砖厂设有两砖厂A1、A2 分别供应三个工地分别供应三个工地B1、B2、B 3，运价表如下，问如何调运使总运，运价表如下，问如何调运使总运费最省？列出数学模型。费最省？列出数学模型。工地工地工地工地运价运价运价运价（元（元（元（元/万块）万块）万块）万块）砖厂砖厂砖厂砖厂B1 B2 B B3 产量产量产量产量（万块）万块）万块）万块）A1 50 50 60 60 70 70 2 3 2 3 A260 60 110 110160160 27 27销量销量(万块）万块）万块）万块）17 17 18 181515 50 50.解解 设设设设Ai调运给调运给Bj的调运量为的调运量为的调运量为的调运量为x xij ij,i=1,2;j=1,2,3,i=1,2;j=1,2,3其数学模型为：其数学模型为：min S=50 xmin S=50 x1111+60 x+60 x12 12+70 x+70 x1313+60 x+60 x2121+110 x+110 x2222+160 x+160 x2323 s.t.xs.t.x1111+x+x12 12+x+x1313=23=23 x x2121+x+x22 22+x+x2323=27=27 x x1111+x+x21 21=17=17 x x1212+x+x22 22=18=18 x x1313+x+x23 23=15=15 x xij ij0,i=1,2;j=1,2,30,i=1,2;j=1,2,3 工地工地工地工地 运价运价运价运价砖厂砖厂砖厂砖厂B B1 1 B B2 2 B B3 3产量产量产量产量（万（万（万（万块）块）块）块）A A1 1 50 50 60 60 70 70 2 3 2 3 A A2 260 60 110 110160160 27 27销量销量销量销量 17 17 18 181515 50 50.其他典型问题：其他典型问题：运输问题运输问题.其他典型问题：其他典型问题：合理下料问题合理下料问题运输问题运输问题生产的组织与计划问题生产的组织与计划问题.其他典型问题：其他典型问题：合理下料问题合理下料问题运输问题运输问题生产的组织与计划问题生产的组织与计划问题投资证券组合问题投资证券组合问题.其他典型问题：其他典型问题：合理下料问题合理下料问题运输问题运输问题生产的组织与计划问题生产的组织与计划问题投资证券组合问题投资证券组合问题分派问题分派问题.其他典型问题：其他典型问题：合理下料问题合理下料问题运输问题运输问题生产的组织与计划问题生产的组织与计划问题投资证券组合问题投资证券组合问题分派问题分派问题生产工艺优化问题生产工艺优化问题.用于成功决策的实例：用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决班和哪些机组人员被安排于哪架飞机的决策策.用于成功决策的实例：用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决班和哪些机组人员被安排于哪架飞机的决策策美国国防部关于如何从现有的一些基地美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资向海湾运送海湾战争所需要的人员和物资的决策的决策.用于成功决策的实例：用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决班和哪些机组人员被安排于哪架飞机的决策策美国国防部关于如何从现有的一些基地美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资向海湾运送海湾战争所需要的人员和物资的决策的决策 Chessie道路系统关于购买和修理价值道路系统关于购买和修理价值40亿美圆货运汽车决策亿美圆货运汽车决策.用于成功决策的实例：用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每魁北克水利部门关于用哪几个水库来满足每天电力需求决策天电力需求决策.用于成功决策的实例：用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每魁北克水利部门关于用哪几个水库来满足每天电力需求决策天电力需求决策农场信贷系统联邦土地银行关于如何支付到农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年期债券和应发售多少新债券以获取资金（每年共计共计60亿美圆）来维持发展决策亿美圆）来维持发展决策.用于成功决策的实例：用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每魁北克水利部门关于用哪几个水库来满足每天电力需求决策天电力需求决策农场信贷系统联邦土地银行关于如何支付到农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年期债券和应发售多少新债券以获取资金（每年共计共计60亿美圆）来维持发展决策亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆北美长途运输公司关于每周如何调度数千辆货车的决策货车的决策.用于成功决策的实例：用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每魁北克水利部门关于用哪几个水库来满足每天电力需求决策天电力需求决策农场信贷系统联邦土地银行关于如何支付到农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年期债券和应发售多少新债券以获取资金（每年共计共计60亿美圆）来维持发展决策亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆北美长途运输公司关于每周如何调度数千辆货车的决策货车的决策埃克森炼油厂关于调节冶炼能力去适应关于埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策无铅燃料生产的法律更改的决策.用于成功决策的实例：用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每魁北克水利部门关于用哪几个水库来满足每天电力需求决策天电力需求决策农场信贷系统联邦土地银行关于如何支付到农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年期债券和应发售多少新债券以获取资金（每年共计共计60亿美圆）来维持发展决策亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆北美长途运输公司关于每周如何调度数千辆货车的决策货车的决策埃克森炼油厂关于调节冶炼能力去适应关于埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策无铅燃料生产的法律更改的决策.4 4 线性规划问题的一般形式：线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+.+cnxns.t.a11x1+a12x2+.+a1nxn (=,)b1 a21x1+a22x2+.+a2nxn (=,)b2 .am1x1+am2x2+.+amnxn (=,)bm x1,x2,.,xn 0.线性规划问题的标准形式线性规划问题的标准形式线性规划问题的标准形式线性规划问题的标准形式(1)(1)：Max S=cMax S=c1 1x x1 1+c+c2 2x x2 2+.+c+.+cn nx xn ns.t.as.t.a1111x x1 1+a+a1212x x2 2+.+a+.+a1n1nx xn n=b=b1 1 a a2121x x1 1+a+a2222x x2 2+.+a+.+a2n2nx xn n=b=b2 2 .a am1m1x x1 1+a+am2m2x x2 2+.+a+.+amnmnx xn n=b=bmm x x1,1,x x2 2,.,x,.,xn n 0 0其中：其中：其中：其中：b bi i 0(i=1,2,.m)0(i=1,2,.m)线性规划问题的标准形式线性规划问题的标准形式线性规划问题的标准形式线性规划问题的标准形式(2)(2)：向量形式向量形式向量形式向量形式(3)(3).线性规划标准型的矩阵形式线性规划标准型的矩阵形式(3)：x x1 1 0 0 x x2 2 0 0C=(cC=(c1 1,c,c2 2,c,cn n )X=0=)X=0=.x xn n 0 0 a a11 11 a a1212 .a .a1n 1n b b1 1 A=a a21 21 a a2222 .a .a2n 2n b =b b2 2 .a am1 m1 a am2m2 .a .amn mn b bn n.如何将一般问题化为标准型：如何将一般问题化为标准型：若目标函数是求最小值若目标函数是求最小值 Min S=CX 令令 S=-S,则则 Max S=-CX.如何将一般问题化为标准型：如何将一般问题化为标准型：若目标函数是求最小值若目标函数是求最小值 Min S=CX 令令 S=-S,则则 Max S=-CX若约束条件是不等式若约束条件是不等式.如何将一般问题化为标准型：如何将一般问题化为标准型：若目标函数是求最小值若目标函数是求最小值 Min S=CX 令令 S=-S,则则 Max S=-CX若约束条件是不等式若约束条件是不等式若约束条件是若约束条件是“”不等式不等式 n n aijxj+yi=bi j=1 yi 0是非负的是非负的松驰变量松驰变量.如何将一般问题化为标准型：如何将一般问题化为标准型：若约束条件是若约束条件是“”不等式不等式 n aijxj-zi =bi j=1 zi 0是非负的松驰变量是非负的松驰变量.如何将一般问题化为标准型：如何将一般问题化为标准型：若约束条件右面的某一常数项若约束条件右面的某一常数项 bi0这时只要在这时只要在bi相相对应的约束方程两边乘对应的约束方程两边乘上上-1。.如何将一般问题化为标准型：如何将一般问题化为标准型：若约束条件右面的某一常数项若约束条件右面的某一常数项 bi0这时只要在这时只要在bi相相对应的约束方程两边乘对应的约束方程两边乘上上-1。若变量若变量 xj无非负限制无非负限制引进两个非负变量引进两个非负变量xj xj”0 令令xj=xj-xj”.如何将一般问题化为标准型：如何将一般问题化为标准型：若约束条件右面的某一常数项若约束条件右面的某一常数项 bi=0 令令xj=xj-xj”（可正可负）可正可负）任何形式的线性规划总可以化成标准型任何形式的线性规划总可以化成标准型.例例6 将下列问题化成标准型将下列问题化成标准型:Min S =-x1+2x2-3x3s.t.x1+x2+x3 7 x1-x2+x3 2 -3x1+x2+2x3=5 x1,x2 0 x3 无非负限制无非负限制.Max S =x1-2x2+3x3-3x3”s.t.x1+x2+x3-x3”+x4 =7 x1-x2+x3-x3”-x5=2 -3x1+x2+2x3-2x3”=5 x1,x2,x3,x3”,x4,x5 0例例例例6 6 将下列问题化成标准型将下列问题化成标准型将下列问题化成标准型将下列问题化成标准型:Min S =-xMin S =-x1 1+2x+2x2 2-3x-3x3 3s.t.xs.t.x1 1+x+x2 2+x+x3 3 7 7 x x1 1-x-x2 2+x+x3 3 2 2 -3x -3x1 1+x+x2 2+2x+2x3 3=5=5 x x1 1,x,x2 2 0 x 0 x3 3 无非负限制无非负限制无非负限制无非负限制.（二维）线性规划问题图解法：（二维）线性规划问题图解法：（1）满足约束条件的变量的值，称）满足约束条件的变量的值，称为可行解。为可行解。.（二维）线性规划问题图解法：（二维）线性规划问题图解法：（1）满足约束条件的变量的值，称）满足约束条件的变量的值，称为可行解。为可行解。（2）使目标函数取得最优值的可行）使目标函数取得最优值的可行解，称为最优解。解，称为最优解。.（二维）线性规划问题图解法：（二维）线性规划问题图解法：（1）满足约束条件的变量的值，称为可）满足约束条件的变量的值，称为可行解。行解。（2）使目标函数取得最优值的可行解，）使目标函数取得最优值的可行解，称为最优解。称为最优解。例例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 0 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围成的区域围成的区域围成的区域围成的区域.x2504030201010203040 x12x1+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的区域的区域的区域的区域可行域可行域.x2504030201010203040 x1可行域可行域可行域可行域O（0，0）Q1（25，0）Q2（15，20）Q3（0，40）可行域是由约束条件围成可行域是由约束条件围成可行域是由约束条件围成可行域是由约束条件围成的区域，该区域内的每一的区域，该区域内的每一的区域，该区域内的每一的区域，该区域内的每一点都是可行解，它的全体点都是可行解，它的全体点都是可行解，它的全体点都是可行解，它的全体组成问题的解集合。组成问题的解集合。组成问题的解集合。组成问题的解集合。该问题的可行域是由该问题的可行域是由该问题的可行域是由该问题的可行域是由OO，QQ1 1，QQ2 2，QQ3 3作为顶点的作为顶点的作为顶点的作为顶点的凸多边形凸多边形.x2504030201010203040 x1可行域可行域可行域可行域目标函数是以目标函数是以S作为作为参数的一组平行线参数的一组平行线S=50 x1+30 x2x2=S/30-（5/3）x1-2-5/3-4/3.x2504030201010203040 x1可行域可行域可行域可行域当当S值不断增加时，该直线值不断增加时，该直线x2=S/30-（5/3）x1沿着其法线方向向右上方移沿着其法线方向向右上方移动。动。.x2504030201010203040 x1可行域可行域可行域可行域当该直线移到当该直线移到当该直线移到当该直线移到QQ2 2点时，点时，点时，点时，S S（目标函（目标函（目标函（目标函数）值达到最大：数）值达到最大：数）值达到最大：数）值达到最大：Max S=50*15+30*20=1350此时最优解此时最优解=（15，20）Q2（15，20）.二个重要结论：二个重要结论：满足约束条件的可行域一般都满足约束条件的可行域一般都构成凸多边形。这一事实可以构成凸多边形。这一事实可以推广到更多变量的场合。推广到更多变量的场合。.二个重要结论：二个重要结论：满足约束条件的可行域一般都满足约束条件的可行域一般都构成凸多边形。这一事实可以构成凸多边形。这一事实可以推广到更多变量的场合。推广到更多变量的场合。最优解必定能在凸多边形的某最优解必定能在凸多边形的某一个顶点上取得，这一事实也一个顶点上取得，这一事实也可以推广到更多变量的场合。可以推广到更多变量的场合。.解的讨论：解的讨论：最优解是唯一解最优解是唯一解；.解的讨论：解的讨论：最优解是唯一解最优解是唯一解；无穷多组最优解：无穷多组最优解：例例1的目标函数由的目标函数由 max S=50 x1+30 x2变成：变成：max S=40 x1+30 x2 s.t.4x1+3x2 120 2x1+x2 50 x1,x2 0例例例例1 max S=50 x1 max 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可行域可行域可行域可行域目标函数是同约束目标函数是同约束条件：条件：4x1+3x2 120平行的直线平行的直线x2=S/30-（4/3）x1.x2504030201010203040 x1可行域可行域可行域可行域当当S的值增加时，目的值增加时，目标函数同约束条件：标函数同约束条件：4x1+3x2 120重合，重合，Q1与与Q2之间之间都是最优解。都是最优解。Q1（0，40）Q2（15，20）.解的讨论：解的讨论：无界解：无界解：例：例：max S=x1+x2 s.t.-2x1+x2 40 x1-x2 20 x1,x2 0.x2504030201010203040 x1该可行域无界，目标函该可行域无界，目标函数值可增加到无穷大，数值可增加到无穷大，称这种情况为无界解或称这种情况为无界解或无最优解。无最优解。-2x1+x2 40 x1-x2 20.解的讨论：解的讨论：无可行解：无可行解：例：例：max S=2x1+3x2 s.t.x1+2x2 8 x1 4 x2 3 -2x1+x2 4 x1,x2 0该问题可行域为该问题可行域为空集，即无可行空集，即无可行解，也不存在最解，也不存在最优解。优解。.解的情况：解的情况：有可行解有可行解 有唯一最优解有唯一最优解 有无穷最优解有无穷最优解 无界解无界解(无无最最优解）优解）无可行解无可行解.线性规划问题解的概念线性规划问题解的概念线性规划标准型的矩阵形式：线性规划标准型的矩阵形式：Max S =CX （1-9）s.t.AX=b （1-10）X 0 （1-11）.a a11 11 a a1212 .a .a1n 1n b b1 1 A=a a21 21 a a2222 .a .a2n 2n b =b b2 2 a am1 m1 a am2m2 .a .amn mn b bn n c c1 1 x x1 1 0 0 c c2 2 x x2 2 0 0C=X=0=C=X=0=.c cn n x xn n 0 0.线性规划问题的数学模型：线性规划问题的数学模型：一般式，标准型。一般式，标准型。线性规划问题的图解法（二维）线性规划问题的图解法（二维）线性规划标准型的矩阵形式：线性规划标准型的矩阵形式：线性规划标准型的矩阵形式：线性规划标准型的矩阵形式：Max S =CXMax S =CX s.t.AX=b s.t.AX=b X X 0 0.线性规划问题的解线性规划问题的解解、可行解、最优解解、可行解、最优解满足约束条件（满足约束条件（1-10）的）的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）.解、可行解、最优解解、可行解、最优解 满足约束条件（满足约束条件（1-10）的）的X，称为称为 线性规划问题的解。线性规划问题的解。满足约束条件（满足约束条件（1-10）与（）与（1-11）的的X，称为线性规划的问题可行解称为线性规划的问题可行解。.解、可行解、最优解解