1-4(1)

null第一章 线性规划 第一章 线性规划 第四节 单纯形法典式 迭代原理 单纯形法举例 两阶段法 null复习基变量个数与方程个数一致null复习null证明：检验数向量非基变量检验数向量复习第一章 线性规划 第一章 线性规划 一.典式典式的向量形式 典式的分量形式 典式的表格形式(单纯形表) 基本可行解null基本可行解1.典式的向量形式典式的向量形式一个典式唯一地对应一个基本可行解称为(LP)的以 为基变量的典式null例：null例：典式(基变量为x1,x2)：基本可行解：目标值：可行基典式基本可行解注：基变量：只出现在其中一个方程中，且系数为1。null2.典式的分量形式B(可行基)null例：典式(基变量为x1,x2)：nullnullnull例：典式(基变量为x1,x2)：nullnull例：null1.每个方程都有且仅有一个基变量，基变量仅出现在一个方程中且系数为1。 2.非基变量的系数是其检验数。典式的分量形式null例：典式(基变量为x1,x2)：基本可行解：目标值：null典式的分量形式null非基变量 的检验数null典式的分量形式:基本可行解:目标值:0， 0， null0001101单纯形表3.典式的表格形式(单纯形表)nullnull单纯形表：null单纯形表：基本可行解:目标值:0， 0， null例：典式基本可行解：目标值：1-2010021010201-1单纯形表：null例：典式基本可行解：目标值：101111221210111021011-201002101null例：典式基本可行解：目标值：1-2010021011212110201-1第一章 线性规划 第一章 线性规划 一.典式典式的向量形式 典式的分量形式 典式的表格形式(单纯形表) 基本可行解第一章 线性规划 第一章 线性规划 第四节 单纯形法典式 迭代原理 单纯形法举例 两阶段法 第一章 线性规划 第一章 线性规划 一.典式典式的向量形式 典式的分量形式 典式的表格形式(单纯形表) 基本可行解复习null1.典式的向量形式：2.典式的分量形式：复习null1.典式的向量形式：复习2.典式的分量形式：基本可行解基本可行解:目标值:null0001101单纯形表3.典式的表格形式(单纯形表)null单纯形表：基本可行解:目标值:最优单纯形表最优解null单纯形法的迭代思想：顶点1顶点2顶点3基本可行解1基本可行解2基本可行解3单纯形表1单纯形表2单纯形表3………………null二.迭代原理：初始基本可行解新的基本可行解初始单纯形表null0000011.初始单纯形表00000100000101初始基本可行解null二.迭代原理：初始基本可行解新的基本可行解null2) 若有某些检验数 ，例如：1) 若 或2.判断当前基本可行解是否是最优解：即非基变量 的检验数 都 ， 则 是最优解。则 不是最优解(在非退化情况下)。null0001）单纯形表000000101最优解null0002）单纯形表000000101不是最优解null二.迭代原理：初始基本可行解新的基本可行解3. 转移到新的基本可行解：确定进基变量 确定离基变量 进行换基运算3. 转移到新的基本可行解：null1.典式的向量形式：2.典式的分量形式：复习null1)确定进基变量：将检验数 的非基变量进基做基变量，可使新的基本可行解目标函数值下降。<0确定进基变量的准则：null确定进基变量的准则：1. Bland 规则：2. 最负检验数法：null000单纯形表0000001013. 转移到新的基本可行解：确定进基变量 确定离基变量 进行换基运算3. 转移到新的基本可行解：null1.典式的向量形式：2.典式的分量形式：复习null2)确定离基变量：null2)确定离基变量：最小非负比值准则null000单纯形表000000101第一种情况：假设null000单纯形表000000101第二种情况：若则对 没限制，而即(LP)没有有限的最优解。null第三种情况：无穷多最优解判别条件：若对于某个基本可行解，所有检验数都非负，且存在一个非基变量的检验数=0，则(LP) 有无穷多个最优解。 3. 转移到新的基本可行解：确定进基变量 确定离基变量 进行换基运算3. 转移到新的基本可行解：null因为 代替 成为第p 个方程的基变量，所以它只能出现在第p个方程中，且系数为1，不能出现在其他方程中，检验数也为0。0000000001013)换基运算：100003. 转移到新的基本可行解：确定进基变量 确定离基变量 进行换基运算3. 转移到新的基本可行解：null二.迭代原理：初始基本可行解新的基本可行解null若 (LP)没有有限的最优解。 迭代原理：初始基本可行解X0X0是最优解确定进基变量xq确定离基变量xp换基运算新的基本可行解X 1第一章 线性规划 第一章 线性规划 第四节 单纯形法典式 迭代原理 单纯形法举例 两阶段法 null例1-10求解线性规划问题：0 -3 -2 -4 0 01 1 3 1 0 00 -2 1 1 1 00 -1 6 -1 0 1-6 6 3 41001 -2 1 -3 0 0单纯形表典式null 1 3 1 0 00 -3 -2 -4 0 00 -2 1 1 1 00 -1 6 -1 0 1-6 6 3 46，0，0，0，3，46073152例1-10表一null 1 3 1 0 00 -3 -2 -4 0 02 0 7 3 1 00 -1 6 -1 0 1-6 6 15 46，0，0，0，3，46例1-10109010表一null 1 3 1 0 00 -3 -2 -4 0 02 0 7 3 1 01 0 9 0 0 1-6 6 15 106，0，0，0，3，46例1-10表一null 1 3 1 0 00 -3 -2 -4 0 02 0 7 3 1 01 0 9 0 0 1-6 6 15 106，0，0，0，3，46例1-10307-112表一null2 0 7 3 1 0 1 3 1 0 03 0 7 -1 0 01 0 9 0 0 112 6 15 106，0，0，0，3，46例1-100，6，0，0，15，10-1215表一表二null 0 1 01 1 3 1 0 03 0 7 -1 0 01 0 9 0 0 112 6 5 106，0，0，0，3，46例1-100，6，0，0，15，10-121表二null 0 1 0 1 0 03 0 7 -1 0 01 0 9 0 0 112 1 5 106，0，0，0，3，46例1-100，6，0，0，15，10-12170表二null 1 0 0 0 1 01 0 9 0 0 117 1 5 106，0，0，0，3，46例1-100，6，0，0，15，10-120，1，0，5，0，10-17000表二最优表null例1-11求解线性规划问题：-1 -3 -4 0 0 3 5 -4 1 0 -2 3 1 0 1 0 10 500-1 -3 -4 0 0 单纯形表null3 5 -4 1 0 0，0，0，10，50例1-11-2 3 1 0 1 -1 -3 -4 0 0 5 1001null0，0，0，10，50例1-11-1 -3 -4 0 0 010010null0，0，0，10，50例1-11 1001000，0，0，null0，0，0，10，50例1-11 1001000，0，0，该问题没有有限的最优解第一章 线性规划 第一章 线性规划 第四节 单纯形法典式 迭代原理 单纯形法举例 两阶段法 作业：P95 6 (1) (2) (3)作业：P41 6 (1) (2) (3)