Page 112 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 112
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
reStrIccIoNeS de acuerdo coN el proBleMa de prograMacIóN
Las restricciones se deben establecer de acuerdo con lo que se busca satisfacer en el problema que
se tiene en ese momento. Si buscamos maximizar los recursos dentro de un problema de progra-
mación lineal, el conjunto de restricciones debe ser de signo menor o igual; en caso de ser mayor o
igual se debe multiplicar por -1 para cambiarla por la restricción adecuada.
Si buscamos minimizar los recursos, los signos de las restricciones deben ser mayor o igual en todos
los casos; si una no está así, se debe multiplicar por -1 para establecerla de la manera adecuada.
De acuerdo con lo anterior, tenemos que una restricción representa una frontera, que es un concepto
geométrico, donde nosotros podemos obtener la ecuación de la frontera de restricción de cualquier
restricción al sustituir los signos ≤, ≥ por el signo igual.
En consecuencia, la forma de la ecuación de frontera de restricción es esta:
.
Las únicas que no van a obedecer lo anterior son las restricciones de no negatividad:
x > 0.
j
La solución óptima de cualquier problema de programación lineal se encuentra sobre la frontera de
la región factible, siendo una propiedad general.
regIoNeS
La región factible es un espacio convexo donde se satisfacen todas y cada una de las restricciones
a las cuales está sujeto nuestro problema de programación lineal.
Las restricciones en los problemas de programación lineal, debido a que son desigualdades lineales,
geométricamente representan hiperespacios, que son conjuntos convexos.
Debido a que la intersección de conjuntos convexos es convexa, la región factible resulta ser un
conjunto convexo y a su vez tiene la forma de un poliedro, la cual es una figura geométrica de caras
planas.
Si se tiene una región factible, que es de forma de poliedro y convexa, se puede garantizar lo si-
guiente:
• Se tiene el óptimo y este ocurre en al menos un punto extremo.
106
