精品！《管理运筹学》不容错过，不看太可惜！

　　今日推荐：《管理运筹学(微课版）》 作者：徐选华。搜索书名开始观看吧～

　　

　　-----精选段落-----

　　第1章线性规划基础

　　表1-11 单纯形运算表

　　最优解为：

　　X*=X(3)=(75,15,180,0,0)T

　　Z*=Z(3)=5 700

　　即得最优决策方案：产品甲、乙分别安排产量75千克、15千克，可使公司获得最大利润为5 700元。

　　1.5.6 人造基下的单纯形表求解——大M法

　　用单纯形法求解需要将数模化为规范型，但是并非所有的数模都能够通过引入松弛变量化为规范型，当数模的约束条件出现“=”或“≥”时，要将数模化为规范型，一般情况下就需要引入一种新的变量（称之为人工变量）形成初始基（称之为人造基）。

　　因此，规范型数学模型解基的形成只有三种可能：

　　（1）由决策变量自然形成的解基；

　　（2）由添加松弛变量形成的解基；

　　（3）由引入人工变量形成的解基，叫人造基，它由虚拟的人工变量组成。

　　前二种解基由具体的物理变量组成，每步迭代后的解均是可行解，可含在最优解里，具有实际的经济意义。

　　第三种解基中的人工变量是虚拟变量，没有任何意义，它们的引入改变了原 s.t.，使得求出的解是不可行解。第三种解基（人造基）的规范型数学模型采用大M（很大很大的正数）法求解：通过单纯形迭代，将人工变量从基中置换出来，使其取值为0，并得初始基本可行解，这相当于第一阶段；舍去人工变量，继续用单纯形迭代，求出最优解，这相当于第二阶段。

　　【例1-11】求解下列线性规划数学模型

　　解：用图解法可求得最优解X*= (0,3)T,Z*=6，如图1-9所示。

　　引入非负剩余变量——松弛变量x3、x4和x5将约束条件化为标准型：

　　令Z=–Z'，原目标函数等价于Max Z'= -x1+ 2x2

　　再引入非负人工变量x6和x7将约束条件化为规范型。于是得原问题的规范型为

　　现采用大M法求解。在原目标函数Min Z= x1-2x2中的后面加上（Max型目标函数减去）阻碍项M（x6+x7）得新目标函数Min Z= x1-2x2+M（x6+x7），其中M是很大的正数。

　　令Z=–Z'，则新目标函数等价于目标函数Max Z'=-x1+ 2x2-M（x6+x7），由于x6、x7为基变量，须消去，从约束条件得x6+x7=3-2 x2+x3+x4，代入目标函数Z’中得：Max Z'=–3M–x1+（2M+2）x2–Mx3–Mx4。于是得出如下新的规范型数学模型：

　　单纯形表求解如表1-12所示。

　　表1-12 大M法单纯形运算表

　　所以最优解为：

　　X*= X(5)= (0,3,1,2,0)T

　　Z*= -Z'(5)= -6

　　1.6 单纯形的经济信息

　　单纯形法提供的解和参数远比图解法和传统的定性经验决策提供的解丰富，这些解和参数反映了规划问题各个量之间的规律。揭示这些规律不仅可看到这种算法的优点和用途，而且可以看到它在科学决策领域中展现的新思想。

　　1.6.1 决策变量的最优解

　　最优解是单纯形法的基本决策信息，在建模参数可靠的基础上，它提供最优决策方案。如【例1-1】中，x1=75千克、x2=15千克，提供甲、乙两种产品的最优生产计划。

　　1.6.2 松弛变量的解

　　单纯形表的每一个基本可行解，不仅包含了决策变量的解，而且还有松弛变量的解，在最优决策条件下，松弛变量的解提供资源的剩余量，如【例1-1】中：

　　x3=180，表示设备A的闲置工时，表明设备A可用工时没有得到充分利用；

　　x4= 0，表示设备B的闲置工时，表明设备B可用工时得到充分利用；

　　x5= 0，表示设备C的闲置工时，表明设备C可用工时得到充分利用。

　　由此可知，在制订生产计划时，各种资源的筹备量往往不平衡，有的多有的少。为了达到预定的目标要求，最优生产计划只能按资源量最紧的条件来规划，从而筹备量大的资源就有多余。这就是松弛变量的事理意义。当最优方案确定后，一个精明的生产管理者就应该从约束方程找到松弛变量大于零的资源，想办法加以利用，以便使闲置资源能作出更大贡献，为企业创造更多效益。

　　1.6.3 产品的相关价值系数

　　产品的价值系数是单位产品提供的利润（如【例1-1】）。改化（或约化）的价值系数（即新解下的价值系数）称为产品相关价值系数，它是一个动态的数：

　　决策变量 x1的价值系数一开始为70，表明市场对产品甲有需求，因此也就有利润，公司调整产品结构，提高甲产品产量到80千克满足了市场需求，甲产品价值系数随即降为0，已无任何利润。与此同时，乙产品价值系数为20/3，表明市场对产品乙仍有需求，也有利润，公司继续调整产品结构，提高乙产品产量到15千克满足了市场需求，乙产品价值系数随即降为0，无任何利润。因此两个产品价值系数的变化反映了考虑市场信息和规划方案改变对利润的综合影响。

　　1.6.4 资源的影子（潜在）价格

　　资源的影子价格对管理人员来说是非常有益的，可以为加强资源管理提供有益的思路。

　　1.影子价格的概念

　　最优规划条件下，单位资源能够带来的目标增量，是反映资源最优利用的一种虚拟价格，也叫资源边际利润。

　　2.影子价格的计算

　　最优表中表示资源的松弛变量检验数的相反数（或最优目标函数中松弛变量系数的相反数）。如【例1-1】的最优解表（见表1-13）。

　　表1-13 最优解表

　　松弛变量x3、x4、x5的检验数为0、-2、-20/3，其相反数0、2、20/3就是设备A、B、C的影子价格。因为从最优表的目标函数MaxZ= 5700+0x1+ 0 x2+ 0 x3-2 x4-(20/3) x5中可知：

　　当设备A增加1个工时时，A的闲置时间缩短1个工时，即x3=-1，此时利润Z增加 0元，为（5 700+ 0）元；当设备B增加1个工时时，B的闲置时间缩短1个工时，即x4=-1，此时利润Z增加2元，为（5 700 +2）元；当设备C增加1个工时时，C的闲置时间缩短1个工时，即x5=-1，此时利润Z增加20/3元，为（5 700 + 20/3）元。

　　根据影子价格的定义，设备A的影子价格为0（元/台时）、设备B的影子价格为2（元/台时）、设备C的影子价格为20/3（元/台时）。

　　资源影子价格的高低表明资源的重要性的大小，影子价格为0的资源是非关键资源，影子价格大于0的资源是关键资源。影子价格越高，相应资源的重要性越大。

　　3.影子价格的应用

　　（1）在企业内部：指出挖潜方向，影子价格高的资源潜力大，影子价格低的资源潜力小。

　　设备A的影子价格为 0 元/台时，已有180台时剩余，缺少180台时不会造成任何损失，增加可用数量也不会增加任何利润，为非关键设备，不应为此花费代价。

　　设备B的影子价格为2元/台时，缺少1台时将造成2元的损失，增加1台时将增加2元的利润，为关键设备，应重点挖潜（如增加设备的可用时数），其重要程度较高。

　　设备C的影子价格为20/3元/台时，缺少1台时将造成 20/3元的损失，增加1台时将增加20/3元的利润，为关键设备，应重点挖潜，其重要程度最高。

　　值得注意的是，随着资源可用量的不断增加，其影子价格会不断下降，当影子价格降为0时，该资源可用量就不能再增加了，此时该资源已变成非关键资源。

　　（2）在企业外部：制定外单位来料加工时的收费用标准。

　　设备A的收费用标准为0元/台时，现有540台时，共收费0×540 = 0元（不考虑收费）；

　　设备B的收费用标准为2元/台时，现有450台时，共收费2×450 = 900元；

　　设备C的收费用标准为20/3元/台时，现有720台时，共收费20/3×720 = 4 800元；

　　合计收费0 + 900 + 4 800 = 5 700元。

　　（3）可以衡量资源的使用是否合理：同一种资源在不同的地方和不同的时期，其影子价格不相同，影子价格高的说明使用合理，所以应建立动态影子价格体系，做到物尽其用。

　　1.7 单纯形理论分析

　　由前面的实例可知，单纯形法是根据基本可行解（对应可行解域的顶点）的特点通过基变换来形成的，其核心是基变换，基变换包括三个部分的内容：

　　（1）由目标函数中非基变量前的检验数确定入基变量；

　　（2）由最小比值规则确定出基变量和主元素；

　　（3）根据主元素，对约束方程和目标函数进行初等行变换，实现基变换（也称为换基），形成一个新的基本可行解（新的顶点）。

　　为了说明更普遍的意义，以下对具有n个变量和m个约束方程的数学模型进行理论分析。由于标准型数学模型容易获得，下面从标准型数学模型开始讨论。

　　1.7.1 数学模型的标准型

　　通常，数学模型的标准型有以下几种形式。

　　（1）一般形式：为最普通的写法，目标函数和约束方程均写成线性方程。

　　（2）求和形式：目标函数和约束方程均写成和的形式。

　　（3）向量形式：目标函数和约束方程均写成向量的形式。

　　其中，C=（c1, c2,…, cn）,X=

　　（4）矩阵形式：目标函数和约束方程均写成矩阵的形式。

　　其中A=

　　为了书写方便，有时矩阵形式也可简写为：L=

　　1.7.2 数模的规范型

　　由前所述，规范型的数学模型有以下特点。

　　（1）s.t．方程中含有一组基：不妨设为XB=(x1,x2,…,xm)T，则有下列形式：

　　解得：

　　（2）目标函数中不含基变量XB：

　　其中，目标值为：

　　检验数为：Rj= cj-(c1, c2,…, cm)

　　因此，规范型数学模型为：

　　1.7.3 确定入基的非基变量

　　选择最大的正检验数对应的非基变量入基，即选

　　（1）若入基列

　　（2）若出现k个Rp相等，一般选使Z改变得最快的非基变量入基，理论上可任选一个。

　　分别选这k个Rp对应的k个非基变量xp入基，分别计算出k组正比值θk，每一组选一个最小正比值得k个最小正比值，在这k个最小正比值中选一个最大的正比值，其对应的非基变量入基。

　　1.7.4 确定出基的基变量

　　用 b列除以入基列，选正数得到一组正比值θi，然后从中挑选一个最小的正比值θL，对应的基变量xL出基，即选择

　　若出现k个θL相等，一般用字典法选择，理论上可任选一个。

　　从左至右依次用非基变量列（入基列除外）暂时代替比值θi，直至能够从中挑选一个最小的比值θL，其对应的基变量出基。

　　1.7.5 确定主元素并进行旋转运算

　　确定主元素aLP，以该主元素为中心进行旋转运算，如表1-14所示，即用初等行变换将入基列变为单位向量列，入基变量的检验数变为0，得下一个新表，如此循环进行直至全部检验数Rj≤0，即得最优表。

　　表1-14 初始单纯形表

　　1.8 软件求解与经济分析

　　本书以目前MBA运筹学教学流行软件WinQSB为基础，WinQSB是一个集模型求解、结果分析、经济与管理分析于一体的功能十分强大的运筹学专用软件，由美籍华人开发，包括运筹学的大部分模块，软件安装后可根据模型的类型选择相应的软件模块求解相应的模型，软件提供大量的相关分析数据。软件界面为英文，但比较直观和灵活，使用方便，是一个非常受欢迎的优秀运筹学软件。

　　求解线性规划调用模块“Linear and Integer Programming”，软件本身具有将数学模型标准化和规范化的功能，因此用户只需要将原始模型输入软件即可，另外软件可动态改变模型参数，如变量名称、类型、取值范围，目标函数方向等。

　　1.8.1 资源合理利用问题

　　现以【例1-1】的模型为例进行说明，数学模型如下：

　　运行子程序“Linear and Integer Programming”（从Windows的菜单找到该子程序），进入主窗口，通过菜单或快捷方式图标建立新问题（模型）。

　　第一步将原始模型输入软件。

　　首先设置模型参数，这里决策变量数为2，约束方程数为3（变量非负不作为约束条件），变量类型选非负连续（Nonnegative continuous），如图1-10所示，这些已经设置好的模型参数在模型建立后均可修改。单击按钮，将进入模型系数输入窗口。

　　其次将原始模型中的系数按照图1-11所示窗口进行输入，约束条件的方向、决策变量的类型及其取值范围都可以通过鼠标双击进行改变，也可以通过该窗口顶端的菜单下拉的功能菜单项进行改变。

　　举报/反馈