《运筹学--线性规划（01）》由会员分享，可在线阅读，更多相关《运筹学--线性规划（01）（118页珍藏版）》请在金锄头文库上搜索。
1、第一章 线性规划与单纯形方法,第一节 线性规划问题及数学模型 线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzing）,线性规划（概论） 线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzing） 1951年提出单纯形算法（Simpler）,线性规划（概论） 线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzing） 1951年提出单纯形算法（Simpler） 1963年Dantzing写成“Linear Programming and Ext
2、ension”,线性规划（概论） 线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzing） 1951年提出单纯形算法（Simpler） 1963年Dantzing写成“Linear Programming and Extension” 1979年苏联的Khachian提出“椭球法”,线性规划（概论） 线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzing） 1951年提出单纯形算法（Simpler） 1963年Dantzing写成“Linear Programming and Extensi
3、on” 1979年苏联的Khachian提出“椭球法” 1984年印度的Karmarkar提出“投影梯度法”,线性规划（概论） 线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzing） 1951年提出单纯形算法（Simpler） 1963年Dantzing写成“Linear Programming and Extension” 1979年苏联的Khachian提出“椭球法” 1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。,1 线性规划发展
4、史 线性规划（Linear Programming)创始人： 1947年美国人G.B.丹齐克（Dantzing） 1951年提出单纯形算法（Simpler） 1963年Dantzing写成“Linear Programming and Extension” 1979年苏联的Khachian提出“椭球法” 1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。,2 线性规划基本概念生产计划问题 如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。 如何合理使用有限的人力，物力和资金，以达到最
5、经济的方式，完成生产计划的要求。,例1 生产计划问题（资源利用问题）某家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？,解：将此问题列成图表如下：,将一个实际问题转化为线性规划模型有以下几个步骤：,将一个实际问题转化为线性规划模型有以下几个步骤： 1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量,解：将一个实际问题转化为线性规划模型有
6、以下几个步骤： 1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量 2确定目标函数：家具厂的目标是销售收入最大max z=50x1+30x2,解：将一个实际问题转化为线性规划模型有以下几个步骤： 1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量 2确定目标函数：家具厂的目标是销售收入最大max z=50x1+30x2 3确定约束条件：4x1+3x2 120（木工工时限制）2x1+x2 50 （油漆工工时限制）,解：将一个实际问题转化为线性规划模型有以下几个步骤： 1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量 2确定目标函数：家具厂的目标是销售收入最大max z=50x
7、1+30x2 3确定约束条件：4x1+3x2 120（木工工时限制）2x1+x2 50 （油漆工工时限制） 4变量取值限制：一般情况，决策变量只取正值（非负值）x1 0, x2 0,解：将一个实际问题转化为线性规划模型有以下几个步骤： 1确定决策变量：x1=生产桌子的数量x2=生产椅子的数量 2确定目标函数：家具厂的目标是销售收入最大max z=50x1+30x2 3确定约束条件：4x1+3x2120（木工工时限制）2x1+x2 50 （油漆工工时限制） 4变量取值限制：一般情况，决策变量只取正值（非负值）x1 0, x2 0,数学模型max S=50x1+30x2 s.t. 4x1+3x2
8、1202x1+ x2 50x1,x2 0线性规划数学模型三要素：决策变量、约束条件、目标函数,一、问题的提出,解：,1.决策变量：设产品I、II的产量分别为 x1、x2,2.目标函数：设总运费为z，则有：max z = 2 x1 + 3 x2,3.约束条件：,3 线性规划问题的数学模型,例3 营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？,各种食物的营养成分表,每天需要 3000 55 800,各种食物的营养成分
9、表,每天需要 3000 55 800,X1 X2 x3 x4,解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：min S=14x1+6x2 +3x3+2x4 s.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的元钢各一
10、根组成一套，需100根，每根省下料头0.9m，就浪费了。若改为套裁，可以节约原料。几种套裁方案如下表：,设各种方案下料的根数为xi,i=1,2,3,4,5 其数学模型为： min S=0.3x1+0x2 +0.1x3+0.8x4+0.2x5 (or minS= 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 、B 3，运价表如下，问如何调运使总运费最省？列出数学模型。,解 设Ai调
11、运给Bj的调运量为xij,i=1,2;j=1,2,3 其数学模型为： min S=50x11+60x12 +70x13+60x21+110x22+160x23 s.t. x11+x12 + x13=23x21+x22 + x23=27x11+x21 =17x12+x22 =18x13+x23 =15xij0 , i=1,2;j=1,2,3,其他典型问题： 运输问题,其他典型问题：合理下料问题 运输问题 生产的组织与计划问题,其他典型问题：合理下料问题 运输问题 生产的组织与计划问题 投资证券组合问题,其他典型问题：合理下料问题 运输问题 生产的组织与计划问题 投资证券组合问题 分派问题,其他典
12、型问题：合理下料问题 运输问题 生产的组织与计划问题 投资证券组合问题 分派问题 生产工艺优化问题,用于成功决策的实例： 美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策,用于成功决策的实例： 美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策 美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策,用于成功决策的实例： 美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策 美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策Chessie道路系统关于购买和修理价值40亿美圆货运汽车
13、决策,用于成功决策的实例： 魁北克水利部门关于用哪几个水库来满足每天电力需求决策,用于成功决策的实例： 魁北克水利部门关于用哪几个水库来满足每天电力需求决策 农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策,用于成功决策的实例： 魁北克水利部门关于用哪几个水库来满足每天电力需求决策 农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策 北美长途运输公司关于每周如何调度数千辆货车的决策,用于成功决策的实例： 魁北克水利部门关于用哪几个水库来满足每天电力需求决策 农场信贷系统联邦土地
14、银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策 北美长途运输公司关于每周如何调度数千辆货车的决策 埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策,用于成功决策的实例： 魁北克水利部门关于用哪几个水库来满足每天电力需求决策 农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金（每年共计60亿美圆）来维持发展决策 北美长途运输公司关于每周如何调度数千辆货车的决策 埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策,4 线性规划问题的一般形式： Max(Min)S=c1x1+c2x2+cnxn s.t.
15、 a11x1+a12x2+.+a1nxn (=, )b1a21x1+a22x2+.+a2nxn (=, )b2.am1x1+am2x2+.+amnxn (=, )bmx1,x2,.,xn 0,线性规划问题的标准形式(1)： Max S=c1x1+c2x2+cnxn s.t. a11x1+a12x2+.+a1nxn=b1a21x1+a22x2+.+a2nxn=b2.am1x1+am2x2+.+amnxn=bmx1,x2,.,xn 0 其中：bi 0(i=1,2,.m),线性规划问题的标准形式(2)：,向量形式(3),线性规划标准型的矩阵形式(3)：,x1 0x2 0 C= (c1 ,c2 , ,cn ) X= 0= xn 0,a11 a12 . a1n b1 A= a21 a22 . a2n b = b2 .am1 am2 . amn bn,
