运筹学期末复习提纲

1线性规划线性规划问题及其数学模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论线性规划的概念目标能表成求MAX或MIN达到目标有多种方案实现目标有一定条件目标和条件都能用线性函数表示例如，对于线性规划问题0,,,6323523632max432143214214321xxxxxxxxxxxxxxxz其系数矩阵为31125023则下面两个矩阵都是该线性规划问题的基。12233152和还能找出其它基吗？基解：令非基变量等于0的解。基可行解：基解+可行解例如，对于上面的线性规划问题，如果取x1，x2为基变量，则令非基变量x3，x4为零，约束方程组为623232121xxxx解之得。故我们得到基解注意到这个基解还是一个可行解。712,71521xx0,0,712,7154321xxxx是否所有的基解都是基可行解？（选x1,x3作为基变量）解的概念0,,,,1823122453max54321321423221xxxxxxxxxxxxxxz解2.3(1)x1x2x3x4x5z是否可行12620036y24306027y34600-642n460-612018n5094-6045n60640630y740012612y800412180y(2)线性规划要注意的几点图解法对只包含两个决策变量的线性规划问题，可以用图解法来求解。图解法顾名思义就是通过作图来求解的方法，它简单直观、并有助于说明一般线性规划问题求解的基本原理。线性规划的标准形式0,...,,..max2122122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz它具有如下四个特征：①目标函数求max；②约束方程符号取“=”；③bi非负；④所有决策变量xj非负。线性规划解的存在性线性规划问题的所有可行解构成的集合是凸集，也可能为无限集。他们有有限个顶点，线性规划问题的每个基可行解对应可行域一个顶点，反之亦然。若线性规划问题有最优解，必在某顶点达到。大M法将人工变量在目标函数中反映出来得到如下形式的线性规划：0,,,,,,,4222212232max876543216321853217432187321xxxxxxxxxxxxxxxxxxxxxxMxMxxxxz0,0,0,2,0,2.1,4.1,087654321xxxxxxxx4.5527*z因此最优解为最优目标函数值为需要说明的是，如果在用大M法求解线性规划问题时，最终表的基变量中还含有人工变量，那么这个最终表并没有给出原来问题的基可行解，从而没有给出原来的线性规划问题最优解。这时原来线性规划问题为无可行解。用EXCEL执行该计算过程0,2,0,56,57,0654321xxxxxx4.55/27*z故原来问题的最优解为最优目标函数值这一结果与大M法得到的结果是一致的。无可行解的判别：在用大M法求解线性规划问题时，若最终单纯形表的基变量中含人工变量；或用两阶段法求解时，第一阶段最终表的基变量中含非零的人工变量，也就是第一阶段最优目标函数值不等于零，则线性规划问题无可行解。找出初始基变量列出初始单纯形表计算检验数sjsj£0基变量中含有非零的人工变量无可行解存在非基变量的检验数等于零无穷多个最优解唯一的最优解对某个sJ0,有Pj£0无界解设sk=max{sJ0},则xk为换入变量为主元为换出变量，则设lkllklikikilaxabaab,0min旋转运算：经矩阵的初等行运算，使主元变为1，主元列的其它数变为零，得到新的单纯形表YYNYNNNY2.8单纯形法小结2线性规划对偶理论及其应用规范形式的线性规划与对偶规划问题£0..maxXbAXtsCXz0''..'minYCYAtsYbw原问题（LP）对偶问题（DLP）对偶规划的基本性质3.2.2弱对偶性定理：如果X、Y分别是原问题和对偶问题的一个可行解，则其对应的原问题的目标函数值不大于对偶问题的目标函数值，也即YbCX'££0XbAX0''YCYAYbYAXYAXCXCX')'(''''££证明：因为X、Y分别是原问题（3.1）与对偶问题（3.2）的可行解，故：所以推论一：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是起原问题目标函数值的上界。推论二：如果原问题存在无界解，则对偶问题一定无可行解；反之，如果对偶问题存在无界解，原问题也一定不存在可行解。注意，该推论的逆反定理并不成立。注意，该推论的逆反定理并不成立。推论三：如果原问题无解，且对偶问题有可行解，则对偶问题具有无解解，；反之，如果对偶问题无解，且原问题有可行解，则对偶问题具有无界解。最优性定理互补松弛定理约束方程也分为两种情况：，约束条件比较松；，约束条件比较紧；yi=0,分为两种情况：yi0，约束条件比较松；yi=0，约束条件比较紧；互补松弛定理的解释injjijbxa1injjijbxa£1injjijbxa1变量同其对偶问题的约束方程之间至多只能够有一个取松弛的情况，当其中一个取松弛的情况时，另外一个比较紧，即取严格等号。例已知下面的LP1和LP2为一组对偶规划，且已知LP1的最优解为X=（1.5，1）’。试运用互补松弛定理求出对偶问题的最优解Y。£££0,934425223max2121212121xxxxxxxxs.t.xxz生产计划问题（LP1）资源定价问题（LP2）0,,232342..945min321321321321yyyyyyyyytsyyyw解：由X=（1.5，1）’得55.3221xx01y0,021xx232342321321yyyyyy联立求解得：5.0,5.0,0321yyy解：由X=（1.5，1）’得55.3221xx01y0,021xx232342321321yyyyyy联立求解得：5.0,5.0,0321yyy解：由X=（1.5，1）’得55.3221xx01y0,021xx232342321321yyyyyy联立求解得：5.0,5.0,0321yyy灵敏度分析约束条件右端向量b的变化3目标规划目标规划基本概念（1）偏差变量d+：正偏差变量，表示决策值超出目标值的部分d-：负偏差变量，表示决策值未达到目标值的部分按定义有：d+≥0，d-≥0，d+•d-=0（2）绝对约束和目标约束绝对约束（硬约束）：必须严格满足的约束条件目标约束（软约束）：目标规划特有（3）优先因子（P）和权系数（W）优先因子用P1，P2，…，Pl表示，规定PlPl+1，表示Pl比Pl+1有更大的优先权。（4）目标函数决策值=目标值min{f(d++d-)}决策值目标值min{f(d+)}决策值目标值min{f(d-)}目标规划模型的建立例4.1某企业计划生产甲、乙两种产品。已知有关数据见表4-1。问如何安排生产使获得的总利润最大？项目甲乙拥有量原材料（kg）2111设备（台时)1210利润（元/件）810表4-1设x1、x2分别表示计划生产产品甲、乙的产量，它的数学模型为：它的最优解为x1=4，x2=3，最大目标函数值为62。maxz=8x1+10x22x1+x2≤11st.x1+2x2≤10x1,x2≥0但企业的经营目标不仅是利润，企业还考虑了以下问题：（1）根据市场信息，产品甲开始出现滞销现象，故考虑产品甲的产量应不超过产品乙；（2）超过计划供应的原材料需高价采购，应避免过量消耗；（3）应尽可能充分利用设备台时，但不希望加班；（4）应尽可能达到并超过计划利润指标56元。例4.2例4.1的决策者经过综合考虑，决策者的目标分别为：首先原材料使用限额不能突破；其次产品甲的产量不大于产品乙；再次充分利用设备台时，不希望加班；最后利润额不少于56元。问应如何安排生产？解：原材料使用限额的约束是绝对约束，其他三个约束是属于目标约束，分别赋予这三个目标的优先因子为P1，P2，P3。这问题的数学模型为：2x1+x2≤11x1-x2+d1--d1+=0x1+2x2+d2--d2+=108x1+10x2+d3--d3+=56x1,x2,di-,di+≥0i=1,2,3min{P1d1+,P2(d2-+d2+),P3d3-}s.t.32目标规划模型的一般形式：Min﹛Pl（∑（wlk-dk-+wlk+dk+））,l=1,2…,L﹜k=1K∑ckjxj+dk--dk+=gk，k=1，2，…，Kj=1n∑aijxj≤（=，≥）bi，i=1，2，…，mj=1nxj≥0,j=1，2，…，ndk-，dk+≥0,k=1，2，…，KS.t.33目标规划模型的一般形式：Min﹛Pl（∑（wlk-dk-+wlk+dk+））,l=1,2…,L﹜k=1K∑ckjxj+dk--dk+=gk，k=1，2，…，Kj=1n∑aijxj≤（=，≥）bi，i=1，2，…，mj=1nxj≥0,j=1，2，…，ndk-，dk+≥0,k=1，2，…，KS.t.当总产量=总销量，称为产销平衡问题当总产量≠总销量，称为产销不平衡问题4运输问题产销平衡的运输问题的数学模型如下0≥6=++5=++6=++3=++9=+++4=+++7=+++5+10+4+7+8+2+9++01+3+11+3=min343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxs.t.xxxxxxxxxxxxz运输问题含有m×n个变量，m+n个约束方程。其系数矩阵的结构比较特殊，对应变量xij的系数向量，其分量中除第i个和第m+j个为1以外，其余的都为零模型中只有个相互独立的约束方程。因此，运输问题的任一基可行解都有m+n-1个基变量。B1B2B3B4产量311310A1x11x12x13x1471928A2x21x22x23x24474105A3x31x32x33x349销量365620运输问题的表上作业法B1B2B3B4产量311310A171928A2474105A39销量36562)沃格尔法列罚数行罚数2513011621301232121201763520012B1B2B3B4产量311310A171928A2474105A39销量36566314331σ11=c11-c13+c23-c21=3-3+2-1=1解的最优性检验1)闭回路法对偶变量法（位势法）B1B2B3B4产量311310A171928A2474105A39销量36566334130310-1-529121-11012vjui基变量：cij=ui+vj非基变量：σij=cij–(ui+vj)产销不平衡运输问题1.一般产销不平衡运输问题1)总产量总销量n1jjm1iiba£0xn,,3,2,1j,bxm,,3,2,1i,ax.t.sxczminijm1ijijn1jiijm1in1jijij假想一销地Bn+1，令销量为,运价c=0n1jjm1iiba5整数规划5.1整数规划实例及一般模型5.2分支定界法5.30-1整数规划5.4指派问题整数规划的类型纯整数规划：xj全部是整数混合整数规划：x