Investigacion De Operaciones

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 opromedio 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 ?? esCopiar & 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 posibleresultado 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 ?? ?? ,?? ?? ∈ ??,
entonces ?? = ?? ?? = ?? ?? y ?? es un punto extremo (Bazaraa & Jarvis, 1981).
En la Ilustración 2, se puedenobservar algunos ejemplos de puntos extremos y
no extremos, podemos ver que mientras ?? ?? es un punto extremo, ?? ?? y ?? ?? no lo son.

x1
x3
x2

Ilustración 2.- Ejemplos de puntos extremos y no extremos (Elaboración Propia).
2.1.2 Rayos y direcciones
Otro ejemplo de conjunto convexo es un rayo. Un rayo es una colección de puntos de la
forma ?? ?? + ????: ?? ≥ 0}, en donde ?? es un vectordistinto de cero. En este caso, ?? ?? es el
vértice del rayo, y ?? es la dirección del rayo (Bazaraa & Jarvis, 1981).
2.1.2.1 Direcciones de un conjunto convexo
Si se tiene un conjunto convexo y un vector ?? distinto de cero, se dice que ?? es una
dirección del conjunto si para cada ?? ?? dentro del conjunto, el rayo o semirrecta ?? ?? +
????: ?? ≥ 0} también pertenece al conjunto. Basados enesta definición podemos concluir
que si un conjunto es acotado, entonces no contiene direcciones (Bazaraa & Jarvis,
1981; Arreola Risa, 2003).
2.1.2.2 Direcciones extremas
Análogamente al concepto de punto extremo de un conjunto convexo, el concepto de
dirección extrema de un conjunto convexo, se refiere a una dirección del conjunto
convexo que no se puede representar como una combinaciónlineal positiva de dos
direcciones diferentes del conjunto. Por lo tanto ?? es una dirección extrema del
conjunto convexo ??, si para dos direcciones ???? y ???? de ??, es decir, si ?? = ??1 ???? +
??2 ????, ??1 ?? ??2 ≥ 0, implica que ???? es proporcional a ????
2.1.3 Conos convexos
Un tipo especial de conjuntos convexos son los conos convexos. Estos tienen la
propiedad adicional de que paracualquier cono convexo ?? , ???? Є ?? para cada ?? Є ?? y
?? ≥ 0. Para ?? = 0, un cono convexo siempre contiene al origen. Si a su vez tomamos
cualquier punto ?? Є ?? entonces el rayo ??, también pertenece a ?? . Por lo tanto un cono

convexo es un conjunto convexo cuyos elementos son los rayos que salen del origen
(Bazaraa & Jarvis, 1981; Arreola Risa, 2003).
2.1.4 Conjuntos y conos...