当前位置：文档之家 › 运筹学第二章

运筹学第二章

  • 格式：ppt
  • 大小：912.50 KB
  • 文档页数：49

下载文档原格式

  / 49

合集下载

运筹学第二章

运筹学第二章

CB XB
• 对应初始单纯形表中的单位矩阵I，迭代后的单纯
形
表中为B-1 项目 基变量 基变量 • 初始单纯形表中基变量Xs=b，迭代后的表中XB=B-1b XB XN Xs • 初始单纯形表中约束系数矩阵为 0 [A,I]=[B,N,I]，B XB b N I CB CN 迭代后的表中约束系数矩阵为 [B-1A,B-1I]=[B-1B,B-1N,B-1I]=[I,B-1N,B-1] 0

影 子 价 格

影子价格反映单纯形表中各个检验数的经济意 义。一般说对线性规划问题的求解是确定资源
的最优分配方案，而对于对偶问题的求解则是
确定对资源的恰当估价，这种估价直接涉及资 源的最有效利用。
计算下面线性规划问题各种资源的影 子价格：
影 子 价 格
2 x1 3 x2 1 0 0 4 x1 2 x2 1 2 0 x , x 0 1 2
影 子 价 格

影子价格是一种边际价格。Z

bi
yi

资源的影子价格实际上又是一种机会成本。随 着资源的买进卖出，其影子价格也将随之发生
变化，一直到影子价格与市场价格保持同等水
平时，才处于平衡状态。 生产过程中如果某种资源未得到充分利用时， 该种资源的影子价格为零；又当资源的影子价 格不为零时，表明该种资源在生产中已耗费完 毕。
1
j
B
1
B
1
1
1
i
i
L
j
k
Lj
Lj
Lk
对偶单纯行法的优点： 可以尽量避开人工变量，简化计算 进行灵敏度分析
对 偶 单 纯 行 法
对偶问题单纯行法的应用条件： 所有约束全是不等式； 问题标准化后，价值系数全非正

运筹学第2章

运筹学第2章
China University of Mining and Technology
-43-
运 筹 学
线性规划的对偶理论
性质3 最优性定理：如果 X 0 是原问题的可行解， 0 是其对偶 Y 问题的可行解，并且:
CX 0 BY 0
即: z w
则 X 0是原问题的最优解，Y 0是其对偶问题的最优解。
T
分别是原问题和对偶问题的可行解。 且原问题的目标函数值为
min W 20 y1 20 y2 s.t. y1 2 y2 1 2 y1 y2 2 2y1 3 y2 3 3 y1 2 y2 4 y1 , y2 0
Z CX 10
min W 20 y1 20 y2 s.t. y1 2 y2 1 2 y1 y2 2 2y1 3 y2 3 3 y1 2 y2 4 y1 , y2 0
(DP)
-41China University of Mining and Technology
-44China University of Mining and Technology
运 筹 学
线性规划的对偶理论
性质4 强(主)对偶性：若原问题及其对偶问题均具有可行解， 则两者均具有最优解，且它们最优解的目标函数值相等。
还可推出另一结论：若一对对偶问题中的任意一个有最优解， 则另一个也有最优解，且目标函数最优值相等；若一个问题 无最优解，则另一问题也无最优解。 一对对偶问题的关系，有且仅有下列三种： 1. 都有最优解，且目标函数最优值相等； 2. 两个都无可行解； 3. 一个问题无界，则另一问题无可行解。
-1-
运 筹 学
学习要点： 1. 理解对偶理论，掌握描述一个线性规划问题 的对偶问题。 2. 能够运用对偶单纯形法来求解线性规划问题。 3. 会用互补松弛条件来考虑一对对偶问题的界。

运筹学第二章

运筹学第二章

例2.4：将以下线性规划问题转化为 标准形式
Max s.t. Z = 3 x1 - 5 x2 + 8 x3 2x1 + 2x2 - x3 = 15.7
4 x1
+ 3x3 = 8.9
x1 + x2 + x3 = 38 x2 , x3 ≥ 0
4.右端项有负值的问题：
在标准形式中，要求右端项 必须每一个分量非负。当某一个 右端项系数为负时，如 bi<0，则 把该等式约束两端同时乘以-1， 得到：
产品甲 设备A 3 产品乙 2 设备能力 （h） 65
设备B
设备C 利润（元/件）
2
0 1500
1
3 2500
40
75
问：如何安排生产计划，才能使制药厂利润最大？
解：设变量 xi为第i种（甲、乙）产品的生 产件数（i＝1，2）。根据前面分析，可 以建立如下的线性规划模型： Max
z = 1500 x1 + 2500 x2
MinZ=∑xi
i=1
X6 +
x1 x1 + x2 x2 + x3 x3 + x4 x4 + x5 x5 + x6
≥ 8 ≥ 12
≥ 10
≥ 8 ≥ 6 ≥ 4
二、线性规划模型的一般形式
目标函数 s.t.
产品对资源的 单位消耗量
利润系数
Max(Min)z=c1x1+c2x2+……+cnxn
a11x1+a12x2+……+a1nxn≥(=、≤)b1 a21x1+a22x2+……+a2nxn≥(=、≤)b2 …… am1x1+am2x2+……+amnxn≥(=、≤)bm

运筹学第2章：线性规划的对偶理论

运筹学第2章：线性规划的对偶理论

目
标函数求极小时取“≥”号
注：对称形式与线性规划标准型是两种不同的形 式，对称形式中约束条件的符号由目标函数决定
从以下方面比较(LP1)与(LP2)：
原问题
对偶问题 约束系数矩阵的转 臵 目标函数中的价格 系数向量 约束条件的右端项 向量 Min w=Y’b A’Y≥C’ Y≥0
A
b C 目标函数 约束条件 决策变量
非基变量 基变量
XB
0 b Xs C j - zj B
XN
N
Xs
I
0
初始 单纯形表
非基变量
CB
CN
基变量
最终
单纯形表
CB
XB
XB B-1b Cj - zj
I 0
Xs B-1 N B-1 CN-CBB-1N -CBB-1
XN
若B-1b为最优解，则
CB CB ( B 1B) 0 C N CB B N 0 CB B 1 0
令 y 2 y 2 , y3 y3 y3 ，则
min 2 y1 y2 4 y3
2 y1 3 y2 y3 1 3 y y y 4 1 2 3 s.t. 5 y1 6 y2 y3 3 y1 0, y2 0, y3无约束
n j 1 m j j
C X Y b, 即 c j x j y i bi
j 1 i 1
__
__
n
m
c x ( a
j 1 m i 1 n i i i 1 i 1 j 1
n
m
ij
yi ) x j aij x j yi ( a ji yi c j )
例1

运筹学第2章 单纯形法

运筹学第2章 单纯形法

所有检验数 j 0 ，则这个基本可行解是最优解。
n
z z0 j x j
j m 1
m
j ciaij c j =CTBa j c j
i 1
m
m
z0 c j x j = cibi =CBT b
j 1
i 1
✓对于求目标函数最小值的情况，只需 σj≤0
0
XB
b
x1
-1 x5 0
0
0 x4 3
1
-3 0
0
00
x2
x3
x4
0
-2 0
2
-2 1
0 10
-1 bi/aik
x5
1
0
0
29 2020/3/4
2、无界解
在求目标函数最大值的问题中，所谓无界解是指在约束条件 下目标函数值可以取任意的大。
•存在着一个小于零的检验数，并且该列的系数向量的每个元素 都小于或等于零，则此线性规划问题是无界的，一般地说此类
2x1 x2 x3 x5 2
s.t. x1 2x2
x4
3

x1,
x2 , x3, x4 , x5 0
✓添加人工变量x5来人为的创造一个单位矩阵作为基 ✓M叫做罚因子，任意大的数。 ✓人工变量只能取零值。必须把x5从基变量中换出去，否 则无解。
cj
3
2
00
CB XB
2020/3/4
14
(2)出基变量和主元的确定——最小比值规则
min

bi aik
aik

0


bl alk
确定出基变量的方法：把已确定的入基变量在各约束方程中的正的系数

运筹学02-单纯形法

运筹学02-单纯形法

反之，若经过迭代，不能把人工变量都变
为非基变量，则表明原LP问题无可行解。
19
第2章
单纯形法
2.3 人工变量法
2.3.1 大M法
在原问题的目标函数中添上全部人工变量，并令其系数 都为-M，
而M是一个充分大的正数。即
max z = c1x1 + c2x2 + c3x3 + … + cnxn – M( xn+1 + xn+2 +…+ xn+m )
思路：由一个基本可行解转化为另一个基本可行解。 等价改写为 目标方程 max z max z = 3x1+5x2 z -3x1 -5x2 = 0 z -3x1 -5x2 x1 +x3 x1 +x3 = 8 2x2 +x4 2x2 +x4 = 12 s.t. s.t. 3x1+4x2 +x5 3x1 + 4x2 +x5 = 36 x1 ， x2 ，x3，x4，x5 x1 ， x2 ，x3，x4，x5 ≥ 0
以主列中正值元素为分母，同行右端常数为分子，求比值；
6
第2章
单纯形法
2.1 单纯形法的基本思想
(Ⅰ)
用换基运算 将X0 转化为 另一个基本 可行解 X1。
z- 3x1 -5x2 = 0 0 换基运算—— x1 +x3 = 8 ① 方程组的初等变换 目的是把主列变为 22x2 +x4 = 12 ② 单位向量：主元变 3x1 + 4x2 +x5 = 36 ③ 为1，其余变为0。 X0 = ( 0, 0, 8, 12, 36 )T z0 = 0
⑴ 当前基：m阶排列阵

运筹学第二章线性规划的对偶理论


(5.5) (5.6)
4.3 对偶问题的基本性质
证： 设B是一可行基，于是A=(B,N)
max z=CBXB+ CNXN BXB+BXN +Xξ=b X,XB,Xξ ≥0
其中Yξ=(Yξ1, Yξ2)
min ω =Yb YB－Yξ1=CB YN－Yξ2=CN Y, Yξ1 Yξ2 ≥0
(5.5) (5.6)
x1﹐x2 ≥0
关系？
对原模型设： 1 2
A= 4 0 b=(8,16,12)T C=(2，3) 04
X=（x1，x2）T Y=（y1，y2 ，y3 ） 则可得:
4.1 对偶问题的提出
min ω=8 y1+16y2 +12y3
y1+4y2
≥2
2 y1 +4y3≥3
与
y1 ， y2 ，y3≥0 12
max z＝2x1+3x2 x1＋ 2x2 ≤8
4x1
≤16
4x2 ≤12
x1﹐x2 ≥0
有何关 系？
对愿模型设： A= 4 0 04
b=(8,16,12)T C=(2，3)
X=（x1，x2）T
Y=（y1，y2 ，y3 ） 则可得:
max z=CX AX≤b （5.1） 和
min ω =Yb YA ≥ C （5.2）
120
A=
1 -3
0 2
1 1
1 -1 1
b=(2,3,-5,1)T C=(5,4, 6)
确定约束条件
YA
C
x1 ≥0 ﹐x2≤0, x3 无约束
解：因原问题有3个变 于是 量，4个约束条件， 所以对偶问题4个 变量，3个约束条

运筹学第2章-线性规划的对偶理论

❖ 影子价格不是市场价格，而是在现有技术和管理条件下， 新增单位资源所能够创造的价值，是特定企业的一种边 际价格；不同企业或同一企业不同时期，同种资源的影 子价格可能不同；当市场价格高于影子价格，可以卖出； 相反，则应买进，以获取更大收益
Ma例x：Z （ 2第x一1 章3例x22）
2 x1 2 x2 12
当原问题和对偶问题都取得最优解时，这 一对线性规划对应的目标函数值是相等的：
Zmax=Wmin
二、原问题和对偶问题的关系
1、对称形式的对偶关系
（1）定义：若原问题是
MaxZ c1 x1 c2 x2 cn xn
a11x1 a12 x2 a1n xn b1
s.t.a21
x1
a22
二、 手工进行灵敏度分析的基本原则 1、在最优表格的基础上进行； 2、尽量减少附加计算工作量；
5y3 3
，y
2
3
0
（用于生产第i种产 品的资源转让收益不 小于生产该种产品时 获得的利润）
对偶变量的经济意义可以解释为对工时及原材 料的单位定价 ；
若工厂自己不生产产品A、B和C，将现 有的工时及原材料转而接受外来加工时， 那么上述的价格系统能保证不亏本又最富 有竞争力（包工及原材料的总价格最低）
内，使得产品的总利润最大 。
MaxZ 2x1 3x 2
2x1 2x2 12
s.t.54xx12
16 15
x1, x 2 0
它的对偶问题就是一个价格系统，使在平衡了 劳动力和原材料的直接成本后，所确定的价格系统 最具有竞争力：
MinW 12y1 16y2 15y3
2y1 4y2
2
s.t.2y1y，1y
y1, y2, , ym 0

运筹学第2章单纯形法

==８ ==6
① ② ③
－２Ｘ４＋Ｘ５ ＝１２
得到新的基本可行解 X1 =(0,6,8,0,12)T
(1)、决定进基变量：1=--3, X1进基 (2)、决定离基变量：最小比值规则来确定主 元与离基变量.
则Xl为进基变量。 MIN(8/1,-,12/3)=12/3 此时可以确定X5为离基变量
Z
X(0) =(0, 0, 10, 15 )T
Z0 =0
Z-30X1-20X2 =0 选中X1从0↗，X2 =0 X3=10-(-X1 )0
X4=15-(-3X1 )0 求X1， X1→+ ,Z→+
2.2.3 单纯形法计算之例
2-3 人工变量法 (Artificial Variable)
+1/2X4
+X5 =42 =6
X3 +2/3X4 -1/3X5 =4
X2 +1/2X4
X1 -2/3X4+1/3X5=4 令X4 =X5 =0 X =(4, 6, 4, 0, 0)T Z =42
。此时4=1/2,
Z值不 再增大了,X值是最优基本解
5
=1,
* T * 即:X =(4,6) ,Z =42
检验数
当目标方程中基变量系数全为0时，非基 变量的系数可以作为检验当前的基本可 行解是否最优的标志，称之为检验数。
(2)、判定解是否最优 Z-3X1-5X2 =0 当X1从0↗或X2从0↗ Z从0↗ ∴ X0 不是最优解
(3)、由一个基可行解→另一个基可行解。 ∵ -5<-3 选X2从0↗，X1 =0 X3 =8 X4 =12-2X2 0 X2 12/2
N
沿边界找新 的基本可行解
结束

运筹学 第二章

8
由例1的求解的过程中，我们观察到如下事实： 由例 的求解的过程中，我们观察到如下事实： 的求解的过程中 1）若某一个线性规划问题有最优解，则一定有一个可行域的 ）若某一个线性规划问题有最优解， 顶点对应一个最优解。 顶点对应一个最优解。 2）线性规划存在有无穷多个最优界的情况。 ）线性规划存在有无穷多个最优界的情况。 如例1中将目标函数改为 如例 中将目标函数改为 max z = 50 x 1 + 50 x 2 , 则代表目标函数 的直线平移到最优位置后， 重合。 的直线平移到最优位置后， 与直线 x 1 + x 2 = 300 重合。 3）线性规划存在无界解，即无最优解的情况。 如 ）线性规划存在无界解，即无最优解的情况。 x2 • 目标函数： 目标函数： max z = x + x , 约束条件： 约束条件： x 1 − x 2 ≤ 1, − 3 x 1 + 2 x 2 ≤ 6, x 1 ≥ 0, x 2 ≥ 0. 此时称该问题无界！ 原因： 原因：某些约束条件没有考虑到
第二章 线性规划的图解法
几种常见的典型的线性规划问题在管理上的应用: 几种常见的典型的线性规划问题在管理上的应用: 1.合理利用线材问题: 现有一批长度一定的钢管， 1.合理利用线材问题: 现有一批长度一定的钢管， 由于生产的 合理利用线材问题 需要， 需要， 要求截出不同规格的钢管若干。 试问应如何下料， 要求截出不同规格的钢管若干。 试问应如何下料，既满足了 生产的需要，又使得使用原材料钢管最少。 生产的需要，又使得使用原材料钢管最少。 最少 2.配料问题: 用若干种不同价格不同成分含量的原料， 2.配料问题: 用若干种不同价格不同成分含量的原料，用不 配料问题 同的配比混合调配出一些不同的规格的产品， 同的配比混合调配出一些不同的规格的产品， 在原料供应量的限 制和保证产品的成分的含量的前提下，如何获取最大的利润。 制和保证产品的成分的含量的前提下，如何获取最大的利润。 最大的利润 3.投资问题: 从不同的投资项目中选出一个投资方案， 3.投资问题: 从不同的投资项目中选出一个投资方案，使得 投资问题 投资回报为最大 最大。 投资回报为最大。 4.产品生产计划: 合理充分利用厂里现有的人力、物力、财 4.产品生产计划: 合理充分利用厂里现有的人力、物力、 产品生产计划 做出最优的生产计划，使得工厂获利最大 最大。 力，做出最优的生产计划，使得工厂获利最大。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
W 8
Production rat (units per week) for windows ate
7 6 5 4 3 2 1 Origin
A product mix of D = 4 and W = 6 (4, 6)
产 品 组 合 图 形
A product mix of D = 2 and W = 3 (2, 3)
Chapter 2. Linear Programming: Basic Concepts
2
Table of Contents
Three Classic Applications of LP (Section 2.1) (线性规划的三个经典应用 第2.1节]) 线性规划的三个经典应用[第 节 线性规划的三个经典应用 The Wyndor Glass Company Product Mix Problem (Section 2.2) (伟恩德玻璃制品公司产品 伟恩德玻璃制品公司产品 组合问题[第 节 组合问题 第2.2节]) Formulating the Wyndor Problem on a Spreadsheet (Section 2.3) (在电子表格上建立韦 在电子表格上建立韦 恩德公司问题的模型[第 节 恩德公司问题的模型 第2.3节]) The Algebraic Model for Wyndor (Section 2.4) (韦恩德公司问题的数学模型 第2.4节]) 韦恩德公司问题的数学模型[第 节 韦恩德公司问题的数学模型
An 8-foot glass door with aluminum framing. (8英尺的 英尺的 铝框玻璃门) 铝框玻璃门 A 4-foot by 6-foot double-hung, wood-framed window. (4英尺 英尺的双把木框门 英尺*6英尺的双把木框门 英尺 英尺的双把木框门)
市场的变动导致不同时期生产不同类型的胶 合板所带来的利润也不同 生产资源的有限性 Considered limited resources, and determined optimal mix of plywood products. (考虑了有限资源，并确定了胶合 考虑了有限资源， 考虑了有限资源 板产品的最优组合) 板产品的最优组合 Increased overall profitability of company by 20%. (公司的总利润增加了 公司的总利润增加了20%) 公司的总利润增加了
Chapter 2. Linear Programming: Basic Concepts
9
Wyndor Glass Co. Product Mix Problem
Should they go ahead with launching these two new products? If so, what should be the product mix?
W
8
负 约 束
Production rate for windows e
非
6
4
2
0
2
4
6
8
D
Production rate for doors
Chapter 2. Linear Programming: Basic Concepts
13
Wyndor Glass Co. Product Mix Problem
Boundary Line for Constraint 3D + 2W ≤ 18 (约束条件边界线 约束条件边界线) 约束条件边界线
Chapter 2. Linear Programming: Basic Concepts
Chapter 2. Linear Programming: Basic Concepts
5
Three Classic Applications of LP
Personnel Scheduling at United Airlines (联合航空公司的员工排程 联合航空公司的员工排程) 联合航空公司的员工排程
-2
-1
0 -1 -2
1
2 3 4 5 6 7 8 Production rate (units per week) for doors
D
Chapter 2. Linear Programming: Basic Concepts
12
Wyndor Glass Co. Product Mix Problem
The SDM system uses LP to coordinate the supply, distribution, and marketing of each of Citgo’s major products throughout the United States. (SDM系统使用 来协调全美 系统使用LP来协调全美 系统使用 来协调全美Citgo石油 石油 公司主要产品的供应、配送和营销) 公司主要产品的供应、配送和营销 The resulting reduction in inventory added $14 million annually to Citgo’s profits. (库存成本的 库存成本的 下降每年为公司增加1400万美元的收入 万美元的收入) 下降每年为公司增加 万美元的收入
Chapter 2. Linear Programming: Basic Concepts
6
Three Classic Applications of LP
Planning Supply, Distribution, and Marketing at Citgo Petroleum Corporation (Citgo石油公 石油公 司的供应、配送和营销计划) 司的供应、配送和营销计划
Operations Research
运筹学 Operations Research
潘燕春 博士 深圳大学管理学院 pan_yc@
Chapter 2. Linear Programming: Basic Concepts
1
Operations Research
Chapter 2. Linear Programming: Basic Concepts 第二章. 线性规划: 基本概念
公司是否应该生产这 两个新产品？ 两个新产品？如果生 产，两个新产品的生 产组合如何？ 产组合如何？
Chapter 2. Linear Programming: Basic Concepts
10
Wyndor Glass Co. Product Mix Problem
Algebraic Model for Wyndor Glass Co. (韦恩德公司问题的数学模型 韦恩德公司问题的数学模型) 韦恩德公司问题的数学模型 Let D = the number of doors to produce (门的生产量 门的生产量) 门的生产量 W = the number of windows to produce (窗的生产量 窗的生产量) 窗的生产量
W 8 D=4
D≤4 非 负 约 束
Production rate for windows
6
4
2
0
2
6 4 Production rate for doors
8
D
Chapter 2. Linear Programming: Basic Concepts
14
Wyndor Glass Co. Product Mix Problem
Chapter 2. Linear Programming: Basic Concepts
3
Table of Contents
The Graphical Method Applied to the Wyndor Problem (Section 2.5) (韦恩德公司问题的图形方 韦恩德公司问题的图形方 法[第2.5节]) 第 节 Using the Excel Solver with the Wyndor Problem (Section 2.6) (使用 使用Excel Solver解决韦 使用 解决韦 恩德公司问题[第2.6节]) 恩德公司问题 第 节 A Minimization Example—The Profit & Gambit Co. (Section 2.7) (一个最小化的例子 一个最小化的例子——利博公 一个最小化的例子 利博公 司广告组合问题[第 节 司广告组合问题 第2.7节])
Chapter 2. Linear Programming: Basic Concepts
4
Three Classic Applications of LP
Product Mix at Ponderosa Industrial (潘得 潘得 罗索工业公司的产品组合问题) 罗索工业公司的产品组合问题
Maximize P = $300D + $500W subject to (约束 约束) 约束 D≤4 2W ≤ 12 3D + 2W ≤ 18 and D ≥ 0, W ≥ 0.
Chapter 2. Linear Programming: Basic Concepts
运筹学 线性规划
11
Wyndor Glass Co. Product Mix Problem
Production rate for windows W 8
2 W = 12
2W 非 ≤ 12 负 约 束
6
4
2
0
2 4 Production rate for doors
6
8
D
Chapter 2. Linear Programming: Basic Concepts
15
Wyndor Glass Co. Product Mix Problem