Problema de Alocação Ótima

+1 voto
36 visitas

Problema 2.1 do livro Dynammic programming: A computational tool de Art Lew e Holger Mauch:

The optimal allotment problem is that of deciding how to distribute a limited amount of resources to a set of users of these resources, where there are specified costs or profits associated with allotting units of the resource to users.

Assume there are M total units of the resource, and let C(k,d) be the cost or profit associated with allotting d units to user k, where d = 0, . . . , M and k = 1,...,N. Suppose we make the allotment decisions in stages, initially allotting $d_1$ units to user 1, then $d_2$ units to user 2, etc. This arbitrary sequencing 1, 2, . . . , N can be assumed since only the quantities allotted matter, not the sequence in which they are made. We define the state (k,m) as remaining number m of units of resource at stage k. The cost of deciding to allot d units at stage k to user k is C(k,d). The next-state is (k + 1,m − d). The DPFE is

$f(k,m) = min_{d∈\{0,...,m\}} \{C(k,d) + f(k + 1,m − d) \}.$

The goal is to find f(1,M) with base-conditions f(N+1,m) = 0 when m ≥ 0. If we allow d > m (bounding d by M instead), we may use the additional base- condition f (N + 1, m) = ∞ when m < 0 to prevent allotting more resources than is available.

For instance, let M = 4, N = 3 and

$(C_{k,d})_{k∈{1,2,3};d∈{0,...,4}} =$
$\begin{bmatrix} ∞ & 1 & 0.8 & 0.4 & 0 \\ ∞ & 1 & 0.5 & 0 & 0 \\ ∞ & 1 & 0.6 & 0.3 & 0 \end{bmatrix}.$

Then f (1, M ) = 1.0 + 0.5 + 1.0 = 2.5 for the optimal sequence of allotments $d_1 = 1$, $d_2 = 2$, $d_3=1$.

1 Resposta

+2 votos
respondida Jul 12 por (51 pontos)

Podemos resolver essa questão construindo, a partir de um conjunto com as distribuições possíveis das unidades entre os agentes, o valor do custo para cada distribuição, e retornar o valor mínimo nesse conjunto.

import numpy as np

#Definindo função para obter alocação ótima com 3 indivíduos a partir da matriz de custos e do número de unidades.
def Allot(G, d):
da = list()
diml= list()
for i in range(0, d+1):
for m in range(0, d-i+1):
d1 = i
d2 = m
d3 = d-d1-d2
dim = [d1, d2, d3]
diml.append(dim)
dam = G[dim] + G[dim] + G[dim]
da.append(dam)
print("Minimum value:")
print(min(da))
pstn = da.index(min(da))
print("At point [d1, d2, d3]:")
print(diml[pstn])

# Construindo a Matriz do Exemplo.
CMat = ([np.inf, 1, 0.8, 0.4, 0],
[np.inf, 1, 0.5, 0, 0],
[np.inf, 1, 0.6, 0.3, 0])
#Aplicando a função.
Allot(CMat, 4)

Minimum value:
2.5
At point [d1, d2, d3]:
[1, 2, 1]

Assim, obtemos o valor mínimo de f(1,m) = 2.5 para a alocação ótima $d_1=1, d_2=2, d_3=3$ .

comentou Jul 12 por (286 pontos)
editado Jul 13 por Pablo Castro
Ótima solução, consegui replicar seu código perfeitamente no meu computador.

Só notei que você faz uma implementação para o caso onde N = 3. Acho que seria interessante uma implementação para um número genérico de agentes. Isso seria apenas uma pequena alteração no código que ficou muito bom.