运筹学课件1-1 线性规划

《运筹学课件1-1 线性规划》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹帷幄之中决胜千里之外线性规划LinearProgramming第一章线性规划★线性规划问题★线性规划模型★线性规划的图解法★可行域的性质★线性规划的基本概念★基础解、基础可行解★单纯形表§1.1线性规划问题及其数学模型●生产计划问题●配料问题●背包问题●运输问题●指派问题●下料问题1.生产计划问题（ProductionPlanning）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙

2、、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18设四种产品的产量分别为x1，x2，x3，x4，总利润为z，线性规划模型为：maxz=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80

3、001.5x1+3.0x2+3.5x3+1.0x4≤5000x1,x2,x3,x4≥0目标函数约束条件变量非负约束这个问题的最优解为：x1=294.12件，x2=1500件，x3=0，x4=58.82件最大利润为：z=12737.06元。2.配料问题（MaterialBlending）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（％），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量（％）如下表：T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.

4、332.10Ni5.823.064.272.734.30单价（元/公斤）115978276要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。T1T2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276minz=115x1+97x2+82x3+76x4s.t.3.21x1+4.53x2+2.19x3+1.76x4≥320Cr的含量下限约束2.04x1+1.12x2+3.57x3+4.33x4≥210Mn的含量下限约束5.82x1+3.

5、06x2+4.27x3+2.73x4≥430Ni的含量下限约束x1+x2+x3+x4=100物料平衡约束x1,x2,x3,x4≥0设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。这个问题的最优解为：x1=26.58,x2=31.57,x3=41.84，x4=0（公斤）,最低成本为z=9549.87元。3.背包问题（KnapsackProblem）一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：物品1物品2物品3重量（公斤/件）104120价值（元/件）177235求背包中装入每种物品各多少件，使背包中物品总价值最高。设三种物品的

6、件数各为x1，x2，x3件，总价值为z。maxz=17x1+72x2+35x3s.t.10x1+41x2+20x3≤50x1，x2，x3≥0x1，x2，x3为整数这是一个整数规划问题（IntegerProgramming）。最优解为：x1=1，x2=0，x3=2件，最高价值z=87元。物品1物品2物品3重量（公斤/件）104120价值（元/件）1772354.指派问题（AssignmentProblem）有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由第i个人完成第j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。设：张、王、李、赵四位老师被分

7、配教语文、数学、物理、化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教这四门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。语文数学物理化学张92688576王82917763李83907465赵93618375例题设：语文数学物理化学张x11x12x13x14王x21x22x23x24李x31x32x33x34赵x41x42x43x44maxz=92x11+68x12+