【数学建模】数学建模学习1---线性规划（例题+matlab代码实现）
1 线性规划
  在⼈们的⽣产实践中，经常会遇到如何利⽤现有资源来安排⽣产，以取得最⼤经济效益的问题。此类问题构成了运筹学的⼀个重要分⽀—数学规划，⽽线性规划(Linear Programming 简记 LP)则是数学规划的⼀个重要分⽀。⾃从 1947 年 G. B. Dantzig 提出求解线性规划的单纯形⽅法以来，线性规划在理论上趋向成熟，在实⽤中⽇益⼴泛与深⼊。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适⽤领域更为⼴泛了，已成为现代管理中经常采⽤的基本⽅法之⼀。
1.1 线性规划的实例与定义
例 1   某机床⼚⽣产甲、⼄两种机床，每台销售后的利润分别为 4000 元与 3000 元。⽣产甲机床需⽤ A、B 机器加⼯，加⼯时间分别为每台 2 ⼩时和 1 ⼩时；⽣产⼄机床需⽤ A、B、C 三种机器加⼯，加⼯时间为每台各⼀⼩时。若每天可⽤于加⼯的机器时数分别为 A 机器 10 ⼩时、B 机器 8 ⼩时和C 机器 7 ⼩时，问该⼚应⽣产甲、⼄机床各⼏台，才能使总利润最⼤？
  上述问题的数学模型：设该⼚⽣产 x1 台甲机床和 x2 ⼄机床时总利润最⼤，则 x1, x2
  应满⾜
  这⾥变量 x1 , x2 称之为决策变量，（1）式被称为问题的⽬标函数，（2）中的⼏个不等式是问题的约束条件，记为 s.t.(即 subject to)。由于上⾯的⽬标函数及约束条件均为线性函数，故被称为线性规划问题。
  总之，线性规划问题是在⼀组线性约束条件的限制下，求⼀线性⽬标函数最⼤或最⼩的问题。在解决实际问题时，把问题归结成⼀个线性规划数学模型是很重要的⼀步，但往往也是困难的⼀步，模型建⽴得是否恰当，直接影响到求解。⽽选适当的决策变量，是我们建⽴有效模型的关键之⼀。
1.2 线性规划的 Matlab 标准形式
  线性规划的⽬标函数可以是求最⼤值，也可以是求最⼩值，约束条件的不等号可以是⼩于号也可以是⼤于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为
  其中 c 和 x 为 n 维列向量， A 、 Aeq 为适当维数的矩阵，b 、beq 为适当维数的列向量。
1.3 线性规划问题的解的概念
⼀般线性规划问题的（数学）标准型为
可⾏解 满⾜约束条件（4）的解 x = (x1, x2 ,L, xn ) ，称为线性规划问题的可⾏解，⽽使⽬标函数（3）达到最⼤值的可⾏解叫最优解。可⾏域 所有可⾏解构成的集合称为问题的可⾏域，记为 R 。
1.4 线性规划的图解法
  图解法简单直观，有助于了解线性规划问题求解的基本原理。我们先应⽤图解法来求解例 1。对于每⼀固定的值 z ，使⽬标函数值等于z 的点构成的直线称为⽬标函数等位线，当 z 变动时，我们得到⼀族平⾏直线。对于例 1，显然等位线越趋于右上⽅，其上的点具有越⼤的⽬标函数值。不难看出，本
例的最优解为 x* = (2,6)T ，最优⽬标值z* = 26 。
  从上⾯的图解过程可以看出并不难证明以下断⾔：
（1）可⾏域 R 可能会出现多种情况。R 可能是空集也可能是⾮空集合，当 R ⾮空时，它必定是若⼲个半平⾯的交集（除⾮遇到空间维数的退化）。R 既可能是有界区域，也可能是⽆界区域。
（2）在 R ⾮空时，线性规划既可以存在有限最优解，也可以不存在有限最优解（其⽬标函数值⽆界）。
（3）若线性规划存在有限最优解，则必可到具有最优⽬标函数值的可⾏域 R 的“顶点”。
1.5 求解线性规划的 Matlab 解法
  单纯形法是求解线性规划问题的最常⽤、最有效的算法之⼀。这⾥我们就不介绍单纯形法，有兴趣的读者可以参看其它线性规划书籍。下⾯我们介绍线性规划的 Matlab解法。
matlab学好了有什么用
  Matlab 中线性规划的标准型为
  基本函数形式为 linprog(c,A,b)，它的返回值是向量 x 的值。还有其它的⼀些函数调⽤形式（在 Matlab 指令窗运⾏ help linprog 可以看到所有的函数调⽤形式），如：
  [x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)
  这⾥ fval 返回⽬标函数的值，LB 和 UB 分别是变量 x 的下界和上界，x0 是 x 的初始值，OPTIONS 是控制参数。
例 2 求解下列线性规划问题
解 （i）编写 M ⽂件
c=[2;3;-5];
a=[-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))
value=c'*x
（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))
2 运输问题(产销平衡)
例 6  某商品有m 个产地、n 个销地，各产地的产量分别为a1,L,am ，各销地的需求量分别为b1,L,bn 。若该商品由i 产地运到 j 销地的单位运价为cij ，问应该如何调运才能使总运费最省？
解：引⼊变量 xij ，其取值为由i 产地运往 j 销地的该商品数量，数学模型为
  显然是⼀个线性规划问题，当然可以⽤单纯形法求解。
  对产销平衡的运输问题，由于有以下关系式存在：
  其约束条件的系数矩阵相当特殊，可⽤⽐较简单的计算⽅法，习惯上称为表上作业法（由康托洛维奇和希奇柯克两⼈独⽴地提出，简称康—希表上作业法）。
3 指派问题
3.1 指派问题的数学模型
例 7   拟分配n ⼈去⼲n 项⼯作，每⼈⼲且仅⼲⼀项⼯作，若分配第i ⼈去⼲第 j项⼯作，需花费cij 单位时间，问应如何分配⼯作才能使⼯⼈花费的总时间最少？
  容易看出，要给出⼀个指派问题的实例，只需给出矩阵C = (cij) ，C 被称为指派问题的系数矩阵。
  引⼊变量 xij ，若分配i ⼲ j ⼯作，则取 xij = 1，否则取 xij = 0 。上述指派问题的数学模型为
  上述指派问题的可⾏解可以⽤⼀个矩阵表⽰，其每⾏每列均有且只有⼀个元素为1，其余元素均为 0；可以⽤1,L,n 中的⼀个置换表⽰。
  问题中的变量只能取 0 或 1，从⽽是⼀个 0-1 规划问题。⼀般的 0-1 规划问题求解极为困难。但指派问题并不难解，其约束⽅程组的系数矩阵⼗分特殊（被称为全单位模矩阵，其各阶⾮零⼦式均为 ±1），其⾮负可⾏解的分量只能取 0 或 1，故约束 xij = 0或1可改写为xij ≥ 0⽽不改变其解。此时，指派问题被转化为⼀个特殊的运输问题，其中m = n ，ai = bj =1。
3.2 求解指派问题的匈⽛利算法
  由于指派问题的特殊性，⼜存在着由匈⽛利数学家 Konig 提出的更为简便的解法—匈⽛利算法。算法主要依据以下事实：如果系数矩阵C = (cij) ⼀⾏（或⼀列）中每⼀元素都加上或减去同⼀个数，得到⼀个新矩阵 B = (bij) ，则以C 或 B 为系数矩阵的指派问题具有相同的最优指派。
例 8 求解指派问题，其系数矩阵为
解 将第⼀⾏元素减去此⾏中的最⼩元素 15，同样，第⼆⾏元素减去 17，第三⾏元素减去 17，最后⼀⾏的元素减去 16，得