Matlab--运筹学

Posted on | In , | Visitors:

This is my blog.
好久没学知识了，都是复习的锅
感觉blog太弱了，看到别人的都是满满的知识
我还都看不懂
今天终于学了点点
点点说：你这叫搬运工，方便自己查么

别被标题吓到了，毕竟，你懂的，我没啥东西的

运筹学

what

它主要研究人类对各种资源的运用及筹划，在满足一定约束的条件下，以期发挥有限资源的最大效益，达到总体最优的目标。
简单地说：凡是有“最”字，如：利润最大化、成本最小化，基本就和运筹学息息相关。

classify

好吧，以下才是我今天想要说的重点呢！关于规划问题的一些东西。毕竟自己不是数学系的，也不负责建模，就不探讨原理了，直接上一些函数，方便自己调用喽！

线性规划（Linear Programming）

貌似是高考的一道大题类型吧。

Matlab linprog(c,A,b,Aeq,beq,lb,ub);
若没有等式约束，则Aeq = [] , beq = []

非线性规划 (Nonlinear Programming)

就是不是一次的么。。。

  1. 二次规划

  2. 约束极小

凸优化 (Convex Optimization)

凸优化有个非常重要的定理，即任何局部最优解即为全局最优解。
贪婪算法（Greedy Algorithm）或梯度下降法（Gradient Decent），收敛求得的局部最优解即为全局最优。

（混合）整数规划 (Mixed Integer Programming)

动态规划(Dynamic Programming)、近似算法(Approximation Algorithms)、启发式算法（Heuristic Algorithms， Meta Heuristics）、遗传算法 (Generic Algorithms)—用来解例如整数规划等NP难优化问题的算法，后俩个通常只能得到局部最优解，最经典的当属最大流最小割定理衍生出来的一些最大流算法（全局最优）。

  1. 分支定界法
    分支：将可行解域分割成几个（经常是两个）互不相交的集合
    定界：在任何分割出的子集合上能够计算出一个界
  2. 割平面法

Matlab intlinprog(c,intcon,A,b,Aeq,beq,lb,ub);

半正定规划 (Semi-definite Programming

貌似是关于内地安，凸包啥的。。。看不懂。。。

网络流问题（Network Flow Problems）

离散书上那个是吗？费用流，网络流。。。唔，好久没打代码了，罪过

随机取样计算法

用概率论知识，balabala（不知所云），反正就是可以用么。
看代码理解吧！

Matlab 函数

类型 模型 基本函数名
一元函数极小 Min F(x) s.t. x1<x<x2 x = fminbnd(‘F’,x1,x2)
无约束极小 Min F(X) x = fminunc(‘F’,x0)
线性规划 Min c^T * X s.t. AX<=b x = linprog(c,A,b)
二次规划 Min 1/2x^T H x + C^T * x s.t. Ax<=b quadprog(H,c,A,b)
约束极小（非线性规划） Min F(x) s.t. G(x)<=0 x = fmincon(‘FG’,x0)
达到目标问题 Min r s.t. F(x)-w*r <= goal x = fgoalattain(‘F’,x,goal,w)
极小极大问题 Min max { Fi(x) } s.t. G(x)<=0 x = fminimax(‘FG’,x0)
整数规划 x = intlinprog(c,intcon,A,b);

注 其中，fminbnd，fminunc，fmincon，fgoalattain，fminimax中的f，必须为行命令对象或M文件、嵌入函数或MEX文件的名称

这里需先插入一个知识点

options

  1. Display：取值为’off’时，不显示输出；取值为’iter’时，显示每次迭代的值；取值为’final’（默认）,显示最终结果。
  2. MaxIter：允许进行迭代的最大次数，取值为正整数
  3. LargeScale = ‘on’（使用大型算法）/‘off’（使用中型算法）
    注只有上下界存在或只有等式约束，fmincon函数将选择大型算法。当既有等式约束又有梯度约束时，使用中型算法。
  4. HessUpdate = ‘bfgs’/‘dfp’/‘steepdesc’（最速下降法）
  5. GradObj = ‘on’（默认）/‘off’ 梯度
  6. exitflag
    Exitflag | 含义
    ———- | ———-
    1 | 一阶最优性条件满足容许范围
    2 | X 的变化小于容许范围
    3 | 目标函数的变化小于容许范围
    4 | 重要搜索方向小于规定的容许范围并且约束违背小于options.TolCon
    5 | 重要方向导数小于规定的容许范围并且约束违背小于options.TolCon
    0 | 到达最大迭代次数或到达函数评价
    -1 | 算法由输出函数终止
    -2 | 无可行点
  7. attainfactor变量是超过或低于目标的个数。若attainfactor为负，则目标已经溢出；若attainfactor为正，则目标个数还未达到
  8. nonlcon该函数计算非线性不等式约束c(x) <=0和非线性等式约束ceq(x)=0。nonlcon函数是一个含函数名的字符串，该函数可以是M文件、内部函数或MEX文件。
  9. maxfval为目标函数在x处的最大值
  10. …（其他的我都不认识 0-0）
1
options = optimset(...)

Example

举例子（栗子🌰）

光看可能觉得很简单，但我记不住啊，敲一遍喽

  1. fminbnd
    1
    2
    3
    4
    5
    f = '2 * exp(-x) .* sin(x)';
    fplot(f,[0,8]);
    [xmin,ymin] = fminbnd(f,0,8)
    f1 = '-2 * exp(-x) .* sin(x)';
    [xmax,ymax] = fminbnd(f1,0,8)

小废话 发现lingo还不错哎！简直白话文…

1
2
3
4
5
model:
min=2*@exp(-x)*@sin(x);
x>0;
x<8;
end

  1. fminunc
    fun1.m
    1
    2
    function f = fun1(x)
    f = exp(x(1))*(4*x(1)^2+2*x(2)^2+4*x(1)*x(2)+2*x(2)+1);

test.m

1
2
3
x0 = [-1,1];
x = fminunc('fun1',x0);
y = fun1(x)

小废话上面那个例子不知道题目了，明明昨天写的么，可能是Matlab官方手册上的吧！下面给出另一个例子，不写题目，自行体会啦！
fun2.m

1
2
3
4
function g = fun2(x);
M = 50000;
f = x(1)^2 + x(2)^2 + 8;
g = f - M * min(x(1),0) - M * min(x(2),0) - M * min(x(1)^2-x(2),0)+M * abs(-x(1)-x(2)^2+2);

test.m

1
2
[x,y] = fminunc('test',rand(2,1))
% rand(m,n)产生m行n列的位于(0,1)区间的随机数

小废话 唔，好吧！我觉得我自己过几天也看不懂了。
解决的问题：（形式）
min f(x)
s.t.
\(g_i(x) <= 0, i=1,2,…,r\)
\(h_i(x) >= 0, i=1,2,…,s\)
\(k_i(x) = 0, i=1,2,…,t\)
M是一个充分大的数，自己决定的，但是要大于0 然后构造函数
\(P(x,M) = f(x) + M1 max(G(x),0) + M2 min(H(x),0) + M3 * ||K(x)||\)
其中\(M_1，M_2，M_3\)是适当的行向量。

  1. linprog
    1
    2
    3
    4
    5
    6
    7
    8
    c = [-2;-3;5];
    a = [-2,5,-1;1,3,1];
    b = [-10;12];
    Aeq = [1,1,1];
    beq = [7];
    VlB = zeros(3,1)
    VUB = [];
    x = linprog(c,a,b,Aeq,beq,VlB,VUB)

注 对于求最大值这个，我觉得还是不要将c的每一个元素变负，而是在调用linprog时用-c为好，这样计算出的fval就是最大值了。

  1. quadprog

    首先，还是需要脑子🧠的么—
    可是我不喜欢这种，感觉化简很麻烦的呢…
    写成标准形式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    H = [1 -1;-1 2];
    c = [-2;-6];
    A = [1 1;-1 2];
    b = [2;2];
    Aeq = [];
    beq = [];
    VLB = [0;0];
    VUB = [];
    [x,z] = quadprog(H,c,A,b,Aeq,beq,VLB,VUB)

  2. fmincon

    fun3.m

    1
    2
    function f = fun3(x)
    f = -x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2

test.m

1
2
3
4
5
6
7
8
x0 = [1;1];
A = [2 3;1 4];
b = [6;5];
Aeq = [];
beq = [];
VLB = [0;0];
VUB = [];
[x,fval] = fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB)


fun4.m

1
2
3
function f = fun4(x);
f = exp(x(1)) * (4 * x(1)^2 + 2 * x(2)^2+4 * x(1)*x(2) + 2 * x
(2) + 1)

mycon.m

1
2
3
4
%定义非线性约束
function [g,ceq] = mycon(x)
g = [1.5 + x(1)*x(2) - x(1) - x(2);-x(1) * x(2) - 10]
ceq = 0;

test.m

1
2
3
4
5
6
7
8
x0 = [-1;1];
A = [];
b = [];
Aeq = [1 1];
beq = [0];
VLB = [];
VUB = [];
[x,fval] = fmincon('fun4',x0,A,b,Aeq,beq,VLB,VUB,'mycon')

  1. fgoalattain
    fgoalattian是用来求解多目标规划，包括线性规划和非线性规划，因此是一个非常有力的工具，需要注意的是求解之前要建立三个向量，即goal—目标判断向量，weight—权重向量，x0—初始解。其中goal一般为已知，weight一般按照目标比例确定，初始值的选取可以根据条件目测一个，如果看不出来可以随机生成一个（一般不会影响结果）。
    ［x,fval,attainfactor,exitflag］= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon)
    例：求侧某化工厂拟生产两种新产品A和B，其生产设备费用分别为2万元/吨和5万元/吨。这两种产品均将造成环境污染，设由公害所造成的损失可折算为A为4万元/吨，B为1万元/吨。由于条件限制，工厂生产产品A和B的最大生产能力各为每月5吨和6吨，而市场需要这两种产品的总量每月不少于7吨。试问工厂如何安排生产计划，在满足市场需要的前提下，使设备投资和公害损失均达最小。该工厂决策认为，这两个目标中环境污染应优先考虑，设备投资的目标值为20万元，公害损失的目标为12万元。
    设工厂每月生产产品A为x1吨，B为x2吨，设备投资费为f(x1),公害损失费为f(x2)

    fun5.m
    1
    2
    3
    function f = fun5(x)
    f(1) = 2 * x(1) + 5 * x(2);
    f(2) = 4 * x(1) + x(2);

test.m

1
2
3
4
5
6
7
8
9
10
x0 = [5 5];
goal = [20 12];
weight = [20 12];
A = [1 0;0 1;-1 -1];
b = [5;6;-7];
Aeq = [];
beq = [];
lb = zeros(2,1);
ub = [];
[x,fval,attainfactor,exitflag] = fgoalattain('fun5',x0,goal,weight,A,b,Aeq,beq,lb,ub)

  1. fminimax

    即到所有点最远的那个距离最小

    fun6.m
    1
    2
    3
    4
    5
    6
    function f=fun6(x)
    m = [1 4 3 5 9 12 6 20 17 8];
    n = [2 10 8 18 1 4 5 10 8 9];
    for i = 1:10
        f(i) = abs(x(1) - m(i)) + abs(x(2) - n(i));
    end

test.m

1
2
3
4
5
6
7
8
x0 = [6;6];
A = [-1 0;1 0;0 -1;0 1];
b = [-5;8;-5;8];
Aeq = [];
beq = [];
lb=[0;0];
ub=[];
[x,fva,maxfval,exitflag,output]=fminimax(@fun6,x0,A,b,Aeq,beq,lb,ub)

  1. intlinprog
    1
    2
    3
    4
    5
    6
    7
    8
    9
    c = [40;90];
    intcon = [1,2];
    A = [9,7;7,20];
    b = [56;70];
    Aeq = [];
    beq = [];
    lb = zeros(2,1);
    x = linprog(-c,intcon,A,b,Aeq,beq,lb)
    fval = c' * x;

转化为线性规划问题

后记

我才知道原来要呆一个月左右，半夜看剧发慌，唔～
没有什么好吃的呢！
不过倒也不是无聊，也算一件好事啦！
抓紧整理各种类型的代码吧！
别露马脚啦，嘻嘻嘻
(唔～为什么图片加载不出来了。不开心，算了，不想折腾，以后再说喽，相信机智的你可以脑补啦！）

转载请注明出处，谢谢。

愿 我是你的小太阳



买糖果去喽