运筹学外点法

（一） 实验目的

熟练掌握外点法、内点法原理并可以在matlab 熟练运行。

（二） 问题描述

目标函数：z =min x 1+x 2

s.t. –x 21+x 2≥0

x 1≥0

(三) 算法介绍

外点法： 对于混合约束问题 min f(x)

s.t. s i x ≥0, i =1:m

h j x =0, i =1:n

可以转化为：

min F(x,σ)=f(x)+ σ([max{0,− s

21 x }]2+ max 0, − s2 x 2+…

+ max 0, − sm x 2+ h1 x +h 2 x 2+⋯+h n x 2) = f(x)+ σ( m i=1[max{0,− sm x }]2+ n j=1h 2j

其中，P(x)= m i=1 max 0, − sm x 2+ n j=1h 2j

F(x,σ) ：增广目标函数

P(x)：惩罚函数 ，σ：罚因子

外部惩罚函数法迭代步骤：

给定初始点x 0，初始惩罚因子σ1，放大系数c>1，ε>0置k:=1

Step1：以x k −1为初始点求解min F（x, σk ）得极小点x k

Step2：若σk P x k

Step3：σk+1=c σk ，置k ≔k +1转step1

注意外点法在选取初始点时要选取在可行域外的点。

在本问题中x 0 =[-1;-1],c=10，ε=0.01，σ1=1

内点法：这种解法只能用于不等式

对于约束问题 min f(x)

s.t. s i x ≥0, i =1:m

可以转化为：

min F(x,σ)=f(x)+μ（1

s 1 x +1

s 2 x +⋯+1

s m x ） …

其中μ为一个小正数

内部惩罚函数法迭代步骤：

已知f(x), si x , 取β x =s 11 x +s 12 x +⋯+s 1m x

给定初始点x 0，初始惩罚因子μ1，放大系数1>c>0，ε>0置k:=1

Step1：以x k −1为初始点求解min F（x, μk ）得极小点x k

Step2：若μk P x k

Step3：μk =c μk ，置k ≔k +1转step1

在本问题中x 0 =[0.03;0.03],c=0.2，ε=0.001，μ1=0.1

注意内点法在选取初始点时要选取在可行域内的点。

其中以xk−1为初始点求解min F （x, σk）得极小点xk的求解过程我们利用最速下降法得到

（四）程序代码及运行结果：

（1）外点法源程序代码：

function f=again(x,c,e)

syms x1 x2 t

a=1;

f=x1+x2;

y1=-x1^2+x2;

y2=x1;

y1=-subs(y1,{x1,x2},x);

y2=-subs(y2,{x1,x2},x) ;

P=(max(0,double(y1)))^2+(max(0,double(y2)))^2;

if double(y1)>0&&double(y2)>0

y11=-x1^2+x2;

y22=x1;

end

if double(y1)0

y11=0;

y22=x1;

end

if double(y2)0

y11=-x1^2+x2;

y22=0;

end

FF=f+a*(y11^2+y22^2) ;

a1=diff(FF,x1);

b1=diff(FF,x2);

a1=subs(a1,{x1,x2},x);

b1=subs(b1,{x1,x2},x);

g=[a1;b1];

d=-g;

while P*a>e

while double(sqrt(a1^2+b1^2))>0.5

x=x+t*d;

FF=subs(FF,{x1,x2},x);

f1=diff(FF);

f1=solve(f1);

if f1~=0

ti=double(f1);

else

break

end

x=subs(x,t,ti(1,1));

FF=f+a*(y11^2+y22^2);

a11=diff(FF,x1);

b11=diff(FF,x2);

a11=subs(a11,{x1,x2},x);

b11=subs(b11,{x1,x2},x);

g11=[a11;b11];

d=-g11;

a1=a11;

b1=b11;

end

a=a*c;

y1=-x1^2+x2;

y2=x1;

y1=-subs(y1,{x1,x2},x);

y2=-subs(y2,{x1,x2},x) ;

P=(max(0,double(y1)))^2+(max(0,double(y2)))^2;

if double(y1)>0&&double(y2)>0

y11=-x1^2+x2;

y22=x1;

end

if double(y1)0

y11=0;

y22=x1;

end

if double(y2)0

y11=-x1^2+x2;

y22=0;

end

FF=f+a*(y11^2+y22^2) ;

a1=diff(FF,x1);

b1=diff(FF,x2);

a1=subs(a1,{x1,x2},x);

b1=subs(b1,{x1,x2},x);

g=[a1;b1];

d=-g;

end

x,a

（2）在matlab 对话框中输入again([-1;-1],10,0.01)， 外点法得到结果为 ：

x =

1.0e-003 *

-0.4673

-0.5140

a =

10000

其中a 为惩罚因子。

（3）内点法源程序代码：

function f=neidian(x,c,e)

syms x1 x2 t

a=0.1;

f=x1+x2;

y1=-x1^2+x2;

y2=x1;

FF=f+a*((1/(y1))+(1/(y2)) ) ;

a1=diff(FF,x1);

b1=diff(FF,x2);

a1=subs(a1,{x1,x2},x);

b1=subs(b1,{x1,x2},x);

g=[a1;b1];

d=-g;

y1=subs(y1,{x1,x2},x);

y2=subs(y2,{x1,x2},x) ;

P=1/double((y1))+1/double((y2));

while P*a>e

while double(sqrt(a1^2+b1^2))>0.5

x=x+t*d;

FF=subs(FF,{x1,x2},x);

f1=diff(FF);

f1=solve(f1);

if f1~=0

ti=double(f1);

else

break

end

x=subs(x,t,ti(1,1));

y1=-x1^2+x2;

y2=x1;

FF=f+a*((1/(y1))+(1/(y2)) ) ;

a11=diff(FF,x1);

b11=diff(FF,x2);

a11=subs(a11,{x1,x2},x);

b11=subs(b11,{x1,x2},x);

g11=[a11;b11];

d=-g11;

a1=a11;

b1=b11;

end

a=a*c;

y1=-x1^2+x2;

y2=x1;

FF=f+a*((1/(y1))+(1/(y2)) ) ;

a1=diff(FF,x1);

b1=diff(FF,x2);

a1=subs(a1,{x1,x2},x);

b1=subs(b1,{x1,x2},x);

g=[a1;b1];

d=-g;

y1=subs(y1,{x1,x2},x);

y2=subs(y2,{x1,x2},x) ;

P=1/double(y1)+1/double(y2);

end

x,a

（4）在matlab 对话框中输入

neidian([0.03;0.03],0.2,0.001)，

内点法得到结果为 ：

x =

0.0010

0.0013

a =

2.5600e-007

（六）结果分析

本题理论算法的最优解为min=0，x 1=0，x 2=0；但在matlab 上运行不能得到理想解，但经过多步迭代我们已经得到了一个非常接近于最优解的值。如果想得到更接近的最优解可通过减小ε的值使迭代步数增加。

（七）心得体会

外点法的求解过程中会遇到max 这一函数，但是由于max 函数中与0比较的函数含有未知量，无法进行比较因此在每次循环前先赋值比较在利用if 条件语句重新得到P(x)，而这一过程的获得需要我们在编程之初就进行考虑，否则问题多多。

同时，由于我们在本题中进行了循环嵌套，内层循环是利用最速下降法求解每一步的极小点x k ，外层循环是惩罚函数精度的限制，因此在每一步内层循环结束后函数的重新赋值需要弄明白否则会发生很多错误。

对于内点法体会最深的一点就是初始点，惩罚因子，以及精度选择很重要，选择不当将会导致程序运行出错。

（一） 实验目的

熟练掌握外点法、内点法原理并可以在matlab 熟练运行。

（二） 问题描述

目标函数：z =min x 1+x 2

s.t. –x 21+x 2≥0

x 1≥0

(三) 算法介绍

外点法： 对于混合约束问题 min f(x)

s.t. s i x ≥0, i =1:m

h j x =0, i =1:n

可以转化为：

min F(x,σ)=f(x)+ σ([max{0,− s

21 x }]2+ max 0, − s2 x 2+…

+ max 0, − sm x 2+ h1 x +h 2 x 2+⋯+h n x 2) = f(x)+ σ( m i=1[max{0,− sm x }]2+ n j=1h 2j

其中，P(x)= m i=1 max 0, − sm x 2+ n j=1h 2j

F(x,σ) ：增广目标函数

P(x)：惩罚函数 ，σ：罚因子

外部惩罚函数法迭代步骤：

给定初始点x 0，初始惩罚因子σ1，放大系数c>1，ε>0置k:=1

Step1：以x k −1为初始点求解min F（x, σk ）得极小点x k

Step2：若σk P x k

Step3：σk+1=c σk ，置k ≔k +1转step1

注意外点法在选取初始点时要选取在可行域外的点。

在本问题中x 0 =[-1;-1],c=10，ε=0.01，σ1=1

内点法：这种解法只能用于不等式

对于约束问题 min f(x)

s.t. s i x ≥0, i =1:m

可以转化为：

min F(x,σ)=f(x)+μ（1

s 1 x +1

s 2 x +⋯+1

s m x ） …

其中μ为一个小正数

内部惩罚函数法迭代步骤：

已知f(x), si x , 取β x =s 11 x +s 12 x +⋯+s 1m x

给定初始点x 0，初始惩罚因子μ1，放大系数1>c>0，ε>0置k:=1

Step1：以x k −1为初始点求解min F（x, μk ）得极小点x k

Step2：若μk P x k

Step3：μk =c μk ，置k ≔k +1转step1

在本问题中x 0 =[0.03;0.03],c=0.2，ε=0.001，μ1=0.1

注意内点法在选取初始点时要选取在可行域内的点。

其中以xk−1为初始点求解min F （x, σk）得极小点xk的求解过程我们利用最速下降法得到

（四）程序代码及运行结果：

（1）外点法源程序代码：

function f=again(x,c,e)

syms x1 x2 t

a=1;

f=x1+x2;

y1=-x1^2+x2;

y2=x1;

y1=-subs(y1,{x1,x2},x);

y2=-subs(y2,{x1,x2},x) ;

P=(max(0,double(y1)))^2+(max(0,double(y2)))^2;

if double(y1)>0&&double(y2)>0

y11=-x1^2+x2;

y22=x1;

end

if double(y1)0

y11=0;

y22=x1;

end

if double(y2)0

y11=-x1^2+x2;

y22=0;

end

FF=f+a*(y11^2+y22^2) ;

a1=diff(FF,x1);

b1=diff(FF,x2);

a1=subs(a1,{x1,x2},x);

b1=subs(b1,{x1,x2},x);

g=[a1;b1];

d=-g;

while P*a>e

while double(sqrt(a1^2+b1^2))>0.5

x=x+t*d;

FF=subs(FF,{x1,x2},x);

f1=diff(FF);

f1=solve(f1);

if f1~=0

ti=double(f1);

else

break

end

x=subs(x,t,ti(1,1));

FF=f+a*(y11^2+y22^2);

a11=diff(FF,x1);

b11=diff(FF,x2);

a11=subs(a11,{x1,x2},x);

b11=subs(b11,{x1,x2},x);

g11=[a11;b11];

d=-g11;

a1=a11;

b1=b11;

end

a=a*c;

y1=-x1^2+x2;

y2=x1;

y1=-subs(y1,{x1,x2},x);

y2=-subs(y2,{x1,x2},x) ;

P=(max(0,double(y1)))^2+(max(0,double(y2)))^2;

if double(y1)>0&&double(y2)>0

y11=-x1^2+x2;

y22=x1;

end

if double(y1)0

y11=0;

y22=x1;

end

if double(y2)0

y11=-x1^2+x2;

y22=0;

end

FF=f+a*(y11^2+y22^2) ;

a1=diff(FF,x1);

b1=diff(FF,x2);

a1=subs(a1,{x1,x2},x);

b1=subs(b1,{x1,x2},x);

g=[a1;b1];

d=-g;

end

x,a

（2）在matlab 对话框中输入again([-1;-1],10,0.01)， 外点法得到结果为 ：

x =

1.0e-003 *

-0.4673

-0.5140

a =

10000

其中a 为惩罚因子。

（3）内点法源程序代码：

function f=neidian(x,c,e)

syms x1 x2 t

a=0.1;

f=x1+x2;

y1=-x1^2+x2;

y2=x1;

FF=f+a*((1/(y1))+(1/(y2)) ) ;

a1=diff(FF,x1);

b1=diff(FF,x2);

a1=subs(a1,{x1,x2},x);

b1=subs(b1,{x1,x2},x);

g=[a1;b1];

d=-g;

y1=subs(y1,{x1,x2},x);

y2=subs(y2,{x1,x2},x) ;

P=1/double((y1))+1/double((y2));

while P*a>e

while double(sqrt(a1^2+b1^2))>0.5

x=x+t*d;

FF=subs(FF,{x1,x2},x);

f1=diff(FF);

f1=solve(f1);

if f1~=0

ti=double(f1);

else

break

end

x=subs(x,t,ti(1,1));

y1=-x1^2+x2;

y2=x1;

FF=f+a*((1/(y1))+(1/(y2)) ) ;

a11=diff(FF,x1);

b11=diff(FF,x2);

a11=subs(a11,{x1,x2},x);

b11=subs(b11,{x1,x2},x);

g11=[a11;b11];

d=-g11;

a1=a11;

b1=b11;

end

a=a*c;

y1=-x1^2+x2;

y2=x1;

FF=f+a*((1/(y1))+(1/(y2)) ) ;

a1=diff(FF,x1);

b1=diff(FF,x2);

a1=subs(a1,{x1,x2},x);

b1=subs(b1,{x1,x2},x);

g=[a1;b1];

d=-g;

y1=subs(y1,{x1,x2},x);

y2=subs(y2,{x1,x2},x) ;

P=1/double(y1)+1/double(y2);

end

x,a

（4）在matlab 对话框中输入

neidian([0.03;0.03],0.2,0.001)，

内点法得到结果为 ：

x =

0.0010

0.0013

a =

2.5600e-007

（六）结果分析

本题理论算法的最优解为min=0，x 1=0，x 2=0；但在matlab 上运行不能得到理想解，但经过多步迭代我们已经得到了一个非常接近于最优解的值。如果想得到更接近的最优解可通过减小ε的值使迭代步数增加。

（七）心得体会

外点法的求解过程中会遇到max 这一函数，但是由于max 函数中与0比较的函数含有未知量，无法进行比较因此在每次循环前先赋值比较在利用if 条件语句重新得到P(x)，而这一过程的获得需要我们在编程之初就进行考虑，否则问题多多。

同时，由于我们在本题中进行了循环嵌套，内层循环是利用最速下降法求解每一步的极小点x k ，外层循环是惩罚函数精度的限制，因此在每一步内层循环结束后函数的重新赋值需要弄明白否则会发生很多错误。

对于内点法体会最深的一点就是初始点，惩罚因子，以及精度选择很重要，选择不当将会导致程序运行出错。


相关文章

  • 运筹学的产生历史和发展现状

    • 运筹学的产生历史和发展现状 摘要 运筹学是包含多种学科的综合性学科,是最早形成的一门软科学.它把科学 的方法.技术和工具应用到包括一个系统管理在内的各种问题上,以便为那些掌 管系统的人们提供最佳的解决问题的办法.它用科学的方法研究与某一系统 ...查看


  • 华北理工大学工业工程运筹学文献综述

    • 1.运筹学发展史 运筹学是二战以后发展起来的一门新兴的应用学科,它运用分析. 试验. 量化的方法对人. 物. 财等有限资源进行统筹安排,为管理人员做决策提供科学的依据,以实现最有效的管理.20世纪50年代中期钱学森. 许国志等教授将运筹学由 ...查看


  • [军事运筹学]百科名片

    • 军事运筹学 求助编辑百科名片 军事运筹学是应用数学工具和现代计算技术对军事问题进行定量分析,为决策提供数量依据的一种科学方法.它是一门综合性应用学科,是现代军事科学的组成部分.解决现代条件下国防建设和军事活动中一系列复杂的指挥控制问题,不但 ...查看


  • 工业工程专业英语翻译 运筹学

    • 运筹学 英国运筹学协会将运筹学定义如下: 运筹学是一种在工业.商业.政治和国防等领域,对大规模的人.机器.物料和资金这些复杂问题所提出的指导和管理的现代科学模式.它的独特之处在于先建立一个有关该系统的科学模型,综合考量诸如机会和风险等相关因 ...查看


  • 战争中的数学应用

    • 战争中的数学应用 2010-5-22 16:23:16 [字体大小:大 中 小] 一.方程在海湾战争中的应用 1991年海湾战争时,有一个问题放在美军计划人员面前,如果伊拉克把科威特的油井全部烧掉,那么冲天的黑烟会造成严重的后果,这还不只是 ...查看


  • 运筹学及其在卫生管理中的作用论文

    • 运筹学及其在卫生管理中的作用论文 运筹学及其在卫生管理中的作用 关键词:卫生管理.作用.运筹模型.现状.前景 摘要:在卫生事业管理中,随着卫生服务规模的扩大,卫生资源需求的增加,要求卫生服务经济投入越来越多,而政府财政难以满足所有的卫生需求 ...查看


  • 运筹学感想

    • 学习<运筹学>有感 进入大学之后,才听闻有运筹学这门课程,实属孤陋寡闻.若要谈对这门课程最初的印象,便不得不提起运筹帷幄这个成语.所谓运筹帷幄,原指在营帐中谋划制定作战的方法策略."夫运筹帷幄之中:决胜于千里之外:吾不 ...查看


  • 管理运筹学教学大纲

    • 2013年下学期 <管理运筹学>课程教学大纲 1 <管理运筹学>课程教学大纲 一.本课程教学目的和课程性质 本课程是为管理科学与工程类本科生开设的专业理论基础必修课.运筹学是管理科学的重要分支.通过本课程的学习目的是 ...查看


  • 运筹学论文. 1

    • 知识经济条件下,经济发展中的知识含量高,对过去一直贯穿和渗透于农业和工业经济中的知识的作用就凸显得日益突出,知识经济时代的到来,是知识成为社会的主要财富,知识和信息逐步成为与人力.资金并列的企业第三大"战略资源".因此, ...查看


  • 对物流运筹学的认识

    • 物流102 30号 罗勇峰 我对物流运筹学的认识 运筹帷幄之中,决胜千里之外!这就是古代运筹学应用于军事的上奇妙之处.现在,运筹学广泛地运用于人们的生活生产中,取得的非常大的经济效益,我们作为将来的物流人,有必要掌握物流运筹学,将来创造性地 ...查看


热门内容