运筹学复习提纲

1、运筹学复习提纲复习内容：绪论、第一章线性规划、第二章线性规划的进一步研究、第三章运输问题、第六 章决策分析、第九章对策论。重点内容：运筹学的定义特征、线性规划问题的数学模型、线性规划问题单纯形法的求解过程、对偶问题及理论、对偶单纯形法的求解过程、运输问题的数学模型、表上作业法的求解过程、风险型决策分析和完全不确定型决策分析、效用理论、二人有限零和博弈。管理运筹学重在对实际问题的理解的基础上对问题进行建模，并用适宜的办法对问题进行求解。管理运筹学是一门决策的科学。 从决策环境的角度来讲，可以 将问题分为确定型决策和非确定性决策。 其中本期前面的内容，线性规划问题和 运输问题可以理解为确定型决策。

2、非确定型决策又可以分为风险型决策和完全不 确定型决策，这在本书第六章有介绍。附：部分复习题一、简答题1简述运筹学的定义和特征2、比较可行解、基本解与基可行解之间的区别3、简述对偶问题的基本性质4、简述表上作业法的求解过程5、简述单纯形法的求解过程6、简述影子价格对决策的作用7、简述运输问题中最优解的判定方法8简述完全不确定型决策的准则二、计算题1某工厂利用原材料甲、乙、丙生产产品A、B、C,有关资料见表2-23 .表 2-23材 '、产品产 、材料消耗消 原 材料耗品ABC每月可供原材料(Kg )甲211200乙123500丙221600每件产品利润413(1) 怎样安排生产，使利润最

3、大.(2) 若增加1kg原材料甲，总利润增加多少.【解】(1)设XI、X2、X3分别为产品A、B、C的月生产量，数学模型为max Z 4x x2 3x32% +1x2 +x3 兰 200% + 2x2 + 3x3 兰 5002为 x2 x3 乞 600% _ 0,x2 _0,x3 _0最优单纯形表:C(j)413000R.H.S.RatioXbCbX1X2X3X4X5X6X1411/503/5-1/5020X3303/51-1/52/50160X60000-101400C(j)-Z(j)0-8/50-9/5-2/50Z=560最优解X= (20, 0, 160), Z=560。工厂应生产产品

4、A20件，产品C160种，总利润为丿元。92(2)则最优表可知，影子价格为y1, y2, y3 = 0 ,故增加利润1.8元。552、用对偶单纯形法求解下列线性规划问题560mi nZ = 3% 4x2 5x3x1 2x2 3x3 _ 8I2x1 2x2 x3 _ 10XX2,X3 一 0【解】将模型化为min Z =3为 4x2 5x3-Xi - 2x2 _ 3x3 ' X4 = _ 8« 2为2x2 x3 +疋=10Xj K0, j =1,2,3,4,5对偶单纯形表：Cj34500CbXbX1X2X3X4X5b0X4-1-2-310-8-210X5-2-1010C(j)-

5、Z(j)3450000X40-15/211/2-33X1111/201/25C(j)-Z(j)017/203/205X2015/2-11/233X110-21-12C(j)-Z(j)00111b列全为非负，最优解为x= (2 , 3, 0); Z = 183、给出如下运输问题运价产BEbB3B4产量A5310490A169640A20105770销量30508040200(1) 应用最小元素法求其初始方案；(2) 应用位势法求初始方案的检验数，并检验该方案是否为最优方案。解：（1）初始方案BiB2B3B4产量Ai504090A2301040A 370销量30508040（2）检验表BiB2B3

6、B4UiAi63-1A211A32395-3Vj0485检验数全部非负，该方案最优。4、某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙46101203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；2）用单纯形法求该问题的最优解。 解：（1）建立线性规划数学模型：设甲、乙产品的生产数量应为X" X2，则X" X2> 0,设Z是产品售后的总利润，则max z =70xi+120x2g +4X2 兰3604x1 6x 2003x11

7、0x300I X1, X2 - 0（2 ）用单纯形法求最优解：加入松弛变量X3, X4, X5,得到等效的标准模型：max z =70x 1+120x2+0 X3+0 X4+0 X5©Xj +4x2 + x34Xt +6x2+ x43xi +10X2= 360= 200X5= 300Xj -0, j =1,2,.,5列表计算如下:70120000CBXBbx1x2x3x4x50 L0x336094100900x420046010100/30x53003(10)001300000070120 f0000x324039/5010-2/5400/130x420(11/5 )001-3/51

8、00/11120x2303/101001/1010036120001234 f000120x31860/1100139/1119/1170x1100/111005/11-3/11120x2300/11010-3/222/1143000701200170/1130/1111000-170/1130/11 X*= ( 100 ,11300I86011，3000, 0)11”、/ 100 max z =70 x+120 x11 11 115、用大M法求解如下线性规划模型：(15分)max z =5x 1 + 2x2 + 4x3430003x1 x2 2x3 - 46x3x2 5x3 - 10Xi,X

9、2,X3 - 0用M法先进行标准形式的变形max Z = 5xi 2x2 4x33x1 x2 2x3 _x4= 4«6人 +3x2 +5x3_x5 =10yj 王0, j =1,2,5增加人工变量X6、X7,得到：max z/ = 5xi 2x? - 4x3 M - M X7s.t3x x2 2x3 - x46x1 3x2 5x3x6=4- X5x - 10Xj 一 0, j = 1,2,.,7大M法单纯形表求解过程如下:0,0,52400MMCBXBbx1x2x3x4x5x6x70 LMx64(3)1210104/3Mx71063501015/39M4M7MMMMM9M 5 f4M

10、 27M 4MM005x14/311/32/31/301/30Mx72011(2)12115-M 5/3-M 10/3-2 M +5/3M2M 5/3-M0M 1/3M 2/32M 5/3 fM3M +5/305x15/311/25/601/601/610/30x410(1/2 )1/211/211/2255/225/605/605/601/2 f1/605/6MM +5/65x12/3101/311/311/32x220112121225211/311/311/33001/311/3M+1M+1/32222最优目标函数值 min z = max z/ =()=336、给定下列运输问题：（表中

11、数据为产地 Ai到销地Bj的单位运费）B1B2B3B4SiA1123410A2876580A391011915dj82212181）用最小费用法求初始运输方案，并写出相应的总运费；2）用1）得到的基本可行解，继续迭代求该问题的最优解。先用最小费用法 （最小元素法） 求此问题的初始基本可行解:费销地B1地B2B3B4SiA112341082XXA2876520XX218A391011930X2010Xdj82212186060Z=1 X 8+2 X 2+6 X 2+5 X 18+10 X 20+11 X 10=4242）用闭回路法，求检验数:费7B1B2B3B4SiA112304-21082XXA28-47-26520XX218A39010119130X2010Xdj82212186060二 34 =1 > 0，其余二 j 三 0选X34作为入基变量