单纯形方法求解

单纯形方法求解第1页，课件共28页，创作于2023年2月1.图解法的局限图解法只可解决两个变量的线性规划问题，而在实际应用中还有多个变量的线性规划问题无法解决。因此，

1947年G.B.Dantzig提出的单纯形法提供了方便、有效的通用算法求解线性规划。

第2页，课件共28页，创作于2023年2月3基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。非基向量：在A中除了基B之外的一列则称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n－m个。基本概念第3页，课件共28页，创作于2023年2月一、单纯形法的基本原理

顶点的逐步转移

即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。第4页，课件共28页，创作于2023年2月基本思路：第5页，课件共28页，创作于2023年2月

根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。

于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据第6页，课件共28页，创作于2023年2月表格单纯形法例题1：用单纯形法求解线性规划问题

maxf=3x1+4x2x1+2x2≤63x1+2x2≤12x2≤2x1≥0,x2≥0第7页，课件共28页，创作于2023年2月首先将此现行规划问题化为标准形式得到：minf’=-f=-3x1-4x2x1+2x2+x3=63x1+2x2+x4=12x2+x5=2x1≥0,x2≥0,x3≥0,x4≥0,x5≥0第8页，课件共28页，创作于2023年2月表格单纯形法：1、初始单纯形表的建立(1)表格结构：

-3-4000常数dx1x2x3x4x50x31210060x432010120x5010012检验数b340000cjxjxBcB第9页，课件共28页，创作于2023年2月单纯形表的列法：原方程中自带的变量称为非基变量，如x1,x2;为解题而设出的变量称为基变量，如x3,x4,x5。cj：目标函数中变量的系数;xj:变量；xB：基变量；cB:基变量在目标函数中对应的系数；d:各约束条件的常数项；检验数：第10页，课件共28页，创作于2023年2月求例题的检验数：b01=0*1+0*3+0*0-(-3)同理求得b02,b03,b04,b05则最右下角的我们称之为b0，所以b0=0第11页，课件共28页，创作于2023年2月解答：（1）确定换入基的变量。只要有检验数b﹥0，对应的变量xj就可作为换入基的变量，当有一个以上检验数大于零时，一般从最大的开始。因此在本题的检验数中找到最大的正检验数。-3-4000常数dx1x2x3x4x50x31210060x432010120x5010012检验数b340000cjxjxBcB第12页，课件共28页，创作于2023年2月这说明我要调整非基变量x2，使其成为基变量，并相应调出一个基变量为非基变量。（2）确定换出基的变量。为确定哪个基变量调出首先计算:所以本题有：则此最小值对应x5,所以我们将x5行与x2列相交的数值“1”圈起来。即要将x2与x5进行调整。“1”被称为旋转元素。第13页，课件共28页，创作于2023年2月（3）用换入变量xj替换换出变量xB，得到一个新的基。对应这个基找出新的基可行解并列出新的单纯性表。ⅰ）首先将旋转元变为“1”，即将所要转换的基变量行除以旋转元。因为本题中旋转元已经为“1”，所以x5行不用调整。ⅱ）将旋转元所在行转换后的整行数字乘以（-aij),加到表中的第i行数字上，即将要转化为基变量的列变为除转换元为“1”外，其他数字都为“0”的列。在本题中，即是将x5行中的各数乘以（-2），分别加到x3和x4行上。再将x5行乘以（-4）加到检验行上。使得x2列上除了旋转元变为“1”，其余数字都变为“0”。并将xB列中的x5调为x2,表示x2调入基变量，x5调入非基变量。因此得到下表。第14页，课件共28页，创作于2023年2月-3-4000常数dx1x2x3x4x50x31010-220x43001-28-4x2010012检验数b3000-4-8cjxjxBcB以上不过程称之为迭代。如果检验数中任然存在大于“0”的数字，则重复以上3个步骤。直至检验数中所有数字均小于等于0，此时所的的结果即为最优解。第15页，课件共28页，创作于2023年2月以上线性规划问题所得的最后检验数都小于或等于“0”的单纯形法表格如下：-3-4000常数dx1x2x3x4x5-3x110-1/21/2030x500-3/41/411/2-4x2013/4-1/403/2检验数b00-3/2-1/20-15cjxjxBcB因此得到当x1=3，x2=3/2,x3=x4=0,x5=1/2时，目标函数最大值f=15.第16页，课件共28页，创作于2023年2月练习1：第17页，课件共28页，创作于2023年2月①将线性规划问题化成标准型②建立初始单纯形表③计算各非基变量xB的检验数

若所有b≤0，则问题已得到最优解，停止计算，否则转入下步。④在大于0的检验数中，若某个bj﹥0，而所对应的列中没有正数，则此问题是无界解，停止计算，否则转入下步。二、单纯形法的计算步骤

第18页，课件共28页，创作于2023年2月⑤根据max{dj｜dj＞0}=dk原则，确定xk为换入变量(进基变量)，再按规则计算：=min{bi′/aik′|aik′＞0}=bl′/aik′

确定出换出变量。建立新的单纯形表，此时换入非基变量取代了换出基变量的位置。以aik′为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik′变为1，同列中其它元素为0。后转第③步。

第19页，课件共28页，创作于2023年2月练习2：第20页，课件共28页，创作于2023年2月人工变量法

用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基。但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵。人工变量

采用人造基的办法：人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。处理方法有两种：大M法两阶段法第21页，课件共28页，创作于2023年2月例题2：大M法第22页，课件共28页，创作于2023年2月大M法：本题化为标准形式后，发现只有x4一个基变量，但题中需要三个基变量，于是，加入行x6,x7两个人工变量。其目标函数中的系数为M，M代表任意大的正值。第23页，课件共28页，创作于2023年2月练习3：第24页，课件共28页，创作于2023年2月两阶段法：第一阶段：先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中的其他变量系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束条件不变的情况下求这个目标函数极小化的解。显然在第一阶段中，当人工变量取值为零时，目标函数值为零。这个时候的最优解就是原线性规划问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为零，即最优解的非基变量中含有非零的人工变量，表明线性规划问题无可行解。第二阶段：当第一阶段求解结果表明问题有可行解，则此阶段在原问题中去除人工变量，并从此可行解出发继续寻找最优解。第25页，课件共28页，创作于2023年2月例3：两阶段法第26页，课件共28页，创作于2023年2月单纯形法一般还可证明：1.解的情况：(1)如果在单纯形表中所有检验数都非正：

1）若基变量中含非零的人工变量，