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

第二章线性规划

  • 格式：ppt
  • 大小：1019.50 KB
  • 文档页数：65

下载文档原格式

  / 65

合集下载

第二章线性规划

第二章线性规划



线性规划要研究的两类问题中都包含有约束条件和目 标函数。用数学的方式描述，规划的目的就是在给定 的限制条件（或称约束条件）下，求目标函数的极值 问题（包括极小值和极大值）。
2
线性规划的数学模型
3
解： 设产品 的产量为：1 , 产品 的产量为：x2 x
4
5
6
7

配料问题：由若干种不同价格、不同成分含量的原料，用 不同的配比混合调配出一些不同规格的产品，在原料的供 应量限制和保证产品成分含量的前提下，如何进行配料来 获取最大利润或使总成本最低。
15
2.2.3 线性规划求解的可能结局
1、有唯一的最优解
2、有无穷多个最优解 （将目标函数改为 z=4x1+3x2 ）
x2
max z 4 x1 3 x2 x1 2 x2 5 2 x x 4 1 2 s.t. 4 x1 3 x2 9 x1 , x2 0
3x1 2 x2 4 x3 3
3x1 2 x2 4 x3 xs 3
剩余变量
变量xs实际上是原式左端减去右端的差，即 ：
xs 3x1 2 x2 4 x3 3
当约束条件是“ ”型的不等式时，只要将该约 束条件左端减去一个非负的剩余变量即可化为等式。 无论是松弛变量还是剩余变量在决策中都不产生实际价 值，因此它们在目标函数中的系数都应该为零。有时也将松 29 弛变量和剩余变量统称为松弛变量。
2x1+x2=4 D C
x1+2x2=5 B 4x1+3x2=9 O A x1
16
3、无界解
指线性规划问题有可行解，但是 在可行域，目标函数值是无界的， 因而达不到有限最优值。因此线 性规划问题不存在最优解。

第二章线性规划

第二章线性规划

解：设产品 A、B 的产量分别为x , y 。则，数学模型为：
m inZ 2 x 3 y x 125 x y 350 2 x y 600 x, y 0
例3 营养问题
某公司饲养试验用的动物以供出售。已知这些动物的生长 对饲料中的三种营养元素特别敏感，分别称为营养元素A 、B、C。已求出这些动物每天至少需要700克营养元素 A,30克营养元素B，而营养元素C每天恰好为200克。现有 五种饲料可供选择，各种饲料的营养元素及单价如下表22所示，为了避免过多使用某种饲料，规定混合饲料中各 种饲料的最高含量分别为：50、60、50、70、40克。求满 足动物需要且费用最低的饲料配方。
最优解必定可在可行域的某个顶点上 取得。
QM软件求解两个变量的LP问 题的方法。（演示）
Step1 Step2 Step3 Step4
1 A B C 价 格 3 1 0.5 2
2 2 0.5 1 7
3 1 0.2 0.2 4
4 6 2 2 9
5 18 0.5 0.8 5
需 求 700 30 200
解：设 x j
j 1,2 ,3,4 ,5 为每天混合饲料内包含的
第 j 种饲料的数量 （克） 则营养问题的数学模型为： 。
m inZ 2 x1 7 x 2 4 x3 9 x 4 5 x5 3x1 2 x 2 x3 6 x 4 18x5 700 x 0.5 x 0.2 x 2 x 0.5 x 30 2 3 4 5 1 0.5 x1 x 2 0.2 x3 2 x 4 0.8 x5 200 x 50, x 60, x 50, x 70, x 40 2 3 4 5 1 x j 0, j 1,2,3,4,5,

第2章 线性规划

第2章 线性规划

目标函数下降
MAXZ=4X1-3X2 S.T. X1+2X210 X16 X24 X11 X1,X20
X2=4
B A
目标函数上升
C
X2 0
E
D
X1 X1=6
4X1-3X2=0
X1=1
对解的讨论： .唯一解 .无穷解 .无解： 可行域空集 可行域无界
X2 X1+2X2=10 X2=4
X1 0
a11 a12 a1n 约束方程组 A P1 , P2 , Pn 系数矩阵 a m1 a m 2 a mn
A为m ×n矩阵（ m为约束方程个数，n为变量个数）
a11 a12 a1n A P1 , P2 , Pn a m1 a m 2 a mn
消除负的右端常数项
MAXZ=-X1-3(X3-X4) S.T. 6X1+7(X3-X4)8 X1-3(X3-X4) ≥6 X1-(X3-X4)=3 X1、X3、X4 0
约束方程还不是等式约束
人为添加变量，成为等式约束
对于“≤”约束，添加松弛变量 对于“≥”约束，添加剩余变量
6X1=5X1+3X2 S.T. 3X1+5X215
max Z 5 x1 3 x 2 3 x1 5 x 2 x 3 15 5 x1 3 x 2 x 4 10 x1 , x 2 , x 3 , x 4 0
5X1+2X210
X1,X20
2、给出基本可行解
• 6．基本可行解：满足非负条件
对于D1 ，基变量为X4、X5，X1、X2、X3为非基变量，令 X1、X2、X3=0， X4 = 8、X5 = 1 对于D2 ，基变量为X1、X2，X3、X4、X5为非基变量，令 X3、X4、X5 =0， X1 = -13/4 、X2=15/4

管理运筹学第二章线性规划的图解法

管理运筹学第二章线性规划的图解法

02
图解法的基本原理
图解法的概念
图解法是一种通过图形来直观展示线性规划问题解的方法。它通过在坐标系中绘 制可行域和目标函数，帮助我们理解问题的结构和最优解的位置。
图解法适用于线性规划问题中变量和约束条件较少的情况，能够直观地展示出最 优解的几何意义。
图解法的步骤
确定决策变量和目标函数
明确问题的决策变量和目标函数，以便在图 形中表示。
目标函数是要求最小化或最大化的函数，通常表示为 $f(x) = c_1x_1 + c_2x_2 + ldots + c_nx_n$。
04
约束条件是限制决策变量取值的条件，通常表示为 $a_1x_1 + a_2x_2 + ldots + a_nx_n leq b$或 $a_1x_1 + a_2x_2 + ldots + a_nx_n = b$。
LINDO是一款开源的线性规划求解器，用 户可以免费使用。
软件工具的使用方法
Excel
用户需要先在Excel中设置好线性规划模型，然后使 用“数据”菜单中的“规划求解”功能进行求解。
Gurobi/CPLEX/LINDO
这些软件通常需要用户先在软件界面中输入线性规划 模型，然后通过点击“求解”按钮进行求解。
实例三：分配问题
总结词
分配问题是指如何根据一定的分配原则 或目标，将有限的资源分配给不同的需 求方，以最大化整体效益。
VS
详细描述
分配问题在实际生活中广泛存在，如物资 分配、任务分配等。通过图解法，可以将 分配问题转化为线性规划模型，并利用图 形直观地展示最优解的资源分配方案。在 分配问题中，通常需要考虑不同需求方的 重要性和优先级，以及资源的有限性等因 素，以实现整体效益的最大化。

2 线性规划

2 线性规划

第一节 线性规划问题及其数学模型
可加性假定：每个决策变量对目标函数和约
束方程的影响是独立于其他变量的，目标函 数值是每个决策变量对目标函数贡献的总和 连续性假定：线性规划问题中的决策变量应 取连续值。 确定性假定：线性规划问题中的所有参数都 是确定的参数。线性规划问题不包含随机因 素。
约 束 方 程
约束条件
变量约束
第一节 线性规划问题及其数学模型
线性规划问题隐含的假定： 比例性假定 可加性假定 连续性假定 确定性假定
比例性假定：决策变量变化引起的目标函数
的改变量和决策变量的改变量成比例，同样， 每个决策变量的变化引起约束方程左端值的 改变量和该变量的改变量成比例
≥0
=
≥0
第一节 线性规划问题及其数学模型
标准型的简缩形式
max Z
c x
j j 1
n
j
s .t
n aij x j bi , i 1,2 , , m j 1 x j 0 , i 1,2 , , m

第一节 线性规划问题及其数学模型
或
松弛变量
a i 1 x 1 a i 2 x 2 a in x n bi
a i 1 x1 a i 2 x 2 a in x n x p bi , x p 0
剩余变量
练习
例:将下列线性规划问题划为标准形式： min Z = x1+3x2
s.t.
6x1+7x28 -x1+3x2-6 x1-x2=3 x10
可行域无界
x1+2x2 10 x2 0 x1
可行域无界
x2
x1 0

第二章线性规划

第二章线性规划
线性规划研究的问题主要有以下两类。 (1) 给出一定量的人力、物力、财力等资源，如何统筹规划这些有限资源完成最大 任务。 (2) 给定一项任务，如何运筹规划，合理安排，以最少资源来完成它。 线性规划要研究的两类问题中都有一个限制条件：第一类问题是给出一定量的人力、 物力和财力等资源；第二类问题是给定一项任务。这种限制条件可以用一组线性方程组或 线性不等式组来描述。限制条件所要达到的结果称为“目标”，第一类问题的目标是利用有 限资源完成最大任务，第二类问题的目标是以最少资源完成给定任务。可以用一个线性函 数来描述这种目标，称这个线性函数为目标函数。 由此可见，各类问题尽管限制条件与目标不相同，但规划的目的就是使这些资源发挥 最大限度的作用，从而完成最多最大的任务。换句话说，也就是资源的最优利用问题。用 数学形式表示的话，规划的目的就是在给定的限制条件(或称约束条件)下，求目标函数的极 值问题(包括极小值和极大值)。 下面用一个例题来说明线性规划问题的特点。
0.1x1 0.17x2 0.14x3 0.22x4 0.07x5 ≥140 000 平均信用度不低于 6，即
非负约束，即
(11x1 8x2 10x3 4x4 10x5 ) /(5106 ) ≥6 xi ≥ 0 ， i =1, 2, 3, 4, 5
综上所述，该问题的数学模型可以表示为
16
第二章 线性规划
三、人力资源问题的数学模型
例 2-4 某商场因为每天顾客的数量不同，所以每天需要的营业员人数也不同。经过统 计分析，商场对营业员的需求量如表 2-5 所示。按照规定，营业员每周工作五天后，连续 休息两天。问：应如何安排营业员的作息，既能满足工作需要，又使得雇佣的营业员人数 最少？
表 2-3 产品规格
产品名称 X

最优化方法：第2章 线性规划


Z=CBB-1b+(σm+1,
σm+k ,
xm+1
σn
)
CB B-1b+σ m+k
xn
因为 m+k 0，故当λ→+∞时，Z→+∞。
用初等变换求改进了的基本可行解
假设Ｂ是线性规划 maxZ=CX,AX=b,X 0的可行基，则
AX=b
(BN)
XB XN
b
(I,B-1 N)
➢ 若在化标准形式前，m个约束方程都是“≤”的形式， 那么在化标准形时只需在一个约束不等式左端都加上一个松弛变 量xn+i (i=12…m)。
➢ 若在化标准形式前，约束方程中有“≥”不等式， 那么在化标准形时除了在方程式左端减去剩余变量使不等式变 成等式以外，还必须在左端再加上一个非负新变量，称为 人工变量．
单纯形法简介
考虑到如下线性规划问题 maxZ=CX AX=b X 0
其中Ａ一个m×n矩阵，且秩为m，ｂ总可以被调整为一 个m维非负列向量，Ｃ为n维行向量，Ｘ为n维列向量。
根据线性规划基本定理： 如果可行域Ｄ={ Ｘ∈Ｒn / ＡＸ=ｂ，Ｘ≥0}非空有界， 则Ｄ上的最优目标函数值Ｚ=ＣＸ一定可以在Ｄ的一个顶 点上达到。 这个重要的定理启发了Dantzig的单纯形法， 即将寻优的目标集中在D的各个顶点上。
非基变量所对应的价值系数子向量。
要判定 Z=CBB-1b 是否已经达到最大值，只需将
XB =B-1b-B-1NX N 代入目标函数，使目标函数用非基变量
表示，即：
Z=CX=(CBCN
)
XB XN
=CBXB +CNXN =CB (B-1b-B-1NXN )+CNXN

第二章线性规划的图解法


➢ 答案：
X2 ➢ 最优解为： x1 ＝15 ，x2＝10 40 ➢ 最优值为：z*＝2500×15+1500×10
➢
30
＝52500
3x2＝75
20
（15，10）
10
O
10
20
30
40
50 X1
3x1+2x2＝65
2x1+x2＝40
五、线性规划问题解的情况
➢ 例1.5的最优解只有一个，这是线性规划问题 最一般的解的情况，但线性规划问题解的情 况还存在其它特殊的可能：无穷多最优解、 无界解或无可行解。
... am1x1+am2x2 +…+amnxn≤( =, ≥ )bm x1 ，x2 ，… ，xn ≥ ( ≤) 0 或无约束
xj为待定的决策变量； cj为目标函数系数，或价值系数、费用系数； aij为技术系数； bj为资源常数，简称右端项； 其中i＝1，2，…m； j＝1，2，…n
可以看出，一般LP模型的特点： A、决策变量x1，x2，x3，……xn表示要寻求
O
100 200 300
X1
3、无界解的情况
➢若将例1.5的线性规划模型中约束条件1、2的 不等式符号改变，则线性规划模型变为：
➢ 目标函数：Max z= 50x1+100 x2 约束条件：x1+x2 ≥ 300 2x1+x2 ≥ 400 x2≤250 x1 ≥0， x2 ≥0
B、定义决策变量；
C、用决策变量的线性函数形式写出所要追求 的目标，即目标函数；
D、用一组决策变量的等式或不等式来表示在 解决问题过程中所必须遵循的约束条件。
三、线性规划的数学模型
1、LP模型的一般形式 目标函数：

第二章 线性规划

第二章线性规划一.线性规划所研究的问题可以归结为两方面：1）在现有的资源条件下，如何充分利用资源，使目标完成的最好。

（求极大问题）.2)在给定的目标和任务下，以最少的资源消耗或代价，去实现目标。

（求极小化问题）。

二.线性规划的标准型：1.标准型： max z=c1x1+c2x2+…+c n x ns.t. a11x1+a12x2+…a1n x1n=b1a21x1+a22x2+…+a2n x2=b2…a m1x1+a m2x2+…a mn x n=b mx1,x2,…,x n≥02.线性规划变换方法：1）min转换为max 目标函数乘以(-1);2）对于≤引进松弛变量，将其变成取等号。

对于≥引进剩余变量，将其变成取等号。

3）将变量中的非正限制或无限制转化为非负限制。

3.二维线性规划的图解法：1）正法向量：由目标函数系数组成的与等值线垂直的向量，称正法向量。

2）等值线：使目标函数取相等值的所有点的集合，称等值线。

4.二维线性规划解的形式：1）唯一最优解 2)无穷多个最优解 3)有可行解但无最优解 4）无可行解5.线性规划解的概念：1）解：满足约束方程条件的点。

2）可行解：满足所有约束条件的点。

（非负性约束）3）最优解：使目标函数得到极值的可行解。

4）基：由最大的线性无关的列向量所构成的子矩阵。

（基向量/非基向量）5）基变量：与基向量对应的变量称为基变量。

同理（非基变量）6）基本解：X=（B-1b）（ 0 ）7）基本可行解：对于基本解，同时又满足非负性要求称基本可行解。

（可行解与基本解之间相交的部分）有图。

8）可行基：基本可行解对应的基。

9）基本最优解：满足目标函数要求的基本解。

10）退化基本可行解：基本可行解中存在取值为零的基变量。

6.线性规划的基本定理：1）如果一个线性规划问题存在可行解，则一定有基本可行解。

2）若线性规划问题存在最优解，则一定存在最优基本可行解。

三 线性规划的求解1.单纯形方法（消去发）：1）标准化处理。

第2章 线性规划(对偶问题)


对偶问题（或原问题）
目标函数为 Min W
n个
约束条件
＝
m个
变量
0 0 无约束
约束条件右端项cj 价值系数bi 约束条件的系数矩阵AT
例：
• 写出下面线性规划问 题的对偶问题：
• 1.
max Z 2x1 x2 3x3 x4
x1 x2 x3 x4 5
s.t.
2x1 x2 3x3
原问题（对偶问题）
目标函数 限定向量 价值向量 技术系数 约束条件 变量数目 约束条件个数 变量正负
对偶问题（原问题）
目标函数 价值向量 限定向量 技术系数 对偶变量 约束条件个数 对偶变量数目 约束条件
非对称形式的对偶问题
• 在原线性规划问题为Max型，且变量非负 的前提下：
1. 原问题约束条件是“”型
x1
x3
x4
1
4
x1, x3 0, x2 , x4无约束
• 解：根据上述对偶关 系，可以写出原问题 的对偶问题：
min W 5 y1 4 y2 y3
y1 2 y2 y3 2
s.t.
y1 y1
y2 1 3y2 y3
3
y1
y3
1
y1 0, yLeabharlann 0, y2无约束例：y1
0,
y3
0,
y2无约束
对偶的基本性质
• 原问题： Max Z=CTX
• 对偶问题： Min W=bTY
s.t. AXb X0
s.t. ATY C Y0
• ①对称性：对偶问题的对偶是原问题； • ②弱对偶性：若X是原问题的可行解，Y是
对偶问题的可行解，则CTX bTY
• 弱对偶性的证明： AX’ b X’TAT bT X’TATY’ bTY’
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
z0就是原问题 min z CX的最小值 例如求 min z 2x1 6x2 8x3 可化为求 max z 2x1 6x2 8x3
2019/11/23
13
(2)约束条件为“≤”型
对a21x1 a22 x2 a2n xn b2 则引入松弛变量s1, s1 0 则有a21x1 a22 x2 a2n xn s1 b2，且s1 0 如：2x1 6x2 8x3 5 原约束方程变为：2x1 6x2 8x3 s1 5，s1 0
授课内容
线性规划研究问题
模型的建立
线性规划的标准化变换 线性规划的图解法 线性规划解的概念
单纯形法
人工变量法
退化和循环
线性规划的应用
2019/11/23
1
线性规划研究问题
在现有的人、财、物等资源的条件下，研究如 何合理地计划、安排，可使得某一目标达到最 大，如产量、利润等。
在任务确定后，如何计划、安排，使用最少的 人、财、物等资源，去实现该任务，如使生产 成本、费用最少等。
1000x1 1500x2 1750x3 3250x4 4000
s.t
:


0.6x1 0.27x2 0.68x3 0.3x4 1 17.5x1 7.5x2 30x4 30

x1, x2, x3, x4 0
2019/11/23
线性
6
模型建立
确定决策变量：用变量取值表示可供选择的方案。 建立目标函数：找到目标值与决策变量的数量关系 确定约束条件：即决策变量所受到的外界条件的制 约。约束条件一般为决策变量的等式或不等式。 要求：目标函数与约束条件均是线性的，且目标函 数只能是一个。
3x1 2x2 65
st
:


2x1 x2 40 3x2 75
x1, x2 0,为整数
“Max”是英文单词“Maximize”的缩写；“st.”
是“subject to”的缩写。
2019/11/23
4
例2：如果有甲、乙、丙、丁四种食品，都含有不 同成分的维生素，其含量和单价如下表：

xij 0
2019/11/23
10
线性规划模型的标准化变换
标准型式的特征: 求目标函数的最大值 约束方程为等式方程 约束方程的右边非负 决策变量均非负
2019/11/23
11
标准形式：
n
max z c1x1 c2x2 cnxn max z cixi i1
b1,b2, bm 0 bj 0, j 1, 2, , m
2019/11/23
12
(1)对求目标函数最小值:
min z ci xi ,取z z i
则求 min z ci xi问题转为求 max z ci xi问题
i
当求出max z ci xi问题的最大值z0后，
a11x1 a12x2 a1nxn b1

s.t

a21x1 a22x2 a2nxn b2
n
ajixi bj , j 1, 2, , m
am1x1 am2x2 amnxn bm
i1
x1, x2 , xn 0 xi 0,i (1, , n)
(或

，或 ）b2
am1x1 am2 x2 amn xn (或 ，或 ）bm
约束方程
x1 , x2 , xn 0
非负约束
其中aij , bi , c j (i 1,2,, m; j 1,2,, n) 为已知常数
决策变量
2019/11/23
8
设有三个工厂B1、B2、B3，它们需要同一种原料，数量 分别是72吨、102吨、41吨，另外有三座仓库A1、A2、A3，可 以供应上述原料56吨、82吨、77吨，由于工厂和仓库位置不 同，单位运价不同，具体数据如下表，应如何安排运输
寻求在一定约束条件下使某个指标达到最优.
2019/11/23
2
例1:某工厂拥有ABC三种类型的设备，生产甲乙两
种产品。每件产品在生产中需要占用的设备机时， 获得的利润及设备可利用的时数如下表：
问题：如何安排生产可获得最大的总利润？
2019/11/23
3
Maxz 1500x1 2500x2
2019/11/23
14
(3)约束条件为“≥”型
对a21x1 a22 x2 a2n xn b2 则引入剩余变量s1, s1 0 则有a21x1 a22 x2 a2n xn s1 b2，且s1 0 如：2x1 6x2 8x3 5 原约束方程变为：2x1 6x2 8x3 s1 5，s1 0
16x23 8x31 16x32 24x33
x11 x12 x13 56

x21

x22

x23

82
s.t.
x11 x31

x21 x32

x31 x33

72 77

x12

x22

x32
102
x13 x23 x33 41
方案，才能使总运费最小？B1A14A2
16
A3
8
需求量 72
B2
B3
8
8
24
16
16
24
102
41
产量 56 82 77 215
2019/11/23
9
设xij表示由Ai运到Bj的数量,(i 1, 2, 3; j 1, 2, 3),
Z 表示总运费,数学模型为：
min Z 4x11 8x12 8x13 16x21 24x22
希望每天得到的维生素不少于规定的需要量，应如 何搭配各种食品才使所花费的费用最少？
2019/11/23
5
决策变量：x1 每天采购甲食品的数量，x2 每天采购乙食品的数量 x3 每天采购丙食品的数量，x4 每天采购丁食品的数量 目标函数：M 每天采购食品的费用
min M 0.8x1 0.5x2 0.9x3 1.5x4
2019/11/23
7
max（或min）z c1x1 c2 x2 cn xn
目标函数
maximum minimum
subject to
a11x1 a12 x2 a1n xn (或 ，或 ）b1
s.t

a21 x1

a22 x2
a2n xn