[学习笔记]几类可以神奇转化为线性规划的问题matlab求解
几类可以神奇转化为线性规划的问题matlab求解
有些有约束的“伪线性规划”问题可以巧妙转化成线性规划的问题得以求解。实在太巧秒了。
1.第一类问题（含绝对值的“伪线性规划”问题）：
则上面的优化问题转化为：
c=[1,2,3,4,1,2,3,4];
Aeq=[1,-1,-1,1,-1,1,1,-1;1,-1,1,-3,-1,1,-1,3;1,-1,-2,3,-1,1,2,-3];
beq=[0;1;-1/2];
lb=zeros(8,1);
uv0=ones(8,1);
options = optimset('LargeScale', 'off', 'Simplex',
'on','Diagnostics','on','MaxIter',1000);
[uv,fval,exitflag,output,lambda]=linprog(c,[],[],Aeq,beq,lb,[],uv0,options)
解得u1,u2,u3,u4,v1,v2,v3,v4分别为：1/4,0,0,0,0,0,0,1/4,即
x1,x2,x3,x4的值分别为：1/4,0,0,-1/4时，最小者为1.25
用Lingo验证结果：
x1-x2-x3+x4=0;
x1-x2+x3-3*x4=1;
x1-x2-2*x3+3*x4=-1/2;
@free(x1);@free(x2);@free(x3);@free(x4);
value:&&&&&&&1.250000
Variable&&&&&&&Value&&&&&&&&
0.2500000&&&&&&&&&&&&
&&&X2&&&&&&&
0.000000&&&&&&&&&&&&
0.000000&&&&&&&&&&&&
&&&X4&&&&&
-0.2500000&&&&&&&&&&&
与matlab求得结果一致。
2.第二类问题（含取最大或最小值的“伪线性规划”问题）：
现令x0=max{x1-x2+x3，x1+x2,x1-x3},故有
x0&=x1-x2+x3,x0&=x1+x2,x0&=x1-x3
故上面的规划问题转换为：
c=[1,0,0,0];
Aeq=[0,1,1,-1;0,2,-1,0];
beq=[1;2];
A=[0,1,-2,1;-1,1,-1,1;-1,1,1,0;-1,1,0,-1];
b=[1;0;0;0];
lb=zeros(3,1);
xx0=[-0;0;0];
options = optimset('LargeScale', 'off', 'Simplex',
'on','Diagnostics','on','MaxIter',1000);
[x,fval,exitflag,output,lambda]=linprog(c,A,b,Aeq,beq,lb,[],xx0,options)
求得结果：x1,x2,x3分别为：1,0,0时，取得最优解为1。
用Lingo验证结果：
object/1..3/:
f(1) = x1-x2+x3;
f(2) = x1+x2;
f(3) = x1-x3;
x1+x2-x3=1;
2*x1-x2=2;
x1-2*x2+x3&=1;
min = @smax(f(1),f(2),f(3));
value:&&&&&&&&
Variable&&&&&&&Value&&&&&&&&
&&&X1&&&&&&&
1.000000&&&&&&&&&&&&
0.000000&&&&&&&&&&&&
&&&X3&&&&&&&
0.000000&&&&&&&&&&&
与matlab求的一致。
3.第三类问题：线性回归问题
线性回归是一种常用的数理统计方法，这个方法要求对图上的一系列点(x1,y1),(x2,y2),...,(xn,yn)选配一条合适的直线拟合。方法通常是先定直线方程为：y=bx+a，然后按某种准则求a、b。通常这个准则为最小二乘法，则求对应的a、b值。
下面用线性规划求解：
按照第一类问题的解法，设有四个点为：（1,2),(2,4),(3,8),(4,10)，令
模型转化为：
c=[0,0,1,1,1,1,1,1,1,1];
Aeq=[1,1,1,0,0,0,-1,0,0,0;1,2,0,1,0,0,0,-1,0,0;1,3,0,0,1,0,0,0,-1,0;1,4,0,0,0,1,0,0,0,-1];
beq=[2;4;8;10];
lb=[-inf,-inf,0,0,0,0,0,0,0,0];
abuv0=ones(10,1);
options = optimset('LargeScale', 'off', 'Simplex',
'on','Diagnostics','on','MaxIter',1000);
[abuv,fval,exitflag,output,lambda]=linprog(c,[],[],Aeq,beq,lb,[],abuv0,options)
求解得出：a=
-0.6667，b=2.6667。验证结果：
用Lingo求解验证：
min=u1+u2+u3+u4+v1+v2+v3+v4;
a+b+u1-v1=2;
a+2*b+u2-v2=4;
a+3*b+u3-v3=8;
a+4*b+u4-v4=10;
@free(a);@free(b);
求得a=-0.6666667&，b=2.666667。与matlab的是一致的。&&&&&&&&&&&&&&&&&&&&
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。运筹学1_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
阅读已结束，下载本文需要
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩9页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢当前位置： >
线性规划问题就是求出一组变量，在一组线性约束条件下，使某个线性目标函数达到极大（小）值。满足线性约束条件的变量区域称为可行解区。由于可行解区的边界均是线性的（平直的），属于单纯形，所以线性目标函数的极值只要存在，就一定会在可行解区边界的某个顶点达到。因此，在求解线性规划问题时，如果容易求出可行解区的所有顶点，那么只要在这些顶点处比较目标函数的值就可以了。
例如，线性规划问题：max S=x+y（求S=x+y的最大值）；2x+y&7， x+2y&8， x&0，y&0的可行解区是由四条直线2x+y=7， x+2y=8， x=0，y=0围成的，共有四个顶点。除了原点外，其他三个顶点是（ &）。因此，该线性规划问题的解为（ &）。
A.（2，3），（0，7），（3.5，0） B.（2，3），（0，4），（8，0） C.（2，3），（0，7），（8，0） D.（2，3），（0，4），（3.5，0） A. x=2，y=3 B. x=0，y=7 C. x=0，y=4 D. x=8，y=0
所属学科：
试题类型：客观题
所属知识点：
试题分数：2.0 分
暂无学习笔记。
&&&&&&&&&&&&&&&希赛网 版权所有 & &&请问一下设置目标函数的格式是怎样的？_百度知道
请问一下设置目标函数的格式是怎样的？
y=f(x)什么意思，哪个范筹的问题？
就是在设置目标函数是它老是说什么“目标函数必须是公式”我按照我们老师的PPT做的 但是还是做不对。比如我在目标函数那个单元格写“a1*100+b1*120”，但是用规划求解的时候就说我输入的不对。
前面加个“＝”（就是等于号）试试
前面有等号貌似也不行的说。。不过还是谢谢啦
采纳率：32%
为您推荐：
其他类似问题
目标函数的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。查看: 21469|回复: 10
目标函数带绝对值的线性规划问题Matlab求解
签到天数: 12 天[LV.3]偶尔看看II
用 求解下列线性规划问题：
min z=|x1|+2|x2|+3|x3|+4|x4|;
s.t. x1-x2-x3+x4=0;
x1-x2+x3-3*x4=1;
x1-x2-2*x3+3*x4=-0.5.
签到天数: 12 天[LV.3]偶尔看看II
我们知道Matlab的优化工具箱提供了好多优化函数，当然不缺少线性规划的函数
但是很惋惜的是，Matlab的线性规划函数linprog只能求解线性目标函数，而该目标函数带有对绝对值，此时linprog是无能为力的！
那怎么办呢？下面我提供三种方法解决
不幸中的万幸，Matlab提供了fmincon ，它可以解决非线性的目标最优化问题，但是有些大材小用，另外就是该函数必须提供初值，这个把人累死了。
不管它，我们这里只是演示，初值不一定合适，看看下面的程序吧%by dynamic
%see also http://www.matlabsky.com
objfun=@(x)abs(x(1))+2*abs(x(2))+3*abs(x(3))+4*abs(x(4))
Aeq=[1 -1 -1 1
1 -1 -2 3];
beq=[0 1 -0.5]';
x0=[0 0 0 0];%给一个初值 很关键 和很重要哦
x=fmincon(objfun,x0,[],[],Aeq,beq) 复制代码方法二：
假如说数学功底特别好的网友，也许见过下面的定理
对任意的X，必存在U，V&0满足
X=U-V，|X|=U+V
U=(X+|X|)/2，Vi=(|X|-X)/2
于是对于上面的问题我们转化为
min z=[1 2 3 4 1 2 3 4]*[u1 u2 u3 u4 v1 v2 v3 v4]'
A=[1 -1 -1 1 1 -1 -1 1
& & 1 -1 1 -3 1 -1 1 -3
& & 1 -1 -2 3 1 -1 -2 3]
b=[0 1 -0.5]'
x=[u1 u2 u3 u4 v1 v2 v3 v4]'
于是编程有，注意此时目标函数是线性的了，故不需要初值了，真是太好了%目标函数
f=[1 2 3 4 1 2 3 4];
%等式约束
Aeq=[1 -1 -1 1 1 -1 -1 1
1 -1 1 -3 1 -1 1 -3
1 -1 -2 3 1 -1 -2 3];
beq=[0 1 -0.5]';
%边界条件
lb=zeros(8,1);
%调用linprog
x=linprog(f,[],[],Aeq,beq,lb)
复制代码方法三：
既然Matlab没有提供直接的相关函数，但是我们不能吊死一棵树呀，该多方求救吗
功夫不负有心呀，以下两个工具箱都可以很方便的帮我们解决这个问题
【YALMIP高级优化工具箱】
【BNB20分支定界工具箱】
特别是BNB20分支定界工具箱
在实际应用着经常需要求解非线性整数规划或混合规划问题，该领域中的一种常用的算法是分支定界(branch and bound)算法，但是matlab工具箱中没有相关的函数。荷兰Groningen大学的Koert Kuipers编写的的BNB20工具箱可以用来求解一般非线性整数规划问题。
该用户从未签到
对任意的X，必存在U，V&0满足
X=U-V，|X|=U+V
U=(X+|X|)/2，Vi=(|X|-X)/2
于是对于上面的问题我们转化为
min z=[1 2 3 4 1 2 3 4]*[u1 u2 u3 u4 v1 v2 v3 v4]'
A=[1 -1 -1 1 1 -1 -1 1
& & 1 -1 1 -3 1 -1 1 -3
& & 1 -1 -2 3 1 -1 -2 3]
b=[0 1 -0.5]'
x=[u1 u2 u3 u4 v1 v2 v3 v4]'
楼主,对于你这个,我指出点问题,你看看是不是应该这样
x=[u1 u2 u3 u4 -v1 -v2 -v3 -v4]'
该用户从未签到
按照方法2，运行结果为如下：
x=[ 0.2500& & 0.0000& & 0.2500& & 0.0000& & 0.2500& & 0.0000& & 0.2500& & 0.0000];
将其带入约束条件，结果不对啊。
按照3楼的方法修改运行结果如下：
x=[ 0.2500& & 0.0000& & 0.0000& & 0.0000& & 0.0000& & 0.0000& & 0.0000& & 0.2500];
感觉3楼的建议x=[u1 u2 u3 u4 -v1 -v2 -v3 -v4]';应该是正确的，将其带入约束条件，结果也不对啊。
期待高手。方法1运行可以。
该用户从未签到
这种问题用1stOpt很简单啊：
Algorithm = DE1;
minfunction abs(x1)+2*abs(x2)+3*abs(x3)+4*abs(x4);
x1-x2-x3+x4=0;
x1-x2+x3-3*x4=1;
x1-x2-2*x3+3*x4=-0.5;
复制代码结果：
目标函数值(最小): 1.25
x2: -1.49E-16
x3: 1.43E-18
& &1: x1-x2-x3+x4-(0) = 0
& &2: x1-x2+x3-3*x4-(1) = 0
& &3: x1-x2-2*x3+3*x4-(-0.5) = 0
签到天数: 13 天[LV.3]偶尔看看II
新手上路，有空来下载的
这歌我收了！谢谢楼主！
MATLAB技术论坛太棒了！
网站官方，，，保证您有偿编程安全。
签到天数: 1 天[LV.1]初来乍到
本帖最后由 luu 于
17:51 编辑
借用二楼方法二
改动如下：
min z=[1 2 3 4 1 2 3 4]*[u1 u2 u3 u4 v1 v2 v3 v4]'
Aeq=[A -A]b=[0 1 -0.5]'
x=[u1 u2 u3 u4 v1 v2 v3 v4]'
matlab如下:
f=[1 2 3 4 1 2 3 4];
A=[1 -1 -1 1
& & 1 -1 1 -3
& & 1 -1 -2 3];
Aeq=[A -A];
beq=[0 1 -0.5]';
lb=zeros(8,1);
x=linprog(f,[],[],Aeq,beq,lb);
签到天数: 340 天[LV.8]以坛为家I
恩恩.第二个只要把A改了就对了~~学习了~~~~~``
网站官方，，，保证您有偿编程安全。
签到天数: 340 天[LV.8]以坛为家I
好帖~~学习了~~~~~~~~~~~~~~
该用户从未签到
很好很强大，学习了！
网站官方，，，保证您有偿编程安全。
Powered by