§1.1线性规划的数学模型.ppt

《§1.1线性规划的数学模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划线性规划(linearprogramming)是康托洛维奇1939年提出的，1947年（G.B.Dantzig）提出求线性规划的单纯形法（simplemethod），理论上趋向成熟，实际上的应用也越来越广泛，几乎各行各业都可建立线性规划模型。本章核心问题是单纯形法。§1.1线性规划问题§1.2图解法§1.3线性规划的标准型§1.4单纯形原理§1.5单纯形算法§1.6初始基确定例1生产计划问题某企业要在计划期内安排生产甲、乙两种产品，这个企业现有的生产资料是：设备18台时，原材料A4吨，原材

2、料B12吨；已知单位产品所需消耗生产资料及利润如表1。问应如何确定生产计划使企业获利最多。§1.1线性规划问题表1产品资源甲乙资源量设备/台时3218原料A/吨104原料B/吨0212单位赢利/万元35问题分析确定生产计划就是确定产品甲、乙的生产量。为了定量分析解决这个问题，首先应建立其数学模型。设x1、x2分别表示在计划期内甲、乙两种产品的产量。首先分析x1、x2应满足什么条件，才能使生产正常进行。由于现有的生产资料总量是有限的.因此，正常生产过程中生产资料消耗不能超过现有量.产品资源甲乙资源量设备/

3、台时3218原料A/吨104原料B/吨0212单位赢利/万元35问题分析x1、x2应同时满足下列条件：原材料A限制原材料B限制设备台时限制182321£+xx产品资源甲乙资源量设备/台时3218原料A/吨104原料B/吨0212单位赢利/万元35现在的问题是找出x1、x2，在上述各种条件限制下，使Z达到最大值。由于产品产量不能是负的，故有非负限制：该生产计划的总利润为：产品资源甲乙资源量设备/台时3218原料A/吨104原料B/吨0212单位赢利/万元35生产计划问题的数学模型产品资源甲乙资源量设备/台

4、时3218原料A/吨104原料B/吨0212单位赢利/万元35一般的资源利用问题可表述为：设某企业利用m种资源来生产n种产品，已知该企业拥有的第i种资源的数量是bi,生产单位第j种产品所消耗的第i种资源的数量为aij，第j种产品的单位cj。现制定一个生产计划方案，使总利润最大。资源的合理利用问题资源利用问题的数学模型为：aij技术系数bi资源系数cj价值系数xjj种产品的生产量。例2（资源定价问题）假设企业决策者不考虑自己生产产品甲乙，而是将厂里的现有资源（见表1）买出。试问该厂的决策者应给每种资源制定

5、一个怎样的价格，才能获得良好收益？产品资源甲乙资源量设备/台时3218原料A/吨104原料B/吨0212单位赢利/万元35问题分析解：　决策者显然要考虑两个因素：第一，每种资源所收回的费用应不底于自己生产时所获得的利润；第二，定价又不能太高，要使对方容易接受。总之，定价要公平合理，使双方都能接受。产品资源甲乙资源量设备/台时3218原料A/吨104原料B/吨0212单位赢利/万元35问题分析设y1,y2,y3分别表示这三种资源的收费单价。则由第一条原则：将用于加工产品甲或乙的所有资源，如用来加工外来产品

6、所获得的收回的费用，应不低于可获得的利润，即产品资源甲乙资源量设备/台时3218原料A/吨104原料B/吨0212单位赢利/万元35从工厂的决策者来看当然是w越大越好。但是根据第二条原则，也应该使对方的支出尽可能的少；从而这个问题就可以转化为下述数学问题：当然对价格还要有非负限制。即：将该厂所有的资源都用来加工外来产品，其总收入（即对方的总支出）是产品资源甲乙资源量设备/台时3218原料A/吨104原料B/吨0212单位赢利/万元35定价问题的数学模型产品资源甲乙资源量设备/台时3218原料A/吨104

7、原料B/吨0212单位赢利/万元35设某单位现有n个人员A1,A2……,An来完成n项工作B1,B2,……,Bn。按工作要求，每个人员需干一项工作，每项工作也需一人去完成。已知人员Ai做工作Bj的效率是cij。问应如何分配，才使总效率最好。例3人员分配问题问题分析令xij表示分配人员Ai完成工作Bj的决策变量。xij=1表示分配Ai干工作Bjxij=0表示不分配Ai干工作Bj按问题要求，每人要做一项工作，每项工作需一人去做。建立该问题的数学模型的过程：问题分析派工方案的总效益对工作Bj；要求一人员去完成

8、对人员Ai；要求承担一项工作：分配问题的数学模型例4（物资运输问题）某公司要运销一种物资。该物资有甲、乙两个产地，产量分别是2000吨、1000吨；另有A、B、C三个销地，销量分别是1700吨、1100吨、200吨。已知该物资的单位运价如表1-2。问应如何确定调运方案，才能使在产销平衡的条件下，总运费最低？销地单位运价产地甲乙销量ABC2125751513717001100200产量20001000表1-2分析确定调运方案就是确定从不同产地