La programació lineal entera serveix per resoldre els problemes de programació lineal en què les variables han de prendre valor enters.[1]
Quan representem un problema de programació lineal ens podem trobar que només tenen sentit aquelles solucions de la regió factible, que les seves variables són nombres enters. Llavors estem davant d'un problema de programació lineal entera.
Un problema de programació lineal entera es formula de la mateixa manera que un problema de programació lineal convencional, però amb la diferència que el resultat d'aquest es trobarà dins d'una regió factible, en aquesta trobarem diversos punts, però només són vàlids els que tenen unes coordenades enteres. Aquests problemes són a vegades fàcils de resoldre i a vegades impossibles, perquè no trobem cap punt dins de la regió factible que tingui coordenades enteres.
Per resoldre aquests problemes s'utilitza el mètode gràfic. Aquest consisteix a representar la regió factible, dibuixar la funció objectiu i buscar en quin punt assoleix el màxim o el mínim.
Una vegada buscat el màxim o el mínim, si aquests punts no tenen coordenades enteres s'ha de buscar quins punts amb coordenades enteres són pròxims aquests i en quins d'aquests s'obté el màxim o el mínim.
Un fuster vol fabricar amb 80 kg de fusta i 50 kg de ferro dos tipus de taula, la taula A i la B. Per la taula B necessita 20 kg de fusta i 10 kg de ferro. Per la taula A necessita 10 kg de fusta i 10 kg de ferro. Les taules A les ven a 30 euros i les B a 40 euros. El fuster només vol fabricar com a màxim 5 taules del tipus A. Quantes taules ha de fabricar de cada tipus per obtenir el màxim benefici?
x = nombre de taules A que ha de fabricar.
y = nombre de taules B que ha de fabricar.
Funció objectiu: 30x+ 40y (recta de color lila)
Restriccions:
10x + 20y ≤ 80 (recta de color blau)
10x + 10y ≤ 50 (recta de color taronja)
x ≤ 5 (recta de color verd)
x,y naturals
On obté el major benefici és en el punt B (5, 1'5) però aquest punt no serveix per resoldre el problema perquè no és lògic que faci 5 taules de tipus A i 1'5 de tipus B. Per tant, els punts que estan a prop d'aquest i que tenen coordenades enteres són els punts D(4, 2) i E (5,1). Calculem el benefici al punt D i ens dona un benefici de 200 euros i al punt E el benefici és de 190 euros. Per tant, el màxim benefici s'obté al punt D.
Per tant, la solució aquest problema és que el fuster ha de fabricar 4 taules del tipus A i 2 del tipus B.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
