《运筹学》总结复习计划参考材料知识点总结及试题.docx

优选文档 第一部分线性规划问题的求解 一、两个变量的线性规划问题的图解法： ㈠看法准备：定义：满足全部拘束条件的解为可行解；可行解的全体称为可 行（解）域。 定义：达到目标的可行解为最优解。 ㈡图解法： 图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将拘束条件（取等 号）用直线绘出； 2、确定可行解域； 3、绘出目标函数的图形（等值线），确定它向最优解的挪动方向； 注：求极大值沿价值系数向量的正向挪动；求极小值沿价值系数向量的反向挪动。 4、确定最优解及目标函数值。 ㈢参按例题：（只要求下面这些有独一最优解的种类） 例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不一样样的设备上加工，每 种产品在不一样样设备上加工所需的工时不一样样，这些产品销售后所能获得利润以及这三种加工设 备因各种条件限制所能使用的有效加工总时数以下表所示： 消 设 备 利润 A B C （万元） 耗 产 品 甲 3 5 9 70 乙 9 5 3 30 有效总工时 540 450 720 —— 问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？ （此题也可用“单纯形法”或化“对偶问题”用大M法求解） . 优选文档 解：设x1、x2为生产甲、乙产品的数量。 maxz=70x1+30x2 ⑴ s.t. 3x1 9x2 540 ⑵ 5x1 5x2 450 ⑶ 9x1 3x2 720 ⑷ x1，x2 0 ⑸、⑹ 可行解域为oabcd0，最优解为b点。 由方程组 5x1 5x2 450 解出x1=75，x2=15 9x1 3x2 720 x1 ∴X*=x2=（75，15）T ∴maxz=Z*=70×75+30×15=5700 . 优选文档 例2：用图解法求解 maxz=6x1+4x2 ⑴ s.t. 2x1 x2 10 ⑵ x1 x2 8 ⑶ x2 7 ⑷ x1，x2 0 ⑸、⑹ 解： 可行解域为oabcd0，最优解为b点。 由方程组 2x1x210 解出x1=2，x2=6 x1x28 x1 ∴X*=x2=（2，6）T ∴maxz=6×2+4×6=36 . 优选文档 例3：用图解法求解 minz=－3x1+x2 ⑴ s.t. x1 4 ⑵ x2 3 ⑶ 2x1 5x2 12 ⑷ x1 2x2 8 ⑸ x1，x2 0 ⑹、⑺ 解： 可行解域为bcdefb，最优解为b点。 由方程组 x1 4 4 2x15x212 解出x1=4，x2=5 ∴X* x1 （， 4 =x2 = ）T 4 5 41 minz=－3×4+5=－115 . 优选文档 二、标准型线性规划问题的单纯形解法： ㈠一般思路： 1、用简单易行的方法获得初始基本可行解； 2、对上述解进行检验，检验其能否为最优解，假如，停止迭代，否则转入3； 3、依照θL规则确定改进解的方向； 4、依照可能改进的方向进行迭代获得新的解； 5、依照检验规则对新解进行检验，假如最优解，则停止迭代，否则转入3，直 至最优解。 ㈡详尽做法（可化归标准型的情况）： 设已知 maxz=c1x1+c2x2++cnxn s.t. a11x1 a12x2 ... a1nxn b1 a21x1 a22x2 ... a2nxn b2 ............ am1x1 am2x2 ... amnxn bm xj 0，j 1，2，...，n 对第i个方程加入废弛变量xn+i，i=1，2，，m，获得 a11x1 a12x2 ... a1nxn xn1b1 a21x1 a22x2 ... a2nxn xn2b2 ............ am1x1 am2x2 ... amnxn xnmbm xj 0，j 1，2，...，n 列表计算，格式、算法以下： . 优选文档 CB XB b c1 c2 cn+m θL x1 x2 xn+m c n+1 x n+1 b a a a 1 11 12 1n+m c n+2 x n+2 b a a a 2 21 22 2n+m . . . . . . ? ? ? ? . . . c n+m x n+m b a a a n m1 m2 mn+m z z 2 z n+m 1 σ1 σ 2 σn+m m 注①：z j =c n+1 1j +c n+2 2j n+mmj cniaij ，（j=1 ，2，，n+m） a a ++c a = i1 j=cj－zj,当σj≤0时，当前解最优。 注②：由max{σj}确定所对应的行的变量为“入基变量”； 由θL=min biaik0确定所对应的行的变量为“出基变量”，行、列交 i aik 叉处为主元素，迭代时要求将主元素变成 1，此列其余元素变成0。 例1：用单纯形法求解（此题即是本资料P2“图解法”例1的单纯形解法；也可化“对偶问题”求解） ma