Trabajo colaborativo N 2Programacin Lineal

PROGRAMACION LINEALTRABAJO COLABORATIVO N 2MARCELA CACERES CARRILLOCOD 1095795933

DEICI YOANA CASTELLANOS BURGOS

COD 1053331390

VALENTINA GARCIA LOPEZ

COD 1088256923

GRUPO 100404_18

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD

FACULTAD DE CIENCIAS BASICAS E INGENIERIA

PROGRAMACION LINEAL2009INTRODUCCIONLa programacin lineal es parte importante en nuestro diario vivir ya que nos permite utilizar herramientas en la solucin de problemas cotidianos; es importante mantener conceptos claros y poderlo aplicarlos en nuestra carrera y campo disciplinar.

OBJETIVOS Que el estudiante sea capaz de resolver problemas que se le presenten en su diario vivir Identificar los diferentes algoritmos utilizados para solucionar problemas de programacin lineal.

Proponer y plantear problemas de aplicacin donde se utilicen los diferentes mtodos para solucionar problemas de PL.

Adquirir nuevos conocimientos y destrezas. Aprender o reforzar temas de inters.

TRABAJO COLABORATIVO N 2GUIA DE ACTIVIDADESEste trabajo se compone de tres fases con entregas sucesivas en las fechas programadas. El grupo colaborativo debe realizar las tres fases y entregar los respectivos informes preparndose para la debida sustentacin en los chats propuestos para tal fin.

FASE 1: Se debe realizar la lectura auto regulada:Entrevista a Datzing el creador de la Programacin lineal, realice una presentacin en power point en la que muestre la historia de la programacin lineal y su aplicacin a travs de la historia.

FASE 2: Desarrolle los talleres 2.4 y 3.5 del mdulo de contenidos y presente el informe correspondiente en grupos colaborativos. En el foro de produccin intelectual.

FASE 3: Proponga un problema de programacin lineal para desarrollarlo por el mtodo simplex, suba el respectivo archivo al foro correspondiente (produccin intelectual).

Debe tener la siguiente estructura: Cdigo del Curso-Nombre del Grupo y debe subirse en el foro de equipo bajo el tema ENTREGA FINAL DEL TRABAJO COLABORATIVO No. 2. TRABAJO COLABORATIVO N 2

Solucin HISTORIA PROGRAMACION LINEAL

La programacin lineal es un conjunto de tcnicas racionales de anlisis y de resolucin de problemas que tiene por objeto ayudar a los responsables en las decisiones sobre asuntos en los que interviene un gran nmero de variables. El nombre de programacin lineal no procede de la creacin de programas de ordenador, sino de un trmino militar, programar, que significa 'realizar planes o propuestas de tiempo para el entrenamiento, la logstica o el despliegue de las unidades de combate'.

Aunque parece ser que la programacin lineal fue utilizada por G. Monge en 1776, se considera a L. V. Kantorvich uno de sus creadores. La present en su libro Mtodos matemticos para la organizacin y la produccin (1939) y la desarroll en su trabajo Sobre la transferencia de masas (1942). Kantorvich recibi el premio Nobel de economa en 1975 por sus aportaciones al problema de la asignacin ptima de recursos humanos.

Los siglos XVII y XVIII, grandes matemticos como Newton, Leibnitz, Bernouilli y, sobre todo, Lagrange, que tanto haban contribuido al desarrollo del clculo infinitesimal, se ocuparon de obtener mximos y mnimos condicionados de determinadas funciones. Posteriormente el matemtico frnces Jean Baptiste-Joseph Fourier (1768-1830) fue el primero en intuir, aunque de forma imprecisa, los mtodos de lo que actualmente llamamos programacin lineal y la potencialidad que de ellos se deriva. Si exceptuamos al matemtico Gaspar Monge (1746-1818), quien en 1776 se interes por

problemas de este gnero, debemos remontarnos al ao 1939 para encontrar nuevos estudios relacionados con los mtodos de la actual programacin lineal. En este ao, el matemtico ruso Leonodas Vitalyevich Kantarovitch publica una extensa monografa titulada Mtodos matemticos de organizacin y planificacin de la produccin en la que por primera vez se hace corresponder a una extensa gama de problemas una teora matemtica precisa y bien definida llamada, hoy en da, programacin lineal . En 1941-1942 se formula por primera vez el problema de transporte, estudiado

independientemente por Koopmans y Kantarovitch, razn por la cual se suele conocer con el nombre de problema de Koopmans-Kantarovitch.ALGORITMO SIMPLEX

El objetivo del Algoritmo Simplex consiste en que partiendo de una solucin

Factible bsica inicial, encontrar otra que mejore la Funcin Objetivo.

ELEMENTOS DEL ALGORITMO SIMPLEX

Para iniciar el proceso iterativo, simplex necesita un vrtice (base) factible inicial. Siendo los coeficientes del problema original aparece una identidad y todos los lados derechos tenemos una base factible inicial trivial: la correspondiente a las variables que forman la identidad. Sin embargo, en muchos casos esto no ocurre, por lo que tenemos que disponer de un mtodo para hallar soluciones bsicas factibles si las hay. Esto consiste en agregar tantas variables artificiales como sea necesario para formar una identidad y luego resolver un problema de optimizacin consistente en tratar de que dichas variables artificiales se hagan nulas y por tanto se puedan eliminar. Para ello tratamos de minimizar la suma de variables artificiales:

Si la suma optima de variables artificiales es no nula significa que alguna variable artificial es positiva y por tanto no la podemos eliminar. En dicho caso, el problema es no es factible.

Si la suma ptima de variables artificiales es nula significa que todas las variables artificiales son nulas y por tanto las podemos eliminar

Si ninguna variable artificial est en la base ptima de fase I, entonces tomamos dicha base como vrtice inicial para la fase II.

Si existen variables artificiales en la base ptima de fase I, entonces podemos intentar reemplazarla por cualquier variable no bsica para formar una base factible para la fase II.

PROBLEMAS

Maz3x1+5x2

3x1+2x2=18

X1=4

X2=6

X1.X2=0

Maz2x1+3x2

x1+2x2=6

2x1+X2=8

X1.X2=0

Maz2x1-X2+X3

3x1+x2+x3=60

X1-X2+2x3=10

X1+X2-X3=20

X1.X2.X3=0

Minimizar Z = 10X2 + 30X3 + 40X4 + 10X5 + 20X7

C.S.R. = Con las siguientes restricciones:

3X1 + 2X2 + X6 + X7 = 5.000

2X4 + X5 + X6 = 15.000

X2 +3X3 + 2X5 + X6 + 2X7 = 5.000

Xj > 0 ; j = 1,2,3,4,5,6,7

Adicionando las variables artificiales necesarias para obtener una solucin bsica factible, el problema queda expresado de la siguiente forma:

Min Z = 10X2 + 30X3 + 40X4 + 10X5 + 20X7 + MX8 + MX9 + MX10

C.S.R.

3X1 + 2X2 + X6 + X7 + X8 = 5.000

2X4 + X5 + X6 + X9 = 15.000

X2 + 3X3 + 2X5 + X6 + 2X7 + X10 = 5.000

Xj > 0 ; j = 1,2,3,4,5,6,7,8,9,10

Variables bsicas X8 , X9 y X10

Solucin:

Variables de Decisin: X1* = X2* = X3* = X5* = X7* = 0 ; X4* = X6* = 5.000 ; Z* = 200.000

Variables Artificiales: X8* = X9* = X10* = 0

Interpretacin: Para que halles un mnimo de desperdicio de 200.000 cm de lmina y cumplir exactamente con los pedidos, hay que cortar 5.000 lminas de la forma 4 y 5.000 lminas de la forma 6CONCLUSIONES

En la actualidad en la que vivimos el planteamiento y solucin correcta de estos ejercicios es la forma de desempearnos como profesionales creativos y dinmicos. El mtodo simplex es ms prctico y eficiente y conduce a soluciones optimas.

El desempeo al que se puede llegar mediante cada uno de los mtodos es lo que nos permite desarrollar mas cualidades para saber aplicar la programacion lneal a nuestra vida diaria y profesional.

BIBLIOGRAFIA MDULO CURSO PROGRAMACION LINEAL PRIMERA EDICIN, Universidad Nacional Abierta y a Distancia, Bogot D. C., 2008

http://es.wikipedia.org www.monografias.com www.gnu.org www.diarioti.com www.ubuntu.com www.qbex.com

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD www.unad.edu.co

PTU: www.unadvirtual.org

_1265309860.bin