unidad 1 introduccion a la programacion lineal

7/23/2019 Unidad 1 Introduccion a La Programacion Lineal

1/38

Unidad 1 Introduccion a la programacion Lineal

CAPITULO 1. La investigacion de Operaciones

PROGRAMACIN LINEAL.

Introduccin.

Muchas personas clasifican el desarrollo de la programacin lineal

entre los avances cientficos ms importantes del siglo XX. Su

impacto desde 1950 ha sido extraordinario. En la actualidades una

herramienta de uso normal que ha ahorrado miles o millones de

dlares a muchas compaas, en los pases industrializados del mundo,

su aplicacin a otros sectores de la sociedad se ha ampliado con

rapidez.

Cual es la naturaleza de esta notable herramienta y que tipo de

problemas puede manejar?. Expresado en forma breve, el tipo ms

comn de aplicacin abarca el problema general de asignar recursos

limitados entre actividades competitivas de la mejor manera posible

(de forma ptima). Con ms precisin, este problema incluye elegir el

nivel de ciertas actividades que compiten por recursos escasos

necesarios para realizarlas. Despus, los niveles de actividad elegidosdictan la cantidad de cada recurso que consumircada una de ellas. La

variedad de situaciones a las que se puede aplicar esta descripcin es

sin duda muy grande, y va desde la asignacin de instalaciones de

produccin a los productos, hasta la asignacin de recursos nacionales

a las necesidades de un pas; desde la planeacin agrcola hasta el

diseo de una terapia de radiacin, etc.


2/38

Unidad 1 Introduccion a la programacion Lineal

a.- Antecedentes y origen de la Investigacin de Operaciones

PROGRAMACIN LINEALINTRODUCCIN

La programacin lineal es un conjunto de tcnicas racionales de anlisis y deresolucin de problemas que tiene por objeto ayudar a los responsables en lasdecisiones sobre asuntos en los que interviene un gran nmero de variables.

El nombre de programacin lineal no procede de la creacin de programas deordenador, sino de un trmino militar, programar, que significa 'realiar planes opropuestas de tiempo para el entrenamiento, la log!stica o el despliegue de lasunidades de combate'.

"unque parece ser que la programacin lineal fue utiliada por #. $onge en %&&,se considera a L. (. )antorvic* uno de sus creadores. La present en su libro$todos matemticos para la organiacin y la produccin +%- y la desarrollen su trabajo /obre la transferencia de masas +%01. )antorvic* recibi elpremio 2obel de econom!a en %&3 por sus aportaciones al problema de laasignacin ptima de recursos *umanos.

La investigacin de operaciones en general y la programacin lineal en particularrecibieron un gran impulso gracias a los ordenadores. 4no de momentos msimportantes fue la aparicin del mtodo del simple5. Este mtodo, desarrolladopor #. 6. 7antig en %0&, consiste en la utiliacin de un algoritmo paraoptimiar el valor de la funcin objetivo teniendo en cuenta las restriccionesplanteadas. 8artiendo de uno de los vrtices de la regin factible, por ejemplo elvrtice ", y aplicando la propiedad9 si la funcin objetivo no toma su valorm5imo en el vrtice ", entonces e5iste una arista que parte del vrtice " y a lolargo de la cual la funcin objetivo aumenta. se llega a otro vrtice.

El procedimiento es iterativo, pues mejora los resultados de la funcin objetivo encada etapa *asta alcanar la solucin buscada. :sta se encuentra en un vrticedel que no parta ninguna arista a lo largo de la cual la funcin objetivo aumente.

"unque a lo largo de esta unidad nicamente se resuelven problemas deprogramacin lineal bidimensional, este tipo de anlisis se utilia en casos donde

intervienen cientos e incluso miles de variables.

OBJETIVOS

;esolver grficamente inecuaciones y sistemas de inecuaciones linealescon dos incgnitas


3/38


4/38

Otro antecedente de uso de la Investigacin Operativa se produce durante la "rimera!uerra 0undial en Inglaterra con el estudio matem$tico de 1rederic2 3illiam+anchester sobre la potencia balstica de las fueras opositoras. Adem$s desarroll a

partir de un sistema de ecuaciones diferenciales la +ey Cuadr$tica de Combate de+anchester con la que era posible determinar el desenlace de una batalla militar enfuncin de la fuera num-rica relativa y la capacidad relativa de fuego de loscombatientes.

4homas Alva Edison tambi-n hio uso de la Investigacin Operativa contribuyendo enla guerra antisubmarina desarrollando t-cnicas para que los navos pudiesen evadir ydestruir los submarinos enemigos dot$ndolos de una proteccin anti5torpedos.

6esde el punto de vista matem$tico en los siglos 7,II y 7,III 8e9ton +eibnit:ernoulli y +agrange traba&aron en obtener m$ximos y mnimos condicionados deciertas funciones. El matem$tico franc-s ;ean :aptiste5;oseph 1ourier esbo m-todosde la actual programacin lineal. < en los #ltimos a/os del siglo 7,III !aspar 0ongeasent los precedentes del m-todo !r$fico gracias a su desarrollo de la !eometra6escriptiva.

A finales del siglo 7I7 1rederic2 3inslo9 4aylor reali un estudio que permitimaximiar el rendimiento de los mineros en el que se determinaba que la #nica variablerealmente significativa era el peso combinado de la pala y su carga. 6e esta forma sedise/aron palas seg#n los diferentes tipos de materiales con los que iban a utiliarse.

;anos ,on 8eumann public en '=>? su traba&o @4eora de ;uegos@ que proporcionfundamentos matem$ticos a la "rogramacin +ineal. "osteriormente en '=B vision


5/38

la similitud entre los problemas de programacin lineal y la teora de matrices que habadesarrollado.

En '=*= el matem$tico ruso +eonid,it$lievichantorvich y el holand-s 4&allingCharles oopmans desarrollaron la teora matem$tica llamada @"rogramacin +ineal@

por la que les fue concedido el "remio 8obel de Economa.

En '=( !eorge ;oseph %tigler plante elproblema de la dieta a ra de lapreocupacin del e&-rcito americano por asegurar unos requerimientos nutricionalesb$sicos para sus tropas al menor coste posible. %e trataba de determinar la cantidadentre BB alimentos diferentes que debera ingerir diariamente un hombre mediano deaproximadamente B)g de peso de modo que las necesidades mnimas de nutrientesfuesen iguales a las recomendadas por el Conse&o 8acional de Investigacinnorteamericano. El problema fue resuelto manualmente mediante un m-todo heursticocon el cual se examinaron (') diferentes posibilidades de combinacin de alimentos ycuya solucin difera tan slo unos c-ntimos de la solucin aportada a/os m$s tarde por

el m-todo %implex.

6urante los a/os '=' y '=> antorovich y oopmans estudiaron de formaindependiente el problema del transporte por primera ve conoci-ndose este tipo de

problemas como problema de oopmans5antorovich. "ara su solucin emplearonm-todos geom-tricos que est$n relacionados con la teora de convexidad de 0in2o9s2i.

%e cree que Charles :abbage es el padre de la Investigacin Operativa debido a susinvestigaciones acerca de los costos de transporte y clasificacin del correo realiada enla Dniform"enny "ost de Inglaterra en '?).

%in embargo no se considera que ha nacido una nueva ciencia llamada InvestigacinOperativa o Investigacin de Operaciones hasta la II !uerra 0undial durante la batallade Inglaterra. +a +uft9affe 1uera A-rea Alemana estaba sometiendo a este pas a unfuerte acoso aprovechando la reducida capacidad a-rea brit$nica debido a la poltica dedesarme aunque experimentada en el combate. El gobierno brit$nico buscando alg#nm-todo para defender su pas convoc cientficos de diversas disciplinas para tratar deresolver el problema y sacar el m$ximo beneficio de los radares de reciente invencinde que disponan. !racias a su traba&o determinando la localiacin ptima de lasantenas y la me&or distribucin de las se/ales consiguieron duplicar la efectividad delsistema de defensa a-rea y evitar que la isla cayera en manos de la Alemania nai.

4ambi-n en '=> la D5:oots9affe alemana con su flota de submarinos D5:oot iniciun bloqueo a !ran :reta/a atacando convoyes de barcos cargados de suministros

procedentes de Estados Dnidos e impidiendo que alcanaran su destino. El !rupo deInvestigacin de Operaciones de !uerra Antisubmarina de Estados Dnidos A%3OF!Anti5%ubmarine3arfareOperationsFesearch!roup en ingl-sG reali representacionesmatem$ticas de dichos convoyes teniendo en cuenta una serie de restricciones ycondiciones impuestas por la realidad tales como la velocidad m$xima a la que podandesplaarse los navos la cantidad de suministros que deban transportar y elcombustible necesario para alcanar su destino. Aplicaron estos modelos tambi-n sobrelos D5:ootsH el tama/o de su flota el alcance de los submarinos sus torpedos etc. Con

base a esta informacin fueron capaces de modelar la guerra naval y determinar si erame&or una estrategia basada en convoyes formados por un gran grupo de navos de carga
http://www.phpsimplex.com/problema_dieta.htmhttp://www.phpsimplex.com/problema_dieta.htm


6/38

escoltados por muchos destructores o por el contrario peque/os grupos m$s difciles delocaliar para el enemigo e incluso la manera de causar un mayor da/o a lossubmarinos D5:oot. Cuando la armada de los Estados Dnidos de Am-rica puso en

pr$ctica esta estrategia disminuy de forma considerable la cantidad de barcoshundidos mientras se incrementaba la destruccin de submarinos alemanes pasando del

hundimiento de apenas una treintena al a/o a rondar los >() anuales en '=* y '=G.

4ras apreciar el alcance de -sta nueva disciplina Inglaterra cre otros grupos de lamisma ndole para obtener resultados ptimos en la contienda. 6e la misma formaEstados Dnidos EEDDG al unirse a la !uerra en '=> comen a aplicar t-cnicas deInvestigacin de Operaciones militarmente y unos a/os m$s tarde en '=B form ungrupo de traba&o dedicado a me&orar los procesos de planificacin a gran escalaH el

proyecto %COO" %cientificComputation Of Optimum"rogramsG. En dicho grupo seencontraba traba&ando !eorge :ernard 6antig quien desarroll en '=B el algoritmodel m-todo %implex.

6urante la !uerra 1ra la antigua Dnin %ovi-tica DF%%G excluida del "lan 0arshallquiso controlar las comunicaciones terrestres incluyendo rutas fluviales de :erln. "araevitar la rendicin de la ciudad y su sumisin a formar parte de la ona comunistaalemana Inglaterra y Estados Dnidos decidieron abastecer la ciudad o bien medianteconvoyes escoltados lo que podra dar lugar a nuevos enfrentamientosG o mediante

puente a-reo rompiendo o evadiendo en cualquier caso el bloqueo de :erln. %e optpor -sta segunda opcin iniciando la +uftbrc2e puente a-reoG el >( de &unio de '=?.Jste fue otro de los problemas en los que particip el grupo %COO" en diciembre deese mismo a/o se consegua abastecer con ()) toneladas diarias y tras estudios deInvestigacin Operativa se optimi el abastecimiento hasta llegar a las ?))) =)))

toneladas diarias en maro de '==. Jsta cifra era la misma que se hubiera transportado
http://www.phpsimplex.com/biografia_Dantzig.htmhttp://www.phpsimplex.com/biografia_Dantzig.htm


7/38

por medios terrestres por lo que los sovi-ticos decidieron levantar el bloqueo el '> demayo de '==.

4ras la %egunda !uerra 0undial se estim oportuno realiar la organiacin de losrecursos de Estados Dnidos energa armamento y todo tipo de suministrosG mediante

modelos de optimiacin resueltos mediante la "rogramacin +ineal.

Al mismo tiempo que la doctrina de la Investigacin Operativa se desarrollarontambi-n las t-cnicas de computacin las cuales permitieron una importante reduccindel tiempo de resolucin de los problemas.

El primer resultado de estas t-cnicas se obtuvo en el a/o '=(> utiliando un ordenador%EAC del 8ational :ureau of %tandars para obtener la solucin de un problema. El-xito en el tiempo de resolucin fue tan alentador que de inmediato se us para todo tipode problemas militares tales como la gestin de fondos monetarios para logstica yarmamento determinar la altura ptima a la que deberan volar los aviones para

localiar los submarinos enemigos e incluso la profundidad a la que se deban enviarlas cargas para alcanar los submarinos enemigos de forma que causara el mayorn#mero de ba&as. 4odo esto se tradu&o en un aumento de hasta cinco veces en la eficaciade la fuera a-rea.

6urante las d-cadas de los () y K) creci el inter-s y el desarrollo de la InvestigacinOperativa debido a su aplicacin en el $mbito del comercio y la industria. Dn e&emplode esto es el problema del c$lculo del plan ptimo de transporte de arena deconstruccin a las obras de edificacin de la ciudad de 0osc# donde existan ') puntosde origen y >*) de destino. "ara resolverlo se utili un ordenador %trena en el mes de

&unio de '=(? y despu-s de ') das de c$lculos produ&o una solucin que aport unareduccin del ''L de los gastos respecto a los costes originales previstos.

Anteriormente ya se haban planteado estos problemas en una disciplina conocida comoInvestigacin de Empresas o An$lisis de Empresas que no disponan de m-todos tanefectivos como los desarrollados durante la %egunda !uerra 0undial por e&emplo elm-todo %implexG. +as aplicaciones no b-licas de la Investigacin Operativa seextienden a todos los $mbitos con problemas que van desde la alimentacin ganaderadistribucin de campos de cultivo en agricultura transporte de mercancas localiacindistribucin de personal problemas de redes colas grafos etc.

A modo de e&emplo se pueden observar los siguientes casos reales de uso deInvestigacin Operativay los beneficios reportados.

a.2.- Biogra!a de "ant#ing

!eorge :ernard 6antigOurisson naci el ? de 8oviembre de '=' en "ortland en elestado de Oregon de los Estados Dnidos de Am-rica. Mi&o de 4obas 6antig
http://www.phpsimplex.com/casos_reales.htmhttp://www.phpsimplex.com/casos_reales.htmhttp://www.phpsimplex.com/casos_reales.htmhttp://www.phpsimplex.com/casos_reales.htm


8/38

matem$tico ruso y An&aOurisson lingista francesa especialiada en idiomas eslavosquienes emigraron a EEDD en '=') despu-s de casarse.

A principios de la d-cada de '=>) la familia 6antig se traslad desde :altimore a3ashington en el estado de 0aryland donde An&a traba& como lingista en la

:iblioteca del Congreso y 4obas imparti clases como profesor de matem$ticas en laDniversidad de 0aryland hasta que se retir de&ando su puesto de ;efe del6epartamento de 0atem$ticas poco despu-s de la %egunda !uerra 0undial.

El peque/o !eorge estudi en las escuelas "o9ell ;unior Migh %chool y Central Migh%chool. 6esde su infancia comen a mostrar un especial inter-s por la geometrainstigado tambi-n por su propio padre quien le propona complicados problemas degeometra proyectiva.

!eorge 6antig reali sus estudios universitarios en la Dniversidad de 0aryland dondeobtuvo una licenciatura en 0atem$ticas y 1sica en '=*K. %in embargo le defraud elhecho de no haber visto ni una sola aplicacin real de las matem$ticas en ninguna de lasmaterias que haba cursado.


9/38

En el verano de ese mismo a/o se cas con Anne%hmuner y la pare&a de reci-n casadosse mud a Ann Arbor. All continu sus estudios gracias a una beca MoraceFac2hamcon un m$ster en 0atem$ticas en la Dniversidad de 0ichigan. A excepcin de laEstadstica le pareci que los cursos eran demasiado abstractos por lo que slo deseabauna cosaH acabar sus estudios y enfocarse en el mundo laboral.

As en '=*B 6antig de& 0ichigan para traba&ar en un proyecto de estudio demercado @Drbanstudy of consumerpurchase@G como estadstico en el :ureau of +abor%tatistics. %in embargo dos a/os despu-s decidi completar sus estudios con un

6octorado en Estadstica ba&o la supervisin del famoso profesor ;ery8eyman en laDniversidad de :er2eley California.

1ue durante su primer a/o en :er2eley cuando protagoni una an-cdota que ha sidoconsiderada como una leyenda hasta que a/os despu-s el propio 6antig corrobor suveracidad. As en '=*= !eorge asista a un curso de Estadstica impartido por el

profesor ;ery8eyman el cual tena por costumbre proponer un par de e&ercicios en lapiarra al inicio de sus clases para que fuesen resueltos como tarea en el hogar. Dn da!eorge lleg tarde a clase y anot los dos problemas de la piarra pensando que setrataba de tarea para casa. Algunos das despu-s se los entreg al profesor 8eymandisculp$ndose por haber tardado un poco m$s de lo habitual ya que les parecieron @un

poco m$s difciles que los problemas ordinarios@. Dnas K semanas m$s tarde cuando;ery8eyman revis aquellas notas concienudamente y comprendi el gran hallagoque poda suponer se present en casa de su alumno un domingo a primera hora de lama/ana. Estaba impaciente por proponerle a 6antig la publicacin de un artculofundamentado en la resolucin de estos e&ercicios ya que se trataba de dos famosos

problemas no resueltos de la Estadstica. A ra de este hecho y a sugerencia de8eyman !eorge 6antig desarroll su tesis doctoral acerca de dichos problemas.

%in embargo no acabara el doctorado hasta '=K ya que cuando Estados Dnidos entren la contienda de la %egunda !uerra 0undial a finales de '=' interrumpi susestudios por segunda ve y se traslad a 3ashington para unirse a las 1ueras A-reas de

Estados Dnidos. All ocup un puesto de &efe en la subdivisin civil de an$lisis decombate en el Centro de Control Estadstico D.%.A.1. Meadquarters%tatisticalControlG.


10/38

%u labor consista en la recopilacin de datos y an$lisis de los combates a-reos n#merode misiones bombas lanadas aeronaves perdidas tasas de desercin .G as cmo lidiarcon las logsticas de la cadena de abastecimiento y la gestin de cientos de miles dediferentes tipos de recursos materiales y humanos. 4oda esa planificacin se llevaba acabo mediante t-cnicas manuales por lo que fueron estos problemas aparentemente

irresolubles los que estimularon la b#squeda de un modelo matem$tico y sentaron lasbases de lo que sera la programacin lineal. "or el traba&o realiado durante la %egunda!uerra 0undial fue galardonado con la medalla al excepcional servicio civil prestado al6epartamento de !uerra N3ar6epartmentsExceptionalCivilian%ervice0edalPG en'=.

Al terminar la guerra volvi a :er2eley para finaliar el doctorado que haba de&ado

interrumpido. Dna ve obtenido el ttulo le ofrecieron un puesto en la Dniversidad querecha por ser un cargo modesto aunque con un buen salario ' mil dlares anualesG.Fealmente fue disuadido de la idea de aceptar la oferta laboral por su mu&er a quien nole convenca debido al en su opinin escaso sueldo con el que les costara mantenerseteniendo ya un hi&o.

As pues en &unio de '=K se encontraba de nuevo en 3ashington considerando variasofertas de traba&o. 1inalmente persuadido por sus colegas de la D.%.A.1. se decant porel cargo de asesor matem$tico para las 1ueras A-reas. 4raba& en una metodologa paracalcular el tiempo de duracin de las etapas de un programa de despliegueentrenamiento y suministro logstico de forma m$s r$pida y eficiente a la utiliada hasta

el momento. %e trataba de intentar mecaniar todo el proceso de planificacin. Esto lellev a realiar sus grandes descubrimientos.

:as$ndose en el m-todo input5output ideado por el economista ruso 3assily+eontief en'=*= por cuyo traba&o recibi el "remio 8obelG estableci el problema general de"rogramacin +ineal. %in embargo los problemas planteados eran demasiado comple&os

para las computadoras m$s veloces de la -poca. %e haca necesario desarrollar unm-todo capa de encontrar soluciones en un tiempo raonable. En este punto entr en

&uego la intuicin geom-trica que 6antig haba desarrollado en su &uventud. %eg#n suspropias declaracionesH NComenc- observando que la regin factible es un cuerpoconvexo es decir un con&unto poli-drico. "or tanto el proceso se podra me&orar si sehacan movimientos a lo largo de los bordes desde un v-rtice al siguiente. %in embargoeste procedimiento pareca ser demasiado ineficiente. En tres dimensiones la regin se


11/38

poda visualiar como un diamante con caras aristas y v-rtices. En los casos de muchosbordes el proceso llevara a todo un recorrido a lo largo de ellos antes de que se pudiesealcanar el v-rtice ptimo del diamanteP. En el verano de '=B reali la primeraformulacin del m-todo %implex.

El primer problema pr$ctico resuelto con este nuevo m-todo fue elproblema denutricinque haba planteado !eorge ;oseph %tigler a finales de la d-cada anteriordebido al inter-s del e&-rcito americano por encontrar una dieta equilibrada paraalimentar a sus tropas que cumpliera con unos requisitos mnimos de nutricin y fueseeconmica. El problema que constaba de = ecuaciones y BB incgnitas fue resueltomanualmente tras '>) das de traba&o. %e demostr que el resultado obtenido apenasdifera unos c-ntimos de la solucin hallada anteriormente mediante m-todosheursticos resultando el nuevo m-todo %implex todo un -xito.

En esa -poca concretamente en &unio de '=B las 1ueras A-reas establecieron ungrupo de traba&o dedicado a me&orar los procesos de planificacin a gran escala que fue

llamado "royecto %COO" %cientificComputation of Optimal"rogramsG. !eorge6antig permaneci como &efe matem$tico de este grupo hasta '=(>.

El * de octubre de '=B 6antig visit el InstituteforAdvanced%tudy IA%G un centrode posgrado independiente ubicado en "rinceton 8ueva ;erseyG donde se realianinvestigaciones en diversos campos cientficos. All conoci a ;ohn von 8eumannconsiderado el me&or matem$tico del mundo quien le habl de su traba&o &unto a Oscar0orgenstern sobre la teora de &uegos. A lo largo de '= esta pare&a haba realiadoinvestigaciones sobre &uegos de suma cero &uegos en los que todos los participantesconocen a priori las estrategias y consecuencias del restoG que culminaron en el teoremaNminimaxP que afirma que existe una &ugada posible en la que minimiar su m$xima

p-rdida de ah su nombreG. Como resultado de sus investigaciones publicaron el libroN4heory of !ames and Economic:ehaviorP. 6e esta manera !eorge tuvo constancia

por primera ve de la importancia de la 4eora de la 6ualidad.
http://www.phpsimplex.com/teoria_metodo_simplex.htmhttp://www.phpsimplex.com/problema_dieta.htmhttp://www.phpsimplex.com/problema_dieta.htmhttp://www.phpsimplex.com/teoria_metodo_simplex.htmhttp://www.phpsimplex.com/problema_dieta.htmhttp://www.phpsimplex.com/problema_dieta.htm


12/38

A principio de la d-cada de los () concretamente en &unio de '=(> comen a traba&aren la FA86 Corporation FesearchA8d6evelopmentG una corporacin fundada en'=? por las 1ueras A-reas de Estados Dnidos con fines de investigacin y desarrollo.

%u cometido era la aplicacin del m-todo %implex en las computadoras con el ob&etivode obtener resultados en un tiempo mucho m$s reducido.

En la imagen se puede observar la portada de uno de los memor$ndum de investigacinque public en la FA86. %u referencia es F05'>K y fue publicado en '=( ba&o elttulo 8otes on +inear "rogrammingH 4hegeneralied %implex methodforminimiing alinear formunder linear inequalityrestrains. %e encuentra disponible para su descarga

&unto a otros documentos y memor$ndums en la p$gina oficial de FA86H999.rand.orgQpubsQresearchRmemorandaQF0'>K.html

En '=( 6antig &unto con otros dos compa/eros matem$ticos 6elbertFay1ul2erson y

%elmer 0artin ;ohnson lograron un hito matem$tico en optimiacin combinatoria alresolver el problema del Comercial ,ia&ero tambi-n conocido como problema del,ia&ante o por las siglas 4%" del ingl-s 4raveling%alesman"roblem. Consiste en hallarla ruta ptima para un vendedor que debe visitar un con&unto determinado de ciudadescumpliendo las siguientes condicionesH la distancia total recorrida debe ser mnimavisitar cada ciudad una #nica ve y regresar al punto de partida una ve finaliada laruta. El problema resuelto constaba de = ciudades una por cada estado de EEDDAlas2a y Ma9aii no se convirtieron en estados hasta '=(=G. %e aplicaron las recientest-cnicas de "rogramacin +ineal dando lugar al m-todo de los "lanos de Corte Cutting5"lanemethodG precursor del algoritmo de Famificacin y Acotacin :ranch and:oundalgorithmG. +os resultados de esta investigacin se publicaron en el artculoN%olution of a large5scale4raveling%alesman"roblemP. Este tipo de problemas tienem#ltiples aplicaciones m$s all$ de encontrar una ruta mnima en logstica siendo


13/38

utiliada en la actualidad en $reas como dise/o de chips secuenciacin del genomaobservaciones astronmicas de la 8A%A etc.

En general los problemas presentan par$metros con una alta componente aleatoria ofalta de fiabilidad en los datos debido entre otros factores a que no se puede determinar

con exactitud qu- ocurrir$ en el futuro. "or e&emplo en un problema de inversin enbolsa el tiempo afecta a la solucin incluyendo la incertidumbre de si los valores enbolsa se mantendr$n o sufrir$n una nefasta cada. Esto dio lugar a una nueva rama en la"rogramacin +ineal en el a/o '=(( llamada "rogramacin Estoc$stica o "rogramacin:a&o Incertidumbre ampliamente desarrollada de nuevo por !eorge :ernard 6antig yrecogida en su libro N+inear "rogrammingunderDncertaintyP. Evelyn 0artin+ansdo9ne:eale tambi-n llev a cabo desde Inglaterra de forma paralela eindependiente investigaciones en esta $rea.

%in embargo las investigaciones de !eorge 6antig no se limitaron #nicamente a lascitadas sino que tambi-n incluyen aplicaciones de variables discretas problema de la

mochila red y rutas de camino m$s corto el m-todo %implex revisado y mucho m$s.Dn e&emplo de ello es otro m-todo ampliamente utiliado hoy en daH el principio dedescomposicin que desarroll &unto a "hilip 3olfe entre '=(= y '=K). Conocidocomo el m-todo de 6escomposicin de 6antig53olfe establece pautas para encontrarla solucin de problemas de gran tama/o es decir que implican grandes cantidades dedatos y variables. Como curiosidad existe un m-todo dual a -ste llamado m-todo de6escomposicin de :enders de gran utiliacin en la actualidad en "rogramacinEstoc$stica.

!eorge regres a la Dniversidad de :er2eley en '=K) donde comen una brillantecarrera como profesor del departamento de Ingeniera Industrial tutor y asesor paraalumnos de doctorado. Ese mismo a/o fund el Centro de Investigacin OperativaOperationsFesearch CenterG y se erigi como director del mismo.

6urante este periodo en :er2eley escribi su gran libro de referencia N+inear

"rogramming and ExtensionsP publicado en agosto de '=K*. Esta publicacin recoge eltraba&o realiado en el "ent$gono y en la FA86 Corporation describiendo entre otros


14/38

el m-todo %implex desde su teora m$s b$sica hasta su uso para resolver problemasreales de distinta ndole. Es posible descargar este libro en formato "61 desde la p$ginaoficial de FA86H 999.rand.orgQpubsQreportsQF*KK.html.

Alrededor de '=K* 6antig propuso a la administracin de la Dniversidad de %tanford

"alo AltoG la creacin de un programa interdepartamental de Investigacin Operativaentre ambas universidades aunque la propuesta fue rechaada. 4res a/os despu-s6antig comenara a traba&ar en la Dniversidad de %tanford como docente en eldepartamento de Investigacin de Operaciones y Ciencias de la Computacin. !eorgeexplica con una an-cdota que uno de los motivos de su traslado desde :er2eley a%tanford era una plaa de aparcamiento en la misma puerta del departamento dondetraba&ara. %in embargo tuvo tan mala suerte que al trasladarse todo el aparcamiento yahaba desaparecido incluida su deseada plaa.

+os avances en computacin de la d-cada de los K) permitieron afrontar la resolucinde problemas reales en tiempo finito. 0otivado por esta ran 6antig fund en '=KB

en la Dniversidad de %tanford el %ystemsOptimiation+aboratory %O+G para lainvestigacin b$sica y aplicada de programacin matem$tica a gran escalaH desarrollo dealgoritmos formulacin de modelos y produccin de soft9are. El traba&o de estelaboratorio abarcaba problemas de planificacin de inversiones a trav-s del tiempodise/os de ingeniera y optimiacin sistemas fsicos biolgicos y ecolgicos

planificacin urbana y sistemas de transporte. Entre los proyectos de %O+ destaca elproyecto "I+O4 para una me&or planificacin y ahorro en el sector energ-tico deEstados Dnidos.

!eorge 6antig visit en varias ocasiones el International Institute ofApplied%ystemsAnalysis IIA%AG ubicado en +axenburg ciudad a *) 2m de ,ienaAustriaG. El IIA%A es una organiacin no gubernamental de investigacin donde sellevan a cabo estudios cientficos en m#ltiples $reas como economa tecnologaambiental y social. En '=B* pas un a/o sab$tico &unto con su esposa Annecolaborando como &efe del grupo de metodologa en las instalaciones del IIA%A. Dna

an-cdota protagoniada por !eorge 6antig expone su inter-s en la optimiacin deproblemas reales. 6urante su estancia all un da !eorge se percat de un camin


15/38

inusualmente largo parado frente a su oficina y poniendo en duda las venta&as de tallongitud pregunt al administrador Futh %teiner acerca del contenido del camin su

procedencia ruta y cmo era posible que circulara a trav-s de las estrechas calles. +asrespuestas de Futh fueron que el camin transportaba muebles desde %alburg via&ando

por la autopista y maniobrando para pasar por calles. !eorge estudi los datos y poco

tiempo despu-s coment a Futh que la compa/a de transporte podra ahorrarse el )Lde los gastos utiliando camiones m$s peque/os y le sugiri informar de ello a laempresa.

!eorge continu su labor como profesor en la Dniversidad de %tanford hasta '=B* a/oen que obtuvo la c$tedra C. A. Criley en Ciencias del 4ransporte NC. A.CrileyEndo9edChair in 4ransportation%ciencePG. %e retir oficialmente en '=BB aunque

permaneci en activo hasta '=?( como profesor em-rito.

+a excelente y enorme labor investigadora que desarroll a lo largo de su vida y losfascinantes resultados descubrimientos y aportes a la ciencia fueron determinantes para

ser merecedor de una gran cantidad de premios y reconocimientos aunque no lleg aconseguir el "remio 8obel.

As en '=B( !eorge :ernard 6antig fue el primer galardonado con el premio ;ohn von8eumann 4heory"rie otorgado por el InstituteforOperationsFesearch and the0anagement %ciences por su labor continuada y contribucin fundamental en estoscampos.

4extualmente Npor la invencin de la "rogramacin +ineal y el descubrimiento dem-todos que condu&eron a aplicaciones cientficas y t-cnicas a gran escala de los

problemas importantes de logstica planificacin y optimiacin de redes y por elempleo de ordenadores para hacer un uso eficiente de la teora matem$tica descubiertaPle fue concedida en '=B( la 0edalla 8acional de Ciencias en la disciplina dematem$ticas estadstica y computacin N8ational0edal of %cience inthe0athematical %tatistical and Computer%ciences disciplinePG. %iendo esta la mayordistincin en ciencias de los Estados Dnidos la ceremonia tuvo lugar el '? de Octubrede '=BK en la Casa :lanca donde el presidente !erald 1ord hio entrega del premio.


16/38

!eorge recibi doctorados Nhonoris causaP en diversas universidades de todo el mundo.Cabe destacar el de su universidad alma mater de 0aryland en '=BK con la cita Nla"rogramacin +ineal de 6antig ha sido una de las principales fueras impulsoras de laaparicin de una nueva disciplina matem$tica para toma de decisiones llamadaInvestigacin de Operaciones en la d-cada de los ()P.

En reconocimiento a su dedicacin obtuvo distinciones tanto nacionales comointernacionales. Algunas de ellas fueron el "remio de la Academia 8acional de Cienciasen 0atem$ticas Aplicadas y An$lisis 8um-rico N8ationalAcademy of %cienceA9ard inApplied0athematics and 8umericalAnalysisPG en '=BB el Marvey "rie en Ciencia y4ecnologa de la Dniversidad de 4echnion NMarvey "rie in %cience and 4echnologyPGde Israel en '=?( y la 0edalla de "lata de la %ociedad :rit$nica de Investigacin deOperaciones N%ilver0edal of the :ritish OperationalFesearch%ocietyPG en '=?K. 4uvoel honor de ser la primera persona incluida en el Mall of 1ame de la International1ederation of OperationalFesearch%ocieties I1OF%G.

El grupo de ex alumnos del profesor 6antig formado por F. 3. Cottle E. +. ;ohnsonF. 0. van %ly2e y F. ;. :. 3ets fundaron en su honor el premio 6antig"rie en '=?>.6icho premio es concedido cada * a/os por la 0athematicalOptimiation%ociety0O%G y la %ocietyfor Industrial and Applied0athematics %IA0G.

A lo largo de su vida public multitud de traba&os y varios libros. %in embargo el libroN+inear "rogrammingP compuesto por dos vol#menes en los que plasm las ideas

principales de sus estudios e investigaciones es considerado como la :iblia de la"rogramacin +ineal y la Investigacin Operativa. El primero de ellos con el subtituloNIntroductionP fue publicado en '==B mientras que el segundo N4heory andExtensionsP no aparecera hasta >))*. Ambos fueron escritos con&untamente con0u2und 8. 4hapa. En el primer volumen tal y como su nombre indica trata de losaspectos b$sicos de la "rogramacin +ineal y aplicaciones reales. "or su parte en elsegundo se ampla la teora y se incluyen variantes del m-todo %implex m-todos del

punto interior e incluso teora de &uegos entre otros.

El propio 6antig se sorprendi de que el m-todo %implex funcionara con tantaeficiencia tal y como se puede comprobar en una entrevista de '===. Citando sus

propias palabrasH N+a mayor parte de las ocasiones el m-todo %implex resolvaproblemas de m ecuaciones en >m o en *m pasos algo realmente impresionante. En

realidad nunca pens- que fuese a resultar tan eficiente. "or aquel entonces yo a#n tenapoca experiencia con problemas de grandes dimensiones y no confiaba en mi intuicingeom-trica. "or e&emplo pensaba que el procedimiento requerira demasiados pasos de


17/38

un v-rtice al siguiente. En la pr$ctica son muy pocos pasos. 6icho con pocas palabrasla intuicin en espacios de grandes dimensiones no es muy buena gua. %lo ahora (>a/os despu-s de haber propuesto el m-todo %implex por primera ve la gente est$comenando a tener una idea de por qu- el m-todo funciona tan bien como lo haceP.

El '* de 0ayo de >))( !eorge :ernard 6antig falleci a la edad de =) a/os en sucasa de %tanford debido a complicaciones con la diabetes y problemas cardiovasculares.

$.- %&u' es la Programacion Lineal(

La 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, sobre todo, de las

Ciencias Sociales.

Nos centraremos en este tema en aquellos problemas simples de programacin

lineal, los que tienen solamente 2 variables, problemas bidimensionales; los

sistemas de mas variables, el procedimiento no es tan sencillo y se resuelven

por el llamado mtodo Simplex (ideado por G.B.Danzig, matemticoestadounidense en 1951).

Recientemente (1984) el matemtico indio establecido en Estados Unidos,

NarendaKarmarkar, ha encontrado un algoritmo, llamado algoritmo de

Karmarkar, que es mas rpido que el mtodo simplex en ciertos casos. Los

problemas de este tipo, en el que intervienen gran numero de variables, se

implementan en ordenadores.

PROGRAMACIN LINEAL1. Introduccin+a programacin lineal es una t-cnica matem$tica relativamente reciente siglo 77G

que consiste en una serie de m-todos y procedimientos que permiten resolver problemasde optimiacin en el $mbito sobre todo de las Ciencias %ociales.


18/38

8os centraremos en este tema en aquellos problemas simples de programacin lineallos que tienen solamente > variables problemas bidimensionales. "ara sistemas de m$svariables el procedimiento no es tan sencillo y se resuelven por el llamado m-todo%implex ideado por !.:.6anig matem$tico estadounidense en '=('G.Fecientemente '=?G el matem$tico indio establecido en Estados Dnidos

8arendaarmar2ar ha encontrado un algoritmo llamado algoritmo de armar2ar quees m$s r$pido que el m-todo simplex en ciertos casos. +os problemas de este tipo en elque intervienen gran n#mero de variables se implementan en ordenadores.2. Inecuaciones lineales con dos variablesDna inecuacin lineal con > variables es una expresin de la formaHaxS by)cdonde el smbolo )puede ser tambi-n * T o bien UG donde a b y c son n#merosreales yx ey las incgnitas.Fesolver una inecuacin consiste en encontrar todos los valores de las incgnitas queverifican dicha inecuacin. El con&unto de estos valores se denomina solucin generalde la inecuacin. Dna solucin particular de la inecuacin es un par de valores

cualquiera que satisfaga dicha inecuacin.6os o m$s inecuaciones son equivalentes si tienen la misma solucin."ara resolver estas inecuaciones hay que representar gr$ficamente en el plano la rectadada por la correspondiente ecuacin lineal y marcar una de las dos regiones en quedicha recta divide al plano.

EjemploH%i queremos resolver la inecuacin >x S *y ** representamos en primer lugar la recta>x S*y V *.6icha recta divide al plano en dos regiones una de las cuales es la solucin de lainecuacin. "ara saber qu- parte seguiremos el siguiente procedimientoH%e toma un punto cualquiera que no perteneca a la recta por e&emplo el ' >G. "ara quedicho punto sea solucin tendr$ que cumplir la desigualdad por lo que sustituimos enla inecuacin inicial el punto elegido ' >GH> W ' S* W > ** +? **Como esta #ltima desigualdad es evidentemente cierta concluimos que el punto ' >Ges una solucin particular de la inecuacin y por tanto el semiplano que contiene a dicho

punto ' >G es la solucin general es decir la solucin general es el semiplano superior.%i hubi-ramos elegido el punto ) )G al sustituir en la inecuacin tendramos queH> W ) S* W ) ** +) **Esta #ltima desigualdad es evidentemente falsa y por tanto concluimos que el punto ))G no es una solucin particular de la inecuacin y por tanto el semiplano que contiene

a dicho punto ) )G no es la solucin general. +a solucin general de la inecuacin es elotro semiplano es decir el semiplano superior.En ambos casos se llega a que la solucin general del sistema esH. !iste"as de inecuaciones lineales con dos inc#nitasDn sistema de inecuaciones lineales con dos incgnitas es un con&unto de dos o m$sinecuaciones lineales con dos incgnitas.+lamaremos regin factible al con&unto de puntos xyG que satisfacen todas lasdesigualdades que forman el sistema y que constituyen la solucin general.+a regin factible se puede calcular hallando la interseccin de las regiones que sonsolucin de cada una de las inecuaciones que forman el sistema.

EjemploH

Fesolver el sistema de inecuaciones siguienteH >**))xyxy,) * *


19/38

En primer lugar representamos las rectas >x S*y V *x V ) ey V ) y posteriormenteseleccionamos el semiplano solucin de cada una de las desigualdades que forman elsistemaH>x S *y )*

x*)

y*)+a regin factible que es la ona interseccin de las tres onas anteriores esHEl tri$ngulo rayado es la solucin del sistema.+a solucin de un sistema de inecuaciones lineales con dos incgnitas es un con&untoconvexo que puede ser acotado o no. +a frontera de este con&unto puede pertenecer o noa la solucin dependiendo de si las inecuaciones iniciales son estrictas T UG o no )*G.+lamaremos v-rtices a los puntos que son interseccin de las rectas frontera. %u c$lculoes sencillo pues se reduce a resolver los sistemas de dos ecuaciones lineales con dosincgnitas que se obtienen al igualar las ecuaciones de las rectas correspondientes.En el e&emplo anterior los calcularamos los v-rtices resolviendo los siguientes

sistemasH>**)xyx, 'G >**)xyy, >G *G ))xy

Cuyas soluciones son respectivamenteH)'xy 'G >G *Q>)xy ))xy *G

Estos tres puntos son los v-rtices de la regin factibleH6e manera general el con&unto solucin de un sistema de inecuaciones lineales puedeser un semiplano una semirrecta un segmento un punto o el con&unto vaco.$. Pro#ra"acin linealDn problema de programacin lineal es aquel en el que pretendemos hallar el m$ximo oel mnimo de una funcin llamada funcin ob&etivo su&eta a una serie de restriccionesque vienen expresadas en forma de inecuaciones.%i hablamos de un problema de programacin lineal de dos variablesx ey se trata deoptimiar hacer m$xima o mnima seg#n los casosG una funcin llamada funcinob&etivoG de la formaH

F xyG VAxSBy

su&eta a una serie de restricciones dadas mediante un sistema de inecuaciones linealesdel tipoH'''>>nnaxbycaxbycaxbyc,)>n

,),)

+os puntos del plano que cumplen el sistema de desigualdades forman un recintoconvexo acotado poligonalG o no acotado llamado regin factible del problema.


20/38

4odos los puntos de dicha regin cumplen el sistema de desigualdades. %e trata debuscar entre todos esos puntos denominados soluciones factibles aquel o aquellos quehagan el valor deF xyG m$ximo o mnimo seg#n sea el problema.6e todas esas soluciones factibles aquellas que hacen ptima m$xima o mnimaG lafuncin ob&etivo se llaman soluciones ptimas.

En general un problema de programacin lineal puede tener una infinitas o ningunasolucin. "ero en todo caso lo que s se verifica es queH%i hay una #nica solucin ptima -sta se encuentra en un v-rtice de la regin factible ysi hay infinitas soluciones ptimas se encontrar$n en un lado de la regin factible.Es posible que no haya solucin ptima pues cuando el recinto es no acotado lafuncin ob&etivo puede crecer o decrecer indefinidamente."ara resolver el problema podemos abordarlo de dos formas pero antes a aplicarcualquiera de ellas siempre hay que dibu&ar la regin factible resolviendo el sistema deinecuaciones lineales correspondiente como se ha visto anteriormente la reginfactible puede estar acotada o noG y se calculan los v-rtices de dicha regin.$.1 M%todo anal&tico

Consiste simplemente en sustituir cada uno de los v-rtices de la regin factible en lafuncin ob&etivo.%e tiene queH%i la funcin ob&etivo alcana un valor m$ximo o mnimoG en un #nico v-rtice esteser$ la solucin del problema.%i el valor m$ximo o mnimoG se alcana en dos v-rtices la solucin ser$n todos los

puntos del lado de la regin que une esos dos v-rtices.EjemploHDn estudiante dedica parte de su tiempo al reparto de propaganda publicitaria. +aempresaA le paga ( c-ntimos de euro. por cada impreso repartido y la empresaB confolletos m$s grandes le paga B c-ntimos de euro por impreso. El estudiante lleva dos

bolsasH una para los impresosA en la que caben '>) y otra para los impresosB en laque caben ')). Ma calculado que cada da es capa de repartir '() impresos comom$ximo. +o que se pregunta el estudiante esH Xcu$ntos impresos habr$ que repartir decada clase para que su beneficio diario sea m$ximoY"ara plantear el problema llamemosH

x V nZ de impresos diarios tipoA repartidos.y V nZ de impresos diarios tipoB repartidos.+a funcin ob&etivo es el beneficio que obtiene del repartoHF xyG V (x S By+as restriccionesH

8#mero m$ximo de impresos tipoA que caben en la bolsa +) )x )'>)

8#mero m$ximo de impresos tipoA que caben en la bolsa +) )y )'))8#mero m$ximo de impresos que es capa de repartir +x Sy )'()En este e&emplo la regin factible esH%us v-rtices sonHA V ) '))G : V () '))G C V '>) *)G 6 V '>) )G+os valores de la funcin ob&etivoH

F ) '))G V ( W ) S B W ')) V B))F () '))G V ( W () S B W ')) V =()F '>) *)G V ( W '>) S B W *) V ?')F '>) )G V ( W '>) S B W ) V K))6ebe repartir () impresos tipoA y ')) tipoBpara una ganancia m$xima diaria de =()

c-ntimos de euro esto es =( euros.EjemploH


21/38

0inimiarF xyG V *x S *y su&eta a las restriccionesH(**'>'>xyyxyxyxyx,*),

K>

/*/,) /) +a regin factible es en este casoH+os v-rtices respectivos sonHA V ' G : V 'G C V B >G 6 V '>)**y E V ')'=**+os valores de la funcin ob&etivoH

F ' G V * W ' S * W V '(F 'G V * W S * W ' V '(F B >G V * W B S * W > V >BF '>)**V * W ' S * W *>)* V *F ')'=**V * W ') S * W *'= V >= *Observamos que el valor mnimo se alcana en A y en : y por tanto en todos los puntoscomprendidos entre ellos es decir el problema tiene infinitas soluciones todos los

puntos del segmento A:G.$.2. M%todo #r'(ico"ara llevar a cabo este m-todo seguiremos los siguientes pasosHaG %e representa la lnea de beneficio nulo que viene dada por la ecuacinF xyG V )es decirH

AxSByV )bG %e dibu&an las rectas de nivel es decir rectas paralelas a la recta de beneficio nuloque pasan por todos los v-rtices de la regin factible es decir se traan paralelas a larectaAxSByV ) por todos los v-rtices.cG %e observa en qu- v-rtice la funcin ob&etivo se hace m$xima o mnimaG sin m$sque tener en cuenta cu$l de las rectas tiene mayor o menorG ordenada en el origen.6ependiendo de la funcin ob&etivo que tengamos y de la regin factible en la queestemos estudiando su comportamiento se pueden presentar distintas posibilidades quese recogen en el siguiente cuadro las rectas de nivel aumentan en el sentido de lasflechasGHSOLUCIONESnicaInfinitas

No tieneProbleasde !"iosProbleasde #nios

EjemploH0aximia y 0inimia la funcinF xyG Vx Sy su&eta a las restriccionesH))>>xyxyxy** ,* ,)

+a regin factible esH+os v-rtices son los puntosH


22/38

A V ) >G : V > )G y C V )G4raamos en moradoG la recta de beneficio nulo x Sy V )G y las paralelas a ella restasde nivelG que pasan por los v-rtices de la regin factible. %e observa gr$ficamente quede las tres paralelas traadas la que corta al e&e OY en un punto mayor es la que pasa

por el punto )G que por tanto ser$ la solucin ptima al problema de m$ximos

planteado."ara saber cu$l es este valor m$ximo sustituimos en la funcinHF )G V S ) V +uego la funcin tiene su solucin ptima en )G donde toma el valor ."or otra parte la recta de nivel hace mnima la funcin es la que pasa por los v-rtices Ay : y por tanto el mnimo se presenta en todos los puntos del segmento A:. El

problema tiene infinitos mnimos.

Curso: 2 Bachillerato de Ciencias Sociales

0. 7E=>2>?2 @ AE;$>2BLB#C".

n !ro"le#a de Pro$ra#aci%n Lineal consiste en optimiar+ma5imiar o minimiar la funcin9

D = + 5%, 51, ... ,5n D c%5% c151 ... cn5n

sujeto a9

a%%5% a%151 . . . a%n5nFV Gb

a1%5% a1151 . . . a1n5nFD Gb1

. . .

am%5% am151 . . . amn5nFDGbm

5%, 51 , . . . , 5n [H

" la funcin D = + 5%, 51, ... ,5n D c%5% c151 ... cn5n sele denomina &unci%n o"'eti(oo funcin criterio.


23/38

Los coeficientes c%, c1, ... , cnson nmeros reales y se llaman

coe&icientes de "ene&icio o coe&icientes de costo. /on datos de

entrada del problema.

5%, 51, ... , 5n son las (aria"les de decisi%n +o niveles de

actividad que deben determinarse.

Las desigualdades ai%5% ai151 . . . ain5nFbi , con i D

%, ... , m se llaman restricciones.

Los coeficientes aij , con i D %, ... , m y j D %, ... , n son

tambin nmeros reales conocidos y se les denomina coe&icientestecnol%$icos.

El vector del lado derec*o, es decir los trminos bi , con i D

%, ... , m, se llama (ector de dis!oni"ilidadeso requerimientos y

son tambin datos conocidos del problema.

Las restricciones 5jGH con j D %, ... , n se llaman

restricciones de no ne$ati(idad)

"l conjunto de valores de +5%, 51, ... ,5n que satisfacen

simultneamente todas las restricciones se le denomina re$i%n

&acti"le.


24/38

2. Metodologa de la Investigacin de OperacionesEl enfoque de sistemas a un problema es caracterstico en la IO consiste en examinartoda el $rea que es responsabilidad del administrador y no una en particular\ esto

permite que el grupo de IO observe los efectos de acciones fuera del $rea de

localiacin del problema lo que puede permitir resolver el problema verdadero y noslo sus sntomas. Adem$s debe incluirse una base cuantitativa o modelo para la tomade decisin en la solucin del problema pero en algunos casos las respuestas dadas porla computadora conducir$n a la necesidad de ciertas modificaciones que refle&en lafutura condicin del negocio o bien ser$ una gua a seguir por el administrador sinnecesidad de hacer cambios.

+a investigacin de operaciones proporciona la oportunidad de que sus resultados seutilicen en la toma de decisiones a niveles administrativos superiores medianos y ba&os.+a experiencia del administrador las futuras condiciones del negocio y los resultados de

un modelo matem$tico forman la me&or combinacin para la planeacin organiacindireccin y control de las actividades de la empresa. El procedimiento de siete pasosmostrado en el siguiente diagrama puede constituir una metodologa de accin alaplicar la IO.


25/38

$ig%ra &. 'iagraa con etodolog#a de la investigaci(n de operaciones

Paso 1.- Identi9car el pro$lema.

Comiena con la observacin de los fenmenos que rodean el problema\ hechosopiniones y sntomas relativos al mismo. Esto incluye la especificacin de losob&etivos de la organiacin y de las partes a analiar de la misma. En algunasocasiones puede que el problema no est- bien definido porque entran enconflicto los ob&etivos como es maximiar la utilidad pero tambi-n es deseableminimiar los costos totales lo cual es improbable lograr simult$neamente\ portal motivo se requiere di$logo y acuerdos entre los miembros del equipo de IO y


26/38

la parte corporativa para decidir un ob&etivo global. 4ambi-n las primerasobservaciones pueden resultar con ob&etivos en conflicto como es undepartamento de produccin que desea programar grandes y prolongadascampa/as de un slo artculo para disminuir los costos de preparacin y monta&ede sus m$quinas. "ero en contraste si se cumple lo anterior creceran losinventarios de materia prima y de producto tanto en proceso como terminadocausando serios problemas en departamentos deH ventas contabilidad y finanas.6e este modo ventas desea un gran inventario pero muy variado con una

produccin muy flexible\ por su parte finanas desea mantener el inventario ba&oy me&orar las inversiones de capital. Cuando muchos factores de esta claseconcurren en el problema es indispensable la aportacin de la interdisciplina delequipo de IO pues es raonable que las fases individuales de un problema secomprendan y analicen me&or por los que tienen el adiestramiento especialnecesario en los campos apropiados. "or e&emplo un banco desea reducir los

gastos relacionados con los salarios de los ca&eros pero manteniendo un niveladecuado de servicio a los clientes tiempo de espera raonable para el cliente yde ocio para los ca&erosG. +os aspectos funcionales del banco que influyen paraconseguir los ob&etivos pueden ser los que siguenH

+legadas promedio al banco de clientes por hora pues conformeaumenta se deben instalar ca&eros adicionales para tener el nivel deseadode servicio.

"romedio de clientes servidos por hora de uno o m$s ca&eros.

Efecto sobre los ob&etivos del banco de mantener filas colasG para cadaca&a o formar una sola que distribuye clientes conforme se desocupan lasca&as.

Intercambio entre filas de clientes con desorden en sistema de cola porca&a.

Paso 2.- O$servar el sistema

%e determinan aquellos factores que afectan como sonH variables limitaciones ysuposiciones. +os factores variables que requieren decisiones como es el nivelde inventario y la necesidad de publicidad\ las limitaciones restringen el uso derecursos comoH dinero tiempo personal capacidad productiva existencias demateria prima\ las suposiciones pueden ser paraH precios de producto ycompetencia del mercado. May que reunir datos para estimar valores de los

par$metros que afectan el problema de la organiacin. En el e&emplo del bancoalgunos par$metros pueden serH

+legadas promedio de clientes por hora tasaG durante la &ornadabancaria.


27/38

"romedio de clientes servidos por hora en ca&a con diferente tama/o defila.

Paso :.- ;ormular un modelo matem para a&ustes de observacin.


28/38

Paso =.- 5eri9car el modelo y usarlo en predicciones

%e trata ahora de verificar si el modelo matem$tico dise/ado en el paso *anterior es una buena representacin de la realidad que se estudia calificando suvalide para situaciones actuales. Cuando sea posible se debe obtener

informacin respecto al comportamiento del modelo al cambiar valores en susvariables y par$metros especialmente si estos #ltimos no se pueden determinarcon exactitud esto se conoce como an$lisis de sensibilidad o experimentacinsobre el modelo y con ayuda de la computadora cambiando los valores avariables y par$metros que representen las situaciones reales incluyendo lasdesventa&osas. 1recuentemente si la experimentacin es muy limitada se

pueden tener resultados enga/osos que posteriormente en aplicacin a poblacinmayor se debe regresar a corregir los criterios equivocados en los pasos

precedentes > y *. Con el an$lisis de sensibilidad se puede a&ustarH

+a medida de efectividad u ob&etivo como es el dinero como utilidad ocosto.

Fevisin de las variables ba&o control o de decisin.

Fevisin de las variables no controlables y ambientales como demanda yubicacin de clientes precios de la competencia o nivel de actividadeconmica.

Felacin de los factores ya mencionados con las restricciones propuestas.

En particular para el e&emplo del banco si los valores de prediccin para eltiempo de espera en cola y el nivel de servicio no est$n cerca de los valoresreales obtenidos en la observacin del paso > seguramente se necesitar$ otromodelo o al menos revisar los par$metros considerados al mismo. Este caso es

para analiar si el modelo es v$lido para las situaciones de poca demanda declientes y para los das de pago acostumbrados.

Paso >.- 7eleccionar una alternativa

%i existe una alternativa que se adapte me&or a los ob&etivos de la organiacincon el modelo matem$tico propuesto entonces debe seleccionarse para su

presentacin a los responsables de decidir pero frecuentemente la situacin noes clara para hacerlo as porque el con&unto de opciones resultantes est$ su&eta arestricciones difciles de cumplir o imposibles.

Paso ?.- Presentar resultados a la organi#acin

Al terminar la etapa de pruebas y desarrollo de un modelo con solucin

aceptable se puede presentar una recomendacin o bien varias alternativas paraque la organiacin seleccione la que me&or se a&usta a sus necesidades.


29/38

!eneralmente hay necesidad de mostrar varias corridas de computadora en cuyocaso es conveniente instalar un sistema bien documentado para aplicar el modeloseg#n lo establecido por la administracin. Este sistema debe incluir tanto elmodelo como el procedimiento de solucin an$lisis de sensibilidad y los

procedimientos operativos para su probable implantacin. "ero dado el casomuy frecuente de rechao a la solucin propuesta ya sea por definicinincorrecta o debido a la poca participacin del tomador de decisin entoncesser$ necesario regresar al paso '> *.

Paso @.- Implantar y evaluar las recomendaciones

%i la organiacin acepta el estudio con la propuesta de solucin se procede a laimplantacin que incluye el sistema de computo y la vigilancia constante paralas actualiaciones por cambios en el sistema. Con frecuencia se requiere un

n#mero considerable de programas integrados. +as bases de datos y los sistemasde informacin administrativos puede proporcionar informacin actualiadacada ve que el modelo se utilice en cuyo caso se necesitan programas deinterfa interaccin con el usuarioG para hacer amigablela operacin delsistema propuesto. 4ambi-n se pueden instalar programas adicionales quemane&en los resultados del implante de manera autom$tica o bien un sistemainteractivo de computadora denominadosistema de soporte de decisiones paraayudar a la direccin con informacin relevante en sus decisiones. %e puedegenerar informes con la terminologa usual en el medio que relacionen losresultados entregados por el sistema implantado y las implicaciones.

6ependiendo del tama/o del estudio se pueden requerir meses o a/os paraimplantar desarrollar probar e instalarG el sistema computariado y

posteriormente su mantenimiento en las indispensables actualiaciones deprogramas modelo y a#n de equipo hard9areG. Cualquier falla o rechao en laimplantacin puede hacer necesario la revisin y a&uste en los pasos ' > * y .

U)ICACI*N 'E LA IO EN LAS O+,ANI-ACIONES.+a investigacin deoperaciones ha tenido un impacto impresionante en el mundo al me&orar la eficiencia demuchas organiaciones. Ma hecho contribuciones significativas al incremento de la

productividad dentro de la economa de muchos pases de ellos m$s de *) que sonmiembros de la International 1ederation of OperationalFesearch%ocieties I1OF%G. Alinicio de la d-cada de los =) el D.%. :ureau of +abor %tatistics predi&o que la IO serala *] $rea profesional de m$s r$pido crecimiento para los egresados graduados entre'==) y >))( en Estados Dnidos con '))))) personas laborando como analistas de IOen el >))(.

El problema de la localiacin de un grupo de IO dentro de la empresa ha merecido unagran atencin sin embargo no hay una posicin preferida para las organiaciones\ perose puede decir que los que han tenido -xito dependen de los niveles &er$rquicos

superiores de la institucin lo cual da una base firme para su funcionamiento conobligaciones de enfrentar los problemas de tomar decisiones y de utilidad inmediata


30/38

para la administracin. 4eniendo el respaldo de la autoridad superior con prestigiodentro de la empresa se podr$n cruar los linderos departamentales y obtener lainformacin necesaria para dar soluciones.

!eneralmente el grupo de IO se asocia con el de sistemas de procesamiento de datospues el acceso a las computadoras es el apoyo indispensable para sus actividades por loque no es raro que est-n integrados dada la posibilidad de tener el me&or mane&o de lainformacin deseada y ordenada como convenga. 6e este modo ambos grupos el de IOy el de sistemas de procesamiento de datos se complementan en t-rminos de losob&etivos de la institucin.

"ara la mayora de los estudios de IO se recomienda un equipo compuesto de analistasy de personal involucrado en el problema que se enfrenta este grupo informa a unComit- 6irectivo de la Administracin integrado por los directivos departamentales que

est$n afectados en el problema estudiado de IO los cuales a su ve se re#nen con laadministracin superior para reportar los progresos. +os comit-s allanan el camino del

personal de IO para obtener la cooperacin del personal de operacin y su aceptacin.

4opicovervie9

Identi9cacin de Pro$lemas de Programacin Lineal

Administracin de produccin y operaciones

8orman !aither and !reg 1raier. ?thed. 0exico CityH Cengage+earning >))). p>))5>)'. CO"))) Cengage+earning Editores %.A. de C.,.

ead7peaer

6scucCar
http://go.galegroup.com/ps/eToc.do?rcDocId=GALE%7CCX3002500082&inPS=true&prodId=GVRL&userGroupName=unad&resultClickType=AboutThisPublication&contentModuleId=GVRL&searchType=&docId=GALE%7C2VGHhttp://go.galegroup.com/ps/eToc.do?rcDocId=GALE%7CCX3002500082&inPS=true&prodId=GVRL&userGroupName=unad&resultClickType=AboutThisPublication&contentModuleId=GVRL&searchType=&docId=GALE%7C2VGHhttp://rs.go.galegroup.com/cgi-bin/rsent?customerid=4476&lang=es_us&readid=documentDisplay&url=http%3A%2F%2Fgo.galegroup.com%2Fps%2Fi.do%3Bjsessionid%3DF91FCDEFEE0522EF2BB8AE8A89C70934.omni6%3Fid%3DGALE%257CCX3002500082%26v%3D2.1%26u%3Dunad%26it%3Dr%26inPS%3Dtrue%26prodId%3DGVRL%26userGroupName%3Dunad%26ReadSpeaker%3Dtrue%26p%3DGVRL%26action%3Dinterpret%26sw%3Dw%26asid%3D814ccd79f13b7fa65d9cc8e6a2b5ffb3http://go.galegroup.com/ps/eToc.do?rcDocId=GALE%7CCX3002500082&inPS=true&prodId=GVRL&userGroupName=unad&resultClickType=AboutThisPublication&contentModuleId=GVRL&searchType=&docId=GALE%7C2VGHhttp://go.galegroup.com/ps/eToc.do?rcDocId=GALE%7CCX3002500082&inPS=true&prodId=GVRL&userGroupName=unad&resultClickType=AboutThisPublication&contentModuleId=GVRL&searchType=&docId=GALE%7C2VGHhttp://rs.go.galegroup.com/cgi-bin/rsent?customerid=4476&lang=es_us&readid=documentDisplay&url=http%3A%2F%2Fgo.galegroup.com%2Fps%2Fi.do%3Bjsessionid%3DF91FCDEFEE0522EF2BB8AE8A89C70934.omni6%3Fid%3DGALE%257CCX3002500082%26v%3D2.1%26u%3Dunad%26it%3Dr%26inPS%3Dtrue%26prodId%3DGVRL%26userGroupName%3Dunad%26ReadSpeaker%3Dtrue%26p%3DGVRL%26action%3Dinterpret%26sw%3Dw%26asid%3D814ccd79f13b7fa65d9cc8e6a2b5ffb3


31/38

eDto completo

P delinea brevemente las cuatro caractersticas b$sicasdel problema. Cuando se cumplen todos estos requisitos la programacin lineal puedeser una herramienta adecuada para el an$lisis.

+os e&emplos K.' y K.> son muestras en la administracin de la produccin y de lasoperaciones de problemas apropiados para solucin de programacin lineal. %iga estose&emplos con cuidado y vea si puede identificar el ob&etivo las alternativas disponiblesy la naturalea de las restricciones las tres primeras caractersticas de los problemas de

programacin DnealG. "or ahora no se preocupe de los requerimientos matem$ticos.

Dna ve que podamos discernir qu- es y qu- no es un problema de programacin linealel siguiente paso ser$ formular el problema en su formato de programacin lineal.

FecuadroH0ostrar

FecuadroHOcultar

6F6GPLO?.1 LP-I 34GO I"60I;I3A U0 POBL6GA "6PO8AGA3I40 U06AL "6 U0A G63LA "6 PO"U3O7

Como parte de su proceso estrat-gico de planeacin "recision0anufacturingCompanydebe determinar para el siguiente a/o la mecla de productos a manufacturar. +aempresa produce dos lneas principales de productos para la industria de la construccincomercialH una lnea de sierras circulares port$tiles para uso pesado y una lnea desierras de mesa de precisin. +as dos lneas comparten una misma capacidad de

produccin y se venden a trav-s de los mismos canales de ventas. Aunque dentro de lalnea de productos existe alguna diversidad la utilidad promedio es de =)) dlares porcada sierra circular y de K)) dlares por cada sierra de mesa. +a capacidad de

produccin est$ limitada de dos manerasH capacidad de fabricacin y capacidad de

ensamble. 4odos los meses est$ disponible un m$ximo de ))) horas de capacidad defabricacin\ cada sierra circular requiere dos horas y cada sierra de mesa una hora. May

help.do?page=/pa http://rs.go.galegr es!s
http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3


32/38

disponible al mes un m$ximo de ())) horas de capacidad de ensamble y cada sierracircular requiere una hora y cada sierra de mesa requiere dos horas. El departamento decomercialiacin estima que existir$ en el mercado para el a/o que viene una demandam$xima de *()) sierras al mes para ambas lneas de productos combinadas. XCu$ntassierras circulares y cu$ntas sierras de mesa deber$n producirse mensualmente el

prximo a/o para maximiar la utilidadY

1. %6Diste o no un o$etivo gerencial Jnico(

As es.El ob&etivo es maximiar la utilidad del a/o.

2. %6Disten cursos alternos de accin gerencial(

As es.+a gerencia puede decidir producir durante el a/o slo sierras circulares oslo sierras de mesa o cualquier mecla de las dos lneas de productos.

:. %6l logro total del o$etivo est< restringido por recursos escasos o poralguna otra limitacin(

6e ser as Xcu$l es la naturalea de las restriccionesY

P.(toneladas de cobre y un mnimo de cuatro toneladas de plomo al da Xcu$ntos carros deferrocarril de chatarra deben comprarse diariamente de la fuente A y de la fuente : para

minimiar el costo de la chatarra a largo plaoY
http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3#contenthttp://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3#contenthttp://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3http://go.galegroup.com/ps/i.do?id=GALE%7CCX3002500082&v=2.1&u=unad&it=r&p=GVRL&sw=w&asid=814ccd79f13b7fa65d9cc8e6a2b5ffb3


33/38

1. %6Diste un o$etivo gerencial Jnico(

As es.+a gerencia desea minimiar los costos diarios de comprar chatarra de lacual se podr$ extraer cobre y plomo.

2. %6Disten cursos alternos de accin gerencial(

As es.+a gerencia puede comprar toda su chatarra ya sea slo de la fuente A o: o puede elegir cualquier combinacin de cantidades de chatarra de ambasfuentes.

:. %6st< restringido el logro total del o$etivo por recursos escasos uotras restricciones( "e ser as! %cu Aug. 2E1>.

UL

CttpRRgo.galegroup.comRpsRi.do(id8AL6S@33T:EE2>EEE2v2.1uunaditrp85LsVVasid1=ccd@W1:$@a?>dWcce?a2$>X$:

N/ero de doc%ento de ,ale0 !A+E^C7*))>()))?>

Capitulo >

a.- ;ormulacin de un pro$lema de Programacin Lineal

"a progra$a%&'( l&(eal so( $odelos dest&(ados a la as&g(a%&'( e)&%&e(te de losre%!rsos l&$&tados e( a%t&*&dades %o(o%&das %o( el o+,et&*o de sat&s)a%er las$etas deseadas -$a&$&/ar +e(e)&%&os o $&(&$&/ar %ostos0.


34/38

"a %ara%ter1st&%a d&st&(t&*a de los $odelos es 2!e las )!(%&o(es 2!ereprese(ta( el o+,et&*o 3 las restr&%%&o(es so( l&(eales. -No se per$&te$!lt&pl&%a%&'( de *ar&a+les (& *ar&a+les ele*adas a pote(%&as0.

Probleas de prograaci(n lineal I2

un problema de prograaci(n linealtratamos de optimiar maximiar o minimiarG una funcin lineal que depende das variables sometidas a ciertas restricciones tambi-n lineales. Inicialmente abordaremos problemas en los que

rvienen solamente dos variables.

a resolver este tipo de problemas es conveniente tener en cuenta los siguientes pasosH

'. Identificar las variablesy analiar las restricciones a las que est$n sometidas y la funcin que tratamos de optimiarque llamamos f%nci(n ob3etivo. Dna tabla puede ser un instrumento muy #til para organiar esta informacin.

>. "lantear el sistea de inec%acionesdado por las restricciones y escribir la expresin algebraica de la funcinob&etivo.

*. Mallar el recinto solucin o regi(n factible con sus v-rtices y en general representarlo gr$ficamente.

. Obtener el (ptiode la funcin ob&etivo en la regin factible comparando los valores que toma dicha funcin enlos v-rtices de la regin factible.

ta de seguir los pasos citados para resolver el siguiente problemaH

a conitera realiza una oerta a sus clientes a tra!"s de dos tipos de lotes A y B. El lote A lle!a # tabletas de turrn y $

as de bombones. El lote B est% compuesto por $ tabletas de turrn y # cajas de bombones. &or cuestiones de estrategia

ercial' el n(mero de lotes B debe ser menor )ue el n(mero de lotes del tipo A incrementado en *. El n(mero de tabletas

urrn disponibles en el almac"n para esta oerta es de $+ y el de cajas de bombones' ,-. a !enta de un lote del tipo A

orta una ganancia de ,'$ euros' y uno del tipo B' /'$ euros. 0etermina el n(mero de lotes de cada tipo )ue debe !endera )ue la ganancia sea lo mayor posible. 1alcula esa ganancia m%xima.

ueba de acceso a la Dniversidad Castilla +a 0ancha >))=G.


35/38

eg%ntas

'. XCu$les son las variables que intervienenY XCu$les son las restricciones a las que est$n sometidasY XCu$l es la

funcin ob&etivoY +a siguiente tabla puede ayudarte a organiar la informacinH compl-tala con los datos que faltan.


36/38

A ) 'isponible

Tabletas de t%rr(n '=(

Ca3as de bobones >)

,anancia

'. Escribe el sistema de inecuaciones correspondiente. Escribe tambi-n la expresin algebraica de la funcin ob&etivo.

>. Fepresenta gr$ficamente una a una y en los mismos e&es de coordenadas las inecuaciones del sistema. Identifica laregin factible.

*. Malla las coordenadas de los v-rtices de la regin factible y calcula el valor de la funcin ob&etivo en cada uno deellos. XCu$l es la solucin del problemaY

. ,amos a utiliar ahora la aplicacin para representar la regin factible y hallar la solucin del problemaH

Ma clic sobre la casilla A' para representar gr$ficamente la regin que corresponde a la inecuacin queexpresa la restriccin en la cantidad disponible de cobre.

Ma clic sobre la casilla A> para representar ahora la inecuacin que expresa la restriccin en la cantidaddisponible de titanio.

Ma clic sobre la casilla A* para representar la inecuacin que expresa la restriccin en la cantidad disponiblede aluminio.

Ma clic sobre las casillas A y A( para representar la condicin de que las longitudes de cable de los tipos Ay : deben ser positivas.

Observa ahora la interseccin de todas las regiones que has representadoH esa ser$ la regin factible.

A continuacin ha clic en la casilla de la celda A'(. Observa la recta que aparece. X_u- relacin tiene con lafuncin ob&etivoY X_u- significa el t-rmino independiente de la ecuacin de la rectaY

Coloca el punto sobre los v-rtices de la regin factible y observa el valor de la funcin ob&etivo en cada unode ellos.

XCu$l es la solucin del problemaY XCoincide con el que habas encontrado previamenteY

(. Ma clic sobre el botn Feiniciar. Dtilia la siguiente aplicacin para resolver los problemas que se proponen acontinuacin. "ara elloH

o Identifica las variables las restricciones a las que est$n sometidas y la funcin ob&etivo. Dna tabla puede serun instrumento muy #til para organiar esta informacin.

o Escribe y simplifica las inecuaciones y la funcin ob&etivo.

o Escribe en la ho&a de c$lculo las inecuaciones. Dtilia una fila para cada inecuacin. En cada fila escribe en

las celdas de las columnas : y C los coeficientes respectivos de las variables de las inecuaciones. Acontinuacin selecciona en la celda de la columna 6 el elemento de comparacin que corresponda. Escribe


37/38

ahora en la celda de la columna E el t-rmino independiente. "or #ltimo ha clic sobre la casilla de la celda dela columna A para representar gr$ficamente la regin representada por la inecuacin.

o Dtilia la fila '( de la ho&a de c$lculo para introducir la funcin ob&etivo. Escribe los coeficientes de lasvariables en las celdas :'( y C'( respectivamente y ha clic sobre la casilla de la celda A'( para

representarla gr$ficamente.

o Observa el recinto com#n a las regiones que has representado. 0ueve la recta que corresponde a la funcinob&etivo y sit#a el punto resaltado de la misma en los v-rtices de la regin factible.

o Compara los valores obtenidos y escribe la solucin del problema.

Probleas

A. Una papelera )uiere li)uidar 2asta 3/ 4g de papel reciclado y 2asta 5#/ 4g de papel normal. &ara ello 2acetipos de lotes' A y B. os lotes A est%n ormados por 5 4g de papel reciclado y # 4g de papel normal y los lote

+ 4g de papel de cada clase. El precio de !enta de cada lote A es de -.6 7 y el de cada lote B es de 5 7. 81u%

lotes A y B debe !ender para maximizar sus ingresos9 8A cu%nto ascienden estos ingresos m%ximos9

"rueba de acceso a la Dniversidad 0adrid >))KG

:. Un rutero )uiere li)uidar $-- 4g de naranjas' *-- 4g de manzanas y +#- 4g de peras. &ara ello prepara dosde ruta de oerta: la bolsa A consta de 5 4g de naranjas y + 4g de manzanas y la bolsa B consta de + 4g de n

5 4g de manzanas y 5 4g de peras. &or cada bolsa del tipo A obtiene un beneicio de +'$ euros' y # euros por

bolsa del tipo B. ;uponiendo )ue !ende todas las bolsas' 8cu%ntas bolsas de cada tipo debe preparar paramaximizar las ganancias9 81u%l es el beneicio m%ximo9

"rueba de acceso a la Dniversidad Comunidad ,alenciana >))=G

C. Una compa del n(mero tot

pa)uetes )ue comprar% ser% de B.

a. 81u%ntos pa)uetes tiene )ue comprar el librero de cada editorial para minimizar el coste' satisacer lmnimos y cumplir la promesa9


38/38

b. 81u%nto le costar%n en total las no!elas9

"rueba de acceso a la Dniversidad Islas :aleares >))=G

:. Una reinera de petrleo ad)uiere dos tipos de crudo' ligero y pesado' a un precio de 3- 7 y ,$ 7 por barril'

respecti!amente. 1on cada barril de crudo ligero la reinera produce -.# barriles de gasolina 6$' -.* barrilegasolina 6/ y -.+ barriles de gasoil. Asimismo' con cada barril de crudo pesado produce -.5' -.+ y -.$ barril

cada uno de estos tres productos' respecti!amente. a reinera debe suministrar al menos +,#-- barriles de

gasolina 6$' *-,-- barriles de gasolina 6/ y +6$-- barriles de gasoil. 0etermina cu%ntos barriles de cada ti

crudo debe comprar la reinera para cubrir sus necesidades de produccin con un coste mnimo y calcula es

"rueba de acceso a la Dniversidad Comunidad ,alenciana >))KG

K Una %brica de conser!as recibe el encargo de preparar dos tipos de lotes de ruta en almbar. 0ispone para3$-- botes de melocotn' ,--- botes de pi

unidad 1 introduccion a la programacion lineal

Documents