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

...