Exploratorul polar şi problema rucsacului

Azi e o zi deosebită, în special pentru numerologi. E 11.11.11. De dimineaţă au căzut primii fulgi…

De curând, pe polimedia.us/fain/ am găsit câteva comentarii la două dintre articolele mele, comentarii care m-au amuzat mult. Se referă la „Ion Creangă şi Teoria Jocurilor”, precum şi la „Credinţă şi Revelaţii”. Un comentator anonim a găsit în primul articol elemente şoviniste :), iar în al doilea – motive de mare veselie… 🙂 Unde dai şi unde crapă… 😉

Se dovedeşte că ziua e specială din perspectiva matematică: magia cifrelor şi atenţia acordată unor articole cu specific de matematică aplicată. Împreună cu primii fulgi mi-a sugerat ideea articolului curent.

În 1995, canadianul Richard Weber şi rusul Misha Malakhov, au realizat o performanţă greu de depăşit: o expediţie la Polul Nord cu reîntoarcere fără suport de orice natură. Expediţia a luat start pe 14 februarie, a culminat prima dată pe 12 mai, când s-a ajuns la Polul Nord, apoi a finalizat cu recordul unical la revenirea pe Pământul Mare pe 15 iunie. Recordul celei mai lungi expediţii polare fără suport a însumat un total de 108 zile.

Cum au reuşit ei să se alimenteze în acele 108 zile, fără suport? Evident, că au avut la îndemână nişte alimente cu o mare valoare energetică, deoarece atât volumul, cât şi masa alimentelor au fost tare restricţionate. Inevitabil se ajungem la o problemă matematică foarte interesantă, numită problema rucsacului. Şi ce e mai important că Internetul ne oferă posibilităţi de a o rezolva online, fără cunoştinţe matematice speciale 😉

Prezint o formulare a problemei din problemarul „Ашманов С.А., Тимохов А.В., Теория оптимизации в задачах и упражнениях, М., Наука, 1991„, chiar dacă datele problemei, dar şi formularea ei, pot fi arbitrare.

Un explorator polar îşi încarcă rucsacul şi trebuie să decidă ce alimente să ia cu sine şi în ce cantităţi. Are la dispoziţie: carne, făină, lapte praf şi zahăr. Pentru alimente, în rucsac e rezervat un volum de 45 dm3 la o masă totală nu mai mare de 35 de kg. Medicul expediţiei recomandă ca masa cărnii s-o depăşească pe cea a făinii cel puţin de două ori, făină să fie nu mai puţină decât lapte, iar masa laptelui praf să depăşească cel puţin de 8 ori masa zahărului. Cu ce producte şi în ce cantităţi trebuie încărcat rucsacul ca valoarea energetică totală să fie maximă?
Tabelul ce urmează prezintă valorile energetice ale alimentelor.

Caracteristici Alimente
Carne Făină Lapte praf Zahăr
Volum (dm3/kg) 1 1.5 2 1
Cantitate calorică
(kcal/kg)
1500 5000 5000 4000

Să construim modelul matematic al problemei. În primul rând să remarcăm că necunoscute sunt masele alimentelor:

x1 – masa de carne,
x2 – masa de făină,
x3 – masa de lapte praf,
x4 – masa de zahăr.

În aceste notaţii cantitatea calorică totală este egala cu:

1500 x1 + 5000 x2 + 5000 x3 + 4000 x4,

volumul alimentelor este:

x1 + 1.5 x2 + 2 x3 + x4,

iar masa lor:

x1 + x2 + x3 + x4.

Conform condiţiilor problemei, volumul total trebuie să fie nu mai mare decât 45 dm3, iar masa nu trebuie să depăşească 35 de kilograme. În plus, medicul recomandă ca masa cărnii să fie cel puţin de două ori mai mare decât cea a făinii, adică:

x1 ≥ 2 x2,

masa făinii să fie nu mai mică decât cea a laptelui praf:

x2 ≥ x3,

iar masa laptelui praf să depăşească cel puţin de 8 ori masa zahărului:

x3 ≥ 8 x4.

Ca rezultat se obţine următoarea problemă de programare liniară:

1500 x1 + 5000 x2 + 5000 x3 + 4000 x4 → max,
_____x1 + __1.5 x2 + ____2 x3 + ____x4 ≤ 45,
_____x1 + _____x2 + _____x3 + ____x4 ≤ 35,
_____-x1 + ___2 x2__________________ ≤ 0,
_____________-x2 + _____x3 _________≤ 0,
______________________-x3 + ___8 x4 ≤ 0,
_____x1 ≥ 0,___x2 ≥ 0,___ x3 ≥ 0,___ x4 ≥ 0.

Problema matematică obţinută e şi ea numită problemă a rucsacului, denumirea fiind una generică pentru o clasă largă de probleme aplicate de acest gen. Problema discretă a rucsacului este foarte cunoscută în teoria complexităţii de calcul, fiind NP-completă, adică problemă pentru care nu există (cel puţin la moment) algoritmi de soluţionare cu o complexitate de calcul polinomială.

Remarca de mai sus ar putea fi interpretată şi ca o eschivare de la soluţionarea finală a problemei (are 4 variabile, cere cunoaşterea unor metode speciale de rezolvare cum este metode simplex). În realitate nu este aşa şi vă propun să ne adresăm motorului de căutare WolframAlpha. Problema de mai sus se introduce notând variabilele x1, x2, x3, x4, într-o singură linie sub următoarea formă:

maximize
1500×1+ 5000×2 + 5000×3 + 4000×4

subject to

x1+1.5×2 + 2×3 +x4<=45
and x1+x2+x3+x4<=35
and x1>=2×2
and x2>=x3
and x3>=8×4
and x1>=0
and x2 >=0
and x3>=0
and x4 >=0

De fapt, dacă se apasă aici, se accesează motorul WolframAlpha, în câmpul de căutare al căruia este deja introdusă problema de mai sus.

Rămâne doar să se constate că soluţia problemei este:

x1 =16, x2 =8, x3 =8, x4=1,

adică rucsacul se încarcă cu: 16 kg de carne, câte 8 kg de făină şi lapte praf, şi un kilogram de zahăr, la o valoare energetică totală de 108 000 kcal. Se mai observă că masa totală este doar de 33 de kg, adică e cu 2 kilograme mai mică decât cea permisă.

În concluzia finală vreau să remarc, în primul rând, că problema rucsacului este o problemă cu aplicaţii foarte largi în viaţa de toate zilele. În al doilea rând, atrag atenţia că partea ce mai complicată la rezolvarea unei probleme practice ţine de identificarea problemei şi de construirea unui model adecvat. Restul devine doar rutină, deoarece motorul WolframAlpha rezolvă problema elementar.

Să aveţi azi o zi cât mai bună, în special la 1111 11.11.11 🙂

P.S. Tema aplicarii matematicii se abordeaza si in urmatoarele articole de pe blog:

  1. Iniţiere în programarea matematică
  2. Modele economico-matematice celebre
  3. Metoda grafică în programarea matematică
  4. Mulţimi poliedrale, vârfuri şi soluţii admisibile de bază
Anunțuri

4 comentarii la “Exploratorul polar şi problema rucsacului

  1. E important că s-a înţeles că matematica poate fi aplicată în orice domeniu 😉

    Pe de altă parte, nici n-ar fi bine dacă toţi am fi matematicieni… În viaţă sunt atâtea alte activităţi interesante şi importante, că nu ne ajung multe vieţi ca să ne putem dedica tuturor talentelor care le posedăm. Fiecare are multe talente ascunse, care aşa şi rămân nedescoperite…

  2. Da…matematica ne ajuta in structurarea memoriei, indiferent cat de mult am studiat la scoala si cat de mult aplicam in viata mai departe. Desi sunt artist, matematica ma ajuta foarte mult. In primul rand m-a invatat sa fiu coerenta , sa incerc sa trec de suprafata lucrurilor, sa analizez , sa sintetizez informatiile si sentimentele (care uneori vin in avalansa)!
    Multumesc!

  3. Comentariul tau il primesc, Daliana, ca pe un compliment personal, deoarece apreciez mult creatiile tale! Te felicit cu reusita la recentul concurs! Inspiratia si spiritul de creativitate sa te insoteasca in continuare, iar matematica sa fie un sprijin de nadejede in activitatea ta! La mai mult si la mai mare!

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s