Programació lineal

Primera part. Rectes al pla i punts de tall

De moment només vull que em feu un dibuix d’una figura formada per rectes al pla. res més. Quan estiguin els dibuixos seguirem treballant el tema.

Exercici 1

Dibuixeu les següents rectes del pla, trobant tots els punts de tall que hi hagi entre les rectes.

• L’eix d’abscisses
• x = 0
• x = 4
• y = x + 1
• x + y = 5

Nota: Són 9 els punts que heu de trobar.

Solució exercici 1

Segona Part. Regions del pla.

Una recta separa el pla en dos SEMIPLANS

Exemple 1 (recta vertical)

La recta x = 4 separa el pla en dos semiplans, que són:

• x < 4, el semiplà a l’esquerra de la recta vertical
• x > 4, el semiplà a la dreta de la recta vertical.

Exemple 2 (recta obliqua expressada amb equació explicita)

La recta y = x + 1 separa el pla en dos semiplans, que són

• y < x + 1, la regió del pla per sota de la recta
• y > x + 1, la regió del pla per sobre de la recta

El mateix criteri serveis per rectes horitzontals, com y = 0

• y < 0, la regió del pla per sota de l’eix de les x
• y > 0, la regió del pla per sobre de l’eix de les x

Exemple 3 (recta obliqua expressada amb equació general)

La recta x + y = 5 separa el pla en dos semiplans.

Per determinar quin és quin segons el sentit de la desigualtat, podríem aïllar la y i fer-ho com a l’exercici 2.

Però una manera més ràpida és provant el punt (0,0) en quina regió està. d’aquesta manera

x + y < 5 és la regió del pla que està per sota de la recta

Justificació
El punt (0,0), que està per sota de la recta, compleix la inequació, 0 + 0 < 5.

x + y > 5 és la regió del pla que està per sobra de la recta

ADVERTÈNCIA!

Un es pot pensar que en l’equació Ax +By = C.

• El sentit < de la desigualtat sempre dona la regió que està per sota de la recta
• El sentit < de la desigualtat sempre dona la regió que està per sobre de la recta

FALS! Depèn del signes de A i B. Per no equivocar-vos teniu dos mètodes.

1. Trobar l’equació explicita aïllant la y, i aleshores sí,
   “y < …” per sota, “y > …” per sobre.
2. Fer la prova de quina de les dues desigualtat verifica el punt (0,0)
   i fixar-se en la regió en la que està aquest punt.

Els eixos de coordenades divideixen el pla en quatre QUADRANTS

1. x > 0 i y > 0, que és el primer quadrant
2. x < 0 i y > 0, que és el segon quadrant
3. x < 0 i y < 0, que és el tercer quadrant
4. x > 0 i y < 0, que és el quart quadrant

Regions obertes del pla

Els semiplans i els quadrants són exemples de regions obertes del pla.

Un altre regió oberta del pla seria la determinada per les següents inequacions:

• y > 0
• y > x + 1
• x < 0
• x + y < 5

Heu de saber reconèixer que la regió del pla determinada per aquestes quatre equacions és la regió on hi ha un *. És una regió oberta.

Regions tancades del pla

Podem referir-nos a les regions tancades pel punts dels seus vèrtex.

Exemple 4

• GHI determina un triangle, com ho fan ABG, BCD, DEF, AEI, BEH, CFH…
• ADFI determina un quadrilàter, com també ho fa BEIG…
• BDFIG determina un pentàgon, no regular.

Aquestes regions tancades també es poden expressar per desigualtats.

Exercici 2

Expressar amb desigualtats el quadrilàter BEIG

Solució exercici 2

• x + y < 5, desigualtat que determina la regió per sota de la recta que conté l’aresta BE del quadrilàter.
• y > 0, desigualtat que determina la regió per sobre de la recta que conté l’aresta EI del quadrilàter.
• x > 0, desigualtat que determina la regió a la dreta la recta que conté l’aresta IG del quadrilàter.
• y < x + 1, desigualtat que determina la regió per sota de la recta que conté l’aresta GB del quadrilàter.

Anem a veure si fins aquí està entès. Us proposo quatre exercici breus.

Exercici 3

Expressar amb desigualtats el triangle BCD

Exercici 4

Expressar amb desigualtats el quadrilàter ADFI

Exercici 5

Expressar amb desigualtats el pentàgon BDFIG

Exercici 6

Pintar de color la regió delimitada per les rectes

• y = x + 1
• x = 4
• x + y = 5
• y = 0

1. És oberta o tancada aquesta regió?
2. Determineu el sentit de cada una de les quatre desigualtats que determinen la regió.

Solució exercici 3

• y < x + 1
• x + y > 5
• x < 4

Solució exercici 4

• x + y < 5
• x > 0
• x < 4
• y > 0

Solució exercici 5

• y < x + 1
• x + y < 5
• x > 0
• x < 4
• y > 0

Solució exercici 6

• És oberta, és la regió marcada amb **.

Les desigualtats són:

• y < x + 1
• x + y > 5
• x > 4
• y > 0

Funció objectiu

Una funció objectiu és z = f(x, y)

Si l’expressió f(x,y) no fos lineal, per trobar el màxim i el mínim d’aquesta funció objectiu en una regió del pla hauríem de fer derivades en dues variables. És temari de segon d’universitat, tranquils, no entra.

Quan la funció objectiu és lineal, z = f(x,z) = Ax + By, geomètricament un pla obliquo (no vertical), trobar el màxim i mínim en una regió del pla és molt fàcil, és resol amb PROGRAMACIÓ LINEAL.

En aquest cas, els màxim o mínim en una regió del pla mai s’obtenen a l’interior de la regió, s’obtenen sempre a la vorera. Hi ha tres casos:

1. En un dels vèrtex de la regió.
2. En el segment que uneix dos vèrtex de la regió.
3. Mai, en el cas que sigui una regió oberta i el pla creixi cap a infinit o decreixi cap a a menys infinit en aquesta regió.

Per resoldre l’exercici, cal recorre a un full de càlcul o calcular-ho a ma.

Exercici 7

En la següent taula tens tres funcions objectius.

Sobre les quatre regions que hem treballat en l’exercici anterior, tres tancades i una d’oberta, ens pregunten que determinem el màxim i el mínim de la funció objectiu i que indique en quin punt s’assoleix.

Us he començat a fer l’exercici, per que tingueu una referència.

CAL QUE COMPLETEU TOTES LES CASELLES EN GROC.

Solucions a l’exercici 7