TSP Investigacion de operaciones. Métodos de solución en Programación Lineal: Simplex y Dual-Simplex

[pic 1]

M: 1, U: 1, O: 1

Una carpintería fabrica dos tipos de estantes: Clásico (A) y Moderno (B). El estante tipo

A requiere 3 horas de corte y 1 hora de barnizado. El estante tipo B requiere 2 horas de

corte y 4 horas de barnizado. El taller dispone de un máximo de 120 horas semanales

para corte y 100 horas para barnizado. La utilidad neta es de $15 por cada estante tipo

A y $20 por cada tipo B.

Formule el modelo PL, determinando:

1. Variables de Decisión.

2. Función Objetivo.

3. Restricciones.

4. El modelo matemático de Programación Lineal

Solución:

Para resolver este problema siguiendo los pasos metodológicos para la formulación de modelos de programación lineal (P.L.) detallados en el texto básico de la UNA se procede a continuación:

1. Variables de Decisión: Para construir el modelo se parte en definir el conjunto de actividades y asignarles niveles no negativos, los cuales representarán las variables de decisión.

• ​ = Número de estantes tipo Clásico (A) a fabricar por semana.[pic 11]
• ​ = Número de estantes tipo Moderno (B) a fabricar por semana.[pic 12]

2. Función Objetivo: Se establece que se debe definir la medida de efectividad del sistema como una función de las variables de decisión. Como el problema indica que se obtiene una utilidad neta de $15 por el estante A y $20 por el estante B, el objetivo lógico de la empresa es Maximizar sus ganancias.

• Maximizar:  (donde Z representa la utilidad neta total).[pic 13]

3. Restricciones: En este paso se requiere establecer el conjunto de restricciones mediante el reconocimiento de los recursos limitados. En esta carpintería, los recursos limitados son las horas disponibles para corte y para barnizado, sumado a que no se pueden producir cantidades negativas de estantes.

• Restricción de tiempo de corte:  (horas máximas semanales).[pic 14]
• Restricción de tiempo de barnizado (horas máximas semanales).[pic 15]
• Restricciones de no negatividad: ​≥0, ​≥0.[pic 16][pic 17]

4. El Modelo Matemático de Programación Lineal (PPL) 

Integrando las variables, la función objetivo y las restricciones de forma coherente y completa, el modelo matemático queda formulado de la siguiente manera:

• Maximizar [pic 18]
• Sujeto a: [pic 19]

M: 1, U: 2, O: 2

Maximizar [pic 20]

Sujeto a:

[pic 21]

[pic 22]

[pic 23]

Se pide:

1. Convierta el Problema de Programación Lineal (PPL) a su forma estándar.

2. Resuelva el PPL utilizando el Algoritmo Simplex. Muestre la tabla inicial y las

iteraciones necesarias hasta alcanzar la solución óptima. Identifique claramente la

variable de entrada, la variable de salida y el elemento pivote en cada iteración.

Solución:

1. Conversión del PPL a su forma estándar

Para aplicar el Algoritmo Simplex, se debe transformar las inecuaciones (restricciones de ≤) en ecuaciones. Esto se logra sumando una variable de holgura no negativa a cada restricción. Representaremos estas variables como S1​ y S2​. Asimismo, la Función Objetivo se iguala a cero.

Función Objetivo: [pic 24]

Restricciones: [pic 25][pic 26]

1. Resolución del PPL utilizando el Algoritmo Simplex

A. Configuración de la Tabla Simplex Inicial (Iteración 0)

• Variable de entrada: ​, porque es la que tiene el coeficiente más negativo en la fila de la función objetivo Z (-5).[pic 27]
• Variable de salida: Para determinarla, dividimos la columna "Solución" entre los coeficientes positivos de la columna de entrada (X1​):

• Fila S1​: 18/3=6
• Fila S2​: 10/1=10 Como 6 es el menor valor positivo, la variable de salida es S1​.

• Elemento pivote: 3 (intersección de la columna X1​ y la fila S1​).

B. Iteración 1

Se debe convertir el elemento pivote en 1 y el resto de los elementos de su columna en 0 realizando operaciones de fila.

1. Nueva Fila ​ (antigua ​): Dividimos toda la fila ​ entre 3. → Fila [pic 28][pic 29][pic 30][pic 31]
2. Nueva Fila Z: Fila Z anterior - (-5) * Nueva Fila ​. → Fila [pic 32][pic 33]
3. Nueva Fila ​: Fila  anterior - (1) * Nueva Fila ​. → Fila S2[pic 34][pic 35][pic 36][pic 37]
4. Tabla Simplex - Iteración 1

• Variable de entrada: ​, por ser el único coeficiente negativo en la fila Z (-2/3).[pic 40]
• Variable de salida: Se aplica la prueba del cociente mínimo:

• Fila [pic 41]
• Fila  Como 3 es el menor valor, la variable de salida es ​.[pic 42][pic 43]

• Elemento pivote: 4/3 (intersección de la columna X2​ y la fila S2​).

C. Iteración 2

Nuevamente, se convierte el elemento pivote en 1 y hacemos ceros en su columna.

1. Nueva Fila ​ (antigua ​): Multiplicamos la fila ​ por 3/4. → Fila [pic 44][pic 45][pic 46][pic 47]
2. Nueva Fila Z: Fila Z anterior - (-2/3) * Nueva Fila ​. → Fila [pic 48][pic 49]
3. Nueva Fila ​: Fila  anterior - (2/3) * Nueva Fila ​. → Fila [pic 50][pic 51][pic 52][pic 53]

1. Tabla Simplex - Iteración 2

...