本文共 4903 字，大约阅读时间需要 16 分钟。

一.总述模型

二.概述

1.什么是数学规划

在给定的条件下（约束条件），如何按照某一衡量指标（目标函数）来寻求计划，管理工作中的最优方案

2.一般形式

3.例子

4.分类

1. 线性规划：如果目标函数$f(x)$和约束条件$s.t.$均是决策量$x$的线性表达式，那么此时就是线性规划
   使用“单纯形法”
2. 非线性规划：当目标函数$f(x)$或者约束条件$s.t.$有一个是决策量$x$的非线性表达式，那么就是非线性规划
   没有通用算法，大多数算法就是在选定决策变量的初始值，通过寻找最优的决策变量
3. 整数规划：一类要求变量取整数值的数学规划（包括线性整数规划，非线性整数规划 ）
4. $0-1$规划：整数变量只能取$0$和$1$

三.线性规划问题求解

1.Matlab中线性规划的标准型

$minC$^T$X$（向量的内积，$C=$$\left[\begin{array}{c}{c}_1\\ c_2\\ ⋮\\ c_n\end{array}\right]$,$X=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]$,$n$是决策变量的个数）

2.例题

3.Matlab求线性规划函数

[x fval] = linprog(c, A, b, Aeq, beq, lb,ub,x0)

1. $x$₀表示给定MATLAB迭代求解的初始值（一般不用）
2. $c,A,b,Aeq,beq,lb,ub$的意义和标准型中的意义一致
3. 若不存在不等式约束，可用“[]”代替$A$和$b$
4. 若不存在等式约束，可用“[]”代替$Aeg$和$beg$
5. 若某个$x$_i无上下界，则设置$lb(i)=-lnf$,$ub(i)=+lnf$
6. 返回的$x$表示最小值处的x取值，fval表示最优解处时取得的最小值
7. 不是所有的线性规划问题都是纬一街，可能无解或有无穷多的解
8. 如果求得最大值，别忘了在最后给$fval$加一个负号

4.代码

%% Matlab求解线性规划% [x fval] = linprog(c, A, b, Aeq, beq, lb,ub, x0)  % c是目标函数的系数向量，A是不等式约束Ax<=b的系数矩阵，b是不等式约束Ax<=b的常数项% Aeq是等式约束Aeq x=beq的系数矩阵，beq是等式约束Aeq x=beq的常数项% lb是X的下限，ub是X的上限，X是向量[x1,x2,...xn]' , 即决策变量。% 迭代的初始值为x0（一般不用给）% 更多该函数的用法说明请看讲义

%% 例题1c = [-5 -4 -6]';  % 加单引号表示转置% c = [-5 -4 -6];  % 写成行向量也是可以的，不过不推荐，我们按照标准型来写看起来比较正规A = [1 -1 1;        3 2 4;        3 2 0];b = [20 42 30]';   lb = [0 0 0]'; [x fval] = linprog(c, A, b, [], [], lb)  % ub我们直接不写，则意味着没有上界的约束% x =%          0%    15.0000%     3.0000% % fval =%    -78

%% 例题2c = [0.04 0.15 0.1 0.125]';  A = [-0.03 -0.3 0 -0.15;        0.14 0 0 0.07];b = [-32 42]';Aeq = [0.05 0 0.2 0.1];beq = 24;lb = [0 0 0 0]';[x fval] = linprog(c, A, b, Aeq, beq, lb)% x =%          0%   106.6667%   120.0000%          0% % fval =%     28% 这个题可能有多个解，即有多个x可以使得目标函数的最小值为28（不同的Matlab版本可能得到的x的值不同，但最后的最小值一定是28）% 例如我们更改一个限定条件：令x1要大于0（注意Matlab中线性规划的标准型要求的不等式约束的符号是小于等于0）% x1 >0  等价于  -x1 < 0，那么给定 -x1 <= -0.1 (根据实际问题可以给一个略小于0的数-0.1)，这样能将小于号转换为小于等于号，满足Matlab的标准型c = [0.04 0.15 0.1 0.125]';  A = [-0.03 -0.3 0 -0.15;        0.14 0 0 0.07        -1 0 0 0];b = [-32 42 -0.1]';Aeq = [0.05 0 0.2 0.1];beq = 24;lb = [0 0 0 0]';[x fval] = linprog(c, A, b, Aeq, beq, lb)% x =%     0.1000%   106.6567%   119.9750%          0%% fval =%    28.0000

%% 例题3c = [-2 -3 5]';A = [-2 5 -1;          1 3 1];b = [-10 12];Aeq = ones(1,3);beq = 7;lb = zeros(3,1);[x fval] = linprog(c, A, b, Aeq, beq, lb)fval = -fval % 注意这个fval要取负号（原来是求最大值，我们添加负号变成了最小值问题）% x =%     6.4286%     0.5714%          0% fval =%   -14.5714% fval =%    14.5714

%% 多个解的情况% 例如 ： min z = x1 + x2   s.t.  x1 + x2 >= 10c = [1 1]';   A = [-1 -1];b = -10;[x fval] = linprog(c, A, b)   % Aeq, beq, lb和ub我们都没写，意味着没有等式约束和上下界约束% x有多个解时，Matlab会给我们返回其中的一个解

%% 不存在解的情况% 例如 ： min z = x1 + x2   s.t.  x1 + x2 = 10 、 x1 + 2*x2 <= 8、 x1 >=0 ，x2 >=0 c = [1 1]'; A = [1 2];b = 8;Aeq = [1 1];beq = 10;lb = [0 0]';[x fval] = linprog(c, A, b, Aeq, beq, lb)  % Linprog stopped because no point satisfies the constraints.（没有任何一个点满足约束条件）

四.线性规划例题

1.例题1：生产决策问题

%% 生产决策问题format long g   %可以将Matlab的计算结果显示为一般的长数字格式（默认会保留四位小数，或使用科学计数法）% (1) 系数向量c = zeros(9,1); % 初始化目标函数的系数向量全为0c(1) = 1.25 -0.25 -300/6000*5;  % x1前面的系数是c1c(2) = 1.25 -0.25 -321/10000*7;c(3) = -250 / 4000 * 6;c(4)  = -783/7000*4;c(5) = -200/4000 * 7;c(6) = -300/6000*10;c(7) = -321 / 10000 * 9;c(8) = 2-0.35-250/4000*8;c(9) = 2.8-0.5-321/10000*12-783/7000*11;c = -c;  % 我们求的是最大值，所以这里需要改变符号% (2) 不等式约束A = zeros(5,9);A(1,1) = 5;  A(1,6) = 10;A(2,2) = 7;  A(2,7) = 9; A(2,9) = 12;A(3,3) = 6;  A(3,8) = 8;A(4,4) = 4;  A(4,9) = 11;A(5,5) = 7;  b = [6000 10000 4000 7000 4000]';% (3) 等式约束Aeq = [1 1 -1 -1 -1 0 0 0 0;            0 0 0 0 0 1 1 -1 0];beq = [0 0]';%（4）上下界lb = zeros(9,1);% 进行求解[x fval] = linprog(c, A, b, Aeq, beq, lb)fval = -fval% fval =%           1146.56650246305%  注意，本题应该是一个整数规划的例子，我们在后面的整数规划部分再来重新求解。intcon = 1:9;[x,fval]=intlinprog(c,intcon,A,b,Aeq,beq,lb)fval = -fval

2.例题2：投料问题

%% 投料问题clear,clcformat long g   %可以将Matlab的计算结果显示为一般的长数字格式（默认会保留四位小数，或使用科学计数法）% (1) 系数向量a=[1.25  8.75  0.5  5.75  3  7.25];  % 工地的横坐标b=[1.25  0.75  4.75	5  6.5  7.25];   % 工地的纵坐标x = [5  2];  % 料场的横坐标y = [1  7];  % 料场的纵坐标c = [];  % 初始化用来保存工地和料场距离的向量 (这个向量就是我们的系数向量）for  j =1:2    for i = 1:6        c = [c;  sqrt( (a(i)-x(j))^2 + (b(i)-y(j))^2)];  % 每循环一次就在c的末尾插入新的元素    endend% (2) 不等式约束A =zeros(2,12);A(1,1:6) = 1;A(2,7:12) = 1;b = [20,20]';% (3) 等式约束Aeq = zeros(6,12);  for i = 1:6    Aeq(i,i) = 1;  Aeq(i,i+6) = 1;end% Aeq = [eye(6),eye(6)]  % 两个单位矩阵横着拼起来beq = [3 5 4 7 6 11]';  % 每个工地的日需求量%（4）上下界lb = zeros(12,1);% 进行求解[x fval] = linprog(c, A, b, Aeq, beq, lb)x = reshape(x,6,2)  % 将x变为6行2列便于观察（reshape函数是按照列的顺序进行转换的，也就是第一列读完，读第二列，即x1对应x_1,1，x2对应x_2,1）% fval =%           135.281541790676

转载地址：http://nafg.baihongyu.com/