# Problema de Alocação Ótima

+1 voto
62 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, 2019 por (61 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, 2019 por (286 pontos)
editado Jul 13, 2019 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.