Prog Lineal

PROGRAMACIÓN LINEAL

INVESTIGACIÓN DE OPERACIONES

Ing. César Canelo Sotelo


La programación lineal es una técnica de optimización que consiste en la maximización o minimización de una función lineal llamada función objetivo, sujeta a restricciones también lineales.

La programación lineal es una herramienta para resolver problemas de optimización.


Un problema de programación lineal es un problema de optimización para el cual se efectúa lo siguiente:

1) Se intenta maximizar (minimizar) una función lineal de las variables de decisión. La función que se desea maximizar o minimizar se llama función objetivo.

2) Los valores de las variables de decisión deben satisfacer un conjunto de restricciones. Cada restricción debe ser una ecuación lineal o una desigualdad lineal.

3) Se relaciona una restricción de signo con cada variable. Para cualquier variable xi, la restricción de signo especifica que xi no debe ser negativa (xi>=0) o ser sin restricción de signo (SRS).

EL MODELO DE PROGRAMACIÓN LINEAL

El modelo de programación lineal esta conformado por:

1. Un conjunto de variables de decisión.

2. Una función objetivo.3. Un conjunto de restricciones:

a) Restricciones estructurales. b) Restricciones de no negatividad

de las variables.

FORMA GENERAL DEL MODELO DE PROGRAMACIÓN LINEAL

Max o Min Z = c x sujeto a: <=

A x = b >= No negatividad: x >= 0

EL MODELO DE PROGRAMACIÓN LINEAL

Z: Función objetivo.c: Vector fila de n elementos. Es el vector de

coeficientes de las variables en la función objetivo.

x: Vector columna de n elementos. Es el vector de variables de decisión del modelo.

A: Matriz mxn. Los elementos de la matriz A son los coeficientes de las variables en el lado izquierdo de las restricciones.

b: Vector columna de m elementos. Es el vector de constantes de los lados derecho de las restricciones.

FORMA GENERAL DESARROLLADA DEL MODELO DE PROGRAMACIÓN LINEAL

Max o Min Z = c1x1 + c2x2 + … + cnxn

s. a. : a11x1 + a12x2 + . . . + a1nxn <= b1

a21x1 + a22x2 + . . . + a2nxn = b2

. . . . . . . . . . . . … am1x1 + am2x2 + . . . + amnxn >= bm

xj >= 0 j=1, 2, … , n

FORMA CANÓNICA DEL MODELO DE PROGRAMACIÓN LINEAL

Max Z = cx s. a. : Ax <= b x >= 0

FORMA ESTÁNDAR DEL MODELO DE PROGRAMACIÓN LINEAL

Max Z = cx s. a. : Ax = b x >= 0

FORMA MIXTA DEL MODELO DE PROGRAMACIÓN LINEAL

Max Z o Min Z = cx s. a. : <= Ax >= b x >= 0

SUPOSICIONES DE LA PROGRAMACIÓN LINEAL

UNA SOLA FUNCIÓN OBJETIVOTodo modelo de programación lineal tiene una sola función objetivo: maximización o minimización.


SUPOSICIÓN DE PROPORCIONALIDADEsta suposición se cumple tanto en la función objetivo como en las restricciones.1) La contribución a la función objetivo de cada variable de decisión, es proporcional al valor de la variable.

2) La contribución de cada variable al primer miembro de cada restricción, es proporcional al valor de la variable.


SUPOSICIÓN DE ADITIVIDADEsta suposición también se cumple tanto en la función objetivo como en las restricciones. Tanto en la función objetivo como en las restricciones, no se puede dar el producto cruzado de dos o más variables.

1) La contribución a la función objetivo para cualquier variable, es independiente de los valores de las otras variables de decisión.

2) La contribución de una variable al primer miembro de cada restricción, es independiente de los valores de la variable.


SUPOSICIÓN DE DIVISIBILIDADEsta suposición requiere que todas las variables de decisión puedan asumir valores fraccionarios. Un problema de PL en el cual algunas de las variables, o todas, debe ser un número entero no negativo, recibe el nombre de problema de programación lineal entera. En muchas situaciones donde la divisibilidad no está presente, el redondeo de las variables a un entero, en la solución óptima de PL, proporciona una solución razonable.


SUPOSICIÓN DE CERTIDUMBREPor esta suposición se requiere conocer con certeza todos los parámetros del modelo de programación lineal: coeficientes en la función objetivo (cj), coeficientes tecnológicos (aij) y segundo miembro de las restricciones (bi). Para que un modelo de programación lineal represente en forma adecuada una situación de la vida cotidiana, éste debe cumplir todas las suposiciones de la programación lineal.

FORMULACIÓN DE MODELOS DE PROGRAMACIÓN LINEAL

No existe una fórmula general que se pueda usar para formular el modelo de todo problema lineal. Para la formulación del modelo de programación lineal de un problema se siguen ciertos pasos y técnicas que ilustraremos considerando el problema que enfrenta la gerencia de Química S.A.

EJEMPLO DE UN PROBLEMA DE PROGRAMACIÓN LINEAL

Química S.A. produce dos solventes, CS-01 y CS-02, en su planta de producción. El proceso de producción de los solventes consta de mezclado y purificación. El departamento de mezclado emplea a 5 trabajadores a tiempo completo que trabajan 40 horas a la semana y 2 a tiempo parcial, que trabajan 15 horas a la semana. Estas personas operan las 7 máquinas que mezclan ciertos químicos para producir cada solvente. Los productos salen del departamento de mezclado para ser refinados en el departamento de purificación, que actualmente tiene 7 purificadores y emplea a 6 trabajadores de tiempo completo que trabajan 40 horas a la semana y a uno de tiempo parcial que trabaja 10 horas a la semana. Se tienen los siguientes datos de requerimiento de tiempo de proceso de los solventes en ambos departamentos:

Horas por miles de galones de CS-01 CS-02 Mezclado 2 1 Purificación 1 2

Química S.A. tiene una provisión casi ilimitada de la materia prima que necesita para producir los dos solventes. Química S.A. puede vender toda la cantidad producida de CS-01, pero la demanda del producto más especializado, el CS-02, está limitada a lo más a 120,000 galones por semana. El departamento de contabilidad asigna un margen de ganancia de $0.30 por galón de CS-01 y de $0.50 por galón de CS-02. El gerente de producción requiere determinar el plan de producción semanal óptimo para Química S.A. ¿ Qué cantidad de cada solvente debe producir Química S.A. para maximizar la ganancia?

FORMULACIÓN DEL MODELO DE PROGRAMACIÓN LINEAL

El objetivo ahora es convertir la descripción cualitativa del problema a un modelo matemático que pueda resolverse. Este proceso se llama formulación del modelo de programación lineal y generalmente implica cuatro pasos.


1. IDENTIFICACIÓN DE LAS VARIABLES DE DECISIÓN

El primer paso en la formulación del modelo es identificar las variables de decisión. Los valores de estas variables, una vez determinados, proporcionan la solución al problema. Para el problema en estudio, se puede identificar las variables de decisión preguntándonos qué información se necesita proporcionar al personal del departamento de producción, para que sepan cómo proceder. La respuesta a esta pregunta debería ser:

La cantidad de miles de galones de CS-01 por producir semanalmente.La cantidad de miles de galones de CS-02 por producir semanalmente.

Como los valores de estos elementos no se conocen todavía, a cada variable de decisión se le da un nombre simbólico cualquiera. Esto equivale a la definición de las variables. Para este ejemplo, se podrían definir las siguientes variables:

X1 = Número de miles de galones de CS-01 por producir semanalmente.X2 = Número de miles de galones de CS-02 por producir semanalmente.

Obsérvese que la definición de las variables deben ser precisas, es decir que su definición deben incluir las unidades asociadas con las cantidades que las variables representan.


La necesidad de identificar las variables de decisión correctamente es vital. De otra manera, la formulación de un modelo válido que capte todos los aspectos del problema es imposible. La definición de las variables no es única, y no existen reglas fijas, sin embargo son útiles las siguientes pautas para la adecuada identificación de las variables de decisión.

¿ Qué valores, una vez determinados, constituyen una solución para el problema ?

¿ Qué elementos se pueden elegir y/o controlar libremente ?

¿ Qué elementos afectan los costos y/o ganancias o, en general, el

objetivo global ?

¿ Qué decisiones se tienen que tomar ?

Para el ejemplo, las respuestas a todas estas preguntas son iguales y llevan a la identificación de las variables de decisión.


2. IDENTIFICACIÓN DE LOS DATOS DEL PROBLEMA

La finalidad de resolver un problema es proporcionar los valores reales a las variables de decisión que se han identificado. Se requiere conocer cierta información para ayudar a determinar esos valores. Por ejemplo, para determinar las cantidades reales de los dos solventes a producir para maximizar las ganancias, se necesitará saber:

1) El número de horas de trabajo disponibles en el departamento de mezclado.

2) El número de horas de trabajo disponibles en el departamento de purificación.

3) La cantidad de ganancias obtenidas al producir y vender cada tipo de solvente.


Estas cantidades constituyen los datos del problema. Estos valores son necesarios para formular el problema. Para el ejemplo, se tienen los siguientes datos: 1) El departamento de mezclado tiene cinco trabajadores a tiempo completo (40 horas cada uno) y dos trabajadores a tiempo parcial (15 horas cada uno). Esto da un total de 230 horas de trabajo a la semana en el departamento de mezclado. 2) De manera similar, los seis trabajadores de tiempo completo (40 horas cada uno) y el trabajador a tiempo parcial (10 horas) representan un total de 250 horas de trabajo a la semana en el departamento de purificación. 3) Se tiene el dato de un margen de ganancia de $0.30 por galón de CS-01 y de $0.50 por galón de CS-02, esto es, $300 por mil galones de CS- 01 y $500 por mil galones de CS-02. A diferencia de las variables de decisión, cuyos valores se pueden controlar, los valores de los datos son constantes y no se pueden controlar.


3. IDENTIFICACIÓN DE LA FUNCIÓN OBJETIVO En este paso de la formulación, se debe expresar el objetivo

organizacional global en forma matemática usando las variables de decisión y los datos conocidos del problema. La función objetivo, generalmente se formula en dos etapas:

Establecer el objetivo en forma verbal. Para el ejemplo, este objetivo es: Maximizar la ganancia semanal total de la producción de CS-01 y CS-02.

Cuando sea apropiado, descomponer el objetivo en una suma, diferencia o producto de cantidades individuales, usando las variables de decisión y otros datos del problema conocidos. Para el ejemplo, la ganancia total puede calcularse como la suma de la ganancia de CS-01 y la de CS-02:

Maximizar ganancia= (ganancia de CS-01) + (ganancia de CS-02)


4. IDENTIFICACIÓN DE LAS RESTRICCIONES

En este ejemplo, el objetivo es maximizar las ganancias. La función objetivo planteada dice que mientras más grande sea el valor de las variables, más grande será la ganancia. Pero el mundo real pone un límite en los valores que puede asignar a estas variables. En el ejemplo, los departamentos de mezclado y purificación tienen ciertas restricciones físicas: un número limitado de horas de trabajo disponible cada uno. Estas limitaciones, así como otras consideraciones que imponen restricciones sobre los valores de las variables, son las restricciones. Se tiene que identificar cada restricción y escribirlas en forma matemática.


Las restricciones son condiciones que las variables de decisión deben satisfacer para constituir una solución “aceptable”. Las restricciones por lo general surgen de:

Limitaciones físicas (el número limitado de horas de trabajo en los departamentos de mezclado y purificación, por ejemplo). Restricciones impuestas por la administración ( por ejemplo, ésta pudo haber prometido una cierta cantidad de un producto a un cliente especial). Restricciones externas (por ejemplo, esta empresa no puede vender más de 120 mil galones de CS-02 a la semana, y no hay razón para producir más que la cantidad demandada).

Relaciones implicadas entre variables. Restricciones lógicas (no negatividad) sobre variables individuales (en este ejemplo, no se puede producir una cantidad negativa de solventes).


En conclusión, la aplicación de los pasos y técnicas ilustrados, dan como resultado el siguiente modelo de programación lineal para el problema de Química S.A.

VARIABLES:X1 = Número de miles de galones de CS-01 por producir semanalmente.X2 = Número de miles de galones de CS-02 por producir semanalmente. FUNCIÓN OBJETIVO:

Max Z = 300X1 + 500X2 Maximización de ganancias. SUJETO A:2X1 + 1X2 <= 230 Horas disponibles en el dpto. mezclado.1X1 + 2X2 <= 250 Horas disponibles en el dpto. purificación. X2 <= 120 Límite máximo de CS-02No negatividad: X1, X2 >= 0

G R A C I A S

Documents

Prog Lineal