运筹学-第2讲线性规划模型

《运筹学-第2讲线性规划模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章线性规划本章要求：1.掌握并熟练应用线性规划的模型处理实际问题2.掌握线性规划的图解法3.掌握软件求解线性规划4.了解线性规划对偶问题的基本性质5.理解有关灵敏度分析内容关于“线性规划”英文名：LinearProgramming,缩写为LP自1947年丹齐格提出求解一般线性规划的有效方法——单纯形法后，得到迅速发展，成为运筹学应用最广泛的分支。特点：1.应用广泛2.模型简单易建3.求解方法成熟线性规划是运筹学的重要组成部分，也是最基础的部分。自1947年丹齐格（G.B.Dantzig）提出了求解线性规划的一般方法－－单纯形法

2、以来，线性规划在理论上趋向成熟，日臻完善，尤其是计算机处理问题的规模及运算速度提高后，线性规划的应用领域更加广泛。无论工业、农业、商业、交通运输、军事、经济计划和管理决策等领域都有应用。大到一个国家、一个地区，小到一个企业、一个车间、一个班组都有运用线性规划后提高经济效益的例子。简介问题的提出在生产管理和经营活动中，组织常常必须对如何向不同的活动分配资源的问题做出决策，以便最好地达成组织的目标。这样的问题通常有两类，一类是如何合理地使用有限的劳动力、设备、资金等资源，以最大化效益；另一类是为了达到一定的目标，应如何组织生产，或合理

3、安排工艺流程，或调整产品的成分……以使资源消耗最少。向不同的活动分配的资源可以是资金、不同的人员以及机器、设备。而需要这些资源的活动也可以是各类生产活动，例如产品生产、营销、在不同媒体做广告、金融活动、进行资金投资或其他一些活动。由于所有活动都要求一定资源作支撑，而资源却是有限的，这必然导致活动间的冲突与矛盾。这就需要管理者利用一些科学的方法进行协调，以使资源达到最大的效用。显然，上述活动所引起的问题是一类有约束的最优化问题（ConstrainedOptimization）。线性规划正是解决有约束的最优化问题的一种常用的方法，其涉

4、及的主要概念包括：◆目标（Objective）:所要达到的最优结果（最　　　大或最小）；◆约束条件（Constraints）:对所能产生结果的　　　限制。例11.1基本问题1.1.1基本模型的建立例2例3：生产计划问题某厂计划安排生产A，B两种产品，已知生产单位产品的利润与所需的劳动力，设备台时及原材料的消耗如图所示。问应该如何安排生产获利最大？产品A产品B资源限制劳动力（工时）设备（台时）原材料（公斤）9434510360200300单位产品利润（元）70120LP模型：设:安排生产A产品x1个单位，B产品x2个单位.例4：饮料

5、配制计划大众酒吧自行配制生产甲，乙两种饮料，管理层决定下月总产量至少达到350升。甲饮料每升的制造成本为2元，制造时间需2小时，乙饮料每升的制造成本为3元，制造时间需1小时，下月总生产时间为600小时。此外，下月有一位客户已预定甲饮料125升。试为管理层制定满足客户要求且制作成本最小的生产计划。线性规划模型？LP模型：设:配制生产甲饮料x1升,乙饮料x2升.某集团有1000000元资金供投资，该集团有5个可供选择的投资项目，其中各种资料如下表：投资项目风险，%红利，%增长，%信用度1105101126817831871410412

6、62245410710该集团的目标为：投资风险最小，每年红利至少80000元，最低平均增长率14%，最低平均信用度6，请用线性规划方法描述该问题。例5投资问题[分析建模]：决策变量为各项目的投资数额，设为xi（i=1,2,3,4,5）。目标函数：投资额约束：红利约束：增长额约束：平均信用度约束：非负约束：[LP模型]：例6：运输问题A1，A2两个煤矿给B1，B2，B3三个城市供煤，各煤矿产量和各城市需求量以及各地之间的单位运价如下表所示：问应该如何调运，才能既满足城市需求，又使总运费最小？线性规划模型？煤矿日产量（吨）城市需求量（

7、吨）A1A2200250B1B2B3100150200运价（元/吨）B1B2B3A1A29070100806580销地产地B1B2B3产量A1A2销量9070100200806580250100150200运价（元/吨）设xij表示产地Ai运往销地Bj煤的数量(i=1,2;j=1,2,3).运输表产品组合问题的推广线性规划的矩阵形式对于一般线性规划模型，目标函数可以求最大，也可以求最小；约束条件可以是“≤”，也可以是“≥”或“=”型。因此，一般线性规划模型可表示为线性规划模型的一般形式线性规划模型的标准形式线性规划化的标准化(1)

8、目标函数(2)约束条件当要求目标函数极小化时，将目标函数价值系数乘以“-1”，按最大化求解。不等式+松弛变量不等式-剩余变量==maxz=3x1+5x2写出例1.1的标准形式标准形式maxz=3x1+5x2s.t.s.t.(3)变量令令解例将下列线