线性规划问题是目标函数和约束条件均为线性函数(Liner Function)的问题；
MATLAB解决的线性规划问题的标准形式为：
其中 f、x、b、beq、lb、ub 为向量，A、Aeq 为矩阵。
其它形式的线性规划问题都可经过适当变换化为此标准形式。
线性规划问题（Linear Programming）已用函数linprog取代了旧版中的lp函数。当然，由于版本的向下兼容性，一般说来，低版本中的函数在新版中仍可使用。
linprog函数
x = linprog(f,A,b) %求 min f' *x sub.to A ⋅ x ≤ b 线性规划的最优解。x = linprog(f,A,b,Aeq,beq) %等式约束 Aeq ⋅ x = beq ，若没有不等式约束A ⋅ x ≤ b ，则 A=[ ]，b=[ ]。x = linprog(f,A,b,Aeq,beq,lb,ub) %指定 x 的范围lb ≤ x ≤ ub ，若没有等式约束Aeq ⋅ x = beq ，则 Aeq=[ ]，beq=[ ] x = linprog(f,A,b,Aeq,beq,lb,ub,x0) %设置初值 x0 x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) % options 为指定的优化参数[x,fval] = linprog(…) % 返回目标函数最优值，即 fval= f ' *x。[x,lambda,exitflag] = linprog(…) % lambda 为解 x 的 Lagrange 乘子。[x, lambda,fval,exitflag] = linprog(…) % exitflag 为终止迭代的错误条件。[x,fval, lambda,exitflag,output] = linprog(…) % output 为关于优化的一些信息
说明：若 exitflag>0 表示函数收敛于解 x，exitflag=0 表示超过函数估值或迭代的最大数字，exitflag<0 表示函数不收敛于解 x；
若 lambda=lower 表示下界 lb，lambda=upper 表示上 界 ub，lambda=ineqlin 表示不等式约束，lambda=eqlin 表示等式约束，lambda 中的非 0 元素表示对应的约束是有效约束；
output=iterations 表示迭代次数，output=algorithm 表示使用的运算规则，output=cgiterations 表示 PCG 迭代次数。
例：
求解
min − 5x1 − 4x2 − 6x3 （目标函数）sub.tox1 − x2 + x3 ≤ 20 （约束条件）3x1 + 2x2 + 4x3 ≤ 423x1 + 2x2 ≤ 300 ≤ x1, 0 ≤ x2, 0 ≤ x3
程序：
clc,clear,close allf = [-5; -4; -6];A = [1 -1 1;3 2 4;3 2 0]; b = [20; 42; 30]; lb = zeros(3,1); [x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb)
运行结果：
x = %最优解0.0000 15.0000 3.0000 fval = %最优值-78.0000 exitflag = %收敛1output = iterations: 6 %迭代次数cgiterations: 0 algorithm: 'lipsol' %所使用规则lambda = ineqlin: [3x1 double]eqlin: [0x1 double]upper: [3x1 double]lower: [3x1 double]>> lambda.ineqlin ans = 0.0000 1.5000 0.5000 >> lambda.lower ans = 1.0000 0.0000 0.0000
表明：不等约束条件 2 和 3 以及第 1 个下界是有效的.
0-1整数规划
0-1规划是决策变量仅取值0或1的一类特殊的整数规划。
intlinprog函数
[x,fval,exitflag]= intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)
官方文档
参数意义：
f ：目标函数的系数矩阵intcon ：整数所在位置A ：不等式约束的变量系数矩阵b ：不等式约束的资源数Aeq ：等式约束的变量系数矩阵beq ：等式约束的资源数lb ：变量约束下限ub ：变量约束上限
该函数的使用和linprog函数的使用十分相似，其仅仅在linprog函数的基础上多了一个参数——intcon。我们来通过下面的例子来学习该参数的意义。
例：
由于题目本身不难，首先直观上可以用暴力求解尝试各种方案组合，尽量安排每个工人做其相应工作时间最短的工作，不难得出：
甲 A
乙 D
丙 C
丁 B
这个方案，最短时间为70.
接下来用整数0-1模型求解验证;
首先建立模型：
min 15x1+18x2+21x3+24x4+19x5+23x6+22x7+18x8+26x9+17x10+16x11+19x12+19x13+21x14+23x15+17x16%目标函数：令工作时长最短.sub.tox1+x2+x3+x4=1x5+x6+x7+x8=1x9+x10+x11+x12=1x13+x14+x15+x16=1x1+x5+x9+x13=1x2+x6+x10+x14=1x3+x7+x11+x15=1x4+x8+x12+x16=1x1~16=0 或 1%约束条件满足甲乙丙丁四人各完成一件不同的工作.
clc,clear,close allf = [15 18 21 24 19 23 22 18 26 17 16 19 19 21 23 17];ic = [1:16];Aeq = [ones(1,4),zeros(1,12);...zeros(1,4),ones(1,4),zeros(1,8);...zeros(1,8),ones(1,4),zeros(1,4);...zeros(1,12),ones(1,4);...[1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,zeros(1,3)];...[0,1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,zeros(1,2)];...[zeros(1,2),1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,0];...[zeros(1,3),1,zeros(1,3),1,zeros(1,3),1,zeros(1,3),1]];beq = ones(8,1);lb = zeros(16,1);ub = ones(16,1);[x,fval] = intlinprog(f,ic,[],[],Aeq,beq,lb,ub)
运行结果：
LP:Optimal objective value is 70.000000. Optimal solution found.Intlinprog stopped at the root node because theobjective value is within a gap tolerance of the optimal value,options.AbsoluteGapTolerance = 0 (the default value). The intcon variables areinteger within tolerance, options.IntegerTolerance = 1e-05 (the default value).x =0100100000100001fval =70
可见与我们暴力求解的最优化方案一致！
此外，本题作为经典的任务分派问题，也可以作为匹配问题用匈牙利算法解决：
匈牙利算法(Hungarian method)由美国数学家哈罗德·库恩于1955年提出。
此算法之所以被称作匈牙利算法，是因为算法很大一部分是基于以前匈牙利数学家Dénes Kőnig和Jenő Egerváry的工作之上创建起来的。
匈牙利算法是基于Hall定理中充分性证明的思想，它是二分图（也称二部图）匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。
简单来说，匈牙利算法就是为了解决匹配问题的一种算法。
是一种在多项式时间内求解任务分配问题的组合优化算法，并推动了后来的原始对偶方法。可以设想这样一个问题，有三个工人要共同完成三件任务。每个人只能专注完成一件任务。且工人完成不同任务所需要的时间是不一样的。
当然这里可以直接通过枚举的方式来遍历所有的分配方式（暴力求解）来进行求解。但当求解的问题的维度变得比较大时，这样处理就显得不太明智了。
所以，为了解决这一类问题，匈牙利算法得以提出。
具体实现过程可参考：
分派问题（匈牙利算法）与MATLAB实现
