线性规划及单纯形法第二部分

第一章线性规划及单纯形法(2)13.3 解法（单纯形法）基本思路n从可行域的某个顶点开始，不断地转换到另一个顶点，转换中使目标函数值得到改善（Max为增大，Min为减小），直到不能改善，就得到最优解n三个基本问题q1、如何寻找初始顶点（人工变量法、两阶段法）q2、如何判断某个顶点是否最优（检验数）q3、顶点转换（迭代）2ABC：最优解DO可行域OABCD3单纯形法的基本步骤n第一步：求出线性规划的初始基可行解n第二步：进行最优性检验-如果表中所有检验数n 则为最优解，否则继续。n第三步：从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表。n 确定换入基的变量n 确定换出基的变量n用换入的变量替换基变量中的掏出变量，得到一个新的基n第四步：4基本结论n线性规划问题的可行域（如果存在）是一个凸集n该凸集有有限个顶点（基可行解）n线性规划问题的最优解（如果存在），一定在某个顶点（基可行解）达到5求解的可能结果n唯一最优解n多最优解，即无穷多最优解n无界解，即目标函数值趋近无穷（通常是遗漏了约束）n无可行解（通常是存在矛盾的约束）6基可行解n基：Amn的非奇异子阵Bmmn基变量与非基变量：Bmm各列对应的变量为基变量XB，其余变量为非基变量XNn基解：X=（XB，XN），XB=B-1b，XN=0n基可行解：基解中，XB=B-1b0 目标函数值Z0=CBB-1bn可行基：基可行解对应的基7顶点转换n选择一个非基变量（进基变量）去替代一个基变量（出基变量），形成新的基变量组n进基变量选择qMAX：检验数0的非基变量中，检验数最大的非基变量qMIN：检验数0的非基变量中，检验数最小的非基变量n出基变量选择：最小比值法（保证新的基解还是可行的）8单纯形表9例4生产计划问题10初始表11（0，0）12最小比值法13迭代114（0，3）15迭代216为何x1不参加比选？17（2，3）18迭代319（4，2）20欲速则不达进基变量选择讨论n例1种，经过三次顶点转换才达到最优点；从图示看出，实际可以二次转换就达到n没有更好的指导标准21初始基可行解的确定人工变量法n对于任意一个线性规划问题，通常难以确定初始顶点n思路：强行添加人工变量，使得这些人工变量与模型中原有的某些变量（如松弛变量）的系数矩阵，能够构成一个单位矩阵n求解：对含有人工变量的模型进行求解，在求解过程中，逐渐用非人工变量替代基变量中的人工变量，当人工变量全部出基后，得到的就是原问题的初始基可行解22如何让人工变量尽快出基？n大M法qMAX：给每个人工变量一个量级很小的系数（M）qMIN：给每个人工变量一个量级很大的系数（M）n两阶段法q第一阶段：MIN Z=人工变量q第二阶段：原来的目标函数23示例24添加松弛与剩余变量x4,x525无法直接观察到初始可行基26添加人工变量x6,x7大M法27初始表28迭代129迭代230迭代331添加人工变量x6,x7两阶段法n第一阶段：构筑所有人工变量之和最小化的目标函数，用单纯形法求解32初始表阶段133迭代1阶段134迭代2阶段135n第一阶段求解的两种可能结果1.最优时，还有人工变量在最优基变量中：原问题无可行解2.最优时，所有人工变量都是非基变量：进入求解的第二阶段n第二阶段：目标函数换回原来的目标函数，在第一阶段得到的最优基基础上，继续求解（检验数、基转换）36初始表阶段237迭代1阶段238解的判别n唯一解：最优时，所有非基变量检验数0（MAX）或0（MIN）n多最优：最优时，存在某个非基变量检验数=0n无界解：未达到最优时，只要某个可以进基的变量的系数列向量元素的取值全部0（最小比值法无法进行）n无可行解：最优时，人工变量还在基变量中395-5单纯形法小结n1、线性规划模型化为标准形式n1）变量：要求为非负n2）约束条件：全为“=”，右端项要求为非负，若为负数，则约束条件两端乘“-1”；n约束条件“”，添加松弛变量n约束条件“”，减去剩余变量，添加人工变量n约束条件“=”，添加人工变量n3）目标函数：化为求极大，加松弛变量时，变量前系数为0，加人工变量时，变量前系数为-M40n2、单纯形法计算步骤n第一步：引进松弛变量、人工变量，列出初始单纯形表n第二步：计算非基变量各列检验数 ，基变量中无人工变量，某非基变量检验数不为0，则有唯一最优解，为0，则有无穷多最优解；若基变量中有人工变量，则无可行解。若 ，找出最大的正检验数 ，存在 ，对所有 计算，41迭代运算42Thanks for Attention!Questions&Answers43