Cvičení 3: Rozhodnutí ano/ne a logické vazby

Řešení.

Otevřete notebook v Jupyteru nebo Google Colabu. Buňky spouštějte shora dolů pomocí Shift+Enter. Hlavní příklad i krátké demonstrace obsahují úplný kód; v sekci 9 je malý úkol k samostatnému doplnění. V sekci 10 najdete odkaz na samostatný domácí úkol. Data jsou modelová.

Používáme Python 3.12 nebo novější a PuLP 3.3.2, stejně jako ve C2. Nejprve spusťte instalační buňku v sekci 0; případný požadavek na restart jádra (v Colabu relace) se zobrazí přímo v jejím výstupu. Následující kód je určen pro tuto verzi; PuLP 4 má jiné rozhraní.

0. Příprava prostředí — spusťte jako první

Tato buňka nainstaluje PuLP 3.3.2 do prostředí aktuálního notebooku, pokud správná verze chybí. Stačí ji spustit; příkazy není potřeba upravovat.

Pokud už máte v paměti PuLP 4, buňka po instalaci výpočet zastaví a vyzve k restartu relace/jádra. V Colabu otevřete nabídku Runtime (Běhové prostředí) a zvolte restart relace; v Jupyteru Kernel → Restart Kernel. Potom spusťte notebook znovu shora. Samotné opakování import pulp starou verzi z paměti neodstraní. Po hlášení „Připraveno“ můžete pokračovat. Instalace vyžaduje připojení k internetu.

import sys
import subprocess
from importlib.metadata import version, PackageNotFoundError

REQUIRED_PULP = "3.3.2"
try:
    installed_pulp = version("pulp")
except PackageNotFoundError:
    installed_pulp = None

if installed_pulp != REQUIRED_PULP:
    subprocess.check_call([
        sys.executable, "-m", "pip", "install", "--quiet",
        "--disable-pip-version-check", "--no-cache-dir", "pulp==3.3.2"
    ])
if version("pulp") != REQUIRED_PULP:
    raise RuntimeError("PuLP 3.3.2 se nenainstalovalo. Zkontrolujte výpis instalace výše.")

loaded_pulp = sys.modules.get("pulp")
if loaded_pulp is not None and getattr(loaded_pulp, "__version__", None) != REQUIRED_PULP:
    raise RuntimeError(
        "PuLP 3.3.2 je nainstalované, ale v paměti zůstává jiná verze. "
        "V Colabu zvolte Runtime > Restart session (případně Restart runtime). "
        "V Jupyteru zvolte Kernel > Restart Kernel. Potom spusťte všechny buňky shora."
    )
print("Připraveno: PuLP 3.3.2 je nainstalované. Pokračujte dalšími buňkami.")

Připraveno: PuLP 3.3.2 je nainstalované. Pokračujte dalšími buňkami.

Co si dnes vyzkoušíme

V C2 jsme sestavili model a přečetli výsledek. Dnes se naučíme zapsat podmínky typu „nejvýše jedna možnost“, „právě jedna možnost“ a „B jen tehdy, když A“.

Nejprve si řekneme, které kombinace mají být dovoleny. Potom napíšeme omezení a ověříme, zda skutečně vyjadřuje zamýšlené pravidlo.

import pulp

if pulp.__version__ != "3.3.2":
    raise RuntimeError("Spusťte sekci 0 a postupujte podle pokynu k restartu.")
print("PuLP:", pulp.__version__)
TOL = 1e-7

PuLP: 3.3.2

1. Zadání: program studentské akce

Připravujeme studentskou akci a vybíráme z pěti aktivit. Každou buď uskutečníme celou, nebo ji vynecháme. Žádnou neopakujeme a zatím nemáme předepsáno, kolik jich musíme vybrat.

Máme nejvýše 10 tisíc Kč a celkem 10 člověkohodin organizátorů. Člověkohodina je hodina práce jednoho člověka: dva lidé pracující dvě hodiny spotřebují čtyři člověkohodiny. Nejde o délku programu a nesestavujeme časový rozvrh.

Kód	Aktivita	Náklady [tis. Kč]	Čas [člověkohodiny]	Přínos [body]
A	Robotická dílna	4	3	9
B	Programovací dílna	3	4	8
C	Vědecký kvíz	3	2	6
D	Astronomická přednáška	2	2	4
E	Noční pozorování	3	3	9

Data jsou umělá. Body vyjadřují hodnocení organizátorů a v tomto modelu se sčítají; nejsou počtem různých návštěvníků. Také náklady a čas se sčítají, nezávisle na ostatních vybraných aktivitách. Hledáme výběr s nejvyšším celkovým přínosem.

V základní úloze další podmínky nejsou. Organizační pravidla přidáme později, každé nejprve zvlášť.

2. Proměnná znamená rozhodnutí ano/ne

Pro každou aktivitu $i\in\{A,B,C,D,E\}$ zavedeme proměnnou $$y_i=\begin{cases}1,&\text{aktivitu uskutečníme},\\0,&\text{aktivitu vynecháme}.\end{cases}$$ Taková proměnná je binární. Neměří počet návštěvníků ani množství aktivity. Hodnota $0{,}5$ by znamenala půl aktivity, což zadání nedovoluje.

Model na papíře

$$\begin{aligned} \max\quad &9y_A+8y_B+6y_C+4y_D+9y_E &&\text{(body)},\\ \text{za podmínek}\quad &4y_A+3y_B+3y_C+2y_D+3y_E\le10 &&\text{(tisíce Kč)},\\ &3y_A+4y_B+2y_C+2y_D+3y_E\le10 &&\text{(člověkohodiny)},\\ &y_A,y_B,y_C,y_D,y_E\in\{0,1\}. \end{aligned}$$ Například člen $4y_A$ znamená: robotická dílna stojí 4 tisíce Kč, pokud ji zvolíme, a 0 Kč, pokud ji vynecháme.

3. Sestavení modelu po krocích

Krok 1: vstupní data

S pěti aktivitami už se vyplatí uložit údaje do slovníků. cost["A"] znamená náklad aktivity A. Seznam activities určuje, přes které aktivity budeme procházet.

Hodnota rozpočtu je 10, protože náklady zadáváme v tisících Kč. Záměnou za 10000 bychom vytvořili jinou úlohu.

activities = ["A", "B", "C", "D", "E"]
cost = {"A": 4, "B": 3, "C": 3, "D": 2, "E": 3}
hours = {"A": 3, "B": 4, "C": 2, "D": 2, "E": 3}
benefit = {"A": 9, "B": 8, "C": 6, "D": 4, "E": 9}
budget = 10
time_limit = 10

print(cost["A"])

4

Krok 2: prázdná maximalizační úloha

LpProblem a LpMaximize známe ze C2. Při opakovaném sestavování začněte znovu touto buňkou a pokračujte dolů, aby se omezení nepřidávala podruhé.

model = pulp.LpProblem("student_event", pulp.LpMaximize)

Krok 3: pět binárních proměnných

cat="Binary" dovoluje pouze hodnoty 0 a 1. Samotné meze lowBound=0, upBound=1 u spojité proměnné by nestačily: dovolovaly by i zlomky.

Do prázdného slovníku y vložíme jednu proměnnou pro každou aktivitu. Cyklus se postupně provede pro A, B, C, D a E. Zápis f"y_{i}" vytvoří názvy y_A, y_B a tak dále. y["A"] zatím označuje proměnnou modelu, nikoli nalezené číslo.

y = {}
for i in activities:
    y[i] = pulp.LpVariable(f"y_{i}", cat="Binary")

print(y)

{'A': y_A, 'B': y_B, 'C': y_C, 'D': y_D, 'E': y_E}

Krok 4: účelová funkce jako součet

Na papíře jsme napsali pět členů. pulp.lpSum(benefit[i] * y[i] for i in activities) udělá totéž: pro každou aktivitu vytvoří člen a všechny sečte. Následující buňka zatím pouze vypíše výraz $9y_A+8y_B+6y_C+4y_D+9y_E$.

print(pulp.lpSum(benefit[i] * y[i] for i in activities))

9*y_A + 8*y_B + 6*y_C + 4*y_D + 9*y_E

Teď výraz přidáme do modelu jako účelovou funkci. Stejně jako ve C2 používáme +=; výraz nemá nerovnost ani rovnost.

model += pulp.lpSum(benefit[i] * y[i] for i in activities), "benefit"

Krok 5: rozpočet

Za vybranou aktivitu zaplatíme její celý náklad, za nevybranou nic. Všechny náklady se sečtou a nesmějí překročit společný rozpočet.

model += pulp.lpSum(cost[i] * y[i] for i in activities) <= budget, "budget"

Krok 6: čas organizátorů

Stejným způsobem sečteme člověkohodiny. Rozpočet a čas jsou dvě různé podmínky s různými jednotkami.

model += pulp.lpSum(hours[i] * y[i] for i in activities) <= time_limit, "time"

Krok 7: kontrola zapsaného modelu

Ve výpisu najděte účelovou funkci, obě omezení a pět proměnných. PuLP 3.3.2 může binární proměnné vypisovat jako 0 <= y_A <= 1 Integer. Celočíselnost společně s těmito mezemi právě dovoluje jen 0 a 1.

print(model)

student_event:
MAXIMIZE
9*y_A + 8*y_B + 6*y_C + 4*y_D + 9*y_E + 0.0
SUBJECT TO
budget: 4 y_A + 3 y_B + 3 y_C + 2 y_D + 3 y_E <= 10

time: 3 y_A + 4 y_B + 2 y_C + 2 y_D + 3 y_E <= 10

VARIABLES
0 <= y_A <= 1 Integer
0 <= y_B <= 1 Integer
0 <= y_C <= 1 Integer
0 <= y_D <= 1 Integer
0 <= y_E <= 1 Integer

4. Řešení a čtení výstupu

Model vyřešíme pomocí CBC. Nejdříve přečteme stav, teprve po potvrzení Optimal hodnoty proměnných a hodnotu účelové funkce. Výpis 1.0 znamená vybranou aktivitu, 0.0 vynechanou.

Seznam na konci vybere kódy s hodnotou větší než 0.5. U binárního řešení tím pohodlně odlišíme jedničky od nul; není to postup pro zaokrouhlení spojitého řešení.

status = model.solve(pulp.PULP_CBC_CMD(msg=False))
print(pulp.LpStatus[status])
if status == pulp.LpStatusOptimal:
    for i in activities:
        print(i, y[i].value())
    print("Vybrané aktivity:", [i for i in activities if y[i].value() > 0.5])
    print("Přínos [body]:", pulp.value(model.objective))

Optimal
A 1.0
B 1.0
C 0.0
D 0.0
E 1.0
Vybrané aktivity: ['A', 'B', 'E']
Přínos [body]: 26.0

Výsledek znamená: uskutečnit A, B a E, s celkovým přínosem 26 bodů. Oba workshopy jsou zatím povoleny a pozorování zatím nevyžaduje přednášku; tyto podmínky v základním modelu nejsou.

Kontrola dosazením do zadání

Z nalezených nul a jedniček přepočítáme náklady, čas a přínos. Zde sčítáme čísla, proto stačí vestavěné sum. Pomocí all(...) ověříme, že každá hodnota leží u nuly nebo jedničky. Tolerance TOL = 1e-7 je absolutní, v jednotkách dané kontroly. assert zastaví buňku, pokud kontrola neprojde.

if status == pulp.LpStatusOptimal:
    used_cost = sum(cost[i] * y[i].value() for i in activities)
    used_time = sum(hours[i] * y[i].value() for i in activities)
    checked_benefit = sum(benefit[i] * y[i].value() for i in activities)
    binary_ok = all(
        min(abs(y[i].value()), abs(y[i].value() - 1)) <= TOL
        for i in activities
    )
    print("Náklady [tis. Kč]:", used_cost, "/", budget)
    print("Čas [člověkohodiny]:", used_time, "/", time_limit)
    print("Přínos přepočtený z dat [body]:", checked_benefit)
    print("Binarita:", binary_ok)
    assert used_cost <= budget + TOL and used_time <= time_limit + TOL
    assert binary_ok
    assert abs(checked_benefit - pulp.value(model.objective)) <= TOL

Náklady [tis. Kč]: 10.0 / 10
Čas [člověkohodiny]: 10.0 / 10
Přínos přepočtený z dat [body]: 26.0
Binarita: True

Spotřebujeme 10 tisíc Kč a 10 člověkohodin. Při přepočtu vycházíme z původních dat; jejich slovníky proto ještě porovnáme s tabulkou zadání. Samotná kontrola přípustnosti neprokazuje optimalitu, tu zde přebíráme ze stavu řešiče.

Každou následující variantu sestavíme jako nový model s novými proměnnými. Vždy vyjdeme ze základu a přidáme jen pravidlo právě probírané sekce. Pravidla tedy zatím nekumulujeme.

5. Nejvýše jedna možnost

Organizátoři chtějí vybrat nejvýše jeden z workshopů A a B. Smíme vybrat A, B nebo ani jeden; nesmíme vybrat oba.

$y_A$	$y_B$	$y_A+y_B$	Dovoleno?
0	0	0	ano
0	1	1	ano
1	0	1	ano
1	1	2	ne

Tabulka přesně odpovídá omezení $y_A+y_B\le1$. Tabulka posuzuje pouze toto pravidlo; celý model musí splnit i rozpočet a čas. Než spustíte další buňky, zkuste odhadnout, zda původní výběr A, B, E projde.

exclusive_model = pulp.LpProblem("exclusive", pulp.LpMaximize)
exclusive_y = {}
for i in activities:
    exclusive_y[i] = pulp.LpVariable(f"exclusive_y_{i}", cat="Binary")
exclusive_model += pulp.lpSum(benefit[i] * exclusive_y[i] for i in activities), "benefit"
exclusive_model += pulp.lpSum(cost[i] * exclusive_y[i] for i in activities) <= budget, "budget"
exclusive_model += pulp.lpSum(hours[i] * exclusive_y[i] for i in activities) <= time_limit, "time"

exclusive_model += exclusive_y["A"] + exclusive_y["B"] <= 1, "one_workshop_at_most"

exclusive_status = exclusive_model.solve(pulp.PULP_CBC_CMD(msg=False))
print(pulp.LpStatus[exclusive_status])
if exclusive_status == pulp.LpStatusOptimal:
    for i in activities:
        print(i, exclusive_y[i].value())
    print("Vybrané aktivity:", [i for i in activities if exclusive_y[i].value() > 0.5])
    print("Přínos [body]:", pulp.value(exclusive_model.objective))

Optimal
A 1.0
B 0.0
C 1.0
D 0.0
E 1.0
Vybrané aktivity: ['A', 'C', 'E']
Přínos [body]: 24.0

Vybereme A, C a E, přínos 24 bodů. Původní výběr obsahoval oba workshopy a nové pravidlo porušoval. Teď ověříme kapacity, binaritu i novou podmínku.

if exclusive_status == pulp.LpStatusOptimal:
    used_cost = sum(cost[i] * exclusive_y[i].value() for i in activities)
    used_time = sum(hours[i] * exclusive_y[i].value() for i in activities)
    checked_benefit = sum(benefit[i] * exclusive_y[i].value() for i in activities)
    binary_ok = all(
        min(abs(exclusive_y[i].value()), abs(exclusive_y[i].value() - 1)) <= TOL
        for i in activities
    )
    print("Náklady [tis. Kč]:", used_cost, "/", budget)
    print("Čas [člověkohodiny]:", used_time, "/", time_limit)
    print("Přínos přepočtený z dat [body]:", checked_benefit)
    print("Binarita:", binary_ok)
    assert used_cost <= budget + TOL and used_time <= time_limit + TOL
    assert binary_ok
    assert abs(checked_benefit - pulp.value(exclusive_model.objective)) <= TOL
    rule_ok = exclusive_y["A"].value() + exclusive_y["B"].value() <= 1 + TOL
    print("Nejvýše jedna z A a B:", rule_ok)
    assert rule_ok

Náklady [tis. Kč]: 10.0 / 10
Čas [člověkohodiny]: 8.0 / 10
Přínos přepočtený z dat [body]: 24.0
Binarita: True
Nejvýše jedna z A a B: True

6. Právě jedna možnost

Nyní začneme znovu od základního modelu. Organizátoři vyžadují právě jednu z aktivit C a D: buď kvíz, nebo astronomickou přednášku. Tentokrát nesmíme vynechat obě.

$y_C$	$y_D$	$y_C+y_D$	Dovoleno?
0	0	0	ne
0	1	1	ano
1	0	1	ano
1	1	2	ne

Pravidlo zapisujeme $y_C+y_D=1$, v Pythonu pomocí ==. Jedno = by bylo přiřazení. Ve srovnání s „nejvýše jednou“ navíc zakazujeme součet 0.

Do této varianty nepřenášíme omezení na workshopy A a B.

exactly_model = pulp.LpProblem("exactly", pulp.LpMaximize)
exactly_y = {}
for i in activities:
    exactly_y[i] = pulp.LpVariable(f"exactly_y_{i}", cat="Binary")
exactly_model += pulp.lpSum(benefit[i] * exactly_y[i] for i in activities), "benefit"
exactly_model += pulp.lpSum(cost[i] * exactly_y[i] for i in activities) <= budget, "budget"
exactly_model += pulp.lpSum(hours[i] * exactly_y[i] for i in activities) <= time_limit, "time"

exactly_model += exactly_y["C"] + exactly_y["D"] == 1, "one_of_quiz_and_talk"

exactly_status = exactly_model.solve(pulp.PULP_CBC_CMD(msg=False))
print(pulp.LpStatus[exactly_status])
if exactly_status == pulp.LpStatusOptimal:
    for i in activities:
        print(i, exactly_y[i].value())
    print("Vybrané aktivity:", [i for i in activities if exactly_y[i].value() > 0.5])
    print("Přínos [body]:", pulp.value(exactly_model.objective))

Optimal
A 1.0
B 0.0
C 1.0
D 0.0
E 1.0
Vybrané aktivity: ['A', 'C', 'E']
Přínos [body]: 24.0

Opět vybereme A, C a E, přínos 24 bodů. Stejný výsledek neznamená stejná omezení: například prázdný výběr vyhovuje pravidlu z předchozí sekce, ale ne požadavku právě jedné z C a D.

if exactly_status == pulp.LpStatusOptimal:
    used_cost = sum(cost[i] * exactly_y[i].value() for i in activities)
    used_time = sum(hours[i] * exactly_y[i].value() for i in activities)
    checked_benefit = sum(benefit[i] * exactly_y[i].value() for i in activities)
    binary_ok = all(
        min(abs(exactly_y[i].value()), abs(exactly_y[i].value() - 1)) <= TOL
        for i in activities
    )
    print("Náklady [tis. Kč]:", used_cost, "/", budget)
    print("Čas [člověkohodiny]:", used_time, "/", time_limit)
    print("Přínos přepočtený z dat [body]:", checked_benefit)
    print("Binarita:", binary_ok)
    assert used_cost <= budget + TOL and used_time <= time_limit + TOL
    assert binary_ok
    assert abs(checked_benefit - pulp.value(exactly_model.objective)) <= TOL
    rule_ok = abs(exactly_y["C"].value() + exactly_y["D"].value() - 1) <= TOL
    print("Právě jedna z C a D:", rule_ok)
    assert rule_ok

Náklady [tis. Kč]: 10.0 / 10
Čas [člověkohodiny]: 8.0 / 10
Přínos přepočtený z dat [body]: 24.0
Binarita: True
Právě jedna z C a D: True

7. Jedna aktivita vyžaduje druhou

Znovu začneme od základního modelu. Organizátoři tentokrát stanovili, že noční pozorování E smí proběhnout jen společně s astronomickou přednáškou D, která účastníky připraví. Samotná přednáška D je dovolena.

$y_D$	$y_E$	Dovoleno?	Význam
0	0	ano	nevybereme ani jednu
0	1	ne	pozorování bez přednášky
1	0	ano	samotná přednáška
1	1	ano	přednáška i pozorování

Potřebujeme zakázat jedinou kombinaci: $y_E=1$, $y_D=0$. To přesně zajistí $y_E\le y_D$.

Pozor na směr: $y_D\le y_E$ by vyjadřovalo opačný požadavek. Rovnost $y_E=y_D$ by zakázala i samotnou přednášku a znamenala by „obě, nebo žádná“. Ani jedno není naše zadání.

requires_model = pulp.LpProblem("requires", pulp.LpMaximize)
requires_y = {}
for i in activities:
    requires_y[i] = pulp.LpVariable(f"requires_y_{i}", cat="Binary")
requires_model += pulp.lpSum(benefit[i] * requires_y[i] for i in activities), "benefit"
requires_model += pulp.lpSum(cost[i] * requires_y[i] for i in activities) <= budget, "budget"
requires_model += pulp.lpSum(hours[i] * requires_y[i] for i in activities) <= time_limit, "time"

requires_model += requires_y["E"] <= requires_y["D"], "observation_requires_talk"

requires_status = requires_model.solve(pulp.PULP_CBC_CMD(msg=False))
print(pulp.LpStatus[requires_status])
if requires_status == pulp.LpStatusOptimal:
    for i in activities:
        print(i, requires_y[i].value())
    print("Vybrané aktivity:", [i for i in activities if requires_y[i].value() > 0.5])
    print("Přínos [body]:", pulp.value(requires_model.objective))

Optimal
A 1.0
B 1.0
C 1.0
D 0.0
E 0.0
Vybrané aktivity: ['A', 'B', 'C']
Přínos [body]: 23.0

Vybereme A, B a C, přínos 23 bodů. Přednášku ani pozorování nezvolíme. Nové pravidlo totiž nevyžaduje uskutečnit E; pouze stanoví podmínku pro případ, že E vybereme. Nulové hodnoty D a E tedy pravidlo splňují.

if requires_status == pulp.LpStatusOptimal:
    used_cost = sum(cost[i] * requires_y[i].value() for i in activities)
    used_time = sum(hours[i] * requires_y[i].value() for i in activities)
    checked_benefit = sum(benefit[i] * requires_y[i].value() for i in activities)
    binary_ok = all(
        min(abs(requires_y[i].value()), abs(requires_y[i].value() - 1)) <= TOL
        for i in activities
    )
    print("Náklady [tis. Kč]:", used_cost, "/", budget)
    print("Čas [člověkohodiny]:", used_time, "/", time_limit)
    print("Přínos přepočtený z dat [body]:", checked_benefit)
    print("Binarita:", binary_ok)
    assert used_cost <= budget + TOL and used_time <= time_limit + TOL
    assert binary_ok
    assert abs(checked_benefit - pulp.value(requires_model.objective)) <= TOL
    rule_ok = requires_y["E"].value() <= requires_y["D"].value() + TOL
    print("E pouze při D:", rule_ok)
    assert rule_ok

Náklady [tis. Kč]: 10.0 / 10
Čas [člověkohodiny]: 9.0 / 10
Přínos přepočtený z dat [body]: 23.0
Binarita: True
E pouze při D: True

8. Porovnání variant

Každý řádek vychází ze stejného základního modelu a přidává právě uvedené pravidlo.

Varianta	Přidané pravidlo	Výběr	Přínos [body]	Náklady [tis. Kč]	Čas [člověkohodiny]
Základ	žádné	A, B, E	26	10	10
Nejvýše jedna	$y_A+y_B\le1$	A, C, E	24	10	8
Právě jedna	$y_C+y_D=1$	A, C, E	24	10	8
E vyžaduje D	$y_E\le y_D$	A, B, C	23	10	9

Nové omezení při maximalizaci téže účelové funkce nemůže nejlepší dosažitelný přínos zvýšit: dovoluje jen některé z původně přípustných výběrů. U jiných dat se optimální hodnota nemusí změnit; nové pravidlo také může způsobit nepřípustnost.

Pro vlastní projekt vždy začněte slovním významem pravidla. Vyzkoušejte několik povolených a zakázaných kombinací, zapište omezení a nakonec ověřte, že nalezené řešení splňuje původní požadavek. Samotný stav Optimal neodhalí, že jste napsali obrácenou implikaci.

9. Krátký samostatný úkol

Vraťte se k základní úloze a nyní přidejte současně dvě podmínky:

• Z workshopů A a B lze vybrat nejvýše jeden.
• Pozorování E smí proběhnout pouze při uskutečnění přednášky D.

Podmínku na právě jednu z C a D tentokrát nepřidávejte. Nejprve odhadněte, zda některý z dosavadních optimálních výběrů projde oběma požadavky. Potom sestavte nový model, vyřešte jej a vypište stav, výběr a přínos. Dosazením ověřte rozpočet, čas, binaritu i obě nová pravidla. Zkuste to bez kopírování hotových variant; kroky v sekci 3 slouží jako nápověda.

practice_model = pulp.LpProblem("practice", pulp.LpMaximize)
practice_y = {}
for i in activities:
    practice_y[i] = pulp.LpVariable(f"practice_y_{i}", cat="Binary")
practice_model += pulp.lpSum(benefit[i] * practice_y[i] for i in activities), "benefit"
practice_model += pulp.lpSum(cost[i] * practice_y[i] for i in activities) <= budget, "budget"
practice_model += pulp.lpSum(hours[i] * practice_y[i] for i in activities) <= time_limit, "time"

practice_model += practice_y["A"] + practice_y["B"] <= 1, "one_workshop_at_most"
practice_model += practice_y["E"] <= practice_y["D"], "observation_requires_talk"

practice_status = practice_model.solve(pulp.PULP_CBC_CMD(msg=False))
print(pulp.LpStatus[practice_status])
if practice_status == pulp.LpStatusOptimal:
    for i in activities:
        print(i, practice_y[i].value())
    print("Vybrané aktivity:", [i for i in activities if practice_y[i].value() > 0.5])
    print("Přínos [body]:", pulp.value(practice_model.objective))

Optimal
A 1.0
B 0.0
C 0.0
D 1.0
E 1.0
Vybrané aktivity: ['A', 'D', 'E']
Přínos [body]: 22.0

if practice_status == pulp.LpStatusOptimal:
    used_cost = sum(cost[i] * practice_y[i].value() for i in activities)
    used_time = sum(hours[i] * practice_y[i].value() for i in activities)
    checked_benefit = sum(benefit[i] * practice_y[i].value() for i in activities)
    binary_ok = all(
        min(abs(practice_y[i].value()), abs(practice_y[i].value() - 1)) <= TOL
        for i in activities
    )
    print("Náklady [tis. Kč]:", used_cost, "/", budget)
    print("Čas [člověkohodiny]:", used_time, "/", time_limit)
    print("Přínos přepočtený z dat [body]:", checked_benefit)
    print("Binarita:", binary_ok)
    assert used_cost <= budget + TOL and used_time <= time_limit + TOL
    assert binary_ok
    assert abs(checked_benefit - pulp.value(practice_model.objective)) <= TOL
    rule_ok = practice_y["A"].value() + practice_y["B"].value() <= 1 + TOL
    print("Nejvýše jedna z A a B:", rule_ok)
    assert rule_ok
    rule_ok = practice_y["E"].value() <= practice_y["D"].value() + TOL
    print("E pouze při D:", rule_ok)
    assert rule_ok

Náklady [tis. Kč]: 9.0 / 10
Čas [člověkohodiny]: 8.0 / 10
Přínos přepočtený z dat [body]: 22.0
Binarita: True
Nejvýše jedna z A a B: True
E pouze při D: True

Žádný z předchozích optimálních výběrů oběma pravidly neprojde: A, B, E a A, B, C obsahují oba workshopy; A, C, E obsahuje pozorování bez přednášky.

Nový výsledek je A, D a E, přínos 22 bodů. Spotřebujeme 9 tisíc Kč a 8 člověkohodin. Z workshopů zvolíme pouze A a pozorování má doprovodnou přednášku D. Zbývající zdroje nemusíme vyčerpat: podmínky mají tvar horních mezí, nikoli rovností.

10. Domácí úkol: malý výrobní projekt

Otevřete notebook k domácímu doplnění. Úloha se třemi kapalnými směsmi procvičuje samostatný postup: slovní zadání, oddělená data, model v PuLP, kontrolu výsledku a jednu změnu kapacity. Instalační buňka je stejná jako zde a ve C2.

Do notebooku doplňte kód i vlastní vysvětlení výsledků. Před dokončením restartujte jádro a spusťte všechny buňky shora. Řešení je v samostatném souboru, stejně jako u ostatních cvičení.