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. 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, ziua 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, ajungem la o problemă matematică foarte interesantă, numită problema rucsacului. Şi ce e mai important – 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 metoda simplex). În realitate nu este aşa şi vă propun să ne adresăm motorului de căutare WolframAlpha. Notând variabilele x1, x2, x3, x4, problema de mai sus se introduce într-o singură linie sub următoarea formă:
maximize
1500 x1 + 5000 x2 + 5000 x3 + 4000 x4
subject to
x1 + 1.5 x2 + 2 x3 + x4 <= 45
and x1 + x2 + x3 + x4 <= 35
and x1 >= 2 x2
and x2 >= x3
and x3 >= 8 x4
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.
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:
Un cumparator trebuie sa se aprovizioneze cu producte ce ii vor ajunge pentru o saptamina. Suma maxima care o are in buzunar este de 170 lei. Trebuie sa cumpere carne, peste, lapte si zahar. Avind la dispozitie un cos pentru cumparaturi ce are 37 decimetri cubi si masa productelor nu trebuie sa depaseasca 46 kg. Unde greutatea pestelui este de 2 ori mai mare ca a carnii, greutatea laptelui este egala cu suma greutatii pestelui si a zaharului,iar greutatea zaharului este egala cu suma greutatii carnii si a pestelui.
Modelul matematic
z = 40 x1 + 20 x2 + 9 x3 + 15 x4 → max
2 x1 + 3 x2 + 4 x3 + 6 x4 ≤ 46
4 x1 + 6 x2 + 3 x3 + 2 x2 = 2 x1
x3 ≥ x2+x4
x4 ≥ x1+x2
x1≥0, x2≥0, x3≥0, x4≥0 (unde x1-cantitatea de carne, x2-cantitatea de peste, x3-cantitatea de lapte, x4-cantitatea de zahar)
Raspuns: x1=1, x2=2, x3=5, x4=3.
Violeta, Din pacate, si problema, dar si modelul au mai multe lacune…
Pentru alimentatia copiilor la gradinita este necesar de ales un vast asortiment de produse alimentare, bogate in proteine si vitamine, dar cit mai ieftine, pentru a se incadra in suma prevazuta la articolul de cheltuieli bugetare. Astfel, pina la moment in alimentatie se foloseau:
pine pe zi 8kg, suma in total cheltuita 72 lei, contin 250 kcal/kg;
lapte in zi 10 litri, suma 80 lei, 70 kcal/kg;
legume si fructe pe zi 20 kg, suma 175 lei, contin 50 kcal/kg;
carne in zi 5 kg, 350 lei, 270 kcal/kg.
Pentru alimentatia copiilor in 3 zile se vor cheltui 3305 lei. Masa produselor nu trebuie sa depaseasca pe zi 275 kg. Si in aceste 3 zile numarul de kcal nu trebuie sa depaseasca 2790 kcal.
Suma de pine si lapte ≥ legume si fructe,
iar lapte sa fie de 2 ori mai mult si +1 decit legume,
legumele ≥ 3 parti din carne.
Rezolvare:
Notam:
x1 – cantitatea de pine,
x2 – cantitatea de lapte,
x3 – cantiatea de legume si fructe,
x4 – cantitatea de carne.
z = 72 x1 + 80 x2 + 175 x3 + 350 x4 → max
250 x1 + 70 x2 + 50 x3 + 270 x4 ≤ 2790
8 x1 + 10 x2 + 20 x3 + 5 x4 = x3
2 x2 + 1 ≥ x3
x3 ≥ 3 x4
x1≥0, x2≥0, x3≥0, x4≥0
Raspuns: ( 5, 4, 9, 3)
Rodica,
Ai incercat sa formulezi o problema interesanta, dar cu parere de rau are mai multe lacune. In primul rand nu-i clar ce vreai sa faci… Ce inseamna 72 x1 + 80 x2 + 175 x3 + 350 x4 → max? La fel nu e clar ce inseamna 8 x1 + 10 x2 + 20 x3 + 5 x4 = x3? Etc. Trebuie sa tii cont ca fiecare expresie trebuie sa aiba o anumita semnificatie si sa se masoare in anumite unitati: lei, kg, kcal …
Spre exemplu, expresia 8 x1 + 10 x2 + 20 x3 + 5 x4 se masoara in kg*kg
Pentru o creştere şi dezvoltare sănătoasă a unui copil, în alimentaţia sa trebuie să folosească produse precum lactate, peste, carne, fructe–legume, cereale. O mama merge la cumpărături o dată în 3 zile. Bugetul familiei nu îi permite ca să cheltuie mai mult de 350 lei pentru 3 zile. Medicii recomandă în alimentaţia copilului să se folosească alimentele în anumite cantitaţi. Consumul de legume si fructe să fie de 3 ori mai mare decît cel de cereale dar să nu intreaca suma cantitatilor de cereale şi a celei de carne-peste, 3 parţi din carne şi peşte nu trebue să depaşească 2 părţi din fructe şi legume, iar cantitatea de lactate sa fie mai mare decît jumate din suma cantitatiide peşte-carne şi a acelei de fructe şi legume. Valoarea nutritivă pentru un copil pe perioada data de 3 zile nu trebuie sa depăşească 2660 kcal. În tabelul de mai jos avem data valoarea nutritivă a fiecărui produs şi preţul lui in medie. Ce cantităţi de fiecare produs va cumpăra femeia in conditiile date de mai sus.
Lactate| Peşte–carne| Fructe–legume | Cereale
Kcal |60 | 180 | 200 | 220
Lei/kg |10 | 30 | 25 | 15
Medelul matematic :
Z = 60 x1 + 180 x2 + 200 x3 + 220 x4 → max
10 x1 + 30 x2 + 25 x3 + 15 x4 ≤ 350
3 x2 ≥ 2 x3
x3 ≥ x2 + x4
x3 ≥ 3 x4
x1 ≥ 1/2 (x2 + x3)
xi≥0, i=1,2,3,4.
Raspuns: 2660 pentru (x1, x2, x3, x4) = (5, 4, 6, 2)
Modelul matematic:
z=13 x1+17 x2+25 x3 → min
in restrictiile 12 x1 + 8 x2 + 20 x3 ≥ 37
12 x1 + 4 x2 + 8 x3 ≥ 20
10 x1 + 3 x2 + 19 x3 ≥ 90
x1≥0, x2≥0, x3≥0
Raspuns: 2600 pentru (x1, x2, x3) = (200:7, 0, 0)
Nicoleta,
Dacă interpretăm rezultatul obţinut de tine, atunci persoana trebuie sa concume zilnic aproape 30 kg de terci (trei găleţi de terci). Să ştii că e un rezultat foarte amuzant
@Doina
Se accepta!
La o sectie in cadrul unei uzine metalurgice trebuie sa se elaboreze un program optim pentru executarea a doua tipuri de produse P1 si P2. Intr-o anumita perioada sectia are disponibile trei utilaje:
cuptorul de recoacere,
agregatul de decapare
si un laminor finisor.
Fiecare din aceste utilaje are un anumit fond de timp disponibil pentru cele doua piese. Consumurile de timp pentru P1 (respectiv P2) sunt:
in cuptorul de recoacere – 5ore/tona (3ore/tona);
in agregatul de decapare – 0,5ore/tona (2ore/tona);
in laminorul finisor – 3ore/tona (5ore/tona),
iar fondul de timp disponibil in fiecare din aceste utilaje este:
2100 ore, 550 ore si 1500 ore, respectiv.
Veniturile unitare au fost evaluate la 15 si 20 unitati monetare pentru o tona de produs P1, respectiv P2. Programul se considera optim daca asigura un venit total maxim in conditiile date.
Modelul matematic:
Notăm: x1, x2 – cantitatile de produse P1, respectiv P2, care urmeaza sa fie executate conform indicatorilor cantitativi.
z=15 x1 + 20 x2 → max,
5 x1 + 3 x2 ≤ 2100,
0.5 x1 + 2 x2 ≤ 550,
3 x1 + 5 x2 ≤1500,
x1≥0, x2≥0.
Venitul total maxim este de 7125 cind (x1, x2) = (375, 75).
Modelul si solutia – corecte!
Pentru alimentatia copiilor la gradinita este necesar de ales un vast asortiment de produse alimentare, bogate in proteine si vitamine, dar cit mai ieftine, pentru a se incadra in suma prevazuta la articolul de cheltuieli bugetare. Astfel, pina la moment in alimentatie se foloseau:produse: pine| lapte| legume si fructe|carne|
cantitati: 250kcal/kg|70kcal/kg|50kcal/kg| 270kcal/kg|
72 lei |80lei |175lei | 380lei |
8kg/lei |10kg/lei |20kg/lei |5kg/lei |
Pentru alimentatia copiilor in 3 zile BUGETUL STATULUI nu permite de cheltui mai mult 3305 lei. Masa produselor nu trebuie sa depaseasca pe zi 275 kg. Si in aceste 3 zile numarul de kcal nu trebuie sa depaseasca 2790 kcal.
Suma de pine si lapte ≥ legume si fructe,
iar lapte sa fie de 2 ori mai mult si +1 decit legume,
legumele ≥ 3 parti din carne.
Rezolvare:
z = 72 x1 + 80 x2 + 175 x3 + 350 x4 → max
250 x1 + 70 x2 + 50 x3 + 270 x4 ≤ 2790
8 x1 + 10 x2 + 20 x3 + 5 x4 = x3
2 x2 + 1 ≥ x3
x3 ≥ 3 x4
x1≥0, x2≥0, x3≥0, x4≥0
Raspuns: 3305 pentru(x1,x2,x3,x4)=( 5, 4, 9, 3)
Rodica,
Cu parere de rau lacunele persista! Nu e clara semnificatia functiei obiectiv… Ce inseamna kg/lei? Ce inseamna a doua restrictie (ecuatia)?
Fabrica de mobila
Pentru producerea unei mese sunt necesare: 1.5 m de pin, 0.6 m de stejar, 3 ore de lucru.
Pentru producerea unui scaun sunt necesare: 0.3 m de pin, 1 m de stejar, 2 ore de lucru.
Pentru o tabla: 2.5 m de pin, 1.2 m de stejar, 5 ore de lucru.
Capacitatea de resurse saptamanala este: 4500 m de pin, 3000 metri de stejar, 20 de angajati a cate 40 de ore fiecare.
Daca se stie ca profitul de la comercializarea unei mese este de 12$, de la un scaun de 5$, iar de la o tabla de 15$ si cererea saptamanala este de: 40 mese, 130 scaune, 30 table, sa se gaseasca planul de producere saptamanal astfel ca profitul sa fie maxim.
Modelul matematic:
Vom nota cu xi cantitatea bunurilor produse de tipul i.
{
1.5 x1 + 0.3 x2 + 2.5 x3 ≤ 4500,
0.6 x1 + x2 + 1.2 x3 ≤ 3000,
3 x1 + 2 x2 + 5 x3 ≤ 800,
x1 ≥ 40,
x2 ≥ 130,
x3 ≥ 30,
x1, x2, x3 apartin Z
Funcția obiectiv devine:
12 x1 + 5 x2 + 15 x3 → max.
Rezolvare:
Maximize[{12 x1 + 5 x2 + 15 x3, 1.5 x1 + 0.3 x2 + 2.5 x3 <= 4500,
0.6 x1 + x2 + 1.2 x3 <= 3000, 3 x1 + 2 x2 + 5 x3 = 40,
x2 >= 130, x3 >= 30, (x1 | x2 | x3) \[Element] Integers}, {x1, x2, x3}]
{2660., {x1 -> 130, x2 -> 130, x3 -> 30}}
Vor fi construite 130 de mese, 130 de scaune, 30 de table care vor aduce un profit saptamanal de 2660$.
Mariana,
Am efectuat corectiile necesare in model. Incearca sa mai rezolvi inca o data problema la computer!
Problema
O agenţie de turism îşi propune promovarea Republicii Moldova, prin vizitarea principalelor obiective turistice de care dispune aceasta. Astfel, ea prezintă potenţialilor clienţi ofertă turistică, care presupune efectuarea excursiilor pentru un grup nu mai mare de 40 de persoane, şi le propune la alegere 5 itinerarii turistice. Pentru fiecare itinerar prezentat, în funcţie de numărul de obiective propuse spre vizitare, este preconizat un anumit număr de zile, care nu trebuie sa depăşească cifra de 7 zile.
Numarul itinerariului
1 2 3 4 5
Numarul de persoane 25 15 35 5 20
Numar de zile 3 5 1 6 2
Obiective turistice 55 75 15 95 40
Trebuie sa construim un model matematic pentru determinarea unui complet de itinerarii in care sunt incluse cele mai multe obiective turistice.
Modelul
max f(x)= 55 x1 + 75 x2 + 15 x3 + 95 x4 + 40 x5
25 x1 + 15 x2 +35 x3 + 5 x4 + 20 x5 ≤ 40
3 x1 + 5 x2 + x3 + 6 x4 + 2 x5 ≤ 7
xj >= 0
CS,
Rezultatul pe care il obtii nu este de tip intreg deoarece nu ai inclus o asa restrictie asupra varibilelor. Daca vei includ cererea ca varibilele sunt de tip intreg, raspunsul va fi unul corect.