metodo simplex

Problema de Programación
Lineal

Introducción
La optimización es un enfoque que busca la mejor solución a un
problema.

Propósito:
Maximizar o minimizar una función objetivo que mide la calidad
de la solución, respetando las restricciones impuestas.
Programación lineal: Técnica para resolver problemas de
optimización modelados matemáticamente.

1

Programación Lineal
Un modelo deprogramación lineal se define generalmente como:

donde (1a) es la función objetivo, (1b), (1c) y (1d) son las
restricciones del problema, y (1e) es la restricción de no
negatividad.

Forma Canónica
La forma canónica de un problema de programación lineal es:

Todas las variables de decisión son no negativas.
Todas las restricciones son del tipo menor o igual.
La función objetivo es detipo de maximización.

2

Forma Estándar
La forma estándar de un problema de programación lineal es:

Todas las restricciones son ecuaciones excepto las de no negatividad.
Los elementos del lado derecho de cada ecuación son no negativos.
Todas las variables son no negativas.
La función objetivo es del tipo de maximización o minimización.

Ejemplo de Forma Estándar
Cambiar a formaestándar:

La forma estándar es:

3

Solución de un Problema
Solución de un problema de optimización:
Asignación de variables que optimicen la función objetivo
respetando todas las restricciones.
Espacio de soluciones: Es aquella región donde los valores de
las variables satisfacen todas las restricciones.
Método gráfico:
1.- Encontrar el espacio de soluciones.
2.- Determinar lasolución óptima entre todos los puntos factibles.

Ejemplo: Solución de un
Problema
Ejemplo: Resolver el siguiente problema

4

Ejemplo: Espacio de
Soluciones

Ejemplo: solución de un
Problema
Solución óptima: Es aquel punto del espacio de soluciones
donde la función objetivo tenga un valor máximo.
Punto Extremo: Es aquel punto donde se intercepta un
subconjunto de restricciones.
Espaciode soluciones: Es un espacio convexo.
UNA SOLUCIÓN ÓPTIMA SIEMPRE SE PRESENTA EN
UN PUNTO EXTREMO DEL ESPACIO

5

Método Simplex
Algoritmo que resuelve problemas de
programación lineal
Cada iteración resuelve un sistema de
ecuaciones
Cada iteración aplica prueba de optimalidad

Método Simplex
Busca la solución óptima en los puntos extremos de la región
factible.
Requiere que elproblema esté representado en forma estándar.
Características:
• Representación del espacio de soluciones con la forma
estándar.
• Determinación algebraica de los puntos extremos.
• Condiciones de optimalidad y factibilidad.
• Mecanismo para pasar de una solución factible a otra que
asegure la optimalidad.

6

Determinación Algebraica de
puntos Extremos
Solución básica: Es la soluciónde un sistema de ecuaciones mxn
donde n-m variables se hacen cero y se resuelve el problema.
m variables básicas
n-m variables no básicas
Un punto extremo es una solución básica de un sistema de mxn
ecuaciones simultaneas.
Soluciones básicas factibles: Respetan la no negatividad.
Soluciones básicas no factibles: No respetan la no negatividad.

Optimalidad y Factibilidad
Método simplex:Inicia en una solución básica factible y pasa a través de una
sucesión de soluciones básicas factibles, de tal manera que cada nueva solución
tenga la facultad de mejorar el valor de la función objetivo.
Condición de optimalidad: Cuando una solución en un vértice es igual o mejor
que todas las soluciones factibles en los vértices adyacentes a ella.
Condición de factibilidad: Partiendo de unasolución básica factible,
únicamente se encontrarán durante el cálculo soluciones básicas factibles.
Las variables de holgura proporcionan la primer solución básica factible,
haciendo 0 las variables originales (no básicas)
La función objetivo se trabaja como una ecuación igual a cero, y se incluye en
el proceso para asegurar la condición de optimalidad.

7

Pasar de una Solución...