华南理工大学 运筹学 第2章 线性规划的单纯形解法-1 工商管理学院

1第2章线性规划的单纯形解法线性规划的发展历程线性规划在美国数学家GeorgeDantzig（线性规划之父）提出单纯形解法后正式成为一门学科和研究分枝。线性规划问题的求解算法可以分为两大类：单纯形法内点算法（美籍印裔数学家NarendraKarmarkar）2单纯形法的思路单纯形法求解线性规划问题思路类似图解法，即可行域的有限顶点中寻找最优解。3找到可行域的任意一个顶点最优解/有无界解？求解结束移动到相邻的更优的顶点是否线性规划问题的标准形式单纯形法求解线性规划问题，要求问题模型必须先转化为标准形式。4112211112111211221212112111212max..,,,0,,,,0nnnnnmmmnmnmZcxcxcxaxaxaxbstaxaxaxbaxaxaxbxxxbbb线性规划问题的标准形式线性规划问题非标准形式的标准化处理1-目标函数为求最小值51212minmaxmax'min34max34ZZZZZxxZxxZ定义新的目标函数表达式为，将目标函数。例如:线性规划问题的标准形式线性规划问题非标准形式的标准化处理2-大于等于（“≥”）形式的不等式约束Surplusvariable6312123357357xxxxxx引入非负的剩余变量在不等号的左边减去一个非负的剩余变量，将不等式约束变为等式约束。例如:线性规划问题的标准形式线性规划问题非标准形式的标准化处理3-小于等于（“≤”）形式的不等式约束Slackvariable7312123357357xxxxxx引入非负的松弛变量在不等号的左边加上一个非负的松弛变量，将不等式约束变为等式约束。例如:线性规划问题的标准形式线性规划问题非标准形式的标准化处理4-决策变量非正或无符号限制844440xxxx如果决策变量非正，则引入该变量的相反数。例如:，则以替换掉所有的。线性规划问题的标准形式线性规划问题非标准形式的标准化处理4-决策变量非正或无符号限制911111xxxxx如果决策变量无符号限制（允许取负值），将决策变量替换为两个非负的新决策变量之差。例如，变量无符号限制，则以替换所有的。线性规划问题的标准形式线性规划问题非标准形式的标准化处理5-约束条件右端常数项为负数1012121357357xxxx将约束条件等式两端同时乘以。例如，线性规划问题的标准化示例111123123123123min2343330..24800,0,Zxxxxxxstxxxxxx无限制12331233412335123345max234433330..24480,,,,,0Zxxxxxxxxxstxxxxxxxxxxx（例2-1）单纯形法中的术语线性规划问题标准形式的矩阵描述12单纯形法中的术语13单纯形法中的术语14单纯形法中的术语示例1确定下面线性规划问题的所有基本解（例2-2）1512121212max354..63218,0Zxxxstxxxxx12132412512345max354..63218,,,,0Zxxxxstxxxxxxxxxx标准化单纯形法中的术语示例116单纯形法中的术语示例117单纯形法中的术语示例118单纯形法中的术语示例119单纯形法的计算步骤如果线性规划问题的最优解存在，那么最优解一定为该问题的某一个基本可行解。（定理2.2）20得到初始基本可行解最优解/有无界解？求解结束得到相邻的更优的基本可行解是否找到可行域的任意一个顶点最优解/有无界解？求解结束移动到相邻的更优的顶点是否单纯形法的计算步骤第1步：得到初始基本可行解21矩阵变化单纯形法中的术语22单纯形法的计算步骤第2步：基本可行解的最优检验及判定典则形式中，非基变量的检验数就是用于判断当前基本可行解是否为最优解的数学指标。23单纯形法的计算步骤第2步：基本可行解的最优检验及判定24单纯形法的计算步骤第3步：迭代得到相邻的更优的基本可行解在所有正检验数的非基变量中选择一个非基变量（入基变量）换入基变量组合，同时（为了使基变量数量维持不变）将现有的某一个基变量（出基变量）换出成为非基变量，从而得到新的基变量组合。所谓“相邻”，是指新的基变量组合只是替换了原有组合中的1个而不是多个基变量（在空间上，新的基本可行解与原基本可行解是可行域中的相邻顶点！）。25单纯形法的计算步骤第3步：迭代得到相邻的更优的基本可行解当正检验数的非基变量只有一个时，该非基变量为入基变量；当有正检验数的非基变量不止一个时，选择正检验数最大的非基变量作为入基变量-xk。26单纯形法的计算步骤第3步：迭代得到相邻的更优的基本可行解确定入基变量后，找出基变量的思路是：随着入基变量值的增大，取值最先变为0的基变量就是出基变量-xq。27单纯形法的计算步骤第3步：迭代得到相邻的更优的基本可行解确定了入基变量和出基变量后，就得到了新的基变量组合。继续写出新的基变量组合所对应的线性规划问题的典则形式。28单纯形法的计算步骤第3步：迭代得到相邻的更优的基本可行解29单纯形法的计算步骤第3步：迭代得到相邻的更优的基本可行解30单纯形法计算示例1例2-331maxZ=3x1+5x2s.t.x1£4x2£63x1+2x2£18x1,x2³0ÞÞÞmaxZ=3x1+5x2s.t.x1+x3=4x2+x4=63x1+2x2+x5=18x1,x2,x3,x4,x5³0单纯形法计算示例1第1步：找到初始基本可行解32121324125123453453451212max354..63218,,,,0,,,,,,Zxxxxstxxxxxxxxxxxxxxxxxxxx变量在系数矩阵中对应的列向量构成了一个单位矩阵，可选择变量为基变量，变量为非基变量。并且，目标函数中只有非基变量，当前已经是典则形式！单纯形法计算示例1第2步：基本可行解的最优检验及判定33单纯形法计算示例1第3步：迭代计算34单纯形法计算示例1第3步：迭代计算35单纯形法的解释当前非基变量为x1,x2（=0），基变量为x3,x4,x5（=0）。现确定了非基变量x2为入基变量，即非基变量x2成为了基变量。根据定义，一个入基变量，则必须有一个基变量出基，即变为非基变量（=0）。同时，另外一个非基变量x1保持不变，即x1=0。36单纯形法的解释出基变量的选择（x20）37x1+x3=4x2+x4=63x1+2x2+x5=18Þ0+x3=4x2+x4=60+2x2+x5=18Þx4=6-x2=b2-a22x2=0x5=18-2x2=b3-a32x2=0Þx4:x2=6=b2a22x5:x2=9=b3a32单纯形法的解释出基变量的选择（x20）38x1+x3=4x2+x4=63x1+2x2+x5=18Þx4:x2=6=b2a22x5:x2=9=b3a32单纯形法的解释无边界解的情况39maxZ=3x1+5x2s.t.x1+x3=4-x2+x4=63x1-2x2+x5=18x1,x2,x3,x4,x5³0Þx4=6+x2a220()x5=18+2x2a320()单纯形法的解释最优化判断出基变量选择40单纯形法计算示例1第3步：迭代计算计算得出当前基变量组合所确定的典式4114132414512345max30354..6326,,,,0Zxxxxstxxxxxxxxxxx2=6-x4单纯形法计算示例1第2轮迭代，计算42x3=4-x1x5=6-3x114132414512345max30354..6326,,,,0Zxxxxstxxxxxxxxxx单纯形法计算示例1第3轮迭代，计算得到43453452414512345max36321..233621233,,,,0Zxxstxxxxxxxxxxxxx单纯形表解法将标准化后的线性规划问题用矩阵形式填入表格来完成求解过程，此即单纯形表法，或称单纯形表上作业法。44单纯形表解法45单纯形表解法46单纯形表解法非基变量的检验数47单纯形表解法48X单纯形表解法非基变量的检验数49单纯形表解法50X单纯形表解法示例1例2-4511212131224121251212345max35max3544....6632183218,0,,,,0ZxxZxxxxxststxxxxxxxxxxxxxxx单纯形表解法示例152单纯形表解法示例153单纯形表解法示例154单纯形表解法示例155单纯形表解法示例156单纯形（表）解法的详细步骤57