sin título de diapositiva - jhanoverbr.weebly.com · 1 m3 $ 1000 c/u caja tipo 1 1.2 m3 $ 1120 c/u...

29
4-1 Clase # 4 FORMULACIÓN DE MODELOS DE PROGRAMACIÓN LINEAL

Upload: buikhanh

Post on 12-Oct-2018

224 views

Category:

Documents


0 download

TRANSCRIPT

4-1

Clase # 4

FORMULACIÓN DE MODELOS

DE

PROGRAMACIÓN LINEAL

4-2

CONTENIDO

• 1. Etapas en la Formulación del Modelo • 2. Ejemplo 1: Asignación de Recursos• 3. Ejemplo 2: Formulación de Dietas• 4. Ejemplo 3: Programación de personal• 5. Ejemplo 4: Análisis de Inversiones

4-3

1. Etapas en la Formulación del Modelo

1.1 Definición de Variables 1.2 Coeficientes de costos (o de utilidades)1.3 Función Objetivo (F. O.)1.4 Término independiente o del lado derecho

(recursos o requerimientos)1.5 Coeficientes tecnológicos1.6 Restricciones funcionales1.7 Restricciones de signo de las variables

4-4

2. Ejemplo 1: Asignación de Recursos

El señor Martínez tiene un pequeño camión con capacidad interior de 20m3 en el cual transporta mercancía.

Una reconocida empresa de la ciudad le ha contratado para hacer acarreos de esta mercancía, desde la planta de producción, hacia los puntos de distribución.

La mercancía está empacada en cajas de 3 tamaños diferentes. Además la ganancia por transportar cada tipo de caja es distinta.

sigue

4-5

1 m3

$ 1000 c/uCaja tipo 1

1.2 m3

$ 1120 c/uCaja tipo 2

0.8 m3

$ 900 c/uCaja tipo 3

¿ Cómo debe llenar el señor Martínez su camión para maximizar las ganancias en cada viaje que realice, si tiene que transportar como mínimo 8 cajas tipo 1 y 5 cajas tipo 3 en cada viaje ?

4-6

2.1 Definición de Variables.2.1 Definición de Variables.

XX11 : Número de cajas tipo 1 : Número de cajas tipo 1 transportados en cada viaje transportados en cada viaje [[caja/viajecaja/viaje ]]

XX22 : Número de cajas tipo 2 : Número de cajas tipo 2 transportados en cada viaje transportados en cada viaje [[caja/viajecaja/viaje ]]

XX33 : Número de cajas tipo 3 : Número de cajas tipo 3 transportados en cada viaje transportados en cada viaje [[caja/viajecaja/viaje ]]

4-7

2.2 Coeficientes de costo (utilidad): Datos2.2 Coeficientes de costo (utilidad): Datos

2.3 Medida de la eficiencia (F. O.)2.3 Medida de la eficiencia (F. O.)

ZZ : Ganancia total (pesos) por el transporte de : Ganancia total (pesos) por el transporte de los 3 tipos de cajas en cada viaje.los 3 tipos de cajas en cada viaje.

MaxMax Z = 1000XZ = 1000X11 + 1120X+ 1120X2 2 + 900X+ 900X33

[$[$/ caja/ caja]] * * [[ caja/viajecaja/viaje]] ==[$[$/ viaje/ viaje]]

4-8

2.6 Restricciones funcionales 2.6 Restricciones funcionales R1: Capacidad del camión (recurso) R1: Capacidad del camión (recurso)

1X1X11 + 1.2X+ 1.2X22 + 0.8 X+ 0.8 X33 ≤≤ 20 20 [m[m33/ caja/ caja]] * * [[caja/viaje caja/viaje ]] ==[m[m3 3 /viaje/viaje]]

R2 : Mínimo de mercancía tipo 2 (requerimiento) R2 : Mínimo de mercancía tipo 2 (requerimiento) XX11 ≥≥ 8 8 [[caja/viaje caja/viaje ]]

R3 : Mínimo de mercancía tipo 2 (requerimiento)R3 : Mínimo de mercancía tipo 2 (requerimiento)XX3 3 ≥≥ 5 5 [[caja/viaje caja/viaje ]]

2.7 Restricción de signo de las variables 2.7 Restricción de signo de las variables

XX11 , X, X2 2 , X, X33 ≥≥ 00

4-9

••Modelo completo.Modelo completo.

MaxMax Z = 1000XZ = 1000X11 + 1120X+ 1120X2 2 + 900X+ 900X33

s.as.a1X1X11 + 1.2X+ 1.2X22 + 0.8 X+ 0.8 X33 ≤≤ 20 20

XX11 ≥≥ 88

XX3 3 ≥≥ 55

XX11 , X, X2 2 , X, X33 ≥≥ 00

4-10

3. Ejemplo 2: Formulación de DietasLa señora María Eugenia, dietista del Hospital General, es la responsable de la planeación y administración de los requerimientos alimenticios de los pacientes.

En la actualidad examina el caso de un paciente, a quien se le ha formulado una dieta especial que consta de 2 fuentes alimenticias.

Al paciente no se le ha restringido la cantidad de alimentos que puede consumir; sin embargo, deben satisfacerse ciertos requerimientos nutricionales mínimos por día. sigue

4-11

Nutriente ANutriente A

RequerimientoRequerimientomínimo mínimo

(en unidades)(en unidades)

Contenido Contenido por onzapor onzaalimento 2alimento 2

(en unidades)(en unidades)

Nutriente BNutriente B

Nutriente CNutriente C

Contenido Contenido por onzapor onzaalimento 1alimento 1

(en unidades)(en unidades)

10001000

20002000

15001500

100100

400400

200200

200200

250250

200200

Costo de alimento ($/libra)Costo de alimento ($/libra) 66 88

La señora María Eugenia, desea determinar la La señora María Eugenia, desea determinar la combinación de fuentes alimenticias que arroje el combinación de fuentes alimenticias que arroje el menor costo y satisfaga todos los requerimientos menor costo y satisfaga todos los requerimientos nutritivos.nutritivos.

4-12

3.1 Definición de Variables3.1 Definición de Variables

XX11 : Número de onzas de la fuente : Número de onzas de la fuente alimenticia tipo 1 que deben alimenticia tipo 1 que deben consumirse diariamente consumirse diariamente [[ onzas onzas ]]

XX22 : Número de onzas de la fuente : Número de onzas de la fuente alimenticia tipo 2 que deben alimenticia tipo 2 que deben consumirse diariamente consumirse diariamente [[ onzas onzas ]]

4-13

3.2 Coeficientes de costo: Datos 3.2 Coeficientes de costo: Datos

3.3 Medida de la eficiencia (F. O.)3.3 Medida de la eficiencia (F. O.)ZZ: Costo de suministrarle los 2 tipos de : Costo de suministrarle los 2 tipos de

alimentos al pacientealimentos al pacienteMinMin Z = 0.375XZ = 0.375X11 + 0.5X+ 0.5X2 2

[$[$/ onza/ onza]] * * [[ onzaonza]] ==[$][$]

Nota: Recuerde que los costos de las fuentes alimenticias se expresaron en libras y no en onzas. Por tanto c1 = $6/16 = $0.375 por onza , y c2 = $8/16 = $0.5 por onza. (libra= 16 onzas)

4-14

3.6 Restricciones funcionales3.6 Restricciones funcionalesR1: Consumo mínimo de nutriente A R1: Consumo mínimo de nutriente A

100X100X11 + 200X+ 200X22 ≥≥ 10001000[[unidades/ onzaunidades/ onza]] * * [[ onza onza ]] ==[[unidadesunidades]]

R2: Consumo mínimo de nutriente B R2: Consumo mínimo de nutriente B 400X400X11 + 250X+ 250X22 ≥≥ 20002000

[[unidades/ onzaunidades/ onza]] * * [[ onza onza ]] ==[[unidadesunidades]]

R3: Consumo mínimo de nutriente CR3: Consumo mínimo de nutriente C200X200X11 + 200X+ 200X22 ≥≥ 15001500

[[unidades/ onzaunidades/ onza]] * * [[ onza onza ]] ==[[unidadesunidades]]

3.7 Restricciones de signo de las variables 3.7 Restricciones de signo de las variables XX11 , X, X2 2 ≥≥ 00

4-15

••Modelo completo.Modelo completo.

MinMin Z = 0.375XZ = 0.375X11 + 0.5X+ 0.5X22

s.as.a100X100X11 + 200X+ 200X22 ≥≥ 10001000

400X400X11 + 250X+ 250X22 ≥≥ 20002000

200X200X11 + 200X+ 200X22 ≥≥ 15001500

XX11 , X, X2 2 ≥≥ 00

4-16

4 Ejemplo 3: Programación de personalUnion Airways va a agregar vuelos desde y hacia su aeropuerto base, y por lo tanto necesita contratar más agentes de servicio al cliente. Sin embargo, no está claro cuantos más debe contratar.

La administración reconoce la necesidad de controlar el costo y al mismo tiempo brindar un nivel de atención satisfactorio

Se ha realizado un análisis del número mínimo de agentes de servicio que deben encontrarse de guardia en diferente momentos del día para proporcionar un nivel satisfactorio de servicio

sigue

4-17

TurnoTurno

√√√√√√

PeríodoPeríodo

√√ √√

√√ √√

√√√√

6:00 6:00 amam a 8:00ama 8:00am11 33 44 5522

Número mínimo Número mínimo de agentesde agentesnecesariosnecesarios

Costo diario Costo diario por agentepor agente

Períodos cubiertosPeríodos cubiertos

8:00 8:00 amam a 10:00ama 10:00am10:00 10:00 amam a 12:00ama 12:00am12:00 12:00 amam a 2:00pma 2:00pm2:00 2:00 pmpm a 4:00pma 4:00pm4:00 4:00 pmpm a 6:00pma 6:00pm6:00 6:00 pmpm a 8:00pma 8:00pm8:00 8:00 pmpm a 10:00pma 10:00pm

10:00 10:00 pmpm a 12:00pma 12:00pm12:00 12:00 pmpm a 6:00ama 6:00am

√√ √√√√√√√√

√√ √√

√√

√√

4848797965658787646473738282434352521515

170170 175175 180180 195195160160

4-18

Se ha acordado que cada agente trabaje un turno de 8 horas, 5 días a la semana en los turnos mostrados en la tabla anterior.

Los salarios de cada turno son diferentes debido a que unos son más deseables que otros.

La compañía debe determinar cuántos agentes deben asignarse a los turnos respectivos cada día para minimizar el costo total del personal, debido a los agentes, según el último renglón de la tabla anterior. Los requerimientos mínimos de servicio deben cumplirse obligatoriamente, pero pueden sobrepasarse.

4-19

4.1 Definición de Variables4.1 Definición de Variables

XXjj: Número de agentes asignados : Número de agentes asignados al turno j al turno j

[[ agentesagentes]] j= 1,2,3,4,5.j= 1,2,3,4,5.

4.2 Coeficientes de costo: Datos4.2 Coeficientes de costo: Datos

4-20

••4.3 Medida de la eficiencia (F. O.)4.3 Medida de la eficiencia (F. O.)

ZZ: Costo total de los agentes asignados a los 5 : Costo total de los agentes asignados a los 5 turnosturnos

MinMin Z = 170XZ = 170X11 + 160X+ 160X2 2 + 175X+ 175X3 3 + 180X+ 180X4 4 + 195X+ 195X5 5

[$[$/ agente/ agente]] * * [[ agenteagente]] = = [$][$]

4-21

4.6 Restricciones funcionales 4.6 Restricciones funcionales A excepción de las restricciones de no negatividad, A excepción de las restricciones de no negatividad, todas las restricciones de este problema se basan en todas las restricciones de este problema se basan en el hecho de que existe un requerimiento mínimo de el hecho de que existe un requerimiento mínimo de personal en cada período. personal en cada período. [agente[agentess]]

XX11 ≥≥ 4848XX1 1 + X+ X2 2 ≥≥ 7979XX1 1 + X+ X2 2 ≥≥ 6565XX11 + X+ X2 2 + X+ X33 ≥≥ 8787

XX2 2 + X+ X33 ≥≥ 6464XX3 3 + X+ X44 ≥≥ 7373XX3 3 + X+ X44 ≥≥ 8282

XX44 ≥≥ 4343XX44 + X+ X55 ≥≥ 5252

XX55 ≥≥ 5252

6:00 6:00 amam a 8:00ama 8:00am

8:00 8:00 amam a 10:00ama 10:00am

10:00 10:00 amam a 12:00ama 12:00am

12:00 12:00 amam a 2:00pma 2:00pm

2:00 2:00 pmpm a 4:00pma 4:00pm

4:00 4:00 pmpm a 6:00pma 6:00pm

6:00 6:00 pmpm a 8:00pma 8:00pm

8:00 8:00 pmpm a 10:00pma 10:00pm

10:00 10:00 pmpm a 12:00pma 12:00pm

12:00 12:00 pmpm a 6:00ama 6:00am

Xj ≥≥ 0 para j= 1,..,5

4-22

Algunas de estas restricciones son redundantes:Algunas de estas restricciones son redundantes:

XX1 1 + X+ X2 2 ≥≥ 7979XX1 1 + X+ X2 2 ≥≥ 6565 RedundanteRedundante

XX3 3 + X+ X44 ≥≥ 7373XX3 3 + X+ X44 ≥≥ 8282

RedundanteRedundante

Las restricciones de no negatividad de las variables X1, X4, X5, también sobran, pues tienen cotas inferiores por encima de cero.

4-23

••Modelo completo.Modelo completo.

MinMin Z = 170XZ = 170X11 + 160X+ 160X2 2 + 175X+ 175X3 3 + 180X+ 180X4 4 + 195X+ 195X55

s.as.a XX11 ≥≥ 4848XX1 1 + X+ X2 2 ≥≥ 7979XX1 1 + X+ X2 2 ≥≥ 6565XX11 + X+ X2 2 + X+ X33 ≥≥ 8787

XX2 2 + X+ X33 ≥≥ 6464XX3 3 + X+ X44 ≥≥ 7373XX3 3 + X+ X44 ≥≥ 8282

XX44 ≥≥ 4343XX44 + X+ X55 ≥≥ 5252

XX55 ≥≥ 5252Xj ≥≥ 0 para j= 1,..,5

4-24

5. Ejemplo 4: Análisis de InversionesUn banco trata de determinar su portafolio de inversiones para el próximo año. Actualmente dispone de US$ 500000 para invertir en bonos, prestamos hipotecarios, préstamos para compra de automóviles y préstamos personales.

La tasa de rendimiento anual para cada inversión resulta ser:

• Bonos : 10%• Préstamos hipotecarios : 16%• Préstamos para compra de automóviles : 13%• Préstamos personales : 20%

sigue

4-25

Para asegurar que la cartera del banco no sea demasiado arriesgada, el gerente de inversiones del banco ha puesto las siguientes 3 restricciones de cartera:

1. La cantidad invertida en préstamos personales, no puede ser mayor que la invertida en bonos.2. La cantidad invertida en préstamos hipotecarios, no puede ser mayor que la invertida en préstamos para automóviles.3. No puede invertirse más del 25% de la cantidad total invertida, en préstamos personales.

El objetivo del banco es maximizar el rendimiento anual de su cartera de inversiones.

4-26

5.1 Definición de Variables5.1 Definición de Variables

XXjj : Cantidad de dinero a invertir : Cantidad de dinero a invertir durante el año en la opción j durante el año en la opción j

[[ US$US$]] j= 1,2,3,4.j= 1,2,3,4.

1. Bonos 2. Préstamos hipotecarios 3. Préstamos para compra de automóviles4. Préstamos personales

4-27

5.2 Coeficientes de costo: Datos5.2 Coeficientes de costo: Datos

5.3 Medida de la eficiencia (F. O.)5.3 Medida de la eficiencia (F. O.)

ZZ: Ganancia total de las inversiones : Ganancia total de las inversiones hechas durante el añohechas durante el año

MaxMax Z = 0.1XZ = 0.1X11 + 0.16X+ 0.16X2 2 + 0.13X+ 0.13X3 3 + 0.2X+ 0.2X4 4

[US$][US$]

4-28

5.6 Restricciones funcionales5.6 Restricciones funcionales

R1: R1: La cantidad invertida en préstamos personales, no puede ser mayor que la invertida en bonos.

XX44 ≤≤ XX11 [[US$US$]]

R2: R2: La cantidad invertida en préstamos hipotecarios, no puede ser mayor que la invertida en préstamos para automóviles. XX22 ≤≤ XX33 [[US$US$]]

R3: R3: No puede invertirse más del 25% de la cantidad total invertida, en préstamos personales.

XX44 ≤≤ 0.25*0.25*( ( XX11 ++XX2 2 ++XX3 3 ++XX44 ) ) [[US$US$]]

R4: R4: La empresa posee solamente US$ 500000 para invertir. XX11 ++XX2 2 ++XX3 3 ++XX4 4 ≤≤ 500000 [500000 [US$US$]]

4-29

••Modelo completo.Modelo completo.

MaxMax Z = 0.1XZ = 0.1X11 + 0.16X+ 0.16X2 2 + 0.13X+ 0.13X3 3 + 0.2X+ 0.2X4 4

s.as.a--XX11 +X+X44 ≤≤ 00

XX2 2 -- XX33 ≤≤ 00

XX11 ++XX2 2 ++XX3 3 -- 33XX4 4 ≥≥ 00

XX11 ++XX2 2 ++XX3 3 ++XX4 4 ≤≤ 500000500000

XX11 , X, X2 2 , X, X3 3 , X, X4 4 ≥≥ 00