当前位置：文档之家 › 第一章---线性规划--第一节

第一章---线性规划--第一节

  • 格式：ppt
  • 大小：810.00 KB
  • 文档页数：39

下载文档原格式

  / 39

合集下载

第一章线性规划-模型和图解法

第一章线性规划-模型和图解法

a22 am2
a1n
a2n amn
(P1,
P2 ,
, Pn )
用向量表示时，上述模型可写为：
max(min)Z CX
s.t
n j 1
Pj x j
(, )b
X 0
线性规划问题可记为矩阵和向量的形式：
max(min)Z CX
s.t
AX
X
(, )b 0
max(min)Z CX
x21 x23
x14
x23
x32
x41
xij 0(i 1, ,4;
15
x22 x31 12
x23 x32
j 1, ,4)
10 20
二。线性规划问题的数学模型 下面从数学的角度来归纳上述三个例子的共同点。 ①每一个问题都有一组变量---称为决策变量，一般记为
x1, x2 , , xn. 对决策变量每一组值：(x1(0) , x2(0) , xn(0) )T 代表了
表1-3
月份
12
所需仓库面积 15 10
单位：100m2
34 20 12
合同租借期限 合同期内的租费
表1-4
单位；元/100m2
1个月 2个月 3个月 4个月
2800 4500 6000 7300
表1-2
月份
12
所需仓库面积 15 10
单位：100m2
34 20 12
合同租借期限 合同期内的租费
max(min) Z c1x1 c2 x2 cn xn
a11x1 a12 x2 a1n xn (, )b1
s.t
a21x1
a22 x2
a2n xn
(, )b2
am1x1 am2 x2 amnxn (, )bm

第一章 线性规划

第一章 线性规划

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第1章：线性规划

第1章：线性规划

有多少种配比方案？为什麽？ 何为最好？ • 5种硫酸价格分别为：400，700，1400， 1900，2500元/t，则有：
【例1-1】已知某企业生产资料如下表所示，问如何安排生产 才能企业使利润最大？
产 品 资 源 设备 材料A 材料B 利润（元） 90 甲 1 3 乙 1 2 5 70
每天可用于产品生产 的资源量
二、线性规划问题数学模型的一般形式
1．定义：对于求取一组变量 x j (j =1,2,......,n)，使之既满足线性约束 条件，又使具有线性表达式的目标函数取 得极大值或极小值的一类最优化问题称为 线性规划问题，简称线性规划Liner Programming(LP)。
2.配比问题和生产计划问题的线性规划模型的 特点： 用一组未知变量表示要求的方案，这组未 知变量称为决策变量； 存在一定的限制条件，且为线性表达式； 有一个目标要求（最大化，当然也可以是 最小化），目标表示为未知变量的线性表 达式，称之为目标函数； 对决策变量有非负要求。
第二节 线性规划图解法
一什么是图解法
线性规划的图解法就是用几何作图的方法分析并 求出其最优解的过程。 求解的思路是：先将约束条件加以图解，求得满 足约束条件的解的集合（即可行域），然后结合 目标函数的要求从可行域中找出最优解。 图解法虽然只能用于解二维（两个变 量）的问题， 但其主要作用并不在于求 解，而是在于能够直观 地说明线性规划解 的一些重要性质。
解：上述问题中令： ⑴ Z Z 得到 max Z Z
⑵ x1 x1
⑶ x3 x3 x3
⑷在第一个约束条件的左端加入一个松弛变量 x4 ( x4 0)
⑸在第二个约束条件是左端减去一个剩余变量 x5 ( x5 0) ⑹将第三个约束条件两端同乘“-1”

第一章_线性规划

第一章_线性规划

第 一 节 线性规划问题及其数学模型
一、线性规划问题的数学模型
线性规划问题主要解决以下两类问题： 1、任务确定后，如何统筹安排，做到应用尽量少的人 力和物力资源来完成任务； 2、在一定量的人力、物力资源的条件下，如何安排、 使用他们，使完成的任务最多。
在生产管理和经济活动中，经常会遇到线性规划问 题，如何利用线性规划的方法来进行分析，下面举例 来加以说明。
表1－2
成分
产品来源
分析：很明显，该厂可以有多种不同的方案从A，B 两处采购原油，但最优方案应是使购买成本最小的一 个，即在满足供应合同单位的前提下，使成本最小的 一个采购方案。
解：设分别表示从A，B两处采购的原油量（单位：万 吨），建立的数学模型为：
m in S 200 x1 290 x2
3. 若存在无非负要求的变量。即有某一个变 量 xj 取正值或负值都可以。这时为了满足标准型 对变量的非负要求，可令 xj = xjˊ- xj〞, 其中： xjˊ、 xj〞 0 ，由于xjˊ可能大于也可能小于xj〞，故 xj 可以为正也可以为负。
上述的标准型具有如下特点： （1）目标函数求最大值； （2）所求的变量都要求是非负的； （3）所有的约束条件都是等式； （4）常数项非负。 综合以上的讨论可以说明任何形式的线
max Z x1 2x2 3x4 3x5 0x6 0x7
x1 x2 x4 x5 x6 7
x13x1x2
x4 x2
x5 2x4
x7 2 2x5 5
x1, x2, x4, , x7 0
第二节 线性规划问题的图解法及几何意义
例1－1：（计划安排问题）某工厂在计划期内安排 生产Ⅰ、Ⅱ两种产品，已知生产单位产品所占用的 设备A、B的台时、原材料的消耗及两种产品每件 可获利润见表所示：

第1章-线性规划及单纯形法-课件(1)

第1章-线性规划及单纯形法-课件(1)

✓ x1、 x2 0
IБайду номын сангаас
设备
1
原材料 A 4
原材料 B 0
利润
2
II 资源限量
2 8 台时
0
16kg
4
12kg
3
第一章 线性规划及单纯形法 运筹学
该计划的数学模型
✓ 目标函数 ✓ 约束条件
Max Z = 2x1 + 3x2
x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0
x1
✓ 美国航空公司关于哪架飞机用于哪一航班和哪些 机组人员被安排于哪架飞机的决策。
✓ 美国国防部关于如何从现有的一些基地向海湾运 送海湾战争所需要的人员和物资的决策。
✓ ……
第一章 线性规划及单纯形法 运筹学
二、线性规划问题的数学模型
✓ 1、一般形式 ✓ 2、简写形式 ✓ 3、表格形式 ✓ 4、向量形式 ✓ 5、矩阵形式
1、唯一最优解
max Z 2 x 1 3 x 2
2 x 1 2 x 2 12 ⑴
x1 4 x1
2 x2
8 16
⑵ ⑶
4 x 2 12 ⑷
x 1 0 , x 2 0
1 234 56
x2
⑶ ⑷
(4，2)
0 1 234 5678
x1
⑵
⑴
✓最优解：x1 = 4,x2 = 2，有唯一最优解Z=14。
第一章 线性规划及单纯形法 运筹学
三、线性规划模型的标准形式
✓ 1、标准形式 ✓ 2、转换方式
第一章 线性规划及单纯形法 运筹学
1、标准形式
maZx cjxj
xj
aijxj 0
bi

线性规划概念与数学模型

线性规划概念与数学模型

约束条件的图解:
每一个约束不等式在平面直角坐标系中都 代表一个半平面，只要先画出该半平面的边 界，然后确定是哪个半平面。
怎么画边界
?
怎么确定 半平面
以第一个约束条件（工时）
x1+2 x2 8 为例 说明约束条件的图解过程。
如果全部的劳动工时都用来生产甲 产品而不生产
乙产品，那么甲产品的最大可能产量为8吨，计算
D
条件的边界－－
4
Q4
Q3
直线CD，EF: E
3
F
4x1 =16,4x2 =12
2
Q2 4x2 = 12
1
Q1
0
1
2
3
4
5
6
7
8
9
B
C
x1+4x2 = 8
4x1=16
三个约束条件及非负条件x1,x2 0所代表的公共部分
－－图中阴影区，就是满足所有约束条件和非负条件的点的
集合，即可行域。在这个区域中的每一个点都对应着一个可
目标函数值递增的方向， 用箭头标出这个方向。 图中两条虚线 l1和l2就 分别代表 目标函数等值线 2x1+3x2=0 和 2x1+3x2=6, 箭头表示使两种产品的总 利润递增的方向。
5
l3
A4
E
B
3
l1 l2 2
1
1
2
D
F 4x1=12
Q2 4,2
x1+2x2 = 8
A
3
4
5
6
7
8
9
B
4x1=16 C
1 1
1 1
1 1
B1 1
4 , B2 1

第一章 线性规划

第四节 线性规划的典型案例
线性规划
【开篇案例】
一、人力资源分配的问题
某旅行社为了迎接旅 游黄金周的到来，对一日 游导游人员的需求经过统 计分析如表所示。为了保 证导游充分休息，导游每 周工作 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
外协铸件成本(元/件)

线性规划(完整版本)


2 线性规划基本概念
生产计划问题
➢如何合理使用有限的人力，物力 和资金，使得收到最好的经济效益。 ➢如何合理使用有限的人力，物力 和资金，以达到最经济的方式，完 成生产计划的要求。
例1 生产计划问题（资源利用问题） 某家具厂生产桌子和椅子两种家具。
桌子售价50元/个，椅子销售价格30元/
个，生产桌子和椅子要求需要木工和油 漆工两种工种。生产一个桌子需要木工4 小时，油漆工2小时。生产一个椅子需要 木工3小时，油漆工1小时。该厂每个月 可用木工工时为120小时，油漆工工时为 50小时。问该厂如何组织生产才能使每 月的销售收入最大？
决策变量、约束条件、目标函数
3 线性规划问题的数学模型
一、问题的提出
解：
例2 某厂生产两种产品，下表给 出了单位产品所需资源及单位产品 利润
产品 资源
I
设备
1
材料 A
4
材料 B
0
单位利润
（元）
2
可利用
II
资源
2
8
0
16
4
12
3
问：应如何安排生产计划，才能使 总利润最大？
1.决策变量：设产品I、II的产量分
别为 1、x2
2.目标函数：设总运费为z，则有： max z = 2 x1 + 3 x2
3.约束条件：
x1 + 2x2 ≤ 8
4x1
≤ 16
4x2 ≤ 12
x1， x2≥0
例3 营养配餐问题 假定一个成年人每天需要从食物中
获得3000千卡的热量、55克蛋白质和 800毫克的钙。如果市场上只有四种食 品可供选择，它们每千克所含的热量 和营养成分和市场价格见下表。问如 何选择才能在满足营养的前提下使购 买食品的费用最小？

第01次课--第一章 线性规划

（1-2） am1 x1 am 2 x2 amn xn (, )bm
(如果取≥0)
x1 , x2 , , xn (, )0
约束条件 （1-3）
决策变量
30
非负约束条件
国防科技大学
第一节 线性规划的问题及其数学模型
标准形式
max Z c1 x1 c2 x2
cn xn
顶点同时得到最优解，则它们连线上的任意一点都是最
优解，即有无穷最优解。
28
国防科技大学
第一节 线性规划的问题及其数学模型
图解法的优缺点分析
• 直观、简便 • 变量数多于三个以上时，无能为力
通用普遍的 求解方法 （代数方法）
？
单纯形法
模型的标准形式
？
29
国防科技大学
第一节 线性规划的问题及其数学模型 线性规划的数学模型的一般形式：
2
国防科技大学
第一章 线性规划与单纯形法
在军事活动，以及生产、管理、经营等社 会活动中经常提出一类问题，即如何合理地利用 有限的人力、物力、财力等资源，以得到最好的 效果。
3
国防科技大学
第一节 线性规划的问题及其数学模型
例 兵力运送问题 设有A、B两种型号的直升机，每次A能运 载35人，需驾驶员2人，B能运载20人，需驾
目标函数取 最大值
j 1 a11 x1 a12 x2 a1n xn b1 n a21 x1 a22 x2 a2 n xn b2 简记做 aij x j bi (i 1, 2, , m) j 1 x 0 ( j 1, 2, , m) a x a x a x b j mn n m m1 1 m 2 2 约束条件为等式， x , x , , x 0 且右端项为非负 1 2 n 值

线性规划及单纯形法


2021/8/17
25
例1 max Z 2 x1 3 x 2
x1 2 x2 8
s .t . 4 x1
16 4 x 2 12
x1 , x 2 0
可化为
2021/8/17
maZx 2x13x2 0x3 0x40x5
x1 2x2 x3
8
4x1
4x2
x4
16
x5 12
xj 0(j 1,,5)
n
4
1 B1 3
2 5
，
1 B2 3
1 0
，
B3
1 3
0 1
，
B4
2 5
1 0
，
B5
2 5
0 1
，
B6
1 0
0 1
根 2021/8/17 据 基 B 1 B 的 6 均 L 定 为 问 P义 题， 的 基 30 。
a11 令Ba21
a12
a22
a1m a2m＝
（ P1,P2,,Pm）
②
无公共区域(可行域) 产生原因：
有相互矛盾的 约束条件。
③
①
x1
15
4. 图解法的作用
揭示了线性规划问题有关规律和结论。
（1）规律：
有可行解 LP问题
有最优解
唯一解 无穷多解
无最优解（可行域为无界）
无可行解（无解）
（2）结论：若LP问题有最优解，则要么最优解唯一（对
应其中一个顶点），要么有无穷多最优解（对
原 A 约 料4 束 x 10x ： 216
原 B 约 料0 束 x 14x ： 212
2021变 /8/17 量非负约 x1 束 0， x： 2 0
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。



b 1


0
bm
决策变量向量：X x , x , , x T
1
2Leabharlann n第一节 线性规划问题及其数学模型
一、线性规划问题及数学模型 二、线性规划模型特点 三、线性规划问题的一般形式 四、线性规划问题的标准形式 五、非标准形转化为标准形
非标准形转化为标准形
1. 目标函数的转换 2.约束条件的转换 3. 变量的转换 4. 右端项常数的转换

2x2 2 x2 5
x1 0
min z x1 ( x3 x4 )
2x1 ( x3 x4 ) x5 2
s.t
.
x1 x1

2( x3 x4 (x3 x4 )
) x6 2 x7 5
xi 0;i 1,3,4,5,6,7
线性规划问题及数学模型
例1 生产计划问题
Ⅰ Ⅱ 每天可用能力
设备A (h) 0 5
15
设备B (h) 6 2
24
调试工序 (h) 1 1
5
利润 (元)
21
两种家电各生产多少, 可获最大利润?
线性规划问题及数学模型
解:设两种家电产量分别为变量x1 ， x2
max Z= 2x1 +x2 5x2 15
i1 1
i2 2
in n
i
ii
或
a x a x a x b
i1 1
i2 2
in n
i
松弛变量
a x a x a x s b,s 0
i1 1
i2 2
in n
i
ii
剩余变量
非标准形转化为标准形
3. 变量的转换
（1）若存在取值无约束的变量xk，可令,
xk

xk'

x
" k
x1 +x2 +x4 -x5 +x6 =7 x1 -x2 +x4 -x5 - x7 =2 x1 , x2 , x4 , … , x7 0
研究对象
有一定的人力、财力、资源条件下，如 何合理安排使用，效益最高
某项任务确定后，如何安排人、财、物， 使之最省
x,x ,x 123
目标函数：每天的生产利润最大，
利润函数 3x 5x 4x
1
2
3
约束条件：
每天原料的需求量不超过可用量：
原料 P ： 2x 3x 1500
1
1
2
原料 P ：2x 4x 800
2
2
3
原料 P ：3x 2x 5x 2000
3
1
2
3
蕴含约束：产量为非负数
非标准形转化为标准形
练习二： 将 min Z = -x1+2x2 -3x3 x1+x2 +x3 7 x1 -x2 +x3 2 x1，x20，x3无限制
化为标准形
非标准形转化为标准形
解：① 令x3 =x4 - x5 ② 加松弛变量x6 ③ 加剩余变量x7 ④ 令Z'= -Z
maxZ'= x1 -2x2 +3x4 -3x5
线性规划问题及数学模型
模型
24
min
cij xij
i1 j1
xi1 xi2 xi3 xi4 ai ; i 1,2
s.t. x1 j x2 j b j ; j 1,2,3,4
xij 0;i 1,2, j 1,2,3,4
线性规划问题及数学模型
例3：

a mj


b m

线性规划问题的标准形式
用矩阵表示为：
目标函数：max z CX
约束条件： XAX
0
b
系数矩阵：A


a 11


a m1

a 1n



P , 1
P , 2
P; n
a mn

零向量：0

0；资源向量：b
b 1
约束条件：a21
x 1
a x 22 2


ax 2n n

b 2
a x a x a x b
m1 1
m2 2
mn n
n

x 1
,
x , 2
,
x n

0
线性规划问题的标准形式
n
目标函数：max z cj xj j 1

约束条件：
非标准形转化为标准形
练习一： 将minZ= 0.15x1 + 0.25x2 + 0.1x3
50x1 + 150x2 + 90 x3 175
100x2 - 50x3 -30
70x1+ 10 x2
200
30x1 + 80x2 + 200 x3 100
xi 0 (i =1,2)
化为标准形
捷运公司拟在下一年度的1-4月的4个月 内需租用仓库堆放物资，已知各月所需仓库 面积如表一。仓库租借费用随合同期限而定， 合同期越长，折扣越大，具体见表二。租借 仓库的合同每月初都可办理，每份合同具体 规定租用面积数和期限。该厂可在任何一月 办理租借合同，每次办理一份或若干份均可。 为使租借费用最小，公司应如何选择签订合 同的最优决策？
a x a x a x (,) b
m1 1
m2 2
mn
m
x ,x , , x 0
12
n
(1.1)
(1.2) (1.3)
线性规划问题的一般形式
n
max(min) Z
CjX j
j 1
n



j 1
aij
X
j

bi
(i
1,2,
, m)

n j 1
aij
x
j
bi ,
i 1,2,L ,m
xj 0, j 1,2,L , n
标准形式的规定：
（1） 目标函数是求最大值 （2） 所有约束条件均用等式表示 （3） 所有决策变量均取非负数 （4） 所有右端项常数均为非负数
线性规划问题的标准形式
用向量表示为：
目标函数：max z CX
线性规划问题及数学模型
minZ= 2800（ x11 + x21 +x31+x41 ） +4500（ x12 + x22+x32）+6000（ x13 + x23 ）+7300x14
x11 + x12 +x13+x14 15 x12 + x13 +x14+x21 +x22+x23 10 x13 + x14 +x22+x23 +x31+x32 20 x14 + x23 +x32+x41 12 xij 0 (i =1,…,4; j =1,…,4)
约束条件：
从仓库运出总量不超过可用总量，运入零售点的数
量不低于需求量。
由于总供给量等于总需求量，所以都是等号。即
x x x x a ;i 1,2
i1
i2
i3
i4
i
x x b ; j 1,2,3,4
1j
2j
j
蕴含约束：数量非负 x 0;i 1,2, j 1,2,3,4 ij
x 2

x 3

x 4

x 5

9
s.t.34xx11

x 2x 2x x
2
3
4
6
2x 3x 3x 6
2
3
4
4
xj 0, j 1, ,6
非标准形转化为标准形
例2
max z x1 x2
2x1 x2 2
s.t
.
x1 x1
第一节 线性规划问题及其数学模型
一、线性规划问题及数学模型 二、线性规划模型特点 三、线性规划问题的一般形式 四、线性规划问题的标准形式 五、非标准形转化为标准形
线性规划模型特点
决策变量：向量(x1… xn)T 决策人要
考虑和控制的因素非负 约束条件：线性等式或不等式
目标函数：Z=ƒ(x1 … xn) 线性式，求Z
第一节 线性规划问题及其数学模型
一、线性规划问题及数学模型 二、线性规划模型特点 三、线性规划问题的一般形式 四、线性规划问题的标准形式 五、非标准形转化为标准形
线性规划问题的标准形式
目标函数：max z c x c x c x
11
22
nn
a11
x 1

ax 12 2

a x 1n n
第一章 线性规划及单纯形法
Linear Programming
第一节 线性规划问题及其数学模型
一、线性规划问题及数学模型 二、线性规划模型特点 三、线性规划问题的一般形式 四、线性规划问题的标准形式 五、非标准形转化为标准形
线性规划问题及数学模型
规划问题：
在既定的资源限制条件下，如 何确定方案，使预期目标达到最优。
x,x ,x 0 123
课堂练习
模型
max 3 x1 5 x2 4 x3 2x1 3x2 1500
s.t. 2x2 4x3 800