第一章 线性规划与单纯形方法

第一章线性规划与单纯形方法第一节线性规划问题及数学模型线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。1线性规划发展史线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。2线性规划基本概念生产计划问题如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。例1生产计划问题（资源利用问题）某家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？桌子椅子总工时（小时）木工（小时）43120油漆工2150价格（元/个）5030解：将此问题列成图表如下：将一个实际问题转化为线性规划模型有以下几个步骤：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大maxz=50x1+30x2解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大maxz=50x1+30x23．确定约束条件：4x1+3x2120（木工工时限制）2x1+x250（油漆工工时限制）解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大maxz=50x1+30x23．确定约束条件：4x1+3x2120（木工工时限制）2x1+x250（油漆工工时限制）4．变量取值限制：一般情况，决策变量只取正值（非负值）x10,x20解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大maxz=50x1+30x23．确定约束条件：4x1+3x2120（木工工时限制）2x1+x250（油漆工工时限制）4．变量取值限制：一般情况，决策变量只取正值（非负值）x10,x20数学模型maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20线性规划数学模型三要素：决策变量、约束条件、目标函数一、问题的提出产品资源III可利用资源设备128材料A4016材料B0412单位利润（元）23例2某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润问：应如何安排生产计划，才能使总利润最大？解：1.决策变量：设产品I、II的产量分别为x1、x22.目标函数：设总运费为z，则有：maxz=2x1+3x23.约束条件：x1+2x2≤84x1≤164x2≤12x1，x2≥03线性规划问题的数学模型例3营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？序号食品名称热量（千卡）蛋白质（克）钙（毫克）价格(元/kg）1猪肉100050400142鸡蛋8006020063大米9002030034白菜200105002各种食物的营养成分表每天需要300055800序号食品名称热量（千卡）蛋白质（克）钙（毫克）价格(元/kg）1猪肉100050400142鸡蛋8006020063大米9002030034白菜200105002各种食物的营养成分表每天需要300055800X1X2x3x4解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：minS=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，x3，x40例4合理下料问题现做100套钢架，每套用长为2.9m,2.1m和1.5m的原钢各一根。已知原料长为7.4m，问应如何下料，使用的原料最省。解：最简单的方法是在每根原料上截取2.9m,2.1m,1.5m的元钢各一根组成一套，需100根，每根省下料头0.9m，就浪费了。若改为套裁，可以节约原料。几种套裁方案如下表：下料方案数（根）长度ⅠⅡⅢⅣⅤ2.92.11.5120103201013022合计（m)料头(m)7.10.37.407.30.16.60.87.20.2设各种方案下料的根数为xi,i=1,2,3,4,5其数学模型为：minS=0.3x1+0x2+0.1x3+0.8x4+0.2x5(orminS=x1+x2+x3+x4+x5)s.t.x1+2x2+2x3=1002x1+x4+2x5=1003x1+x3+3x4+2x5=100x1，x2，x3，x4，x50例5运输问题设有两砖厂A1、A2分别供应三个工地B1、B2、B3，运价表如下，问如何调运使总运费最省？列出数学模型。工地运价（元/万块）砖厂B1B2B3产量（万块）A150607023A26011016027销量(万块）17181550解设Ai调运给Bj的调运量为xij,i=1,2;j=1,2,3其数学模型为：minS=50x11+60x12+70x13+60x21+110x22+160x23s.t.x11+x12+x13=23x21+x22+x23=27x11+x21=17x12+x22=18x13+x23=15xij≥0,i=1,2;j=1,2,3工地运价砖厂B1B2B3产量（万块）A150607023A26011016027销量17181550其他典型问题：•运输问题其他典型问题：•合理下料问题•运输问题•生产的组织与计划问题其他典型问题：•合理下料问题•运输问题•生产的组织与计划问题•投资证券组合问题其他典型问题：•合理下料问题•运输问题•生产的组织与计划问题•投资证券组合问题•分派问题其他典型问题：•合理下料问题•运输问题•生产的组织与计划问题•投资证券组合问题•分派问题•生产工艺优化问题用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策用于成功决策的实例：美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策Chessie道路系统关于购买和修理价值40亿美圆货运汽车决策用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策用于成功决策的实例：魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策4线性规划问题的一般形式：Max(Min)S=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn(=,)b1a21x1+a22x2+….+a2nxn(=,)b2………………….am1x1+am2x2+….+amnxn(=,)bmx1,x2,….,xn0线性规划问题的标准形式(1)：MaxS=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn=b1a21x1+a22x2+….+a2nxn=b2………………….am1x1+am2x2+….+amnxn=bmx1,x2,….,xn0其中：bi0(i=1,2,….m)njxmibxatsxcMaxZjnjijijnjjj,,2,1,0,,2,111线性规划问题的标准形式(2)：njxbxPxczjmjjjnjjj,,2,1,0max11向量形式(3)线性规划标准型的矩阵形式(3)：x10x20C=(c1,c2,…,cn)X=0=………..xn0a11a12….a1nb1A=a21a22….a2nb=b2…………………………………….am1am2….amnbn0