Page 114 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 114
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
Figura 5.2. Región factible acotada
En la figura 5.2, los vértices extremos que producen un espacio factible son V V y V y V . Si se
A, C E F
hallan los valores de la función objetivo en cada uno de los vértices,
La solución es única y corresponde al vértice para el que la función objetivo toma el valor máximo.
En este caso es el Por tanto se deben construir 21 casas de tipo A y 58 de tipo B con un coste de
261.4 millones de pesos. Se observará que el óptimo tiene valores fraccionarios, es decir, se tienen
que construir 21.7 casas del tipo A, aunque construir 0.7 casas suena ilógico. Por ello, construir 21 y
58 casas no garantiza plenamente que sea el óptimo, de esta forma se creó la programación entera.
regIóN factIBle acotada coN MúltIpleS SolucIoNeS
Esta situación surge cuando se tiene más de una solución dentro de la región factible que satisface
el conjunto de restricciones a las cuales está sujeto el problema de programación lineal, donde al
menos dos deben de ser soluciones adyacentes. Por ejemplo:
Maximizar la función Z = 4x + 2y
108
