确定型决策课件

确定型决策小组成员：

郑婕1确定型决策主要内容确定型决策

--确定型决策概述--确定型决策应具备的条件--确定型决策主要方法线性规划法

--线性规划法概述--线性规划法数学模型--线性规划法求解2确定型决策确定型决策概述确定型决策是指决策的自然状态是一种既定的情况，即在已知未来可能发生的情况的条件下，根据每一个行动方案只能产生的唯一的结果，选择最优方案。自然状态：指各种可行方案可能遇到的客观情况和状态。

例如：公司可以生产两种产品1和2，生产产品1在销量好的情况下获利100万，不好的情况下获50万，产品2在好的情况下获利90万，差的时候获利60万。3确定型决策应具备的条件（1）存在着决策人希望达到的一个明确目标。（2）只存在一个确定的自然状态。（3）存在着可供选择的两个或两个以上的行动方案。（4）不同的行动方案在确定状态下的损失或利益值可以计算出来。例如：某企业可向三家银行借贷，但利率不同，分别为8%、7.5%、和8.5%。企业需决定向哪家银行借款。很明显，向利率最底的银行借款为最佳方案。这就是确定型决策。此外，象企业中确定状态下的库存管理，生产日程计划或设备计划的决策都属于确定型决策。4确定型决策确定型决策方法（1）线性规划法（2）直观分析法（3）盈亏平衡分析方法（4）投资回收期法（5）排队法

5确定型决策线性规划法概述线性规划（LinearProgramming),简称LP。线性规划法产生于20世纪40年代，广泛应用于生产制造、物料分配、人力资源计划、运输问题和投资决策等方面。这种方法的本质是寻求如何使用有限的资源获得最大的效果，或者用最小的成本完成一项既定的任务。通常是在一些线性等式或不等式的约束条件下，寻求目标函数的最优值。6确定型决策线性规划数学模型问题的提出例1：生产计划问题某公司可以生产两种新产品，其主要数据如下表所示。问：产品Ⅰ、Ⅱ各生产多少件，使利润最大？ⅠⅡ限制

设备台时128台时

材料A4016kg材料B0412kg利润23显然，此问题是在设备可用时间和材料重量受到限制的情况下来寻求每周利润最大化，其决策方案是决定产品一和产品二各自的产量为多少才最佳？7确定型决策线性规划的几个概念（1）决策变量变量是运筹学问题或系统中待确定的某些量，在实际问题中常常把变量X叫决策变量。在例1中，就可以记x1为生产产品1的产量；x2为生产产品二的产量。（2）约束条件求目标函极值时的某些限制称为约束条件。在例1中，设备可用时间和材料重量的约束，全为“≤”的不等式约束。（3）目标函数在例1中，生产计划安排的“最优化”要有一定的标准或评价方法，目标函数就是这种标准的数学描述，这里的目标要求生产的利润为最大。8确定型决策根据上面的规定，例1的产品组合问题可抽象地归结为一个数学模型，如下：ⅠⅡ限制

设备台时128台时

材料A4016kg材料B0412kg利润23目标函数：max

z=2x1

+

3x2约束条件：1x1

+

2x2≤84x1

≤

16

4x2

≤

12x1，x2

≥

0

9确定型决策线性规划的假定条件（1）比例性假定。意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。（2）可加性假定。每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。（3）连续性假定。决策变量应取连续值。（4）确定性假定。所有参数都是确定的参数，不包含随机因素。

10确定型决策线性规划模型所需的数据资源单位活动对资源的使用量资源可利用量12…n1a11a12…a1nb12a21a22…a2nb2………………mam1am2…amnbm单位活动对Z的贡献c1c2…cn11确定型决策线性规划的数学模型：其中，目标函数可以是min的形式，函数约束中“≤”可以是“=”或“≥”，变量的非负性限制也可以取消。

12确定型决策说明：

(1)决策变量：x1，x2，···，xn。

一组决策变量表示为问题的一个方案；(2)目标函数：max(min)zz为决策变量的线性函数;(3)约束条件一组线性不等式。cj为价值系数,bi为资源，aij为技术系数(i=1,…,m;j=1,…,n).13确定型决策线性规划的标准型标准型（z极大值，等式，b非负，x非负）

14确定型决策用向量表示15确定型决策

用矩阵描述为：

其中:X=(x1,x2,···,xn)TC=(c1,c2,···,cn)b=(b1,b2,···,bm)T

16确定型决策标准型的化法

(1)min→max。

令z’=-z即可。(2)不等式。对于“≤”情况，在“≤”左边加上一个松弛变量（非负），变为等式，如x1≤4,可令x1+x3=4,则x3≥0；对于“≥”情况：在“≥”左边减去一个剩余变量（非负），变为等式，如0.6x1+0.4x2≥6,可令0.6x1+0.4x2+x4=6。

注意：松弛变量、剩余变量在目标函数中的价值系数为0。(3)无约束变量。令xj=xj’-

xj”，xj’,xj”≥

0，代入即可。(4)变量xj≤0。令xj’=-xj即可。

17确定型决策

将下述问题化为标准型

minz=-x1+2x2-3x3x1+x2+x3

≤

7① x1-x2+x3

≥

2② -3x1+x2+2x3

=5③ x1,x2

≥

0，x3无约束解：令x3

=x3’-x3”，x3’,x3”≥

0；①式加上一个松弛变量x4；②式减去一个剩余变量x5；令z’=-z、；

maxz’=x1-

2x2

+

3(x3’

-

x3”)

+

0x4

+

0x5x1

+

x2

+(x3’

-

x3”)

+

x4

=7 x1

-

x2

+(x3’

-

x3”)

-

x5=2 -3x1

+

x2

+

2(x3’

-

x3”)

=5 x1,x2,x3’,x3”,x4,x5

≥

0 18确定型决策线性规划求解图解法比较简单、直观，适用于只有两个变量的线性规划问题。单纯形法适用于两个或两个以上变量的线性规划问题，比较复杂的问题需要借助计算机软件求解。

19确定型决策线性规划解的概念设线性规划为max

z=cx

①Ax=b②x≥0③

A为m

×

n矩阵,n

>

m,Rank

A=m(A为行满秩矩阵）

1、可行解：满足条件②、③的X；

2、最优解：满足条件①的可行解；

3、基：取B为A中的m

×

m子矩阵，Rank

B

=

m，则称B为线性规划问题的一个基。取B=(p1,p2,···,pm)pj=(a1j,a2j,···,amj)T

则称x1,x2,···,xm为基变量，其它为非基变量。20确定型决策4、基解：取B=(p1,p2,···,pm)

a11,···,a1mx1a1m+1,···,a1nxm+1b1┆┆┆+

┆

┆┆=┆

am1,···,ammxmamm+1,···,amnxnbm

↑↑

↑↑基基变量

非基非基变量

令xm+1=···=xn=0(非基变量为0)则BXB=b

∴

21确定型决策5、基可行解满足③式要求的基解。如右图所示，各边交点O,Q1,Q2,Q3,Q4均为基可行解；而其延长线的交点Q5为基解，但不是基可行解。O(0,0)Q1(4,0)Q2(4,2)Q4(0,3)Q3(2,3)Q5(4,3)6、可行基基可行解对应的B为可行基。可行解基可行解非可行解基解22确定型决策

图解法用图解法求例1。max

z=2x1

+

3x21x1

+

2x2

≤

8①4x1

≤

16②

4x2

≤

12③x1，x2

≥

0解：(1)建立x1

-

x2坐标；x2x1(2)约束条件的几何表示；

①②Q1Q2③Q3Q4(3)目标函数的几何表示；

*

z=2x1

+

3x2

o4323确定型决策首先取z=0，然后，使z逐渐增大，直至找到最优解所对应的点。*可见，在Q2点z取到最大值。因此，Q2点所对应的解为最优解。Q2点坐标为(4，2)。即:x1

=

4，x2

=

2∴由此求得最优解：x1*

=

4x2*

=

2最大值：max

z

=

z*

=

2x1

+

3x2

=

14x2x1①②Q1Q2(4,2)③Q3Q4*4324确定型决策讨论：(1)唯一最优解max

z

=

z*时，解唯一，如上例。(2)无穷多最优解

对例1，若目标函数

z

=

2x1

+

4x2，此时表示目标函数的直线与表示条件①的直线平行，最优点在线段Q3Q2上。即存在无穷多最优解。x2x1②Q1Q2(4,2)③Q3(2,3)Q4o43*①25确定型决策(3)无界解

max

z=2x1

+

3x24x1

≤

16x1，x2

≥

0则x2

→

∞，z

→

∞。即存在无界解。在实际问题中，可能是缺少约束条件。o22426确定型决策(4)无可行解

max

z

=

2x1

+

3x22x1

+

4x2

≥

8x1

+

x2

≤

1x1，x2

≥

0

无公共部分，无可行域。即无可行解。在实际问题中，可能是关系错。1124x1x227确定型决策

单纯形法

基本思路：从可行域的一个顶点到另一个顶点迭代求最优解。初始基可行解的确定1、松弛基（松弛变量对应的B）

max

z=x1

+

3x2x1

+

2x2≤32x1

+

3x2≤4x1,x2

≥0max

z=x1

+

3x2

+

0x3

+

0x4

x1

+

2x2

+

x3

=32x1

+

3x2

+

x4=4x1,x2,x3,x4

≥0

化标准型

取x3、x4为基变量,令非基变量x1=x2=0∴初始基可行解：X(0)=(0034)T28确定型决策2、观察法

max

z=x1

+

3x2

+

2x3

+

x4x1

+

2x2

+

3x3

=3

3x2

+

x3

+

x4=4x1,x2,x3,x4

≥0

选XB=(x1x4)T

令x2=x3=0

则初始基可行解：X(0)=(3004)T29确定型决策最优性的检验与解的判别30确定型决策则31确定型决策解的判别：1.若，则此时的基可行解为最优解；2.若存在某个非基变量的检验数，且，则该线性规划问题具有无界解（或称无最优解）；3.若所有，又，对于某个非基变量有，则该线性规划问题具有无穷多最优解。32确定型决策基变换33确定型决策旋转运算（消元运算）

a1k’0

┆

┆al-1k’0pk’=（alk’）（1）al+1k’0┆

┆amk’0

得到基可行解，重复上面的步骤，求出最优解。34确定型决策单纯形表

35确定型决策

建立单纯形表cBxBbc1···cncn+1···cn+mθx1···xnxn+1···xn+mcn+1xn+1b1a11···a1n1···0θ1┆┆┆┆┆┆┆┆cn+mxn+mbmam1···amn0···1θm-z-z0σ1

···σn

0···0σj

用单纯形法求解

max

z=x1

+

3x2x1

+

2x2

≤

84x1

≤

16

4x2

≤

12x1,x2

≥

036确定型决策

解：①标准化，建立单纯形表

引入松弛变量x3，x4，x5为初始基变量

max

z=x1+3x2+0x3+0x4+0x5x1

+

2x2

+

x3

=84x1

+

x4

=16

4x2

+

x5=12x1,x2,x3,x4,x5≥0cBxBbx1x2x3x4x5θ13000cBxBbx1x2x3x4