运筹学第2章-单纯形法.pptx

赵明霞

山西大学经济与管理学院;第2章单纯形法;单纯形法

内容

原本方法

对偶方法

形式

方程组形式

表格形式

矩阵形式;2024/3/18;2024/3/18;2024/3/18;根本性质：

线性规划问题的可行域是凸集。

标准形线性规划的根本可行解与可行域的极点互相对应。

线性规划的根本定理对标准形线性规划问题〔M〕：

假设有可行解，那么必有根本可行解；

假设有最优解，那么必有最优根本解。

假设LP问题的可行域R≠Φ，那么R至少有一个极点。

LP问题可行域R的极点为有限个。;2024/3/18;2024/3/18;2024/3/18;2024/3/18;判断已求得的根本可行解是否是最优解。

〔1〕最优性检验的依据——检验数σj;CB;3、基变换

(1)入基变量确实定——最小检验数规那么

从最优解判别定理知道，当某个σj0时，非基变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数小于0的非基变量换到基变量中去〔称之为入基变量〕。假设有两个以上σj0的，那么为了使目标函数增加得更大些，一般选其中的σj最小者的非基变量为入基变量。

在本例题中σ1=-3是检验数中最小的负数，应选x1为入基变量。

同时，入基变量xk的系数列向量ak为主列。;(2)出基变量和主元确实定——最小比值规那么

确定出基变量的方法：把已确定的入基变量在各约束方程中的正的系数除其所在约束方程中的常数项值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。

这样在下一步迭代的矩阵变换中可以确保新得到的bi值都大于等于零。

出基变量xl所在行的系数alj构成主行。

确定主元的方法：主行〔最小比值所在的约束方程〕与主列〔入基变量系数列〕交于alk为主元。

基变换通过初等变换实现，目标：将主列化为单位向量〔alk=1〕，以符合典式;x1为入基变量，我们把各约束方程中x1的为正的系数除对应的常量，得

所以，出基变量应为x3，主元为a13;;;2024/3/18;添加人工变量;1、大M法;;2、两阶段法

将参加人工变量后的线性规划划分两阶段求解。

第一阶段：判断原线性规划是否有基可行解，方法是先求解以下线性规划问题;;;;;第二阶段：求解原问题，

删除第一阶段最终单纯形表中的人工变量各列、cj列、cj行、检验行；

将cj换成原问题的cj；

重新计算。

;;;;;;2024/3/18;2024/3/18;2024/3/18;作业