I. Definicin general de mtodos simplex.
El mtodo Simplex es un procedimiento general para resolver problemas de programacin lineal. Desarrollado
por George Dantzig en 1947, est comprobada su extraordinaria eficiencia, y se usa en forma rutinaria para
resolver problemas grandes en computadoras actuales. Tambin se usan extensiones y variaciones del mtodo
Simplex para realizar anlisis pos ptimo (que incluye el anlisis de sensibilidad) sobre el modelo.
El mtodo Simplex es un procedimiento algebraico, Sin embargo, sus conceptos fundamentales son
geomtricos, por lo que la comprensin de estos conceptos geomtricos nos proporciona una fuerte intuicin
sobre como opera el mtodo Simplex y porque es tan eficiente.
Este mtodo se emplea con un proceso interactivo, o sea, que se usa sucesivamente la misma rutina bsica de
clculo, lo que da por resultado una serie de soluciones sucesivas hasta que se encuentra la mejor. Una
caracterstica bsica del mtodo Simplex es que la ltima solucin produce una contribucin tan grande o mayor
que la solucin previa en un problema de maximizacin, lo que da la seguridad de llegar finalmente a la
respuesta ptima.
PARA QU SIRVE EL MTODO SIMPLEX?
El mtodo Simplex nos sirve para solucionar problemas en donde debemos de optimizar nuestros recursos de la
manera ms eficiente. Se utiliza para resolver problemas de programacin lineal en los que intervienen tres o
ms variables.
IMPORTANCIA DEL MTODO SIMPLEX
El mtodo simplex permite localizar de manera eficiente la ptima solucin entre los puntos extremos de un
problema de programacin lineal. La gran virtud del mtodo simplex es su sencillez, mtodo muy prctico, ya
que solo trabaja con los coeficientes de la funcin objetivo y de las restricciones.
Es muy importante en el rea empresarial ya que lo utilizan para obtener solucin a los problemas de las
empresas en cuanto a inventario, ganancias y prdidas. Este mtodo permite visualizar cuanto se debe vender,
cuanto se debe producir o cuanto se debe comprar segn sea el caso para que la empresa obtenga las ganancias
optimas y suficientes para competir en el mercado.
En Base a esta importancia El mtodo simplex ha tenido diversas aplicaciones en las industrias especialmente
en el rea de transporte, en la parte de inventarios y en lo empresarial en general.
VENTAJAS DEL MTODO SIMPLEX
1) Es un Mtodo heurstico. Se basa en consideraciones geomtricas y no requiere el uso de derivadas de la
funcin objetivo.
2) Es de gran eficiencia incluso para ajustar gran nmero de parmetros.
3) Se puede usar con funciones objetivo muy sinuosas pues en las primeras iteraciones busca el mnimo ms
ampliamente y evita caer en mnimos locales fcilmente.
4) Es fcil implementar y usar, y sin embargo tiene una alta eficacia.
DESVENTAJAS DEL MTODO SIMPLEX
Converge ms lentamente que otros mtodos, pues requiere ms nmero de iteraciones.
En el caso de que la funcin tenga todas sus variables bsicas positivas, y adems las restricciones sean de
desigualdad "", al hacer el cambio se quedan negativas y en la fila del valor de la funcin objetivo se quedan
positivos, por lo que se cumple la condicin de parada, y por defecto el valor ptimo que se obtendra es 0.
VARIABLES DE HOLGURA Y EXCESO
Aplica para las restricciones del tipo ( y ), donde el lado derecho de la desigualdad representa el limite sobre
la disponibilidad de un recurso y el lado izquierdo representa la utilizacin de ese recurso limitado que hacen las
variables del modelo. Esto quiere decir que una holgura representa la cantidad disponible del recurso que
excede a la utilizacin que se le da. En la conversin de este tipo de desigualdad se aade una variable de ajuste
(Si) para convertirla en igualdad. Por ejemplo, tenemos la siguiente restriccin: 3X1 + 2X2 6, su equivalente
seria, 3X1 + 2X2 + S1 = 6.
II. Tcnicas de variables artificiales o tcnica M.
Una variable artificial es un truco matemtico para convertir inecuaciones ">=" en ecuaciones, o cuando
aparecen igualdades en el problema original, la caracterstica principal de estas variables es que no deben
formar parte de la solucin, dado que no representan recursos. El objetivo fundamental de estas variables es la
formacin de la matriz identidad.
Estas variables se representa por la letra "A", siempre se suman a las restricciones, su coeficiente es M (por esto
se le denomina Mtodo de la M grande, donde M significa un nmero demasiado grande muy poco atractivo
para la funcin objetivo), y el signo en la funcin objetivo va en contra del sentido de la misma, es decir, en
problemas de Maximizacin su signo es menos (-) y en problemas de Minimizacin su signo es (+), repetimos
con el objetivo de que su valor en la solucin sea cero (0).
A modo general, el mtodo Simplex consta de los pasos siguientes:
Determinar una solucin bsica factible inicial.
Definir una variable de entrada empleando la condicin de factibilidad. El algoritmo se detiene
cuando ya no hay una variable de entrada.
Seleccionar una variable de salida empleando la condicin de factibilidad.
Determinar las nuevas soluciones bsicas factibles aplicando los clculos apropiados a travs de la
metodologa Gauss-Jordn.
En el contexto de la aplicacin del Mtodo Simplex no siempre es inmediata la obtencin de una solucin
bsica factible inicial, en las variables originales del modelo. Para conseguir esto existen varios procedimientos
como son el Mtodo Simplex de 2 Fases y el Mtodo de la M Grande (o Gran M) el cual abordaremos en este
artculo. Para ello consideremos el siguiente modelo de Programacin Lineal en 2 variables:
A continuacin agregamos las variables no negativas (holgura restriccin 1), (auxiliar restriccin 2),
(exceso restriccin 3) y (auxiliar restriccin 3). El modelo ahora es:
Donde el parmetro M es una constante positiva suficientemente grande para representar una penalizacin
adecuada en la funcin objetivo. La tabla inicial del mtodo est dada por:
Antes de continuar con las iteraciones se debe procurar que el costo reducido de las variables y sean ceros.
Para ello multiplicamos por -M la fila 2 y la fila 3 y luego sumamos a la fila 4, obteniendo lo siguiente:
Ahora debemos seleccionar que variable no bsica ingresa a la base. El menor costo reducido corresponde a la
variable en consecuencia dicha variable ingresa a la base. Luego calculamos el mnimo cociente en dicha
columna: , el cual se alcanza en la fila 1, por tanto la variable deja la base. Se
actualiza la tabla:
Siguiendo con las iteraciones ahora la variable entra a la base. El criterio de factibilidad indica
que: la variable abandona la base (el pivote se encuentra en la fila 3). Actualizamos
la tabla:
Una nueva iteracin indica que ingresa a la base. El mnimo cociente en la respectiva columna
es: (recordar que se omiten denominadores menores a cero). Ahora el pivote se
encuentra en la fila 2 y en consecuencia deja la base. Se actualiza la tabla:
Se ha alcanzado la solucin ptima con y . Notar que las variables auxiliares (r1 y r2) son
no bsicas en el ptimo. El valor ptimo es 21/4 (notar que el signo esta cambiado).
Para una mejor comprensin de los resultados alcanzados a continuacin se presenta la resolucin grfica del
problema haciendo uso del software Geogebra. El dominio de soluciones factibles corresponde a la recta que
une los vrtices A y B. Adicionalmente se muestra la curva de nivel que pasa por la solucin ptima (vrtice B).
Tericamente se espera que en la aplicacin del Mtodo de la M Grande las variables auxiliares sean no bsicas
en el ptimo. Si el modelo de Programacin Lineal es infactible (es decir, si las restricciones no son
consistentes), la iteracin del Mtodo Simplex final incluir al menos una variable artificial como bsica.
Adicionalmente la aplicacin de la tcnica de la M Grande implica tericamente que M tiende a infinito. Sin
embargo al usar la computadora M debe ser finito, pero suficientemente grande. En especfico M debe ser lo
bastante grande como para funcionar como penalizacin, al mismo tiempo no debe ser tan grande como para
perjudicar la exactitud de los clculos del Mtodo Simplex, al manipular una mezcla de nmeros muy grandes y
muy pequeos.
III. Dualidad
El concepto de dualidad desempea importantes papeles dentro de la programacin lineal (tambin en la no
lineal), tanto desde un punto de vista terico como prctico. Todo programa lineal lleva asociado otro programa
lineal conocido como su programa dual; el programa inicial se conoce tambin como programa primal. Para
comprender el concepto de dualidad y sus posibles interpretaciones, pueden analizarse los siguientes ejemplos.
Ejemplo primal:
Una granja utiliza dos preparados alimenticios (P1 y P2) para la cra del ganado. El coste por kilogramo de esos
dos preparados es de 2 unidades monetarias y 3 unidades monetarias respectivamente. Por otra parte, los aportes
vitamnicos de cada kilo de los preparados se expresan en la siguiente tabla:
Kg P1 Kg P2
Unidades de Vitamina
5 3
A
Unidades de Vitamina
1.5 3
B
Unidades de Vitamina
1 1.3
C
Los expertos en nutricin animal recomiendan que cada animal reciba al menos las siguientes unidades diarias
de cada una de las vitaminas:
Unidades diarias de Vitamina
20
A
Unidades diarias de Vitamina
15
B
Unidades diarias de Vitamina
8
C
El objetivo de los responsables de la granja es decidir las cantidades diarias de cada uno de los dos preparados
que deben suministrarse a cada animal, de forma que, por un lado se cumplan las recomendaciones de los
dietistas, y por otro se minimicen los costes de alimentacin del ganado. Dicho objetivo supone resolver el
siguiente programa lineal:
Min 2x1+3x2
5x1+3x2 >= 20
1.5x1+3x2 >= 15
X1+1.3x2 >= 8
X1, x2 >= 0
Donde x1 y x2 representan las cantidades diarias, en kilos, suministradas a cada animal de los
preparados P1 y P2 respectivamente.
El mnimo del problema anterior se alcanza sobre el punto:
X1 = 4.286 x2 = 2.857
Siendo por tanto el coste mnimo de 17.143 unidades monetarias por animal y da.
Ejemplo dual:
Pinsese ahora en una empresa de productos alimenticios para ganado, que desea suministrar a la granja del
ejemplo anterior tres tipos de pastillas vitamnicas. Esta empresa debe convencer a los responsables de la granja
para que aporten las vitaminas que el ganado necesita mediante sus pastillas, y no mediante los preparados que
hasta ahora utilizaban. Para ello el precio de venta de las pastillas debe resultar competitivo con respecto a los
preparados P1 y P2.
Sean z1, z2 y z3 los precios por unidad de las vitaminas A, B y C respectivamente. El objetivo de la empresa es
fijar unos precios que consigan maximizar sus beneficios pero que adems resulten atractivos para los
responsables de la granja.
Cada kilogramo del preparado P1 aportaba 5 unidades de vitamina A, 1.5 unidades de vitamina B y 1
unidad de vitamina C. El precio que debera pagar la granja por conseguir esas mismas cantidades de
vitaminas en pastillas sera: 5z1+1.5z2+z3. A la granja no le resultaran rentables las pastillas a no ser
que 5z1+1.5z2+z3 <= 2
De la misma forma, otra restriccin que debera plantearse la empresa es:3z1+3z2+1.3z3 <= 2
Por supuesto, los precios de las pastillas vitamnicas deben ser positivos, por tanto se tienen adems las
restricciones z1,z2,z3 >= 0
Suponiendo que la granja se decida por utilizar las pastillas, comprarn justamente las necesarias para aportar
las necesidades mnimas del ganado de cada una de las vitaminas. Es decir, por cada animal y da se compraran
20 unidades de vitamina A, 15 de vitamina B y 8 de vitamina C. Por tanto los ingresos de la empresa por la
venta de las pastillas seran de
V (z1, z2, z3) = 20z1+15z2+8z3
Por animal y da.
Para establecer los precios, la empresa debera plantearse el programa lineal
Max 20z1+15z2+8z3
5z1+1.5z2+z3 <= 2
3z1+3z2+1.3z3 <= 3
z1, z2, z3 >= 0
La solucin de dicho programa se alcanza sobre el punto
z1 = 0
z2 = 0.381
z3 = 1.428
Siendo entonces el valor mximo V (0,0.381, 1.428) = 17.143 unidades monetarias. Observar como uno de los
precios ha resultado ser nulo. Esto significa que la granja con los preparados P1 y P2solo debe preocuparse de
aportar al ganado las unidades necesarias de vitaminas B y C, ya que con ello conseguira tambin la aportacin
necesaria de vitamina A. Es la razn por la cual la granja no necesita comprar unidades adicionales de vitamina
A.
En estos dos ejemplos se observa una relacin interesante entre los problemas primal y dual. Como puede
observarse:
Uno de ellos es de minimizacin, el otro en cambio es de maximizacin.
Los coeficientes en la funcin objetivo y los elementos de la derecha de las restricciones, intercambian
su papel.
La matriz de coeficientes en las restricciones del problema dual es la traspuesta de la del problema
primal.
Las restricciones del problema primal son de tipo >=, en cambio en el dual son de tipo<=.
Cada restriccin en el problema primal se corresponde con una variable en el dual.
El punto ptimo del programa dual se corresponde con las variables duales (multiplicadores de Kuhn-
Tucker) del programa primal.
Otro aspecto importante es que, aunque el punto ptimo es diferente, los valores ptimos de los dos
problemas son los mismos.
La resolucin del programa dual puede interpretarse como la asignacin a cada recurso de un precio o valor, que
coincide con el incremento que provoca en el valor ptimo del problema primal un aumento de una unidad en el
recurso.
La construccin realizada en los ejemplos anteriores puede generalizarse para cualquier programa lineal:
Definicin:
Dado un programa lineal de la forma
Min cx
Ax >= b
x >= 0
su programa dual es
max b'z
A'z <= c'
z >= 0
Donde A', b' y c' son los traspuestos de A, b y c respectivamente. En esta definicin no es necesario que todos
los elementos del vector b sean mayores o iguales que cero.
Pero no solamente pueden construirse los programas duales para programas de la forma anterior; en general se
puede para cualquier programa lineal (tambin hay una teora de dualidad para programas no lineales), pero
teniendo en cuenta lo siguiente:
Una restriccin de igualdad en el programa primal hace que la correspondiente variable dual pueda tener
cualquier signo.
En cambio, una restriccin de desigualdad del tipo >= en el primal implica que la variable dual sea
mayor o igual que cero.
Si las variables del primal son mayores o iguales que cero, las restricciones del dual son del tipo <=.
Cuando las variables del primal no estn sometidas a ninguna limitacin sobre su signo, las restricciones
del dual son de igualdad.
Ejemplo:
Programa primal Programa dual
max 3z1+2z2
min x1+x2-x3
2z1+z2 = 1
2x1+x2 >= 3
z1 = 1
x1-x3 = 2
-z2 <= -1
x3 >= 0
z1 >= 0
La importancia del programa dual queda de manifiesto en el siguiente resultado.
Teorema fundamental de dualidad:
Dado un programa P y su dual D, se cumple necesariamente una de las siguientes afirmaciones:
Los dos programas tienen soluciones ptimas y los valores de sus respectivas funciones objetivo en el
ptimo coinciden.
Uno de los programas tiene ptimo no acotado y el otro no tiene ninguna solucin factible.
Los dos programas son infactible (no tienen soluciones factibles).
A partir de este teorema se puede deducir el valor ptimo de un programa lineal, o si dicho programa es factible,
analizando la forma de su programa dual. En algunos casos el estudio del programa dual puede resultar ms
sencillo que el del primal.
Bibliografa
Charles A. G y Hugh J. W. (2005) Mtodos Cuantitativos para la toma de decisiones en administracin
en 2 partes. Editorial Universitaria. La Habana.
Colectivo de Autores (2013). Investigacin de Operaciones. Editorial Universitaria. La Habana
Colectivo de Autores (2013). Investigacin de Operaciones. Modelos y Mtodos Determinsticos.
Editorial Universitaria. La Habana
Eppen, G. D (2000). Investigacin de Operaciones en la Ciencia Administrativa. Creacin de modelos
de decisiones con hojas de clculo electrnicas. Prentice- Hall. Mxico
Conclusin
Como conclusin tenemos que la programacin lineal es una tcnica poderosa para tratar problemas de
asignacin de recursos escasos entre actividades que compiten, al igual que otros problemas cuya formulacin
matemtica es parecida. Se ha convertido en una herramienta estndar de gran importancia para muchas
organizaciones industriales y de negocios. An ms, casi cualquier organizacin social tiene el problema de
asignar recursos en algn contexto y cada vez mayor el reconocimiento de la aplicabilidad tan amplia de esta
tcnica.
Sin embargo, no todos los problemas de asignacin de recursos limitados se pueden formular de manera que se
ajusten a un modelo de programacin lineal, ni siquiera como una aproximacin razonable. Cuando no se
cumplen una o ms de las suposiciones de programacin lineal, tal vez sea posible aplicar otro tipo de modelos
matemticos, por ejemplo, los modelos de programacin entera o de programacin no lineal.
UNIVERSIDAD CENTRAL DE NICARAGUA
UCN- Jinotepe
Facultad de Ciencias Econmicas
Asignatura: Toma de decisiones.
Carrera: Administracin de Empresas.
Temas:
Definicin general de mtodos simplex.
Tcnicas de variables artificiales o tcnica M.
Dualidad.
Alumno (a): Rina Marcela Cerda Ruiz.
Jinotepe, 14 de Mayo 2017
