El Método Simplex

Unidad II
El Método Simplex

2.1 Solución Grafica De Un Problema Lineal.
2.2 Teoría Del Método Simplex
2.3 Forma Tabular Del Método Simplex
2.4 Método De Dos Fases
2.5 El Método Simplex Revisado
2.6 Casos Especiales

El Método Simplex
El método del simplex fue creado en 1947 por el matemático George Dantzig.
El método del simplex se utiliza, sobre todo, para resolver problemas deprogramación lineal en los que intervienen tres o más variables.
El álgebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituyen la base del método simplex.
Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.
Partiendo del valor dela función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.
El método del simplex se basa en la siguientepropiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.

2.1. SOLUCIÓN GRÁFICA DE UN PROBLEMA LINEAL
Muchos problemas de administración y economía están relacionados con la optimización (maximización o minimización) de una función sujeta a un sistema de igualdades o desigualdades.
La función poroptimizar es la función objetivo. Las funciones de ganancia y de costo son ejemplos de funciones objetivo. El sistema de igualdades o desigualdades a las que está sujeta la función objetivo reflejan las restricciones (por ejemplo, las limitaciones sobre recursos como materiales y mano de obra) impuestas a la solución (o soluciones) del problema.
Los problemas de esta naturaleza se llaman problemasde programación matemática. En particular, aquellas donde la función objetivo y las restricciones se expresan como ecuaciones o desigualdades lineales se llaman problemas de programación lineal.
Un problema de programación lineal consta de una función objetivo lineal por maximizar o minimizar, sujeta a ciertas restricciones en la forma de igualdades o desigualdades lineales.

Solución GráficaLos problemas de programación lineal en dos variables tienen interpretaciones geométricas relativamente sencillas; por ejemplo, el sistema de restricciones lineales asociado con un problema de programación lineal bidimensional- si no es inconsistente- define una región plana cuya frontera está formada por segmentos de recta o semirrectas, por lo tanto es posible analizar tales problemas en formagráfica.
2.2 Teoría Del Método Simplex.
El método S implex es un pr ocedimiento iterativo q ue per mite i r m ejorando l a solución a cada paso. El proceso concluye cuando no es posible seguir mejorando
más dicha solución.
El método g ráfico m uestra q ue l a s olución ó ptima d e P rogramación Lineal
siempre está as ociada c on un punto de es quina ( también c onocidomatemáticamente c omo punto e xtremo) del espacio d e l a s olución. E ste
resultado es la idea clave para el desarrollo del método simplex algebraico general
para resolver cualquier modelo de Programación Lineal.
La t ransición d el punto ex tremo geométrico (o es quina) de l a s olución al
método s implex r adica en i dentificar al gebraicamente l os puntos extremos. P ara
lograr es ta m eta,pr imero c onvertimos el m odelo a l a forma e stándar d e P L,
utilizando variables de holgura o de s uperávit, par a c onvertir las r estricciones de
desigualdad en ecuaciones.
El interés en la forma estándar de PL, se basa en las soluciones básicas de
las ec uaciones l ineales s imultáneas. E sta s olución bás ica ( algebraica) d efine
completamente t odos l os pu ntos ex...