单纯形法小结VIP免费

单纯形法小结继续继续返回返回上页下页返回基本概念•线性规划模型–三个要素：•决策变量、目标函数、约束条件–线性性•线性规划解的性质–线性规划问题的可行域是凸集。上页下页返回–最优解必在顶点上得到。•线性规划求解方法–图解法–单纯形法重点掌握内容上页下页返回单纯形法小结•一般线性规划问题的标准化及初始单纯形法表.—变量''''''''00:,0,,0jjjjjjjjjjjxxxxxxxxxxx不需要处理令无约束令：上页下页返回—约束条件单纯形法小结00-1,bb不需要处理约束条件两端同乘加松弛变量加人工变量加剩余变量再加人工变量上页下页返回–目标函数•单纯形法计算步骤框图单纯形法小结maxminZ,maxZ:0:0:ZZZM不需要处理令：求松弛变量加入变量的系数剩余变量人工变量上页下页返回1.2./,/3.,1,04.,,ljllklkklllklljlkljlkabijikijiikiaaxxlbabaaakaaaabab迭代运算:用非基变量替换基变量对主元行第行,令对主元列第列令其他元素表中其他行列元素令引进松弛变量、人工变量列出初始单纯行表计算非基变量各列检验数σj找出最大的正检验数σk所有σj≤0基变量中有人工变量某非基变量检验数为0唯一最优解存在aik>0无可行解无穷多解无界解0/min{}ikiiiklilkabaa对所有计算令找出主元素是是是是否否否否上页下页返回一、已知某LP的初始单纯形表和单纯形法迭代的表，求未知数a~l的值。6bcd101-13e01a-1200fg2-11/204hi11/210-7jkljcbBX1x3x2x4x5xjjzc4xjjzcx1x55x上页下页返回6bcd101-13e01a-1200fg2-11/204hi11/210-7jkLjcbBX1x3x2x4x5xjjzc4xjjzcx1x55xb=2102c/2=2c=44d/2=-1d=-2-2-2a-1=-7a=33350g=1h=01=-1+ee=225-3/2解：上页下页返回•二、LP问题maxz=CX,AX=b，X≥0，如是该问题的最优解，又为某一常数，分别讨论下列情况时最优解的变化。（1）目标函数变为（2）目标函数变为（3）目标函数变为约束条件变为CXzmaxX*0XICz)(maxmaxzCXAXb上页下页返回•解：（a）仍为最优解，；（b）一般不再是问题的最优解。（c）最优解变为，目标函数值不变。X**maxCXz*X*X上页下页返回三、考虑LP问题，分别用大M法和两阶段法求解0,,623824..32min32121321321xxxxxxxxtsxxxz上页下页返回大M法，第一步转化成标准型：0,,623824..0032max3217521643217654321xxxxxxxxxxxxtsMxMxxxxxxz第二步建表：上页下页返回-2-3-100-M-Mθx1x2x3x4x5x6x7-Mx68142-10102-Mx763200-1013cj-zj4M-26M-32M-1MM00-3x221/411/2-1/401/408-Mx725/20-11/2-1-1/214/5cj-zj5/2M-5/401/2-MM/2-3/4-M3/4-1/2M0-3x29/5013/5-3/101/103/10-1/10-2x14/510-2/51/5-2/5-1/52/5cj-zj000-1/2-1/2-M+1/2-M+1/2BBCXbjc。问题具有无穷多最优解，即该换入得到另一个最优解可作为基所以且存在系数所对应检验数基变量小于等于零，而其中非结论：所有的检验数都LPxax31333,0,0上页下页返回两阶段法：0,,623824..min32175216432176xxxxxxxxxxxxtsxxw化成标准型：0,,623824..max32175216432176xxxxxxxxxxxxtsxxw上页下页返回00000-M-Mθx1x2x3x4x5x6x7-Mx68142-10102-Mx763200-1013cj-zj4M-26M-32M-1MM00-3x221/411/2-1/401/408-Mx725/20-11/2-1-1/214/5cj-zj5/2M-5/401/2-MM/2-3/4-M3/4-1/2M0-3x29/5013/5-3/101/103/10-1/10-2x14/510-2/51/5-2/5-1/52/5cj-zj000-1/2-1/2-M+1/2-M+1/2BBCXbjc上页下页返回•四、已知线性规划问题用单纯形法求解得最终单纯形表如下,表中x4x5为松弛变量试计算确定c1、c2、c3和b1、b2的值。0,,2322..max32123211321332211xxxbxxxbxxxtsxcxcxcz续x1x2x3x4x5x211/5103/5-1/5x333/501-1/52/5cj-zj-7/1000-3/5-4/5上页下页返回•解：建立初始单纯形表,•根据单纯形法的矩阵描述，有•由•,解出c1=1.5,c2=2,c3=3及b1=5,b2=5。x1x2x3x4x5x211/5103/5-1/5x333/501-1/52/5cj-zj-7/1000-3/5-4/5...