线性规划（LP）

线性规划（LP） 思维导图，线性规划是运筹学的一个重要分支，研究较早，理论较完善，应用最广泛的一个学科

线性规划（LP）

• 线性规划
  • 概念
    • 运筹学的一个重要分支，研究较早，理论较完善，应用最广泛的一个学科
  • 线性规划类型
    • MAX型
      • 资源一定，完成任务最多
    • MIN型
      • 任务一定，资源用最少
• 线性规划方法运用和典型情况
  • 运输问题
  • 整数规划
  • 指派问题
  • 动态规划
• 线性规划解法
  • 图解法
    • 图解方法步骤
      • 1.建立平面直角坐标系
      • 2.确定可行域
      • 3.画目标函数等值线
      • 4.找出最优点，确定最优解
    • 解的情况
      • 有唯一最优解
      • 无穷多解
      • 无界解
      • 无可行解
    • 图解法的启示
      • 若线性规划问题的可行域存在，则可行域是个凸集
      • 若线性规划问题的最优解存在，则最优解或最优解之一一定是可行域的凸集的某个顶点
      • 可行解构成的凸多边形的顶点个数是有限的
  • 线性规划单纯型法
    • 单纯形法的原理
      • 凸集及其顶点
        • 凸集概念
        • 顶点条件
      • 解的概念
        • 可行解
        • 最优解
        • 基
        • 基解
        • 基可行解
        • 可行解
      • 单纯形法计算步骤
        • 找出处初始可行解
        • 最优性检验
          • 无穷多最优解判定定理
          • 无界解判定定理
          • 最优解判定定理
        • 基变换
        • 迭代
        • 重复以上步骤
      • 单纯形法·的·进一步讨论
        • 有人工变量的线性规划问题
          • 人工变量法（大M法）
          • 解的退化问题
• 线性规划的数学模型
  • 数学模型三要素
    • 决策变量
    • 目标函数
    • 约束条件
  • 线性规划模型标准化
    • 1.目标函数求max
    • 2.所有约束条件均用=
    • 3.所有决策变量为负
    • 4.约束条件右侧常熟为非负
  • 标准化方法
    • (1）目标函数为最小化时，令z'=-z，则max Z'=-m min z=-CX，转化为最大化问题。
    • (2）约束方程右侧常数为负数时，方程两边同乘﹣1
    • (3）约束方程为不等式时，若为"≤"不等式，则在"≤"不等式左端加入一非负变量（称为松弛变量）化为等式；若为"≥"不等式，则在"三"不等式左端减去一非负变量（称为剩余变量）化为等式。松弛变量和余变量在目标函数中的系数为0。 标准化方法
    • (4）对于无约束决策变量x，可用两个非负变量代替 即令x=x'-x"，其中x20,x"20。