Apuntes PL Metodo Grafico

8/18/2019 Apuntes PL Metodo Grafico

1/20

Guía Práctica para Investigación de Operaciones

Página 31

PROGRAMACIÓN LINEAL

Los fundamentos matemáticos de la programación lineal se deben al matemático

norteamericano de origen húngaro Janos von Neuman (1903-1957), quien en 1928publicó su famoso trabajo Teoría de Juegos. En 1947 conjetura la equivalencia de los

problemas de programación lineal y la teoría de matrices desarrollada en sus trabajos.La influencia de este respetado matemático, discípulo de David Hilbert en Gotinga y,

desde 1930, catedrático de la Universidad de Princenton de Estados Unidos, hace que

otros investigadores se interesaran paulatinamente por el desarrollo riguroso de esta

disciplina.

En 1858 se aplicaron los métodos de la programación lineal a un problema concreto: el

cálculo del plan óptimo de transporte de arena de construcción a las obras de

edificación de la ciudad de Moscú. En este problema había 10 puntos de partida y 230

de llegada. El plan óptimo de transporte, calculado con el ordenador Strena en 10 días

del mes de junio, rebajó un 11% los gastos respecto a los costos previstos.

Se ha estimado, de una manera general, que si un país subdesarrollado utilizase los

métodos de la programación lineal, su producto interior bruto (PIB) aumentaría entre

un 10 y un 15% en tan sólo un año.

Definición de Programación lineal:

Se llama programación lineal al conjunto de técnicas matemáticas que pretenden

resolver la situación siguiente: Optimizar (maximizar o minimizar) una función objetivo,

función lineal de varias variables, sujeta a una serie de restricciones, expresadas porinecuaciones lineales.

Un problema de programación lineal en dos variables, tiene la siguiente formulación estándar:

Pudiendo cambiarse maximizar por minimizar, y el sentido de las desigualdades.

En un problema de programación lineal intervienen:

La función z = ax + by llamada función objetivo y que es necesario optimizar. En esaexpresión x e y son las variables de decisión, mientras que a, b y c son constantes.

Las restricciones que deben ser inecuaciones lineales. Su número depende delproblema en cuestión. El carácter de desigualdad viene impuesto por las limitaciones,

disponibilidades o necesidades, que son: inferiores a … ( < o ); como mínimo de…

( > o ) . Tanto si se trata de maximizar como de minimizar, las desigualdades puedendarse en cualquiera de los dos sentidos.


2/20


Página 32

Al conjunto de valores de x e y que verifican todas y cada una de las restricciones se le

denomina conjunto (o región) factible. Todo punto de ese conjunto puede ser solución del problema; todo punto no perteneciente a ese conjunto no puede ser

solución. En el apartado siguiente veremos cómo se determina la región factible.

Lasolución óptima

del problema será un par de valores ( x 0,

y 0 ) del conjunto factible

que haga que f( x,y ) tome el valor máximo o mínimo.

Utilizaremos las siglas PPL para indicar problema de programación lineal

Determinación de la región factible:

La solución de un problema de programación lineal, en el supuesto de que exista, debe estar

en la región determinada por las distintas desigualdades. Esta recibe el nombre de regiónfactible, y puede estar o no acotada.

Región factible acotada Región factible no acotada

La región factible incluye o no los lados y los vértices, según que las desigualdades sean en

sentido amplio ( o ) o en sentido estricto (< o >).

Si la región factible está acotada, su representación gráfica es un polígono convexo con un

número de lados menor o igual que el número de restricciones.

El procedimiento para determinar la región factible es el siguiente:

1) Se resuelve cada inecuación por separado, es decir, se encuentra el semiplano desoluciones de cada una de las inecuaciones.

Se dibuja la recta asociada a la inecuación. Esta recta divide al plano en dos regiones osemiplanos

Para averiguar cuál es la región válida, el procedimiento práctico consiste en elegir un

punto, por ejemplo, el (0,0) si la recta no pasa por el origen, y comprobar si lascoordenadas satisfacen o no la inecuación. Si lo hacen, la región en la que está esepunto es aquella cuyos puntos verifican la inecuación; en caso contrario, la regiónválida es la otra.

2) La región factible está formada por la intersección o región común de las solucionesde todas las inecuaciones.

Como sucede con los sistemas de ecuaciones lineales, los sistemas de inecuaciones lineales

pueden presentar varias opciones respecto a sus soluciones: puede no existir solución, en el

caso de que exista el conjunto solución puede ser acotado o no.

Veámoslo con un ejemplo:


3/20


Página 33

Dibuja la región factible asociada a las restricciones:

x + y 4

y 4

y x

Las rectas asociadas son: r : x + y = 4 ; s : y = 4 , t: y = x

Elegimos el punto P(0,0), que se encuentra en el

semiplano situado por debajo de la recta.

Introduciendo las coordenadas (0,0) en la

inecuación x + y 4, vemos que no la satisface:

0 + 0 = 0 < 4 . Por tanto, el conjunto de

soluciones de la inecuación es el semiplano

situado por encima de la recta r : x + y = 4 .

Procedemos como en el paso anterior.

Las coordenadas (0,0) satisfacen la

inecuación y 4 ( 0 4) . Por tanto, elconjunto de soluciones de la inecuación

es el semiplano que incluye al punto O.

La recta t asociada a la restricción pasa por

el origen, lo cual significa que si probásemos

con el punto P(0,0) no llegaríamos a ninguna

conclusión. Elegimos el punto (1,0) y vemos

que no satisface la inecuación y x (y = 0 <

1 = x ). Por tanto, el conjunto solución de esta

inecuación es el semiplano determinado porla recta t que no incluye al punto (1,0).

La región factible está formada por los puntos

que cumplen las tres restricciones, es decir,

se encuentran en los tres semiplanos

anteriores.


4/20


Página 34

Método gráfico :

Solución Gráfica de un problema de PL

Problema 1.

La WINDOR GLASS CO produce artículos de vidrio de alta calidad, entre ellos ventanas y

puertas de vidrio. Tiene tres plantas. Los marcos y molduras de aluminio se hacen en la planta

1, los de madera en la planta 2; la 3 produce el vidrio y ensambla los productos.

Debido a una reducción de las ganancias, la alta administración ha decidido reorganizar la línea

de producción de la compañía. Se descontinuarán varios productos no rentables y se dejará

libre una parte de la capacidad de producción para emprender la fabricación de dos productos

nuevos que tienen ventas potenciales grandes:

– Producto 1: una puerta de vidrio de 8 pies con marco de aluminio.

– Producto 2: una ventana corrediza con marco de madera de 4 pies por 6.

El producto 1 requiere de la capacidad de producción en las plantas 1 y 3 y nada en la planta 2.

El producto 2 sólo necesita trabajo en las plantas 2 y 3. La división de comercialización ha

concluido que la compañía puede vender todos los productos que se puedan fabricar en las

plantas. Sin embargo, como ambos productos competirán por la misma capacidad de

producción en la planta 3, no está claro qué mezcla de productos sería la más rentable. Por lo

tanto, se ha formado un equipo de IO para estudiar este problema.

El grupo comenzó a realizar juntas con la alta administración para identificar los objetivos del

estudio y desarrollaron la siguiente definición del problema:

Determinar que tasas de producción deben tener los dos productos con el fin de maximizar las

utilidades totales, sujetas a las restricciones impuestas por las capacidades de producción

limitadas disponibles en las tres plantas. (Cada producto se fabricará en lotes de 20 unidades,

de manera que la tasa de producción está definida con el número de lotes que se producen a

la semana) Se permite cualquier combinación de tasas de producción que satisfaga estas

restricciones, incluso no fabricar uno de los productos y elaborar todo lo que se posible delotro.

El equipo de IO también identificó los datos que necesitan reunir:

Número de horas de producción disponibles por semana en cada planta para estos nuevos

productos. (Casi todo el tiempo de estas plantas estás plantas está comprometido con los

productos actuales, lo que limita la capacidad para manufacturar nuevos productos.)

Número de horas de fabricación que emplea cada lote producido de cada artículo nuevo en

cada una de las plantas.


5/20


Página 35

La ganancia por lote de cada producto nuevo. (Se escogió la ganancia por lote producido como

una medida adecuada una vez que el equipo llegó a la conclusión de que la ganancia

incremental de cada lote adicional producido sería, en esencia, constante, sin importar el

número total de lotes producidos. Debido a que no se incurre en costos sustanciales para

iniciar la producción y comercialización de estos nuevos productos, la ganancia total de cada

uno es aproximadamente la ganancia por lote producido multiplicado por el número de lotes.)

La obtención de estimaciones razonables de estas cantidades requirió del apoyo de personal

clave en varias unidades de la compañía. El personal de la división de manufactura

proporcionó los datos de la primera categoría mencionada. El desarrollo de estimaciones para

la segunda categoría requirió un análisis de los ingenieros de manufactura involucrados en el

diseño de los procesos de producción para los nuevos artículos. Al analizar los datos de costos

obtenidos por estos ingenieros, junto con la decisión sobre los precios de la división de

mercadotecnia, el departamento de contabilidad calculó las estimaciones para la tercera

categoría.

• La tabla siguiente resume los datos reunidos de la información anterior.Planta Tiempo de producción por Lotes, Horas Tiempo de producción

disponible a la

semana, horas Producto

1 2

1 1 0 4 2 0 2 12 3 3 2 18

Ganancias por lote $ 3000 $5000

El primer paso para la resolución del problema de programación es la definición de las

variables de decisión en este caso tenemos dos tipos de producto:

1. Variables de decisión

La función objetivo es lo que queremos optimizar (minimizar o maximizar), por ello está

compuesta por los costos de cada producto, los cuales van acompañado por las variables de

decisión en el caso de la minimización y de utilidades y variables de decisión en el caso de la

maximización. En este problema en particular lo que desea la empresa es encontrar la solución

que maximice sus utilidades. Colocamos 3 en lugar de 3000 y 5 en lugar de 5000, para trabajar

en unidades mas pequeñas; pero al final representa miles de dólares.

2. Función Objetivo

1 x Número de lotes del producto1 fabricado por semana

2 x Número de lotes del producto2 fabricado por semana

Maximizar 2121 53),( x x x x f Z


6/20


Página 36

En este caso las restricciones son las limitantes que tiene la empresa para producir el

producto1 y el producto2. Tenemos 3 restricciones bien definidas, las cuales. Cabe señalar que

las restricciones de no negatividad, siempre es necesario incluirlas, ya que en las respuestas no

pueden resultar valores menores que cero, sino la solución del problema no tendría ningún

sentido.

3. Restricciones

4. Formule el modelo matemático del PPL.

Ahora se puede formular el modelo matemático del problema para lo cual definimos la

función objetivo a maximizar, sujeta a las restricciones que se señalan.

41 x

Horas disponibles en la planta 1, para producir lotes del producto 1

122 2 x Horas disponibles en la planta 2, para producir lotes del producto 2

1823 21 x x Horas disponibles en la planta 3, para producir lotes del producto 1 y producto 2

0

0

2

1

x

x

Restricciones de no negatividad

Máx.

21 53 x x Z

S.a

0

0

1823

122

4

2

1

21

2

1

x

x

x x

x

x


7/20


Página 37

5. Con la forma estándar del modelo, graficamos para encontrar la región factible.

Si hacemos uso del WinQSB los pasos ha seguir son los siguientes

1. Nos vamos a INICIO.

2. Elegimos todos los programas

3. Damos clic derecho izquierdo en WinQSB

4. y elegimos con un clic izquierdo la herramienta Goal Programming.

5. Al cargar el programa nos vamos a archivo y damos clic en nuevo.

6. Aparecerá una nueva ventana que nos muestra:

Título del problema: el título es totalmente opcional cada uno le pueda dar el

nombre que desee.

Número de Goal, es decir número de metas. En este caso queremos encontrar un

solo óptimo por lo cual, la meta es 1.

Número de variables: las variables de decisión, no son más que las que definimos

al inicio, son dos. Entonces escribimos 2.

Número de restricciones: también ya las hemos definido. Son tres restricciones. El

programa ya incluye las restricciones de no negatividad, por lo que solamente

escribimos las otras faltantes 3.

El programa trae la opción de minimización o maximización. Como el nuestro es un

problema de maximización le damos entonces clic en maximización.

Damos clic en aceptar y nos aparecerá una nueva ventana en la cual veremos en la

primera columna C1, C2, C3; estas son las restricciones del problema. Aparece

además en la primer fila la letra Z, allí colocaremos los coeficientes de las variables

de decisión de la función objetivo.

Para tener una mejor interpretación es necesario que cambiamos los nombres a

las restricciones e incluso a las variables de decisión, para ello nos vamos a Edición;

elegimos la opción constraint name y podemos cambiarle el nombre a las

restricciones de igual forma, podemos elegir la opción variable name y definir bien

quien es x1 y x2.

Cuando hemos introducido los coeficientes de la función objetivo y de las

restricciones, entonces podemos irnos a la opción Solve and Analize y elegimos

Graphic Method, dado que nuestra intención es resolverlo por el método gráfico.

Al hacer esto el programa nos mandará a una nueva ventana, la cual nos indica

que variable conforma el eje de las X y cual conforma el eje de las Y, le damos

aceptar y ante nosotros aparecerá un gráfico como el que se muestra a

continuación.


8/20


Página 38

Los pares ordenados que han sido seleccionados son los que acotan la llamada Región Factible,

son las posibles soluciones al problema y son esenciales para descubrir cual es el óptimo. El

siguiente paso es evaluar cada uno de estos puntos y encontrar el que maximice nuestras

utilidades al mayor porcentaje posible.

6. Soluciones factibles.

Valores permitidos 21 , x xde la región factible

Función Objetivo

21 53 x x Z Soluciones factibles

(FEV)

(0,0) )0(5)0(3 Z 0

(0,6) )6(5)0(3 Z 30

(2,6) )6(5)2(3 Z 36

(4,3) )3(5)4(3 Z 27

(4,0) )0(5)4(3 Z 12

Después de haber analizado las soluciones factibles vemos que la que nos da la máxima

utilidad es el punto (2,6)

Esto se interpreta de la siguiente manera:

7. Soluciones óptimas:

Para obtener la máxima utilidad que es de $36,000 tendremos que

producir dos lotes del producto 1 y 6 lotes del producto 2.

(0,6)

(2,6)

(4,3)

(0,0) (4,0)

Región


9/20


Página 39

Problema 2.

Rulisa fabrica masa para pasteles de tipo I y II. La de tipo I la vende a 5 euros el kilo, gastando 1

euro en ingredientes y 2 en mano de obra. La de tipo II se vende a 3 euros y cuestan 1 euro,

tanto los ingredientes como el trabajo. Para hacer las masas se necesitan dos tipos de

actividades: amasado y horneado. Rulisa dispone de 18 horas de amasado y 12 de horneado a

la semana. La masa de tipo I necesita 2 horas de amasado

Y 3 de horneado, mientras que la de tipo II, necesita 3 de amasado y 1 de horneado.

Si la cantidad de masa que se puede vender es ilimitada, optimizar los beneficios semanales de

Rulisa.

Análisis del problema

• Identifiquemos los datos que necesitamos para la para definir el modelo:

– Número de horas disponibles para producción, por semana. (18 para amasado

y 12 para horneado)

– Número de horas que requiere cada tipo de masa (tipo I y II) en amasado y

horneado.

– La ganancia por cada producto (precio de venta - costos de producción) de

cada uno.

La tabla siguiente resume los datos reunidos.

Actividades Tiempo de producción por producto, horas Tiempo de produccióndisponible a la

semana, horas Tipo de masa

I II Amasado 2 3 18 Horneado 3 1 12

Ganancias Por

Producto €2 €1

Para lograr una mejor solución del problema definiremos nuestras variables de decisión, las

cuales son:


1 x Kilogramos de masa I a fabricar semanalmente.

2 x Kilogramos de masa II a fabricar semanalmente.


10/20


Página 40

En este caso la función objetivo estará compuesta por la ganancia obtenida por cada tipo

de masa y por las variables de decisión. El problema que estamos resolviendo es un

problema de maximización.


Dado que este producto requiere de dos operaciones fundamentales (Amasado, Horneado) las

restricciones estarán dadas por la capacidad en horas semanales para estas actividades.

Además colocaremos la restricción de no negatividad.

3. Restricciones

4. Ahora se puede formular el modelo matemático del problema para lo cual definimos

la función objetivo a maximizar, sujeta a las restricciones que se señalaron

anteriormente.

5. Con la forma estándar del modelo, graficamos para encontrar la región factible.

Para graficar la región factible es necesario que conozcamos los puntos por donde pasan las

diferentes rectas por lo que hacemos uso de el método de intercepto. Aunque existen otros

Maximizar

2121 2),( x x x x f z

Tiempo máximo de amasado permitido

Tiempo máximo de horneado permitido

Restricciones de no negatividad

Maximizar 212 x x z

S. a

1832 21 x x

123 21 x x

1832 21 x x

123 21 x x

0

0

2

1

x

x


11/20


Página 41

formas de resolver sistemas de ecuaciones haremos uso de este por considerarlo más sencillo

de utilizar.

Primero cambiamos el signo por el =.

Elegimos de las ecuaciones.

9

2/18

18)0(32

0

1

1

1

2

x

x

x

x

Punto1 (0,6)

Punto2 (9,0) este punto queda descartado dado que no es uno de los vértices de la región

factible

12

12)0(3

0

123

2

2

1

21

x

x

x

x x

Punto3 (0,12)

Punto (4,0) Descartamos este punto dado que No forma parte de la región Factible.

Para encontrar la intercepción de las rectas 1832 21 x x y 123 21 x x usamos el método

de sustitución. Veámoslo a continuación.

Dado que no todos los puntos son parte de la región factible, podemos decir que los vértices

de la región factible son:

6

3/18

183)0(2

0

1832

2

2

2

1

21

x

x

x

x

x x

4

3/12

1203

0

1

1

1

2

x

x

x

x

730

718

187

183692

18)312(32

123

1832

2

1

1

11

11

21

21

x

x

x

x x

x x

x x

x x


12/20


Página 42

Para encontrar la solución óptima es necesario que evaluemos todos los valores de los vértices

en la función objetivo.



Función Objetivo

212 x x Z Soluciones factibles

(FEV)

(0,0) 0)0(2 Z 0

(0,6) 6)0(2 Z 6

(18/7, 30/7) 7/30)7/18(2 Z 66/7

(4,0) 0)4(2 Z 8

La solución óptima se puede analizar de la siguiente manera.


1832 21 x x

123 21 x x

(18/7,30/7)

(0,0)(4,0)

(0,6)

Para alcanzar la máxima utilidad es necesario que la empresa produzca 18/7 kg de masa de

tipo I y 30/7 Kg de masa de tipo II, para alcanzar una utilidad máxima de 66/7 de euros.


13/20


Página 43

GUÍA PRÁCTICA # 2

Solución Gráfica de PPL

Unidad 2: Programación lineal

Contenidos:

• Construcción del modelo de programación lineal.• Solución gráfica del problema bidimensional

Objetivos: A l finalizar la práctica el estudiante adquiera las siguientes habilidades:

Resolver problemas de programación lineal con dos y tres restricciones através del Método Gráfico.

Graficar la región de factibilidad en un sistema de coordenadas, haciendo usode las restricciones del problema de programación lineal.

Hacer uso del IOR Tutoríal para encontrar la región de factibilidad del problemade programación lineal.

Encontrar la solución al problema de programación lineal de dos y tresrestricciones.

I. Resuelva los siguientes problemas por el método grafico.

Problema 1:

La compañía INTEL produce dos dispositivos para computadoras, (producto 1 y

producto 2) y requiere partes de metal y componentes eléctricos. La administración

desea determinar cuantas unidades de cada producto fabricar para maximizar la

ganancia. Por cada unidad del producto 1 se requiere 1 unidad de partes de metal y 2

unidades de componentes eléctricos. Por cada unidad del producto 2 se necesitan 3

unidades de partes de metal y 2 unidades de componentes eléctricos. La compañía

tiene 200 unidades de partes de metal y 300 componentes eléctricos. Cada unidad del

producto 1 da una ganancia de $ 2 y cada unidad del producto 2 da una ganancia de $

3.00

a) formule un modelo de programación lineal.b) Utilice el método grafico para resolver este modelo. ¿Cuál es la

ganancia total que resulta?

MaterialesUnidades de Material para cadadispositivo

Total de unidadesdisponibles decada materialProducto 1 Producto 2

Ganancias por unidad


14/20


Página 44



3. Restricciones

4. Formule el modelo matemático del PPL.Ahora se puede formular el modelo matemático del problema para lo cualdefinimos la función objetivo a maximizar, sujeta a las restricciones quese señalan.

5. Con la forma estándar del modelo, graficamos para encontrar la regiónfactible.

Forma estándar del modelo:


15/20


Página 45



Función Objetivo Soluciones factibles(FEV)


Problema 2:

Una fábrica de bombones tiene almacenados 500 Kg.. de chocolate, 100 Kg.. de

almendras y 85 Kg.. de frutas. Produce dos tipos de cajas: las de tipo A contienen 3

Kg. de chocolote, 1 Kg. de almendras y 1 Kg. de frutas; la de tipo B contiene 2 Kg. de

chocolate, 1,5 Kg. de almendras y 1 Kg. de frutas. Los precios de las cajas de tipo A y

B son 13 y 13,50 €, respectivamente. ¿Cuántas cajas de cada tipo debe fabricar para

maximizar sus ventas?


16/20


Página 46

Caja tipo A Caja tipo B Disponibles

Chocolate

Almendras

Frutas

Precio en euros

1. Variables de decision



17/20


Página 47

Restricciones

3. Formule el modelo matemático del PPL.Ahora se puede formular el modelo matemático del problema para lo cualdefinimos la función objetivo a maximizar, sujeta a las restricciones que

se señalan.




18/20


Página 48





Problema 3:

Un laboratorio de Cómputos, almacena, al menos 300 Computadoras de un tamaño y

400 de un segundo tamaño. Se ha decidido que el número total de computadoras

almacenadas no debe exceder de 1200. Determine las cantidades posibles de estos

dos tipos de computadoras que pueden almacenarse.

RestriccionesTipo de Computadoras Total

ComputadorasComputadora 1 Computadora 2

Tipos de Computadoras



3. Restricciones


19/20


Página 49

4. Formule el modelo matemático del PPL.Ahora se puede formular el modelo matemático del problema para lo cualdefinimos la función objetivo a maximizar, sujeta a las restricciones que

se señalan.



Valores permitidos 21 , x x

de la región factible





20/20


Página 50

El Método Simplex

Para la solución de un problema de PL

Para resolver los problemas de PL se utilizan varios Algoritmos. El más antiguo y más

utilizado sigue siendo el Algoritmo del Simplex debido a Dantzig.

La solución de los problemas de programación lineal parte de dos teoremas

fundamentales:

El conjunto factible de un problema de PL puede representarse mediante un

poliedro convexo.

Si un PL tiene solución óptima y finita ésta se encuentra en uno de los vértices

del poliedro convexo.

De ellos se deduce que:

Puesto que el número de vértices de un poliedro factible es finito, el número de

posibles soluciones de un PL también es finito.

Esto sugiere, inicialmente, un algoritmo para calcular la solución óptima:

Calcular el valor de la función objetivo en cada vértice del conjunto factible y escoger

el mejor. Sin embargo, el número de vértices de un conjunto factible es:

m = número de restricciones

n =número de variables

Ejemplo: Sí m=3; y n=2; entonces el número de Vértices=10

El concepto de vértice es de naturaleza geométrica y es poco adecuado para construir

un algoritmo utilizable por ordenadores.

Conceptos importantes:

Variable básica: Una de las variables restantes, diferentes a las no-básicas, de unprograma lineal en forma estándar (igual en número al total de restricciones de

igualdad)

Variable no básica: conjunto seleccionado de variables de un programa lineal enforma estándar (en número igual al total de variables menos el número de

restricciones de igualdad) cuyos valores se toman como cero.

Forma estándar : Una forma particular de un problema de programación lineal en elque la función objetivo debe ser maximizada; solamente existen restricciones de

igualdad y todos los lados derechos de las variables son no negativos

m)!-n(mm!

n)!(m

m

nm

Apuntes PL Metodo Grafico

Documents

Transcript of Apuntes PL Metodo Grafico