【图文】运筹学复习大纲汇总

1、运筹学复习大纲唯一最优解2个变:没有有限的最优角大M法无穷多个最优解引人工*本可行解max线性规划3个以上图解法标准型两阶段法对偶单纯形解题方法：（1）建立直角坐标系：以决策变量Xl ,x2为坐标轴。.（2）绘制可行域：对每个约束条件（包括xi 0）,先取其为等式，并在坐标系中作出相应 的直线，判定不等式所决定的半平面若各约束半平面交出的区域存在， 则其中的点称为线性规划的可行解， 所有可 行解组成的集合称为可行域或可行集若不存在，线性规划无可行解、（3）绘制目标函数等值线，并移动求解1做一条目标函数的等值线。（最好穿过可行域）“2查看目标函数，若求max,确定函数值增加的方向；若求min ,

2、确定 函数值减少的方向；.3最后，依据目标函数的要求在可行域内平移等值线（平移到等值线与可行域的最后交点（一个或多个）求下列线性规划的基本可行解maxz= 2x1 + x2 - x3s.t.x+ x2 + 2x3 6 xl + 4x2-x3 01、先化为标准型。max z = 2x1 -v xl xis.t.x + x2 + 2x3 + x4 = 6x + 4x2 x3 + x5 = 4xl,兀 2, x3, x4, x5 n 03)先判断是否是基？因为z = l,2,-10,所以鸟为线性规划的基.对于B1=(P1,P2), xl,x2为的基变量，令非基变量A-3=A*4 =A*5 = 0,则

3、可得到x= (20/3 -2/3 0 0 0)基本解，非可行解对于B2= (P1?P3), xl,x3为耳的基变量， 令非基变量x2= x4= x5= 0,则可得到 严=(14/3 0 2/3 0 0)基本可行解,场为可行基“112 10A二14101同理，基本可行解有.*)=(4 0 0 2 0)为基本可行解，型为可行基x(5)=(0 14/9 20/9 0 0)为基本可行解，心为可行基。”?6)=(0 1 0 5 0)为基本可行解，为可行基*)=(0 0 3 0 7)为基本可行解，坊为可行基?10)=(0 0 0 6 4)为基本可行解，论为可行基基本解.X(4)=(60 0 0 -2) 2

4、=(0 6 0 0 -20) x=(0 0 -4 14 0)“4.求出基本可行解的目标函数值， 目标函数值最大的那个基本 可行解为最优解，其目标函数值为最优值， 对应的基为最优基Z=26/3 Z=8Z=-2/3, Z=1Z(9)= -3 Z(10)= 0.所以最优解为?2)=(14/3 0 2/3 0 0)，最优值为26/3,最优基为求下列线性规划的最有解max z = x2 2x3s.t.xl + 3x2 + 4x3 = 122x2 x3 0先化为标准形式(引入松弛变量x4)max z = x2 2x3s.t.x + 3x2 + 4x3 = 122x2 x3 + x4 = 12 xl, x2

5、,x3 OCB.bfp01-20.3,0“wX4o12“134d4b0.12,02-1L6.o.01*-2o.1.,4.1/314/30(L兀.4-2/30-11/3Lz“-4.-1/30-10/3(L13 4 0A =0 2-111.0.X2*41/31S0-2/30-11/3L_z.-4.皿0Q 30利用大 M 法和两阶段法来求解下列模型min f = 3xj + x2s.t. x, + x2 1xxx2 01化为标准形式max z = 3x. 一_1S.t._ X+兀2+ 兀3 = 2 A二Xj + x2 x4= 11110 01 0 -112引入人工变量Xx+ 兀2 + =2%! +

6、X2 X4+X51x50法一构造新目标函数max z = 3坷x2MxXB、b-3-100七0JAi屯兀70.2.-11100 2”4LL110-1l.1*Z.M.M73M-l0-M0.0YL-2011-1.J1.L110-1LZ.L-200-11-M.J所以，此问题的最优解为(0,1,1,0,0),最优值为 T,因为x ?*=0，所以(0,1,1,0)为原问题的最优解，原问题的最优值为1。max z =-x5Xbl00 00T兀2兀0.可.2.-11 100-LL11fl-11.1*.L11fl-10.0.V3.02 1-11.C0.兀3L11 0-11z.0.00 00-L此时最优解为(1

7、,0,3,0,0),因为Aj = 0,(1,0,3,0)为原问题基本可行解XBbl-3-100。e-V1X2屯“ Jr o.3.021-1 3/2.| -3XI.h110-10|-Z3.02*030.XIL-2011 .-LX21-110-1 z-200-1 所以(0,1,1,0)为原问题的最优解，最优值为1。约束：I变量：xj V .变量无非负限制两者可行解之间并无必然联系P最优 vAD最优解且两者目标函数值相等正常关系_maxmin w =bJy(D)最优A D有可行解若P (D)有可行解P解关系D(对偶o心t7V 乙一i o I ly=N XVUJo %0 N % -乙 N 咳+ % _

8、 一,乙 N 乙人乙一力_丁 気 + %乙=/UIUIoxxuxOS N尤 +ZXL- x?Qix-zxvxi- jr+zx+x- rsZXl+Xl=2 XDUImin f = 2x+ 3x2+ 4x3sJ. x, +2X2+x3 12xtx2+2兀3 4 xpx2,x30化为标准型-1 -2-110A =-21-201XBb-2-3-400X1X2X3X4X50X4-1-1-2-1100.X5.-4*.-21-201 z0-2-3-400兀5CBXBb-2-3-400X1X2X3X4X50X410-5/201-1/2-2X121-1/210-1/2-z40-4-20-1最优解为( (2, 0

9、, 0,1,0),最优解为43 (2)B1B2B3B4产量A118141712100A2581315100A3177129150销量50706080B1B2B3B4B5产量A1181417120100A25813150100A31771290150销量5070608090平衡vj9101712QUiBlB2B3B4B5产量0Al18ei144171I410120 + 0or090100 4A255082135015704100-3A317ni7701209 80-08003150销量5070608090平衡Vj71015120UiBlB2B3B4B5产量0Al18111417f21210090

10、1002A25508e(J50-5q15502100-3A31713712 T9700315070+外 10-0销量5070608090平衡vj71015120UiBlB2B3B4B5产量0Al181114141712100901002A255085013011551021003A31713720126097003150销量5070608090平衡例：下表是得到最优解的情(1)运价C22在什么范围内变化，以上最优调运方案不变？( (2) C24在什么范围内变化，最优调运方案不变?况B1B2A11015A2120710A32514销量515B3B4产量2011101591520251618515

11、1045vj13-C22110-C22uiB1B2B3B4产量0A110C22-31520C22+1011 1015C22-1A2120C22109152010-C2225IC22-1A31251424-C2216】171818-C2251销量515151045C22-3024-C220C22+10010-C22018-C220o 3 V C” V10vj61311uiB1B2B3B4产量0A11015201110156A2120710915C24C24-1；25r-4A3251416185销量515151045cncui74、最小元素法Vj12172325ui地BlB2B3B4产量（吨）0Al*219 17250 + 232550-的004250P 1502A21040H3A323141217 2035022150500销量400250350200平衡令0 = 0,代入得到Vj16172325ui销地产地B1B2B3B4产量（吨）0A1215 1725023P 12550300-6A21040015430131904003A323102172035022150500销量400250