minimizacion

simplex, maximizacion

Método Simplex

Introducción a la programación lineal

La programación lineal se aplica a modelos de optimización en los que las funciones objetivo y
restricción son estrictamente lineales. La técnica se aplica en una amplia variedad de casos, en
los campos de agricultura, industria, transporte, economía, salud, ciencias sociales y de la conducta,
y militar. También produce algoritmos eficientes de cómputo para problemas con miles
de restricciones y variables. En realidad, debido a su tremenda eficiencia de cálculo, la programación
lineal forma la columna vertebral de los algoritmos de solución para otros modelos de
investigación de operaciones, como las programaciones entera, estocástica y no lineal.
Este capítulo comienza con el caso de un modelo de dos variables, y presenta su solución
gráfica. Esta solución gráfica permite tener una perspectiva del desarrollo del método
símplex, técnica algebraica general (véase el capítulo 3). También presenta ideas concretas
para el desarrollo y la interpretación de análisis de sensibilidad en programación lineal. El capítulo
termina con la formulación y la interpretación de la solución de varias aplicaciones realistas.

El método símplex
 
El método gráfico indica que la solución óptima de un programa lineal siempre
está asociada con un punto esquina del espacio de soluciones. Este resultado es la clave del
método símplex algebraico y general para resolver cualquier modelo de programación lineal.
La transición de la solución del punto esquina geométrico hasta el método símplex implica
un procedimiento de cómputo que determina en forma algebraica los puntos esquina. Esto
se logra convirtiendo primero a todas las restricciones de desigualdad en ecuaciones, para
después manipular esas ecuaciones en una forma sistemática.
Una propiedad general del método símplex es que resuelve la programación lineal en
iteraciones. Cada iteración desplaza la solución a un nuevo punto esquina que tiene potencial
de mejorar el valor de la función objetivo. El proceso termina cuando ya no se pueden obtener
mejoras.
El método símplex implica cálculos tediosos y voluminosos, lo que hace que la computadora
sea una herramienta esencial para resolver los problemas de programación lineal. Por
consiguiente, las reglas computacionales del método símplex se adaptan para facilitar el cálculo
automático.

Las primeras actividades formales de investigación de operaciones se dieron en Inglaterra durante
la Segunda Guerra Mundial, cuando se encomendó a un equipo de científicos ingleses la
toma de decisiones acerca de la mejor utilización de materiales bélicos. Al término de la guerra,
las ideas formuladas en operaciones militares fueron adaptadas para mejorar la eficiencia
y la productividad en el sector civil. Hoy en día, la investigación de operaciones es una herramienta
dominante e indispensable para tomar decisiones.
Un elemento principal de la investigación de operaciones es el modelado matemático.
Aunque la solución del modelo matemático establece una base para tomar una decisión, se
deben tener en cuenta factores intangibles o no cuantificables, por ejemplo el comportamiento
humano, para poder llegar a una decisión final. 

  
                    1 Toma de decisiones.
1.1 Ambientes y criterios para la toma de
decisiones.
1.2 Toma de decisiones bajo modelos de
certidumbre, incertidumbre y riesgo.
1.3 Enfoque cuantitativo en la toma de
decisiones.
1.4 Teoría de la utilidad.
1.5 La obtención de datos para la toma de
decisiones.
1.6 Árboles de decisión.





Criterio del valor esperado
El criterio del valor esperado busca la maximización de la utilidad (promedio) esperada o la
minimización del costo esperado. En los datos del problema se supone que la retribución (o el
costo) asociada con cada alternativa de decisión es probabilística.

Análisis con árbol de decisión. En el ejemplo que sigue se describen casos sencillos de decisión
con una cantidad finita de alternativas de decisión con matrices explícitas de retribución.

                      2 Programación lineal.
2.1 Formulación y aplicación de modelos de
programación lineal.
2.2 Método gráfico.
2.3 Método simplex .
2.3.1 Método algebraico.
2.3.2 La tabla simples.
2.4 Método dual.
2.5 Método dual-simplex.
2.6 Análisis de resultados.

La programación lineal se aplica a modelos de optimización en los que las funciones objetivo y
restricción son estrictamente lineales. La técnica se aplica en una amplia variedad de casos, en
los campos de agricultura, industria, transporte, economía, salud, ciencias sociales y de la conducta,
y militar. También produce algoritmos eficientes de cómputo para problemas con miles
de restricciones y variables. En realidad, debido a su tremenda eficiencia de cálculo, la programación
lineal forma la columna vertebral de los algoritmos de solución para otros modelos de
investigación de operaciones, como las programaciones entera, estocástica y no lineal.
Este capítulo comienza con el caso de un modelo de dos variables, y presenta su solución
gráfica. Esta solución gráfica permite tener una perspectiva del desarrollo del método
símplex, técnica algebraica general. También presenta ideas concretas
para el desarrollo y la interpretación de análisis de sensibilidad en programación lineal. El capítulo
termina con la formulación y la interpretación de la solución de varias aplicaciones realistas.

MODELO DE PROGRAMACIÓN LINEAL CON DOS VARIABLES
Esta sección explicará la solución gráfica de una programación lineal con dos variables. Aunque
en la práctica casi no existen problemas con dos variables, la presentación aportará ideas concretas
para el desarrollo del algoritmo de solución general.

El modelo de programación lineal, como en cualquier modelo de investigación de operaciones,
tiene tres componentes básicos.
1. Las variables de decisión que se trata de determinar.
2. El objetivo (la meta) que se trata de optimizar.
3. Las restricciones que se deben satisfacer.
La definición correcta de las variables de decisión es un primer paso esencial en el desarrollo
del modelo. Una vez hecha, la tarea de construir la función objetivo y las restricciones se hace
en forma más directa.
                    3 Asignación y transporte.
3.1 Método de Esquina Noroeste.
3.2 Método de Costo Mínimo.
3.3 Método de Aproximación de Vogel.
3.4 Método de Asignación.