管理运筹学(讲义)A-2

《管理运筹学(讲义)A-2》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第二章对偶理论与灵敏度分析(dualitytheoryandsensitivityanalysis)第一节单纯形法的矩阵描述用矩阵描述单纯形法求解过程比较简便，也有助于加深对单纯形法的理解。设有线性规划问题，用矩阵形式表示，maxz=CXAX0在约朿条件中加入松弛变量Xs=(E+i，£+2，・・・，£+J，将其化成标准型：maxz=CX+0・AX+I・Xs=bX>0,Xs>0式中I为mXm的单位阵运用单纯形法求解，需将标准型中系数矩阵、变量和目标函数中的系数向量改写成分块形式：♦系数矩阵(儿/)改写为(B,N)两块，B为基矩阵；♦变量(X、改写为/、XB,Xb为对应于基矩阵

2、B的基变量;s丿Pn丿♦目标函数中系数向量(C,0)改写为(q,CQ，C〃为对应于基变量的系数向量；一(X目标函数：z二CX+0・Xs=(CbCn)B=CbXb+CnXn(X和丿(x、约束条件：AX+IXS=(BN)B=BXb+NXn=bXn)所以，改写后的线性规划问题为，maxz=CBXB+CNXN(1)[BXB+NXN=b⑵下面按照单纯形法求解原理，对改写后的线性规划模型进行分析：从(2)式中，可得出用非基变量表示基变量的表达式：XB=B~lb-B~lNXN(3)在(3)式中，令Xn=O,可得到一个基解乂=I。丿再将(3)式代入(1)式，可得出用非基变量表示目标函数的表达式：

3、z=CB(B~[b-B-lNXN)+CNXN二CbB5(Cn-CbB-'N)Xn(4)令Xn=O,可得目标函数值，z=CBB~{b再对(3)和(4)进行分析，又可得出：。在(4)式中，非基变量X”系数Cn7矿即为非基变量的检验数cr；v,基变量Xr的检验数为0；这个非基变量检验数=Cn-CbB~'N与前一章提到的非基变量cfj=Cj-Zj,j=m+!,•••,"含义完全相同。在这个检验数b”=Cn—CbB-'N中，由于C”中对应于Xs的系数为0,所以，Xs的检验数为-CbB'xo另外，由于基变量的检验数为Cb-CbB*",所以，所有变量的检验数都可用C-q矿1A和-CbB^表示o◊从

4、(3)式，确定换出变量的0规则，用矩阵可表示为,(沪以＞0=h_Ia这里的0规则与前面介绍的0规则含义完全相同，在上一章介绍的。规则为，0-min纠。＞0在上式中，(BS是向量矿％的第i个分量，即亦(B“p)是矿”的第i个分量，即aik。＜用矩阵描述的单纯形表。为用矩阵描述的单纯形表，需要将上面(1)和(2)再进行改写，将非基变量乂何再分成两块(Xm，Xs),即BXB+N{XNi+IXs=b二Xb+B-'NXn+B~{XS=B~xb(5)将(4)式移项后，得，-+凤+%"+()•心=0(6)将⑸式代入⑹式,得，—z+(Cn_CbB一'N)Xn、_CbB—'Xs=-Cb矿％(7)

5、用单纯形表表示即为,XbXnRHSXnXsIB-'N矿1Bf0CnCbB-'N-CbB]-CBB~xb这是迭代后的单纯形表，从表中可以看出，各部分数字都与基矩阵B的逆矩阵3"有关，而逆矩阵对应于松弛变量的位置。将(5)式和(7)式合并，用矩阵表示即为,厂_7、‘0IB-'Nb~x、J0Cn-CbB—'N-CbB-XbXnB~xbJ-CM丿第二节改进单纯形法从上一章介绍的表格单纯形法可以看出，用该法求解线性规划问题时，每迭代一次都要把整个单纯形表计算一遍，实际上，从上一张单纯形表变换到下一张时，即迭代一次有许多计算是不必要的，所需重新计算的数据仅仅是检验数、主元列元素、

6、当前的基变量及b列数据等，一些与基变换运算暂时无关的列向量没有必要计算。因此，按此法用计算机求解线性规划问题，特别是大型线性规划问题时，计算效率非常低。为了提高计算效率，人们对表格单纯形法进行了改进提出了适合于计算机计算的改进单纯形法。改进单纯形法有两个特点：①在迭代过程屮，有许多数据计算都依赖于基矩阵B的逆矩阵所以，在迭代过程中，只要求出基矩阵的B的逆矩阵沪，检验数Cn-CbB-'N、基可行解屮的基变量B»b、日标函数值CBB~lb及0值等数据都可以从线性规划问题的初始数据直接求出。②在进行了基变换后，如何用最少的计算量来求出新的基矩阵的逆矩阵就成了该法的关键。如果每次迭代都必须从

7、原始数据来计算计算量是很大的。改进单纯形法能够在相邻的两次迭代中，用上一次基矩阵的B的逆矩阵3"直接计算出新的基矩阵的目的逆矩阵大大简化了计算。改进单纯形法的计算步骤：[1]根据给出的线性规划问题，在加入松弛变量或人工变量后，得到初始基变量，求出初始可行基B的逆矩阵和初始基可行解，5坷比丿<0>再计算单纯形乘子Y=CbB~]⑵计算非基变量X”的检验数乙，Cn=Cn-CbB'N；如果<0,即每一个非基变量对应的检验数都小于零，则表示已得到了最优解,停止计算。