《《运筹学》知识点总结》由会员分享，可在线阅读，更多相关《《运筹学》知识点总结（14页珍藏版）》请在金锄头文库上搜索。
1、1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。max zx1x26x110x21205x1103x282.将下述线性规划问题化成标准形式。min z3x14x22x35x44x1x22x3x42（ 1）x1x2x32x4142x1 3x2x3x42x1, x2, x30, x4无约束解：令 zz ， x4x4x4max z3x4x22x35x5x1444xx22xxx21344xx2x32x2xx5141442x3x2x3xxx62144x1, x2 , x3 , x4 , x4 , x5 , x603.分别用图解法和单纯形法求解下述线性规划问题
2、，并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。max z10x15x23x14 x295x12x28x1 , x20解：图解法：单纯形法：将原问题标准化：max z10x15x23x14x2 x395x12x2x4 8x1, x2 , x3 , x40Cj10500对应图解法CBBbx1x2x3x4中的点0x39341030x4852018/5O 点j0105000x321/5014/51-3/53/210x18/512/501/54C 点j-16010-25x23/2015/14-3/1410x1110-1/72/7B 点j35/200-5/14-25/14最优解为（ 1
3、,3/2,0,0 ），最优值Z=35/2 。单纯型法步骤：转化为标准线性规划问题；找到一个初始可行解，列出初始单纯型表；最优性检验，求cj-zj，若所有的值都小于0，则表中的解便是最优解，否则，找出最大的值的那一列，求出 bi/aij ，选取最小的相对应的 xij ，作为换入基进行初等行变换，重复此步骤。4.写出下列线性规划问题的对偶问题。mnmin zc ij xiji 1j 1nx ija ii1, mj1（1）ms.t .x ijb jj1, ni1x ij0i1, m ; j1, nmnmax wai yib jy jmi 1i1yiym jciji 1, , m; j1, , ns.
4、t.xi , y j 无约束nmax zc jx jj 1nj1aij x jbii 1, m1m（2）naij x jbiim11,m12, ms.t.j1x j0j1,n1nx j无约束jn11, nmmin wbi yii 1maijyic jj1,2,n1ni 1ms.t.aijyic jjn11,ni 1yi0i1,2,m1myi 无约束im11, m5. 给出线性规划问题max z2x14 x2x3x4x13x2x482x1x26s.t.x2x3x46x1x2x39xj0 j1,4要求：（1）写出其对偶问题； （ 2）已知原问题最优解为 X *2,2,4,0 T ，试根据对偶理论，
5、直接求出对偶问题的最优解。解：min w8 y16 y26 y39y4y12y2y42（1）3y1y2y3y44s.t.y3y41y1y31y j0 j1,4（2）因为 x1 , x2 , x30 ，第四个约束取等号，根据互补松弛定理得：y12 y2y423y1y2y3y44y3y41y40求得对偶问题的最优解为：Y *4,3,1,0 ，最优值 min w=16 。55例 已知原问题Max z =x1 + 2 x 2 + 3 x 3 + 4 x 4x 1 + 2 x 2 + 2 x 3 + 3 x 4 202x 1 + x 2 + 3 x 3 + 2 x 4 20x 1、 x 2 、 x 3
6、、 x 4 0和对偶问题Min w =20y1 + 20 y 2y 1 + 2 y 2 12y1+ y222y1+ 3 y233y1+ 2 y24y 1 、 y 2 0已知对偶问题的最优解y 1 = 1.2 、 y 2 =0.2，最优值 min w=28，求原问题的最优解及最优值。可用如下方法求解：引入将原问题和对偶问题化为标准形式。Max z =x1 + 2x2 + 3x3 + 4x4x1 + 2x2 + 2x3 + 3x4 + x5= 202x1 + x2 + 3x3 + 2x4+ x6 =20x1、x2、 x3 、x4 、x5 、 x6 0和Min w =20y 1 + 20 y2y1 + 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.2=1.61这就表示该约束条件的松弛变量：y3 =1.6 1=0.60y3与x1中至少有一个为零，故 x1=0。（4）同理，对于第 2个约束条件在取得最优值时2y1+y2 = 21.
