Notebook

Gradnja hiše¶

Gradbinec in samooklicani arhitekt Brezzobec se je odločil, da bo postavil zelo posebno hišo. Gradnja bo imela sedem glavnih faz:

In [1]:

faze = {
#   faza  opis                            trajanje  pogoji    min  cena
    'A': ('gradnja kleti',                      10, [],         7, 200),
    'B': ('gradnja pritličja',                  6,  ['A'],      5, 100),
    'C': ('gradnja prvega nadstropja',          7,  ['B', 'F'], 5, 150),
    'D': ('gradnja strehe',                     8,  ['C', 'E'], 6, 160),
    'E': ('gradnja desnega podpornega stebra',  13, ['A'],      9, 250),
    'F': ('gradnja glavnega podpornega stebra', 14, [],        11, 240),
    'G': ('gradnja baročnega stolpa pred hišo', 30, [],        25, 300),
}

Brezzobčev bratranec ima podjetje, ki lahko pomaga pri gradnji, vendar za vsak dan krajšanja posamezne faze zahteva ustrezno plačilo (stolpec cena), pri čemer je v stolpcu min podano najkrajše možno trajanje opravila. Brezzobca zanima način, kako bi s čim manjšimi stroški čas gradnje zmanjšal na $27$ dni.

Linearni program¶

Problem bomo modelirali z linearnim programom s sledečimi spremenljivkami:

$x_i$: trajanje faze $i$
$y_i$: začetni čas faze $i$

Naj bo $t_i$ privzeto trajanje opravila $i$, $P_i$ množica pogojev za začetek opravila $i$, $m_i$ minimalno trajanje opravila $i$, $c_i$ cena za skrajšanje opravila $i$ za en dan in $T$ želeno trajanje projekta. Potem lahko zapišemo sledeči linearni program:

\begin{align*} \min \sum_i c_i (t_i - x_i) & \\ \text{p. p.} \quad \forall i. m_i \le x_i &\le t_i \\ \forall i. 0 \le y_i &\le T - x_i \\ \forall i \forall j \in P_i. y_i &\ge y_j + x_j \end{align*}

In [2]:

p = MixedIntegerLinearProgram(maximization=False)
x = p.new_variable(real=True)
y = p.new_variable(real=True)
T = 27

In [3]:

p.set_objective(sum(c * (t-x[i]) for i, (_, t, P, m, c) in faze.items()))
for i, (_, t, P, m, c) in faze.items():
    p.add_constraint(x[i] >= m)
    p.add_constraint(x[i] <= t)
    p.add_constraint(y[i] >= 0)
    p.add_constraint(y[i] <= T - x[i])
    for j in P:
        p.add_constraint(y[i] >= y[j] + x[j])

Z metodo solve dobimo optimalno vrednost ciljne funkcije.

In [4]:

p.solve()

Out[4]:

1620.0

Izpišimo še začetne čase in trajanja opravil.

In [5]:

X = p.get_values(x)
Y = p.get_values(y)
{i: (Y[i], X[i]) for i in faze}

Out[5]:

{'A': (0.0, 8.0),
 'B': (8.0, 6.0),
 'C': (14.0, 7.0),
 'D': (21.0, 6.0),
 'E': (8.0, 13.0),
 'F': (0.0, 14.0),
 'G': (0.0, 27.0)}