最优化理论与方法单纯形法精.ppt

最优化理论与方法单纯形法第1页，本讲稿共18页2.1 标准形式o一般线性规划问题总可以写成下列一般线性规划问题总可以写成下列标准形式标准形式：(2.1.1)o用矩阵表示：用矩阵表示：(2.1.2)其中，A是mXn矩阵，c是n维行向量，b是m维列向量。为了计算方便，一般假设 ，即b的每个分量都是非负数。第2页，本讲稿共18页表示定理o设 为非空多面集，则有：n极点集非空，且存在有限个极点 .n极方向集为空集的充要条件是S有界。若S无界，则存在有限个极方向 .nxS的充要条件是：第3页，本讲稿共18页定理与结论o线性规划的可行域是凸集。线性规划的可行域是凸集。o设线性规划设线性规划(2.1.2)的可行域非空，则有下列结论：的可行域非空，则有下列结论：n线性规划线性规划(2.1.2)存在有限最优解的充要条件是所有存在有限最优解的充要条件是所有 为非负数，为非负数，其中其中 是可行域的极方向。是可行域的极方向。n若线性规划若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某个极点上达到。存在有限最优解，则目标函数的最优值可在某个极点上达到。（最优极点最优极点）极点是个几何概念，直观性强，但不便于演算，因此需要研究极点的代数含义。第4页，本讲稿共18页基本可行解o 称为方程组的一个称为方程组的一个基本解基本解；oB称为称为基矩阵基矩阵，简称基；，简称基；oxB的各分量称为的各分量称为基变量基变量；o基变量的全体基变量的全体 称为一组基；称为一组基；oxN的各分量称为的各分量称为非基变量非基变量；o若若 ，则称基本可行解，则称基本可行解是非退化的基本可行解是非退化的基本可行解；o若若 且至少有一个分量是零，则称且至少有一个分量是零，则称 此此时的基本可行解是时的基本可行解是退化的基本可行解退化的基本可行解；同时，此；同时，此基本可行解对应的基被称为基本可行解对应的基被称为退化的可行基退化的可行基。o又若又若 ，则称，则称 为约束条件为约束条件 的的基本可行解基本可行解，称称B为为可行基矩阵可行基矩阵，为一组为一组可行基可行基；第5页，本讲稿共18页基本可行解的个数o若A是mXn矩阵，A的秩为m时，基本可行解的个数不会超过：第6页，本讲稿共18页定理与推理o线性规划的可行域是凸集。线性规划的可行域是凸集。o设线性规划设线性规划(2.1.2)的可行域非空，则有下列结论：的可行域非空，则有下列结论：n线性规划线性规划(2.1.2)存在有限最优解的充要条件是所有存在有限最优解的充要条件是所有 为非负数，为非负数，其中其中 是可行域的极方向。是可行域的极方向。n若线性规划若线性规划(2.1.2)存在有限最优解，则目标函数的最优值可在某个极点上达存在有限最优解，则目标函数的最优值可在某个极点上达到。（到。（最优极点最优极点）o线性规划的线性规划的可行域的极点集可行域的极点集与与基本可行解集基本可行解集等价等价；o当线性规划当线性规划(2.1.2)有可行解，则一定存在基本可行解。有可行解，则一定存在基本可行解。o当线性规划当线性规划(2.1.2)存在最优解时，则一定存在一个基本可行解是目标函数的存在最优解时，则一定存在一个基本可行解是目标函数的最优解。（最优解。（最优基本可行解最优基本可行解）第7页，本讲稿共18页第3章 单纯形方法o3.1单纯形方法原理o3.2两阶段法o3.3修正单纯形法第8页，本讲稿共18页单纯形方法的基本思想o就是，从一个基本可行解出发，求一个使目标函数值有所改变的基本可行解；通过不断改进基本可行解，力图达到最优基本可行解。o怎样实现基本可行解的转换？第9页，本讲稿共18页表格形式的单纯形法o显然，在单纯形表中包含了单纯形方法所需的全部数据。f xB xN 右端xB 0 Im B-1N B-1bf 1 0 cBB-1N-cN cBB-1b第10页，本讲稿共18页表格形式的单纯形法o显然，在单纯形表中包含了单纯形方法所需的全部数据。主元进基变量离基变量第11页，本讲稿共18页表格形式的单纯形法o解的几种情况在单纯形表上的体现(min型)：n唯一最优解：终表非基变量判别数均小于零；n多重最优解：终表非基变量判别数中有等于零的；n无界解：任意表有正判别数正判别数相应的系数列系数列均非正非正。omax型单纯形表与min型的区别仅在于：判别数反号，即，n令负判别数中最小的对应的变量进基；n当判别数均大于等于零时为最优。第12页，本讲稿共18页两阶段法o用单纯形法消去人工变量（如果可能），即把人工变量变为非基变量，求出原问题的一个基本可行解；n首先引入人工变量。令 ，即 n消去人工变量的一种方法是解如下第一阶段问题：o用单纯形法求解原问题。设得到的最优基本可行解是 ，此时必有下列三种情况之一：（1）（无可行解）（2）且 的分量都是非基变量 （得基本可行解 ）（3）且 的某些分量是基变量 （用主元消去法）第13页，本讲稿共18页大M法o其基本思想是：其基本思想是：在约束中增加人工变量 xa，同时修改目标函数，增加惩罚值惩罚值MeTxa，M是很大的正数，这样，在极小化目标函数的过程中，由于M的存在，将迫使人工变量离基。第14页，本讲稿共18页修正单纯形法o在运用单纯形法解决线性规划问题时，如果知道了可行基的可行基的逆逆，就能利用它和原始数据原始数据来计算基变量的取值及判别数，从而能够确定一个基本可行解，并判断它是否为最优解。因此，只要保存原始数据和现行基的逆即可。o修正单纯形法的基本思想是：给定初始基本可行解以后，修正单纯形法的基本思想是：给定初始基本可行解以后，通过修改通过修改旧基的逆旧基的逆来获得来获得新基的逆新基的逆，进而完成单纯形法的其，进而完成单纯形法的其它运算。在整个过程中它运算。在整个过程中保存现行基的逆保存现行基的逆。第15页，本讲稿共18页修正单纯形法的计算步骤1.给定初始可行基的逆给定初始可行基的逆 ，计算单纯形乘子，计算单纯形乘子w 和右端向量和右端向量 。构成下表：。构成下表：2.对于每个非基变量，计算判别数，令对于每个非基变量，计算判别数，令 。如果如果 则停止计算，现行基本可行解是则停止计算，现行基本可行解是最优解最优解；否则，下一步。；否则，下一步。3.计算主列计算主列 。若。若 ,则停止计算则停止计算,无有限最优解无有限最优解;否则下一步。否则下一步。4.把主列置于把主列置于逆矩阵表逆矩阵表的右边，组成下表：的右边，组成下表：按最小比值确定主行，令按最小比值确定主行，令 ，r 为主行，以为主行，以 为主元进行主元消去，为主元进行主元消去，然后去掉原来的主列，返回第然后去掉原来的主列，返回第2步。步。目标函数值单纯形乘子可行基的逆第16页，本讲稿共18页【例】用修正单纯形法解下列问题第17页，本讲稿共18页修正单纯形法的优势o只保存表中的数据和原始数据，而不需保存原来单纯形表中的全部数据，这样减少了在计算减少了在计算机中的存储量机中的存储量，特别是当当n比比m大得很多大得很多时显然有利。第18页，本讲稿共18页