当前位置：文档之家 › 管理运筹学第六—第八章

管理运筹学第六—第八章

  • 格式：ppt
  • 大小：2.28 MB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

管理运筹学 第6章 目标规划

管理运筹学 第6章 目标规划

目标规划问题及模型
∵正负偏差不可能同时出现，故总有：
x1－x2+d--d+ =0
若希望甲的产量不低于乙的产量，即不希望d->0,用目标约束可
表为:
min{d }
x1
x2
d
d
0
若希望甲的产量低于乙的产量，即不希望d＋>0,用目标约束可
表为:
min{d }
x1
x2
d
d
0
若希望甲的产量恰好等于乙的产量，即不希望d＋>0,也不希望
2x1 2x2 12
s.t
4
x1 x1
2x2
8 16
4x2 12
x1 , x2 0
其最优解为x1＝4，x2＝2，z＊＝14元
目标规划问题及模型
但企业的经营目标不仅仅是利润，而且要考虑多个方面，如： (1) 力求使利润指标不低于12元； (2) 考虑到市场需求，甲、乙两种产品的生产量需保持1:1的比
标决策的需要而由线性规划逐步发展起来的一个分支。 由于现代化企业内专业分工越来越细，组织机构日益复
杂，为了统一协调企业各部门围绕一个整体的目标工作，产 生了目标管理这种先进的管理技术。目标规划是实行目标管 理的有效工具，它根据企业制定的经营目标以及这些目标的 轻重缓急次序，考虑现有资源情况，分析如何达到规定目标 或从总体上离规定目标的差距为最小。
min Z = f（ d ++ d - ）
（2） 要求不超过目标值，但允许达不到目标值，即只有使 正偏差量要尽可能地小（实现最少或为零）
min Z = f（ d +）
目标规划问题及模型
例1. 某企业计划生产甲，乙两种产品，这些产品分别要在 A,B,C,D四种不同设备上加工。按工艺文件规定，如表所示。

管理运筹学判断题背诵讲义

管理运筹学判断题背诵讲义

管理运筹学判断题背诵讲义第一章 线性规划与单纯形表a)图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的； b) 线性规划模型中增加一个约束条件,可行域的范围般将缩小,减少一个约束条件,可行域的范围一般将扩大；c) 线性规划问题的每一个基解对应可行域的一个顶点； d)如线性规划问题存在可行域，则可行域定包含坐标的原点；e)对取值无约束的变量j x ，通常令'''j j j x x x =-其中'j x ≥0,''j x ≥0,在用单纯形法求得的最优解中有可能同时出现'j x >0，''j x >0；f)用单纯形法求解标准型的线性规划问题时，与j σ>0对应的变量都可以被选作换人变量；g)单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负；h) 单纯形法计算中,选取最大正检验数k σ对应的变量k x 作为换入变量，将使目标函数值得到最快的增长；i)一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从 单纯形表中删除,而不影响计算结果；j)线性规划问题的任-可行解都可以用全部基可行解的线性组合表示；k)若X 1,X 2分别是某一线性规划问题的最优解则X=1λX 1 +2λX 2也是该线性规划问题的最优解，其中1λ，2λ可以为任意正的实数；1)线性规划用两阶段法求解时，第一阶段的目标函数通常写为 minz=ai ix ∑(ai x 为人工变量)，但也可写为minz=i ai ik x ,只要所有k i ,均为大于零的常数； m)对一个有n 个变量、m 个约束的标准型的线性规划问题,其可行域的顶点恰好为m n c 个；n) 单纯形法的迭代计算过 程是从一个可行解转换到目标函数值更大的另一个可行解；o)线性规划问题的可行解如为最优解，则该可行解定是基可行解；p)若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解；q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值,则该顶点处的目标函数值达到最优；r) 将线性规划约束条件的“≤”号及“≥”号变换成“一”号,将使问题的最优目标函数值得到改善；s)线性规划目标函数中系数最大的变量在最优解中总是取正的值:t)一个企业利用3种资源生产4种产品建立线性规划模型求解得到的最优解中最多只含有3种产品的组合；u)若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解； v)一个线性规划问题求解时的选代工作量主要取决于变量数的多少，与约束条件的数量关系相对较小。

管理运筹学课后习题答案

管理运筹学课后习题答案

第2章 线性规划的图解法1．解：x`A 1 (1) 可行域为OABC(2) 等值线为图中虚线部分(3) 由图可知，最优解为B 点， 最优解：1x =712，7152=x 。

最优目标函数值：7692．解： x 2 10 1(1) 由图解法可得有唯一解 6.02.021==x x ，函数值为3.6。

(2) 无可行解 (3) 无界解 (4) 无可行解 (5)无穷多解(6) 有唯一解 3832021==x x ，函数值为392。

3．解：(1). 标准形式：3212100023m ax s s s x x f ++++=,,,,9221323302932121321221121≥=++=++=++s s s x x s x x s x x s x x(2). 标准形式：21210064m in s s x x f +++=,,,46710263212121221121≥=-=++=--s s x x x x s x x s x x(3). 标准形式：21''2'2'10022m in s s x x x f +++-=,,,,30223505527055321''2'2'12''2'2'1''2'2'11''2'21≥=--+=+-=+-+-s s x x x s x x x x x x s x x x4．解：标准形式：212100510m ax s s x x z +++=,,,8259432121221121≥=++=++s s x x s x x s x x松弛变量（0，0） 最优解为 1x =1，x 2=3/2.标准形式：32121000811m in s s s x x f ++++=,,,,369418332021032121321221121≥=-+=-+=-+s s s x x s x x s x x s x x剩余变量（0.0.13） 最优解为 x 1=1，x 2=5.6．解：(1) 最优解为 x 1=3，x 2=7. (2) 311<<c (3) 622<<c (4)4621==x x(5) 最优解为 x 1=8，x 2=0. (6) 不变化。

第8章 动态规划《管理运筹学》PPT课件

第8章 动态规划《管理运筹学》PPT课件
Vk,n (sk , uk , , sn1) fk [sk , uk ,Vk 1,n (sk 1, uk 1, , 1)] ③函数 fk (sk , uk ,Vk 1,n ) 对于变量 Vk1,n 要严格单调。
8.2 动态规划模型建立
下面以投资问题为例介绍动态规划的建模条件。
【例8-2】 某公司现有资金20万元，若投资于三个
8.1 动态规划基础知识
（5）状态转移方程：状态转移方程是确定过程由一
个状态转移到另一个状态的演变过程。动态规划中某一状
态以及该状态下的决策，与下一状态之间具有一定的函数
关系，称这种函数关系的表达式为状态转移方程。如果第
k段的状态为 sk ，该阶段的决策为
的状态就可以用下式来表示：
uk
sk
，则第k+1段
阶段的指标函数，是该阶段最优的指标函数。
8.2 动态规划模型建立
建立动态规划模型，就是在分析实际问题的基础上建 立该问题的动态规划基本方程。成功地应用动态规划方法 的关键，在于识别问题的多阶段特征，将问题分解成为可 用递推关系式联系起来的若干子问题，或者说正确地建立 具体问题的基本方程，这需要经验与技巧。而正确建立基 本递推关系方程的关键又在于正确选择状态变量，保证各 阶段的状态变量具有递推的状态转移关系。
第8章 动态规划
动态规划(DYnamic Programming，缩写为DP)方法 ，是本世纪50年代初期由美国数学家贝尔曼(Richard E ，Bellman)等人提出，后来逐渐发展起来的数学分支， 它是一种解决多阶段决策过程最优化问题的数学规划法 。动态规划的数学模型和求解方法比较灵活，对于连续 的或离散的，线性的或非线性的，确定性的或随机性的 模型，只要能构成多阶段决策过程，便可用动态规划方 法求其最优解。因而在自然科学、社会科学、工程技术 等许多领域具有广泛的用途，甚至一定程度上比线性规 划（LP）、非线性规划（NLP）有成效，特别是对于某 些离散型问题，解析数学无法适用，动态规划方法就成 为非常有用的求解工具。

管理运筹学_第六章

管理运筹学_第六章

δj δj Max a'kj 0 ΔC k Min a'kj 0 a'kj a'kj
管 理 运 筹 学
3
§1 单纯形表的灵敏度分析
例： 目标函数：Max z=50X1+100X2 约束条件：X1+X2≤300 2X1+X2≤400 X2≤250 X1，X2≥0 最优单纯形表如下 迭代次数 基变量 X1 S2 X2 ZJ CJ -ZJ
管
理
运
筹
学
8
§1 单纯形表的灵敏度分析
下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值。
约束条件 ≤ ≥
影子价格的取值
等于这个约束条件对应的松弛变量的 等于这个约束条件对应的剩余变量的 等于这个约束条件对应的人工变量的
z j 值,即为 j 的相反数 z j 值,即为 j 的相反数 z j 值,即为 j 的相反数
2
CJ -ZJ
0
0
- C’1
0
C’1-100
从δ 3≤0，得到-c1’≤0,即c1’≥0，并且从δ 5≤0，得 到c1’≤100。 那么如果c1’取值超出这个范围，必然存在一个检验数 大于0，我们可以通过迭代来得到新的最优解。
管
理
运
筹
学
6
§1 单纯形表的灵敏度分析
二、约束方程中常数项的灵敏度分析
迭代次数 基变量 CB X1 50 X2 100 0 0 1 100 0 S1 0 1 -2 0 50 S2 0 0 1 0 0 S3 0 -1 1 1 50 -50 50 50 250 27500 b
品Ⅲ，已知生产产品Ⅲ,每件需要设备2台时，并消耗A原料0.5公斤。B原料 1.5公斤，获利150元，问该厂应该生产该产品多少？ 解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量X3在初始 表上的系数列的问题，

管理运筹学 第8章 方差分析

管理运筹学 第8章 方差分析
615如果进行一个的多因素试验不考虑交互作用完全水平组合试验总数为次若采用正交试验设计最小的试验次数为25611现有三台机器生产同规定的铝合金薄板其厚度分别服从同方差的正态分布从三台机器上各取五块斑测量其厚度对其进行方差分析求得f3292查f分a三台机器生产的薄板厚度在显著性水平095上有显著差异b三台机器生产的薄板厚度在显著性水平095上无显著差异c三台机器生产的薄板厚度在显著性水平005上有显著差异d三台机器生产的薄板厚度在显著性水平005上无显著差异个总体若符合单因子方差分析方法分析数据的假定时所检验的原假设是各总体的变异系数相等方差分析单因子方差分析是在相同方差的假定下检验多个正态总体的均值是否相等的一种统计方法即检验的原假设是三种饲料喂猪得一个月后每猪所增体重单位
• H1： 1 , 2 , , r 不全等。
【案例1】哪种促销方式效果最好？
• 某大型连锁超市为研究各种促 销方式的效果，选择下属 4 个 门店，分别采用丌同促销方式， 对包装食品各迚行了4 个月的 试验。试验结果如下：
超市管理部门希望了解： ⑴丌同促销方式对销售量是否 有显著影响？ ⑵哪种促销方式的效果最好？
X
.j
SS B a X
j 1 a b
b

.j
X

2
SS E
X
i 1 j 1
ij
X
i.
X

2
称为误差平方和，反映试验误差对试验指标的影响。
4. 检验用的统计量
同样可以证明：当 H01 为真时，统计量
FA S A /( a 1 ) S e /( a 1 )( b 1 )
• 问： • （1）不同品种的平均每公顷产 量是否存在显著差异？ （2）任意两个品种的平均每 公顷产量是否都存在显著差异？ 并确定适合该地区的高产小麦 品种。

《管理运筹学教案》课件

《管理运筹学教案》PPT课件第一章：管理运筹学概述1.1 管理运筹学的定义解释管理运筹学的概念和内涵强调管理运筹学在实际管理中的应用价值1.2 管理运筹学的发展历程介绍管理运筹学的起源和发展过程提及著名学者和管理运筹学的重要成果1.3 管理运筹学的方法和工具概述管理运筹学常用的方法和工具简要介绍线性规划、整数规划、动态规划等方法1.4 管理运筹学的应用领域列举管理运筹学在不同领域的应用实例强调管理运筹学在企业经营、物流管理、生产计划等方面的应用第二章：线性规划2.1 线性规划的基本概念解释线性规划的目标函数和约束条件引入可行解、最优解等基本概念2.2 线性规划的图解法演示线性规划问题的图解法步骤提供实际例子进行图解法的应用演示2.3 线性规划的代数法介绍线性规划的代数法解题步骤使用具体例子进行代数法的应用解释2.4 线性规划的应用案例提供实际案例，展示线性规划在企业决策、资源分配等方面的应用强调线性规划在解决实际问题中的重要性第三章：整数规划3.1 整数规划的基本概念解释整数规划与线性规划的区别引入整数规划的目标函数和约束条件3.2 整数规划的解法介绍整数规划常用的解法，如分支定界法、动态规划法等使用具体例子进行整数规划解法的应用解释3.3 整数规划的应用案例提供实际案例，展示整数规划在人员排班、物流配送等方面的应用强调整数规划在解决实际问题中的重要性3.4 整数规划与线性规划的比较对比整数规划与线性规划的解法和技术强调整数规划在处理离散决策问题时的优势第四章：动态规划4.1 动态规划的基本概念解释动态规划的定义和特点引入动态规划的基本原理和基本定理4.2 动态规划的解法步骤演示动态规划的解题步骤，如最优子结构、状态转移方程等使用具体例子进行动态规划解法的应用解释4.3 动态规划的应用案例提供实际案例，展示动态规划在库存管理、项目管理等方面的应用强调动态规划在解决多阶段决策问题中的重要性4.4 动态规划与其他运筹学方法的比较对比动态规划与其他运筹学方法的特点和适用场景强调动态规划在处理具有时间序列特征的问题时的优势第五章：决策分析5.1 决策分析的基本概念解释决策分析的目的和意义引入决策问题的基本要素和决策方法5.2 确定型决策分析介绍确定型决策分析的方法和步骤使用具体例子进行确定型决策分析的应用解释5.3 不确定型决策分析介绍不确定型决策分析的方法和步骤使用具体例子进行不确定型决策分析的应用解释5.4 风险型决策分析介绍风险型决策分析的方法和步骤使用具体例子进行风险型决策分析的应用解释5.5 决策分析的应用案例提供实际案例，展示决策分析在企业战略规划、新产品开发等方面的应用强调决策分析在解决实际问题中的重要性第六章：网络计划技术6.1 网络计划技术的基本概念解释网络计划技术的定义和作用引入节点、箭线、活动等基本元素6.2 常用网络计划技术介绍常用的网络计划技术，如PERT、CPM等演示这些网络计划技术的绘制和应用方法6.3 网络计划技术的应用案例提供实际案例，展示网络计划技术在项目管理和生产调度等方面的应用强调网络计划技术在时间管理和资源分配中的重要性6.4 网络计划技术的优化介绍网络计划技术的优化方法和步骤使用具体例子进行网络计划技术优化的应用解释第七章：排队论7.1 排队论的基本概念解释排队论的定义和研究对象引入队列、服务设施、顾客等基本元素7.2 排队论的模型构建介绍排队论的模型构建方法和步骤使用具体例子进行排队论模型的应用解释7.3 排队论的应用案例提供实际案例，展示排队论在服务业、制造业等方面的应用强调排队论在解决等待问题和提高服务水平中的重要性7.4 排队论的优化策略介绍排队论的优化策略和方法使用具体例子进行排队论优化策略的应用解释第八章：存储论8.1 存储论的基本概念解释存储论的定义和研究对象引入存储成本、缺货成本、需求量等基本元素8.2 存储论的模型构建介绍存储论的模型构建方法和步骤使用具体例子进行存储论模型的应用解释8.3 存储论的应用案例提供实际案例，展示存储论在库存管理、供应链等方面的应用强调存储论在解决存货控制和降低成本中的重要性8.4 存储论的优化策略介绍存储论的优化策略和方法使用具体例子进行存储论优化策略的应用解释第九章：对偶理论9.1 对偶理论的基本概念解释对偶理论的定义和意义引入对偶问题、对偶关系等基本元素9.2 对偶理论的解法介绍对偶理论的解法方法和步骤使用具体例子进行对偶理论的应用解释9.3 对偶理论的应用案例提供实际案例，展示对偶理论在优化问题和经济学中的应用强调对偶理论在解决实际问题中的重要性9.4 对偶理论与灵敏度分析解释对偶理论与灵敏度分析的关系介绍灵敏度分析的方法和步骤第十章：总结与展望10.1 管理运筹学的重要性和局限性总结管理运筹学在实际管理中的应用价值和局限性强调管理运筹学在解决问题和创新方面的潜力10.2 管理运筹学的发展趋势展望管理运筹学未来的发展趋势和研究方向提及新兴领域和技术在管理运筹学中的应用前景10.3 提高管理运筹学能力的建议给出提高管理运筹学能力的建议和指导鼓励学习者持续学习和实践，以提升解决实际问题的能力重点解析本文教案主要介绍了管理运筹学的十个重点内容，具体如下：1. 管理运筹学的定义、发展历程、方法与工具，以及应用领域。

运筹学第八章_动态规划

15
□状态集合：状态变量 xk 的取值集合称为状态集合，状态集合 实际上是关于状态的约束条件。 □通常用Sk表示状态集合，xkSk。
□第1阶段 S1={A}；
x1
x2
□第2阶段具有3个状
态B1、B2和B3，故
S2={B1, B2, B3}。 □……
x3
x4
x5
16
（3）决策（decision）
x2
B1
C1
C2
C3
□决策集合：第k阶段当状态处于xk时决策变量uk( xk )的取值范 称为决策集合，常用Dk( xk ) 表示。
□例1中，从第2阶段的 状态B1出发，可以选择 下一阶段的C1、C2、 C3。 □即 D2( B1 ) = { C1、 C2、C3 }；
B1
C1
C2
C3
□决策集合实际上是决策的约束条件，uk( xk ) ∈ Dk( xk ) 。
6
□这是一个多阶段决策过程。 □该过程可以分为相互联系的若干阶段，每一阶段都需作出决
策，从而形成全过程的决策。
x1=1000
u1 第1年
x2=0.7u1+ 0.9(x1-u1)
u2 第2年
x3=0.7u2+ 0.9(x2-u2)
u3 第3年
x4=0.7u3+ 0.9(x3-u3)
u4 第4年
x5=0.7u4+ 0.9(x4-u4)
3
提纲
1 动态规划实例 2 动态规划的基本概念 3 动态规划的基本思想与基本原理 4 逆序解法与顺序解法
4
1 动态规划实例
学习目标：
1 明确什么是多阶段的决策问题，特别要注意没有明显 的时段背景的问题如何化归为多阶段的决策问题。

管理运筹学 易错判断题整理

主要内容： 1 存储费 2 订货费 3 生产成本 4.缺货成本 5 订货提前期 6 订货点 7 （s,S）型存储 2 确定性存储的4种形式，要会画图。 判断题： 1 在其他费用不变的情况下，随着单位缺货费的增加， 最优订货批量将相应减少。× 2 其他费用不变，订货费用的增加将导致订货批量的减少。 × 3 在需求量为常数，订货提前期为0的经济订货批量存储模型中， 4 最优订货批量随一次订货费的增大而增大，随存储费用的增加而减小。 √
× 5 如果运输问题或者转运问题模型中，Cij 都是产地i到销地j的最小 运输费用，则运输问题同转运问题将得到相同的最优解。
√
第三章：目标规划
主要内容： 1 描述目标规划建模的思路以及他的数学模型同一般线性 数学模型的相同和不同点。 2 解释下列变量：1正负偏差变量 2绝对约束和目标约束 3 优先因子与权系数。 3 目标规划图解法的步骤。 4 目标规划 目标函数特点。 判断题： 1 目标规划模型中，可以不含有绝对约束但是必须含有目 标约束。
第一章：线性规划及单纯形法
2.1单纯形法和两阶段法大M法 主要内容
1 线性规划数学模型的结构及各要素的特征。 2 求解线性规划时可能出现哪几种结果。 3 叙述线性规划问题的可行解、基解、基可行解、最优解 的概念及上述解之间的关系。
4 单纯性法的计算步骤，如何在单纯性表中判别问题是具 有唯一最优解、无穷多最优解、无界解。
√ 4 动态规划的基本方程保证各阶段内决策的独立进行，可以不考虑这之前和之后 决策的如何进行。
√
第六章：网络规划
主要内容：
6.1 1 通常用G=（v,e）表示一个图，试描述符号V,E及表达式的含义。 2 解释下列名词，说明区别。1 端点，相邻，关联边， 2 环，多重边，简单图 3链，初等链 4. 圈，初等圈，简单圈。 5.回路，初等路6.节点的次，悬挂点，悬挂边，孤立点 7. 连通图，连通分图 ，支撑子图8. 有向图，基础图，赋权图 3 描述树，图的支撑树，最小支撑树的概念。 4 描述Dijkstra算法的基本思想和步骤。 5 最大流问题是线性规划问题，说明其线性形式。 6 什么是增光链，为什么不存在关于可行流f的增广链，就是最大流。 7截集，截量以及最大流最小截量定理。 8 最小费用最大流的概念。

第6章目标规划管理运筹学


目标规划的正式提出
目标规划（Goal Programming）:是针对线性规划目标单一 的局限性而提出的，是线性规划的应用拓展，是解决实际问题 的一种方法。线性规划是研究资源有效分配和利用，其特点是 在满足一组约束条件的情况下，寻求某一个目标的最大值或最 小值。而在现实社会中，经常遇到需要考虑多个目标的优化问 题。目标规划与传统方法不同，它强调了系统性，其方法在于 寻找一个“尽可能”满足所有目标的解，而不是绝对满足这些 目标的值。
根据背 景材料 列出全 部约束 不等式
目标 约束
系统 约束
xj ≥0 d±≥0
“≥”min{d-} “≤”min{d+} “=”min{d-+d+}
左端+ d－－d+=右端
确定优先 级和权系 数,构造目 标偏差最 小的目标 函数
约束 条件
目标 规划 数学 模型
管理运筹学 第6章 目标规划
例6-1
已知某实际问题的线性规划模型 为：
目标规划有着极大的灵活性，表现在它可以模拟系统的约束和 目标优先等级变化的各种模型，为管理决策提供众多的信息。 解决目标规划问题首先要根据目标的重要性分清主次先后、轻 重缓急，引入偏差变量，将目标按等级转化为目标约束，最终 形成可用线性规划方法解决的问题。
管理运筹学 第6章 目标规划
目标规划的正式提出
（2）据市场预测，I、II两种产品 需求量的比例大致是1:2；
（3）A为贵重设备，严格禁止超时 使用；
（4）设备C可以适当加班，但要控 制；设备B既要求充分利用，又尽可 能不加班，在重要性上设备B是C的 3倍。
综合考虑上述因素，企业应如何决 策？这里本章所要讨论的问题。
管理运筹学 第6章 目标规划
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

局中人Ⅰ策略集合: S1={α 1，α 2，…，α m} 局中人Ⅱ策略集合: S2={β 1，β 2，…，β n} {α i，β j}称为局势 6.2.3支付与支付函数 当局中人选定某一策略后,得到的收益或损失称为 局中人的支付;不同的策略导致不同的支付,因此支付 是策略的函数. 6.2.4零和对策 若在一局对策中,全体局中人的支付总和为0,则将 该对策称为零和对策,否则称为非零和对策. 6.2.5对策分类
A= xi
y1 … yj … yn
yj Σ aijxi≥V (j=1,2,…,n) Σ xi=1
i=1 i=1
m
m
xm
……………... ai1… aij … ain ……………... am1 … amj … amn
xi≥0 (i=1,2,…,m)
xi Σ aijyj≤V (i=1,2,…,m) Σ yj=1
α A = α α α β1 8 1 9 -3 β2 6 3 6 1 β
3
β
4
1
2
3 4
8 6 4 -3 7 6 10 3
min 6 -3 6 -3
max
9
6
10
6
局中人Ⅰ最好结果： max min aij =max {6，-3，6，-3}=6 局中人Ⅱ最好结果： min max aij = min {9，6，10，6}=6
第六章矩阵对策
6.1 对策问题 6.2 对策论的基本概念 6.3 矩阵对策的概念及模型 6.4 矩阵对策的纯策略解(鞍点解) 6.5 矩阵对策的混合策略解 6.6 矩阵对策的解
第六章矩阵对策
6．1对策问题
6．2对策论的基本概念 6．2．1局中人 一场竞争或斗争称为一局对策，一局对策中的决策者 称为该局对策的局中人（只有两个局中人，称为两人 对策；两人以上称为多人对策）。 6．2．2策略与策略集合 指导局中人自始至终如何行动的一个实际可行的完 整的行动方案称为策略。 局中人所有策略构成的集合称为策略集合。 有限策略 有限对策 无限策略 无限对策
β1 β2 β3 α1 -6 2 -7 A = α2 5 3 6 α3 18 0 -8 α4 -2 -12 7 局中人Ⅰ 局中人Ⅱ： α1 min{-6，2，-7} = -7 β 1 max{-6，5，18，-2}=18 α2 min{ 5，3，6 } = 3 β 2 max{2，3，0，-12} = 3 α3 min{18，0，-8} = -8 β 3 max{-7，6，-8，7} = 7 α4 min{-2，-12，7}=-12 最好结果： 最好结果： min max {18，3，7}=3 max min {-7，3，-8，-12}=3 α 2，β 2分别为局中人Ⅰ、Ⅱ的最优策略； {α 2，β 2}为对策解 （鞍点） 而 a22=3称为对策值。
5 20
35 10
对于局中人Ⅰ而言，若局中人Ⅱ选取β 1，β 2，则局中 人Ⅰ的支付期望值分别为 β1 5x1+20（1-x1）=20-15x1≥V β 2 35x1+10（1-x1）=25x1+10≥V
V
20 10 E 0
D
1/4
局中人Ⅰ用“最大最小”原则选 取自己的策略，即 max{ min (20-15x1 ,25x1+10)} 0≤x1≤1 从图中可知： min (20-15x1 ,25x1+10) 0≤x1 ≤1 为折线EDF，D为所求的极值点， 其坐标:（1/4,161/4） 所以 F 5 X*=(x1* ,1-x1*)=(1/4,3/4) 1/4 V =16 X G* 1 1 35
β β β β
1
2
3 4
2x1+4（1-x1）=4-2x1 3x1+（1-x1）=1+2x1 x1+6（1-x1）=6-5x1 5x1 =5x1
≥ V ≥ V ≥ V ≥ V
（1） （2） （3） （4）
X2 6
从图中可知：min (4-2x1，1+2x1，6-5x1，5x1) 0≤x1≤1
6
5
4 3 2 1 A B
例5：矩阵对策G={ S1，S2，A} 其中: S1={α 1，α 2}， S2={β 1，β 2，β 3，β 4}
2 A = 4
3 1
1 6
5 0
解：作混合扩充： S*1={x1 ，1-x1}，S*2={y1 ，y2 ，y3，y4} 对于局中人Ⅰ而言，若局中人Ⅱ选取β 1，β 2，β 3， β 4则局中人Ⅰ的支付期望值分别为： β1 2x1+4（1-x1）=4-2x1 ≥V （1） β2 3x1+（1-x1）=1+2x1 ≥V （2） β3 x1+6（1-x1）=6-5x1 ≥V （3） β4 5x1 =5x1 ≥V （4） 局中人Ⅰ用“最大最小”原则选取自己的策略，即 max {min (4-2x1，1+2x1，6-5x1，5x1)} 0≤x1 ≤1
零和对策
二人对策 非零和对策 有限对策
零和对策
n人对策 非零和对策 对策 零和对策 二人对策 非零和对策
无限对策
零和对策 n人对策 非零和对策 有限二人零和对策也称为矩阵对策.
6．3矩阵对策的概念及模型
一般形式： 局中人Ⅰ策略集合: S1={α 1，α 2，…，α m} 局中人Ⅱ策略集合: S2={β 1，β 2，…，β n} 其中 α i，β j 分别为局中人Ⅰ、Ⅱ的纯策略，策略偶 {α i，β j}称为纯局势； 若局中人Ⅰ在{α i，β j}下的支付为aij则 A =
j=1 j=1
n
n
yj≥0 (j=1,2,…,n)
定理 3 ：若（ X*，Y*）是对策 G 的最优混合策略，则对 某一个i或j来说： (1)若yj*≠0 则 Σ aijxi*=V (2)若xi*≠0 则 Σ aijyj*=V (3)若Σ aijxi* >V 则yj*=0 (4)若Σ aijyj* <V 则xi*=0
max min aij = min max aij=6 对策值： ai*j*=a12= a14= a32= a34= 6 对策解（鞍点）： （α i*，β j*）=（α 1，β 2）=（α 1，β 4） =（α 3 ，β 2 ）=（α 3 ，β 4 ） α 1，α 3为局中人Ⅰ的最优纯策略 β 2，β 4为局中人Ⅱ的最优纯策略 由此可见对策解不是唯一的，但对策值是唯一的。 两条重要性质： （1）无差别性：若（α i1 ，β j1 ）与（α i2 ，β j2 ） 是G的两个解，则ai1 j1 = ai2 j2 （2）可交换性：若（α i1 ，β j1 ）与（α i2 ，β j2 ） 是G的两个解，则（α i1 ，β j2 ）与（α i2 ，β j1 ） 也是G的两个解。
则称纯局势{α i*，β j*}为G在纯策略中的解(鞍点解)； 而α i*，β j*分别为局中人Ⅰ、Ⅱ的最优纯策略；ai*j*称 为矩阵对策G的值（对策值）。
定理 1: 矩阵对策 G={ S1，S2，A} 存在最优纯策略的 充分必要条件为： max min aij = min max aij 例3：已知矩阵对策G={ S1，S2，A}
a11 a12 … a1n a21 a22 … a2n …………... am1 am2 … amn
称为局中人Ⅰ的支付矩阵，矩阵对策模型可记为： G={ S1，S2，A} 局中人Ⅱ的支付矩阵为：-A
例1：包、剪、锤游戏中 矩阵对策模型：G={ S1，S2，A} 其中 甲：S1={α 1（包），α 2（剪），α 3（锤）} 乙：S2={β 1（包），β 2（剪），β 3（锤）}
Hale Waihona Puke 以下定义一套与纯策略解完全平行的混合策略的解。
定义2：如果存在X*∈S*1，Y*∈S*2；对任意的X∈S*1， 及Y∈S*2均满足： E（X，Y*）≤E（X*，Y*）≤E（X*，Y） 则称混合局势（X*，Y*）为G在混合策略中的解(混合 解)；而X*，Y*分别为局中人Ⅰ、Ⅱ的最优混合策略 ；E（X*，Y*）称为矩阵对策G的对策值，通常记为: VG*= E（X*，Y*）
5
4 3 2 C 1
为折线OABC，B为 所求的极值点 其坐标: （5/7，17/7）, 所以 X*=(x1* ,1-x1*) =(5/7,2/7) VG*=17/7
0
5/7
1
X1
对于局中人Ⅱ而言，若局中人Ⅰ选取α 1，α 2，则的支 付期望值分别为 α1 2y1+3y2+y3+5y4 ≤V α2 4y1+y2+6y3 ≤V 无法作图，应用定理3求出局中人Ⅱ的最优混合策略， x1* =5/7 2y1*+3y2*+y3*+5y4* =V x2* =2/7 4y1*+y2*+6y3* =V 将x1* =5/7，x2* =2/7 ，V=17/7 代入下列约束： 推出：
2x1+4（1-x1）=4-2x1 ≥V 4-2x1* 3x1+（1-x1） =1+2x1 ≥V 1+2x1* x1+6（1-x1）=6-5x1 ≥V 6-5x1* 5x1 =5x1 ≥V 5x1 * 代入下列方程组： =18/7 =17/7 =17/7 =25/7 > = = >
6．5矩阵对策的混合策略解
6．5．1混合策略与混合扩充 6．5．1．1混合策略 局中人Ⅰ以概率xi(i=1,2,…,m)选取纯策略α 局中人Ⅱ以概率yj(j=1,2,…,n)选取纯策略β 其中： Σ xi =1 (0≤xi≤1)
i=1 n m
i
j
Σ yj =1 (0≤yj≤1)
j=1
则向量X=(x1,x2,…,xm),Y=（y1,y2,…,yn)分别称为局中 人Ⅰ、Ⅱ混合策略；（X，Y）称为一个混合局势 显然：纯策略是混合策略的特例。
6．5．1．2 混合扩充 在混合策略中,局势（α i ，β 因此局中人Ⅰ的支付期望为：