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

1、1.用图解法求解下列线性规划问题，并指出问题具有惟一最优解、无穷多最优解、无界解还是无可行解。max zx1x26x110x21205x1103x282.将下述线性规划问题化成标准形式。min z3x14x22x35x44x1x22x3x42x1x2x32x414（ 1）3x2x3x422x1x1, x2, x30, x4无约束解：令 z'z ， x4x4'x4''max z'3x4x22x35x'5x''1444xx22xx'x''21344xx2x32x'2x''x5141442

2、x3x2x3x'x''x62144x , x2, x3, x ', x'', x5, x601443.分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中的可行域的哪个顶点。max z10x15x23x14 x295x12x28x1 , x20解：图解法：单纯形法：将原问题标准化：max z10x15x23x14x2 x395x12x2x4 8x1, x2 , x3 , x40Cj10500对应图解法CBBbx1x2x3x4中的点0x39341030x4852018/5O 点j0105000x321/5014/

3、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/2,0,0 ），最优值Z=35/2 。单纯型法步骤：转化为标准线性规划问题；找到一个初始可行解，列出初始单纯型表；最优性检验，求cj-zj，若所有的值都小于0，则表中的解便是最优解，否则，找出最大的值的那一列，求出 bi/aij ，选取最小的相对应的 xij ，作为换入基进行初等行变换，重复此步骤。4.写出下列线性规划问题的对偶问题。mnmin zc ijxiji 1j 1nx ija ii1, m

4、j1（1）ms.t .x ijb jj1, ni1xij0i1, m ; j 1, nmnmax wai yib jy jmi 1i1yiym jciji 1, , m; j1, , ns.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 1maij yic jj1,2,n1ni1ms.t.aij yic jjn11,ni1yi0i1,2,m1myi 无约束im11,m5. 给出线性规划问题max z2x14x2x3

5、x4x13x2x482x1x26s.t.x2x3x46x1x2x39xj0 j1,4要求：（1）写出其对偶问题； （ 2）已知原问题最优解为 X *2,2,4,0T，试根据对偶理论，直接求出对偶问题的最优解。解：min w8 y16 y26 y39 y4y12 y2y42（1）3y1y2y3y44s.t .y3y41y1y31y j0 j1,4（2）因为 x1 , x2 , x30 ，第四个约束取等号，根据互补松弛定理得：y1 2 y2y423y1y2y3y44y3y41y40求得对偶问题的最优解为：Y *4,3,1,0 ，最优值 min w=16 。55例 已知原问题Max z =x1 +

6、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 、 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 +

7、 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.2>0，而 y1与x5中至少有一个为零，故 x5 =0。（2）同理， y2=0.2>0，所以 x6 =0。（3）对偶问题的第一个约束条件在取最优值时y1 +2y2=1.2+2×0.2=1.6>1这

8、就表示该约束条件的松弛变量：y3 =1.6 1=0.6>0y3与x1中至少有一个为零，故 x1=0。（4）同理，对于第 2个约束条件在取得最优值时2y1+y2 = 2×1.2+0.2=2.6>2y4=2.6 2=0.6>0y4与x2中至少有一个为零，故 x2=0。（ 5）同理，对于第3个约束条件在取得最优值时2y1+3y2 = 2× 1.2+ 3 × 0.2=3y5=3 3=0y5与x3中至少有一个为零，故 x3>0或者 x3=0 。（ 6）对于第 4个约束条件的分析也可得到x4>0 或者 x4=0 。对于（ 5） 和（ 6）的分析，

9、对于确定原问题的最优解没有任何帮助。但从（ 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、，是未知数。因企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。影子价格是一种边际价格。资源的影子价格实际上又是一种机会成本。随着资源的买进卖出，其影子价格也将随之发生变化，一直到影子价格与市场价格保持同等水平时，才处于平衡状态。生产过程中如果某种资源未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。影子价格反映单纯形表中各个检验数的经济意义。一般说对线性规划问题的求解是确定资源的最优分配方案， 而对于对偶问题的求解则是确定对资源的恰当估价，这种估价直接涉及资源的最有效利用对偶单纯型法： 转化成标准的线性规划问题； 确定换入基变

12、量， bi 小于 0 中的最小的那一排，再求（ cj-zj ）/aij ，且 aij<0, 找出最小值，这对应的 xi 便是换入基，若所有的 bi 都大于 0，则找到了最优解7 下列表分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。注意要基可行解的个数一定是行列变量数减一销地B1产地A 14A 21A 33销量6解：（ 1）确定初始方案西北角法：销地产地B1A 16A 2A 36销量最小元素法：销地B 1产地A 1A 25A 31销量6沃格尔法：销地B1产地A 14A 216A 33销量6B2B 314257556B2B3235156B2B35

13、3356B2B3B414653250275131563B 4产量680814320B 4产量8834320B 4产量8384320产量行罚数12348022381154124420列12111211罚2311数4158.下表给出一个运输问题及它的一个解，试问：（ 1）表中给出的解是否为最优解？请用位势法进行检验。（ 2）若价值系数 C24 由 1 变为 3，所给的解是否仍为最优解？若不是，请求出最优解。（ 3）若所有价值系数均增加 1，最优解是否改变？为什么？（ 4）若所有价值系数均乘以 2，最优解是否改变？为什么？销地B 1B2B 3B4产量产地A 14146853A 212611082A

14、33751431销量856322解：（ 1）销地B1B 2B3B4产量ui产地A 141468053A 2126110182A 337514131销量856322vj0140空格检验数为：460125所有检验数均大于等于零，该方案为最优方案。（2）若价值系数C24由 1 变为 3，6-2-1645由于有检验数小于零，所以此方案不是最优方案。5（ -2）3（ +2）8（+2）2（ -2）3（ -2）1（ +2）调整为：358213空格检验数为：461225所有检验数均小于等于零，该方案为最优方案。min z3 1548122153143 。（ 3）不改变，不影响检验数的大小。（ 4）不改变，不影

15、响检验数的符号。解的最优性检验：1. 闭回路法：找各个非基变量的闭合回路，依次加减求检验数，是先减再加，若所有的检验数的值都全非负，那么此可行解是最优解。2. 位势法（对偶变量法）：增加位势列 ui 和位势行 vj ；计算位势，ui+vj=基可行解的对应的运费，指定其中某一值为 0，算出其他几位的值，填入表中；计算检验数，某非基变量对应的运费减对应的位势行和位势列，若检验数全为非负，则为最优解。（检验数都是非基变量经过处理后的值，处理过程中应用的是基变量）解的改进： 1. 以检验数小于 0 的 xi 为换入基（取最小的那个）2. 找此 xi 的闭合回路， 以 xi 为始沿顺逆时针方向把定点依次

16、编号3.在所有偶数顶点中，找出运输量最少的顶点作为xi的换出变量4.将基数顶点的运输量增加xj ，偶数顶点的运输量减少xj ，重新得到一组新的方案5. 进行解的最优性检验9.公司决定使用1000 万元新产品开发基金开发A ，B，C 三种新产品。 经预测估计， 开发 A ，B ，C 三种新产品的投资利润分别为 5%、 7%、 10% 。由于新产品开发有一定风险，公司研究后确定了下列优先顺序目标：第一， A 产品至少投资 300 万元；第二，为分散投资风险，任何一种新产品的开发投资不超过开发基金总额的35% ；第三，应至少留有 10%的开发基金，以备急用；第四，使总的投资利润最大。试建立投资分配方

17、案的目标规划模型。解，设 A ， B， C 三种新产品的开发投资额分别为x1 , x2 , x3 万元，目标规划模型为：min P1d1 , P2 d2d3 d 4 , P3 d5 , P4 d 6x1d1d1300x1d2d2100035%x2d3d 3100035%s.t. x3d 4d4100035 %1000x1x2x3d5d 5100010%5% x17% x210% x3d6d6100010%x1 , x2 , x3 , di, di0 i1,6Pl是优先因子，关系为l越小，则有绝对的优先性，还有一种是相对的优先性，用权系数来表示目标规划的一般格式 ;minpld+ 或 d-（要明

18、白为什么是写min 里的 d 是要取值为零的，即若不等式要大于零时，则写d+或 d- ， d- ）；必须要满足的绝对约束，还有目标约束；xj>0,d+,d->0目标规划的图解法： 先画绝对约束的可行域， 然后按照优先性优先考虑某个目标约束，随着 min 系数中 d+或者 d- 的增大移动曲线，画出最合适的那条，直到最后10.用割平面法解下列整数规划：max zx1 x22 x1x26（1）5x2s.t . 4 x120x1 , x20, 且为整数解：引进松弛变量x3 , x4 ，将问题化为标准形式，用单纯形法解其松弛问题。cj1100CBX Bbx1x2x3x40x36【 2】11

19、030x42045015j11001x1311/21/2060x480【 3】-218/3j01/2-1/201x15/3105/6-1/61x28/301-2/31/3j00-1/6-1/6找出非整数解变量中分数部分最大的一个基变量（x2），并写下这一行的约束：x22 x31 x42 2333将上式中的所有常数分写成整数与一个正的分数值之和得：x211 x301 x422333将上式中的分数项移到等式右端，整数项移到等式左端得：x2x3 22 1 x31 x4333得到割平面约束为：1 x31 x42x5 ，得割平面方程为：333引入松弛变量11x4x523x333cj11000CBX Bbx1x2x3x4x51x15/3105/6-1/601x28/301-2/31/300x5-2/300【 -1/3】-1/31j00-1/6-1/60j/arj1/21/21x10100-15/21x240101-20x320011-3j0000-1/2最优解为 X *0,4,2,0,0Tmax z4，最优值为4=0 ，最优解不唯一？11.用分支定界法解下列整数规划max z2x1x2x1x25（1）x1x