PROGRAMACIÓN

MATEMÁTICA
Dra. Nesly de los Ángeles Laguna Valle
La programación matemática es una potente técnica de
optimización utilizada en el proceso de toma de
decisiones de numerosas organizaciones. Como otras
ramas de la ciencia y la tecnología, la programación
matemática se sirve de modelos para representar
aquellos aspectos de la realidad que tienen influencia en
su ámbito de interés, en este caso las decisiones que
optimizan el funcionamiento de un sistema.
 Procesos principales que llevan al diseño de un
modelo de optimización.

La
especificación Desarrollar un modelo de
del conjunto costes del sistema. Esto
Identificación de las posibles de valores de supone diseñar una
decisiones que pueden tomarse en el las variables función objetivo que
sistema y su representación en forma de decisión asigne a cada conjunto
de variables: las variables de decisión. que resultan posible de valores de las
admisibles en variables de decisión su
el sistema. valor de coste/beneficio.
CLASIFICACIÓN DE MODELOS MATEMÁTICO

o Programación o Programación
Determinanticos

Probabilísticos
matemática estocástica
 Programación lineal o Gestión de inventarios
 Programación entera o Fenómenos de espera
 Programación (colas)
dinámica o Teoría de juegos
 Programación no lineal o Simulación
 Programación
multiobjetivo
o Modelos de transporte
o Modelos de redes
CLASIFICACIÓN DE MODELOS MATEMÁTICO
Programación
Programación Lineal
Binaria

Mezcla de productos Mochila

Dietas Corte

Transporte Viajantes

Transbordo Horarios o Calendarización

Asignación Cubrimiento

Empaquetado
Las unidades que se abordaran en el módulo son:
Convexos y Poliedros, Método Simplex, Modelización
de Problemas, Análisis de Sensibilidad, Flujos y
Redes y Articulo Científico
Actividad 1: Reunidos en equipo de 3 aspirantes a
doctores, leer y analizar un artículo científicos relacionado
a la aplicación de modelos matemáticos en problemas
diversos, luego preparar presentación del mismo para
presentarlo al grupo, resaltando el tipo de modelo que se
aplica, su construcción y método de solución.
 Tarea 1: Elaboración de articulo de revisión o
modelación de problema real

Artículo de Revisión
“El artículo de revisión es considerado como un estudio pormenorizado,
selectivo y crítico que integra la información esencial en una perspectiva
unitaria y de conjunto. Es un tipo de artículo científico que sin ser original
recopila la información más relevante de un tema específico. Su finalidad es
examinar la bibliografía publicada y situarla en cierta perspectiva”. (Vera
Carrasco, 2009)

Las etapas propuestas son: definir los objetivos de la revisión, realizar la

búsqueda bibliográfica, organizar de la información de acuerdo a mapas
mentales y redactar el artículo.
 Estructura del articulo científico
1. Título
2. Autores/as
3. Resumen – Abstract (máximo 250 palabras)
4. Palabras claves
5. Introducción (contextualización teórica del estado de la cuestión que trata
el artículo)
6. Método (narrar el proceso de la búsqueda bibliográfica, objetivos de la
revisión, tipo de revisión, criterios de selección de los artículos o
documentos, así como el diversidad de documentos, etc.).
7. Resultados y discusiones (qué datos relevantes habéis hallado, cómo
contrastan éstos entre diferentes estudios, aplicaciones, modelos, qué
implicaciones prácticas se derivan, cómo contrastan los resultados.
8. Conclusiones (destacar las principales aportaciones de su revisión a luz de
la literatura científica consultada –artículos, libros-, etc.).
9. Referencias bibliográficas
Aspectos Generales
Temáticas (Aplicaciones de programación matemática):
• Programación lineal, entera, mixta
• Problemas de dietas
• Problemas de mezcla de productos
• Aplicación del método simplex
• Transporte
• Problemas de asignación
• Problemas de redes
• Problema de la mochila
• Problema de corte

Extensión máxima de 15 páginas

Letra: Arial, tamaño 12
Espaciado: 1.5.
Texto justificado
Márgenes 2,5 cm
APA 6ta Edición
Conjuntos Convexos y
Poliedros
Conceptos sobre conjuntos convexos
Espacio Euclidiano

 Un espacio euclidiano n-dimensional, denotado por , es una colección de

todos los vectores de dimensión n.
 

Combinación Lineal y Afín

  vector b en se dice que es una combinación lineal de en , si , donde son

Un
números reales. Si, además, , entonces se dice que b es una combinación lineal
afín de .
 Subespacio Lineal y Afín
 Un subespacio linealde es un subconjunto de tal que si y , entonces cada
combinación lineal de y pertenecen a . Similarmente, un subespacio afín de
es un subconjunto de tal que y , entonces cada combinación lineal afín de y
pertenecen a .

Dependencia Lineal
 Una colección de vectores de n dimensión es linealmente independiente si:

Por lo tanto son linealmente dependientes si existen , no todos ceros, tal que
 En resumen

Se dice que un vector X en es una combinación lineal de los vectores si

existe adecuados tales que . Además:

i) Si los verifican , entonces se dice que X es una combinación afín de los

ii) Si los verifican , entonces X es una combinación lineal positiva de los
iii) Finalmente, si se verifica ambas condiciones a la vez, esto es, si y , se dice
que X es una combinación convexa de los
 
Tres Resultados Equivalentes
  Demostración

De (2)
 Sumando (1) y (3)

Obtenemos

Sea

Luego

Por tanto
Conjunto Convexo

 Definición: Un conjunto de se dice que es convexo si y solo si contiene

cualquier combinación convexa de cualquier pareja de elementos de
elementos del conjunto. Es decir:
 

 
Nota: es convexo y por convenio también. Los puntos de cualquier segmento
son combinaciones convexas (se expresan como combinaciones convexas) de
los extremos del segmento.
  
Note que con λ en el intervalo representan los puntos sobre el segmento de
recta que unen . Todos los puntos de la forma con se llama una combinación
convexa. Si , entonces la combinación convexa es llamada estricta
Conjuntos Convexos y no Convexos
y

 𝑥1  =0
 𝑥′ = ( 1− 𝜆 ) 𝑥1 + 𝜆 𝑥 2
 𝑥 ′

 𝑥′ = 𝑥 − 𝜆 𝑥 1+ 𝜆 𝑥 2
1

 𝑥2  =0
 𝑥′ = 𝑥 + 𝜆 (𝑥 2 − 𝑥 1)
1

x
 
Algunos ejemplos de conjuntos convexos son los siguientes

1. , donde A es una matriz mxn y b es un vector de dimensión m

2. , donde A es una matriz mxn y b es un vector de dimensión m
3. , donde A es una matriz mxn y b es un vector de dimensión m
  Ejemplo
Probamos que , donde A es una matriz mxn y b es un vector de dimensión m)
es un conjunto convexo.

 
Sean y dos puntos que pertenecen al conjunto X. Entonces debemos probar que
X es un conjunto convexo, o sea, probaremos que todo punto.

 Multiplicando la primera relación por λ y la segunda por (1-λ) y sumando

las relaciones encontradas tenemos:

Por lo tanto x’
 Probar
  que es un conjunto convexo

− 𝑥 𝑜‖=‖( 1 − 𝜆 ) 𝑥 1 + 𝜆 𝑥2 − 𝑥 𝑜‖  𝑥2

‖
 ‖𝑥 ′ − 𝑥 𝑜‖= ( 1 − 𝜆 ) 𝑥 1 + 𝜆 𝑥2 − ( ( 1 − 𝜆 ) 𝑥 0 + 𝜆 𝑥 0 ) ‖
 𝑥 ′
  ‖𝑥 ′ − 𝑥 𝑜 ‖= ¿
 𝑥1
  ‖𝑥 ′ − 𝑥 𝑜 ‖≤ ¿
 𝑥 0

 ‖𝑥 ′ − 𝑥 𝑜‖≤ ( 1 − 𝜆 ) ‖𝑥 1 − 𝑥 0‖+ 𝜆‖𝑥 2 − 𝑥 0‖

  ‖𝑥 ′ − 𝑥 𝑜‖< ( 1 − 𝜆 ) 𝜀 + 𝜆 𝜀

  ‖𝑥 ′ − 𝑥 𝑜 ‖< 𝜀
 
Proposición:

Sea , dos conjuntos convexos, se cumple:

i. es convexo
ii. es convexo
iii. es convexo
iv. La imagen y la anti - imagen por una aplicación lineal de un
convexo es un convexo

Es decir, si , f lineal, entonces:

es convexo convexo

es convexo convexo
 Puntos Extremos

 
Un punto x de un conjunto convexo X se llama punto extremo de X si x no
puede representarse como un combinación convexa estricta de dos puntos
distintos en X. En otras palabras, si , entonces

Definición (punto extremo): Dado un conjunto convexo no vacío. Sea , se

dice que x es un punto extremo de S si y solo si x no se puede expresar como
combinación convexa estricta de dos puntos distintos de S.
 
 
Equivalentemente:

 Se denota extr(S) al conjunto de los puntos extremos de S.

 Cuando S es compacto (cerrado y acotado), cualquier punto

de S se puede expresar como combinación convexa de sus
puntos extremos, pero cuando no es acotado, no se puede
decir lo mismo, por tanto hablamos de direcciones y
direcciones extremas
 Hiperplano y semiespacio
  
Definición: Un hiperplano es un conjunto de la forma , donde a
es el vector normal al hiperplano.
 
Equivalentemente, un hiperplano consiste en todos los puntos
que satisface la ecuación . La constante k puede ser eliminada
cuando nos referimos a un punto fijo sobre el hiperplano. Si ,
entonces , y para algunas , tenemos . Al restar tenemos . En
otras palabras, H puede representarse como una colección de
puntos que satisface , donde es algún punto fijo en H. Un
Hiperplano es un conjunto convexo.
 Hiperplano

  es convexo
y
 𝐻 ( 𝑝 , 𝛼 )= { 𝑥 ∈ ℝ 𝑛 ∕ 𝑝 ∙ 𝑥=𝛼 }

 
 𝑝

 𝑥 0
 
 𝑥

x  

⊥
 𝑥 − 𝑥 0 = 𝑦 ⇒ 𝑥=𝑥 0+ 𝑦 ⇒ 𝐻 ( 𝑝 , 𝛼 )=𝑥 0 + 𝑝
 𝑝⊥
 Un hiperplano divide en dos regiones llamadas semiespacio. Por lo tanto,
un semiespacio es una colección de puntos de la forma , donde p es un
vector no nulo en y k es un escalar. Un semiespacio puede también ser una
representación de un conjunto de puntos de la forma . La unión de los dos
semiespacios y es .
 Rayos y direcciones

 Otro ejemplo de un conjunto convexo es un rayo. Un rayo es una colección de

puntos de la forma donde d es un vector no nulo. Aquí, se llama vértice del rayo,
y d es la dirección del rayo.

Direcciones de un conjunto convexo

 
Dado un conjunto convexo, un vector d distinto de cero se denomina dirección del
conjunto, si para cada del conjunto, el rayo también pertenece al conjunto. Por lo
tanto, comenzando en cualquier punto en el conjunto, uno puede retroceder a lo
largo de d para cualquier paso de longitud y permanecer dentro del conjunto.
Claramente, si el conjunto está limitado, entonces no tiene direcciones.
 Definición (Dirección): Un vector “d” de no nulo () se dice que es una
dirección de S, siendo S un conjunto convexo, si

Se dice que dos direcciones de S son distintas si y solo si

  Ejemplo
Considere el conjunto , encontrar las direcciones extremas de X.

 
Sea un punto fijo factible arbitrario. Entonces es una dirección de X si y solo si y pertenece a X
para todo . Por lo tanto,

Como , entonces implica que . Por lo tanto, es una dirección de X si y solo si

 
 DIRECCIONES EXTREMAS DE UN CONJUNTO
CONVEXO

La noción de direcciones extremas es similar a la noción de puntos extremos.

Una dirección extrema de un conjunto convexo es una dirección del conjunto
que no puede ser representado como una combinación positiva de dos
direcciones distintas del conjunto. Los dos vectores, d1 y d2, se dice que son
distintos, o no equivalentes, si d1 no puede ser representado como un
múltiplo positivo de d2.

 En el ejemplo anterior, después de la normalización, tenemos dos direcciones

extremas . Cualquier otra dirección del conjunto, que no sea un múltiplo de d1 y
d2, puede se representará como , donde , Cualquier rayo que está contenido
en el conjunto convexo y cuya dirección es una dirección extrema se denomina
rayo extremo.
 Definición (Dirección Extrema): Se
dice que una dirección S, es dirección
extrema si y solo si no se puede obtener
como una combinación positiva de dos
direcciones de S, equivalentemente
Conos convexos

 Un cono convexo C es un conjunto convexo con la

propiedad adicional que para cada y para cada . Tenga en
cuenta que un cono convexo siempre contiene el origen al
dejar y también, dado cualquier punto , el rayo o la línea
media pertenece a C. Por lo tanto, un cono convexo es un
conjunto convexo que consiste enteramente en rayos que
emanan desde el origen.
 Como ejemplo, considere el cono
convexo cuyas direcciones extremas
son (1, 1) y (0, 1). De la Figura está
claro que el cono convexo debe ser
 
Dado un conjunto de vectores ,
podemos formar el cono convexo C
generados por estos vectores. Este
cono consta de todas las
combinaciones no negativas de , es
decir,
 Envoltura convexa
 Definición: Dado , se define la envoltura convexa de S, como el menor convexo (en
sentido de inclusión), que convenga a S.  De lo anterior:

La envoltura convexa de S es la intersección de todos los conjuntos convexos que

contienen a S.
 De modo que
 Nota:

 La envoltura convexa de un numero finito de puntos es un

politopo
 La envoltura convexa de (n+1) puntos afínmente
independientes es un simplex
 
Lema: Sea , S es convexo si y solo si S contiene todas las
combinaciones finitas de sus elementos.
 Teorema de Caratheodory (1907).
 
La envoltura convexa no establece restricción alguna sobre el número
de puntos de A necesarios para la combinación. El Teorema de
Caratheodory nos dice, precisamente, cuál es el número máximo de
puntos requeridos.
 
 
Teorema de Caratheodory
Sea arbitrario. Si entonces tal que
es decir:

 
Funciones Convexas y Cóncavas

  
Las funciones convexas y cóncavas juegan un papel importante en
los problemas de optimización. Estas funciones surgen naturalmente
en problemas de optimización lineal (en una forma no lineal) cuando
se trata de análisis paramétrico. Se dice que una función f del vector
de variables () es convexa si la siguiente desigualdad se mantiene
para cualquiera de los dos vectores :
 

 
CONJUNTOS POLIÉDRICOS

 Los conjuntos poliédricos y los conos poliédricos representan casos

especiales importantes de conjuntos convexos y conos convexos. Un
conjunto poliédrico o un poliedro es la intersección de un número finito de
semiespacios. Un conjunto poliédrico acotado se llama un politopo. Dado que
un semiespacio puede ser representado por una desigualdad del tipo

porque cada fila (restricción) del sistema anterior representa un semiespacio.

 
Definición (Poliedro):
Un conjunto se dice que es un poliedro o conjunto poliédrico si es la intersección de un
número finito de semi-espacios, i.e.

Donde

De forma equivalente

Si construimos una matriz cuyas filas con los vectores normales asociados a los
hiperplanos que definen el poliedro, es posible representar el conjunto poliédrico como:
Nota:
 Las desigualdades que pueden eliminarse sin modificar el poliedro se
conoce como desigualdades redundantes
 Un conjunto de puntos del poliedro que pertenece a uno o más de los
hiperplanos que definen el poliedro se dice que es una cara del poliedro
(vértice-arista)
 Un cono poliédrico es un poliedro formado por semi-espacios cuyos
hiperplanos pasan por el origen.
 Un poliedro acotado es un politopo.
 Cualquier poliedro puede admitir, gracias a la existencia de restricciones
redundantes, infinitas representaciones.
 Como ejemplo, considere el conjunto poliédrico definido por las
siguientes desigualdades:
 PUNTOS EXTREMOS, CARAS, DIRECCIONES Y DIRECCIONES
EXTREMAS DE CONJUNTOS POLIÉDRICOS: PERSPECTIVA
GEOMÉTRICA

Puntos extremos

 Sean los (m+n) hiperplanos definidos por los semiespacios de X, llamados de

hiperplanos de definición de X. Si la matriz A correspondiente es de rango
completo entonces esos hiperplanos son LI. Entonces un punto x es un punto
extremo si pertenece (está en la intersección) a n hiperplanos de definición de
X. Si más de n hiperplanos pasan por entonces el punto extremo es llamado de
degenerado. Los hiperplanos en exceso a n indica el orden de degeneración del
punto extremo.

Proposición. Dado , A una matriz mxn, un punto es un punto extremo si y

solo si existen “n” hiperplanos en la descripción de S, que pasan por y son
linealmente independientes.
Definición: Un punto extremo
es degenerado cuando el
número de hiperplanos que
pasa por el es superior a “n”.
en R2 los puntos extremos de
los poliedros se obtienen como
intersección de dos hiperplanos
linealmente independientes.
Los puntos extremos
degenerados se obtienen como
intersección de 3 o más planos.

Nota: la degeneración no necesariamente implica la existencia de desigualdades redundantes.

 Teorema de Caracterización de Puntos Extremos
 
Dado un poliedro en donde A es una matriz mxn de rango
completo y es un punto extremo de S si y sólo si es posible
descomponer la matriz A en dos submatrices de modo que

Donde B es una matriz no singular mxm y

Caras, Aristas y Puntos Extremos Adyacentes

 
Cara Propia de X:

Es un conjunto de puntos de X que pertenecen a un conjunto no vacío

de hiperplanos activos. Sea r(F) el número máximo de hiperplanos LI
activos en todos los puntos de la cara F, entonces se define la
dimensión de F de la siguiente forma:

En otras palabras, cada hiperplano activo LI produce la pérdida de un

grado de libertad.
 Consecuencias:
1. Un punto extremo es una cara propia de dimensión cero porque tiene 1
hiperplanos activos LI.
2. Una arista es una cara propia de dimensión 1 porque tiene (n-1)
hiperplanos activos LI. Así, una arista es una cara propia de un grado de
libertad porque tiene solamente (n-1) hiperplanos activos LI (un
hiperplano menos que un punto extremo). Por lo tanto, una arista es un
conjunto de puntos que tienen (n-1) hiperplanos activos LI, o sea, todos
los puntos de una arista tienen la siguiente característica: en todos los
puntos de una arista existen (n-1) hiperplanos activos LI.
3. , entonces es de dimensión completa porque en este caso tenemos el
conjunto completo X y debe existir por lo menos un punto en el cual
ningún hiperplano está activo (un punto interior del conjunto poliedral).
Así, el conjunto X y el conjunto vacío son llamados caras impropias de
X.
4. La cara propia de mayor dimensión, es:

es llamado cara de X.
 
Puntos extremos adyacentes: Dos puntos extremos de X son llamados
adyacentes si el segmento de recta que los une es una arista. Así, los puntos
extremos adyacentes tienen (n-1) hiperplanos activos LI comunes.
Direcciones Extremas de un Conjunto Poliedral

 Las direcciones de un conjunto poliedral X

son dadas por los vectores que satisfacen la relación:

Geométricamente, este conjunto puede ser encontrado simplemente

trasladando todos los hiperplanos, que definen X, paralelamente a sí
mismos hasta llegar al origen. Recuerde la semejanza
 

 
 Para evitar duplicación en representar direcciones se puede normalizar los
vectores d usando la siguiente norma:

 
como todos los elementos de entonces la norma se resume a:

 
Así, el conjunto de vectores que son direcciones de X asumen la siguiente
forma:
 

 
y lógicamente:

 
Propiedad importante: Los puntos extremos de d son direcciones extremas de
X.
 Ejemplo:Encontrar el conjunto D y las direcciones
extremas de X en el siguiente problema:
 
TEOREMA DE REPRESENTACIÓN INTERNA

 Sea , . Sea , entonces cualquier punto puede expresarse de la

siguiente forma
 Ejemplo. Sea . Obtener un punto extremo a partir del punto de asociado a
Inicio: Agregar variables de holgura:
 Primera desigualdad

Segunda desigualdad

Ahora tenemos dos problemas

Problema (P)

Problema (P’)
  Hallar y en (P’)

 Ya que

Observemos qué y tiene cuatro componentes positivas, a

lo más deberían ser dos, por tanto, procedemos a realizar
las iteraciones correspondientes.
 Iteración 1

Paso 1: Hallar vector

Las columnas de A son LD.

 
Por lo tanto no todos nulos, tal que: . Es decir

 
Resultado
   Paso 2: Hallar
  Hacemos

X’

En Ec.2
1 1 1/1 = 1
4 0 -
5 1 5/1 = 5
5 -1 -

  1 5
∴ 𝜶 = 𝐦𝐢𝐧
1≤ 𝒋 ≤ 𝒌
{ }
, =1
1 1
 Paso 3: Hallar las coordenadas del nuevo punto x’ haciendo:

Paso 4: x’ cumple con

Paso 5: x’ no tiene a lo más dos componentes

positivas.
 Iteración 2

Paso 1: Hallar vector (considerar la columna de A

asociada a )

 
De aquí resulta
   Paso 2: Hallar
 Hacemos

X’
Sustituyendo en Ec.2 0 0 -
4
0 1
0 4/1=4
-
4 2
1 4/2=2
4/1=4
6
4 2 6/2=3
4/2=2
6 2 6/2=3

  4 4 6
∴ 𝜶 = 𝐦𝐢𝐧
1≤ 𝒋 ≤ 𝒌
{ }
, , =2
1 2 2
   Paso 3: Hallar las coordenadas del nuevo punto x’
haciendo
:
′
 
  𝒙 𝒋= 𝒙 𝒋 − 𝜶 𝝀 𝒋
𝒙 ′𝟏=𝟎 − 𝟐 ( 𝟎 ) =𝟎 𝟎

𝒙′𝟑 = 𝟒 − 𝟐 ( 𝟐 ) = 𝟎
′
𝒙 𝟒= 𝟔 − 𝟐 ( 𝟐 ) = 𝟐
[]
𝒙 ′𝟐= 𝟒 − 𝟐 ( 𝟏 ) = 𝟐 ⇒ 𝒙 = 𝟐
′

𝟎
𝟐

  Paso 4: x’ cumple con

Paso 5: el nuevo x’ tiene a lo más dos componentes positivas.

STOP