线性规划与单纯形法

线性规划问题及其数学模型：在生产管理和经营活动中经常提出一类问题, 即如何合理地利用有限的人力、物力、财力等资源, 以便得到最好的经济效果。
问题特征
(1) 每一个问题都用一组决策变量 $( x_1 , x_2 , ⋯ , x_n )$ 表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的。
(2) 存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。
(3) 都有一个要求达到的目标, 它可用决策变量的线性函数(称为目标函数) 来表示。按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为线性规划的数学模型。Matlab中的标准型为：
目标函数 $\quad min(z)=\sum_{i=1}^n c_ix_i$
约束条件 $\quad \sum_{i=1}^n a_{ji}x_i\leqslant b_j\quad j=1,2,...,m$
$\quad\quad\quad\quad~ \sum u_ix_i=v$
$\quad\quad\quad\quad\quad\quad\quad x_i\geqslant0$

matlab:linprog([c],[a],[b],[u],v,options(zeros(m,1)))

图解法

1. 无穷多最优解
2.无界解
3.无可行解

当求解结果出现第2、3 两种情况时，一般说明线性规划问题的数学模型有错误。前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意。
图解法虽然直观、简便, 但当变量数多于三个以上时, 它就无能为力了。所以要介绍一种代数法——单纯形法。为了便于讨论, 先规定线性规划问题的数学模型的标准型式。
（ $\color{red}{不同于 Matlab 的标准型}$ ）

标准型	矩阵形式
$max(z)=\sum_{j=1}^n c_jx_j$ $\sum_{j=1}^n a_{ij}x_j= b_i\quad i=1,2,...,m$ $x_j\geqslant0$	$max(z)=CX$ $AX=\sum_{j=1}^n P_{j}x_j= b$ $X\geqslant0$

在标准形式中规定各约束条件的右端项 $b_i>0$ ，否则等式两端乘以 $"-1"$ 。
其中 $C=(c_1,c_2,...,c_n)$
$X=\left[\begin{array}{c}{x_{1}} \\ {x_{2}} \\ {\vdots} \\ {x_{n}}\end{array}\right]$ ； $P_{j}=\left[\begin{array}{c}{a_{1j}} \\ {a_{2j}} \\ {\vdots} \\ {a_{mj}}\end{array}\right]$ ； $b=\left[\begin{array}{c}{b_{1}} \\ {b_{2}} \\ {\vdots} \\ {b_{m}}\end{array}\right]$ ； $0=\left[\begin{array}{c}{0} \\ {0} \\ {\vdots} \\ {0}\end{array}\right]$
$A=\left[\begin{array}{cccc}{a_{11}} & {a_{12}} & {\cdots} & {a_{n}} \\ {\vdots} & {\vdots} & {} & {\vdots} \\ {a_{m 1}} & {a_{m 2}} & {\cdots} & {a_{m n}}\end{array}\right]=\left(P_{1}, P_{2}, \cdots, P_{n}\right)$
A —— 约束条件的 $m\times n$ 维系数矩阵，一般 $m<n$ ；
b —— 资源向量；
C —— 价值向量；
X —— 决策变量向量。
实际碰到各种线性规划问题的数学模型都应变换为标准型式后求解。
以下讨论如何变换为标准型的问题。
(1 ) 若要求目标函数实现最小化，即 $min~z = CX$ 。这时只需将目标函数最小化变换求目标函数最大化，即令 $z′= - z$ ，于是得到 $max~z′= - CX$ 。这就同标准型的目标函数的形式一致了。
(2 ) 约束方程为不等式。这里有两种情况: 一种是约束方程为 $“\leqslant”$ 不等式，则可在 $“\leqslant”$ 不等式的左端加入非负松弛变量；把原 $“\leqslant”$ 不等式变为等式；另一种是约束方程为 $“\geqslant”$ 不等式，则可在 $“\geqslant”$ 不等式的左端减去一个非负剩余变量( 也可称松弛变量) ，把不等式约束条件变为等式约束条件。

线性规划与单纯形法

图解法

推荐阅读更多精彩内容