title: 数学规划模型 -- 线性规划问题
date: 2020-02-26 20:08:59
categories: 数学建模
tags: [MATLAB, 数学规划模型]
Matlab 中线性规划的标准型
标准型
\[ min \ C^{T}X \\ \s.t. \ \begin{cases} & \text{} AX<=b \quad 不等式约束 \\ & \text{}Aeg*x=beg \quad 等式约束 \\ & \text{}lb<=x<=ub \quad 上下界约束 (也可以当成不等式约束) \end{cases} \]
向量的内积 ,
\[ c=\begin{pmatrix} C_{1}\\ C_{2}\\ ...\C_{n} \end{pmatrix} \quad x=\begin{pmatrix} x_{1}\\ x_{2}\\ ...\x_{n} \end{pmatrix},n 是决策变量的个数 \]
练习题
min->maxm 加负号
不等式约束的标准是 <=,>= 需要转换
变量如果不在约束条件, 用 inf 与 - inf 巧妙转换
Matlab 求解线性规划 的函数
[x ,fval] = linprog [ c, A, b, Aeq, beq, lb, ub, X0]
1 X0 表示给定 Matlab 迭代求解的初始值 ( ? 般不? 给)
2 c, A, b, Aeq, beq, lb, ub 的意义和 标准型中的意义? 致
3 若不存在不等式约束, 可? "[ ]" 替代 A 和 b
4 若不存在等式约束, 可? "[ ]" 替代 Aeq 和 beq
5 苦某个 x? 下界或上界, 则设置 lb(i)=-inf,ub(i)=+inf
6 返回的 x 表示? 值处的 x 取值 ; fval 表示优解处时取得的最小值
7. 不是所有的线性规划都有唯一解, 可能无解或有无穷多的解.
8. 如果求的是最大值, 别忘在最后给 fval 加一个负号.
上? 三个题的代码 :
- [x, fval]=linprog[c, A, b, [], [], lb]
- [x, fval]=linprog[c, A, b,Aeg, beg, lb]
- [x, fval]=linprog[c, A, b,Aeg, beg, lb]
- fval=-fval
代码
%% 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(一般不用给)
% 更多该函数的用法说明请看讲义
%% 例题 1
c = [-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
%% 例题 2
- c = [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
%% 例题 3
- c = [-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>= 10
- c = [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
设备有效台:
你有 100 台设备, 每月工作 22 天, 每天工作 8 小时, 设备每天只有 5 小时有效运作 (生产), 则你的设备有效台时 = 5*22*100=11000 台时, 你的工作台时 = 8*22*100=17600 台时, 设备有效作业率 = 5/8=62.5%
%% 生产决策问题
format long g % 可以将 Matlab 的计算结果显示为一般的长数字格式 (默认会保留四位小数, 或使用科学计数法)
% (1) 系数向量
c = zeros(9,1); % 初始化目标函数的系数向量全为 0
c(1) = 1.25 -0.25 -300/6000*5; % x1 前面的系数是 c1
- c(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
%% 投料问题
clear,clc
format 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 的末尾插入新的元素
end
end
% (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://www.bubuko.com/infodetail-3438382.html