当前位置：文档之家 › 4-运筹学B-第1章线性规划

4-运筹学B-第1章线性规划

  • 格式：ppt
  • 大小：2.50 MB
  • 文档页数：114

下载文档原格式

  / 114

合集下载

运筹学课后习题答案

运筹学课后习题答案

第一章 线性规划1、由图可得：最优解为2、用图解法求解线性规划： Min z=2x 1+x 2⎪⎪⎩⎪⎪⎨⎧≥≤≤≥+≤+-01058244212121x x x x x x解：由图可得：最优解x=1.6,y=6.4Max z=5x 1+6x 2⎪⎩⎪⎨⎧≥≤+-≥-0,23222212121x x x x x x解：由图可得：最优解Max z=5x 1+6x 2, Max z= +∞Maxz = 2x 1 +x 2⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤0,5242261552121211x x x x x x x由图可得：最大值⎪⎩⎪⎨⎧==+35121x x x ， 所以⎪⎩⎪⎨⎧==2321x xmax Z = 8.1212125.max 23284164120,1,2maxZ .jZ x x x x x x x j =+⎧+≤⎪≤⎪⎨≤⎪⎪≥=⎩如图所示，在（4，2）这一点达到最大值为26将线性规划模型化成标准形式：Min z=x 1-2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≥-=++-≥+-≤++无约束321321321321,0,052327x x x x x x x x x x x x解：令Z ’=-Z,引进松弛变量x 4≥0，引入剩余变量x 5≥0，并令x 3=x 3’-x 3’’,其中x 3’≥0,x 3’’≥0Max z ’=-x 1+2x 2-3x 3’+3x 3’’⎪⎪⎩⎪⎪⎨⎧≥≥≥≥≥≥-=++-=--+-=+-++0,0,0'',0',0,05232'''7'''5433213215332143321x x x x x x x x x x x x x x x x x x x7将线性规划模型化为标准形式Min Z =x 1+2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≤-=--≥++-≤++无约束，321321321321,00632442392-x x x x x x x x x x x x解：令Z ’ = -z ，引进松弛变量x 4≥0,引进剩余变量x 5≥0,得到一下等价的标准形式。

第一章 线性规划

第一章 线性规划
(1-8)
例 1.5 （汽油混合问题） 一种汽油的特性可用两个指标描述：其点火性用“辛烷数” 描述，其挥发性用“蒸汽压力”描述，某炼油厂有四种标准汽油，设其标号分别为 1，2， 3，4，其特性及库存量见表 1.5，将上述标准汽油适量混合，可得到两种飞机汽油，其标 号分别为 1，2，这两种飞机汽油的性能指标及产量需求见表 1.6，问应如何根据库存情况 适量混合各种标准汽油，使既满足飞机汽油的性能指标，而产量又为最高。
注：前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了 12 个变量，10 个约束条件。
表 1.2 资源 住宅体系 砖混住宅 壁板住宅 大模住宅 资源限量 造价 (元/m2) 105 135 120 110000 (千元 钢材 (公斤/m2) 12 30 25 20000 (吨) 例 1.2 的数据表 水泥 (公斤/m2) 110 190 180 150000 (吨) 砖 (块/m2) 210 —— —— 147000 (千块) 人工 (工日/m2) 4.5 3.0 3.5 4000 (千工日)
3．线性规划模型的一般形式 以 MAX 型、≤约束为例 决策变量： x1 ,
(1-4)
, xn
目标函数： Maxz = c1 x1 +
+ cn x n
⎧a11 x1 + + a1n x n ≤ b1 ⎪ ⎪ 约束条件： s.t.⎨ ⎪a m1 x1 + + a mn x n ≤ bm ⎪ ⎩ x1 , , x n ≥ 0
2
Maxz = x1 + x 2 + x3 ⎧0.105 x1 + 0.135 x 2 + 0.120 x3 ≤ 110000 ⎪0.012 x1 + 0.030 x 2 + 0.025 x3 ≤ 20000 数学模型为: ⎪0.110 x1 + 0.190 x 2 + 0.180 x 3 ≤ 150000 (1-3) s.t ⎨ 0.210 x ≤ 147000 ⎪0.00451 x + 0.003x 2 + 0.0035 x 3 ≤ 4000 ⎪x , x , x 1 ≥ 0 ⎩ 1 2 3

《运筹学》课件 第一章 线性规划

《运筹学》课件 第一章 线性规划

10
解：令
xi=
1， Si被选中
min z= ci xi i 1 10
0， Si没被选中
xi 5
i 1
x1 x8 1 x7 x8 1
称为技术系数
b= (b1,b2, …, bm) 称为资源系数
2、非标准型
标准型
（1）Min Z = CX
Max Z' = -CX
（2）约束条件
• “≤”型约束，加松弛变量；
松弛变量
例如： 9 x1 +4x2≤360
9 x1 +4x2+ x3=360
• “≥”型约束，减松弛变量；
例、将如下问题化为标准型
数据模型与决策 (运筹学）
课程教材：
吴育华,杜纲. 《管理科学基础》，天津大学出版社。
绪论
一、运筹学的产生与发展
运筹学（Operational Research) 直译为“运作研究”。
• 产生于二战时期 • 60年代，在工业、农业、社会等各领域得到广泛应用 • 在我国，50年代中期由钱学森等引入
Min z x1 2x2 3x3
x1 x2 x3 7
s.t
.
x1 x2 x3 3x1 x2 2
x3
2
5
x1, x2 , x3 0
解：令 Min z Max z' (z' z) ，第一个约束加松弛变量x5，
第二个约束减松弛变量x6，得标准型：
Max z' x1 2x2 +3x3
x1 x2 x3 x4 7
s.t .
x1 x2 3x1
x3 x2
x5 2 2x3 5
x1 , , x5 0

第一章 线性规划

第一章 线性规划

第1章线性规划Chapter 1 Linear Programming本章内容提要线性规划是运筹学的重要内容。

本章介绍线性规划数学模型、线性规划的基本概念以及求解线性规划数学模型的基本算法——单纯形法。

学习本章要求掌握以下内容：⏹线性规划模型的结构⏹线性规划的标准形式，非标准形式转化为标准形式⏹线性规划的图解以及相应的概念。

包括：约束直线，可行半空间，可行解，可行域，凸集，极点，目标函数等值线，最优解⏹线性规划的基本概念。

包括：基，基础解，基础可行解，基变量，非基变量，进基变量，离基变量，基变换⏹单纯形法原理。

包括：基变量和目标函数用非基变量表出，检验数，选择进基变量的原则，确定离基变量的方法，主元，旋转运算⏹单纯形表。

包括初始单纯形表的构成，单纯形表运算方法⏹初始基础可行解，两阶段法⏹退化的基础可行解§1.1 运筹学和线性规划1.1.1 运筹学运筹学（Operations Research）是二十世纪三十年代二次大战期间由于战争的需要发展起来的一门学科。

当时，英国组织了一批自然科学和工程科学的学者，和军队指挥员一起，研究大规模战争提出的一些问题。

如轰炸战术的评价和改进、反潜艇作战研究等，研究结果在战争实践中取得了明显得效果。

这些研究当时在英国称为Operational Research，直译为作战研究。

战争结束以后，这些研究方法不断发展完善，并逐步形成学科理论体系，其中一些主要的理论和方法包括：线性规划，网络流，整数规划，动态规划，非线性规划，排队论，决策分析，对策论，计算机模拟等。

这些理论和方法在经济管理领域也得到了广泛应用，Operations Research也转义成为“作业研究”。

我国将Operations Research译成“运筹学”，非常贴切地将Operations Research这一英文术语所包含的作战研究和作业研究两方面的涵义都体现了出来。

现在，运筹学已经成为管理科学重要的基础理论和应用方法，是管理科学专业基本的必修课程之一。

运筹学第1章-线性规划

运筹学第1章-线性规划
凸集的数学定义:设K为n维欧氏空间的一个点集，若K中任意两个 点X1和X2连线上的所有点都属于K，即“X =αX1+(1-α) X2 ∈ K(0≤a ≤ 1)”，则称K为凸集。设X(x1，x2，…，xn)，X1(u1， u2，...，un)，X2(v1，v2，…，vn)，如图1一5所示，“X =αX1+(1α) X2 ∈ K(0≤a ≤ 1)”的证明思路如下:
下一页 返回
图解法步骤：
（1）建立坐标系； （2）将约束条件在图上表示； （3）确立满足约束条件的解的范围； （4）绘制出目标函数的图形 （5）确定最优解
用图解法求解下列线性规划问题
max z 2x1 3x2
4x1 0x2 16
s.t
10xx11
4x2 2x2
12 8
x1, x2 0
1. 1.1问题举例
(1)生产计划问题。 生产计划问题是典型的已知资源求利润最大化的问题，对于此类
问题通常有三个假设:①在某一计划期内对生产做出的安排;②生产 过程的损失忽略不计;③市场需求无限制，即假设生产的产品全部 卖出。
下一页 返回
1.一般线性规划问题的数学模型
例1 用一块连长为a的正方形铁皮做一个容 器，应如何裁剪，使做成的窗口的容积为最 大？
解：设 x1, x2分别表示从A,B两处采购的原油量（单
位：吨），则所有的采购方案的最优方案为：
min z 200x1 290x2
0.15x1 0.50x2 150000
s.t
0.20x1 0.50x1
0.30x2 0.15x2
120000 120000
x1 0, x2 0
1. 1线性规划问题与模型
也可以写成模型(1-6)和模型(1-7)的形式，其中模型(1-7)较为常用。

运筹学基础及应用课后习题答案(第一二章习题解答)

运筹学基础及应用课后习题答案(第一二章习题解答)

运筹学基础及应用课后习题答案(第一二章习题解答)第一章：线性规划一、选择题1. 线性规划问题中，目标函数可以是（）A. 最大化B. 最小化C. A和B都对D. A和B都不对答案：C解析：线性规划问题中，目标函数可以是最大化也可以是最小化，关键在于问题的实际背景。

2. 在线性规划问题中，约束条件通常表示为（）A. 等式B. 不等式C. A和B都对D. A和B都不对答案：C解析：线性规划问题中的约束条件通常包括等式和不等式两种形式。

二、填空题1. 线性规划问题的基本假设是______。

答案：线性性2. 线性规划问题中，若决策变量个数和约束条件个数相等，则该问题称为______。

答案：标准型线性规划问题三、计算题1. 求解以下线性规划问题：Maximize Z = 2x + 3ySubject to:x + 2y ≤ 83x + 4y ≤ 12x, y ≥ 0答案：最优解为 x = 4, y = 2，最大值为 Z = 14。

解析：画出约束条件的图形，找到可行域，再求目标函数的最大值。

具体步骤如下：1) 将约束条件化为等式，画出直线；2) 找到可行域的顶点；3) 将顶点代入目标函数，求解最大值。

第二章：非线性规划一、选择题1. 以下哪个方法适用于求解非线性规划问题（）A. 单纯形法B. 拉格朗日乘数法C. 柯西-拉格朗日乘数法D. A和B都对答案：B解析：非线性规划问题通常采用拉格朗日乘数法求解，单纯形法适用于线性规划问题。

2. 非线性规划问题中，以下哪个条件不是K-T条件的必要条件（）A. 梯度条件B. 正则性条件C. 互补松弛条件D. 目标函数为凸函数答案：D解析：K-T条件包括梯度条件、正则性条件和互补松弛条件，与目标函数是否为凸函数无关。

二、填空题1. 非线性规划问题中，若目标函数和约束条件都是凸函数，则该问题称为______。

答案：凸非线性规划问题2. 非线性规划问题中，K-T条件是求解______的必要条件。

运筹学第1章：线性规划问题及单纯型解法

运筹学第1章：线性规划问题及单纯型解法

原料甲 原料乙 最低含量 VA 0.5 0.5 2 VB1 1.0 0.3 3 VB2 0.2 0.6 1.2 VD 0.5 0.2 2 0.3 0.5 单价
分别代表每粒胶丸中甲, 设 x1, x2分别代表每粒胶丸中甲, 乙两种原料的用量
5
例3,合理下料问题 , 分别代表采用切割方案1~8的套数, 的套数, 设 xj 分别代表采用切割方案 的套数
19
( f(x
)= 3
6
1.2.2 单纯型法的基本思路
确定初试基础可行解
检查是否为 最优解? 最优解?
是
求最优解的目标函数值
否 确定改善方向
求新的基础可行解
20
1.2.3 单纯型表及其格式
IV CB III XB II x1 b c1 a11 a21 c1′′= cn+1 xn+1 b1 c2′′= cn+2 xn+2 b2 x2 … xn c2 … cn a12 … a1n a22 … a2n I xn+1 cn+1 1 0 0 zn+1 xn+2 cn+2 0 1 0 zn+2 … … … … … … xn+m cn+m 0 0 1 zn+m
OBJ : max f ( x) = 6x1 + 4x2 2x1 + x2 ≤ 10 铜资源约束 x1 + x2 ≤ 8 铅资源约束 s.t. x2 ≤ 7 产量约束 x1, x2 ≥ 0 产量不允许为负值 最优解: x1 = 2, x2 = 6, max f ( x) = 36.
4
例2,配料问题(min, ≥) ,配料问题(
2 max 1 O 1 2 3 4 D 5 6 7 H 8

运筹学：第1章 线性规划 第3节 对偶问题与灵敏度分析

运筹学：第1章 线性规划 第3节 对偶问题与灵敏度分析

s.t.
4x1 3x1
5x2 200 10x2 300
x1, x2 0
9x1 4x2 360
s.t.
34xx11
5x2 10 x
200 2 300
3x1 10x2 300
x1, x2 0
则D为
min z 360y1 200y2 300y3 300y4
9 y1 4 y2 3y3 3y4 7 s.t.4 y1 5y2 10 y3 10 y4 12
amn xn bm ym xn 0
机会成本 a1 j y1 a2 j y2 aij yi amj ym
表示减少一件产品所节省的可以增加的利润
（3）对偶松弛变量的经济解释——产品的差额成本
机会成本
利润
min w b1 y1 b2 y2 bm ym
a11 y1
st
a12
y1
a1n y1
max z CX
（P）
AX b
s
.t
.
X
0
（D）
min w Yb
s.t.
YA C Y 0
• （2）然后按照（D）、（P）式写出其对偶
例：写出下面线性规划的对偶规划模型：
max z 2x1 3x2
min w 3 y1 5y2 1y3
x1 2x2 3 y1 0
s.t.
2xx11
例如，在前面的练习中已知
max z 2.5x1 x2 的终表为
3x1 5x2 15 s.t.5x1 2x2 10
x1, x2 0
0 x3 9 2.5 x1 2
0 19 1 - 3
5
5
1
2
0
1
5

第一章 线性规划

第一章 线性规划
第四节 线性规划的典型案例
线性规划
【开篇案例】
一、人力资源分配的问题
某旅行社为了迎接旅 游黄金周的到来，对一日 游导游人员的需求经过统 计分析如表所示。为了保 证导游充分休息，导游每 周工作 5天，休息两天， 并要求休息的两天是连续 的。问应该如何安排导游 人员的作息，既满足工作 需要，又使配备的导游人
下午5时14分
什么是规划？
• 以上问题无一例外都属于规划问题，涉及到求解最大值 和最小值
• 人们经常谈规划，比如国家有5年规划、10年规划、城市 有城市规划，个人有自己的人生规划.
• 规划是在现有的人力、物力水平下，使得目标达到最优 的全面、理性的计划
下午5时14分
线性规划
• 线性规划简介： • 运筹学中最成熟的一个分支 • 静态规划：单周期决策
第一节 下午5时14分 线性规划的一般模型
三、线性规划模型的特征
1. 模型隐含假定
作为严密的数学模型，线性规划蕴含着以下假定： （1）线性化假定
函数关系式f(x)= c1x1+c2x2+… +cnxn，称线性函数。 经济学中大多数函数都是非线性，通过偏导求最优。但在企业
运营决策中，经常考虑比较短时间内的计划安排，通过线性化 更便于应用。
乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？
甲
乙
丙
资源限制
铸造工时(小时/件)
5
10
7
8000
机加工工时(小时/件)
6
4
8
12000
装配工时(小时/件)
3
2
2
10000
自产铸件成本(元/件)
3
5
4
外协铸件成本(元/件)

第1章 线性规划

第1章 线性规划

第1章线性规划本章介绍了什么是线性规划，线性规划数学模型的概念及其建立数学模型方法；阐述了线性规划的图解法、解的概念及解的形式；详细介绍了普通单纯形法、人工变量单纯形法及单纯形法计算公式。

1．考核知识点（1） 基本概念：数学模型、决策变量、目标函数、约束条件、标准型、图解法、基矩阵、基变量、非基变量、可行解、基解、基可行解、最优解、基最优解、唯一解、多重解、无界解、无可行解、单纯形法、最小比值、入基变量、出基变量、解的判断、大M法、两阶段法、改进单纯形法。

（2） 建立简单的线性规划数学模型。

（3） 求解线性规划的图解法。

（4） 基、可行基及最优基的定义。

（5） 可行解、基本解、基可行解、最优解、基本最优解的定义及其相互关系。

（6） 有唯一解、有无穷多解、无界解、无可行解的判断。

（7） 求解线性规划的单纯形法。

（8） 求解线性规划的人工变量法。

（9） 单纯形法中的5个计算公式。

2．学习要求（1） 深刻领会线性规划的各种基与解的基本概念，它们之间的相互关系。

（2）掌握图解法的计算步骤，注意怎样将目标函数表达成一条直线，这条直线如何平移使得目标函数值上升或下降。

（3） 熟练掌握单纯形法计算的全过程，特别应注意如何列出单纯形表，如何由一个基可行解换到另一个基可行解，基可行解是最优解、无界解或多重解的判断准则。

（4） 理解在什么情况下加入人工变量，人工变量起何作用，用大M法计算时目标函数的变化，两阶段法计算时目标函数的构成，掌握这两种计算方法的全过程，在什么情形下线性规划无可行解。

（5） 理解用矩阵形式代替单纯形表，并用矩阵公式求解线性规划。

3．重点建立线性规划数学模型，有关线性规划解的概念、解的形式，单纯形法计算、大M法、两阶段法。

4．难点解析（1）建立线性规划数学模型建立数学模型是学习线性规划的第一步也是关键的一步。

建立正确的数学模型要掌握3个要素：研究的问题是求什么，即设置决策变量；问题要达到的目标是什么即建立目标函数，目标函数一定是决策变量的线性函数并且求最大值或求最小值；限制达到目标的条件是什么，即建立约束条件。

运筹学第一章

运筹学第一章
OR1
30
1.1.3解的概念
概念： 1、可行解：满足所有约束条件的解。 2、可行域：即可行解的集合。所有约束条件的交 集，也就是各半平面的公共部分。满足所有约 束条件的解的集合，称为可行域。 3、凸集：集合内任意两点的连线上的点均属于这 个集合。如：实心球、三角形。线性规划的可 行域是凸集。
OR1
OR1
27
线性规划图解法例题
（无界解）
max z x 2 y x y 1 2 x 4 y 3 x 0, y 0
OR1
28
线性规划图解法例题
（无解）
min z x 2 y x y 2 2 x 4 y 3 x 0, y 0
请问该 医院至 少需要 多少名 护士？
5
例题2建模
目标函数：min Z=x1+x2+x3+x4+x5+x6 约束条件： x1+x2 ≥70
x2+x3 ≥60 x3+x4 ≥ 50 x4+x5 ≥20 x5+x6 ≥30 非负性约束：xj ≥0,j=1,2,…6
OR1
6
例题3：运输问题
三个加工棉花的加工厂，并且有三个仓库供应棉花，各 供应点到各工厂的单位运费以及各点的供应量与需求量 分别如下表所示：问如何运输才能使总的运费最小？
OR1
14
总
结
从以上 5 个例子可以看出，它们都属于优化问题，它们 的共同特征： 1 、每个问题都用一组决策变量表示某一方案；这组决 策变量的值就代表一个具体方案，一般这些变量取值是 非负的。 2 、存在一定的约束条件，这些约束条件可以用一组线 性等式或线性不等式来表示。 3 、都有一个要求达到的目标，它可用决策变量的线性 函数（称为目标函数）来表示。按问题的不同，要求目 标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划的数学模型。

运筹学

运筹学
满足
12X1 + 6X2 ≤ 600 X1≥0，X2 ≥0 使 max f(x)=7X1 + 5X2
3.合理配料模型
例1-5 用三种原料A1、A2、A3配制一种食品，要求该食品中 蛋白质、脂肪、碳水化合物和维生素的含量分别不低于150、 200、250、300个单位，这三种原料的单价及每单位原料所含各 种成份的数量如表1-6所示。问如何配制这种食品，使成本最低？
X2 = 18 maxf(x) = 2600
第三节
解的结构
线性规划的解有三种情况：有最优解、有解但无 最优解和无可行解。有最优解又有两种情况：有惟一 的最优解和有无穷多个最优解。 当线性规划的约束条件中出现矛盾约束时，即二 元一次不等式组无解时，线性规划问题无可行解。
在例2－1中，加一个约束条件： 求x1,x2
令f(x)=-f(x) ′ 则maxf(x)=-min[-f(x)] =-minf(x) ′
例1-14 将下列线性规划数学模型化为标准形式: 求 x1,x2,x3
2x1 +
x2 + x3
≤ 8
满足
x1
-
x2
x2
+
x3
≥ 3
3x1 -
– 2x3 ≤ -5
≥0,X3是自由变量
X1≥0，x2
使 maxf(x) = x1 – 2x2 + 3x3
解:令X3=X4-X5，其中X4≥0，X5≥0， 在第一个约束条件的左边加入一个松驰变量X6，化为等式； 在第二个约束条件的左边减去一个松驰变量X7，化为等式； 在第三个约束条件的左边加入一个松驰变量X8，化为等式； 并且等式两边同乘以-1； 将求 maxf(x) = X1 - 2X2 + 3X3 化为求

第一章 线性规划

第一章 线性规划
下料方法 毛坯数 毛坯长
B1 5 1 5
B2 4 2 20
B3 3 3 35
B4 2 4 50
B5 1 5 65
B6 0 7 10
毛坯 需要量 3000 5000
85 70 余料长度
4、营养问题 例5.假定一个成年人每天需要从食物中获取3000大 卡热量、65克蛋白质、800毫克钙和75克脂肪。如 果市场上只有8种食物可供选择，他们每千克所含热 量和营养成分以及市场价格见表所示，问如何选择才 能在满足营养的前提下使购买食品的费用最小。
◦ 1、画出满足约束条件的可行区域，可行区域的点称为可 行解 ◦ 2、任取一点f=f0，画出等值线 ◦ 3、平移等值线，使目标函数达到最优。



1、把数学模型转化为标准型 2、确定基变量，在所有约束方程中只出现一次并 且系数为1的为基变量，其余为非基变量。 3、列出初始单纯型表 4、换基迭代：
红星玻璃制品厂是一个有3个工人的生产两种类型手工艺窗户的小厂。 窗户一种是木框架的，一种是铝框架的。3个工人的分工是：张三制作木 框架，每天做4个；李四制作铝框架，每天做6个；王二制作和切割玻璃， 每天制作18平方米的玻璃。又知每生产一个木框架窗户使用3平方米玻璃， 每一个铝框架窗户使用2平方米玻璃。又知每生产一个木框架窗户可获得 30元的利润，每生产一个铝框架窗户可获得50元的利润。由于工厂产量小， 可假设每天生产出来的产品都可以卖出去。现请为该厂制定一个每天的生 产计划，使其获利最大。 木框架窗户 铝框架窗户 工人的生产能力


5、检查检验数：若、确定最优解
◦ 原则上检验数大的变量入基，采用θ法则确定出基变量， 入基与出基交叉点处的变量为旋转元，用方框圈起。 ◦ 将旋转元所在行的所有元素都除以旋转元，将旋转元变为 1 ◦ 利用旋转元所在行的元素把旋转元所在列的所有元素都变 为0

运筹学 第01章 线性规划问题

运筹学 第01章 线性规划问题

线性规划建模步骤
设定决策变量 明确约束条件并用决策变量的线性等式或 不等式表示 用变量的线性函数表示要达到的目标，并 确定是求极小还是求极大 根据变量的物理性质确定变量是否具有非 负性 注：其中最关键是设定决策变量这一步
生产计划问题(1)
某工厂用三种原料生产三种产品，已知的 条件如下表所示，试制订总利润最大的日 生产计划
线性规划问题解的有关概念(2)
基本解：令模型中所有非基变量的值等于零后，由 模型的约束方程组得到的一组解。 基本可行解：满足非负条件的基本解称为基本可行 解。 可行基：对应于基本可行解的基称为可行基。 退化解：基本可行解的非零分量个数小于m时，称 为退化解。 最优基：若对应于基B的基本可行解X是线性规划的 最优解，则称B为线性规划的最优基
人员安排问题(1)
医院护士24小时值班，不同时段需要的护 士人数不等（见下表）。每个护士每天连 续值班8小时，在各时段开始时上班。问最 少需要多少护士？
序号 1 2 3 4 时段 06—10 10—14 14—18 18—22 最少人数 60 70 60 50
5 6
22—02 02—06
20 30
人员安排问题(2)
设xj为第j时段开始值班的护士人数
目标函数为：使人数最少，则有
min f ( X ) x1 x2 x3 x4 x5 x6 x6 x1 60 x x 70 1 2 x2 x3 60 s.t. x3 x4 50 x x 20 5 4 x5 x6 30 x1 , x2 , x3 , x4 , x5 , x6 0且为整数
运筹学
第一章 线性规划问题
本章重点
线性规划建模 线性规划的图解法 线性规划的标准形式 单纯形法 两阶段法 大M法

运筹学1至6章习题参考答案

运筹学1至6章习题参考答案
C(j)-Z(j)
0
2
11/8
0
-3/4
0
9
X4
0
0
0
9/8
1
7/16
-1/4
27/4
6
X1
3
1
0
-1/2
0
1/4
0
3
M
X2
2
0
1
[11/16]
0
-3/32
1/8
1/8
0.181818
C(j)-Z(j)
0
0
0
0
-9/16
-1/4
37/4
X3进基、X2出基，得到另一个基本最优解。
C(j)
3
2
-0.125
6重油
7残油
辛烷值
80
115
105
蒸汽压：公斤／平方厘米
1.0
1.5
0.6
0.05
每天供应数量(桶)
2000
1000
1500
1200
1000
1000
800
问炼油厂每天生产多少桶成品油利润最大，建立数学模型。
解设xij为第i（i＝1,2,3,4）种成品油配第j(j=1,2,…,7)种半成品油的数量（桶）。
10
-5
1
0
0
0
* Big M
5
3
1
0
0
0
X1
10
1
3/5
1/5
0
1/5
2
X4
0
0
4
-9
1
1
25
C(j)-Z(j)
0
-11
-1

运筹学第1章线性规划及单纯形法复习题

运筹学第1章线性规划及单纯形法复习题

max (min)
Z = CX
AX ≤ ( = , ≥ ) b X ≥ 0
3、线性规划的标准形式 、
ma0
4、线性规划问题的解 、 （一）求解方法
一 般 有 两种方法 图 解 法 单纯形法 两个变量、 两个变量、直角坐标 三个变量、 三个变量、立体坐标
适用于任意多个变量、 适用于任意多个变量、但需将 一般形式变成标准形式
（二）线性规划问题的解
1、解的概念 可行解：满足约束条件② 的解为可行解。 ⑴ 可行解：满足约束条件②、③的解为可行解。 所有解的集合为可行解的集或可行域。 所有解的集合为可行解的集或可行域。 最优解： 达到最大值的可行解。 ⑵ 最优解：使目标函数①达到最大值的可行解。 ⑶ 基：B是矩阵A中m×m阶非奇异子矩阵 是矩阵A ≠0）， ），则 是一个基。 （∣B∣≠0），则B是一个基。
§2 图 解 法
例一、 例一、 max
Z = 2 x 2 x 2 x 4 x
2 2 1
+ 3 x
2
2 x1 + x + 1 4 x1 x1 ≥
≤ 12 ≤ 8 ≤ 16 ≤ 12
2
⑴ ⑵ ⑶ ⑷
2
0, x
≥ 0
max
Z = 2 x1 + 3 x 2 x 2 x
2 2
当xj=0时, 必有 j=zj=0, 因此 时 必有y
∑P x = ∑P y = ∑P z
j =1
r
r
r
r
j
j
j =1
j
j
j =1
j
j
=b
∑(y
j =1
j
− z j ) Pj = 0

运筹学1至6章习题参考答案

运筹学1至6章习题参考答案

运筹学1至6章习题参考答案第1章 线性规划工厂每月生产A 、B 、C 三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示．表1－23310和130.试建立该问题的数学模型,使每月利润最大．【解】设x 1、x 2、x 3分别为产品A 、B 、C 的产量，则数学模型为123123123123123max 1014121.5 1.2425003 1.6 1.21400150250260310120130,,0Z x x x x x x x x x x x x x x x =++++≤⎧⎪++≤⎪⎪≤≤⎪⎨≤≤⎪⎪≤≤⎪≥⎪⎩ 建筑公司需要用5m 长的塑钢材料制作A 、B 两种型号的窗架．两种窗架所需材料规格及数量如表1－24所示：表1－24 窗架所需材料规格及数量【解】 第一步：求下料方案，见下表。

设x j （j =1,2,…，10）为第j 种方案使用原材料的根数，则 （1）用料最少数学模型为10112342567368947910min 28002120026002239000,1,2,,10jj j Z x x x x x x x x x x x x x x x x x x j ==⎧+++≥⎪+++≥⎪⎪+++≥⎨⎪+++≥⎪⎪≥=⎩∑L （2）余料最少数学模型为2345681012342567368947910min 0.50.50.52800212002*********0,1,2,,10j Z x x x x x x x x x x x x x x x x x x x x x x x x j =++++++⎧+++≥⎪+++≥⎪⎪+++≥⎨⎪+++≥⎪⎪≥=⎩L某企业需要制定1～6月份产品A 的生产与销售计划。

已知产品A 每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。

1～6月份产品A 的单件成本与售价如表1－25所示。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

设备A
3
设备B
2
乙
1 2
丙 现有资 源
2 200
4 200
2
x1
3x2
5 x3
300
x1 0， x 2 0， x 3 0
材料C 材料D 利润（元/
4 5 1 360 2 3 5 300 40 30 50
件）
最优解：X*=(50, 30, 10)T，Z*=3400，即在计划期内甲、乙、丙产
量分别为50、30和10件，利润最大，为3400元。
OR:SM
第一节 线性规划的一般模型
线性规划(Linear Programming，LP)是运筹学的重要 分支之一，研究较早、发展较快、方法较成熟，而且是众 多分支的基础，借助计算机计算更方便，应用更广泛。
线性规划通常研究资源的最优利用、设备最佳运行以 及费用最低等问题。例如，当任务或目标确定后，如何统 筹兼顾，合理安排，用最少的资源 （如资金、设备、原 标材料、人工、时间等）去完成确定的任务或目标；企业 在一定的资源条件限制下，如何组织安排生产获得最好的 经济效益（如产品量最多 、利润最大）。
2020/4/21 4
OR:SM
表1.1 某企业单位产品资源消耗及利润 产品
资源
甲乙
丙 现有资源
设备A
3 x1
1 x2 2 x3
200(h)
设备B
2 x1
2 x2 4 x3
200(h)
材料C
4 x1
5 x2 1 x3
360(kg)
材料D
2 x1
3 x2
5 x3
300(kg)
利润（元/件） 40 x1 30 x2 50 x3
产品 设备
A B C
工时消耗
甲乙 2 x1 0 x2 0 x1 2 x2 3 x1 4 x2
工时成本 (元/h) 20×2 ×0 15×0 ×2 10×3 ×4
生产能力 (h) 16 10 32
2020/4/21 8
OR:SM
(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。 (2)约束条件：生产受设备能力制约，不能突破有效供给量。
3x1 + 9x2 ≤ 540 s.t. 5x1 + 5x2 ≤ 450
max Z = 70x1＋30x2
2020/4/21
9x1 + 3x2 ≤ 720 x1 , x2 ≥0
10
OR:SM
线性规划的数学模型由
决策变量 目标函数 约束条件
Decision variables Objective function 构成，称为三要素。
Constraints
怎样辨别一个模型是线性规划模型？
其主要特征是：
1. 解决的问题是规划问题；
2．解决问题的目标函数是多个决策变量的
线性函数，通常是求最大值或最小值；
3．解决问题的约束条件是多个决策变量
的线性不等式或等式。
2020/4/21
第1章 线性规划
第1章 线性规划
内S容ub 提titl要e
第一节 线性规划的一般模型
✓一、线性规划模型的举例
✓二、LP模型的要素及特征
Hale Waihona Puke ✓三、线性规划的图解方法✓四、线性规划解的可能性
第二节 线性规划的单纯形法
✓一、线性规划的标准型式
✓二、线性规划之解的概念
2020/4/21 2
✓三、单纯形法的基本原理
▪ 设备A的约束条件表达为 2x1 ≤16
▪ 同理，设备B的加工能力约束条件表达为 2x2 ≤10
▪ 设备C的装配能力也有限，其约束条件为 3x1+ 4x2 ≤32
(3)目标函数：目标是企业利润最大化
max Z = 3x1 + 5x2
(4)非负约束：甲乙产品的产量为非负
x1 ≥0， x2 ≥0
2020/4/21 9
2020/4/21 5
OR:SM
【解】设x1、x2、x3 为甲、乙、丙三种产品的产量，则该 线性规划问题的数学模型为：
mZ a 4 xx 1 0 3x2 0 5x3 0
3 x1 x2 2 x3 200
s
.t
.
2 4
x1 x1
2 x2 5 x2
4 x3 x3
200 360
产品
甲 资源
注意：最优解的表达方式！
2020/4/21 6
OR:SM
第一节 线性规划的一般模型
二、线性规划的三个要素
• 决策变量（一组） ▪ 决策问题待定的量值 ▪ 取值要求非负
• 约束条件（一组） ▪ 任何管理决策问题都是限定在一定的条件下求解 ▪ 把各种限制条件表示为一组等式或不等式称约束条件 ▪ 约束条件是决策方案可行的保障 ▪ 约束条件是决策变量的线性函数
• 目标函数（一个） ▪ 衡量决策优劣的准则，如时间最省、利润最大、成本最低 ▪ 目标函数是决策变量的线性函数 ▪ 有的目标要实现极大，有的则要求极小
2020/4/21 7
OR:SM
练习1.1 某厂生产甲、乙两种产品，生产工艺路线为： 各自的零部件分别在设备A、B加工，最后都需在设备C 上装配。经测算得到相关数据如下表所示，单位甲、乙 产品的销售价格分别为73和75元。问应如何制定生产计 划，才能使总利润为最大？
设备 A B C 产品
甲 乙
限时
359 953 540 450 720
利润
70 30
③ 设备可用工时数限制
3x1 + 9x2 ≤ 540 5x1 + 5x2 ≤ 450 9x1 + 3x2 ≤ 720
解: ① 设甲、乙产品产量分别 max Z = 70x1＋30x2
为x1、x2 公斤， ② 设总利润为Z，则：
2020/4/21 3
OR:SM
第一节 线性规划的一般模型
一、线性规划模型的举例 【例】生产计划问题。
某企业在计划期内计划生产甲、乙、丙三种产品。这 些产品分别需要在设备A、B上加工，需要消耗材料C、D， 按工艺资料规定，单件产品在不同设备上加工及所需要的 资源如表1.1所示。已知在计划期内设备的加工能力各为 200小时，可供材料分别为360、300公斤；每生产一件甲、 乙、丙三种产品，企业可获得利润分别为40、30、50元， 假定市场需求无限制。问：企业决策者应如何安排生产计 划，使企业在计划期内总的利润最大？
LP模型：
m ax Z 3 x1 5 x2
2 x1 16
s
.t
.
2 3
x x
2 1
10 4 x2
32
x 1 , x 2 0
s.t. (subject to) 使满足，使服从
OR:SM
练习1.2：某厂生产甲、乙两种产品，均需在A、B、C三种不同的设备 上加工，单位产品加工所需工时、销售后能获得的利润及设备有效工 时数见下表。问：如何安排生产计划，才能使该厂获得总利润最大？