《运筹学一般单纯形法讲解》由会员分享，可在线阅读，更多相关《运筹学一般单纯形法讲解（48页珍藏版）》请在金锄头文库上搜索。
1、第三章 单纯形法,单纯形法的一般解法 大M法和两阶段法 修正单纯形法 单纯形法的数学原理,单纯形法适用于任何线性规划问题的求解。,第一节 单纯形法的一般解法,例：,步骤1,引入松弛变量等，将问题化成标准形式；,步骤2,具体写出各系数矩阵，B，j和; 特别注意：A矩阵中有否完全单位向量组。,步骤3,形成初始表如下，表中基变量为矩阵中完全单位向量组对应的变量。,例,例,步骤4.1,计算检验数：其中等于中各分量与相应的左边各的乘积之和，等于上面对应的减去；,步骤4.2：判断,（）若所有检验数均时，即得到最优解和最优值； （）若检验数存在正值，继续下一步。 本例中：c1-z10，c2-z20,步骤5：
2、换基迭代,5.1决定主元素 5.2换基迭代 5.3计算新元素,5.1 决定主元素：,当表中出现正检验数时，找出其中绝对值最大的一个所在的列作为主元列，记为Pj*，然后用主元列中各正分量去除b列中相应的分量，得到 i，接着取 i中最小的分量所在的行为主元行，记为Pi*；主元行与主元列相交处的元素即主元素，记为Pi*j*；找到主元素后，打上一个圈以示区别。,例：,主元列,主元行,主元素,5.2：换基,把主元行对应的变量（出基变量/调出变量）从基底调出，用主元列对应的变量（入基变量/调入变量）代替之，进入下一段。 例中：x4调出，x2调入。,换基后,5.3：计算新元素,5.3.1 原主元行上元素的计
3、算： 将原主元行上的元素，分别除以主元素，使主元素为“1”。即：,例：,5.3 计算新元素,5.3.2 原非主元行上元素的计算： 先将原主元行上的新元素乘以某一数A后，分别加上原非主元行上的元素，使原主元列上各元素除了原主元素为“1”外，其余均为0。,则：A=-4,步骤6：回到第4步,步骤4：计算检验数、判断检验数 计算检验数-： （）若所有检验数均时，即得到最优解和最优值； （）若检验数存在正值，继续下一步。,计算检验数，判断检验数,计算检验数，判断检验数,换基迭代，计算新元素（原主元行）,换基迭代，计算新元素（原主元行）,计算新元素（原非主元行）,计算检验数，判断检验数,结论,所有检验数均为非正，得最优解、最优值。 最优解即基变量对应的列数值，不在基变量范围的其他变量数值为； 最优值检验数对应的列数值的相反数。,例2,标准化：引入松弛变量x3,x4,x5,写出各系数矩阵，B和;,解题过程,初始表,计算结果,练习题,
