Algoritme símplex

Algoritme símplex

Un sistema de desigualtats llineals definix un poliedre com una regió factible. L'algoritme símplex comença en un vèrtiç i es mou a lo llarc de les arestes del poliedre fins que alcança el vèrtiç de la solució òptima.

En optimisació matemàtica, el terme algoritme símplex habitualment es referix a un conjunt de métodos molt usats per a resoldre problemes de programació llineal, en els quals es busca el màxim d'una funció llineal sobre un conjunt de variables que satisfaça un conjunt d'equacions o inecuaciones llineals. El algoritme símplex primal va ser desenrollat pel matemàtic nortamericà George Dantzig en 1947, i procedix examinant vèrtiços adjacents del poliedre de solucions. Un algoritme símplex és d'alguna manera un algoritme de pivot.

Un método cridat de manera similar, pero no relacionat a l'anterior, és el método de Nelder-Pixeu (1965) o método de descens (o ascens) símplex; un método numèric que busca un mínim (o màxim) local d'una funció qualsevol examinant en cada pas els vèrtiços d'un símplex.

L'algoritme del método símplex va ser elegit com un dels 10 algoritmes més importants de el XX.

Entrada del problema

Considerem un problema de programació llineal,

$\{\begin{array}{cc}\text{Maximizar}& z={𝐜}^T𝐱\\ \text{Sujeto a:}\\ & 𝐀𝐱\le 𝐛\\ & 𝐱\ge 0\end{array}$

L'algoritme símplex requerix que la matriu del problema estiga en la seua forma aumentada. El problema pot ser descrit com seguix:

Maximizar $z$ en:

$\left[\begin{array}{ccc}1& -{𝐜}^T& 0\\ 0& 𝐀& 𝐈\end{array}\right]\left[\begin{array}{c}z\\ 𝐱\\ {𝐱}_s\end{array}\right]=\left[\begin{array}{c}0\\ 𝐛\end{array}\right]$

$𝐱,{𝐱}_s\ge 0$

a on x són les variables des de la forma estàndar, x_s són les variables de chala introduïdes en el procés de aumentación, c conté els coeficients d'optimisació, descriu el sistema d'equacions contretes, i z és la variable a ser maximizar.

El sistema està típicament no determinat, ya que el número de variables excedix el número d'equacions. La diferència entre el número de variables i el número d'equacions nos dona els graus de llibertat associats al problema. Qualsevol solució, òptima o no, inclourà un número de variables de valor arbitrari. L'algoritme símplex usa zero com a valor arbitrari, i el número de variables en valor zero és igual als graus de llibertat.

Les variables en valors diferents de zero seran cridades "variables bàsiques", les demés "variables no bàsiques".

Esta forma simplifica el trobar la solució factible bàsica inicial, ya que totes les variables de la forma estàndar poden ser elegides per a ser no bàsiques (zero), mentres que totes les noves variables introduïdes en la forma aumentada, seran bàsiques (diferents de zero), ya que el seu valor pot ser calculat trivialment (${𝐱}_{si}={𝐛}_j$ per a elles, ya que la matriu problema aumentada en diagonal és el seu costat dret)

En cada una de les desigualtats que es plantegen en el model matemàtic de programació llineal, es plantegen desigualtats de <, >, ≤, ≥ o =; estes desigualtats es convertixen en igualtats completant en variables de chala si es tracta de menor o igual que, o menor que; en el cas de que siga major o igual que o major que, es completa en variables d'excedent, estes en signe negatiu ya que com el seu nom ho indica, és una cantitat que està d'excedent i cal llevar per a convertir-la en igualtat; en cas es manege el =, es manegen les variables artificials.

Conceptes bàsics

Forma estàndar

És l'igualació de les restriccions del model plantejat, aixina com l'aument de variables de chala, o be la resta de variables d'excés.

Erro al crear miniatura:

Forma canònica

En el método símplex és de prou utilitat la forma canònica, especialment per a explorar la relació de dualitat, a on un problema de programació llineal es troba en la forma canònica si es complixen les següents condicions:

Per al cas de la forma canònica d'maximización:

• La funció objectiu deu ser d'maximización
• Les variables de decisió no negatives.
• Les restriccions són del tipo $\le$.

Per al cas de la forma canònica de la dieta:

• La funció objectiu és minimisada.
• Les restriccions són de tipo $\ge$.
• Les variables de decisió són no negatives.

Eixemple:

Forma Canònica d'Maximización

$$\{\begin{array}{cc}\text{Maximizar}& z=2x_1+3x_2+5x_3\\ \text{Sujeto a:}\\ & 2x_1+3x_2+8x_3\le 8\\ & 5x_1+2x_2+4x_3\le 9\\ & x_1,x_2,x_3\ge 0\end{array}$$

Forma Canònica de la dieta

$$\{\begin{array}{cc}\text{Minimizar}& z=-x_1-3x_2\\ \text{Sujeto a:}\\ & x_1-x_2\ge 6\\ & -x_1+2x_2\ge 8\\ & x_1,x_2\ge 0\end{array}$$

Model ampliat

Quan s'introduïx en cada restricció una variable artificial que no continga una variable de chala.

Erro al crear miniatura:

Eixemple d'un Model d'Maximisació en la seua Forma Ampliada

Variables d'entrada

Estes solen trobar-se en un criteri que es coneix com a “Condició de optimalidad”, en un model, ya siga d'maximisació o minimisació, i es referix a la variable no bàsica en el rengló “z” en el coeficient més negatiu, si es tracta d'una maximización, o el coeficient més positiu, si es tracta d'una minimisació, la qual, en la taula de solució anterior, a excepció de la primera taula, esta variable era una variable bàsica.

Variables d'eixida

Esta variable és un punt extrem que es troba en un criteri conegut com a “condició de factibilidad”, en un model, ya siga d'optimisació o minimisació, i es referix a la variable bàsica associada en la mínima raó no negativa en el coeficient més negatiu, si es tracta d'una maximización, o el coeficient més positiu, si es tracta d'una minimisació, la qual, en la taula de solució següent, passarà a ser variable no bàsica.

	Variables bàsiques	Variables no bàsiques	Variable d'entrada	Variable d'eixida
A	X3, X4, X5, X6	X1, X2	X1	X2
B	X3, X4, X5, X1	X6, X2	X2	X3
C	X2, X4, X5, X1	X6, X3	X6	X4
D	X2, X6, X5, X1	X4, X3	X3	X1
I	X2, X6, X5, X3	X4, X1	X4	X2

Variable degenerada

Una variable degenerada és una variable bàsica que val zero. Gràficament açò pot ocórrer quan més de dos rectes toquen una sola intersecció en el mateix punt.

Base

Conjunt de variables bàsiques. En l'eixemple anterior, la base és {X3, X4, X5, X6}

Variable no restringida

Variable artificial

S'usa una variable artificial quan les restriccions són = i ≥ i succeïx quan l'orige no es troba dins de la regió factible, tractant de dur el model a una atra dimensió en la qual l'orige si existixca en la regió.

És aquella que pot prendre tota classe de valors positius, zero i negatius pot escriure's com la diferència de dos variables no-negatives.

Funció objectiu:

Definix l'efectivitat del model com a funció de les variables de decisió.

Solució òptima

Erro al crear miniatura:

Eixemple gràfic de la solució òptima

Sempre està associada a un punt extrem de la regió factible i satisfà totes les restriccions si s'evalua en elles aixina com és el punt que en el cas d'maximisació fa que el valor de z siga el màxim (més gran) i el cas de minimisació siga el mínim (més menut).

Solució òptima múltiple

Existixen problemes llineals que no tenen una solució òptima única, sino que al contrari, tenen un número infinit de solucions.Per a detectar una solució múltiple en la taula òptima, es deurà tindre a lo manco una variable en la seua Zj-Cj=0 no bàsica.

Vore també

• George Dantzig
• Investigació d'Operacions
• Programació llineal
• Conjectura de Hirsch