《[管理学]第一章 线性规划》由会员分享，可在线阅读，更多相关《[管理学]第一章 线性规划（81页珍藏版）》请在金锄头文库上搜索。
1、浙江科技学院经济管理学院管工系,运筹学,管理科学与工程系 经济与管理学院,2019/1/18,2,课堂要求,1.要求学生上课不迟到，不早退，不得旷课； 2.上课认真听讲，要求每位同学都做笔记； 3.上课不得讲话，看书，玩手机等与课堂无关的内容； 4.课后要求独自完成作业，不得抄袭或不做课后作业。,2019/1/18,3,参考资料,1.胡运权主编，运筹学教程（第三版），清华大学出版社； 2.周华任主编，运筹学解题指导，清华大学出版社； 3.运筹学习题集（修订版），清华大学出版社； 4.熊伟编著，运筹学，机械工业出版社； 5.运筹学数据、模型、决策，科学出版社。,2019/1/18,4,前言运筹学
2、简介,运筹学是管理科学的重要理论基础和应用手段，是管理专业的重要专业基础课程之一。 运筹学根据管理问题的环境条件和决策要求，建立相应的数学模型，利用数学模型对实际问题进行分析和求解，经过分析和比较，得到适合实际问题的方案。,求解 结果 .,求解 结果 .,建立模型,求解模型,修改 模型,求解 结果 .,修改 模型,2019/1/18,5,运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，搜索和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这
3、些研究成为“作战研究”，英文是Operational Research，在美国称为Operations Research。,2019/1/18,6,战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，Operations Research就转义成为“作业研究”。我国把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。 运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划、对偶问题
4、，整数规划、运输问题、动态规划、图与网络分析。,2019/1/18,7,授课主要内容,目录： 绪论（1） 第一章 线性规划（12） 第二章 对偶问题（10） 第三章 运输问题（6） 第五章 整数规划（6） 第七章 动态规划（8） 第八章 图与网络分析（8）,上课总课时：51课时 课程设计1周（下学期开学前）,2019/1/18,8,第一章 线性规划及单纯形法,1.1 线性规划问题及其数学模型 1.2 图解法 1.3 单纯形法原理 1.4 单纯形法计算步骤 1.5 单纯形法进一步讨论,2019/1/18,9,本章学习要求,能建立实际问题的数学规划模型 理解线性规划模型的特点，标准型 掌握线性规划
5、的图解法及其几何意义 掌握单纯形法原理 掌握运用单纯形表计算线性规划问题的步骤及解法 能用二阶段法和大M法求解线性规划问题。 掌握任何基可行解原表及单纯形表的对应关系,2019/1/18,10,1.1线性规划问题及其数学模型,举例说明 线性规划数学模型的标准形式,2019/1/18,11,一、线性规划问题举例说明,生产计划问题 配料问题 背包问题 运输问题 指派问题 下料问题,2019/1/18,12,例1：美佳公司生产计划问题,1、确定决策变量通常由目标问题分解 设x1代表生产种家电数量； x2代表生产种家电数量；,2、分析并表达限制条件，包括约束条件通常由等式或不等式表示。 0x1+5x2
6、15 6x1+2x224 x1+ x2 5 x1 0,x20,3、分析目标是利润最大化 MaxZ=2x1+x2,2019/1/18,13,例2：捷运公司,表12 所需仓库面积,1、确定决策变量通常由目标问题分解 每个月有不同的租用方案，共有4个月需要租用仓库。则：,表13 租金与期限的关系,2019/1/18,14,1. 生产计划问题（Production Planning）,某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占有的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：求使得总利润最大的生产计划。,设四种产品的产量分别为x1，x
7、2，x3，x4，总利润为z，线性规划模型为：,max z=5.24x1+7.30x2+8.34x3+4.18x4 s.t. 1.5x1+1.0x2+2.4x3+1.0x42000 1.0x1+5.0x2+1.0x3+3.5x48000 1.5x1+3.0x2+3.5x3+1.0x45000 x1, x2, x3, x40,2019/1/18,15,2. 配料问题（Material Blending）,某工厂要用四种合金T1、T2、T3、T4为原料，经熔炼成为新的不锈钢G。这四种原料含铬（Cr）、锰（Mn）和镍（Ni）的含量（），这四种原料的单价以及新的不锈钢G所要求的Cr、Mn、Ni的最低含量
8、（）如下表：要求配100公斤不锈钢G，并假定在配制过程中没有损耗。求使得总成本最低的配料方案。,设四种原料分别选取x1，x2，x3，x4公斤，总成本为z。,min z=115x1+97x2+82x3+76x4 s.t. 3.21x1+4.53x2+2.19x3+1.76x43.20 Cr的含量下限约束 2.04x1+1.12x2+3.57x3+4.33x42.10 Mn的含量下限约束 5.82x1+3.06x2+4.27x3+2.73x44.30 Ni的含量下限约束 x1+x2+x3+x4=100 物料平衡约束 x1, x2, x3, x40,2019/1/18,16,3. 背包问题（Knap
9、sack Problem）,一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价格如下表：求背包中装入每种物品各多少件，使背包中物品总价值最高。,设三种物品的件数各为x1，x2，x3件，总价值为z。 max z=17x1+72x2+35x3 s.t. 10x1+41x2+20x350 x1，x2，x30 x1，x2，x3为整数 这是一个整数规划问题（Integer Programming）。这个问题的最优解为： x1=1件，x2=0件，x3=2件，最高价值z=87元,2019/1/18,17,4. 运输问题（Transportation）,某种物资从两个供应地
10、A1，A2运往三个需求地B1，B2，B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地每吨物资的运输价格如下表：求总运费最低的运输方案。,35吨,25吨,10吨,30吨,20吨,2019/1/18,18,设从两个供应地到三个需求地的运量（吨）如下表：,min z=2x11+3x12+5x13+4x21+7x22+8x23 s.t. x11+x12+x13 =35 供应地A1 x21+x22+x23 =25 供应地A2 x11 +x21 =10 需求地B1 x12 +x22 =30 需求地B2 x13 +x23 =20 需求地B3 x11, x12, x13, x21, x22,
11、x230,2019/1/18,19,这个问题的最优解表示如下：,最小总运费为：z=330+55+410+815=275元,30吨,5吨,10吨,15吨,2019/1/18,20,5. 指派问题（Assignment Problem）,有n项任务由n个人完成，每项任务交给一个人，每人都有一项任务。由i个人完成j项任务的成本（或效益）为cij。求使总成本最小（或总效益最大）的分配方案。 设：,2019/1/18,21,张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老
12、师上哪一门课，使四门课的平均总成绩最高。,设：,2019/1/18,22,设：,max 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 (7
13、) x14+x24+x34+x44=1 (8) xij=0,1,2019/1/18,23,6. 下料问题 现将1m长的钢切成A0.4m,B=0.3m，C=0.2m长的三种钢，其中A，B，C三种钢分别需要20根，45根和50根，问如何进行切割使得需要的1m钢为最少？,解：将1m的钢分别切成A，B，C三种钢的可能方案如下：,设第i种方案进行切割的1m钢的为xi根； minZ=0.1x3+0.1x5+0.1x7 s.t. 2x1+x2+x3+x420 2x2+x3+3x5+2x6+x745 x1+x3+3x4+2x6+3x7+5x850 xi 0 (i=1,28),2019/1/18,24,小结,线
14、性规划问题要求目标函数和约束方程必须是线性函数，隐含如下假定： 比例性假定：每个决策变量对目标函数的贡献与决策变量的值成比例。每个变量对约束条件左端的贡献与变量的值成比例； 可加性假定：任何变量对目标函数的贡献都与其他决策变量的值无关。一个变量对每个约束条件左端的贡献与该变量的值无关。 连续性假定（可除性假定）：允许每个决策变量值使用分数值。 确定性假定：已经确切知道每个参数（价值系数，工艺系数，右侧常数） 线性规划数学模型三个要素： 决策变量 目标函数 约束条件,2019/1/18,25,课堂习题 P45 1.13 1.14(1) 课后作业 P46 1.14(2) 1.15,2019/1/1
15、8,26,二、线性规划模型标准形式,min(max) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn (, )b1 a21x1+a22x2+a2nxn (, )b2 am1x1+am2x2+amnxn (, )bm x1, x2, , xn 0 (, Free),线性规划模型的目标函数必须是变量的线性函数，约束条件必须是变量的线性等式或不等式。如右的问题就不是线性规划问题：,1.一般形式,2019/1/18,27,2.线性规划的标准形式,目标函数为极大化，约束条件全部为等号约束，所有变量全部是非负的，这样的线性规划模型称为标准形式 maxz=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,2019/1/18,28,3.线性规划模型用矩阵和向量表示,max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxn bm x1, x2, , xn 0,价值系数,工艺系数矩阵,资源约束,2019/1/18,29,线性规划模型用矩阵和向量表示（
