运筹学一般单纯形法课件

第三章　单纯形法单纯形法的一般解法大M法和两阶段法修正单纯形法单纯形法的数学原理单纯形法适用于任何线性规划问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 的求解。第一节　单纯形法的一般解法例：步骤1引入松弛变量等，将问题化成标准形式；步骤3形成初始 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 如下，表中基变量为Ａ矩阵中完全单位向量组对应的变量。段cj→Cθi注↓基bp1p2…pn1基变量对应的cj基变量例段cj→θi注↓基bP1P2P3P41cj-zj→　　例段cj→031000θi注↓基bP1P2P3P410x32434100x415-1501cj-zj→　　步骤4.1计算检验数Ｃｊ－Ｚｊ：其中Ｚｊ等于Ｐｊ中各分量与相应的左边各Ｃｊ的乘积之和，Ｃｊ－Ｚｊ等于Ｐｊ上面对应的Ｃｊ减去Ｚｊ；段cj→031000θi注↓基bP1P2P3P410x32434100x415-1501cj-zj→　　步骤4.2：判断（１）若所有检验数均≤０时，即得到最优解和最优值；（２）若检验数存在正值，继续下一步。本例中：c1-z1>0，c2-z2>0段Cj→031000θi注↓基bP1P2P3P410x32434100x415-1501cj-zj→31000　　5.1决定主元素：当表中出现正检验数时，找出其中绝对值最大的一个所在的列作为主元列，记为Pj*，然后用主元列中各正分量去除b列中相应的分量，得到θi，接着取θi中最小的分量所在的行为主元行，记为Pi*；主元行与主元列相交处的元素即主元素，记为Pi*j*；找到主元素后，打上一个圈以示区别。段Cj→031000θi注↓基bP1P2P3P410x32434100x415-1501Cj-Zj→31000　　5.2：换基把主元行对应的变量（出基变量/调出变量）从基底调出，用主元列对应的变量（入基变量/调入变量）代替之，进入下一段。例中：x4调出，x2调入。段Cj→031000θi注↓基bP1P2P3P410x324341060x415-1(5)013Cj-Zj→31000　　换基后段Cj→031000θi注↓基bP1P2P3P410x324341060x415-1(5)013Cj-Zj→31000　　20x310x2Cj-Zj→　5.3：计算新元素 5.3.1原主元行上元素的计算：将原主元行上的元素，分别除以主元素，使主元素为“1”。即：段Cj→031000θi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000　　20x310x2Cj-Zj→　　例：段Cj→031000θi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000　　20x310x23-1/5101/5Cj-Zj→　　5.3计算新元素5.3.2原非主元行上元素的计算：先将原主元行上的新元素乘以某一数A后，分别加上原非主元行上的元素，使原主元列上各元素除了原主元素为“1”外，其余均为0。段Cj→031000θi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000　　20x3010x23-1/5101/5Cj-Zj→　　步骤6：回到第4步步骤4：计算检验数、判断检验数计算检验数Ｃｊ-Ｚｊ：（１）若所有检验数均≤０时，即得到最优解和最优值；（２）若检验数存在正值，继续下一步。计算检验数，判断检验数段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000　　20x31219/501-4/510x23-1/5101/5Cj-Zj→　　换基迭代，计算新元素（原主元行）段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000　　20x312(19/5)01-4/5调出10x23-1/5101/5Cj-Zj→500-2　　33x1　　10x2Cj-Zj→　　换基迭代，计算新元素（原主元行）段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000　　20x312(19/5)01-4/5调出10x23-1/5101/5Cj-Zj→500-2　　33x160/19105/19-4/19　　10x20Cj-Zj→　　计算检验数，判断检验数段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→31000　　20x312(19/5)01-4/5调出10x23-1/5101/5Cj-Zj→500-2　　33x160/19105/19-4/19　　10x269/19011/193/19Cj-Zj→00-25/19-18/19　　结论所有检验数均为非正，得最优解、最优值。最优解即基变量对应的ｂ列数值，不在基变量范围的其他变量数值为０；最优值检验数对应的ｂ列数值的相反数。段Cj→031000Qi注↓基bP1P2P3P410x32434106调出0x415-1(5)013Cj-Zj→031000　　20x312(19/5)01-4/5调出10x23-1/5101/5Cj-Zj→-30500-2　　33x160/19105/19-4/19　　10x269/19011/195/19Cj-Zj→-870/1900-25/19-18/19　　标准化：引入松弛变量x3,x4,x5写出各系数矩阵Ａ，B和Ｃ;解题过程初始表段Cj→034000Qi注↓基bP1P2P3P4P510x36121000x412320100x5201001Cj-Zj→　　段Cj→034000Qi注↓基bP1P2P3P4P510x3612100　0x41232010　0x5201001Cj-Zj→034000　　段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　20x300x404x2201001　Cj-Zj→　　段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　20x321010-20x483001-24x2201001Cj-Zj→　　段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　20x321010-20x483001-24x2201001　Cj-Zj→-83000-4　　段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　20x32（1）010-22→0x483001-28/34x2201001-　Cj-Zj→-83000-4　　段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　20x32（1）010-22→0x483001-28/34x2201001　Cj-Zj→-83000-4　　33x121010-2　　0x404x20Cj-Zj→段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　20x32（1）010-22→0x483001-28/34x2201001　Cj-Zj→-83000-4　　33x121010-2　　0x4200-3144x2201001Cj-Zj→　　段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　20x32（1）010-22→0x483001-28/34x2201001　Cj-Zj→-83000-4　　33x121010-2　　0x4200-3144x2201001Cj-Zj→-1400-302　　段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　20x32（1）010-22→0x483001-28/34x2201001　Cj-Zj→-83000-4　　33x121010-2　　0x4200-31（4）1/2→4x22010012　Cj-Zj→-1400-302　　段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　20x32（1）010-22→0x483001-28/34x2201001　Cj-Zj→-83000-4　　33x121010-2　　0x4200-31（4）1/2→4x22010012　Cj-Zj→-1400-302　　43x10　　0x51/200-3/41/414x20Cj-Zj→　　段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　20x32（1）010-22→0x483001-28/34x2201001　Cj-Zj→-83000-4　　33x121010-2　　0x4200-31（4）1/2→4x22010012　Cj-Zj→-1400-302　　43x1310-1/21/20　　0x51/200-3/41/414x23/2013/4-1/40Cj-Zj→　　段Cj→034000Qi注↓基bP1P2P3P4P510x36121003　0x412320106　0x520（1）0012→Cj-Zj→034000　　20x32（1）010-22→0x483001-28/34x2201001　Cj-Zj→-83000-4　　33x121010-2　　0x4200-31（4）1/2→4x22010012　Cj-Zj→-1400-302　　43x1310-1/21/20　　0x51/200-3/41/414x23/2013/4-1/40Cj-Zj→-1500-3/2-1/20　　计算结果练习题