《2022年大学运筹学课程知识点总结》由会员分享，可在线阅读，更多相关《2022年大学运筹学课程知识点总结（14页珍藏版）》请在金锄头文库上搜索。
1、1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。83105120106max212121xxxxxxz2.将下述线性规划问题化成标准形式。（1）无约束4, 03, 2, 12321422245243min4321432143214321xxxxxxxxxxxxxxxxxxxxz解：令zz， 444xxx0,232142222455243max65 443216 443215 44321 44321 44321xxxxxxxxxxxxxxxxxxxxxxxxxxxxxz3.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对
2、应精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 14 页图解法中的可行域的哪个顶点。0,825943510max21212121xxxxxxxxz解：图解法：单纯形法：将原问题标准化：0,825943510max432142132121xxxxxxxxxxxxzCj10 5 0 0 对应图解法中的点CBB b x1x2x3x40 x39 3 4 1 0 3 O 点0 x48 5 2 0 1 8/5 j 0 10 5 0 0 0 x321/5 0 14/5 1 -3/5 3/2 C 点10 x18/5 1 2/5 0 1/5 4 j-1
3、6 0 1 0 -2 5 x23/2 0 1 5/14 -3/14 B 点10 x11 1 0 -1/7 2/7 j35/2 0 0 -5/14 -25/14 最优解为（ 1,3/2,0,0） ，最优值Z=35/2。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 14 页单纯型法步骤：转化为标准线性规划问题；找到一个初始可行解，列出初始单纯型表；最优性检验，求cj-zj，若所有的值都小于0，则表中的解便是最优解，否则，找出最大的值的那一列，求出bi/aij，选取最小的相对应的xij ，作为换入基进行初等行变换，重复此步骤。4.写出下列线
4、性规划问题的对偶问题。（1）njmixnjbxmiaxtsxczijjmiijinjijminjijij,1;,10,1, 1.min1111无约束jiijjminimjjmiiiyxnjmicyytsybyaw, 1;, 1.max11（2）nnjxnnjxmmmibxammibxatsxczjjinjjijinjjijnjjj, 1, 10,2, 1, 1.max11111111无约束mmiymmiynnjcyannjcyatsybwiijmiiijjmiiijmiii, 1, 2, 10, 1,2, 1.min1111111无约束精选学习资料 - - - - - - - - - 名师归纳
5、总结 - - - - - - -第 3 页，共 14 页5. 给出线性规划问题4, 10966283.42max321432214214321jxxxxxxxxxxxxtsxxxxzj要求： （1）写出其对偶问题； （2）已知原问题最优解为TX0 ,4, 2,2*，试根据对偶理论，直接求出对偶问题的最优解。解：（1）4, 10114322.9668min314343214214321jyyyyyyyyyyyytsyyyywj（2）因为0,321xxx，第四个约束取等号，根据互补松弛定理得：0143224434321421yyyyyyyyyy求得对偶问题的最优解为：0 , 1 ,53,54*Y，
6、最优值 min w=16 。例已知原问题Max z =x1 + 2x2 +3x3 +4x4x1 + 2x2 +2x3 +3x4202x1 + x2 +3x3 +2x420x1、 x2、 x3、x4 0和对偶问题Min w =20y1 + 20 y2y1 + 2y2 12y1 + y2 22y1 + 3 y2 33y1 + 2 y2 4y1、 y2 0已知对偶问题的最优解y1 = 1.2 、 y2 =0.2 ，最优值min w=28，求原问题的最优解及最优值。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 14 页可用如下方法求解：引入将
7、原问题和对偶问题化为标准形式。Max z =x1 +2x2 +3x3 +4x4x1 +2x2 +2x3 +3x4 +x5 = 202x1 +x2 +3x3 +2x4 +x6 =20x1、x2、x3、x4 、x5 、x6 0Min w =20y1 +20y2y1 +2y2 y3 = 12y1 +y2 y4 = 22y1 +3y2 y5 = 33y1 +2y2 y6 = 4y1、y2 、y3 、y4 、y5 、y6 0和（1） y1=1.20，而y1与x5中至少有一个为零，故 x5=0。（2）同理，y2=0.20，所以 x6=0。（3）对偶问题的第一个约束条件在取最优值时y1+2y2=1.2+20
8、.2=1.61这就表示该约束条件的松弛变量：y3=1.61=0.60y3与x1中至少有一个为零，故x1=0。（4）同理，对于第2个约束条件在取得最优值时2y1+y2= 21.2+0.2=2.62y4=2.62=0.60y4与x2中至少有一个为零，故 x2=0。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 14 页（5）同理，对于第3个约束条件在取得最优值时2y1+3y2= 21.2+ 30.2=3y5=3 3=0y5与x3中至少有一个为零，故 x30或者 x3=0 。（6）对于第 4个约束条件的分析也可得到x40或者 x4=0 。对于
9、（ 5） 和（ 6）的分析，对于确定原问题的最优解没有任何帮助。但从（ 1）到（ 4）的分析中得知，原问题取得最优解时：x5=0，x6=0，x1=0，x2=0代入原问题的约束方程组得：2x3+3x4= 203x3+2x4= 20解此方程组，可求得原问题的最优解为：x1=0，x2=0 ，x3=4 ，x4=4 ，x5=0，x6=0弱对偶性的推论：(1) 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界(2) 如原问题有可行解且目标函数值无界( 具有无界解 ) ，则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问
10、题无可行解。注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然。(3) 若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。强对偶性 (或称对偶定理 ) 若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。互补松弛性在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。影子价格资源的市场价格是其价值的客观体现，相对比较稳定，而它的影子价格则有赖于资源的利用
11、情况，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。影子价格是一种边际价格。资源的影子价格实际上又是一种机会成本。随着资源的买进卖出，其影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 14 页的影子价格不为零时，表明该种资源在生产中已耗费完毕。影子价格反映单纯形表中各个检验数的经济意义。一般说对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求
12、解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用对偶单纯型法： 转化成标准的线性规划问题；确定换入基变量， bi 小于 0 中的最小的那一排，再求（ cj-zj）/aij，且 aij0,d+,d-0 目标规划的图解法： 先画绝对约束的可行域， 然后按照优先性优先考虑某个目标约束，随着min 系数中 d+或者 d-的增大移动曲线，画出最合适的那条，直到最后10.用割平面法解下列整数规划：（1）且为整数,0,205462.max21212121xxxxxxtsxxz解：引进松弛变量43,xx，将问题化为标准形式，用单纯形法解其松弛问题。cj1 1 0 0 CBXBb x1x2x3x40
13、 x36 【2】1 1 0 3 0 x420 4 5 0 1 5 j1 1 0 0 1 x13 1 1/2 1/2 0 6 0 x48 0 【 3】-2 1 8/3 j0 1/2 -1/2 0 1 x15/3 1 0 5/6 -1/6 1 x28/3 0 1 -2/3 1/3 j0 0 -1/6 -1/6 找出非整数解变量中分数部分最大的一个基变量（x2） ，并写下这一行的约束：3223132432xxx精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 14 页将上式中的所有常数分写成整数与一个正的分数值之和得：322310311432
14、xxx将上式中的分数项移到等式右端，整数项移到等式左端得：43323131322xxxx得到割平面约束为：32313143xx引入松弛变量5x，得割平面方程为：323131543xxxcj1 1 0 0 0 CBXBb x1x2x3x4x51 x15/3 1 0 5/6 -1/6 0 1 x28/3 0 1 -2/3 1/3 0 0 x5-2/3 0 0 【-1/3】-1/3 1 j0 0 -1/6 -1/6 0 j/arj1/2 1/2 1 x10 1 0 0 -1 5/2 1 x24 0 1 0 1 -2 0 x32 0 0 1 1 -3 j0 0 0 0 -1/2 最优解为TX0 ,0
15、, 2, 4, 0*，最优值为4max z4=0，最优解不唯一？11.用分支定界法解下列整数规划（1）且为整数,0,2126052max2121212121xxxxxxxxxxz解：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 14 页最优解（ 3,1） ，最优值z=7。12.匈牙利解法：见课本145 页13.如图，0v是一仓库，9v是商店，求一条从0v到9v的最短路。解：0v1v2v3v4v5v6v7v8v9vP=T=0 T=T=T=T=T=T=T=T=T=P=T=2 T=T=11 T=T=7 T=T=4 T=T=T=13 T=1
16、1 T=T=7 T=P=T=4 T=T=T=13 T=11 T=P=T=7 T=11 T=13 T=T=13 P=T=11 T=T=11 T=13 T=T=13 T=16 P=T=11 T=13 T=P=T=13 T=16 T=13 T=20 T=16 P=T=13 T=19 P=T=16 T=19 P=19 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 14 页最短路长为19。最短路为：0129，0329，0349，01249，0789。14.如图，发点1s，2s分别可供应10 和 15 个单位，收点1t，2t可以接收 10 和
17、25 个单位，求最大流，边上数为ijc。最大流为21 15.如图所示网络中，有向边旁数字为ijijdc ,，ijc表示容量，ijd表示单位流量费用，试求sv到tv流值为六的最小费用流。解： d(f)=37 16.图的生成树：（一）避圈法在图中任取一条边e1，找一条与e1 不构成圈的边e2，再找一条与 e1，e2不构成圈的边e3。一般设已有 e1，e2，ek ，找一条与 e1， e2，ek 中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 14 页（二）破圈法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 14 页
