线性规划基础

运筹学第一章知识总结，概述了线性规划的标准形式及其求解过程，包括如何将非线性问题转化为线性规划问题，并详细解释了线性规划中的关键概念和步骤。

线性规划基础

• 线性规划标准型
  • 标准型特征
    • 1.目标值取Max
    • 2.约束条件用=
    • 3.变量取非负：Xi≥0
    • 4.约定bi≥0
  • 一般式转换为标准型
    • 变量
      • 对于自由变量Xk（无正负约束）： 令Xk=Xk'-Xk''(其中Xk'、Xk''满足非负约束)
    • 目标函数
      • 原：minZ=CX 改：maxZ'=-CX
    • 约束条件
      • 对于不等式约束： ≤，增加松弛变量X(i+1); ≥，减去剩余变量X(i+2); [松弛变量与剩余变量均满足非负约束]
• 解的概念
  • 可行解
    • 满足所有约束条件的解
  • 最优解
    • 满足目标函数的可行解
  • 基
    • A为约束方程组的系数矩阵，其秩为m； B由A中m个线性无关的系数列向量组成，且秩为m（B为可逆矩阵，且|B|≠0）
  • 基本解
    • 令非基变量全部为0，利用高斯消元法得到的解（其中非零分量不大于m）
  • 基本可行解
    • 满足非负约束的基本解
  • 退化基本解
    • 非零分量小于m的基本解
• 图解法（仅两个变量）
  • 1.根据非负约束确定象限； 2.画出约束条件表示的范围； 3.将目标函数中的Z看成参数，以任意变量为因变量，另一个为自变量画出目标函数的直线形式； 4.所有平行于目标函数的图线，且满足约束范围的点集即为可行解
  • 唯一最优解：最优情况为约束范围的某个顶点 无穷多组最优解：当最优情况的目标函数图线与约束范围边界重合 无界解（无最优解）：可行域无界