Trabajo practico MAT329
METODOS DE SOLUCION DE MODELOS MATEMATICOS DE PROGRAMACION
LINEAL
METODO GRAFICO
Ejercicio 1 – Minimización
Un estudiante de administración de empresas necesita completar un total de 65 cursos
para graduarse. El número de cursos de administración tendrá que ser mayor que o
igual a 23. El número de cursos ajenos al área de administración deberá ser mayor
que o igual a 20. El curso de administración promedio requiere un libro de texto que
cuesta $60 e implica 120 horas de estudio. Los cursos ajenos al área de
administración requieren un libro de texto que cuesta $24 e implican 200 horas de
estudio. El estudiante dispone de un presupuesto de $3,000 para libros.
a. Formule un conjunto de ecuaciones lineales para describir la función objetivo y
las restricciones.
b. Utilice el análisis gráfico para encontrar la solución visual.
c. ¿Con qué combinación de cursos de administración y otros ajenos a esta área
se minimizaría el número total de horas de estudio?
d. Identifique las variables de holgura o superávit.
a) El planteamiento del problema de programación lineal sería:
Variables:
X = Cursos de Administración que cursará el estudiante
Y = Cursos ajenos al área de Administración que cursará el estudiante
Función Objetivo:
Z = Minimizar (120X + 200 Y)
Restricciones:
Cursos Necesarios para graduarse: X + Y = 65
Cantidad de Cursos de Administración: X ≥ 23
Cantidad de Cursos ajenos a Administración: Y ≥ 20
Presupuesto del estudiante: 60X + 24Y ≤ 3000
b) Análisis grafico
Para resolver el problema vamos a calcular la región factible que está formada por el
área que satisface el conjunto de restricciones.
Paso 1:
No Negatividad: X1, X2 ≥ 0
Las variables de decisión del problema deben de cumplir la restricción de no
negatividad; es decir, sus valores pueden ser de 0 a más.
En nuestro gráfico, significa que la región factible se encontrará en el primer
cuadrante:
Paso 2:
Restricción N° 1: X1 + X2 = 65
Como esta restricción es una igualdad, la gráfica corresponde a una recta.
X1 + X2 = 65
Calculamos los puntos de intersección de la recta con los ejes X1 y X2, para ello
evaluamos la ecuación dándole el valor de 0 a cada una de las variables:
Sea X1 = 0 => X2 = 65
Sea X2 = 0, entonces X1 = 65
De los resultados obtenidos se obtienen los siguientes puntos: A = (0,65) y B = (65,0).
La recta cruzará por ambos puntos en el gráfico.
Según las restricciones evaluadas, la región factible formada hasta el momento
corresponde a una recta, el cual se encuentra señalizado en el gráfico con la letra R.
Paso 3:
Restricción N° 2: X1 + 0X2 ≥ 23
Para graficar esta restricción, convertiremos la inecuación en una igualdad cambiando
el "≥" por "=" para graficar la línea recta:
X1 = 23
Dado que el coeficiente de X2 es cero, simplemente se procede a resolver la ecuación:
X1 = 23
La recta se trazará de manera paralela al eje X2 y pasará por el punto B = (23,0).
Para determinar si el área que debe sombrearse en la recta trazada, basta con evaluar
cualquier coordenada diferente a la calculada y verificar si cumple la restricción. Por
ejemplo evaluaremos la coordenada (46,0) en la restricción:
1(46) ≥ 23 => 46 ≥ 23
Dado que se cumple la desigualdad, se debe pintar el área donde está ubicado el
punto elegido.
Según las restricciones evaluadas, la región factible formada hasta el momento
corresponde a una recta, el cual se encuentra señalizado en el gráfico con la letra R.
Paso 4:
Restricción N° 3: 0X1 + X2 ≥ 20
Para graficar esta restricción, convertiremos la inecuación en una igualdad cambiando
el "≥" por "=" para graficar la línea recta:
X2 = 20
Dado que el coeficiente de X1 es cero, simplemente se procede a resolver la ecuación:
X2 = 20
La recta se trazará de manera paralela al eje X1 y pasará por el punto A = (0,20).
Para determinar si el área que debe sombrearse en la recta trazada, basta con evaluar
cualquier coordenada diferente a la calculada y verificar si cumple la restricción. Por
ejemplo evaluaremos la coordenada (0,40) en la restricción:
1(40) ≥ 20 => 40 ≥ 20
Dado que se cumple la desigualdad, se debe pintar el área donde está ubicado el
punto elegido.
Según las restricciones evaluadas, la región factible formada hasta el momento
corresponde a una recta, el cual se encuentra señalizado en el gráfico con la letra R.
Paso 5:
Restricción N° 4: 60X1 + 24X2 ≤ 3000
Para graficar esta restricción, convertiremos la inecuación en una igualdad cambiando
el "≤" por "=" para graficar la línea recta:
60X1 + 24X2 = 3000
Calculamos los puntos de intersección de la recta con los ejes X1 y X2, para ello
evaluamos la ecuación dándole el valor de 0 a cada una de las variables:
Sea X1 = 0 => 24X2 = 3000 => X2 = 3000/24 => X2 = 125
Sea X2 = 0, entonces 60X1 = 3000 => X1 = 3000/60 => X1 = 50
De los resultados obtenidos se obtienen los siguientes puntos: A = (0,125) y B =
(50,0). La recta cruzará por ambos puntos en el gráfico.
Ahora que calculamos la recta de la gráfica, volvemos a la restricción inicial:
60X1 + 24X2 ≤ 3000
Para determinar si debemos sombrear la parte superior e inferior de la recta podemos
seguir la siguiente regla:
Signo del coeficiente de Tipo de Inecuación Ubicación del área a
X2 pintar en relación a la
recta
+ ≤ Inferior
+ ≥ Superior
- ≤ Superior
- ≥ Inferior
Dado que el inecuación es ≤ (menor igual que) y el signo del coeficiente
X2 es positivo el área a sombrear corresponde a la parte inferior de la recta.
Nota: Otra forma de verificar que lado de la recta debes sombrear es eligiendo un
punto al azar, ya sea de la parte superior o inferior de la recta. Si al reemplazar las
coordendas en la inecuación, se cumple la desigualdad; entonces el lado donde se
encuentra el punto elegido es la que debes sombrear. En caso no se cumpla la
desigualdad, el área a sombrear es la del otro lado.
Según las restricciones evaluadas, la región factible formada hasta el momento
corresponde a una recta, el cual se encuentra señalizado en el gráfico con la letra R.
Paso 6:
La región factible corresponde a un segmento de recta, por lo tanto, evaluaremos los
extremos del segmento para minimizar la función objetivo:
Coordenadas
Punto (X1,X2) Valor de la Función Objetivo 120X1 + 200X2
A (23,42) 120(23) + 200(42)=11160
B (40,25) 120(40) + 200(25)=9800
El mínimo valor de la función objetivo se encuentra en el punto B= (40,25) con un
resultado de 9800:
Solución
Valor Óptimo (Z) X₁ X₂
9800 40 25
La solución visual se encontraría en el punto B:
X = 40
Y = 25
c) Con los valores obtenidos de X = 40, Y = 25, se minimizará las horas de estudio,
teniendo como resultado 9800 horas.
d) Se tiene las variables de superávit para las restricciones respecto a la cantidad de
cursos de administración (s1) y cursos ajenos a la administración (s2).
s1 = 40 – 23 = 17
s2 = 25 – 20 = 5
METODO SIMPLEX
EJERCICIO 2
Gutchi Company fabrica bolsos de mano, bolsos para rasuradora y mochilas. La
elaboración incluye piel y materiales sintéticos, y la piel es la materia prima escasa. El
proceso de producción requiere dos tipos de mano de obra calificada: costura y
acabado. La siguiente tabla da la disponibilidad de los recursos, su consumo por los
tres productos y las utilidades por unidad.
REQUERIMIENTOS DE RECURSOS POR UNIDAD
Recurso Bolsos de Bolsos para Mochila Disponibilidad
Mano rasuradora diaria
Piel (pies2) 2 1 3 42 pies2
Costura (h) 2 1 2 40 h
Acabado (h) 1 0.5 1 45 h
Precio de 24 22 45
venta ($)
a. Formule el problema como un programa lineal, y halle la solución óptima.
b. A partir de la solución óptima, determine el estado de cada recurso.
SOLUCION
a. El planteamiento del problema sería:
Maximizar Z=24x1+22x2+45x3
Sujeto a:
2x1+x2+3x3≤42
2x1+x2+2x3≤40
x1+0.5x2+x3≤45
x1, x2, x3≥0
Para resolver el problema por el método simplex utilizaremos la versión de membresía
de nuestra calculadora de programación lineal:
El problema se adecuará al modelo estándar de programación lineal, agregando las
variables de holgura, exceso y/o artificiales en cada una de las restricciones:
Restricción 1: Tiene signo «≤» (menor igual) por lo que se agregará la variable
de holgura S1. En la tabla inicial, S1 estará en la base.
Restricción 2: Tiene signo «≤» (menor igual) por lo que se agregará la variable
de holgura S2. En la tabla inicial, S2 estará en la base.
Restricción 3: Tiene signo «≤» (menor igual) por lo que se agregará la variable
de holgura S3. En la tabla inicial, S3 estará en la base.
A continuación se muestra el problema en la forma estándar. Se colocará el
coeficiente 0 (cero) donde corresponda para crear nuestra matriz:
Función Objetivo
Maximizar: Z = 24X1 + 22X2 + 45X3 + 0S1 + 0S2 + 0S3
Sujeto a:
2X1 + 1X2 + 3X3 + 1S1 + 0S2 + 0S3 = 42
2X1 + 1X2 + 2X3 + 0S1 + 1S2 + 0S3 = 40
1X1 + 1/2X2 + 1X3 + 0S1 + 0S2 + 1S3 = 45
X1, X2, X3, S1, S2, S3 ≥ 0
Solución
Matriz Inicial
Cálculo de Vector Solución (Z)
Para esta tabla, el valor de la fila Z se calculará así:
Z1 = (Cb,1*X1,1) + (Cb,2*X1,2) + (Cb,3*X1,3) – Cj1 = (0*2) + (0*2) + (0*1) – (24) = -24
Z2 = (Cb,1*X2,1) + (Cb,2*X2,2) + (Cb,3*X2,3) – Cj2 = (0*1) + (0*1) + (0*1/2) – (22) = -22
Z3 = (Cb,1*X3,1) + (Cb,2*X3,2) + (Cb,3*X3,3) – Cj3 = (0*3) + (0*2) + (0*1) – (45) = -45
Z4 = (Cb,1*S1,1) + (Cb,2*S1,2) + (Cb,3*S1,3) – Cj4 = (0*1) + (0*0) + (0*0) – (0) = 0
Z5 = (Cb,1*S2,1) + (Cb,2*S2,2) + (Cb,3*S2,3) – Cj5 = (0*0) + (0*1) + (0*0) – (0) = 0
Z6 = (Cb,1*S3,1) + (Cb,2*S3,2) + (Cb,3*S3,3) – Cj6 = (0*0) + (0*0) + (0*1) – (0) = 0
Z7 = (Cb,1*R,1) + (Cb,2*R,2) + (Cb,3*R,3) = (0*42) + (0*40) + (0*45) = 0
Tabla
1 Cj 24 22 45 0 0 0
Cb Base X1 X2 X3 S1 S2 S3 R
0 S1 2 1 3 1 0 0 42
0 S2 2 1 2 0 1 0 40
0 S3 1 1/2 1 0 0 1 45
- - -
Z 24 22 45 0 0 0 0
Ingresa la variable X3 y sale de la base la variable S1. El elemento pivote es 3
Iteración 1
Cálculos
Realizaremos las iteraciones de cada valor en la tabla considerando lo siguiente:
Nuevo Valor Fila Pivote = Valor Actual Fila Pivote / Elemento Pivote
Nuevo Valor = Valor Actual – (Elemento Fila Columna Pivote*Nuevo Valor Fila
Pivote)
Cálculos en fila Pivote (Fila N° 1):
Valor Actual
Fila Pivote 2 1 3 1 0 0 42
Elemento
Pivote 3 3 3 3 3 3 3
Nuevo Valor 2/3= 1/3 3/3= 1/3= 0/3= 0/3= 42 / 3 =
Fila Pivote 2/3 = 1/3 1 1/3 0 0 14
