线性规划
线性规划的实例与定义
例：某机床厂生产甲、乙两种机床，每台销售后的利润分别为 4000 元与 3000 元。 生产甲机床需用 A、 B机器加工，加工时间分别为每台 2 小时和 1 小时；生产乙机床 需用A 、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时 数分别为 A机器 10 小时、B 机器 8 小时和C 机器 7 小时。问该厂应生产甲、乙机床各几台，才能使总利润最大？
上述问题的数学模型：设该工厂生产x 1 x_{1}x1台甲机床和x 2 x_{2}x2乙机床时总利润z zz最大，则x 1 x_{1}x1，x 2 x_{2}x2应满足
max z = 4 x 1 + 3 x 2 ( 1.1 ) \max z=4x_{1}+3x_{2}\qquad\left(1.1\right)maxz=4x1+3x2(1.1)
s . t . { 2 x 1 + x 2 ≤ 10 ， x 1 + x 2 ≤ 8 ， ( 1.2 ) x 2 ≤ 7 ， x 1 , x 2 ≥ 0 。 s.t.\begin{cases}2x_{1}+x_{2}\leq 10，\\ x_{1}+x_{2}\leq 8，\qquad\left(1.2\right)\\ x_{2}\leq 7，\\ x_{1},x_{2}\geq 0。\end{cases}s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧2x1+x2≤10，x1+x2≤8，(1.2)x2≤7，x1,x2≥0。
式（1.1）为问题的目标函数，式（1.2）中的几个不等式为问题的约束条件，记为s.t.(subject to)。由于目标函数及约束条件为线性函数，故称为线性规划问题。
线性规划的Matlab标准形式
因为线性规划的目标函数可以求最大值或者最小值，约束条件可以是大于等于或者小于等于，为了避免形式多样性带来的不便，Matlab中规定线性规划的标准形式为
min x f T x ， \min_{x} f^{T}x，minxfTx，
s . t . { A ⋅ x ≤ b ， A e q ⋅ x = b e q ， l b ≤ x ≤ u b 。 s.t.\begin{cases}A\cdot x\leq b，\\ Aeq\cdot x=beq，\\ lb\leq x\leq ub。\end{cases}s.t.⎩⎪⎨⎪⎧A⋅x≤b，Aeq⋅x=beq，lb≤x≤ub。
式中：f , x , b , b e q , l b , u b f,x,b,beq,lb,ubf,x,b,beq,lb,ub为列向量，其中f ff称为价值向量；b bb称为资源向量；A , A e q A,AeqA,Aeq为矩阵。（其实Matlab中f ff是否是列向量对结果无影响，其余的为列向量的原因是矩阵相乘时是前行后列相乘，下面详细说）
Matlab中求解线性规划的命令为
[x,fval]=linprog(f , A , b f,A,bf,A,b)
[x,fval]=linprog(f , A , b , A e q , b e q f,A,b,Aeq,beqf,A,b,Aeq,beq)
[x,fval]=linprog(f , A , b , A e q , b e q , l b , u b f,A,b,Aeq,beq,lb,ubf,A,b,Aeq,beq,lb,ub)
式中：x返回最优解；fval返回目标函数的最优值；A和b对应线性不等式约束；Aeq和beq对应线性等式约束；lb和ub分别对应下界向量和上界向量。（若题目中没有等式约束，将Aeq,beq以[ ]空矩阵代替 即：[x,fval]=linprog(f , A , b , [ ] , [ ] , l b , u b f,A,b,[ ],[ ],lb,ubf,A,b,[],[],lb,ub)）
例如，线性规划
max x c T x ， \qquad\qquad\qquad\max_{x} c^{T}x，maxxcTx，
s . t . A x ≥ b 。 \qquad\qquad\qquad s.t.\quad Ax\geq b。s.t.Ax≥b。
的Matlab标准型为
min x − c T x ， \qquad\qquad\qquad\min_{x} -c^{T}x，minx−cTx，
s . t . − A x ≤ − b 。 \qquad\qquad\qquad s.t.\quad -Ax\leq -b。s.t.−Ax≤−b。 (最大值的负值即为最小值，不等式变号)
例：求解下列线性规划问题
max z = 2 x 1 + 3 x 2 − 5 x 3 ， ( f 即 该 式 的 系 数 向 量 ) \max z = 2x_{1}+3x_{2}-5x_{3}，(f即该式的系数向量)maxz=2x1+3x2−5x3，(f即该式的系数向量)
s . t . { x 1 + x 2 + x 3 = 7 ， （ A e q 、 b e q 即 该 式 的 等 式 约 束 条 件 ) 2 x 1 − 5 x 2 + x 3 ≥ 10 ， x 1 + 3 x 2 + x 3 ≤ 12 ， x 1 ， x 2 ， x 3 ≥ 0 。 （ l b 、 u b 即 该 式 的 条 件 ） \qquad s.t.\begin{cases} x_{1}+x_{2}+x_{3}=7，（Aeq、beq即该式的等式约束条件) \\ 2x_{1}-5x_{2}+x_{3}\geq 10，\\ x_{1}+3x_{2}+x_{3}\leq 12，\\ x_{1}，x_{2}，x_{3}\geq 0。（lb、ub即该式的条件）\end{cases}s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧x1+x2+x3=7，（Aeq、beq即该式的等式约束条件)2x1−5x2+x3≥10，x1+3x2+x3≤12，x1，x2，x3≥0。（lb、ub即该式的条件）
解（1）化成Matlab标准型，即
min w = − 2 x 1 − 3 x 2 + 5 x 3 ， \qquad\qquad\qquad\min w=-2x_{1}-3x_{2}+5x_{3}，minw=−2x1−3x2+5x3，
s . t . { [ − 2 5 − 1 1 3 1 ] [ x 1 x 2 x 3 ] ≤ [ − 10 12 ] ， (这里因为Matlab标准型是小于等于，所[ 2,-5,1]系数取反) [ 1 , 1 , 1 ] ⋅ [ x 1 x 2 x 3 ] = 7 ， [ x 1 , x 2 , x 3 ] T ≥ [ 0 , 0 , 0 ] T 。 \qquad\qquad\qquad s.t.\begin{cases}\begin{bmatrix} -2 & 5 & -1 \\ 1 & 3 & 1 \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix}\leq \begin{bmatrix} -10 \\ 12 \end{bmatrix}，\textbf{(这里因为Matlab标准型是小于等于，所[ 2,-5,1]系数取反)}\\ \left[ 1,1,1\right]\cdot\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix}=7，\\ \left[ x_{1},x_{2},x_{3}\right]^T\geq \left[0,0,0\right]^T。\end{cases}s.t.⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧[−2153−11]⎣⎡x1x2x3⎦⎤≤[−1012]，(这里因为Matlab标准型是小于等于，所[ 2,-5,1]系数取反)[1,1,1]⋅⎣⎡x1x2x3⎦⎤=7，[x1,x2,x3]T≥[0,0,0]T。
上面说的矩阵相乘时是前行后列相乘的意思是：[ − 2 × x 1 + 5 × x 2 − 1 × x 3 = − 10 1 × x 1 + 3 × x 2 + 1 × x 3 = 12 ] \begin{bmatrix} -2\times x_{1}+5\times x_{2}-1\times x_{3}=-10\\ 1\times x_{1}+3\times x_{2}+1\times x_{3}=12\end{bmatrix}[−2×x1+5×x2−1×x3=−101×x1+3×x2+1×x3=12]
A矩阵的第i行和x矩阵的第j列对应元素相乘再相加为b矩阵的第i行第j列元素。
（2）求解的Matlab程序如下：
求得的最优解为x 1 = 6.4286 ， x 2 = 0.5714 ， x 3 = 0 ， 对 应 的 最 优 值 为 z = 14.5714 。 x_{1}=6.4286，x_{2}=0.5714，x_{3}=0，对应的最优值为z=14.5714。x1=6.4286，x2=0.5714，x3=0，对应的最优值为z=14.5714。