WEO啦

最优化理论与方法_2_单纯形法
收录时间:2023-01-26 03:27:53  浏览:1

1、第2章 线性规划的基本性质/2/1标准形式及图解法 2/2基本性质/2/1 标准形式/一般线性规划问题总可以写成下列标准形式: (2/1/1) 用矩阵表示: (2/1/2)/其中,A是mXn矩阵,c是n维行向量,b是m维列向量。 为了计算方便,一般假设 ,即b的每个分量都是非负数。/表示定理/设 为非空多面集,则有: 极点集非空,且存在有限个极点 / 极方向集为空集的充要条件是S有界。若S***,则存在有限个极方向 / xS的充要条件是:/定理与结论/线性规划的可行域是凸集。 设线性规划 (2/1/2)的可行域非空,则有下列结论: 线性规划(2/1/2)存在有限最优解的充要条件是所有 为非负数,

2、 其中 是可行域的极方向。 若线性规划(2/1/2)存在有限最优解,则目标函数的最优值可在某个极点上达到。(最优极点)/极点是个几何概念,直观性强,但不便于演算, 因此需要研究极点的代数含义。/基本可行解/称为方程组的一个基本解; B称为基矩阵,简称基; xB的各分量称为基变量; 基变量的全体 称为一组基; xN的各分量称为非基变量;/若 ,则称基本可行解是非退化的基本可行解; 若 且至少有一个分量是零,则称 此时的基本可行解是退化的基本可行解;同时,此基本可行解对应的基被称为退化的可行基。/又若 ,则称 为约束条件 的基本可行解, 称B为可行基矩阵, 为一组可行基;/基本可行解的个数/若A是

3、mXn矩阵, A的秩为m时, 基本可行解的个数不会超过:/定理与推理/线性规划的可行域是凸集。 设线性规划 (2/1/2)的可行域非空,则有下列结论: 线性规划(2/1/2)存在有限最优解的充要条件是所有 为非负数, 其中 是可行域的极方向。 若线性规划(2/1/2)存在有限最优解,则目标函数的最优值可在某个极点上达到。(最优极点) 线性规划的可行域的极点集与基本可行解集等价; 当线性规划(2/1/2)有可行解,则一定存在基本可行解。 当线性规划(2/1/2)存在最优解时,则一定存在一个基本可行解是目标函数的最优解。(最优基本可行解)/第3章 单纯形方法/3/1单纯形方法原理 3/2两阶段法

4、3/3修正单纯形法/单纯形方法的基本思想/就是,从一个基本可行解出发,求一个使目标函数值有所改变的基本可行解;通过不断改进基本可行解,力图达到最优基本可行解。 怎样实现基本可行解的转换?/表格形式的单纯形法/显然,在单纯形表中包含了单纯形方法所需的全部数据。/表格形式的单纯形法/显然,在单纯形表中包含了单纯形方法所需的全部数据。/主元/进基变量/离基变量/表格形式的单纯形法/解的几种情况在单纯形表上的体现(min型): 唯一最优解:终表非基变量判别数均小于零; 多重最优解:终表非基变量判别数中有等于零的; ***解:任意表有正判别数相应的系数列均非正。 max型单纯形表与min型的区别仅在于:

5、判别数反号,即, 令负判别数中最小的对应的变量进基; 当判别数均大于等于零时为最优。/两阶段法/用单纯形法消去人工变量(如果可能),即把人工变量变为非基变量,求出原问题的一个基本可行解; 首先引入人工变量。令 , 即 消去人工变量的一种方法是解如下第一阶段问题: 用单纯形法求解原问题。/设得到的最优基本可行解是 ,此时必有下列三种情况之一: (1) (无可行解) (2) 且 的分量都是非基变量 (得基本可行解 ) (3) 且 的某些分量是基变量 (用主元消去法)/大M法/其基本思想是:在约束中增加人工变量 xa,同时修改目标函数,增加惩罚值MeTxa ,M是很大的正数,这样,在极小化目标函数的

6、过程中,由于M的存在,将迫使人工变量离基。/修正单纯形法/在运用单纯形法解决线性规划问题时,如果知道了可行基的逆,就能利用它和原始数据来计算基变量的取值及判别数,从而能够确定一个基本可行解,并判断它是否为最优解。因此,只要保存原始数据和现行基的逆即可。 修正单纯形法的基本思想是:给定初始基本可行解以后,通过修改旧基的逆来获得新基的逆,进而完成单纯形法的其它运算。在整个过程中保存现行基的逆。/修正单纯形法的计算步骤/给定初始可行基的逆 ,计算单纯形乘子w 和右端向量 。构成下表: 对于每个非基变量,计算判别数,令 。 如果 则停止计算,现行基本可行解是最优解;否则,下一步。 计算主列 。若 /则停止计算/无有限最优解/ 否则下一步。 把主列置于逆矩阵表的右边,组成下表: 按最小比值确定主行,令 , r 为主行,以 为主元进行主元消去,然后去掉原来的主列,返回第2步。/目标函数值/单纯形乘

温馨提示:
1. WEO啦仅展示《最优化理论与方法_2_单纯形法》的部分公开内容,版权归原著者或相关公司所有。
2. 文档内容来源于互联网免费公开的渠道,若文档所含内容侵犯了您的版权或隐私,请通知我们立即删除。
3. 当前页面地址:https://www.weo.la/doc/a45ee9673aa84799.html 复制内容请保留相关链接。