《运筹学自学指导书》由会员分享，可在线阅读，更多相关《运筹学自学指导书（9页珍藏版）》请在金锄头文库上搜索。
1、运筹学自学指导书张尚立第一章 线性规划及单纯形法 重点：线性规划数学模型的标准化。单纯形法求解线性规划模型。1、3、4重点掌握：一、将一般的线性规划模型化为标准的线性规划模型，即1 .目标函数为求最大值：max Z = CX;2约束条件方程为等式：“=”；3 .所有变量都是非负变量：Xj 0, j=1,2,，n；4.约束条件方程右边的常数非负：bi0, i=1,2,，m。二、会利用单纯形法求解线性规划模型。即1. 确定初始基可行解,建立初始单纯形表；2 .检验各非基变量的检验数c j是否全部满足c jW 0，若是，已得最优解，停止计算; 否则,转下一步。3.确定换出与换入变量后，进行迭代，得到
2、一新的单纯形表。重复2、3可求出最优 解。第二章 对偶理论与灵敏度分析 重点：线性规划的对偶问题与对偶理论，对偶单纯形法。3、4、6重点掌握：一、对于给定的线性规划模型根据对偶原理可确定其对偶问题的模型，即：1. 目标函数“ max”化为“ min”。2. 约束条件“W”化为。3 .价值系数c与常数b互换。二、会利用对偶单纯形法求解线性规划模型。1. 列出初始单纯形表，检查 b 列的数字，若都为非负，检验数为非正，则已得最优解， 停止计算。若 b 列的数字至少有一个负分量，检验数非正，则转下一步。2. 确定换出与换入变量。3. 按原单纯形法在表中进行迭代运算，得到新的计算表，重复1， 2， 3
3、可求出最优解。第三章运输问题重点：运输问题的数学模型表上作业法 1, 2重点掌握：用表上作业法求解运输2运输的最优解。1 用最小元素法确定初始基可行解。2用闭回路法求非基变量的检验数，若检验数存在负数，则需要改进。3用闭回路调整法进行改进，得到新的基可行解，重复2、3可得最优解。第五章整数规划重点：分枝定界解法与 0-1型整数规划。 2, 4重点掌握：一、整数规划是线性规划的特殊情形，求解的基本思路是利用单纯形法或对偶单纯形法先求出最优解，如果不满足整数约束条件再将问题分枝求解。二、0-1型整数规划是一种隐枝举法，通过增加过滤条件可以减少运算次数。第十章图与网络分析 重点：图的基本概念、树、最
4、短路问题。 1, 2, 3重点掌握：一、图与树的一些基本概念。二、利用“破圈法”或“避圈法”求图的一个最小支撑树。练习题1 :一、将下列线性规划问题化为标准型Minz = -3x 1 + 4x2 -2x3=5x4* 4 X1 - X2 +2 X3 -X4 = -2X1 + X2 +3 X3 -X4 0, X4 无约束二、用单纯形法求解线性规划问题maxz = 2x1 + 5X2X1W 42x2 123x1 + 2x2 0三、用对偶单纯形法求解线性规划问题mi nz = 2xi + 3x2 + 4x3Xi + 2X2 + X3 3-2xi - X2 + 3x3 4一 xi, X2, x3 0五、
5、求下图的一个最小支撑树参考答案：四、用表上作业法求解运输问题销地产地BiB2B3B4产量Ai3113107A219284A3741059销量3656#一、maxz = 3xi -4X2 + 2X3 -5（X5 -X6）厂-4X1 + X2 - 2x3 +（X5 - X6）= 2X1+ X2 + 3X3 -（X5 - X6）+X7 =14-2X1 +3 X2 - X3 +2（X5 - X6）- X8 =2-Xi, X2, X3, X5, X6, X7, X8 0二、Xi = 2, X2 = 6, maxz = 34一3三、xi = 11/5, X2 = 2/5, X3 = 0, minz = 5
6、 一5五、V6V2V4练习题2:一、将下列线性规划模型化为标准型1) minz = 2x 1 + 3x2 -5x3-X1 -X2 -X3 = -7V 2x1 - 5x2 + X3 10-X1, x2 02) minz = 2x 1 + 3x2 + X3X1 + 4x2 + 2x3 83x1 + 2x2 6X1, X2, X3 03) minz = 5x 1 - 2x2 + 3x3 5x1 + 3x2 + X3 5 X1, X2,X3 0二、用单纯形法求解1) maxz = 2x1 + 3x2X1 + 2 X2W 8& 4x1 16 4X2 02) maxz = 2x1 + x23x1 + 5
7、X2 156x1 + 2 X2 0三、用对偶单纯形法求解1) minw = 8x 1 + 16x2 + 12x3X1 + 4 X2 22x1 + 4 X2 3X1, X2, X3 02) minw = 2x 1 + 3x2 + 3x3X1 + X2 + 3X3 42x1 - X2 + X3 3X1, X2,X3 0四、用表上作业法求解运输问题、一.销地 产地、BiB2B3B4产量Ai37645A224322A 343853销量332五、求解整数规划问题maxz = 40x 1 + 90x2才 9xi + 7x2 w 567xi + 20x2 w 70xi, X2 0xi, X2 整数六、求解0
8、-1型整数规划问题maxz = 3xi - 2x2 + 5x3xi + 2X2 - X3 w 2xi + 4x 2 + x 3 w 4s xi + X2 w 34xi + X3 w 6L xi, X2,X3 = 0 或 i七、求下图的一个最小支撑树V5参考答案：* i) maxz = -2x i - 3x2 + 5x4 -5x5Xi + X2 + X4 - X5 =72 xi - 5x2 + X4 - X5 + X6 =i0xi, X2, X4, X5, X6 02) maxz = -2xi - 3x2 -X3xi +4 X2 +2 X3 - X4 =83xi + 2x2 - X5 = 6Xi
9、, X2, X3, X4, X5 03) maxz = -5x1 + 2x2 -3X35x1 + 3x2 + X3 + X4 =9彳 2x1 + X2 + X3 - X5 = 5 0、1) xi = 4, X2 = 2, maxz = 14452)X1 =社3X2 =-4Maxz =9912、1) mi nw = 132) minw = 5四、B1B2B3B4A13002A202A33五、X1 = 4, x2 = 2, maxz = 340六、maxz = 8练习题3:一、将下列线性规划问题化为标准型minz = 2xi - x2 3x3X1 + X2 + X3 1Xi 0, X2 0, X3
10、 无约束二、用单纯形法求解maxz = 2xi X2 + X33X1 + X2 + X3 60 xi- X2 + 2x3 10X1 + X2 - X3 0三、写出下列线性规划问题的对偶问题:minz = - 5xi 6x2 7x3- xi + 5x2 - 3x3 15-5xi- 6x2 + 10x3 20Xi - X2 - X3 = -5X1 0, X3 无约束四、用对偶单纯形法求解：minz = 4xi + 12x2 + 18x3l xi + 3x3 3S 2x2 + 2x3 5一、令 x2X2 , X3 = X4 - X5z = -zJ Xi , X2, X3 0五、已知运输问题的有关数据如下表，试写出其数字模型销地 产地 、 产量11010321521422407322243416销量12820参考答案：maxz = -2xi + X2 +3x3X1- X2 + X4 - X5 + X6 = 7 -2xi - 3 x2-5 X4 + 5x5 =8Xi - 2 X4 +2 X5 X7 =1maxz = 30、maxw = 15y i + 20y2 - 5y3厂-yi - 5 y2 + y3 - 55 yi - 6 y2 - y3 0, y2 0, i 1,2,3, j=1,2,3
