运筹学计算题摘要.doc

运筹学 线性规划（Linear Programming，简称LP），运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。 1947年G.B. Dantying提出了一般线性规划问题求解的方法——单纯形法之后，线性规划的理论与应用都得到了极大的发展。 60年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。 LP问题的标准形式（会将一般形式化为标准形式），目标函数min,max2类 线性规划问题的一般形式： max（min）z = c1x1 + c2x2 + … + cnxn s.t. a11x1 + a12x2 + … + a1nxn ≤（或=，≥）b1 a21x1 + a22x2 + … + a2nxn ≤（或=，≥）b2 … … am1x1 + am2x2 + … + amnxn ≤（或=，≥）bm xj ≥ 0 （j = 1,2,…,n） 其中aij、bi、cj（i = 1,2,…,m；j = 1,2,…,n）为已知常数 线性规划问题的标准形式： max z = c1x1 + c2x2 + … + cnxn s.t. a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 … … am1x1 + am2x2 + … + amnxn = bm xj ≥ 0 （j = 1,2,…,n） bi ≥ 0 （i = 1,2,…,m） 如何转化为标准形式？ 1、目标函数为求极小值，即为： 因为求 min z 等价于求 max (-z)，令 z’ = - z，即化为： 2、约束条件为不等式， xn+1 ≥ 0松弛变量 如何处理？ ３、右端项bi 0时，只需将等式两端同乘（-1）则右端项必大于零 4、决策变量无非负约束 设 xj 没有非负约束，若 xj ≤0，可令 xj = - xj’ ，则 xj’ ≥0； 又若 xj 为自由变量，即 xj 可为任意实数，可令 xj = xj’ - xj’’，且 xj’ , xj’’ ≥0 e.g. 3 试将 LP 问题 min z = -x1+2x2-3x3 s.t. x1+x2+x3 ≤7 x1-x2+x3 ≥2 -3x1+x2+2x3 = -5 x1,x2 ≥0 化为标准形式。 解：令 x3= x4 - x5 其中x4、x5 ≥0； 对第一个约束条件加上松弛变量 x6 ； 对第二个约束条件减去松弛变量 x7 ； 对第三个约束条件两边乘以“-1” ； 令 z’=-z 把求 min z 改为求 max z’ LP的几种表示形式： (2) 线性规划问题的图解法 定义1 在LP 问题中，凡满足约束条件(2)、(3)的 解 x = (x1,x2,…,xn)T 称为LP 问题的可行解， 所有可行解的集合称为可行解集（或可行域）。 记作 D={ x | Ax = b ,x≥0 }。 定义2 设LP问题的可行域为D，若存在x*∈D，使得 对任意的x∈D 都有c x*≥c x，则称x*为LP 问题 的最优解，相应的目标函数值称为最优值， 记作 z*=c x*。 LP问题图解法的基本步骤： 1、在平面上建立直角坐标系； 2、图示约束条件，确定可行域和顶点坐标； 3、图示目标函数（等值线）和移动方向； 4、寻找最优解。 可行域为无界区域一定无最优解吗？ Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。 重要结论： 1、LP 问题从解的角度可分为： ⑴ 有可行解 a.有唯一最优解b.