Programación Lineal

Algebra lineal

Introducción.-

¿Qué es Programación Lineal?

Inecuaciones Lineales

Para entender los fundamentos de la programación lineal es

necesario saber e interpretar los sistemas de inecuaciones lineales.

Inecuaciones lineales con dos variables: • Una inecuación lineal con 2 variables es una expresión

de forma:

𝑎𝑥 + 𝑏𝑦 ≤ 𝑐

• (el símbolo ≤ puede ser también ≥, < ó >), Donde a, b

y c son números reales, x e y las incógnitas.

Si se requiere resolver o graficar una inecuación solo basta con seguir el ejemplo siguiente:

Ejemplo:

Resolver la inecuación: 2𝑥 + 3𝑦 ≥ −3.

Solución:

• Paso 1: Se debe igualar la inecuación a -3. (Para encontrar la recta que la representa)

2𝑥 + 3𝑦 = −3

• Paso 2: Luego se despeja la variable y. (tomando en cuenta que si en una inecuación multiplicamos o dividimos por un número negativo, la desigualdad cambia de sentido).

𝑦 ≥ −3 − 2𝑥

3

• Paso 3: Se procede a realizar

el gráfico, como cualquier

función lineal (función lineal

obtenida en el paso 1).

No obstante debemos considerar

que La recta divide al plano en dos regiones,

una de las cuales es la solución de la inecuación,

es decir, podemos reemplazar cualquier punto que no

pertenezca a la recta en la inecuación, y la desigualdad

se seguirá cumpliendo.

(Figura 2.a).

• Paso 4: debemos demostrar que la zona del semiplano señalado (en

amarillo), son la respuesta de la inecuación, en este caso elegimos el punto, P = 1,2 y lo remplazamos en la Inecuación 2𝑥 + 3𝑦 ≥ −3.

2 × 1 + 3 × 2 = 8, es decir, 8 ≥ −3

Como la igualdad en el ejercicio anterior graficado en la figura 2.a, es verídica, se puede concluir que el punto 𝑃 = (1,2) es solución ya que está contenido en el semiplano señalado y además satisface la desigualdad.

Sistemas De Inecuaciones Lineales Con Dos Variables.

Ejemplo:

Resolver el sistema de inecuaciones siguientes:

2𝑥 + 3𝑦 ≥ −3

2𝑥 − 𝑦 − 9 ≤ 0

2𝑥 − 5𝑦 − 5 ≥ 0

Solución:

• Paso 1: Se procede a graficar cada una de las inecuaciones, siguiendo los pasos anteriormente mencionados. Cada una de las inecuaciones está representada por las rectas respectivas, como se muestra en la figura 2.b:

2𝑥 + 3𝑦 = −3 (Recta r)

2𝑥 − 𝑦 − 9 = 0 (Recta t)

2𝑥 − 5𝑦 − 5 = 0 (Recta s)

* El Triángulo rayado es la solución del sistema.

Nota: Debemos considerar además que en ocasiones los sistemas de inecuaciones, en donde falta alguna incógnita, por ejemplo, 𝑥≥𝑘 o también 𝑦≥𝑘. Corresponden a inecuaciones, cuyas rectas son horizontales o verticales, en los cuales en programación lineal son llamados “casos extremos”. De estos casos, podremos analizar mejor en temas posteriores.

Programación Lineal &

Su Estructura

Estructura Básica De Un Problema De Programación Lineal

Un problema de Programación Lineal consta de una función

objetivo (lineal) por maximizar o minimizar, sujeta a ciertas restricciones en la forma de igualdades o desigualdades.

Algunos Conceptos Importantes:

• Función Objetivo: Es La función por optimizar (maximizar o Minimizar)

• Restricciones: Representan Las condiciones que es preciso satisfacer,

Representado Por Un sistema de desigualdades (≤ ó ≥). Pueden Ser de tipo

Estructural o de no negatividad.

• Conjunto Factible: Es el conjunto de puntos que integran la región de

resolución.

• Solución Factible: Cada punto que integra la región (plana) que resuelve el

problema.

• Solución Óptima: Constituye la solución al problema de Programación Lineal.

Estructura Básica De Un Problema De Programación Lineal

Ejemplo: Maximizar La Siguiente Función

Función Objetivo

(Representada Generalmente Por Un Vector)

Restricción De Tipo Estructural

(Representa Limitaciones de Recursos u Otros

Dados En Problema)

Restricción De No Negatividad

(Garantiza Que las Variables De Decisión

No Sea Negativa)

𝑃 = 3𝑥 + 2𝑦 Sujeto A: 2𝑥 + 3𝑦 ≤ 12

2𝑥 + 𝑦 ≤ 8

𝑥 ≥ 0 𝑦 ≥ 0

• Paso 1: Se grafica cada una de las inecuaciones, con los Métodos ya mencionados.

• Paso 2: Se Identifican Cada uno de los vértices del polígono del conjunto factible.

Se observa en qué vértice la función P se hace máxima (o mínima)sin más que tener en cuenta

cual de las rectas tiene mayor (o menor) ordenada en el origen, es decir, qué recta

corta en un punto mayor o menor al eje y.

• Paso 3: Se Procede a reemplazar cada un de los vértices en la función Objetivo,

𝑃 = 3𝑥 + 2𝑦

𝐴 = 𝑃(0,4) = 3 𝑥 0 + 2 𝑥 4 = 8. 𝐵 = 𝑃(3,2) = 3 𝑥 3 + 2 𝑥 2 = 13. 𝐶 = 𝑃(4,0) = 3 𝑥 4 + 2 𝑥 0 = 12.

Si Analizamos cada uno de los vértices obtenidos en la región factible, obtendremos que la función se hace máxima en el Vértice B (3,2), con lo que vendrá a ser la solución Del problema de programación lineal

Aplicación De Programación Lineal En Un Ejercicio DE

Optimización

Ejercicio:

Un estudiante reparte propaganda publicitaria en su tiempo

libre. La empresa A le paga 0,05€ por impreso repartido y la

empresa B, con folletos más grandes, le paga 0,07 € por impreso.

El estudiante lleva dos bolsas: una para los impresos de tipo A, en

la que le caben 120, y otra para los de tipo B, en la que caben 100.

Ha calculado que cada día puede repartir 150 impresos como

máximo.

¿Cuántos impresos habrá de repartir de cada clase para que su beneficio diario sea máximo?¿Á Cuánto Equivale Dicho Beneficio?

Solución:

• Paso 1: Vamos a llamar 𝑥 al número de impresos de tipo A e 𝑦 al

número de impresos de tipo B.

La función Objetivo, es decir que nos da el beneficio es:

𝑓 𝑥, 𝑦 = 0,05𝑥 + 0,07𝑦.

Las restricciones son:

0 ≤ 𝑥 ≤ 120

0 ≤ 𝑦 ≤ 100

𝑥 + 𝑦 ≤ 150

Debemos Maximizar La Función que representa el beneficio De Acuerdo

A Las restricciones ya mencionadas, que están determinadas por la capacidad

del bolso (R.E.) y por la ganancia que por razones obvia debe ser positiva

(R.N.N).

• Paso 4: El máximo se alcanza en el

punto de intersección de las rectas:

𝑥 + 𝑦 = 150

𝑦 = 100

- Se Procede a resolver el sistema:

𝑥 + 100 = 150

𝑥 = 150 – 100

𝑥 = 50

1.- Por tanto, habrá de repartir 50

impresos de tipo A y 100 de tipo B.

2.- El beneficio será de:

f(50, 100) = 0,05 · 50 + 0,07 · 100 = 9,5 €

• Paso 3: Se Procede a realizar la grafica correspondiente, a las inecuaciones

representadas por la restricciones, como sigue en la figura siguiente:

Conclusión.-