Vinar¶

Vinar Janez je pridelal $2000$ litrov rumenega muškata, $10000$ litrov laškega rizlinga in $5000$ litrov renskega rizlinga. Njegovi kupci so bara Kocka in Luka ter župnišče Sv. Martin in občina Duplek. Vsak od njih je pripravljen kupiti največ določeno količino vina po fiksni ceni, ne glede na sorto:

kupec	Kocka	Luka	župnišče	občina
cena za liter	$1.0$	$1.1$	$1.5$	$1.8$
največja količina v litrih	$15000$	$5000$	$500$	$1000$

Janez se je odločil, da bo vsako sorto prodal največ enemu kupcu, in sicer v maksimalni količini (če kupec ne kupi vsega vina iste sorte, ga Janez ohrani zase). Župan pravi, da občina drugega vina kot renskega rizlinga ne bo kupila. Bar Luka želi rumeni muškat, če bar Kocka dobi laški rizling. Pri Kocki so se dogovorili, da če občina in župnišče ne kupijo nič, tudi oni ne bodo kupili ničesar. Janezova žena pa vztraja, da če kupec $A$ kupi sorto $s_A$ in kupec $B$ kupi sorto $s_B$, potem naj sorta $s_C$ ostane doma ali jo kupi kupec $C$ (za neke $A, B, C$). Kako naj Janez proda vino, da bo čim več zaslužil?

Zapiši problem kot celoštevilski linearni program.

Parametri¶

Sorte in stranke bomo označili s kraticami, ki jih zbremo v sledečih seznamih.

In [1]:

sorte = ["RM", "LR", "RR"] # rumeni muškat, laški rizling, renski rizling
stranke = ["K", "L", "Z", "O"] # bar Kocka, bar Luka, župnišče sv. Martin, občina Duplek

V zadnjem pogoju vrednosti $A, B, C$ niso znane vnaprej. Določimo jim neko vrednost, da bomo lahko rešili celoštevilski linearni program. Seveda lahko vrednosti zamenjamo, pa bo optimalna rešitev potem morda drugačna.

In [2]:

A, B, C = "K", "L", "Z"
sA, sB, sC = "RR", "LR", "RM"

Celoštevilski linearni program¶

Zapisali bomo sledeči celoštevilski linearni program:

\begin{align*} \max &\ 2000 x_{RM, K} + 2200 x_{RM, L} + 750 x_{RM, Z} + 1800 x_{RM, O} \\ {}+ &\ 10000 x_{LR, K} + 5500 x_{LR, L} + 750 x_{LR, Z} + 1800 x_{LR, O} \\ {}+ &\ 5000 x_{RR, K} + 5500 x_{RR, L} + 750 x_{RR, Z} + 1800 x_{RR, O} \\ \text{p. p.} \quad \forall i \ \forall j. \ 0 \le x_{ij} &\le 1, \ x_{ij} \in \mathbb{Z} \\ \forall i. \sum_j x_{ij} &\le 1 \\ \forall j. \sum_i x_{ij} &\le 1 \\ x_{RM, O} + x_{LR, O} &= 0 \\ x_{LR, K} - x_{RM, L} &\le 0 \\ \sum_i (x_{i, O} + x_{i, Z} - x_{i, K}) &\ge 0 \\ x_{s_A, A} + x_{s_B, B} + \sum_{j \ne C} x_{s_C, j} &\le 2 \\ \end{align*}

Tukaj smo predpostavili, da indeks $i$ teče po sortah, indeks $j$ pa po strankah.

In [3]:

p = MixedIntegerLinearProgram(maximization=True)
x = p.new_variable(binary=True)

In [4]:

p.set_objective(x["RM", "K"] * 2000 + x["RM", "L"] * 2200 + x["RM", "Z"] * 750 + x["RM", "O"] * 1800 +
                x["LR", "K"] * 10000 + x["LR", "L"] * 5500 + x["LR", "Z"] * 750 + x["LR", "O"] * 1800 +
                x["RR", "K"] * 5000 + x["RR", "L"] * 5500 + x["RR", "Z"] * 750 + x["RR", "O"] * 1800)

In [5]:

for i in sorte:
    p.add_constraint(sum(x[i, j] for j in stranke) <= 1)
for j in stranke:
    p.add_constraint(sum(x[i, j] for i in sorte) <= 1)
p.add_constraint(x["RM", "O"] + x["LR", "O"] == 0)
p.add_constraint(x["LR", "K"] <= x["RM", "L"])
p.add_constraint(sum(x[i, "O"] + x[i, "Z"] - x[i, "K"] for i in sorte) >= 0)
p.add_constraint(x[sA, A] + x[sB, B] + sum(x[sC, j] for j in stranke if j != C) <= 2)

In [6]:

p.solve()

Out[6]:

14000.0

In [7]:

res = p.get_values(x)
res

Out[7]:

{('LR', 'K'): 1.0,
 ('LR', 'L'): 0.0,
 ('LR', 'O'): 0.0,
 ('LR', 'Z'): 0.0,
 ('RM', 'K'): 0.0,
 ('RM', 'L'): 1.0,
 ('RM', 'O'): 0.0,
 ('RM', 'Z'): 0.0,
 ('RR', 'K'): 0.0,
 ('RR', 'L'): 0.0,
 ('RR', 'O'): 1.0,
 ('RR', 'Z'): 0.0}

In [8]:

{i: j for (i, j), v in res.items() if v == 1}

Out[8]:

{'LR': 'K', 'RM': 'L', 'RR': 'O'}