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$, in $c_i$ cena za skrajšanje opravila $i$ za en dan. 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 27 - 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)

In [3]:

p.set_objective(sum(c * (t-x[i]) for i, _, t, P, m, c in faze))
for i, _, t, P, m, c in faze:
    p.add_constraint(x[i] >= m)
    p.add_constraint(x[i] <= t)
    p.add_constraint(y[i] >= 0)
    p.add_constraint(y[i] <= 27 - 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, _, t, P, m, c 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)]