运筹学之线性规划ppt课件.ppt

《运筹学之线性规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划基本性质本章主要内容线性规划一般模型线性规划的图解法(重点）线性规划的标准形式(重点）线性规划解的主要概念（难点）线性规划应用——建模线性规划（Linearprogramming----LP)解决稀缺资源最优分配的有效方法研究对象在一定的人力、财力、资源条件下，如何合理安排，使得收益最高某项任务确定后，如何安排人、财、物，使得费用最省1.1.1引例例1:某工厂拥有A、B、C三个车间，生产甲、乙两种产品。每件产品在生产中需要占用生产能力时数，每件产品可以获得的利润以及三个车间可利用的时数如下表所示：产品甲x1产品乙x2

2、生产能力（工时/天）A108B0212C3436利润（百元/件）351.1线性规划的一般模型问题：工厂应如何安排生产可获得最大的总利润？解：设变量x1、x2分别为甲、乙产品的日生产量。得到不等式：x1≤8；2x2≤12；3x1+4x2≤36x1,x2≥0z=3x1+5x2目标函数Maxz=3x1+5x2约束条件x1+8s.t.2x2123x1+2x236x1，x20例2配料问题某化工厂根据一项合同要为用户生产一种用甲、乙两种原材料混合配置而成的特殊产品。甲、乙两种原材料都含有A、B、C三种化学成分，其含量（%）是：甲为12

3、，2，3；乙为3，3，15，按合同规定，成品中有三种化学成分的含量不得低于4，2，5。甲、乙两种原材料成本为每千克3，2元。厂方希望总成本达到最小，则应如何配置该产品？解设每千克该产品用x1千克甲原料和x2千克乙原料配置而成，每千克产品成本为z元，则x1+x2=1原成料分成分含量甲乙x1x2产品成分最低含量（%）ABC12323315425成本（元/千克）32目标函数MINZ=3x1+2x2约束条件12x1+3x2≥4s.t.2x1+3x2≥23x1+15x2≥5x1+x2=1x1，x20例3生产计划问题（资源利用问题）胜利家具

4、厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？解：将一个实际问题转化为线性规划模型有以下几个步骤：1．确定决策变量：x1=生产桌子的数量x2=生产椅子的数量2．确定目标函数：家具厂的目标是销售收入最大maxz=50x1+30x23．确定约束条件：4x1+3x2120（木工工时限制

5、）2x1+x250（油漆工工时限制）4．变量取值限制：一般情况，决策变量只取正值（非负值）x10,x20数学模型maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20例4营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？各种食物的营养成分表生产计划问题AB备用资源煤1230劳动日3260仓库0224利润4050解

6、:设产品A,B产量分别为变量x1，x2x1+2x2303x1+2x2602x224x1，x20maxZ=40x1+50x2原料ABＣ每单位成本14102261253171642538每单位添加剂中维生12148素最低含量求：最低成本的原料混合方案解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4)minZ=2x1+5x2+6x3+8x44x1+6x2+x3+2x412x1+x2+7x3+5x4142x2+x3+3x48xi0(i=1,…,4)例：某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：人

7、力资源分配的问题设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?解：设xi表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5+x6约束条件：s.t.x1+x6≥60x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30x1,x2,x3,x4,x5,x6≥0人力资源分配的问题“Max”是英文单词“Maximize”的缩写，Min(minimize最小化）

8、；“s.t.”是“subjectto”的缩写，表示“满足于……”。线性规划（Linearprogramming----LP)1.1.2线性规划的一般模型目标函数：Max(Min)z=c1x1+c2x2+…+cnxn约束条件：a11x1+a12x2+