problemas de programación lineal.docx

7/21/2019 Problemas de programacin lineal.docx

1/18

Problemas de programacin lineal con dos variables.

Un problema de programacin lineal con dos variables tiene por finalidad optimizar(maximizar o minimizar) una funcin lineal:

F(X,Y) = ax + by

Llamada funcin objetivo, sujeta a una serie de restricciones presentadas en forma desistema de inecuaciones con dos incgnitas de la forma:

Cada desigualdad del sistema de restricciones determina un semiplano.

l conjunto interseccin de todos esos semiplanos recibe el nombre de zona de solucionesfactibles. l conjunto de los v!rtices del recinto se denomina conjunto de solucionesfactibles b"sicas # el v!rtice donde se presenta la solucin ptima se llama solucinm"xima (o m$nima seg%n el caso). l valor &ue toma la funcin objetivo en el v!rtice desolucin ptima se llama valor del programa lineal.

l procedimiento a seguir para resolver un problema de programacin lineal en dosvariables ser", pues:

'. legir las incgnitas.

. scribir la funcin objetivo en funcin de los datos del problema.

. scribir las restricciones en forma de sistema de inecuaciones.

*. +veriguar el conjunto de soluciones factibles representando gr"ficamente lasrestricciones.

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

-. Calcular el valor de la funcin objetivo en cada uno de los v!rtices para ver en cu"l deellos presenta el valor m"ximo o m$nimo seg%n nos pida el problema (a# &ue tener encuenta a&u$ la posible no existencia de solucin si el recinto no es acotado)


2/18

PROBLEMAS DE PROGRAMACIO LIEAL

'. Una compa/$a posee dos minas: la mina + produce cada d$a ' tonelada de ierro dealta calidad, toneladas de calidad media # de baja calidad. La mina 0 producecada d$a toneladas de cada una de las tres calidades. La compa/$a necesita al

menos 12 toneladas de mineral de alta calidad, '-2 toneladas de calidad media #22 de baja calidad. 3abiendo &ue el coste diario de la operacin es de 222 eurosen cada mina 4cu"ntos d$as debe trabajar cada mina para &ue el coste sea m$nimo5

d!as Al"a calidad Calidad media Ba#a calidad Cos"e dia

Mina A x 'x x x 222x

Mina B # # # # 222#

12 '-2 22

La funcin objetivo C(x, #)6222x 7 222#

Las restricciones son las siguientes:

La regin factible la obtenemos dibujando las rectas auxiliares:

r' x 7 #612,

r x 7 #6 '-2

r x 7 #622

n el primer cuadrante # considerando la regin no acotada &ue determina el sistema derestricciones:


3/18

La regin factible la obtenemos dibujando las rectas auxiliares: r' x 7 #612, r x 7#6 '-2 # r x 7 #622 en el primer cuadrante # considerando la regin no acotada &uedetermina el sistema de restricciones:


4/18

Los v!rtices son los puntos +(2, '22), 0(2, 2), C(*2, 2), 8(12, 2), &ue se encuentran alresolver el sistema &ue determinan dos a dos las rectas auxiliares # (# &ue est!n dentro de laregin factible).

r' r &ue nos da el punto (*2, 2) (comprobarlo)

r r &ue nos da el punto (2, 2)

r' r no ace falta calcularlo pues &ueda fuera de la regin factible.

n la gr"fica se aprecia &ue el primer punto &ue se alcanza al desplazar la recta C(x, #)62es el (*2, 2). Luego la solucin es trabajar *2 d$as en la mina + # 2 en la 0. (m!todogr"fico).


5/18

$sando el m%"odo gr&'ico(

Ma)imi*ar + , -/01 -2/3S4#e"o a( 3/01 /3 5 036 78oras de prod4ccin9

3/01 :/3 5 066 78oras de inspeccin ; empa 69


6/18

M?@ODO SIMPLE/

l M%"odo Simple) es un m!todo anal$tico de solucin de problemas de programacinlinela capaz de resolver modelos m"s complejos &ue los resueltos mediante el m!todo

gr"fico sin restriccin en el n%mero de variables.l M%"odo Simple)es un m!todo iterativo &ue permite ir mejorando la solucin en cadapaso. La razn matem"tica de esta mejora radica en &ue el m!todo consiste en caminar delv!rtice de un poliedro a un v!rtice vecino de manera &ue aumente o disminu#a (seg%n elcontexto de la funcin objetivo, sea maximizar o minimizar), dado &ue el n%mero dev!rtices &ue presenta un poliedro solucin es finito siempre se allar" solucin.

ste famos$simo m!todo fue creado en el a/o de '9* por el estadounidense ;eorge0ernard 8antzig # el ruso Leonid


7/18

OBSERACIOES IMPOR@A@ES AL $@ILI+AR M?@ODO SIMPLE/

ARIABLES DE OLG$RA E/CESO

l @!todo 3implex trabaja bas"ndose en ecuaciones # las restricciones iniciales &ue se

modelan mediante programacin lineal no lo son, para ello a# &ue convertir estasinecuaciones en ecuaciones utilizando unas variables denominadas de olgura # excesorelacionadas con el recurso al cual ace referencia la restriccin # &ue en el tabulado finalrepresenta el E3lacF or surplusE al &ue acen referencia los famosos programas deresolucin de investigacin de operaciones, estas variables ad&uieren un gran valor en elan"lisis de sensibilidad # juegan un rol fundamental en la creacin de la matriz identidadbase del 3implex.

stas variables suelen estar representadas por la letra E3E, se suman si la restriccin es designo EG6 E # se restan si la restriccin es de signo EH6E.

Ior ejemplo:


8/18

VARIABLE ARTIFICIAL / MTODO DE LA "M"

Una variable artificial es un truco matem"tico para convertir inecuaciones EH6E enecuaciones, o cuando aparecen igualdades en el problema original, la caracter$sticaprincipal de estas variables es &ue no deben formar parte de la solucin, dado &ue norepresentan recursos. l objetivo fundamental de estas variables es la formacin de lamatriz identidad.

stas variables se representa por la letra "A",siempre se suman a las restricciones, sucoeficiente es @ (por esto se le denomina @!todo de la @ grande, donde @ significa unn%mero demasiado grande mu# poco atractivo para la funcin objetivo), # el signo en lafuncin objetivo va en contra del sentido de la misma, es decir, en problemas de@aximizacin su signo es menos (J) # en problemas de @inimizacin su signo es (7),repetimos con el objetivo de &ue su valor en la solucin sea cero (2).

MTODO SIMPLEX PASO A PASO

EL PROBLEMA

La empresa el 3+@K? Ltda. 8edicada a la fabricacin de muebles, a ampliado suproduccin en dos l$neas m"s. Ior lo tanto actualmente fabrica mesas, sillas, camas #bibliotecas. Cada mesa re&uiere de piezas rectangulares de 1 pines, # piezas cuadradasde * pines. Cada silla re&uiere de ' pieza rectangular de 1 pines # piezas cuadradas de *pines, cada cama re&uiere de ' pieza rectangular de 1 pines, ' cuadrada de * pines # basestrapezoidales de pines # finalmente cada biblioteca re&uiere de piezas rectangulares de1 pines, bases trapezoidales de pines # * piezas rectangulares de pines. Cada mesa


9/18

cuesta producirla '2222 # se vende en 2222, cada silla cuesta producirla 1222 # sevende en 1222, cada cama cuesta producirla 2222 # se vende en *2222, cadabiblioteca cuesta producirla *2222 # se vende en -2222. l objetivo de la f"brica esmaximizar las utilidades.

Iroblema planteado por M!ctor +ngulo J ngeniero ndustrial

PASO 1: MODELACIN MEDIANTE PROGRAMACIN LINEAL

Las variables:

/0,Cantidad de mesas a producir (unidades)

/3,Cantidad de sillas a producir (unidades)

/:,Cantidad de camas a producir (unidades)

/,Cantidad de bibliotecas a producir (unidades)

Las restricciones:

/01'/37 '/:7 /G6 *

/01/37 '/:G6 2

/:7 /G6 2

*/G6 '-


10/18

La funcin Nbjetivo:

+MA/,2222/012222/312222/:7 2222/

PASO 2: CONVERTIR LAS INECUACIONES EN ECUACIONES

n este paso el objetivo es asignar a cada recurso una variable de Molgura, dado &ue todaslas restricciones son EG6E.

/01'/37 '/:7 /1'S07 2S312S:12S6 *

/01/37 '/:12/123'7 'S312S:12S6 2

2/012/37 /:1/12S07 2S31'S:12S,2

2/012/37 2/:1*/12S07 2S312S:1'S,'-

8e esta manera podemos apreciar una matriz identidad (n 6 *), formado por las variablesde olgura las cuales solo tienen coeficiente ' en su respectivo recurso, por el ejemplo lavariable de olgura E3'E solo tiene coeficiente ' en la restriccin correspondiente a elrecurso '.

La funcin objetivo no sufre variaciones:

+MA/,2222/012222/312222/:7 2222/

PASO 3: DEFINIR LA SOLUCIN BSICA INICIAL

l @!todo 3implex parte de una solucin b"sica inicial para realizar todas susiteraciones, esta solucin b"sica inicial se forma con las variables de coeficiente diferentede cero (2) en la matriz identidad.

'S06 *

'S3 6 2

'S:,2

'S ,'-

PASO 4: DEFINIR LA TABLA SIMPLEX INICIAL


11/18

Sol4cin: (segundo t!rmino)6 n esta fila se consigna el segundo t!rmino de la solucin, esdecir las variables, lo m"s adecuado es &ue estas se consignen de manera ordenada, tal cualcomo se escribieron en la definicin de restricciones.

C#6 La fila ECjE ace referencia al coeficiente &ue tiene cada una de las variables de la filaEsolucinE en la funcin objetivo.

ariable Sol4cin6 n esta columna se consigna la solucin b"sica inicial, # a partir deesta en cada iteracin se van inclu#endo las variables &ue formar"n parte de la solucinfinal.

Cb6 n esta fila se consigna el valor &ue tiene la variable &ue se encuentra a su derecaE


12/18

PASO 5: REALIAR LAS ITERACIONES NECESARIAS

ste es el paso definitivo en la resolucin por medio del @!todo 3implex, consiste enrealizar intentos mientras el modelo va de un v!rtice del poliedro objetivo a otro.

l procedimiento a seguir es el siguiente:

'. valuar &ue variable entrar" # cual saldr" de la solucin ptima:

Ma)imi*ar Minimi*ar

ariable


13/18

J Lo siguiente es comenzar a rellenar el resto de la tabla, fila x fila.

J 3e repite este procedimiento con las dos filas restantes, aora se ar"n los c"lculoscorrespondientes en el resto de las celdas.


14/18

8e esta manera se culmina la primera iteracin, este paso se repetir" cuantas veces seanecesario # solo se dar" por terminado el m!todo seg%n los siguientes criterios.

Ma)imi*ar Minimi*ar

Sol4cin p"ima Cuando todos los Cj J Dj sean G6 2 Cuando todos los Cj J Dj sean H6 2

J Continuamos con las iteraciones para lo cual tenemos &ue repetir los pasos anteriores.


15/18

n esta %ltima iteracin podemos observar &ue se cumple con la consigna Cj J Dj G6 2, para

ejercicios cu#a funcin objetivo sea E@aximizarE, por ende emos llegado a la respuestaptima.

/0,

/3,*

/:,-

/,*

Con una utilidad de: *2222

3in embargo una vez finalizado el @!todo 3implex se debe observar una matriz identidaden el rect"ngulo determinado por las variables de decisin, el eco de &ue en este caso nose muestre la matriz identidad significa &ue existe una solucin ptima alterna.


16/18

La manera de llegar a la otra solucin consiste en alterar el orden en &ue cada una de lasvariables entro a la solucin b"sica, recordemos &ue el proceso fue decidido al azar debidoa la igualdad en el Cj J Dj del tabulado inicial. +&u$ les presentamos una de las maneras dellegar a la otra solucin.


17/18

Iodemos observar como existe una solucin ptima alternativa en la cual la combinacinde variables es distinta # existe un menor consumo de recursos, dado &ue el eco de &ue seencuentre la variable E3'E en la solucin ptima con un coeficiente de EE significa &ue se

presenta una olgura de unidades del recurso (pieza rectangular de 1 pines).


18/18

/0,2 (Cantidad de mesas a producir 6 2)

/3, (Cantidad de sillas a producir 6 )

/:,- (Cantidad de camas a producir 6 -)

/,* (Cantidad de bibliotecas a producir 6 *)

S0, (Cantidad de piezas rectangulares de 1 pines sin utilizar 6)

Con una utilidad de: *2222

PROBLEMAS DE MINIMIACIN CON EL MTODO SIMPLEX

Iara resolver problemas de minimizacin mediante el algoritmo simplex existen dosprocedimientos &ue se emplean con regularidad.

J l primero, &ue a mi juicio es el m"s recomendable se basa en un artificio aplicable alalgoritmo fundamentado en la lgica matem"tica &ue dicta &ue "para cualquier funcinf(x), todo punto que minimice a f(x) maximizar tambin a f(x)". Ior lo tanto elprocedimiento a aplicar es multiplicar por el factor negativo (J') a toda la funcin objetivo.

+ continuacin se resuelve el algoritmo como un problema de maximizacin.

l segundo procedimiento, el cual pretende conservar la minimizacin consiste en aplicarlos criterios de decisin &ue emos esbozado con anterioridad, en los casos de la variable&ue entra, &ue sale # el caso en el &ue la solucin ptima es encontrada. +&u$ recordamoslos procedimientos seg%n el criterio dado el caso EminimizarE.

Minimi*ar

ariable

problemas de programación lineal.docx

Documents