PROGRAMACIÓ LINEAL: PER A QUÈ SERVEIX, MODELS, RESTRICCIONS, APLICACIONS - MATEMÀTIQUES - 2025

La programació lineal és un mètode matemàtic que serveix per optimitzar (maximitzar o minimitzar segons es requereixi) una funció les variables estan subjectes a restriccions, sempre que la funció i les restriccions siguin linealment dependents de les variables.

Generalment la funció a optimitzar modela una situació pràctica, com ara el guany d'un fabricant els inputs, mà d'obra o maquinària són limitats.

Figura 1. La programació lineal és molt utilitzada per optimitzar guanys. Font: Piqsels.

Un dels casos més senzills és el d'una funció lineal a maximitzar, que només depèn de dues variables, anomenades variables de decisió. Pot ser de la forma:

Z = k ₁ x + k ₂ i

Amb k ₁ ik ₂ constants. A aquesta funció se li coneix com la funció objectiu. Per descomptat hi ha situacions que mereixen més de dues variables per al seu estudi, sent més complexes:

Z = k ₁ x ₁ + k ₂ x ₂ + k ₃ x ₃ +….

I les restriccions també es modelen matemàticament mitjançant un sistema d'equacions o inequacions, igualment lineals en x i y.

El conjunt de solucions d'aquest sistema es diu solucions factibles o punts factibles. I entre els punts factibles existeix a el menys un, que optimitza la funció objectiu.

La programació lineal va ser desenvolupada de manera independent pel físic i matemàtic nord-americà George Dantzig (1914-2005) i el matemàtic i economista rus Leonid Kantorovich (1912-1986) poc després de la Segona Guerra Mundial.

El mètode de solució de problemes conegut com a mètode simplex és creació de Dantzig, qui va treballar per a la força aèria nord-americana, la Universitat de Berkeley i la Universitat de Stanford.

Figura 2. Els matemàtics George Dantzig (esquerra) i Leonid Kantorovich (dreta). Font: F. Zapata.

Models de programació lineal

Els elements necessaris per establir un model de programació lineal, adequat a una situació pràctica, són:

-Funció objectiu

-Variables de decisió

-Restricciones

En la funció objectiu es defineix el que es vol aconseguir. Per exemple, suposem que es vol maximitzar els guanys obtinguts de la fabricació de determinats productes. Llavors s'estableix l'opció "guany", segons el preu a què es venen els productes.

En termes matemàtics, aquesta funció pot expressar-se abreujadament usant la notació de sumatori:

Z = Σk _i x _i

En aquesta equació, k _i són coeficients i x _i són les variables de decisió.

Les variables de decisió són els elements de sistema que són controlats té i els seus valors són nombres reals positius. En l'exemple proposat, les variables de decisió són la quantitat de cada producte a fabricar per obtenir el guany màxim.

Finalment, tenim les restriccions, que són equacions o inequacions lineals en termes de les variables de decisió. En elles es descriuen les limitacions a el problema, que són conegudes i poden ser per exemple les quantitats de matèria primera disponible a la fabricació.

Tipus de restriccions

Es pot tenir una quantitat M de limitacions, començant des de j = 1 fins j = M. Matemàticament les restriccions són de tres tipus:

1. A _j = Σ a _ij. x _i
2. B _j ≥ Σ b _ij. x _i
3. C _j ≤ Σ c _ij. x _i

La primera restricció és de tipus equació lineal i vol dir que el valor A _j, el qual és conegut, ha de ser respectat.

Les dues restriccions restants són inequacions lineals i significa que els valors B _j i C _j, coneguts, poden respectar o superar-se, quan el símbol que apareix és ≥ (major o igual que) o bé respectar o no superar-se, si el símbol és ≤ (menor o igual que).

Exemple de model

Els camps d'aplicació són molt diversos, abastant des administració d'empreses fins nutrició, però per entendre el mètode, es proposa tot seguit un model senzill d'una situació pràctica amb dues variables.

Una pastisseria local és coneguda per dues especialitats: la coca selva negra i la coca sacripantina.

En la seva elaboració requereixen ous i sucre. Per a la selva negra es necessiten 9 ous i 500 g de sucre, mentre que per a la sacripantina són necessaris 8 ous i 800 g de sucre. Els respectius preus de venda són 8 i 10 $.

El problema és: ¿Quantes coques de cada tipus ha de fabricar la pastisseria per maximitzar el seu guany, sabent que disposa de 10 quilos de sucre i 144 ous?

Variables de decisió

Les variables de decisió són "x" i "i", les quals prenen valors reals:

-x: la quantitat de coques tipus selva negra

-i: les coques tipus sacripantina.

restriccions

Les restriccions venen donades pel fet que el nombre de coques és una quantitat positiva i hi ha quantitats limitades de matèria primera per a preparar-les.

Per tant, en forma matemàtica, aquestes restriccions adquireixen la forma:

1. x ≥ 0
2. i ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

Les restriccions 1 i 2 constitueixen la condició de no negativitat exposada anteriorment, i totes les inequacions plantejades són lineals. A les restriccions 3 i 4 estan els valors que no s'han de superar: 144 ous i 10 kg de sucre.

funció objectiu

Finalment, la funció objectiu és el guany obtingut a l'fabricar "x" quantitat de coques selva negra més "i" quantitat de sacripantinas. Es construeix multiplicant preu per quantitat de coques confeccionades i sumant per a cada tipus. Es tracta d'una funció lineal a la qual anomenarem G (x, y):

G = 8x + 10y

Mètodes de solució

Entre les diverses metodologies de solució es troben els mètodes gràfics, l'algoritme simplex i el mètode del punt interior, per esmentar alguns.

- Mètode gràfic o geomètric

Quan es té un problema de dues variables com el de la secció anterior, les restriccions determinen una regió poligonal en el pla xy, anomenada regió factible o regió de viabilitat.

Figura 3. La regió factible, on es troba la solució de el problema d'optimització. Font: Wikimedia Commons.

Aquesta regió es construeix mitjançant les rectes de restricció, que són les rectes obtingudes a partir de les inequacions de les restriccions, treballant únicament amb el signe d'igualtat.

En el cas de la pastisseria que voleu optimitzar els guanys, les rectes de restricció són:

1. x = 0
2. i = 0
3. 9x + 8y = 144
4. 0.5 x + 0.8y = 10

Tots els punts de la regió tancada per aquestes rectes són possibles solucions, així que hi ha infinites d'elles. Excepte en el cas en què la regió factible resulti buida, en aquest cas el problema plantejat no té solució.

Afortunadament, per al problema de la pastisseria la regió factible no és buida, la tenim a continuació.

Figura 4. La regió factible de el problema de la pastisseria. La recta amb guany 0 creua l'origen. Font: F. Zapata amb Geogebra.

La solució òptima, si és que existeix, es troba amb l'ajuda de la funció objectiu. Per exemple, quan es tracta de trobar el guany màxim G, es té la següent recta, a la qual s'anomena recta d'iso-benefici:

G = k ₁ x + k ₂ i → i = -k ₁ x / k ₂ + G / k ₂

Amb aquesta recta s'obtenen tots els parells (x, y) que proporcionen un guany donada G, així que hi ha una família de rectes segons el valor de G, però totes amb el mateix pendent -k ₁ / k ₂, de manera que són rectes paral·leles.

La solució òptima

Ara bé, es pot demostrar que la solució òptima d'un problema lineal sempre és un punt extrem o vèrtex de la regió factible. llavors:

Si la recta més propera a l'origen té tot un segment en comú amb la regió factible, es diu que hi ha infinites solucions. Aquest cas passa si el pendent de la recta de iso-beneficis és igual a la d'alguna de les altres rectes que limiten la regió.

Per a la nostra pastisseria, els vèrtexs candidats són A, B i C.

- Mètode simplex de Dantzig

El mètode gràfic o geomètric és aplicable per dues variables. No obstant això, resulta més complicat quan hi ha tres variables, i impossible d'utilitzar per a un nombre major de variables.

Quan es tracta de problemes de més de dues variables es fa servir el mètode simplex, que consisteix en una sèrie d'algoritmes per optimitzar les funcions objectius. Solen utilitzar-se matrius i aritmètica senzilla per dur a terme els càlculs.

El mètode simplex comença triant una solució factible i comprovant si és òptima. Si ho és ja tenim resolt el problema, però si no ho és, es continua cap a una solució més propera a l'optimització. Si la solució existeix, l'algoritme dóna amb ella a uns quants intents.

aplicacions

La programació lineal i la no-lineal s'apliquen en molts camps per prendre les millors decisions pel que fa a disminuir costos i augmentar els guanys, que no sempre són monetàries, ja que poden mesurar-se en temps per exemple, si es busca minimitzar el temps necessari per dur a terme una sèrie d'operacions.

Heus aquí alguns camps:

-En màrqueting s'empra per trobar la millor combinació de mitjans (xarxes socials, televisió, premsa i altres) per publicitar cert producte.

-Per l'assignació de tasques adequades a el personal d'una empresa o fàbrica o d'horaris als mateixos.

-A la selecció de l'aliment més nutritiu i a el menor cost en les indústries ramaderes i avícoles.

exercicis resolts

- Exercici 1

Resoldre gràficament el model de programació lineal plantejat en les seccions precedents.

solució

Cal graficar el conjunt de valors determinats pel sistema de restriccions especificat en el problema:

1. x ≥ 0
2. i ≥0
3. 9x + 8y ≤ 144
4. 0.5 x + 0.8y ≤ 10

La regió donada per les inequacions 1 i 2 correspon a el primer quadrant de el pla cartesià. Pel que fa a les inequacions 3 i 4, es comença per trobar les rectes de restricció:

9x + 8y = 144

0.5 x + 0.8y = 10 → 5x + 8y = 100

La regió factible és un quadrilàter els vèrtexs són els punts A, B, C i D.

El guany mínima és 0, per tant la recta 8x + 10y = 0 és el límit inferior i les rectes d'iso-benefici tenen pendent -8/10 = - 0.8.

Aquest valor és diferent de les pendents de les altres rectes de restricció i com la regió factible és fitada, hi ha la solució única.

Figura 5. Solució gràfica de l'exercici 1, mostrant la regió factible i el punt solució C en un dels vèrtexs d'aquesta regió. Font: F. Zapata.

Aquesta solució correspon a una recta de pendent -0.8 que passa per algun dels punts A, B o C, les coordenades són:

A (11; 5.625)

B (0; 12.5)

C (16, 0)

solució òptima

Calculem el valor de G per a cada un d'aquests punts:

- (11; 5.625): G _A = 8 x 11 + 10 x 5.625 = 144.25

- (0; 12.5): G _B = 8 x 0 + 10 x 12.5 = 125

- (16, 0): G _C = 8 x 16 + 10 x 0 = 128

La major guany es troba fabricant 11 coques de selva negra i 5.625 coques sacripantinas. Aquesta solució concorda amb la trobada a través del programari.

- Exercici 2

Verificar el resultat de l'exercici anterior mitjançant l'ús de la funció Solver (Solucionador) disponible a la majoria dels fulls de càlcul com Excel o Calc de LibreOffice, els quals incorporen l'algoritme Símplex per a l'optimització en programació lineal.

solució

Figura 6. Detall de la solució de l'exercici 1 a través del full de càlcul Calc de Lliure Office. Font: F. Zapata.

Figura 7. Detall de la solució de l'exercici 1 a través del full de càlcul Calc de Lliure Office. Font: F. Zapata.

referències

1. Brilliant. Linear Programming. Recuperat de: brilliant.org.
2. Eppen, G. 2000. Investigació d'Operacions a la ciència administrativa. 5ta. Edició. Prentice Hall.
3. Haeussler, I. 1992. Matemàtiques per Administració i Economia. 2dóna. Edició. Grup Editorial Iberoamericana.
4. Hiru.eus. Programació lineal. Recuperat de: hiru.eus.
5. Wikipedia. Programació lineal. Recuperat de: és. wikipedia.org.