[研究生入学考试]1线性规划.ppt

历年真题题型统计分析（03-09） 线性规划：12个 知识点：数学模型，解的概念和类型，单纯形方法，对偶 问题，对偶定理，对偶单纯型方法，影子价格，灵敏度分析 排队系统： 7个 知识点：稳态平衡方程，损失制系统，等待制系统的各种参数指标，状态转移图 图 论： 6个 知识点：生成树算法，最短路径问题，最大流最小截集算法 动态规划： 5个 知识点： 连续型动态规划，离散型动态规划，求和形和求积形 历年真题题型统计分析（03-08） 运输问题： 3个 知识点：模型特点，求解方法，位势法 存储问题： 2个 知识点：经济订购量，不允许缺货模型和允许缺货模型的求解，随机模型 匈牙利算法：1个 知识点：求解过程 决 策 论： 1个 知识点：小中取大，大中取小，Laplace，最小机会损失，折衷主义准则 1.1 线性规划问题及其一般数学模型 问题的提出 1、和式 关于标准型解的若干基本概念： 关于标准型解的若干基本概念： 线性规划标准型问题解的关系 线性规划问题的几个特点： 线性规划问题的可行解的集合是凸集 线性规划问题的基础可行解一般都对应于凸集的极点 凸集的极点的个数是有限的 最优解只可能在凸集的极点上，而不可能发生在凸集的内部 单纯型法的基本思路 单纯型表及其格式 例10 试列出下面线性规划问题的初始单纯型表 关于检验数的数学解释 设 B 是初始可行基，则目标函数可写为两部分(1) 约束条件也写为两部分，经整理得 XB 的表达式(2)，注意 XB中含有非基变量作参数 把 XB 代入目标函数，整理得到(3)式 第 j 个非基变量的机会成本如(4)式 若有cj?zj0, 则未达到最优 标准型的单纯型算法 求初始基本可行解； 最优检验：若所有检验数 ?j =cj? zj?0，j?J,则为最优解，停止。否则转3； 求另一个更好的基本可行解 1）确定入变量xk，若? k =Max{? j | ? j 0}，则xk为入变量； 2) 确定出变量xl* ，若?l =Min{?i =bi’/a’ ik | a’ ik 0}= bl’/a’ lk ，则bl’所在行的基变量为出变量，转3）。若?l 为空集，为无界解，停止。 3）初等变换，得另一更好的基本可行解。 将a’l k 变换为1， a’l k 所在列的其余元变换为0。更换基变量及其价值系数，得另一更好的基本可行解及其目标函数值。计算机会成本和检验数，转2。 表1 例10单纯型表的迭代过程 人工变量的引入及其解法 当约束条件为“?”型，引入剩余变量和人工变量 由于所添加的剩余变量的技术系数为?1，不能作为初始可行基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量 由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定 两种方法 大M法 二阶段法 大M法的求解过程 例11 表2 例11的单纯型表迭代过程 大M法的一些说明 大M法实质上与原单纯型法一样，M 可看成一个很大的常数 人工变量被迭代出去后一般就不会再成为基变量 当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解 大M法手算很不方便 因此提出了二阶段法 计算机中常用大M法 二阶段法手算可能容易 二阶段法的求解过程 第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基础可行解 第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解 若第一阶段结束时，人工变量仍在基变量中，则原问题无解 为了简化计算，在第一阶段重新定义价值系数如下 表3 用二阶段法求解例11的第一阶段 表4 用二阶段法求解例11的第二阶段 练习： 现有线性规划问题，试用大M法求解。 解 在上述问题的约束条件中加入松弛变量x4，剩余变量x5，人工变量x6,x7，得到 1.5 单纯型法的一些具体问题 关于无界解问题 可行区域不闭合(约束条件有问题) 单纯型表中入变量 xj* 对应的列中所有 表1.5.1 例1.5.1 的单纯型表及其迭代过程 1.5.2 关于退化问题 退化问题的原因很复杂，当原问题存在平衡约束时 当单纯型表中同时有多个基变量可选作出变量时 退化的严重性在于可能导致死循环，克服死循环的方法有“字典序”法 1.5.3 关于多