En un problema de programació lineal volem optimitzar (maximitzar o minimitzar) una funció lineal que depèn de diverses variables sotmeses a certes restriccions, també lineals. Tractarem primerament exercicis amb només dues variables.

Per resoldre aquests problemes és convenient tenir en compte els següents passos:

  1. Identificar les variables i analitzar les restriccions a les quals estan sotmeses. Identificar la funció que haurem d'optimitzar, que anomenem funció objectiu. Una taula de valors és un instrument molt útil per organitzar la informació.

  2. Plantejar el sistema d'inequacions amb les restriccions i escriure l'expressió algebraica de la funció objectiu.

  3. Trobar la regió factible, de possibles solucions, amb els seus vèrtexs i, en general, representar-la gràficament.

  4. Obtenir l'òptim de la funció objectiu dins la regió factible, comparant els valors que pren aquesta funció en els vèrtexs de la regió factible.

Exercicis

Ara cal aplicar els passos anteriors per resoldre el següent problema:

Una confiteria realitza una oferta als seus clients a través de dos tipus de lots A i B. El lot A porta 3 barres de torró i 5 capses de bombons. El lot B està format per 5 barres de torró i 3 capses de bombons. Per qüestions d'estratègia comercial, el nombre de lots B ha de ser menor que el nombre de lots del tipus A incrementat en 4. El nombre de barres de torró disponibles al magatzem per aquesta oferta és de 52 i el de capses de bombons, 60.
La venda d'un lot del tipus A reporta un guany de 6,5 euros, i un el tipus B, 8,5 euros. Determina el nombre de lots de cada tipus que ha de vendre la confiteria perquè el guany sigui el més gran possible. Calcula aquest guany màxim.


  1. Quines són les variables que hi intervenen ?
    La següent taula pot ajudar a organitzar la informació completant les dades que falten.

  2.   A B Disponible
    Barres turró     52
    Capses bombons     60
    Guany      

  3. Quines són les restriccions a les quals estan sotmeses ?
    Quina és la funció objectiu ?
    Escriu el sistema d'inequacions corresponent i també l'expressió algebraica de la funció objectiu.

  4. Representa gràficament, una a una, i en els mateixos eixos de coordenades, les inequacions del sistema. Identifica la regió factible.

  5. Troba les coordenades dels vèrtexs de la regió factible i calcula el valor de la funció objectiu en cadascun d'ells. Quina és la solució de el problema ?

  6. Ara utilitzarem l'aplicació per representar la regió factible i trobar la solució del problema:

    • Clica sobre la casella A1 per representar gràficament la regió que correspon a la inequació que expressa la restricció en la composició del lot A (barres de torró i capses de bombons).

    • Clica sobre la casella A2 per representar ara la inequació que expressa la restricció en la composició del lot B (barres de torró i capses de bombons)

    • Clica sobre la casella A3 per representar la inequació que expressa la restricció de la relació entre les quantitats de lots.

    • Observa ara la intersecció de totes les regions que has representat: és la regió factible.

    • Ara clica a la casella de la cel·la A15.
      Observa la recta dibuixada. Quina relació té amb la funció objectiu ?
      Què significa el terme independent de l'equació de la recta ?

    • Col·loca el punt sobre els vèrtexs de la regió factible i observa el valor de la funció objectiu en cadascun d'ells.

    • Quina és la solució del problema ?
      Coincideix amb la que havies trobat prèviament ?

  7. Ara clica sobre el botó Reiniciar. Utiliza l'aplicació per a resoldre els següents problemes.

Problemes

  1. Una papereria vol liquidar fins a 78 kg de paper reciclat i fins a 138 kg de paper normal. Per fer-ho disposa de dos tipus de lots, A i B. Els lots A estan formats per 1 kg de paper reciclat i 3 kg de paper normal, i els lots B per 2 kg de paper de cada classe. El preu de venda de cada lot A és de 0,9 i el de cada lot B és d'1.
    Quants lots A i B ha de vendre per maximitzar els seus ingressos ? Quins són aquests ingressos màxims ?

  2. Un fruiter vol liquidar 500 kg de taronges, 400 kg de pomes i 230 kg de peres. Per fer-ho prepara dues bosses de fruita d'oferta: la borsa A consta d'1 kg de taronges i 2 kg de pomes, i la borsa B consta de 2 kg de taronges, 1 kg de pomes i 1 kg de peres. Per a cada bossa de tipus A obté un benefici de 2,5 euros, i 3 euros per a cada bossa de tipus B. Suposant que ven totes les bosses, quantes bosses de cada tipus ha de preparar per maximitzar els guanys ? Quin és el benefici màxim ?

  3. Una companyia química dissenya dues possibles tipus de càmeres de reacció que s'inclouran en una planta per produir dos tipus de polímers P1 i P2. Una planta ha de tenir una capacitat de producció d'almenys 100 unitats de P1 i, almenys, 420 unitats de P2 cada dia.
    Cada càmera de tipus A costa 600000 euros i és capaç de produir 10 unitats de P1 i 20 unitats de P2 per dia. El procés de disseny obliga a tenir almenys 4 càmeres de cada tipus en una planta.
    Quantes càmeres de cada tipus han d'incloure per minimitzar la despesa satisfent el programa de producció requerit ? Formula el sistema d'inequacions associat a el problema. Representa la regió factible i calcula els seus vèrtexs.

  4. Un llibreter compra llibres de dues editorials. L'editorial A ofereix un paquet de 5 novel·les de ciència ficció i 5 històriques per 60 euros, i l'editorial B ofereix un paquet de 5 novel·les de ciència ficció i 10 històriques per 180 euros.
    El llibreter vol comprar un mínim de 2500 novel·les de ciència ficció i un mínim de 3500 novel·les històriques. A més, per motius personals, el llibreter ha promès a l'editorial B que al menys el 25% del nombre total de paquets que comprarà serà de B.

    1. Quants paquets ha de comprar el llibreter de cada editorial per minimitzar el cost, satisfer els mínims i complir la promesa ?

    2. Quant li costaran en total les novel·les ?

  5. Una refineria de petroli adquireix dos tipus de cru, lleuger i pesat, a un preu de 70 i 65 euros per barril, respectivament. Amb cada barril de cru lleuger la refineria produeix 0,3 barrils de gasolina 95, 0,4 barrils de gasolina 98 i 0,2 barrils de gasoil. També amb cada barril de cru pesat produeix 0,1, 0,2 i 0,5 barrils de cada un d'aquests tres productes, respectivament.
    La refineria ha de subministrar almenys 26300 barrils de gasolina 95, 40600 barrils de gasolina 98 i 29500 barrils de gasoil.
    Determina quants barrils de cada tipus de cru ha de comprar la refineria per cobrir les seves necessitats de producció amb un cost mínim i calcula aquest cost.

  6. Una fàbrica de conserves rep l'encàrrec de preparar dos tipus de lots de fruita en almívar. Disposa de 7500 pots de préssec, 6000 pots de pinya i 6000 pots de pera. Els lots de tipus A estan formats per 2 pots de préssec, 2 pots de pinya i 2 pots de pera, i es venen a 20 euros. Els de tipus B, estan formats per 3 pots de préssec, 2 pots de pinya i 1 pot de pera, i es venen a 25 euros.
    Planteja i resol el problema per saber el nombre de lots de cada tipus que ha de produir la fàbrica perquè els ingressos siguin màxims.


Creative Commons License  Idea original - José Luis Alvarez - Proyecto Gauss (Procomún - Intef)