Práctica 2.Construcción del método Simplex
Elaborado por Carolina Esther Munguía Quintana
Proyecto de titulación: Prácticas para un laboratorio virtual como apoyo a temas selectos de IDO (título corto)
Elaborado por Carolina Esther Munguía Quintana
Proyecto de titulación: Prácticas para un laboratorio virtual como apoyo a temas selectos de IDO (título corto)
La intersección de todas las restricciones dadas en un problema forman la región de soluciones factibles, dicha región tiene la característica de ser un conjunto convexo. Los conjuntos convexos son aquellos con la propiedad de que al unir con un segmento dos puntos cualesquiera dentro del conjunto este segmento queda contenido completamente en el conjunto.
Cuando un problema de PL tiene solución, ésta se encuentra en un punto extremo de la región de soluciones factibles. Un punto es extremo si cualquier segmento de la región factible que contiene al punto tiene a éste al final del segmento. Este punto, también conocido como vértice, no puede definirse como combinación lineal convexa de ningún par de puntos distintos del conjunto.
La forma estandar modifica las restricciones del problema para tener siempre igualdades, es por eso que las inecuaciones son modificadas con variables de holgura y exceso, como se muestra en la tabla
Caracteriza el siguiente conjunto de restricciones:
Demuestra lo siguiente:
Demuestra lo siguiente:
El método Simplex es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima.
Retomaremos las restricciones de la actividad 1 pero ahora agregaremos la función objetivo para encontrar la solución óptima. Así tenemos lo siguiente:
Escribe la forma estándar del PPL
¿Cuál es el vector de costos C?
¿Cuáles son las bases asociadas a soluciones básicas factibles?
Paso 1.
Comenzaremos desde la base B=(a2,a4,a5). Escribe la submatriz correspondiente, así como las matrices XB, XN y N
Identifica los vectores CB y CN del vector de costos reducidos
¿Cuál es el valor de la función objetivo en esta base? (Valor actual)
Paso 2.
Calcula Z
¿Qué pasa si damos algún valor diferente de cero a la variable no básica X1? ¿La función aumenta o disminuye su valor?
¿Qué pasa si damos algún valor diferente de cero a la variable no básica S1? ¿La función aumenta o disminuye su valor?
¿La solución Z=63 es óptima?
Nota: En caso de tener más de un candidato a entrar a la base, seleccionaremos aquel con coeficiente de costo reducido mayor.
¿Qué variable se debe elegir para entrar a la base?
Para saber qué variable saldrá de la base debemos plantear un sistema de ecuaciones ¿Cuál es dicho sistema?
Recordando que hay una variable no básica la cual tiene valor cero, eso reduce el sistema ¿Cuál es el nuevo sistema?
¿Cuál es el valor más grande que puede tomar 𝑋1 de tal forma que se satisfaga la no negatividad del resto de variables? ¿Qué variable se hace cero cuándo la variable entrante toma su valor más grande posible?
Paso 3.
¿Cuál es la nueva base?
Repetir el procedimiento las veces necesarias para encontrar el valor óptimo.
¿Cuál es la solución óptima?