PROGRAMACION LINEAL

INTRODUCCION:

En esta unidad vas a utilizar unas escenas en las que aparece la representación de rectas y expresiones con cálculos que te permitirán contestar a las preguntas formuladas.

En la parte inferior de cada escena puedes ver los parámetros que incorpora la escena. Tienen unos valores iniciales que tu puedes modificar situando el cursor en la casilla del parámetro y tecleando los valores que te interesen. Para pasar de un parámetro al siguiente usa el tabulador y para ver el efecto de esos cambios pulsa ENTER.

Es preferible que selecciones el texto e imprimas en un papel las explicaciones. De esta forma puedes ver la escena y las explicaciones simultáneamente. De otro modo tendrás que desplazarte por la pantalla cada vez que necesites consultar las instrucciones o las explicaciones.

SEMIPLANOS. INECUACIONES DE PRIMER GRADO CON DOS INCÓGNITAS

EXPLICACIÓN:Una recta es el conjunto de puntos (x,y) del plano que verifican la ecuación

Ax+By=C.

La recta divide el plano en dos semiplanos o conjuntos de puntos que verifican las inecuaciones

Ax+By<C semiplano

Ax+By>C semiplano

ESCENA: En la siguiente escena puedes ver una recta, tres puntos, las ecuaciones de esa recta y de los semiplanos y unas expresiones con los cálculos A*x+B*y que hay que hacer para ver el valor que toma la expresión Ax+By en el punto seleccionado. Estudia atentamente la escena hasta familiarizarte con ella. Verás que los cálculos están hechos con un decimal

OBJETIVO: localizar la ecuación de cada semiplano. Para ello sigue las indicaciones que están despues de la escena.

1.-Situa la flecha sobre el punto P de coordenadas (x,y), arrástralo sobre la recta ( mantén pulsado el botón izquierdo) y comprueba en la parte superior izquierda que al sustituir sus coordenadas en la ecuación se verifica la igualdad Ax+By=C

2.- Repite la comprobación con el punto Q arrastrándolo por el semiplano correspondiente y comprueba en la parte inferior izquierda que para esos puntos se verifica la desigualdad Ax+By<C

3.- Repite con el punto R y comprueba en la parte superior derecaha que para esos puntos se verifica la desigualdad Ax+By>C

4.- Puedes modificar la recta seleccionando otros valores de A, B y C (usa las flechas o tecléalos como te expliqué al principio) y comprobar a qué expresión corresponde cada semiplano.

LOCALIZACION DE UN SEMIPLANO CON EL PUNTO (0,0)

EXPLICACION: Puesto que todos los puntos de un mismo semiplano verifican la misma desigualdad es suficiente comprobar con uno de ellos para localizar la desigualdad que lo define. Se suele elegir el punto (0,0) por la sencillez de los cálculos. Si la recta pasa por (0,0) hay que utilizar otro punto cualquiera.

ESCENA: En esta escena vas a ver una recta, las ecuaciones de la recta y de los semiplanos y el valor que toma la expresión A*x+B*y en el punto (0,0) y que debes comparar con C.

OBJETIVO: Localizar la ecuación de cada semiplano observando el punto (0,0)

1.- Observa el valor que toma la expresión Ax+By, compárala con C y elige la desigualdad (>ó <)que representa al semiplano que contiene el punto (0,0). La otra desigualdad representa al semiplano que no contiene el punto (0,0). Arrastrando con el ratón mueve las ecuaciones a los semiplanos correspondientes. Dibuja en tu cuaderno la recta actual y escribe el nombre de los dos semiplanos usando las desigualdades.

2.- Cambia la ecuacion de la recta tecleando otros valores para A , B y C y trata de localizar la desigualdad correspondiente a cada semiplano. En tu cuaderno dibuja esta nueva recta y escribe las desigualdades en cada semiplano.

3.- Elige alguna ecuación que tenga A, B o C negativo , localiza nuevamente la expresión de cada semiplano y anota en tu cuaderno las soluciones.

RECINTOS DEFINIDOS MEDIANTE DESIGUALDADES AX+BY>=C O AX+BY<=C

EXPLICACION: La expresión Ax+By>=C ( también puede ser Ax+By<=C) se llama inecuacion de primer grado con dos incógnitas y sus soluciones son parejas de números (x,y) que se corresponden con los infinitos puntos de la región > y la recta =.

A partir de ahora vamos a estudiar los sistemas de inecuaciones, es decir las soluciones de un conjunto de inecuaciones. Estas habrán de ser parejas de números ( puntos del plano) que verifican todas las desigualdades del sistema y estarán situadas en una región del plano o recinto limitado por algunas de las rectas del sistema.

Estos sistemas con tres inecuaciones dividen el plano en 7 recintos limitados por algunas de las rectas representadas. El problema consiste en localizar cuál de ellos hace verdaderas las tres desigualdades.

ESCENA: En esta escena vas a ver tres inecuaciones , las rectas asociadas a cada una de ellas y un punto P(x,y) que puedes mover por el plano arrastrándolo con el ratón o tecleando en la ventana x o y el valor que te interesa. En la parte superior puedes ver el valor que toma cada expresión al sustituir las coordenadas de P=(x,y).

OBJETIVO: Localizar el recinto que contiene todas las soluciones del sistema de inecuaciones.

1.- Selecciona puntos P en cada recinto hasta localizar aquel que hace verdaderas las tres desigualdades. Puedes probar con (3,1) (0,2) (0,0) (2,2) (4,4) (1,4) u otros.

2.- Arrastra con el ratón el punto P por el recinto seleccionado y verás que en todos los puntos se cumplen las tres desigualdades.

Todos los puntos del recinto seleccionado son soluciones del sistema.

3.- Observa en la escena que hay recintos abiertos (no están limitados por rectas en alguna dirección). En el ejemplo la solución es un recinto cerrado de forma triangular pero si modificas alguna desigualdad poniendo > en lugar de < la solución sería un recinto abierto. En la quinta escena encontrarás un ejemplo

UN PROBLEMA DE PROGRAMACION LINEAL

EXPLICACION: Estos problemas consisten en encontrar el valor máximo o mínimo de una función lineal Ax+By=Z que toma valores en los puntos (x,y) de un recinto. Esencialmente constan de una función objetivo, la que queremos optimizar, y una serie de restricciones que representan el recinto y que son desigualdades como las del apartado anterior.

Debes entender que trabajamos con una familia de rectas, una para cada valor de Z , y se trata de localizar el valor máximo o mínimo de Z cuando toma valores dentro del recinto.

ESCENA: Vas a ver representadas las restricciones, una recta que es la función objetivo y sobre ella un punto P que cumple dos funciones, la de arrastrar la recta por el plano y la de calcular el valor Z que toma A*x+B*y en ese punto P y que puedes verlo en la parte inferior izquierda de la escena.

OBJETIVO: Hallar el punto P en el que la función objetivo Ax+By toma su valor máximo o su valor mínimo.

1.- Selecciona, arrastrando con el ratón, algunos puntos P y observa las restricciones de la parte superior izquierda. Comprobarás que los puntos que cumplen las tres restricciones están en la zona sombreada de la escena. En las proximidades de los bordes del triángulo puede haber alguna confusión debida a que en la pantalla los cálculos se ven con un decimal. Para asegurarte puedes meter (x,y) desde el teclado y verás que los bordes del triángulo y en concreto sus vértices también cumplen las restricciones. Lee en la escena las coordenadas de los vértices y comprueba las restricciones para esos puntos.

Solamente los puntos de la zona sombreada cumplen las tres restricciones. Esa zona se llama región factible y sobre ella buscaremos los valores óptimos de Z.

2.- Selecciona puntos P=(x,y) en la región factible y observa el valor que toma la función objetivo en esos puntos. Asegúrate de tomar puntos que estén en los bordes del recinto, especialmente en los vértices.

3.- Localiza los puntos en los que la función objetivo alcanza el valor máximo y el valor mínimo.

Los valores óptimos de la función objetivo se alcanzan en los vértices de la región factible si ésta es cerrada.

4.- Anota en tu cuaderno los valores de x e y en los que la función objetivo alcanza el máximo y el mínimo. Anota también el valor máximo y mínimo de la función objetivo

5.- Si quieres probar con otra función objetivo pasa a la siguiente escena.

OTRO PROBLEMA CAMBIANDO LA FUNCION OBJETIVO

ESCENA: Ahora puedes elegir la función que deseas optimizar. Observa que hay dos parámetros nuevos A y B que son los coeficientes de la función objetivo. Puedes modificarlos escribiendo otros valores. En esta escena hemos cambiado tambien las restricciones. Si quieres que los cálculos sean más exactos introduce los valores x, y, A, B a través del teclado.

1.- Selecciona puntos P=(x,y) y comprueba que la región factible coincide con la zona sombreada incluyendo los bordes.

2.- Selecciona puntos P(x,y) en la región factible y fíjate en el valor que toma la función objetivo en esos puntos especialmente en los vértices.

3.- Localiza los puntos en los que la función objetivo alcanza el valor máximo y el valor mínimo. Anota en tu cuaderno estas restricciones y la función objetivo. Anota también tus conclusiones.

4.- Elige una función objetivo con coeficientes A y B iguales o proporcionales a los de alguna de las restricciones (por ej A=2, B=-1). Localiza los puntos (x,y) donde se alcanza el máximo y el mínimo de Z. Fíjate bien en los bordes. Anota en tu cuaderno el problema elegido y tus conclusiones

Los óptimos pueden ser muchos pero estarán situados en el borde del recinto

OTRO PROBLEMA CON UN RECINTO ABIERTO

EXPLICACION

Algunas restricciones nos pueden conducir a recintos abiertos. En este caso puede que no existan el máximo o el mínimo..

ESCENA

1.- Localiza la región factible moviendo el punto P=(x,y) por las distintas regiones y observando el valor que toman las restricciones. En este ejemplo las restricciones nos llevan a un recinto que no está limitado por una recta en uno de sus bordes, se trata de un recinto abierto. Puedes ver lo que ocurre en esa dirección moviendo el origen de coordenadas a través de O.x y O.y en la parte superior de la escena. Te sugiero que teclees O.x=-250 O.y=150 y ENTER

2.- Observa el valor que toma la función objetivo tomando P dentro de este recinto y trata de localizar los valores máximo y mínimo. Observarás que esta función tiene un mínimo pero nunca alcanza su valor máximo. Copia en tu cuaderno la gráfica, las restricciones y la función objetivo.

Anota los valores (x,y) en los que Z alcanza el mínimo y anota también el valor mínimo para Z.

Si el recinto es abierto la función objetivo puede que no tenga máximo o mínimo.

3.- Elige otra función objetivo cambiando los parámetros A y B de forma que sean iguales o proporcionales a alguna restricción. Por ejemplo A=2 y B=4. Busca el máximo y el mínimo. Anota en tu cuaderno las soluciones.

Esta función alcanza el mínimo en todos los puntos (x,y) del segmento BC. Nunca alcanza el máximo.

4.- Prueba otra vez con A=2 y B=-1 y anota en tu cuaderno las soluciones.

La función objetivo alcanza el mínimo en todos los puntos (x,y) de una semirecta de ecuación 2x-y=1 con x>=2. El valor mínimo es Z=1. No alcanza el máximo.

5.- Prueba con A=2 y B=-6. Anota las soluciones

La función objetivo alcanza el máximo en todos los puntos de una semirecta de ecuación x-3y=-2 con x>=4. Esta función no alcanza el mínimo.

Los óptimos de la función objetivo pueden ser infinitos pero estarán situados en los segmentos o semirectas que definen el borde del recinto.

Autor: Rosa Jiménez Iraundegui