Como resolver um problema de tamanho de lotes utilizando programação dinâmica?

Question

Esse problema foi retirado do livro Dynamic Programming: A Computational Tool, escrito por Art Lew and Holger Mauch.

O problema de tamanho de lotes é uma variação do problema de inventário e do problema de produção, ambos já resolvidos aqui no PRorum, podendo ser encontrados nos links abaixo:

Problema de inventário
Problema de produção

O problema consiste em encontrar o menor valor necessário para atender, a cada período \(k\), a demanda \(D(k)\), que é conhecida. Escolher produzir em um determinado período leva a um custo fixo \(A\) e outro variável \(b\), de modo que \(C(0) = 0\) e \(C(x) = A + bx\), para \(x\gt0\). Caso a produção em determinado período seja maior que a demanda, o excedente é guardado para o período seguinte, levando a um custo de estocagem dado por \(I(k,s)\).

O problema de tamanho de lotes se diferencia do problema de inventário pois, enquanto no segundo, testa-se todos os valores de x possíveis em todos os períodos até um determinado limite pré-determinado, no problema de tamanho de lotes, avaliamos apenas os custos de se produzir a demanda atual ou a demanda atual somada a determinado número de demandas subsequentes. Essa mudança reduz consideravelmente o tempo de operação do algoritmo sem abrir mão da otimalidade da solução. Isso se deve pois, da maneira que definimos o problema, com as funções de custo lineares e sem restrições de produção ou estoque, nunca será ótimo produzir o bastante para suprir demandas de maneira parcial. Uma prova para esse resultado pode ser encontrada na seção 18.7 do livro Operations Research: Applications and Algorithms, escrito por Wayne L. Winston.

Queremos resolver o problema, isto é, encontrar as decisões ótimas \(x_k\) a cada período e \(f(1)\) para as seguintes condições:

\(N=5\)
\(f(k)=0, \ para\ k \gt N\)
\(C(k,x)=250+2x,\ para\ x \gt 0\)
\(C(k,0)=0\)
\(I(k,s)=s,\ para\ s \gt 0\)
\(D(0)=220\)
\(D(1)=280\)
\(D(2)=360\)
\(D(3)=140\)
\(D(4)=270\)

Answer 1

O código que desenvolvi resolve o problema da seguinte maneira:

• Começando pelo último período, para cada período \(k\), calcular o
  custo total de se produzir a demanda total de todos os períodos \(k\)
  até \(N\).
• Em seguida, calcular o custo de se produzir as demandas de \(k\)
  até \(N-1\) somado ao custo de se utilizar a solução ótima de
  produção para \(N-1\) até \(N\).
• Fazer isso sucessivamente até o momento em que se produz apenas
  \(D[k]\) e utiliza-se a solução ótima de produção para \(k+1\) até
  \(N\)

Obtida uma lista com esses valores, o algoritmo pega o menor deles e guarda numa tabela, sendo esse o custo da solução ótima para o período \(k\)

Segue abaixo o código utilizado:

Parâmetros do problema:

N = 5
Dk = [220, 280, 360, 140, 270]
x = Dk

Funções para calcular o custo de produção e o custo de estoque:

def custo_est(k, p):
    custo = 0
    i = 1
    while k < p:
        custo += (i)*Dk[k]
        i += 1
        k += 1

    return (custo)


def custo_uni(x):
    if x > 0:
        return 250 + 2*x
    else:
        return 0

Função que soluciona o problema de programação dinâmica:

def lot(k):
    lista = []
    s = [0]
    policy = []
    resultado = 0
    i = N + 1
    while i > 0:
        if i > N:
            resultado = 0
            lista.append(resultado)
            i -= 1
        else:
            f_x = []
            Q_x = []
            counter = 0
            for x in range(i, N + 1):

                resultado = custo_uni(sum(Dk[i - 1:N - counter])) + custo_est(x - counter, N - counter) + lista[counter]
                f_x.append(resultado)
                Q_x.append(sum(Dk[i - 1:N - counter]))
                counter += 1

            custo_x = min(f_x)
            lista.append(custo_x)
            ind_x = f_x.index(custo_x)
            s.insert(0, Q_x[ind_x] - Dk[i - 1])
            policy.insert(0, Q_x[ind_x])
            i -= 1

    iter = 0
    for p in policy:
        policy[iter] -= s[iter - 1]
        iter += 1

    return [lista[-k], policy]

Utilizando o código apresentado, podemos então responder o pedido, com:

lot(1)

Cuja saída é:

[3680, [220, 280, 500, 0, 270]]

De modo que o menor custo possível para a solução do problema é de $3680 e as decisões de produção são:

\(x_1=220\)
\(x_2=280\)
\(x_3=500\)
\(x_4=0\)
\(x_5=270\)

Comments

Solução interessante. Definir funções e chamar las dentro de outras funções é um processo bom de organizar as ideias, evitar variáveis globais e deixar o código esteticamente bonito sem ter que recorrer a definição de classe. Além de que, em códigos mais extensos, fica mais fácil a identificação de possíveis erros. Quanto ao resultado do problema em si,  me chamou a atenção a ação frente ao k=3, onde a demanda é bem mais baixa que as demais. O ótimo a ser feito é aumentar a produção em k=2 (um período anterior), de forma que não seja necessário produzir em k=3, visto que nessa situação o custo de estoque é menor que o custo de produzir.