programacion lineal

Universidad de Manizales
INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL

JULIAN GONZÁLEZ LÓPEZ
ALVARO SALAS SALAS

UNIVERSIDAD DE MANIZALES

INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL

JULIÁN GONZÁLEZ LÓPEZ
Profesor Asociado
Universidad de Manizales –Departamento de Matemáticas
Universidad de Caldas - Facultad de Ciencias Exactas y Naturales
Departamento de Matemáticas
ALVARO SALAS SALASProfesor Auxiliar
Universidad de Caldas - Facultad de Ciencias Exactas y Naturales
Departamento de Matemáticas

Manizales, Octubre de 2000

UNIVERSIDAD DE MANIZALES

4

INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL

TABLA DE CONTENIDO

CAPÍTULO I. PROGRAMACIÓN LINEAL.

INTRODUCCIÓN

1

1.1. Modelos de programación lineal
1.1.1. Forma matricial del modelo de programación lineal
1.1.2.Forma estándar de un modelo de programación lineal

3
4
4

1.2. Formulación de modelos de programación lineal
Ejercicios propuestos

8
20

CAPÍTULO II. MÉTODO GRÁFICO PARA RESOLVER MODELOS DE
PROGRAMACIÓN LINEAL CON DOS VARIABLES DE DECISIÓN.
INTRODUCCIÓN

23

2.1. Método gráfico para el caso de dos variables de decisión
2.1.1. Graficación de un sistema de desigualdades
2.1.2.Isocuantas de la función objetivo
Ejercicios propuestos

23
24
27
32

5

UNIVERSIDAD DE MANIZALES

CAPÍTULO III. MÉTODO SÍMPLEX.
INTRODUCCIÓN

35

3.1. Preparación para el método símplex
3.1.1. Variables de holgura
3.2. Forma algebraica del método símplex
3.3. Forma tabular del método símplex
3.4. Método símplex usando la técnica M (método de penalización)
Ejerciciospropuestos

37

HOJA DE RESPUESTAS

73

BIBLIOGRAFIA

76

6

41
56
67
71

INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL

PRESENTACIÓN
La Investigación de Operaciones y en particular una de sus áreas “la programación lineal” ha
tenido bastante difusión y aplicación en los últimos años. La necesidad de asignar en forma
óptima, entre diversas actividades, recursos en general escasos como;dinero, mano de obra,
energía, materia prima y muchos otros factores limitados; es importante para el profesional
que en su ejercicio diario requiere tomar decisiones.
La “programación matemática” dentro de la cual se encuentran los modelos de programación
lineal difiere de los métodos de optimización clásica, ya que enfrenta problemas donde las
limitaciones o restricciones se expresan comodesigualdades, lo que le imprime mayor realismo a los modelos; en estos casos los métodos clásicos basados en el cálculo no funcionan.
Este libro presenta de una manera sencilla, los conceptos básicos de la programación lineal y
algunas de sus múltiples aplicaciones; va dirigido a estudiantes de las ciencias económicoadministrativas y solo requiere de parte del lector conocimientos básicos deálgebra matricial.
En el capítulo I se exponen los modelos de programación lineal y la solución de problemas
cuyo planteamiento conduce a este tipo de modelos. El capítulo II presenta la solución de
modelos de programación lineal con dos variables de decisión a través del método gráfico.
El capítulo III desarrolla el algoritmo simplex inicialmente en forma algebraica con lo cual se
busca una mejorcomprensión de éste por parte del estudiante y posteriormente en su forma
tabular más eficiente desde el punto de vista computacional.
El capítulo IV muestra la implementación del algoritmo simplex en la plataforma del paquete
MATHEMATICA a través de un programa interactivo, el cual permite además analizar los
casos especiales que se presentan en estos modelos tales como; modelos sin solución,con
soluciones óptimas alternativas y no acotados, se proporcionan también los criterios para
detectar en el desarrollo del algoritmo la presencia de éstas situaciones.
Agradecemos a nuestros lectores sus sugerencias y comentarios a fin de mejorar este material en futuras ediciones.

JULIAN GONZALEZ LOPEZ
ALVARO SALAS SALAS
Manizales, septiembre de 2000
7

UNIVERSIDAD DE MANIZALES...