《运筹学》复习参考资料知识点及习题.doc

1、第 1 页 共 30 页第一部分 线性规划问题的求解一、两个变量的线性规划问题的图解法：概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解。图解法：图解法采用直角坐标求解：x 1横轴；x 2竖轴。1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线） ，确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。参考例题：（只要求下面这些有唯一最优解的类型）例 1：某厂生产甲、乙两种产品，这两种产品均需在 A、B 、C 三种不同的设备上加工，

2、每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：A B C 利润（万元）甲乙3 5 99 5 37030有效总工时 540 450 720 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？设备消耗产品第 2 页 共 30 页（此题也可用“单纯 形法”或化“对 偶问题”用大 M 法求解）第 3 页 共 30 页解：设 x1、x 2 为生产甲、乙产品的数量。max z = 70x1+30x2s.t. 0723945502112xx，可行解域为 oabcd0，最优解为 b 点。由方程组解出 x1

3、=75，x 2=15720394551xX *= =（75，15） T2xmax z =Z *= 7075+3015=5700、第 4 页 共 30 页例 2：用图解法求解max z = 6x1+4x2s.t. 078022112xx，解：可行解域为 oabcd0，最优解为 b 点。由方程组解出 x1=2，x 2=6810212xX *= =（2，6） T1xmax z = 62+46=36、第 5 页 共 30 页例 3：用图解法求解min z =3x 1+x2s.t. 08215341121xx，解：可行解域为 bcdefb，最优解为 b 点。由方程组 解出 x1=4，x 2=125241

4、x 54X *= =（4， ） T2xmin z =34+ =1151、第 6 页 共 30 页二、标准型线性规划问题的单纯形解法：一般思路：1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入 3；3、根据 L 规则确定改进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入 3，直至最优解。具体做法（可化归标准型的情况）：设已知max z = c1x1+ c2x2+ cnxns.t. njxbxaaxbxaaj mmn， .210.21 22212 11对第 i 个方程加入

5、松弛变量 xn+i，i =1，2，m ，得到 njx bxxaabxaaj mnmmnn， .210.21 22212 11列表计算，格式、算法如下：第 7 页 共 30 页c1 c2 cn+mCB XB bx1 x2 xn+mLcn+1 xn+1 b1 a11 a12 a1 n+mc n+2 xn+2 b2 a21 a22 a2 n+m. cn+m xn+m bn am1 am2 am n+mz1 z2 zn+m1 2 n+m注： zj =cn+1 a1j+ cn+2 a2j + cn+m amj= ， （j=1，2，n+m）miijnac1j =cjzj ,当 j 0 时，当前解最优。注：

6、由 max j确定所对应的行的变量为“入基变量”；由 L= 确定所对应的行的变量为“出基变量”，行、列0minikab交叉处为主元素，迭代时要求将主元素变为 1，此列其余元素变为 0。例 1：用单纯形法求解 （本题即是本资料 P2“图 解 法 ”例 1 的单纯形解法 ； 也可化 “对偶 问 题 ”求解）max z =70x1+30x2s.t. 0723945502112xx，解：加入松弛变量 x3，x 4，x 5，得到等效的标准模型：max z =70x1+30x2+0 x3+0 x4+0 x5第 8 页 共 30 页s.t. 5,.21,0720394551231jxxxj列表计算如下：70

7、 30 0 0 0CB XB b x1 x2 x3 x4 x5 L0 x3 540 3 9 1 0 0 540/3 =1800 x4 450 5 5 0 1 0 450/5 =900 x5 720 （9） 3 0 0 1 720/9 =800 0 0 0 070 30 0 0 00 x3 300 0 8 1 0 - 1/3 300/8 =37.50 x4 50 0 （10/3） 0 1 - 5/9 50/10/3 =1570 x1 80 1 1/3 0 0 1/9 80/1/3 =24070 70/3 0 0 70/90 20/3 0 0 70/90 x3 180 0 0 1 12/5 130

8、 x2 15 0 1 0 3/10 - 1/670 x1 75 1 0 0 - 1/10 1/670 30 0 2 20/357000 0 0 -2 20/3X *=（75，15，180 ，0，0） Tmax z =7075+3015=5700第 9 页 共 30 页例 2：用单纯形法求解max z =7x1+12x2s.t. 031325460921xx，解：加入松弛变量 x3，x 4，x 5，得到等效的标准模型：max z =7x1+12x2+0 x3+0 x4+0 x5s.t. 5,.21,0303546914231jxxxj列表计算如下：第 10 页 共 30 页7 12 0 0 0C

9、B XB b x1 x2 x3 x4 x5 L0 x3 360 9 4 1 0 0 360/4 =900 x4 200 4 5 0 1 0 200/5 =400 x5 300 3 （10） 0 0 1 300/10 =300 0 0 0 07 12 0 0 00 x3 240 78/10 0 1 0 - 2/5 240/78/10 =2400/780 x4 50 （5/2） 0 0 1 - 1/2 50/5/2 =2012 x2 30 3/10 1 0 0 1/10 30/3/10 =10018/5 12 0 0 6/517/5 0 0 0 6/50 x3 84 0 0 1 78/25 29/257 x1 20 1 0 0 2/5 - 1/512 x2 24 0 1 0 3/25 4/287 12 0 34/25 11/354280 0 0 34/25 11/35X *=（20，24，84 ，0，0） Tmax z =720+1224=428三、非标准型线性规划问题的解法：1、一般地，对于约束条件组：若为“” ，则加松弛变量，使方程成为“” ；若为“” ，则减松弛变量，使方程成为“” 。我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，则为非标准型。可作如下处理：