Tema 3. Método gráfico guía teórica

Tema 3. Método gráfico guía teórica

1. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 1


P








TEMA 3

PROGRAMACIÓN LINEAL: MÉTODO GRÁFICO Y MÉTODO SIMPLEX





Muchas personas clasifican el desarrollo de la Programación Lineal (PL) entre los
avances científicos más importantes de mediados del siglo XX. En la actualidad es una
herramienta común que ha ahorrado miles o millones de dólares a muchas compañías
y negocios, incluyendo industrias medianas en distintos países del mundo.

¿Cuál es la naturaleza de esta notable herramienta y qué tipo de problemas
puede manejar? Expresado brevemente, el tipo más común de aplicación abarca el
problema general de asignar recursos limitados entre actividades competitivas de la
mejor manera posible (es decir, en forma óptima).

Este problema de asignación puede surgir cuando deba elegirse el nivel de
ciertas actividades que compiten por recursos escasos para realizarlas. La variedad de
situaciones a las que se puede aplicar esta descripción es sin duda muy grande, y va
desde la asignación de instalaciones productivas a los productos, hasta la
asignación de los recursos nacionales a las necesidades de un país; desde la
planeación agrícola, hasta el diseño de una terapia de radiación; etc. No obstante, el
ingrediente común de todas estas situaciones es la necesidad de asignar recursos a las
actividades.

Con frecuencia, seleccionar una alternativa incluye satisfacer varios criterios al
mismo tiempo. Por ejemplo, cuando se compra una pieza de pan se tiene el criterio de
frescura, tamaño, tipo (blanco, integral u otro), costo y rebanado o sin rebanar. Se
puede ir un paso más adelante y dividir estos criterios en dos categorías: restricciones
y el objetivo. Las restricciones son las condiciones que debe satisfacer una solución
que está bajo consideración. Si más de una alternativa satisfacen todas las
restricciones, el objetivo se usa para seleccionar entre todas las alternativas factibles.
Cuando se elige una pieza de pan, pueden quererse 100 gr. de pan blanco rebanado y
hecho no antes de ayer. Si varias marcas satisfacen estas restricciones,
puede aplicarse el objetivo de un costo mínimo y escoger las más barata.

2. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 2

Existen muchos problemas administrativos que se ajustan a este molde de
tratar de minimizar o maximizar un objetivo que está sujeto a una lista de
restricciones. un corredor de inversiones, por ejemplo, trata de maximizar el
rendimiento sobre los fondos invertidos pero las posibles inversiones están restringidas
por las leyes y las políticas bancarias. Un hospital debe planear que las comidas para
los pacientes satisfagan ciertas restricciones sobre sabor, propiedades nutritivas, tipo
y variedad, al mismo tiempo que se trata de minimizar el costo. Un fabricante, al
planear la producción futura, busca un costo mínimo al mismo tiempo cómo cumplir
restricciones sobre la demanda del producto, la capacidad de producción, los
inventarios, el nivel de empleados y la tecnología. La PL se ha aplicado con éxito a
estos y otros problemas.

La PL es una técnica determinista, no incluye probabilidades y utiliza un modelo
matemático para describir el problema. El adjetivo lineal significa que todas las
funciones matemáticas del modelo deben ser funciones lineales. En este caso, la
palabra programación no se refiere a programación en computadoras; en esencia es un
sinónimo de planeación.

Así, la PL trata la planeación de las actividades para obtener un resultado
óptimo, esto es, el resultado que mejor alcance la meta especificada (según el modelo)
entre todas las opciones de solución. Aunque la asignación de recursos a las
actividades es la aplicación más frecuente, la PL tiene muchas otras posibilidades. De
hecho, cualquier problema cuyo modelo matemático se ajuste al formato general del
modelo de PL es un problema de PL.


MÉTODO GRÁFICO
Consiste en graficar las soluciones factibles, o el espacio de soluciones (espacio
factible), que satisfaga todas las restricciones simultáneamente. Es una manera
“simple” de resolver un problema de programación lineal que tenga solamente dos
variables de decisión. Es útil para encontrar la solución óptima e información adicional
sobre cuan susceptible es esa solución con respecto a los datos del problema. Aun
cuando para modelos con tres o más variables, este método es impráctico o imposible,
proporciona un buen fundamento para el uso de la Programación Lineal en el mundo
real.

3. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 3

Para la solución gráfica de programas lineales con dos variables, lo que se tiene
que hacer es trazar un eje de coordenadas cartesianas, para graficar las desigualdades
dadas por el problema, después encontrar el Área de Soluciones Factibles y proceder a
graficar la función objetivo para conocer el valor óptimo (maximizar o minimizar) que
será la solución del problema.


TERMINOS IMPORTANTES

Puntos Extremos: Son los puntos esquina de una región factible.

Representan las intersecciones entre las restricciones.


Línea de F.O: Gráfica donde todos los puntos sobre la línea tienen el
mismo valor de función objetivo (Isocostos,
Isoutilidades).
Solución Óptima: Punto en la región factible que tiene el mejor valor de

la función objetivo. Representan los valores óptimos de
las variables de decisión. Pueden existir infinitas
soluciones óptimas.


Valor óptimo: Valor de la función objetivo evaluada en la solución
óptima.


Restricción Activa: Aquella que pasa por la solución óptima. Evaluada en
la solución óptima, los términos de la restricción son
iguales.

Restricción Inactiva: Aquella que no pasa por la solución óptima. Evaluada
en la solución óptima, los términos de la restricción
son diferentes. Posee un excedente o una holgura.

4. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 4



Excedente: Es la diferencia entre el primer miembro y el lado
derecho en una restricción mayor o igual (≥) evaluada
en la solución óptima.


Holgura: Es la diferencia entre el lado derecho y el primer
miembro de una restricción menor o igual (≤) evaluada
en la solución óptima.




METODOLOGÍA

1.- Graficar las soluciones factibles. (espacio encerrado por todas las
restricciones del modelo).

Reemplazar el signo de desigualdad con un signo de igualdad en
cada una de las restricciones.

PROBLEMA Nro. 1

Max Z = 900X + 900Y
S.A.: 400X + 100Y ≥ 800
100X + 100Y ≤ 500
100X ≤ 300
100Y ≥ 100
X,Y ≥ 0

400X + 100Y = 800

100X + 100Y = 500

100X = 300

100Y = 100

X = 0
Y = 0


Graficar la igualdad (línea recta).
Se realiza la gráfica de cada recta señalando dos puntos para cada
una de las restricciones. Se recomienda hacer tomar como puntos cuando
las dos variables tiene un valor igual a cero (0).

5. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 5















Restricción 1














Restricción 2




















Restricción 3

6. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 6
















Restricción 4




















Todas las restricciones








Identificar el lado factible de la recta: Lo indica la dirección de la flecha situada
sobre la línea recta asociada. Se selecciona un punto cualquiera (a,b) que no
pertenezca a la recta y se verifica si satisface la restricción. Si así es, entonces ese
punto está en el lado factible; si no es así, el lado factible está en el lado opuesto al
punto seleccionado. Una manera fácil de determinar la dirección de la flecha es
usar el origen (0,0) como punto de referencia. Si (0,0) satisface la desigualdad, la
dirección factible debe incluir al origen; si no es así, debe estar en el lado opuesto.
R1 = (0,0) = 0 ≥ 800 no satisface

R2 = (0,0) = 0 ≤ 500 si satisface

7. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 7

R3 = (0,0) = 0 ≤ 300 si satisface

R4 = (0,0) = 0 ≥ 100 no satisface




Restricción 1





Restricción 2






Restricción 3

8. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 8




Restricción 4



El área del gráfico que satisface todas las restricciones, se denomina
REGIÓN FACTIBLE (ESPACIO FACTIBLE) y cualquier punto dentro de esta región
es una SOLUCIÓN FACTIBLE.






2.- Determinar la solución óptima.

Método I

Graficar la función (línea) objetivo. Efectúe Z=0.

Localizar su mejor lado. Grafique Z = 0.
“Mover” la línea de la función objetivo paralela a si misma en la
dirección de mejora.



El punto final de corte entre la Región Factible y la función objetivo es la
SOLUCIÓN ÓPTIMA.


Método II

9. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 9

Identificar y determinar los puntos de intersección entre las
restricciones.











Evaluando la función objetivo en los puntos de intersección de las
restricciones (esquinas del área factible):


Max Z = 900X + 900Y

X Y Z
Punto 1 1.75 1 2475
Punto 2 1 4 4500
Punto 3 3 2 4500
Punto 4 3 1 3600




El punto que optimiza (minimiza o maximiza) la función objetivo es

la SOLUCIÓN ÓPTIMA.

10. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 10













PROBLEMA RESUELTO


Maximizar: Z = X + 2Y Sujeto a:
X + Y ≤ 3
X – 2Y ≥ 0

Y ≤ 1

X , Y ≥ 0


1.- Convertir en igualdades todas las restricciones

X + Y = 3

X – 2Y = 0

Y = 1

X = 0

Y = 0

11. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 11

2.- Graficar cada una de las restricciones










3.- Determinar el lado factible de cada recta
R1 = (0,0) = 0 ≤ 3 si satisface R2 =
(1,0) = 1 ≥ 0 si satisface R3 =
(0,0) = 0 ≤ 1 si satisface








3.- Identificar la región factible

12. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 12


4.- Determinar los puntos extremos


X Y F.O(Z)
--------- --------- ---------
1 3.00 0.00 3.00
2 2.00 1.00 4.00
3 0.00 0.00 0.00







5.- Determinar la Solución Óptima

Punto 2

X = 2.00

Y = 1.00

Z = 4.00

13. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 13







CASOS POSIBLES DE SOLUCIÓN EN LA RESOLUCIÓN DE PROBLEMAS DE
PROGRAMACIÓN LINEAL.

Si existe el conjunto de soluciones o valores que satisfacen las
Soluciones Factibles

restricciones. A su vez, pueden ser:



Con solución única

En una urbanización se van a construir casas de dos tipos: A y B. La
empresa constructora dispone para ello de un máximo de 1800 millones de
pesetas, siendo el coste de cada tipo de casa de 30 y 20 millones,
respectivamente. El Ayuntamiento exige que el número total de casas no
sea superior a 80.

Sabiendo que el beneficio obtenido por la venta de una casa de tipo A es 4
millones y de 3 millones por una de tipo B, ¿cuántas casas deben
construirse de cada tipo para obtener el máximo beneficio?
Variables: x = nº de casas tipo A ; y = nº de casas tipo B
Función objetivo: Maximizar Z = f(x,y) = 4x + 3y
Conjunto de restricciones: El coste total 30x + 20y 1800 . El

Ayuntamiento impone x + y 80 . De no negatividad: x 0 , y 0.

Tiene por región factible la región coloreada. Si hallamos los valores de la
función objetivo en cada uno de los vértices : f(O) = f(0,0) = 0 ; (C)=f(60,0)
= 240 ;f(D) = f(20,60) = 260 ; f(E) = f(0,80) = 240

La solución es única, y corresponde al vértice para el que la función
objetivo toma el valor máximo. En este caso es el vértice D(20,60). Por
tanto se deben construir 20 casas de tipo A y 60 de tipo B con un coste de
260 millones de pesetas.

14. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 14

































Con solución Si existe más de una solución óptima

múltiple

Maximizar la función Z = f(x,y) = 4x + 2y sujeta a las restricciones 2x + y

4 , x - y 1 , x 0 , y 0.

Los valores de la fucnión objetivo en cada uno de los vértices son:

f(O)=f(0,0) = 0 , f(A) = f(1,0) = 4 ; f(B)=f(5/3,2/3) = 8 , f(C) = f(0,4) = 8

La función objetivo alcanza el valor máximo en los vértices B y C, por tanto,
en todos los puntos del segmento BC. Hay infinitas soluciones, solución
múltiple, que corresponden a los puntos del segmento situado entre dos
vértices de la región factible. En estos casos, como ya vimos en el
capítulo anterior, la función objetivo es paralela a una de las restricciones.



Con
solución
no
acotada



Cuando no existe límite para la función objetivo

Maximizar la función Z = f(x,y) = x + y sujeta a las restricciones y 2x , y
x/2 . Tiene por región factible la zona coloreada que aparece en la figura,
que es una región no acotada. La función crece indefinidamente para
valores crecientes de x e y. En este caso no existe un valor extremo
para la función objetivo, por lo que puede decirse que el problema
parece de solución. Para que suceda esta situación la región factible
debe estar no acotada.

15. Investigación de Operaciones 3. Programación Lineal

Prof. Lcdo. Wilfredo Díaz Página 15










No factibles Cuando no existe el conjunto de soluciones que cumplen las restricciones, es
decir, las restricciones son inconsistentes.



Maximizar la función Z = f(x,y) = 3x + 8y sujeta a las restricciones x + y 6

, x + y 2 , x 0 , y 0.
No existe la región factible, ya que las zonas coloreadas que aparecen en la
figura son únicamente soluciones de alguna de las inecuaciones . Por
tanto, el conjunto de soluciones del sistema de desigualdades no
determina ninguna región factible. Este tipo de problemas carece de solución.