线性规划标准型以及定义.ppt

* * * * * * * * * * * 定理2:线性规划可行解的集合R={x|Ax =b,x≥0}是凸集.点x0是R的极点充分必要条件是x0是线性规划的基可行解. 二.解释及相关性质 再证x0是R的极点.假设不是,由定义, 解释及相关性质 解释及相关性质 解释及相关性质 解释及相关性质 再证必要性. 反证. （即构造两个可行解x1，x2使得x0是这两个点的组合） 设x0是极点,但不是基可行解.不失一般性,设前s个分量大于0,后面n-s个分量为0. 定理3的第二个结论可知A的前s个列向量线性相关.于是存在一组不全为0的数满足 解释及相关性质 解释及相关性质 解释及相关性质 解释及相关性质 说明:从证明的过程来看,对于任意一个可行解,如果不是基解，可以通过所给的方法，可以得到一可行解，其中0分量的个数至少增加一个。反复进行，一定会得到一基可行解。 解释及相关性质 解释及相关性质 解释及相关性质 线性规划基本定理: 1.若线性规划有可行解,则一定有基可行解. 可行解x x是基解 x不是基解,则逐渐增加0分量个数,变成 基可行解. 解释及相关性质 2.若线性规划有最优解,则一定可以在基可行解上达到. （换句话说，若有最优解，必有基础最优解） 证明：设x为最优解。若x是极点，得证。 若不是极点，由定理3中所证，可以表示为一些点的线性组合，其中一个为极点，不妨设为 解释及相关性质 注：l是有限的。（思考：为什么？） 因为：变量的个数n是有限的。而定理3的方法操作一次，多出一个0分量，同时多出一个解。这样，最多有p+1步（此时基解等于0）。即l≤p+1。 解释及相关性质 带入目标函数，得 又x0最优解，所以所有解目标函数值相等。也即，xl为最优解，且为极点。 * * * * * * * * * * * * * * * * * 第一节 线性规划的标准型 目标函数： 约束条件： 松弛变量，剩余变量 线性规划问题的标准形式 特点： (1) 目标函数求最小值（有时求最大值） (2) 约束条件都为等式方程，且右端常数项bi都大于或等于零 (3) 决策变量xj为非负。 （2）如何化标准形式 目标函数的转换 如果是求极大值即 ，则可将目标函数乘以(-1)，可化为求极小值问题。 也就是：令 ，可得到上式。 即 若存在取值无约束的变量 ，可令 其中： 变量的变换 约束方程的转换：由不等式转换为等式。 称为松弛变量 称为剩余变量 变量 的变换 可令 ，显然 例1 将下列线性规划问题化为标准形式 用 替换 ，且 解:（１）因为x3无符号要求 ，即x3取正值也可取负值，标准型中要求变量非负，所以 (2) 第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0,化为等式； (3) 第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5，x5≥0； (4) 第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数； (5) 目标函数不变 标准形式如下： 一、图解法 第二节 解的性质 max Z = 2X1 + X2 X1 + 1.9X2 ≥ 3.8 X1 - 1.9X2 ≤ 3.8 s.t. X1 + 1.9X2 ≤10.2 X1 - 1.9X2 ≥ -3.8 X1 ，X2 ≥ 0 例2 用图解法求解线性规划问题 图解法 x1 x2 o X1 - 1.9X2 = 3.8(≤) X1 + 1.9X2 = 3.8(≥) X1 - 1.9X2 = -3.8 (≥) X1 + 1.9X2 = 10.2(≤) 4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2） D max Z min Z 此点是唯一最优解， 且最优目标函数值 max Z=17.2 可行域 max Z = 2X1 + X2 图解法 max Z=3X1+5.7X2 x1 x2 o X1 - 1.9X2 = 3.8 (≤) X1 + 1.9X2 = 3.8(≥) X1 - 1.9X2 = -3.8(≥) X1 + 1.9X2 = 10.2 (≤) （7.6，2） D L0： 0=3X1+5.7X2 max Z （3.8，4） 34.2 = 3X1+5.7X2