最优控制课件线性规划.pptVIP

三、当约束条件中含有“≥” 形式时 这里通过一个例题来说明：当约束条件既有“≤”形式，又有“≥” 形式时，引入的剩余变量不能直接拿来作为初始基本变量，同样由所有的松弛变量和非辅助变量组成初始基本变量。 例3-11 (※)求解线性规划问题 解：化为标准线性规划 表3-7 原始表 表3-8 初始表 表3-9 中间数据 表3-10 最终结果 最优解： 最优值： 补充题(※) ：利用单纯形表格法求解下列线性规划问题 自由变量 要求至少要有线性规划的标准形式和最终表格。 3.4.3 两阶段法 当线性规划问题的所有约束条件均具有“≤”形式时，将该问题化为标准线性规划时引入的所有松弛变量可以作为初始基本变量，这样极易得到初始基本可行解。但当约束条件中出现“=”和“≥”形式时，初始基本可行解不能直观得到，这时可像3.4.2节中例3-10，3-11那样处理，也可用两阶段法处理。 两阶段法将线性规划的求解分为两步完成： （1）准备阶段：将原线性规划问题化为标准型后，再引入所谓的暂用变量y，构造一个寻找原问题初始可行解的线性规划问题，其目标函数为所有引入变量之和相反数的极大值，在求解该问题的基础上判断原线性规划问题无解，或者得到一个初始基本可行解，为原问题准备初始表格； （2）计算阶段：在得到的一个初始基本可行解的基础上，用单纯形（表格）法求最优解。 3.5 线性规划的对偶问题(※) 一、线性规划的对偶问题定义 在线性规划问题中，约束条件的数目直接影响着基底的维数，在每次迭代过程中，基底的维数越高则行初等变换等计算量越大。因此，约束条件数目比变量数目更能影响求解时间。在不等式约束中，有时会遇到约束条件数目比变量数目多的情况，为了更好地解决这类具有较多约束条件的线性规划问题，加快计算速度，必须设法减少约束条件数目。 例如在解题过程中，可将约束条件数目与变量数目对调，根据原问题构造出有较少约束数目的新问题，在解新问题的过程中得到原问题的最优解，这就是线性规划的对偶问题。 “对偶”是线性规划中最重要的概念之一，对于每一线性规划问题（称为原始问题）都有另一个线性规划问题（称为对偶问题）与之对应，原始问题与对偶问题之间有密切的联系，它们是从不同的角度来描述实质上相同的问题。 对偶问题的定义 原始问题 对偶问题 由原问题给出对偶问题的原则（※） （1）目标函数的对偶关系是“极大”对“极小”；变量x用w替换；向量b和c对调位置； （3-23） （2）约束条件“≤”对“≥”；系数矩阵“A”变为“AT ”； （3）对偶前后变量都是非负的； （4）原问题各约束条件的形式不统一时，必须统一为“≤”或“≥” （此时不必考虑右侧向量中的元素是否为正），约束形式统一后再确定对偶问题形式； （5）如果原问题有等式约束，需将该条件用等价的两个不等式约束条件替换，即f (x)=k 可以改写成两个不等式约束条件 f (x)≤k ， -f (x) ≤ -k 。 注：原问题对偶的对偶仍是原问题. 这种性质称为对偶关系的“对合”性质.一对相互对偶的线性规划问题,其中任一个都可以称作原问题,而另一个称为它的对偶问题. 例3-14 (※) ：给出以下线性规划问题的对偶问题 解：该题约束条件形式不统一，需统一后再求对偶问题. 统一约束条件形式 原问题的对偶问题： 化为标准型 二、线性规划对偶问题的性质 1. 定理3-4：在式（3-23）定义的对偶问题中，若x和w分别是原问题和对偶问题的任意可行解，则一定有 注： 若其中一个问题的解是无穷大(无穷小)，则对偶问题无可行解；若其中一个问题无可行解，则对偶问题无可行解或解是无穷大(或无穷小)的. 2. 定理3-5：在式（3-23）定义的对偶问题中，若x*和w*分别是原问题和对偶问题的可行解，且 ，则x*和w*分别是原问题和对偶问题的最优解。 3. 定理3-6：在式（3-23）定义的对偶问题中，若x*是原问题的最优解，则对偶问题也必有最优解w* ，且最优值相等，即 。 注：定理3-6说明(※) 1）如果已得到式（3-23）中原问题的最优解x*，则可得到对偶问题的最优解 ，其中B是原问题中对应于最优解x*的基底，cB是相应的加权系数向量。由于对偶关系具有对合性，反之也成立。 2）原问题的最后单纯形表中辅助变量所在列下的最后元素，即判别数就是对偶问题相应变量的最优解。由于对偶关系具有对合性质，所以从对偶问题的最终