CATEDRATICO: ING. MARIO JIMENEZ MARTINEZFEBRERO DEL 2011

La programación lineal es una parte de la técnica más general llamada programación matemática y se usa para determinar la mejor asignación de recursos limitados de una empresa ; dicha programación matemática comprende además de la lineal, la programación cuadrática, la entera, la dinámica, la estocástica, etc .

PROGRAMACION LINEAL

Para poder aplicar programación lineal a la solución de un problema de negocios, se requiere llenar nueve requisitos básicos:

1. Se debe definir claramente una función objetivo, en forma matemática.

2. Debe haber cursos alternativos de acción de entre los cuales se habrá de determinar una solución que satisfaga la función objetivo .

3. Los objetivos y restricciones de la empresa se deberan expresar como ecuaciones y desigualdades lineales

4. El suministro de recursos ha de ser limitado .

5. Las variables del problema deberán estar interrelaciónadas como consecuencia de la condición anterior.

6. La solución óptima debe contener solo variables con valores finitos.

7. Los insumos deben ser divisibles.

8. No debe haber interacción entre procesos y actividades, es decir que el resultado total del proceso debe ser igual a la suma de las actividades que intervienen (Una misma porción de un recurso no puede ser usado para producir dos cosas distintas)

9. Se deben conocer con exactitud los "precios netos“ (coeficientes de las variables en la función objetivo, que indican el ingreso neto de cada actividad en problemas de maximización o el costo neto en problemas de minimización), así como los coeficientes de producción (coeficientes de las variables en las restricciones. que indican la cantidad que se necesita de cada recurso para obtener una unidad de actividad). También debe conocerse con exactitud la disponibilidad de cada recursos y todos esos datos conocidos se deben considerar constantes en el período de análisis.

1). Permite comparar un amplio rango de soluciones alternativas y analizar sus consecuencias requiriendo para ello poco tiempo gerencial .

2). Indica al administrador como emplear más eficazmente sus factores seleccionándolos y distribuyéndolos adecuadamente .

VENTAJAS DE LAPROGRAMACIÓN LINEAl

3. Hace que el administrador sea más objetivo en sus de cisiones al obtener todos los datos que puedan ser dtiles para la formulación matemática del, problema.

4. Permite modificaciones a su solución matemática en .o favor de la conveniencia, mediante la inclusión de restricciones formuladas adecuadamente.

5 . La Programación Lineal, permite identificar los "cuellos de botella" en las operaciones actuales

LIMITACIONES DE LA PROGRAMACIÓN LINEAL

1). La Programación Lineal no puede auxiliar al gerente en la difícil tarea de formular expectativas de precio ; sino que éstos deben ser conocidos para aplicar el proceso.

2). Es de poca utilidad para estimar relaciones de insumo- producto. El planificador debe contar con estimaciones de la cantidad y distribución de mano de obra, tierra y capital necesarios para producir. Estimaciones de este tipo resultan difíciles ; especialmente cuando la empresa no lleva registros adecuados .

3). La Programación Lineal se basa en el supuesto de que los precios y las `expectativas de insumo-producto formuladas fueran igualmente confiables para todos los productos. Es decir que no se toman en consideración situaciones de riesgo en las decisiones .

4). A veces resulta difícil especificar las restricciones

5). No se toma en cuenta los rendimientos marginales físicos decrecientes, sino que se trabaja como si sólo se diera el caso de rendimientos constantes a escala, situación muchas veces errónea en la realidad .

6). Tampoco se puede» manejar adecuadamente las actividad des que involucran costos decrecientes.

7). Se requiere equipo de computación y rutinas de solución bien probadas a fin de tener éxito en la aplicación de programación lineal a la planeación, pues el logro de resultados realistas requiere utilizar un gran número de actividades y restricciones que seria prácticamente imposible manejar con calculadora de escritorio .

2 . FORMA ELEMENTAL DE UN PROBLEMA DE P . L.

Un problema de programación lineal con dos variables tiene por finalidad optimizar (maximizar o minimizar) una función lineal:

llamada función objetivo, sujeta a una serie de restricciones presentadas en forma de sistema de inecuaciones con dos incógnitas de la forma:

Cada desigualdad del sistema de restricciones determina un semiplano. El conjunto intersección de todos esos semiplanos recibe el nombre de zona de soluciones factibles. El conjunto de los vértices del recinto se denomina conjunto de soluciones factibles básicas y el vértice donde se presenta la solución óptima se llama solución máxima (o mínima según el caso). El valor que toma la función objetivo en el vértice de solución óptima se llama valor del programa lineal.

El procedimiento a seguir:•Elegir las incógnitas.

•Escribir la función objetivo en función de los datos del problema.

•Escribir las restricciones en forma de sistema de inecuaciones.

•Averiguar el conjunto de soluciones factibles representando gráficamente las restricciones.

•Calcular las coordenadas de los vértices del recinto de soluciones factibles (si son pocos).

•Calcular el valor de la función objetivo en cada uno de los vértices para ver en cuál de ellos presenta el valor máximo o mínimo según nos pida el problema (hay que tener en cuenta aquí la posible no existencia de solución si el recinto no es acotado).

Ejemplo de maximizacion:1 . Considere:Max z= 3X1 + 5X 2 Función objetivoS .a :X1 ≤ 4 Recurso 1X2 ≤ 6 Recurso 23X1 + 2X2 ≤ 18 Recurso 3X1 mayor igual a 0 Cond . de noX2 mayor igual a 0 Negatividad

Este ejemplo por tener solo dos variables, se puede plantear gráficamente, para ello:Paso 1. Graficar las desigualdades como igualdades:

El área sombreada representa la "Región o Conjunto de Soluciones Factibles" . Esa región contiene todos los valores de X1 y X2 (incógnitas) que satisfacen las restricciones.

INVESTIGACIÓN DE OPERACIONES

MINIMIZACIÓNMÉTODO GRAFICO

PLANTEAMIENTO DEL PROBLEMA

En granjas modelo se usa diariamente un mínimo de 800 libras (lb) de un alimento especial, que es una mezcla de maíz y soya, con las composiciones siguientes:

Las necesidades dietéticas del alimento especial son un mínimo de 30% de proteínas y un máximo de 5% de fibras. Granjas Modelo desea determinar las proporciones de alimento que produzcan un costo diario mínimo.

lb por lb de alimentoAlimento Proteína Fibra Costo($/lb)Maíz 0.09 0.02 0.30Soya 0.60 0.06 0.90

Como la mezcla de alimentos consiste en maíz y soya, las variables de decisión del modelo se definen como lo siguiente:x1= lb de maíz en la mezcla diariax2= lb de soya en la mezcla diariaLa función objetivo trata de minimizar el costo de (en dólares) diario total de la mezcla de alimentos, y en consecuencia se expresa como lo siguiente:Minimizar z = 0.3x1 +0.9x2

Las restricciones del modelo reflejan la cantidad diaria necesaria y los requerimientos dietéticos.

Como Granjas Modelo necesita un mínimo de 800 lb diarias de alimento, la restricción correspondiente se puede expresar como sigue:

x1+x2≥800En cuanto a la restricción dietética de necesidades de proteína, la cantidad de proteína que contiene x1 lb de soya es (0.9x1 +0.6x2)lb. Esta cantidad debe ser cuando menos igual a 30% de la mezcla total de alimentos, (x1+x2)lb; esto es

0.09x1+0.6x2 ≥0.3(x1+x2)De manera similar, la restricción de la fibra se define como :

0.02x1+0.6x2 ≥0.05(x1+x2)

Las restricciones se simplifican agrupando todos los términos en x1 y x2 y pasándolos al lado izquierdo de cada desigualdad, para que solo quede una constante en el lado derecho. Así, el modelo completo viene a ser: minimizar z =0.03x1 + 0.09x2

x1+x2≥8000.21x1-0.30x2 ≤00.03x1+0.01x2 ≥0x1,x2≥0

Para graficar las rectas correspondientes solo se necesita un punto adicional, que se puede obtener asignando un valor a una de las variables y despejando la otra. En la segunda restricción x1=200 produce 0.21 x 200-0.3 x2 =0, es decir, x2 = 140. eso quiere decir que la recta 0.21 x1 – 0.3 x2 = 0 pasar por (0,0) y (200, 140). También obsérvese que no se puede usar (0,0) como punto de referencia en las restricciones 2 y 3, por que ambas rectas pasan por el origen. En lugar de ellos se puede cualquier otro punto, por ejemplo (100,0) ó (0,100) para que ese propósito.

• Ya que en este modelo se busca minimizar la función objetivo, necesitamos reducir todo lo posible el valor de z, en la dirección que muestra la figura. La solución optima es la intersección de las dos rectas, x1 + x2 = 800 y 0.21x1-0.3x2 = 0; así se obtiene x1=470.6 lb y X2 =329.4 lb. El costo mínimo correspondiente , de la mezcla de alimentos, es z=0.3x470.6+0.9x329.4= $437.64 diarios.

PROCEDIMIETO

Para encontrar el valor de la variable x2 (soya):0.20X1- 0.3X2 = 0 X2 = -168/-0.51(X1 + X2 = 800)x(-0.2) X2 = 329.4 lb

0.21X1 – 0.3X2 = 0-0.21X1 -0.21X2 = -168 -0.51X2=-168

Sustituyendo X2 para encontrar X1:

0.21X1 -0.3X2 = 00.21X1-0.3(329.4 lb)=0 X1= 470.6 lb

Sustituyendo los valores de X1 Y X2 en función original:

Minimizar z = 0.3x1 + 0.9 x2

z = $437.64

Minimizar z = 0.3x1 + 0.9 x2

0.03

x1 -0

.01x

2 ≥

0

0.21x1 – 0.3 x2 ≤ 0

X1 + x2

≥800

Optimo: x1=470.6lb x2=329.4lb z= $437.64

0

500

1000

1500

500 1000 1500x1

x2

solución grafica del modelo de la dieta.