第二次课

null第一章 线性规划问题及单纯型解法第一章 线性规划问题及单纯型解法 1.1.3 线性规划问题的形式（重点） 1.1.4 标准型解的若干基本概念（难点） 1.2 图解法 1.3 单纯型解法（难点重点）null*1.1.3 线性规划问题的标准形式（重点） 为了使线性规划问题的解法标准，就要把一般形式化为标准形式 变换的方法：* 变换的方法：1 目标函数为min型，价值系数一律反号。令 f(x) = -f(x) = -CX, 有 min f(x) = max [- f(x)] = max f (x) 2 第i 个约束的bi 为负值，则该行左右两端系数同时反号，同时不等号也要反向 3 第i 个约束为  型，在不等式左边增加一个非负的变量xn+i ，称为松弛变量；同时令 cn+i = 0 4 第i 个约束为  型，在不等式左边减去一个非负的变量xn+i ，称为剩余变量；同时令 cn+i = 0 5 若xj 0，令 xj= -xj ，代入非标准型，则有xj  0 6 若xj 不限，令 xj= xj - xj， xj  0，xj  0，代入非标准型 例3 1.1.4标准型解的若干基本概念（难点）： 1.1.4标准型解的若干基本概念（难点）：基: 在约束方程中线性无关的 m 列，构成该标准型的一个基，即 B = ( P1 , P2  , … , Pm )， | B |  0 P1 , P2  , … , Pm 称为基向量 与基向量对应的变量称为基变量记为XB = ( x1 , x2  , … , xm  )T，其余的变量称为非基变量，记为 XN = ( xm+1 , xm+2 , … , xm+N  ) T ， 最多有 个基 2 基本解 令非基变量 XN = 0，求得基变量 XB的值称为基本解（又称基解）， 即 XB = B1 b null3 可行解与非可行解 满足约束条件和非负条件的解 X 称为可行解，满足约束条件但不满足非负条件的解 X 称为非可行解 全部可行解的集合称为可行域。 4 基本可行解 基本解 XB 的非零分量都  0 时，称为基本可行解，否则为基本非可行解 基本可行解的非零分量个数 < m 时，称为退化解。 最优解 使目标函数达到极值的基本可行解称为最优解。 线性规划标准型问题解的关系* 线性规划标准型问题解的关系约束方程的 解空间基本解可行解非可行解基本 可行解退化解例11.2 图解法1.2 图解法例2 注意：图解法适用于只有两个决策变量的情况 解的几种情况 唯一最优解 无穷多最优解 无可行解 无界解 1.3.1 单纯型法的基本思路 1.3.1 单纯型法的基本思路1.3 单纯型解法1.3.2标准型的单纯型算法1.3.2标准型的单纯型算法求初始基本可行解； 最优检验：若所有检验数 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。例31.3.3注意事项1.3.3注意事项1线性规划化成标准形后才能列单纯形表求解。 2 cj zj 出现两个以上最大值，则任选一个得到进基变量，原则上选前一个。 3 值出现两个以上最小值则任选一个得到出基变量，原则上选非决策变量为出变量。 4所有cj zj0的且非基变量xj的cj zj=0则说明该问题有无穷多最优解。 5存在cj zj >0，但a’ ik 0 则无界解。 1.4 单纯形法原理 关于检验数的数学解释1.4 单纯形法原理 关于检验数的数学解释设 B 是初始可行基，则目标函数可写为两部分(1) 约束条件也写为两部分，经整理得 XB 的表达式(2)，注意 XB中含有非基变量作参数 把 XB 代入目标函数，整理得到(3)式 第 j 个非基变量的机会成本如(4)式 若有cjzj>0, 则未达到最优