Source: http://docplayer.es/21843289-Definicion-de-problemas-de-programacion-lineal-metodo-grafico-metodo-del-simplex-metodo-de-las-dos-fases-analisis-de-sensibilidad-y-problema-dual.html
Timestamp: 2018-12-15 10:36:12+00:00

Document:
Definición de problemas de programación lineal. Método gráfico. Método del SIMPLEX. Método de las dos fases. Análisis de sensibilidad y problema dual - PDF
Definición de problemas de programación lineal. Método gráfico. Método del SIMPLEX. Método de las dos fases. Análisis de sensibilidad y problema dual
Download "Definición de problemas de programación lineal. Método gráfico. Método del SIMPLEX. Método de las dos fases. Análisis de sensibilidad y problema dual"
Alberto Piñeiro Olivares
1 7. Programación lineal y SIMPLEX Definición de problemas de programación lineal. Método gráfico. Método del SIMPLEX. Método de las dos fases. Análisis de sensibilidad y problema dual Programación Lineal Técnica de modelado matemático diseñada para optimizar el empleo de recursos limitados Base para el desarrollo de algoritmos más compleos de modelos de IO, incluyendo la programación entera, no lineal y estocástica.
2 EJEMPLO La empresa Titan S.L. Se dedica a fabricar dos tipos de pinturas, P1 y P2, a partir de dos materiales básicos M1 y M2. Toneladas P1 Toneladas P2 Disponibilidad Máxima diaria (Tm) M M Utilidad por Tm (miles de Euros) 5 4 Una encuesta de mercado indica que la demanda diaria de P2 no puede ser mayor que 1 Tm más que de P1. Además, la demanda máxima diaria de P2 es de 2 Tm. Se desea determinar la mezcla óptima de P1 y P2 que maximice la utilidad diaria total. Planteamiento del problema x 1 = Tm de P1 a fabricar a diario x 2 = Tm de P2 a fabricar a diario Obetivo: maximizar z=5x 1 +4x 2 Restricciones: 6x 1 +4x 2 24 x 1 +2x 2 6 x 2 x 1 +1 x 2 2 x 1,x 2
3 Modelo de PL Elementos básicos (para plantear el problema): Variables de decisión Función obetivo (lineal) Restricciones (lineales) Solución factible: cualquier solución que satisface todas las restricciones Solución factible óptima: solución factible que produce el valor óptimo en la función obetivo Método Gráfico Válido para modelos de dos variables Pasos básicos: Determinación del espacio de las soluciones factibles Determinación de la solución óptima de entre todos los puntos en el espacio de solución factible: Dibuar una recta con valor función obetivo constante (contorno) Mover dicha recta de forma paralela en la dirección en la que se optimiza la función obetivo El espacio de las soluciones factibles es un conunto convexo. Si un problema de PL tiene solución óptima, ésta es un punto extremo o esquina del espacio de las soluciones factibles.
4 Modelo de PL Propiedades intrínsecas en la linealidad: Proporcionalidad: la contribución de cada variable de decisión en la función obetivo y en las restricciones es directamente proporcional al valor de la variable Aditividad: la contribución total de todas las variables en la función obetivo y en las restricciones es la suma de la contribución individual de cada variable. Solución de un problema PL Cuatro casos: Solución óptima única Varias soluciones óptimas: todo un segmento de soluciones La región de soluciones factibles está vacía La región de soluciones factibles no está acotada
5 Análisis de sensibilidad Permite determinar los cambios en la solución óptima que resultan de hacer cambios en los parámetros del modelo: conducta dinámica de la solución óptima. Analiza cambios discretos en los parámetros del modelo. Análisis de sensibilidad Si la base actual permanece óptima después de cambiar el coeficiente de una variable no básica en la función obetivo, los valores de las variables de decisión y el valor obetivo óptimo no cambian. Si cambia el coeficiente de una variable básica, los valores de las variables de decisión pueden permanecer constantes, pero el valor obetivo óptimo puede cambiar Si cambia el lado derecho de una restricción los valores de las variables de decisión y de la función obetivo pueden cambiar
6 Valor por unidad de un recurso Modelo PL= modelo de entrada y salida en el que entran los recursos limitados y sale el valor de la solución obetivo Recursos Modelo PL Valor obetivo Valor por unidad de recurso (precio dual, precio sombra)= tasa de cambio en el valor de la función obetivo debido a cambios en la cantidad disponible de recursos, es decir, lo que aumenta (o disminuye) el valor obetivo al aumentar (o disminuir) en 1 la cantidad de recurso. Método del SIMPLEX Método algebraico para la determinación de la solución factible óptima de un problema de PL con cualquier número de variables de decisión. Requiere que el problema esté en forma estándar: todas las restricciones deben ser de igualdad y todas las variables no negativas La idea básica es: partiendo de un vértice de la región factible buscar otro adyacente en el que meore el valor de la función obetivo.
7 PL estándar en forma matricial Maximizar o minimizar z= CX Sueta a AX=b X donde b X = T ( x, x, K, x ), C= ( c, c, K, c ) 1 a11 a21 A= M am 1 2 a a a M m2 n K a1 n b1 K a 2n = b2, b O M M K amn b m 1 2 n Forma estándar Variable de holgura: En las restricciones ( ) el lado derecho representa el límite sobre la disponibilidad de un recurso y el lado izquierdo el uso de ese recurso limitado. Una holgura representa la cantidad del recurso que no se utiliza. Variable de superávit: Las restricciones ( ) determinan requerimientos mínimos de especificaciones. Un superávit representa el exceso del lado izquierdo sobre el requerimiento mínimo. Variable no restringida: El método del símplex exige trabaar con variables no negativas. Las variables no restringidas pueden expresarse como la diferencia de dos variables no negativas.
8 Conversión a forma estándar Conversión de desigualdades a igualdades: ( ): se introduce una variable de holgura E: x 1 +x 2 3 x 1 +x 2 +s 1 =3, s 1 ( ): se introduce una variable de superavit E: x 1 +3x 2 7 x 1 +3x 2 s 2 =7, s 2 Convesión de una variable no restringida a variables no negativas: x= x + -x -, x +, x - Soluciones básicas La forma estándar de PL incluye m ecuaciones y n variables (m<n). A n-m variables se les asigna el valor Las m variables restantes se determinan resolviendo las m ecuaciones. Si se obtiene una solución única a las m variables asociadas se les llama variables básicas y a las n-m restantes variables no básicas: solución básica. Si todas las variables de la solución básica toman valores no negativos la solución básica es factible, si no, es no factible. El número máximo de posibles soluciones básicas para m ecuaciones con n incógnitas es: n n! = m m!( n m)!
9 Representación vectorial de una base El sistema de ecuaciones AX=b con m ecuaciones y n incógnitas se puede expresar en forma vectorial como n = 1 P x = b donde P representa el vector de la columna de A Un subconunto de m vectores forman una base, B, si y sólo si son linealmente independientes (det(b), B no singular) Soluciones básicas AX= b, sistema de m ecuaciones y n incógnitas X B un subconunto de m elementos de X B matriz mxm que incluye los elementos de A asociados a X B Al asignarles el valor a los n-m elementos restantes de X el sistema se reduce a BX B = b Si B es una base obtenemos solución única: X B =B -1 b solución básica de AX=b Si B -1 b>= X B es factible Si X B > solución no degenerada B y B son adyacentes si tienen m-1 columnas comunes
10 Claves del algoritmo del símplex El conunto Q de todas las soluciones factibles es convexo La solución óptima para el problema de la programación lineal: Maximice z=cx, sueta a AX=b, X>= cuando es finita debe ocurrir en un extremo de su espacio factible Q Un factor necesario y suficiente para que X sea un punto extremo del espacio factible Q es que X sea una solución básica factible (SBF) Condición de factibilidad Dado x, SBF, asociado a la base B (índices J) buscamos x*=x+t max d adyacente a x también SBF: d dirección de búsqueda d ˆ = 1, d k = k J { ˆ } Ax*=b Ad= a d + a ˆ = J d = B 1 J a ˆ x*>= t max x = min, J, d < d
11 Condición de optimalidad Beneficio reducido Beneficio en la dirección x+td: c T T T T T T T 1 ( x+ td) = c x+ tc d = c x+ t( cˆ + c d ) = c x+ t( cˆ c B aˆ ) Beneficio reducido para la variable no básica : c c B Condición de optimalidad: elegir no básica para que el beneficio reducido sea máximo T J 1 a J J J Algoritmo del SIMPLEX 1. Determinar una solución básica factible y su base asociada B con índices J. 2. Calcular los beneficios reducidos: c = c T 1 c B a 3. Si c terminar (la solución es óptima) si no, elegir un con entra en J 1 4. Calcular la dirección d, dj = B a 5. Si d terminar (beneficio óptimo ) si no, determinar t 6. K sale de J x k max= min,, k < dk k x = d 7. Nueva solución factible básica x+t max d, actualizar J y B J d J K K c >
12 Tablas para el método del simplex Max z=5x 1 +4x 2 S.A. 6x 1 +4x 2 24 x 1 +2x 2 6 x 2 x 1 +1 x 2 2 x 1,x 2 V s 1 v 24 5 x Forma estándar 4 x Max z=5x 1 +4x 2 +s 1 +s 2 +s 3 +s 4 S.A. 6x 1 +4x 2 +s 1 = 24 x 1 +2x 2 + s 2 = 6 -x 1 + x 2 +s 3 =1 x 2 + s 4 =2 x 1,x 2,s 1,s 2,s 3,s 4 s 1 1 s s s s 2 s 3 s 4 c J Tablas para el método del simplex V v s 1 s 2 s 3 s x 1 x 2 s 1 s 2 s 3 s 4 c J s s x /3 1/6 5 s 2 2 4/3-1/ /3 1/ /3-5/6
13 Tablas para el método del simplex V v x 1 s 2 s 3 s x 1 x 2 s 1 s 2 s 3 s 4 c J 4 1 2/3 1/ /3-1/6 1 s 3 5 5/3 1/6 1 s /3-5/6 x /4-1/2 5 x 2 3/2 1-1/8 3/4 4 5/2 3/8-5/4 1 1/2 1/8-3/4 1-3/4-1/2 Punto óptimo: x 1 =3, x 2 =1.5 Valor obetivo: 5*3+4*1.5=21 Casos especiales Solución ilimitada Si hay un vector P r que ha de entrar en la base pero sus componentes son todas menores o iguales que (no se puede aplicar criterio de salida) 5 4 Max z=5x1+4x2 S.A. x2 x1+1 x2 2 x1,x2 V v x 1 x 2 s 1 s 2 c J S s
14 Casos especiales Infinitas soluciones Hay una variable no básica con beneficio reducido en la tabla final (condición necesaria) V v x 1 x 2 s 1 s 2 s 3 s 4 s s x x Solución inicial artificial Encontrar una solución básica factible inicial es fácil si todas las restricciones son (<=) y se consideran como variables básicas las variables de holgura Cuando esto no sucede hay que recurrir a variables artificiales que asumen el papel de las holguras en la primera iteración y que se eliminan en iteraciones posteriores
15 Método de las dos fases Primer paso: añadir variables artificiales a 1,...,a k : Modificar las restricciones para que el lado derecho sea no negativo Convertir las desigualdades a su forma estándar. Añadir una variable artificial no negativa (a) a las restricciones que en el paso 1 fueran = o ( ) Método de las dos fases Resolver un problema LP cuya función obetivo (w) sea minimizar la suma de las variables artificiales (FASE 1) Si el valor óptimo de w es positivo el problema original no tiene solución factible Si el valor óptimo de w es y no hay variables artificiales en la solución básica se eliminan las columnas de la tabla óptima de la fase 1 que corresponden a las variables artificiales y se combinan la función obetivo original con las restricciones de dicha tabla. (Fase 2). Si el valor óptimo de w es y hay variables artificiales en la solución básica, eliminamos de la tabla óptima de la fase 1 las variables artificiales no básicas y forzamos a las variables artificiales básicas en las iteraciones de la fase 2 a permanecer nulas o salir de la base.
16 Método de las dos fases Para forzar artificiales básicas a permanecer nulas hay que tener en cuenta que una vez determinada la variable que entra en la solución: si el coeficiente correspondiente a la variable artificial es positivo, la variable artificial sale de la solución básica si el coeficiente correspondiente a la variable artificial vale, esta variable no sufrirá cambios si el coeficiente es negativo, de todas formas forzamos la salida de la variable artificial lo que no afectará a la factibilidad de la solución porque el valor de la v.a. es. Método de las dos fases Coeficiente a 1 Coeficiente a 1 negativo V v x x 2 a 1 s 1 x 1 c 2 s 1 s 2 a x a V v x x 2 a 1 x 1 x 1 c 2 s 1 s x s a 1
17 Problema dual Maximizar z=c t x Sueto a Ax b, x Minimizar w=b t y Sueto a A t y c, y Lema 1: Si x,y son soluciones factibles, entonces z(x) w(y) Corolario: La solución del problema dual da una cota superior del problema original Lema 2: x,y soluciones factibles. Si z(x)=w(y) entonces x e y son óptimas. Lema 3: Si el problema original es no acotado, el problema dual es no factible Lema 4: Si el problema dual es no acotado, entonces el problema original no es factible Teorema dual Si B es una base óptima para el problema primal entonces C J B -1 es una solución óptima del problema dual. Además los valores obetivos óptimos de ambos problemas coinciden. Si X B es factible, entonces es óptimo si y sólo si la solución dual asociada C J B -1 es factible en el dual. Idea de la demostración: B base óptima y B =c J B -1 factible x B solución con valor obetivo óptimo c J B -1 b=z(x B ) = y B b=w(y B ) valor óptimo dual
18 Relación entre el primario y el dual El dual del problema dual es el problema original (primario) Para cualquier par de soluciones factibles primaria y dual el valor del obetivo en el problema de maximización es menor o igual que el valor del obetivo en el problema de minimización. En el óptimo, la relación es válida con la igualdad. Cualquiera de los dos problemas tiene solución si y sólo si la tiene el otro. Si no hay solución óptima sólo pueden darse dos relaciones: Inconsistente-Inconsistente Inconsistente-Ilimitado Análisis de sensibilidad Cambios en costes: mirar última tabla del método del símplex: sigue siendo óptima al cambiar el valor del coeficiente de la función obetivo? V v x 1 x 2 c 1 c 2 x 1 x 2 s 1 s 2 s 3 s /4-1/2 c J C 1 3/2 1-1/8 3/4 c 2 s 3 5/2 3/8-5/4 1 s 4 1/2 1/8-3/4 1 (c 2-2c 1 )/8 (2c 1-3c 2 )/4
19 Análisis de sensibilidad Cambios en recursos: mirar la tabla óptima del método del simplex para el problema dual: sigue siendo óptima al cambiar el valor de los recursos? -b 1 -b 2 -b3 -b4 V v y 1 y 2 y 3 y 4 e 1 e 2 c J y 1 3/4 1-3/8-1/8-1/4 1/8 -b 1 y 2 1/2 1 5/4 3/4 1/2-3/4 -b 2 (-8b 3 +1b 2-3b 1 )/8 (-8b 4 -b 1 +6b 2 )/8 (2b 2 -b 1 )/4 (b 1-6b 2 )/8
PASO 1: Poner el problema en forma estandar.
MÉTODO DEL SIMPLEX PASO Poner el problema en forma estandar: La función objetivo se minimiza y las restricciones son de igualdad PASO 2 Encontrar una solución básica factible SBF PASO 3 Testar la optimalidad
El Método Simplex. H. R. Alvarez A., Ph. D. 1
El Método Simplex H. R. Alvarez A., Ph. D. 1 El Método Simplex Desarrollado en 1947 por George Dantzig como parte de un proyecto para el Departamento de Defensa Se basa en la propiedad de la solución esquina
UNIVERSIDAD NACIONAL DE INGENIERÍA UNI RUACS ESTELI
Estelí, 13 de Agosto del 2012 EL METODO SIMPLEX El método simplex es el más generalizado para resolver problemas de programación lineal. Se puede utilizar para cualquier número razonable de productos y
2.2 PROGRAMACION LINEAL: METODOS DE SOLUCION
2.2 PROGRAMACION LINEAL: METODOS DE SOLUCION 1. METODO GRAFICO 2. METODO SIMPLEX - ALGEBRAICO 3. METODO SIMPLEX - TABULAR 4. METODO SIMPLEX - MATRICIAL 1 2.2.1 METODO GRAFICO (modelos con 2 variables)
EL MÉTODO SIMPLEX ALGEBRAICO. M. En C. Eduardo Bustos Farías
EL MÉTODO SIMPLEX ALGEBRAICO M. En C. Eduardo Bustos Farías 1 EL METODO SIMPLEX Es un procedimiento general para resolver problemas de programación lineal. Fue desarrollado en el año de 1947 por George
315 M/R Versión 1 Integral 1/13 2009/1 UNIVERSIDAD NACIONAL ABIERTA VICERRECTORADO ACADÉMICO ÁREA INGENIERÍA
35 M/R Versión Integral /3 29/ UNIVERSIDAD NACIONAL ABIERTA VICERRECTORADO ACADÉMICO ÁREA INGENIERÍA MODELO DE RESPUESTA (VERSION.2) ASIGNATURA: Investigación de Operaciones I CÓDIGO: 35 MOMENTO: Prueba
MÉTODO SIMPLEX MÉTODO DE SOLUCIÓN GRÁFICO
MÉTODO SIMPLEX MÉTODO DE SOLUCIÓN GRÁFICO Investigación de Operaciones 1 Introducción a la Programación Lineal Un modelo de programación lineal busca maximizar o minimizar una función lineal, sujeta a
(2.c) RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX
(2.c) RESOLUCIÓN DE MODELOS LINEALES. ALGORITMO DEL SIMPLEX FORMA CANÓNICA DE UN SISTEMA Ax = b Forma Standard y Base factible (repaso). Expresión de las v. básicas en función de las no básicas. Forma
Problemas de Programación Lineal: Método Simplex
Problemas de Programación Lineal: Método Simplex Ej. (3.1) (C) Los siguientes Tableaux fueron obtenidos en el transcurso de la resolución de PL en los cuales había que maximizar una Función Objetivo con
Programación Lineal. Unidad 1 Parte 2
Programación Lineal Unidad 1 Parte 2 Para la mayoría de los problemas modelados con programación lineal, el método gráfico es claramente inútil para resolverlos, pero afortunadamente y gracias a la dedicación
Desarrollo de las condiciones de optimalidad y factibilidad. El problema lineal general se puede plantear como sigue:
Método simplex modificado Los pasos iterativos del método simplex modificado o revisado son exactamente a los que seguimos con la tabla. La principal diferencia esá en que en este método se usa el algebra
Pasos en el Método Simplex
Pontificia Universidad Católica Escuela de Ingeniería Departamento de Ingeniería Industrial y de Sistemas Clase 20 El Método Simplex ICS 1102 Optimización Profesor : Claudio Seebach 16 de octubre de 2006
INDICE Parte I Inducción a la programación lineal Capitulo 1 Origen y definición de la programación lineal Capitulo 2 Modelación y formulación
INDICE Parte I Inducción a la programación lineal Capitulo 1 Origen y definición de la programación lineal 3 Introducción 1 1.1 Concepto de solución óptima 4 1.2 Investigación de operaciones 6 1.2.1 Evolución
DUALIDAD EN PROGRAMACION LINEAL
DUALIDAD EN PROGRAMACION LINEAL Relaciones primal-dual Asociado a cada problema lineal existe otro problema de programación lineal denominado problema dual (PD), que posee importantes propiedades y relaciones
4. Métodos de Solución PPL : Solución Algebraica: METODO SIMPLEX Primera Parte
4. Métodos de Solución PPL : Solución Algebraica: METODO SIMPLEX Primera Parte Jorge Eduardo Ortiz Triviño jeortizt@unal.edu.co http:/www.docentes.unal.edu.co En PL un sistema de producción se representa
MÉTODO SIMPLEX. PROFESORA: LILIANA DELGADO HIDALGO Estandarización Tradicional
MÉTODO SIMPLE POFESOA: LILIANA DELGADO HIDALGO Lilianadelgado@correounivalleeduco Minimizar 4x + x Sueto a: x + x 4x + x 6 x + x 4 x, x Estandarización Tradicional Minimizar 4x + x Sueto a: x + x 4x +
CLAVE: MIS 206 PROFESOR: MTRO. ALEJANDRO SALAZAR GUERRERO
MATEMÁTICAS AVANZADAS PARA LA INGENIERÍA EN SISTEMAS CLAVE: MIS 206 PROFESOR: MTRO. ALEJANDRO SALAZAR GUERRERO 1 1. SISTEMAS LINEALES DISCRETOS Y CONTINUOS 1.1. Modelos matemáticos 1.2. Sistemas 1.3. Entrada
La programación lineal hace referencia al uso eficiente o distribución de recursos limitados, para alcanzar unos objetivos determinados.
Programación lineal La programación lineal hace referencia al uso eficiente o distribución de recursos limitados, para alcanzar unos objetivos determinados. El nombre de programación no se refiere a la
UNIDAD UNO PROGRAMACIÓN LÍNEAL Parte 3
UNIDAD UNO PROGRAMACIÓN LÍNEAL Parte 3 Matriz unitaria "I" de base con variables artificiales. Cuando el problema de programación lineal se expresa en la forma canónica de maximizar, las variables de holgura
MÉTODO SIMPLEX MÉTODO DE SOLUCIÓN GRÁFICO. M. En C. Eduardo Bustos Farías
MÉTODO SIMPLEX MÉTODO DE SOLUCIÓN GRÁFICO M. En C. Eduardo Bustos Farías 1 Introducción a la Programación Lineal Un modelo de programación lineal busca maximizar o minimizar una función lineal, sujeta
Método Simplex: Encontrado una SBF
Método Simplex: Encontrado una SBF CCIR / Matemáticas euresti@itesm.mx CCIR / Matemáticas () Método Simplex: Encontrado una SBF euresti@itesm.mx 1 / 31 Determinación de SBF Determinación de SBF El método
PROBLEMAS PROGRAMACIÓN LINEAL CONTINUA
PROBLEMAS PROGRAMACIÓN LINEAL CONTINUA 1. Sea el problema: Max. 3 x 1 + 4 x 2 + 2 x 3 + x 4 s.a. 4 x 1 + 3 x 2 + 4 x 3 + x 4 5 2 x 1 + x 2 + 5 x 3 + 2 x 4 6 x 1 6, 0 x 2 3, x 3 libre, x 4 0 a) Ponerlo
Si el objetivo es maximizar, entonces se tiene la forma estándar de maximización y, si el objetivo es minimizar, la forma estándar de minimización.
Tema El método simplex Los modelos lineales con dos o tres variables se pueden resolver gráficamente. En el Tema hemos visto la solución gráfica de modelos lineales de dos variables. Sin embargo, este
PROGRAMACION ENTERA. M. en C. Héctor Martínez Rubin Celis 1
M. en C. Héctor Martínez Rubin Celis PROGRAMACION ENTERA En muchos problemas prácticos, las variables de decisión son realistas únicamente si estas son enteras. Hombres, máquinas y vehículos deben ser
Ejemplo : PROGRAMACIÓN LINEAL
PROGRAMACIÓN LINEAL Los problemas de Programación Lineal son aquellos donde se trata de encontrar el óptimo de una función, por ejemplo máximo de beneficios, o mínimo de costos, siendo esta función lineal.
En el siguiente capítulo se hará un repaso de algunas propiedades básicas de conjuntos convexos, para después explicar el método simplex.
Capitulo 2 Método Simplex Para explicar el método de generación de columnas se explicaran a continuación conceptos básicos de la programación lineal y el método simplex. En especial, el concepto de costo
METODO SIMPLEX ANALISIS DE SENSIBILIDAD Y DUALIDAD
METODO SIMPLEX ANALISIS DE SENSIBILIDAD Y DUALIDAD Análisis de sensibilidad con la tabla simplex El análisis de sensibilidad para programas lineales implica el cálculo de intervalos para los coeficientes
Tema II: Programación Lineal
Tema II: Programación Lineal Contenido: Solución a problemas de P.L. por el método gráfico. Objetivo: Al finalizar la clase los alumnos deben estar en capacidad de: Representar gráficamente la solución
3. Métodos clásicos de optimización lineal
3. Métodos clásicos de optimización lineal Uso del método Simplex El problema que pretende resolverse es un problema de optimización lineal sujeto a restricciones. Para el modelo construido para el problema
PROGRAMACIÓN LINEAL. 1. Introducción
PROGRAMACIÓN LINEAL 1. Introducción La programación lineal es una técnica matemática relativamente reciente (siglo XX), que consiste en una serie de métodos y procedimientos que permiten resolver problemas
Universidad Tec Milenio: Profesional IO04001 Investigación de Operaciones I. Tema # 6. revisado
IO04001 Investigación de Operaciones I Tema # 6 Introducción al método simplex matricial o revisado Objetivos de aprendizaje Al finalizar el tema serás capaz de: Emplear el Método simplex Matricial para
4. Método Simplex de Programación Lineal
Temario Modelos y Optimización I 4. Método Simplex de Programación Lineal A- Resolución de problemas, no particulares, con representación gráfica. - Planteo ordenado de las inecuaciones. - Introducción
7. Programación lineal y SIMPLEX
7. Progrmción linel y SIMPLEX Definición de problems de progrmción linel. Método gráfico. Método del SIMPLEX. Método de ls dos fses. Análisis de sensibilidd y problem dul Progrmción Linel Técnic de modeldo
Programación Lineal con Matlab
Arturo Vega González a.vega@ugto.mx Division de Ciencias e Ingenierías Universidad de Guanajuato Campus León Universidad de Guanajuato, DCI, Campus León 1 / 22 Contenido 1 Programación Lineal Método gráfico
Dirección de Operaciones. SESIÓN # 5: El método simplex. Segunda parte.
Dirección de Operaciones SESIÓN # 5: El método simplex. Segunda parte. Contextualización Qué más hay que conocer del método simplex? En la sesión anterior dimos inicio a la explicación del método simplex.
El método simplex 1. 1 Forma estándar y cambios en el modelo. 2 Definiciones. 3 Puntos extremos y soluciones factibles básicas. 4 El método simplex.
El método simplex Forma estándar y cambios en el modelo. Definiciones. Puntos extremos y soluciones factibles básicas. 4 El método simplex. Definiciones y notación. Teoremas. Solución factible básica inicial.
Contenido: Solución algebraica a los problemas de programación lineal con el método simplex.
Tema II: Programación Lineal Contenido: Solución algebraica a los problemas de programación lineal con el método simplex. Introducción El método simplex resuelve cualquier problema de PL con un conjunto
TEMA III MÉTODO SIMPLEX. CONCEPTOS BÁSICOS
TEMA III MÉTODO SIMPLE. CONCEPTOS BÁSICOS MÉTODOS CUANTITATIVOS I TEMA III. MÉTODO SIMPLE. CONCEPTOS BÁSICOS INDICE.- FACTORES PRODUCTIVOS (A i )....- VECTOR EISTENCIAS (P o )....- TÉCNICA... 4.- PROCESO
TEMA 3: EL MÉTODO SIMPLEX
TEMA 3: EL MÉTODO SIMPLEX El uso de este procedimiento gráfico para resolver problemas de PL queda limitado a problemas con dos variables de decisión, de manera que el problema pueda representarse en un
METODO SIMPLEX NOTAS DE CLASE: INVESTIGACIÓN DE OPERACIONES I UNIVERSIDAD CENTRAL PROFESOR CARLOS DÍAZ. Max Z= 12X 1 + 15X 2
METODO SIMPLEX NOTAS DE CLASE: INVESTIGACIÓN DE OPERACIONES I UNIVERSIDAD CENTRAL PROFESOR CARLOS DÍAZ Max Z= 12X 1 + 15X 2 Sujeto a: 2X 1 + X 2
Tema 3: El Método Simplex. Algoritmo de las Dos Fases.
Tema 3: El Método Simplex Algoritmo de las Dos Fases 31 Motivación Gráfica del método Simplex 32 El método Simplex 33 El método Simplex en Formato Tabla 34 Casos especiales en la aplicación del algoritmo
Qué es la programación lineal?
Qué es la programación lineal? En infinidad de aplicaciones de la industria, la economía, la estrategia militar, etc... Se presentan situaciones en las que se exige maximizar o minimizar algunas funciones
EJEMPLO DE SIMPLEX PARA PROBLEMA DE PROGRAMACIÓN LINEAL CASO DE MAXIMIZAR Prof.: MSc. Julio Rito Vargas Avilés
EJEMPLO DE SIMPLEX PARA PROBLEMA DE PROGRAMACIÓN LINEAL CASO DE MAXIMIZAR Prof.: MSc. Julio Rito Vargas Avilés CONSTRUCCION DE LA TABLA INICIAL DEL MÉTODO SIMPLEX Una vez que el alumno ha adquirido la
Lo que se hace entonces es introducir variables artificiales ADAPTACIÓN A OTRAS FORMAS DEL MODELO.
Clase # 8 Hasta el momento sólo se han estudiado problemas en la forma estándar ADAPTACIÓN A OTRAS FORMAS DEL MODELO. Maximizar Z. Restricciones de la forma. Todas las variables no negativas. b i 0 para
PROGRAMACIÓN LINEAL ENTERA
PROGRAMACIÓN LINEAL ENTERA Programación lineal: hipótesis de perfecta divisibilidad Así pues decimos que un problema es de programación lineal entera, cuando prescindiendo de las condiciones de integridad,
MÉTODO DEL DUAL (TEORIA DE DUALIDAD)
MÉTODO DEL DUAL (TEORIA DE DUALIDAD) Todo problema de programación lineal tiene asociado con él otro problema de programación lineal llamado DUAL. El problema inicial es llamado PRIMO y el problema asociado
Álgebra lineal y. programación lineal Con aplicaciones a ciencias. Administrativas, contables y financieras
Tercera edición Álgebra lineal y programación lineal Con aplicaciones a ciencias Administrativas, contables y financieras Francisco Soler Fajardo Fabio Molina Focazzio Lucio Rojas Cortés Contenido Introducción...XIX
Instituto tecnológico de Minatitlán. Investigación de operaciones Ing. Erika Lissette Minaya mortera Unidad 3: programación no lineal
Instituto tecnológico de Minatitlán Investigación de operaciones Ing. Erika Lissette Minaya mortera Unidad 3: programación no lineal Alejandra de la cruz francisco Ingeniería en sistemas computacionales
Optimización lineal con R José R. Berrendero
Optimización lineal con R José R. Berrendero Introducción Veamos cómo se pueden resolver problemas de optimización lineal con R a través de algunos ejemplos sencillos. La mayor parte de las funciones necesarias
Módulo Programación lineal. 3 Medio Diferenciado
Módulo Programación lineal 3 Medio Diferenciado Profesor: Galo Páez Nombre: Curso :. Sabemos que una ecuación lineal de dos variables tiene la forma con ó y representa siempre una recta en el plano. Ahora
Vectores y Matrices. Tema 3: Repaso de Álgebra Lineal Parte I. Contenidos
Tema 3: Repaso de Álgebra Lineal Parte I Virginia Mazzone Contenidos Vectores y Matrices Bases y Ortonormailizaciòn Norma de Vectores Ecuaciones Lineales Algenraicas Ejercicios Vectores y Matrices Los
6.2 OBSERVACIONES IMPORTANTES AL UTILIZAR MÉTODO SIMPLEX
6. MÉTODO SIMPLEX El Método Simplex es un método analítico de solución de problemas de programación lineal capaz de resolver modelos más complejos que los resueltos mediante el método gráfico sin restricción
Introducción a la programación lineal
Introducción a la programación lineal La programación lineal se aplica a modelos de optimización en los que las funciones objetivo y restricción son estrictamente lineales. La técnica se aplica en una
Resolución. Resolución gráfica de problemas de optimización
Resolución de problemas de optimización Para resolver mente un problema de optimización como éste empezamos representando sus restricciones con igualdad. (0, 4) (0, 4) (4, 0) Para resolver mente un problema
Por Sustitución: y= 2x+6 x + 3 (2x+6) = 4 x + 6x + 18 = 4 7x = -14 x= -2 y=2 (-2)+6 y=2. Por Igualación: 6x+18=4-x 7x=-14 x= -2 y=2 (-2)+6 y=2
Tema 5: Sistemas de Ecuaciones y de Inecuaciones. Programación lineal. 5.1 Sistemas de dos ecuaciones con dos incógnitas. Un sistema de dos ecuaciones con dos incógnitas es de la forma: Un par de valores
Programación Lineal. El método simplex
Programación Lineal El método simplex El método simplex es una herramienta algebraica que permite localizar de manera eficiente el óptimo entre los puntos extremos de una solución a un problema de programación
Práctica 2 Métodos de búsqueda para funciones de una variable
Práctica 2 Métodos de búsqueda para funciones de una variable Introducción Definición 1. Una función real f se dice que es fuertemente cuasiconvexa en el intervalo (a, b) si para cada par de puntos x 1,
1 SISTEMAS DE ECUACIONES LINEALES Una ecuación es un enunciado o proposición que plantea la igualdad de dos expresiones, donde al menos una de ellas contiene cantidades desconocidas llamadas variables
Polinomios. 1.- Funciones cuadráticas
Polinomios 1.- Funciones cuadráticas Definición 1 (Función polinomial) Sea n un entero no negativo y sean a n, a n 1,..., a, a 1, a 0 número s reales con a n 0. La función se denomina función polinomial
PREPARANDO EL MODELO PARA ADAPTARLO AL MÉTODO SIMPLEX. a21 x1 + a22 x2 +... + a2n xn = b2... am1 x1 + am2 x2 +... + amn xn = bm x1,...
El método Simplex es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Partiendo del valor de la
PROBLEMAS de Programación Lineal : Resolución Gráfica
PROBLEMAS de Programación Lineal : Resolución Gráfica Ej. (1.1) Mostrar gráficamente porque los 2 PL siguientes no tienen una Solución Optima y explicar la diferencia entre los dos. (C) (A) Max z = 2x
Programación Lineal. PL: Parte de la Programación Matemática donde tanto la función objetivo como las restricciones son funciones lineales.
Programación Lineal PL: Parte de la Programación Matemática donde tanto la función objetivo como las restricciones son funciones lineales. La importancia de esta técnica se debe a la aparición del método
Programación Lineal Continua
Elisenda Molina Universidad Carlos III de Madrid elisenda.molina@uc3m.es 8 de octubre de 2008 Esquema 1 Formulación y Ejemplos 2 3 Ejemplo: Producción de carbón Una empresa minera produce lignito y antracita.
EJERCICIOS RESUELTOS DE INECUACIONES. Juan Jesús Pascual. Inecuaciones
MATEMÁTICAS EJERCICIOS RESUELTOS DE INECUACIONES Juan Jesús Pascual Inecuaciones Índice ejercicios resueltos A. Inecuaciones lineales con una incógnita B. Inecuaciones de segundo grado con una incógnita
Universidad Nacional de Ingeniería Sede: UNI-Norte Investigación de Operaciones I
Universidad acional de Ingeniería Sede: UI-orte Investigación de Operaciones I Método Simple Revisado Ejemplo. Resolver el siguiente problema de P.L. s. a: Ma, z 6 Para resolver por el método simple revisado,
Apéndice AEl método Simplex José Arturo Barreto M.A. Caracas-Venezuela
A Tels:46-359965 46-6989 44-6643 4-393 josearturobarreto@yahoo.com ALGEBRA LINEAL APLICADA JOSE ARTURO BARRETO,M.A. APÉNDICE A. EL METODO SIMPLEX OBJETIVOS Al terminar el apéndice el estudiante deberá
optimización: programación lineal y entera
UNIVERSIDAD PERUANA LOS ANDES Facultad de Ciencias i Administrativas i ti y Contables METODOS CUANTITATIVOS DE NEGOCIOS capítulo 2. modelos de optimización: programación lineal y entera Objetivos de Aprendizaje:
Ejercicio 1: Realiza las siguientes divisiones por el método tradicional y por Ruffini: a)
Tema 2: Ecuaciones, Sistemas e Inecuaciones. 2.1 División de polinomios. Regla de Ruffini. Polinomio: Expresión algebraica formada por la suma y/o resta de varios monomios. Terminología: o Grado del polinomio:
1. RESOLVER el siguiente problema de programación lineal. max z =15x 1 + 10x 2 suj.a : 2x 1 + x 2 1500 x 1 + x 2 1200 0 x 1 500
1. RESOLVER el siguiente problema de programación lineal max z =15x 1 + 10x 2 suj.a : 2x 1 + x 2 1500 x 1 + x 2 1200 0 x 1 500 x 2 0 2 RESOLVER el siguiente problema de P.L.: max z = 2x 1 + 3x 2 2x 3
Programación Lineal y Optimización Primer Examen Parcial :Solución Profr. Eduardo Uresti, Enero-Mayo 2011
Programación Lineal y Optimización Primer Examen Parcial : Profr. Eduardo Uresti, Enero-Mayo 2011 Matrícula: Nombre: 1. Una pequeña empresa fabrica sustancias de dos tipos a partir de tres materias primas,
P. A. U. LAS PALMAS 2005
P. A. U. LAS PALMAS 2005 OPCIÓN A: J U N I O 2005 1. Hallar el área encerrada por la gráfica de la función f(x) = x 3 4x 2 + 5x 2 y la rectas y = 0, x = 1 y x = 3. x 3 4x 2 + 5x 2 es una función polinómica
MÁXIMOS Y MINIMOS. Marco Antonio Cruz Chávez
MÁXIMOS Y MINIMOS Marco Antonio Cruz Chávez UAEM Av. Universidad 11 Col. Chamilpa C.P. 61 Cuernavaca Morelos, México Agosto 18 del 334858@academ1.mor.itesm.mx Abstract. En este trabajo se presentan algunos
3.1 Por inspección del tablero óptimo genere las respuestas a los numerales dados. X 1 = Cantidad de tarjetas de invitación a producir semanalmente en Kimberly Colpapel y X 2 = Cantidad de tarjetas de
PLs no acotados El método símplex en dos fases PLs no factibles. Investigación Operativa, Grado en Estadística y Empresa, 2011/12
PLs no acotados El método símplex en dos fases PLs no factibles Prof. José Niño Mora Investigación Operativa, Grado en Estadística y Empresa, 2011/12 Esquema PLs no acotados Necesidad de obtener un vértice
Valores y Vectores Propios
Valores y Vectores Propios Departamento de Matemáticas, CSI/ITESM de abril de 9 Índice 9.. Definiciones............................................... 9.. Determinación de los valores propios.................................
MICROECONOMÍA II. PRÁCTICA TEMA 5: El Modelo de Equilibrio General con Intercambio Puro
MICROECONOMÍA II Problema 1 PRÁCTICA TEMA 5: El Modelo de Equilibrio General con Intercambio Puro PRIMERA PARTE: La Caja de Edgeworth y la Curva de Contrato El conjunto de asignaciones eficientes está
Algebra lineal y conjuntos convexos
Apéndice A Algebra lineal y conjuntos convexos El método simplex que se describirá en el Tema 2 es de naturaleza algebraica y consiste en calcular soluciones de sistemas de ecuaciones lineales y determinar
Problemas de transporte, asignación y trasbordo
Problemas de transporte, asignación y trasbordo 1. Plantear un problema de transporte Tiene como objetivo encontrar el mejor plan de distribución, generalmente minimizando el coste. Un problema está equilibrado
Un sistema de inecuaciones lineales con una incógnita es el conjunto formado por dos o más inecuaciones lineales de la forma:
MATEMÁTICAS BÁSICAS SISTEMAS DE DESIGUALDADES SISTEMAS DE DOS INECUACIONES Y DOS INCÓGNITAS Un sistema de inecuaciones lineales con una incógnita es el conjunto formado por dos o más inecuaciones lineales
Ecuaciones. 3º de ESO
Ecuaciones 3º de ESO El signo igual El signo igual se utiliza en: Igualdades numéricas: 2 + 3 = 5 Identidades algebraicas: (x + 4) x = x 2 + 4 4x Fórmulas: El área, A,, de un círculo de radio r es: A =
Formulación de un Modelo de Programación Lineal
Formulación de un Modelo de Programación Lineal Para facilitar el planteamiento del modelo matemático general de la PL considere el siguiente problema: La planta HBB fabrica 4 productos que requieren para
IES Fco Ayala de Granada Septiembre de 2013 (Modelo 2 ) Solución Germán-Jesús Rubio Luna. Opción A
IES Fco Ayala de Granada Septiembre de 01 (Modelo ) Germán-Jesús Rubio Luna Opción A Ejercicio 1 opción A, modelo Septiembre 01 ['5 puntos] Un alambre de 10 metros de longitud se divide en dos trozos.
Tema 2. Sistemas de ecuaciones lineales
Tema 2. Sistemas de ecuaciones lineales Estructura del tema. Definiciones básicas Forma matricial de un sistema de ecuaciones lineales Clasificación de los sistemas según el número de soluciones. Teorema
EL MÉTODO SIMPLEX. los redondos. Por último, a los manteles rectangulares se les deben colocar cuatro esquineros de refuerzo.
EL MÉTODO SIMPLEX Hasta ahora, la única forma que conocemos de resolver un problema de programación lineal, es el método gráfico. Este método es bastante engorroso cuando aumenta el número de restricciones
Programación Lineal. Optimización de la combinación de cifras comerciales en una red lineal de distribución de agua.
Programación Lineal La Programación Lineal es un procedimiento o algoritmo matemático mediante el cual se resuelve un problema indeterminado, formulado a través de ecuaciones lineales, optimizando la función
CONVEXIDAD: CONCEPTOS BÁSICOS
CONVEXIDAD: CONCEPTOS BÁSICOS El estudio de la convexidad de conjuntos y funciones, tiene especial relevancia a la hora de la búsqueda de los óptimos de las funciones, así como en el desarrollo de los
CAPÍTULO 3: DETERMINANTES Y SISTEMAS DE ECUACIONES
CAPÍTULO 3: DETERMINANTES Y SISTEMAS DE ECUACIONES Parte A: determinantes. A.1- Definición. Por simplificar, consideraremos que a cada matriz cuadrada se le asocia un número llamado determinante que se
Líneas y Planos en el Espacio
Líneas y Planos en el Espacio Departamento de Matemáticas, CCIR/ITESM de enero de Índice..Introducción.................................................Ecuación paramétrica de la recta.....................................ecuación
Z Optima X 1 + X 2 5 Z 1 -X 1 + 2X Región factible. Figura 1
Método Gráfico El procedimiento geométrico, es únicamente adecuado para resolver problemas muy pequeños (con no más de dos variables debido al problema de dimensionalidad). Este método provee una gran
MATEMÁTICAS PARA LA ECONOMÍA III
MATEMÁTICAS PARA LA ECONOMÍA III CÁLCULO INTEGRAL. Tema 1. - Funciones primitivas. 1.1 - Funciones primitivas e integral indefinida de una función real de variable real. 1.2 - Primitivas de las funciones
PRIMERA PARTE PROGRAMACION MATEMATICA
CONTENIDO CAPITULO 1 Toma de decisiones en la investigación de operaciones (IO) 1 1.1 Arte y ciencia de la investigación de operaciones. 1 1.2 Elementos de un modelo de decisión.. 2 1.3 Arte de la representación
IES Francisco Ayala Modelo 1 (Septiembre) de 2007 Solución Germán Jesús Rubio Luna. Opción A
IES Francisco Ayala Modelo (Septiembre) de 7 Germán Jesús Rubio Luna Opción A Ejercicio n de la opción A de septiembre, modelo de 7 3x+ Sea f: (,+ ) R la función definida por f(x)= x. [ 5 puntos] Determina
PROBLEMA 1. Considere el siguiente problema de programación lineal:
PROBLEMA 1 Considere el siguiente problema de programación lineal: Sean h1 y h2 las variables de holgura correspondientes a la primera y segunda restricción, respectivamente, de manera que al aplicar el
Grado en Química Bloque 1 Funciones de una variable
Grado en Química Bloque Funciones de una variable Sección.5: Aplicaciones de la derivada. Máximos y mínimos (absolutos) de una función. Sea f una función definida en un conjunto I que contiene un punto
TEMA N 2 RECTAS EN EL PLANO
2.1 Distancia entre dos puntos1 TEMA N 2 RECTAS EN EL PLANO Sean P 1 (x 1, y 1 ) y P 2 (x 2, y 2 ) dos puntos en el plano. La distancia entre los puntos P 1 y P 2 denotada por d = esta dada por: (1) Demostración
RESOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL CON LA CALCULADORA
RESOLUCIÓN DE PROBLEMAS DE PROGRAMACIÓN LINEAL CON LA CALCULADORA AUTORÍA JUAN JOSÉ MUÑOZ LEÓN TEMÁTICA PROGRAMACIÓN LINEAL ETAPA BACHILLERATO Resumen Este artículo trata de cómo resolver problemas de
Con miras a conocer la metodología que se aplica en el Método SIMPLEX, tenemos a continiacion un ejemplo:
Método Simplex. Este método fue creado en el año 1947 por el estadounidense George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich, con el objetivo de crear un algoritmo capaz de crear soluciones

References: RESOLUCIÓN 
 RESOLUCIÓN 
 resolución 
 Resolución 
 Resolución 

Resolución 
 Resolución 
 Resolución 

RESOLUCIÓN 

RESOLUCIÓN