Programació lineal: diferència entre les revisions

Contingut suprimit Contingut afegit
m Robot inserta {{Autoritat}}
m Robot: Reemplaçament automàtic de text (-[[Imatge: +[[Fitxer:, -[[Image: +[[Fitxer:, -[[File: +[[Fitxer:)
Línia 17:
 
==Història==
[[FileFitxer:Leonid Kantorovich 1975.jpg|thumb|[[Leonid Kantoròvitx]]]]
El problema consistent en resoldre un sistema de [[inequació|desigualtat]]s lineals data, com a mínim, de l'època de [[Joseph Fourier|Fourier]], en honor al qual s'anomena el mètode de l'[[eliminació de Fourier-Motzkin]]. La primera programació lineal fou desenvolupada per [[Leonid Kantoròvitx]] el 1939<ref>Vegeu el seu treball de 1940 llistat més avall.</ref> per planejar les despeses i ingressos durant la [[Segona Guerra Mundial]], per així reduir els costos de l'exèrcit i incrementar les pèrdues de l'enemic. El mètode fou mantingut en secret fins al 1947, quan [[George Dantzig]] va publicar el [[algorisme símplex|mètode símplex]] i [[John von Neumann]] va desenvolupar la teoria de la [[#Dualitat|dualitat]] com una solució de l'optimització lineal, i l'aplicà en el camp de la [[teoria de jocs]]. Durant la postguerra, moltes indústries li van trobar utilitat per planejar el seu treball diari.
 
Línia 124:
'''Mètode 1:'''
 
[[FileFitxer:Metode1.png|thumb|Metode1]]
 
Un cop dibuixada la regió factible en el gràfic x, y, busquem els punts on s'interseccionen les restriccions, és a dir, els vèrtexs d’aquesta regió factible.
Línia 146:
'''Mètode 2'''
 
[[FileFitxer:Metode2.png|thumb|Metode2]]
 
Un cop dibuixada la regió factible i trobats els vèrtexs d’aquesta, un altre mètode consisteix en dibuixar les corbes de nivell (f(x,y)=k) corresponents a la funció objectiu. Com podem comprovar en el gràfic, el punt (5,1) és el punt de la regió factible intersecat per la corba de nivell més alta (línia groga ), per tant, podem afirmar que la funció assoleix el seu valor màxim en el punt (5,1). Per trobar aquest valor substituirem les coordenades del punt a la funció objectiu, tal com hem fet en el mètode 1:
Línia 155:
'''Mètode 3'''
 
[[FileFitxer:Metode3.png|thumb|Metode3]]
 
El mètode 3 és molt similar al mètode 2, però més senzill i pràctic. Consisteix en representar en el gràfic una de les corbes de nivell (generalment la corba de nivell F(x,y)=k=0) i mitjançant les derivades parcials, representar també el gradient de F(x,y). El gradient indica la direcció de màxim creixement de la funció, per tant, no caldrà representar totes les corbes de nivell. Com podem observar en el gràfic, la corba de nivell més alta que talla la regió factible es troba en el punt (5,1).