slama.dev

Lineární programování v Pythonu

21. 3. 2021

Ú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. 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 55 kilo mouky, 125125 vajec a půl kila soli. Za jeden chleba získá pekárna 2020 korun, za housku 22 koruny, za bagetu 1010 korun a za koblihu 77 korun. Pekárna se snaží vydělat co nejvíce. Jak ale zjistí kolik chlebů, housek, baget a koblih má 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 + 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 nn předmětů, kde ii-tý má nějakou váhu viv_i a cenu cic_i, máme batoh s danou nosností VV a my se do něj snažíme naskládat předměty tak, abychom maximalizovali celkovou cenu předmětů 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 nn bodů (x1,y1),,(xn,yn)(x_1 , y_1 ), \ldots, (x_n , y_n ) v rovině, tak najděte přímku {xR:y=ax+b}\left\{x \in \mathbb{R}: y = ax + b\right\}, která minimalizuje součet vertikálních vzdáleností bodů od výsledné přímky. Vertikální vzdálenost je vzdálenost měřena pouze na ose yy. Pro jednoduchost předpokládejte, že výsledná přímka není kolmá na osu xx.

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í kk takové, že vrcholy grafu GG lze korektně obarvit kk 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í kk takové, že hrany grafu GG lze korektně obarvit kk 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)G = (V, E, f), kde f:ER0+f : E \mapsto \mathbb{R}^+_0, chceme najít Hamiltonovskou kružnici v GG 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  0  1  1  0  
0  0  1  0  1  
1  1  0  0  0  
1  0  0  0  1  
0  1  0  1  0  

minimální cesta:  291
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  1  0  1  
0  0  0  0  0  0  1  0  0  0  0  1  0  0  0  
0  0  0  0  0  1  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  1  0  0  0  1  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  1  0  0  0  1  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  0  0  1  0  
1  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  0  1  0  
1  1  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  0  0  
0  1  0  0  0  0  0  0  1  0  0  0  0  0  0  

minimální cesta:  2085
0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  1  0  
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  0  1  0  0  0  1  0  0  
1  0  0  0  0  0  0  0  0  0  0  0  1  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  0  1  0  0  0  0  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  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  0  0  
0  1  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  0  0  0  
0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  1  0  
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  0  1  0  1  
0  0  1  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  1  0  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 nn předmětů s vahami w1,,wiw_1, \ldots, w_i. Do každého koše lze umístit předměty o celkové váze nejvýše CC.

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 nn předmětů s vahami w1,,wiw_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
1 2
1 10
0 3
1 8
1 5
0 7
0 9
0 5
0 3
1 2

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

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

velikost: 32
0 19
1 17
0 13
1 9
1 6

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

Pekárny a obchody (a)

V Kocourkově je nn pekáren a mm obchodů. Každý den ii-tá pekárna upeče piNp_i \in \mathbb{N} rohlíků nn a jj-tý obchod prodá ojNo_j \in \mathbb{N} rohlíků, kde i=1npi=j=1moj\sum_{i = 1}^{n} p_i = \sum_{j = 1}^{m} o_j. Převoz jednoho rohlíku z ii-té pekárny do jj-tého obchodu stojí cijc_{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
2 	0 	0 	0 	
0 	3 	0 	0 	
2 	6 	0 	0 	
0 	0 	4 	3 	
5 	0 	0 	0 	
1 	0 	1 	0 	

Pekárny a obchody (b)

Praxe v Kocourkově ukázala, že když ii-tá pekárna zásobuje jj-tý obchod, tak musí pro tuto trasu zajistit logistiku, která je stojí lijl_{ij}. Logistiku lij0l_{ij} \ge 0 je nutné platit pouze tehdy, když ii-tá pekárna zásobuje jj-tý obchod nenulovým počtem rohlíků, a její cena nezávisí na počtu převážených rohlíků. I nadále je nutné platit přepravné cijc_{ij}. Zformulujte příslušnou ú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
0 	2 	0 	0 	
0 	3 	0 	0 	
4 	4 	0 	0 	
1 	0 	3 	3 	
5 	0 	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 

Zdroje/materiály