《运筹学复习2012》由会员分享，可在线阅读，更多相关《运筹学复习2012（14页珍藏版）》请在金锄头文库上搜索。
1、运筹学复习I一、 题型：选择题、 解答题、 填空题、 简述题、 计算题、 应用题、 证明题I二、 线性规划1.数学模型：P10例2.1.1生产的组织与安排问题2.线性规划的标准形式: P15例2.1.33.图解法: P16例2.2.14.单纯形法I(1)基、 基本可行解I(2)典式、 单纯形表:zxBxNRHSz10Nz0xB0INbI(3)换基迭代：k 0 xk为进基变量 =br ark= min bi aik| aik 0, i 1,m xBr为出基变量I下降速度：k,下降量： k线性规划I5.两阶段法：第一阶段min g = g0.g0= 0时， 原问题有可行解.g0 0时， 原问题无可
2、行解.I6.对偶理论：对偶问题、 对偶单纯形法、 对偶定理、 松弛互补条件、 影子价格三、 整数规划I1.割平面法:先求松弛问题的最优解x0,再对其最优解中非整变量xB引进割平面. 设xB所对应的约束方程是xB+jR ajxj=b.对应于 生成行的Gomory割平面条件: jRfjxj f.其中fj是 aj的分数部分，f是b的分数部分.I2.割平面法的特点： 割去了包含松弛问题最优解x0在内的一块， 但未割去IP的任何整数可行解整数规划I3.分枝定界法： 步骤P97对max类型问题:1）选择目标函数值最大的子问题进行分枝；2)分枝过程在某个点上由下述两个原因之一而停止:2-1)找到了问题在这个
3、子域内的整数最优解2-2)相应松弛LP问题是不可行的3）定界: z 当前最好的整数可行解对应的目标函数 值。4)剪枝： 利用对ILP目标函数界的估值z“巧妙”地删去 一些不必要的点的分枝四、 动态规划I1.状态变量、 决策变量、 状态转移方程、 指标函数、 逆推公式I2.后向最优化原理(P163):作为整个过程的最优策略具有这样的性质:对于最优策 略过程中的任一状态而言， 无论其过去的状态和决策如 何， 其余下的诸决策必然构成一个最优的子策略.I3.最短线路问题：P160图5.2.1I4.多阶段资源连续分配问题：P181 3，6有个畜牧场,每年出售部分牲畜， 出售y头牲畜可获得利(y)元。 留
4、t头牲畜繁殖， 一年后可得到at(a 1)头牲畜。已知该畜牧场 年初有x头牲畜， 每年应出售多少， 留下多少， 使N年末还有z头 牲畜并且获得的收入总和最大.把该问题当作多阶段决策问题， 利用最优化原理找出递推公式。动态规划例I阶段：每年为一个阶段， 共N个阶段I第k阶段状态变量xk:第k年年初牲畜数I第k阶段决策变量uk:第k年出售牲畜数I容许决策集合: Uk(xk)=uk|uk 0,xk, k = 1,2,.,N 1UN(xN)=uN|uN 0,xN z.I最优指标函数fk(xk)：在第k年年初有xk头牲畜、 第N年末还有z头牲畜的前提下， 畜牧场能够获得的最大收入I递推公式: fk(xk
5、) = maxuk0,xk(uk) + fk+1a(xk uk),k = N 1, ,1fN(xN) = maxuN0,xNz(uN),xN z,xN b2,证明A*也是下面两个 问题的最优解.(1) minz = cxs.t. A1xb1x0(2)minz=cxs.t.A1x=b1x0I证法一:原问题和对偶问题为(P) minz = cxs.t.A1x b1A2x b2x 0(D) maxg = u1b1+ u2b2s.t.uT1 0uT2 0u1A1+ u2A2 c设u*= (u*1,u*2)是(D)的最优解， 则u*1,u*2 0且u*1A1+ u* 2A2 c.因为A2x* b2,由松
6、弛互补条件得(u*2)T= 0,所以u*2= 0, 进而u*1A1 c.又由对偶定理，cx*= u*1b1+ u*2b2= u*1b1. 易见x*是(1)、(2)的可行解，u*1是(1)、(2)的对偶问题的 可行解,并且它们对应的目标函数值相等(即:cx*= u*1b1),所以x*是(1)、(2)的最优解.I证法二:设x*不是(1)的最优解， 则存在（1）的可行解x0使cx0 b2,所以对充 分小的 0,A2x() b2= (A2x0 b2) + (1 )(A2x* b2) 0.因此x()是原问题的可行解， 但cx()=cx0+ (1 )cx*cx*+ (1 )cx*=cx*,与x*是原问题的
7、最优解矛盾.I例2 P75 15有一LP问题， 目标函数为min z = 5x1 3x2,约束条件为型的线性不等 式，x3,x4为松弛变量， 经过一次迭代后得到下表zx3x1x1x2x3x4RHSb1fg10c011/52de01a试写出原问题， 并写出这张单纯表所对应的B和B1.I解: B = (A3,A1)为基= b = c = 0, d = 1,f = 0.经过一次迭代后的表为zx3x1x1x2x3x4RHS010g100011/521e01aI以 a24为旋转元换基， 得zx3x4x1x2x3x4RHSg1 eg0010 ag1/5e/5102 a/51e01a=g=51 eg=310 ag=0=g=5e=2/5a=2原问题minz=5x13x2s.t.15x12 25x28 5 x1+2 5x22x1,x20B = (A3,A1) =( 11/501),B1= (A3,A4) =( 11/501)I已求出原问题minz=5x13x2s.t.15x12 25x28 5 x1+2 5x22x1,x20所以B = (A3,A1) =( 11/501),B1= (A3,A4) =( 11/501)
