Unidad: MODELAMIENTO MATEMÁTICO

Capitulo y Tema: I. Retroalimentación. Tema 1. Programación Lineal

Actividad (Número y nombre): Ensayo: “Concepto de Programación Lineal, Método Grafico y Método Simplex”.

Módulo: Noveno “B”

Nombre (s): JENNY PAULINA IMACAÑA FERNANDEZ

Profesor: LUIS ANTONIO CHAMBA ERAS

Fecha en la cual el profesor encarga la actividad: Mi 13/Sep/2010

Fecha en la cual el profesor recibe la actividad: Mi 20/Oct/2010

Bibliografía: http://www.fred.ifas.ufl.edu/courses/AEB5516/Lectures/blending.doc http://dsc.gsu.edu/dscthw/Optimize/LP.PDF Ángel A. Javier Faulin. Dualidad en Programación Lineal. http://www.programacionlineal.net/ http://www.phpsimplex.com/teoria_metodo_simplex.htm http://www.uoc.edu/in3/emath/docs/Aplicaciones_PL.pdf

INTRODUCCIÓN: La Programación Lineal Es importante conocer la forma de actuación particular de los algoritmos que resuelven programas lineales. De entre todos los algoritmos destaca por su importancia histórica y práctica el método simplex. Dicho método fue desarrollado por Dantzig en 1947, alcanzando un éxito inusitado en las décadas posteriores con el desarrollo de los computadores. El conocimiento básico de dicho método ayuda a la comprensión de las diferentes formas de resolución de programas lineales. Dicho método puede ser estudiado en alguno de los manuales que se presentan a continuación: Hillier y Liebermann (2001) (Capítulos 4 y 5) o bien Winston (1994) (Capítulos 3 y 4). Por otra parte, el estudio de aplicaciones de la Programación Lineal es exhaustivo en los textos de Hillier, Hillier y Liebermann (2000); Eppen et al.(1998); o bien de Anderson, Sweeney y Williams (2001). El Método Gráfico se utiliza para la solución de problemas de PL, representando geométricamente a las restricciones, condiciones técnicas y el objetivo. El modelo se puede resolver en forma gráfica si sólo tiene dos variables. Para modelos con tres o más variables, el método gráfico es impráctico o imposible. Cuando los ejes son relacionados con las variables del problema, el método es llamado método gráfico en actividad. Cuando se relacionan las restricciones tecnológicas se denomina método gráfico en recursos. 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, 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 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. OBJETIVO: La Programación Lineal

Fijar los requerimientos para establecer un modelo de programación lineal. Representación gráfica de un modelo de programación lineal. Obtención de niveles óptimos de una función lineal, cuyas variables se encuentran sujetas

a una serie de condiciones restrictivas, expresadas bajo forma de inecuaciones lineales, es también una forma de aplicar modelos de optimización para empresas netamente productivas.

Conocimiento detallado de la Programación Lineal en el mundo real. Conocimiento detallado de los principales problemas que resuelve la Programación Lineal.

El Método Gráfico Resolución del problema por medio de una ayuda visual para comprender muchos de los

conceptos y términos que se utilizan y formalizan con métodos de solución más sofisticado El Método Simplex

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.

RESULTADOS: La Programación Lineal Un modelo de programación lineal busca maximizar o minimizar una función lineal, sujeta a un conjunto de restricciones lineales. Un modelo de programación lineal está compuesto de lo siguiente:

Un conjunto de variables de decisión Una función objetivo Un conjunto de restricciones

La importancia de la programación lineal no solo radica en el procedimiento matemático, sino en la herramienta financiera que nos puede brindar como soporte para la toma de decisiones en cualquier organización, ya que permite la asignación eficiente de recursos escasos (limitados).

Ventajas del modelo de programación lineal:

Obtención de una solución óptima única. Obtención de soluciones alternativas Modelos no acotados. Modelo no factibles.

Construcción de los Modelos de Programación Lineal De forma obligatoria se deben cumplir los siguientes requerimientos para construir un modelo de Programación Lineal. Requerimiento 1. Función objetivo. (F.O). Debe haber un objetivo (o meta o blanco) que la optimización desea alcanzar. Requerimiento 2. Restricciones y decisiones. Debe haber cursos o alternativas de acción o decisiones, uno de los cuáles permite alcanzar el objetivo. Requerimiento 3. La F.O y las restricciones son lineales. Deben utilizarse solamente ecuaciones lineales o desigualdades lineales. Modelo standard de Programación Lineal Optimizar Z = C1X1+ C1X2 +….+ Cn Xn). Función objetivo. Sujeta a a11X1+ a11X2 +…..+ a1nXn) £ b1 a21X1+ a21X2 +…..+ a2nXn) £ b1 Restricciones am1X1+ am1X2 +…..+ amnXn) £ bm Debiendo ser X1 ³ 0, X2 ³ 0, ….. Xn ³ 0

Donde : Xj : variables de decisión, j = 1,2.., n. n : número de variables. m : número de restricciones. aij , bi , cj constantes, i = 1,2.., m. Pasos para la construcción del modelo

Definir las variables de decisión. Definir el objetivo o meta en términos de las variables de decisión. Definir las restricciones. Restringir todas las variables para que sean no negativas.

El Método Gráfico

Cuando los ejes son relacionados con las variables del problema, el método es llamado método gráfico en actividad.

Cuando se relacionan las restricciones tecnológicas se denomina método gráfico en recursos.

Los pasos necesarios para realizar el método son nueve: 1. graficar las soluciones factibles, o el espacio de soluciones (factible), que satisfagan todas las restricciones en forma simultánea. 2. Las restricciones de no negatividad Xi>= 0 confían todos los valores posibles. 3. El espacio encerrado por las restricciones restantes se determinan sustituyendo en primer término <= por (=) para cada restricción, con lo cual se produce la ecuación de una línea recta. 4. trazar cada línea recta en el plano y la región en cual se encuentra cada restricción cuando se considera la desigualdad lo indica la dirección de la flecha situada sobre la línea recta asociada. 5. Cada punto contenido o situado en la frontera del espacio de soluciones satisfacen todas las restricciones y por consiguiente, representa un punto factible. 6. Aunque hay un número infinito de puntos factibles en el espacio de soluciones, la solución óptima puede determinarse al observar la dirección en la cual aumenta la función objetivo. 7. Las líneas paralelas que representan la función objetivo se trazan mediante la asignación de valores arbitrarios a fin de determinar la pendiente y la dirección en la cual crece o decrece el valor de la función objetivo. Ejemplo. Maximizar Z = 3X1 + 2X2 Restricciones : X1 + 2X2 <=6 (1) 2X1 + X2 <=8 (2) -X1 + X2 <=1 (3) X2 <= 2 (4) X1 >= 0 (5) X2 >= 0 (6) Convirtiendo las restricciones a igualdad y representándolas gráficamente se tiene: X1 + 2X2 = 6 (1) 2X1 + X2 = 8 (2) -X1 + X2 = 1 (3) X2 = 2 (4) X1 = 0 (5) X2 = 0 (6)

El Método Simplex Es un procedimiento iterativo que progresivamente permite obtener una solución óptima para los problemas de programación lineal. Procedimiento general del simplex 1. Establézcase la tabla inicial de simples. Formular la función objetivo y las restricciones e

introducir las variables de decisión, variable en la solución, valor en solución (LD), C (contribución de la variable), Z (costo de introducir la variable), C – Z (contribución neta de la variable).

2. Selecciónese la columna pivote. Ésta es la columna con el número positivo más grande en el renglón inferior (C - Z). Esta se convierte en la nueva variable de la solución.

3. Selecciónese el renglón pivote. Éste es el renglón con la razón más pequeña del valor LD dividido por el valor de la columna pivote. Úsense sólo números positivos. Esto identifica la variable que deja la solución.

4. Enciérrese en un círculo el elemento pivote. Ésta es la intersección del renglón y la columna pivotes.

5. Conviértase al elemento pivote en un 1. Hágase esto dividiendo cada valor del renglón pivote entre el valor pivote. Métase este renglón en una tabla nueva.

6. Genérense los demás renglones de la nueva tabla con ceros en la columna pivote. Esto se hace multiplicando el nuevo renglón (del paso 5) por el negativo del elemento en la columna pivote. El resultado será sumado al antiguo renglón. Introdúzcase este renglón revisado en la nueva tabla, y continúese este procedimiento en cada renglón de la sección central de la tabla.

7. Prueba de optimización. Calcúlense los valores de Z y C – Z. Los valores de Z de cada columna son (elementos de la columna) ( C ). Si todos los valores de C – Z son ≤ 0, la solución es óptima. Léanse los valores de las variables en la solución de la columna de LD y el valor de la función objetivo del renglón de Z en la columna de LD. Si la solución no es óptima, regrese al paso 2.

El método requiere que las restricciones sean ecuaciones en lugar de inecuaciones, lo cual se logra añadiendo variables de holgura a cada inecuación del modelo, variables que nunca pueden ser negativas y tienen coeficiente 0 en la función objetivo. Por ejemplo tenemos: Z – 6X1 – 4X2 = 0 2X1 + 2X2 + s1 = 160 X1 + 2X2 + s2 = 120 4X1 + 2X2 + s3 = 280 Todas las variables son no negativas. La solución básica inicial se obtiene seleccionando las variables de holgura como variables básicas, resultando conveniente disponer los valores como se muestran en la tabla siguiente:

i VB Z X1 X2 S1 S2 S3 Bi

1 Z 1 - 6 -4 0 0 0 0

2 S1 0 2 2 1 0 0 160

3 S2 0 1 2 0 1 0 120

4 S3 0 4 2 0 0 1 280

Cada ecuación debe tener una única variable básica(VB), con el coeficiente unidad en la fila correspondiente.

La solución básica debe ser examinada para observar si puede ser mejorada. La presencia de coeficientes negativos en la FO indica que la solución básica puede ser mejorada, pues el valor de Z se incrementará. Cuando no hay coeficientes negativos, significa que la solución es óptima. Para encontrar una solución mejorada es necesario:

Elegir la variable que entra como la de mayor coeficiente negativo (X1) Elegir la variable que sale como aquella que al ser removida permita que la variable que

entra a la base pueda tener un valor tan grande como sea posible, sin violar alguna de las restricciones en el modelo. En este caso la variable S3 deja la base y a su vez X1 se introduce como la nueva variable básica.

El elemento pivote es el coeficiente que está en la intersección de la columna de la variable que entra y la fila de la variable que sale.

Los valores correspondientes a la nueva fila pivote se obtienen dividiendo los coeficientes de la fila pivote en la tabla inicial por el elemento pivote.

Las otras filas de la solución mejorada se calculan por la expresión:

Nueva fila = Fila anterior – elemento de la columna pivote(nueva fila pivote), se obtiene la siguiente tabla:

i VB Z X1 X2 S1 S2 S3 Bi

0 Z 1 0 - 1 0 0 1.5 420

1 S1 0 0 1 1 0 -0.5 20

2 S2 0 0 1.5 0 1 - 0.25 50

3 X1 0 1 0.5 0 0 0.25 70

Iterando nuevamente se obtiene la tabla correspondiente que se muestra a continuación:

i VB Z X1 X1 S1 S2 S3 Bi

0 Z 1 0 0 1 0 1 440

1 X2 0 0 1 1 0 - 0.5 20

2 S2 0 0 0 - 1.5 1 0.5 20

3 X1 0 1 0 - 0.5 0 0.5 60

Aspectos Fundamentales Del Método Simplex

1. Encuentra una solución óptima 2. Es un método de cambio de bases 3. Requiere que la función objetivo sea expresada de tal forma que cada variable básica

tenga como coeficiente 0 4. Requiere que cada variable básica aparezca en una y solamente una ecuación de

restricción.

CONCLUSIONES:

La resolución de problemas lineales con sólo dos o tres variables de decisión se puede ilustrar gráficamente, mostrándose como una ayuda visual para comprender muchos de los conceptos y términos que se utilizan y formalizan con métodos de solución más sofisticados, como por ejemplo el Método Simplex, necesarios para la resolución de problemas con varias variables. Para ello se puede usar el método Gráfico.

En el método simplex cuando no hay coeficientes negativos, significa que la solución es óptima.

El método simplex para sistemas lineales las condiciones de optimidad y factibilidad garantizan, partiendo de un punto extremo factible (solución básica), el poder mejorar el valor de la función objetivo hasta llegar al optimo en cada iteración.