UNIDAD 2

PROGRAMACIÓN LINEAL
La palabra programación no hace referencia a la utilización de códigos computacionales, en
realidad su nombre se origina en la Segunda Guerra Mundial, época en la cual los planes de
abastecimiento, el despliegue de unidades, la utilización del material bélico eran denominados
programas, y el objetivo de cada programa era optimizar recursos.

En la vida cotidiana nos encontramos inmersos en distintas situaciones en las que la disyuntiva
es optimizar recursos, por ejemplo, teniendo diferentes alternativas, cómo invertir nuestro
dinero para obtener más rendimiento del capital; en una empresa hallar una política de
producción que minimice costos y maximice ganancias, etc.
Una diversidad de problemas empresariales, de economía ciencia, etc., requieren determinar el
valor máximo si se trata de ganancia o el valor mínimo en cuanto a costo.
Ésta ganancia o éste costo estará representado por una función denominada ¨Función
Objetivo(FO)¨ cuya característica es ser lineal, además, la FO se sujetará a ciertas limitaciones
propias de la situación en discusión, estas limitaciones o restricciones están dadas por
igualdades y/o desigualdades lineales.
Aquellos problemas de programación línea (PL) que contengan únicamente dos variables
pueden ser resueltos por el método gráfico.
Consideremos el problema:
Cierta fábrica de muebles desea producir anaqueles y escritorios, la empresa cuenta con 800
metros de madera de pino y 900 horas de mano de obra, además se conoce que, para la
fabricación de un anaquel, se requiere de 5 metros de madera y 10 h de mano de obra y se
obtiene una ganancia de $45 por anaquel. Para la fabricación de un escritorio, se requiere de
20 metros de madera y 15 h de mano de obra y se obtiene una ganancia de $80. El departamento
de ventas considera que es posible vender todos los anaqueles y todas las mesas que se
elaboren.
Respecto a la información anterior, surgen las siguientes inquietudes:

 ¿Qué plan de producción es el adecuado para maximizar nuestra ganancia?

 ¿Cuál es la ganancia máxima?
 ¿Qué sucedería si los anaqueles por especulación del mercado alcanzan un valor de
$55, en este caso cuál es el plan de producción aconsejado?

Para dar solución a este problema se requiere la cuantificación de sus diferentes elementos. Es de
competencia de la IO la cuantificación de problemas (simples y/o complicados) de nuestro diario vivir
con este tipo de enfoque.
La IO utiliza la PL y es quien nos ayudará a contestar todas estas interrogantes con la utilización de
herramientas como el método gráfico y el método simplex.
CARACTERÍSTICAS

 Deben existir varias soluciones para un determinado problema

 Para la optimización se debe fijar un criterio de decisión
 Existe interdependencia entre las variables de la FO y las restricciones
 Las variables, la FO y las restricciones son del tipo línea
APLICACIONES
Entre otras tenemos:

 Transporte: Para determinar las rutas de transporte de un origen a un destino

 Formulación de dietas: Para establecer las dosis específicas de cada tipo de alimento
que debe ingerir una persona
 Presupuesto: Para definir la distribución del presupuesto a los diferentes
departamentos de la empresa
 Aerolíneas comerciales: Para establecer una programación de vuelos
 Comunicación: Diseño de redes
 Industria del petróleo: Para obtener mezclas óptimas, dar solución a problemas de
transporte, planeación de la producción

DESIGUALDADES LINEALES EN DOS VARIABLES

A menudo, la mayoría de nosotros estamos familiarizados con las ecuaciones o igualdades matemáticas
(=); las desigualdades o inecuaciones son expresiones matemáticas en las que se involucra las
expresiones: ≤, ≥, <, >, las dos últimas expresiones representan desigualdades estrictas.
Consideremos la ecuación 𝑦 = 2𝑥 − 4, ésta ecuación podemos graficarla en el plano cartesiano
ya sea dando valores a la variable x, ó realizando intersecciones con los ejes.
En el primer caso supongamos 𝑥 = 1, al reemplazar en la ecuación inicial tenemos 𝑦 = 2(1) − 4, se
tiene 𝑦 = −2 y obtenemos el punto A (1,-2) si 𝑥 = 3 tenemos 𝑦 = 2(3) − 4, 𝑦 = 2 tenemos el punto
B (3,2)
Otra forma de graficar es la intersección con los ejes : cuando 𝑦 = 0 , entonces 𝑥 = 2, así tenemos el
punto C(2,0) ahora si 𝑥 = 0 resulta 𝑦 = −4 y nuestro punto es D (0,-4). Cualquiera de las dos formas,
aunque proporcionan puntos distintos al final la gráfica es la misma recta.
GRAFIQUE 𝑦 = 4𝑥 − 3
En el caso de las desigualdades ¿cuál es su gráfica?
Para graficar desigualdades seguimos los siguiente pasos:
1.-Graficamos la ecuación asociada a la inecuación.
2.- Una vez graficada la recta escojemos un punto arriba de la recta o bajo ella (si la recta no pasa por
el origen se recomienda tomar el punto (0,0)
3.- Reemplazamos el punto elegido en la inecuación y determinamos la verdad de esta
4.- Si la relación es verdadera, sombreamos la región que contiene el punto elegido
5.- Si la relación no es verdadera, sombreamos la región que no contiene el punto elegido.

La solución son infinitos puntos correspondientes al semiplano que hemos sombreado.

Consideremos la desigualdad 𝒚 ≤ 𝟐𝒙 − 𝟒.

Paso 1 y 2 graficamos la ecuación asociada 𝒚 = 𝟐𝒙 − 𝟒.

Paso 3: Reemplazamos el punto escojido en la inecuación original

𝒚 ≤ 𝟐𝒙 − 𝟒. 𝟎 ≤ 𝟐(𝟎) − 𝟒 𝟎 ≤ −𝟒 la inecuación es falsa,

entonces el semiplano solución es el lado de la recta que no contiene al punto
elegido.
Supongamos alguien decide elegir un punto bajo la recta por ejemplo (2,-4) y reemplazamos
en 𝒚 ≤ 𝟐𝒙 − 𝟒. −𝟒 ≤ 𝟐(𝟐) − 𝟒 −𝟒 ≤ 𝟎 la inecuación es
verdadera, entonces el semiplano solución es el lado de la recta que contiene al
punto elegido.

𝒚 ≤ 𝟐𝒙 − 𝟒

En el caso de que si la desigualdad es estricta 𝑦 < 2𝑥 − 4 la gráfica de la recta es

entrecortada.

entrecortada
 Para 𝑦 ≥ 4𝑥 − 3 x=y

X=a

x = -3 Y=4
 Para 𝒚≤𝟒
𝒙 ≤ −𝟑

En el caso de un sistema de inecuaciones los pasos a seguir son los mismos.

El resultado final es la zona básica factible de soluciones (ZBFS) que es aquella zona en la cual
se intersecan todas las zonas de solución (coinciden todas las zonas de rayado).
En la ZBFS identificamos los vértices de dicha zona, los mismos que los determinamos por
simple observación unos, y otros resolviendo el sistema de ecuaciones formado por las rectas
intersecantes.
 SISTEMA DE INECUACIONES Primer Segundo
punto punto
(x ,y) (x,y)
𝑥≤4
𝑥+𝑦≤6 (0,6) (6,0)
𝑦≤5
x,y≥ 0 La ZBFS está en el primer
cuadrante

B C

A
E

VÉRTICES: A(0,0); B(0,5); E(4,0), C y D los determinamos resolviendo el sistema de ecuaciones:

𝑦=5 reemplazando y=5 en 𝑥 + 𝑦 = 6 𝑥+5=6
Luego C(1,5)
𝑥+𝑦=6 entonces x= 1

𝑥 ≤ 4reemplazando x=4 en 𝑥 + 𝑦 = 6 4+𝑦 =6 Luego D (4,2)

𝑥+𝑦=6 entonces y= 2
SISTEMA DE INECUACIONES Primer Segundo
punto punto
(x ,y) (x,y)
( 𝐿1 ) 2𝑥 − 3𝑦 > −12 (0,4) (-6,0)
3𝑥 + 𝑦 > −6 (0,-6) (-2,0)
𝑦>𝑥 (0,0) (1,1)
−6 < 𝑦 < 5

C
D
B

2𝑥 − 3(−6 − 3𝑥) = −12 x=-30/11

30
𝑦 = −6 − 3(11) y=24/11 EL PUNTO RESULTANTE DEL SISTEMA ES B (-30/11, 24/11)

2𝑥 − 3𝑦 = −12 2x-3(5) =-12

𝑦 = 5 x=3/2 EL PUNTO RESULTANTE DEL SISTEMA ES C (-3/2, 5)

𝑦=𝑥
𝑦=5 D (5,5)
4𝑥 = −6 x=-6/4y=-6/4
𝑦=𝑥 EL PUNTO RESULTANTE DEL SISTEMA ES A (-3/2, -3/2)
PLANTEAMIENTO DEL PROBLEMA DE PROGRAMACIÓN LINEAL
1.- Conocer y entender el problema: Leer detenidamente el problema y determinar su objetivo
2.- Definir variables de decisión: Se establece las variables de decisión (𝑥1 , 𝑥2 , 𝑥3 , … ). Por lo general
se las identifica en la pregunta del problema
3.- Determinar la Función Objetivo (FO): Se define la FO, la misma que relaciona las variables de decisión
y representa la meta a ser alcanzada (por ejemplo: máxima utilidad, costo mínimo, etc.).
4.- Establecer las restricciones estructurales: las restricciones estructurales son propias de cada
problema, relacionan las variables de decisión y representan las limitaciones de la situación en estudio.
5.-Plantear las restricciones no explícitas: Las restricciones no explícitas son las condiciones que el
ejercicio no especifica a cerca de las variables de decisión, como el que estas no deben ser negativas,
que posiblemente dependiendo de la naturaleza del problema a veces deban ser enteras.
La PL será útil siempre que el problema se pueda describir mediante ecuaciones y desigualdades
lineales.
En resumen:

Un negocio se dedica a la fabricación de sillas y mesas. El negocio tiene dos departamentos: el

de corte y el de ensamble, los mismos que tienen disponibles una cantidad limitada de horas
de trabajo, 120h para corte y 90h para ensamble. La venta de una silla representa para la
empresa una ganancia de $80 y la venta de una mesa $50. La fabricación de una silla consume
2h en el departamento de corte y 1h en el de ensamble, mientras que para una mesa es
necesario 1h en el departamento de ensamble y 1h en el de corte. Determine la cantidad a
producir de sillas y mesas para obtener la máxima ganancia posible.

Paso 1: Determinamos las VARIABLES DE DECISIÓN que por lo general las encontramos en la
pregunta.
𝒙𝟏 : 𝑪𝒂𝒏𝒕𝒊𝒅𝒂𝒅 𝒅𝒆 𝒎𝒆𝒔𝒂𝒔 𝒒𝒖𝒆 𝒔𝒆 𝒅𝒆𝒃𝒆 𝒑𝒓𝒐𝒅𝒖𝒄𝒊𝒓
𝒙𝟐 : 𝑪𝒂𝒏𝒕𝒊𝒅𝒂𝒅 𝒅𝒆 𝒔𝒊𝒍𝒍𝒂𝒔 𝒒𝒖𝒆 𝒔𝒆 𝒅𝒆𝒃𝒆 𝒑𝒓𝒐𝒅𝒖𝒄𝒊𝒓

Paso 2: Definimos la FUNCIÓN OBJETIVO, la misma que en general se encuentra asociada a la

maximización o minimización de recursos.
 𝒁 = 𝟓𝟎𝒙𝟏 + 𝟖𝟎𝒙𝟐

Paso 3: Identificamos las RESTRICCIONES (limitaciones) a las cuales se encuentra sujeta la FO.
En el departamento de corte se consume 1h por mesa y 2h por silla , el departamento solo
dispone de 120h(no debemos excedernos de esa cantidad), entonces
𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟏𝟐𝟎.
En el departamento de ensamble se consume 1h por mesa y 1h por silla , el departamento solo
dispone de 90h (no debemos excedernos de esa cantidad), entonces
𝒙𝟏 + 𝒙𝟐 ≤ 𝟗𝟎.

Paso 4: Restricciones implícitas

La cantidad de sillas y masas a producir no deben ser negativas, por tanto 𝒙𝟏 , 𝒙𝟐 ≥ 𝟎, además
deben ser cantidades enteras.
Para este ejercicio, la estructura de nuestro problema de programación lineal es la siguiente:
Maximizar
𝒁 = 𝟓𝟎𝒙𝟏 + 𝟖𝟎𝒙𝟐
Sujeta a:
𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟏𝟐𝟎
𝒙𝟏 + 𝒙𝟐 ≤ 𝟗𝟎
𝒙 𝟏 , 𝒙𝟐 ≥ 𝟎

Paso 5: Resolvemos el sistema de inecuaciones y hallamos la zona básica factible de

soluciones

Primer punto Segundo punto

𝒙𝟏 + 𝟐𝒙𝟐 ≤ 𝟏𝟐𝟎 (0,60) (120,0)
𝒙𝟏 + 𝒙𝟐 ≤ 𝟗𝟎 (0,90) (90,0)
𝒙𝟏 , 𝒙 𝟐 ≥ 𝟎 Si las dos variables son no negativas, la ZBFS estará en el
primer cuadrante.