Cochabamba_bolivia.pdf

UNIVERSIDAD MAYOR DE SAN SIMON FACULTAD DE CIENCIAS Y TECNOLOGÍA

INVESTIGACIÓN OPERATIVA 1

Cochabamba – Bolivia

1

ÍNDICE 1. Introducción a la investigación de operaciones 1.1. 1.2. 1.3.

Introducción Concepto de la I.O. Herramientas de la I.O.

2. El modelo de programación lineal 2.1. Introducción 2.2. Concepto del modelo de programación lineal (p.l.) 2.3. Estructura matemática del modelo de p.l. 2.4. Formas de representar el modelo de p.l. 2.4.1. Forma canónica 2.4.2. Forma estándar 2.5. Formulación matemática del modelo de p.l. 2.6. Soluciones normales del modelo de p.l. 2.6.1. Método gráfico 2.6.2. Método simplex 2.6.3. Variaciones del simplex 2.6.3.1. Método de las Ms. 2.7. Soluciones especiales 2.7.1. El modelo de p.l. es no acotado(N.A.) 2.7.2. El modelo de p.l. no tiene solución básica factible (N.T.S.B.F.) 2.7.3. El modelo de p.l. tiene soluciones múltiples (S.M.) 3. La teoría de la dualidad 3.1. 3.2. 3.3. 3.4.

Introducción Concepto de dual Aplicaciones de la teoría de la dualidad Las condiciones del simplex y la teoría de la dualidad

4. La teoría de redes 4.1. 4.2. 4.3. 4.4. 4.5. 4.6.

Introducción Conceptos básicos El problema de la ruta más corta El problema del árbol de comunicación mínima El problema del flujo máximo Ejercicios

5. El modelo de transporte 5.1. 5.2. 5.3. 5.4. 5.5.

Introducción Concepto del Modelo de transporte Matriz del costo de transporte Formulación matemática del modelo de transporte Solución del modelo de transporte

6. Bibliografía

2

1. Introducción a la investigación de operaciones 1.1. Introducción El objetivo del análisis de este tema es el de caracterizar los siguientes conceptos: 1. ¿Qué es la I.O.? 2. ¿Cuál es la evolución histórica de la I.O.? 3. ¿Cuáles son las herramientas y el campo de acción de la I.O.? 1.2. Concepto de la I.O. Mundo Real Problema [Sistema]

Mundo Ideal Modelo

Método científico

Decisión

Resultados Óptimos

La investigación de operaciones es la utilización del método científico en el análisis y solución de problemas del mundo real (industria, economía, comercio, educación, defensa, etc.). Estos problemas deben ser concebidos como sistemas y entidades complejas que manejan recursos (equipos, útiles, información). Estos sistemas son representados en el mundo ideal por modelos matemáticos cuyo análisis y solución busca la optimización de resultados que deben ser interpretados y comprometidos para ofrecer asesoramiento y ayudar a la toma de decisiones. 1.3. Herramientas de la I.O. Entre algunas herramientas de la I.O. se tiene: 1. El modelo de p.l. 2. El modelo de transporte 3. La teoría de redes 4. La teoría de la decisión 5. Las cadenas de Markov 6. La programación dinámica 7. La programación entera 8. La teoría de colas 9. La simulación 10. La programación mixta 11. La programación no lineal 12. Inteligencia artificial 13. Etc.

3

2. El modelo de programación lineal (p.l.) 2.1. Introducción El modelo de p.l. es una herramienta decisional y de optimización de la I.O. Esta herramienta esta dentro del campo de optimización restringido (limitantes, restricciones) disponibilidad de recursos. En este modelo todas las ecuaciones son del tipo lineal. Toda ecuación y/o función lineal debe cumplir con dos propiedades importantes: 1) Homogeneidad Una función es homogénea si al cambiar en la proporción constante todas las variables independientes, el valor de la función también cambia en la misma proporción . ,

,…,

,

,…,

2) Aditividad Una función es aditiva si el valor de la función para la suma de dos conjuntos de variables independientes, es igual a la suma de las funciones para cada uno de los conjuntos de variables. ,

,…,

,

,…,

,

,…,

Ambas condiciones se pueden expresar en solo una de la siguiente manera: ,

Ejemplos:

,…,

,

,…,

,

,…,

7

" !

Demostrar si las siguientes funciones son lineales o no. a)

b)

,

,

2

,

5

4

,

2

,

,

7 ,

,

, ,

,

,

,

,

" !

,

" !

" !

,

,

" !

4

,

4

" !

" !

5 5

2

, " !

,

2

" !

7

4

4 4

5

7

,

5

" !

4

,

2

7

,

" !

" !

4

7 ,

4

" !

,

" !

7

7

" !

" !

" !

c)

,

#

,

,

$

,

#

%

,

,

#

Lo que hace la herramienta es ver como se distribuyen los “n” recursos limitados a “n” actividades. Recursos (tiempo, personas, dinero, etc.)

Actividades (compras, organizar casa, etc.)

2 2

. . .

. . . 2

Optimizar significa maximizar utilidades (U = I – G) o ganancias y minimizar pérdidas o costos.

2.2. Concepto del modelo de p.l. El modelo de p.l. es una herramienta decisional y de optimización de la I.O. cuyo objetivo fundamental es optimizar una función objetivo (función económica), tomando en cuenta una serie de limitantes o restricciones, cuyo objetivo último es la toma de decisiones. 2.3. Estructura matemática del modelo de p.l. Son tres los elementos y componentes del modelo de p.l.: 1. Definición de variables. 2. La función objetivo [F.O.] también llamada función económica [F.E.] [$us]. 3. Restricciones: [S.A.] (Sujeto a) 1. Restricciones funcionales. restricciones. 2. Restricciones de no negatividad. Forma desarrollada: 1º) Definir variables. 2º) &. (. : (*+. : , 3º) 0. 1.:

-

-

.

-/

/

.

-

5

3 +3 -- %

4 -%

3 +3 -- % ,:

-/ :

,

4+ ; ; -%

F/ : -%

-

-

/: =

+ 2

3 2

5

;

%

; -

%

4 -ó -%%

+ + - % ó< -% % -

9

9

< +=; ;> ,

-% óB "D" %

,

. . 8 .

=

9

,…,

;

-

+ -% +% <

2F : 3 -43 % B + ;%

2.4. Formas de representar el modelo de p.l.

7 0@

-+ = ; ; "D"

+ ; ; ; 3 -43 % G4 ; 2

: úB 3% ; = 3 2

6 7 29

3 %*+ B , ;

*é3; ; -%

B: úB 3% ; 3 +3 -- %

6 72 6 72 :

; -

3

%- ;%

-+ = ; ; D

4 -% %

2.4.1. Forma canónica La función objetivo tiene que ser maximizar: max ,

-

-

.

-/

/

Todas las restricciones funcionales deben ser del tipo: 3 +3 -- %

4 -%

5

9

.

-

. . 8 .

9

9

6 L2 6 L2 : 6 L29

Todas las variables decisionales tienen que ser: > ,

2.4.2. Forma estándar

,…,

7 0@

La función objetivo puede ser maximizar o minimizar: max ,

-

-

.

-/

/

.

-

.

-/

/

.

-

Ó min ,

-

-

Todas las restricciones funcionales deben ser del tipo: 3 +3 -- %

4 -%

5

6

9

9

. . 8 .

9

-+ = ; ; "D"

2 2 : 29

Todas las variables decisionales tienen que ser: > ,

Ejemplo F.O.:

min ,

S.A.:

3

2

,…,

7 0@

O4

7

!

O4

4

O5

!

70

!

!

68

74

% 3 +3 < ;% !

60

Determinar el modelo en su forma canónica y estándar. Forma canónica:

F.O.:

max O,

S.A.:

O

O O

O

3

4

4

O2

O O

O

O

O5

!

70

!

O

7

!

6 O4 !

6 O4

!

64

68

70

!

Para

Para

no restringido se realiza el cambio de variable:

!

6 0 se realiza el cambio de variable: !

O

O

!

70

70

R

T O

70 S !

7

60 T

70 !

70

Forma estándar: F.O.:

min ,

S.A.:

3

O

O4 O

O

O

4

O

2

5

!

O

O

70

O7

!

!

4

U

!

4

8

70

!

Donde:

Para

Para

U

= 3 2

= 3 2

70

70

; U% <43 * 3 3 +3 -- % 4* 3 4 * 3 3 +3 - %

no restringido se realiza el cambio de variable:

!

6 0 se realiza el cambio de variable: !

;

O

O

!

R

T O

70 S !

2.5. Formulación matemática del modelo de p.l.

60 T

;

+ *% 6

+ *% 7

70 !

70

No existe una regla general para formular los modelos de p.l. por que la formulación se plantea a partir del razonamiento lógico, solo la práctica puede ayudar, mientras mas formulación se haga mejor. Ejemplos 1) La empresa de confecciones Julyo’s Ltda. Produce y comercializa camisas y pantalones. Cada unidad producida de camisas es vendida en 250 [bs] y cada pantalón en 350 [bs]. El costo de producir una camisa es 150 [bs] y el de pantalón 180 [bs] por unidad. La empresa dispone de un presupuesto semanal para la producción de 10000 [bs]. La producción combinada de ambos artículos no debe exceder las 1200 unidades por semana. El estudio de mercado indica que por cada pantalón comprado, el cliente compra por lo menos dos camisas. Este estudio también recomienda que se deban producir como mínimo 500 camisas, no existiendo limitante alguna para los pantalones. a) Formule el modelo de p.l. de modo que se pueda saber cuantas unidades de camisas y pantalones se deben producir para que la utilidad sea máxima.

8

úB 3% ; 4 ; ; úB 3% ; 4 ; ; W250

max V

F.O.:

*3%;4- 3 ; - B *3%;4- 3 ; * + % 350 X O W150

150

S.A.:

180

180 X

6 10000

72

*%3 B *%3 B

6 1200

,

7 500

70

2) Una compañía opera tres plantas de tratamientos de aguas. El agua de cada una de las plantas se clasifica antes de bombearse en dos calidades: industrial y potable. La capacidad diaria de producción de las plantas de tratamiento, así como sus costos diarios de operación asociado a cada tipo de tratamiento se tabula en la tabla siguiente: Planta de tratamiento

Agua industrial (m3/día)

I II III

4000 6000 1000

Costo de operación (Bs./día) 8000 15000 5000

Agua potable (m3/día) 6000 4000 6000

Costo de operación (Bs./día) 12000 8000 15000

La compañía se comprometió a entregar 60000 [m3] de agua industrial, 70000 [m3] de agua potable. Determinar el número de días que cada planta debería operar durante la siguiente semana. úB 3% ; ;í

!

F.O.:

S.A.:

úB 3% ; ;í

úB 3% ; ;í min \]

6000 ,

!

%* 3 3

%* 3 3

20000

4000

,

%* 3 3

*

+ [ *%3

*

+ [[ *%3

*

+ [[[ *%3

23000

6000

1000

4000

6000

6 7 _ 3 +3 -- % ,

,

9

!

70

B

20000 ! !

!

7 60000 7 70000

; -%U 3

-

B

B

3) La municipalidad de Cochabamba, con objeto de cubrir la demanda de viviendas de la población tiene un proyecto, construir viviendas tipo A y B. Si solo se construyen viviendas tipo A, se pueden construir 15 por hectárea y si se construyen solo viviendas tipo B se pueden construir 20 en una hectárea. El costo por vivienda B y A es 13000 $ y 15000 $ respectivamente. Se ha estimado que la demanda de la vivienda tipo A es cuando menos 30, en cambio el número de viviendas tipo B no representa ninguna condicionante. Se dispone para la construcción de un terreno de 10 hectáreas, en tanto que el presupuesto para este nuevo plan de desarrollo se desea que no exceda a 2000000 $. Finalmente el asesor de la obra sugirió que el número de viviendas tipo B sea al menos 50 unidades mayor que la mitad del número de viviendas tipo A. úB 3% ; = =

F.O.:

S.A.:

;

úB 3% ; = = max a

-%

;

-%

; ;% ; a 15000

1 15

4)

+ *% ` ;

6 2000000

1 20

7 30

,

+34 3 ;

+ *% 1

úB 3% ; = =

13000

7 50

+34 3 ;

6 10

1 2

70

Una compañía produce 2 tipos de calzados deportivos, con caña y sin caña. Con la experiencia y el tiempo de trabajo se ha podido llegar a la conclusión de que se necesita 1 obrero para producir 1 unidad del modelo con caña y 4 obreros para producir una unidad del modelo sin caña (por ser calzado deportivo de última tecnología). El precio de venta de venta es de 350 bs. Por calzado con caña y 280 Bs. Por calzado sin caña. El costo de producción para la compañía es de 80 y 60 Bs. para los modelos con caña y sin caña respectivamente. El capital con el que cuenta la compañía no le permite gastar más de 8000 Bs. semanales. Formule el problema como un modelo de programación lineal, si el número total de obreros disponibles por semana es de 18. úB 3% ; - , ;% -% - ñ

F.O.:

úB 3% ; - , ;% sin - ñ max V

350

280

10

*3%;4- 3 *%3

*3%;4- 3 *%3

O 80

60

B

B

S.A.:

80

60 ,

5)

4

6 800

6 18

70

Un pequeño banco asigna un máximo de Bs. 20000 para préstamos personales y para automóviles durante el mes siguiente. El banco cobra una tasa de interés anual de 14% a préstamos personales y del 12% a préstamos para automóviles, ambos tipos de préstamos se saldan en periodos de tres años. El monto de los prestamos para automóviles debe ser cuando menos dos veces mayor que el de los prestamos personales. La experiencia pasada ha demostrado que los adeudos no cubiertos constituyen el 2% de los préstamos personales. ¿Cómo deben asignarse los fondos? `% =

`% =

F.O.:

% G4 =%e

max [

S.A.:

% G4 =%e

<

<

3 * 3 *3 + B% * 3 %

3 * 3 *3 + B% * 3

3 f 0,14

3 f 0,12

4+%Bó=

O 3 f 0,02

6 20000

,

6)

72

70

Reddy Mikks company posee una pequeña fábrica de pinturas para interiores y exteriores de casas para su distribución al mayoreo. Se utilizan dos materiales básicos, A y B, para producir las pinturas. La disponibilidad máxima de A es 6 toneladas diarias; la de B es de 8 toneladas diarias. La necesidad diaria de materia prima por tonelada de pintura para interiores y exteriores se resume en la tabla que sigue:

Materia prima A Materia prima B

Tonelada de materia prima por tonelada de pintura Exterior Interior 1 2 2 1

Disponibilidad máxima (ton.) 6 8

Un estudio de mercado ha establecido que la demanda diaria de pintura para interiores no puede ser mayor que la de pintura para exteriores en más de una tonelada. Asimismo, el estudio señala que la demanda máxima de pintura para interiores está limitada a dos toneladas diarias. El precio al mayoreo por tonelada es $ 3000 para la pintura de exteriores y $ 2000 para la pintura de interiores. ¿Cuánta pintura para exteriores e interiores debe producir la compañía todos los días para maximizar el ingreso bruto?

11

+% F.O.:

S.A.:

+%

;

*3%;4- 3 ; * +43

;

+ 3 %3 *%3 ;í

*3%;4- 3 ; * +43

max [

3000

2

,

7)

2000

2 6

+ 3 %3 *%3 ;í

66 68

62

1

70

En vista de los buenos resultados que esta obteniendo últimamente el plantel de Wilsterman, existe una gran demanda de heladeros que se dan cita en el Estadio para poder vender su producto, debido a que existe una buena asistencia de público. El precio del helado de cono es de 10 Bs. y el de barquillo 7 Bs. Se necesitan 12 heladeros para poder cubrir con todo el lote de helados de cono y 9 heladeros para cubrir el lote de helados de barquillo, sabiendo que en todo el Estadio están distribuidos 40 heladeros que venden diferentes tipos de helados. Después de haber transcurrido una buena cantidad de partidos se llego a la conclusión de que la gente prefiere helados de barquillo en un número de 7000 como mínimo por partido, contra los helados de cono que se consume en un total de 6500 por fecha como máximo. Que cantidad de helados de ambas clases se debe vender, si el número de helados que se demanda es de 14000. úB 3% ; U

F.O.:

S.A.:

úB 3% ; U

;% ; -% %

;% ; 2 3G4 %

=

max [

10

7

12

9

40

7 7000

6 6500 ,

14000

70

12

=

; 3 *%3 * 3+ ;%

; 3 *%3 * 3+ ;%

8) Una trabajadora tiene dos tipos de tareas en un centro de artesanías a) hilar y b) tejer patrones con el hilo así producido. Produce una unidad de hilo por hora y dos unidades de patrón por hora y se le paga un $ por unidad de hilo y 2.5 $ por unidad de patrón. Desea ganar no menos de 6 $ al día y trabajar como máximo 8 horas diarias. La fibra hilada no debe exceder al hilo consumido en más de dos unidades. El centro requiere que sus salarios por tejidos no excedan a los de hilados en más de 10 $. La ganancia en la venta es de un $ por unidad de hilado y de 3 $ por unidad de tejido. ¿Cuántas unidades de hilado y tejido debe producir la trabajadora al día para maximizar la ganancia por ventas? úB 3% ; 4 ; ; ; U %

F.O.:

úB 3% ; 4 ; ; ; + D ;%

S.A.:

max h

*3%;4- 3 *%3 ;í

3 1 2

68

2,5

2,5

*3%;4- 3 *%3 ;í

76

6 ,

6

2

70

10

9) Cierta sucursal tiene tres plantas sucursales con capacidad de producción en exceso. Las tres plantas tienen los elementos necesarios como para poder producir determinado producto y el gerente ha decidido usar parte de la capacidad de producción en exceso con tal fin. Este producto puede hacerse en tres tamaños: grande, mediano y pequeño, que dan como resultado una utilidad unitaria neta de Bs. 140, Bs. 120 y Bs. 100 respectivamente. Las plantas 1, 2 y 3 tienen la capacidad de mano de obra y equipo en exceso como para producir 750, 900 y 450 unidades por día de este producto, respectivamente, sin importar el tamaño o la combinación de tamaños que se aplique. Sin embargo el espacio de almacenamiento disponible para productos en proceso también impone una limitación sobre las tasas de producción. Las plantas 1, 2 y 3 tienen 13000, 12000 y 5000 pies cuadrados de espacio de almacenamiento disponible para productos en proceso, para un día de producción de este artículo. Cada unidad de los tamaños grande, mediano y pequeño producida por día requiere de 20, 15 y 12 pies cuadrados respectivamente. Los pronósticos de ventas indican que pueden venderse al día 900, 1300 y 750 unidades de los tamaños grande, mediano y pequeño respectivamente como mínimo. Con este fin de mantener una carga uniforme de trabajo y conservar cierta flexibilidad, el gerente ha decidido que la producción adicional asignada a cada planta debe usar el mismo porcentaje de la capacidad de la mano de obra y equipo en exceso. Formular el problema como un modelo de P.L.

13

Tamaños

Utilidad (Bs./unidad)

Grande Mediano Pequeño

140 120 100

Plantas

Capacidad de producción (unidades/día) 750 900 450

1 2 3 F,/

F.O.:

S.A.:

-

+; ;; 4 ; ;

max V

Requerimiento de espacio (pie2/unidad) 20 15 12

140

k

; + B ñ% k

h, i, j

120

k!

20

20

k

m

6 750

k!

l!

m!

6 450

15 15

k

l

750

m

m

m

12

l

15

l k

l!

l

k

k

l

l

12

l

12

l

k

k!

l k

m

l! l

900

F,/

m!

70

Espacio (pie2/día) 13000 12000 5000

*3%;4- 3

k k

20

l

Mínimo de ventas (unidades/día) 900 1300 750

*

+ D 1,2,3 *%3 ;í

100

m

l!

m!

m

m!

6 900 m m

m

6 13000 6 12000 6 5000

7 900

7 1300 7 750 m

k!

450

2.6. Soluciones normales de modelos de p.l. 2.6.1. Método gráfico Este método se recomienda emplear cuando el modelo de p.l. tenga como máximo dos variables decisionales y las restricciones funcionales pueden ser del tipo 6, , 7. Este método permite realizar una interpretación sencilla de la solución del modelo de p.l. Ejemplo

14

max ,

F.O.: S.A.:

5

3

65 n

n"

63 n

6 12 n!

6 9 no

7 0 np

7 0 nq

A. Hallar la solución óptima del modelo B. Realizar el análisis de actividad del modelo n" : 5

10

nq

10 9 8

no

7 6 5 4

Solución óptima

3

n!

2

S

1 0

n" : 5

5

1 2 3

4

n

5

6

n

7

8

9 10

11

12

13

np

14

Cada una de las restricciones se grafican, considerando inicialmente la desigualdad como una igualdad. La región sombreada S se llama región factible. Luego la restricción n" se iguala a cualquier número arbitrario para graficar la recta que este dentro de la región factible y además que este lo más alejado del origen, si el caso es maximizar, y lo más cerca del origen, si el caso es minimizar. Para este ejemplo la solución óptima es la intersección de las rectas n e n _ r 3 ; r 2 Remplazando estos valores en n" se obtiene , r 17 W4BX donde [um] significa unidades monetarias. A. Solución óptima: ,r

17 $ ;

15

r

3;

r

2

B. Análisis de actividad del modelo: Restricciones activas: Es aquella que pasa por el punto solución, es parte de la región factible y tiene una variable de holgura o superflua igual a cero, es decir que se consume todo el recurso. Restricciones inactivas: Es aquella que no pasa por el punto solución, pero es parte de la región factible, y tiene una variable de holgura o superflua diferente de cero, es decir que no se consume todo el recurso. Restricciones redundantes: Son aquellas que no pasan por el punto solución, no son parte de la región factible, tiene una variable de holgura o superflua diferente de cero, la inclusión o no de esta restricción no afecta a la solución óptima del modelo. Para el ejemplo remplazamos los valores óptimos de Restricciones activas:

Restricciones inactivas:

n :

n! :

Restricciones redundantes:

65_3

n : 3

63_3 6 12 _ 3

no :

69_2

2

U

r

y

U

3;U

r

en las restricciones funcionales:

5;U

3 2

U!

Uo

9 ; Uo

0

0

12 ; U!

3

7

Caso 1. Modelos con solución óptima única El modelo es formulado por una empresa asesora de inversiones para elaborar la cartera de un cliente. Las variables X1 y X2 representan la cantidad de acciones Tipo 1 y 2 a comprar para satisfacer el objetivo establecido de maximizar el retorno anual de esa inversión o compra de acciones. El monto total disponible para invertir es de $80.000. El riesgo es una medida relativa de las dos inversiones alternativas. La acción Tipo 1 es una inversión más riesgosa. Limitando el riesgo total para la cartera, la firma inversora evita colocar montos excesivos de la cartera en inversiones de retorno potencialmente alto pero de alto riesgo. También se limita el monto de acciones de mayor riesgo.

a) Graficar las restricciones: Restricción 1: Cuando X1 = 0, entonces X2 = 1.600; Cuando X2 = 0, entonces X1 = 3.200 Una los puntos (3.200, 0) y (0, 1.600). El lado de la restricción (<) está bajo esa recta. Restricción 2: Cuando X1 = 0, entonces X2 = 2.800; Cuando X2 = 0, entonces X1 = 1.400 Una los puntos (1.400, 0) y (0, 2.800). El lado de la restricción (<) está bajo esa recta. Restricción 3: X1 = 1.000 y X2 = 0 Es una recta que parte de la abscisa en el punto 1.000. El lado de la restricción (<) se tiene, a partir de esa recta, hacia el lado donde está el punto de origen.

16

b) Grafique la Función Objetivo asignándole un valor arbitrario. Este valor, preferiblemente, debe permitir que el objetivo se muestre en la región solución. Por ejemplo, puede ser utilizado el valor 3.000. Los puntos de corte en los ejes, para graficarla, son los puntos (1.000, 0) y (0, 600). La Función Objetivo se grafica con línea de color, en este caso, para diferenciarla de las restricciones. c) Mueva la Función Objetivo, paralelamente a sí misma en la dirección que incrementa su valor (hacia arriba en este caso), hasta que toque el último (los últimos, si los toca al mismo tiempo) punto extremo de la región solución. d) En ese punto extremo final, b en este caso, resuelva el par de ecuaciones que se interceptan. En este caso son las ecuaciones 1 y 2. Utilice cualquiera de los métodos para resolver pares de ecuaciones lineales con dos variables. e) Alternativamente, para determinar la solución óptima, puede calcular las coordenadas a todos los puntos extremos: a, b, c y d y e, en el conjunto convexo de soluciones. Luego evalúa la Función Objetivo en cada uno de ellos. El punto extremo que proporcione el mayor valor será el punto extremo óptimo. f) En ambos casos se obtiene la solución óptima en el punto extremo b con coordenadas (800, 1.200). Así, la solución óptima es X1 = 800 y X2 = 1.200. Resolviendo en la Función Objetivo: Max 3X1+ 5X2 Se obtiene: 3(800) + 5(1.200) = 8.400

Caso 2. Modelos con soluciones óptimas alternas o múltiples

El modelo es formulado por una empresa que desea determinar la cantidad de unidades de producto 1 (X1) y producto 2 (X2) a fabricar para satisfacer el objetivo establecido de maximizar el beneficio. El monto total disponible de horas de trabajo para este período es de 48. La disponibilidad de materia prima es de 120 unidades y la cantidad mínima de horas disponibles para supervisión es de 36 horas. Graficar las restricciones y obtener el espacio de solución se efectúa en forma similar al proceso efectuado en el caso 1 y por lo tanto no se repetirán las instrucciones. Los puntos extremos del conjunto convexo son: A (16,0), B (8,24), C (8/3,28) y D (12,0). Dos puntos extremos proporcionan el máximo valor del objetivo, los puntos A y B. Esto permite afirmar que existen soluciones óptimas Alternas para este modelo. Son óptimos todos los puntos sobre el segmento de línea AB que limita el conjunto convexo de solución y corresponden a la primera restricción. Si Usted utiliza el método de graficar la Función Objetivo con un valor arbitrario, 48 por ejemplo, podrá observar que la línea es completamente paralela a la primera y tercera restricción. Al desplazarla paralelamente hacia su optimización, hacia arriba porque se está maximizando, finalmente caerá completamente sobre la primera restricción, de horas de trabajo, antes de salir totalmente fuera de la región solución. Dos puntos extremos estarían limitando el crecimiento del objetivo, el punto B y el punto A. “Cualquier recta que tenga ratio de coeficientes igual al de otra recta, es paralela a esa otra recta”

17

La ventaja que presentan los modelos con este Tipo de solución es que se puede elegir cualquiera de las soluciones óptimas, porque todas presentan el mismo valor óptimo para el objetivo. Por ejemplo, si una de las soluciones tiene valores fraccionales para las variables y no puede trabajarse con valores fraccionales, el que toma la decisión seleccionará una solución con valores enteros.

Caso 3. Modelos sin solución posible No se definirán los elementos del modelo porque no habrá una solución posible para tomar alguna decisión.

Puede observarse en el Gráfico 4, que mientras las 3 primeras restricciones delimitan un espacio en común, las 2 últimas delimitan otro espacio común para ellas. Por lo tanto, no hay una región de puntos comunes que satisfagan ambos conjuntos de restricciones y el modelo no tendrá solución posible. En estos casos es necesario determinar cuáles son las restricciones inconsistentes para el modelo. Es decir, cuáles son realmente válidas para el modelo. Observe que si las variables X1 y X2 toman el valor mínimo que pueden tomar en las dos últimas restricciones, es decir X1 = 30 y X2 = 15 entonces la tercera restricción no se cumpliría. Esto es una inconsistencia. Estos modelos no deben existir en el mundo real. Si el sistema modelado trabaja, entonces el modelo debe representarlo de tal manera que permita obtener una solución posible.

18

Caso 4. Modelos que presentan solución con valor infinito

No se definirán los elementos del modelo porque no habrá una solución para tomar alguna decisión. En el gráfico 5 el conjunto convexo llamado región solución, que contiene todas las soluciones posibles, es un espacio abierto. Tiene tres puntos extremos A, B y C, pero ninguno delimita el crecimiento del objetivo. Esta función puede tomar valores infinitos ya que las variables conforman puntos con valores infinitos dentro de la región solución y ninguno de ellos le proporciona un valor finito óptimo. Por lo tanto, existiendo restricciones, no es lógico encontrar un objetivo de valor infinito. En estos casos debe buscarse dentro del sistema, la restricción o las restricciones que se omitieron en el modelo y que limitarían las variables de decisión a valores factibles.

Caso 5. Modelos con espacio de solución no acotado y solución de valor finito

El modelo es formulado para una guardería de perros que se destaca por dar una alimentación balanceada a las mascotas. El alimento lo elabora mezclando 2 marcas conocidas de alimentos que llamaremos X1 y X2. Se desea determinar la cantidad de gramos de X1 y X2 a mezclar en el alimento, con el objetivo establecido de minimizar los costos de la mezcla. Esta, debe contener al menos 500 gramos de proteínas y al menos 300 gramos de grasa por día. Los porcentajes de contenido de grasa y proteína de cada gramo de X1 y X2 se conocen y son usados en el modelo. El espacio de solución obtenido se muestra en el Gráfico 6. Se observa una región abierta con las soluciones posibles y puntos extremos A, B, C. Esto indica que pueden existir combinaciones de cantidad de gramos de alimento X1 y X2 con valor infinito, en este caso los costos serían infinitos. Esto es posible porque no se está limitando directamente la cantidad de X1 y X2 en alguna restricción específica y las restricciones existentes son todas de Tipo “7que”. Pero, mientras exista al menos una combinación con valor finito, en algún punto extremo que limite el valor del objetivo, a esa combinación se le considerará óptima. En los casos de región abierta de soluciones posibles, es conveniente entonces encontrar el valor óptimo con el procedimiento de graficar la Función Objetivo.

19

Al graficar la Función Objetivo, con un valor arbitrario de 120, se observa que al desplazarla paralelamente hacia su optimización, hacia abajo porque se está minimizando, la línea cae sobre el punto B, antes de salir completamente de la región solución. A este punto se le considerará punto extremo óptimo. La solución óptima es Única con los valores: X1 = 1.500, X2 = 250 F.O. = 102.5

Caso 6. Modelos con solución degenerada

El modelo es formulado por una oficina de correos que puede contratar hasta 10 empleados para manejar el correo. La oficina conoce que un empleado (hombre) puede manejar 300 cartas y 80 paquetes por día y una empleada (mujer) puede manejar 400 cartas y 50 paquetes en un día. No menos de 3.400 cartas y de 680 paquetes se esperan por día. A cada empleado hombre (X), se le paga Bs. 2.500 por día y a una empleada mujer (Y) se le paga Bs. 2.200 por día. Se quiere determinar la cantidad de hombres (X) y mujeres (Y) que se deben contratar para satisfacer las restricciones y lograr el objetivo establecido de minimizar los costos de la nómina. Graficar las restricciones y obtener el espacio de solución se efectúa en forma similar al hecho en el caso 1 y por lo tanto no se repiten las instrucciones. El gráfico obtenido es el Gráfico 7. Se observa una región de soluciones posibles de un solo punto común para todas las restricciones y por lo tanto un único punto extremo A. Esto indica que existe una única combinación posible y además óptima, de cantidad de empleados “X” y “Y” que satisface las restricciones y optimiza el objetivo.

20

2.6.2. Método simplex Se recomienda utilizar este método cuando el modelo de programación lineal tenga dos o más variables decisionales, pero las restricciones funcionales tienen que ser del tipo 6 ; .

Este método involucra seis pasos: Paso #1

Llevar el modelo a su forma estándar y plantear la tabla inicial o iteración cero. Modelo inicial: F.O.:

(*+. : ,

S.A.: 3 +3 -- %

-

-

4 -%

,

Forma estándar: F.O.:

S.A.:

0

3 +3 -- ó

xv

8 xy

0

8 0

/

. . . 8 .

9

,…,

70

-

9

6 6

6

2 2 : 29

O-

O . O -/

/

O .O -

O 0U O 0U O . O 0U9

0

min , O -

O-

O . O -/

/

O .O -

O 0U O 0U O . O 0U9

0

4 -%

6

0

4B

tu O8

9

tv O8

9

= 3 2

3 +3 -- ó ,

Variables no básicas

z 1 0

9

-/

max , O -

Tabla inicial o iteración cero:

F.O. z xu

5

.

… … … …

8 …

,…,

ó

; U% <43 UF e

4 -%

-%

, U , U , … , U9 7 0

<4

-%

3=

Después de una o más iteraciones tienen un incremento ,/

+

tw O-

xu 0 1

xv 0 0

… … …

xy 0 0

8

0

1

…

0

8 0

9

Variables básicas iniciales

21

8 0

8 …

8 1

+ ;

;% ; 3 -U%

L.D. 0 2 2

8 29

z

2 { # 2 { #

{

8 29#

F

F

|

|

F

|

Paso #2 Verificar si la tabla es óptima. Si la función objetivo es maximizar todos los coeficientes de dicha función deben ser cero o positivos y recíprocamente. Si no se cumple se debe pasar al paso #3. Si la F.O. es:

Entonces para que la tabla sea óptima:

max ,

-

-

.

-/

/

.

-

/

.

-

O- , O- , … , O- 7 0 ó

Si la F.O. es:

Entonces para que la tabla sea óptima:

min ,

-

-

.

-/

O- , O- , … , O- 6 0

Paso #3

Se elige el valor más negativo del conjunto >O- , O- , … , O- @, si es la primera iteración, si no se elige el valor más negativo del conjunto >, O - , , O - , … , , O - @, si hay más de uno se elige cualquiera, se marca como columna pivote la columna F 1 6 6 del valor más negativo O-F . Luego se calcula el radio rho: }/

min ~

2F F

• ; } € 0 ; ;% ;

16 6

e 16D6B

Si no se encuentra ningún valor de }, que cumpla las condiciones anteriores, entonces se tiene una solución no acotada y si se encuentra varios se elige cualquiera. La intersección de la columna “i” y la fila “j” es el pivote. Paso #4 Si el pivote es igual a 1 continuar con el paso #5, si no multiplicar la fila “j” por un factor conveniente para que sea 1. Paso #5 Obtener una nueva tabla o iteración haciendo que los valores de la columna “i” sean ceros, excepto el pivote, mediante el método Gauss – Jordan. Paso #6 Verificar si la tabla es óptima. Si la F.O. es:

Entonces para que la tabla sea óptima:

max ,

-

-

22

.

-/

/

.

-

Ó si la F.O. es:

Entonces para que la tabla sea óptima:

, O - ,, O - ,…,, O - 7 0 min ,

-

-

.

-/

/

.

-

, O - ,, O - ,…,, O - 6 0

Donde ,/ es el incremento neto que se opera en el coeficiente -/ a través de las iteraciones.

Si no es la tabla óptima pasar al paso #3.

Ejemplo F.O.:

max ,

S.A.:

5 63 ,

a) Hallar la solución óptima del modelo

65

3

6 12

70

Forma estándar: F.O.:

S.A.:

max ,

5

U

,

3

0U U

U!

3

0U

0U!

5

12

, U , U , U! 7 0

Las variables superfluas y de holgura, s y h, suben a la F.O. con coeficientes 0. F.O.:

max , O 5

O

O 0U O 0U O 0U!

23

0

Tabla inicial o iteración cero:

Si la F.O. es maximizar deben ser 7 0 y si es minimizar deben ser 6 0 para la tabla óptima. F.O.

z

z

1

-5

-1

U

U

0

1

0 0

U

U!

0

U!

L.D.

0

U

0

0

}

0

1

0

0

3

3/1

1

1

0

1

0

5

5/1

1

3

0

0

1

12

12/1

Se elige como fila pivote U por tener el menor radio positivo } 3. Si hay más de uno se elige cualquiera. Y si no hay ninguno es una solución no acotada.

Se elige como pivote por ser la intersección entre la fila pivote y la columna pivote. Si no es igual a 1 se multiplica toda la fila por un factor conveniente para que sea 1. Iteración 1:

5

U

0

U!

L.D.

-1

U

0

15

1

0

1

0

0

3

0

0

1

-1

1

0

2

2/1

0

0

3

-1

0

1

9

9/3

}

F.O.

z

z

1

0

U

0

U!

Se elige como columna pivote por el valor más negativo -5. Si hay más de uno se elige cualquiera.

}

Mediante el método Gauss – Jordan se logra que los valores de la columna sean ceros excepto el pivote. Significa que se llego a la tabla óptima por que todos son 7 0.

Iteración 2: tabla óptima

4

U

1

U!

L.D.

0

U

0

17

1

0

1

1

0

3

0

0

1

-1

1

0

2

0

0

0

2

-3

1

3

F.O.

z

z

1

0

0 U!

Solución óptima: ,r

17 W4. B. X;

•

r

‚.•.

24

W , , U! X WU , U X

W3,2,3X W0,0X

2.6.3. Variaciones del simplex 2.6.3.1. Método de las Ms Llamado también método de penalizaciones, este método puede ser empleado cuando el modelo tiene 2 o más variables decisionales y las restricciones funcionales son del tipo 6 ; ; 7. El término M representa un número muy grande. Los pasos a seguir para la solución del modelo de p.l. son similares al del método simplex, con la excepción de que se corrige la función objetivo. Paso #1 Llevar el modelo a su forma estándar.

Modelo inicial: F.O.:

(*+. : ,

S.A.: 3 +3 -- %

-

-

4 -%

5

S.A.:

3 +3 -- ó

,…,

-/

.

/

-

. . 8 .

9

70

6 72 6 72 : 6 7 29

9

max , O -

O-

O . O -/

/

O .O -

O 0UF O 0

i ƒF

0

min , O -

O-

O . O -/

/

O.O-

O 0UF O 0 F O i ƒF

0

0

0

9

,

Forma estándar: F.O.:

.

0

3 +3 -- ó

3 +3 -- ó

4 -%

7

4 -%

4 -%

3 + 4

,

ó

4B 4

6

= 3 2

,…,

4B 4

= 3 2

4* 3 4

, UF , ƒ F ,

F

= 3 2

70

F

e

F

3+

-

ƒF

; U% <43 UF 4B 4

= 3 2

3+

-

ƒF

Paso #2 Corregir la función objetivo. Las variables básicas iniciales que corresponden a la tabla inicial o iteración cero deben incluir a las variables artificiales, por que sus columnas forman parte de la matriz identidad, pero sus coeficientes en la F.O. no son cero sino M; entonces deberán volverse cero haciendo una corrección a la F.O. y utilizando para ello operaciones elementales de fila con aquellos reglones que incluyen a estas variables.

25

Paso #3 Plantear la tabla inicial y proceder como en el método simplex para obtener la tabla óptima. Ejemplo F.O.:

min ,

S.A.:

5

3

F.O.:

min ,

S.A.:

5

Wn X

63

7 12 Wn! X

1

,

5 Wn X

7 0 Wno X e Wnp X

,

Forma estándar:

Wn" X

1

3

0U

O

,

0

U

!

,U ,

3 !,

!

!

i

!

i

!

5 12

70

Si se multiplica a Z por (-1) para ponerlo en forma de Max (-Z) y pasando todo al primer miembro, se tiene: F.O.:

max O,

Corrección de la F.O.

5

1

0U

0

i

!

i

0

!

Todos los coeficientes de las variables artificiales en la F.O. tienen que ser cero.

Tienen que ser cero (solo las variables artificiales)

n" n

n! n"

5

1

M

U

0

0

M

0

1

1

1

0

0

0

5

1

3

0

0

-1

1

12

-2M+5

-4M+1

0

0

M

0

-17M

!

26

!

L.D.

f Oi

f Oi

n"

n"

F.O. corregida

Tabla inicial o iteración cero con la F.O. corregida:

Se eligen como variables básicas iniciales por que tienen coeficiente cero en la F.O. corregida. F.O. Z U

Z -1 0 0 0

!

-2M+5 1 1 1

-4M+1 1 0 3

U 0 0 1 0

0 1 0 0

Primera iteración aplicando el método simplex:

!

M 0 0 -1

!

0 0 0 1

L.D. -17M 5 3 12

Z

1

-(2/3)M

0

0

U

0

-(1/3)M+1/3

(4/3)M-1/3

-M-4

U

0

2/3

0

1

0

1/3

-(1/3)

1

0

1

0

0

1

0

0

3

0

1/3

1

0

0

-(1/3)

1/3

4

Z

!

!

L.D.

Segunda iteración:

Tienen que ser ≥ 0 por que la F.O. es maximizar.

Z

U

Z -1 0 0 0

0 1 0 0

0 0 0 1

M-7 3/2 -(3/2) -(1/2)

U 0 0 1 0

-2 1/2 -(1/2) -(1/2)

0 0 0 1

M-1 3 0 1

U 0 0 1 0

0 1 0 0

Tercera iteración, tabla óptima: Z

!

U

Z -1 0 0 0

4 2 1 1

Solución óptima: ,r

5 W4. B. X;

r

•

‚.•.

27

W !, U , W , ,

X !X

!

!

W3,3,5X W0,0,0X

!

M+2 -(1/2) 1/2 1/2

!

M -1 0 0

L.D. -11 3/2 3/2 7/2

L.D. -5 3 3 5

2.7.

Soluciones especiales Muchos de los modelos de p.l. pueden tener resultados atípicos (anormales). Analizaremos tres tipos de soluciones anormales. 1. Cuando el modelo de p.l. es no acotado (N.A.). 2. Cuando el modelo de p.l. no tiene solución básica factible (N.T.S.B.F.). 3. Cuando el modelo de p.l. tiene soluciones múltiples (S.M.).

2.7.1. El modelo de p.l. es no acotado La gráfica para el modelo de 2 variables decisionales es:

S

Donde “z” óptimo es indefinido. Si el modelo tiene más de dos variables decisionales existirá la imposibilidad de elegir el pivote en alguna etapa del proceso iterativo. Ejemplo F.O.:

max ,

S.A.:

3

20

O3 O

Forma estándar: F.O.:

S.A.:

max ,

20 3

5

O4 ,

O

O4

5

„ 50

!

U

!

6 20

70

!

!

28

!

!

10 O3

!

!

6 10

!

,

10

0U U

10

U!

0U 50 20

0U!

,

Tabla inicial: Z 1 0 0 0

Z U U U!

-20 3 1 1

,

!, U

U 0 1 0 0

!

-10 -3 0 -1

-1 5 1 4

U!

Z 1 0 0 0

U 0 0 1 0

U! 0 0 0 1

L.D. 0 50 10 20

}

50/3 10 20

No existen valores de rho para continuar.

Primera iteración: Z U

, U , U! 7 0

0 0 1 0

U 0 1 0 0

!

-10 -3 0 -1

19 2 1 -5

U 20 -3 1 -1

… B%; % ; *3%<3 B - ó

U! 0 0 0 1

L.D. 200 20 10 10

}

% -%+ ;%.

2.7.2. El modelo de p.l. no tiene solución básica factible

Si el modelo de programación lineal tiene 2 variables decisionales, existirá la imposibilidad de poder encontrar una región factible S. En cambio si tiene más de 2 variables decisionales en la tabla óptima z aún dependerá de M, y en la base de la tabla óptima se encontrará una variable artificial.

n

n

Ejemplo F.O.:

S.A.:

max , 2

3

2 2

,

3 ,

!

29

!

!

64

!

7 12

70

Forma estándar: F.O.:

2

max ,

S.A.:

3

2

Corrección de la F.O.: n" n n"r

-1 3 -3M-1

2

3

,

!

U

!

O

!, U

,

U 0 0 0

!

-1 2 -2M-1

,

0U O 0

!

-2 1 -M-2

Z 1 0 0

-3M-1 2 3

-2M-1 1 2

Z 0 1 0

ƒ

0 1 0

7/2M-1/2 3/2 -7/2

Segunda iteración y tabla óptima: Z

ƒ

Z 1 0 0

M+1 2 -1

… B%; % % +

0 1 0 % 4- ó 2á -

,ƒ 70

U 2M+1 1 -2

!

5M+1 3 -5 -+ 2

12 Wn X ƒ M 1 0

M 0 -1

U 3/2M+1/2 1/2 -3/2

!

-1/2M-1/2 1/2 1/2

ƒ

U 0 1 0

!

-M-2 3 1

Primera iteración: Z

4 Wn X

0 -1 M

Tabla inicial: Z U ƒ

O i ƒ Wn" X

*%3 G4 ,

M 0 -1

M 0 -1 , i ei

L.D. 0 12 -12M

ƒ 0 0 1

ƒ 0 0 1

ƒ 0 0 1

f Oi

L.D. -12M 4 12

L.D. -6M+2 2 6

L.D. -4M+4 4 4

4 = %3 B4e <3

n" }

2 4

}

4 12

}

; .

2.7.3. El modelo de p.l. tiene soluciones múltiples Si el modelo de programación lineal tiene dos variables decisionales, una de las restricciones funcionales será paralela a la función objetivo. Si el modelo tiene más de dos variables decisionales en la tabla óptima existirán más coeficientes cero que variables básicas.

30

n

n Ejemplo F.O.:

max ,

S.A.:

2 2

3

3 !

!

6 10

65

,

,

61 !

70

Forma estándar: F.O.:

max ,

S.A.:

,

Tabla inicial: Z U U U!

Z 1 0 0 0

-1 1 1 1

-2 2 1 0

2

3

!

0U

2

3

!

U

,

U!

!, U

U

1

5

0U

0U!

10

, U , U! 7 0 U 0 1 0 0

!

-3 3 0 0

31

U 0 0 1 0

U! 0 0 0 1

L.D. 0 10 5 1

}

10/3

Primera iteración: Z

!

U U!

Z 1 0 0 0

0 1/3 1 1

U 1 1/3 0 0

!

0 2/3 1 0

0 1 0 0

Solución óptima: ,r

10 W4. B. X;

r

•.

‚.•.

W ! , U , U! X W , ,U X

U 0 0 1 0

W10⁄3 , 5,1X W0,0,0X

Si se elige una variable básica con coeficiente cero, “z” óptimo es el mismo.

32

U! 0 0 0 1

L.D. 10 10/3 5 1

}

3.

La teoría de la dualidad

3.1. Introducción La teoría de la dualidad es una herramienta decisional de optimización de la I.O. Muchos de los modelos de programación lineal analizados con anterioridad pueden ser representados desde una óptica diferente, ya no desde el punto de vista de la óptima asignación de recursos, sino más bien desde la óptica de la óptima utilización de los recursos. 3.2. Concepto del dual Dual representa el planteamiento al revés de un problema original denominado primal. PRIMAL

DUAL

Problema original

Planteamiento al revés

Objetivo: óptima utilización de recursos.

Objetivo: óptima asignación de recursos. Recursos

Actividades

2 2

8

8

2

3.3. Aplicaciones de la teoría de la dualidad La teoría de la dualidad se recomienda aplicar en dos tipos de situaciones. 1) Cuando el número de restricciones funcionales sea muy superior al número de variables decisionales. 2) Cuando se quiere realizar una interpretación exhaustiva y económica del primal. Primal

F.O.: max , \ˆ ; ;% ; \ B +3 , ; -% - + + - % ó< -% . S.A.:

F.O.: min ‰" = 3 2 ;4

1ˆ 6 2

S.A.:

ˆ70

Ejemplo 1) F.O.:

max ,

4

33

1Š ‰ 7 \ ‰70

Dual

2‰ ; ;% ; ‰ .

B +3 , ;

S.A.:

2

69

O

3

O2

O3

O

O4

2

,

Plantear el dual. F.O.:

S.A.:

min e" 2e

1e

2) F.O.:

S.A.:

9e

8e

S.A.:

64

61

67

65

70

4e!

1e O 1e! O 3eo 1e

1eo 1ep

7ep

5eq

2eq 7 1

3e! O 2eo O 1ep O 4eq 7 4

e , e , e! , eo , ep , eq 7 0 max ,

3

5

2

4

61

O

5

77

70

9

% 3 +3 < ;%

Plantear el dual.

F.O.:

68

min e" 2e

4e

1e

7e

9e!

1e O 1e! 7 3 1e

5e!

5

e 7 0 , e 6 0 , e! % 3 +3 < ;%

34

3) F.O.:

max ,

S.A.:

Plantear el dual. F.O.:

S.A.:

!

2

O5

O

4

O2

7 0,

6 0,

min e"

7e

67

!

69

74

O

!

9

% 3 +3 < ;%

9e

4e!

9eo

2e

1e O 1e! O 2eo 7 1

0e

1e

O5e

1e

4e! O 1eo 6 1

0e!

0eo

1

e 7 0 , e 7 0 , e! 6 0 , eo % 3 +3 < ;% 3.4. Las condiciones del simplex y la teoría de la dualidad Son 4 las condiciones del simplex, las cuales pueden utilizarse para los siguientes objetivos: 1. Dado un problema original (modelo de P.L.) se puede llegar a la solución óptima, sin necesidad de llevar adelante el proceso iterativo, pero con el conocimiento de las variables básicas finales. 2. Dado la solución óptima del modelo (tabla óptima) se puede regenerar el modelo original de P.L. Primera condición

‰/

Segunda condición

Tercera condición

Cuarta condición

Œ

`‹

/

ˆ•

`‹ 2

Œ

\• ˆ•

Œ

\• ` ‹ 2

Π2 , Π

Œ/ O -/

\• ` ‹

Π

35

/

O -/

Donde:

‰/ /

B +3 , ; -% `‹

%

ˆ•

% -%

2

Z 1 0 0 8 0

Z

Ž Ž

8

Ž9

= %3 ;

Π

-/

Tabla inicial:

--

8

9

+

+

= 3

; `" .

+ - % ó< -% ; = 3 2

2á -

3 -43 % B + ;% ;

B +3 , ; = 3 2

-/ %

% -%

-

+

+ 2

+ 2

ó*+ B -

;4

.

-% +%.

Ž

, Ž

8

8

9, Ž

`"

Tabla final:

Ž9

L.D. 0 2 2 8 29

0

, Ž9

, Ž9

8

.

9, Ž

/

.

… … . .

, Ž

, Ž

9

.

.

0

, Ž

8

-

Ž

0

--

.

9

+ - % ó< -% - B2 ;%.

B +3 ,

… . . …

--

8

-

-

9, Ž9

2

Las columnas de las variables básicas finales deben cumplir con la matriz identidad.

Z • •

8

•9

Z 1 0 0 8 0

, Oe e 8 e9

, Oe e 8 e9

… . . … .

, Oe e 8 e9

,

Ž

e e

Ž

O, Ž

, Ž

8 e9, Ž

Ejemplo 1) Sea el siguiente modelo de programación lineal. F.O.:

S.A.:

max , 2

3

6

7 ,

2

67

68

70

36

Ž

,

Ž

e e

Ž

O, Ž

, Ž

8 e9, Ž

Ž

… … . . .

,

Ž9

e e

Ž9

O-

, Ž9

, Ž9

e9,

8

Ž9

Ž9

L.D. Z • •

8

•9

,

Se sabe que las variables básicas finales son:

Hallar la solución óptima del modelo utilizando las 4 condiciones del simplex. Forma estándar: F.O.:

max , O 3

S.A.:

2 Tabla inicial: Z U U

Z 1 0 0

O6 7

U

2

,

U

8 U 0 1 0

-6 7 2

Primera condición

‰/

La inversa B-1:

0

7

,U ,U 7 0

-3 1 2

Variables básicas finales

O 0U O 0U

`‹

U 0 0 1

/

1

7

U

1

U

2

2

0

1

1

7

1

0

0

-12

-2

1

1

7

1

0

0

1

1/6

-1/12

1

0

-1/6

7/12

0

1

1/6

-1/12

•

‰/ Segunda condición

O1/6 1/6

7/12 1 ‘’ O1/12 2 ˆ•

ˆ•

•

O1/6 1/6

`‹ 2

7 “ 2

7/12 7 ‘’ “ O1/12 8

37

f O2

0

’

1 0

f ~O

0 “ 1

7/2 • ‘ 1/2

1 • 12

f O7

`‹

L.D. 0 7 8

Tercera condición

Œ

\• ` ‹ 2

Œ

Œ

\• ˆ•

Œ

\• ˆ•

Π2 , Π W3

\• ` ‹

6X •

7/2 ‘ 1/2

27/2

Coeficientes costo en la F.O. de las variables básicas finales en valor absoluto. Cuarta condición Π

\• ` ‹

ΠO-

Π

ΠO-

Tabla final:

Z

W3

Π

Z 1 0 0

Œ/ O -/

Π

O1/6 6X • 1/6

O-

O-

W1/2

O -/

7/12 ‘ O1/12

W1/2

0 1 0

5/4X

•

‚•

W1/2

1 ’ “ O W3X 2

7 5/4X ’ “ O W6X 2 U 1/2 -1/6 1/6

0 0 1

Solución óptima:

r

/

27 2

Œr

W , X WU , U X

W7/2 W0

20

10

5/4X 0

0

U 5/4 7/12 -1/12

L.D. 27/2 7/2 1/2

1/2X

0X

Ejercicio F.O.: S.A.:

max ,

6 70 6 50

6 120

,

6 90

70

Hallar la solución óptima del modelo utilizando las 4 condiciones del simplex sabiendo que las variables básicas finales son , U , U! , .

38

4. La Teoría de redes 4.1. Introducción En el presente capítulo analizaremos tres tipos de problemas: 1. El problema de la ruta más corta. 2. El problema del árbol de comunicación mínima. 3. El problema del flujo máximo. 4.2. Conceptos básicos a) ¿Qué es una red? Es una estructura reticular o grafo que esta formado por nodos (puntos o vértices) que se comunican a través de arcos (líneas, bordes, ramas) por cuyo interior existe algún tipo de flujo, que puede o no ser fluido. Ejemplo Nodo

Arco

Flujo

Aeropuerto

Rutas aéreas

Avión

Casas

Tuberías

Agua

Intersección de calles

Calles

Vehículos

b) Red direccional y a direccional Una red direccional es aquella en la que el sentido del flujo esta definido. La red a direccional es aquella red en la que el sentido del flujo no esta definido. Ejemplo Red direccional

2

4

1

6 3

5

Red a direccional

2

4

6

1

3

5

39

c) Red conexa e inconexa La red conexa es aquella red en la que el proceso comunicacional no se ve interrumpido entre sus elementos y una red inconexa es aquella red en la que el proceso comunicacional se ve interrumpido entre sus elementos. Ejemplo Conexa

2

4

3

5

Existe comunicación entre todos los nodos.

1

Inconexa

2

4

3

5

1

d) Cadena Es un conjunto de nodos y arcos a lo largo de una red. Ejemplo 1 cadena

1

1

1

1

Varias cadenas

1

1

1

1 1

1

e) Ruta Es un conjunto de nodos y arcos a lo largo de la red donde el sentido del flujo esta definido. Ejemplo 1

ruta

1

2

5

6

40

f) Ciclo Es un conjunto de nodos y arcos donde el nodo origen y destino es el mismo nodo. Ejemplo

2

1

2

3

1

1

1 3

g) Árbol Es una red conexa que no tiene ciclos.

8 6

7 5 4

3 2

1

4.3. El problema de la ruta más corta El objetivo del análisis de este problema es el de hallar la ruta más corta entre un nodo origen y cualquiera de los otros nodos componentes de la red. Esta distancia corta estar medida en longitud, tiempo, costo. Para dar solución a este problema utilizamos el algoritmo de las etiquetas. El algoritmo de las etiquetas:

Etiqueta temporal W0,0X

Etiqueta permanente W0,0X

1

De donde viene

W0,0X 41

Distancia

1

Ejemplo Hallar la ruta más corta entre 1 – 6.

6 2

4

5

5 2

1

2

4

6

3

5 3

7

W3,5X W1,5X

W3,7X

W2,11X

6

2

W0,0X

5

4

5

5 2

1

2

4

6

3

5 3

W1,3X W2,7X

W4,12X W5,14X

5

W4,9X W3,10X

7

Resumen Nodo 2 3 4 5 6

Ruta más corta 1–3–2 1–3 1–3–4 1–3–4–5 1–3–4–6

Distancia [unidades métricas] 5 3 7 9 12

La ruta más corta es:

4

5

4

1

6 3 3

Ejercicio Hallar la ruta más corta entre 1 – 7.

42

2

15

8 16

5

17

9 1

8

3

4

7

19

20

10

7

9

6 18

4.4. El problema del árbol de comunicación mínima Denominado también árbol minimal. Es el árbol que comunica a todos los nodos de la red con la menor longitud, tiempo o costo. El algoritmo que da solución a este problema es el denominado Kruskal – Voraz. Aplicaciones 1) Determina la menor distancia, tiempo o dinero entre nodos. 2) Determina el menor recurso para cada ruta hacia cada nodo. Ejemplo Hallar el árbol minimal.

3 2

4

1

6 5

5

1

6

3

7

1 3

5 6

Algoritmo Paso 1 Construir la tabla en el que el número de filas y columnas es el número de nodos. Escoger cualquier fila (por lo general la última) y marcar el número de fila y columna del mismo número. En este caso marcamos la fila 6 y columna 6. Paso 2 Elegir el menor valor de la fila marcada y tachar la columna donde se encuentre si hay más de uno elegir cualquiera. En este caso la columna 5. Paso 3 Marcar la fila del mismo número de columna del paso 2 y escoger el menor valor entre las dos filas marcadas sin que este valor este bajo una columna tachada si hay más de uno elegir cualquiera. En este caso la fila marcada es 5 y el valor escogido es 1 de la columna 4. Paso 4

43

Tachar el número de columna donde se encuentre el valor escogido del paso 3, luego tachar la fila del mismo número de columna. En este caso marcar la columna y fila 4. Paso 5 Escoger el menor valor de las tres filas marcadas que no estén debajo de una columna tachada si hay más de uno elegir cualquiera. En este caso el 5. Repetir el proceso hasta que todas las filas y columnas estén tachadas. a

1

De 1 2

6

3

7

2

3

6

7

4

5

5

3

3

6

1)

úB 3% ;

3-%

1

1

úB 3% ;

%;% O 1 _ 5

2) La red tiene que ser un árbol minimal

1

3

6

Pruebas:

6

5

5

6

3

5

4

5

1

6O1

Conclusión

3 2

4 1

6 5

1

6 1

3 ”9í

Ejercicio

6

F9•

5 5

Hallar el árbol minimal.

3

1

1

16 W4 ; ;

Bé+3 -

X

15 2 8

1

16

10 9

5

8

20

8 15

9 3

9

6 17

10

10 13

10

9

20

11 4

7 19 44

9

4.5. El problema del flujo máximo Algoritmo Paso 1 Elegir una ruta del nodo origen al nodo destino sin que ninguna de las capacidades de flujo positivo sea cero. Paso 2 Elegir la mínima capacidad de flujo positivo y restar a las capacidades de flujo con dirección positiva. Luego sumar dicha capacidad mínima a las capacidades de flujo con dirección negativa. Paso 3 Repetir el proceso hasta que no existan más rutas. Paso 4 El flujo máximo será:

Donde }9í Ejemplo

& 4D% Bá B% F

– }9í

es la capacidad mínima de la ruta i.

2

0

2

0

3

4 1

5

F

F—

0

1

0

6

1 0

0

4 3

0

0

1 5 5

6

0

Paso 1 Ruta 1

2 0

0

2

4

3 0

5 1 Capacidad de flujo en sentido positivo

Capacidad de flujo en sentido negativo

Paso 2

6

Las capacidades de flujo positivo son 5, 2 y 3 el valor mínimo es 2 por lo tanto }9í

2

Restamos el valor mínimo a todas las capacidades de flujo positivo y sumamos el mismo valor a las capacidades de flujo negativo.

45

0 2

2 0 3

2 0

2

1 3

4

0

5

}9í

2

2

6 1

Ruta 2

2 3

3 2

2 1 0

1

5 6

0 1 3

1 0

6

}9í

5 5 4

1

0 1

Ruta 3

0 4

1

4

1 5

5 1

0 4

0 3

Paso 4

5 1

6 }9í

5

4D% Bá B%

2

1

4

7

4.6. Ejercicios 1) a) Hallar la ruta más corta entre 1 – 8. b) Hallar el árbol minimal.

38 2 80

40 78

1 90

3 49

5 45

40

44

50

6

49

47

4

7 57 46

47

8 38

!

4

2) a) Hallar la ruta más corta entre A y G. b) Hallar el árbol minimal.

B 100,25

70,4 80,1

101,7 A

E 80,1 90,7

C 50,8

201,4 D

66,8 66

F 58,4

47

G 69,7

5. El modelo de transporte 5.1. Introducción El modelo de transporte es una herramienta decisional y de optimización cuyo objetivo fundamental es el de distribuir un producto desde los puntos de origen a los puntos del destino con el costo de transporte mínimo. Plan de embarque óptimo

Origen

Destino

Oferta

Demanda

1

200

1

2

1500

2

700 1800

Fábricas

Consumidores

N

N

800 \% + ; +3

5.2. Concepto del modelo transporte (M.T.)

*%3+

650

Bí B%

El M.T. es una herramienta de la I.O. que se encuentra dentro del campo de la optimización restringida, cuyo objetivo fundamental es, el determinar el plan de embarque óptimo, es decir como se debe distribuir el producto desde los puntos de origen u oferta a los puntos de destino o de demanda, garantizando el costo mínimo de transporte, satisfaciendo los requerimientos de oferta y demanda. 5.3. Matriz del costo de transporte …

Destino 1 Origen 1

m

-

2 8

2

9

Demanda

-F/

F/

-9

2 %

-

n

9

2

4 ; ;

-% +% ;

-

Oferta

-

-9

G4

= 3

48

9

2

= ;

*3%;4-+% ;

D

D

-9

8 – 2F

9

–

F

5.4. Formulación matemática del modelo de transporte F.O.:

min ,

S.A.

-

-

.

-F/

. -9

F/

9

.

. 9

8

Restricción de oferta

.

9

9

.

2

. 9

. F/

, -F/

F/

-% +% 4 + 3 % ;

G4

= 3

2/

B

F

29

9

70

4 - ó -% +% ; +3

#; 4 ; ;

2

8

9

9

Restricción de no negatividad

*%3+ +%+

= ;

%3 <

*3%;4-+% ;

%

; B

Restricción de demanda

3+

.

; D.

# ; %3í<

3B %3 <

; + % D.

.

#; ; + % .

5.5. Solución del modelo de transporte La solución del modelo de transporte involucra los siguientes pasos: 1) Balancear el modelo de transporte 2) Hallar la solución básica por los siguientes métodos: a. Método de la esquina noroeste (MENO) b. Método de la aproximación de Voguel (MAV) c. Método de costo mínimo (MCM) 3) Hallar el plan de embarque óptimo con el algoritmo de transporte

49

, ;%. ; 3 % D.

1) Balancear el modelo da transporte Ejemplo

Tiendas ™u

Demanda Oferta šu

™v

šv

Fábricas

š›

3

2

10

1

4

5

2

1

8

7

Demanda

Oferta

9

23 16

La oferta debe ser igual a la demanda para que este balanceado

Condición para el balance: –%

3+

9

– F—

0

0

Demanda Oferta šu

%

%

3+

3+

€; B

„; B

™u

šv š›

Demanda

7

;

;

–; B – 2/

F

;

/—

+% -

+% -

-3

-3

™v

; B %

3+

;

-+ -

-+ -

™r›

Oferta

3

2

0

10

1

4

0

5

2

1

0

8

9

7

23 23

50

Demanda ficticia

2) Hallar la solución básica a) Método de la esquina noroeste (MENO) (solo encuentra la tabla inicial) Ejemplo Demanda Oferta šu

™u

šv š›

™v

Oferta

3

2

0

10

1

4

0

5

2

1

0

8

7

Demanda

™r›

9

7

23 23

Demanda Oferta šu šv

™u

3

7

1

š› Demanda

™v

2 7 0

3 5

™r›

2

0

4

0

1

1 9 6 1 0

Oferta 10 3 0 5 0 8 7 0

0

7 7 0

23

23

Algoritmo de solución Paso 1 Ubicarse en la casilla que este en la esquina arriba y a la izquierda de la tabla. En este caso la casilla F1T1. Luego elegir el menor valor entre la oferta de la fila y la demanda de la columna. En este caso el 7. Si los dos valores son iguales se puede elegir cualquiera. Paso 2 Anotar el valor en la casilla elegida en un principio y marcarlo como variable básica para restar este valor a la oferta y demanda de dicha casilla. Luego tachar la fila o columna que sea cero. En este caso la columna T1. Si la fila y columna son ceros entonces tachar la fila o columna que se eligió al final del paso 1. Solo se pueden tachar los dos a la vez en la última casilla que quede después de haber tachado las demás. Paso 3 Repetir el proceso hasta que no quede ninguna fila o columna sin tachar. Existen tres pruebas para este método:

51

Primera: al final, en la última casilla, tanto la demanda y oferta deben ser iguales. Segunda: # = 3 2

2á -

B

O 1 ; ;% ; B

úB 3% ;

e

úB 3% ; -% 4B

.

Tercera: para cada fábrica la suma total de la demanda (variables básicas) debe ser igual a la oferta. b) Método de la aproximación de Voguel (MAV) Ejemplo

Costos

Demanda Oferta šu

™u

šv š›

Demanda Diferencia

7

|1 O 2|= 1

™v

™r›

Oferta

Diferencia

0

10 3

2–0=2

3

2

1

4

0

5

1–0=1

2

1

0

8

1–0=1

7

9

7 0 0–0=0

2–1=1

23 23

Algoritmo de solución Paso 1 Elegir dos costos menores de la fila 1 (F1) y restarlos en valor absoluto. Si hay más de tres costos mínimos elegir solo dos. Se hace lo mismo para todas las filas y columnas. Paso 2 Elegir el máximo valor de las diferencias de las filas y columnas, si existen dos elegir cualquiera. Luego elegir el menor costo de dicha fila o columna. Paso 3 En la casilla elegida en el paso 2 colocar el menor valor entre la oferta y la demanda, y restar el mismo valor a la oferta y demanda. Paso 4 Tachar la columna o fila que se haga cero, si existen dos elegir una. Paso 5 Repetir el proceso hasta eliminar toda la tabla.

52

Destino Origen

T1

F1 F2

5

F3

T2

2

3

1

1

4

5 0

3

2

1

8

1

Oferta

Diferencia

3 0

1

8

1

Oferta

Diferencia

8 2

1

7 2

9

Diferencia

1

1

Destino Origen

T1

T2

F1

3

F3

2

2

3

1

Demanda

2

9 6

Diferencia

1

1

Destino Origen

T1

T2

Demanda

Diferencia

3

Demanda

F3

Oferta

2

6

2

6 0

Destino Origen

T1

F3 Demanda

1

Oferta 2 0

2

2

2 0

Primera prueba: Al final la oferta y la demanda deben ser iguales. Segunda prueba:

#; = 3 2

2á -

53

B

O1

Tabla de resultados:

Demanda Oferta šu

™u

™v

3

šv

2

2

6

7

Demanda

Oferta

0

10

4

0

5

1

0

8

2

3

1

5

š›

™r›

7

9

7

23 23

3) Hallar el plan de embarque óptimo Ejemplo Destino Origen

T2

T1

T3

Oferta

F1

5

1

2

7

F2

2

3

1

10

Demanda

5

5

7

17 17

Resolviendo por el método MENO se tiene: Destino Origen F1

5

F2 Demanda

T2

T1

T3

5

2

1

2

3

3

5

5

7

Oferta 2

7

1

10

7

17 17

Para verificar si la tabla es óptima se calculan las variables básicas y no básicas. Variables básicas:

-F/

4F

=/ ; ;% ; -F/

Para el ejemplo se tiene 4 variables básicas.

= 3 2

2á - ;

54

e -% 4B

D;

% -% +%

4 4 5 4 4

= = = =!

5 1: 3 1

Costos

Para resolver el sistema de ecuaciones se elige cualquier variable y se iguala a cero. Por ejemplo =! :

=!

Al resolver el sistema se tiene el valor de las variables:

Variables no básicas:

4

,F/ O -F/

1; =

-F/ O 4F

0

2; 4

=/ ; ;% ; -F/

O1 ; =

6

-% +% ;

= 3 2

% 2á -

Si todas las variables no básicas son mayores o iguales a cero es decir ,F/ O -F/ 7 0, entonces es la tabla óptima, sino se genera la siguiente tabla de iteración. Para el ejemplo se tienen 2 variables no básicas. ,

,

!

O-

O-

!

2O 4

2O 4

=!

=

3

O5

No es óptimo

Como la tabla no es óptima entonces se genera la siguiente tabla de iteración, para hacer posible esto se realiza un circuito cerrado en dicha tabla. Circuito cerrado El circuito cerrado se aplica solo para las variables básicas no necesariamente todas. Con las variables básicas se deben formar circuitos cerrados de manera que formen figuras geométricas que no sean triángulos. Puede haber más de un circuito. Figuras geométricas permitidas Cuadrado

Figuras geométricas no permitidas

Rectángulo

Triángulo

Triángulo rectángulo

Combinado

Para formar el circuito se debe ubicar el valor mínimo de las variables no básicas o sea el más negativo en la tabla, en este caso el -5, y poner en la casilla un polo positivo para comenzar el circuito, luego colocar en la siguiente esquina de la figura, formada por las variables básicas, un polo negativo, después en la siguiente un polo positivo y así sucesivamente.

55

Destino Origen

T1

Viene de , !O- !

5

2

T2

T3

Oferta

3

7

F1 F2

-5

Demanda

5

3

10

7

5

7

17 17

Viene de , O-

Valor mínimo de las V.N.B. inicio del circuito

Luego de formar el circuito se elige un pivote:

Para este caso:

* =%+

•

min>= 3 2

2á -

•

-% *% % ;

min>5,3@

< %

< + =%@

3

Este pivote debe estar al inicio del circuito como variable básica para la siguiente tabla de iteración. Además este valor se resta a las variables que tengan polo negativo y se suma a los que tienen polo positivo. Si el resultado es cero no se altera el valor. Destino Origen

T2

T1

F1 2

F2

Oferta

-2

7

5

5

3

Demanda

T3

5

10

7

5

7

17 17

Variables básicas

4

0 entonces:

4

1; =

5

=

2

4

=

4

=!

4

Si =!

=

1; 4

56

1 1 4; =

O3

Variables no básicas

,

,

Destino Origen

T1

F1

2

!

O-

2O 4

!

O-

=!

3O 4

* =%+

•

=

min>2,7@

T2

2

T3

Oferta

2

3

5

Demanda

5

7 5

F2

O2

5

10

5

5

7

17 17

Variables básicas

4

=

1

4

=

2

4

Si =!

4

0 entonces:

4

Variables no básicas

,

,

=! =!

1; =

1; 4

O-

5O 4

O-

3O 4

2 1 2; = =

=

O1 2

3

La tabla ya es óptima por que todas las variables no básicas son mayores a cero. Plan de embarque óptimo

Origen

Destino

T1

5

F1 2

F2

T2

5 5

T3

57

Ÿ% ; ž` %

\% +% ; +3

= 3 2

\% +% ; +3

2á -

*%3+ Bí B%

e\ %

*%3+ Bí B%

\]9í

– ž` F f \F F—

% -% +% 3 * -+ =% ; - ; = 3 2

5f1

2f2

24 W4BX

5f2

5f1

24

2á -

Ejercicios 1) A Jesús le gustaría tomar exactamente 20 litros de cerveza cacera hoy y al menos 20 litros más mañana. José vende en total 40 litros de cerveza cacera a 9 [Bs] el litro hoy y 10 [Bs] el litro mañana. Teresa vende en total 20 litros de cerveza cacera a 11 [Bs] el litro hoy y 9 [Bs] el litro mañana. Carlos vende en total 10 litros de cerveza cacera a 8 [Bs] el litro hoy y 11 [Bs] el litro mañana. ¿Cómo debe realizar sus compras Jesús para satisfacer sus requerimientos mínimos de sed al costo mínimo? 2) La empresa “Records Importaciones” tiene tres fábricas con capacidades de producción de 70 unidades por día en cada una de sus fábricas. Distribuye su producto a dos de sus tiendas cuyas demandas son 60 unidades por día en cada tienda. EL costo unitario de transporte en [Bs/día] de la fábrica 1 es de 4, a la tienda 2 de 7; de la fábrica 2 a la tienda 1 es 2 y la tienda 2 es de 4; de la fábrica 3 a la tienda 1 de 7 y a la tienda 2 de 5. Como la oferta es mayor que la demanda existirá un déficit, pero esta no esta permitido en la fábrica 3 que tiene que acomodar toda su oferta. Con esta información: Hallar el plan de embarque óptimo que minimice el costo total de transporte.

6. Bibliografía 1. Rafael Terrazas Pastor, “MODELOS LINEALES DE OPTIMIZACIÓN [Tercera edición], Cochabamba – Bolivia 2005. 2. Manual de Investigación de Operaciones para Administración. 3. Apuntes de la clase Investigación Operativa 1 semestre 2 – 2012.

58