运筹学周四

求解如下线性规划问题0,,12324112..3min32131321321321xxxxxxxxxxxtsxxxz111-211000113-4120-1103/21-20[1]000110M16xx4x3103-20100-110[1]00-11-211-2010001-3x11x21x341001/3-2/32/3-5/310100-11-2900102/3–4/3-7/3-31100MM-10001M-1M+1zj-cj0001/31/3M-1/3M-2/3zj-cj0x41x21x312[3]001-22-5410100-11-21-2010001cj0MMX4X6X7bCBXBX1X2X3X4X5X6X7i-3+6M1-M1-3M0M00cj-zj-11-M00M03M-1cj-zj最优解是0,9,1,47654321xxxxxxx目标函数为-2。第一阶段：求解辅助规划问题0,,,,,12324112..min76532173165321432176xxxxxxxxxxxxxxxxxxtsxx2、两阶段法111-211000113-4120-1103/21-20[1]000110106xx4x3103-20100-110[1]00-11-211-201000100000110000011zj-cj0x40x20x312[3]001-22-5410100-11-21-2010000cj011X4X6X7bCBXBX1X2X3X4X5X6X7i6-1-30100cj-zj0-100103cj-zj12[3]001-2410100-11-20100-3112xx1x341001/3-2/310100-190012/3-4/3-31100cj011X4X2X3bCBXBX1X2X3X4X5i-10001cj-zj0001/31/3cj-zjx6，x7是人工变量，第一阶段求解的最优结果是=0，因此得最优解为：0,12,1,1,07654321xxxxxxx第二阶段：取消人工变量，添入原问题目标函数的系数，求解相应的线性规划。最优解为：914321xxx最优值为：z=-2（无可行解）求解下列线性规划问题解：首先将问题化为标准型令，则1231231323123minZ=3x+2x+xxxx6x-x4x-x3x,x,x0'12378123413572368MMmaxZ=-3x-2x-x-x-xx+x+x+x=6x-x-x+x=4x-x-x+x=3xj0,j=1,2,8.'Z=-Z故引入人工变量，并利用大M法求解78x,x1231234135236'maxZ=-3x-2x-xx+x+x+x=6x-x-x=4x-x-x=3xj0,j=1,2,6.C-3-2-1000-M-MCBXBbx1x2x3x4x5x6x7x8θ0-M-Mx4x7x86431111000010-10-101001-100-1016/1-3/1Z’-7M-6-4M-15-M-3+M-2+M-1-2M0-M-M000-M-2x4x7x23431021010-110-10-101001-100-1013/14/1-Z’Z’-3+M0-3-M0-M-202-M-3-M-2x1x7x23131021010-100-3-1-1-11101-100-101003-3M3-M-M1-M0-1在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量x7=1为基变量，所以原线性规划不存在可行解。（无界解）试用单纯形法求解下列线性规划问题：解：引入松弛变量x3,x4化为标准型12121212maxZ=2x+2xx-x-11-xx22x0,x012123124jmaxZ=2x+2x-xxx11-xx+x22x0,j1,2,3,4C2200θCXBBx1x2x3x40X31-11100X42-1/2101Z022001=20因但所以原问题无最优解1-1P=01-2（退化）求解下述线性规划问题：解：引入松弛变量化标准型1234123412343jmaxZ=3x-80x+2x-24xx-32x-4x36x0x-24x-x6x0x1x0,j1,2,3,41234123451234637jmaxZ=3x-80x+2x-24xx-32x-4x36xx0x-24x-x6xx0xx1x0,j1,2,3,4,5,6,7567x,x,x000-242-8030Z-5-60-420-805Z10001001x3212060-2411x13321300-803x500-30-425-800Z11001001x700106-1-2410x130-1130-3-800x50-11001001x7000106-1-2410x60000136-4-3210x50x7x6x5x4x3x2x1bXBCB000-242-803Cθ第一次迭代中使用了摄动法原理，选择下标为6的基变量x6离基。可得最优解，目标函数值maxZ=５，X1,0,1,0,3T000-242-8030Z00-3-132141600Z11001001x7001-1-30380000-1136-4-3210x53-11001001x7000106-1-2410x60000136-4-3210x50x7x6x5x4x3x2x1bXBCBθx1勃兰特法则无穷多最优解：32132minxxxZ0,,62382432121321xxxxxxxx用大M法或者二阶段法求解764321''*032maxMxMxxxxxZZZ0,,,,,,6238247654321752164321xxxxxxxxxxxxxxxx标准型：其中M是一个任意大的正数Cj-2-3-100-M-Mθ-M8142-10102-M63200-1013C-Z4M-26M-32M-1-M-M00CBXBbx6x7x1x2x3x4x5x6x7Cj-2-3-100-M-Mθ-321/411/2-1/401/408-M25/20-11/2-1-1/214/5C-Z5/2M-5/401/2-M1/2M-3/4-M-3/2M+3/40CBXBbx7x1x2x3x4x5x6x7x2Cj-2-3-100-M-Mθ-39/5013/5-3/101/103/10-1/102-24/510-2/51/5-2/5-1/52/53C-Z000-1/2-1/21/2-M1/2-MCBXBbx1x2x3x4x5x6x7x2x1可得最优解（4/5,5/8,0,0,0,0,0）如下表，是某求极大化线性规划问题计算得到的单纯形表。表中无人工变量，a1，a2，a3，d，c1，c2为待定常数。试说明这些常数分别取何值时，以下结论成立。（1）表中解为唯一最优解（2）表中解为最优解，但存在无穷多最优解（3）该线性规划问题具有无界解（4）表中解非最优解，为对解改进，换入变量为x1，换出变量为x6基BX1X2X3X4X5X6X3d4a110a20X42-1-301-10X63a3-500-41Cj-Zjc1c200-30433da•（1）当解为最优解时，必有d≥0，c1‹0，c2‹0。•（2）当解为最优解，但存在无穷多最优解时，必有d≥0，c1≤0，c2=0或d≥0，c1=0，c2≤0•（3）当该问题为无界解时，必有d≥0，c1≤0，c2›0且a1≤0。•（4）当解为非最优，为对解进行改进，当换入变量为x1，换出变量为x6，必有d≥0，c1‹0且•c1≥c2，a3›0，无穷多最优解无穷多最优解判别原理：若线性规划问题某个基本可行解所有的非基变量检验数都小于等于零，但其中存在一个检验数等于零，那么该线性规划问题有无穷多最优解。例３：最优表：非基变量检验数，所以有无穷多最优解。最优解集为可行域两个顶点的凸组合：C12000θCBXBbx1x2x3x4x5021x3x2x12320012-101010100-212/23/1-Z’80000-14=0X(2,3,2,0,0)(1)4,2,0,1,0,01.TT退化解当线性规划问题的基本可行解中有一个或多个基变量取零值时，称此基本可行解为退化解。产生的原因：在单纯形法计算中用最小比值原则确定换出变量时，有时存在两个或两个以上相同的最小比值θ，那么在下次迭代中就会出现一个甚至多个基变量等于零。遇到的问题：当某个基变量为零，且下次迭代以该基变量作为换出变量时，目标函数并不能因此得到任何改变（由旋转变换性质可知，任何一个换入变量只能仍取零值，其它基变量的取值保持不变）。通过基变换以后的前后两个退化的基本可行解的坐标形式完全相同。从几何角度来解释，这两个退化的基本可行解对应线性规划可行域的同一个顶点，解决的办法：最小比值原则计算时存在两个及其以上相同的最小比值时，选取下标最大的基变量为换出变量，按此方法进行迭代一定能避免循环现象的产生（摄动法原理）。