线性规划（一）：基本概念

浅夏110

1.线性规划的概念
线性规划(Linear Programming 简记 LP)是了运筹学中数学规划的一个重要分支。自从 1947 年 G. B. Dantzig 提出 求解线性规划的单纯形法以来，线性规划在理论上趋向成熟，在实用中由于计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划现代管理中经常采用的基本方法之一。 在解决实际问题时，需要把问题归结成一个线性规划数学模型，关键及难点在于选适当的决策变量建立恰当的模型，这直接影响到问题的求解。
2 b2 o' u+ G3 x7 F# K9 f
线性规划问题的目标函数及约束条件均为线性函数；约束条件记为 s.t.(即 subject to)。目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以 是小于号也可以是大于号。

一般线性规划问题的（数学）标准型为

8 f4 a! g* V$ ^8 |1 l$ I; `: r, ?
. X$ N* U7 U% f8 F  z
6 \; c1 b9 p( o: n  m) S8 d  }线性规划的实例
4 w7 ]; m/ ~9 b) v$ Z1 M: K
$ h+ S* ~$ }$ x8 l

2.线性规划问题的解的概念 ：可行解、可行域、图解法
可行解  满足约束条件（4）的解  称为线性规划问题的可行解， 而使目标函数（3）达到最大值的可行解叫最优解。

# Y2 p; @- u1 H' ^5 _可行域  所有可行解构成的集合称为问题的可行域，记为R 。
1 ~. d, y6 g: x3 K, |3 `7 p
" N" I2 Q# ^0 }$ B1 ]% A图解法 简单直观，适用于二维决策变量，它有助于了解线性规划问题求解的基本原理。。对于每一固定的值z，使目标函数值等于z的点构成的直线称为目标函数等位线，当z变动时，我们得到一族平行直线。
) J  z0 l4 x5 R/ Q* _7 y
$ H9 h5 E# d3 s8 b# \' o+ ~
) B9 B+ I3 N5 Z+ N7 m
2.1. 推广到多维空间的线性规划：超平面、多胞形、多面体
. b( A( c5 ]( U以下结论可以推广到一般的线性规划问题，区别只在于空间的维数：

  _, C5 }" ^. t7 W( k# n; P（1）可行域R 可能会出现多种情况。R 可能是空集也可能是非空集合，当R 非空 时，它必定是若干个半平面的交集（除非遇到空间维数的退化） 。R 既可能是有界区域， 也可能是无界区域。

' h: W/ `2 S7 h2 h5 b- ?（2）在R 非空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其 目标函数值无界）。
3 u9 L2 C4 D0 e) _) o
（3）若线性规划存在有限最优解，则必可找到具有最优目标函数值的可行域R 的 “顶点” 。
, q  Z. e; \$ {! H7 O. d$ j
在一般的n维 空间中，满足线性等式   的点集被称为一个超平面；

( V& B* m$ R1 q      或的点集被称为一个半空间，其中为一个n维行向量，b为一个实数。
4 }. L% D/ G, H& l4 R) C8 K
, q' w7 j9 u8 ?5 O" H3 @) h若干个半空间的交集被称为多胞形，有界的多胞形又被称为多面体。易见，线性规划的可行域必为多胞形（为统一起见，空集Φ也被视为多胞形）。 在一般n维空间中，要直接得出多胞形“顶点”概念还有一些困难。二维空间中的顶点可以看成为边界直线的交点，但这一几何概念的推广在一般n维空间中的几何意义并不十分直观。为此，我们将采用另一途径来定义它。


: d( s6 E* p0 K0 S6 c( h' J/ }( s
, b$ ?( r$ g2 U, b3 D, a  n3 v单纯形法是求解线性规划问题的最常用、最有效的算法之一 ，此处不作介绍。这里我们就不介绍 单纯形法，有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的 Matlab 解法。

3.求解线性规划的 Matlab 解法
7 {1 T- k) W+ ~' x) wMatlab 中规定线性规划的标准形式为
" l3 P9 e: e6 t0 {* o! `( [# Q/ N9 H5 x


其中c和 x为n 维列向量， A、 Aeq 为适当维数的矩阵，b 、beq为适当维数的列向量。 （Aeq 对应约束条件中等式约束的系数矩阵，A为约不等式约束的系数矩阵）。
  Z1 b. ~8 C: u  ~" q; D2 ]3 Y
! {) l* h& h) J# z' O  Y4 W- [
3 r. e* d+ i! m: C" \% @- y
! q4 J# P9 o. k/ v基本函数形式为 linprog(c,A,b)，它的返回值是向量 x的值。还有其它的一些函数调用形 式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：

[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)

; E: L$ ~7 v5 M6 P9 n* E2 M

这里 fval 返回目标函数的值，LB 和 UB 分别是变量 x的下界和上界， 0 x 是x的初始值， OPTIONS 是控制参数。

例题

例如求解下列线性规划问题

解 （i）编写 M 文件

c=[2;3;-5];
& u' F% D7 [' v6 {. y& j( w( ya=[-2,5,-1;1,3,1];
b=[-10;12];
aeq=[1,1,1];
beq=7;
x=linprog(-c,a,b,aeq,beq,zeros(3,1))
3 z, p. l# w. @! g" ]value=c'*x
1 K8 B/ Y, w0 U5 c- S
" C4 V3 _5 L( j# V7 s- f1 k# n
: v( ]( Q% s& L' s& ]8 }. b* Y

（ii）将M文件存盘，并命名为example1.m。

（iii）在Matlab指令窗运行example1即可得所求结果。

例3 求解线性规划问题

解  编写Matlab程序如下：

c=[2;3;1];
a=[1,4,2;3,2,0];
b=[8;6];
[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))
! s7 m/ I; P- |4 a( e" `1 D( }8 ]
9 i! q$ O( X# @) M- c2 R
1 Q% _/ S' ~5 N
————————————————
版权声明：本文为CSDN博主「wamg潇潇」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 |( @7 c1 S7 _* m1 R原文链接：https://blog.csdn.net/qq_29831163/article/details/88893234
2 Y# t0 d1 D, j5 q$ n! U
7 I$ d, @  C# w) d: X