当前位置：文档之家 › 运筹学2 -对策论

运筹学2 -对策论

  • 格式：ppt
  • 大小：1.08 MB
  • 文档页数：31

下载文档原格式

  / 31

合集下载

运筹学2

运筹学2

• 从当前极点进化到另一极点，既使目标函数值上升，有保 达点可行
– 进基变量：最小检验数规则 – 离基变量：最小比值规则
z 3 x1 2 x2 x x 1 3 s.t. ( I ) 2 x2 x4 2 x 3x x5 1 2 x1 , x2 , x3 , x4 , x5 0
（1） 进基变量的相持及其突破
进基变量按最小检验数规则选定，如果出现两个或更多个 σj<0同时达到最小而相持时,则应： 从相持的检验数σk 所对应的变量 xk中,任选一个 作为进基量。
（2） 离基变量的相持及其突破——退化与循环
从相持的离基变量中，选择下标最大者作为离基 变量。
0 x4 0 1 0 0
0 x5 0 0 1 0
比 值
x1 x4 x5
6 8 6 18
4 2 min
3 0 2
x1 x4 x2
6
4
2 22
1 0 0 0
0 0 1 0
1 4/3 -2/3 5/3
0 1 0 0
0 -2/3 1/3 2/3
X*= (6, 2, 0, 4, 0)T,
z* = 22
第三节 ห้องสมุดไป่ตู้他法则
进基（最小检验数规则）： 在负检验数中选择最小的进基。 min{σ j︱σj<0 } = σk → xk 进基 min{ -3，-2 } = -3= σ1 → x1 进基 由① ② ③有 ≥ 0 → x1 ≤ 6/1 x3 = 6-x1 ≥0 x4 = 8 x5 = 18 -2x1 ≥ 0 → x1 ≤ 18/2
2.2.3 单纯形法的计算过程 1° 把LP问题化为标准形
max Z 3 x1 2 x 2

运筹学Ⅱ理解练习知识题(付答案解析)

运筹学Ⅱ理解练习知识题(付答案解析)

练习题（博弈论部分）： 1、化简下面的矩阵对策问题：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=2504363432423622415332412A2、列出下列矩阵对策的线性规划表达式⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡------=334133313A3、用线性方程组解 “齐王赛马”的纳什均衡。

解：已知齐王的赢得矩阵为A =⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡------3111111311111131111113111111311111134、已知对策400008060A ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦的最优解为：)133,134,136(),134,133,136(**==Y X ，对策值1324*=V ，求以下矩阵对策的最优解和对策值⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=203820442020202032'A5、设矩阵对策的支付矩阵为：353432323A ⎡⎤⎢⎥=-⎢⎥⎢⎥⎣⎦，求其策略和策略的值。

6、求解下列矩阵对策的解：123312231A ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦练习题（多属性决策部分）：1、拟在6所学校中扩建一所，经过调研和分析，得到目标属性值如下表（费用和学生就读距离越小越好）试用加权和法分析应扩建那所学校？讨论权重的选择对决策的影响！2、拟选择一款洗衣机，其性能参数（在洗5Kg 衣物的消耗）如下表，设各目标的重要性相同，采用折中法选择合适的洗衣机3、六方案四目标决策问题的决策矩阵如下表,各目标的属性值越大越好，{0.3,0.2,0.4,0.1}TW =请用ELECTRE法求解，折中法，加权法求解排队论练习：例1：在某单人理发馆，顾客到达为普阿松流，平均到达间隔为20分钟，理发时间服从负指数分布，平均时间为15分钟。

求：(1)顾客来理发不必等待的概率；(2)理发馆内顾客平均数；(3)顾客在理发馆内平均逗留时间；(4)如果顾客在店内平均逗留时间超过1.25小时，则店主将考虑增加设备及人员。

问平均到达率提高多少时店主才能做这样考虑呢？例2：某机关接待室只有一位对外接待人员，每天工作10小时，来访人员和接待时间都是随机的。

运筹学第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. 会用互补松弛条件来考虑一对对偶问题的界。

运筹学 胡运权 第二章

运筹学 胡运权 第二章
《运筹学》 运筹学》
第1页
第二章 线性规划的对偶理论
一、问题的提出: 设用两种原料（A、B）
生产三种产品的一个生产计划问题
m f ( x) = x1 + 2x2 + 4x3 ax x1 + 2x2 + 2x3 ≤ 25 s.t. 2x1 + x2 + 2x4 ≤15 x1, x2 , x3 ≥ 0
华东师范大学
《运筹学》 运筹学》
第11页 11页
弱对偶性的推论： 对偶性的推论：
max问题的任何可行解目标函数值是其对偶min问 题目标函数值的下限； min问题的任何可行解目标 函数值是其对偶max问题目标函数值的上限。 如果原max(min)问题为无界解，则其对偶 min (max) max(min) 问题无可行解。 如果原max(min)问题有可行解，其对偶 min (max) 问题无可行解，则原问题为无界解。 存在原问题和对偶问题同时无可行解的情况。
华东师范大学
14 December 2010
《运筹学》 运筹学》
第10页 10页
1. 弱对偶性定理（P55） 对偶问题(min)的任何可行解Y0，其目 标函数值 bTY0 总是不小于原问题(max) 的任何可行解X0的目标函数值CTX0, 即 CTX0 ≤ bTY0
14 December 2010
14 December 2010
华东师范大学
《运筹学》 运筹学》
第8页
表2.1 对偶变换的规则
原问题(max,≤) ≤ 原问题 系数矩阵 A 目 标 系数 C 常数 项 b 第 i 行约束条件为 ≤ 型 第 i 行约束条件为 ≥ 型 第 i 行约束条件为 = 型 决策变量 xj ≥ 0 决策变量 xj ≤ 0 决策变量 xj ±不限 ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ ⇔ 对偶问题(min,≥) ≥ 对偶问题 系数矩阵 AT 常数项 b 目 标 系数 C 对偶变量 yi ≥ 0 对偶变量 yi ≤ 0 对偶变量 yi ±不限 第 j 行约束条件为 ≥ 型 第 j 行约束条件为 ≤ 型 第 j 行约束条件为 = 型

运筹学(二)

运筹学(二)
C
CB
b
CN
0
CB CB
xB XB
XB
B B
CB CB B1B
1
XN
B 1 N
CN CB B1 N
XS
B 1
CB B 1
B 1b
cz
若XB为最优基变量，则对应的目标函数值为： z CB XB CN XN 0 X S CB B1b
且对于上表中各检验数，有：
min W Y b
可见，当原问题得到最优解时，其松弛变量检验数的相反数 CB B 是该问题的对偶问题的一个可行解。
1
例：
原问题
对偶问题
max z 2 x1 x2
同样，少生产一件I产品，则可以 节省设备A、设备B和调试工序0、 6、1个小时，把这些资源出租， 就可以获得租金0y1+6y2+y3
但少生产一件I产品，则 丧失了2元的利润
所以，只有当 6 y2 y3 2
5 y1 2 y2 y3 1
总的出让费 最低出让费即为：
15 y1 24 y2 5 y3
max z c1 x1 c2 x2 c3 x3 c3 x3
a11 x1 a12 x2 a13 x3 a13 x3 b1 a21 x1 a22 x2 a23 x3 a23 x3 b2 st . a21 x1 a22 x2 a23 x3 a23 x3 b2 a31 x1 a32 x2 a33 x3 a33 x3 b3 x1 , x2 , x3 , x3 0
(1 ) (2) (3)
约束（2）可以用以下两个约束来表示：
a21 x1 a22 x2 a23 x3 a23 x3 b2 (2 -1) a21 x1 a22 x2 a23 x3 a23 x3 b2 (2 - 2)

《运筹学》(第二版)课后习题参考答案

《运筹学》(第二版)课后习题参考答案
表1—17 家具生产工艺耗时和利润表
生产工序
所需时间（小时）
每道工序可用时间（小时）
1
2
3
4
5
成型
3
4
6
2
3
3600
打磨
4
3
5
6
4
3950
上漆
2
3
3
4
3
2800
利润（百元）
2.7
3
4.5
2.5
3
解：设 表示第i种规格的家具的生产量（i=1,2,…,5），则
s.t.
通过LINGO软件计算得： ．
11．某厂生产甲、乙、丙三种产品，分别经过A，B，C三种设备加工。已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产品的利润如表2—10所示。
－10/3
－2/3
0
故最优解为 ，又由于 取整数，故四舍五入可得最优解为 , ．
（2）产品丙的利润 变化的单纯形法迭代表如下：
10
6
0
0
0
b
6
200/3
0
1
5/6
5/3
－1/6
0
10
100/3
1
0
1/6
－2/3
1/6
0
0
100
0
0
4
－2
0
1
0
0
－20/3
－10/3
－2/3
0
要使原最优计划保持不变，只要 ，即 ．故当产品丙每件的利润增加到大于6.67时，才值得安排生产。
答：（1）唯一最优解：只有一个最优点；
（2）多重最优解：无穷多个最优解；
（3）无界解：可行域无界，目标值无限增大；

运筹学(二)


x1＝0， x2＝400，s1＝－ ＝－100，s2＝0，s3＝－ ＝－150。 ，
由于在这个基本解中s1＝－100，s3＝－150，不 ＝－ ， ＝－ 不 满足该线性规划最后一个变量非负的约束条件， 满足该线性规划最后一个变量非负的约束条件，显然不 是此线性规划的可行解，一个基本解可以是可行解， 是此线性规划的可行解，一个基本解可以是可行解，也 可以是非可行解， 可以是非可行解，它们之间的主要区别在于其所有变量 的解是否满足非负的条件。 的解是否满足非负的条件。
1 1 1 1 与 0 2 1 0 0 1 0 0 0 1 0 0 0 1
都是该线性规划的一个基。 都是该线性规划的一个基。
6
它们都是由3个线性无关的系数列向量组成的。 它们都是由 个线性无关的系数列向量组成的。 个线性无关的系数列向量组成的 基向量： 中的一列即称为一个基向量。 基向量：基B中的一列即称为一个基向量。基B中共
1 1 0 1 0 0 1 0 1
的一个基， 为A的一个基，
为零。 令这个基的非基变量 x1，s2 为零 。 这时约束方程就 变为基变量的约束方程： 变为基变量的约束方程：
x 2 + s1 = 300 , x 2 = 400 , x 2 + s3 = 250 .
8
求解得到唯一基变量的一组解： 求解得到唯一基变量的一组解： x2＝400，s1＝－ 100，s3＝－ ， ＝－150，再加上非基变量： x1＝0，s2＝0，就 再加上非基变量： 再加上非基变量 ， 得到了此线性规划的一个基本解： 得到了此线性规划的一个基本解：
第五章
单纯形法
在第二章里我们用图解法解决了只含有两个决策变 量的线性规划的问题， 量的线性规划的问题，然而由于我们画图的平面只是二维 的，对多于两个决策变量得线性规划问题，图解法就显得 对多于两个决策变量得线性规划问题， 无能为力了。 无能为力了。现在我们在这一章里介绍由美国数学家丹捷 提出的， 格(G.B.Dantzig)提出的，得到最广泛应用的线性规划的代 提出的 数算法－－单纯形法， 数算法－－单纯形法，这恐怕是在运筹学发展史上最辉煌 －－单纯形法 的一笔。 的一笔。我们在第三章所介绍的线性规划问题的计算机解 法就是基于单纯形法编程来解决可以含有上千个决策变量 的及上千个约束条件的复杂的线性规划问题。 的及上千个约束条件的复杂的线性规划问题。

运筹学第二章习题和答案

运筹学第二章习题和答案运筹学是一门研究如何通过数学模型和方法来优化决策和资源分配的学科。

在运筹学的学习过程中，习题是非常重要的一部分。

通过做习题，我们可以巩固理论知识，提高解决问题的能力。

本文将针对运筹学第二章的习题进行讨论和答案解析。

第二章主要介绍了线性规划的基本概念和方法。

线性规划是一种常见的优化问题，其数学模型可以表示为最大化或最小化一个线性目标函数的同时满足一组线性约束条件。

在解决线性规划问题时，我们常常使用单纯形法或者内点法等方法。

习题2.1：一个公司生产两种产品A和B，每个单位A产品的利润为3万元，每个单位B产品的利润为4万元。

公司的生产能力为每天生产A产品100个单位，B产品80个单位。

产品A和B分别需要2个和3个单位的原材料X和Y。

而公司每天可用的原材料X和Y分别为180个单位和210个单位。

问该公司应如何安排生产，才能使利润最大化？解析：首先，我们需要定义决策变量。

假设公司每天生产A产品x个单位，B 产品y个单位。

则我们的目标是最大化利润，即最大化目标函数Z=3x+4y。

同时，我们需要满足生产能力和原材料约束条件。

生产能力约束条件为x≤100，y≤80。

原材料约束条件为2x+3y≤180，2x+3y≤210。

通过绘制约束条件的图形，我们可以得到可行解的区域。

在该区域内，我们需要找到目标函数Z=3x+4y的最大值点。

通过计算，我们可以得到最大利润为320万元，此时生产100个单位的A产品和60个单位的B产品。

习题2.2：某工厂生产两种产品，产品A和产品B。

产品A的生产需要1个单位的原材料X和2个单位的原材料Y，产品B的生产需要2个单位的原材料X 和1个单位的原材料Y。

每个单位的产品A的利润为3万元，每个单位的产品B的利润为4万元。

工厂每天可用的原材料X和Y分别为10个单位和12个单位。

问该工厂应如何安排生产，才能使利润最大化？解析：同样地，我们首先定义决策变量。

假设工厂每天生产A产品x个单位，B产品y个单位。

运筹学第2讲


例二、将线性规划问题化为标准型
max 3 x1 x1 x 1 解： min Z
Z = − x − 8 x − 3 x
2 2
1
+ 2 x
2
≤ 5 ≥ 4
≥ 0 , x 2 为无约束
= x1 − 2( x 3 − x 4 )
= 5 3 x1 − 8( x 3 − x 4 ) + x 5 − x6 = 4 x1 − 3( x 3 − x 4 ) x ,x ,x ,x ,x ≥ 0 4 5 6 1 3
2 图 解 法
x2
6
⑴ ⑵ ⑶ ⑷
⑶
4
5
⑷
3
1
2
(4 2)
0
1
2
3
4
5
6
7
8
x1
⑵ ⑴
∴ 最优解：x1 = 4 x2 = 2 有唯一最优解，Z = 14
满足约束条件的所有点都会在阴影区域，叫可行域 可行域
例二、 例二、
max Z = x 1 + 2 x 2
x2
无穷多最优解
⑵ ⑶
2 图 解 法
x1 + 2 x2 ≤ 6 3 x + 2 x ≤ 12 1 2 x2 ≤ 2 x1 ≥ 0, x2 ≥ 0
Z = 2 x1 + 3 x
2
− x1 + 2 x2 ≤ 2 2 x1 − x2 ≤ 3 x2 ≥ 4 x1, x2 ≥ 0
1.4 线性规划问题的解
的 数 1 学 一 模 般 型 线 性 规 划 问 题
线性规划问题：
目标函数： 约束条件： s.t.
max Z =
∑c x

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