Zadanie - programowanie liniowe

Mistrz optymalizacji poszukiwany

Poszukujemy osoby która opracuje algorytm rozwiązania zadania z dziedziny programowania liniowego, a następnie odpowie na pytania naszego programisty, który będzie to rozwiązanie implementował. Jeżeli algorytm będzie wykorzystywał gotową metodę (np. metodę SIMPLEX), będziemy potrzebowali teoretycznej pomocy w jej implementacji. Oczywiście za wsparcie przewidujemy wynagrodzenie ;)

ZADANIE:

Pieniądze z budżetu domowego są wydawane w kilku kategoriach (paliwo, rozrywka, zakupy spożywcze, itd.). Każda z Promocji Bankowych daje określony procentowo zwrot w conajmniej jednej z kategorii, przy czym kwota zwrotu może posiadać górny limit (np. promocja PB1 daje 3% zwrotu z kwoty wydanej na paliwo oraz 2% z "rozrywki"; promocja PB2 daje 5% zwrotu z kategorii "rozrywka", jednak nie więcej niż 40zł). Każdy z domowników może uczestniczyć w dowolnej liczbie Promocji Bankowych (przy czym nie może uczestniczyć kilkukrotnie w tej samej promocji). Liczba domowników jest znana. Zestaw i reguły Promocji Bankowych są znane. Wysokość budżetu domowego i jego podział na kategorie wydatków również jest z góry ustalony.

Celem zadania jest znalezienie takiego przyporządkowania Promocji Bankowych do rozkładu wydatków w budżecie domowym, aby zwrot z tych promocji był możliwie jak największy. Należy uwzględnić liczbę osób w gospodarstwie domowym i założyć, że wszystkie wydają pieniądze z tego samego budżetu.

edit: Autor(ka) chciała żeby rozwiązanie wysłać na maila, ale skoro pytanie jest zadane na forum to odpowiedź powinna się znaleźć na forum. Chyba że to zlecenie, w takim razie zły dział i brak kwoty. - msm

pw :)

A ja chyba nie bardzo rozumiem gdzie w tym zadaniu jest jakiś haczyk. Skoro wydatki są znane i ustalone oraz każda promocja daje nam bonus to rozwiązaniem optymalnym zawsze jest brać wszystkie promocje. Czy te promocje sie w jakiś sposób wykluczają?

Można wziąć każdą raz a rodzai a płaci się 5 razy :)
Drugi haczyk jest taki ze megii studiuje logistykę ;)

No to w takim razie to wygląda na dość trywialne zadanie jeśli użyjemy constraint programmingu. Zresztą @Afish niedługo napisze dobry solver dla ILP ;)

Zadanie moze byc bardziej skomplikowane jesli dodamy pare zalozen. Mozliwe ze takie sa, tylko nie sa sprecyzowane w zadaniu.

1. Kazda promocje mozemy wziac raz i czas jej trwania to 1 miesiac (zwrot po miesiacu z wydatkow z danego miesiaca).
2. Wydatki w budzecie sa znane z gory w wiekszym przedziale czasowym, np. 6 miesiecy.
3. Znane sa dostepne promocje rowniez w przedziale czasowym, np. 6 miesiecy.

Wtedy trzebaby wybrac taki rozklad promocji na osobe w konkretnych miesiacach aby zyski w ciagu 6 miesiecy byly jak najwieksze.

Obecne zadanie jest niestety banalne. Juz myslalem ze cos ciekawego bede mial do roboty w wolnym czasie. :)