# 线性规划相关概念

• 求生产利润最大值
  • 设甲生产 $x_1$ 件，乙生产 $x_2$ 件
  • 决策变量：$x_1$，$x_2$
  • 目标函数： maxZ = 300x1 + 400x2
  • 约束条件：
    • $A$ 材料只有 $40$ $\to$ 2x1 + x2 <= 40
    • $B$ 材料只有 $30$ $\to$ x1 + 1.5x2 <= 30
    • 决策变量非负 $\to$ x1 >= 0, x2 >= 0

# 图解法

• 可行解：满足线性规划模型约束条件的解
• 最优解：使目标函数达到最大（小）值的可行解
  • 最优解有四种

# 线性规划的一般型

• 目标函数：$max(min)Z=\sum\limits_{j=1}^{n}c_jx_j$
• $c_j$ 称为价值系数
• 约束条件：

$$\begin{cases} \sum\limits_{j=1}^na_{ij}x_j\le(或=,\ge)b_i,~i=1,2,...,m\\ x_j\ge0, j=1,2,...,n\\ \end{cases}$$

• $a_{ij}$ 称为工艺系数
• $b_i$ 称为资源限量

# 线性规划矩阵形式的标准型

$$maxZ=CX, \begin{cases} AX=b\\ x\ge0 \end{cases}$$

• $A$ 是系数矩阵：$m×n$ 矩阵，且 $m\le n, r(A)=m$
• 基矩阵：$A$ 的 $m×m$ 阶子矩阵 $B$ 满足 $r(B)=m$，则 $B$ 为线性规划的一个基矩阵（或基）
• 基向量：基矩阵对应的列向量为基向量
• 非基向量：其余列向量为非基向量
• 基变量：基向量对应的变量为基变量
• 基本解：对某一确定的基 $B$，在约束条件 AX = b 中，令非基变量等于零，求解出基变量，称这组解为线性规划问题的基本解
• 基本可行解：若基本解满足 $x\ge0$ 的非负约束，称为基本可行解

# 线性规划模型的标准型

• 目标函数为求最大值
• 约束条件均为等式方程
• 变量 $x_j$ 为非负
• 常数 $b_i$ 都大于等于 $0$
• 能找出一个单位矩阵的部分，若找不到则需添加人工变量