Métodos de solución mas conocidos

Solución Gráfica de Modelos Lineales con dos Variables.

Para la solución gráfica de problemas lineales con dos variables, lo que se tiene que hacer es :

Dibujar un sistema de coordenadas cartesianas en el que cada variable de decisión esté representada por un eje, con la escala de medida adecuada a su variable asociada.

1. Dibujar en el sistema de coordenadas las restricciones del problema (incluyendo las de no negatividad). Para ello, observamos que si una restricción es una inecuación, define una región que será el semi plano limitado por la línea recta que se tiene al considerar la restricción como una igualdad. Si la restricción fuera una ecuación, la región que define se dibuja como una línea recta. La intersección de todas las regiones determina la región factible o espacio de soluciones (que es un conjunto convexo). Si esta región es no vacía, ir a la fase siguiente. En otro caso, no existe solución que satisfaga (simultáneamente) todas las restricciones y el problema no tiene solución, denominándose no factible.
2. Determinar los puntos extremos (puntos que no están situados en segmentos de línea que unen otros dos puntos del conjunto convexo) de la región factible (que, como probaremos en la siguiente sección, son los candidatos a solución óptima). Evaluar la función objetivo en estos puntos y aquél o aquellos que maximicen (o minimicen) el objetivo, corresponden a las soluciones óptimas del problema.

 

Forma algebraica

Consiste, simplemente, en sustituir cada uno de los vértices de la región en la función objetivo. La soluciónoptima vendrá dada por aquel que tome el mayor (o menor) valor.

Para resolver un problema de programación lineal por métodos algebraicos, se aplica el siguiente procedimiento operativo:

• 1. Se definen las variables.
• 2. Para cada restricción existente se escribe una inecuación lineal representativa.
• 3. Se define la expresión matemática de la función objetivo.
• 4. Se construyen sistemas cuadrados de ecuaciones a partir del conjunto inicial de inecuaciones lineales. Por ejemplo, si se tuvieran cuatro inecuaciones con dos incógnitas, se podrían construir seis sistemas distintos de ecuaciones lineales (sustituyendo la desigualdad por igualdad).
• 5. Se resuelven todos estos sistemas y se anota el valor de los puntos obtenidos como solución.
• 6. Se comprueban estos puntos en cada una de las inecuaciones. Los que cumplan todas las restricciones serán los vértices de la región factible.
• 7. Se calcula el valor de la función objetivo para cada vértice.
• 8. La solución óptima será aquella para la cual la función objetivo es máxima (o mínima, según el planteamiento del problema).

Esta técnica recibe el nombre de métodode los vértices.

Sitios de interés:
Metodo analítico

Método Símplex

 El método símplex es un algoritmo.De hecho el 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 de la función objetivo en un vértice cualquiera, elmétodo consiste en buscar sucesivamente otro vértice que mejore al anterior. Labú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 Simplex se basa en la siguiente propiedad: 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.

Deberá tenerse en cuenta que este método sólotrabaja para restricciones que tengan un tipo de desigualdad "≤" y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo "≥" o "=" habrá que emplear otros métodos, siendo el más común el método de las Dos Fases.




Sitios de Interes:

MétodoSímplex

Tags: Grafico, Algebraico, Simplex