Lingo求解0-1整数规划问题（LINGO18.0x64）
案例：有99个数，从中取17个数使它们的和为89.884。
⽤于解决该问题的Lingo代码如下：
1 model:
2 sets:
3 row/1..99/:c,x;
4 endsets
5 data:
6 c=6,6,6,4.56,5.76,2.94,2.1738,0.5723,6,6,3.3,6,3.72,3.6,1.8,2.145,4.785,6,6,6,3,2.85,3.2565,4.776,3.063,3,6,6,6,5.4,5.4,6,3.54,30,30,10,6.3,10,2.34,2.514,6.555,7.8,10,30,5.04,10,6.3,6.075,9.32988,7.2,9,2.7,5.415,10,3.75,1.5,8.1
7 enddata
8 min=@abs(89.884-@sum(row:c*x));
9 @sum(row:x)=17;
10 @for(row:@bin(x));
其中
row/1..99/:c,x; ⽤于定义长度为99的⾏向量c，x
min=@abs(89.884-@sum(row:c*x)); 表⽰选出的数的和为89.884，且该条件作为⽬标函数
@sum(row:x)=17; 表⽰向量x的和为17
@for(row:@bin(x)); ⽤于设定向量x中的元素取值⾮0即1，⽤于0-1整数规划 计算结果部分展⽰如下：
穷举法求解0-1整数规划的matlab程序
（原创）
0-1整数规划有很广泛的应用背景，比如指派问题，背包问题等等，实际上TSP问题也是一个0-1问题，当然这些问题都是NP问题，对于规模较大的问题用穷举法是没有办法在可接受的时间内求得最优解的，本程序只不过是一个练习，得意之处是用递归法把所有解都排列出来。另：胡运权所著的《运筹学基础及应用（第三版）》第97页的例3，我用本程序求解得到的结果是：最优解是x*=(1,0, 0,
0, 0)，最优值是f(x*)=8，但书求得最优解是x*=(1,0, 1, 0, 0)，最优值是f(x*)=4，是不是书中写错了，请大家验证。以下是源程序，大家可以任意使用无版权问题，另外，如果大家有大规模的0-1规划的问题也希望提供给我，谢谢。
%%% 用隐穷举法求解0-1线性规划
%%% min c'x
%%% s.t. Ax<=b
function [y,fval]=qiongju(c,A,b)
guimo=length(c);
suoyoujie=lingyi(guimo);?? % 所有可能解的排列
[m,n]=size(A);
opt_solution=inf; % 解的上界
for i=1:2^guimo
yueshu=A*suoyoujie(i,:)';
for j=1:m
if yueshu(j)>b(j)?? % 不满足某约束条件，则不是解
break;
end
end
if j==m?? % 满足所有约束，则计算该的目标值，并与当前最优解相比较
val=c'*suoyoujie(i,:)';
if val<=opt_solution
opt_solution=val;
y=suoyoujie(i,:);
end
end
end
fval=opt_solution;
function y=lingyi(k)
if k==3
y=[0 0 0;
2.5 0-1规划
在军队管理、作战指挥、计算机辅助决策中常常会碰到一类分配问题，又称指派问题。这是指有m个单位或人去完成，条件是
（1）每项工作只能分配给一个单位或人去完成；
（2）每个单位或人只能接受其中一项工作。
问题是怎样合理分配，才能使总的费用最小或总的效益最高？
例16 我军有1D、2D、3D、4D四个导弹阵地，同时射击地方1A、2A、3A、4A四架敌机。根据敌机来袭方向和阵地位置等，算得每个导弹阵地对各架敌机的击毁概率如表2-21。试给每个导弹阵地分配一架敌机，给每架敌机分配一个导弹阵地，使得对敌机的击毁概率最大。
解：设ijx为问题的决策变量，它只取0，1两种值。我们定义
时。分配给目标当不把阵地时，分配给目标当把阵地jijiijADADx01
i=1,2,3,4； j=1,2,3,4。
得线性规划
444342413433323124232221141212112.08.09.06.08.06.08.04.06.08.06.08.06.04.09.06.0maxxxxxxxxxxxxxxxxxP
表2-21
A1 A2 A3 A4
D1 0.6 0.9 0.4 0.6
D2 0.8 0.6 0.8 0.6
D3 0.4 0.8 0.6 0.8
D4 0.6 0.9 0.8 0.2
约束于 敌
机 击
毁
概
率 导 弹 阵 地
4,3,2,1,4,3,2,1,,1,0111111114434241443332313423222124131211144434241343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxij＋
由于这个规划的决策变量只能取0，1两个值，故这种规划我们也称之为0-1规划。一般来说，指派问题可以化成如下的0-1规划：
0-1规划
0-1规划（Zero-One Programming）是一种最优化问题求解方法。它是一类离散规划问题的特例，通过将问题转化为一个整数规划问题，通过寻找满足一系列约束条件的0-1变量取值，来求解最优解。
0-1规划是一种非常重要的数学模型，可以用来解决许多实际问题。它通常应用于资源分配、项目选择、生产排程等领域。其目标是在满足约束条件的情况下，使得某个目标函数取得最大值或最小值。
在0-1规划中，变量只能取0或1两个值，这种限制使得问题变得更有挑战性。为了将问题转化为0-1规划问题，需要将问题中的决策变量转化为二进制变量，并构建一个合适的目标函数和约束条件。
0-1规划的解决方法主要包括贪婪算法、动态规划和分支定界法等。其中，贪婪算法是最简单、最直观的方法，但不一定能得到最优解；动态规划是一种递推求解的方法，可以解决一些特殊问题；而分支定界法是一种逐步逼近最优解的方法，具有较高的求解精度。
0-1规划的一个经典例子是背包问题。假设有一个背包，容量为W，现在有n个不同重量和价值的物品，需要选择哪些物品放入背包，使得背包中的物品总重量不超过W，同时使得物品的总价值最大化。
对于这个问题，可以将每个物品的选择状态表示为一个0-1变量。如果选择放入背包，变量取值为1；如果不选择放入背包，变量取值为0。然后可以设置目标函数为物品的总价值，约束条件为物品的总重量不超过背包容量。
这个问题可以通过分支定界法求解。首先，将问题分解为一个个子问题，然后通过计算上界和下界，逐步减小解空间。最终可以找到一个近似最优解。
总之，0-1规划是一种重要的最优化问题求解方法。虽然在实际应用中，由于问题的复杂性，往往需要使用更加复杂的算法来求解，但0-1规划的基本思想和方法依然具有广泛的应用。通过合理地构建目标函数和约束条件，可以帮助我们在资源有限的情况下，做出最优的决策。
