Intorduccon A La Programacion Lineal

intorduccon a la programacion lineal

La programación lineal se aplica a modelos de optimización en los que las funciones objetivo y

restricción son estrictamente lineales. La técnica se aplica en una amplia variedad de casos, en

los campos de agricultura, industria, transporte, economía, salud, ciencias sociales y de la conducta,

y militar. También produce algoritmos eficientes de cómputo para problemas con miles

de restricciones y variables. En realidad, debido a su tremenda eficiencia de cálculo, la programación

lineal forma la columna vertebral de los algoritmos de solución para otros modelos de

investigación de operaciones, como las programaciones entera, estocástica y no lineal.

Este capítulo comienza con el caso de un modelo de dos variables, y presenta su solución

gráfica. Esta solución gráfica permite tener una perspectiva del desarrollo del método

símplex, técnica algebraica general (véase el capítulo 3). También presenta ideas concretas

para el desarrollo y la interpretación de análisis de sensibilidad en programación lineal. El capítulo

termina con la formulación y la interpretación de la solución de varias aplicaciones realistas.

2.1 MODELO DE PROGRAMACIÓN LINEAL CON DOS VARIABLES

Esta sección explicará la solución gráfica de una programación lineal con dos variables. Aunque

en la práctica casi no existen problemas con dos variables, la presentación aportará ideas concretas

para el desarrollo del algoritmo de solución general que se presentará en el capítulo 3.

12 Capítulo 2 Introducción a la programación lineal

Ejemplo 2.1-1 (La compañía Reddy Mikks)

Reddy Mikks produce pinturas para interiores y exteriores, M1 y M2. La tabla siguiente proporciona

los datos básicos del problema.

Ton de materia prima de

Pinturas para Pinturas para Disponibilidad diaria

exteriores interiores máxima (ton)

Materia prima,M1 6 4 24

Materia prima,M2 1 2 6

Utilidad por ton (miles de $) 5 4

Una encuesta de mercado indica que la demanda diaria de pintura para interiores no puede

ser mayor que 1 tonelada más que la de pintura para exteriores. También, que la demanda

máxima diaria de pintura para interiores es de 2 toneladas.

Reddy Mikks desea determinar la mezcla óptima (la mejor) de productos para exteriores

y para interiores que maximice la utilidad diaria total.

El modelo de programación lineal, como en cualquier modelo de investigación de operaciones,

tiene tres componentes básicos.

1. Las variables de decisión que se trata de determinar.

2. El objetivo (la meta) que se trata de optimizar.

3. Las restricciones que se deben satisfacer.

La definición correcta de las variables de decisión es un primer paso esencial en el desarrollo

del modelo. Una vez hecha, la tarea de construir la función objetivo y las restricciones se hace

en forma más directa.

Para el problema de Reddy Mikks, se necesita determinar las cantidades a producir de

pinturas para exteriores e interiores. Así, las variables del modelo se definen como sigue:

x1 = Toneladas producidas diariamente, de pintura para exteriores

x2 = Toneladas producidas diariamente, de pintura para interiores

Para formar la función objetivo, la empresa desea aumentar sus utilidades todo lo posible. Si

z representa la utilidad diaria total (en miles de dólares), el objetivo de la empresa se expresa así:

Maximizar z = 5x1 + 4x2

A continuación se definen las restricciones que limitan el uso de las materias primas y la

demanda. Las restricciones en materias primas se expresan verbalmente como sigue:

Según los datos del problema,

Uso de la materia prima M1, por día = 6x1 + 4x2 toneladas

Uso de la materia prima M2, por día = 1x1 + 2x2 toneladas

Ya que la disponibilidad de las materias primas M1 y M2 se limita a 24 y 6 toneladas, respectivamente,

las restricciones correspondientes se expresan como sigue:

a

Uso de una materia prima

para ambas pinturas b … a

Disponibilidad máxima

de materia prima b

2.1 Modelo de programación lineal con dos variables 13

6x1 + 4x2 ≤ 24 (Materia prima M1)

x1 + 2x2 ≤6 (Materia prima M2)

La primera restricción de la demanda indica que la diferencia entre la producción diaria de

pinturas para interiores y exteriores, , no debe ser mayor que 1 tonelada, y eso se traduce

en . La segunda restricción de la demanda estipula que la demanda máxima

diaria de pintura para interiores se limita a 2 toneladas, y eso se traduce como .

Una restricción implícita (o “que se sobreentiende”) es que las variables y no pueden

asumir valores negativos. Las restricciones de no negatividad, , , expresan ese

requisito.

El modelo de Reddy Mikks completo es

sujeta a

Cualquier valor de y que satisfaga todas las restricciones del modelo es una solución

factible. Por ejemplo, la solución toneladas diarias y tonelada diaria es factible,

porque no viola alguna de las restricciones, incluyendo las de no negatividad. Para comprobar

este resultado se sustituye en el lado izquierdo de cada restricción.

Por ejemplo, en la primera restricción, , que es menor

que 24 en el lado derecho. El valor de la función objetivo correspondiente a la solución

es (miles de dólares).

Desde el punto de vista de todo el modelo, nos interesa determinar la solución óptima

factible que produzca la utilidad total máxima y al mismo tiempo satisfaga todas las restricciones.

No se acepta enumerar las soluciones factibles, porque el modelo tiene una cantidad

infinita de ellas. En su lugar, se necesita un procedimiento sistemático que ubique con eficiencia

la solución óptima. El método gráfico de la sección 2.3, y su generalización algebraica en

el capítulo 3, resuelven este punto.

En el ejemplo anterior, las funciones objetivo y restricciones son lineales, todas. La linealidad

implica que la programación lineal debe satisfacer dos propiedades: proporcionalidad y

aditividad.

1. La proporcionalidad requiere que la contribución de cada variable de decisión en la

función objetivo, y sus requerimientos en las restricciones, sea directamente proporcional al

valor de la variable. Por ejemplo, en el modelo de Reddy Mikks, las cantidades 5x1 y 4x2 expresan

las utilidades por producir x1

...