Programacion lineal
Páginas: 16 (3784 palabras)
Publicado: 10 de diciembre de 2009
Cap´ ıtulo 8
´ PROGRAMACION LINEAL
8.1. Introducci´n o
La programaci´n lineal es una t´cnica matem´tica relativamente reciente (siglo XX), que consiste o e a en una serie de m´todos y procedimientos que permiten resolver problemas de optimizaci´n en el e o a ´mbito, sobre todo, de las Ciencias Sociales. Nos centraremos en este tema en aquellos problemas simples de programaci´n lineal, losque tienen o s´lamente 2 variables, problemas bidimensionales. o Para sistemas de m´s variables, el procedimiento no es tan sencillo y se resuelven por el llamado a m´todo Simplex (ideado por G.B.Danzig, matem´tico estadounidense en 1951). e a Recientemente (1984) el matem´tico indio establecido en Estados Unidos, Narenda Karmarkar, a ha encontrado un algoritmo, llamado algoritmo de Karmarkar, quees m´s r´pido que el m´todo a a e simplex en ciertos casos. Los problemas de este tipo, en el que intervienen gran n´mero de variables, u se implementan en ordenadores.
8.2.
Inecuaciones lineales con 2 variables
ax + by ≤ c
Una inecuaci´n lineal con 2 variables es una expresi´n de la forma: o o
(donde el s´ ımbolo ≤ puede ser tambi´n ≥ , < o bien >), donde a, b y c son n´meros realesy x e y las e u inc´gnitas. o Para resolver estas inecuaciones, se recordar´ de otros cursos, hay que representar gr´ficamente en a a el plano la recta dada por la correspondiente ecuaci´n lineal y marcar una de las dos regiones en que o dicha recta divide al plano. Ejemplo: Si queremos resolver la inecuaci´n: 2x + 3y ≥ −3, representamos en primer lugar la recta o 2x + 3y = −3:
127
´ CAP´ITULO 8. PROGRAMACION LINEAL
128
La recta divide al plano en dos regiones, una de las cuales es la soluci´n de la inecuaci´n. Para o o saber qu´ parte es, hay dos procedimientos: e 1. Se despeja la y de la inecuaci´n, poniendo cuidado en que si en una inecuaci´n multiplicamos o o o dividimos por un n´mero negativo, la desigualdad cambia de sentido. u En este caso tend´ ıamos que: y≥ −3 − 2x 3Observando el dibujo vemos que la recta divide al eje de ordenadas (y) en dos partes. La soluci´n de la inecuaci´n ser´ aquella parte en la que la y sea mayor que la recta, es decir, la o o a parte superior.
Figura 8.1: Soluci´n de la inecuaci´n lineal o o
2. Se toma un punto cualquiera que no pertenezca a la recta, por ejemplo el (1,2). Para que dicho punto sea soluci´n, se tendr´ quecumplir la desigualdad, por lo que sustituimos o a en la inecuaci´n inicial el (1,2): o 2 · 1 + 3 · 2 ≥ −3, es decir, 8 ≥ −3. Como esta ultima desigualdad es evidentemente cierta, concluimos que el (1,2) es soluci´n y ´ o por tanto el semiplano que contiene al (1,2) es la soluci´n, es decir el semiplano superior, como o hab´ ıamos obtenido antes. Cualquiera de los procedimientos es v´lido si serealiza con correcci´n. a o
8.3.
Sistemas de inecuaciones lineales con dos variables
Un sistema de inecuaciones lineales, por tanto, es un conjunto de inecuaciones del tipo anterior, y resolverlo consistir´ en resolver gr´ficamente cada inecuaci´n (como en el caso anterior), representar a a o la soluci´n en un mismo gr´fico y la soluci´n total ser´ la parte com´n a todas las soluciones. o a oa u
´ CAP´ ITULO 8. PROGRAMACION LINEAL Ejemplo: Resolver el sistema de inecuaciones siguiente: 2x + 3y ≥ −3 2x − y − 9 ≤ 0 2x − 5y − 5 ≥ 0 Si representamos las rectas: 2x + 3y = −3 (recta r) 2x − y − 9 = 0 (recta s) 2x − 5y − 5 = 0 (recta t)
129
Figura 8.2: Soluci´n del sistema de inecuaciones lineales o El tri´ngulo rayado es la soluci´n del sistema. a o Adem´s, para losproblemas de programaci´n lineal es necesario el c´lculo de los v´rtices de la a o a e regi´n soluci´n. Es sencillo su c´lculo, pues se reduce a resolver sistemas de ecuaciones lineales son o o a dos inc´gnitas, que provienen de igualar las ecuaciones de las rectas correspondientes. o Por ejemplo, en este caso, si queremos el punto intersecci´n de las rectas r y t tendremos que o resolver el...
´ PROGRAMACION LINEAL
8.1. Introducci´n o
La programaci´n lineal es una t´cnica matem´tica relativamente reciente (siglo XX), que consiste o e a en una serie de m´todos y procedimientos que permiten resolver problemas de optimizaci´n en el e o a ´mbito, sobre todo, de las Ciencias Sociales. Nos centraremos en este tema en aquellos problemas simples de programaci´n lineal, losque tienen o s´lamente 2 variables, problemas bidimensionales. o Para sistemas de m´s variables, el procedimiento no es tan sencillo y se resuelven por el llamado a m´todo Simplex (ideado por G.B.Danzig, matem´tico estadounidense en 1951). e a Recientemente (1984) el matem´tico indio establecido en Estados Unidos, Narenda Karmarkar, a ha encontrado un algoritmo, llamado algoritmo de Karmarkar, quees m´s r´pido que el m´todo a a e simplex en ciertos casos. Los problemas de este tipo, en el que intervienen gran n´mero de variables, u se implementan en ordenadores.
8.2.
Inecuaciones lineales con 2 variables
ax + by ≤ c
Una inecuaci´n lineal con 2 variables es una expresi´n de la forma: o o
(donde el s´ ımbolo ≤ puede ser tambi´n ≥ , < o bien >), donde a, b y c son n´meros realesy x e y las e u inc´gnitas. o Para resolver estas inecuaciones, se recordar´ de otros cursos, hay que representar gr´ficamente en a a el plano la recta dada por la correspondiente ecuaci´n lineal y marcar una de las dos regiones en que o dicha recta divide al plano. Ejemplo: Si queremos resolver la inecuaci´n: 2x + 3y ≥ −3, representamos en primer lugar la recta o 2x + 3y = −3:
127
´ CAP´ITULO 8. PROGRAMACION LINEAL
128
La recta divide al plano en dos regiones, una de las cuales es la soluci´n de la inecuaci´n. Para o o saber qu´ parte es, hay dos procedimientos: e 1. Se despeja la y de la inecuaci´n, poniendo cuidado en que si en una inecuaci´n multiplicamos o o o dividimos por un n´mero negativo, la desigualdad cambia de sentido. u En este caso tend´ ıamos que: y≥ −3 − 2x 3Observando el dibujo vemos que la recta divide al eje de ordenadas (y) en dos partes. La soluci´n de la inecuaci´n ser´ aquella parte en la que la y sea mayor que la recta, es decir, la o o a parte superior.
Figura 8.1: Soluci´n de la inecuaci´n lineal o o
2. Se toma un punto cualquiera que no pertenezca a la recta, por ejemplo el (1,2). Para que dicho punto sea soluci´n, se tendr´ quecumplir la desigualdad, por lo que sustituimos o a en la inecuaci´n inicial el (1,2): o 2 · 1 + 3 · 2 ≥ −3, es decir, 8 ≥ −3. Como esta ultima desigualdad es evidentemente cierta, concluimos que el (1,2) es soluci´n y ´ o por tanto el semiplano que contiene al (1,2) es la soluci´n, es decir el semiplano superior, como o hab´ ıamos obtenido antes. Cualquiera de los procedimientos es v´lido si serealiza con correcci´n. a o
8.3.
Sistemas de inecuaciones lineales con dos variables
Un sistema de inecuaciones lineales, por tanto, es un conjunto de inecuaciones del tipo anterior, y resolverlo consistir´ en resolver gr´ficamente cada inecuaci´n (como en el caso anterior), representar a a o la soluci´n en un mismo gr´fico y la soluci´n total ser´ la parte com´n a todas las soluciones. o a oa u
´ CAP´ ITULO 8. PROGRAMACION LINEAL Ejemplo: Resolver el sistema de inecuaciones siguiente: 2x + 3y ≥ −3 2x − y − 9 ≤ 0 2x − 5y − 5 ≥ 0 Si representamos las rectas: 2x + 3y = −3 (recta r) 2x − y − 9 = 0 (recta s) 2x − 5y − 5 = 0 (recta t)
129
Figura 8.2: Soluci´n del sistema de inecuaciones lineales o El tri´ngulo rayado es la soluci´n del sistema. a o Adem´s, para losproblemas de programaci´n lineal es necesario el c´lculo de los v´rtices de la a o a e regi´n soluci´n. Es sencillo su c´lculo, pues se reduce a resolver sistemas de ecuaciones lineales son o o a dos inc´gnitas, que provienen de igualar las ecuaciones de las rectas correspondientes. o Por ejemplo, en este caso, si queremos el punto intersecci´n de las rectas r y t tendremos que o resolver el...
Leer documento completo
Regístrate para leer el documento completo.