0-1规划的隐枚举法.doc_第1页
0-1规划的隐枚举法.doc_第2页
0-1规划的隐枚举法.doc_第3页
0-1规划的隐枚举法.doc_第4页
0-1规划的隐枚举法.doc_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

2013-2014（2）专业课程实践论文题目：0-1规划的隐枚举法 一、算法理论01规划在整数规划中占有重要地位，一方面因为许多实际问题，例如指派问题、选地问题、送货问题都可归结为此类规划，另一方面任何有界变量的整数规划都与01规划等价，用01规划方法还可以把多种非线性规划问题表示成整数规划问题，所以不少人致力于这个方向的研究。求解01规划的常用方法是分枝定界法，对各种特殊问题还有一些特殊方法。线性模型中，当变量的取值只能是“0”或“1”时，称之为“0-1规划问题”。有种极其简单的解法，就是将变量取值为0或1的所有组合列出，然后分别代入目标函数，选出其中能使目标函数最优化的组合，即为最优解。但是真的这样会做很多无用功，浪费大量资源，所以，需要改进方法。本文主要介绍隐枚举法的应用原理，意在剖析其“隐”在何处。从而帮助读者更好地应用这种方法。和线性规划问题一样，首先需要将模型标准化。标准化对0-1规划问题提出四点要求：1.目标函数为最小优化2.目标函数中变量的系数都为正3.在目标函数中，变量按系数值从小到大排列，则约束函数中，变量的排列次序也做相应改变。4.所有变量均为0或10-1线性规划的基本形式是 二、算法框图三、算法程序function intx,intf = ZeroOneprog(c,A,b,x0)%目标函数系数向量，c%不等式约束矩阵，A%不等式约束右端向量，b%初始整数可行解，x0%目标函数取最小值时的自变量值，intx%目标函数的最小值，intf sz = size(A);if sz(2) = b %是否满足约束条件 f_tmp = c*x1; if f_tmp = b f_tmp = c*x1; if f_tmp c=1 2 3 1 1; A=2 3 5 4 7;1 1 4 2 2; b=8;5; x0=1;1;1;1;1; intx,intf=ZeroOneprog(c,A,b,x0)所得结果如下：例2求下面0-1线性规划解：在MATLAB命令框在输入下列命令： c=-3,2,-5; A=-1,-2,1;-1,-4,-1;-1,-1,0;-4,0,-1; b=-2;-4;-3;-6; x0=1;0;0; intx,intf=ZeroOneprog(c,A,b,x0)例3求解下面0-1规划解:在MATLAB命令框在输入下列命令： c=3,7,-1,1;A=2,-1,1,-1;1,-1,6,4;5,3,0,1;b=1;8;5; x0=1;1;1;1; intx,intf=ZeroOneprog(c,A,b,x0)例4求解下面0-1规划解:在MATLAB命令框在输入下列命令： c=-6,-2,-3;A=-1,-2,-1;3,-5,1
人人文库> 全部分类> 行业资料 > 管理策划

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论