ciencias

Investigación de Operaciones I

Programación lineal

Programación Lineal
1.
2.
3.
4.
5.
6.
7.

Se presenta a continuación, parte de esta entrevista:

Introducción.
Definición.
Supuestos y limitaciones.
Modelo matemático.
Transformaciones.
Formatos Canónico y Estándar.
Construcción de modelos de PL.

"Considere el problema de asignar 70 hombres a 70
empleos. Una'actividad' consiste en asignar el iésimo
hombre al j-ésimo empleo. Las restricciones son dos:
en primer lugar hay 70 hombres, cada uno de los cuales
debe asignarse a un puesto, y en segundo lugar, cada
uno de los 70 puestos existentes debe estar ocupado.
El nivel de una actividad puede ser 1, lo cual indica que
está siendo usada, o 0, lo cual significa que no. En
consecuencia hay 2 x 70 =140restricciones y 70 x 70
=
4900
actividades
con
4900
variables
correspondientes de decisión uno-cero. Por desgracia
también hay factorial de 70 permutaciones o formas
de hacer las asignaciones. El problema consiste en
comparar éste factorial de 70 formas y elegir la que
sea la óptima o 'mejor' según algún criterio
previamente establecido."

Introducción.
"Los
que
mandan
generalmentemueven
las
manos
y
dicen
'He
considerado
todas
las
alternativas'. Pero eso es
casi siempre basura. Lo más
probable es que no pudiesen
estudiar
todas
las
combinaciones."

"En el ejemplo anterior, factorial de 70 es un número
muy grande. A fin de tener una idea de qué tan grande
es, supóngase que se hubiese tenido una computadora
IBM del tipo main-frame en el instante en el queocurrió el Big Bang hace quince millones de años.
¿Habría podido, entre ese entonces y ahora, examinar

George B. Dantzig , el creador de la programación
lineal, en una entrevista publicada en The College
Mathematical Journal, marzo de 1986.

37

MCIA. Jaime Delgado Ochoa

Investigación de Operaciones I

Programación lineal

todas las soluciones posibles? ¡No! No obstante,supóngase que se hubiese tenido una computadora aun
más poderosa, una que pudiese examinar mil millones
de asignaciones por segundo. La respuesta seguiría
siendo negativa. Aun si la Tierra se llenase con
computadoras
cuyas
rapideces
fueran
de
nanosegundos, todas ellas trabajando en paralelo, la
respuesta aun sería no. Sin embargo, si existiesen diez
Tierras, todas llenas con computadoras deltipo
mencionado, todas programadas en paralelo desde el
instante del Big Bang hasta que el Sol fuese una esfera
fría, entonces quizás la respuesta podría ser sí. Lo
notable es que el método Simplex, con la ayuda de una
computadora moderna, puede resolver este problema
en una fracción de segundo" .

alguna relación directa entre la meta establecida y las
acciones emprendidas para talfin."
"Si se estudiaba con cuidado el paso siguiente, se podía
ver que algún líder había promulgado un montón de
reglas básicas que, en su concepto, llevarían a la meta.
Esto distaba mucho de lo que sería honestamente
estudiar todas las combinaciones alternativas de las
acciones a seguir para elegir la mejor combinación. Los
que mandan generalmente mueven las manos y dicen
'He consideradotodas las alternativas'. Pero eso es
casi siempre basura. Lo más probable es que no
pudiesen estudiar todas las combinaciones. Antes de
1947 era inconcebible pensar en la existencia de una
herramienta como la programación lineal que
permitiese examinar millones de combinaciones. No
había algoritmo o herramienta computacional que
pudiera hacer eso".

"Cuando el problema de la planeación fueformulado
inicialmente para la Fuerza Aérea, no existía la noción
exacta de una función objetivo, la idea de una meta
claramente definida. Por supuesto, teníamos sólo un
falso respeto hacia el concepto de objetivo. En el
discurso de los militares escuché a menudo decir,
'nuestro objetivo es ganar la guerra'. En el mundo de
los negocios se escucharía quizás 'nuestro objetivo es
obtener...