PROGRAMACIN LINEAL1. INTRODUCCINLa programacin lineal es una tcnica matemtica relativamente reciente (siglo XX), que consiste en una serie de mtodos y procedimientos que permiten resolver problemas de optimizacin en el mbito de la minera.Para sistemas de ms variables, el procedimiento no es tan sencillo y se resuelven por el llamado mtodo Simplex (ideado por G.B.Danzig, matemtico estadounidense en 1951).Recientemente (1984) el matemtico indio establecido en Estados Unidos, Narenda Karmarkar, ha encontrado un algoritmo, llamado algoritmo de Karmarkar, que es ms rpido que el mtodo simplex en ciertos casos. Los problemas de este tipo, en el que intervienen gran nmero de variables, se implementan en ordenadores.2. DEFINICINTcnica de programacin matemtica para resolver problemas de optimizacin de re La resolucin ptima de problemas constituye una parte importante de la formacin de un cientfico o tcnico. Dentro de las Matemticas este problema se enmarca en la Programacin Matemtica.Los problemas de programacin lineal admiten, para un mximo de 3 variables, una fcil interpretacin grfica.Un problema de programacin lineal es un problema de minimizar o maximizar una funcin lineal sujeta a restricciones lineales del tipo desigualdad, igualdad o ambas. 3. CARACTERSTICASa. Se busca una combinacin de recursos.b. Se deben satisfacer varios criterios.c. Se identifica un criterio como el objetivo.

4. UBICACIN

5. MODELIZACINLa modelizacin de un problema consiste en representar matemticamente dicho problema.5.1. MODELO DE TRANSPORTETenemos una red de carreteras. Hay varios puntos donde se va a producir algo y otros puntos donde se va a demandar algo.Conociendo los costes de transporte, hay que elegir el camino para que el coste sea el mnimo posible.Elegir desde que centro de produccin atenderemos a cada centro de demanda.Solucin:Lo primero que haremos ser definir las variables:Pi ------ produccin mxima de cada centro iCij ---- coste de transporte de un centro i a un centro de demanda jdj ----- demanda mxima en cada centro jF.O..: Minimizar Xij * CijSiendo Xij lo que producido en el centro i vamos a mandarlo al centro j.S.a..:Para todo i: Xij PiPara todo j: Xij djPara todo i,j: Xij 0Este problema se podra complicar dando nuevas restricciones como podran ser el tener una demanda mxima y otra mnima. Lo mismo se podra aplicar a la produccin.Otro tipo de restricciones que se podran introducir vendran dadas por la aparicin de almacenes intermedios. En ellos podramos almacenar lo que hiciese falta, para repartirlo en otro momento por otros vehculos. Esto sera un modelo de transbordo.Tambin se puede dar una capacidad mxima a cada almacn.

5.2. MODELO DE ASIGNACINSupone que tiene unos puestos de trabajo y unos candidatos. Se quiere estudiar cmo cubrir estos puestos de forma que se optimice una variable que sea significativa.Es la modelizacin en programacin lineal del algoritmo hngaro.Para este tipo de modelizacin necesitamos definir una nueva variable, llamada variable dual y su funcionamiento es el siguiente:Si aij = 1 entonces el seor i ocupa el puesto j.Si aij = 0 entonces el seor i no ocupa el puesto j.Se llama variable dual porque slo puede tomar dos valores: 1 0.En nuestro problema tendremos que definir:Vij ---- valor de la persona i para el puesto j.F.O.: Maximizar aij * VijS.a.: Para todo i: aij = 1Para todo j: aij 1La primera restriccin indica que un seor slo ocupar un puesto.La segunda indica que un puesto slo lo ocupar un seor o bien no estar ocupado.

5.3. MODELO DE ORDENACIN DE TAREASEstudia los tiempos de demora que dependern de si se hace una tarea antes que otra.El modelo es igual que el anterior slo que intentaramos minimizar los costes muertos entre tarea y tarea, es decir:Min aij * tijAparecer una restriccin que ser: si una tarea i se realiza antes que una tarea j, entonces la tarea j no se har antes que la tarea i.

5.4. MODELO DE LA MOCHILAConsiste en la aplicacin de un determinado peso en cada unidad portante con la finalidad de obtener el peso mnimo en cada unidad.Solucin:F.O.: Min ni * PiSiendo ni el nmero de objetos del tipo i que llevar:S.a.: ni Ni ni N siendo Ni el nmero total de objetos i de que dispone.

5.5. FORD- FULKERSONEs el problema del flujo mximo.Definimos:Cij------capacidad del arco que tiene como nodo origen i y como nodo final j.fij------ flujo que circula por el arco (i,j).F.O.: Max fij.S.a.: Para todo i y para todo j: fijCij.Para todo i: fij - fik =0Para todo i y para todo j: fij, Cij0

5.6. ALGORITMO DE KLEINPij---- coste del arco (i,j)F.O.: Min Pij * fijLas restricciones son iguales que las de Ford-Fulkerson.Pero podran aparecer nuevas restricciones aplicables a los dos mtodos, en el caso de que hubiese aportes, Aj, o bien existiesen prdidas, Pj, las restricciones se representaran:Para todo j: fij - fjk + Aj=0 en caso de aportes.Para todo j: f fij - fjk Pj=0 en caso de prdidas.

5.7. CAMINOS HAMILTONIANOS DE COSTE MNIMOaij =0 el arco (i,j) no forma parte del camino.aij =1 el arco (i,j) forma parte del camino.F.O.: Min Cij * aijS.a.: para todo i: aij =1 slo sale un arco de cada nodo.Para todo j: aij =1 slo llega un arco de cada nodo.

5.8. KRUSKALCij---- coste arista entre el nodo i y el nodo j.F.O.: Min Cij * aijS.a.: para todo i: aij 1Al menos llega una arista y al menos sale otra para todo j: aij 1aij 1

5.9. PERT CPMTij---- duracin entre la actividad i y la actividad j.Tj---- tiempo ms temprano de empezar la actividad i.F.O.: Min Ti.S.a.: Tj - Ti Tij.6. MTODOS

6.1. MTODO DE REPRESENTACIN GRFICAConsiste en representar las restricciones sobre unos ejes de coordenadas, para delimitar la regin dnde se encuentran las soluciones factibles.Las soluciones ptimas se encontrarn en el permetro del polgono resultante.Si nuestra funcin objetivo es una maximizacin y la lnea que delimita nuestro dominio no es convexa, entonces nuestro problema, bajo estas condiciones, no tiene solucin.

6.2. MTODO SIMPLEXResuelve los problemas del tipo maximizar con restricciones menor o igual.

6.3. MTODO DE LAS DOS FASESEste mtodo se aplica cuando existen restricciones del tipo mayor o igual.El tratamiento de las restricciones para convertir las desigualdades en igualdades en este caso es el siguiente. Sea aij * Xj bi lo podremos transformar en aij * Xj Yk = bi donde Yk ser una nueva variable denominada variable de holgura.Si introdujsemos esto en la tabla de simplex, nos dara lugar a una base inicial no factible, por lo que para poder resolver el problema, tendremos que aplicar una tcnica diferente. Esta tcnica es la del mtodo de las dos fases.El mtodo de las dos fases va a realizar un tratamiento de nuestro problema, para que sea posible aplicar el mtodo simplex.Para poder crear una base factible inicial que nos permita aplicar el mtodo simplex, al transformar las desigualdades de tipo mayor o igual en igualdades, introducimos una variable ficticia, que nos dar lugar a una base cannica.

6.4. CAMBIOS DE VARIABLEEn algunas ocasiones en las que nos encontramos con un problema en el que aparecen variables acotadas inferiormente, puede ser conveniente someter dichas variables a un cambio de variable para que queden de la forma:Xi0Y poder aplicar el mtodo simplex. Es decir, lo que vamos a buscar es que slo quede la restriccin de positividad.

7. REPRESENTACIN DE VARIABLES

7.1. FORMA.Carcter que representa un determinado producto.

7.2. MODALIDADES.1. Serie: Dos letras maysculas de imprenta (A y B o X e Y).2. Subndice: Una letra mayscula de imprenta con subndices (X) (1 y 2).3. Nemotecnia: Dos letras maysculas de imprenta representativas.

8. RESTRICCIONES

8.1. CONCEPTO DE RESTRICCIN.Conjunto de condiciones exigidas, relacionadas con los recursos involucrados en un problema, que debe satisfacer toda solucin.

8.2. TIPOS DE RESTRICCIONES.

8.2.1. RESTRICCIONES DE CAPACIDAD: Se deben a la cantidad disponible de:- Equipo- Espacio- Mano de obra Ejemplo: Tiempo disponible en la mquina N 1.

8.2.2. RESTRICCIONES DE MERCADO: Son lmites de la cantidad de producto (bien o servicio) que puede venderse o usarse. Puede ser:- Inferior- Superior- Ambos Ejemplo: No pueden venderse ms de 200 litros de gasolina.

8.2.3. RESTRICCIONES DE DISPONIBILIDAD: Son lmites ocasionados por la escasez de recursos.- Materias primas.- Fuerza de trabajo.- Financiamiento.- Otros. Ejemplo: La cantidad de litros de combustible para mezcla es de 30.000 litros.

8.2.4. RESTRICCIONES DE CALIDAD: Son restricciones que limitan la mezcla de ingredientes y que por lo tanto determinan la calidad de los productos resultantes. Ejemplo: El octanaje que debe tener una mezcla de gasolina de aviacin.

8.2.5. RESTRICCIONES DE EQUILIBRIO: Son restricciones de tecnologa de produccin o equilibrio de materiales. Determinan la salida de un proceso como una funcin de las entradas, muchas veces con una prdida por desperdicios. Ejemplo: Entradas de troncos de pino y abeto usados para producir hojas de madera contrachapada.

8.2.6. RESTRICCIONES DE DEFINICIN: Son restricciones que definen una variable. Muchas veces provienen de definiciones contables. Ejemplo:El inventario final de productos terminados debe ser igual a 0.

9. ANLISIS DE SENSIBILIDAD9.1. CONCEPTO DE ANLISIS DE SENSIBILIDAD.Estudio del efecto de los cambios en los parmetros del problema, sobre la solucin ptima de Programacin Lineal.

9.2. IMPORTANCIA DEL ANLISIS DE SENSIBILIDAD.1. Los modelos de Programacin Lineal son con frecuencia grandes y costosos, debido a lo cual no es eficiente usarlos para un solo caso.

2. Los elementos que se dan como datos para un problema, muchas veces son aproximaciones, debido a lo cual es necesario examinar ms de un conjunto de circunstancias.

9.3. TIPOS DE ANLISIS DE SENSIBILIDAD.

9.3.1. SENSIBILIDAD DE LA FUNCIN OBJETIVO:a. Cambios en los coeficientesDeterminar la gama de optimismo para la pendiente de los parmetros de la funcin objetiva que mantendr inalterable la solucin ptima de un modelo determinado.b. Cambios en el trmino independiente (LD)

9.3.2. SENSIBILIDAD DE LAS RESTRICCIONES:a. Cambios en los coeficientes de las restricciones.b. Cambios en el trmino independiente de las restricciones. (LD)c. Adicin de nuevas restricciones.

9.3.3. SENSIBILIDAD DE LAS LIMITACIONES:a. Cambios en la limitacin de las abscisas.b. Cambios en la limitacin de las ordenadas.