当前位置:首页 >> 数学 >>

运筹学 010线性规划


《运筹学》讲稿:线性规划

1

第 1 章 线性规划
第一节 线性规划问题及数学模型
一、引例
例 1:生产计划问题 工厂可生产 A、B 两种产品。每生产一吨 A 产品需用煤 9 吨,耗电 4 千瓦,用 工时 3 个;每生产一吨 B 产品需用煤 4 吨,耗电 5 千瓦,用工时 10 个。每生产一吨 A 产品工厂可获得利润 700 元,一吨 B 产品可获利润 1200 元。工厂的煤、电力和工 人均为有限,分别为煤:360 吨,电:200 千瓦时,工时:300 个。在这种情况下, 问:为获得最大利润,工厂应分别生产 A、B 两种产品各多少吨? 该问题中的数据可归纳为下表: 产品 煤 电 工时 利润 A 9 4 3 700 B 4 5 10 1200 资源限制 360 200 300

下面列出该问题的数学模型。 首先设变量, x1 为产品 A 的生产量, x2 为产品 B 的生产量。 可列出问题中煤、电、工时三种资源的消耗和限制情况: 煤: 电:

9 x1 ? 4 x2 ? 360
4 x1 ? 5x2 ? 200

工时: 3x1 ? 10x2 ? 300 再列出获得最大利润这一目标:

max z ? 700x1 ? 1200x2
最后列出变量的有效取值范围: x1 , x2 ? 0 上面这些表达式用数学形式反映出了问题中的各种因素,即称为该问题的数学 模型,整理如下:
max z ? 700x1 ? 1200x 2 9 x1 ? 4 x 2 ? 360 4 x1 ? 5 x 2 ? 200 3 x1 ? 10x 2 ? 300 x1 , x 2 ? 0

该数学模型即是一个线性规划模型。

《运筹学》讲稿:线性规划

2

二、问题的特征
引例中的问题可表示为一个线性规划模型,该问题也就相应地称为是一个线性 规划问题。下面结合该例题明确线性规划问题所具有的几个特征: (1) 目标性。 问题中存在一个趋向性的目标, 要求某个指标尽可能大或尽可能小。 如要求利润尽可能大。 (2) 约束性。问题中存在一定的限制条件,如煤、电、工时的消耗量不能超过一 定的限量。 (3) 矛盾性。是指不论如何调整解决问题的方案,都会对问题的目标同时产生有 利和不利两方面的影响。或者说,对模型中所设定的每个变量,不论是增大还是减 小变量的取值,都会从不同的方面导致目标值的增大和减小。如增加产品 A 的产量, 会增大 A 的利润,但同时会增大 A 消耗的资源,从而减少 B 可用的资源,导致 B 的 产量及利润减少。 矛盾性决定了一个问题无法通过简单的计算得到结果,而需要采用最优化方法 来求解。 (4) 比例性与可加性。比例性指问题中各变量所产生的效应与变量的取值成正 比。如资源的消耗量、利润均与产量成正比;可加性指各变量所产生的效应之和等 于总效应,如两种产品所产生的利润相加即等于总利润。

三、线性规划模型的一般形式
线性规划模型的一般形式可表示如下:

max( min) z ? c1 x1 ? c2 x2 ? ?? ? cn xn (目标函数) 或

a11 x1 ? a12 x 2 ? ?? ? a1n xn ? (?, ?)b1 a 21 x1 ? a 22 x 2 ? ?? ? a 2 n x n ? (?, ?)b2 ?? a m1 x1 ? a m 2 x 2 ? ?? ? a mn x n ? (?, ?)bm
(约束条件)

第二节 图解法
一、求解方法
例:
max z ? 2 x1 ? 3x 2 2 x1 ? 2 x 2 ? 12 4 x1 x1, x 2 ? 0 ? 16 5 x 2 ? 15

解:

《运筹学》讲稿:线性规划

3

(1) 建立一个二维坐标系,将 x1 对应于横轴, x2 对应于纵轴。 (2) 画出约束条件 在坐标系中画出各约束条件及变量约束,得到能满足全部约束的区域,如图中 阴影部分所示。该区域称为可行域。

x2
2x1+2x2=12

5x2=15

4x1=16

? ? ?
x1
(3) 画出目标函数线,确定目标线的移动方向。 取不同的 z 值,画出对应的目标线,并根据趋向性要求确定目标线的移动方向。

x2

12 =

2x

2

1+

3x

? ? ? ?

6= 2x 1+

3x 2

x1
(4) 在图上确定最优解的位置 根据目标线的移动方向,将目标线移动到能与可行域存在相交的极限位置,此 时目标线与可行域相交的部分即为最优解。

《运筹学》讲稿:线性规划

4

x2

? ? ?

? ? ? ?

? ? ?

??

?

x1
(5) 求得最优解 根据最优解的图上位置可知其处于约束线 5 x2 ? 15与 2 x1 ? 2 x2 ? 12 的相交处。 联 立这两条直线方程求解,可得最优解: x1 ? 3,x2 ? 3 将解代入目标函数可得最优目标值:z*=15

二、线性规划解的情况
结合上例,可明确线性规划模型的解存在如下四种情况: (1) 无穷多最优解 如果将上例中的目标函数改为: max z ? 3x1 ? 3x2 则可行域右上角斜边线上的所有点均为最优解,其由无穷多个。 (2) 无界解 如去掉上例中第 1 和第 3 个约束条件,则目标线可一直向右上方推,z 值可达到 无穷大。在实际问题中若出现此种情况,通常是列模型错误,漏列了某些约束条件。 (3) 无可行解 如果将第 2、 3 个约束条件均改为≥, 第 则不能存在可同时满足所有约束的区域, 即不存在可行域,此时模型无可行解。如实际问题中出现此种情况,通常应调整模 型,放宽某些约束条件。 (4) 唯一最优解 例题中所求得的解即为唯一最优解。唯一解与无求多解在实际问题中均为正常 情况。

《运筹学》讲稿:线性规划

5

第三节 线性规划的 Excel 求解
一、Execl 规划求解功能的加载
执行 Excel 菜单项“工具——加载宏”;勾选“规划求解”;确定。 该项操作只需进行一次。

二、Excel 求解步骤
(1)规划单元格布局,填写数据; (2)填写目标函数及约束函数; (3)设定规划求解目标、变量及约束(菜单:工具——规划求解); (4)求解,获取结果。

三、举例
例 1:用 Excel 求解如下线性规划模型。
max z ? 700x1 ? 1200x 2 9 x1 ? 4 x 2 ? 360 4 x1 ? 5 x 2 ? 200 3 x1 ? 10x 2 ? 300 x1 , x 2 ? 0

解:(1)规划单元格布局,填写数据

(2)填写函数 目标函数 D4:=SUMPRODUCT($B$3:$C$3,B4:C4) 约束函数 D5:=SUMPRODUCT($B$3:$C$3,B5:C5) D6:=SUMPRODUCT($B$3:$C$3,B6:C6) D7:=SUMPRODUCT($B$3:$C$3,B7:C7) (3)求解设定 执行 Excel 菜单项“工具——规划求解”,作如下设定: 目标单元格:$D$4 等于:最大值 可变单元格:$B$3:$C$3

《运筹学》讲稿:线性规划

6

约束: $D$5 <= $E$5 $D$6 <= $E$6 $D$7 <= $E$7 (以上三项可合并设为“$D$5:$D$7 <= $E$5:$E$7”) $B$3:$C$3 >= 0 选项:点击“选项”按钮,勾选“采用线性模型” (4)求解,获取结果 在“规划求解参数”窗体中点击“求解”按钮,即可完成求解。 B3、C3 单元格中为求得的变量值;D4 单元格中为目标值;D5、D6、D7 单元格中 分别为煤、电、工时的消耗量。 例 2:用 Excel 求解如下线性规划模型。
max z ? ?3 x1 ? x3 x1 ? x 2 ? x3 ? 4 ? 2 x1 ? x 2 ? x3 ? 1 3 x 2 ? x3 ? 9 x1 , x 2 , x3 ? 0

解:(1) 规划单元格布局,填写数据

(2)单元格公式 目标函数 E4:=SUMPRODUCT($B$3:$D$3,B4:D4) 约束函数 E5:=SUMPRODUCT($B$3:$D$3,B5:D5) E6:=SUMPRODUCT($B$3:$D$3,B6:D6) E7:=SUMPRODUCT($B$3:$D$3,B7:D7) (3)求解设定 执行 Excel 菜单项“工具——规划求解”,作如下设定: 目标单元格:$E$4 等于:最大值 可变单元格:$B$3:$D$3 约束: $E$5 <= $F$5 $E$6 >= $F$6

《运筹学》讲稿:线性规划

7

$E$7 = $F$7 $B$3:$D$3 >= 0 选项:点击“选项”按钮,勾选“采用线性模型” (4)求解,获取结果 在“规划求解参数”窗体中点击“求解”按钮,即可完成求解。 B3、C3、D3 单元格中为求得的变量值;E4 单元格中为目标值;E5、E6、E7 单元 格中分别为各约束函数值。

作业 1: P47,1.1(a)(c) P48,1.7(a)(b),用 Excel 求解,画出所填写的数据表,写出单元格公式及求解设 定,写出求解结果。

第四节 线性规划应用举例
例 1 生产计划问题 某工厂可以生产 A1、A2、 ?、An 共 n 种产品, 生产中需要消耗 B1、B2、 ?、Bm ? ? 共 m 种资源。 生产每单位产量的 Aj 产品需要消耗 Bi 种资源的数量为 aij,各种产品每 单位的利润分别为 c1、c2、 ?、cn 。工厂的资源是有限的,每种资源的数量分别为 ?

b1、b2、 ?、bm 。 ?
上述情况可表示在如下生产情况表中。 产品 资源 B1 B2 … … Bm 单位利润 解: 设: A1、A2、 ?、An 的产量分别为 x1、x2、 ?、xn 。 ? ? 问题的线性规划模型为: A1 a11 a21 … … am1 c1 A2 a12 a22 … … am2 c2 … … … … … … An a1n a2n … … amn cn 资源限制 b1 b2 … … bm

… …

… …

问:为了使生产的总利润达到最大,每种产品各应生产多少?

《运筹学》讲稿:线性规划

8

max z ? c1 x1 ? c2 x 2 ? ?? ? cn x n a11 x1 ? a12 x 2 ? ?? ? a1n xn ? b1 a 21 x1 ? a 22 x 2 ? ?? ? a 2 n x n ? b2 ?? a m1 x1 ? a m 2 x 2 ? ?? ? a mn x n ? bm x1 , x 2 , ? , x n ? 0

例 2 货运问题 某企业租用了一节火车车皮运送甲、乙两种货物到外地销售。这两种货物每箱 的重量分别为:甲—0.2 吨,乙—0.3 吨;每箱的体积分别为:甲—1 米 3,乙—0.6 米 3;每箱可获得的利润分别为:甲—500 元,乙—400 元。一节车皮的有效载重为 56 吨,有效容积为 180 米 3。问:为获得最大利润,甲、乙各应运载多少箱? 解:设甲、乙货物的运送量分别为 x1、x2。 模型为:

max z ? 500x1 ? 400x 2 0.2 x1 ? 0.3x 2 ? 56 x1 ? 0.6 x 2 ? 180 x1 , x 2 ? 0
用 Excel 求解得: 甲运送 114 箱,乙运送 110 箱,可得利润 101000 元。货物总重量为 55.8 吨,总 体积为 180 米 3。 例 3 混合配料问题 某饲养厂每天需要 1000 公斤饲料, 其中至少要含 7000 克蛋白质、 克矿物质、 300 1000 毫克维生素。现有五种饲料可供使用,各种饲料每公斤营养含量及价格如下表 所示: 饲料 1 2 3 4 5 蛋白质(克) 3 6 1 2 18 矿物质(克) 1.0 0.5 0.2 2.0 0.5 维生素(毫克) 0.5 1.0 0.2 2.0 0.8 价格(元) 0.2 0.7 0.4 0.3 0.8

给出费用最省的饲料选用方案。 解:设每天各种饲料的用量依次为: x1 , x2 , x3 , x4 , x5 。 模型为:

《运筹学》讲稿:线性规划

9

min z ? 0.2 x1 ? 0.7 x 2 ? 0.4 x3 ? 0.3x 4 ? 0.8 x5 3 x1 ? 6 x 2 ? x3 ? 2 x 4 ? 18x5 ? 7000 x1 ? 0.5 x 2 ? 0.2 x3 ? 2 x 4 ? 0.5 x5 ? 300 0.5 x1 ? x 2 ? 0.2 x3 ? 2 x 4 ? 0.8 x5 ? 1000 x1 ? x 2 ? x3 ? x 4 ? x5 ? 1000 x1 , x 2 , x3 , x 4 , x5 ? 0

用 Excel 求解得: 每天第一种饲料的用量为 438.6 公斤,第四种 276.3 公斤,第五种 285.1 公斤, 第二、第三种饲料不用;每天所需费用为 398.7 元;饲料总量为 1000 公斤,可提供 的蛋白质含量为 7000 克,矿物质含量为 1134 克,维生素含量 1000 毫克。 例 4 下料问题 现需要 90 根 3 米长和 90 根 4 米长的钢筋,现有一种 10 米长的钢筋,问:如何 切割这种 10 米长的钢筋,才能使所切割的钢筋数量最少? 解:有如下三种非劣的切割方案: 方案 1:3,3,4; 方案 2:3,3,3; 方案 3:4,4。 设按三种方案切割钢筋的数量依次为 x1,x2,x3。 模型为:

min z ? x1 ? x 2 ? x3 2 x1 ? 3x 2 ? 90 x1 ? 2 x3 ? 90 x1 , x 2 , x3 ? 0,为整数
用 Excel 求解得: 按第一种方案切割 46 根, 第二种方案切割 22 根; 所需切割的钢筋总数为 68 根; 切割出的 3 米钢筋数量为 92 根,4 米为 90 根。 例 5 排班问题 某旅行社对一日游导游的需求如下: 时间:周一 需求: 40 周二 34 周三 32 周四 35 周五 28 周六 46 周日 42

导游每周工作五天,连续休息两天。问应如何安排导游的工作时间,能使所需 配备的导游人数最少? 解:从周一至周日开始上班的导游人数依次为: x1 , x2 , x3 , x4 , x5 , x6 , x7 则周一处于上班状态的导游人数为: x1 ? x4 ? x5 ? x6 ? x7 ,该人数应大于等于周

《运筹学》讲稿:线性规划

10

一的需求人数 40。同理可得其它各天的工作人数。 所配备的导游人员的总数为 x1 ? x2 ? x3 ? x4 ? x5 ? x6 ? x7 ,其应尽量小。 可得如下线性规划模型:

min z ? x1 ? x 2 ? x3 ? x 4 ? x5 ? x6 ? x7 x1 ? x 4 ? x5 ? x6 ? x7 ? 40 x1 ? x 2 ? x5 ? x6 ? x7 ? 34 x1 ? x 2 ? x3 ? x6 ? x7 ? 32 x1 ? x 2 ? x3 ? x 4 ? x7 ? 35 x1 ? x 2 ? x3 ? x 4 ? x5 ? 28 x 2 ? x3 ? x 4 ? x5 ? x6 ? 46 x3 ? x 4 ? x5 ? x6 ? x7 ? 42 x1 , x 2 , x3 , x 4 , x5 , x6 , x7 ? 0,为整数
用 Excel 求解得: 每周二、四、六、日分别安排 11、19、18、5 人开始上班,周一、周三不安排 人开始上班;共需导游 53 人;周一至周日每天可上班的人数分别为:42、34、34、 35、30、48、42。 例 13 多产品混合配料问题(教材 P44) 用 Excel 求解得: 甲种糖果用 A、B、C 三种原料的量分别为 580、193.3、193.3 公斤,乙种糖果 用 A、B、C 三种原料的量分别为 1420、2306.7、1006.7 公斤,丙种糖果不生产;可 获得利润为 5450 元;A、B、C 三种原料的总用量分别为 2000、2500、1200 公斤。

《运筹学》讲稿:线性规划

11

作业 2: 列出如下问题的线性规划模型,并用 Excel 求解,写出求解结果。 1. 某厂生产 A、B、C 三种产品,每单位产品的原材料、工时消耗、利润及资源 的限制量如下表。 产品 资源 材料 工时 利润 A 3 2 20 B 1 4 16 C 2 2 12 资源限量 1600 2000

试制定利润最大的生产计划。 2. 上题中,根据市场情况,三种产品的最低生产量分别为 300、250、100,最 高生产量分别为 400、350、200。试制定利润最大的生产计划。 3. 某公司准备把下表所示的 5 种现有合金混合起来,配置一种含铅 30%、铜 20%、铝 50%的新合金,共 1000 公斤。问现有合金应各用多少公斤才能使总费用最 省。 合金品种 含铅(%) 含铜(%) 含铝(%) 价格(元/kg) 4. 教材 P50:1.18 5. 某昼夜服务的公交线路,每天各时间区段内所需司机数量如下: 班次 时间段 所需人数 1 6:00~ 10:00 60 2 10:00~ 14:00 70 3 14:00~ 18:00 60 4 18:00~ 22:00 50 5 22:00~ 2:00 20 6 2:00~ 6:00 30 1 30 40 30 49 2 10 10 80 65 3 50 20 30 72 4 20 30 50 53 5 40 20 40 75

司机分别在各时间区段一开始上班,并连续工作 8 小时,问该线路应如何排班 才能满足需要,并使所需的总人数最少。列出该问题的线性规划模型。 6. 某公司租用一架飞机运送甲、乙两种货物销往外地。这两种货物的单位体积 分别为:甲—1.95 米 3/吨,乙—2.28 米 3/吨;单位利润分别为:甲—2000 元/吨,乙— 2300 元/吨。 该飞机有前后两个货舱, 两舱的有效容积分别为: 前舱—28 米 3, 后仓—

《运筹学》讲稿:线性规划

12

34 米 3,在同一舱内可混装两种货物,飞机的最大载重量为 30 吨。为了保持飞机的 平衡,前后两仓所载货物的重量必须相等。 在上述情况下,应如何安排运输才能使利润最大? 7. 教材 P49,1.13 设 xij 为第 i 月初起租借到第 j 月末止的租借面积, 1 ? i ? j ? 4 , 有 即有效的变量 为 x11 , x12 , x13 , x14 , x22 , x23 , x24 , x33 , x34 , x44 。 8. 教材 P50,1.14 设 xij 为第 i 种产品在第 j 种设备上加工的数量。 i ? 1,2,3 ,依次对应于 I,II,III 三种产品, j ? 1,?,5 ,依次对应于 A1,A2,B1,B2,B3 五种设备,其中 x24 , x25 , x31 , x33 , x35 无意义。


相关文章:
《运筹学》线性规划_图文.ppt
运筹学线性规划 - 第2章 线性规划 例1 穗羊公司的例子 I II 每周可
运筹学作业.doc
运筹学作业 - 运筹学作业题集 No.1 1 线性规划 1、某织带厂生产 A、B
运筹学作业.doc
运筹学作业 - 运筹学作业题集 No.1 1 线性规划 1、某织带厂生产 A、B
运筹学线性规划的图解法.ppt
运筹学线性规划的图解法 - 第二节 ? 线性规划的图解法 对于只包含两个决策变量的线性规划问题,可以 用图解法来求解。 ? 图解法简单直观,有助于了解线性规划...
运筹学线性规划及单纯形法_图文.ppt
运筹学线性规划及单纯形法 - 第一章线性规划及单纯形法 线性 规划 及单 纯形 法 ? ? ? ? ? ? ? 线性规划问题及数学模型 图解法 单纯形法原理 单纯形法...
运筹学线性规划.ppt
运筹学线性规划_管理学_高等教育_教育专区。经济与管理学院 -张凤林 1 授课内容 第一章 线性规划 第二章...
运筹学(线性规划).ppt
运筹学(线性规划)_数学_自然科学_专业资料。德州学院数学科学学院运筹学教案运 筹帷幄之中 Linear Programming 决胜 线性规划 千里之外 page1 线性规划介绍 ? 历史...
运筹学 线性规划问题_图文.ppt
运筹学 线性规划问题_管理学_高等教育_教育专区。运筹学 线性规划的求解 yufumao@Gmail.com Operational Research Lecture 线性规划问题的求解内容提要: ? 单纯形法...
线性规划-运筹学_图文.ppt
线性规划-运筹学 - 第一章 线性规划 ( Linear Programming) §1 线性规划问题及其数学模型 本节重点: 线性规划模型结构及特点(了解) 线性规划解的存在情况(理解...
运筹学线性规划的标准形式_图文.ppt
运筹学线性规划的标准形式 - 第三节 线性规划的标准形式 ? ? 为什么要转化为
运筹学之线性规划(一)_图文.ppt
运筹学线性规划(一) - 第一章 第一节 线性规划与单纯形法 线性规划问题及其数学模型 一、线性规划问题的数学模型 二、线性规划问题的图解法 三、线性规划问题...
运筹学线性规划_图文.ppt
运筹学线性规划 - 第二章 线性规划 第一节 线性规划问题 第二节 图解法 第三
运筹学-1-线性规划.ppt
运筹学-1-线性规划_数学_自然科学_专业资料。运筹学-线性规划运筹学管理学院 朱卫未 zhuww@njupt.edu.cn 运筹帷幄之中 第一章线性规划及单纯形法 决胜千里之 Li...
运筹学 线性规划_图文.ppt
运筹学 线性规划 - 第二章 线性规划 (Linear Programming)
运筹学-线性规划-第一次.doc
运筹学-线性规划-第一次 - 课内实验报告 课程名: 任课教师: 专学姓业: 号: 名: 运筹学邢光军 2012/2013 学年 第 2 学期 南京邮电大学 经济与管理学院...
运筹学基础线性规划_图文.pdf
运筹学基础线性规划 - 运筹学通论 胡晓东 应用数学研究所 中国科学院数学与系
运筹学线性规划实验报告_图文.doc
运筹学线性规划实验报告 - 《管理运筹学》实验报告 实验日期: 2016 年 0
运筹学线性规划单纯形法_图文.ppt
运筹学线性规划单纯形法 - 运筹学单纯形法的使用介绍,比较详细... 运筹学线性规划单纯形法_数学_自然科学_专业资料。运筹学单纯形法的使用介绍,比较详细 ...
第3章 运筹学线性规划问题的计算机求解_图文.ppt
第三章 线性规划问题的计算机求解 §1 “管理运筹学”软件的操作方法 §2 “管理运筹学”软件的输出信息分析 管 理 运 筹 学 1 第三章 线性规划问题的计算机...
运筹学-2线性规划_图文.ppt
运筹学-2线性规划 - 线性规划 (Linear Programming) 线性规划问题及其数学模型 线性规划问题的求解方法 线性规划的图解法 线性规划的单纯形法 单纯形法的进一步讨论...
更多相关文章: