dynamic_programming1.m

clc, clear, close all

%A regional electric power company is planning a large investment in power 
% plants over the next few years. A total of eight power plants must be 
% built over the next six years because of both increasing demand in the 
% region and the energy crisis, which has forced the closing of some of 
% their antiquated fossil- fuel plants. Suppose that, for a first 
% approximation, we assume that demand for electric power in the region is 
% known with certainty and that we must satisfy the minimum levels of 
% cumulative demand indicated in Table below. The power company has decided
% at least to meet this minimum-demand schedule. The building of power 
% plants takes approximately one year. In addition to a cost directly 
% associated with the construction of a plant, there is a common cost of 
% $1.5 million incurred when any plants are constructed in any year, 
% independent of the number of plants constructed. This common cost results
% from contract preparation and certification of the impact statement for 
% the Environmental Protection Agency. In any given year, at most three 
% plants can be constructed. The cost of construction per plant is given in
% Table below for each year in the planning horizon. These costs are 
% currently increasing due to the elimination of an investment tax credit 
% designed to speed investment in power. However, new technology should be
% available soon, which will tend to bring the costs down, even given the 
% elimination of the investment tax credit.


% Year Cumulative demand(in number of plants)  Cost per plant ($ × 1000)
% 1991   1   5400
% 1992   2   5600
% 1993   4   5800
% 1994   6   5700
% 1995   7   5500
% 1996   8   5200

% SEE THE GRAPH NETWORK

years = 1:6;                   % 1991–1996
T = length(years);

D = [1 2 4 6 7 8];             % cumulative demand per year
C = [5400 5600 5800 5700 5500 5200];  % cost per plant (in $1000)
F = 1500;                      % fixed cost per year (if k>0)
Kmax = 3;                      % max plants per year
TotalPlants = 8;

% optimize the cost value --> 48.8M $

INF = 1e12;

% DP table: f(t,x)
% t = 1..6, x = 0..8
f = INF * ones(T+2, TotalPlants+1);

% Decision table to recover policy
policy = zeros(T, TotalPlants+1);

for x = 0:TotalPlants
    if x == TotalPlants
        f(T+1, x+1) = 0;  % MATLAB index shift
    else
        f(T+1, x+1) = INF;
    end
end


%Backward computation
for t = T:-1:1 % all years backward
    for x = 0:TotalPlants % plants built before year t

        bestCost = INF;
        bestK = 0;
        for k = 0:Kmax % each decision

            % cumulative demand constraint
            if x + k < D(t)
                continue;
            end

            % cannot exceed total requirement
            if x + k > TotalPlants
                continue;
            end

            % cost this year
            if k == 0
                costThisYear = 0;
            else
                costThisYear = k * C(t) + F;
            end

            % cost-to-go
            costFuture = f(t+1, x+k+1);  % +1 for MATLAB indexing

            totalCost = costThisYear + costFuture;

            % update best
            if totalCost < bestCost
                bestCost = totalCost;
                bestK = k;
            end

        end

        f(t, x+1) = bestCost;
        policy(t, x+1) = bestK;
    end
end

x = 0;  % start with zero plants built
opt_build = zeros(1, T);

for t = 1:T
    k = policy(t, x+1);
    opt_build(t) = k;
    x = x + k;
end

opt_cost = f(1, 1);

fprintf('\nOptimal yearly construction schedule:\n');
for t = 1:T
    fprintf('Year %d: build %d plants\n', 1990 + t, opt_build(t));
end

fprintf('\nTotal minimum cost = %.2f million dollars\n', opt_cost/1000);