Оптимизация: минимизировать стоимость хранения в сети - PullRequest
Новая
       41

Оптимизация: минимизировать стоимость хранения в сети

0 голосов
/ 10 января 2020

У меня следующая проблема.

Предположим, у вас есть 3 узла в сети, где у каждого узла есть цена, зависящая от остаточной суммы входного и выходного потоков + спрос / предложение на узел. Узлы обмениваются потоками с целью сближения цен. Думайте об этом как о трех странах, обменивающих власть для максимизации благосостояния.

Единственным ограничением является емкость ar c.

Переменные решения должны быть элементом цен / потоков (см. Ниже). ). Оптимальное решение может быть несбалансированным (например, предложение! = Спрос), следовательно, сохранение не требуется.

Пример задачи:

Problem

Пример решения:

Solution

Узел 1: 

+----------+------+------+------+---+------+------+------+
| Residual | -600 | -400 | -200 | 0 | +200 | +400 | +600 |
+----------+------+------+------+---+------+------+------+
| Price    |  -60 |  -20 |  -10 | 0 |   15 |   20 |   50 |
+----------+------+------+------+---+------+------+------+

Узел 2 

+----------+------+------+------+---+------+------+------+
| Residual | -600 | -400 | -200 | 0 | +200 | +400 | +600 |
+----------+------+------+------+---+------+------+------+
| Price    |  -55 |  -15 |  -10 | 0 |   17 |   20 |   60 |
+----------+------+------+------+---+------+------+------+

Узел 3 

+----------+------+------+------+---+------+------+------+
| Residual | -600 | -400 | -200 | 0 | +200 | +400 | +600 |
+----------+------+------+------+---+------+------+------+
| Price    |  -75 |  -30 |  -15 | 0 |   20 |   25 |   30 |
+----------+------+------+------+---+------+------+------+

Это то, что я имею до сих пор, боюсь, это не много. Я использую PulP, но не стесняйтесь предлагать использовать любой другой пакет оптимизации. 

# Import PuLP modeller functions
from pulp import *

# List of all the nodes
Nodes = ["Node 1",
         "Node 2",
         "Node 3"]

nodeData = {# NODE        Supply Demand
         "Node 1":    [0,600],
         "Node 2":    [0,400],
         "Node 3":    [1000,0]}

# List of all the arcs
Arcs = [("Node 1","Node 2"),
        ("Node 1","Node 3"),
        ("Node 2","Node 1"),
        ("Node 2","Node 3"),
        ("Node 3","Node 1"),
        ("Node 3","Node 2")]

arcData = { #      ARC                Cost Min Max
        ("Node 1","Node 2"):      [0,0,0],
        ("Node 1","Node 3"):  [0,0,200],
        ("Node 2","Node 1"): [0,0,400],
        ("Node 2","Node 3"):     [0,0,400],
        ("Node 3","Node 1"):  [0,0,200],
        ("Node 3","Node 2"): [0,0,200],}

# Splits the dictionaries to be more understandable
(supply, demand) = splitDict(nodeData)
(costs, mins, maxs) = splitDict(arcData)

# Creates the boundless Variables as Integers
vars = LpVariable.dicts("Route",Arcs,None,None,LpInteger)

# Creates the upper and lower bounds on the variables
for a in Arcs:
    vars[a].bounds(mins[a], maxs[a])

# Creates the 'prob' variable to contain the problem data    
prob = LpProblem("FlowProblem",LpMinimize)

# Creates the objective function
prob += lpSum([vars[a]* costs[a] for a in Arcs]), "Total Cost of Transport"

# Creates all problem constraints - this ensures the amount going into each node is at least equal to the amount leaving
for n in Nodes:
    prob += (supply[n]+ lpSum([vars[(i,j)] for (i,j) in Arcs if j == n]) >=
             demand[n]+ lpSum([vars[(i,j)] for (i,j) in Arcs if i == n])), "Flow Conservation in Node %s"%n

# The problem data is written to an .lp file
prob.writeLP("FlowProblem.lp")

# The problem is solved using PuLP's choice of Solver
prob.solve()

# The status of the solution is printed to the screen
print("Status:", LpStatus[prob.status])

# Each of the variables is printed with it's resolved optimum value
for v in prob.variables():
    print(v.name, "=", v.varValue)

# The optimised objective function value is printed to the screen    
print("Total Cost of Transportation = ", value(prob.objective))
...