生产管理： Wagner

生产管理： Wagner"/>

生产管理： Wagner

Wagner-Whitin算法在1958年提出，用来解决单产品、无能力约束的多阶段批量生产问题（ULSP，uncapacitated lot sizing problem），论文的发表在Management Science上，论文地址：=-cTlYuzABxpcyxK1bP0o_CMa02MfLQvJkk7dWuLmpm3pD9vjTx7odQYMfFBHENTksywxAmQ3lmEgyG-Px2VF5Z08Sl-h103BlHVnmI0NuyK

该算法运用了动态规划的思想，计算复杂度为：

O(n^2)

该算法是一个多项式时间算法。论文首先证明了最优解满足两个性质：
（1）只有当库存为0时补货才是最优的。
（2）对于j期间的需求D(j)，假设提前m期订购，那么这个m有一个上界，即最优策略中，补货不应过分提前发生。

c++代码：

#include<iostream>
#include<fstream>using namespace std;const int T=12; //周期
const double D[T]={10,62,12,130,154,129,88,52,124,160,238,41}; 
const double s[T]={54,54,54,54,54,54,54,54,54,54,54,54};
const double h[T]={0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4};double min(double *,int);//返回一个数组中的最小值template<typename T>
void print(T *,int);void main()
{double cost[T][T];//任意两个周期间的成本，从一个周期启动生产，库存持续到另一个周期double Opt_cost[T]; //记录从第一期到第T期的最优总成本int Order[T];  //从第一期到第T期的最优生产序列，用0-1表示，0表示该期不生产，1表示该期启动生产	double I[T]; //记录每阶段的库存for (int i=0;i<T;i++)for (int j=0;j<T;j++)cost[i][j]=INT_MAX;  //初试化成本//计算两个周期内的成本，以及最优总成本序列for (int i=0;i<T;i++){if(i>0)  //记录从第1期到第i-1期的最优总成本{double p[T];for (int j=0;j<T;j++)p[j]=cost[j][i-1];Opt_cost[i-1]=min(p,T);}for (int j=i;j<T;j++){double sum=0;for (int k=i;k<j+1;k++)sum+=D[k];double h_sum=0;for (int k=i;k<j+1;k++){	h_sum=h_sum+h[i]*(sum-D[k]);sum=sum-D[k];}if (i>0)cost[i][j]=Opt_cost[i-1]+h_sum+s[i];//得到第i期到第j期的最优总成本elsecost[i][j]=h_sum+s[i];}}double p[T];for (int j=0;j<T;j++)p[j]=cost[j][T-1];Opt_cost[T-1]=min(p,T);//求最优生产序列，从后向前推int i=T-1;while (i>=0){if (Opt_cost[i]==cost[i][i]){Order[i]=1;i=i-1;}else{Order[i]=0;int index=i;for (int k=0;k<i;k++){if (Opt_cost[i]==cost[k][i]){index=k;Order[index]=1;break;}}Order[index]=1;for (int k=index+1;k<i;k++)Order[k]=0;i=index-1;}}//根据最优生产序列得到每个阶段的库存，从前向后推i=0;int index=0;while (index<T-1){		for (int j=i+1;j<T;j++){if (Order[j]==1){index=j;break;}if (j==T-1&&Order[j]==0){index=T;}}double sum=0;for (int k=i;k<index;k++)sum+=D[k];for (int k=i;k<index;k++){sum=sum-D[k];I[k]=sum;}i=index;}cout<<"最优生产序列:"<<endl;print(Order,T);//print(cost,T);cout<<"从第1期到各期的最优总成本:"<<endl;print(Opt_cost,T);cout<<"最优生产时的各阶段库存水平位:"<<endl;print(I,T);}double min(double *a,int n)
{double temp=a[0];for (int i=1;i<n;i++)if (a[i]<temp)temp=a[i];return temp;
}template<typename T>
void print(T *a,int n)
{for (int i=0;i<n;i++)cout<<a[i]<<" ";cout<<endl;
}

java 代码：

import java.util.Arrays;public class SingleItemLS {public static void main(String[] args) {// TODO Auto-generated method stubint T=12; //周期double[] D={10,62,12,130,154,129,88,52,124,160,238,41}; double[] s={54,54,54,54,54,54,54,54,54,54,54,54};double[] h={0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4,0.4};double[][] cost = new double[T][T];//任意两个周期间的成本，从一个周期启动生产，库存持续到另一个周期double[] OptCost = new double[T]; //记录从第一期到第T期的最优总成本int[] Order = new int[T];  //从第一期到第T期的最优生产序列，用0-1表示，0表示该期不生产，1表示该期启动生产	double[] I = new double[T]; //记录每阶段的库存for (int i = 0; i < T; i++)for (int j = 0; j < T; j++)cost[i][j]=Double.MAX_VALUE;  //初试化成本//计算两个周期内的成本，以及最优总成本序列for (int i = 0; i < T; i++){if(i > 0)  //记录从第1期到第i-1期的最优总成本{double[] p = new double[T];for (int j=0;j<T;j++)p[j]=cost[j][i-1];OptCost[i-1]= Arrays.stream(p).min().getAsDouble();}for (int j = i; j < T; j++){double sum=0;for (int k = i; k < j + 1; k++)sum += D[k];double hSum = 0; for (int k = i; k < j + 1; k++){	hSum = hSum + h[i]*(sum - D[k]);sum = sum - D[k];}if (i>0)cost[i][j] = OptCost[i-1] + hSum + s[i];//得到第i期到第j期的最优总成本elsecost[i][j] = hSum + s[i];}}double[] p = new double[T];for (int j = 0; j < T; j++)p[j] = cost[j][T-1];OptCost[T-1] = Arrays.stream(p).min().getAsDouble();//求最优生产序列，从后向前推int i=T-1;while (i>=0){if (OptCost[i] == cost[i][i]){Order[i] = 1;i = i-1;}else{Order[i] = 0;int index = i;for (int k = 0; k < i; k++){if (OptCost[i] == cost[k][i]){index = k;Order[index] = 1;break;}}Order[index] = 1;for (int k = index + 1; k < i; k++)Order[k] = 0;i = index - 1;}}//根据最优生产序列得到每个阶段的库存，从前向后推i=0;int index = 0;while (index < T-1){		for (int j = i + 1; j < T; j++){if (Order[j] == 1){index = j;break;}if (j == T-1 && Order[j] == 0){index = T;}}double sum = 0;for (int k = i; k < index; k++)sum += D[k];for (int k = i; k < index; k++){sum = sum - D[k];I[k] = sum;}i = index;}System.out.println("最优生产序列:");System.out.println(Arrays.toString(Order));System.out.println("从第1期到各期的最优总成本:");System.out.println(Arrays.toString(OptCost));System.out.println("最优生产时的各阶段库存水平位:");System.out.println(Arrays.toString(I));}
}