《运筹学》课程授课教案（讲稿）第1讲 绪论及建模

课程名称：《运筹学》第_1_讲次第一章绪论授课题目第二章线性规划2.1建模型及概念本讲目的要求及重点难点：「目的要求】通过本讲课程的学习，了解什么是线性规划问题，初步学习线性规划的建模方法。[重点及难点]建立线性规划模型内容[本讲课程的引入]运筹学是一门基础性的应用学科，主要研究系统最优化的问题，通过对建立的模型求解，为决策者进行决策提供科学依据。[本讲课程的内容]第一章 绪论一、运筹学的概念和特点1、运筹学的定义运筹学是一门应用科学，至今还没有统一的定义。定义一：为决策机构在对其控制下业务活动进行决策时，提供V以数量化为基础的科学方法。》定义二：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。》定义三：运筹学是一种给出问题坏的答案的艺术，否则问题的结果会更坏。2、运筹学的特点(1)科学方法。意义在于它不单是某种研究方法的分散和偶然的应用，而是可用于整个一类问题上。(2)多学科交叉的特点。(3)强调以量化为基础。数学的广泛应用。(4)强调最优决策。最优过分理想，在实际工作中往往用次优、满意等概念代替最优。二、运筹学简史

课程名称：《运筹学》 第 1 讲次 授课题目 第一章 绪论 第二章 线性规划 2.1 建模型及概念 本讲目的要求及重点难点： 目的要求] 通过本讲课程的学习，了解什么是线性规划问题，初步学习线性规划的建模 方法。 [重点及难点] 建立线性规划模型 内 容 [本讲课程的引入] 运筹学是一门基础性的应用学科，主要研究系统最优化的问题，通过对建立的模型 求解，为决策者进行决策提供科学依据。 [本讲课程的内容] 第一章 绪论 一、运筹学的概念和特点 1、 运筹学的定义 运筹学是一门应用科学，至今还没有统一的定义。  定义一：为决策机构在对其控制下业务活动进行决策时，提供 以数量化为基础的科学方法。  定义二：运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中 提出的专门问题，为决策者选择最优决策提供定量依据。  定义三：运筹学是一种给出问题坏的答案的艺术，否则问题的结果会更坏。 2、 运筹学的特点 （1） 科学方法。意义在于它不单是某种研究方法的分散和偶然的应用，而是可用于整个 一类问题上。 （2） 多学科交叉的特点。 （3） 强调以量化为基础。数学的广泛应用。 （4） 强调最优决策。最优过分理想，在实际工作中往往用次优、满意等概念代替最优。 二、运筹学简史

内容年代代表人物/组织主要贡献1917年爱尔朗（Erlang）研究哥本哈根电话公司的通讯系统时，提出了(丹麦排队论的一些著名公式，20世纪20年存贮论的最优批量公式。代初20世纪30年英、美的一些研究小组OPERATIONALRESEARCH的提出。代末二战中，英、美为对付德国的空袭，研究如何合理地运用雷达系统：研究了护航舰队保护商船队的编队问题和当船队遭受德国潜艇攻击时，如何使船队损失最小的问题：研究了反潜深水炸弹的合理爆炸深度问题。二战后兰德公司（RAND）英、美军队中相继成立了更为正式的运筹学研究组织，针对未来武器系统的设计及其合理的运用方法等方面进行了研究。1947年丹捷格（美）在解决美国空军军事规划问题时，提出了求解(G·B·Dantzig)线性规划问题的单纯形法。1960年康托洛维奇（苏）《最佳资源利用的经济计算》的出版，并因此获得了诺贝尔奖金。实际上，早在1939年，康在解决工业生产组织和计划问题时，已提出了类似线性规划的模型，并给出了“解乘数法”的求解方法，只是当时未被重视。20世纪60年运筹学开始在工业、农业、经济和社会等各领代域广泛应用，并形成了许多分支。我国运筹学的发展情况20世纪50年钱学森，许国志，华罗钱学森，许国志等将运筹学由西方引入我国，代中期庚1957年正式定名为运筹学。在此期间，以华罗庚为首的一批数学家加入到运筹学的研究队伍，使运筹学的许多分支很快赶上国际水平。三、运筹学的工作步骤提出和形成问题a)b)建立模型c）求解d)解的检验解的控制e)D解的实施以上过程应反复进行

内 容 三、 运筹学的工作步骤 a) 提出和形成问题 b) 建立模型 c) 求解 d) 解的检验 e) 解的控制 f) 解的实施 以上过程应反复进行。 年代 代表人物/组织 主要贡献 1917 年 爱尔朗（Erlang） （丹麦） 研究哥本哈根电话公司的通讯系统时，提出了 排队论的一些著名公式。 20 世纪 20 年 代初 存贮论的最优批量公式。 20 世纪 30 年 代末 英、美的一些研究小组 OPERATIONAL RESEARCH 的提出。 二战中，英、美为对付德国的空袭，研究如何 合理地运用雷达系统；研究了护航舰队保护商 船队的编队问题和当船队遭受德国潜艇攻击 时，如何使船队损失最小的问题；研究了反潜 深水炸弹的合理爆炸深度问题。 二战后 兰德公司（RAND） 英、美军队中相继成立了更为正式的运筹学研 究组织，针对未来武器系统的设计及其合理的 运用方法等方面进行了研究。 1947 年 丹捷格（美） （G·B·Dantzig） 在解决美国空军军事规划问题时，提出了求解 线性规划问题的单纯形法。 1960 年 康托洛维奇（苏） 《最佳资源利用的经济计算》的出版，并因此 获得了诺贝尔奖金。实际上，早在 1939 年，康 在解决工业生产组织和计划问题时，已提出了 类似线性规划的模型，并给出了“解乘数法” 的求解方法，只是当时未被重视。 20 世纪 60 年 代 运筹学开始在工业、农业、经济和社会等各领 域广泛应用，并形成了许多分支。 我国运筹学的发展情况 20 世纪 50 年 代中期 钱学森，许国志，华罗 庚 钱学森，许国志等将运筹学由西方引入我国， 1957 年正式定名为运筹学。在此期间，以华罗 庚为首的一批数学家加入到运筹学的研究队 伍，使运筹学的许多分支很快赶上国际水平

内容四、运筹学的模型运筹学在解决问题时，按研究对象不同可构造各种不同的模型。模型是研究者对客观现实经过思维抽象后用文字、图表、符号、关系式以及实体模样描述所认识到的客观对象。1、模型的基本形式(1)形象模型(2)模拟模型(3)符号或数学模型2、建模的方法(1)直接分析法(2)类比法(3)数据分析法(4)试验分析法(5)构想法建模是一种创造性的劳动，成功的模型往往是科学和艺术的结晶。模型的一般数学形式：目标的评价准则U=f(xi, yjs, Zk)约束条件g(jz)≥0其中：xi为可控变量，yi为已知参数，Zk为随机因素。五、运筹学在管理领域的应用运筹学在市场营销，生产管理，后勤管理，财务管理，人事管理等管理的各个领域都有广泛的应用。六、运筹学的展望1、注重实际应用，解决实际问题。2、注重多学科的横向交叉联系。3、与计算机技术的密切结合，决策支持系统（DSS）是运筹学发展的一个契机。第二章线性规划2.1建模型

内 容 四、 运筹学的模型 运筹学在解决问题时，按研究对象不同可构造各种不同的模型。 模型是研究者对客观现实经过思维抽象后用文字、图表、符号、关系式以及实体模样描述 所认识到的客观对象。 1、 模型的基本形式 （1） 形象模型 （2） 模拟模型 （3） 符号或数学模型 2、 建模的方法 （1） 直接分析法 （2） 类比法 （3） 数据分析法 （4） 试验分析法 （5） 构想法 建模是一种创造性的劳动，成功的模型往往是科学和艺术的结 晶。 模型的一般数学形式： 目标的评价准则 U = f (xi , yj , zk ) 约束条件 g ( xi ,yj ,z k ) ≥ 0 其中：xi 为可控变量，yj 为已知参数，zk 为随机因素。 五、 运筹学在管理领域的应用 运筹学在市场营销，生产管理，后勤管理，财务管理，人事管理等管理的各个领域都 有广泛的应用。 六、 运筹学的展望 1、注重实际应用，解决实际问题。 2、注重多学科的横向交叉联系。 3、与计算机技术的密切结合，决策支持系统（DSS）是运筹学发展的一个契机。 第二章 线性规划 2.1 建模型

内容今天我们主要研究线性规划的建模问题，（板书：S2.1线性规划问题及其数学模型）让我们首先看一个生产计划问题（板书：例1、生产计划问题）。例1、生产计划问题：某工厂在计划期内要安排生产I、IⅡ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表下表所示：II12设备18台时40原材料A16 kg0412 kg原材料B该工厂每生产一件产品I可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多？设xl，x2分别表示计划期内产品I，IⅡI的产量，Z表示利润，此问题可用以下数学模型来描述：目标函数Maxz=2x/ +3x2约束条件xl +2x2\84xl≤164x2≤12xl，x2≥0上例代表一类优化问题，它们的共同特征：（1）用一组决策变量（xl，x2，，xn）表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量的取值是非负的。（2）存在一定的约束条件，这些约束条件可以用一组线性等式或线形不等式来表示。（3）都有一个要求达到的目标，它可用决策变量的线形函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划模型。其一般形式为：(1)目标函数max(min)z=clxl+c2x2++cnxn约束条件allxl+al2x2+..+alnxn≤(=,≥)bl(2)≤(=,≥)b2a2lxl+a22x2+...+a2nxn-.≤ (=, ≥) bmamlxl +am2x2+... +amnxn(3)xl,x2, * n ≥0

内 容 今天我们主要研究线性规划的建模问题，（板书：§2.1 线性规划问题及其数学模型） 让我们首先看一个生产计划问题（板书：例 1、生产计划问题）。 例1、 生产计划问题：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产 单位产品所需的设备台时及 A、B 两种原材料的消耗，如表下表所示： 该工厂每生产一件产品Ⅰ可获利 2 元，每生产一件产品Ⅱ可获利 3 元，问应如何安排 计划使该工厂获利最多？ 设 x1，x2 分别表示计划期内产品Ⅰ，Ⅱ的产量，Z 表示利润，此问题可用以下数学 模型来描述： 目标函数 Max z = 2x1 + 3x2 约束条件 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1， x2 ≥ 0 上例代表一类优化问题，它们的共同特征： （1）用一组决策变量 （ x1 , x2 , . , xn）表示某一方案，这组决策变量的值就代表 一个具体方案。一般这些变量的取值是非负的。 （2）存在一定的约束条件，这些约束条件可以用一组线性等式或线形不等式来表示。 （3）都有一个要求达到的目标，它可用决策变量的线形函数（称为目标函数）来表 示。按问题的不同，要求目标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划模型。 其一般形式为： 目标函数 max（min）z = c1x1 + c2x2 + . + cnxn （1） 约束条件 a11x1 + a12x2 + . +a1nxn ≤（= , ≥）b1 a21x1 + a22x2 + . +a2nxn ≤（= , ≥）b2 （2） . . . . am1x1 + am2x2 + . +amnxn ≤（= , ≥）bm x1 , x2 , . xn ≥ 0 （3） Ⅰ Ⅱ 设备 1 2 8 台时 原材料 A 4 0 16 ㎏ 原材料 B 0 4 12 ㎏

内容在线性规划的数学模型中，方程（1）称为目标函数：（2）、（3）称为约束条件：（3）也称为变量的非负约束条件。接下来再给大家介绍一种营养配餐问题（板书：例2营养配餐问题）看一看这类问题的模型例2、营养配餐问题假定一个成年人每天需要从食物中获取3000大卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每公斤所含热量和营养成分以及市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小。各种食物的营养成分表序号食品名称热量(大卡)蛋白质（g）钙(mg)价格（元）1猪肉5014100040062鸡蛋8006020033大米1000203004白菜200105002解：设xl为第j种食品每天的购入量，则配餐问题的线性规划模型如下：min z=14 xl +6x2+3x3+2x41000x/+800x2+900x3+200x4≥3000s. t.50xl+60x2+20x3+10x4≥55400xl+200x2+300x3+500x4≥800x≥0j=l,.,4实用的配餐问题要比上例复杂的多，可包括几十甚至上百种原料，几十种营养配方。例如医院的营养配餐和养殖业中的配合饲料问题。还有一类问题在运筹学里非常重要，那就是运输问题（板书：例3运输问题）例3、运输问题设有两个砖厂Ar、Aa。其产量分别为23万块与27万块。它们的砖供应3个工地。其需要量分别为17万块、18万块、和15万块。而自各产地到各工地的运价列表如下：工地BiBsBz砖厂

内 容 在线性规划的数学模型中，方程（1）称为目标函数；（2）、（3）称为约束条件；（3） 也称为变量的非负约束条件。 接下来再给大家介绍一种营养配餐问题（板书：例 2 营养配餐问题）看一看这类问 题的模型 例 2 、营养配餐问题 假定一个成年人每天需要从食物中获取 3000 大卡的热量、55 克蛋白质和 800 毫克的 钙。如果市场上只有四种食品可供选择，它们每公斤所含热量和营养成分以及市场价格见 下表。问如何选择才能在满足营养的前提下使购买食品的费用最小。 各种食物的营养成分表 序号 食品名称 热量(大卡) 蛋白质(g) 钙(mg) 价格(元) 1 猪肉 1000 50 400 14 2 鸡蛋 800 60 200 6 3 大米 1000 20 300 3 4 白菜 200 10 500 2 解：设 x1 为第 j 种食品每天的购入量，则配餐问题的线性规划模型如下： min z = 14 x1 + 6 x2 + 3 x3+ 2 x4 s.t. 1000 x1 + 800 x2 + 900 x3 + 200 x4  3000 50 x1 + 60 x2 + 20 x3 + 10 x4  55 400 x1 + 200 x2 + 300 x3 + 500 x4  800 xj  0 j =1, ., 4 实用的配餐问题要比上例复杂的多，可包括几十甚至上百种原料，几十种营养配方。 例如医院的营养配餐和养殖业中的配合饲料问题。 还有一类问题在运筹学里非常重要，那就是运输问题（板书: 例 3 运输问题） 例 3、 运输问题 设有两个砖厂 A1、A2 。其产量分别为 23 万块与 27 万块。它们的砖供应 3 个工地。 其需要量分别为 17 万块、18 万块、和 15 万块。而自各产地到各工地的运价列表如下： 工地 砖厂 B1 B2 B3

内容Ai50607060Aa110160（其中运价为（元/万块））问如何调运，才使总运费最省？解：设xij表示由砖厂Ai运往工地Bj的砖的数量（单位：万块）（i=1，2；j-1，2，3)，现列表如下：工地BtBzBs发量（万块）砖厂23 Atx12xllX13A27X21X22X2317181550收量(万块)所求数学模型为：Minz=50xll+60x/2+70x13+60x21+110x22+160x23x//+x/2+X13=23s. t.X21 + X22 + X23 = 27x/+ x21 = 17x/2+x22=18X13 + X23 = 15xll、x12、X13、X21、X22、x23≥0通过例题总结运输问题的一般模型：（板书）(i=1,2,",m;j=1,2,",n)xij表示由产地Ai运往销地Bj的物资数那么，上述问题的数学模型为：minz=C1+C2/12 +..+Cmm*mmS.t.X+X2+...+Xn=aX21+X22+..+X2n=a2Xml+Xm2+...+Xmm=amX+X2I+.+Xm =b,X12+X22+..+Xm2=b..............Xi,+X2n+...+m=bhx, ≥0 (i=1,2,,m;j=1,2,",n)

内 容 A1 50 60 70 A2 60 110 160 （其中运价为（元/万块））问如何调运，才使总运费最省？ 解：设 xij 表示由砖厂 Ai 运往工地 Bj 的砖的数量（单位：万块）（i =1 , 2 ; j=1 , 2 , 3),现列表如下： 工地 砖厂 B1 B2 B3 发量（万块） A1 x11 x12 x13 23 A2 x21 x22 x23 27 收量(万块) 17 18 15 50 所求数学模型为： Minz = 50 x11 + 60 x12 + 70 x13 + 60 x21 + 110 x22 + 160 x23 s.t. x11+ x12 + x13 = 23 x21 + x22 + x23 = 27 x11+ x21 = 17 x12 + x22 = 18 x13 + x23 = 15 x11、 x12、x13、 x21、x22、x23 0 通过例题总结运输问题的一般模型：（板书） xij 表示由产地 Ai 运往销地 Bj 的物资数 那么，上述问题的数学模型为： (i 1,2,  ,m; j 1,2,  ,n) mn mn z  c x c x c x min 11 11 12 12    2 1 2 2 2 2 1 1 1 2 1 1 . . x x x a st x x x a n n         0 ( 1,2, , ; 1,2, , ) 1 2 1 2 2 2 2 2 1 1 2 1 1 1 1 2 x i m j n x x x b x x x b x x x b x x x a i j n n mn n m m m m mn m                          

内容课堂练习：某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：品n甲乙设备能力（小时)设备A3265B2140c0375利润(元/件）15002500问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi为第i种（甲、乙）产品的生产件数（i=1，2)。根据题意，可以建立如下的线性规划模型目标函数MaxZ=1500xl+2500x2约束条件s. t.3xl+2x2≤652xl+x2≤403x2≤75xl，x2≥0[本讲小结】今天我们重点给大家介绍了生产计划问题、营养配餐问题、运输问题等实际问题的建模方法，无论哪一种我们都必须铭记线性规划模型所必备的四个要素即：确定决策变量、写出目标函数、写出约束方程和对变量的非负限定。[本讲课程的作业]】看课本相关内容

内 容 课堂练习： 某工厂拥有 A、B、C 三种类型的设备，生产甲、乙两种产品。每件产品 在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如 下表所示： 甲 乙 设备能力（小时） A 3 2 65 B 2 1 40 C 0 3 75 利润（元/件） 1500 2500 问题：工厂应如何安排生产可获得最大的总利润？ 解：设变量 xi 为第 i 种（甲、乙）产品的生产件数（i＝1，2）。根据题意， 可以建立如下的线性规划模型 目标函数 MaxZ =1500 x1 + 2500 x2 约束条件 s.t. 3 x1 + 2 x2 ≤ 65 2 x1 + x2 ≤ 40 3 x2 ≤ 75 x1 , x2≥0 [本讲小结] 今天我们重点给大家介绍了生产计划问题、营养配餐问题、运输问题等实际 问题的建模方法，无论哪一种我们都必须铭记线性规划模型所必备的四个要素即：确定 决策变量、写出目标函数、写出约束方程和对变量的非负限定。 [本讲课程的作业] 看课本相关内容。 n J=1 J=m+1 n m ( P1 , P2 , . ,P n ) = a11 a12 . a1n ┇ ┇ ┇ am1 am2 . amn A = O = 品 设备