El método de Vogel, o aproximación de Vogel, es un método que permite llegar a una solución inicial factible del problema de transporte.
El procedimiento de este método es el siguiente:
Tener los valores de costos de envíos desde cada origen a cada destino tabulados (matriz de costos). En caso de que la matriz no este equilibrada (el numero de filas es diferentes del numero de columnas), agregar una fila o columna de ceros según corresponda. Esto quiere decir que según sea el caso se creara un origen o un destino ficticio.
Realizar el cálculo de las penalizaciones para cada fila y columna. Las penalizaciones se calculan restando los dos valores más pequeños de cada fila y cada columna. Las penalizaciones tienen valor absoluto.
Identificar la fila o columna con la mayor penalización (en caso de que exista un empate en las penalizaciones, se puede elegir cualquiera de las que tiene el mayor valor), y asignar la mayor cantidad de material posible a la casilla con el menor costo en esa fila o columna.
Se sombrean (eliminan) las filas o columnas que hayan sido satisfechas, reduciendo así la matriz.
Se repite el procedimiento desde en paso 2.
Una vez satisfechos todos los orígenes y destinos (sombreadas todas las filas y columnas) se puede proceder a calcular el costo del programa de envió encontrado mediante este método (cabe resaltar que la solución factible encontrada con este método no es necesariamente la optima).
VENTAJAS
Conduce rápidamente a una mejor solución. mediante los cálculos de las llamadas penalizaciones de fila y columna, los cuales representan el posible coste de penalización que se obtendría por no asignar unidades a transportar a una determinada posición.
Tiene en cuenta en el análisis la diferencia entre los menores costos de transporte, mediante los cálculos de las llamadas penalizaciones de fila y columna, los cuales representan el posible coste de penalización que se obtendría por no asignar unidades a transportar a una determinada posición.
DESVENTAJAS
No aporta ningún criterio que permita determinar si la solución obtenida por este método es la mejor (óptima) o no.
requiere mayores esfuerzos de cálculos que el Método de la esquina noroeste
APLICACIÓN
El modelo se utiliza para ayudar a la toma de decisiones en la realización de actividades como: control de inventarios, flujo de efectivo, programación de niveles de reservas en prensas entre otras. Este método es heurístico y suele producir una mejor solución inicial, produce una solución inicial óptima, o próxima al nivel óptimo.
CONNOTACION
Este método requiere mayor esfuerzo que el método de la Esquina Noreste pero conduce a una solución inicial bastante mejor, pues tiene en cuenta la in formación de los costes de transporte a través de penalizaciones de fila y columna, que representan el posible coste de penalización que se obtendría por no situar unidades a transportar en una determinada posición.
El método consiste en la realización de un algoritmo que consta de 3 pasos fundamentales y 1 más que asegura el ciclo hasta la culminación del método.
PASO 1
Identificar en cada fila y columna los dos costos más bajos o menores, posteriormente se restan entre si dichos valores y a ese resultado lo llamamos “PENALIZACION”. (El valor de la penalización siempre es positivo dado que se resta el valor mayor menos el menor) .
PASO 2
Identificar la fila o columna con la mayor penalización, es decir que de la resta realizada en el "Paso 1" se debe escoger el número mayor de manera general. En caso de haber empate, se debe escoger arbitrariamente (a juicio personal).
PASO 3
La fila o columna de mayor penalización determinada en el paso anterior, debemos de identificar la celda con el menor costo, y en esta asignar la mayor cantidad posible que cumpla con las condiciones de demanda y disponibilidad. Una vez se realiza este paso una oferta o demanda quedará satisfecha por ende reducimos la tabla sombreando las columnas o filas satisfechas (en caso de haber empate solo se tachara 1, la restante o no satisfecha quedará con oferta o demanda igual a la diferencia.) en adelante repetir el proceso desde el paso 1.
Para tener en cuenta si durante el desarrollo de este paso se presentan dos penalización iguales de grandes y nos asalta un interrogante. ¿Cuál columna o fila elegir? Debemos analizar las dos por separado; es decir primero reglón y luego columna al realizar el comparativo del costo total elegimos o gana la opción que nos ofrezca el mínimo costo.
para calcular el cotos total de distribución (z): sumamos el producto de las multiplicaciones (se multiplica las casillas que quedaron con unidades máximas asignadas por el costo unitario - valores anotados dentro de la misma).
PASO 4: DE CICLO Y EXCEPCIONES.
- Si queda sin tachar exactamente una fila o columna con cero oferta o demanda, detenerse.
Si queda sin tachar una fila o columna con oferta o demanda positiva, determine las variables básicas en la fila o columna con el método de costos mínimos, detenerse.
- Si todas las filas y columnas que no se tacharon tienen cero oferta y demanda, determine las variables básicas cero por el método del costo mínimo, detenerse.
- Si no se presenta ninguno de los casos anteriores vuelva al paso 1 hasta que las ofertas y las demandas se hayan agotado.
Método de Transporte
El problema general del transporte se refiere a la distribución de mercancía desde cualquier conjunto de centro de suministro, denominados orígenes (fuentes), hasta cualquier conjunto de centros de recepción, llamados destinos, de tal forma que se minimicen los costos totales de distribución. Cada origen tiene que distribuir ciertas unidades a los destinos y cada destino tiene cierta demanda de unidades que deben recibir de los orígenes.
Representación de una red de transporte
Como se puede observar cualquier modelo de transporte se compone de unidades de un bien a distribuir, m orígenes, n destinos, recursos en el origen, demandas en los destinos y costos de distribución por unidad. Adicionalmente, se tienen varios supuestos:
Supuesto de requerimientos: cada origen tiene un suministro fijo de unidades que se deben distribuir por completo entre los destinos.
Supuesto de costo: el costo de distribuir unidades de un origen a un destino cualquiera es directamente proporcional al número de unidades distribuidas.
Propiedad de soluciones factibles: un problema de transporte tiene soluciones factible si y sólo si la sumatoria de recursos en lo m orígenes es igual a la sumatoria de demandas en los destinos.
Propiedad de soluciones enteras: En los casos en los que tanto los recursos como las demandas toman un valor entero, todas las variables básicas (asignaciones), de cualquiera de las soluciones básicas factibles (inclusive la solución optima), asumen también valores enteros.
Debido a la particularidad del modelo de transporte la forma tabular Símplex adquiere una estructura que facilita el proceso de asignación a las variables básicas, tal se muestra a continuación:
Forma Tabular Símplex Transporte
En los renglones se ubican los orígenes indicando en la columna de la derecha los recursos (oferta disponible). En las columnas se ubican los distintos destinos indicando en el último renglón los totales demandados. En el pequeño recuadro ubicado en la margen superior derecha se indica el costo de distribuir una unidad desde el origen hasta ese destino y en la parte inferior de cada recuadro se registran las asignaciones Xi para cada variable. En los casos donde la sumatoria de los recursos y las demanda no sean las mismas, se agrega un origen o destino ficticio con la cantidad que permita cumplir la propiedad de soluciones factibles.
Después de planteado el modelo de transporte, el siguiente paso es obtener una solución básica factible, la cual se puede obtener a partir de cualquiera de los 3 criterios siguientes:
Regla de la esquina noroeste.
Método de la ruta preferente.
Método de aproximación de Vogel
Antes de explicar el procedimiento para cada uno de estos criterios de asignación para encontrar la solución inicial BF, se debe conocer el número de variables básicas, el cual se determina con la expresión: m + n - 1. En el modelo anterior 3 + 2 - 1 = 4 variables básicas.
Regla de la esquina noroeste: la primera elección X11, es decir, se inicia la asignación por la esquina noroeste de tabla. Luego se desplaza a la columna de la derecha si todavía quedan recursos en ese origen. De lo contrario se mueve al reglo debajo hasta realizar todas las asignaciones.
Método de la ruta preferente: se fundamenta en la asignación a partir del costo mínimo de distribuir una unidad. Primero se identifica este costo se realiza la asignación de recursos máxima posible y luego se identifica el siguiente costo menor realizando el mismo procedimiento hasta realizar todas las asignaciones.
Método de asignación de Vogel: para cada reglón y columna, se calcula su diferencia, que se define como la diferencia aritmética entre el costo unitario más pequeño y el costo menor que le sigue en ese renglón o columna. En el renglón o columna con la mayor diferencia, se le asigna al menor costo unitario. Los empates se pueden romper de manera arbitraria.
De estos 3 modelos para encontrar la solución inicial BF, el método de Vogel ha sido el más utilizado. Considerando que este criterio toma en cuenta los costos de distribución de forma más eficaz, ya que la diferencia representa el mínimo costo adicional que se incurre por no hacer una asignación en la celda que tiene el menor costo ya sea columna o renglón.
Posterior a esta asignación inicial se requiere un procedimiento que permita las siguientes iteraciones y se obtenga la solución óptima.
Prueba de optimalidad: un solución BF es óptima si y sólo si Cij - Uij -Vij >= 0 para todo (i,j) tal que Xij es no básica. Primeramente para todo variable básica de la solución actual se tiene que Cij - Uij -Vij = 0, por lo que se deduce Cij = Uij -Vij para todo (i,j) tal que Xij es básica. Para los fines de facilitar los diferentes de las diferente ecuaciones resultantes se asume el valor de U1 como cero.
En cada iteración se determina una variable básica entrante, una variable básica saliente y luego la nueva solución básica factible. Paso 1: la variable de entrada se determina a partir de la relación Cij - Uij -Vij, donde la variable Xij con el resultado más negativo es la que contribuye en una mejor medida a disminuir el costo total, se debe tener en cuenta que esta disminución va en proporción a la asignación resultante. Paso 2: la variable básica saliente es aquella variable básica que disminuya su valor a cero, es decir, es aquella variable de menor asignación y que participa en la reacción en cadena que se establece para compensar los cambios de asignar valor a la variable entrante que permitan satisfacer las restricciones de recursos y demandas. En este punto, se definen dos tipos variables para receptoras y donadoras, de acuerdo a la variación de signo que se produzca en el polígono que permite la transferencia desde la variable de salida a la variable entrante. Paso 3: se encuentra la nueva solución BF, sumando el valor de la variable básica saliente a las asignaciones de las celdas receptoras y se resta a las asignaciones de las celdas donadoras.
Para los fines de ejemplo, se selecciona el problema 8.2-8 ubicado en la página 325 del libro de texto. La Cost-Less Corp., surte sus cuatro (4) tiendas desde sus cuatro (4) plantas y desea minimizar los costos de distribución. A continuación se muestra la tabla con las informaciones de los costos de distribución:
Planteando este problema a través de Solver Excel (ver página relacionada en este blog) y utilizando la primera asignación con el método de la esquina noroeste, se obtiene:
Solución Básica Inicial
Solución Optima
Utilizando el programa TORA se puede visualizar cada una de las iteraciones, se asume el valor de U1 como cero en cada una de las iteraciones.
En la primera iteración, la variable de entrada es X14 y la variable de salida es X11, con una transferencia de 10 unidades, con un resultado de -800 por lo que la reducción al costo total es de 8,000.
Iteración 1
En la segunda iteración, la variable de entrada es X23 y la variable de salida es X22, con una transferencia de 0 unidades, con un resultado de -600 por lo que la reducción al costo total es de 0.
Iteración 2
En la tercera iteración, la variable de entrada es X42 y la variable de salida es X32, con una transferencia de 10 unidades, con un resultado de -600 por lo que la reducción al costo total es de 6,000.
Iteración 3
En la cuarta iteración, la variable de entrada es X42 y la variable de salida es X32, con una transferencia de 0 unidades, con un resultado de -400 por lo que la reducción al costo total es de 0.
Iteración 4
La solución óptima presenta un costo total de 11,000 y la distribución de las diferentes plantas hacia las diferentes tiendas es como sigue:
Un modelo de Programación Lineal (PL) considera que las variables de decisión tienen un comportamiento lineal, tanto en la función objetivo como restricciones del problema. En este sentido, la Programación Lineal es una de las herramientas más utilizadas en la Investigación Operativa debido a que por su naturaleza se facilitan los cálculos y en general permite una buena aproximación de la realidad.
Los Modelos Matemáticos se dividen básicamente en Modelos Deterministas (MD) o Modelos Estocásticos (ME). En el primer caso (MD) se considera que los parámetros asociados al modelo son conocidos con certeza absoluta, a diferencia de los Modelos Estocásticos, donde la totalidad o un subconjunto de los parámetros tienen una distribución de probabilidad asociada. Los cursos introductorios a la Investigación Operativa generalmente se enfocan sólo en Modelos Deterministas.
Las aplicaciones de los modelos de Programación Lineal abarcan diversas áreas de la Ingeniería. A continuación un breve compendio de alguna de sus aplicaciones y referencias de interés para el lector:
1. Problema de Transporte: (Referencia: Hitchcock, 1941; Kantorovich, 1942; Koopmans 1947).
El problema consiste en decidir cuántas unidades trasladar desde ciertos puntos de origen (platas, ciudades, etc) a ciertos puntos de destino (centros de distribución, ciudades, etc) de modo de minimizar los costos de transporte, dada la oferta y demanda en dichos puntos. Se suponen conocidos los costos unitarios de transporte, los requerimientos de demanda y la oferta disponible.
Por ejemplo, suponga que una empresa posee dos plantas que elaboran un determinado producto en cantidades de 250 y 400 unidades diarias, respectivamente. Dichas unidades deben ser trasladadas a tres centros de distribución con demandas diarias de 200, 200 y 250 unidades, respectivamente. Los costos de transporte (en $/unidad) son:
Se requiere formular un modelo de Programación Lineal que permita satisfacer los requerimientos de demanda al mínimo costo.
Variables de Decisión:
Xij: Unidades transportadas desde la planta i (i=1, 2) hasta el centro de distribución j (j=1, 2, 3)
Función Objetivo: Minimizar el costo de transporte entre las plantas y los centros de distribución dado por:
Satisfacer los requerimientos de Demanda de los Centros de Distribución:
X11+ X21 = 200
X12 + X22 = 200
X13 + X23 = 250
Sujeto a la Oferta o Capacidad de Producción de las Plantas::
X11+ X12 + X13 = 250
X21 + X22+ X23 = 400
No Negatividad:
Xij>= 0 i=1,2 y j=1,2,3
El siguiente diagrama permite una visualización de la situación anterior:
A continuación una descripción de la implementación computacional y resolución del problema anterior utilizando el complemento Solver de Microsoft Excel:
1. Abrir una Planilla de Cálculo de Excel. Asegúrese de tener instalado el complemento Solver. Luego construya una planilla como la de la imagen de referencia. Se han marcado con amarillo las celdas cambiantes (variables de decisión) y con color azul la celda de la función objetivo.
Notar que algunas celdas en la imagen anterior consideran fórmulas:
F7=SUMA(C7:E7)
F8=SUMA(C7:E7)
C9=SUMA(C7:C8)
D9=SUMA(D7:D8)
E9=SUMA(E7:E8)
2. Ingrese la función objetivo, celdas cambiantes y restricciones en la ventana de Parámetros de Solver. Seleccione también la opción Convertir variables sin restricciones en no negativas. Si utiliza la mismas celdas de la imagen anterior, usted debería obtener lo siguiente:
3. Seleccione Resolver. Obtendrá la solución al problema y podrá requerir los Informes de Solver. Finalmente presione Aceptar para obtener el o los informes de interés.
Finalmente, se obtienen los informes de confiabilidad (o sensibilidad) los cuales entregan información relevante en cuanto a los precios sombra asociados a las restricciones, intervalos de variación de garantizan la validez del precio sombra, intervalo de variación para los coeficientes de la función objetivo, etc.
Programación Lineal
Cuando se habla de programación lineal (PL) se refiere a varias técnicas matemáticas empleadas para asignar, de forma óptima, los recursos limitados a distintas demandas, tareas, operaciones o productos que compiten entre ellos, es decir, la programación de actividades para obtener un resultado óptimo. La programación lineal utiliza un modelo matemático para describir y formular el problema; y el aspecto de lineal se refiere a que todas la funciones matemáticas del modelo deben ser funciones lineales (Ecuaciones o Inecuaciones).
Aplicaciones típicas:
Planeación de operaciones y ventas para encontrar el programa de producción que tenga el costo mínimo.
Análisis de la productividad en la producción o servicios, considerar el grado de eficiencia con el cual los establecimientos de servicios y de manufactura están utilizando sus recursos en comparación con la unidad que tiene mayor desempeño.
Planeación de los productos, encontrar la mezcla óptima de productos, considerando que varios productos requieren diferentes recursos y tienen distintos costos.
Rutas de los productos se refiere a encontrar el camino óptimo para fabricar un producto que debe ser procesado en secuencia.
Programación de vehículos (método de transporte), encontrar la ruta óptima para utilizar los recursos de transporte que involucren el movimiento de productos o materiales de varios puntos llamados origen hacia otros puntos llamados destinos.
Control de procesos, minimizar el volumen de desperdicio de material generado en los procesos de producción, tales como cortes de acero, pieles o telas.
Control de inventario, encontrar la combinación óptima de productos a mantener en existencia dentro de una red de almacenes para garantizar el abastecimiento de las demandas de las líneas de producción.
Otras aplicaciones que se pueden mencionar están la programación de la distribución de embarques, los estudios para ubicar una planta entre distintas alternativas y los programas de manejo de materiales con un costo mínimo.
Construcción de un modelo de programación lineal
Cualquier modelo de PL se compone de tres elementos básicos:
Variables de decisión, que se trata de determinar.
Función objetivo (meta), que se busca optimizar ya sea maximizar (beneficios) o minimizar (costos).
Restricciones que se deben satisfacer.
Para fines didácticos, se visualizan estos elementos básicos a través de un ejemplo de mezcla de productos. La empresa FICTICIA, S.A. elabora dos tipos de productos Alpha y Beta, los cuales requieren para su elaboración de dos materias primas (P y Q). Alpha utiliza 6 toneladas de P y requiere 1 tonelada de Q, mientras que Beta usa 4 toneladas de P y 2 toneladas de Q. La empresa disponone diariamente de 24 toneladas de P y de 6 toneladas de Q. El equipo de IO ha determinado que la contribución de Alpha es 5,000 y Beta aporta 4,000 dólares de beneficio y según una encuesta de mercado proporcionada por el equipo de marketing el producto Beta tiene una demanda máxima de 2 toneladas. Así mismo, se determinó que la demanda diaria de Beta no puede exceder a la demanda de Alpha por más de una (1) tonelada.
La variables de decisión de este problema están definidas por: X1 = Producto Alpha X2 = Producto Beta
La función objetivo se define de la siguiente manera: Maximizar (Z) = 5 X1 + 4 X2 (en miles de dólares)
Cualquier par de valores de X1, X2 que satisfaga todas las restricciones anteriormente expresadas, se considera una solución factible del modelo. Tal es el caso de la solución factible dada por X1=3 y X2=1 con un Z= 5x3 + 4x1 = 19 (miles de dólares). Posteriormente se mostrará como llegar a la solución óptima a través del método gráfico y del matemático.
Método Gráfico:
Este procedimiento plantea la construcción de una gráfica en un plano (2 ejes - 2 variables de decisión). Primeramente, se formulan las restricciones de manera matemática (paso ya cubierto). Segundo, se trazan todas las restricciones formuladas en el modelo de PL (se recomienda definir los interceptos de cada restricción a los ejes y luego trazar la recta que se define). Nota: para el intercepto en el eje X1 se encuentra al llevar X2 a cero y para el intercepto en X2 hacemos que el valor de X1 sea cero. Por ejemplo, para la restricción (1) los interceptos son X1 = 24/6 = 4 y para X2 = 24/4 = 6.
Tercero, se define el espacio de solución factible, el cual está formado por la región de puntos que cumplen con todas las restricciones. Se deben marcar los puntos extremos del espacio de solución, es decir, los puntos de intersección de dos o más rectas y que pertenecen al espacio de solución delimitado.
Por último, se traza la recta definida por la ecuación objetivo (se recomienda utilizar la pendiente o se puede utilizar dos Z convenientes para simular el comportamiento de esta recta), luego se extiende esta recta hasta el punto más alejado en la región factible, este punto es el que determina la solución óptima del modelo. Para el ejemplo formulado de la empresa FICTICIA, S.A. se encuentra que la solución óptima se define por X1 = 3 producto Alpha y X2 = 1.5 producto Beta con un Z = 21 (miles). Ver gráfica a continuación:
En resumen, el enfoque gráfico consiste en la secuencia de pasos siguientes:
Plantear el problema de programación en términos matemáticos.
Trazar las ecuaciones (inecuaciones) formuladas para las restricciones.
Determinar el área de factibilidad (espacio de solución).
Trazar la función objetivo.
Encontrar el punto óptimo.
Método Matemático:
Como se pudo observar, la solución optima de cualquier modelo de programación lineal se encuentra en uno de los puntos o vértices que conforman el polígono del espacio solución, los cuales se forman por las intersecciones de las restricciones del modelo. El enfoque matemático aprovecha esa situación, y emplea el álgebra para encontrar esos puntos de intersección a través de la solución de cada sistema de ecuaciones (inecuaciones) que se forma con cada par de restricciones y luego evaluando esos puntos en la función objetivo se determina la solución óptima, ya sea el mayor valor para los casos de maximización, como el menor valor para los casos de minimización.
La conjugación del método gráfico con el matemático es bastante utilizada. En el sentido, que el método gráfico permite simplificar la cantidad de pares de sistemas de ecuaciones que se deben resolver, reduciendo este número a un sólo sistema de ecuaciones, el cual se puede resolver por cualquier método matemático de su conveniencia. Se recomienda el enfoque de reducción o el de sustitución por su facilidad de encontrar la solución al sistema. En el ejemplo prototipo, el sistema de ecuaciones lo conforma las restricciones (1) y (2), cuya solución arroja el par ordenado que se constituye en la solución óptima. Intenta verificarlo!
Existen diversas aplicaciones y/o paquetes de software en el mercado que se pueden descargar de manera gratuita. Se les recomienda a los estudiantes para la solución de problemas de programación lineal buscar por alguno de estos:
LINDO / LINGO
MPL / CPLEX
TORA
Excel Solver
ejemplos de método simplex
software
1re ejercicio
2do ejercicio
jueves, 13 de septiembre de 2018
EJERCICIO MÉTODO SIMPLEX
martes, 11 de septiembre de 2018
METODO SIMPLEX
Para comprender el funcionamiento de este tema basta con recordar el método gráfico, el cual se iban buscando esquinas del grafico hasta llegar la solución óptima. El método simplex se basa en ir buscando esquina por esquina a fin de encontrar el punto esquina optimo, pero al contrario del método grafico este se logra mediante un proceso algebraico, no obstante es necesario convertir cada restricción de desigualdades a igualdades con el objetivo de manipular estas ecuaciones de forma sistemática.
Conversión de desigualdades a igualdades:
Sean las desigualdades:
Para la primera desigualdad, representa un valor más pequeño o igual que 8, por lo tanto si quisiéramos convertir esta desigualdad en igualdad deberíamos sumar un valor de holgura (denotada usualmente como ) que represente el número necesario para llegar a 8, de esta manera si tomara un valor de 3 y un valor de 2 el valor de holgura será 3. La primera restricción se transforma como sigue:
Para la segunda restricción, representa un valor más grande o igual a 5 por lo tanto se debe buscar un valor de holgura que le reste a la desigualdad y llegue al valor de 5, por ejemplo si vale 4 y tiene un valor de 6 el número de holgura será 3 de manera que cuando restemos el valor de holgura llegue al valor de 5. La segunda ecuación queda como sigue:
Siguiendo con nuestro tema, tomaremos un ejemplo en particular e iremos describiendo paso a paso la solución del problema.
Supondremos el siguiente caso:
Maximizar:
Sujeto a:
Como se vio anteriormente las restricciones tomaran el valor de:
Y la función objetivo tomara la forma:
Si reordenamos en una tabla las restricciones y la función objetivo tomaría la siguiente forma:
Se denominara las posibles variables de entrada a todos los valores de la fila z como sigue:
Cuando se trata de maximizar se debe seleccionar el valor más negativo, en este caso será -2 y posteriormente se debe seleccionar la respectiva columna (columna pivote):
Para la última tabla se le ha agregado una columna (razón, denotada a menudo como ) este indica la razón entre el número de la columna “resultado” y el posterior numero de la columna pivote (Obviando la columna z), en forma más grafica el procedimiento para hallar la razón se hace del siguiente modo:
El segundo paso es hallar la fila pivote, y este se hace seleccionando el valor más pequeño positivo en la columna “razón” (variable de salida), en este caso será el 5, y posteriormente seleccionando toda la fila:
Normalmente se dividiría toda la fila pivote por el número sombreado en rojo, pero esta vez no es necesario, puesto que tiene valor 1, y por ende cada división resultaría el mismo número.
El tercer paso se basara en transformar toda la columna pivote en cero, a excepción del numero tocado por la fila pivote. Para este procedimiento se usa el método gauss, el cual se detallara a continuación:
Para transformar la columna R1 en forma adecuada se usa la siguiente ecuación:
Esto indica que cada cuadro de la columna deberá ser restado por el respectivo valor de , así cuando se transforme el número de la columna pivote este tome el valor de cero:
Igualmente el valor de Z será transformado con la ecuación:
Para una mayor comprensión hacia el lector se detallara los procesos para la ecuación anterior:
En general la columna nueva será el valor de la columna antigua menos el número pivote de la columna multiplicado por el número de la fila pivote.
La grafica final queda como sigue:
Para este sistema ya no es posible encontrar una solución más óptima, esto es porque los valores de y en la fila z son cero, por lo tanto el valor de z será 10, x1 será 0 (esto es porque la columna x no puede ser transformada en valores de cero) y x2 será igual a 5.
Transformar las desigualdades
Es posible a veces manipular las desigualdades de tal manera que se transformen en desigualdades “<=” por ejemplo se tienen la ecuación:
Es posible transformar esta desigualdad multiplicando cada miembro por -1:
Posteriormente es posible transformar un problema de minimización a maximización multiplicando cada variable por -1, por ejemplo se tiene la función objetivo:
Es posible transformar esta función objetivo de la siguiente forma:
Es muy usual hacer este tipo de procedimientos cuando se tiene mucha más experiencia haciéndolo de la forma maximizar con restricciones de desigualdad <=.
Método de la gran M
Supongamos el siguiente problema:
Minimizar:
S.A:
Si reordenamos las restricciones de la forma común, tomaría la forma:
Para el reglón 1, si se multiplicara por -1 la variable de holgura podría tomar valores negativos, y violaría la restricción . Es por eso que para este tipo de problema se le asigna una variable artificial (a), de tal manera que su valor sea lo suficientemente alto para no convertir s1 en un número negativo.
De una forma similar pasara con el reglón 3, si se multiplicara esta por -1 tanto x como y podrían tomar valores negativo, y por consiguiente se le debe agregar una variable artificial
Las restricciones quedaran como sigue:
Desafortunadamente no hay garantía para que las últimas restricciones tengan los mismos resultados que se piden en el enunciado. Puede existir la posibilidad de que se consiga algún valor a en el resultado final. Para solucionar este problema se hace lo siguiente:
La M agregado representan valores extremadamente grandes por lo tanto si se trata de minimización los valores serán iguales a cero, y el resultado final serán iguales a los que se piden en el problema primero
Reordenando la función objetivo quedará como sigue:
En tabla la función objetivo y las restricciones tomara la siguiente forma:
Antes de seguir nuestro estudio miraremos un último problema:
Si la columna z tiene un resultado final de 0 las variables z, x, y tomarían valores de cero también, por consiguiente en el reglón R1 por ejemplo los valores de a1+a2 seria 4, por ende toda la tabla seria inconsistente. Para solucionar este problema se transforma cada una de las M en cero utilizando el método gauss, la formula a utilizar será:
La tabla modificada será:
En este punto ya es posible proceder con el método gauss ordinario, pero tratándose de minimización se buscara el valor más positivo en la columna Z, el cual resulta 3M-2
De igual manera se selecciona la variable de salida como el valor más pequeño de la razón de la fila “total” con la fila “x” (en este caso seria 1), posteriormente la columna pivote será las casillas consecutivas a este. La tabla 6 muestra la columna y fila pivote sombreadas en azul.
El ejercicio continúa normalmente como se mostró en el primer ejemplo, recordando que:
Ha de tener en cuenta que este es un ejercicio de minimización por ende la variable de entrada será el de valor más positivo, pero a su vez solo se deben tener en cuenta las variables del problema y no las holguras o los valores artificiales.
Se llega al óptimo cuando los valores de zx y zy son cero o mayores a este.
El resultado final será:
Como ayuda al lector se ha especificado que se debe hacer con los diferentes criterios de decisión en la siguiente tabla:
Método simplex paso a paso – Programación lineal
El método simplex es un algoritmo creado por George Dantzig que permite la solución de muchos problemas de programación lineal.
Muy popular, es bien aceptado en las zonas donde las diferentes necesidades y limitaciones influencia en un valor que necesita ser aumentado o disminuido al máximo.
El algoritmo puede ser implementado de varias maneras diferentes, pero el principio es básicamente el mismo. A continuación se muestra el enfoque utilizado por [Papadmitriou].
Al final del texto se le puede asignar una implementación de lenguaje de programación en Python está disponible en Github.
El método Simplex permite encontrar los valores óptimos en situaciones donde deben respetarse muchos aspectos. Ante un problema, las desigualdades se establecen limitaciones que representan a las variables. A partir de ahí, se prueba posibilidades con el fin de optimizar el resultado tan pronto como sea posible.
El uso más común de la Simplex es maximizar el resultado, es decir, encontrar el valor más grande posible para un total. Los problemas típicos de resolver con Simplex están buscando cantidades óptimas de productos para ser vendidos, con restricciones en el almacenamiento y la producción de los mismos.
La idea es para aislar una función como el objetivo. Las cantidades que desee optimizar están representados por las variables aquí llamados , y la función objetivo se presenta como siendo los coeficientes de las variables. Estos muestran la proporcionalidad entre ellos.
Por lo general son números racionales obtenidos en el problema que desea resolver.
Las restricciones se presentan como las desigualdades. Peculiaridades indican el hecho de que una empresa sólo es capaz de almacenar un determinado peso o volumen de los productos, por ejemplo.
Entre las posibilidades de los valores de las variables que satisfagan las limitaciones, el algoritmo debe encontrar a los que dan la función objetivo el total más alto posible.
Operación
Relacionado con la programación lineal, se trabaja con funciones de 1º grado, la idea del algoritmo es bastante simple. Inicialmente, se asigna el valor cero a variables, sería muy lejos de la solución.
A continuación, se incrementa gradualmente a la variable que tiene la interferencia más positivo en los resultados de la función objetivo, es decir, el que tiene el coeficiente más alto. Esto se llama “la variable activa” y tiene una gran importancia inicial, ya que es el más “rentable” ellos, es decir, que nos lleva más cerca de optimización.
A medida que este valor aumenta, el algoritmo comprueba todas las restricciones, hasta que uno de ellos no se cumple. Esta restricción se llama la “restricción activa”. En este momento, se sabe la variable activa máxima.
El procedimiento se desplaza a la siguiente variable que nos trae buena solución, siempre teniendo en cuenta la cantidad máxima que el primero podría lograr. Cada uno de estos cambios, el Simplex convierte todos los coeficientes (incluyendo la función objetivo) de acuerdo con los límites que se encuentran en las sucesivas restricciones activas.
El procedimiento se repite hasta que el incremento de las variables se presente como una disminución en total alcanzado. Esto se identifica con el signo negativo delante de los coeficientes de la función objetivo. Al final, los valores buscados son conocidos por medio de un sistema de ecuaciones, los derivados de la problema original.
Minimización
Aunque los ejemplos son casi siempre maximizando el Simplex también comprende los casos en que desea encontrar el valor más pequeño posible. Los costos y gastos son algunos de los resultados buscados comúnmente en estas situaciones.
Para ello, el algoritmo puede ser perfectamente adaptado con el fin de resolver un problema en el que desea encontrar un pequeño resultado. Sin embargo, lo que se hace a menudo es simplemente invertir todas las relaciones, multiplicando los coeficientes por -1 y haciendo que el problema original es visto como un simple maximización.
Cuadro
Ya implementada en varios idiomas diferentes, el Simplex también se puede aplicar de forma manual. El método, conocido como Tableau, es poner toda la información organizada de forma correcta en un marco, haciendo exactamente lo que el software lo haría. En muchos lugares, el Simplex se enseña en este camino, por lo que la gente tiene un buen campo de la técnica de optimización.
Matrices
El algoritmo de procesamiento puede ser realizado por un producto de matriz. Una vez que los coeficientes están correctamente dispuestos en filas y columnas, es suficiente que este se multiplica por una versión modificada de la “identidad Matrix”, de tamaño igual al número de variables.
La versión modificada tiene una línea formada por los coeficientes simétricos de la línea relativa a la limitación violado dividido por el coeficiente de la variable violada. Esta línea se corresponderá, en orden, a la variable que violó la restricción.
Este producto hace que las matrices siempre tiene una lista de coeficientes ya modificados de acuerdo con las restricciones y los mejores valores posibles para las variables hasta la fecha. El proceso se repite hasta que encuentre el resultado óptimo, es decir, cuando ya no es posible mejorar el total sin violar las restricciones.
En el espacio de dimensión N
Si se considera a la óptica geométrica, el Simplex trabajando en la construcción de un politopo con un número de dimensiones igual al número de variables del problema. La solución óptima será siempre un conjunto de coordenadas de los vértices del politopo. Cada incrementar una variable, es como el Simplex percorresse uno de los bordes, siempre en busca de la punta perfecta.
Complejidad
Formalmente, se cree que la complejidad del algoritmo Simplex ser exponencial. Muestra que en una aplicación ingenua, cada iteración en busca de la mejor solución es, en principio, la complejidad en términos de variables y restricciones.
Sin embargo, utilizando el enfoque de procesamiento lineal en cada iteración de la totalidad del sistema se enciende de manera que el vértice anterior es el nuevo origen de la complejidad por iteración se convierte.
Por supuesto, la pregunta es ¿cuántas iteraciones son necesarias para alcanzar los criterios de parada. Un límite superior para este número es, el extremo que conduce a la complejidad exponencial en a.
Afortunadamente, tanto Papadimitriou como informó de que, en la práctica, pocos problemas tomando esta complejidad y, por lo tanto, el algoritmo Simplex es muy utilizado.
Con un algoritmo de Tableau
Estos procedimientos son válidos para problemas de maximización:
Introduzca las variables de holgura, uno para cada desigualdad;
Establecer un marco para los cálculos mediante la colocación de los coeficientes de todas las variables con sus signos y, en la última línea, incluyen los coeficientes de la función objetivo transformado;
Establecer una solución básica inicial, por lo general mediante la asignación de valor cero a las variables originales y la búsqueda de valores positivos para las variables de holgura;
Como siguiente variable para entrar en la base, elegir no variable básica que proporciona, en la última línea, la mayor contribución al aumento de la función objetivo (es decir, tiene el valor más negativo). Si todas las variables que están fuera de la base tienen cero o positivos coeficientes en esta línea, la solución actual es óptima. Si cualquiera de estas variables tienen coeficiente cero, esto significa que se puede insertar en la base sin incrementar el valor de la función objetivo. Esto significa que tenemos una gran solución con el mismo valor de la función objetivo.
Para elegir la variable que debe salir de la base, debe realizar lo siguiente:
Dividir los elementos de la última columna de los elementos positivos correspondientes de la columna de la variable que va a entrar en la base. Si no hay elemento positivo en esta columna, el proceso debe detenerse, ya que la solución sería ilimitado.
La proporción menor indica la ecuación cuya variable básica respectiva que ser anulada, por lo que es variable no básica.
El uso de las operaciones válidas con filas de la matriz, la transformación de la mesa de cálculos con el fin de encontrar una nueva solución alcalina. La columna de la nueva variable básica debe convertirse en una identidad vectorial, donde se anularon los elementos 1 aparece en la línea correspondiente a la variable.
Vuelva al paso 4 para iniciar otra iteración.
Programación lineal
En las matemáticas , un problema de programación lineal (LP) son problemas de optimización en el que la función objetivo y las restricciones son lineales.
Programación lineal es un campo importante de la optimización por varias razones. Muchos de los problemas prácticos en la investigación de operaciones se pueden expresar como problemas de programación lineal.
Ciertos casos especiales de programación lineal, tales como problemas de flujo de red y problemas de flujo multiservicio se consideran lo suficientemente importante que si una gran cantidad de investigación se ha generado en los algoritmos especializados para sus soluciones. Varios algoritmos para otros tipos de trabajo resolver problemas de optimización problemas de PL como sub-problemas.
Históricamente, las ideas de programación lineal han inspirado a muchos de los conceptos centrales de la teoría de optimización, tales como la dualidad, la descomposición , y la importancia de la convexidad y sus generalizaciones.
Ejemplo
Aquí está un ejemplo de un problema de programación lineal. Supongamos que un agricultor tiene un pedazo de tierra que decir, el km 2 , para ser sembrada con trigo o cebada, o una combinación de ambos.
El agricultor haya una cantidad limitada de fertilizantes F permitido y insecticida P permitida para ser utilizados, cada uno que se requiera en diferentes cantidades por unidad de superficie para el trigo ( F 1 , P 1 ) y cebada ( F 2 , P 2 ).
Sea S 1 precio de venta de trigo, y S 2 de la cebada. Si llamamos a la superficie sembrada con trigo y cebada x 1 y x 2 , respectivamente, a continuación, el número óptimo de km 2 de siembra con trigo vs. La cebada se puede expresar como un problema de programación lineal:
maximizar (Maximizar el beneficio – esta es la “función objetivo”)
sujeto a (Límite de la superficie total)
(Límite de fertilizantes)
(Límite de insecticida)
(No se puede sembrar un área negativa)
Teoría
Geométricamente, las restricciones lineales definen un poliedro convexo , que se llama el conjunto de puntos factibles . Dado que la función objetivo también es lineal, es un fantástico lugar automáticamente un óptimo global.
Para ser función objetivo lineal también implica que una solución óptima sólo puede ocurrir en un punto del conjunto de puntos factibles frontera.
Hay dos situaciones en las que una solución óptima no se puede encontrar. En primer lugar, si las restricciones se contradicen entre sí (por ejemplo, x ≥ 2 y x ≤ 1), entonces la región factible está vacía y no puede haber ninguna solución óptima, ya que no puede haber solución. En este caso, la PL se dice no factible .
Alternativamente, el poliedro puede ser ilimitada en la dirección de la función objetivo (por ejemplo, maximizar x 1 + 3 x 2 sujetos a x 1 ≥ 0, x 2 ≥ 0, x 1 + x 2 ≥ 10), en este caso no existe una solución óptima desde arbitrariamente grandes soluciones de la función objetivo puede ser construido, y el problema se dice a ilimitado .
Aparte de estas dos condiciones patológicas (que a menudo se eliminan por las limitaciones de recursos inherentes en el problema que se modela como arriba), el óptimo se alcanza siempre un vértice poliedro.
Sin embargo, la óptima no siempre es único: es posible tener un conjunto de soluciones óptimas que cubren un borde o cara del poliedro, o incluso todo el poliedro (Esta última situación puede ocurrir si la función objetivo es uniformemente igual a una constante).
Algoritmos
El algoritmo simplex resuelve problemas de PL por la construcción de una solución admisible en vértice poliedro, y entonces corre a través de los vértices del poliedro que tienen valores sucesivamente más altos de la función objetivo para encontrar el máximo.
Aunque este algoritmo es muy eficiente en la práctica, y está garantizado para encontrar un óptimo global si ciertas condiciones para evitar los ciclos se toman, es débil en el peor de los casos: Usted puede construir un problema de programación lineal práctico para los que el método simplex realiza un número exponencial de pasos en relación con el tamaño de la emisión.
De hecho, desde hace algún tiempo no se sabía si los problemas de programación lineal fueron NP-completo o ha tenido solución en tiempo polinómico.
El primer algoritmo de programación lineal en el tiempo polinomio en el peor caso fue propuesto por Leonid Khachiyan en 1979 . Se basaba en optimización no lineal de Naum Shor, que es una generalización del método de elipsoide Arkadi Nemirovski, uno de los ganadores del Premio de Teoría John von Neumann en 2003 , y D. Yudin.
Sin embargo, el rendimiento práctico es decepcionante algoritmo Khachiyan: en general, el método simplex es más eficiente. Su importancia es que fomenta la investigación de métodos de punto interior.A diferencia de algoritmo simplex, que sólo avanza a lo largo puntos en el límite de la región factible, los métodos de punto interior pueden moverse por el interior de la región factible.
En 1984 , Narendra Karmarkar propuso su método proyectivo, que se convirtió en el primer algoritmo para un buen desempeño en la teoría y en la práctica: el peor de los casos es la complejidad polinómica y los problemas prácticos de la experiencia muestra que es razonablemente eficiente en comparación con el algoritmo simplex.
Dado que el método Karmarkar, se han propuesto y analizado muchos otros métodos de punto interior. Un método popular es el método predictor-corrector de Mehrotra, cuya actuación tiene un buen rendimiento en la práctica, aunque se sabe poco acerca de ello en teoría.
La última opinión entre los estudiosos es que la eficiencia de las buenas implementaciones de los métodos basados en simplex y los puntos interiores son similares a la aplicación rutinaria de la programación lineal.
La solución de programación lineal se están utilizando diversos problemas de optimización generalizados en la industria, tales como la optimización del flujo de transporte, que puede transformarse en problemas de programación lineal sin demasiadas dificultades.
Variables enteras
Si ninguna de las variables de problemas pertenecen al conjunto de los números enteros, tenemos una programación lineal subclase llamada Programación Entera (IP) o la programación lineal entera. A diferencia de la PL que se puede encontrar la solución óptima en un tiempo razonable, muchos problemas de programación entera se consideran NP-duro.
Si las variables son binarias, es decir, teniendo sólo los valores 0 (cero) o 1, tienen un caso especial de PI, que también puede ser clasificado como NP-duro.
Cuando sólo algunas de las variables son números enteros y otra continua, tenemos la “Programación Entera Mixta” (PIM).
Sin embargo, hay algunas clases de problemas que se pueden resolver perfectamente en tiempo polinómico, tienen su propia estructura de la matriz llama matrices totalmente unimodulares.
Si la estructura del problema permiten también es posible aplicar un algoritmo de generación de columnas
