Introducción a la programación lineal

La programación lineal facilita la resolución de problemas de producción, economía,

rendimiento, etc. Resolver un problema de programación lineal consiste en optimizar
(maximizar o minimizar) una función lineal, denominada función objetivo, estando las
variables sujetas a una serie de restricciones expresadas mediante inecuaciones lineales. El
conjunto de todas las soluciones posibles se denomina conjunto solución factible. Para
resolver problemas de programación lineal se siguen tres pasos: planteamiento, determinación
de la región factible y determinación de la solución óptima.

Planteamiento
Para plantear la solución de un problema de programación lineal, debemos realizar lo
siguiente:
 Organizar la información mediante una tabla.
 Identificar y representar las incógnitas.
 Determinar las restricciones que se crean convenientes.
 Plantear la función objetivo.

Ejemplo 1

En una panadería se dispone diariamente de 80 kg de masa y de 24 kg de frutas (secas y

confitadas) para preparar dos tipos de panetones: panetón especial, con 200 g de frutas y 1 kg
de masa, y panetón premium, con 400 g de frutas y 1 kg de masa. Si el panetón especial se
vende a S/. 18 Y el panetón premium a S/. 24, determina las restricciones y plantea la función
objetivo que determina el máximo ingreso.

 Del análisis de la información del problema, tenemos:

 Dos cantidades de insumos: masa y frutas (secas y confitadas).
 Dos tipos de panetón: especial y premium, cada uno con un precio.
 Se desea obtener el máximo ingreso por la venta de los panetones.

 Organizamos la información en una tabla:

Insumos por panetón Disponibilidad

Especial Premium por día (kg)

Masa (kg) 1 1 80
Frutas (kg) 200 g = 0,2 kg 400 g = 0,4 kg 24
Precio (S/.) 18 24

 Identificamos y representamos las incógnitas:

x: número de panetones especiales y: número de panetones
premium

 Determinamos las restricciones:

  De insumos: masa x + y ≤ 80 frutas 0,2x + 0,4y ≤ 24
 De no negatividad, x e y son valores enteros no negativos: x ≥0; y ≥0

 Como 18x es el ingreso total por la venta de los panetones especiales y 24y por la de los
panetones premium, entonces la función objetivo que determina el máximo ingreso es:
F(x; y) = 18x + 24y.

Determinación de la región factible

La solución de un problema de programación lineal debe estar en la región determinada por
las
distintas desigualdades. Esta recibe el nombre de región factible, y puede estar o no estar
acotada. Si la región factible está acotada, su representación gráfica es un polígono con
un número de lados menor o igual que el número de restricciones.

Ejemplo 2

Determina la región factible del problema anterior (ejemplo 1)

El sistema que se va a graficar es:

x ≥0; y ≥0 x ≥0; y ≥0
x + y≤ 80 x + y≤ 80
0,2x + 0,4y≤ 24 x + 2y ≤ 120

 Determinamos las soluciones de los seis

sistemas que se forman:

A x =0 B x =0 E y =0
y =0 x + y= 80 x + 2y= 120
A (0; 0) B (0; 80) E (120; 0)
C y =0 D X =0 F x + y =80
x + y = 80 x + 2y = 120 x + 2y= 120
C (80; 0) D (0; 60) F (40; 40)

La solución es una región factible acotada. Su representación gráfica es el polígono

ACFD.

Determinación de la solución óptima

La solución óptima es aquella que maximiza o minimiza la función objetivo F(x, y). Se
encuentra en la frontera de la región factible.

Ejemplo 3
 Si la función objetivo es F(x; y) = 18x + 24y (problema del ejemplo 1), determina
la solución óptima.
 Identificamos los vértices: A(0; 0), C(80; 0), F(40; 40) y D(0; 60)
 Evaluamos la función objetivo en cada punto:

Punto A: F(0; 0) = 18(0) + 24(0) = 0

Punto C: F(80; 0) = 18(80) + 24(0) = 1440
Punto F: F(40; 40) = 18(40) + 24(40) = 1680
Punto D: F(0; 60) = 18(0) + 24(60) = 1440

La solución óptima se obtiene en el punto F, donde la función objetivo F(x; y) = 18x + 24y
= 40 e y = 40. Esto quiere decir que para obtener el máximo
obtiene su máximo valor cuando x
ingreso (S/. 1 680 diarios), se necesitan vender 40 panetones especiales y 40 panetones
premium por día.
Tipos de soluciones

Los problemas de programación lineal con dos variables pueden presentar distintos tipos
de soluciones.

Solución única
La solución es única cuando la solución óptima se encuentra solo en uno de los vértices.

Ejemplo 4

En un taller se fabrican estantes y escritorios. En la fabricación de cada estante se requieren 5

pies de madera y 8 horas de trabajo, y en la de un escritorio, 15 pies de madera y 12 horas de
trabajo. En el almacén del taller hay 420 pies de madera y las horas de trabajo disponibles son
480. Si se quiere obtener la máxima utilidad ganando en la venta de cada estante SI. 60 Y de
cada escritorio SI. 110, ¿cuántos muebles de cada tipo deben fabricarse?

 Identificamos y representamos las incógnitas:

X: número de estantes y: número de escritorios

 Organizamos la información en una tabla:

Estantes Escritorios Disponibilidad

Pies de madera 5 15 420
Horas de trabajo 8 12 480
Precio (S/.) 60 110

x ≥0; y ≥0
 Determinamos las restricciones:
5x + 15y ≤420 => x + 3y ≤ 84

8x + 12y ≤ 480 => 2x + 3y ≤ 120

 Planteamos la función objetivo que permita obtener la máxima utilidad F(x; y) = 60x +
110y
 Determinamos los vértices A(O; O), B(O; 28), C(36; 16), D(60; O) y graficamos la
región factible:
 Determinamos la solución óptima:
 En A: F(0; 0) = 60(0) + 110(0) = 0
 En B: F(0; 28) = 60(0) + 110(28) = 3080
 En C: F(36; 16) = 60(36) + 110(16) = 3920 Solución óptima
 En D: F(60; 0) = 60(60) + 110(0) = 3600

La máxima utilidad se obtiene en el vértice C (36; 16). Esta solución única indica que
deben fabricarse 36 estantes y 16 escritorios. En tal caso, dicha utilidad es de S/. 3 920.

 Una panadería vende tortas chicas a S/. 19 cada una, y tortas grandes a S/. 30 cada una.
La capacidad máxima de elaboración de tortas es de 100 al día, entre grandes y chicas.
Pero por falta de moldes, no se pueden elaborar más de 80 tortas chicas ni más de 60
grandes. Como la panadería vende todo lo que produce, el administrador desea averiguar
cuántas tortas grandes y cuántas chicas deben elaborar para la venta y así obtener el
máximo ingreso posible. Además, quiere saber a cuánto ascendería este ingreso máximo,

Solución Múltiple

La solución es múltiple cuando hay infinitas soluciones que corresponden a los puntos del
segmento que tiene por extremos a dos vértices de la región factible.

Ejemplo 5

Un granjero tiene 480 hectáreas en la que puede sembrar maíz o trigo y dispone de 800 h
de trabajo durante la temporada. Los márgenes de utilidad para cada uno de los productos son
S/. 40 por hectárea y los requerimientos laborales para trabajar en la siembra de maíz son 2 h
por hectárea y en la del trigo, 1 h por hectárea. ¿Cuántas hectáreas de cada cultivo debe plantar
para maximizar su utilidad? ¿Cuál es la utilidad máxima?

x: número de hectáreas sembradas de maíz

 Incógnitas
y: número de hectáreas sembradas de trigo

 Organizamos la información en una tabla:

Maíz Trigo Disponibilidad

Superficie 1 hectárea 1 hectárea 480 hectáreas

Requerimiento laboral 2 horas 1 hora 800 horas
Utilidad S/. 40 S/. 40
  Determinamos las restricciones: x ≥0; y ≥0; x + y ≤ 480; 2x + y ≤ 800
 La función objetivo que maximiza la utilidad es: F(x; y) = 40x + 40y
 Sus vértices son: A(0; 0), B(0; 480), C(320; 160) y D(400; 0).
 Graficamos en el margen la región factible.
 Calculamos el valor de la función objetivo en cada uno de los
vértices:
 En A: F(0; 0) = 40(0) + 40(0) = 0
 En B: F(O; 480) = 40(0) + 40(480) = 19200
 En C: F(320; 160) = 40(320) + 40(160) = 19 200
 En D: F(400; O) = 40(400) + 40(0) = 16000

La máxima utilidad se obtiene en los vértices B y C, y también en cualquiera de los puntos de

BC. En todos estos casos, su máxima utilidad es S/. 19200.

Solución no acotada
Cuando la función objetivo no tiene valores extremos, la región factible es no acotada.

Ejemplo 6

Maximiza la función objetivo F(x; y) = x + 2y para un problema cuyas restricciones son: x ≥0; y
≥0; x - 2y :≤ 2; x - y ≥ 4

 Resolvemos los sistemas qué se forman y obtenemos: (0;0), (0; -1), (0; -4), (2; 0), (4; 0) y (6; 2)
 Graficamos en el margen; la región factible se extiende infinitamente y su único
vértice está en A (6; 2).
 En este caso no existe un valor máximo para la función objetivo, por lo que puede
decirse que el problema carece de solución.

Solución no factible
Cuando no existe la región por falta de zona común en el sistema de inecuaciones, la solución es no
factible.

Ejemplo 7

Sea un problema en que las restricciones son: x ≥0; y ≥0; x + y ≥ 6; 2x + y ≤ 4. Maximiza

la función objetivo F(x, y) = 4x + 3y

 Resolvemos el sistema y obtenemos: (6; 0), (0; 0), (0; 6), (0; 4), (2; 0) y (-2; 8)
 Representamos gráficamente el sistema:

 Observamos que no existe región factible, ya que no hay zona común en el sistema de
inecuaciones.
 Por lo tanto, este problema carece de solución.