Algorithm assignment 1

2020-12-10

一、用动态规划方法手工求解下面的问题:

某工厂调查了解市场情况,估计在今后四个月内,市场对其产品的需求量如下表所示。

时期(月) 需要量(产品单位)
1 2
2 3
3 2
4 4

已知:对每个月来讲,生产一批产品的固定成本费为3 (千元),若不生产,则为零。每生产单位产品的成本费为1 (千元)。同时,在任何一个月内,生产能力所允许的最大生产批量为不超过6 个单位。又知每单位产品的库存费用为每月0.5 (千元),同时要求在第一个月开始之初, 及在第四个月末,均无产品库存。

问:在满足上述条件下,该厂应如何安排各个时期的生产与库存,使所花的总成本费用最低?

要求:写出各种变量、状态转移方程、递推关系式、和详细计算步骤。


该题既可以顺推也可以逆推,但逆推的手工计算量较小。因此这里用逆推的方式求解。

  • 变量描述:设\(n\) 为总月份,\(w_i\) 代表第\(i\)个月的需求量,\(u_i\) 代表第\(i\)个月的产量,生产固定成本\(c_1=3\) ,生产单位产品成本费\(c_2=1\) ,单位产品的库存费\(c_3=0.5\) ,单月最大生产量\(max_p=6\)

  • 状态转移方程

    \(s_i\)为第i个月的库存,则\(s_{i+1}=s_i + u_i - w_i\),且\(s_i \geq 0\)\(0 \leq u_i \leq max_p\)

    \(v_i\)为第i个月的花费,则\(v_i = c_3s_i+\begin{cases}c_2u_i+c_1&,&u_i>0\\0&,&u_i=0\end{cases}\)

    \(f_i(s_i)\)为第i个月后,库存为\(s_i\)的最小成本,则

    \[f_i(s_i)=min_{u_i}\{{v_i + f_{i + 1}(s_{i+1})}\} \]

    最终所求为\(f_1(0)\)

  • 递推关系式

    \[\begin{cases} f_n(0)=0\\ f_i(s_j)=min_{u_i}\{v_i+f_{i+1}(s_k)\} \end{cases} \]

  • 计算步骤

    由题知,所求\(n = 4; w = \{2,3,2,4\}\),所以有\(u_4=s_5-s_4+w_4=4-s_4\),即\(0 \leq s_4 \leq 4\)

    \[f_4(s_4)=min_{u_4}\{v_4+f_{5}(0)\}=min_{u_4}\{0.5 * s_4+\begin{cases}1 * u_4+3&,&u_4>0\\0&,&u_4=0\end{cases}\} \implies \begin{cases} f_4(0)=7&,&u_4=4\\ f_4(1)=6.5&,&u_4=3\\ f_4(2)=6&,&u_4=2\\ f_4(3)=5.5&,&u_4=1\\ f_4(4)=2&,&u_4=0\\ \end{cases} \]

    所以有\(u_3=s_4-s_3+w_3\),即\(0 \leq s_3 \leq 6\)

    \[f_3(s_3)=min_{u_3}\{v_3+f_{4}(s_4)\}=min_{u_3}\{0.5 * s_3+\begin{cases}1 * u_3+3&,&u_3>0\\0&,&u_3=0\end{cases}\} \implies \begin{cases} f_3(0)=11&,&u_3=6\\ f_3(1)=10.5&,&u_3=6\\ f_3(2)=8&,&u_3=0\\ f_3(3)=8&,&u_3=0\\ f_3(4)=8&,&u_3=0\\ f_3(5)=8&,&u_3=0\\ f_3(6)=5&,&u_3=0\\ \end{cases} \]

    所以有\(u_2=s_3-s_2+w_2\),即\(0 \leq s_2 \leq 9\)

    \[f_2(s_2)=min_{u_2}\{v_2+f_{3}(s_3)\}=min_{u_2}\{0.5 * s_2+\begin{cases}1 * u_2+3&,&u_2>0\\0&,&u_2=0\end{cases}\} \implies \begin{cases} f_2(0)=16&,&u_2=5\\ f_2(1)=15.5&,&u_2=4\\ f_2(2)=15&,&u_2=3\\ f_2(3)=12.5&,&u_2=0\\ f_2(4)=12.5&,&u_2=0\\ f_2(5)=10.5&,&u_2=0\\ f_2(6)=11&,&u_2=0\\ f_2(7)=11.5&,&u_2=0\\ f_2(8)=12&,&u_2=0\\ f_2(9)=9.5&,&u_2=0\\ \end{cases} \]

    \(s_1 = 0\)\(u_1=s_2 - s_1 + w_1\)

    \[f_1(s_1)=min_{u_1}\{v_1+f_{2}(s_2)\}=min_{u_1}\{0.5s_1+\begin{cases}1 * u_1+3&,&u_1>0\\0&,&u_1=0\end{cases}\} \implies f_1(0)=20.5,u_1=5 \]

    \(u=[5,0,6,0]\)\(s = [0,3,0,4]\),即4个月分别生产5、0、6、0单位产品,各月库存量分别为0、3、0、4,总成本最低为\(f_1(0)=20.5\)

二、用动态规划方法编程求解下面的问题:

某推销员要从城市\(v_1\) 出发,访问其它城市\(v_2,v_3,…,v_6\) 各一次且仅一次,最后返回\(v_1\)。D为各城市间的距离矩阵。

\[D= \begin{matrix} v_1 \\ v_2 \\ v_3 \\ v_4 \\ v_5 \\ v_6 \end{matrix} \begin{bmatrix} 0 & 10 & 20 & 30 & 40 & 50\\ 12 & 0 & 18 & 30 & 25 & 21\\ 23 & 19 & 0 & 5 & 10 & 15 \\ 34 & 32 & 4 & 0 & 8 & 16 \\ 45 & 27 & 11 & 10 & 0 & 18 \\ 56 & 22 & 16 & 20 & 12 & 0 \end{bmatrix} \]

问:该推销员应如何选择路线,才能使总的行程最短?

要求:写出递推关系式、伪代码和程序相关说明,并分析时间复杂性。 (请遵守第一节课提出的有关 assignment 的要求)


  • 变量描述:记城市数量\(n=6\),城市编号为\(0,1,2,\dots,n-1\),距离矩阵为\(D\)

  • 状态转移方程:设\(f_{i,S}\)代表推销员走到第i个城市,已经访问过的城市集合为S,则

    \[f_{i,S}=min\{f_{j,S-\{i\}}+D_{j,i}\} \]

  • 递推关系式:初始时S为空,\(f_{i,S}=0\)

    \[\begin{cases} f_{i,S}=0\\ f_{i,S}=min\{f_{j,S-\{i\}}+D_{j,i}\} \end{cases} \]

  • 伪代码

    func TSP(n, D){
    	// Input: n城市数量,D为距离矩阵下标从0开始
    	// Output: 一个数,代表从v1=0出发,最后回到v1的最小距离
    	初始化f为INF
    	将v1添加进集合S,此时f[i][S]=0
    	从{v1}开始枚举集合S的状态
    		枚举第i个城市是否在集合内,如果在
    			枚举不在集合内的第j个城市
    				将j加入集合S记为S‘,此时花费为f[i][S] + D[i][j]
    				记f[j][S']=min{f[j][S'], f[i][S] + D[i][j]}
    	则得到f[i][S]为从0出发,最后集合状态为S的最小
    	最后加上从最后经过的城市返回v1的距离,输出答案
    }
    
  • 时间复杂度\(O(n^2*2^n)\)

  • 附程序代码

    #include<iostream>
    #include<cstring>
    using namespace std;
    #define INF 0x3f3f3f3f
    const int n = 6;
    const int D[6][6]={
        {0,10,20,30,40,50},
        {12,0,18,30,25,21},
        {23,19,0,5,10,15},
        {34,32,4,0,8,16},
        {45,27,11,10,0,18},
        {56,22,16,20,12,0}
    };
    int f[10][1024];
    int main() 
    {
        memset(f, INF, sizeof(f));
        f[0][1] = 0;
        int tot = (1 << n) - 1;
        for (int s = 1; s <= tot; s++) {
            for (int i = 0; i < n; i++) {
                if ((s >> i & 1 == 0) || (f[i][s] == INF)) continue;
                for (int j = 0; j < n; j++) if ((s >> j & 1) == 0)
                    f[j][s | 1 << j] = min(f[j][s | 1 << j], f[i][s] + D[i][j]);
            }
        }
        int ans = INF;
        for (int i = 0; i < n; i++) if (f[i][tot] < INF)
            ans = min(ans, f[i][tot] + D[i][0]);
        cout << ans << endl; 
    }