Programació lineal és un concepte matemàtic que s'utilitza per trobar la solució òptima de la funció lineal. Aquest mètode utilitza supòsits senzills per optimitzar la funció donada. La programació lineal té una gran aplicació al món real i s'utilitza per resoldre diversos tipus de problemes.

La programació lineal s'utilitza en diverses indústries, com ara les indústries navilieres, les indústries manufactureres, les indústries del transport, les telecomunicacions i altres.

El terme programació lineal consta de dues paraules lineal i programació, la paraula lineal indica la relació entre diversos tipus de variables de grau 1 utilitzades en un problema i la paraula programació ens indica el procediment pas a pas per resoldre aquests problemes.

En aquest article, coneixerem detalladament la programació lineal, els seus exemples, fórmules i altres conceptes.

Taula de contingut

• Què és la programació lineal?
• Components de la programació lineal
• Exemples de programació lineal
• Problemes de programació lineal
• Tipus de problemes de programació lineal
• Fórmula de programació lineal
• Com resoldre problemes de programació lineal?
• Mètodes de programació lineal
• Mètode simplex de programació lineal
• Mètode Gràfic de Programació Lineal
• Aplicacions de programació lineal
• Importància de la programació lineal
• Aplicacions actualitzades de la programació lineal
• Programació lineal en investigació operativa
• Mètode Simplex

Què és la programació lineal?

Programació lineal o Optimització lineal és una tècnica que ens ajuda a trobar la solució òptima per a un problema determinat, una solució òptima és una solució que és el millor resultat possible d'un problema determinat.

En termes senzills, és el mètode per esbrinar com fer alguna cosa de la millor manera possible. Amb recursos limitats, cal fer una utilització òptima dels recursos i aconseguir el millor resultat possible en un objectiu particular, com ara el menor cost, el marge més alt o el menor temps.

La situació que requereix una recerca dels millors valors de les variables subjectes a determinades restriccions és on utilitzem problemes de programació lineal. Aquestes situacions no es poden gestionar amb les tècniques de càlcul i numèriques habituals.

Definició de programació lineal

La programació lineal és la tècnica utilitzada per optimitzar un escenari concret. L'ús de la programació lineal ens proporciona el millor resultat possible en una situació determinada. Utilitza tots els recursos disponibles de manera que produeixin el resultat òptim.

Components de la programació lineal

Els components bàsics d'un problema de programació lineal (LP) són:

• Variables de decisió: Variables que voleu determinar per aconseguir la solució òptima.
• Funció objectiu: M equació atemàtica que representa l'objectiu que voleu assolir
• Restriccions: Limitacions o restriccions que han de seguir les vostres variables de decisió.
• Restriccions de no negativitat: En alguns escenaris del món real, les variables de decisió no poden ser negatives

Característiques addicionals de la programació lineal

• Finitud: El nombre de variables de decisió i restriccions en un problema LP és finit.
• Linealitat: La funció objectiu i totes les restriccions han de ser funcions lineals de les variables de decisió . Significa que el grau de variables hauria de ser un.

Exemples de programació lineal

Podem entendre les situacions en què s'aplica la programació lineal amb l'ajuda de l'exemple que es comenta a continuació,

Suposem que un repartidor ha de lliurar 8 paquets al dia a les diferents ubicacions d'una ciutat. Ha de triar tots els paquets de A i els ha de lliurar als punts P, Q, R, S, T, U, V i W. La distància entre ells s'indica mitjançant les línies tal com es mostra a la imatge següent. El camí més curt seguit pel repartidor es calcula mitjançant el concepte de Programació Lineal.

rudyard kipling si explicació

Problemes de programació lineal

Problemes de programació lineal (LPP) implica optimitzar una funció lineal per trobar la solució de valor òptima per a la funció. El valor òptim pot ser el valor màxim o el valor mínim.

En LPP, les funcions lineals s'anomenen funcions objectives. Una funció objectiu pot tenir múltiples variables, que estan sotmeses a condicions i han de satisfer el restriccions lineals .

Tipus de problemes de programació lineal

Hi ha molts problemes de programació lineal (LPP) diferents, però en aquest article tractarem tres problemes principals de programació lineal.

Problemes de fabricació

Els problemes de fabricació són un problema que tracta sobre el nombre d'unitats que s'han de produir o vendre per maximitzar els beneficis quan cada producte requereix mà d'obra fixa, hores de màquina i matèries primeres.

Problemes de dieta

S'utilitza per calcular el nombre de diferents tipus de constituents que s'han d'incloure en la dieta per obtenir el cost mínim, subjecte a la disponibilitat dels aliments i els seus preus.

Problemes de transport

S'utilitza per determinar l'horari de transport per trobar la forma més barata de transportar un producte des de plantes/fàbriques situades en diferents llocs a diferents mercats.

Fórmula de programació lineal

Un problema de programació lineal consisteix en,

• Variables de decisió
• Funció objectiva
• Restriccions
• Restriccions no negatives

Variables de decisió són les variables x i y, que decideixen la sortida del problema de programació lineal i representen la solució final.

El funció objectiva , representada generalment per Z, és la funció lineal que cal optimitzar segons la condició donada per obtenir la solució final.

El restriccions imposades a les variables de decisió que limiten els seus valors s'anomenen restriccions.

Ara, la fórmula general d'un problema de programació lineal és:

Funció Objectiva : Z = ax + by

Restriccions: cx + dy ≥ e, px + qy ≤ r

Restriccions no negatives: x ≥ 0, i ≥ 0

En la condició anterior, x i y són les variables de decisió.

Com resoldre problemes de programació lineal?

Abans de resoldre els problemes de programació lineal primer hem de formular els problemes segons els paràmetres estàndard. Els passos per resoldre problemes de programació lineal són:

Pas 1: Marqueu les variables de decisió del problema.

Pas 2: Construïu la funció objectiu del problema i comproveu si cal minimitzar o maximitzar la funció.

Pas 3: Escriu totes les restriccions dels problemes lineals.

Pas 4: Garantir restriccions no negatives de les variables de decisió.

Pas 5: Ara resoleu el problema de programació lineal utilitzant qualsevol mètode, generalment utilitzem el mètode simplex o el gràfic.

Mètodes de programació lineal

Utilitzem diversos mètodes per resoldre problemes de programació lineal. Els dos mètodes més comuns utilitzats són,

• Mètode Simplex
• Mètode Gràfic

Anem a conèixer aquests dos mètodes en detall en aquest article,

Mètode simplex de programació lineal

Un dels mètodes més comuns per resoldre el problema de programació lineal és el mètode simplex. En aquest mètode, repetim una condició específica 'n' diverses vegades fins que s'aconsegueix una solució òptima.

Els passos necessaris per resoldre problemes de programació lineal mitjançant el mètode simplex són:

Pas 1: Formular els problemes de programació lineal a partir de les restriccions donades.

Pas 2: Converteix totes les desigualtats donades en equacions o igualtats dels problemes de programació lineal afegint la variable slack a cada desigualtat quan sigui necessari.

Pas 3: Construeix la taula simplex inicial. Representant cada equació de restricció en una fila i escrivint la funció objectiu a la fila inferior. La taula així obtinguda s'anomena taula Simplex.

Pas 4: Identifiqueu l'entrada negativa més gran a la fila inferior, la columna de l'element amb l'entrada negativa més alta s'anomena columna pivot.

Pas 5: Dividiu les entrades de la columna més a la dreta amb les entrades de la columna pivot respectiva, excloent les entrades de la fila més avall. Ara la fila que conté la menor entrada s'anomena fila pivot. L'element de pivot s'obté per la intersecció de la fila de pivot i la columna de pivot.

Pas 6: Utilitzant l'operació de matriu i amb l'ajuda de l'element pivot, feu que totes les entrades de la columna pivot siguin zero.

Pas 7: Comproveu les entrades no negatives a la fila inferior si no hi ha entrades negatives a la fila inferior, finalitzeu el procés, sinó torneu a iniciar-lo des del pas 4.

Pas 8: La taula símplex final així obtinguda dóna la solució al nostre problema.

Mètode Gràfic de Programació Lineal

El mètode gràfic és un altre mètode que el mètode Simplex que s'utilitza per resoldre problemes de programació lineal. Com el seu nom indica, aquest mètode utilitza gràfics per resoldre els problemes de programació lineal donats. Aquest és el millor mètode per resoldre problemes de programació lineal i requereix menys esforç que el mètode simplex.

Mentre utilitzem aquest mètode tracem totes les desigualtats que estan sotmeses a restriccions en els problemes de programació lineal donats. Tan aviat com totes les desigualtats de la LPP donada es representen en el gràfic XY, la regió comuna de totes les desigualtats dóna la solució òptima. Es calculen tots els punts de cantonada de la regió factible i es calcula el valor de la funció objectiu en tots aquests punts, i comparant aquests valors obtenim la solució òptima de la LPP.

Exemple: Trobeu el valor màxim i mínim de z = 6x + 9y quan les condicions de restricció són:

• 2x + 3y ≤ 12
• x i y ≥ 0
• x + y ≤ 5

Solució:

Pas 1 : primer convertiu les inequacions en equacions normals. Per tant, les equacions seran 2x+3y = 0, x = 0, y = 0 i x + y = 5.

Pas 2 : Trobeu els punts en què 2x + 3y i x + y = 5 tallen l'eix x i l'eix y. Per trobar el punt d'intersecció de l'eix x poseu y = 0 a l'equació respectiva i trobeu el punt. De la mateixa manera, per als punts d'intersecció de l'eix y poseu x = 0 a l'equació respectiva.

Pas 3 : Dibuixa les dues línies tallant l'eix X i l'eix Y. Trobem que els dos eixos es tallen mútuament a (3,2).

Pas 4 : Per a x ≥ 0 i y ≥ 0, trobem que se segueixen ambdues inequacions. Per tant, la regió inclourà una regió d'àrea tancada per dos eixos i ambdues línies incloent l'origen. La regió representada es mostra a continuació a la figura.

Pas 5 : Trobeu Z per a cada punt i màxims i mínims.

Coordenades	Z = 6x + 9y
(0,5)	Z = 45
(0,4)	Z = 36
(5,0)	Z = 30
(6,0)	Z = 36
(3,2)	Z = 36

Per tant, trobem que Z = 6x + 9y és màxim a (0,5) i mínim a (5,0).

Aplicacions de programació lineal

La programació lineal té aplicacions en diversos camps. S'utilitza per trobar el cost mínim d'un procés quan es donen totes les restriccions dels problemes. S'utilitza per optimitzar el cost de transport del vehicle, etc. Hi ha diverses aplicacions de la Programació Lineal

Indústries d'Enginyeria

Les indústries d'enginyeria utilitzen la programació lineal per resoldre problemes de disseny i fabricació i per obtenir el màxim rendiment d'una condició determinada.

Indústries manufactureres

Les indústries manufactureres utilitzen programació lineal per maximitzar els beneficis de les empreses i reduir el cost de fabricació.

Indústries Energètiques

Les empreses energètiques utilitzen la programació lineal per optimitzar la seva producció.

Indústries del transport

La programació lineal també s'utilitza a les indústries del transport per trobar el camí per minimitzar el cost del transport.

Importància de la programació lineal

La programació lineal té una gran importància en diverses indústries, maximitza el valor de sortida alhora que minimitza els valors d'entrada segons diverses restriccions.

LP és molt aplicable quan tenim diverses condicions mentre resolem un problema i hem d'optimitzar la sortida del problema, és a dir, hem de trobar el valor mínim o el màxim segons una condició determinada.

Llegeix més,

• Desigualtats lineals
• Solució algebraica de desigualtats lineals

Problemes de programació lineal

Problema 1: Una empresa fabrica i ven dos tipus de productes i el cost de producció de cada unitat a i b és de 200 i 150 rupies, respectivament, cada unitat de producte dóna un benefici de 20 rupies i cada unitat de producte b produeix un benefici de 15 rupies en vendre . L'empresa estima que la demanda mensual d'A i B és com a màxim de la unitat collida en tot el pressupost de producció del mes s'estableix en 50.000 rupies. Quantes unitats ha de fabricar l'empresa per obtenir el màxim benefici de les seves vendes mensuals d'un i b?

Solució:

Sigui x = nombre d'unitats de tipus A

y = Nombre d'unitats de tipus B

Maximitza Z = 40x + 50y

Subjecte a les limitacions

3x + y ≤ 9

x + 2y ≤ 8

i x, y ≥ 0

Considereu l'equació,

3x + y = 9

x = 3

y = 0

i x + 2y = 8

x = 8

y = 0

Ara, podem determinar el valor màxim de Z avaluant el valor de Z en els quatre punts (vèrtexs) que es mostra a continuació

Vèrtexs	Z = 40x + 50y
(0, 0)	Z = 40 × 0 + 50 × 0 = Rs. 0
(3, 0)	Z = 40 × 3 + 50 × 0 = Rs. 120
(0, 4)	Z = 40 × 0 + 50 × 4 = Rs. 200
(2, 3)	Z = 40 × 2 + 50 × 3 = Rs. 230

Benefici màxim, Z = Rs. 230

∴ El nombre d'unitats del tipus A és 2 i el nombre d'unitats del tipus B és 3.

Problema 2: Maximitzar Z = 3x + 4y.

Subjecte a les restriccions , x + y ≤ 450, 2x + y ≤ 600 i x, y ≤ 0.

Solució:

Tenim del donat

Restriccions (1)

X + Y = 450

Putting x = 0, ⇒ 0 + y = 450 ⇒ y = 450

Putting y = 0, ⇒ x + 0 = 450 ⇒ x = 450

Des de, Restriccions (2)

2x + y = 600

Putting x = 0, ⇒ 0 + y = 600 ⇒ y = 600

Putting y = 0, ⇒ 2x + 0 = 600 ⇒ x = 300

Ara, tenim la coordenada de punts Z = 3x + 4y

Per tant, la solució òptima màxima Z = 1800 a la coordenada x = 0 i y = 450. La gràfica es mostra a continuació.

Aplicacions actualitzades de la programació lineal

La programació lineal, una tècnica matemàtica potent, s'utilitza per resoldre problemes d'optimització en diverses indústries. Aquí hi ha algunes aplicacions modernes:

• Optimització de la cadena de subministrament : La programació lineal ajuda les empreses a minimitzar costos i maximitzar l'eficiència en les seves cadenes de subministrament. S'utilitza per determinar les rutes de transport, les operacions de magatzem i les estratègies de gestió d'inventaris més rendibles.
• Gestió de l'energia : En el sector energètic, la programació lineal s'utilitza per optimitzar la combinació de mètodes de producció d'energia. Això inclou equilibrar les fonts d'energia tradicionals amb les renovables per reduir costos i l'impacte ambiental alhora que satisfan la demanda.
• Disseny de xarxes de telecomunicacions : La programació lineal ajuda a dissenyar xarxes de telecomunicacions eficients. Ajuda a assignar ample de banda, dissenyar dissenys de xarxa i optimitzar el flux de dades per garantir una comunicació d'alta velocitat a menors costos.
• Planificació financera : Les empreses i els analistes financers utilitzen la programació lineal per a l'optimització de la cartera, la gestió del risc i el pressupost de capital. Ajuda a prendre decisions d'inversió que maximitzen els rendiments alhora que minimitzen el risc.
• Logística Sanitària : En l'àmbit sanitari, la programació lineal s'aplica per optimitzar l'assignació de recursos, com ara llits hospitalaris, personal mèdic i equipaments. És fonamental per millorar l'atenció al pacient, reduir els temps d'espera i gestionar els costos de manera eficaç.
• Optimització del procés de fabricació : La programació lineal s'utilitza per determinar els nivells de producció òptims per a diversos productes dins d'una instal·lació de fabricació, tenint en compte limitacions com la mà d'obra, els materials i la disponibilitat de la màquina.
• Planificació Agrària : Els agricultors i els planificadors agrícoles utilitzen la programació lineal per decidir sobre la selecció de cultius, l'ús de la terra i l'assignació de recursos per maximitzar els rendiments i els beneficis alhora que es conserven els recursos.
• Programació de la tripulació de la companyia aèria : Les companyies aèries utilitzen programació lineal per programar les tripulacions de manera eficient, assegurant que els vols tinguin personal d'acord amb la normativa i minimitzant els costos operatius.

Aquestes aplicacions demostren la versatilitat i el poder de la programació lineal per resoldre problemes d'optimització complexos en diversos sectors, mostrant la seva rellevància en el món actual basat en dades.

Programació lineal en investigació operativa

• Eina bàsica : La programació lineal és una eina fonamental en la investigació operativa per optimitzar recursos.
• Presa de decisions : Ajuda a prendre les millors decisions pel que fa a l'assignació de recursos, la maximització dels beneficis o la minimització de costos.
• Àmplies aplicacions : S'utilitza en diversos camps com ara la logística, la fabricació, les finances i l'assistència sanitària per resoldre problemes complexos.
• Modelització de problemes del món real : Transforma problemes del món real en models matemàtics per trobar les solucions més eficients.

Mètode Simplex

• Algoritme d'optimització : El mètode simplex és un algorisme potent utilitzat en programació lineal per trobar la solució òptima a les desigualtats lineals.
• Enfocament pas a pas : Es mou iterativament cap a la millor solució navegant per les vores de la regió factible definida per restriccions.
• Eficiència : Conegut per la seva eficiència en la resolució de problemes de programació lineal a gran escala.
• Versatilitat : Aplicable a diversos dominis com ara la planificació de la dieta, els fluxos de xarxa, la programació de la producció i molt més, mostrant la seva versatilitat.

Programació lineal - Preguntes freqüents

Què és la programació lineal?

La programació lineal és un concepte matemàtic que s'utilitza per optimitzar un problema lineal determinat que té una varietat de restriccions. Utilitzant la programació lineal obtenim la sortida òptima del problema donat

Què són els problemes de programació lineal?

Els problemes de programació lineal (LPP) són els problemes que donen la solució òptima a les condicions donades.

Què és la fórmula de programació lineal?

Les fórmules generals de programació lineal són,

• Funció objectiu: Z = ax + by
• Restriccions: px + qy ≤ r, sx + ty ≤ u
• Restriccions no negatives: x ≥ 0, y ≥ 0

Quins són els diferents tipus de programació lineal?

Els diferents tipus de mètodes de programació lineal són,

• Programació Lineal per Mètode Simplex
• Programació lineal pel mètode R
• Programació lineal per mètode gràfic

Quins són els requisits de la programació lineal?

Diversos requisits dels problemes de programació lineal són:

• Linealitat
• Funció Objectiva
• Restriccions
• No-negativitat

Quins són els avantatges de la programació lineal?

Diversos avantatges de la programació lineal són,

• Proporciona la solució òptima a qualsevol problema lineal donat.
• És fàcil d'utilitzar i sempre dóna resultats consistents
• Ajuda a maximitzar els beneficis i reduir el cost dels inputs.