经济数学方法与模型教学PPT课件-第三章 线性规划精选.pptVIP

性质3.2.1　线性规划问题所有的可行解组成的集合 是凸集． 性质3.2.2　 是线性规划问题标准形式的基本可行解 的充要条件是： 为可行域 的极点． 凸集 凸集 不是凸集 极点 * 性质3.2.3　（线性规划基本定理）给定线性规划问题 ， 是秩为 的 矩阵． 若存在可行解，则必存在基本可行解； 若存在有界最优解，则必存在有界最优基本可行解。 该性质表明：在寻找线性规划的最优解时，只需在 其基本可行解中寻找．按性质3.2.2，基本可行解是可行 域的极点，因此若线性规划有最优解，则必定能在其可 行域的某个极点得到． * 第三节 单纯形法 单纯形法的基本思想是根据线性规划的解的 性质，在可行域中找到一个基本可行解作初始 解；并检验此解是否是最优解，若是最优解可结 束计算，否则就转到另一个基本可行解，并使目 标函数值得到改进；然后对新解进行检验，以决 定是否需要继续进行转换，一直到求得最优解为 止． * 例1 求下列线性规划问题 * 解：化为标准形 * 写出单纯形表 25/1 36/2 0 -3 -2 0 -2 -72 0 1 1/2 0 1 -1/2 7/1/2 1 x5 1/2 1 0 1/2 18/1/2 0 7 18 1 1/2 1/2 x2 0 x6离基， x2进基， x5离基， x1进基， * 0 -4 -2 -2 -1 -86 0 1 1 0 2 -1 1 x1 0 1 -1 1 0 14 11 0 1 0 x2 0 得到最优解，最优解为： （x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0） min z’=-86，max z=86 * 单纯形法计算的一般步骤： 1、建立初始单纯形表并确定初始可行基，从而确定 基变量及其值，计算出 ． 2、检验所得的基本可行解是否为最优解。若所有的 ≤0，则已获得最优解，停止计算，否则转入下一步。 3、基变换。确定换入变量和换出变量，从而得到主 元． 若所有的 中，有一个 对应的 的系数列向量 ，则此问题为无界解，停止计算，否则转下一步． 4、进行迭代得新的单纯形表． 重复24步直到取得最优解． * 第四节　大M法与两阶段法 在用单纯形法求解线性规划问题时，首先要确定一 个初始基本可行解．第三节所列举的模型中的所有约束 条件都是“≤”类型，且 ，当把这些模型 化为标准模型后，所有松驰变量的系数构成一个 阶子 矩阵，以其为基，松驰变量为基变量，右端常数就可提 供一个明显的初始基本可行解，但是，对于任意一个线 性规划问题，在化成标准模型后，一般来说不易直接得 到一个初始的基本可行解。 * 例1　线性规划模型 * 其标准模型（以下称为模型1，用M1表示）为 在上述模型中，只有松驰变量 的系数列向量为单 位向量，其他变量的系数列向量均为非单位向量，系数 矩阵中没有一个单位矩阵为基，由此可见该约束方程没 有一个明显的初始基本可行解。 * 为了迅速地找到一个初始基本可行解，就必须使方 程组的系数矩阵中存在一个三阶单位矩阵．为此，我们 在模型的约束方程组的后两个约束条件的左边，人为地 分别加上非负变量 和 （称这种人为引入的变量为人 工变量或人造变量），于是得到 （3.4.1） * 这时方程组（3.4.1）中， 所对应的列向量构成 一个单位矩阵，如果选 为初始基变量，则可得到方 程组（3.4.1）中一个明显的初始基本可行解 ． 由于人工变量的加入，破坏了原有模型的约束条件 ，因此上面得到的 不再是的基本可行解，但如果在求 解迭代过程中，人工变量能从基变量中退出，变为非基 变量，则方程组（3.4.1）的基本可行解也就自然成为模 型 的基本可行解了。为实现这一目的，就要设法在迭 代过程中让人工变量从基变量中退出去（或其值为零）。 下面介绍两种常用的方法—大M法和两阶段法． * 一、大M法 根据大M法对 构成的新问题为： 这里M是一个很大的正数，通常称M为惩