4. Teoria general de la programació lineal

Per regla general, un problema de programació lineal amb dues variables, consisteix a optimitzar (maximitzar o minimitzar) una funció lineal z de la forma z = mx + ny que anomenem funció objectiu, i que està subjecta a un sistema d'inequacions o restriccions:

a1x + b1y » c1
a2x + b2y » c2
.................
anx + bny » cn

on el símbol » pot ser >, <, ≤, o, ≥.
    El subconjunt de punts del pla, les coordenades dels quals són solució del sistema d'inequacions, s'anomena conjunt de solucions factibles o regió factible. Per últim, s'anomena solució òptima aquella solució factible, on la funció objectiu pren el seu valor màxim o mínim.

Teorema. En tot problema de programació lineal, la funció objectiu pren els seus valors extrems (si existeixen) en els vèrtexs de la regió factible.
Índex.

5. Mètode analític de resolució
    El mètode per resoldre aquest tipus de problemes es redueix a:
  1. Dibuixar la regió factible.
  2. Calcular els seus vèrtexs.
  3. Substituir les coordenades de cada vèrtex en la funció objectiu.
  4. Observar en quin vèrtex pren aquesta funció els seus valors extrems.
    Finalment, la solució del problema, serà l'ordenada i l'abscissa del vèrtex on la funció objectiu prengui el valor òptim.

    Cal anar amb compte en els següents dos casos:
  • Si la regió factible no està acotada, pot ser que la funció objectiu no prengui mai el seu valor òptim, amb la qual cosa el problema no tindria solució.
  • De forma semblant, si la funció objectiu pren el valor òptim en dos o més vèrtexs consecutius, també valdrà el mateix en els punts continguts en les arestes que uneixen aquests vèrtex. Així, doncs, ens trobaríem en el cas d'un problema amb infinites solucions (tot segment està constituït per infinits punts).
  Per al nostre problema de les nines, si observem el gràfic on es mostrava la regió factible i calculem els seus vèrtexs (només cal trobar el punt de tall de dues rectes, en cada cas). Obtenim el resultat següent:
El punt A és el punt de tall de les rectes y = 40 i x = 0. Ens dóna: A(0, 40)
El punt B és el punt de tall de les rectes y = 40 i y = 50 - x/2. Ens dóna: B(20, 40)
El punt C és el punt de tall de les rectes y = 50 - x/2 i y = 100 - 1,25x. Ens dóna: C(66,6; 16,6)
El punt D és el punt de tall de les rectes y = 100-1,25x i y = 0. Ens dóna: D(80,0)
El punt E és el punt de tall de les rectes y = 0 i x = 0. Ens dóna: E(0, 0)

Si se substitueixen els valors de les coordenades dels vèrtexs en la funció objectiu obtenim:
Per al vèrtex A: z = 18 × 0 + 24 × 40 = 960 euros.
Per al vèrtex B: z = 18 × 20 + 24 × 40 =
1.320 euros.
Per al vèrtex C: z = 18 × 66,6 + 24 × 16,6 = 1.600 euros.
Per al vèrtex D: z = 18 × 80 + 24 × 0 = 1.440 euros.
Per al vèrtex E: z = 18 × 0 + 24 × 0 = 0 euros.

    Per tant, és clar que el benefici màxim es troba en el vèrtex C. És a dir, a l'empresa li interessa produir 66,6 Baby Moquets Dia, i 16,6 Baby Moquets Nit.

    Això seria la solució matemàtica del problema, però és evident que no es poden produir parts fraccionàries del producte (66,6; 16,6).
    Si estudiem la funció al voltant d'aquest punt de la regió factible, però fixant-nos sols en punts de coordenades enteres, trobem que el valor màxim de la funció objectiu es pren en el punt (66, 16), punt on el benefici és de 1.572
euros.


Índex

6. Mètode gràfic de resolució
    En la majoria dels problemes de programació lineal que veuràs aquest curs, la funció objectiu
z = mx + ny
(o bé y = -mx/n + z/n en forma explícita) la trobaràs amb coeficient n positiu. Per aquest motiu, com més gran és el valor de la funció objectiu z, major és l'ordenada en l'origen de l'equació
y = -mx/n + z/n
, i a l'inrevés.


    Amb això tenim que, per trobar en quin punt de la regió factible pren la funció el seu valor òptim, només cal anar dibuixant rectes paral·leles a la recta mx + ny = 0 que passant per la regió factible tinguin la major ordenada possible en l'origen (si busquem un màxim de la funció).
    Si es tractés de trobar el mínim de la funció objectiu, llavors traçaríem les rectes amb menor ordenada possible en l'origen .
    Recorda que en aquest tipus de problemes, els valors extrems de la funció els trobaràs en els vèrtexs de la regió factible. Així, sols cal traçar les paral·leles que passin per aquests punts.
    Un cop dibuixada la paral·lela que dóna el valor òptim de la funció objectiu, et trobaràs en un del casos següents:
  • Que aquesta recta passi per un sol punt de la regió factible. En aquest cas, la solució serà única, i prendrà el valor de les coordenades d'aquest punt.

  • Que la recta se superposi a un dels costats de la regió factible. En aquest cas hi haurà infinites solucions, una per a cada un dels punts que integrin el costat.

  • Si la regió factible no és acotada, pot ser que no es pugui trobar cap paral·lela que passi per la regió i tingui una ordenada en l'origen major que la resta (en aquest cas s'ha de buscar un màxim; menor si busquem un mínim). En aquest cas, la funció objectiu no té l'extrem buscat.


En el nostre problema s'ha de procedir de la següent manera:
  1. Es dibuixa la regió factible:

  1. Es dibuixa la recta corresponent a z = 0.

  1. Es traça la paral·lela a aquesta recta que en passar per la regió factible tingui una ordenada en l'origen màxima.



Com bé pots observar, per tenir la major ordenada possible en l'origen, aquesta recta ha de passar pel punt C(66,6; 16,6). Així, tal com passava amb el mètode analític, és en aquest punt C on la funció de beneficis pren el seu valor màxim. És a dir, a l'empresa li interessa produir 66,6 Baby Moquets Dia, i 16,6 Baby Moquets Nit.

També cal fer l'observació que això seria la solució matemàtica del problema però que és evident que no es poden produir parts fraccionàries del producte. (66,6; 16,6).
Estudiant la funció al voltant d'aquest punt de la regió factible, però fixant-nos sols en punts de coordenades enteres, trobem que el valor màxim de la funció objectiu es pren en el punt (66, 16). En aquest punt, el benefici és de 1.572 euros.

Índex

 

7. Resolució de problemes amb l'eina.
Vegem-ho amb el nostre problema de les nines:

Introduïm primerament les dades que ja coneixem, i polsem el botó representar en l'eina.


Adona't que l'applet també dóna la llista de vèrtexs de la regió factible.

Fins i tot si cliquem amb el ratolí en un dels vèrtex de la llista, aquest es marcarà en el dibuix, i a sota de la llista de vèrtexs, podrem veure'n lescoordenades i el valor de la funció objectiu en aquest punt.

Així doncs, per trobar el vèrtex que fa màxima la funció objectiu, sols cal anar fent clic en cada un dels vèrtexs de la llista i observar el valor de la funció objectiu en el quadre de sota. (Això es el mateix que es fa en el mètode analític: anar comprovant el valor de la funció en cada vèrtex, fins que trobem l'òptim.)

Si ho fas d'aquesta manera trobaràs que el quart vèrtex de la llista
(66,6, 16,6) és el que dóna un valor més gran per a la funció objectiu (1.600 Euros).

D'altra banda, si situes el ratolí a dins del dibuix, veuràs que en el quadre Valor funció objectiu se'n mostra la posició, i el valor de la funció en aquest punt. (Si és interior a la regió factible)

Amb aquesta utilitat, podem anar més enllà del problema i estudiar una mica més a fons el comportament de la funció.


Per exemple, podem veure que el valor de la funció augmenta en desplaçar-nos del vèrtex E al D per l'aresta, i que encara aumenta més si ens desplacem del D al C. En canvi, si seguim de C a B per l'aresta, veiem que comença a disminuir el valor de la funció objectiu. Es a dir que efectivament, el màxim és en el punt C.


Índex


8. Estudis posteriors.

Com ja deus haver observat, en aquesta unitat didàctica ens hem limitat a estudiar problemes que sols depenen de dues variables. A més a més, tant les funcions objecte d'estudi com les restriccions imposades són lineals.
Tot i que això ja abraça un gran nombre de problemes, pots notar que no totes les qüestions d'optimització s'ajusten a aquestes exigències.

Ja en deus conèixer d'altres amb funcions no lineals (quadràtiques, cúbiques, exponencials, logarítmiques, etc.); això sí, sense restriccions, i depenent sols d'una variable. Les tècniques d'optimització que utilitzes en aquestos casos estan basades en el càlcul diferencial. De fet, més en davant, a la universitat, potser et trobaràs amb l'ampliació d'aquestes tècniques d'optimització (també conegudes com programes diferenciables). Es tracta sempre de funcions diferenciables no necessàriament lineals, sotmeses o no a restriccions també diferenciables i no necessàriament lineals.

Per al cas de problemes lineals amb més de dues variables, el mètode de resolució que dóna continuïtat als estudiats en aquesta unitat didàctica és el del Simplex.

Però tot això ja és matèria d'estudis posteriors...

Índex