Optimización Lineal

miércoles, 23 de abril de 2014

Modelos Duales

Unidad 4
Participación 1

Sea el modelo primal:

Max w= 4y1 + 2y2 -y3

s.a.

y1 + 2y2 ≤ 6
y1 - y2 + 2y3 = 8
y1, y2 ≥ 0 y3 no restringida

Haciendo uso del resumen, obtenemos el modelo dual correspondiente, considerando:

Max w → Min g
3 variables   → 3 restricciones
2 restricciones → 2 variables
c → cT
b → bT
rest 1 ≤ b1 → x1≥0
rest 2 = b2    → x2 no restringida
y1 ≥ 0 → rest 1 ≥ c1
y2 ≥ 0   → rest 2 ≥ c2
y3 no rest → rest 3 = c3

Entonces tenemos:

Min g= 6x1 + 8 x2

s.a.

x1 + x2 ≥ 4
2x1 - x2 ≥ 2
2x2 = -1

x1≥0
x2 no restringida

martes, 22 de abril de 2014

Programas computacionales del Método Simplex

Programa	URL	Características	Ventajas	Desventajas
PHPSimplex	Click	Es una herramienta online para resolver problemas de programación lineal. Su uso es libre y gratuito. PHPSimplex es capaz de resolver problemas mediante el método Simplex, el método de las Dos Fases, y el método Gráfico, y no cuenta con limitaciones en el número de variables de decisión ni en las restricciones de los problemas.	No solo muestra los resultados finales sino también las operaciones intermedias. También ofrece la solución directa para uso de profesionales. Otras de sus ventajas son que no precisa de ningún lenguaje para enunciar el problema, ofrece una interfaz amigable, es cercano al usuario, de manejo fácil e intuitivo, no es necesario instalar nada para poder usarlo, y está disponible en varios idiomas	En el método gráfico no específica la región factible.
JSimplex	Click	Permite resolver problemas de Programación Lineal usando el método Simplex. Para los problemas que tengan variables artificiales se usará el método de la gran M, y para los problemas que involucren variables enteras se usará el método de ramificar y acotar (branch and bound).	Se pueden ver los cálculos intermedios y la explicación de como resolver el problema.Sirve para problemas de variable entera.	No realiza método gráfico.
Método Simplex (ZweigMedia Inc.)	Click	Permite resolver modelos de Programación Lineal utilizando el Método Simplex.	Se obtiene la solución óptima, valor óptimo y cada una de las tablas del Método Simplex. Tiene tres modos de trabajo: entero, fracción y decimal.	La interfaz de la aplicación no es tan amigable con el usuario como en los otros programas. No resuelve para problemas de variable entera. No realiza método gráfico.
Simplex Online Calculator	Click	Es una aplicación que ayuda a resolver problemas de programación lineal. Aplica método simplex y algoritmo de las dos fases cuando el problema así lo requiere. Con ella el usuario puede ver paso a paso la ejecución del algoritmo, el elemento pivote, los xb, etcétera. Consta de varios menús como pasar a dual, añadir fila, borrar fila y ejecutar.	Hay también una versión para dispositivos android y permite manipular el dual, lo cual facilita la interpretación de resultados.	Tiene muchas ventanas emergentes de publicidad.
Pivot	Click	Pivot ha sido utilizado en todo el mundo para resolver problemas de programación lineales por el método Simplex. Pivot ha sido reescrito en Java. Con la ayuda de esta aplicación, serás capaz de resolver problemas lineales utilizando el método Simplex.	Dado que no es software libre, está en mejora continua lo cual permite tener asesoría al utilizarlo. Su versión de prueba tiene licencia de 6 meses.	Requiere Java y no es software libre.

Referencias:

■ "PHPSimplex" Recuperado en abril 21 de «http://www.phpsimplex.com/»

■ "JSimplex" Recuperado en abril 21 de «http://soft.ingenieria-industrial.net/programacion_lineal.php»

■ "El método Simplex" Recuperado en abril 21 de «www.programacionlineal.net/simplex.html»

■ "Simplex Online Calculator" Recuperado en abril 22 de «http://www.mathstools.com/section/main/Simplex_On_Line?lang=es#.U1YfEFV5Ots»

■ "Pivot 3.01" de Bennette Harris, recuperado en abril 22 de «http://www.softpedia.es/programa-Harris-Pivot-208167.html»

martes, 15 de abril de 2014

Tarea III

sábado, 15 de marzo de 2014

UNIDAD 3. Actividad 1

Método Simplex

Pasos del método Simplex:

Seleccionar una solución básica factible inicial (en general es el origen).
Elegir a la variable de entrada, que en el caso de maximización será la variable no básica que tenga el valor más negativo y en el caso de minimización, aquella de valor positivo mayor.
Seleccionar la variable de salida basándose en la razón entre la columna de soluciones y el coeficiente respectivo a la columna de la v. de entrada ya elegida, teniendo en cuenta descartar aquellas razones en las que el coeficiente respectivo sea ≤=0.
Usar operaciones fila para hallar la nueva solución básica factible (actualizar tabla).
Detenerse cuando ya no haya variables no básicas que cumplan la condición dada en 1, mientras no se llegue a ello repetir los pasos anteriores.

Problema

Pedrito es un pequeño fabricante de camisas para caballero y blusas de dama para las tiendas de descuento Waldos, corporación que aceptará toda la producción surtida por Pedrito, El proceso de producción incluye el corte, la costura, y el empaque. Se ha empleado a 25 trabajadores en el departamento de corte, 35 en el de costura y 5 en empaque. La fábrica trabaja un turno de 8 horas, 5 días a la semana. La siguiente tabla muestra los requerimientos de tiempo y utilidad por unidad para las dos prendas:

Modelo

Forma estándar

Tablas

Comenzamos con la solución:

Como ya no hay más variables no básicas negativas, la solución es la óptima.

Resultados

Los resultados indican que deben producirse 480 camisas y 840 blusas, lo cual agota la disponibilidad de los departamentos de corte y costura aunque nos queda una holgura de 2,880minutos (48 horas) disponibles del departamento de empaque, las cuales corresponden a la labor realizada por 1.2 personas a la semana, es decir, podríamos restar un empleado de ese departamento.