Pagina principal

1 Definiciones

Programación Lineal (PL): Es una rama de la programación matemática dedicado a la optimizacion de funciones lineales Minimizacion o maximizacion y cuya funcion esta sujeta a restricciones expresadas en ecuaciones e inecuaciones tambien lineales. Existen muchos métodos para resolver problemas de programacion lineal, el más utilizado es el método simplex.

Modelo de programación lineal:

Conjunto de expresiones lineales que se delimitan una región factible, que buscan optimizar una combinación lineal de las variables. Un modelo de programacion lineal consta de los siguientes elementos:

  • Función objetivo: Es una funcion lineal que deberá ser optimizada bajo dos posibles enfoques(Maximizar o Minimizar).
  • Restricciones: Son condiciones descritas en expresiones algebraicas de tipo lineal que limitan a la función objetivo.

Para ejemplificar un modelo de PL, definiremos lo siguiente:

\(P_i :=\) conjunto de productos \(i \in {1, 2, 3, ... , n}\)

\(Y:=\) Gancia total.

\(\beta_i:=\) Ganancias unitarias por producto i.

\(x_i:=\) Cantidad de unidades de producto i.

\(D_i:=\) Demanda del producto i.

\(B:=\) Presupuesto global.

\(C_i:=\) Costo por producir y vender el producto i.

Dado lo anterior, el modelo de PL en su forma general se deja escribir como:

\[Max \: Y = \sum_{i \in P} \: \left ( \beta_i \times x_i \right )\]

sujeto a:

\[x_i \leq D_i \: \forall \: i \in P\]

\[\sum_{i \in P}\left( C_i \times x_i \right) \leq B \: \forall \: i \in P\] \[ x_i \geq 0 \: \forall \: i \in P\] Para \(i \in {1, 2}\), el modelo de PL en su forma extendida se deja escribir como:

\[Max \: Y = \: (\beta_1 \times x_1) + (\beta_2 \times x_2)\]

sujeto a:

\[x_1 \leq D_1\] \[x_2 \leq D_2\]

\[(C_1 \times x_1) + (C_2 \times x_2)\leq B\] \[x_1 \geq 0\] \[ x_2 \geq 0 \]

2 Forma estándar

  • Podemos transformar cualquier problema en la forma estándar.

  • Considere un problema general, como el siguiente:

    \[ Min \; f(x_1, ... , x_n) = c_1 x_1 + ... + c_n x_n \] \(s.a\)

\[a_{11} x_1 + ... + a_{1n} x_n \leq b_1 \\ a_{21} x_1 + ... + a_{2n} x_n \geq b_2 \\ . \quad \quad \quad . \quad \quad \quad\quad\quad . \\ . \quad \quad \quad . \quad \quad \quad\quad\quad . \\ . \quad \quad \quad . \quad \quad \quad\quad\quad . \\ a_{m1} x_1 + ... + a_{mn} x_n = b_n \\ x_1, ... , x_n \geq 0\]

Usaremos las siguientes equivalencias

  1. \(Max \; f(x) = (1) \times min - f(x)\). En la forma estádar la FO debe ser de maximización.
  2. \(a_{11} x_1 + ... + a_{1n} x_n \leq b_1 \Rightarrow a_{11} x_1 + ... + a_{1n} x_n + {\color{darkblue}{s_{1}}=} \; b_1\). Siendo \({\color{darkblue}{s_{1}}} \geq 0\) una variable de \(\color{darkblue}{holgura}\).
  3. \(a_{21} x_1 + ... + a_{2n} x_n \geq b_2 \Rightarrow a_{21} x_1 + ... + a_{2n} x_n - {\color{darkblue}{s_{2}}=} \; b_2\). Siendo \({\color{darkblue}{s_{2}}} \geq 0\) una variable de \(\color{darkblue}{exceso}\).
  4. Si algun valor de \(b_i < 0\), entonces multiplicaremos la inecuacion por -1

Ejemplo:

El siguiente problema de PL en su forma canónica, puede ser transformado en la forma estándar como:

\[ \begin{matrix} Max \: Y = \: \beta_1x_1 + \beta_2x_2& & Max \: Y = \beta_1x_1 +\beta_2x_2 + 0s_1 + 0s_2 + 0s_3\\ x_1 \leq D_1 & & x_1 +0x_2 + s_1 + 0s_2 + 0s_3 = D_1\\ x_2 \leq D_2 & \implies & 0x_1 +x_2 + 0s_1 + s_2 + 0s_3 = D_2\\ c_1x_1 + c_2x_2 \leq B & & c_1x_1 +c_2x_2 + 0s_1 + 0s_2 + s_3 = B\\ x_1, x_2\geq 0 & & x_1, x_2, s_1, s_2, s_3 \geq = 0 \end{matrix}\]

3 Notación Matricial

  • Considere un problema general en su forma estándar, como el siguiente:

\[ Max \; f(x_1, ... , x_n) = c_1 x_1 + c_2 x_2 + ... + c_n x_n \]

\(\quad \quad s.a\)

\[a_{11} x_1 + a_{12} x_2 + ... + a_{1n} x_n = b_1 \\ a_{21} x_1 + a_{22} x_2 + ... + a_{2n} x_n = b_2 \\ \vdots \quad \quad \quad \vdots \quad \quad \quad \ddots \quad \quad \quad \quad \vdots \\ a_{m1} x_1 + a_{m2} x_2 + ... + a_{mn} x_n = b_n \\ x_1, x_2, ... , x_n \geq 0\]

  • Los valores pueden escribirse en vectores y matrices como:

    \[ {\mathbb x} = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} ,\; {\mathbb c} =\begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix} ,\; {\mathbb A} =\begin{bmatrix} a_{11} \: a_{12} \: ... \:a_{1n} \\ a_{21} \: a_{22} \: ... \:a_{2n} \\ \vdots \quad \vdots \; \; \; \; \ddots \; \; \; \vdots \\ a_{m1} \: a_{m2} \: ... \:a_{mn} \end{bmatrix} ,\; {\mathbb b} =\begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix}\]

  • El problema general en su forma matricial se deja escribir como:

    \[ f({\mathbb x}) = \begin{bmatrix} c_1 & c_2 & \cdots & c_n \end{bmatrix} \times \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} \]

\(\quad\quad sujeto \: a: \\\) \[ \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} \; \times \; \begin{bmatrix} a_{11} \: a_{12} \: ... \:a_{1n} \\ a_{21} \: a_{22} \: ... \:a_{2n} \\ \vdots \quad \vdots \; \; \; \; \ddots \; \; \; \vdots \\ a_{m1} \: a_{m2} \: ... \:a_{mn} \end{bmatrix} \; = \; \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix}\]

  • Finalmente la notación matricial es definida como:

    \[ Max \; f({\mathbb x}) = {\mathbb c}^T {\mathbb x} \\ S.a: \quad {\mathbb A} {\mathbb x} = {\mathbb b} \\ \quad {\mathbb x} \geq 0\]

    Donde :

    \({\mathbb c}:\) Vector de costos.

    \({\mathbb x}:\) Vector de variables.

    \({\mathbb A}:\) Matriz tecnológica.

    \({\mathbb b}:\) Vector de terminos independientes.

Ejemplo: Considere el siguiente problema de PL en su forma estándar:

\[ \begin{matrix} Max \: Y = \beta_1x_1 +\beta_2x_2 + 0s_1 + 0s_2 + 0s_3\\ x_1 +0x_2 + s_1 + 0s_2 + 0s_3 = D_1\\ 0x_1 +x_2 + 0s_1 + s_2 + 0s_3 = D_2\\ c_1x_1 +c_2x_2 + 0s_1 + 0s_2 + s_3 = B\\ x_1, x_2, s_1, s_2, s_3 \geq = 0 \end{matrix}\]

Recordemos que la notación matricial se deja escribir como:

\[ Max \; f({\mathbb x}) = {\mathbb c}^T {\mathbb x} \\ S.a: \quad {\mathbb A} {\mathbb x} = {\mathbb b} \\ \quad {\mathbb x} \geq 0\]

Así entonces, los vectores y matrices para el problema planteado los podemos definir como:

\[ {\mathbb x} = \begin{bmatrix} x_1 \\ x_2 \\ s_1 \\ s_2 \\ s_3 \end{bmatrix} ,\; {\mathbb c} =\begin{bmatrix} \beta_1 \\ \beta_2 \\ 0 \\ 0 \\ 0 \end{bmatrix} ,\; {\mathbb A} =\begin{bmatrix} 1 \: \: \: 0 \: \: \: 1 \: \: 0 \: 0 \\ 0 \: \: \: 1 \: \: \: 0 \: \: 1 \: 0 \\ c_1 \: c_2 \: 0 \: \: 0 \: 1 \\ \end{bmatrix} ,\; {\mathbb b} =\begin{bmatrix} D_1 \\ D_2 \\ B \end{bmatrix}\]

4 Ejercicios para practicar

  1. Una metalúrgica produce dos tipos de aleaciones metálicas. Cada aleación está compuesta por proporciones diferentes de cobre, zinc y plomo, las cuales están disponibles en cantidades limitadas en el inventario. Se desea determinar cuanto producir de cada aleación, de modo que se maximice la ganancia bruta, satisfaciendo las siguientes composiciones y disponibilidades de materia prima en el inventario:
Materia Prima Aleación 1 Aleación 2 Inventario (Ton)
Cobre 50% 30% 3
Zinc 10% 20% 1
Plomo 40% 50% 3
Precio de venta 3000 2000 -
  1. Formule un modelo de programación lineal para el anterior problema.
  2. Escriba el modelo en su forma estándar.
  3. Escriba el modelo con notación matricial, especificando los vectores y matrices utilizados.

  1. Hacía el final de la dinastía Han del este, personas sufrieron bajo el cruel gobierno de la época. El ejército turbante amarillo estalló causando caos.

    Tres soldados se conocieron y juraron eliminar el ejército turbante amarillo con el fin de unificar a la Dinastía Han.

    Los soldados planearon reclutar soldados de los pueblos Feng, Liu, Zhao y Jian. Los hombres que estaban disponibles para el reclutamiento eran diferentes en términos de su poder, salario y número como se muestra a continuación:

Los soldados solo tenían un presupuesto de $10.000 para pagar a todos los soldados contratados. Formule un modelo de PL que ayude a determinar cuantos soldados de cada pueblo se deberian de contratar para maximizar la fuerza total.