Programacion Lineal Completa.docx

PROGRAMACION LINEAL

DESIDERIO PADILLA GARCIA

Dr en Ciencias de la Educación

Docente U.P.C.

PROGRAMACION LINEAL DEFINICION Es una técnica que se vale de los modelos matemáticos lineales y la informática para resolver problemas del mundo real, tomando decisiones acertadas que garanticen optimizar los recursos

TERMINOLOGIA

Investigación de Operaciones

Es el termino mas general con el cal se conoce esta técnica, la investigación de operaciones consta de dos partes :una la Programación Lineal constituida por todos aquellos problemas que se pueden plantear con el modelo de ecuaciones de primer grado o lineales y la otra la programación no lineal que se plantea con modelos de ecuaciones de diferentes grados. También podemos encontrar la Investigación de Operaciones con los nombre de : El Estudio de los Métodos Cuantitativos

para Resolver Problemas de la

Administración y el Estudio de los Modelos Cuantitativos Problemas de la Administración.

para Resolver

JUSTIFICACIÓN

Colocar al alcance del estudiante una herramienta para

resolver problemas de la

Investigación de Operaciones con cualquier número de variables, que manualmente son muy complejos de resolver, ofreciendo soluciones con unos datos confiables, ágiles e instantáneos. El texto se hace como una guía de consulta obligatoria en la función básica de sistematización del proceso educativo en la enseñanza de la Programación Lineal y no lineal, por otra parte sirve de instrumento didáctico de la enseñanza teórica frente al desarrollo de la práctica en la solución de los modelos matemáticos de la Programación Lineal y no lineal, de esta forma se hace participe al estudiantado con una mejor preparación del desarrollo institucional y se crea un proceso dinámico para que los estudiantes puedan adaptarse al medio en el ejercicio de sus profesiones.

Se requiere para la toma de decisiones ejecutivas, que consiste en: – El arte de modelar situaciones complejas, – La ciencia de desarrollar técnicas de solución para resolver dichos modelos. – La capacidad de comunicar efectivamente los resultados en la planeación , programación y ejecución .

OBJETIVO GENERAL

El Objetivo de la Programación Lineal

es Aportar a la toma de decisiones sistemas

complejos. Estudiar la asignación óptima de recursos escasos a determinada actividad. Evaluar el rendimiento de un sistema con objeto de mejorarlo. Obtener de la información resultados

cuantitativos

para

optimizar

los

recursos.

Mejorar

procedimientos

tradicionales: opiniones de expertos, reglas simples. Lograr flexibilidad y bajos costos. Conocer las limitaciones de los modelos determinísticos. Conocer y aplicar las metodologías y herramientas científicas básicas de la Programación Lineal mediante la construcción de modelos, conllevan a la resolución de problemas y su optimización, bajo situaciones de disponibilidad de recursos escasos. .

OBJETIVOS ESPECÍFICOS

Facilitar el proceso de aprendizaje de la programación lineal y no lineal. -

Servir de herramienta práctica para la solución de problemas del mundo real, en el campo de la programación lineal, con cualquier número de variables.

-

Desarrollar en el gestor educativo cualidades y destrezas en el análisis para la toma de decisiones cuantitativas acertadas, que contribuyan a la optimización de los recursos escasos disponibles (y a su cualificación).

Ofrecer a los estudiantes una comprensión conceptual y práctica en el uso del método SIMPLEX de la programación lineal en la optimización de los recursos escasos.

Servir de guía técnica y experimental, que propenda la cualificación del profesional en la Administración de los recursos.

Servir de guía para solucionar problemas relacionados con las actividades industriales y de servicios, optimizando los costos e ingresos que permitan la dinámica efectiva del proceso en la planeación, programación y organización administrativa.

Desarrollar al estudiante la capacidad de interpretación económica del resultado obtenido en la optimización.

PROGRAMACION LINEAL

1. CONCEPTOS BÁSICOS DE LA PROGRAMACIÓN LINEAL

1.1.1.

Formulación del problema.

Un problema de programación lineal se puede formular de la siguiente manera:

Dados los números reales o parámetros Cj, bi, aij, ( i = 1, 2, 3, ....m ; j = 1, 2, 3, ... n). Se desea optimizar el objetivo. Sujeto a m restricciones, por los recursos escasos.

1.1.2.

Variables de decisión

Es el conjunto de variables cuya magnitud deseamos determinar resolviendo el modelo de la programación lineal, dan respuesta a la pregunta hecha en la formulación del problema, estas las representamos por Xj j = 1, 2, . . . n 1.1.3.

Función objetivo (F.O)

La función objetivo la denominamos las variables de decisión

Z, es la función matemática que relaciona

Xj

j = 1, 2, 3 . . . n.

1.1.4. Restricciones

Las

restricciones

están

constituidas

por

el

conjunto

de

ecuaciones

y

desigualdades que limitan los valores que puedan tomar las variables de decisión en la solución, debido a la escasez de los recursos. (m número de restricciones)

1.1.5. Linealidad

Las relaciones entre las variables en la función objetivo, al igual que en las restricciones deben ser lineales; es decir, debe formularse el problema como un modelo de programación lineal.

1.1.6. Desigualdades cerradas

Las desigualdades usadas para representar las restricciones tienen que ser cerradas o flexibles, esto quiere decir, menor o igual o mayor o igual, no se permiten restricciones abiertas.

1.1.7. Condición de no-negatividad

Las variables en el modelo matemático de la programación lineal sólo puede tomar valores de cero o positivos, no se permiten variables con valores negativos.

2.

EL MODELO MATEMÁTICO GENERAL DE LA PROGRAMACION LINEAL

El modelo matemático de la programación lineal tiene la siguiente estructura: Maximizar

Z = C1 X1 + C2 X2 + ... + Cn Xn Sujeto a:

a11x1 + a12x2 +

...

+a1xn



a21x1 + a22x2 +

...

+a2xn



. . .

. . .

am1 X1 + am2x2 +

...

+am1xn 

xj  0 para j = 1, 2, …n

b1 b2

. . . bm

Éste modelo lo podemos expresar en forma condensada como sigue: haciendo uso de sumatorias o de anotación matricial.

Maximizar Z

  Cj X j

j = 1, 2, ... n

Sujeto a:

ax ij

j

Xj 0 Max. Z =

 bi

para i = 1, 2, ...m

J = 1,2 ...n

para j = 1, 2, ... n

c x

Sujeto a :

AX  b X  0 Donde la función Z es la función objetivo que se desea optimizar sujeta a las restricciones. Xj representa las variables de decisión cuyos valores deseamos conocer.

Cj , a ij y bi son parámetros

El vector renglón

Cj =



C1 , C2 , . . . , Cn ]

Se llama el “ vector de costos unitarios “ o “vector de precios unitarios “.

El Vector

b

b1 b2 . . . bm

b

El Vector b Es el vector de disponibilidad de recursos, es un vector columna.

La matriz A de valores aij se llama “matriz de coeficientes tecnológicos” o “matriz de uso o consumo”.

A=

.a11 .a21 . . . .am1

a12 a22

. . . . . .

a1n a2n

am2

. . .

amn

X1

X  Las Decisión

X es un vector columna

variables de

X2 . . . Xn

A=



a1 a2 a3 ... an



a j = Vector formado por el vector correspondiente a cada columna de la matriz A ; se denominan vectores de actividad.

Xj



0 para j = 1, 2, . . . n

Representa la condición de no-negatividad de las variables del sistema matemático.

X es un vector columna de las variables de decisión. En las m

restricciones del modelo matemático no se incluye la condición de no negatividad X  0 , ya que esta es una condición y no una restricción.

Aplicación en la construcción de modelos matemáticos de la programación lineal a partir de la formulación de problemas : Problema de producción La compañía P G. produce dos tipos de radios y compra distintas partes de los radios a otra compañía local y los arma en su planta. El radio tipo I necesita 5 horas de montaje y el tipo II necesita 3 horas. Se dispone diariamente de 105 horas en el departamento de montaje, la compañía puede gastar hasta U$ 70 para comprar los elementos de los radios. Utiliza U$ 2 de material para el radio tipo I y U$ 4 para el radio tipo II, se pueden vender todos los que se producen y gana U$ 20 netos al vender cada unidad de radio tipo I y U$ 16 al vender cada unidad tipo II.

La compañía P y G pide que se calculen cuántas unidades de cada uno de los radios se deben producir para maximizar la utilidad.

Nota: los datos están en miles de unidades.

3.1

Modelo matemático

Planteamiento Variables de decisión

Sea: x1 = Número de unidades del radio tipo I a producir. x2 = Número de unidades del radio tipo II a producir. F. O.1

Maximizar

Z = 20 X1 + 16 X2

Sujeto a: Restricciones. 1.

5 X1 + 3 X2  105

2.

2 X1 + 4 X2 

N. N. 2

X1 X2  0

70

Convertir las desigualdades a igualdades o pasar a la forma estándar. Igualar.

(0)

Z = 20X1 + 16X2 + 0X3 + 0X4

(1)

5X1 + 3X2 + X3 = 105

(2)

2X1 + 4X2 + X4 = 70 X1’ X2’ X3’ X4’  0

Problema de mezcla 1 2

Función Objetivo No Negatividad

16. La Compañía Moreno Ltda.. fabrica fertilizantes especiales para clientes del mercado de cítricos. La Compañía acaba de recibir un pedido de 1000 toneladas de un fertilizante que debe satisfacer las siguientes especificaciones.

a.

Cuando menos un 20% de nitrógeno.

b.

Cuando menos un 30% de potasio.

c.

Cuando menos un 8% de fosfato.

La Compañía ha adquirido cuatro mezclas de fertilizantes a partir de los cuales puede fabricar sus fertilizantes especiales. Los porcentajes de potasio, nitrógeno y fosfato que contienen los fertilizantes básicos son:

Porcentaje de Fertilizante Nitrógeno

Potasio

Fosfato

1

40

20

10

2

30

10

5

3

20

40

5

4

5

5

30

Básico

El porcentaje restante de cada fertilizante básico consta de ingredientes inertes. Los costos de los fertilizantes básicos respectivos son $16, $12, $15, y $ 8 por tonelada. El objetivo es minimizar los costos. Plantear el modelo matemático.

MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN Sea:

Xj = El número de toneladas de cada uno de los fertilizantes básicos que deben incluirse en la mezcla de las 1000 toneladas. j = 1, 2, 3, 4

FUNCIÓN OBJETIVO

Mín Z = 16X1 + 12X2 + 15X3 + 8X4

Sujeto a: 1) 0.40X1 + 0.30X2 + 0.20X3 + 0.05X4  200 2) 0.20X1 + 0.10X2 + 0.40X3 + 0.05X4  300 3) 0.10X1 + 0.05X2 + 0.05X3 + 0.30X4  80 4)

X1 +

X1 ,

X2 +

X2 , X 3 , X4

X3 +



0

X4 = 1000

Problema de publicidad El Gerente de Mercadotecnia de una compañía que vende productos

19.

alimenticios dietéticos está considerando la promoción de un nuevo producto. El presupuesto de publicidad de la compañía incluye U$ 80000 para este fin.

La compañía puede hacer publicidad al nuevo producto a través de comerciales en televisión y / o anuncios en revistas. Cada comercial de televisión cuesta U$ 10000, pero se ha estimado que esos comerciales los ven 60000 personas.

Cada anuncio de revista cuesta U$ 6500, se estima que 35000 personas ven esos anuncios. Debido a que la compañía controladora de la empresa que vende alimentos dietéticos también tiene inversiones en diversas imprentas, los administradores de primer nivel han dado instrucciones al Gerente de mercadotecnia de que coloque cuando menos tres anuncios de revistas.

El Gerente de mercadotecnia ha decidido que la compañía debería tener cuando menos tantos comerciales de televisión como anuncios en revistas.

Formule el modelo de Programación Lineal para este problema.

MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN

Sea : X1 X2

= Cantidad de dinero a invertir en comerciales de televisión. = Cantidad de dinero a invertir en anuncios de revistas.

FUNCIÓN OBJETIVO

Max Z

= 60000X1 + 35000X2

Sujeto a: 1)

10000X1 + 6500X2  80000 X2  3

2) 3)

X1 -

X2 = 0

X1 ,

X2  0

UN PROBLEMA DE INVERSION

Problema 1. Disponemos de 210.000 euros para invertir en bolsa. Nos recomiendan dos tipos de acciones. Las del tipo A, que rinden el 10% y las del tipo B, que rinden el 8%. Decidimos invertir un máximo de 130.000 euros en las del tipo A y como mínimo 60.000 en las del tipo B. Además queremos que la inversión en las del tipo A sea menor que el doble de la inversión en B. ¿Cuál tiene que ser la distribución de la inversión para obtener el máximo interés anual? Solución Plantear el modelo matemático de programación lineal. Sea x a la cantidad que invertimos en acciones de tipo A , y a la cantidad que invertimos en acciones de tipo B

Acciones

Inversión

rendimiento

Tipo A

X

0,1x

Tipo B

Y

0,08y

Función objetivo Maximizar

z = 0,1x+0,08y

Sujeto a: Condiciones que deben cumplirse (restricciones):

R1 X + y <= 210.000 inversión total

<=

R2 X

130.000 inversión tipo A

R3 y > = 60.000 inversión tipo B R4

x -2y <= 0 relación de inversiones

Condición de no negatividad

El problema de las vitaminas 11.

Se quiere obtener la cantidad de leche, carne y huevos que satisfacen

determinada dieta nutritiva en cuanto a vitamina A, B y C. Suponga que el número de miligramos de cada una de estas vitaminas, contenidas por unidad de producto se muestra en la siguiente tabla:

VITAMINAS

Gl. de LECHE

Lb. DE CARNE

Doc. De HUEVOS

A

1

1

10

B

100

10

10

C

10

100

10

Las cantidades mínimas requeridas diariamente son :

Vitamina A un miligramo; Vitamina C 50 miligramos y Vitamina D 10 miligramos. Los costos son: Galón de leche U$ 4; libra de carne U$ 10 y huevos U$ 1.5 la docena.

Formule el modelo de Programación Lineal para este problema. MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN

Sea:

X1 = Cantidad de galones de leche a comprar para producir la dieta.

X2 = Cantidad de libras de carne a comprar para producir la dieta. X3 = Cantidad de docenas de huevos a comprar para producir la dieta.

FUNCIÓN OBJETIVO

Min Z = 4X1 + 10x2 + 1.5X3

Sujeto a : Restricciones

1) 2) 3)

X1 +

X2 + 10X3  1

100X1 + 10X2 + 10X3  50 10X1 +100X2 + 10X3  10 X1 , X2 , X3  0

LA SOLUCION GRAFICA

SOLUCIONES GRAFICAS Gráficamente Se puede resolver un problema de programación lineal que tenga sólo dos variables de decisión, ya que en un plano solamente contamos con dos dimensiones, el método de solución grafico es restringido, pero lo utilizamos pedagógicamente como un método apropiado para el aprendizaje, con el cual podemos apropiarnos de de los conocimientos,(saber),actitudes (querer hacer ) y las habilidades(saber hacer),sobre lo que se refiere a las soluciones de un modelo matemático de la Programación Lineal.

PROCEDIMIENTO 1. Graficar todas las restricciones, una por una y de finir el área de soluciones factibles para cada restricción. 2. simultáneamente, en la medida que vamos haciendo la gráfica vamos construyendo el área de soluciones factibles (Esta es el área común a todas las restricciones). 3.

Encontramos la solución optima

Se comienza: 1. graficando todas las restricciones una a una, sobre un sistema de ejes coordenados, colocamos los valores de X1, (x) en el eje horizontal y los valores de X2,(y) en el eje vertical.( la gráfica de una igualdad es una recta, la gráfica de una desigualdad es un semiplano, a un lado de la recta) El siguiente paso consiste en determinar qué puntos solución corresponden al área de soluciones factibles para el programa lineal. Se requiere que tanto X1 (x)como X2

(y)

: sean no negativas, y por ello sólo es necesario

considerar la porción de la gráfica en la que

X1 ≥0

y

X2 ≥0.

Solo nos interesa la Grafica en el cuadrante

X 1 ≥0

y

X2 ≥0. Es el

único cuadrante del sistema coordenado que cumple con el concepto de no negatividad.

Que corresponde al primer cuadrante o cuadrante de arriba a la derecha del sistema de ejes coordenados , éste cuadrante en su totalidad señala la porción de la región de soluciones en donde se satisfacen esos requisitos de no negatividad , en términos generales. Como siempre se requiere que las variables decisorias de la programación lineal sean no negativas. la gráfica que se obtengan en cada restricción o general, mostrarán sólo la porción de la región de soluciones factibles que corresponde a los valores no negativos de las variables de decisión. Una solución factible es aquella que cumple con la condición de no negatividad.

LA grafica de una igualdad son los puntos sobre esa recta. Para trazar una recta buscamos dos puntos solución que satisfagan la ecuación y trazamos una recta por tales puntos.

Para buscar un punto solución le damos un

valor cualquiera a una de las variable y

despejamos la otra. Luego le damos un

valor cualquiera

a la otra variable y

despejamos la anterior. Por conveniencia le podemos dar valores cero a las variable para obtener los dos puntos cuando la recta no pasa por el origen. Si la recta pasa por el origen ( por ejemplo 2x ≥0. 0 sea que el valor a la derecha del signo sea cero ) solo para el primer valor le podemos dar un valor de cero, para el segundo valor debe dársele un valor diferente de cero Y obtenemos los dos puntos solución para trazar la recta. coordenados(por conveniencia).

NOTA: LA grafica de una desigualdad es un semiplano a un lado de la recta

Para encontrar el semiplano solución, tomamos un punto cualquiera a un lado de la recta y remplazamos el valor de sus coordenadas en la ecuación, si el resultado es consecuente el punto pertenece al semiplano solución. Por ejemplo si tomamos la ecuación 25X1 + ½ X2 <= 20 Trazamos la recta 25X1 + ½ X2 = 20,tomamos un punto a un lado de la recta por ejemplo p (40, 30 ) , remplazamos estos valores en la ecuación 25 x 40 + ½ x 30 <= 20 200

+ 15

<= 20

215 <= 20 no es consecuente por que 215 no es menor que 20 el punto p (40, 30) no pertenece al semiplano solución luego la el semiplano solución es el del otro lado de la recta

Grafica de la desigualdad

25 x 40 + ½ x 30 <= 20

Grafica de la inecuación

1/5 X2 <= 5

Grafica de la inecuación 2X1 – X2 <= 100

Grafica de la inecuación X1 - X2 < =

0

SOLUCION ÓPTIMA

Para encontrar la solución optima buscamos los valores de la función objetiva f(z) en los puntos extremos del aérea de las soluciones factibles y si estamos maximizando la solución optima será el mayor valor encontrado ., pero si estamos minimizando será el menor valor la solución optima.

ANALISIS

Luego hacemos el análisis de la solución optima tomando los valores optimos

y

remplazándolos en cada restricción podemos ver que holgura nos resulta si se trata de una ecuación con signo



o que excedente si se trata de una restricción del

cumplen las proporcionalidades en la igualdad.=

APLICACIÓN DE LA SOLUCION GRAFICA

 o si se

UN PROBLEMA DE INVERSION

Problema 1. Disponemos de 210.000 euros para invertir en bolsa. Nos recomiendan dos tipos de acciones. Las del tipo A, que rinden el 10% y las del tipo B, que rinden el 8%. Decidimos invertir un máximo de 130.000 euros en las del tipo A y como mínimo 60.000 en las del tipo B. Además queremos que la inversión en las del tipo A sea menor que el doble de la inversión en B. ¿Cuál tiene que ser la distribución de la inversión para obtener el máximo interés anual? Solución Plantear el modelo matemático de programación lineal. Sea x a la cantidad que invertimos en acciones de tipo A , y a la cantidad que invertimos en acciones de tipo B

Acciones

Inversión

rendimiento

Tipo A

X

0,1x

Tipo B

Y

0,08y

Función objetivo Maximizar

z = 0,1x+0,08y

Sujeto a: Condiciones que deben cumplirse (restricciones):

R1 X + y <= 210.000 inversión total R2 X

<=

130.000 inversión tipo A

R3 y > = 60.000 inversión tipo B R4

x -2y <= 0 relación de inversiones

Condición de no negatividad Dibujamos las rectas auxiliares asociadas a las restricciones para conseguir el área de soluciones factibles (conjunto de puntos que cumplen esas condiciones) r1

r2 (paralela a OY)

r3(paralela a Ox

r4

X

y

X

y

x

y

x

y

0

210000

130000

0

0

60000

0

0

210000

0

130000

65000

E

D A B

C

Grafica N° 1

A(0, 60000), B(120000, 60000), C(130000, 65000), D(130000, 80000) y E(0, 210000) La región factible, o el área de soluciones factibles es la pintada de amarillo, de vértices A, B, C, D y E o el polígono ABCDE.

La función objetivo es;

F(x, y) Maximizar Z = 0,1x+0,08y Si dibujamos la recta F(x, y) =0 (en rojo) y la desplazamos se puede comprobar gráficamente que el vértice mas alejado es el D, y por tanto es la solución óptima. Comprobarlo analíticamente (es decir comprobar que el valor máximo de la función objetivo, F, se alcanza en el vértice D)

ENCONTRAR LA SOLUCION OPTIMA EXPLORANDO LOS VALORES DE LA FUNCION OBJETIVA EN LOS PUNTOS EXTREMOS

PUNTOS EXTREMOS

X

Y

Z

A

0

60 000

4 800

B

120 000

60 000

16 800

C

130 000

65 000

18 200

D

130 000*

80 000*

19 400*

E

0

21 0000

16 800

NB. Para encontrar las coordenadas del punto de corte de

dos rectas, se resuelve el sistema de las dos ecuaciones Z(A)=

4.800

Z(E) = 16.800

Z(B) = 16.800 Z(C) = 18.200 Z(D) = 19.400

Tomamos los valores de la mayor Z porque estamos maximizando

La solución optima es : Z*(C) = 19.400

X* = 130.000

Y* = 80.000

ANALISIS

Tomamos la R1 R1 X + y <= 210.000 inversión total

Remplazamos los valores de la solucion optima en ella X*= 130.000

y*= 80.000

Tenemos : Consumo de la solución optima 130.000 + 80.000 210.000

<=

disponibilidad

<=

210.000

<=

210.000

210.000

=

210.000

Significa: La Solución óptima Consumió exactamente

los 2100 disponible

Sigue la R2

R2 X

<=

130.000 inversión tipo A

Remplazamos los valores de la solucion optima en ella X*= 130.000

y*= 80.000

Tenemos :

130.000 <= 130.000 130.000=130.000 la inversión tipo A fue exactamente

En estos casos no existe holgura, la holgura es cero Sol optima + holgura

= disponibilidad

Para todos los casos <=

Sigue la R3

R3 y > = 60.000 inversión tipo B

130.000

Remplazamos los valores de la solucion optima en ella X*= 130.000

y*= 80.000

Tenemos

80.000 >= 60.000 Entonces 80.000

igualamos al lado derecho -

20.000

= 60.000

Solución - excedente

= disponibilidad

Óptima

O sea : la solución optima consume 80.000 excede en 20.000 de lo que se dispone.

quiere decir que se

Cuando una restricción es de signo >= existe un excedente igual a la diferencia entre el con sumo optimo y la disponibilidad. Cuando las dos cantidades son iguale disponibilidad ) el excedente es igual a cero.

Sol optima – excedentes Para todos los casos

PROBLEMA 2

>=

= disponibilidad

(consumo

optimo

=

En una pastelería se hacen dos tipos de tortas: Vienesa y Real. Cada torta Vienesa necesita un cuarto de relleno por cada Kg. de bizcocho y produce un beneficio de $,250 mientras que una torta Real necesita medio Kg. de relleno por cada Kg. de bizcocho y produce $400 . de beneficio. En la pastelería se pueden hacer diariamente hasta 150 Kg. de bizcocho y 50 Kg. de relleno, aunque por problemas de maquinaria no pueden hacer mas de 125 tortas de cada tipo. ¿Cuántas tortas Vienesas y cuantas Reales deben vender al día para que sea máximo el beneficio? Solución En primer lugar hacemos una tabla para organizar los datos: Tipo

Nº

Bizcocho

Relleno

Beneficio

T. Vienesa

x

X

0,250x

$250

T. Real

y

Y

0,500y

$400

150

50

Función objetivo máximo beneficio: f(x, y) z=250x+ 400y

Sujeta a : LAS RESTRICCIONES

 150

r1

x+y

r2

0,25x + 0,5y

r3

x

 50

 125 biscocho

 125 relleno

r4

y

CNN

X ≥0

y ≥0.

Consideramos las restricciones y dibujamos la región factible: Se buscan los puntos de corte de cada recta con el sistema de ejes coordenado y trazamos cada recta, NB. ninguna reta pasa por el origen. Para X

Y

0

150

r1

x + y =150

150 0

Para

r2 0.25x + 0.5y=50, ó x + 2y=200

Multiplicando x40 todos los términos

x

Y

0

100

200

0

La otras dos son paralelas a los ejes

Al eje OY

x=125

Al eje Ox

y =125

La región factible o area de soluciones factibles se ha coloreado de amarillo: r3 r4 D

C B r2

O A

r1

Grafica N° 2

Encontremos los vértices: El O(0,0), el A(125, 0)

y el D(0, 100) se encuentran directamente

(son las intersecciones con los ejes coordenados) Se observa que la restricción y

es redundante (es decir “sobra”)

Las coordenadas de B se obtienen resolviendo el sistema: X+y=150 X=125 Cuya solución es: X=125, Y=25 B(125, 25)

Las coordenadas de C se obtienen resolviendo el sistema

 150

r1

x+y

r2

x + 2y

 200

por reducción obtenemos y=50, x=100 C( 100,50)

Los vértices de la región son O(0,0), A(125,0), B(125,25) y C(100,50) y D(0,100), que constituyen el area de soluciones factibles , el polígono OABCD ( grafica color amarillo)

BUSCAMOS LA SOLUCIÓN OPTIMA

SE ENCUENTRA LA SOLUCION OPTIMA EXPLORANDO LOS VALORES DE LA FUNCION OBJETIVA EN LOS PUNTOS EXTREMOS

Lo comprobamos con el método analítico, es decir usando el teorema que dice que si existe solución única debe hallarse en uno de los vértices o puntos extremos del área de soluciones factibles

PUNTOS EXTREMOS

X

Y

Z

0

0

0

0

A

125

0

31.250

B

125

25

41.250

C

100*

50*

45.000*

D

0

100

40.000

Encontramos :

Z(O) = 0

Z(A) = 31.250

Z(B) = 41,250

Z(C) =45,000

Z(D) = 40.000

La solución optima es : Z*(C) = 45.000

Y* = 50

X* = 100

Se ve gráficamente que la solución es el punto C* (100, 50), ya que es el vértice mas alejado (el último que nos encontramos al desplazar la rectas 250x+400y=0 ) Lo comprobamos con el método analítico, es decir usando el teorema que dice que si existe solución única debe hallarse en uno de los vértices La unción objetivo era: f(x, y)=250x+400y, sustituyendo en los vértices obtenemos Z(A) =f(125,0)=31.250(D) = (0,100)=40.000

El máximo beneficio es 45.000 y se obtiene en el punto (100, 50) Conclusión: se tienen que vender 100 tortas vienesas y 50 tortas reales.

ANALISIS: Tomamos la r1 En las restricciones siempre consideramos el lado izquierdo del signo como lo consumido por la solución optima y el lado derecho la disponibilidad y si el signo es



la forma general es :

r1



x+y

consumo de la solución optima

+ holgura

=

150 disponibilidad

Remplazamos los valores de la solución optima en ella X*= 100

y*= 50

Tenemos : 100 + 50 <= 1500 150 Consumo de la Solución optima

+ 0

150

holgura

=

Solución optima

<=

150

=

disponibilidad

150 disponibilidad

Consumió Significa que la solución optima consumio exactamente igual a los 150 disponible

de biscocho 150

Sigue la r2 r2

0,25x + 0,5y

 50

Remplazamos los valores de la solución optima en ella X*= 100 Tenemos :

y*= 50

25 + 25 <= 50 50=50 la solución optima consumio 50 exactamente igual a los 50 disponibles.

Sigue la R3 r3

x

 125

Remplazamos los valores de la solución optima en ella X*= 100

y*= 50

Tenemos :

100

 125 tortas

100

Solución

+

25

=

Holgura

125

Disponibilidad

Optima

O sea : la solución optima consume 100 quiere decir que tenemos una holgura de 25 en la disponibilidad de 125. Cuando una restricción es de signo <= existe una holgura igual a la diferencia entre el con sumo optimo y la disponibilidad.

Cuando las dos cantidades son disponibilidad ) la holgura es cero.

iguale

(consumo

optimo

=

Nota la holgura se considera un sobrante.

r4

y

 125 vienesa

Remplazamos los valores de la solución optima en ella X*= 100

y*= 50

Tenemos :

50

 125 tortas

50

Solución

+

75

=

Holgura

125

Disponibilidad

Optima

O sea : la solución optima consume 50 quiere decir que tenemos una holgura de 75 en la disponibilidad de 125.

En el caso de signo mayor o igual la holgura se combierte en un excedendte consumido por la solución optima comparada con la disponibilidad.

Problema 3. Una escuela prepara una excursión para 400 alumnos. La empresa de transporte tiene 8 autocares de 40 plazas y 10 autocares de 50 plazas, pero solo dispone de 9 conductores. El alquiler de un autocar grande cuesta 80 euros y el de uno pequeño, 60 euros. Calcular cuantos de cada tipo hay que utilizar para que la excursión resulte lo mas económica posible para la escuela. Solución Es un problema de programación lineal, en este caso lo que queremos es hacer mínima la función objetivo. Llamamos x al nº de autocares de 40 plazas e y al nº de autocares de 50 plazas que alquila la escuela.

Entonces se tiene x

,y

Como sólo hay 9 conductores se verifica que: x +y Como tienen que caber 400 alumnos se debe de verificar: 40x +50y

, que simplificada quedaría 4 x +5y

Por lo tanto las restricciones que nos van a permitir calcular la región factible (conjunto de puntos solución donde se cumplen todas las condiciones) son Función objetivo de mínimo costo: Minimizarf(x, y) z=60x+ 80y

Sujeta a : LAS RESTRICCIONES

r1

x

8

r2

y

 10

r3 r4

CNN

x+ y

9

4x + 5y ≥ 40.

X ≥0

y ≥0.

Dibujamos las restricciones

r1

r2

r4

r3

X

y

X

y

X

y

X

y

8

0

0

10

0

9

0

8

9

0

10

0

8

r1

x

r1

x =8

Se encuentra la región factible o el área de soluciones factibles en el dibujo es la parte amarilla.

r2

B C

r1

A

r4

r3

 10

r2

y

r2

y = 10

El area de soluciones factibles es el polígono ABC (amarillo) Los vértices son C(0, 8) de la recta r4,B(0, 9) de r3 y el A(5, 4), este último es el punto de intersección de las rectas r3 y r4 r3 r4

x+ y

9

4x + 5y ≥ 40.

A sus coordenadas salen al resolver el sistema r3 y r4

restando ambas ecuaciones se tiene x =5 y sustituyendo en la 1ª ecuación, y =4 Resolviendo gráficamente se llega a que el punto (5, 4) es la solución del problema. La solución óptima . Comprobarlo sustituyendo en F(x, y) todos los vértices y que este es el que da menor valor (método analítico).

SE ENCUENTRA LA SOLUCION OPTIMA EXPLORANDO LOS VALORES DE LA FUNCION OBJETIVA EN LOS PUNTOS EXTREMOS

Lo comprobamos con el método analítico, es decir usando el teorema que dice que si existe solución única debe hallarse en uno de los vértices o puntos extremos del área de soluciones factibles

Minimizar

z=60x+ 80y

Z(A)= 60x 5 + 80x4 = Z (C) = 80x8 Z (B) = 80 x 9 =

= 640 720

300+ 320 =

620

PUNTOS EXTREMOS

X

Y

Z

A

5*

4*

B

0

9

720

C

0

8

640

La solución optima es Z minima : Z*(A) = 620

Y* = 4

620*

X* = 5

PROBLEMA 4 4. Una compañía posee dos minas: la mina A produce cada día 1 tonelada de hierro de alta calidad, 3 toneladas de calidad media y 5 de baja calidad. La mina B produce cada día 2 toneladas de cada una de las tres calidades. La compañía necesita al menos 80 toneladas de mineral de alta calidad, 160 toneladas de calidad media y 200 de baja calidad. Sabiendo que el costo diario de la operación es de 2000 euros en cada mina ¿cuántos días debe trabajar cada mina para que el coste sea mínimo?. Solución Organizamos los datos en una tabla:

días

Alta calidad

Calidad media

Mina A

x

1x

3x

5x

2000x

Mina B

y

2y

2y

2y

2000y

80

160

200

La función objetivo C(x, y)=2000x + 2000y

Las restricciones son:

Baja calidad

Coste diario

La región factible la obtenemos dibujando las rectas auxiliares: r1 + 2y=80, r2

x

3x + 2y= 160 y r3 5x + 2y=200 en el primer cuadrante y

considerando la región no acotada que determina el sistema de restricciones:

Los vértices son los puntos A(0, 100), B(20, 50), C(40, 20), D(80, 0), que se encuentran al resolver el sistema que determinan dos a dos las rectas auxiliares y (y que estén dentro de la región factible).

r1

r2

que nos da el punto (40, 20) (comprobarlo)

r2

r3

que nos da el punto (20, 50)

r1

r3 no hace falta calcularlo pues queda fuera de la región factible.

En la gráfica se aprecia que el primer punto que se alcanza al desplazar la recta C(x, y)=0 es el (40, 20). Luego la solución es trabajar 40 días en la mina A y 20 en la B. (método gráfico) Lo comprobamos aplicando el método analítico: C(0, 100)=2000.100=200000 C(20, 50)=2000.20+2000.50=40000 + 100000= 140000 C(40, 20)= 2000. 40+2000.20=80000 + 40000= 120000

coste

mínimo C(80, 0)= 2000.80 =160000

5. Se va a organizar una planta de un taller de automóviles donde van a trabajar electricistas y mecánicos. Por necesidades de mercado, es necesario que haya mayor o igual número de mecánicos que de electricistas y que el número de mecánicos no supere al doble que el de electricistas. En total hay disponibles 30 electricistas y 20 mecánicos. El beneficio de la empresa por jornada es de 250 euros por electricista y 200 euros por mecánico. ¿Cuántos trabajadores de cada clase deben elegirse para obtener el máximo beneficio y cual es este? Sea

x = nº electricistas y = nº mecánicos

La función objetivo

f (x, y)=250x+ 200y , las restricciones

La región factible sería para estas restricciones:

Se aprecia gráficamente (línea en rojo) que la solución óptima está en el punto (20, 20). Por tanto: 20 electricistas y 20 mecánicos dan el máximo beneficio, y este es 9000 euros, ya que f(x, y) =250.20+200.20=9000

6. Para recorrer un determinado trayecto, una compañía aérea desea ofertar, a lo sumo, 5000 plazas de dos tipos: T(turista) y P(primera). La ganancia correspondiente a cada plaza de tipo T es de 30 euros, mientras que la ganancia del tipo P es de 40 euros. El número de plazas tipo T no puede exceder de 4500 y el del tipo P, debe ser, como máximo, la tercera parte de las del tipo T que se oferten. Calcular cuántas tienen que ofertarse de cada clase para que las ganancias sean máximas. Solución Sea x el nº que se ofertan de tipo T, y el nº que se ofertan de tipo P. nº

Ganancia

Turista

x

30x

Primera

y

40y

Total

5000

30x +40y

La función objetivo es: f(x, y)=30x +40y

Las restricciones:

La región factible:

Los vértices, A(0, 5000), B(3750, 1250), C(4500, 500) y D(4500, 0) (comprueba el punto B resolviendo el sistema correspondiente) El método gráfico nos da que el punto solución es el B (3750, 1250)

Comprueba los resultados usando el método analítico (sustituyendo los puntos vértices en f y viendo q el máximo valor se obtiene en B)

APLICACIÓN COMPUTARIZADA DEL METODO SIMPLEX

INTRODUCCIÓN

Muchos problemas de la administración de empresas y negocios son formulados y desarrollados como o modelos matemáticos de la programación lineal, con un número cualquiera de variables de decisión y de restricciones. El algoritmo que explicaremos es un procedimiento interactivo denominado el MÉTODO SIMPLEX.

En el transcurso del desarrollo del método SIMPLEX, para cada problema se hace la formulación, se definen las variables de decisión y se construye el modelo matemático. Para la aplicación del programa sistematizado se prepara la tabla inicial y se somete a la generación de la solución óptima, a través del programa computarizado.

Este método, encuentra una solución básica factible del problema y una sucesión de soluciones básicas factibles nuevas en cada una de sus interacciones; de tal forma, que los valores de la función lineal objetiva que estamos tratando llega progresivamente hasta su valor óptimo (máximo o mínimo) para dar así una decisión óptima, escogida de un gran número de decisiones posibles. La decisión óptima es la que satisface un objetivo de administración sujeta a varias restricciones.

El método SIMPLEX con el uso del computador encuentra amplias aplicaciones efectivas, empleadas exitosamente en la administración de las industrias petroleras, automotriz, químicas, forestales, metalúrgicas, agrícolas, militares, de servicios, financieras y otras. Al ser desarrollado en el centro de información durante el transcurso del programa de programación lineal; en la Universidad Popular del Cesar, pretendo que los estudiantes aprendan a aplicar e

interpretar los modelos matemáticos y sigan la dinámica para

adaptarse a los cambios frecuentes del medio en el que los profesionales actúan.

1. ESTANDRIZACIÓN DEL MODELO MATEMÁTICO O IGUALAR

Un modelo de programación lineal se dice que esta en forma estándar, cuando se convierte en un problema equivalente donde el objetivo es maximizar, todas las restricciones son ecuaciones y todas las variables del modelo son negativas.

NOTA: Minimizar Z = - Máx Z

TABLA PARA ESTANDARIZAR EL MODELO MATEMÁTICO O IGUALAR

TABLA 1

TIPO

Agregar a:

DE

La

RESTRICCIÓN

Restricción

Menor o igual

V. De Holgura



+S

La Función Maximizar

Objetivo Minimizar

+OS

+OS

+OS-MA

+OS+MA

-M*A

+MA

V. Excedente y Mayor o igual

Artificial



-S+A

Igualdad

Variable Artificial

=

A

V

Variable

Para estandarizar nuestro modelo matemático debemos utilizar variables de relleno y variables artificiales. Como se ilustra en la tabla número uno, si la restricción en el modelo es del tipo  (menor o igual), agregamos una variable de relleno al lado izquierdo de la restricción con signo (+) más, para convertirla en una igualdad, se llama variable de relleno de holgura, porque toma la diferencia entre la parte derecha de la ecuación de los recursos disponibles, para convertirla en una igualdad, y esta variable de holgura modifica a la función objetivo agregándole cero por la variable de holgura. Si la restricción es de tipo  (mayor o igual) debemos agregar al lado izquierdo de la restricción una variable de relleno con el signo (-) o variable de excedente, para que asuma el exceso de la desigualdad de los recursos

disponibles y una variable artificial para conservar la condición de no-negatividad, de la variable de excedente; estas variables agregan a la función objetivo cero por la variable de excedente, y -M por la variable artificial, si estamos maximizando o +M por la variable artificial si se trata de minimizar.

Los signos del coeficiente M nos garantiza que la variable artificial no este en la solución final. Si la restricción es del tipo igual se agrega una variable artificial al lado izquierdo de la restricción y la función objetivo se afecta en

-M por la

variable artificial si estamos maximizando o +M por la variable artificial si se trata de minimizar.

El valor de los coeficientes de las variables de relleno en la función objetivo siempre son cero porque los recursos de holgura no contribuyen en nada en las utilidades, el valor de los coeficientes de las variables artificiales en la función objetivo depende de que el problema sea maximización o minimización. Para asegurarnos de que ninguna variable artificial este en la solución final en la función objetivo, damos el coeficiente M anotado, lo que hacemos es restar o sumar M veces la variable artificial, donde M es un número mil veces mayor que cualquiera de los coeficientes del modelo. Digamos (999´999.999.999). número comparado con M para el computador.

LA SOLUCIÓN INICIAL tabla 2

CB

CB1

X1

X2

. . .

Xn

Solución

Cj

C1

C2

. . .

Cn

bi

LA BASE

a1

a2

. . .

an

XB1

a11

a12

a1n

b1 b2

CB2

XB2

a21

a22

a2n

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

CBm

XBm

am1

am2

amn

-C1

-C2

-Cn

bm

Zj - Cj Max

Zj

=

CB

0

CB x a j

= Vector fila formado por todos los coeficientes de las variables en la base

de la función objetivo.

Fila de Decisión Simplex: Zj - Cj, son los coeficientes para la función objetivo en la tabla inicial y sucesivas se llama z.

4. ALGORITMO SIMPLEX

2.1

PROCESO BÁSICO DE SOLUCIÓN

2.1.1 Solución Básica factible y solución óptima

Podemos notar que en un problema o modelo matemático de la programación lineal existen n variables y m ecuaciones, donde n > m entonces podemos tener una solución Básica haciendo (n –m) variables iguales a cero y resolviendo

en forma simultánea las

m

ecuaciones

restantes,

m ecuaciones con

m

variables.

A las n-m variables se le denominan NO BÁSICAS o fuera de la base y las m variables que se usan en el proceso de solución son las variables BÁSICAS o dentro de la base. Cuando todas las variables básicas de una solución básicas son no negativas entonces la solución se denomina Solución Básica Factible.

La solución básica factible que tiene el mejor valor para la función objetivo se llama la solución óptima.

La solución óptima cumple las condiciones de todas las restricciones incluyendo la condición de no negatividad.

La importancia del algoritmo SIMPLEX es que proporciona solución etapa por etapa, donde podemos analizar cada solución básica factible y en cada etapa podemos obtener una mejor solución, hasta encontrar la solución óptima.

En cada etapa podemos analizar si la solución es óptima, si no, proseguimos con la operación hasta encontrar la solución óptima o la mejor solución. Para la tabla inicial debemos hacer n – m variables iguales a cero o no básicas, y resolver para las m variables m ecuaciones con m variables.

n número total de variables y m número total de restricciones ; las variables no básica en la solución inicial son las originales y de excedentes. Las de holgura y artificiales son BÁSICAS.

El proceso de eliminación de

GAUSS-JORDAN, para resolver un sistema de

ecuaciones simultáneas lineales son la base del proceso para el algoritmo

SIMPLEX de la programación lineal.

El proceso de eliminación completa de

Gauss-Jordan, pasa una matriz inicial (A / I / B /) en la forma ( I / A-1/ X).

Al llegar al final de la transformación se dice que la matriz se ha invertido y de esa manera se obtiene la solución al sistema de ecuaciones, lo cual aplicado al método SIMPLEX permite llegar a una solución factible y / u óptima.

3. APLICACIÓN PROBLEMAS

Utilicemos un ejemplo para la construcción de la tabla.

La compañía P G. produce dos tipos de radios y compra distintas partes de los radios a otra compañía local y los arma en su planta. El radio tipo I necesita 5 horas de montaje y el tipo II necesita 3 horas. Se dispone diariamente de 105 horas en el departamento de montaje, la compañía puede gastar hasta U$ 70 para comprar los elementos de los radios. Utiliza U$ 2 de material para el radio tipo I y U$ 4 para el radio tipo II, se pueden vender todos los que se producen y gana U$ 20 netos al vender cada unidad de radio tipo I y U$ 16 al vender cada unidad tipo II.

La compañía P y G pide que se calculen cuántas unidades de cada uno de los radios se deben producir para maximizar la utilidad.

Nota: los datos están en miles de unidades.

3.2

Modelo matemático

Planteamiento Variables de decisión

Sea: x1 = Número de unidades del radio tipo I a producir. x2 = Número de unidades del radio tipo II a producir. F. O.3

Maximizar

Z = 20 X1 + 16 X2

Sujeto a: Restricciones. 1.

5 X1 + 3 X2  105

2.

2 X1 + 4 X2 

N. N. 4

X1 X2  0

70

Convertir las desigualdades a igualdades o pasar a la forma estándar. Igualar.

(3)

Z = 20X1 + 16X2 + 0X3 + 0X4

(4)

5X1 + 3X2 + X3 = 105

(5)

2X1 + 4X2 + X4 = 70 X1’ X2’ X3’ X4’  0

Función objetivo igualada a cero. Z – 20 X1 - 16 X2 = 0

3 4

Función Objetivo No Negatividad

SOLUCIÓN INICIAL SIMPLEX

Cj 

TABLA 3

X1

X2

X3

X4

20

16

0

0 Sale X3

CB

LA BASE

a1

a2

0

X3

5

3

0

X4

2

4

Máx

ZJ - CJ ZJ

-20 0

-16 0

a4

Solución

1

0

105

0

1

70

0

0 0

a3

0

0

 Entra

0



X1

ZJ

=

CB a j 3.3

Variable que entra en la base

La tabla inicial nos enseña que la solución inicial es el origen del sistema, puesto Entraes cero y las variables de holgura X3 y X4 presentan toda la que la ganancia

disponibilidad de recursos; ya que estos no han sido utilizados. Para resolver el problema tenemos que utilizar las disponibilidades, por lo tanto , se debe entrar alguna de las variables de decisión a la base y sacar una variable de holgura.

El criterio para seleccionar la variable que entra en la base, es la de escoger aquella variable que nos aumenta más rápidamente el valor de la función objetivo Z, es decir, la que da el máximo valor para la función objetivo.

Si examinamos la función objetivo

Z - 20 X1 - 16 X2 = 0

Si damos un valor positivo a cualquiera de las variables

X1, X2

la función

aumenta de valor; pero cual de las dos escogemos: por ejemplo,

1. damos a X1 = 1

X2 = 0



Z - 20 X1 - 6 X 0 = 0 Z = 20

La función Z nos aumenta 20 veces el valor tomado. Si tomamos X2 y damos el mismo valor X2 = 1  X1 = 0 Entonces: Z – 20 X 0 - 16 X 1 = 0 Z = 16 La función Z aumentaría 16 veces el valor tomado. Luego, debemos entrar a la base X1 ya que es la variable que nos aumenta más rápidamente el valor de Z comparado con X2, o sea que escogemos aquella con el coeficiente más negativo, es decir, la variable que nos da la mayor utilidad por unidad.

A la columna de la variable que entra en la base, la llamamos la columna pivote (K). Columna 1. Escogemos el mínimo Zk – Cj < 0 y para al menos una aij >0 (para i = 1, 2, . . . m ; j = 1, 2, . . . n ).

3.4

Variable que sale de la base

Encontramos la razón para cada elemento de la columna solución entre su correspondiente elemento de la columna pivote aik > 0.

Encontrar el mínimo

bi a ik

i = 1, … m

aik > 0 105 , 5

70 , 2

21,

35

Sale X4 este renglón se llama el renglón (r). En este caso el renglón (r) en la intersección con la columna (k) encontramos el pivote, para este caso el 5.

3.5

Encontrar los coeficientes de la nueva tabla (proceso manual)

3.4.1. Encontramos los nuevos valores

de los coeficientes del renglón de la

variable que salió de la base i = r, con ellos seguimos nuestro proceso de eliminación completa.

Realizamos esta operación dividiendo todos los coeficientes del renglón r entre el pivote operacional. ark

arj  a rj

arj ark

5 3 1  Coeficient e 5 Nuevo 5 5

aij

1

3/5

1/5

0 5

0

5 105

21

Los nuevos valores del renglón X1 renglón 1.

3.4.2. Para encontrar los nuevos valores de los demás renglones diferente al de la



variable que entra i

seguimos el siguiente procedimiento:

Le restamos al elemento que deseamos encontrar al producto de 1 multiplicado por el respectivo elemento en la columna pivote.

a

(i,j) = a (i,j) - a ( i,k ) * a ( r,j )/ark

Para la fila 2 a 21  2 

2 x5 0 5

a 22  4 

2 x3 14  5 5

a 23  0 

2 x1 2  5 5

a 24  1 

2 x0 1 5

a 20  70 

2 x105  28 5

La nueva fila dos es: 0

14/5

-2/5

1

28

De la misma manera encontramos los nuevos coeficientes de la función objetivo para la fila 3:

a ij  a ij  a ik x

a

a



5 x 20  20  0 31 5

 32

 16 

 20 x3  4 5

a rj a rk

a a

a

33

 0

 20 x1 4 5

34

 0

 20 x0 0 5

30

 0

 20 x105  420 5







Luego tenemos la nueva solución en la tabla siguiente.

PRIMERA INTERACCIÓN

X1 Cj

20

CB

LA BASE

a1

20

X1

0

X5

TABLA 4

X2 16

X3

X4

LA

0

0

SOLUCION

a2

a3

a4

b

1

3/5

1/5

0

21

0

14/5

-2/5

1

28

Máx

Zj - Cj

0

-4

0

420

Ahora en nuestra nueva solución solo hay un coeficiente negativo en el renglón de Zj-Cj. Hay una sola posibilidad de incrementando el valor de Z, o sea que X 2 entra a la base tomando valores positivos, luego la columna bajo esta variable es la columna pivote.

Sacamos las razones de los renglones 1 y 2 y escogemos el mínimo. X Bi a ik

i  1,...m

aik > 0 21 3 5

y 28 14 5

Para el caso escogemos la fila 2 , la del menor valor positivo 10 sale X5, el pivote operativo es entonces 14/5, luego aplicamos el criterio para encontrar los nuevos valores para i = r e i

 r.

Encontramos la nueva solución .

SEGUNDA INTERACCIÓN

CB

CJ

LA BASE

1 2

TABLA 5

X1

X2

X3

X4

20

16

0

0

a1

a2

a3

La Solución

a4

b

20

X1

1

0

2/7

-3/14

15

6

X2

0

1

-1/7

5/14

10

Máx

Zj-Cj

0

0

30/7

10/7

460

SOLUCIÓN ÓPTIMA

Como el renglón de decisión SIMPLEX o Zj-Cj no tienen coeficientes negativos hemos llegado a la solución óptima en la cual se deben producir :

X1 = 15 unidades de radios tipo I X2 = 10 unidades de radios tipo II

Para una ganancia total de Z = 460. Siempre debemos tener en cuenta :

1.

Que los coeficientes de las variables que están en la base constituyen los elementos de una matriz identidad en cada etapa del proceso simplex.

2.

llegaremos a la solución óptima cuando los coeficientes de la función objetivo en la tabla SIMPLEX sean positivos o cero

Zj

-

Cj

4.



0

MINIMIZACIÓN

Para resolver este caso directamente lo hacemos similar al procedimiento maximizar; teniendo en cuenta lo siguiente:

1. El criterio para escoger la variable que entra en la base es seleccionar el coeficiente de la función objetivo con mayor valor positivo en el renglón de criterio SIMPLEX (m+1), para ello:

Zj = C B x

aj

j = 1, 2 . . . n

C B = vector fila de los coeficientes de las variables en la base en la función

objetivo.

aj

cualquier vector columna de la matriz A para j = 1, 2, . . .n

renglón de criterio simplex Zj - Cj (m+1).

2. El valor del coeficiente de la variable artificial es +M. El resto del procedimiento es similar al de maximización y tendremos una solución óptima cuando todos los coeficientes Zj - Cj  0 del renglón de criterio simplex sean negativos o ceros. Ejemplo: La compañía D. C recibió la orden de una mezcla de 20.000 lbs que lleva cereal y carne de res como alimento para perros. El cereal cuesta $300 c/lbs y $800 la libra de carne. Solamente hay 8000 lbs de cereal y hay que usar al menos 6000 lbs de carne en la mezcla. Que cantidad de cada ingrediente se debe utilizar, de tal manera que se minimice el costo y cumplir con los requisitos al mismo tiempo.

5. Modelo Matemático

Desarrollo: Sea

X1 = Cantidad de libras de cereal en la mezcla. X2 = Cantidad de libras de carne de res en la mezcla.

F.O. Min.

Z = 300 X1 + 800 X2

Sujeto a: Restricciones X1  8000 X2

 6000

X1

+

X2 = 20.000 X2 

X1,

0

Estandarización o igualación.

(0) Z = 300 X1 + 800 X2 + 0 X3 + 0 X4 + M As + M A6

Sujeto a: Restricciones

1)

X1

X3

2)

X2

3)

X1 + X2

= 8000 -X4 + A5

= 6000

A5 = X5

+ A6 = 20000

X1, X2, X3, X4, A5, A6



A6 = X6

0.

SOLUCIÓN INICIAL SIMPLEX

TABLA 6

300

800

0

0

LA BASE

X1

X2

X3

X4

X5

0

X3

1

0

1

0

0

0

M

A5

0

1

0

-1

1

0

6000

M

A6

1

1

0

0

0

1

20000

Min

Zj - Cj

0

-M

0

0

26000M

0

-M

M

M 26000M

Cj CB

M-300 2M-800

Zj

M

2M

+M

+M X6 Solución 8000

El problema de minimización lo podemos convertir en n problema de maximización mediante la fórmula:

Minimizar

Z = - Máx Z

Entonces el procedimiento para resolver este problema es como el caso maximizar anterior, lo que quiere decir, que debemos hacer el cambio de signo para el renglón de decisión simple.x (renglón m+a) de la función objetivo y como consecuencia terminaremos cuando todos los ZJ - CJ  0, allí estaremos en la solución óptima.

TABLA TRANSFORMADA A MAXIMIZAR

TABLA 7

300

800

0

0

+M

+M

La

X1

X2

X3

X4

X5

X6

Solución

LA BASE

a1

a2

a3

a4

a5

a6

0

X3

1

0

1

0

0

0

+M

X5

0

1

0

-1

1

0 6000

+M

X6

1

1

0

0

0

1 20000

-Max

Zj - Cj

0

M

0

0 -26000M

Cj CB

300-M 800-2M

b 8000 

Tabla inicial transformada a - Maximizar Z = MINIMIZAR PARA M = 1000 -Max

-Zj

-

Cj

-700

-1200

0

1000

0

 ENTRA X2

INTERACCIÓN Nro. 1 CMAX = -1200

V. B. X3

1

0

1

0

0

0

=

8000

X2

0

1

0

-1

1

0

=

6000

X6

1

0

0

1

-1

1

=

14000

0 -26000000

C =

-700 0

0

-2000

1200

Variable básica que entra =

2

Variable básica que sale =

5

0

Z = -1 . 88E + 07

INTERACCIÓN Nro.

2

CMAX = -700

V. B.

X1

1

0

1

0

0

0

=

8000

X2

0

1

0

-1

1

0

=

6000

X6

0

0

-1

1

-1

1

=

6000

0

700

-200 1200 0

C = 0

Variable básica que entra = 1 Variable básica que sale

= 3

Z = -1 .32E+07

INTERACCIÓN Nro.

3

CMAX = -200

V. B. X1

1

0

1

0

0

0

=

8000

X2

0

1

-1

0

0

1

=

12000

X4

0

0

-1

1

-1

1

=

6000

C = 0

0

500

0

1000 200

Variable básica que entra = 4 Variable básica que sale

= 6

Z = -1 . 2E+07 = -1.2 x 107 = -12’000.000 Como minimizar = - Maximizar el resultado es positivo

SOLUCIÓN ÓPTIMA FUNCIÓN OBJETIVA MÁXIMA Z = 12’000.000 VARIABLES BÁSICAS DE LA SOLUCIÓN MÁXIMA

X(1) =

8000

X(2) =

12000

X(4) =

6000

6. APLICACIÓN DEL PROBLEMA

PROBLEMA No. 1

1. Considere que se han aislado 4 nutrientes para ganado; designados A, B, C y D. El I.C.A. especifica que el requerimiento mínimo diario por animal es de 6 libras de A, 8 libras de B, 4 libras de C y 5 libras de D exactamente, se dispone de dos alimentos, Maíz y Alfalfa. Los análisis de estos alimentos son:

NUTRIENTES

ALIMENTOS MAIZ(%) ALFALFA(%)

A

10

45

B

40

20

C

30

15

D

20

20

El maíz cuesta 4 centavos la libra y la alfalfa 3 centavos la libra. Qué cantidad de cada alimento se debe comprar para obtener EL COSTO MÍNIMO.

Sea:

X1 = Número de libras de Maíz por animal DESARROLLO

DEL MODELO MATEMÁTICO DE LA PROGRAMACIÓN LINEAL

VARIABLES DE DECISIÓN

a consumir diariamente.

X2 = Número de libras de Alfalfa a consumir por animal diariamente.

FUNCIÓN OBJETIVO

Min Z = 4X1 + 3X2

(Costo Mínimo)

Sujeto a: Restricciones 1)

10X1 + 45X2



6 (Nutriente A )

2)

40X1 + 20X2



8 (Nutriente B )

3)

30X1 + 15X2



4 (Nutriente C )

4)

20X1 + 20X2

=

5 (Nutriente D )

X1 , X2  0

2.

Federaltex

enfrenta el problema de determinar

qué problemas de

“crecimiento” debe emprender en los 4 años. La compañía tiene una cantidad limitada de fondos para inversiones de capital; por tanto, no puede financiar todos los proyectos.

A cada uno de estos se ha caracterizado determinando su valor presente y el requerimiento ( costo )

asociado de capital.

Cada proyecto tiene diferentes

requerimientos de capital para los próximos 4 años.

En la tabla siguiente se

muestra el valor presente estimado, los requerimientos de capital y el capital disponible proyectado para cada uno de ellos.

VALOR ACTUAL, REQUERIMIENTOS DE CAPITAL Y CAPITAL DISPONIBLE PARA FEDERALTEX.

REQUERIMIENTOS DE

TIPO DE PROYECTO

VALOR PRESENTE

CAPITAL

Estimado

AÑO 1 AÑO2 AÑO3 AÑ04 Expansión de la planta Nueva Maquinaria

$180.000

$300.000

$40.000

$40.000

$30.000

20.000

12.000

8.000

0

4.000

72.000

30.000

20.000

20.000

20.000

80.000

20.000

30.000

40.000

10.000

$65.000

$80.000

$80.000

$50.000

Investigación sobre nuevos productos Ampliación del Fondos capital

disponibles

de

A los administradores de Federaltex les gustaría desarrollar un plan de asignación de capital que muestre las erogaciones que debe hacer par cada uno de los cuatro años y que proyectos se deben financiar bajo el plan general. El objetivo de Federaltex es determinar que proyectos se pueden “financiar por completo”, es decir, financiar para el período completo de cuatro (4) años, reconociendo que cada año existen disponibles fondos limitados de capital.

El proceso de financiamiento debe ser tal que se maximice el valor actual estimado total de los proyectos.

DESARROLLO DEL MODELO MATEMÁTICO. P.L. VARIABLES DE DECISIÓN

Sea: Xj

= Valor proporcional que indica la medida en que se financiará el

proyecto

j ( Xj = 1 indica que se financia completo, Xj < 1 señala que no se

financia).

J = 1, 2, 3, 4 FUNCIÓN OBJETIVO

Máx Z = 180000X1 + 20000X2 + 72000X3 + 80000X4 Sujeto a : Restricciones

1)

30000X1 + 12000X2 + 30000X3 + 20000X4  65000

2)

40000 X1 + 8000 X2 + 20000 X3 + 30000 X4  80000

3)

40000 X1 +

4)

30000 X1 +

5)

X1

1

6)

X2

1

7)

X3

1

8)

X4

1

0 X2 + 20000 X3 + 40000 X4  80000 4000 X2 + 20000 X3 + 20000 X4  50000

X1 , X2 , X3 , X4

 0

4. La dietista de un hospital debe encontrar la combinación más barata de dos productos A y B que contienen al menos 0.5 miligramos de Tiamina y al menos 600 calorías. Cada onza de A contiene 0.12 miligramos de Tiamina y 100 calorías mientras que cada onza de B contiene 0.08 miligramos de Tiamina y 150 calorías. Si el costo de cada alimento es de U$ 10 por onza. Cuántas onzas de cada uno deberían combinarse?

PRODUCTO

TIAMINA

CALORÍAS

A

0.12 mg.

100

U$ 10

B

0.08 mg.

150

10

0.5

600

Disponibilidad

COSTO

MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN

Sea : X1 = Número de onzas del producto A a combinarse para producir la dieta. X2 = Número de onzas del producto B a combinarse para producir la dieta.

FUNCIÓN OBJETIVO

Min Z = 10X1 + 10X2 Restricciones Sujeto a: 1) 0.12X1 + 0.08  0.5 2) 100X1 + 150X2  600

X1 , X2  0

5. Una compañía produce dos tipos de calculadoras electrónicas, un modelo estándar cuya utilidad es de U$ 5 y un modelo de lujo cuya utilidad es de U$ 8. La compañía estima que su red de distribuidores a lo más puede manejar 1000 calculadoras a la semana.

Debido al

rápido crecimiento de la industria de las calculadoras, existe

disminución tanto en las partes como en la mano de obra calificada necesaria a fin de ensamblar las calculadoras. La compañía puede obtener un suministro semanal regular de solo 5000 circuitos electrónicos (Chips) necesarios para las calculadoras; cada calculadora estándar necesita 3 de estos chips y cada calculadora de lujo requiere 6 chips. Más aún, la compañía dispone de 2500 horas-hombre de mano de obra calificada a la semana, cada calculadora estándar demanda 3 horas-hombre y cada calculadora de lujo necesita 2 horas-hombre.

Cuántas calculadoras de cada tipo deberían producirse a la semana a fin de maximizar la utilidad total?

CALCULADORAS

CHIPS MANO DE OBRA

BENEFICIO

Regular

3

3

U$ 5

Lujo

6

2

U$ 8

Disponibilidad

5000

2500 H/H

MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN

Sea:

X1 = Número de calculadoras regular a producir a la semana. X2 = Número de calculadoras de lujo a producir a la semana.

FUNCIÓN OBJETIVO

Max Z = 5X1 + 8X2 Restricciones Sujeto a:

X1

2)

3X1 + 6X2  5000

3)

3X1 + 2X2  2500

X1 , X2  0

+ X2

 1000

1)

6. La ladrillera lacera desea obtener una mezcla de arena y cemento que tenga 30% de arena

y 70% de cemento.

En el mercado venden tres clases de

productos: Producto 1 tiene 25% de arena y 75% de cemento y vale U$ 600 ton; el producto 2 tiene 40% de arena y 60% de cemento y vale U$ 400 ton y la producto 3 tiene 50% de arena y 50% de cemento y vale U$ 150 ton.

Qué cantidad de cada producto se debe comprar para producir una tonelada de la mezcla deseada? MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN

Sea :

X1 = Número de toneladas de producto 1 a comprar para producir la mezcla deseada. X2

= Número de toneladas de producto 2 a comprar para producir la mezcla

deseada. X3

= Número de toneladas de producto 3 a comprar para producir la mezcla

deseada.

FUNCIÓN OBJETIVO

Min Z = 600 X1 + 400X2 + 150X3 Restricciones Sujeto a : A4 = X4 1)

25X1 + 40X2 + 50X3 = 30

2)

75X1 + 60X2 + 50X3 = 70

3)

X1 +

X2 +

X3 = 1

A5 = X5 A6 = X6

Xj  0,

i = 1, 2, 3

7. La compañía tropical fabrica y vende tres productos A, B, y C. la información relacionada con los tres productos se presenta a continuación en la siguiente tabla.

INFORMACIÓN DE PRECIO Y COSTO ( Por unidad ) A Precio de venta Mano de obra directa

U$ 25 7.50

B

C

30

40

10

12.50

Materiales Directos

9

6

10.50

Costos Variables

6

6

6

Costos Fijos

6

6

6

Los tres productos utilizan el mismo tipo de material directo, el cual cuesta U$ 1.50 por libra de material. La mano de obra directa se paga a la tasa de U$ 5 por hora. Hay 2.000 horas de mano de obra directa y 20.000 libras de materiales directos disponibles en un mes. Cuanto debe fabricar de cada producto, para maximizar la contribución. Plantear el modelo matemático de la P.L.

PRODUCTOS A Mat Dir.

9.0

B 6.0

C 10

M. O. Dir

7.5

10

12.5

Cost. Var

6.0

6.0

6.0

22.5

22

Cost. Var. Total Pvta – Cvatot = Marg Cont

Margen de contribución Horas M. O. D Tasa ( U$ 5 / H )

B

C

2.5

8

11

7.5 / 5= 1,5

10 / 5 = 2

12.5/5 = 2.5

Relación de consumo de Mod/Producto

Materiales Directos ( en U$ 1.5 / lib )

A

9 / 1.5 = 6

6 / 1.5 = 4

10.5 / 1.5 =7

Relación de consumo de materiales/prod

MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN

Sea:

X1 = Número de unidades del producto A a producir en el mes. X2 = Número de unidades del producto B a producir en el mes. X3 = Número de unidades del producto C a producir en el mes.

29

FUNCIÓN OBJETIVO

Max Z = 2.5X1 + 8X2 + 11X3

Sujeto a : 1) 2)

1.5X1 + 2X2 + 2.5X3  2000 (Horas- H) 6X1 + 4X2 + X1 , X2 , X3

7X3  20.000 (Libras)

 0

8. Una compañía fabrica y ensambla dos productos A y B. Toma tres minutos para fabricar cada unidad de A y seis minutos para fabricar cada unidad de B. El tiempo de ensamble por unidad para el producto A es de dos minutos y para el producto B de 9 minutos. Están disponibles 10 horas de tiempo de fabricación y 30 horas de tiempo de ensamble. La compañía logra un margen de contribución de U$ 2 en cada unidad de A que vende y U$ 1 en cada unidad de B. Cuanto debe ensembrar de cada producto para maximizar la contribución.

Formule el problema como un modelo de programación lineal.

MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN

Sea: X1 = Número de unidades del producto A a producir. X2 = Número de unidades del producto A a producir.

10 X 60 = 600 Minutos

30 X 30 = 1800 Minutos

FUNCIÓN OBJETIVO

Max Z = 2X1 + X2

Sujeto a:

1)

3X1 + 6X2 

2)

2X1 + 9X2  1800

600

X1 , X2  0

SOLUCIÓN INICIAL SIMPLEX

TABLA No. 18

Cj

2

1

0

0

Cb

La Base

X1

X2

X3

X4

SOLUCIÓN

0

X3

3

6

1

0

600

0

X4

2

9

0

1

1800

Max

Zj - C j

-2

-1

0

0

0

9.

La compañía Químicos Unidos S. A. fabrica un limpiador industrial para

alfombras. Este químico se hace de una mezcla de otros dos químicos que contienen ambos el agente limpiador W5 y el agente limpiador Q2. su producto debe contener 175 unidades del W5 y 150 unidades del Q2, y pesar al menos 100 libras.

El químico A cuesta U$ 8 por libra, mientras que el químico B cuesta U$ 6 por libra. El químico A contiene una unidad del agente W5 y tres unidades del agente Q2; el químico B contiene siete unidades y una unidad de los agentes respectivos.

PRODUCTO

W5

Q2

COSTO

A

1

3

U$ 8

B

7

1

U$ 6

Disponibilidad

175

150

Formule el problema como un modelo de Programación lineal.

VARIABLES DE DESICION

Sea

X1 = Número de libras del químico A a producir. X2 = Número de libras del químico B a producir.

Min Z = 8X1 + 6X2

Sujeto a : 1)

X1 + 7X2  175

A6 = X6 A7 = X6

2)

3X1 +

X2  150

3)

X1 +

X2  100

X1 , X2  0

A8 = X8

10. La compañía la Muñeca fabrica dos tipos de juguetes A y B. Para producir el juguete B se gasta el doble de tiempo que para producir el juguete tipo A y la compañía tiene tiempo para hacer por día un máximo de 2000 juguetes tipo A.

El suministro de materia prima es suficiente para producir por día 1500 juguetes de A y B combinados. El juguete tipo B requiere de un aditamento especial del cual solo se dispone de 600 unidades por día. El gerente de la compañía se comprometió a entregar a un cliente 200 unidades del juguete tipo A.

Es política de la compañía que el número de juguetes tipo B que se haga no debe ser mayor a 1.5 veces el número de juguetes tipo A. los costos de producción son de U$ 30 y U$ 40 para los juguetes A y B respectivamente, y los precios de venta respectivamente U$ 60 y U$ 90 para A y B respectivamente. Formule el modelo de Programación Lineal para este problema.

MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN

Sea :

X1 = Cantidad de juguetes tipo A a producir por día. X2 = Cantidad de juguetes tipo B a producir por día.

Pv - C = Ut A

60 - 30 = 30

B

90 - 40 = 50

FUNCIÓN OBJETIVO Max

Z = 30X1 + 50X2

Restricciones Sujeto a :

1)

X1 + 2X2  2000

2)

X1 + X2  1500 X2  600

3) 4)

 200

X1

5) –1.5X1 + X2  0 X1 , X2  0

11.

Se quiere obtener la cantidad de leche, carne y huevos que satisfacen

determinada dieta nutritiva en cuanto a vitamina A, B y C. Suponga que el número de miligramos de cada una de estas vitaminas, contenidas por unidad de producto se muestra en la siguiente tabla:

VITAMINAS

Gl. de LECHE

Lb. DE CARNE

Doc. De HUEVOS

A

1

1

10

B

100

10

10

C

10

100

10

Las cantidades mínimas requeridas diariamente son :

Vitamina A un miligramo; Vitamina C 50 miligramos y Vitamina D 10 miligramos. Los costos son: Galón de leche U$ 4; libra de carne U$ 10 y huevos U$ 1.5 la docena.

Formule el modelo de Programación Lineal para este problema.

MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN

Sea:

X1 = Cantidad de galones de leche a comprar para producir la dieta.

X2 = Cantidad de libras de carne a comprar para producir la dieta. X3 = Cantidad de docenas de huevos a comprar para producir la dieta.

FUNCIÓN OBJETIVO

Restricciones Min Z = 4X1 + 10x2 + 1.5X3

Sujeto a :

1) 2) 3)

X1 +

X2 + 10X3  1

100X1 + 10X2 + 10X3  50 10X1 +100X2 + 10X3  10 X1 , X2 , X3  0

12. Un agricultor tiene 500 hectáreas y dispone de 4000 horas-hombre que asignará a cultivar los siguientes productos: maíz, trigo y soya. El agricultor debe producir al menos 150 ton. de trigo debido a un contrato especial firmado con un cliente y al menos 400 toneladas de maíz.

En la siguiente tabla se asume el tonelaje y la mano de obra en horas-hombre por hectárea para los diferentes productos:

Ton / Hect.

MAÍZ

TRIGO

15

8

Horas hombre / hect. 120

135

SOYA 10 105

El maíz, trigo y soya lo comercializan a U$ 200, 300 y 145 / ton. cuántas hectáreas se deben producir de cada producto por cosecha para maximizar los ingresos.

MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN

Sea:

X1 = Número de hectáreas asignadas al cultivo de maíz por cosecha. X2 = Número de hectáreas asignadas al cultivo de trigo por cosecha. X3 = Número de hectáreas asignadas al cultivo de soya por cosecha.

FUNCIÓN OBJETIVO

Máx Z = 15x200X1 + 8x300X2 + 10x145X3

Ingresos Totales

Sujeto a: 1)

X1 +

X2 +

X3 +  500

120X1 + 135 X2 + 105X3 +  40000 (Simplificado al pasar a la tabla)

2)

3)

15X1  400

4)

8 X2x  150 X1 , X2 , X 3  0

13.

La junta de planeación del municipio de Valledupar tiene tres proyectos para la

comunidad de Pueblo bello. Construir un colegio, un puesto de salud y una casa comunal. Abre una licitación para construir estas obras, cuyo número de pliegos presentados por los contratistas muestra las siguientes cotizaciones para las obras en millones de pesos: PROYECTOS CONTRATISTAS

A

B 200

C

1

500

50

2

480

210

45

3

450

180

42

Dentro de las condiciones del pliego la Junta de Planeación especifica que se debe asignar un proyecto a un contratista. Que proyectos adjudican a que contratista? Para minimizar los costos.

MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN Sea:

Xi j = contratista i que se le adjudica el proyecto j.

.i = 1, 2, 3

j = 1, 2, 3

FUNCIÓN OBJETIVO Min Z = 500X11 + 200X12 + 50X13 480X21 + 210X22 + 45X23 450X31 + 180X23 + 42X33 Sujeto a: 1)

X11 + X12 + X13 = 1

2)

X21 + X22 + X23 = 1

3)

X31 + X32 + X33 = 1

4)

X11 + X21 + X31 = 1

5)

X12 + X22 + X32 = 1

6)

X13 + X23 + X33 = 1

Xi j  0 14. El comando de bombardeo estratégico recibe instrucciones de interrumpir la destrucción de tanques del enemigo.

Este tiene 4 plantas de gran importancia localizadas en distintas ciudades y la destrucción de cualquier planta detendrá efectivamente la producción de tanques. Hay una aguda escasez de combustible, que limita la

provisión a

48000 galones para esta misión

particular.

Cualquier bombardeo enviado a determinada ciudad particular debe llevar cuando menos el combustible suficiente para el viaje redondo, mas una reserva de 100 galones. El número de bombarderos de que dispone el comandante, así como las descripciones, se presentan en la siguiente tabla:

TIPO BOMBARDERO

DESCRIPCIÓN

MILLAS/GLS

DISPONIBLE

1

Pesado

2

48

2

Liviano

3

32

La información a cerca de la localización de las plantas y de su vulnerabilidad al ataque de un bombardero liviano y uno pesado, se da enseguida.

PLANTA

DISTANCIA DE LA BASE EN MILLAS

PROBABILIDAD DE DESTRUCCIÓN PESASADO

LIVIANO

1

450

0.10

0.08

2

480

0.20

0.16

3

540

0.15

0.12

4

600

0.25

0.20

Cuántos bombarderos de cada tipo deben ser despachados a las diferentes fábricas y cómo deben repartirse en los cuatro blancos, para hacer máxima la probabilidad de éxito ?.

PLANTAS 1

2

3

MILLAS / GALÓN

DISPONIBILIDAD

4

BOMBARDERO 1

X11

X12 X13 X14

2

48

2

X21

X22

3

32

X23 X24

MODELO MATEMATICO P.L. VARIABLES DE DECISIÓN

Sea: Xij = El número de bombero de tipo i enviado a la ciudad j.

i = 1, 2

j= 1,2,3,4

FUNCION OBJETIVO

Max Z = 0.10X11 + 0.20X12 + 0.15X13 + 0.25X14 + 0.08X21 + 0.16X22 + 0.12X23 + 0.20X24

Sujeto a :

1)

2 x 450 2 x 480 2 x540 2 x600 X 11  X 12  X 13  X 14  2 2 2 2

2 x 450 2 x 480 2 x540 2 x600 X 21  X 22  X 23  X 12  3 3 3 3

100 (X11 + X12 + X13 + X14 + X21 + X22 + X23 + X24 )  48000 (Combustible)

2) X11 + X12 + X13 + X14  48 (aviones pesados)

3) X21 + X22 + X23 + X24  32 (aviones livianos)

X11  0

15. Cervecería Leona tiene tres plantas que embotellan cerveza de marca genérica. La cerveza se distribuye desde tres plantas a cuatro (4) bodegas. Los gerentes de producción de cada una de las plantas han estimado la producción mensual esperada para sus respectivas plantas.

Se fabricará en total en las tres plantas una cantidad

suficiente de cerveza para cargar 300 camiones.

La gerencia general ha asignado la producción total a las respectivas bodegas examinando datos de meses anteriores. En la tabla siguiente se presenta la información de oferta (producción) y demanda (asignación), junto con los costos de transporte para cada combinación de oferta y demanda.

Debe observarse que las unidades de oferta y demanda se expresan en camiones de cerveza, en tanto que las cifras de costo que aparecen en el cuerpo de la tabla se expresan en dólares por camión.

BODEGAS PLANTAS U$

1 464

513

2 654

3

4

867

PRODUCCIÓN (OFERTA) 75

2

352

416

690

791

125

3

995

682

388

685

100

ASIGNACIÓN (DEMANDA)

1

----------80

65

70

85

300

Formule el modelo de programación lineal para un programa de transporte con costo mínimo.

MODELO MATEMÁTICO P. L.

VARIABLES DE DECISIÓN

Sea:

Xij

= Número de camiones que se enviaron de la planta i a la bodega j.

i

= 1, 2, 3

j

= 1, 2, 3, 4

FUNCIÓN OBJETIVO

Min

Z =

464X11 + 513X12 + 654X13 + 867X14

+

352X21 + 416X22 + 690X23 + 791X24

+

995X31 + 682X32 + 388X33 + 685X34

Sujeto a: 1)

X11 + X12 + X13

+ X14 = 75

2)

X21 + X22 + X23

+ X24 = 125

3)

X31 + X32 + X33

+ X34 = 100

4)

X11 + X21 + X31

=

80

5)

X12 + X22 + X32

=

65

6)

X13 + X23 + X33

=

70

7)

X14 + X24 + X34

=

85

Xi j  0

16. La Compañía Moreno Ltda.. fabrica fertilizantes especiales para clientes del mercado de cítricos. La Compañía acaba de recibir un pedido de 1000 toneladas de un fertilizante que debe satisfacer las siguientes especificaciones.

a.

Cuando menos un 20% de nitrógeno.

b.

Cuando menos un 30% de potasio.

c.

Cuando menos un 8% de fosfato.

La Compañía ha adquirido cuatro mezclas de fertilizantes a partir de los cuales puede fabricar sus fertilizantes especiales. Los porcentajes de potasio, nitrógeno y fosfato que contienen los fertilizantes básicos son:

Porcentaje de Fertilizante Nitrógeno

Potasio

Fosfato

Básico

1

40

20

10

2

30

10

5

3

20

40

5

4

5

5

30

El porcentaje restante de cada fertilizante básico consta de ingredientes inertes. Los costos de los fertilizantes básicos respectivos son $16, $12, $15, y $ 8 por tonelada. El objetivo es minimizar los costos. Plantear el modelo matemático.

MODELO MATEMÁTICO P. L. VARIABLES DE DECISIÓN Sea:

Xj = El número de toneladas de cada uno de los fertilizantes básicos que deben incluirse en la mezcla de las 1000 toneladas. j = 1, 2, 3, 4

FUNCIÓN OBJETIVO

Mín Z = 16X1 + 12X2 + 15X3 + 8X4

Sujeto a: 1) 0.40X1 + 0.30X2 + 0.20X3 + 0.05X4  200 2) 0.20X1 + 0.10X2 + 0.40X3 + 0.05X4  300 3) 0.10X1 + 0.05X2 + 0.05X3 + 0.30X4  80

4)

X1 +

X1 ,

X2 +

X2 , X 3 , X4

X3 +



0

X4 = 1000

EL PROBLEMA DE TRANSPORTE Y ASIGNACION

EL PROBLEMA DE TRANSPORTE

El problema de transporte se presenta cuando se planea la distribución de bienes y servicios a partir de varios lugares de suministro, producción, ofertas u orígenes y son transportados a diferentes ubicaciones de demandas clientes o destinos. El Objetivo del problema es minimizar los costos de transportar los artículos desde los orígenes hasta los destinos.

Utilizamos el problema de la programación lineal para resolver el problema de Transporte , para ello definimos los siguientes parámetros y variables, Sea:

i = Índice para los orígenes, i = 1, 2, 3, …..m

j = índice para los destinos

j = 1, 2, 3 … n

X ij = Número de unidades que se envían del origen i al destino j

C ij = Costo por unidad que se envía del origen i al destino j

ai

= Oferta o capacidad de unidades del origen

bj =

Demanda de unidades en el destino

El modelo general de programación lineal de un problema de transporte con m orígenes y n destinos es :

m n

Minimizar Z =

  Cij X ij 1 1

Sujetos :

n

 X ij  ai

i= 1, 2, 3, ..

m

1

m

 X ij  b j j= 1, 2, 3, .. n 1

m

n

1

1

 ai =  bj

Xij  0 para toda

condición necesaria

i = 1, 2, 3, . . . m

y

toda

j = 1, 2, 3, …n

Ejemplo:

Postobón tiene tres fabricas la de Valledupar, Bucaramanga y Barranquilla respectivamente y desea distribuir sus productos en tres poblaciones :El Banco ,Caucacia y Aguachica, en la tabla siguiente se definen las cantidades a transportar en cada una de las variables, los costos por unida en pesos por unidad, la producción y las demadas en millones de botellas semanales. Cual es el programa de costo mínimo semanal.

ui

CLIENTE 1

2

3

1

X 11 6

X 12

7

X 13

5

60

2

X 21

X 22

20

X 23

1

80

3

X 31

X 32

4

X 33

3

40

PLANTA

8

5

Bj

50

90

70

180

210

Solución

1.

Construimos la red de distribución

PLANTAS

CLIENTES

6 1

1 7 5

8 20 2

2 1

5

4

3

3 3

2. IGUALAR OFERTAS Y DEMANDAS Si las ofertas son mayores agregamos un cliente ficticio con costos cero, para que asuma la diferencia de las demandas, en caso contrario agregamos una planta ficticia con costos cero para que asuma la diferencia de las ofertas, de esta forma tenemos la tabla equilibrada o igualada o estandarizada.

TABLA IGUALADA O ESTANDARIZADA

ui

CLIENTE 1

2

3

1

X 11 6

X 12

7

X 13

5

60

2

X 21

X 22

20

X 23

1

80

PLANTA

8

3

X 31 5

X 32

4

X 33

4 FICTICIA

X 41 0

X 42

0

X 43

Bj

50

90

3

0

70

40

30

210

210

3. Construir

el modelo programación lineal

matemático

de

la

MODELO MATEMATICO DE LA PROGRAMACION LINEAL

Minimizar Z = 6X 11 + 7 X 12 + 5 X + 8 X 21 +20 X 22 + X +5X + 13

23

31

+4X +3 X +0 X 41 + 0 X 42 + 0 X 32

33

43

Sujeto a :

1.

X 11 + X 12 +

X

=

13

60

0ferta

2.

X 21 + X 22 +

X

23

=

80

0ferta

3.

X + X

X

33

=

40

oferta

4.

X 41 + X 42 +

=

30

oferta

31

32

+

X

43

5.

X 11 . + X 21 . +

X . +

6. X 12 + X 22 + demanda

X

32

7. X + X demanda

X

33

13

Xij



0

23

+

i = 1, 2, 3,4

X 41 =

31

+

X 42

=

90

+

X

=

70

43

y

j = 1, 2, 3

4. EQUIVALENCIA DE VARIABLES X 11 = X1

X 12 = X2

X 21 = X4

X 22 = X5

50 demanda

X = X3 13

X = 23

X6

X = X7

X = X8 32

31

X 41 = X10

X13 = A13

X 42 = X11

33

X = X12 43

X14 = A14

X15 = A15

X16 = A16

X17 = A17

X18 =A18

5.

X = X9

X19 = A19

MODELO MATEMÁTICO EQUIVALENTE PARA CONSTRUIR LA FORMA SIMPLEX

Minimizar X6

Z = 6 X1 + 7 X2 +5 X3 + 8X4

+ 20 X5 +

+ 5 X7 + 4 X8 + 3 X9 + 0X10 + 0 X11 + 0X12

Sujeto a :

1.

X1 + X2 + X3

2.

X4 + X5 + X6 = 80

3.

X7 + X8 + X9

4.

X10 + X11 + X12=

5. X1. + demanda

6.

X2 +

=

60

0ferta

0ferta

= 40

X4

X5 + X8 +

30

+

oferta

oferta

X7 +

X10 =

50

X11 = 90 demanda

7. X3 demanda

Xj



0

+

X6 + X9

+ X12

=

70

j = 1, 2, 3,4,5,6,7,8,9,10,11,12

6. APLICACIÓN DE LA LA TABLA DE IGUALAR DEL SIMPLEX

TABLA DE IGUALAR SIMPLEX TIPO

Agregar a:

DE

La

RESTRICCIÓN

Restricción

Menor o igual

V. De Holgura



+S

La Función Objetivo Maximizar

+OS

Minimizar

+OS

V. Excedente y Mayor o igual

Artificial



-S+A

Igualdad

Variable Artificial

=

A

+OS-MA

+OS+MA

-M*A

+MA

MODELO MATEMATICO SIMPLEX IGUALADO

Minimizar X6

Z = 6 X1 + 7 X2 +5 X3 + 8X4

+ 20 X5 +

+ 5 X7 + 4 X8 + 3 X9 + 0X10 + 0 X11 + 0X12+MX13 + MX14 + MX15 + MX16 + MX17 + MX18 + MX19

Sujeto a :

1.

X1 + X2 + X3 +

X13 =

60

2. X4 + X5 + X6 +

3. X7 + X8 + X9 +

4. X10 + X11 + X12 +

X14 =

X15 =

X16 =

80

40

30

5.

X1. + X4. +

X7. + X10 + X17 =

6.

X2 + X5 +

X8 +

7.

X3 + X6 +

X9

+

50

X11 + X18 =

X12 + X19

=

90

70

Xj  0 j = 1, 2,3,4,5,6,7,89,10,11,12,13,14,15,16,17,18,1

7. CONSTRUCCION DE LA TABLA DE LA SOLUCION INICIAL

SOLUCIÓN INICIAL SIMPLEX

Cj

6

7

5

8

20

1

5

4

3

0

M 0

M

M

M

M

M

b

M

0

Cb

Base

X1

X2

X3

X4

X5

X6

X7

X8

X9

M

X13

1

1

1

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

60

M

X14

0

0

0

1

1

1

0

0

0

0

0

0

0

1

0

0

0

0

0

80

M

X15

0

0

0

0

0

0

1

1

1

0

0

0

0

0

1

0

0

0

0

40

M

X16

0

0

0

0

0

0

0

0

0

1

1

1

0

0

0

1

0

0

0

30

M

X17

1

0

0

1

0

0

1

0

0

1

0

0

0

0

0

0

1

0

0

50

M

X18

0

1

0

0

1

0

0

1

0

0

1

0

0

0

0

0

0

1

0

90

M

X19

0

0

1

0

0

1

0

0

1

0

0

1

0

0

0

0

0

0

1

70

2M

0

0

0

0

0

0

0

420M

2M

0

0

0

0

0

0

0

420M

Min Zj - Cj 2M-6 2M-7 2M-5 2M-8

Zj

2M

2M

2M

2M

2M20

X10 X11 X12 X13 X14 X15 X16 X17 X18 X19

2M-5 2M-4 2M-3 2M 2M-1

2M

Solución

2M

2M

2M

2M

2M

2M

2M

Min = - Max y para M = 100 (Multiplicamos la ultima fila por -1 y remplazamos a M por 100). Sigue:

M

ZjCj

1

-

1

1 ax

9

-

-

-

-

-

-

-

-

-

1

1

1

1

1

1

2

2

2

9

8

9

9

9

9

0

0

0

2

0

9

5

6

7

0

0

0

9 9

4

5 3

0

0

0

0

0

0

0

-42000

Aplicar el software y obtiene la solución optima.

EL PROBLEMA DE ASIGNACION

El problema de asignación se presenta en diversos casos de toma de decisiones.Por ejemplo los problemas típicos de asignación implican asignar tareas a máquinas. trabajadores a tareas y proyectos ,personas de ventas a territorios de ventas, contratos a licitantes . Una característica es que se asignan uno a uno . por ejemplo una maquina a un obrero, un trabajador una tarea , un proyecto a un analista, un contrato a un licitante, se busca el conjunto de asignaciones que optimice el objetivo planteado tal como minimizar costos, minimizar tiempos o maximizar utilidades

Utilizamos el problema de la programación lineal para resolver el problema de Asignación, para ello definimos los siguientes parámetros y variables, El problema de asignación implica n agentes y m tareas si se hace que:

i = Índice para los orígenes o tareas i = 1, 2, 3, …..m

j = índice para los destinos o agentes

j = 1, 2, 3 … n

X ij = 1 Número de unidades que se asignan del origen i al destino j

C ij = Costo de asignar el agente i

ai

= 1

bj =

a la tarea j

unidad ofrecida

1 unidad

Demandada

El modelo general de programación lineal problema de asignación es :

m n

Minimizar Z =

  Cij X ij 1 1

Sujetos:

n

 X ij  1 i= 1, 2, 3, ..

m

1

m

 X ij  1 j= 1, 2, 3, .. n 1

m

n

1

1

 ai =  bj

condición necesaria

Xij  0 para toda

i = 1, 2, 3, . . . m

y

toda

j = 1, 2, 3, …n

Ejemplo: La empresa EVA tiene tres maquinas y tres trabajadores respectivamente y desea asignar una maquina a cada trabajador, en la tabla siguiente se definen las variables y los costos de asignación por unida en miles de pesos , Cual es el programa de costo mínimo optimo . 2

Trabaj 1

ui 3

Maquinas 1

X 11 7

X 12

5

X 13

6

1

2

X 21

8

X 22

10

X 23

9

1

3

X 31

5

X 32

3

X 33

4

1

Bj

1

1

1

3

3

Solución

1.

Construimos la red de distribución

MAQUINAS

TRABAJADORES

7 1

1 5 6

8 10 2

2 9

5

3

3

3 4

2.

IGUALAR OFERTAS Y DEMANDAS

Si las ofertas son mayores agregamos un cliente ficticio con costos cero, para que asuma la diferencia de las demandas, en caso contrario agregamos una planta ficticia con costos cero para que asuma la diferencia de las ofertas, de esta forma tenemos la tabla equilibrada o igualada o estandarizada. En este caso ya esta igualada o estandarizada tres maquinas y tres trabajadores.

TABLA ESTANDARIZADA O IGUALADA

ui

TRABAJADORES

1

2

3

X 11

X 12

5

X 13

6

1

X 22

10

X 23

9

1

X 32

3

X 33

4

1

MAQUINAS 1

7 2

X 21 8

3

X 31 5

Bj

1

1

1

3

3

3. CONSTRUIR EL MODELO MATEMÁTICO DE LA PROGRAMACIÓN LINEAL MODELO MATEMATICO DE LA PROGRAMACION LINEAL

Minimizar Z = 7X 11 + 5 X 12 + 6 X + 8 X 21 +10 X 22 + +9X + 5 X + 3X +4 X 13

23

31

32

33

Sujeto a :

1.

X 11 + X 12 +

X

13

=

1

0ferta

2.

X 21 + X 22 +

X

3.

X + X

X

31

32

+

23

33

=

1

0ferta

=

1

oferta

4.

X 11 . + X 21 . +

X . = 1 demanda

5.

X 12 + X 22 +

X

32

= 1 demanda

6.

X

X

33

= 1 demanda

Xij



13

0

+ X

23

+

i = 1, 2, 3

31

y

j = 1, 2, 3

4. EQUIVALENCIA DE VARIABLES

X 11 = X1

X 12 = X2

X = X3 13

X 21 = X4

X = X7 31

X10 = A10

X14 = A14

X 22 = X5

X = X8 32

X = 23

X6

X = X9 33

X11 = A11 X12 = A12

X13 = A13

X15 =A15

MODELO MATEMATICO DE LA PROGRAMACION LINEAL EQUIVALENTE

Minimizar Z = 7 X1 + 5 X2 +6 X3 + 8X4 X6

+ 10 X5 + 9

+ 5 X7 + 3 X8 + 4 X9

Sujeto a :

1.

X1 + X2 + X3

= 1

0ferta

2.

X4 + X5 + X6

= 1

oferta

3.

X7 + X8 + X9

= 1

oferta

4.

X1. +

X4 + X7

=

5.

X2 +

X5 + X8

= 1 demanda

6.

X3 +

X6 + X9

=

1 demanda

1

demanda

Xj



0

j = 1, 2, 3,4,5,6,7,8,9

6. APLICACIÓN DE LA TABLA DE IGUALAR DEL SIMPLEX

TABLA DE IGUALAR DEL SIMPLEX

TIPO

Agregar a:

DE

La

La Función Objetivo

RESTRICCIÓN

Restricción

Menor o igual

V. De Holgura



+S

Maximizar

Minimizar

+OS

+OS

+OS-MA

+OS+MA

-M*A

+MA

V. Excedente y Mayor o igual

Artificial



-S+A

Igualdad

Variable Artificial

=

A

MODELO MATEMATICO SIMPLEX

Minimizar 9X6

Z = 6 X1 + 7 X2 +5 X3 + 8X4

+ 10 X5 +

+ 5 X7 + 3 X8 + 4 X9 + MX10 MX12+MX13 + MX14 + MX15

+M X11 +

Sujeto a :

1.

X1 + X2 + X3 +

X10 =

2. X4 + X5 + X6 +

3. X7 + X8 + X9 +

4.

X1. + X4. +

1

X11 =

X12 =

1

1

X7. + X13 =

1

5.

X2 + X5 +

X8 +

X14 =

6.

X 3 + X6 +

X9

X15

Xj



0

+

1

= 1

j = 1, 2, 3,4,5,6,7,8,9,10,11,12,13,14,15

7. CONSTRUCCION DE LA TABLA DE LA SOLUCION INICIAL SOLUCIÓN INICIAL SIMPLEX

Cj

6

7

5

8

10

9

5

3

4

M

M

M

M

M

M

b

Cb

Base

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

X11

X12

X13

X14

X15

solución

M

X10

1

1

1

0

0

0

0

0

0

1

0

0

0

0

0

1

M

X11

0

0

0

1

1

1

0

0

0

0

1

0

0

0

0

1

M

X12

0

0

0

0

0

0

1

1

1

0

0

1

0

0

0

1

M

X13

1

0

0

1

0

0

1

0

0

0

0

0

1

0

0

1

M

X14

0

1

0

0

1

0

0

1

0

0

0

0

0

1

M

X15

0

0

1

0

0

1

0

0

1

0

0

0

0

0

1

1

2M-5

2M-3

2M-4

0

0

0

0

0

6M

M

M

M

M

Zj - C j Min

Zj

2M2M-7 2M-5 2M-8 2M-10 6 2M

2M

2M

2M

2M-9

2M

0

1

0

2M

2M

2M

2M

M

M

Min = - Max y para M = 100 (Multiplicamos la ultima fila por -1 y remplazamos a M por 100). Sigue:

-Máx.

Zj-Cj

1

-

-1

-

-

-

-

-

-

1

9

1

1

1

1

1

1

9

5

9

9

9

9

9

9

2

9

1

5

7

6

0 0

0

0

9 4 3

Aplicar el software y obtiene la solución óptima.

0

0

-600

REFERENCIAS BIBLIOGRÁFICAS

Hamdy A. Taha, Investigación de Operaciones, México, Ediciones Alfa

Omega

S.A, 1991.

G. D Eppen/ F. J Gould, Investigación de Operaciones en las Ciencias Administrativas, México, Editorial PRENTICE – Hall Hispanoamericana S. A, 1992

David R. Anderson, Dennis J. Sweeney, Thomas A. Williams, Introducción a los modelos cuantitativos para administración, México, Grupo Editorial Iberoamérica, 1993.

Frederick S.

Hillier / Gerald J. Lieberman, Introducción a la investigación de

operaciones, México, editorial McGraw-Hill, 1998.

Mokhtar S. Bazaraa / Jhon J. Jarvis, programación lineal y flujo en redes, México, editorial Limusa S. A, 1992.

Herbert Moskowitz / Gordon P. Wright, Investigación de operaciones, Colombia, editorial Prentice / Hall Internacional, 1982.

investigacion de operaciones Mohammad Naghi Namakforoosh Editorial Limusa 1989 Dr. ciencias admitivas UAM Universidad Autonoma De Mexico