Programacion Lineal

UNIVERSIDAD AUSTRAL DE CHILE
FACULTAD DE CIENCIAS DE LA INGENIERIA
INSTITUTO DE INFORMATICA

PROGRAMACION
LINEAL

Modelos y Soluciones
Computacionales
Cuarta edición

Wladimir Ríos Martínez
Miguelina Vega Rosales
2008

Aspectos Teóricos

2

INDICE

INTRODUCCION

3

CAPITULO 1
ASPECTOS TEORICOS Y FORMULACION DE PROGRAMAS LINEALES
1.1 INTRODUCCION

6

1.2 EL MODELOMATEMATICO

7

1.3 ANALISIS GRAFICO

9

1.4 MODELOS BASICOS DE PROGRAMACION LINEAL

11

1.4.1 Modelo de Mezcla de Productos

12

1.4.2 Modelo de Selección de Procesos

13

1.4.3 Modelo de Proceso de Multifase

16

1.4.4 Problema de Transporte y Asignación

19

1.4.4.1 Problema de Transporte Generalizado

20

1.4.4.2 Problema de Transporte con Nodos Intermedios20

1.4.4.3 Problema de Asignación

22

1.4.5 Problemas de Programación Entera
1.4.6 Problemas de Redes de Optimización

24
24

1.4.6.1 Problema de Flujo Máximo

25

1.4.6.2 Problema de Costo Mínimo

26

1.4.6.3 Problema de Flujo Máximo a Costo Mínimo

27

1.4.6.4 Problemas de Programación de Actividades

28

1.5 PROBLEMAS PROPUESTOS

30

1.6 BIBLIOGRAFIA

53INTRODUCCION

W. Ríos – M. Vega

Aspectos Teóricos

3

Los sistemas desarrollados por el hombre, sean éstos físicos (fábricas, aeropuertos, etc.) o sociales
(organizaciones empresariales, instituciones, etc.) se han hecho cada vez más complejos, son tantas
las variables de decisión y las combinaciones entre éstas que es necesario manejar para que el
sistema permanezca y se desarrolle,que se ha hecho necesario utilizar herramientas de tipo
cuantitativo de apoyo a la toma de decisiones, reduciendo el campo de acción de las decisiones de
carácter intuitivo.
Sumado a lo anterior, la creciente escasez de recursos para satisfacer las necesidades de la población
a nivel mundial, ha exigido que las empresas utilicen en forma óptima estos recursos.
La Investigación de Operaciones(IO) y el Análisis de Sistemas (AS) son parte importante de la
respuesta a la complejidad de los sistemas y la necesidad de ir a la optimización de su
funcionamiento.
La característica principal de éstos enfoques es su naturaleza integradora o Enfoque de Sistemas.
Esto significa que, definido el alcance de cierto sistema, el énfasis se pone en el estudio de cada
componente específica(análisis), y posteriormente en el conjunto de interacciones entre éstas
componentes (síntesis).
Churchmann, Ackoff y Arnoff la definen como:
La Investigación de Operaciones es la aplicación, por grupos interdisciplinarios, del método
científico a problemas relacionados con el control de las organizaciones o sistemas (hombremáquina) a fin de que se produzcan soluciones que mejor sirvan a losobjetivos de toda la
organización.
La Investigación de Operaciones se utiliza en tres tipos de problemas:
a)

Problemas determinísticos: Cada alternativa (hay más de dos) tiene una y solo una
solución. Como hay varias alternativas, hay también varias soluciones, cada una con
diferente eficiencia y/o efectividad asociada a los objetivos del sistema. Por lo tanto, existe
el problema de decisión.b)

Problemas con riesgo: Cada alternativa del problema (hay más de dos), tiene varias
soluciones. Cada solución puede ocurrir con una cierta probabilidad. La distribución de estas
probabilidades se conoce o se puede estimar.

c)

Problemas bajo incertidumbre: Cada alternativa del problema (hay más de dos), tiene varias
soluciones. Sin embargo, se ignora con que probabilidad odistribución probabilistica
ocurrirán estas soluciones.
Ackoff establece una serie de etapas que se muestran en la siguiente figura, que son necesarias
para enfrentar un problema en una Organización y solucionarlo a través de técnicas de
Investigación de Operaciones.

W. Ríos – M. Vega

Aspectos Teóricos

4

Etapas en el diseño de sistemas complejos, según Ackoff

1.

Estudio de la...