流网络—最大流问题（Maximum-flow problem）
image.png
希望从0-7找到最大值，管道可以承载的最大值。
那么目标函数是objective：maximize X01+X02+X03
条件s.t.:
image.png
然后首先判断目标函数是什么类型？
该目标函数是linear programming
所以使用linear programming solver
如何求出最优解呢？
scipy
Set Cover Problem (集合覆盖问题)
假设我们有个全集U (Universal Set), 以及m个⼦子集合
𝑆1 ,𝑆2 …,𝑆m, 目标是要寻找最少的集合，使得集合的union等于U
例子： U = {1,2,3,4,5}, S: {𝑆 W ={1,2,3}, 𝑆 X ={2,4}, 𝑆 Y ={1,3},
𝑆 Z ={4}, 𝑆 [ ={3,4}, 𝑆 Ý ={4,5}}, 最少的集合为：{1,2,3}, {4,5}，集
合个数为2。
1、穷举法
从小集合一个个不断组合，找到满足条件则结束。穷举法可以找到最优解
image.png
2、贪心算法
从左到右判断，删掉第一个，后面等不等于U,不等于就进行下一个判断，如此循环，直到找到不能去掉的时候就是最优解，但是这个不能保证是全局最优，就下图所示就不是最优解。
image.png
3、优化算法求解
1、首先设计目标函数，根据对于集合来讲，就是选跟不选，那么可以设计目标函数为
条件 s.t. xi∈{0,1}
image.png
那么我们首先判断函数类别，该函数是否凸函数
因其定义域是是0和1，所以选择任意两个点，连成的线都有没有在其区域内的，所以是个非凸函数。
image.png
那如果这样子，很难求解，能不能relaxation，把目标函数的定义域变成一个连续数据，linear
然后再对求的的x进行一个区域性判断，假如大于0.5，赋值其为1，小于等于0.5则赋值为0
