运筹学课程讲义

运筹学课程讲义第一部分线性规划第一章线性规划的基本性质1.1线性规划的数学模型一、线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个。生产桌子和椅子需木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？213050maxxxz0,50212034212121xxxxxx例：某工厂生产某一种型号的机床。每台机床上需要2.9m、2.1m、1.5m的轴，分别为1根、2根和1根。这些轴需用同一种圆钢制作，圆钢的长度为74m。如果要生产100台机床，问应如何安排下料，才能用料最省？二、数学模型的标准型1.繁写形式2.缩写形式3.向量形式4.矩阵形式三、任一模型如何化为标准型？1.若原模型要求目标函数实现最大化，如何将其化为最小化问题？2.若原模型中约束条件为不等式，如何化为等式？3.若原模型中变量xk是自由变量，如何化为非负变量？4.若原模型中变量xj有上下界，如何化为非负变量？无约束321321321321321,0,052010651535765maxxxxxxxxxxxxxxxxz令'''3'3''3'331'1,0,,,ZZxxxxxxx0,,,,,,,5201010651533507765min7654''3'32'17''3'32'15''3'32'164''3'32'1765''3'32'1'xxxxxxxxxxxxxxxxxxxxxxxxMxMxxxxxxz1.2图解法该法简单直观，平面作图适于求解二维问题。使用该法求解线性规划问题时，不必把原模型化为标准型。一、图解法步骤1.由全部约束条件作图求出可行域2.作出一条目标函数的等值线3.平移目标函数等值线，作图求解最优点，再算出最优值二、从图解法看线性规划问题解的几种情况1.有唯一最优解2.有无穷多组最优解3.无可行解4.无有限最优解（无界解）0,23431246min21212121xxxxxxxxz最优解)0,21(，最优值3直观结论：1）线性规划问题的可行域为凸集，特殊情况下为无界域（但有有限个顶点）或空集；2）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。1.3线性规划的基本概念和基本定理一、线性规划问题的基与解可行解最优解基基向量非基向量基变量非基变量基本解基本可行解最优基本可行解退化的基本解二、几何意义上的几个基本概念1.凸集2.凸组合3.顶点三、线性规划问题的基本定理定理1：若线性规划问题存在可行域，则其可行域是凸集。引理1：线性规划问题的可行解TnxxxX),,,(21为基本可行解的充要条件是X的正分量对应的系数列向量是线性无关的。定理2：线性规划问题的基本可行解对应于可行域的顶点。引理2：K是有界凸集，则任何一点XK可表示为K的顶点的凸组合。定理3：如果线性规划问题有有限最优解，则其目标函数最优值一定可以在可行域的顶点上达到。四、求解线性规划问题的基本思路在有限个基本可行解中寻找最优基本可行解。找一个基本可行解（m个线性无关的系数列向量），由其换到另一个基本可行解。实质即为换基。前提是保证新的基本可行解的目标函数值比原来的更优而不是更劣。第二章单纯形法它是求解线性规划最为成熟的算法。胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子售价30元/个，生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？213050maxxxz0,50212034212121xxxxxx将其变形，得0,,,502120344321421321xxxxxxxxxx将43,xx对应的单位矩阵作为初始可行基。令43,xx为基变量，21,xx为非基变量。原模型变形为213050maxxxz0,,,250341204321214213xxxxxxxxxx如果令非基变量21,xx等于零，得一个基本可行解（0，0，120，50），对应的目标函数值z=0最优性检验：该解是否最优？显然不是。经济意义分析：21,xx等于零意味着家具厂不开工生产，销售收入为零，资源未得到充分利用。数学角度分析：非基变量21,xx前的系数都为正，表明目标函数值有增加的可能。只要将系数为正的非基变量与某一基变量对换，当换入变量的值增加时，目标函数值就可能增加。换基迭代：寻找下一个可行解需要进行换基迭代。换基后需满足：（1）新的解仍是基本可行解；（2）目标函数得到改善。选择入基变量：21,xx系数均为正。对求目标函数极大化的问题，我们希望目标值增加得越快越好，因此应选系数最大的1x入基。选择出基变量：1x入基后，其值从零增加并引起其他变量取值的变化。由问题的典则表达式和变量必须取正值的条件，得下列不等式关系：0x-2x-50x03x-4x-120x214213因迭代后2x仍为取零值的非基变量，上式可简化为02500412011xx很明显，只有选252/50,4/120min1x时，才能使上述不等式成立，并使基变量4x变为零，正好满足非基变量必须为零的条件，所以可令4x出基，新的典则方程变为42123150231204xxxxxx化简后得4234212205.05.025xxxxxx代入目标函数可得4222551250xxz得到下一个基本可行解（25，0，20，0），并完成了第一次迭代。新解是最优解吗？需进行最优检验。由于目标函数中2x的系数仍为正，说明多生产椅子仍有利可图，该解仍不是最优解。再次迭代。2x入基，3x出基，换基后典则形式变为4324314332205.15.0151551350xxxxxxxxz第三个基本可行解为（15，20，0，0），松弛变量都已为零，表明资源已得到充分利用；非基变量在目标函数中的系数全为负值，说明目标函数已无法进一步改善，因此该解已是最优解。2.1单纯形法原理一、构造初始可行基1.引入附加变量，把数学模型化为标准型2.若约束条件中附加变量的系数是-1或原约束即为等式，则必须引入人工变量，以构成初始可行基3.目标函数中，附加变量的系数为0，而人工变量的系数为M（很大的正数）二、求出一个基本可行解1.用非基变量表示基变量和目标函数式5524313212252834xxxMxxxMxxxMMxMxxMxMxM73834543212.求出一个基本可行解及相应的z值三、最优性检验1.最优性检验的依据—检验数j2.最优解判别定理：若在极小化问题中，对于某个基本可行解，所有检验数j0，且人工变量为0，则这个基本可行解是最优解。对于极大化问题，只要把上述定理中的j0改成j0即可。这里的检验数j即为（cj-zj）。3.无穷多最优解判别定理：若在极小化问题中，对于某个基本可行解，所有检验数j0，又存在某个非基变量的检验数为0，且人工变量为0，则线性规划问题有无穷多最优解。4.无可行解情况若在极小化问题中，对于某个基本可行解，所有检验数j0，但人工变量0，则该线性规划问题无可行解。四、基变换1.基本可行解的改进定理2.换入变量的确定3.换出变量的确定最小非负比值规则=br/ark=imin{bi/aik|aik0}在单纯形法迭代中，基变换带来可行域顶点的变换，且相邻两次迭代所对应的顶点也是相邻的。4.无有限最优解（无界解）判定定理：若在极小化问题中，对于某个基本可行解，有一个非基变量的检验数k0，但Pk列中没有正元素，且人工变量为0，则线性规划问题无有限最优解（具有无界解）。2.2单纯形法的表格形式一、构造初始可行基，并计算检验数jj=cj-zjzj=(c1,c2,…,cm)•Pj=(CB)•P'j二、从表中找到基本可行解和相应目标函数值三、最优性检验四、基变换1.换入变量的确定负检验数中最小2.换出变量的确定最小非负比值规则3.主元素的确定换入元素所在列和换出元素所在行交点处的元素4.取主变换通过矩阵行的初等变换，把换入向量变换为单位列向量。即基变换，亦即单纯形法的一次迭代。2.3大M法和两阶段法根据处理人工变量的方法不同，单纯形法的两种常见形式。大M法也叫罚函数法，前已介绍。两阶段法将线性规划问题的求解分为两个阶段。第一阶段：判断原线性规划问题是否有可行解。该阶段所要求解的线性规划问题的约束条件即原问题的约束条件，而目标函数取全部人工变量之和，求其最小值。若求解结果是上述目标函数的最小值为0，则说明所有人工变量都能退出基，原问题有可行解，且第一阶段的最终单纯型表上的基本可行解就是原问题的一个基本可行解。若求解的结果是上述目标函数的最小值大于0，则说明最终人工变量不能完全退出基，原问题无可行解，应停止计算。第二阶段：求解原线性规划问题的最优解。以第一阶段的最终单纯型表为基础，去掉其中的人工变量列，把目标函数换成原问题的目标函数，并修正因cj改变而改变的(CB)T、j和-z。以此作为第二阶段的初始表，继续迭代，得原问题的最优解。438000迭代次数TBC基变量1x2x3x4x5xb13823xx22010022311912.4退化问题一、什么是退化当基本解、基本可行解、最优基本可行解中有基变量为0时，即出现了退化。退化情况下，即使存在最优解，也可能出现循环现象，即迭代过程总是重复解的某一部分序列，目标函数值总是不变，永远达不到最优解。二、摄动法1.摄动法简介对线性规划原问题，为了避免退化情况下发生循环，而使向量b摄动。2.确定换出变量的步骤3.举例三、勃兰特方法法则1：在极小化问题中，如果有几个检验数（cj-zj）都是负的，那么选其中下标最小的非基变量作为换入变量。法则2：在极小化问题中，根据最小非负比值规则确定换出变量时，如果有几个比值同时达到最小比值，那么选其中下标最小的基变量作为换出变量。定理：只要在迭代时，遵循上述法则，就不会出现循环。3.5改进单纯形法每次迭代只计算换入列、常数列及检验数行以提高计算效率。一、单纯形法的矩阵形式1.用矩阵（分块）形式表示线性规划标准型把矩阵A、C、X分别按“基”与“非基”分成两块A=(B,N)C=(CB,CN)NBXXX其中B=（P1，P2，…，Pm）N=（P1m，P2m，…，Pn）CB=（c1,c2,…,cm）CN=(c1m,c2m,…,cn)XB=mxxx21XN=nmmxxx21将分块结果代入标准型，得BXB+NXN=bXB0,XN0BCzminBX+CNXN2.用矩阵（分块）形式表示基本解、目标函数值及检验数XB=B1b-B1NXNz=CBB1b+(CN-CBB1N)XNN=CN-CBB1N令XN=0，可得XB=B1bz=CBB1b3.单纯型乘子Y。Y=CBB1二、改进单纯形法的求解步骤1.完成第0次迭代表。构造初始可行基，计算B10。再利用公式0N=C0N-C0BB10N0=C0N-C0BN0，计算第0次迭代表中的检验数。确定换入向量为Pk，换出向量为PBr，主元素是ark。令i=02.计算B11i1）构造基矩阵B1i2）计算B11i第一种方法：已知B1i，用初等变换法求其逆矩阵B11i。第二种方法：已知B1i和第i次迭代表的换入列P'k，主元素为a'rk，通过取主变换求出B11i。3.计算