0-1规划的求解
实验类型：◆验证性实验 ◇综合性实验 ◇设计性实验
实验目的：学会使用Matlab编程实现求解0-1规划。
实验内容：1.学习使用Matlab定义子函数的命令function；
2.编程求解0-1型整数规划的枚举法或隐枚举法。
例1：求解下面的0-1型整数规划：
例2：求解下面的0-1型整数规划：
实验原理：
基本思路：
1.给出0-1型整数线性规划所有的可能的解；
2.计算出所有可能解的目标函数值，并从大到小排序；
3.按上面顺序，判断对应的解是否可行（即满足所有约束条件）。
若可行，则为最优解；若不可行，可删去该解，按顺序判断下一位，直至找到
可行解（即为最优解）
用到的子函数：
(function)对应的有面3个：
1.给出所有的可能的解，函数名为y=lingyi(k);
2.计算目标函数值，函数名为z=objfunction(c,x);
3.判断是否可行解，函数名为t=feasible(A,x,b).
0-1整数规划是指决策变量只能取0或1的整数规划问题。枚举法是一种简单但耗时的方法，它尝试列举所有可能的解并计算它们的目标函数值，然后选择最优解。隐枚举法则是一种改进的方法，它在列举过程中剔除了显然不是最优解的部分，从而减少了计算量。
在Matlab中，可以使用循环语句来实现枚举法或隐枚举法。首先，定义目标函数和约束条件。然后，使用循环生成所有可能的解，并计算它们的目标函数值。最后，从中选择最优解。
程序代码：
function z=objfunction(c,x)
z=c*x;
end
function y=lingyi(k)
if k==1
y=[0;1];
else if k>1
lc=2^(k-1);
xinlie1=zeros(lc,1);
xinlie2=ones(lc,1);
xinlie=[xinlie1;xinlie2];
pre_lingyi=lingyi(k-1);
pre_lingyi=[pre_lingyi;pre_lingyi];
y=[xinlie,pre_lingyi];
end
end
end
function t=feasible(A,x,b)
if(A*x-b)<=0
t=1;
else
t=0;
end
end
allsolution=lingyi(n);
z=[];
x=zeros(n,1);
for i=1:2^n
z=[z;objfunction(c,allsolution(i,:)')];
end
[maxx,maxxi]=max(z);
while feasible(A,allsolution(maxxi,:)',b)==0
allsolution(maxxi,:)=[];
z(maxxi,:)=[];
[maxx,maxxi]=max(z);
end
input("编程的最优解为：")
allsolution(maxxi,:)
input("编程的优化值为：")
max(z(maxxi))
运行结果：
例1结果：
例2结果：
实验总结：
这个实验通过使用 Matlab 编程实现了求解 0-1 型整数规划的枚举法。在实验过程中，我学会了如何使用 Matlab 定义子函数、编写循环语句来穷举所有可能的解，并通过约束条件来筛选有效解。通过这个实验，我对整数规划的求解方法有了更深入的理解，也提高了我的编程能力。
在实验中，我遇到了一些挑战，如如何正确定义约束条件和有效地遍历所有可能的解。通过仔细思考和调试，我成功地解决了这些问题，并最终得到了正确的结果。
在今后的学习中，我将继续深入学习和掌握 Matlab 的编程技巧，以及更高级的整数规划算法，以便更好地应用于实际问题的求解中。