Boiler

První termín odevzdání je 12.3.2017, druhý termín odevzdání je 26.3.2017.

Popis problému

Obyvatelé jisté obce se rozhodli zkusit efektivněji využívat energii. Zatím nemají mnoho zkušeností s pokročilým řízením energetických sítí, a tak nechtějí se hned na začátku pouštět do megalomanských projektů. V prvním experimentu zkusí centrálně řídit spouštění a vypínání elektrických boilerů B_1, ..., B_N, kde N je počet domů vybavených boilerem, a budou se snažit minimalizovat fluktuaci celkové spotřeby elektrické energie všech boilerů v následujících několika dnech. Cílem je tedy najít takový plán řízení všech boilerů, že rozdíl mezi největší a nejmenší celkovou spotřebou elektřiny v průběhu plánovacího období byl co nejmenší.

Pro zjednodušení problému si plánovací období časové intervaly 1, ..., T stejných délek. V každém časovém intervalu je každý boiler zapnutý nebo vypnutý a přepínat je možné jen na začátku každého intervalu.

Boiler můžeme zjednodušeně popsat jako velkou nádobu plnou vody, která se ohřívá, jestliže je boiler zapnutý, a chladne při spotřebě horhé vody (například sprchování). Jestliže je boiler B_b v nějakém časovém intervalu zapnutý, pak v tomto intervalu spotřebuje P_b elektrické energie a vodě dodá T_b tepelné energie. Když je boiler vypnutý, tak nespotřebovává elektrickou ani nevytváří tepelnou energii. Minimální množství energie v boileru je 0, což odpovídá situaci, kdy teplota vody je stejná jako teplota okolí. Maximální množství energie v boileru je M_b, což je energie vody při maximální teplotě (všimněte si, že M_b je součin objemu body v boileru, měrné tepelné kapacitě vody, hustoty vody a rozdílu maximální a minimální teploty vody). Počáteční množství energie (na začátku intervalu 1) v boileru B_b je I_b a na konečné množství energie (na konci intervalu T) musí být alespoň M_b/2.

K předpovídání spotřeby horké vody v domácnostech radní obce ustanovili speciální tým, který pomocí různých nástrojů (například neuronových sítí) spotřebuje odhaduje. Problematice predikce dat se v tomto úkolu věnovat nebudeme a budeme předpokládat, že odhady jsou přesné. Označme tedy S_bt spotřebu horké vody z boileru b v časovém intervalu t. Množství energie v boileru B_b se v časovém intervalu sníží o S_bt a je-li zapnutý, tak se množství energie zvýší o T_b. Na konci každého intervalu musí množství energie být mezi 0 a M_b.

Napište program, najde plán řízení všech boilerů takový, že rozdíl mezi největší a nejmenší celkovou spotřebou elektřiny v průběhu plánovacího období je co nejmenší.

Formát dat

Váš program musí zadání číst ze standardního vstupu a výsledek vypsat na standardní výstup. Na prvním řádku vstupu jsou dvě čísla udávající počet boilerů N a počet časových intervalů T. Na dalších N řádcích jsou parametry boilerů a jeden řádek vždy odpovídá jednomu boileru s následujícími hodnotami v tomto pořadí.
  • Elektrický příkon boileru P_b
  • Produkce tepelné energie T_b
  • Maximální množství energie M_b
  • Počáteční množství energie I_b
  • Spotřeba tepelné energie B_b1, ..., B_bT v časových intervalech 1, ..., T
Hodnoty T_b, M_b, I_b a S_bt jsou ve stejných jednotkách. Na prvním řádku výstupu musí být optimální hodnota cílové funkce (rozdíl mezi největší a nejmenší celkovou spotřebou elektřiny). Na dalších N řádcích je popsán optimální plán řízení boilerů, každý řádek obsahuje T čísel 0 (boiler je vypnutý) nebo 1 (boiler je zapnutý), jedno číslo pro jeden časový interval v pořadí 1, ..., T. Pořadí boilerů na výstupu musí být stejné jako na vstupu.

Příklad vstupu


3 10
50 45 120 20 0 10 0 60 5 15 100 52 0 10
70 63 150 145 70 0 5 100 3 45 16 57 1 56
60 55 130 70 13 40 55 0 70 4 45 3 40 17

Příklad výstupu


60
0 1 1 0 1 1 1 1 1 0
1 0 0 1 0 1 0 1 0 1
0 1 1 0 1 0 1 0 1 1

Odevzdání

Vaše řešení odevzdejte e-mailem vyučujícímu. Řešení musí obsahovat následující.
  • Zdrojové kódy (pokud je složen z více souborů, zabalte je ZIPem nebo TARem do jednoho).
  • Postup kompilace (pokud zdrojový kód máte rozdělený do více než jednoho souboru, pak přidejte Makefile).
  • Popis vašeho algoritmu ve formátu PDF s důkazem korektnosti.

Hodnocení

Váš program musí správně vyřešit libovolné zadání, pokud jej necháme běžet dostatečně dlouho na počítači s dostatečným množstvím paměti. Hlavním kritériem pro určení počtu bodů, které z tohoto domácího úkolu získáte, je maximální velikost vstupu, který váš program zvládne vyřešit během jedné minuty.

Dále budeme zohledňovat kvalitu kódu a dokumentace.

Testovací data

Vstupní testovací soubor obsahuje 10 vstupních testovacích souborů.

Pravidla

  • Veškerý odevzdaný kód musí být originální tedy vytvořen vámi bez jakékoliv vedlejší „inspirace“.
  • Svůj kód s nikým nesdílejte, aby se váš kód nestal něčí „inspirací“. Výjimku tvoří odevzdání kódu.
  • Povolená jsou řešení v jazycích C/C++ (doporučený jazyk), BASH (awk), Python a Sage. Volba dalších jazyků závisí na vyučujícím.
  • K řešení úloh (celočíselného) lineární programování můžete používat knihovnu GLPK nebo nadstavbový program GLPSOL. Problém lineární programování též můžete popsat v jazyce MathProg a poté použít GLPSOL k nalezení optimálního řešení. Ostatní řešiče můžou být povoleny pouze po předchozí domluvě s vyučujícím.
  • Váš program musí být jednoduše zkompilovatelný a spustitelný na systému GNU/Linux bez netriviálních závislostí. O netriviálnosti rozhoduje vyučujícím. Například v C++ byste si měli vystačit s se standardními knihovnami a glpk.
  • Nedodržení formátu výstupu povede k zamítnutí vašeho řešení.

Rady

  • Přečtěte si pořádně zadání.
  • Před odevzdáním si váš program vyzkoušejte v Unixové laboratoři na Malé Straně. Na případné problémy tak můžete přijít sami a nebude zbytečně ztrácet body.