• Author / Uploaded
• Antolino Garcia Bocio

Citation preview

UNIDAD 4 INTRODUCCION Wagner (1950) y Alan S. Manne (1959) se consideran los pioneros de la programación lineal, ya que tradicionalmente sus modelos se consideran subclases de la programación lineal; aunque, las variables de decisión que aparecen en dichos modelos solo toman valores enteros, por lo que en realidad deben considerarse como problemas de programación entera.

Métodos de solución Algoritmo fraccional de Gomory

Paso 1. Resolver el problema primal; si la solución es entera, esta corresponde a la solución óptima para el problema de programación lineal entera. Paso 2. Seleccionar variables con soluciones decimales y escoger aquella que tenga la mayor parte fraccionaria tomando las ecuaciones completas. Paso 3. Los coeficientes de la ecuación se expresan separando la parte entera y se, retienen solamente la parte fraccionaria.

Método de ramificación y acotamiento (Branh and bound) La solución para cada problema de programación lineal entera se divide en dos subproblemas. En tal caso, para cada subproblema puede ocurrir lo siguiente: 1. Cuando el subproblema es no factible de solucionarse se da por terminado. 2. Cuando la solución es entera, mejor que cualquier solución entera conocida es candidata a solución, no se busca más. 3. Cuando la solución es fraccionaria, mejor que la solución entera conocida más adecuada, el problema se fracciona en dos. 4. Cuando la solución es peor que la mejor solución entera conocida; no se investiga más.

Método de enumeración exhaustiva o enumeración explícita Este consiste en enumerar todas las soluciones posibles, a partir de los valores tomados para las variables enteras y realizar todas las combinaciones posibles hasta encontrar una que nos proporcione el valor óptimo de la función objetivo y que cumpla con todas las restricciones del problema.

Programación lineal entera binaria Por lo general, siempre utilizamos la noción de tipo binario en nuestros razonamientos y en nuestras acciones: todo o nada, blanco o negro, abierto o cerrado, existe o no existe, 0 o 1, verdadero o falso, prendido o apagado, muerto o vivo, entre otros.

Métodos de solución Método de enumeración implícita cero-uno El método de enumeración implícita cero-uno consiste en enumerar todas las soluciones y analizarlas; se entiende que este proceso es bastante dispendioso, sobre todo si se tiene un número apreciable de variables, ya que el número de combinaciones corresponde a 2n, donde n es el número de variables del problema.

Método aditivo (enumeración) de Egon Balas El método de Balas constituye un procedimiento de enumeración que encuentra el óptimo de forma más rápida; la eficacia de este método consiste en la evaluación de solo algunas soluciones. Dicho método empieza poniendo todas las variables iguales a cero y luego, mediante un procedimiento sistemático de forma consecutiva, asigna el valor de 1 a cada una de las variables; luego, estas se reemplazan en cada una de las restricciones y se averigua la infactibilidad.

Programación lineal entera mixta En un problema de programación lineal entera mixta, algunas variables deben ser enteras, mientras que otras pueden no serlo.

Problema del transporte o distribución El problema del transporte o distribución se considera un problema de redes, que no es usual resolverlo por simplex, ya que resulta bastante extenso, porque al establecer las ecuaciones de oferta entre las fuentes y la demanda hacia los destinos resultan igualdades.

Regla de la esquina noroeste Se empieza en la celda que se encuentra en la celda noroeste (esquina superior izquierda) y se asigna lo máximo que se pueda por fila (columna) y se sigue sucesivamente de la misma manera hasta llegar a la última celda que se pueda asignar, para obtener así una solución factible inicial.

Unidad 5 Algoritmos especiales: el problema de transporte Introducción al problema de transporte El modelo de transporte es un caso especial en la programación lineal. El problema tiene como objetivo minimizar los costos de distribución de cierto número de unidades de las fuentes u orígenes a los destinos. En el modelo más elemental, las fuentes son entidades que ofertan cierto número de unidades, mientras que los orígenes reciben cierto número de unidades. Esto implica que los orígenes son proveedores de unidades y los destinos, constituyen las entidades que demandan estas.

Modelo de programación lineal del problema de transporte En esta sección plantearemos el modelo de programación lineal (MPL) para el problema de transporte y después lo extenderemos para el problema de transbordo. Por último, modelaremos el problema de transporte, con el fin de generalizar su uso en cualquier red de transporte.

MPL para el modelo de transporte Para formalizar el problema de transporte, definiremos las variables de decisión como xik, el número de unidades que se envían de la fuente i al destino k. De tal suerte, que la suma de todos los costos ci k xi k constituye la función objetivo sujeta

a no rebasar la capacidad de los nodos fuente y a que la demanda de los nodos destino sea cubierta. Entonces, formalmente el modelo es el siguiente:

Min_

lk ΣΣcik xik Sujeto a:

i ik

i

Σx

≤

o

i

Σx

=

d

para_toda_fuente _i k ik para_todo_origen_k Xik ≥ 0

MPL para el modelo de transbordo Para definir este modelo, es necesario definir dos variables: a) xij, que es la cantidad de unidades enviadas de las fuentes i a los transbordos j, y b) yjk, definida como la cantidad de unidades que son enviadas del transbordo j al destino k.

Método de la esquina noroeste En este método las variables básicas son las que están en la esquina noroeste de la tabla inicial. En este caso, el valor de la variable es el valor máximo entre la oferta del renglón y la demanda de la columna. En tanto, el valor mínimo se resta de la oferta y la demanda correspondientes.

Método del costo mínimo Este método consiste en colocar la mayor cantidad de unidades en la celda que

tiene el menor costo.

Método de Aproximación de Vogel (MAV ) Este método se basa en un concepto llamado costo de penalización, definido como la diferencia entre los dos costos de transporte menores por columna o renglón, y se calcula por cada columna y cada renglón. Este método se desarrolla en tres pasos: 1) calcula el costo de penalización para cada renglón y para cada columna; 2) selecciona la columna o el renglón con el mayor costo de penalización y 3) coloca la mayor cantidad de unidades en la celda con el menor costo de transporte en la columna o el renglón, con el mayor costo de penalización.