BIK-PA1 prva uloha

answered 2015-11-07 16:37:14 +0100

Josef Kokeš
2956 ●20 ●35 ●73

updated 2015-11-07 18:13:02 +0100

Hmm, radši ve formě odpovědi, ať je na to dost místa. Podotýkám, že nemám přístup na ProgTest, vycházím ze zadání, jak je napsané na Fit-Wiki - pokud tam není přesně, tak ta moje odpověď nemusí být správně.

Akým vzorcom je potrebné

Vzorec není potřeba. Tohle není úvaha na vzorce, dá se to vyřešit prostou úvahou. Pokud vysloveně chcete vzorec, dá se na to napasovat vážený aritmetický průměr. Ale IMHO je to zcela zbytečné.

Čo reprezentuju čísla

Čísla 0,33333 a 0,66667 z prvního zadání určují množství první resp. druhé látky, aby celkové množství (1,00000) bylo to zadané a koncentrace směsi byla také ta zadaná. Výpočet celkové koncentrace a celkového objemu je dle zadání zjednodušený proti realitě, což následně zjednodušuje i formulaci problému a jeho řešení.

Ještě k tomu vzorci

Dá se to řešit i formálním matematickým aparátem a pro těžší verzi zadání to možná bude i výhodné. Ta úloha se dá triviálně přeformulovat jako úloha lineárního programování s dvěma proměnnými a čtyřmi omezujícími podmínkami, což pak simplexová metoda dokáže snadno vyřešit. Akorát to je dost s dělem na vrabce, ta úloha je zcela jistě formulovaná tak, aby ji mohli vyřešit i studenti prvního ročníku, kteří nikdy o lineárním programování a simplexové metodě neslyšeli. Ale mohlo by to být dobré, pokud chcete porazit referenční řešení, zvlášť pokud nebudete psát obecnou simplexovou metodu, ale adaptujete si ji na tento konkrétní specifický příklad.

Standardní reformulace pro lineární programování:

# x, y ... kolik gramů první resp. druhé látky se má použít pro získání koncentrace
MAX 1 # Chceme jakékoliv vyhovující řešení, nepotřebujeme optimalizovat na to nejlepší z nich
SUBJECT TO
  x, y <= dostupné množství první resp. druhé látky
  x, y >= 0
  x + y = požadované množství směsi
  x*koncentrace_x + y*koncentrace_y = požadovaná koncentrace směsi

Ještě k využití simplexové metody

Co jsem si to teď kreslil (velmi nahrubo, bez konkrétních čísel, takže mi možná někde něco zásadního uteklo - ale řekl bych, že ne), vychází mi, že to konkrétní specifické řešení pro tento soubor příkladů by mělo spočívat ve výpočtu průsečíku dvou přímek a ověření čtyř triviálních podmínek. Ten průsečík se také dá zformulovat jako "vzoreček" pro x a pro y, takže ve finále skutečně jde jen o dosazení do dvou vzorečků a ověření, že získaný výsledek vyhovuje zadání. Vřele doporučuji, nakreslete si úlohu jako obrázek, zauvažujte nad ní jako nad abstraktním problémem z analytické geometrie a teprve potom se pusťte do programování; zjistíte nejspíš, že vlastně ani nic moc programovat nemusíte - takhle od pohledu bych to viděl na dva jednoduché výpočty s přiřazením výsledku do proměnných a test čtyř podmínek. Jediný "komplikovaný" případ (ve smyslu přidání dalších řádek kódu) by byl, kdyby koncentrace všech látek (zdrojové i cílové) byly shodné.