EN QUE CONSISTE?

La Programación Lineal corresponde a un algoritmo a través del cual se resuelven situaciones reales en las que se pretende identificar y resolver dificultades para aumentar la productividad respecto a los recursos (principalmente los limitados y costosos), aumentando así los beneficios. El objetivo primordial de la Programación Lineal es optimizar, es decir, maximizar o minimizar funciones lineales en varias variables reales con restricciones lineales (sistemas de inecuaciones lineales), optimizando una función objetivo también lineal.

Los resultados y el proceso de optimización se convierten en un respaldo cuantitativo de las decisiones frente a las situaciones planteadas. Decisiones en las que sería importante tener en cuenta diversos criterios administrativos como:

-Los hechos
-La experiencia
-La intuición
-La autoridad  

¿COMO RESOLVER UN PROBLEMA MEDIANTE PROGRAMACIÓN LINEAL?

El primer paso para la resolución de un problema de programación lineal consiste en la identificación de los elementos básicos de un modelo matemático, estos son:

• Función Objetivo
• Variables
• Restricciones

El siguiente paso consiste en la determinación de los mismos, para lo cual proponemos seguir la siguiente metodología:

LA FUNCIÓN OBJETIVO

La función objetivo tiene una estrecha relación con la pregunta general que se desea responder. Si en un modelo resultasen distintas preguntas, la función objetivo se relacionaría con la pregunta del nivel superior, es decir, la pregunta fundamental. Así por ejemplo, si en una situación se desean minimizar los costos, es muy probable que la pregunta de mayor nivel sea la que se relacione con aumentar la utilidad en lugar de un interrogante que busque hallar la manera de disminuir los costos.

La función objetivo puede ser:

LAS VARIABLES DE DECISIÓN

Similar a la relación que existe entre objetivos específicos y objetivo general, se comportan las variables de decisión respecto a la función objetivo, puesto que estas se identifican partiendo de una serie de preguntas derivadas de la pregunta fundamental. Las variables de decisión, son en teoría, factores controlables del sistema que se está modelando, y como tal, estas pueden tomar diversos valores posibles, de los cuales se precisa conocer su valor óptimo, que contribuya con la consecución del objetivo de la función general del problema.

Las variables son números reales mayores o iguales a cero.

En caso que se requiera que el valor resultante de las variables sea un número entero, el procedimiento de resolución se denomina Programación entera.

LAS RESTRICCIONES

Cuando hablamos de las restricciones en un problema de programación lineal, nos referimos a todo aquello que limita la libertad de los valores que pueden tomar las variables de decisión. 

La mejor manera de hallarlas consiste en pensar en un caso hipotético en el que decidiéramos darle un valor infinito a nuestras variables de decisión, por ejemplo, ¿qué pasaría si en un problema que precisa maximizar sus utilidades en un sistema de producción de calzado decidiéramos producir una cantidad infinita de zapatos? Seguramente ahora nos surgirían múltiples interrogantes, como por ejemplo:

• ¿Con cuánta materia prima cuento para producirlos?
• ¿Con cuánta mano de obra cuento para fabricarlos?
• ¿Pueden las instalaciones de mi empresa albergar tal cantidad de producto?
• ¿Podría mi fuerza de mercadeo vender todos los zapatos?
• ¿Puedo financiar tal empresa?

Pues bueno, entonces habríamos descubierto que nuestro sistema presenta una serie de limitantes, tanto físicas, como de contexto, de tal manera que los valores que en un momento dado podrían tomar nuestras variables de decisión se encuentran condicionados por una serie de restricciones.

Las restricciones pueden ser de la forma:

Donde:

• A = valor conocido a ser respetado estrictamente;
• B = valor conocido que debe ser respetado o puede ser superado;
• C = valor conocido que no debe ser superado;
• j = número de la ecuación, variable de 1 a M (número total de restricciones);
• a; b; y, c = coeficientes técnicos conocidos;
• X = Incógnitas, de 1 a N;
• i = número de la incógnita, variable de 1 a N.

En general no hay restricciones en cuanto a los valores de N y M. Puede ser N = M; N > M; ó, N < M.

Sin embargo si las restricciones del Tipo 1 son N, el problema puede ser determinado, y puede no tener sentido una optimización.

Los tres tipos de restricciones pueden darse simultáneamente en el mismo problema.

 Ejemplos :

1: Un comerciante acude a cierto mercado a comprar naranjas con $500 . le ofrecen dos tipos de naranjas , las de tipo A $ 0.5 el kg y los de tipo B $ 0.8 el kg.
sabemos que solo dispone en su furgoneta de naranjas como maximo y que piensa vender , el kilo de naranjas de tipo A a $0.58 y del tipo B  $0.9 .

 

2.- Un orfebre fabrica dos tipos de joyas. Las de tipo A precisan 1 gramo de oro y 1,5 gramos de plata, vendiéndolas a 40 euros cada una. Para la fabricación de las del tipo B emplea 1,5 gramos de oro y 1 gramo de plata y las vende a 50 euros. El orfebre tiene sólo en el taller 750 gramos de oro y 750 gramos de plata. ¿Cuántas joyas ha de fabricar de cada clase para obtener un ingreso máximo?

Expresamos los datos del problema en la siguiente tabla:

Dibujamos las rectas, resolvemos gráficamente el sistema de inecuaciones, dibujamos el recinto solución y calculamos sus vértices

Los vértices son:
 
 
 
 

Aplicamos la función objetivo a cada uno de los vértices:

 
 
 
 

Observamos que los ingresos máximos (27000 euros) se obtendrían fabricando 300 joyas de tipo A y otras 300 de tipo B

3.-Mile-High Microbrewery fabrica una cerveza clara y una oscura. Mile-High dispone de una provisión limitada de cebada, tiene capacidad de embotellamiento limitada y un mercado también limitado para su cerveza clara. Las utilidades son de $0.20 por cada botella de cerveza clara y $0.50 por cada botella de cerveza oscura.

1. La siguiente tabla muestra la disponibilidad de recursos en la Mile-High Microbrewery. Aplique el método gráfico de programación lineal para maximizar las utilidades. ¿Cuántas botellas de cada producto deberán fabricarse cada mes?

1. 

1. Identifique las restricciones con holgura o superávit.

Solución :

Parte a)

Variables:

x₁ = Número de botellas de cerveza clara

x₂ = Número de botellas de cerveza oscura

Función Objetivo:

Max (0.20x₁ + 0.50x₂)

Restricciones:

Cebada                                0.1x₁ + 0.6x₂ ≤ 2000

Embotellado                      x₁ + x₂ ≤ 6000

Mercado                             x₁ ≤ 4000

Gráfico

La solución visual se encontraría en el punto C:

x₁ =3200              x₂ = 2800

Utilidad Máxima = 2040

Parte b)

Se tiene una holgura de 800 respecto a la restricción del mercado.

EJEMPLOS CON VÍDEOS EXPLICADOS : 

2.-Una dieta debe contener al menos 16 unidades de carbohidratos y 20 de proteínas. El alimento A contiene 2 unidades de carbohidratos y 4 de proteínas; el alimento B contiene 2 unidades de carbohidratos y 1 de proteínas. Si el alimento A cuesta $1.20 por unidad y el B $0.80 por unidad, ¿cuántas unidades de cada alimento deben comprarse para minimizar el costo? ¿Cuál es el costo mínimo?

3.-Una compañía petrolera que tiene dos refinerías necesita al menos 8000, 14,000 y 5000 barriles de petróleo de grados bajo, medio y alto, respectivamente. Cada día, la refinería I produce 2000 barriles de grado bajo, 3000 barriles de grado medio y 1000 barriles de grado alto, mientras que la refinería II produce 1000 barriles de cada uno de los grados alto y bajo, y 2000 barriles de petróleo de grado medio. Si operar la refinería I cuesta $25,000 por día, y operar la refinería II $20,000 diarios, ¿cuántos días debe operarse cada refinería para satisfacer los requerimientos de producción a un costo mínimo? ¿Cuál es el costo mínimo? (Suponga que existe un costo mínimo.)

5.- Un agricultor comprará fertilizantes que contienen tres nutrientes: A, B y C. Los requerimientos mínimos semanales de éstos son 80 unidades de A, 120 de B y 240 de C. Existen dos mezclas de fertilizantes de gran aceptación en el mercado. La mezcla I cuesta $8 por bolsa, y contiene 2 unidades de A, 6 de B y 4 de C. La mezcla II cuesta $10 por bolsa, con 2 unidades de A, 2 de B y 12 de C. ¿Cuántas bolsas de cada mezcla debe comprar el agricultor para minimizar el costo de satisfacer sus requerimientos de nutrientes?