Adfasdf

Matemáticas.

5. Programación lineal.

1

5. PROGRAMACIÓN LINEAL.
Planteamiento general de problemas con dos variables.
• Un problema de programación lineal para dos variables consiste en optimizar una función lineal del tipo z(x, y ) = ax + by , que se denomina función objetivo, sujeta a un sistema de inecuaciones lineales:
⎧a 1 x + b 1 y ≤ d1 ⎪ ⎪a 2 x + b 2 y ≤ d 2 , ⎨ M M M ⎪ ⎪a n x +b n y ≤ dn ⎩

que se denominan restricciones. • Cada inecuación determina un semiplano, y los puntos que cumplen todas las inecuaciones forman un recinto. Dichos puntos se denominan soluciones factibles. La solución óptima es la solución factible que hace máxima o mínima (según se desee) la función objetivo. El valor de la función objetivo para la solución óptima se llama valor del programalineal. • Se puede demostrar que si existe una única solución óptima, ésta se encuentra en uno de los vértices del recinto. Entonces, dicha solución se puede encontrar calculando las coordenadas de cada vértice y hallando el valor de la función objetivo para cada uno de ellos. Si existen infinitas soluciones óptimas, todas se encontrarán en un lado del recinto. Para recintos no acotados, es posibleque no exista la solución óptima. La solución óptima también puede calcularse gráficamente, desplazando una recta paralela al vector (–a, b) hasta llegar al recinto. El vértice en el que dicha recta tenga la mayor ordenada en el origen es la solución óptima si se trata de maximizar la función objetivo, y aquél en el que tenga la menor ordenada en el origen lo es si se trata de minimizarla.Resolución de un problema tipo.
• Un grupo local posee dos emisoras de radio, una de FM y otra de AM. La emisora de FM emite diariamente 12 horas de música rock, 6 horas de música clásica y 5 horas de información general. La emisora de AM emite diariamente 5 horas de música rock, 8 horas de música clásica y 10 horas de información general. Cada día que emite la emisora de FM los costes son de 500.000pts., y cada día que emite la emisora de AM los costes son de 400.000 pts. Sabiendo que tiene “enlatadas” para emitir 120 horas de música rock, 180 horas de música clásica clásica y 100 horas de información general, ¿cuántos días deberán emitir con ese material cada una de las dos emisoras para que el coste sea mínimo, teniendo en cuenta que entre las dos emisoras han de emitir al menos unasemana? – Construimos una tabla que recoja los datos del problema:

Matemáticas.

5. Programación lineal.

2

Emisora FM Música rock Música clásica Información general Costes diarios 12 horas/día 6 horas/día 5 horas/día 500.000 pts.

Emisora AM 5 horas/día 8 horas/día 10 horas/día 400.000 pts.

Disponible 120 horas 180 horas 100 horas

– Elegimos las variables de la función objetivo y laexpresamos: x ≡ días que emitirá la emisora de FM; y ≡ días que emitirá la emisora de AM. Función objetivo a minimizar: coste de la emisión (z).

z = 500.000 x + 400.000 y
– Expresamos mediante inecuaciones las restricciones del problema:
⎧12 x + 5 y ≤ 120 ⎫ ⎪ ⎪ ⎪6 x + 8 y ≤ 180 ⎬Datos que se recogen en la tabla. ⎪5 x + 10 y ≤ 100 ⎪ ⎭ ⎪ ⎪ ⎨x + y ≥ 7}Entre las dos emisoras han de emitir almenos una semana. ⎪x ≥ 0 ⎫ ⎪ ⎬El número de días que emitan no puede ser negativo. ⎪ y ≥ 0⎭ ⎪ ⎪ ⎩

– Se resuelve cada inecuación y se representa el recinto que encierran:

Se calculan los vértices de dicho recinto, que resultan ser:

Matemáticas.

5. Programación lineal.

3

A (0, 10), B (0, 7), C (7, 0), D (10, 0), E (7’37, 6’32). – Evaluamos la función z en cada uno de los vértices:
z(A) = 4.000.000 z(B ) = 2.800.000 z(C) = 3.500.000 z(D) = 5.000.000 z(E ) = 6.200.000

Entonces, el coste mínimo se obtiene en el punto B. Es decir, el material debe emitirse durante 7 días en la emisora de AM y ningún día en la de FM. – La solución óptima también puede obtenerse gráficamente, trazando rectas paralelas al vector (-400.000, 500.000), es decir, paralelas al vector (4, 5), que...