17. 🍈 Programming & Optimization

🍒 Applied Computation

• 🍒 “Traveling Salesman” route puzzles, integer linear programming “diet problem.”

🍑 Heuristics & Metaheuristics

• 🍑 Genetic algorithms that find solutions, local minima traps.

---

¿Qué es la Programación Lineal?

La programación lineal (PL) implica optimizar (maximizar o minimizar) una función objetivo lineal, sujeta a un conjunto de restricciones lineales. Esto se puede expresar en la forma general como:

\text{Maximizar o Minimizar:   } 
z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n

\text{Sujeto a:   } 
\begin{align*}
a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n & \leq b_1 \\
a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n & \leq b_2 \\
& \vdots \\
a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n & \leq b_m
\end{align*}

x_1, x_2, \dots, x_n \geq 0

Donde:

• $c_i$ son los coeficientes de la función objetivo.
• $x_i$ son las variables de decisión.
• $a_{ij}$ son los coeficientes de las restricciones.
• $b_i$ son los términos constantes de las restricciones.

Programación Entera

La programación entera (PE) es una subclase de la programación lineal donde algunas o todas las variables de decisión están restringidas a tomar valores enteros. Esto es útil en situaciones donde las variables de decisión representan cantidades discretas, como número de objetos o decisiones de sí/no.

¿Cómo se resuelven estos problemas?

Modelado del problema

Identificar la función objetivo, las variables de decisión, y las restricciones basadas en el problema real.

Formulación matemática

Escribir el modelo en forma algebraica.

Solución del problema

Programación lineal

• Se pueden utilizar métodos como el simplex o el de puntos interiores. Programación entera
• Métodos como el de ramificación y acotamiento (branch and bound) son comunes.

---

Ejercicio

Dado el siguiente problema de programación lineal

max 	Z ＝	 𝑥₁ ＋ 　𝟾 𝑥₂
s.t.		 𝑥₁ ＋ 　  𝑥₂	≤　𝟯
		-𝑥₁ ＋ 　𝟸 𝑥₂	≤　𝟯
		𝟸𝑥₁ ＋ 　𝟺 𝑥₂	≤　𝟭𝟮

a. representar a escala

b. Determinar el máximo de la función objetivo mediante consideraciones geométricas.

c. Determinar los precios sombra mediante consideraciones geométricas

Formulación Matricial de un Problema de Programación Lineal

1. Función Objetivo

\max \text{ o } \min \quad z = \mathbf{c}^T \mathbf{x}

Aquí, $c$ es el vector de coeficientes de la función objetivo, y $x$ es el vector de variables de decisión.

2. Restricciones

\mathbf{A} \mathbf{x} \leq \mathbf{b}

Donde $\mathbf{A}$ es la matriz de coeficientes de las restricciones, $\mathbf{x}$ es el vector de variables de decisión, y $\mathbf{b}$ es el vector de términos constantes del lado derecho de las restricciones.

3. Variables de Decisión

\mathbf{x} \geq \mathbf{0}

Las variables de decisión son representadas por el vector xx, y generalmente se requiere que todas sean no negativas

---

Ejercicio

Un usuario de tiene contratos con 3 proveedores de telefon ́ıa mo ́vil. El proveedor 1 cobra 16 do ́lares fijos por mes, ma ́s 0.25 do ́lares por minuto de conexio ́n. El proveedor 2 cobra 25 do ́lares por mes, pero el coste por minuto se reduce a 0.21 do ́lares, y con el proveedor 3, la tarifa fija es 18 do ́lares mensuales, y la proporcional es 0.22 do ́lares por minuto. El cliente suele utilizar el mo ́vil por ma ́s de 200 minutos al mes. Suponiendo que el cliente no pague el coste fijo si no se conecta a un proveedor en un mes, y que puede repartir a voluntad las conexiones entre los tres proveedores,

1. determinar el modelo de programacio ́ n matema ́ tica que permita establecer co ́ mo debe repar- tir sus conexiones entre los tres proveedores para minimizar el coste mensual del servicio (1.5 puntos),
2. Resolver conMatlab1 el modelo de programacio ́n matema ́tica determinado en el punto a. y comentar el resultado obtenido. (1.5 puntos).

Ejercicio

Una fa ́brica dispone de cuatro te ́cnicos para realizar cuatro trabajos. Cada te ́cnico so ́lo puede hacer uno de los trabajos. El tiempo que requiere cada te ́cnico para completar cada trabajo se muestra en la tabla siguiente.

Tiempo (horas)	Trabajo 1	Trabajo 2	Trabajo 3	Trabajo 4
Técnico 1	14	5	8	7
Técnico 2	2	12	6	5
Técnico 3	7	8	3	9
Te ́cnico 4	2	4	6	10

a. Determinar el modelo de programacio ́n matema ́tica que permita establecer co ́mo asignar los trabajos a los te ́cnicos para minimizar el tiempo total necesario para completar los cuatro trabajos. (1 punto)

b. Co ́mo cambia el modelo anterior (0.5 puntos) si • so ́lo el te ́cnico 1 puede realizar el trabajo 2, y • el te ́cnico 2 no puede realizar el trabajo 3. c. Resolver con Matlab el modelo de programacio ́n matema ́tica determinado en el punto a. y comentar el resultado obtenido. (1 punto)

Problema

[+20] 
①┬──────→8────→⑦
⠀├──────→15─────→②
⠀└───→1(7)─────→④

[-15]
②──────→4────→⑥

[+30]
③┬─────→7────→④
⠀└───→13(5)─────→⑥

[15]
④┬─────→9────→⑦
⠀├───→2────→②
⠀└───→5───→⑥

[+10]
⑤┬─────→6────→④
⠀├───→14────→⑥
⠀└────→3─────→③

[-25]
⑥

[0]
⑦─→10──→②

a. Determinar el modelo de programacio ́n matema ́tica que permita resolver el problema de flujo de coste m ́ınimo representado en la figura, donde los pesos de los arcos representan el coste en EUR por unidad de flujo transmitida y los pesos de arcos y nodos entre pare ́ntesis representan capacidades. (1 punto) b. Resolver con Matlab3 el modelo obtenido en el punto a. y comentar el resultado obtenido. (1 punto)

Problema

Determinar el a ́rbol de expansio ́n m ́ınima del grafo representado en la figura siguiente, donde los pesos de los arcos representan distancias.

graph LR
    I[9] <-->|2|H[8]
    I[9] <-->|5|A[1]
    I[9] <-->|1|E[5]
    I[9] <-->|6|C[3]
    I[9] <-->|2|D[4]
    H[8] <-->|3|G[7]
    H[8] <-->|1|A[1]
    A[1] <-->|2|G[7]
    A[1] <-->|5|B[2]
    E[5] <-->|1|B[2]
    E[5] <-->|7|F[6]
    E[5]<-->|2|D[4]
    D[4]<-->|4|F[6]
    D[4]<-->|2|C[3]
    G[7]<-->|4|J[10]
    G[7]<-->|3|B[2]
    B[2]<-->|5|J[10]
    B[2]<-->|2|C[3]
    B[2]<-->|1|F[6]
    F[6]<-->|1|C[3]
    C[3]<-->|1|J[10]