Manual Investigacion de Operaciones 2013

[email protected] Facebook: Giovanny Rodriguez 1

Material de Apoyo y Consulta

MANUAL DE INVESTIGACIÓN DE OPERACIONES

(Versión Preliminar para Revisión)

Ing. Giovanny Rodríguez Martínez

Bogotá, D.C. Mayo de 2013


CONTENIDO

Página

1. Definiciones básicas de programación lineal …….3

2. Aplicaciones y modelos lineales……………………..6

3. Solución por método gráfico…………………………20

4. Solución por Solver……………………………………23

5. Solución por el método Simplex…………………….28

6. Dualidad ……………………………………………..…38

7. Análisis de sensibilidad……………………………….46

8. Modelos de Asignación y Transporte……………….48

9. Programación Entera …………………………………63


DEFINICIONES BÁSICAS PROGRAMACION LINEAL

La programación lineal satisface un tipo especial de problema, uno en el cual todas las relaciones entre las variables son lineales, tanto en las restricciones como en la función objetivo.

CARACTERÍSTICAS

- La función objetivo maximiza o minimiza.

Maximiza = Utilidades/recursos

Minimiza = Costos/recursos

Se llama solución factible a la solución que satisfaga la condición de no negatividad.

PAUTAS PARA UN BUEN PLANTEAMIENTO DE UN MODELO DE PROGRAMACION LINEAL

Formule cada restricción con sus propias palabras, teniendo en cuenta si es de la signo >= (mayor o igual que, al menos, por lo menos, como mínimo), o =< (menor o igual que, no mayor que, como máximo), o = (igual).

Exprese las restricciones de forma que en ambos lados del símbolo se manejen bien sea horas, pesos, kilogramos, etc.

Formule el modelo con la rapidez que le sea posible no intente colocar mas datos de los que le piden, puede llegar a confundir o a desviar el objetivo

ANÁLISIS DE PROBLEMAS

Metodología de Investigación de Operaciones

Definir el problema

Desarrollar un modelo matemático

Resolución del modelo

Validación de la solución

Poner en práctica y supervisar la solución


PROGRAMACION LINEAL “ELEMENTOS”

Variables = cambios

Restricciones =limite ≤ o ≥

Función objetivo = Max o Min Z = C1X1 + C2X2…..+ CnXn

Sujeto a = a11x1 + aijxj ………≤ ó ≥ b1

ai 1 + aijxj ………≤ó ≥ bi

x1, x2 ≥ 0

APLICACIONES DE LA PROGRAMACION LINEAL

Finanzas: El problema del inversor podría ser un problema de selección del mix de su cartera de inversiones. En general, la variedad de carteras puede ser mucho mayor que lo que indica el ejemplo y se pueden agregar muchas más restricciones distintas. Otro problema de decisión implica determinar la combinación de métodos de financiación para una cantidad de productos cuando existe más de un método de financiación disponible. El objetivo puede ser maximizar las ganancias totales cuando las ganancias de un producto determinado dependen del método de financiación.

Administración de Producción y Operaciones: En las industrias de proceso, una materia prima en particular puede transformarse en una gran variedad de productos. Por ejemplo, en la industria petrolera, el crudo puede refinarse para producir nafta, kerosene, aceite. Según el margen de ganancia actual de cada producto, el problema es determinar la cantidad que se debería fabricar de cada producto. Esta decisión está sujeta a numerosas restricciones tales como límites de las capacidades de diversas operaciones de refinado, disponibilidad de materia prima, demandas de cada producto y políticas gubernamentales con respecto a la fabricación de determinados productos. En la industria de productos químicos y de procesamiento de alimentos existen problemas similares.


Recursos Humanos: Los problemas de planificación de personal también se pueden analizar con programación lineal. Por ejemplo, en la industria telefónica, la demanda de servicios de personal de instalación / reparación son estacionales. El problema es determinar la cantidad de personal de instalación / reparación y reparación de líneas que debemos tener incorporada en la fuerza laboral por cada mes a fin de minimizar los costos totales de contratación, despido, horas extras y salarios en horas ordinarias. El conjunto de restricciones comprende restricciones con respecto a la demanda de servicio que se debe satisfacer, uso de horas extra, acuerdos con los sindicatos y la disponibilidad de personal calificado para contratar. Este ejemplo es opuesto a la hipótesis de divisibilidad. Sin embargo, los niveles de fuerza laboral de cada mes normalmente son lo suficientemente altos como para poder redondear al número entero más cercano sin problemas, siempre y cuando no se violen las restricciones.


APLICACIONES Y MOLDELOS DE PROGRAMACIÓN LINEAL

PROBLEMAS DE PRODUCCION

Un taller tiene (3) tipos de maquina A,B,C ; puede fabricar (2) productos 1y2, todos los productos tienen que ir a cada máquina y cada máquina y cada una va en el mismo orden: primero a la maquina A, luego a la B y luego a la C. La tabla siguiente muestra:

Las horas requeridas en cada máquina, por unidad de producto.

Las horas totales disponibles para cada máquina por semana.

La ganancia por unidad vendida de cada producto.

Tipo de Máquina Producto 1 Producto2 Horas disponibles

Por semana

A 2 2 16

B 1 2 12

C 4 2 28

Ganancia por unidad

1

1.50

¿Qué cantidad de cada producto (1y2) se debe manufacturar cada semana, para obtener la máxima ganancia?

¿Cuantas horas semanales sobran en cada departamento?


Solución

Formulación: Definición de las variables:

Xj = Unidades semanales a producir del articulo j- esimo (j=1 y 2)

X1= Cantidad de Producto 1.

X2= Cantidad de Producto 2.

Función Objetivo:

Maximizar Z = X1 + 3/2 X2

Restricciones:

2X1 + 2X2 ≤ 16 Restricción debida a las horas disponibles por semana de la MQ A

X1 + 2x2 ≤ 12 Restricción debida a las horas disponibles por semana de la MQ B

4X1 + 2X2 ≤ 28 Restricción debida a las horas disponibles por semana de la MQ C

Condición de no negatividad

Xj ≥ 0 ; j= 1y2

BODEGAS

Un barco de carga tiene tres bodegas: Proa, Popa y Centro cuya capacidad máxima de peso a transportar en cada una de ellas es: 2000, 1500 y 3000 toneladas respectivamente. Cada bodega tiene un volumen de: 100.000, 200.000 y 135.000 pies cúbicos respectivamente. Se ofrecen tres tipos de carga denominadas A, B, C en las siguientes cantidades: 6000, 4000 y 2000 toneladas respectivamente. Si cada tonelada de los productos A, B, C ocupa 60, 50 y 25 pies cúbicos y el capitán del barco tiene como política de seguridad cargar el mismo porcentaje de toneladas en cada bodega, de tal forma que maximice las utilidades de la carga, sabiendo que por cada tonelada de los productos A, B, C obtiene una utilidad de $6, $8, $5 respectivamente.


Definición de Variables

- Toneladas de producto A, B, C

- Transportar a bodegas (1)Proa, (2)Popa, (3)Centro

Función Objetivo

Max Z= 6(Xa1+ Xa2 + Xa3) + 8(Xb1+ Xb2 + Xb3) + 5(Xc1+ Xc2 + Xc3)

Restricciones

- Capacidad de bodega: * Proa: Xa1+Xb1+Xc1 =< 2000

(Peso) * Popa: Xa2+Xb2+Xc2 =<1500

* Centro: Xa3+Xb3+Xc3 =< 3000

- Capacidad de bodega: * Proa: 60Xa1 + 50Xb1 + 25Xc1 =< 100.000

(Volumen) * Popa: 60 a2 + 50b2 + 25c2 =< 300.000

* Centro: 60 a3 + 50b3 + 25c3 =< 135.000

Condición de No Negatividad

A, B, C, 1, 2, 3 >= 0

TUERCAS Y TORNILLOS

Un distribuidos de ferreteria planea vender paquetes de tuercas y tornillos mezclados. Cada paquete pesa por lo menos 2Lb. Tres tamaños de tornillos y tuercas componen el paquete y se compran en lotes de 200 Lb. Los tamaños 1,2,3 cuestan respectivamente $20, $8, $12, además:

- El peso combinado de los tamaños 1 y 3 debe ser al menos la mitad del peso total del paquete.

- El peso de los tamaños 1, 2 no debe ser mayor que 1,6Lb.

- Cualquier tamaño de tornillo debe ser al menos el 10% del paquete total.


Variables de decisión

- Tamaño tuercas y tornillos que conforman el paquete: 1, 2, 3.

Función objetivo

Min Z: 20/200X1 + 8/200X2 + 12/200X3

Restricciones

- X1+X2+X3 >= 2

- X1 + X3 =< X1 + X2 + X3 / 2

- X1 + X2 =< 1,6

- X1 >= (X1 + X2 + X3)0,1

- X2 >= (X1 + X2 + X3)0,1

- X3 >= (X1 + X2 + X3)0,1

Condición de no negatividad

X1, X2, X3 >= 0

EL PROBLEMA DE LAS JOYAS

Una pequeña empresa de muebles JBC produce sillas y mesas . cada silla vendida representa una ganancia neta de $ 3000 y cada mesa $ 5000 . se dispone de 30 horas-hombre de capacidad de corte y fabricación por día y de 18 horas – hombre de capacidad de terminado y pintura por día. Igualmente existe un suministro de madera de 30 tablas diarias. Se asume por ahora que estas capacidades no son necesariamente en juegos completos. Para fabricar una silla se requieren dos horas de corte y fabricación , una hora de acabado y pintura y consume una tabla. A su vez cada mesa requiere una hora de corte y fabricación, una hora de acabado y pintura y consume dos tablas. Se desea conocer cuantas sillas y cuantas mesas deberán fabricarse para maximizar las ganancias diarias de la empresa.


Solución

Formulación

Definición de las variables

X1= Cantidad de sillas vendidas

X2= Cantidad de mesas vendidas

Función Objetivo

Max Z = 3000 X1 + 5000 X2

Restricciones

- Restricción en horas en el departamento de corte y pintura

2X1 + X2 ≤ 30 horas-hombre

- Restricción en horas en el departamento de terminado y pintura

X1 + X2 ≤ 18 horas-hombre

- Restricción en materia prima cantidad de tablas

X1 + 2X2 ≤ 30 tablas

- Restricciones de no negatividad

X1, X2 ≥ 0

Una empresa fabrica PC’s de dos tipos:

Procesador intel® Celeron®440 (2.00GHz, 800FBS), Sistema Operativo

Windows VIsta®Home Basic original SP1, Memoria.

2GB Dual Channel DDR2 SDRAM at 800MHz-2DIMMs

Disco Duro

Disco Duro de 160Gb Serial ATA (7200RPM) c/Data Burst Cache

Unidades de CD/DVD


Quemador de DVD 16X DVD+/-RW

El otro:

Procesador

Procesador intel®Pentium®dual-core E2180 (1MB L2 Cache, 2.00GHz,80)

Sistema Operativo

Ubuntu Linux, versión 7-1 con DVD Playback

Memoria

Disco Duro

Disco Duro de 16GB Serial ATA (7200RPM) c/DataBurst Cache

Unidades de CD/DVD

Unidad Quemadora de DVD+/RW de 16X-

Su costo de fabricación, para el primero es de $8 dólares y para el segundo es de $6 dólares. La fabricación de sus componentes se realiza en dos laboratorios.

En el laboratorio 1 (L1) se necesitan dos horas para la fabricación del primer equipo y 1 hora para la fabricación del segundo equipo. En L1 se quiere tener al menos de 10 horas de trabajo.

En el laboratorio 2 (L2) se necesitan 2 horas para la fabricación del primer equipo y 2 horas para la fabricación del segundo equipo. En L2 se quiere tener al menos de 16 horas de trabajo.

Plantee el modelo de manera tal que minimice los costos de fabricación.

Solución

Formulación


Definición de variables

X1= Cantidad de PC1

X2= Cantidad de PC2

Función Objetivo

Min Z= 6X1 + 8X2

Restricciones

Laboratorio 1 (L1) = 2X1 + X2 >= 10 h

Laboratorio 2 (L2) = 2X1 + 2X2 >= 16h

Restricciones no Negatividad

X1, X2 ≥ 0

EJERCICIOS

Problema 3.1

Definir Variables

A= Cantidad de Producto Aritex

B= Cantidad de Producto Extendex

R= Cantidad de Producto Resistex

Función Objetivo

Max Z = 7A + 7E + 6R


Restricciones

- De la Demanda

Aritex → Demanda Producto A ≥ 1000

Extendex→ Demanda Producto B ≥ 500

Resistex → Demanda Producto C ≥ 400

- De Inventarios

Polimero A → 4A + 3E + 6R ≤ 500 Lb → 8000 Oz

Polimero B → 2A + 2E + 3R ≤ 425 Lb → 6800 Oz

Polimero C → 4A + 2E + 5R ≤ 650 Lb → 10400 Oz

Base → 6A + 9E + 2R≤ 1100 Lb →17600 Oz

Problema 3.2

Definir Variables

A= Tubos de Tamaño A

B= Tubos de Tamaño B

C= Tubos de Tamaño C

AJ= Tubos de Japon A

BJ = Tubos de Japon B

CJ= Tubos de japon C

Función Objetivo

Max Z = 7ª + 8B + 5C + 3AJ + 2BJ + 3 CJ

Restricciones


- Por Demanda

A + AJ = 2000

B + BJ = 4000

C + CJ = 5000

- Por Fabricación

0.5 A + 0.45B + 0.6 ≤ 2400

- Material a Soldar

A + B + C ≤ 5500

Problema 3.3

Definición de las Variables

Espagueti = E

Pavo =P

Papas = Pa

Espinacas = Es

Pastel de Manzana= Ma

Función Objetivo

Min Z = 5000E + 5000P + 7900Pa + 3000Es + 14300Ma

Restricciones

→ Por Proteínas

5000E + 29300P + 5300Pa + 3000Es + 4000Ma ≥ 63000(mg)

→Por Hierro

1.1E + 1.8P + 0.5Pa + 2.2Es + 1.2 Ma ≥ 10(mg)


→Por Tiacina

1.4E + 5.4P + 0.9Pa + 0.5Es + 0.6Ma ≥ 15(mg)

→Por Tiamina

0.18E + 0.06P + 0.06Pa + 0.07Es + 0.15Ma ≥ 1(mg)

→Por Vitamina C

0.0E + 0.0P + 10.0Pa + 28.0Es +3.0Ma ≥ 50 (mg)

Una joyeria produce dos tipos de joyas: Tipo 1 y Tipo 2. Cada joya tipo 1 contiene, 2 Rubies y 4 diamantes y se vende a $ 10 Unidad y tiene un costo de producción de $5 Unidad. Cada joya tipo 2 contiene 1 Rubi y 1 diamante, se vende a $6 Unidad y tiene un costo de producción de $4 unidad. La joyeria dispone de 30 Rubies y 40 diamantes para producir las joyas. Por la situación del mercado, se deben producir al menos 10 joyas del tipo 2.

Formule el problema de programación lineal para maximizar la utilidad neta de la joyeria.

Solución

Definición de las Variables

X1 = Joyas tipo 1

X2 = Joyas tipo 2

Función Objetivo

Max Z = 5X1 + 2X2

Restricciones

Rubies: 2X1 + 1X2

Diamantes: 4X1 + 1X2

No Negatividad: X1, X2 >= 0.


UN PROBLEMA DE DIETA

Como es conocido cada ser viviente necesita cantidades diarias de calorías, vitaminas, proteínas, minerales y otros elementos. También se tienen preferencias por los tipos de comidas y marcas. La dieta optima será aquella combinación de alimentos que cumpla con los requerimientos nutricionales y a un costo mínimo. Para simplificar el estudio del problema, se va a suponer que solo existen los requerimientos relacionados con la cantidad minima diaria de tres vitaminas que llamaremos V1, V2, V3. También se supone que solo se están considerando dos tipos de alimentos y productos comerciales que contienen dichas vitaminas y a la vez minimizar el costo de la dieta. Tenemos información que el producto comercial A cuesta $12 el gramo y contiene 2 unidades de vitamina V1, 4 unidades de vitamina V2 y 12 unidades de vitamina V3 por gramo. El producto B cuesta $8 el gramo y contiene 3.75 unidades de V1 gramo, 4 de V2 y 4 de V3. Se requiere que la dieta diaria individual contenga por lo menos 30 unidades de V1, 40 unidades de V2 y 60 unidades de V3. Como deberá formularse un modelo para la dieta a un costo mínimo que satisfaga estos requerimientos?

Solución


X1: Cantidad de producto A

X2: Cantidad de producto B

Función objetivo

Min Z: 12X1 + 8X2

Restricciones

2X1 + 3,75X2 >= 30

4X1 + 4X2 >= 40

12X1 + 4X2 >= 60

Condición de No Negatividad

X1, X2 >= 0

UN PROBLEMA DE TRANSPORTE


X,Y,Z productora de motores Diesel tiene cuatro plantas establecidas en Europa. Están ubicadas en Leipzing, Alemania oriental (1); Nancy, Francia (2); Lieja, Belgica (3) y Tilburgo, Holanda (4). Las maquinas ensambladoras usadas en esas plantas se produce en Estado Unidos y se embarcan a Europa. Llegaron a los puertos de de Amsterdan (A), Amberes (B) y el Havre (C).

Los planes de producción del primer trimestre (julio – Septiembre ) ya ha sido formulados.

Los requerimientos de motores diesel E4 son los siguientes:

PLANTA CANTIDAD DE MOTORES

Leipzing 400

Nancy 900

Lieja 200

Tilburgo 500

2000

La cantidad disponible de maquinas E4 en los puertos a tiempo para usarse en el tercer trimestre se muestran enseguida:

PUERTO CANTIDAD DE MOTORES

A) Amsterdam 500

B) Amberes 700

C) El Havre 800

2000

Solución


-Cantidad de Planta: 1,2,3

-Cantidad de Puertos: a,b,c.


Función Objetivo

Max Z: 400X1 + 900X2 + 200X3 + 500X4

Restricciones

- Oferta: Xa1 + Xa2 + Xa3 + Xa4 =< 500

Xb1 + Xb2 + Xb3 + Xb4 =< 700

Xc1 + Xc2 + Xc3 + Xc4 =< 800

- Demanda: X1a + X1b + X1c =< 400

X2a + X2b + X2c =< 900

X3a + X3b + X3c =< 200

X4a + X4b + X4c =< 500

Condición de No negatividad: 1,2,3,a,b,c >= 0

CENTROS DE DISTRIBUCION Y DETALLISTAS

Un fabricante tiene tres centros de distribución en Bogota, Medellín y Cali. Estos centros tiene disponibilidad de 20, 40, y 40 unidades respectivamente. Sus detallistas requieren cantidades: Pereira 25, Tulua 10, Ansermo 20, Ibague 30 y Armenia 15. El costo de transporte por unidad en pesos entre cada centro de distribución y las localidades de los detallista se dan en la siguiente tabla:

DETALLISTAS

CENTRO DE DISTRIBUCIO

N

PEREIRA

TULUA

ANSERMO

IBAGUE

ARMENIA

BOGOTA

55 35 40 50 40

MEDELIN

35 30 100 45 60

CALI 40 60 95 35 30

Cuantas unidades debe mandar el fabricante desde cada centro de distribución a cada detallista, de manera que los costos totales de transporte sean minimos?


Variables de decisión

- Centros de Distribución: (1)Bogota, (2)Medellín, (3)Cali; (1), (2), (3), (4), (5)

Función objetivo

Min Z: 55 X11 + 30 X12 + 40 X 13 + 50 X14 + 40 X15 + 35 X21 + 30 X22 + 100 X23 + 45 X24 + 60X25 + 40X31 + 60X32 + 95 X 33 + 35 X 34 + 30X 35

Restricciones

- Oferta: * Bogota: X11 + X12 + X13 + X14 + X15 =< 20

* Medellín: X21 + X22 + X33 + X44 + X45 =< 40

* Cali: X31 + X32 + X33 + X34 + X35 =< 40

- Demanda: * Pereira: X11 + X21 + X31 = 25

* Tulua: X21 + X212+ X23 = 10

* Armensa: X31 + X32 + X33 = 20

* Ibague: X41 + X42 + X43 = 30

* Armenia: X51 + X52 + X53 = 25

Condición de no negatividad: 1,2,3 , 1,2,3,4,5 >= 0


SOLUCIÓN POR EL MÉTODO GRÁFICO

Lo utilizamos para resolver problemas de programación lineal con 2 variables.

Se grafican las restricciones del modelo y la función objetivo.

Región Factible: Conjunto de posibles soluciones -> Cumplen todas las restricciones

Se encuentra la solución óptima(mejor) o soluciones optimas si las hay.

PASOS

1. En las restricciones, transformar los términos de las desigualdades en igualdades ≤ ó ≥ → =.

2. Igualar una de las variables a cero, con el fin de encontrar los puntos de corte con los ejes

3. Trazar las rectas en el plano cartesiano.

4. Hallar los puntos de corte entre las rectas, puede utilizar igualación

5. Tener en cuenta las condiciones de no negatividad(debe trabajar en el cuadrante 1, del plano cartesiano)

6. Los puntos de solución óptima, deben ser reemplazados en la función objetivo, a fin de encontrar el valor máximo o mínimo, que cumpla todas las restricciones.

7. Hallar los puntos ó área de soluciones factibles que satisfagan todas las restricciones

Para poder graficar la solución factible óptima existen dos procedimientos:

- Evaluar la función objetivo en cada punto del área de soluciones factibles, lo tedioso es que si se tienen muchas restricciones van a generar muchos puntos que por supuesto implica la solución de ecuaciones.


- Usando la función objetivo para determinar el punto de soluciones factible que la optimiza. Lo ineficiente de este método es que cuando la FO es paralela a uno de los lados del punto de soluciones factibles causa una duda sobre cual de los puntos es que se hace que la FO sea optima.

Problema sin solución: Este caso se presenta cuando entre las restricciones existe al menos una de ellas que sean excluyentes

RESOLUCIÓN POR EL MÉTODO GRÁFICO

Revise el ejercicio de fabricación de sillas y mesas

Max Z = 3000X1 + 5000X2

Sa = 2X1 + X2 ≤ 30

X1 + X2 ≤18

X1 + X2 ≤30

X1, X2 ≥ 0

VARIABLES X1= Cantidad de Sillas a fabricar

X2 = Cantidad de Mesas a fabricar

Resolver por el método gráfico

Solución:

En las restricciones, transformar los términos de las desigualdades en igualdades ≤ ó ≥ → =.

2X1 + X2 = 30

X1 + X2 = 18

X1 + X2 = 30

Pasos 2,3,4,5


→ X1 + X2 = 18

Si X1=0 , X2= 18

Si X2=0 , X2=18

→ 2X1 + X2 = 30

SI X1 = 0 , X2=15

SIX2= 0 , X1 = 15

→X1 + 2X2 = 30

SI X1= 0 , X2= 15

SI X2 = 0 , X1= 30

GRÁFICA

Paso 6


Reemplazamos en la Función Objetivo

(0,15 ) = (3000)(0) + (15)(5000)= 75000

(0,12) = (3000)(6) + (12)(5000)= 78000→ Punto de solución optima

(12,6) = (3000)(12) + (6)(5000) = 66000

(15,0) = Ø

El punto de solución óptima debe satisfacer las restricciones

2X1 + X2 ≤ 30→ (2)(6) + 12 ≤ 30

12 + 12 ≤ 30

24 ≤ 30

X1 + X2 ≤ 18→ 6 + 12 ≤ 18

18 = 18

X1 + 2X2 ≤ 30→ 6 + 24 ≤ 30

30 = 30

RESPUESTA→ Se deben producir 6 sillas y 12 mesas para maximizar la ganancia que es de $ 78000


UTILIZACION DE COMPLEMENTO SOLVER DE MS EXCEL

Es una herramienta para resolver y optimizar ecuaciones mediante el uso de métodos numéricos.

Con solver se puede buscar el valor óptimo para una celda, denominada objetivo , en donde se escribe la fórmula de la función objetivo F(X1, X2, X3, …).

Solver cambia los valores de un grupo de celdas, denominadas celdas cambiantes y que estén relacionadas, directa o indirectamente, con la fórmula de la celda objetivo. En estas celdas se encuentran los valores de las variables controlables X1, X2, X3,…Xn.

Puede agregar restricciones a Solver, escribiendo una formula Gi(X, X2, X3… Xn) en una celda y especificando que la celda deberá ser mayor o igual, igual, o menor o igual que otra celda que contiene constante Cj.

También puede especificar valores sea enteros, para evitar dar resultados absurdos de algunos problemas, tales como que se necesitan 3.5 empleados.

Solver ajustara los valores de las celdas cambiantes, para generar el resultado especificado en la fórmula de la celda objetivo.

Solver es un excelente complemento de MS Excel que permite la resolución de

pequeños y medianos problemas de Programación Lineal. En la mayoría de las

aplicaciones con fines estudiantiles es suficiente para resolver dichas instancias.

Ahora, veamos cómo funciona con un simple ejemplo1:

MAX 10X + 16Y

S.A. 2X + 2Y <= 8

...... 1X + 2Y <= 6

..... .X>= 0, Y>= 0

PASO 1. Se ingresan los parámetros a una planilla de cálculo. Las celdas

marcadas en amarillo corresponde a las "Celdas Cambiantes" o variables de

1 http://www.programacionlineal.net/programacion_lineal.html.


decisión del modelo. La Celda C2 corresponde al Valor de la Función Objetivo que

esta dada por: A2*A3 + C2*C3. Las Celdas C5 Y C6 almacenan el valor o lado

izquierdo de las restricciones 1 y 2, quedando definidas como A2*A5 + B2*B5 y

A2*A6 + B2*B6, respectivamente.

PASO 2. Se inicia la aplicación Solver y se cargan los datos de la planilla.

PASO 3. Una vez ingresados los parámetros se selecciona "Opciones". Una vez

dentro de este menu se deben activar las opciones de "Adoptar modelo lineal" y

"Asumir no negativos". Luego se selecciona "Aceptar" y luego "Resolver.

PASO 4. Si el modelo admite solución se obtienen los resultados. Se recomienda

seleccionar los Informes que sugiere Solver para una mayor comprensión del

modelo resuelto.


PASO 5. Los resultados son desplegados en las celdas cambiantes y se verifica el

cumplimiento de las restricciones del problema. La Solución Óptima

es X=2,Y=2 con Valor Óptimo V(P)=52. Adicionalmente, ambas restricciones se

encuentran activas, es decir, se cumplen en igualdad.

PASO 6. Al seleccionar los Informes de Respuesta, en particular el "Informe de

Sensibilidad" se obtiene información relevante sobre el modelo propuesto.

Respecto a las celdas cambiantes (variables de decisión) se incluye un intervalo

de variación para los coeficientes en la función objetivo que mantienen la actual

Solución Óptima. Por ejemplo C1 (Coeficiente que acompaña a X en la función

objetivo, actualmente igual a 10) puede variar en el siguiente intervalo

garantizando la actual Solución Óptima: {10 - 2, 10 + 6} = {8, 16}. De la misma

forma el intervalo para C2 (Coeficiente que acompaña a Y en la función objetivo,

actualmente igual a 16) es {10, 20}


En cuanto a las restricciones, el precio sombra de la restricción 1 es 2, el cual es

válido siempre y cuando la variación en el lado derecho se encuentre en el

intervalo {8 - 2, 8 + 4} = {6, 12}. De la misma forma, el precio sombra para la

restricción 2 es 6, válido en el intervalo de variación del lado derecho entre {4, 8}.


SOLUCIÓN POR EL MÉTODO SIMPLEX

Es muy dispendioso, en razón a que trabaja con todos los datos de las ecuaciones, para mejorar este aspecto se creo el método simplex cuya virtud es su sencillez, este método solo trabaja con los coeficientes de la función objetivo y de las restricciones.

Criterio de decision

Maximizar Minimizar

Variable que entra

- M +M

Variable que entra

La más negativa de los Zj – Cj

La más positiva de los Zj - Cj

Variable que sale

La menos positiva de los b/a, siendo a>0, de lo contrario no restringe

La menos positiva de los b/a, siendo a>0, de lo contrario no restringe a la variable que entra

Solución optima

Cuando todos los Zj – Cj >=0

Cuando todos los Zj – Cj <=0

Para tener en cuenta:

- Si en el tablero simplex de la solución optima queda al menos una variables de Superavit o artificial dentro de las variables básicas, con un valor .0, el problema no tiene solución, esto quiere decir que al menos existen dos restricciones excluyentes, por lo tanto no existe área de soluciones factible y menos una solución, en este caso se debe revisar la formulación del problema.

- Si al escoger la variable que sale ninguna de las variables básicas restringe el crecimiento de la variable no básica escogida para entrar, el problema tiene solución indeterminada y se debe revisar la formulación en busca de una nueva restricción que no se tuvo en cuenta en la formulación inicial.

- Si en el tablero simplex del optimo, al menos una de las variables no básicas tiene coeficiente cero (0) en la función objetivo, esto es si Zj – Cj = 0, el problema tiene múltiples soluciones y se nos esta ofreciendo una de ellas.


Proceso interactivo que permite solucionar modelos de programación lineal de tamaño “n” restricciones y “m” variables.

ACTIVIDADES FUNDAMENTALES

- Prueba de Optimidad

- Identificar las variables que entran y salen

- Realizar un análisis de la tabla característica para desarrollar una nueva solución

PROCEDIMIENTO

1. Estandarize el modelo de programación lineal

2. Construya la tabla característica

3. Identificar las variables que entran y salen

4. Determine la solución básica

5. Probar la optimalidad de la función

ESTANDARIZACION DEL MODELO

Tiene que ver con las restricciones aumentadas es decir cada restricción del problema se debe aumentar utilizando variables de holgura y/o variables artificiales


Cualquier desigualdad “≤” se puede conventir en una igualdad agregando variables de holgura “Si” i= 1,2,3,4……. Para que represente el Superavit

Cualquier desigualdad “≥” se puede convertir en una igualdad restando variables de excedente o de holgura “Si” y sumando una variable artificial. Agregar una variable artificial se justifica para dar cumplimiento al criterio de no negatividad

A las restricciones donde el signo es una igualdad se le agrega una variable artificial para que represente la expresión de lado izquierdo en ausencia de las variables de holgura o excedente

La estandarización del modelo de programación lineal , también tiene que ver con la función objetivo por lo que deben agregarse a esta función todas las variables que aparecen como extras en las restricción

Los coeficientes o contribuciones de las variables extras que deben aparecer en la función objetivo tienen valores : 0, +M, -M, teniendo en cuenta: toda variable de holgura tiene una contribución de 0 para problemas de maximización o minimización.

Las variables artificiales deben tener un coeficiente positivo aproximadamente 100 veces mayor que el coeficiente mas grande que la función objetivo , cuando el problema es de minimización ; esto con el fin de evitar que estén en la solución final

Cuando el problema es de maximización el coeficiente de la variable artificial debe ser negativo y muy pequeño, para que la variable artificial no se mantenga en la base . este coeficiente se representa con la letra “M” y la variable artificial con la letra “A”.

Todo problema de programación lineal que se formule de la forma Maximice, con todas sus restricciones,<= y con la condición de no negatividad, le llamaremos Forma estándar o forma normal.

Aquí al igual que en el método algebraico debemos conseguir una solución básica factible, empleando las variables de holgura y/o artificiales.

EJEMPLO

Min Z = 8X1 + 2X2

Sa = 2X1 + 3X2 ≤ 40


4X1 + 6X2 ≥ 10

5X1 + 2X2 = 20

ESTANDARIZACIÓN

2X1 + 3X2 + S1 =40

4X1 + 6X2 -S2 + A1 =10

5X1 + 2X2 + + A2= 20

Función objetivo

Min Z = 8X1 + 2X2 + 0S1 – 0S2 + MA1 + MA2

CARACTERISTICAS DE LAS VARIABLES DE ESTANDARIZACION

VARIABLE Si = representan el superávit o déficit de recursos excasos. Puede ser variable básica en la solución óptima.

VARIABLE ARTIFICIAL Ai = son ficticias ya que solo se usan al comienzo del proceso simplex para la estandarización del modelo y cumplir con el criterio de no negatividad . no pueden ser variables básicas en la solución optima. Si esto llega a suceder el problema no tiene solución. Son instrumentos de calculo que se usan en las restricciones “≥” ó “=”.

DISEÑO DE LA TABLA

EJEMPLO

Max Z = C1X1 + C2X2………+ CnXn


Sa = a11X1+ a12X2……+ a1nXn ≤ B1

a21X1 + …………….+ a2nXn ≤ B2

Xi ≥ 0

Ci X1 X2 ….Xn Ѳi

C1

C2

C3

X1

X2

X3

B1

B2

B3

a 11

..

..

a 12

..

..

…a1n

..

..

Ѳ1

Ѳ2

Ѳ3

Zj BФ

Cj - Zj

Cj – Zj = Parámetro de optimización ( costos reducidos ).

Ѳi = Bi = Parametro de factibilidad (marca la pauta de la variableque sale)

aij

m

Zj = BФ = ∑ CiBi

i = 1

Ci = contribución de la variable básica (VB )

Xj = Variables Basicas y No Basicas.

Bi = Disponibilidad de recursos al comienzo y valor de las variables básicas al final o sobrante de un recurso

BФ = Valor del Z optimo


DETERMINACION DE LA VARIABLE QUE ENTRA Y SALE

COLUMNA PIVOTE = variable que entra a partir de Cj – Zj se busca el numero mas positivo a partir de cero para problemas de maximización.

VARIABLE QUE ENTRA = se obtiene a partir de Cj – Zj desde cero buscando el mas negativo para el caso de minimización.

FILA PIVOTE (variable que sale)= se optiene a partir de Ѳi mas cercano a cero para cualquier criterio de optimización en la intersección de la columna y la fila se encuentra la celda pivote

DETERMINACION DE LA NUEVA SOLUCIÓN

Introducir a la base la variable correspondiente a la columna pivote que tomara el puesto que corresponde a la fila pivote. Una vez se haga el intercambio se aplica Gauss Jordan para hacer la interaccion simplex.

PROBAR LA OPTIMALIDAD DE LA FUNCIÓN

El proceso simplex se termina cuando todos los Cj – Zj son ceros o negativos en problemas de Maximizacion ; y ceros o positivos en problemas de minimizacion las iteraciones tienen en cuenta la elección de la celda pivote y luego la iteraccion simplex.

ELECCIÓN DE LA CELDA PIVOTE

Se tienen en cuenta 2 criterios


Criterio de optimalidad = El mayor o menor negativo, según el caso, costo reducido dado por Cj – Zj este valor es llamado costo de oportunidad neto y esta dado por la suma de algebraica de la contribución de la variable que sale y la variable que entra.

Criterio Dos = seleccionada la fila pivote se toma como base los aij de la columna anterior para relacionarlos con los recursos disponibles Bi, al fin de obtener el valor de Ѳi que permite aplicar el criterio de factibilidad a partir del Ѳi mas cercano a cero. La excogencia del menor Ѳi se debe a que explica la relación existente entre la disponibilidad del recurso y la tasa de susutitucion , es decir permite visualizar cuanto es lo máximo que puede producir.

Se llama tasa de susutitucion porque susutituye el recurso disponible por un recurso determinado o durante el proceso sustituye lo requerido entre dos variables.

INTERACCIÓN SIMPLEX

Para hacer la iteraccion simplex debe elaborarse un nuevo tablero donde en la base debe aparecer la variable que entra con sus respectivas contribuciones y a partir de esta fila aplicar Gauss Jordan a fin de obtener el nuevo valor de a función objetivo . la solución optima se encuentra en aquel tablero en que los costos de oportunidad sean ceros o negativos o positivos según el caso. La existencia de valores positivos como costos de oportunidad significa que hay incentivos para hacer una nueva combinación que optimiza el valor de Z positivo en caso de Maximizacion y negativo en caso de Minimizacion.

En todos los procesos simplex donde alla costos de oportunidad o Ѳi iguales debe decidirse arbitrariamente.

EJEMPLO METODO SIMPLEX

Min Z = X1 + X2

Sa= X1 + X2 ≥ 2


-X1 + X2 ≥ 3

X1 +3X2 ≥ 12

ESTANDARIZACIÓN

1X1 + 1X2 -1S1 +1A1 = 2

-X1 +1X2 -S2 +1A2 = 3

1X1 + 3X2 +S3 = 12

X1,X2,Si,Ai ≥ 0

Funcion Objetivo

Min Z = X1 + 2X2 + 0S1 + OS2 + 0S3 + MA1 + MA2

Cj 1 2 0 0 0 M M θi

Ci VB Bi X1 X2 S1 S2 S3 A1 A2 Bi/ai

M A1 2 1 1 -1 0 0 1 0 2

M A2 3 -1 1 0 -1 0 0 1 3

0 S3 12 1 3 0 0 1 0 0 4

Zj 5M 0 2M -M -M 0 M M

Cj-Zj 1 2-2M M M 0 0 0

Cj 1 2 0 0 0 M M θi



2 X2 2 1 1 -1 0 0 1 0

M A2 1 -2 0 1 -1 0 -1 1 1

0 S3 6 -2 0 3 0 1 -3 0 2

Zj 4+M 2-2M 2 -2+M -M 0 2-M M

Cj-Zj -1+2M 0

2-M

M

0 -2+2M 0

Cj 1 2 0 0 0 M M θi


2 X2 3 -1 1 0 -1 0 0 1

0 S1 1 -2 0 1 -1 0 -1 1

0 S3 3 4 0 0 3 1 0 -3

Zj 6 -2 2 0 -2 0 0 2

Cj-Zj 3 0 0 2 0 M M-2

CASOS ESPECIALES

Un problema de programación lineal tiene soluciones multiples cuando en el tablero optimo existe una variable no básica con Cj – Zj = 0

Existe una solución degenerada cuando el tablero optimo aparece una variable básica en cero

Existe una solución ilimitada cuando las iteraciones son infinitas

Sin solución o no factible aquellas en el que el tablero optimo aparece una variable básica artificial.


DUALIDAD

Si el primal tiene criterio de optimización maximización, en el dual se incluye minimización y viceversa


Si el primal tiene signos “≥” el dual tiene signos “≤” y viceversa

Las constantes de beneficio Cj de la función objetivo se reemplazan por las constantes de capacidad Bi y viceversa.

En las desigualdades de restricción los coeficientes que se encontraron de izquierda a derecha se coloca en ellos de arriba hacia abajo y viceversa.

Los coeficientes tecnológicos que componen las filas de cada uno de los modelos conforman las columnas del modelo dual y viceversa.

Ignorando el numero de condiciones de no negatividad si en el primal hay “n” variables y “m” desigualdades , en el dual abra “m” variables y “n” desigualdades.

Se desea generalmente en los problemas de minimización que sus restricciones sean ≥ si no es asi se multiplican ambos términos de lado derecho e izquierdo por -1 y se cambia la desigualdad.

EJEMPLO

Min Z = 40 X1+ 200 X2

Sa = 4X1 + 40X2 ≥ 160

3X1 + 10X2 ≥ 60

8X1 + 10X2 ≥ 80

X1, X2 ≥ 0

Primal →2 variables

3 desigualdades

Max Z = 160Y1 + 60Y2 + 80Y3

Sa = 4 Y1 + 3Y2 + 8Y3 ≤ 40

40Y1 + 10Y2 + 10Y3

≤ 200


Y1,Y2,Y3 ≥ 0

Dual → 3 Variables

2 Desigualdades

METODO “SIMPLEX”, DUALIDAD Y SENSIBILIDAD

Utilice el método simplex para resolver los siguientes problemas:

1- MAXIMIZAR Z = X1 +X2

C.S.R: 5X1 + 3X2 ≤ 15

3X1 + 5X2 ≤ 15

CON X1,X2 ≥ 0

Solución:

Maximizar Z = X1 + X2 + 0S1 +0S2

S.a: 5X1 + 3X2 + S1 ≤ 15

3X1 + 5X2 + S2≤ 15

X1, X2, S1, S2 ≥ 0

Cj 1 1 0 0 Θi


Ci Vb Bi X1 X2 S1 S2 Bi/ai

0 S1 15 5 3 1 0 3

0 S2 15 3 5 0 1 5

Zj 0 0 0 0 0

Cj-Zj 1 1 0 0

Cj 1 1 0 0 Θi


1 X1 3 1 0.6 0.2 0 5

0 S2 6 0 3.2 -0.6 1 1.875

Zj 3 1 0.6 0.2 0

Cj-Zj 0 0.4 -0.2 0

Cj 1 1 0 0 Θi


1 X1 1.875 1 0 0.3125 -0.188

1 X2 1.875 0 1 -0.1875 0.3125

Zj 3.75 1 1 0.125 0.125

Cj-Zj 0 0 -0.125 -0.125

Z= 3.75

X1= 1.875 X2= 1.875


2- La cia Peer fabrica cuatro productos (1,2,3,4) . En la siguiente tabla se enumeran, los requerimientos de materia prima , el especio de almacenamiento necesario, las tasas de producción y ganancia. La cantidad total de material, disponible diariamente, para todos los cuatro productos es 180 libras. El espacio total disponible para almacenamiento es de 230 pies cuadrados y en producción se utilizan 7 horas por día .

CUADRO RESUMEN Producto 1 Producto 2 Producto 3 Producto 4

Materia Prima, libras/unidad 2 2 1,5 4

Espacio, pies cuadrado/unidad 2 2,5 2 1,5

Tasa de producción, unidades/ hora 15 30 10 15

Ganancia, $/unidad 5 6,5 5 5,5

¿Cuántas unidades de cada producto deben fabricarse para maximizar la ganancia?

Maximizar Z= 5X1 + 6.5X2 + 5X3 +5.5X4

S.A.:

2X1 + 2X2 + 1.5X3 + 4X4 ≤ 180

2X1 + 2.5X2 + 2X3 + 1.5X4 ≤ 180

15X1 + 30X2 + 10X3 + 1.5X4 ≤ 180

X1, X2, X3, X4 ≥ 0

Solución:

Maximizar Z= 5X1 + 6.5X2 + 5X3 + 5.5X4 + 0S1 + 0S2 + 0S3


S.A.:

2X1 + 2X2 + 1.5X3 + 4X4 + S1 ≤ 180

2X1 + 2.5X2 + 2X3 + 1.5X4 + S2 ≤ 180

15X1 + 30X2 + 10X3 + 1.5X4 + S3≤ 180

X1, X2, X3, X4, S1, S2, S3 ≥ 0

Cj 5 6.5 5 5.5 0 0 0 Θi

Ci Vb Bi X1 X2 X3 X4 S1 S2 S3 Bi/ai

0 S1 180 2 2 1.5 4 1 0 0 90

0 S2 230 2 2.5 2 1.5 0 1 0 92

0 S3 7 15 30 10 15 0 0 1 0.2333

Zj 0 0 0 0 0 0 0 0

Cj-Zj 5 6.5 5 5.5 0 0 0

Cj 5 6.5 5 5.5 0 0 0 θi


0 S1 179.5 1 0 0.833333 3 1 0 -0.067 215.44

0 S2 229.4 0.75 0 1.166667 0.25 0 1 -0.083 196.64

6.5 X2 0.233 0.5 1 0.333333 0.5 0 0 0.033 0.7

Zj 1.517 3.25 6.5 2.166667 3.25 0 0 0.217


Cj-Zj 1.75 0 2.833333 2.25 0 0 -0.217

Cj 5 6.5 5 5.5 0 0 0 Θi


0 S1 179 -0.25 -2.5 0 1.75 1 0 -0.15

0 S2 228.6 -1 -3.5 0 -1.5 0 1 -0.2

5 X3 0.7 1.5 3 1 1.5 0 0 0.1

Zj 3.5 7.5 15 5 7.5 0 0 0.5

Cj-Zj -2.5 -8.5 0 -2 0 0 -0.5

De acuerdo al primal del ejercicio anterior:

Transfórmelo en un problema dual.

Minimizar C= 180Y 1 + 230Y2 + 7Y3

S.A.: 2Y1 + 2Y2 + 15Y3 ≥ 5

2Y1 + 2.5Y2 + 30Y3 ≥ 6.5

1.5Y1 + 2Y2 + 10Y3 ≥ 5

4Y1 + 1.5Y2 + 15Y3 ≥ 5.5

VARIABLES Y1 Y2 Y3

180 230 7

CANTIDAD 0 0 0.5

3.5


S.A.

2 2 15 7.5 >= 5

2 2.5 30 15 >= 6.5

1.5 2 10 5 >= 5

4 1.5 15 7.5 >= 5.5

¿Cuál es su interpretación económica?

Y1= costo de una unidad de materia prima.

Y2= costo de una unidad de espacio de almacenamiento.

Y3= costo de unidad de tiempo de producción por cada unidad de producto.

Para el Producto 1: 2Y1 + 2Y2 + 15 Y3, la suma es el valor total de los insumos para producir una unidad de este producto. El valor de los insumos que entran en la producción de una unidad de este producto, que es $7.5 debe ser mayor o igual al beneficio que la empresa hace al producir una unidad del Producto 1, el cual es $5.

Y asi sucesivamente se va realizando el análisis con cada uno de los productos.

Resuélvalo por Solver, realice el análisis de sensibilidad y explique:

Variables X1 X2 X3 X4

Ganancia 5 6.5 5 5.5

Cantidad 0 0 0.7 0

Utilidad 3.5


S.A

mat prim lb/u 2 2 1.5 4 1.05 <= 180

espacio, pies cua 2 2.5 2 1.5 1.4 <= 230

tasa prod unid/h 15 30 10 15 7 <= 7

ANÁLISIS DE SENSIBILIDAD

INFORME DE SENSIBILIDAD:

Celdas cambiantes

Valor Gradiente Coeficiente Aumento Disminución

Celda Nombre Igual reducido objetivo permisible permisible

$C$11 x1 0 -2.5 5 2.5 1E+30

$D$11 x2 0 -8.5 6.5 8.5 1E+30

$E$11 x3 0.7 0 5 1E+30 1.333333333

$F$11 x4 0 -2 5.5 2 1E+30

Restricciones


Valor Sombra Restricción Aumento Disminución

Celda Nombre Igual precio lado derecho permisible permisible

$G$4 mat prim lb/u Suma Prod 1.05 0 180 1E+30 178.95

$G$5 espacio, pies cua Suma Prod 1.4 0 230 1E+30 228.6

$G$6 tasa prod unid/h Suma Prod 7 0.5 7 1143 7

Informe de límites:

Celda objetivo

Celda Nombre Igual

$C$13 Utilidad x1 3.5

Celdas cambiantes Límite Celda Límite Celda

Celda Nombre Igual inferior objetivo superior objetivo

$C$11 x1 0 0 3.5 0 3.5

$D$11 x2 0 0 3.5 0 3.5

$E$11 x3 0.7 0.7 3.5 0.7 3.5

$F$11 x4 0 0 3.5 0 3.5

- ¿Cuál es el valor de la función objetivo y los valores de cada variable?


El valor de la función objetivo es 3.5 y los valores de las variables X1, X2, X3, y X4 son 0, 0, 0.7 y 0 respectivamente.

-¿Qué interpretación tienen los precios sombra, los costos reducidos, limites, Aumento permisible, disminución permisible?

Precio sombra: Si se dispone de mas horas en la producción, se podría mejorar la utilidad global incrementándose en $ 0.5 por cada hora extra.

Costos reducidos: Las variables X1, X2 y X4 son negativas, es decir no conviene producir estos productos, en cambio X3 es positiva (conviene producir este producto), por lo que su costo reducido es cero.

Limites: El menor valor que puede tomar las variables X1, X2, X3, X4 es 0, 0, 0, y 0 respectivamente (suponiendo que las demás mantienen el valor optimo encontrado), el cual es el mismo valor mayor que pueden tomar y así satisfacer todas las restricciones.

Aumento permisible: Los coeficientes de la función objetivo tienen un incremento admisible de 2.5, 8.5,1E+30, 2 respectivamente sin que cambien los valores óptimos de las variables controlables.

Disminución permisible: Es lo contrario de aumento, es decir que es la disminución admisible en los coeficientes de la función objetivo que para este caso son: 1E+30, 1E+30, 1.333333, 1E+30 respectivamente, sin que los valores óptimos de las variables controlables cambien.


MODELO DE ASIGNACIÓN Y TRANSPORTE

MÉTODO HÚNGARO:

En cada fila establezca el menor costo y reste este a toda la fila. Continúe esta operación con las filas siguientes

Establezca el menor costo por columnas

Establezca la menor cantidad de líneas rectas que agrupen los ceros (Horizontal o vertical).

De acuerdo a la matriz nxn se debe establecer que el número de líneas horizontales y verticales sea igual o mayor al número de filas o columnas. Una vez se cumple con el criterio, hemos encontrado una solución óptima.

Asigne los elementos a cada centro de trabajo, teniendo en cuenta que cada elemento asignado a un centro de trabajo excluye su operación o asignación.

EJEMPLO:

Una organización tiene 3 centros de trabajo (CT1, CT2, CT3), elabora piezas especiales para aviones boing. A continuación se detallan los costos que tendría que realizar en cada centro de trabajo para la fabricación de cada producto:

Encontramos el costo menor por filas:


CT1 CT2 CT3

R34 11 9 6

S67 12 8 10

T-50 3 4 9

El costo menor se resta a cada valor de la fila con el fin de buscar la solución óptima:

CT1 CT2 CT3

R34 5 3 0

S67 4 0 2

T-50 0 1 6

Se traza el menor número de líneas que pasen por los valores iguales a cero:

CT1 CT2 CT3

R34 5 3 0

S67 4 0 2

T-50 0 1 6


Por último se realiza la asignación de cada uno teniendo en cuenta que se deben elegir valores que estén dentro de las líneas trazadas y los de menor costo, es decir, costo=0:

R34 CT3

S67 CT2

T-50 CT1

MÉTODO DE LA ESQUINA NOROESTE:

Consiste en igualar el elemento e la esquina superior izquierda con el menor valor entre su disponibilidad y su demanda. Se completa la fila o columna correspondiente hasta saturarla, es decir, hasta que se haya agotado la disponibilidad correspondiente o se haya satisfecho la demanda de este destino. Repetiremos este proceso, eliminando la fila o columna que se encuentre saturada, hasta completar la solución.

EJEMPLO:

Cierto fabricante dispone de tres centros de distribución para sus productos que denominaremos A, B y C, y cuyas disponibilidades de materia prima son respectivamente 100, 120 y 120 Tm. Esta materia prima debe ser entregada en cinco fábricas donde se elabora el producto final. Las necesidades en Tm de materia prima de cada una de las fábricas son 40, 50, 70, 90 y 90. Señala una solución factible utilizando el método de la esquina noroeste.

Construimos la tabla de transporte del problema:


1 2 3 4 5 bi

A 100

B 120

C 120

dj 40 50 70 90 90 340

Comenzamos asignando en la casilla superior izquierda, es decir, en la casilla noroeste el primer valor de dj. o sea transportaremos 40 Tm de materia prima desde el centro de distribución A hasta la fábrica , satisfaciendo así las necesidades de este destino, con lo cual saturamos la primera columna, pues ya no se transportarán más unidades de materia prima a esta fábrica.

1 2 3 4 5 bi

A 40 100

B 120

C 120

dj 40 50 70 90 90 340

Seguiremos asignando en la casilla de la esquina noroeste, en este caso X12. La asignación será igual al mínimo entre su disponibilidad (una vez ajustado el efecto de la asignación anterior) y su demanda. De esta forma se satisface la demanda del destino 2, por lo que esta columna queda saturada y la eliminaremos en los siguientes pasos.


1 2 3 4 5 bi

A 40 50 100

B 120

C 120

dj 40 50 70 90 90 340

La nueva casilla noroeste es la X13 en la que asignaremos el mínimo entre su disponibilidad y su demanda, es decir, 10 en este caso. De esta forma se satura la primera fila al haberse agotado la disponibilidad de materia prima del centro de distribución A.

1 2 3 4 5 bi

A 40 50 10 100

B 120

C 120

dj 40 50 70 90 90 340

La siguiente asignación en la casilla noroeste será X23, que equivale a 60, con lo que saturamos la tercera columna, correspondiente a la fábrica 3.


1 2 3 4 5 bi

A 40 50 10 100

B 60 120

C 120

dj 40 50 70 90 90 340

Volvemos a seleccionar la casilla noroeste y asignamos hasta saturar la fila o la columna correspondiente, es decir, X24=60

1 2 3 4 5 bi

A 40 50 10 100

B 60 60 120

C 120

dj 40 50 70 90 90 340

Completamos el proceso de búsqueda de una solución inicial factible a través de la esquina noroeste, obteniendo X34=30, con lo que restaría la única asignación más en la casilla X35=90. De esta forma, una solución inicial factible sería la señalada en la siguiente tabla:

1 2 3 4 5 bi

A 40 50 10 100


B 60 60 120

C 30 90 120

dj 40 50 70 90 90 340

MÉTODO DEL MÍNIMO DE FILAS Y COLUMNAS:

MÍNIMO DE FILAS:

Siendo C1j el menor costo de transporte correspondiente a la primera fila de la tabla de transporte, igualaremos X1j al menor valor entre su disponibilidad (b1) y su demanda (dj), saturando de esta forma la fila o la columna respectiva. Si es la fila la que resulta saturada, seguiremos asignando en la misma fila hasta saturar la capacidad de dicho origen (bi).

MÍNIMO DE COLUMNAS:

Es similar al anterior, pero se actúa por columnas en lugar de hacerlo por filas.

EJEMPLO:

Resolver el problema anterior utilizando el método del mínimo de filas y del mínimo de columnas. Teniendo en cuenta que presentaremos a continuación la tabla de datos:


1 2 3 4 5

A 10 20 5 9 10

B 2 10 8 30 5

C 1 20 7 10 4

Aplicando el método de mínimo de filas, la tabla de transporte sería:

O D 1 2 3 4 5 bi

A 10 X11 20 X12 5 X13 9 X14 10 X15 100

B 2 X21 10 X22 8 X23 30 X24 5 X25 120

C 1 X31 20 X32 7 X33 10 X34 4 X35 120

dj 40 50 70 90 90 340

Comenzando con la primera fila, seleccionamos la casilla de menor costo unitario de transporte y asignamos hasta saturar la fila o la columna correspondiente. En este caso, la variable de menor costo unitario de transporte es X13 (C13=5), por lo que el valor de dicha variable será 70, satisfaciendo de esta forma las necesidades de materia prima en la fábrica 3 y eliminaremos, por tanto, esta columna.


O D 1 2 3 4 5 bi

A 10 X11 20 X12 5 70 9 X14 10 X15 100

B 2 X21 10 X22 8 30 X24 5 X25 120

C 1 X31 20 X32 7 10 X34 4 X35 120

dj 40 50 70 90 90 340

Como no hemos saturado la fila con la que estamos trabajando, volvemos a iterar el procedimiento. La variable de menor costo unitario será ahora X14, de manera que X14=30, saturando la fila 1 al haber transportado toda la disponibilidad del origen A.

O D 1 2 3 4 5 bi

A 10 20 5 70 9 30 10 100

B 2 X21 10 X22 8 30 X24 5 X25 120

C 1 X31 20 X32 7 10 X34 4 X35 120

dj 40 50 70 90 90 340

Continuamos desarrollando el proceso de búsqueda de una solución factible a través de las filas de la matriz de transporte obteniendo el siguiente resultado:


O D 1 2 3 4 5 bi

A 10 20 5 70 9 30 10 100

B 2 40 10 8 30 5 80 120

C 1 20 50 7 10 60 4 10 120

dj 40 50 70 90 90 340

Aplicando el método de mínimo de columnas se genera la siguiente solución inicial factible:

O D 1 2 3 4 5 bi

A 10 20 5 70 9 30 10 100

B 2 10 50 8 30 5 70 120

C 1 40 20 7 10 60 4 20 120

dj 40 50 70 90 90 340

MÉTODO DE VOGEL:

Se trata de un procedimiento de búsqueda que podemos examinar a través del siguiente proceso:

Para cada fila y cada columna calculamos la diferencia en valor absoluto entre el menor costo unitario y el siguiente menor, seleccionando aquella fila o columna que proporcione MAYOR diferencia.


En dicha fila o columna seleccionamos la variable (Xij) con menor costo unitario y asignamos hasta completar la demanda (dj) o la disponibilidad (bi). La fila o columna que resulte saturada no se considerará en posteriores iteraciones.

Volvemos a iniciar el proceso hasta completar una solución inicial factible.

EJEMPLO:

A continuación aplicaremos el método de Vogel al ejemplo que venimos utilizando anteriormente. Tener en cuenta la siguiente tabal de datos:

1 2 3 4 5

A 10 20 5 9 10

B 2 10 8 30 5

C 1 20 7 10 4

Comenzaremos calculando las diferencias de costo en cada fila y cada columna:

O D 1 2 3 4 5 bi Diferencia de costos

A 10 X11 20 X12 5 X13 9 X14 10 X15 100 4

B 2 X21 10 X22 8 X23 30 X24 5 X25 120 3

C 1 X31 20 X32 7 X33 10 X34 4 X35 120 3

dj 40 50 70 90 90 340


Dif de costos

1 10 2 1 1

Seleccionamos la diferencia de mayor valor, que se corresponde con la columna 2, y asignamos en la casilla de menor costo de este columna (X22) el mínimo entre su disponibilidad y su demanda, es decir, 50. Con lo que saturamos la columna que dejaremos de considerar en las siguientes iteraciones de este proceso de búsqueda de Vogel.

A continuación, volvemos a calcular diferencias de costo para cada fila y cada columna:


A 10 X11 20 5 X13 9 X14 10 X15 100 4

B 2 X21 10 50 8 X23 30 X24 5 X25 120 3

C 1 X31 20 7 X33 10 X34 4 X35 120 3

dj 40 50 70 90 90 340

Dif de costos

1 -- 2 1 1

En esta segunda iteración, la mayor diferencia se encuentra en la fila 1 para la que seleccionamos la variable de menor costo unitario de transporte (X13) en la que asignaremos X13=70, saturando, de esta forma, la columna 3:



A 10 X11 20 5 70 9 X14 10 X15 100 1

B 2 X21 10 50 8 30 X24 5 X25 120 3

C 1 X31 20 7 10 X34 4 X35 120 3

dj 40 50 70 90 90 340

Dif de costos

1 -- -- 1 1

En la tercera iteración se produce un empate para las menores diferencias de costo entre los orígenes B y C que, o bien se rompe arbitrariamente, o bien se examina cuál de las dos columnas posee la casilla de menor costo, seleccionando esta. Nosotros optamos por la segunda alternativa y elegimos la fila 3, que incluye la variable de menor costo unitario (C31=1), asignando hasta saturar la fila o la columna correspondiente: X31=40


A 10 20 5 70 9 X14 10 X15 100 1

B 2 10 50 8 30 X24 5 X25 120 25

C 1 40 20 7 10 X34 4 X35 120 6

dj 40 50 70 90 90 340

Dif de costos

-- -- -- 1 1

Nuevamente calculamos las diferencias de costo y seleccionamos la de mayor valor absoluto, que en este caso corresponde a la fila 2, en l que asignaremos en su variable de menor costo unitario, X25=70



A 10 20 5 70 9 X14 10 X15 100 1

B 2 10 50 8 30 5 70 120 --

C 1 40 20 7 10 X34 4 X35 120 6

dj 40 50 70 90 90 340

Dif de costos

-- -- -- 1 6

El cálculo de las nuevas diferencias de costo señala como variable básica X35 en la que asignaremos hasta saturar la fila o columna correspondiente X35=20

O D 1 2 3 4 5 bi

A 10 20 5 70 9 X14 10 100

B 2 10 50 8 30 5 70 120

C 1 40 20 7 10 X34 4 20 120

dj 40 50 70 90 90 340

Finalmente, completaremos la solución inicial factible con las variables restantes de manera que se satisfagan las restricciones del problema, obteniendo el siguiente resultado:


O D 1 2 3 4 5 bi

A 10 20 5 70 9 30 10 100

B 2 10 50 8 30 5 70 120

C 1 40 20 7 10 60 4 20 120

dj 40 50 70 90 90 340


PROGRAMACIÓN ENTERA

MÉTODO DE EGON Y BALAS (Min):

Este es un método iterativo que permite encontrar soluciones enteras cuando se tienen problemas de más de dos variables.

Pasos de solución:

En la primera iteración iguala cada una de las variables de las restricciones a cero.

Iguala una de las variables de las restricciones a uno (1) y las demás se toman como un valor igual a cero. Continúe repitiendo este punto con cada variable presente.

Cada respuesta se compara al reemplazar cada valor en la restricción y si cumple con el signo que presenta se toma como verdadero, lo cual no se penaliza y se pone cero; de lo contrario se toma como falso y se penaliza con el monto obtenido en valor absoluto. Luego se suma esto y la respuesta es la infactibilidad.

Elije la menor infactibilidad y reemplaza el valor elegido en cada una de las restricciones.

Realiza la segunda iteración realizando cada paso anterior con las nuevas restricciones obtenidas.

Reemplaza en la función objetivo y elije la e menor costo.


EJEMPLO:

Mín W = 5X1 + 6X2 + 7X3 + 8X4 + 9X5

Restricciones:

3X1 - X2 + X3 + X4 - 2X5 - 2 0

X1 + 3X2 - X3 - 2X4 + X5 + 0 0

-X1 - X2 + 3X3 + X4 + X5 - 1 0

Primera iteración:

X1= X2 = X3 = X4 = X5 =0

-20 F 2

00 V 0

-10 F 1

3 infactibilidad

X1=1 X2 = X3 = X4 = X5 =0

10 V 0

10 V 0

-20 F 2

2 infactibilidad


X2=1 X1 = X3 = X4 = X5 =0

-30 F 3

30 V 0

-20 F 2

5 infactibilidad

X3=1 X1 = X2 = X4 = X5 =0

-10 F 1

-10 F 1

20 V 0

2 infactibilidad

X4=1 X1 = X2 = X3 = X5 =0

-10 F 1

-20 F 2

00 V 0

3 infactibilidad

X5=1 X1 = X2 = X3 = X4 =0

-40 F 4

10 V 0

00 V 0


4 infactibilidad

Reemplazo el menor valor de factibilidad en las restricciones:

X1=1

- X2 + X3 + X4 - 2X5 + 1 0

3X2 - X3 - 2X4 + X5 + 1 0

- X2 + 3X3 + X4 + X5 - 2 0

Segunda iteración:

X2=1 X3 = X4 = X5 =0

00 V 0

40 V 0

-30 F 3

3 infactibilidad

X3=1 X2 = X4 = X5 =0

20 V 0

00 V 0

10 V 0

0 infactibilidad

X4=1 X2 = X3 = X5 =0


20 V 0

-10 F 1

-10 F 1

2 infactibilidad

X5=1 X2 = X3 = X4 =0

-10 F 1

20 V 0

-10 F 1

2 infactibilidad

Reemplazo los valores menores e infactibilidad en la función objetivo:

X3=1

X1=1

W = 5X1 + 6X2 + 7X3 + 8X4 + 9X5

=12

X1 = 1

X4 =1

W = 5X1 + 6X2 + 7X3 + 8X4 + 9X5

=13


X1 = 1

X5 =1

W = 5X1 + 6X2 + 7X3 + 8X4 + 9X5

=14

La solución óptima es la de X3=1 y X1=1, ya que es la que representa menor costos

Documents

Manual Investigacion de Operaciones 2013