﻿功能:0-1整数线性规划

格式:
[minV, x, n] = LineProg01(f, lessa, lessb, equa, equb)
f    : 一个存储最小目标表达式的系数的矩阵变量
lessa: 一个存储小于等于约束系数的矩阵变量,其列数和f中元素个数一致
lessb: 一个存储小于等于约束常数项的矩阵变量,其行数与lessa一致
equa : 一个存储等于约束系数的矩阵变量,其列数和f中元素个数一致
equb : 一个存储等于约束常数项的矩阵变量,其行数与equa一致

minV: 返回的目标最小值
x   : 返回变量的01结果
n   : 程序内部寻找次数

说明:
1. 本函数是求解目标的最小值，即求如下表达式最小值
	f^T * x
	
2. 其中约束满足如下条件
	lessa * x <= lessb
	equa  * x  = equb

3. 如果约束为小于的情况,则直接可把系数放到lessa与lessb中,因为在浮点数计算过程中,存在精度取舍问题,在比较表达式时,程序内部会有一个取舍范围.因此在这里≤与＜的约束,处理成一样的结果

4. 如果约束使得怎么都不满足结果,则程序会返回错误提示.

原理:
1. 对所有系数进行排序, 变量分割, 初步计算等处理
2. 内部根据变量个数采用不同的策略进行计算
3. 当变量个数少于12个时, 采用一种界定方法进行查找, 最坏的情况, 将计算2^m - 1次(这里m为变量个数), 即最终返回的 n = 2^m - 1, 这种情况
4. 当变量个数多余12个时, 内部采用一种优化策略进行求解(使用梯度优化模块的算法进行求解). 求解成功, 返回程序能找到的最佳可行解!

例子:

//求目标函数 z = 20*x1 - 15*x2 - 18*x3 - 14*x4 + 8*x5 + 4*x6 - 10*x7 的最小值，其中满足条件 5*x1-5*x2+2*x3-6*x4-12*x5+2*x6+4*x7<=-10 且 x1,x2,x3,x4,x5,x6,x7 只能为整数0或者1

//下面构建最小目标系数f,这里f当中的系数必须为7个,依次和x1,x2,x3,x4,x5,x6,x7对应
//同样的，构建的约束a的列数也必须为7个,系数依次和x1,x2,x3,x4,x5,x6,x7对应
f = [20 -15 -18 -14 8 4 -10];
a = [5 -5 2 -6 -12 2 4];
b = [-10];
[s, x, n] = LineProg01(f, a, b)//回车得到如下结果,可以发现最小目标为-49, 然后结果为x, 总寻找次数为3
s =
[-49.0000000000000 ]
x =
[ 0.00000000000000
  1.00000000000000
  1.00000000000000
  1.00000000000000
  1.00000000000000
  0.00000000000000
  1.00000000000000 ]
n =
[ 3.00000000000000 ]