数学建模--线性规划

第一部分线性规划（LinearProgramming)线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。线性规划是指如何最有效或最佳地谋划经济活动。它所研究的问题有两类：一类是指一定资源的条件下，达到最高产量、最高产值、最大利润；一类是任务量一定，如何统筹安排，以最小的消耗去完成这项任务。如最低成本问题、最小投资、最短时间、最短距离等问题。前者是求极大值问题，后者是求极小值问题。总之，线性规划是一定限制条件下，求目标函数极值的问题。线性规划（LP）的概念线性规划基本概念生产计划问题如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。1生产计划问题（资源利用问题）胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？解：将一个实际问题转化为线性规划模型有以下几个步骤：解：将一个实际问题转化为线性规划模型有以下几个步骤：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线性规划数学模型三要素：决策变量、约束条件、目标函数线性规划的数学模型由决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints构成。称为三个要素。其特征是：1．解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；2．解决问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？2营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？序号食品名称热量（千卡）蛋白质（克）钙（毫克）价格（元）1猪肉100050400142鸡蛋8006020063大米9002030034白菜200105002各种食物的营养成分表解：设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其他典型问题：•合理下料问题其他典型问题：•合理下料问题•运输问题其他典型问题：•合理下料问题•运输问题•生产的组织与计划问题其他典型问题：•合理下料问题•运输问题•生产的组织与计划问题•投资证券组合问题其他典型问题：•合理下料问题•运输问题•生产的组织与计划问题•投资证券组合问题•分派问题其他典型问题：•合理下料问题•运输问题•生产的组织与计划问题•投资证券组合问题•分派问题•生产工艺优化问题小结：建立线性规划数学模型建立数学模型是学习线性规划的第一步也是关键的一步。建立正确的数学模型要掌握3个要素：研究的问题是求什么，即设置决策变量；问题要达到的目标是什么，即建立目标函数，目标函数一定是决策变量的线性函数并且求最大值或求最小值；限制达到目标的条件是什么，即建立约束条件。max(或min)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nx1n≤(或=,≥)b1..tsa21x1+a22x2+…+a2nx1n≤(或=,≥)b2...am1x1+am2x2+…+amnx1n≤(或=,≥)bmx1,x2,…,xn≥0线性规划问题的一般形式非负约束条件约束约束条件目标函数max(或min)z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nx1n≤(或=,≥)b1..tsa21x1+a22x2+…+a2nx1n≤(或=,≥)b2...am1x1+am2x2+…+amnx1n≤(或=,≥)bmx1,x2,…,xn≥0njjjxcz1min)(max或),,1(0),,1(),(..1njxmibxctsjnjijji或简写形式),,,(21ncccCXCZmin)(max或0),(..1XbxPtsnjjj或,21nxxxX,21jnjjjaaaPmbbbb21LP向量形式)3,2(C21)3,2(maxxxZ1212221240160515..00xxstxx,21xxX,0421P151612bLP向量形式,5022P0021xx21)3,2(maxxxZ15161250042221xxLP矩阵形式0XXCzmaxbXA21xxX500422A151612b)3,2(C系数矩阵资源向量决策向量价值向量nmmmnnaaaaaaaaaA212221212111),,,(21ncccCnxxxX21mbbbb21松弛变量maxZ=2x1+3x2+0x3+0x4+0x5决策变量4x1+x4=165x2+x5=15..tsx1,x2,x3,x4,x5≥02x1+2x2+x3=12使不等式成为等式的非负变量松弛变量目标函数为收益最大,njjjxcZ11(1,,)nijjijaxbimLP问题的标准形式njjjxcZ11(1,,)..0(1,,)nijjijjaxbimstxjnminmax目标函数为求支出最小,求最大目标函数为LP的标准形式（规定）因为它们可以很方便地相互转换如利润最大如成本最小(,,),01负ibimb非),,1(0njxj1目标函数为求得最大2约束条件全为等式3线性规划标准型的矩阵形式(3)：MaxS=CXs.t.AX=bX02.约束方程右端项bi≤0两端同乘-1左端加减松弛变量1.目标函数为求最小值,njjjxcZ1max1(1,,)..0(1,,)nijjijjaxbimstxjnnjjjxcZ1minZZ'njjjxcZ1'max3.约束条件为不等式4.变量取值无约束5x2≤156x1+2x2≥24+x3=15-x4=24令x=x’-x’’,x’≥0,x’’≥05.变量x≤0令x’=-x转化为LP问题的标准形式的措施minZ=x1+2x2+3x3-2x1+x2+x3≤9-3x1+x2+2x3≥43x1-2x2-3x3=-6..tsx1≤0,x2≥0,x3无约束例a(2)max-1×Z=-1×(x1+2x2+3x3)无约束-1×Z令x3=x3’–x3’’且x3’,x3’’≥0(x3’–x3’’)+x4=(x3’–x3’’)-x5=(x3’–x3’’)x3’,x3’’≥0maxZ’=x1’-2x2-3x3’+3x3’+0x4+0x5x1’=–x1’’’++’≥松驰变量x4,x5=+练习1将下列问题化成标准型:MinS=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20x3无非负限制MaxS=x1-2x2+3x3’-3x3”s.t.x1+x2+x3’-x3”+x4=7x1-x2+x3’-x3”-x5=2-3x1+x2+2x3’-2x3”=5x1,x2,x3’,x3”,x4,x501.都有一组未知变量(x1,x2,…,xn)代表某一线性规划问题的数学模型特点2.都有一个目标要求,实现极大或极小.目标函3.未知变量受到一组约束条件的限制,这些约方案,它们取不同非负值,代表不同的具体方案.数用未知变量的线性函数表示.束条件用一组线性等式或不等式表示.线性规划问题隐含的假定：•比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。线性规划问题隐含的假定：•比例性假定：决策变量变化引起的目标函数的改变量和决策变量的改变量成比例，同样，每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例。•可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。线性规划问题隐含的假定：•连续性假定：线性规划问题中的决策变量应取连续值。线性规划问题隐含的假定：•连续性假定：线性规划问题中的决策变量应取连续值。•确定性假定：线性规划问题中的所有参数都是确定的参数。线性规划问题不包含随机因素。线性规划问题隐含的假定：•比例性假定•可加性假定•连续性假定•确定性假定运用线性规划方法的特点及局限性局限性：1.线性规划它是以价格不变和技术不变为前提条件的，不能处理涉及到时间因素的问题。因此，线性规划只能以短期计划为基础。2.在生产活动中，投入产出的关系不完全是线性关系，由于在一定的技术条件下，报酬递减规律起作用，所以要满足线性假定是不可能的。在线性规划解题中，常常把投入产出的非线性关系转化为线性关系来处理，以满足线性的假定性，客观上产生误差。3.线性规划本身只是一组