1. naloga

Ovce

Novozelandski kmet ima n ovac. V času t morajo biti vse ovce ostrižene, saj bo takrat odprodal volno. Ima seznam m strižcev. Za vsakega ima dva podatka:

  • pi je plačilo, ki ga zahteva i-ti strižec za striženje ene ovce;
  • ti je čas, ki ga porabi i-ti strižec za striženje ene ovce.

Aparat za striženje pokuri za c denarnih enot elektrike na časovno enoto. Opiši postopek, ki iz teh podatkov ugotovi, kolikšen je najmanjši znesek, ki ga bo kmet plačal za striženje (najem delovne sile + elektrika), če delovno silo izbira optimalno. Vsi strižci lahko delajo hkrati in vsak ima svoj aparat za striženje. Tisti, ki začne striči ovco, jo mora tudi dokončati. Na voljo bo vedno dovolj delavcev, da bodo lahko v danem času ostrigli vse ovce.

Primer: recimo, da imamo n = 5 ovac, t = 12 enot časa, ceno elektrike c = 1 in dva strižca: enegas p1 = 6, t1 = 2 (drag, a hiter) in enega s p2 = 2, t2 = 5 (počasen, a cenejši). Potem se izkaže, da je najmanjši skupni strošek striženja enak 38 (dosežemo ga, če prvi strižec ostriže tri ovce, drugi pa dve).

PDF besedilo.