资源描述：
《线性规划模型与标准化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第一章、线性规划及单纯形法线性规划（LinearProgramming，LP）是运筹学的一个重要分支。1947年，丹捷格(Dantzig)提出了求解线性规划问题的一种一般解法——单纯形法(SimpleMethod)，使线性规划在理论上趋于成熟，应用日益广泛。随着计算机技术的发展，用计算机处理大规模线性规划问题之后，线性规划的应用更加广泛和深入。目前，它已成为解决现代管理和某些科学技术问题的重要手段之一。1.1线性规划的概念一、线性规划问题的提出——利用有限资源某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台数及A、B两种原材料的消耗量，见表1-1。该工
2、厂每生产一件产品Ⅰ可获利润2元，每生产一件产品Ⅱ可获利润3元，问应如何安排生产计划使该工厂获得的利润最大？生产计划问题产品资源ⅠⅡ资源限量设备(台时)128原材料A(g)4016000原材料B(g)0412000如何制定生产计划，使两种产品总利润最大？利用有限资源：某鸡厂共饲养1万只鸡，用大豆和谷物混合喂养，已知一只鸡消耗饲料1kg/天，它至少需要蛋白质、钙分别为0.22、0.06kg/天。又知每公斤大豆含蛋白质、钙为50％、0.2％，每公斤谷物含蛋白质、钙为10％、0.1％，大豆和谷物售价0.4、0.2元/kg。问怎样喂养，鸡场最合算？饲料成分大豆谷物营养/天.鸡蛋白质.
3、kg50％10％≥0.22钙.kg0.2％0.1％≥0.06售价.元0.40.2设：每只鸡每天需要大豆x1公斤，谷物x2公斤，+=0.20.421xxMinZ=³≥+2,1,00.22..21jx0.1x0.5xtsj≥+0.06210.001x0.002x+＝121xx=³≥++=2,1,00.22×10000..0.20.42121jx0.1x0.5xtsxxMinZj≥+0.06×10000210.001x0.002x+＝1000021xx设：养鸡场每天需要大豆x1公斤，谷物x2公斤二、线性规划的定义和数学描述（模型）1．定义：对于求取一组变量xj(j=1,2,...
4、...,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划（LP）。2.配比问题和生产计划问题的线性规划模型的特点：用一组未知变量表示要求的方案，这组未知变量称为决策变量；存在一定的限制条件，且为线性表达式；有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线性表达式，称之为目标函数；对决策变量有非负要求。在管理中一些典型的线性规划应用合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划
5、：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小线性规划数学模型的组成：目标函数MaxF或MinF约束条件s.t.(subjectto)满足于决策变量用符号来表示可控制的因素3．LP的数学描述(数学模型)：一般形式+++=…)(2211nnxcxcxcZMinMax或≥=+++≥=+++≥=++0,,,),(),(),(..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats……………+……≤≤≤≥三、LP的标准型：1、LP标准型
6、的概念（1）什麽是LP的标准型？（2）LP标准型的特点目标函数约定是极大化Max;约束条件均用等式表示;决策变量限于取非负值;右端常数b均为非负值;即标准形式为：（1）展开式+++=…2211nnxcxcxcMax=+++=+++=++0,,,..2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats……………+……≥（2）紧缩形式=≥===∑==njxmibxatsxcZMaxjnjijijnjjj,2,10,2,1..11∑……（3）矩阵形式其中:),,(21ncccC…=T=),,(21n
7、xxxX…Tmbbbb),,,(21…==mnmmnnaaaaaaaaaA…………………212222111211（4）向量—矩阵形式：其中：njaaaPTmjjjj,,2,1,),,,(21……==),,,(21nPPPA…=2、LP问题的标准化（1）目标函数的标准化MinZ=CXMaxZ’=-CXZ’=-Z目标函数标准化示意图●●◆◆（2）约束条件的标准化&约束条件是≤类型——左边加非负松弛变量&约束条件是≥类型——左边减非负剩余变量&变量符号不限——引入新变量（≥0）&常数项b<0——约束条件的两边同乘-1例1
