Programació lineal entera

La programació lineal entera serveix per resoldre els problemes de programació lineal en què les variables han de prendre valor enters.

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.

Exemple

Representació gràfica del problema.

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.

Fonts

• Programación lineal entera PDF (castellà)
• Programación lineal. Programación entera (castellà)