LL5_Programació lineal

1. Introducció. Objectius.

L'objectiu d'aquest lliurament és resoldre problemes de programació lineal. 

És gairebé segur que en un examen d'aquest bloc surt un problema d'aquest tipus i és molt probable que surti en un examen de les proves PAU. Diem això perquè veieu la importància d'aquests problemes en el bloc.

Per arribar a resoldre aquests problemes de programació lineal bàsicament necessitem saber fer: 

• Resolució d'inequacions i sistemes d'inequacions lineals amb dues incògnites. 
• Representació d'una situació mitjançant un sistema d'inequacions.
• La funció objectiu. Màxims i mínims en una regió. 
• Resolució de problemes de programació lineal bidimensional. Interpretació de la solució segons el context.    

2. Inequacions lineals amb una incògnita

Definició.

Una inequació és una desigualtat entre dues expressions algebraiques, anomenades membre de la inequació.

Els valors de les incògnites que fan  que sigui certa la desigualtat són les solucions de la inequació.

Diem que dues inequacions són equivalents si tenen el mateix conjunt solució.

Una inequació lineal amb una incògnita és una equació equivalent a

Propietats.

1. Si sumem o restem una mateixa expressió polinòmica al dos membre de la inequació, obtenim  una inequació equivalent.

2. Si multipliquem o dividim per un nombre positiu els dos membres d'una inequació, obtenim una inequació equivalent.

   Exemple:         

3. Si multipliquem o dividim per un nombre negatiu els dos membres d'una inequació, per obtenir una inequació equivalent hem d'invertit el sentit de la desigualtat.

   Exemple:

Solucions.

El conjunt de solucions el podem expressar en forma d'interval o fent la representació gràfica.

Exemple:

Exemples d'inequacions lineals amb una incògnita. 

Exemple 1

             expressat en forma d'interval:  

Exemple 2

              expressat en forma d'interval:   

Exemple 3

              expressat en forma d'interval:   

3. Inequacions lineals amb dues incògnites

Definició

És una expressió  equivalent a

amb qualsevol de les desigualtats  <,  ≤,  >,  ≥

Solucions

La solució és un semiplà. Hem de representar gràficament aquest semiplà.

Exemple

Dibuixem la recta 

     Per dibuixar-la trobem dos punts qualssevol de la recta: 

 Aquesta recta divideix al pla en dos semiplans.   La recta és la frontera d'aquests semiplans. 

     Els punts de la recta verifiquen y=-2x+3

     Els punts d'un semiplà verifiquen y<-2x+3 i  els de l'altre semiplà verifiquen y>-2x+3

     Per saber quin semiplà correspon a cada inequació agafem un punt de cada semiplà i veiem quina desigualtat compleix.

     Veiem, per exemple, que el punt (-3,1) compleix y<-2x+3. Tots els punts que es troben en el mateix semiplà que el (-3,1)

     compliran y<-2x+3

     Tots els punts de l'altre semiplà compliran la desigualtat y>-2x+3. Per exemple, ho podem veure amb el punt

     És molt pràctic mirant-ho amb el punt (0,0):

    Substituïm el (0,0) en la inequació i mirem si la compleix o no :

    En aquest cas veiem que el (0,0) compleix  2·0+0 < 3, per tant compleix la inequació.

    Per tant, el semiplà solució és el semiplà que conté al punt (0,0).  En el dibuix ho hem indicat en groc.  

Quan la desigualtat sigui estricta vol dir que la solució no inclou als punts de la recta i, llavors, la dibuixarem amb un traç continu.

Veiem quin semiplà és la solució (indicat en groc) de les inequacions, variant la desigualtat.

Casos particulars.

Si estem treballant amb dues variables però tenim desigualtats amb una única variable, veiem gràficament el semiplà solució: 

Exemples:

    x < 2                                 x 2                                         x > 2                           x 2

                y ≤ 3                       y<3                                 y ≥ 3                            y>3

4. Sistemes d'inequacions

Un sistema d'inequacions lineal amb dues variables és de la forma

(amb qualsevol de les desigualtats 

Ho resolem gràficament.

Dibuixem, en uns mateixos eixos de coordenades, el semiplà solució de cada inequació

La solució del sistema serà la regió intersecció dels dos plans.

Observeu que pot ser que un sistema d'inequacions no tingui solució. Això passarà quan els dos semiplans no tinguin cap punt en comú. 

4.1. Exemple 1

Hem de dibuixar les dues rectes  2x+3y=1 i  x-y=3  en uns mateixos eixos de coordenades.
Per dibuixar-les trobem dos punts de cada recta. 

Recta   

Recta   

Ratllem en verd la solució de la inequació 

   Podem veure que el punt (0,0)  SÏ compleix la inequació,  ja que 
   Per tant el semiplà solució és en el qual es troba el (0,0)

Ratllem en blau la solució de la inequació 

   Podem veure que el punt (0,0)  NO compleix la inequació,  ja que 
   Per tant el semiplà solució és en el qual no es troba el (0,0)

      La regió solució és la regió ratllada
      tant de blau com de vermell.

      veiem que en aquest cas és una regió oberta.

4.2. Exemple 2

En aquest exemple farem el problema a l'inrevés. És a dir, ens donen la regió solució (regió factible) i hem de trobar el sistema d'inequacions del qual és solució. 

-----------------------------------------------------------------------------

La regió ombrejada en verd representa la regió solució d'un sistema d'inequacions.  

Trobeu: 

a) Les equacions de les rectes que delimiten la regió.

     Per trobar l'equació de cada recta, en el dibuix prenem dos punts que clarament veiem en el gràfic que són de la recta.   

     Recordem com es troba l'equació de la recta que passa per dos punts. Ho vam fer en el lliurament 3: Equació de la recta que passa per dos punts  

     Un punt que ens serveix per a les dues rectes és el punt (6,2) què és el punt intersecció. 

     -  Recta que passa pels punts (6,2) i (8,0)     (també podrien agafar el (7,1), el (5,3),.....)

     - Recta que passa pels punts (6,2) i (0,5)

b) El sistema d'inequacions corresponent a la regió ombrejada. 

    Cada recta divideix al pla en dos semiplans. 

    Per a la recta    tenim els dos semiplans d'equacions: 

   I per a la recta  tenim: 

    Una forma pràctica és agafar un punt que clarament estigui en la regió solució. En aquest cas, per exemple, el (0,0). 

    Substituïm en l'equació de la recta i veiem quines desigualtats es compleixen. Veiem que:

                  i        

   Per tant les inequacions que defineixen la regió és:

4.3. Problema

Passos a seguir per resoldre un problema mitjançant un sistema d'inequacions:

- Llegir atentament l'enunciat.
- Escollir les incògnites.
- Traduir cada condició (o restricció) del problema en una inequació, obtenint un sistema d'inequacions.
-  Resoldre el sistema d'inequacions indicant la regió solució.
- Obtenir les solucions i comprovar-les.

Exemple

Disposem d'un màxim de 55€ i hem de comprar al menys 5 bolígrafs i 5 carpetes. Cada bolígraf costa 3€ i cada carpeta 5€. 
Troba totes les opcions de compra.   

Solució

bolígràfs:  x
carpetes:  y

Hem de dibuixar, en uns mateixos eixos de coordenades,  les tres rectes  3x+5y=55,  x=5 (recta vertical) i y=5 (recta horitzontal) i
veure amb quin semiplà ens quedem.

La intersecció d'aquest semiplans és la regió solució.  En aquest cas és un triangle. 

els vèrtexs del qual són els punts d'intersecció de les rectes
dos a dos.

Les solucions de x, y seran els punts (x,y) que es troben dins del triangle solució.

En general, per indicar la solució del sistema serà suficient amb marcar la regió solució en el dibuix.  

--------------------------------------------------------------------------------------------------------------------------------------------------------------

En aquest cas hem d'afinar més si tenim en compte que, com que parlem de nombre de bolígrafs (x) i nombre de capetes (y),
les solucions han de ser nombres naturals:

Trobem els vèrtex de la regió solució. Són els punts d'intersecció de les rectes
dos a dos.

Els punts amb coordenades enteres que estan en la regió solució són:

(5,5), (6,5), (7,5), (8,5), (9,5), (10,5)    5 carpetes i entre 5 i 10 bolígrafs
(5,6), (6,6), (7,6)                               6 carpetes i entre 5 i 7 bolígrafs
(5,7), (6,7)                                       7 carpetes i 5 o 6 bolígrafs
(5,8)                                                8 carpetes i 5 bolígrafs.   

5. Problemes programació lineal

Resoldre un problema de programació lineal consisteix a optimitzar (maximitzar o minimitzar) una funció lineal, anomenada funció objectiu, subjecta a unes restriccions expressades mitjançant un sistema d'inequacions lineal. 

Passos a seguir:
- Llegir atentament l'enunciat i escollir les incògnites. 
- Resoldre el sistema d'inequacions format per les restriccions. A la regió solució del sistema l'anomenem regió factible. 
- Obtenir els vèrtexs de la regió factible.
- Calcular el valor de la funció objectiu en cadascun dels vèrtexs per tal de determinar en quin pren el valor màxim o mínim.  

5.1. Exemple 1

Una empresa fabrica ordinadors portàtils i de sobretaula i ven tots els que fabrica. L'empresa té capacitat per a fabricar 3000 ordinadors. Per qüestions de mercat, el nombre d'ordinadors de sobretaula no pot ser inferior a la meitat del nombre de portàtils, però tampoc pot superar el nombre de portàtils. L'empresa guanya 100 € per cada ordinador de sobretaula, i un 20% més en la venda de cada portàtil.

a) Escriu el sistema d'inequacions que satisfà les restriccions del problema.

Anomenarem x al nombre d'ordinadors de sobretaula, i y al de portàtils.

Restriccions:
- L'empresa té capacitat per a fabricar 3000 ordinadors  
- El nombre d'ordinadors de sobretaula no pot ser inferior a la meitat del nombre de portàtils.  
- El nombre d'ordinadors no pot superar el nombre de portàtils. 

Sistema d'inequacions:

b) dibuixa la regió factible i troba els seus vèrtex.

     Dibuixem les rectes

Cadascuna d'aquestes rectes divideix al pla en dos semiplans. Hem de mirar quins semiplans compleixen les inequacions.

Podem veure que el (0,0) compleix la inequació. Per tant és el semiplà on es troba el (0,0)

      En aquest cas com que el (0,0) és de la recta, agafem altre punt. Per exemple, el (1000,0).
                        Veiem que    Per tant, és el semiplà on es troba el punt (1000,0)

     Agafem, per exemple, el (1000,0).
                 Com que 1000 > 0, no compleix la inequació. El pla solució no és el pla on es troba el punt  (100,0)              

En aquest cas la regió factible és l'interior d'aquest triangle.  Trobem els seus vèrtexs.

I l'altre vèrtex serà òbviament el

c) Quants ordinadors de cada classe ha de fabricar per tal de maximitzar els seus beneficis?

    La funció objectiu és:    

    En aquest cas volem un màxim d'aquesta funció.

    Avaluem aquesta funció en cadascun dels vèrtexs:

    Per tant el màxim benefici s'obté fabricant 1000 ordinadors de sobretaula  i 2000 portàtils

5.2. Exemple 2

Una empresa de confecció produeix abrics i vestits. Per a la confecció de cada abric es necessiten 6 hores de treball i 2m de roba i per a la confecció d'un vestit 3 hores de treball i 4 m de roba. cada abric produeix un benefici de 80 € i cada vestit un benefici de 50 €. L'empresa disposa de 2850 hores de treball i de 1700 m de roba.

a) Escriu el sistema d'inequacions que satisfà les restriccions del problema.

Anomenarem x al nombre d'abrics, i y al de vestits.

Sistema d'inequacions:

b) Dibuixa la regió factible i troba els seus vèrtex.

     Dibuixem les rectes

Cadascuna d'aquestes rectes divideix al pla en dos semiplans. Hem de mirar quins semiplans compleixen les inequacions.

Podem veure que el (0,0) compleix la inequació. Per tant és el semiplà on es troba el (0,0)

     Podem veure que el (0,0) compleix la inequació. Per tant és el semiplà on es troba el (0,0)           

En aquest cas la regió factible és l'interior d'aquest polígon.  Trobem els seus vèrtexs.

Veient el dibuix els altres vèrtexs són obvis. Per tant tenim que els vèrtex de la regió factible són:

A(0,425), B(350,250), C(475,0), D(0,0)

c) Quants abrics i vestits cal fabricar per obtenir el benefici màxim, i quin és aquest benefici?

    La funció objectiu és:    

    En aquest cas volem un màxim d'aquesta funció.

    Avaluem aquesta funció en cadascun dels vèrtexs:

    Per tant el màxim benefici s'obté fabricant 350 abrics i 250 vestits.
    I el màxim benefici és 40500 €

5.3. Exemple 3 (vídeo)

Aquest és un vídeo que encara que és del youtube (podria ser que deixés d'estar activat) us pot ajudar ja que podeu anar veient com es fa l'exercici.

(en cada vídeo cliqueu  l'opció de full screen per veure'l  millor)

Vídeo: