Matlab在最优化问题中的应用
**
(**大学*学院**班)
摘要：通过对最优化问题的研究可知，在解最优化问题时的运算量非常大，
并且很复杂，运用MATLAB工具编程并解决一些实际问题（生产计划安排、指派问题）
关键词：最优化 MATLAB 生产计划安排指派问题
引言：
在实际生活中有很多问题，需要运用到最优化，以达到我们的要求。
例如求最大利润、最佳安排等。
1.提出问题：
⑴某制造厂利用金属薄板生产4种产品，其生产系统有5个车间：冲压、
钻孔、装配、喷漆和包装。
它们的生产数据和产品利润及市场销售量如表1和表2所示。
现已知下月制造乙和丁产品的金属板的最大供应量为2000㎡，产品乙每个需2㎡.产品丁每个需1.2㎡.现要求拟定下月实现最大利润的产品搭配计划。
⑵ 4个工人分派做4项工作，规定每人只能做1项工作，每项工作只能1个人做。
现设每个工人做每项工作所消耗的时间如表3所示，求总耗时最少的分派方案。
2. 建立模型：
⑴设1x 、2x 、3x 、4x 分别为产品甲、乙、丙、丁的月生产数，则从表1、表2可得问题的数学模型：
Max z=4*1x +10*2x +5*3x +6*4x
s.t.⎪⎪⎪⎪⎪
⎪⎪⎩⎪⎪⎪⎪
⎪⎪
⎪⎨⎧≤≤≤≤≤≤≤≤≤+≤+++≤+++≤+++≤++≤+++1000
1003000
50050006000100020002.1240005.002.006.002.045012.003.02.004.050012.005.01.005.0400
1.01
2.006.04001.005.015.00
3.043
21424321432143214214321x x x x x x x x x x x x x x x x x x x x x x x x x
⑵ 本题是一个平衡的分配问题。
设指派问题的效益矩阵为4*4)(ij c ，其元素ij c 表示指派第i 个人去做第j 项工作是的效率（耗时）。
设问题的决策变量为
ij x ，是0-1变量，即
⎩⎨
⎧=项工作
人去做第当不指派第，
项工作人去做第当指派第j i 0j i ,1ij x
则其数学模型为：
Min ∑∑===41i 4
1
z
j ij
ij x c
s.t.⎪⎪⎪⎪⎩
⎪⎪⎪⎪⎨⎧======∑∑==）（或4,3,2,1,10)4,3,2,1(1)4,3,2,1(14
1
4
1j i x j x i x ij i ij j ij
3. 求解模型：
求解上述模型时，运用matlab 工具中的linprog （）函数。
⑴ 将模型进行改为标准型： Min z ’=-4*1x -10*2x -5*3x -6*4x
s.t.⎪⎪⎪⎪⎪
⎪⎪⎩⎪⎪⎪⎪
⎪⎪
⎪⎨⎧≤≤≤≤≤≤≤≤≤+≤+++≤+++≤+++≤++≤+++1000
1003000
50050006000100020002.1240005.002.006.002.045012.003.02.004.050012.005.01.005.0400
1.01
2.006.04001.005.015.00
3.043
21424321432143214214321x x x x x x x x x x x x x x x x x x x x x x x x x 前5个式子为不等式约束
则该线性规划的matlab 程序： >> f=[4 10 5 6]';f=-f;
>> a=[0.03 0.15 0.05 0.1;0.06 0.12 0 0.1;0.05 0.1 0.05 0.12;0.04 0.2 0.03 0.12];
>> a=[a;0.02 0.06 0.02 0.05;0 2 0 1.2]; %构成a >> b=[400 400 500 450 400 2000]';
>> lb=[1000 0 500 100]'; %决策变量下界 >> ub=[6000 500 3000 1000]'; %决策变量上界 >>
[x,fval,exitflag,output,lambda]=lin prog(f,a,b,[],[],lb,ub); %[]表示缺少等式约束中的aeq 和beq
Optimization terminated successfully. %最优化成功的结束 >> exitflag exitflag =
1 %表示线性规划有最优解
>>x
x =
1.0e+003 *
5.5000
x的值为5500
1
0.5000
x的值500
2
3.0000
x的值3000
3
0.1000
x的值100
4
>> fval
fval =
-4.2600e+004 最小值
由以上结果可得下月计划的最优方案为：生产甲产品5500件，乙产品500件，丙产品3000件，丁产品100件，此时利润最大为42600元。
⑵下面给出该题的matlab语言程序：
>> e=[15 18 21 24;19 23 22 18;26 17 16 19;19 21 23 17]; %效率矩阵>> a=e';f=a(:); %f是目标函数
>> o=ones(1,4);z=zeros(1,4);y=eye(4); %o中元素均为1，eye()为单位阵
>> aeq=[o,z,z,z;z,o,z,z;z,z,o,z;z,z,z,o];
>> aeq=[aeq;y,y,y,y]; %形成矩阵aeq
>> beq=ones(8,1);lb=zeros(16,1);
>> [x,fval,exitflag,output,lambda]=linprog(f,[],[],aeq,beq,lb);
%无不等式约束，a，b用[]表示
Optimization terminated successfully. %最优化成功结束
>> xv=reshape(x,4,4);xx=xv'; %xx为指派方阵
>> xx0=round(xx); %xx0为xx取整后的方阵>> xe=xx0.*e;
>> fv=sum(sum(xe)); %取整后的最优值
>> fval %最优值
fval =
70.0000
>> fv %总耗时
fv =
70
>> xx %未取整时的指派方阵
xx =
0.4834 0.5166 0.0000 0.0000
0.5166 0.0000 0.0000 0.4834
0.0000 0.0000 1.0000 0.0000
0.0000 0.4834 0.0000 0.5166
>> xx0 %取整，对指派方阵xx，将元素最大者取作1 xx0 =
0 1 0 0
1 0 0 0
0 0 1 0
0 0 0 1
由以上结果可知，最优指派方案为：工作1分给工人2，工作2分给工人1，工作3分给工人3，工作4分给工人4.此时总耗时最小为70小时。
4.总结：
通过以上实验可知，运用matlab工具可以大大减少运算量，简单有效，在实际生产生活中有很大的帮助，解决这些问题时常用到linprog（）函数，运用这一函数我们还可以解决其他的问题，例如：运输问题、整数规划、网络最大流及最短路等。
参考文献
【1】胡运权、郭耀煌.运筹学教程第四版[M].北京：清华大学出版社，2012. 【2】吴祈宗、郑志勇、邓伟.运筹学与最优化MATLAB编程[M].北京：机械工业出版社，2009.
【3】黄雍检、赖明勇.MATLAB语言在运筹学中的应用[M].湖南：湖南大学出版社，2005.
【4】王翼.MATLAB基础及在运筹学中的应用[M].北京：机械工业出版社，2012. 【5】刘焕彬、库在强、廖小勇、陈文略、张忠诚.数学模型与实验[M].北京：科学出版社，2008.。