大学运筹学课程知识点总结.doc

_1. 用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。 2.将下述线性规划问题化成标准形式。 （1） 解：令， 3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。 解：图解法：单纯形法：将原问题标准化：Cj10500q对应图解法中的点CBBbx1x2x3x40x3934103O点0x4852018/5sj0105000x321/5014/51-3/53/2C点10x18/512/501/54sj-16010-25x23/2015/14-3/14B点10x1110-1/72/7sj35/200-5/14-25/14最优解为（1,3/2,0,0），最优值Z=35/2。单纯型法步骤：转化为标准线性规划问题；找到一个初始可行解，列出初始单纯型表；最优性检验，求cj-zj，若所有的值都小于0，则表中的解便是最优解，否则，找出最大的值的那一列，求出bi/aij，选取最小的相对应的xij，作为换入基进行初等行变换，重复此步骤。 4.写出下列线性规划问题的对偶问题。（1）（2）5. 给出线性规划问题要求：（1）写出其对偶问题；（2）已知原问题最优解为，试根据对偶理论，直接求出对偶问题的最优解。解：（1）（2）因为，第四个约束取等号，根据互补松弛定理得：求得对偶问题的最优解为：，最优值min w=16。弱对偶性的推论：(1) 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界(2) 如原问题有可行解且目标函数值无界(具有无界解)，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然。(3) 若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。强对偶性(或称对偶定理) 若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。互补松弛性在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。影子价格资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。影子价格是一种边际价格。资源的影子价格实际上又是一种机会成本。随着资源的买进卖出，其影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。影子价格反映单纯形表中各个检验数的经济意义。一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用对偶单纯型法：转化成标准的线性规划问题；确定换入基变量，bi小于0中的最小的那一排，再求（cj-zj）/aij，且aij0,d+,d-0目标规划的图解法：先画绝对约束的可行域，然后按照优先性优先考虑某个目标约束，随着min系数中d+或者d-的增大移动曲线，画出最合适的那条，直到最后10.用割平面法解下列整数规划：（1）解：引进松弛变量，将问题化为标准形式，用单纯形法解其松弛问题。cj1100qCBXBbx1x2x3x40x36【2】11030x42045015sj11001x1311/21/2060x480【3】-218/3sj01/2-1/201x15/3105/6-1/61x28/301-2/31/3sj00-1/6-1/6找出非整数解变量中分数部分最大的一个基变量（x2），并写下这一行的约束：将上式中的所有常数分写成整数与一个正的分数值之和得：将上式中的分数项移到等式右端，整数项移到等式左端得：得到割平面约束为：引入松弛变量，得割平面方程为：cj11000CBXBbx1x2x3x4x51x15/3105/6-1/601x28/301-2/31/300x5-2/300【-1/3】-1/31sj00-1/6-1/60sj/arj1/21/21x10100-15/21x240101-20x320011-3sj0000-1/2最优解为，最优值为s4=0，最优解不唯一？11.用分支定界法解下列整数规划（1）解：最优解（3,1），最优值z=7。12. 匈牙利解法：见课本145页13.如图，是一仓库，是商店，求一条从到的最短路。解：P=T=0T=T=T=T=T=T=T=T=T=P=T=2T=T=11T=T=7T=T=4T=T=T=13T=11T=T=7T=P=T=4T=T=T=13T=11T=P=T=7T=11T=13T=T=13P=T=11T=T=11T=13T=T=13T=16P=T=11T=13T=P=T=13T=16T=13T=20T=16P=T=13T=19P=T=16T=19P=19最短路长为19。最短路为：0129，0329，0349，01249，0789。14.如图，发点，分别可供应10和15个单位，收点，可以接收10和25个单位，求最大流，边上数为。最大流为2115.如图所示网络中，有向边旁数字为，表示容量，表示单位流量费用，试求到流值为六的最小费用流。解：d(f)=3716. 图的生成树：（一）避圈法在图中任取一条边e1，找一条与e1不构成圈的边e2，再