求用动态规划的方法求解简单的整数规划问题的matlab程序或者C++程序代码，高手们帮帮忙

max Z=4x1+5x2 +6x3

st 3x1+4x2+5x3<=10

x1,x2,x3>=0且都为整数

约束条件分析：

x1=1,2,3

x2=1,2

x3=1,2

阶段变量：x1、x2、x3

状态变量：

决策变量：

目标函数：Z=4x1+5x2 +6x3

状态转移方程：

约束条件用惩罚处理

……未完待续……

matlab的整数规划功能最差，没有现成的函数，都是自己编的。

例如：求100以内能被13整除的数，用round函数来判断。

n=0;

for

k=1:100

if

k/13==round(k/13)

n=n+1;

m(n)=k;

end

end

[1:n;m]

运行结果：

ans

=

1

2

3

4

5

6

7

13

26

39

52

65

78

91

最近，有很多同行问我在Matlab中怎样求解（混合）整数规划问题，我这里就说一下我所知道的情况。

Matlab 7的优化工具包只能求解0-1变量的（逻辑）整数规划问题，要解一般的整数规划问题，推荐下载一个免费的，叫做LP_SOLVE的软件，支持Matlab,在yahoo讨论组里有下载。

解压后，里面有个文件夹，将其命名为"lp_solve",建议将这个文件夹拷贝到matlab程序文件夹中的toolbox文件夹中，在lp_solve文件夹里面有个lpsolve55dll文件，将其拷贝到系统文件夹%system32中，然后启动matlab，在file菜单里点击setpath,将%MATLAB701/toolbox/lp_solve 路径添为默认路径，现在就可以直接使用lp_solve文件夹里面的函数了。

为了根方便地使用各种优化软件，尤其是lp_solve,我还建议有兴趣的同行再下载一个叫做"Yalmip" 的软件包，同样解压后放在matlab程序文件夹中的toolbox文件夹中，再添加其路径（add with subfolders）。这个软件的重要作用在于使得添加约束条件的过程变得相当方便，例如变量X是一个长度为5的向量，且有约束x1+x2+x3+x4+x5=1,利用Yalmip就可以写成

X=sdpvar(5,1); %定义变量

set(sum(X)==1);%定义约束条件

§3 0 −1型整数规划

0 −1型整数规划是整数规划中的特殊情形，它的变量j x 仅取值0 或1。这时j x 称

为0 −1变量，或称二进制变量。j x 仅取值0 或1 这个条件可由下述约束条件：

0 ≤ ≤ 1 j x ，整数所代替，是和一般整数规划的约束条件形式一致的。在实际问题中，如果引入0 −1变

量，就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们

先介绍引入0 −1变量的实际问题，再研究解法。

如果有m 个互相排斥的约束条件：

a x a x b i m i in n i 1,2, , 1 1 +L+ ≤ = L

为了保证这m 个约束条件只有一个起作用，我们引入m 个0 −1变量y (i 1,2, ,m) i = L

和一个充分大的常数M ，而下面这一组m +1个约束条件

a x a x b y M i m i in n i i 1,2, , 1 1 +L+ ≤ + = L （1）

1 1 y + + y = m − L m （2）

就合于上述的要求。这是因为，由于（2），m 个i y 中只有一个能取0 值，设0 = i y ，

代入（1），就只有i = i的约束条件起作用，而别的式子都是多余的。

32 0 −1型整数规划解法之一（过滤隐枚举法）

解0 −1型整数规划最容易想到的方法，和一般整数规划的情形一样，就是穷举法，

即检查变量取值为0 或1 的每一种组合，比较目标函数值以求得最优解，这就需要检查

变量取值的2n个组合。对于变量个数n较大（例如n >100），这几乎是不可能的。因

此常设计一些方法，只检查变量取值的组合的一部分，就能求到问题的最优解。这样的

方法称为隐枚举法（Implicit Enumeration），分枝定界法也是一种隐枚举法。当然，对有些问题隐枚举法并不适用，所以有时穷举法还是必要的。

蒙特卡洛法（随机取样法）

前面介绍的常用的整数规划求解方法，主要是针对线性整数规划而言，而对于非线

性整数规划目前尚未有一种成熟而准确的求解方法，因为非线性规划本身的通用有效解

法尚未找到，更何况是非线性整数规划。

然而，尽管整数规划由于限制变量为整数而增加了难度；然而又由于整数解是有限

个，于是为枚举法提供了方便。当然，当自变量维数很大和取值范围很宽情况下，企图

用显枚举法（即穷举法）计算出最优值是不现实的，但是应用概率理论可以证明，在一

定的计算量的情况下，完全可以得出一个满意解。

指派问题的计算机求解

整数规划问题的求解可以使用 Lingo 等专用软件。对于一般的整数规划问题，无法

直接利用Matlab 的函数，必须利用Matlab 编程实现分枝定界解法和割平面解法。但对

于指派问题等0 −1整数规划问题，可以直接利用Matlab 的函数bintprog 进行求解。

以上就是关于求用动态规划的方法求解简单的整数规划问题的matlab程序或者C++程序代码，高手们帮帮忙全部的内容，包括:求用动态规划的方法求解简单的整数规划问题的matlab程序或者C++程序代码，高手们帮帮忙、Matlab解决整数规划问题有哪些函数可用请赐教、matlab中NSGA-Ⅱ是否可以求解整数规划等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！