运筹学 线性规划.ppt

《运筹学 线性规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第二章线性规划(LinearProgramming)2.1LP的数学模型2.2图解法2.3单纯形法2.4单纯形法的进一步讨论－人工变量法2.5LP模型的应用本章主要内容：2.1线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大

2、.）2.1线性规划问题的数学模型例2.1某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？2.1线性规划问题的数学模型解：设生产产品I和产品Ⅱ的产量分别为x1和x2。则有如下模型：目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥02.1线性规划问题的数学模型例2.2某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资

3、料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？设备产品ABCD利润（元）甲21402乙22043有效台时12816122.1线性规划问题的数学模型解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：maxZ=2x1+3x2x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12例2.3假定一个成年人每天需要从食物中获取3000卡热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成分以及市场价格如下表所示。问如何选择才能

4、满足营养的前提下使购买食品的费用最小？序号食品名称热量（卡）蛋白质（克）钙（毫克）价格（元）1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002请同学们自己列出模型？2.1线性规划问题的数学模型2.1线性规划问题的数学模型2.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。

5、怎样辨别一个模型是线性规划模型？2.1线性规划问题的数学模型3.线性规划建模过程（1）理解要解决的问题，了解解题的目标和条件；（2）定义决策变量（x1，x2，…，xn），每一组值表示一个方案；（3）用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；（4）用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件2.1线性规划问题的数学模型目标函数：约束条件：4.线性规划数学模型的一般形式简写为：2.1线性规划问题的数学模型其中，ci——称为价值系数aij——称为技术系数（或消耗系数）bi——称为资源系数2.1线性规划问题的数学模型向量

6、形式：其中：2.1线性规划问题的数学模型矩阵形式：其中：2.1线性规划问题的数学模型5.线性规划问题的标准形式特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。2.1线性规划问题的数学模型（2）如何化标准形式目标函数的转换如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。也就是：令，可得到上式。即若存在取值无约束的变量，可令其中：变量的变换2.1线性规划问题的数学模型约束方程的转换：由不等式转换为等式。称为松弛变量称为剩余变量变量的变换可令，显然2.1线性规划

7、问题的数学模型例2.4将下列线性规划问题化为标准形式用替换，且解:（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以2.1线性规划问题的数学模型(2)第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0,化为等式；(3)第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5，x5≥0；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z′=-z,得到maxz′=-z，即当z达到最小值时z′达到最大值，反之亦然;2.1线性规划问题的数学模型

8、标准形式如下：2.1线性规划问题的数学模型6.线性规划问题的解线性规划问题求解线性规划问题，就