数学建模学习笔记3——线性规划

简介

线性规划（Linear programming,简称LP）是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法。研究线性约束条件下线性目标函数的极值问题的数学理论和方法。
线性规划步骤一般如下：
（1）列出约束条件及目标函数
（2）画出约束条件所表示的可行域
（3）在可行域内求目标函数的最优解及最优值

matlab格式

标准格式：mincTx s.t. Ax ≤ b
其中c和x为n维列向量； b为m维列向量 ；A为m*n的矩阵。

若需求最大值，如 maxcTx s.t. Ax ≥ b
需写为 min -cTx s.t. -Ax ≤ -b。

线性规划中单纯形法的基本思路：先找出可行域的一个极点，据一定的规则来判断是否最优，否则转到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到最优解位置。
线性规划在Matlab中的基本函数形式是：linprog(c,A,b)，函数的返回的向量x，其中c代表线性方程的系数，是一个列向量；A代表约束方程参数的系数，b代表约束方程由常数构成的向量。（例一）
线性规划函数：[x,fval]=linprog(c,A,b,Aeq,Beq,LB,UB,X0,Options)：其中Aeq和Beq代表等式约束Ax=b；LB，UB分别是变量X的上下界，X0是X的初始值，Options代表控制参数。（例二）

例

例一：
min z=2x1+3x2+x3
s.t.：
x1+4X2+2X3>=8
3X1+2X2>=6
x1,x2,x3>=0

c=[2 3 1]’;
A=[1 4 2;3 2 0];
b=[8 6]’;
[x,fval]=linprog(c,-A,-b)

例二：
max=2x1+3x2-5x3
s.t.：
x1+x2+x3=7
2x1-5*x2+x3>=10
x1,x2,x3>=0

clear
c=[2 3 -5];
a=[2 -5 1];
b=[10];
Aeq=[1 1 1];
Beq=7;
[x,fval]=linprog(-c,-a,-b,Aeq,Beq,zeros(3,1))