流網(wǎng)絡(luò)—最大流問題（Maximum-flow problem）

image.png

希望從0-7找到最大值，管道可以承載的最大值。

那么目標(biāo)函數(shù)是objective：maximize X01+X02+X03
條件s.t.:

image.png

然后首先判斷目標(biāo)函數(shù)是什么類型？
該目標(biāo)函數(shù)是linear programming
所以使用linear programming solver

如何求出最優(yōu)解呢？

scipy

Set Cover Problem (集合覆蓋問題)

假設(shè)我們有個(gè)全集U (Universal Set), 以及m個(gè)?子集合
??1 ,??2 …,??m, 目標(biāo)是要尋找最少的集合，使得集合的union等于U

例子： U = {1,2,3,4,5}, S: {?? W ={1,2,3}, ?? X ={2,4}, ?? Y ={1,3},
?? Z ={4}, ?? [ ={3,4}, ?? Y ={4,5}}, 最少的集合為：{1,2,3}, {4,5}，集
合個(gè)數(shù)為2。

1、窮舉法
從小集合一個(gè)個(gè)不斷組合，找到滿足條件則結(jié)束。窮舉法可以找到最優(yōu)解

image.png

2、貪心算法
從左到右判斷，刪掉第一個(gè)，后面等不等于U,不等于就進(jìn)行下一個(gè)判斷，如此循環(huán)，直到找到不能去掉的時(shí)候就是最優(yōu)解，但是這個(gè)不能保證是全局最優(yōu)，就下圖所示就不是最優(yōu)解。

image.png

3、優(yōu)化算法求解
1、首先設(shè)計(jì)目標(biāo)函數(shù)，根據(jù)對(duì)于集合來講，就是選跟不選，那么可以設(shè)計(jì)目標(biāo)函數(shù)為

條件 s.t. xi∈{0,1}

image.png

那么我們首先判斷函數(shù)類別，該函數(shù)是否凸函數(shù)
因其定義域是是0和1，所以選擇任意兩個(gè)點(diǎn)，連成的線都有沒有在其區(qū)域內(nèi)的，所以是個(gè)非凸函數(shù)。

image.png

非凸函數(shù)一般要換一種思維去解決，比如跟上面一樣轉(zhuǎn)換為凸函數(shù)，然后決策去判斷。