资源描述：
《运筹学自学指导书》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《运筹学》自学指导书张尚立第一章线性规划及单纯形法重点：线性规划数学模型的标准化。单纯形法求解线性规划模型。§１、§３、§４重点掌握： 一、将一般的线性规划模型化为标准的线性规划模型，即 １．目标函数为求最大值：maxＺ＝ＣＸ；２．约束条件方程为等式：“＝”；３．所有变量都是非负变量：xj≥０，j＝１，２，…，n；４．约束条件方程右边的常数非负：bi≥0，i＝１，２，…，m。 二、会利用单纯形法求解线性规划模型。即 １．确定初始基可行解，建立初始单纯形表； ２．检验各非基变量的检验数σj是否全部满足σj≤0，若是，已得最优解，停止计算；否则，转下一步。３．确定换出
2、与换入变量后，进行迭代，得到一新的单纯形表。重复２、３可求出最优解。第二章 对偶理论与灵敏度分析重点：线性规划的对偶问题与对偶理论，对偶单纯形法。§３、§４、§６重点掌握：一、对于给定的线性规划模型根据对偶原理可确定其对偶问题的模型，即：1．目标函数“max”化为“min”。2．约束条件“≤”化为“≥”。3．价值系数cj与常数bj互换。二、会利用对偶单纯形法求解线性规划模型。1．列出初始单纯形表，检查b列的数字，若都为非负，检验数为非正，则已得最优解，停止计算。若b列的数字至少有一个负分量，检验数非正，则转下一步。2．确定换出与换入变量。3．按原单纯形法在表中进行迭代运算，
3、得到新的计算表，重复1，2，3可求出最优解。8第三章运输问题重点：运输问题的数学模型表上作业法§1，§2重点掌握：用表上作业法求解运输2运输的最优解。1．用最小元素法确定初始基可行解。2．用闭回路法求非基变量的检验数，若检验数存在负数，则需要改进。3．用闭回路调整法进行改进，得到新的基可行解，重复2、3可得最优解。第五章整数规划重点：分枝定界解法与0-1型整数规划。§2，§4重点掌握：一、整数规划是线性规划的特殊情形，求解的基本思路是利用单纯形法或对偶单纯形法先求出最优解，如果不满足整数约束条件再将问题分枝求解。二、0-1型整数规划是一种隐枝举法，通过增加过滤条件可以减少运
4、算次数。第十章图与网络分析重点：图的基本概念、树、最短路问题。§1，§2，§3重点掌握：一、图与树的一些基本概念。二、利用“破圈法”或“避圈法”求图的一个最小支撑树。练习题1：一、将下列线性规划问题化为标准型Minz=-3x1+4x2–2x3=5x44x1-x2+2x3–x4=-2x1+x2+3x3–x4≤14-2x1+3x2-x3+2x4≥2x1，x2，x3≥0，x4无约束二、用单纯形法求解线性规划问题maxz=2x1+5x2X1≤42x2≤123x1+2x2≤18x1,x2≥08三、用对偶单纯形法求解线性规划问题minz=2x1+3x2+4x3X1+2x2+x3≥32x
5、1-x2+3x3≥4x1,x2,x3≥0四、用表上作业法求解运输问题销地产地B1B2B3B4产量A13113107A219284A3741059销量3656五、求下图的一个最小支撑树V35V54V634V2V4276V151参考答案：一、=3x1–4x2+2x3–5(x5–x6)-4x1+x2-2x3+(x5–x6)=2x1+x2+3x3-(x5–x6)+x7=14-2x1+3x2-x3+2(x5–x6)–x8=2x1,x2,x3,x5,x6,x7,x8≥035二、x1=2,x2=6,maxz=34三、x1=11/5,x2=2/5,x3=0,minz=5四、B1B2B3B4
6、A152A231A363V3V54V6V2V42V15五、318练习题2：一、将下列线性规划模型化为标准型1）minz=2x1+3x2–5x3-x1–x2–x3=-72x1-5x2+x3≥10x1,x2≥0x1+4x2+2x3≥83x1+2x2≥6x1,x2,x3≥02）minz=2x1+3x2+x35x1+3x2+x3≤92x1+x2+x3≥5x1,x2,x3≥03）minz=5x1-2x2+3x3二、用单纯形法求解1）maxz=2x1+3x2x1+2x2≤84x1≤164x2≤12x1,x2≥03x1+5x2≤156x1+2x2≤24x1,x2≥02）maxz=2x1+
7、x2三、用对偶单纯形法求解1）minw=8x1+16x2+12x3x1+4x2≥22x1+4x2≥3x1,x2,x3≥02）minw=2x1+3x2+3x3x1+x2+3x3≥42x1-x2+x3≥3x1,x2,x3≥08四、用表上作业法求解运输问题销地产地B1B2B3B4产量A137645A224322A343853销量332~五、求解整数规划问题maxz=40x1+90x29x1+7x2≤567x1+20x2≤70x1,x2≥0x1,x2整数六、求解0-1型整数规划问题maxz=3x1-2x2+5x3x1+2x
