Capítulo 2. Método Simplex- Evaluación del método de generación de columnas para el problema de corte -Cutting Stock- usando heurísticas para la obtención de patrones de corte - Departamento de Ingeniería Reportar como inadecuado




Capítulo 2. Método Simplex- Evaluación del método de generación de columnas para el problema de corte -Cutting Stock- usando heurísticas para la obtención de patrones de corte - Departamento de Ingeniería - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Capítulo 2. Método Simplex- Evaluación del método de generación de columnas para el problema de corte -Cutting Stock- usando heurísticas para la obtención de patrones de corte - Departamento de Ingeniería Industrial y Mecánica. - - Licenciatura en Ingeniería Industrial con área de manufactura. - Escuela de Ingeniería, - Universidad de las Américas Puebla.

Autor: Díaz Smith, Santiago

Fuente: http://catarina.udlap.mx/


Introducción



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 reducido. 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. 2.1 Conjuntos convexos Un conjunto 𝑋 en ℝ𝑛 se dice que es convexo si para cualquier par de puntos 𝐱 𝟏 , 𝐱 𝟐 ∈ 𝑋, resultantes de la recta 𝐱 = 𝜆𝐱 𝟏 + 1 − 𝜆 𝐱 𝟐 ∈ 𝑋 (4) para cualquier 𝝀 ∈ 𝟎, 𝟏 (Bazaraa & Jarvis, 1981). Nos podemos dar cuenta que para cada 𝜆 en el intervalo [0,1], 𝐱 representa un punto del segmento de recta que une a 𝐱 𝟏 y 𝐱 𝟐 .
A cada punto, de esta forma se le llama combinación convexa o promedio ponderado (Bazaraa & Jarvis, 1981).
En la Ilustración 1 se muestra un ejemplo de un conjunto convexo y uno no convexo. x2 x1 x1 x2 Ilustración 1.- Conjunto convexo y conjunto no convexo (Elaboración Propia) Un tipo de conjuntos convexos son los hiperplanos los cuales están definidos de la siguiente manera.
Dado un vector no nulo 𝐩 ∈ ℝn , y, un escalar 𝑘, el conjunto 𝐻 es un hiperplano en ℝn si, 𝐻 = 𝐱 ∈ ℝ𝑛 |𝐩𝐭 𝐱 = 𝑘 , cuyos semiespacios están definidos por, 𝐻 + = 𝐱 ∈ ℝ𝑛 |𝐩𝐭 𝐱 ≥ 𝑘 , y, 𝐻 − = 𝐱 ∈ ℝ𝑛 |𝐩𝐭 𝐱 ≤ 𝑘 (Castillo, Conejo, Pedregal, García, & Alguacil, 2002). 2.1.1 Puntos extremos El concepto de puntos extremos juega un papel muy importante dentro de la programación lineal, debido a que cada punto extremo es un posible resultado del problema que se está solucionando.
Un punto 𝐱 en un conjunto 𝑋 es extremo, si y solo si no se puede representar como una combinación convexa de cualesquiera dos puntos en el conjunto 𝑋.
Por lo tanto si 𝐱 = 𝜆𝐱 𝟏 + 1 − 𝜆 𝐱 𝟐 con 𝜆 ∈ (0,1) y 𝐱 ...





Documentos relacionados