运筹学（OperationsResearch)(PPT131)学习课件.pptxVIP

;运筹学简介;;运筹学的发展历程：;;;运筹学方法使用情况(美1983);运筹学方法在中国使用情况(随机抽样);;;运筹学的主要分支;;;;;运筹学在工商管理中的应用;;;组织;CH1线性规划与单纯形法;;;;;;例2（指派问题）;;;;二、线性规划问题数学模型的一般形式及标准形式;;目标函数

Maxz=c1x1+c2x2+…+cnxn;;设目标函数为

Minf=c1x1+c2x2+…+cnxn

则可以令z＝-f，该极小化问题与下面的极大化问题有相同的最优解，即

Maxz=-c1x1-c2x2-…-cnxn

但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即

Minf＝-Maxz;设约束条件为

ai1x1+ai2x2+…+ainxn≤bi

可以引进一个新的变量s，使它等于约束右边与左边之差

s=bi–(ai1x1+ai2x2+…+ainxn)

显然，s也具有非负约束，即s≥0，

这时新的约束条件成为

ai1x1+ai2x2+…+ainxn+s=bi;当约束条件为

ai1x1+ai2x2+…+ainxn≥bi

时，类似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

显然，s也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn-s=bi;;在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。;在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi0，则把该等式约束两端同时乘以-1，得到：

-ai1x1-ai2x2-…-ainxn=-bi。;三、线性规划问题的图解法;;;;线性规划的可行域和最优解有以下几种可能的情况;;（1）可行解：满足所有约束条件的解。

（2）可行域（可行解集）：所有可行解构成的集合。

（3）最优解：使目标函数达到最优的可行解。

（4）最优值：最优解对应的目标函数值。;;对于线性规划的约束条件

Ax=b，x≥0

设B是A矩阵中的一个非奇异（可逆）的m×m子矩阵，则称B为线性规划的一个基。

记A=(p1，p2，…，pn)，其中pj=(a1j，a2j，…，amj)T?Rm，任取A中的m个线性无关列向量pj?Rm构成矩阵B=(pj1，pj2，…，pjm)，那么B为线性规划的一个基。

我们称对应于基B的变量xj1，xj2，…，xjm为基变量；而其它变量称为非基变量。记XB=(xj1，xj2，…，xjm)T。;（6）线性规划问题的基本解、基本可行解和可行基：;考虑如下线性规划模型：;;;;;§2单纯形法的基本原理;一、概念;;二、单纯形法的基本原理;单纯形法的基本思路是：;§3单纯形法的计算步骤;;;二、单纯形法的计算步骤;例：求解线性规划问题（L）：;取初始基B1=(P3,P4,P5)，初始单纯形表T（B1）为：;新基B2=(P3,P2,P5)，T（B2）为：;新基B3=(P3,P2,P1)，T（B3）为：;第二章对偶理论与灵敏度分析;;;;;;;;§2线性规划的对偶理论;;非对称形式的对偶规划：;;;基本规律：;例2写出下面线性规划问题的对偶问题：;将约束条件改为：;;二、对偶问题的基本性质;;;;;;§3影子价格——对偶问题的经济解释;;影子价格的经济含义;;§4对偶单纯形法;;;;;对偶单纯形法的计算步骤：;;例：求解线性规划问题;化为标准型：;再转化为：;;;§5灵敏度分析;;一、资源数量（约束条件右端常数项）发生变化的情况;例：课本例7;;;二、价值系数（目标函数中变量的系数）发生变化的情况;三、增加一种产品（增加一个新变量）;四、增加一个约束条件（增加一道工序）;例：课本第一章例1的数学模型;最终单纯形表为：;现增加约束条件3x1+2x2≤15，原最优解X=(4,2)T不满足这个约束。将3x1