Lineární programování v Pythonu

21. 3. 2021 · 🇨🇿 · English version of the article · [upravit]

Úvodní informace
Praktické příklady
Zdroje/materiály

Úvodní informace

Tato stránka obsahuje náhodné programy ze cvičení/přednášky předmětu Lineární programování a kombinatorická optimalizace, a zároveň jako dodatečné materiály k mému nově vydanému videu o lineárním programovaní. Ke spuštění programů je potřeba nainstalovat Pythoní knihovnu pulp (přes pip install pulp), kterou k řešení problémů používám.

Pokud s pulpem také vyřešíte nějaký problém, tak budu moc rád za email/pull request, ať tu máme příkladů co možná nejvíce 🙂.

Praktické příklady

Problém pekárny

Pekárna má k dispozici $5000\ \mathrm{g}$ mouky, $125$ vajec a $500\ \mathrm{g}$ soli. Může z nich péct chleby, housky, bagety a koblihy s tím, že každé pečivo vyžaduje jiné množství surovin; konkrétně

	chléb	houska	bageta	kobliha
mouka	$500\ \mathrm{g}$	$150\ \mathrm{g}$	$230\ \mathrm{g}$	$100\ \mathrm{g}$
vejce	$10\ \mathrm{ks}$	$2\ \mathrm{ks}$	$7\ \mathrm{ks}$	$1\ \mathrm{ks}$
sůl	$50\ \mathrm{g}$	$10\ \mathrm{g}$	$15\ \mathrm{g}$

Za jeden chleba získá pekárna $20\ \mathrm{Kč}$ , za housku $2\ \mathrm{Kč}$ , za bagetu $10\ \mathrm{Kč}$ a za koblihu $7\ \mathrm{Kč}$ .

Pekárna se snaží vydělat co nejvíce – kolik chlebů, housek, baget a koblih má ze surovin upéci?

Zdrojový kód

from pulp import *

# vytvoření modelu
model = LpProblem(name="problem-pekarny", sense=LpMaximize)

# proměnné -- kolik pečiva upečeme
xc = LpVariable(name="chleby", lowBound=0, cat='Integer')
xh = LpVariable(name="housky", lowBound=0, cat='Integer')
xb = LpVariable(name="bagety", lowBound=0, cat='Integer')
xk = LpVariable(name="koblihy", lowBound=0, cat='Integer')

# omezení -- nesmíme na pečení spotřebovat více surovin než máme
model += 500 * xc + 150 * xh + 230 * xb + 100 * xk <= 5000
model +=  10 * xc +   2 * xh +   7 * xb +   1 * xk <= 125
model +=  50 * xc +  10 * xh +  15 * xb            <= 500

# funkce k maximalizaci -- zisk z pečení
model += 20 * xc + 2 * xh + 10 * xb + 7 * xk

# řešení (ignorujeme debug zprávy)
status = model.solve(PULP_CBC_CMD(msg=False))
print(int(xc.value()), int(xh.value()), int(xb.value()), int(xk.value()))

Výpis

0 0 0 50

Problém batohu

Pro $n$ předmětů, kde $i$ -tý má nějakou váhu $v_i$ a cenu $c_i$ , máme batoh s danou nosností $V$ a my se do něj snažíme naskládat předměty tak, abychom maximalizovali celkovou cenu předmětů v batohu.

Zdrojový kód

from pulp import *

data = [
        { 'nosnost': 165,
          'hmotnosti': [23, 31, 29, 44, 53, 38, 63, 85, 89, 82],
          'ceny': [92, 57, 49, 68, 60, 43, 67, 84, 87, 72] },
        { 'nosnost': 26,
          'hmotnosti': [12, 7, 11, 8, 9],
          'ceny': [24, 13, 23, 15, 16] },
        { 'nosnost': 6404180,
          'hmotnosti': [382745, 799601, 909247, 729069, 467902, 44328, 34610, 698150, 823460, 903959, 853665, 551830, 610856, 670702, 488960, 951111, 323046, 446298, 931161, 31385, 496951, 264724, 224916, 169684],
          'ceny': [825594, 1677009, 1676628, 1523970, 943972, 97426, 69666, 1296457, 1679693, 1902996, 1844992, 1049289, 1252836, 1319836, 953277, 2067538, 675367, 853655, 1826027, 65731, 901489, 577243, 466257, 369261] },
        ]

for dataset in data:
    size = len(dataset['hmotnosti'])

    # vytvoření modelu
    model = LpProblem(name="problem-batohu", sense=LpMaximize)

    # proměnné -- zda do batohu vložíme i-tou věc
    variables = [LpVariable(name=f"x{i}", cat='Binary') for i in range(size)]

    # omezení -- nesmíme do batohu vložit více než nosnost
    model += lpSum([dataset['hmotnosti'][i] * variables[i] for i in range(size)]) <= dataset['nosnost']

    # funkce k maximalizaci -- cena věcí v batohu
    model += lpSum([dataset['ceny'][i] * variables[i] for i in range(size)])

    # řešení (ignorujeme debug zprávy)
    status = model.solve(PULP_CBC_CMD(msg=False))

    print("cena batohu:", model.objective.value())
    print("vezmeme:", *[int(variables[i].value()) for i in range(size)])
    print()

Výpis

cena batohu: 309.0
vezmeme: 1 1 1 1 0 1 0 0 0 0

cena batohu: 51.0
vezmeme: 0 1 1 1 0

cena batohu: 13549094.0
vezmeme: 1 1 0 1 1 1 0 0 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 1

Prokládání přímkou

Máme-li $n$ bodů $(x_1 , y_1 ), \ldots, (x_n , y_n )$ v rovině, tak najděte přímku $\left\{x \in \mathbb{R}: y = ax + b\right\}$ , která minimalizuje součet vertikálních vzdáleností bodů od výsledné přímky. Vertikální vzdálenost je vzdálenost měřena pouze na ose $y$ . Pro jednoduchost předpokládejte, že výsledná přímka není kolmá na osu $x$ .

Zdrojový kód

from pulp import *

# pole bodů, kterými prokládáme
point_lists = [
    [(0, 0), (1, 1)],
    [(3, 2), (-1, 4)],
    [(3, 4), (1, 4), (5, 2), (1, 1.5), (4.5, 3)],
]

for points in point_lists:
    # vytvoření modelu
    model = LpProblem(name="prokladani-primkou", sense=LpMinimize)

    # proměnné -- koeficienty a, b a vzdálenosti od přímky
    a = LpVariable(name="a")
    b = LpVariable(name="b")
    distances = [LpVariable(name=f"d_{i}") for i in range(len(points))]

    # omezení -- vzdálenosti v absolutní hodnotě
    for i, d_i in enumerate(distances):
        model += -d_i <= (a * points[i][0] + b) - points[i][1]
        model += (a * points[i][0] + b) - points[i][1] <= d_i

    # funkce k minimalizaci -- vzdálenosti od přímky
    model += lpSum(distances)

    # řešení (ignorujeme debug zprávy)
    status = model.solve(PULP_CBC_CMD(msg=False))
    print("rovnice přímky: ", f"{a.value()}x + {b.value()}")

Výpis

rovnice přímky:  1.0x + 0.0
rovnice přímky:  -0.5x + 3.5
rovnice přímky:  -0.28571429x + 4.2857143

Vrcholová obarvitelnost grafu

Nalezněte minimální $k$ takové, že vrcholy grafu $G$ lze korektně obarvit $k$ barvami.

Zdrojový kód

from pulp import *

# seznamy (neorientovaných!) hran grafů
edges_lists = [
    # K_5
    [(1, 2), (3, 2), (2, 4), (3, 4), (5, 4), (3, 5), (1, 5), (2, 5), (3, 1), (1, 4)],
    # skoro K_6
    [(1, 2), (1, 3), (4, 3), (4, 5), (6, 5), (6, 2), (6, 1), (6, 4), (1, 4), (2, 5), (2, 3), (3, 5)],
    # cesta
    [(1, 2), (3, 2), (3, 4), (4, 5), (5, 6)],
]

for edges in edges_lists:
    # počet vrcholů
    n = len(set([u for u, v in edges] + [v for u, v in edges]))

    # vytvoření modelu
    model = LpProblem(name="chromaticke-cislo", sense=LpMinimize)

    # proměnné -- x[i][k] podle toho, zda je i-tý vrchol obarvený k-tou barvou
    # proměnná navíc ještě bude chromatické číslo
    chromatic_number = LpVariable(name="chromatic number", lowBound=0, cat='Integer')
    variables = []
    for i in range(n):
        variables.append([])
        for j in range(n):
            variables[-1].append(LpVariable(name=f"x_{i}_{j}", cat='Binary'))

    # omezení
    ## každý vrchol má právě jednu barvu
    for i in range(n):
        model += lpSum(variables[i]) == 1

    ## pro každou hranu platí, že její sousední vrcholy nemají stejnou barvu
    for u, v in edges:
        for color in range(n):
            model += variables[u - 1][color] + variables[v - 1][color] <= 1

    ## navíc chceme, aby chromatic_number bylo číslo nejvyšší použité barvy
    for i in range(n):
        variables.append([])
        for j in range(n):
            model += chromatic_number >= (j + 1) * variables[i][j]

    # minimalizujeme chromatické číslo
    model += chromatic_number

    # řešení (ignorujeme debug zprávy)
    status = model.solve(PULP_CBC_CMD(msg=False))
    print("chromatické číslo:", int(chromatic_number.value()))
    for i in range(n):
        for j in range(n):
            if variables[i][j].value() != 0:
                print(f"vrchol {i}: barva {j}")
    print()

Výpis

chromatické číslo: 5
vrchol 0: barva 2
vrchol 1: barva 4
vrchol 2: barva 0
vrchol 3: barva 3
vrchol 4: barva 1

chromatické číslo: 3
vrchol 0: barva 2
vrchol 1: barva 1
vrchol 2: barva 0
vrchol 3: barva 1
vrchol 4: barva 2
vrchol 5: barva 0

chromatické číslo: 2
vrchol 0: barva 1
vrchol 1: barva 0
vrchol 2: barva 1
vrchol 3: barva 0
vrchol 4: barva 1
vrchol 5: barva 0

Hranová obarvitelnost grafu

Nalezněte minimální $k$ takové, že hrany grafu $G$ lze korektně obarvit $k$ barvami.

Zdrojový kód

from pulp import *
from networkx import *

n = 300
p = 0.01
g = erdos_renyi_graph(n, p)

edges = g.edges()

# number of vertices
n = len(set([u for u, v in edges] + [v for u, v in edges]))

model = LpProblem(sense=LpMinimize)

# variables -- x_{u, v, k} depending on whether {u, v} is colored using color k
variables = {}
for i, j in edges:
    variables[(i, j)] = []

    for k in range(n):
        variables[(i, j)].append(LpVariable(name=f"x_{i}_{j}_{k}", cat='Binary'))

    variables[(j, i)] = variables[(i, j)]

# the edge chromatic number is also a variable
edge_chromatic_number = LpVariable(name="edge_edge_chromatic_number", lowBound=0, cat='Integer')

# each edge has exactly one color
for i, j in edges:
    model += lpSum(variables[(i, j)]) == 1

# each vertex' adjacent colors are different
for color in range(n):
    for u in range(n):
        model += lpSum([variables[(u, v)][color] for v in range(n) if (u, v) in variables]) <= 1

# edge chromatic number is also the number of the highest color
for i, j in edges:
    for color in range(n):
        model += edge_chromatic_number >= color * variables[(i, j)][color]

# we're minimizing the edge chromatic number
model += edge_chromatic_number

status = model.solve(PULP_CBC_CMD(msg=False))

print("edge chromatic number:", int(edge_chromatic_number.value()))
for i, j in edges:
    for color in range(n):
        if variables[(i, j)][color].value() != 0:
            print(f"edge {(i, j)}: color {color}")

Výpis

edge chromatic number: 3
edge (0, 1): color 3
edge (0, 4): color 0
edge (0, 5): color 1
edge (1, 2): color 2
edge (1, 6): color 0
edge (2, 3): color 0
edge (2, 7): color 1
edge (3, 4): color 1
edge (3, 8): color 3
edge (4, 9): color 2
edge (5, 7): color 2
edge (5, 8): color 0
edge (6, 8): color 1
edge (6, 9): color 3
edge (7, 9): color 0

Problém obchodního cestujícího

Pro daný ohodnocený neorientovaný graf $G = (V, E, f)$ , kde $f : E \mapsto \mathbb{R}^+_0$ , chceme najít Hamiltonovskou kružnici v $G$ s nejmenším ohodnocením.

Zdrojový kód

from pulp import *
from itertools import *

distance_lists = [
    [
        [0],
        [3, 0],
        [4, 4, 0],
        [2, 6, 5, 0],
        [7, 3, 8, 6, 0],
    ],
    [
        [ 0],
        [29,  0],
        [82, 55,  0],
        [46, 46, 68,  0],
        [68, 42, 46, 82,  0],
        [52, 43, 55, 15, 74,  0],
        [72, 43, 23, 72, 23, 61,  0],
        [42, 23, 43, 31, 52, 23, 42,  0],
        [51, 23, 41, 62, 21, 55, 23, 33,  0],
        [55, 31, 29, 42, 46, 31, 31, 15, 29,  0],
        [29, 41, 79, 21, 82, 33, 77, 37, 62, 51,  0],
        [74, 51, 21, 51, 58, 37, 37, 33, 46, 21, 65,  0],
        [23, 11, 64, 51, 46, 51, 51, 33, 29, 41, 42, 61,  0],
        [72, 52, 31, 43, 65, 29, 46, 31, 51, 23, 59, 11, 62,  0],
        [46, 21, 51, 64, 23, 59, 33, 37, 11, 37, 61, 55, 23, 59,  0],
    ],
    [
        [  0],
        [633,   0],
        [257, 390,   0],
        [ 91, 661, 228,   0],
        [412, 227, 169, 383,   0],
        [150, 488, 112, 120, 267,   0],
        [ 80, 572, 196,  77, 351,  63,   0],
        [134, 530, 154, 105, 309,  34,  29,   0],
        [259, 555, 372, 175, 338, 264, 232, 249,   0],
        [505, 289, 262, 476, 196, 360, 444, 402, 495,   0],
        [353, 282, 110, 324,  61, 208, 292, 250, 352, 154,   0],
        [324, 638, 437, 240, 421, 329, 297, 314,  95, 578, 435,   0],
        [ 70, 567, 191,  27, 346,  83,  47,  68, 189, 439, 287, 254,   0],
        [211, 466,  74, 182, 243, 105, 150, 108, 326, 336, 184, 391, 145,   0],
        [268, 420,  53, 239, 199, 123, 207, 165, 383, 240, 140, 448, 202,  57,   0],
        [246, 745, 472, 237, 528, 364, 332, 349, 202, 685, 542, 157, 289, 426, 483,   0],
        [121, 518, 142,  84, 297,  35,  29,  36, 236, 390, 238, 301,  55,  96, 153, 336,   0],
    ]
]

for distances in distance_lists:
    # počet měst
    n = len(distances)

    # vytvoření modelu
    model = LpProblem(name="tsp", sense=LpMinimize)

    # proměnné -- binární x_{i, j} podle toho, zda je tato hrana na cestě
    # jsou symetrické a vždy i >= j
    variables = []
    for i in range(n):
        variables.append([])
        for j in range(i + 1):
            variables[-1].append(LpVariable(name=f"x_{i}_{j}", cat='Binary'))

    # omezení
    ## z každého vrcholu jedna hrana vychází a jedna do něj přichází
    for i in range(n):
        model += lpSum([variables[i if i > j else j][j if i > j else i] for j in range(n)]) == 2
        model += variables[i][i] == 0

    ## z každé podmnožiny vrcholů vychází alespoň jedna hrana
    for size in range(1, n - 1):  # TODO: maybe not
        for subset in combinations(range(n), r = size):
            model += lpSum([variables[i if i > j else j][j if i > j else i] for i in subset for j in range(n) if j not in subset]) >= 1

    # funkce k minimalizaci -- vzdálenosti kružnice
    model += lpSum([variables[i][j] * distances[i][j] for i, j in product(range(n), repeat=2) if i > j])

    # řešení (ignorujeme debug zprávy)
    status = model.solve(PULP_CBC_CMD(msg=False))

    print("minimální cesta: ", int(model.objective.value()))
    for i in range(n):
        for j in range(n):
            print(int(variables[i if i > j else j][j if i > j else i].value()), " ", end="")
        print()
    print()

Výpis

minimální cesta:  19
0  1  1  0  
0  1  0  1  
1  0  0  0  
0  0  0  1  
1  0  1  0  

minimální cesta:  291
0  0  0  0  0  0  0  0  0  1  0  1  0  0  
0  0  0  0  0  0  0  0  0  0  0  1  0  1  
0  0  0  0  0  1  0  0  0  0  1  0  0  0  
0  0  0  0  1  0  0  0  0  1  0  0  0  0  
0  0  0  0  0  1  0  1  0  0  0  0  0  0  
0  0  1  0  0  0  1  0  0  0  0  0  0  0  
0  1  0  1  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  1  0  0  0  1  0  0  0  0  0  
0  0  0  1  0  0  0  0  0  0  0  0  0  1  
0  0  0  0  0  0  1  0  0  0  0  0  1  0  
0  0  1  0  0  0  0  0  0  0  0  0  0  0  
0  1  0  0  0  0  0  0  0  0  0  0  1  0  
1  0  0  0  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  1  0  1  0  0  0  
1  0  0  0  0  0  0  1  0  0  0  0  0  0  

minimální cesta:  2085
0  0  1  0  0  0  0  0  0  0  0  0  0  0  1  0  
0  0  0  1  0  0  0  0  1  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  1  0  0  0  1  0  0  
0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  
1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  1  
0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  0  
0  0  0  0  1  1  0  0  0  0  0  0  0  0  0  0  
0  0  0  1  0  0  0  0  0  0  1  0  0  0  0  0  
1  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  
0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  
0  0  1  0  0  1  0  0  0  0  0  0  0  0  0  0  
0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  1  
0  1  0  0  0  0  0  0  0  0  0  0  1  0  0  0  
0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  
0  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0

Bin packing

Zjistěte, do kolika nejméně krabic lze rozdělit množinu $n$ předmětů s vahami $w_1, \ldots, w_i$ . Do každého koše lze umístit předměty o celkové váze nejvýše $C$ .

Zdrojový kód

from pulp import *
from itertools import *

bins_lists = [
    (100, [70, 60, 50, 33, 33, 33, 11, 7, 3]),
    (100, [99, 94, 79, 64, 50, 46, 43, 37, 32, 19, 18, 7, 6, 3]),
    (100, [49, 41, 34, 33, 29, 26, 26, 22, 20, 19]),
    (524, [442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 46, 37, 37, 12, 12, 12, 10, 10, 10, 10, 10, 10, 9, 9]),
]

for maximum_bin_load, weights in bins_lists:
    # počet objektů
    n = len(weights)

    # vytvoření modelu
    model = LpProblem(name="bin-packing", sense=LpMinimize)

    # proměnné -- binární x_{i, j}, zda i-tý objekt patří do j-tého koše
    # proměnná navíc ještě bude počet košů
    bin_count = LpVariable(name="bin count", lowBound=0, cat='Integer')
    variables = []
    for i in range(n):
        variables.append([])
        for j in range(n):
            variables[-1].append(LpVariable(name=f"x_{i}_{j}", cat='Binary'))

    # omezení
    ## v každém koši je nejvýše tolik, kolik toho unese
    for j in range(n):
        model += lpSum([variables[i][j] * weights[i] for i in range(n)]) <= maximum_bin_load

    ## každý předmět byl umístěn do právě jednoho koše
    for i in range(n):
        model += lpSum([variables[i][j] for j in range(n)]) == 1

    ## navíc chceme, aby bin_count byl počet košů, tzn. je větší
    for i in range(n):
        for j in range(n):
            model += bin_count >= (j + 1) * variables[i][j]

    # funkce k minimalizaci -- počet košů
    model += bin_count

    # řešení (ignorujeme debug zprávy)
    status = model.solve(PULP_CBC_CMD(msg=False))

    print("počet košů:", int(bin_count.value()))
    for i in range(n):
        for j in range(n):
            if variables[i][j].value() != 0:
                print(f"předmět {i} (váha {weights[i]}): koš {j}")
    print()

Výpis

počet košů: 4
předmět 0 (váha 70): koš 2
předmět 1 (váha 60): koš 3
předmět 2 (váha 50): koš 0
předmět 3 (váha 33): koš 1
předmět 4 (váha 33): koš 1
předmět 5 (váha 33): koš 1
předmět 6 (váha 11): koš 2
předmět 7 (váha 7): koš 3
předmět 8 (váha 3): koš 3

počet košů: 7
předmět 0 (váha 99): koš 5
předmět 1 (váha 94): koš 0
předmět 2 (váha 79): koš 2
předmět 3 (váha 64): koš 4
předmět 4 (váha 50): koš 3
předmět 5 (váha 46): koš 6
předmět 6 (váha 43): koš 3
předmět 7 (váha 37): koš 1
předmět 8 (váha 32): koš 4
předmět 9 (váha 19): koš 2
předmět 10 (váha 18): koš 6
předmět 11 (váha 7): koš 6
předmět 12 (váha 6): koš 6
předmět 13 (váha 3): koš 1

počet košů: 3
předmět 0 (váha 49): koš 2
předmět 1 (váha 41): koš 0
předmět 2 (váha 34): koš 1
předmět 3 (váha 33): koš 0
předmět 4 (váha 29): koš 2
předmět 5 (váha 26): koš 1
předmět 6 (váha 26): koš 0
předmět 7 (váha 22): koš 2
předmět 8 (váha 20): koš 1
předmět 9 (váha 19): koš 1

počet košů: 7
předmět 0 (váha 442): koš 2
předmět 1 (váha 252): koš 4
předmět 2 (váha 252): koš 1
předmět 3 (váha 252): koš 0
předmět 4 (váha 252): koš 4
předmět 5 (váha 252): koš 1
předmět 6 (váha 252): koš 5
předmět 7 (váha 252): koš 0
předmět 8 (váha 127): koš 5
předmět 9 (váha 127): koš 5
předmět 10 (váha 127): koš 6
předmět 11 (váha 127): koš 6
předmět 12 (váha 127): koš 6
předmět 13 (váha 106): koš 3
předmět 14 (váha 106): koš 3
předmět 15 (váha 106): koš 6
předmět 16 (váha 106): koš 3
předmět 17 (váha 85): koš 3
předmět 18 (váha 84): koš 3
předmět 19 (váha 46): koš 2
předmět 20 (váha 37): koš 6
předmět 21 (váha 37): koš 3
předmět 22 (váha 12): koš 2
předmět 23 (váha 12): koš 2
předmět 24 (váha 12): koš 2
předmět 25 (váha 10): koš 4
předmět 26 (váha 10): koš 4
předmět 27 (váha 10): koš 0
předmět 28 (váha 10): koš 1
předmět 29 (váha 10): koš 1
předmět 30 (váha 10): koš 0
předmět 31 (váha 9): koš 5
předmět 32 (váha 9): koš 5

Partition problem

Zjistěte, zda množinu $n$ předmětů s vahami $w_1, \ldots, w_i$ jde rozdělit na dvě části tak, aby součty vah těchto částí byly stejné.

Zdrojový kód

from pulp import *
from itertools import *

bins_lists = [
    [2, 10, 3, 8, 5, 7, 9, 5, 3, 2],
    [771, 121, 281, 854, 885, 734, 486, 1003, 83, 62],
    [484, 114, 205, 288, 506, 503, 201, 127, 410],
    [19, 17, 13, 9, 6],
    [3, 4, 3, 1, 3, 2, 3, 2, 1],
]

for weights in bins_lists:
    # počet objektů
    n = len(weights)

    # vytvoření modelu
    model = LpProblem(name="bin-packing", sense=LpMinimize)

    # proměnné -- binární x_i, zda i-tý objekt patří do jedné nebo druhé části
    variables = [LpVariable(name=f"x_{i}", cat='Binary') for i in range(n)]

    # omezení
    ## součet obou částí se rovná
    model += lpSum([variables[i] * weights[i] for i in range(n)]) == lpSum([(1 - variables[i]) * weights[i] for i in range(n)])

    # funkce k minimalizaci -- nic! jedná se o rozhodovací problém

    # řešení (ignorujeme debug zprávy)
    status = model.solve(PULP_CBC_CMD(msg=False))

    print("velikost:", sum([int(variables[i].value()) * weights[i] for i in range(n)]))
    for i in range(n):
        print(int(variables[i].value()), weights[i])
    print()

Výpis

velikost: 27
2
10
3
8
5
7
9
5
3
2

velikost: 2640
771
121
281
854
885
734
486
1003
83
62

velikost: 1419
484
114
205
288
506
503
201
127
410

velikost: 32
19
17
13
9
6

velikost: 11
3
4
3
1
3
2
3
2
1

Pekárny a obchody (a)

V Kocourkově je $n$ pekáren a $m$ obchodů. Každý den $i$ -tá pekárna upeče $p_i \in \mathbb{N}$ rohlíků $n$ a $j$ -tý obchod prodá $o_j \in \mathbb{N}$ rohlíků, kde $\sum_{i = 1}^{n} p_i = \sum_{j = 1}^{m} o_j$ . Převoz jednoho rohlíku z $i$ -té pekárny do $j$ -tého obchodu stojí $c_{ij}$ korun.

Zdrojový kód

from pulp import *
from itertools import *

data = [
    ([2, 3, 8, 7, 5, 2], [10, 9, 5, 3],
    [[1, 3, 2, 4],
     [2, 2, 1, 3],
     [2, 3, 1, 3],
     [2, 4, 0, 0],
     [1, 5, 1, 2],
     [3, 4, 1, 2]]),
]

for p, o, c in data:
    # počet pekáren, počet obchodů
    n = len(p)
    m = len(o)

    # vytvoření modelu
    model = LpProblem(name="1-a", sense=LpMinimize)

    # proměnné -- x_{ij}, kolik i-tá pekárna doveze j-tému obchodu
    # proměnné jsou celočíselné a nezáporné
    x = []
    for i in range(n):
        x.append([])
        for j in range(m):
            x[-1].append(LpVariable(name=f"x_{i}_{j}", lowBound=0, cat='Integer'))

    # omezení
    ## každá pekárna rozveze všechny rohlíky
    for i in range(n):
        model += p[i] == lpSum([x[i][j] for j in range(m)])

    ## každý obchod získá potřebné rohlíky
    for i in range(m):
        model += o[i] == lpSum([x[j][i] for j in range(n)])

    # funkce k minimalizaci -- náklady
    model += lpSum([x[i][j] * c[i][j] for i in range(n) for j in range(m)])

    # řešení (ignorujeme debug zprávy)
    status = model.solve(PULP_CBC_CMD(msg=False))

    print("náklady:", int(model.objective.value()))
    for i in range(n):
        for j in range(m):
            print(int(int(x[i][j].value())), "\t", end="")
        print()
    print()

Výpis

náklady: 39
0 	0 	0 	
3 	0 	0 	
6 	0 	0 	
0 	4 	3 	
0 	0 	0 	
0 	1 	0 	

Pekárny a obchody (b)

Praxe v Kocourkově ukázala, že když $i$ -tá pekárna zásobuje $j$ -tý obchod, tak musí pro tuto trasu zajistit logistiku, která je stojí $l_{ij}$ . Logistiku $l_{ij} \ge 0$ je nutné platit pouze tehdy, když $i$ -tá pekárna zásobuje $j$ -tý obchod nenulovým počtem rohlíků, a její cena nezávisí na počtu převážených rohlíků. I nadále je nutné platit přepravné $c_{ij}$ . Zformulujte příslušnou úlohu LP.

Zdrojový kód

from pulp import *
from itertools import *

data = [
        ([2, 3, 8, 7, 5, 2], [10, 9, 5, 3],
            [[1, 3, 2, 4],
                [2, 2, 1, 3],
                [2, 3, 1, 3],
                [2, 4, 0, 0],
                [1, 5, 1, 2],
                [3, 4, 1, 2]],
            [[10, 3, 2, 1],
                [1, 3, 2, 3],
                [3, 1, 2, 2],
                [1, 2, 2, 3],
                [2, 2, 2, 4],
                [6, 4, 2, 1]]),
            ]

for p, o, c, l in data:
    # počet pekáren, počet obchodů
    n = len(p)
    m = len(o)

    # vytvoření modelu
    model = LpProblem(name="1-a", sense=LpMinimize)

    # proměnné -- x_{ijk}, zda i-tá pekárna doveze j-tému obchodu k rohlíků
    x = []
    for i in range(n):
        x.append([])
        for j in range(m):
            x[-1].append([])
            for k in range(p[i] + 1):
                x[-1][-1].append(LpVariable(name=f"x_{i}_{j}_{k}", cat='Binary'))

    # omezení
    ## nerozvážíme např. 2 a 3 rohlíky individuálně
    for i in range(n):
        for j in range(m):
            model += lpSum([x[i][j][k] for k in range(p[i] + 1)]) == 1

    ## každá pekárna rozveze všechny rohlíky
    for i in range(n):
        model += p[i] == lpSum([k * x[i][j][k] for j in range(m) for k in range(p[i] + 1)])

    ## každý obchod získá potřebné rohlíky
    for i in range(m):
        model += o[i] == lpSum([k * x[j][i][k] for j in range(n) for k in range(p[j] + 1)])

    # funkce k minimalizaci -- náklady
    model += lpSum([k * x[i][j][k] * c[i][j] for i in range(n) for j in range(m) for k in range(p[i] + 1)]) \
            + lpSum([x[i][j][k] * l[i][j] for i in range(n) for j in range(m) for k in range(1, p[i] + 1)])

    # řešení (ignorujeme debug zprávy)
    status = model.solve(PULP_CBC_CMD(msg=False))

    print("náklady:", int(model.objective.value()))
    for i in range(n):
        for j in range(m):
            for k in range(p[i] + 1):
                if x[i][j][k].value() == 1:
                    print(k, "\t", end="")
                    break
        print()
    print()

Výpis

náklady: 61
2 	0 	0 	
3 	0 	0 	
4 	0 	0 	
0 	3 	3 	
0 	0 	0 	
0 	2 	0 	

Největší nezávislá množina

Najděte co možná největší množinu vrcholů grafu takovou, že žádné dva nesdílejí hranu.

Zdrojový kód

from pulp import *

# seznamy (neorientovaných!) hran grafů
edges_lists = [
    # K_5
    [(1, 2), (3, 2), (2, 4), (3, 4), (5, 4), (3, 5), (1, 5), (2, 5), (3, 1), (1, 4)],
    # skoro K_6
    [(1, 2), (1, 3), (4, 3), (4, 5), (6, 5), (6, 2), (6, 1), (6, 4), (1, 4), (2, 5), (2, 3), (3, 5)],
    # cesta
    [(1, 2), (3, 2), (3, 4), (4, 5), (5, 6)],
]

for edges in edges_lists:
    # počet vrcholů
    n = len(set([u for u, v in edges] + [v for u, v in edges]))

    # vytvoření modelu
    model = LpProblem(sense=LpMaximize)

    # proměnné -- x[i] podle toho, zda vyberem i-tý vrchol
    variables = [LpVariable(name=f"x_{i}", cat='Binary') for i in range(n)]

    # omezení
    ## každá hrana musí být pokryta nejvýše jednou
    for u, v in edges:
        model += variables[u - 1] + variables[v - 1] <= 1

    # minimalizujeme počet vybraných vrcholů
    model += lpSum(variables)

    # řešení (ignorujeme debug zprávy)
    status = model.solve(PULP_CBC_CMD(msg=False))
    print("vybrané vrcholy: ", end="")
    for i in range(n):
        print(int(variables[i].value()), end=" ")
    print()

Výpis

vybrané vrcholy: 1 0 0 0 0 
vybrané vrcholy: 1 0 0 0 1 0 
vybrané vrcholy: 1 0 1 0 0 1 

Nejmenší vrcholové pokrytí

Najděte co možná nejmenší množinu vrcholů grafu takovou, že všechny hrany grafu obsahují alespoň jeden vrchol z této množiny.

Zdrojový kód

from pulp import *

# seznamy (neorientovaných!) hran grafů
edges_lists = [
    # K_5
    [(1, 2), (3, 2), (2, 4), (3, 4), (5, 4), (3, 5), (1, 5), (2, 5), (3, 1), (1, 4)],
    # skoro K_6
    [(1, 2), (1, 3), (4, 3), (4, 5), (6, 5), (6, 2), (6, 1), (6, 4), (1, 4), (2, 5), (2, 3), (3, 5)],
    # cesta
    [(1, 2), (3, 2), (3, 4), (4, 5), (5, 6)],
]

for edges in edges_lists:
    # počet vrcholů
    n = len(set([u for u, v in edges] + [v for u, v in edges]))

    # vytvoření modelu
    model = LpProblem(sense=LpMinimize)

    # proměnné -- x[i] podle toho, zda vyberem i-tý vrchol
    variables = [LpVariable(name=f"x_{i}", cat='Binary') for i in range(n)]

    # omezení
    ## každá hrana musí být pokryta alespoň jednou
    for u, v in edges:
        model += variables[u - 1] + variables[v - 1] >= 1

    # minimalizujeme počet vybraných vrcholů
    model += lpSum(variables)

    # řešení (ignorujeme debug zprávy)
    status = model.solve(PULP_CBC_CMD(msg=False))
    print("vybrané vrcholy: ", end="")
    for i in range(n):
        print(int(variables[i].value()), end=" ")
    print()

Výpis

vybrané vrcholy: 1 0 1 1 1 
vybrané vrcholy: 0 1 1 1 0 1 
vybrané vrcholy: 0 1 0 1 0 1 

slama.dev