线性规划

线性规划知识总结，要想在生产、交通运输、商业贸易等领域提高经济效益，有两种途径：一是进行技术创新；二是提高管理水平，改进生产组织与计划，最合理地安排各类生产要素。

线性规划

• 线性规划概述
  • 线性规划问题的引入
    • 要想在生产、交通运输、商业贸易等领域提高经济效益，有两种途径：一是进行技术创新；二是提高管理水平，改进生产组织与计划，最合理地安排各类生产要素。
  • 线性规划模型
    • 简称为LP模型
      • 三要素
        • 决策变量
          • 决策变量的一组定值代表所给问题的一个具体的解决方案
        • 约束条件
          • 为线性等式或线性不等式
        • 目标函数
          • 是决策变量的线性函数
      • 一般形式
  • 线性规划模型的标准型
    • • 特点
        • 目标函数是最大化类型
        • 约束条件均由等式组成
        • 决策变量均为非负
  • 线性规划的图解法
    • 步骤
      • 在平面上建立直角坐标系
      • 根据约束条件画出相应半平面，由这些半平面共同确定的区域即为可行域
      • 画出目标函数的等值线，然后沿目标函数要求的方向平移至与可行域边界相切的点，该点就是最优解，相应的坐标即为最优解
    • 解的结果
      • 唯一解
      • 多重解
      • 无界解
      • 无解
    • 重要结论
      • 线性规划的可行域是若干个半平面的交集，它形成了一个多面凸集（可能是空集）
      • 对于给定的线性规划问题，如果它有最优解，最优解总是可以在可行域的某个顶点上达到。这种情况下包含两种解的情况：唯一解和无穷多解
      • 如果可行域无界，线性规划问题的目标函数可能无界
      • 可行域为空集，无最优解
• 单纯形法
  • 线性规划的概念
    • 标准型
    • 解：
    • 可行解：
    • 可行域：全体可行解的集合称为线性规划的可行域，一般记作 D＝｛X｜AX＝b,X≥0｝
    • 最优解：
    • 最优值：最优解的目标函数值称为线性规划的最优值
    • 基：若A中m×m子矩阵B满足r（B）＝m,则称B是线性规划问题的一个基
    • 基变量、非基变量：
    • 基本解：
    • 基本可行解：若基本解Xв＝B-¹b≥0，则称该解为基本可行解，B为可行基
  • 单纯形法的理论基础
    • 基本概念
    • 基本定理
      • 若线性规划问题存在可行域，则可行域是凸集
      • 线性规划可行域D中的点X为顶点的充要条件是X为基本可行解
      • 若线性规划有最优解，则最优解一定可以在可行域的顶点上得到
  • 单纯形表
    • Cj行
      • 所有变量在原目标函数中的系数
    • Cb列
      • 当前基变量在原目标函数中的系数
    • Xb列
      • 当前基变量
    • b列
      • 当前基变量的取值
    • δ检验数
      • 终表检验数为负数
    • θ
      • 确定换入变量后，某一列Xi的bi值/aij
  • 单纯形法的计算步骤
    • • 向线性约束中添加松弛变量
      • 以原点为初始基可行解
      • 看非基变量表示的目标函数中各个非基变量的系数是否为正
      • 确定换入变量
      • 确定换出变量
      • 使用高斯消元法解方程，确定新的可行解
    • 求解定理
      • 最优解判定定理
      • 无界解判定定理
      • 换基迭代定理
  • 单纯形法的进一步讨论
    • 大M法
    • 两阶段法
• 线性整数规划
  • 线性整数规划模型及其分类
    • 0-1整数规划问题（也称0-1规划）
    • 混合整数规划问题
  • 线性整数规划求解
    • 分支定界法
    • 割平面法
      • 基本思想
        • 首先不考虑变量为整数这一约束条件，但增加线性约束条件（几何术语称为割平面）使得原可行解域中切割掉一部分，这部分只包含非整数解，但没有切割掉整数可行解。采用割平面法的关键是如何找到割平面约束方程，使切割后最终得到这样的可行解域，它的一个有整数坐标的极点恰好就是问题的最优解。
      • 解题步骤
        • （1）去掉整数约束，用单纯形求解。若最优解是整数，停止计算，否则转下一步。
        • （2）寻求附加约束（割平面方程）
          • 从单纯形表最优表中找出非整数解的某一个约束方程
          • 将该约束方程的所有系数和常熟分解为整数和非负真分数之和
          • 整数项（包括整系数项和整常数项）归写于方程左边，真分数项写于右边
          • 利用整数约束条件求出割平面方程
        • （3）将割平面方程规范后加到约束方程组中求解，如所求得的最优解仍为非整数，则转到第（2）步继续进行，直到找到最优整数解为止。
• 对偶问题和灵敏度分析
  • 线性规划的对偶问题
    • 简述
      • 线性规划的原型是生产计划问题
      • 对偶问题的原型是资源定价问题
    • 对偶问题与原问题的对应关系
      • 两个关系的系数矩阵互为转置
      • 一个问题的变量个数等于另一个问题的约束条件个数
      • 一个问题的右端系数是另一个问题的目标函数的系数
      • 一个问题的目标函数为最大化，约束条件为“≤”类型；另一个问题的目标函数为最小化，约束条件为“≥”
    • 线性规划的对偶理论
      • 对偶性：线性规划对偶问题的对偶问题就是原问题
      • 弱对偶定理
      • 强对偶定理：若线性规划问题（2-20）和（2-21）之一有最优解，则另一问题也有最优解，并且两者的目标函数值相等
      • 松弛互补定理
    • 对偶问题的经济解释（影子价格)
      • 线性规划问题求最优解就是在有限资源条件下谋求最高利益，此时相对应的对偶问题中的变量就是影子价格
      • 影子价格完全由企业内部的生产条件（不是由市场）所决定，使企业内部决策的一种参照价格
  • 对偶单纯形法
    • 求解思想
      • 在保证检验数行全部非正的条件下，逐步使得基解“左边”一列各数变成非负，一旦“左边”一列各数均满足了非负条件（即可行性条件），则就获得最优解
    • 计算步骤
      • • （1）找出一个初始基B。，要求对应的单纯形表中的全部检验数δ≤0，但“左边”列中允许有负数，即确定出对偶可行解。
        • （2）若“左边”列中各数均非负，则B。已是最优基，于是求得最优解，计算终止;否则转为第(3)步。
        • （3）若某个基变量取负值，但其所在的行中元素全部是正数，这时问题无可行解:否则转为第(4)步。
        • (4)换基迭代:“左边”列中取值最小(即负得最多)的数所对应的变量为出基变量。为决定进基变量，必须按最小比值原则计算最小比值θ，最小比值出现在哪一列， 则该列所对应的变量即为进基变量，换基后得新基B，以出基变量的行和进基变量列交点处的元素为主元进行单纯形迭代，再转入第(2)步。
  • 灵敏度分析
    • 价值向量的灵敏度分析
      • Cj是非基变量Xj的系数
        • • 非基变量只要满足这个不等式，就不影响最优解的系数
      • Ck是基变量Xk的系数
        • • 该等式结果不会影响最优解，会影响最优值和所有非基变量检验数
    • 资源向量的灵敏度分析
      • b的变化会影响解的最优性
    • 追加一个新的决策变量
      • 新增变量的检验数≤0，则原问题的最优解就是新问题的最优解，否则，继续迭代
    • 技术矩阵A的灵敏度分析
      • 非基变量Xj的系数变化
        • • 影响检验数，最优解与最优值均不变
      • 基变量Xj的系数变化
        • 既影响基本可行解，又影响非基变量的检验数