《第一章线性规划及单纯形法》由会员分享，可在线阅读，更多相关《第一章线性规划及单纯形法（129页珍藏版）》请在金锄头文库上搜索。
1、运筹学经济学院*1课堂要求1.要求同学们上课不迟到，不早退，不得 旷课； 2.上课认真听讲，要求每位同学都做笔记 ； 3.上课不得讲话，看书，玩手机等与课堂 无关的内容； 4.课后要求独自完成作业，不得抄袭或不 做课后作业。Date2参考资料 1.胡运权主编，运筹学教程（第三版），清华大 学出版社； 2.周华任主编，运筹学解题指导，清华大学出版 社； 3.运筹学习题集（修订版），清华大学出版社； 4.熊伟编著，运筹学，机械工业出版社； 5.运筹学数据、模型、决策，科学出版社。Date3 教学计划以线性规划和运输问题为讲授重点，其 它部分作为选讲内容。 教学方法以授课为主，案例分析与上机演示为辅
2、 。而讲课中主要培养用最优化方法解决实 际问题的能力。教学计划与方法Date4前言运筹学简介 运筹学是管理科学的重要理论基础和应用手段， 是管理专业的重要专业基础课程之一。 运筹学根据管理问题的环境条件和决策要求，建 立相应的数学模型，利用数学模型对实际问题进 行分析和求解，经过分析和比较，得到适合实际 问题的方案。求解 结果.求解 结果.建立 模型求解 模型修改 模型求解 结果.修改 模型实际 问题数学 模型Date5 运筹学是在第二次世界大战中诞生和发展 起来的。由于战争的需要，英国和美国招 募了一批年轻的科学家和工程师，在军队 将军的领导下研究战争中的问题，例如大 规模轰炸的效果，搜索和
3、攻击敌军潜水艇 的策略，兵力和军需物质的调运等等。这 些研究在战争中取得了很好的效果。当时 英国把这些研究成为“作战研究”，英文是 Operational Research，在美国称为 Operations Research。Date6 战后这些研究成果逐渐公开发表，这些理 论和方法被应用到经济计划，生产管理领 域，也产生了很好的效果。这样， Operations Research就转义成为“作业研 究”。我国把Operations Research译成“运 筹学”，非常贴切地涵盖了这个词作战研究 和作业研究两方面的涵义。 运筹学的内容十分广泛，包括线性规划、 整数规划、动态规划、非线性规划、
4、图论 与网络优化、排队论、决策理论、库存理 论等。在本课程中，结合管理学科的特点 ，主要介绍线性规划和运输问题。Date7线性规划 数 学 规 划非线性规划 整数规划 动态规划学科内容多目标规划 双层规划组 合 优 化最优计数问题网络优化排序问题 统筹图随 机 优 化对策论 排队论 库存论 决策分析 可靠性分析运筹学的主要内容Date8目录： p第一章线性规划及单纯形法p第二章 对偶问题 p第三章灵敏度分析 p第四章线性规划的建模与应用p第五章 运输问题Date9第一章 线性规划p线性规划问题 p线性规划模型 p线性规划的图解 p可行域的性质 p线性规划的基本概念 p基础解、基础可行解 p单纯
5、形表Date10线性规划问题n生产计划问题n配料问题n背包问题n运输问题n指派问题Date111. 生产计划问题（Production Planning）产品甲产品乙产品丙产品丁设备 能力 （小时） 设备 A1.51.02.41.02000 设备 B1.05.01.03.58000 设备 C1.53.03.51.05000 利润（元/件）5.247.308.344.18某工厂拥有A、B、C三种类型的设备，生产甲、乙、 丙、丁四种产品。每件产品在生产中需要占有的设备 机时数，每件产品可以获得的利润以及三种设备可利 用的时数如下表所示：求使得总利润最大的生产计划。Date12产品甲产品乙产品丙产品
6、丁设备 能力 （小时） 设备 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，线性规划模型为：max z=5.24x1+7.30x2+8.34x3+4.18x4 s.t. 1.5x1+1.0x2+2.4x3+1.0x420001.0x1+5.0x2+1.0x3+3.5x480001.5x1+3.0x2+3.5x3+1.0x45000x1, x2, x3, x40目标函数约束条件变量非负约束这个问题的最优解为：x1=29
7、4.12件，x2=1500件，x3=0，x4=58.82件 最大利润为：z=12737.06元。Date132. 配料问题（Material Blending）某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成 为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和 镍（Ni）的含量（），这四种原料的单价以及新的不 锈钢G所要求的Cr、Mn、Ni的最低含量（）如下表：T1T2T3T4GCr3.214.532.191.763.20 Mn2.041.123.574.332.10 Ni5.823.064.272.734.30 单价（元/公斤 ）115978276要求配100公斤不锈钢G，并假定在
8、配制过程中没有损耗 。求使得总成本最低的配料方案。Date14T1T2T3T4G Cr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30 单价（元/公斤 ）115978276min z=115x1+97x2+82x3+76x4 s.t. 3.21x1+4.53x2+2.19x3+1.76x4320 Cr的含量下限约束2.04x1+1.12x2+3.57x3+4.33x4210 Mn的含量下限约束5.82x1+3.06x2+4.27x3+2.73x4430 Ni的含量下限约束x1+x2+x3+x4=100 物料平衡约束
9、x1, x2, x3, x40设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。这个问题的最优解为：x1=26.58, x2=31.57, x3=41.84，x4=0（公 斤）, 最低成本为z=9549.87元。 问题：如果某一种成分的含量既有下限，又有上限怎么办？ Date153. 背包问题（Knapsack Problem）一只背包最大装载重量为50公斤。现有三种物品，每种 物品数量无限。每种物品每件的重量、价格如下表：物品1物品2物品3重量（公斤/件）104120价值（元/件）177235求背包中装入每种物品各多少件，使背包中物品总价值 最高。Date16设三种物品的件数各为x1
10、，x2，x3件，总价值为z。max z=17x1+72x2+35x3s.t. 10x1+41x2+20x350x1，x2，x30 x1，x2，x3为整数这是一个整数规划问题（Integer Programming）。这 个问题的最优解为：x1=1件，x2=0件，x3=2件，最高价值z=87元物品1物品2物品3重量（公斤/件）104120价值（元/件）177235Date174. 运输问题（Transportation）某种物资从两个供应地A1，A2运往三个需求地B1，B2， B3。各供应地的供应量、各需求地的需求量、每个供应 地到每个需求地每吨物资的运输价格如下表：运价（元/吨）B1B2B3供
11、应量（吨 ）A123535A247825需求量（吨）10302060求总运费最低的运输方案。Date18运价 （元/吨）B1B2B3供应量 （吨）A123535A247825需求量（吨）10302060A1A2B3B2B135吨25吨10吨30吨20吨2 3 54 7 8Date19运价 （元/吨）B1B2B3供应量 （吨）A123535A247825需求量（吨）10302060设从两个供应地到三个需求地的运量（吨）如下表：B1B2B3A1x11x12x13A2x21x22x23Date20运价 （元/吨）B1B2B3供应量 （吨）A123535A247825需求量（吨）10302060min
12、 z=2x11+3x12+5x13+4x21+7x22+8x23 s.t. x11+x12+x13 =35 供应地A1x21+x22+x23 =25 供应地A2x11 +x21 =10 需求地B1x12 +x22 =30 需求地B2x13 +x23 =20 需求地B3x11, x12, x13, x21, x22, x230 Date21运量（吨）B1B2B3供应量（吨 ） A130535A2101525需求量（吨）10302060这个问题的最优解表示如下：最小总运费为：z=330+55+410+815=275元A1A2B3B2B135吨25吨10吨30吨20吨2 3 54 7 830吨5吨1
13、0吨15吨Date225. 指派问题（Assignment Problem）有n项任务由n个人完成，每项任务交给一个人，每人都有一项 任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本 最小（或总效益最大）的分配方案。设：Date23张、王、李、赵四位老师被分配教语文、数学、物理化学四 门课程，每位老师教一门课，每门课由一位老师教。根据这 四位老师以往教课的情况，他们分别教四这门课程的平均成 绩如下表。要求确定哪一位老师上哪一门课，使四门课的平 均总成绩最高。语文数学物理化学张92688576王82917763李83907465赵93618375Date24设：语文数学物理化学张x
14、11x12x13x14王x21x22x23x24李x31x32x33x34赵x41x42x43x44max z=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44 s.t. x11+x12+x13+x14=1 (1)x21+x22+x23+x24=1 (2)x31+x32+x33+x34=1 (3)x41+x42+x43+x44=1 (4)x11+x21+x31+x41=1 (5)x12+x22+x32+x42=1 (6)x13+x23+x33+x43=1
15、 (7)x14+x24+x34+x44=1 (8)xij=0,1Date25最优解为：x14=1，x23=1，x32=1，x41=1，max z=336即张老师教化学，王老师教语文，李老师教数学，赵老师 教语文。语文 数学物理化学张0001王0010李0100赵1000语文数学物理化学张92688576王82917763李83907465赵93618375四门课的总分可以达到336分。Date26线性规划模型min(max) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn (, )b1a21x1+a22x2+a2nxn (, )b2am1x1+am2x2+amnxn (, )bmx1, x2, , xn 0 (, Free)线性规划模型的目标函数必须是 变量的线性函数，约束条件必须 是变量的线性等式或不等式。如 右的问题就不是线性规划问题：Date27线性规划的标准形式目标函数为极大化，约束条件全部为等号约束，右 端常数项均为非负，所有变量全部是非负的，这样 的线性规划模型称为标准形式maxz=c1x1+c2x2+cnxn
