INVESTIGACIÓN DE OPERACIONES I

PROGRAMA DE ESTUDIO
Objetivo
Familiarizar al alumno con las técnicas de modelamiento y
metodologías de resolución de problemas de la Investigación de
operaciones, con especial énfasis en la aplicación de algoritmos de
solución para modelos de programación matemática, en especial
modelos lineales

Contenido
Introducción • Investigación de operaciones
• Modelos matemáticos
• Programación Lineal

Programación • Formulación de modelos

Lineal • Métodos Gráfico
• Método Simplex
• Problema Dual y Análisis de Sensibilidad
• Programación Entera, Binaria y Mixta
 INVESTIGACION DE OPERACIONES
PROGRAMA DEL CURSO
DESCRIPCION
El curso trata principalmente sobre la aplicación de los modelos
usuales de Investigación de Operaciones en la solución de
problemas reales, tales como modelos de Programación Lineal,
Entera, Binaria y Mixta

OBJETIVOS
• Aplicar modelos cuantitativos en la resolución de problemas
lineales.
• Optimizar soluciones usando la Investigación de Operaciones.

METODOLOGÍA
• Clases expositivas para conceptos teóricos con discusiones sobre
cada tema y participación activa del alumno.
• Practicas en laboratorio, donde se conocerán el uso del software de
apoyo a la Investigación de Operaciones.
 BIBLIOGRAFIA
• TAHA HAMDY A. Investigación de operaciones. PEARSON. 9
Ed. 2012
• HILLIER, FREDERICK Y LIEBERMAN, GERALD: “Introducción
a la Investigación de Operaciones”, McGraw – Hill
Interamericana
• WINSTON WAYNE L.: “Investigación de Operaciones:
Aplicaciones y Algoritmos”. Grupo Editorial Iberoamericana.
• DAVIS K ROSCOE y MC KEOWN Patrick. Modelos
Cuantitativos para Administración. Grupo editorial
Iberoamerica. 2 Ed. 1986.   
• PRAWDA, Juan. Métodos y modelos de Investigación de
operaciones. Limusa.
• JORGE ALVAREZ ALVAREZ, Investigación de Operaciones,
Universidad Nacional de Ingeniería, Edición 2001
 INVESTIGACION DE OPERACIONES

Definición:
Conjunto de técnicas matemáticas y estadísticas aplicable a diversos
sistemas con el fin de mejorarlos, buscando las mejores alternativas de
acción; esto mediante el modelamiento matemático de los problemas en
estudio.
¿Qué es la investigación de
operaciones?

Lawrence y Pasternak, (1998) “Es un enfoque

científico para la toma de decisiones ejecutivas,
que consiste en:

• El arte de modelar situaciones complejas,

• La ciencia de desarrollar técnicas de
solución para resolver dichos modelos.
• La capacidad de comunicar efectivamente
los resultados”.
¿Qué es la investigación de
operaciones?

Kamblesh Mathur: “Es el uso de la Matemática

y computadoras para ayudar a tomar
decisiones racionales frente a problemas de
administración”.

Jorge Alvarez: “Es un procedimiento o un

enfoque para resolver problemas relacionados
con la toma de decisiones”.
 RESUMIENDO
La Investigación de Operaciones es el uso de la matemática e
informática para resolver problemas del mundo real, tomando
decisiones acertadas que garanticen el éxito.

La investigación de operaciones tiene como objetivo buscar las

soluciones que sean significativamente mas eficientes (en
tiempo, recursos , beneficios , costos , etc.)
 TOMA DE DECISIONES

Toda toma de decisión empieza con la

detección de un problema.

Para tomar la decisión correcta, se debe:

Definir el problema en forma clara

Formular el o los objetivos

Identificar las restricciones

Identificar las alternativas de solución

Evaluar las alternativas y elegir la mejor

 CARACTERÍSTICA
Tiende a representar el problema cuantitativamente para poder
analizarlo y evaluar un criterio común.
 TOMA DE DECISIONES

¿Como se elige la mejor

alternativa?

Métodos Cualitativos

En base a la experiencia y al juicio profesional

de la persona que toma la decisión

Métodos Cuantitativos

En base a la utilización de herramientas

matemáticas que permitan maximizar la
efectividad en la toma de decisiones.
INVESTIGACIÓN DE OPERACIONES

La dificultad de tomar decisiones ha hecho que el hombre se aboque

en la búsqueda de una herramienta o métodos que le permita tomar
las mejores decisiones de acuerdo a los recursos disponibles y a los
objetivos que persigue.

Este conjunto de herramientas o métodos es lo que llamaremos

Investigación de Operaciones.

Definición más formal

“Enfoque científico de la toma de decisiones que requiere la

operación de sistemas organizacionales”.

La IO nos ofrece una serie de herramientas cuantitativas para la toma

de decisiones.
 MODELOS DE LA INVESTIGACIÓN DE
OPERACIONES
Modelos de IO

Determinísticos Híbridos Estocásticos

Optimización Optimización
Programación Cadenas
Lineal no Lineal
Dinámica de Markov

Programación Métodos
Teoría de Teoría de
Lineal Clásicos
Inventarios Colas

Transporte y Métodos
Asignación de búsqueda Simulación Procesos
Estocásticos

Prog Entera Programación Pert / CPM

y 0,1 no lineal Teoría de
Decisiones
Heurísticas y Juegos
Redes
¿Qué se busca en el curso de Investigación
de Operaciones?

Se intenta encontrar una mejor solución llamada solución

óptima.

Areas de Aplicación de la Investigación de Operaciones

Manufactura.
Transporte.
Telecomunicaciones.
Salud.
Planeación.
Servicios.
Finanzas.
Otros.
 LA NATURALEZA DE UN SISTEMA

Un sistema es un conjunto de dos o más elementos que satisface las

siguientes tres condiciones:

• La conducta de cada elemento tiene un efecto sobre la conducta del

todo.

• La conducta de los elementos y sus efectos sobre el todo son

interdependientes.

• Sin considerar cómo se formen los subgrupos de elementos, cada

uno tiene un efecto sobre la conducta del todo, y ninguno tiene un
efecto independiente sobre él.
 SISTEMAS V/S PROCESOS

• Proceso: Conjunto de actividades que crean una salida o

resultado a partir de una o más entradas o insumos.
• Sistema: Un conjunto de elementos interconectados utilizados
para realizar el proceso. Incluye subprocesos pero también
incluye los recursos y controles para llevar a cabo estos procesos.
• En el diseño de procesos nos enfocamos en QUÉ se ejecuta.
• En el diseño del Sistemas el énfasis está en los detalles de
CÓMO, DÓNDE Y CUÁNDO.
 SISTEMAS V/S PROCESOS
Reglas de
Operación
(Controles)

Sistema

Entidades Entidades
que Entran Actividades
que Salen

Recursos
 METODOLOGÍA DE LA
INVESTIGACION DE OPERACIONES
Problema

Es identificar, comprender y describir en

términos precisos, el problema que la
organización enfrenta. El enunciado es la
definición del problema. Un problema no se
formula sino se define.

Los sistemas son

Los recursos cada vez más
son escasos complejos

Cada vez es más difícil asignar los

recursos o actividades de la forma más eficaz
 MÉTODOS EN INVESTIGACIÓN OPERATIVA

• Métodos determinísticos: Programación lineal, programación

entera, probabilidad de transporte, teoría de la localización o
redes, programación multicriterio, teoría de inventarios, etc.
• Métodos probabilísticos: Cadenas de markov, teoría de juegos,
líneas de espera, teoría de inventarios, etc.
• Métodos híbridos: Conjugan métodos determinísticos y
probabilísticos.
• Métodos heurísticos: soluciones basadas en la experiencia.
 MODELOS
La realidad es multiforme y difícil de capturar. Pero para poder tomar decisiones
de manera racional es necesario conocer las posibilidades que se nos abren y el
efecto de las mismas. Esos “cálculos” los hacemos a través de modelos que
pueden ser más
o menos simples.

El arte de crear modelos requiere mucha experiencia pero también técnica. Y un

poco de filosofía al reconocer que los modelos siempre son representaciones de la
realidad, que asumimos que existe, y es percibida de modo diferente por
diferentes actores en función de sus necesidades.
 ¿QUÉ ES UN MODELO?

“Un modelo es una representación de la realidad”

Pidd (2010) propone la siguiente definición que por su interés se desarrolla

posteriormente:

“Un modelo es una representación explícita y externa de parte de la realidad

como la ven las personas que desean usar el modelo para entender, cambiar,
gestionar y controlar dicha parte de la realidad”

De esta definición se pueden extraer muchas reflexiones interesantes sobre

los modelos y su uso en Investigación de Operaciones. Quizá la más relevante
es que los modelos son representaciones (no son la realidad, que, por cierto,
se asume que existe) pero que los hacemos con un objetivo respecto a la
realidad modelada.
Los modelos son explícitos se construyen manejan y modifican como tales. Y
aunque no se debe confundir el modelo con la realidad, el modelo debe tener
una imagen física sobre la que los diferentes actores puedan opinar.

Los modelos son externos. Mientras no tienen una representación externa

respecto del modelador son simplemente una teoría mental del mismo. En esa
presentación externa radica una de las grandes ventajas de los modelos: ponen
negro sobre blanco los pensamientos, los datos, las hipótesis y las intuiciones.

¿PARA QUÉ SIRVE UN MODELO?

En atención a lo anterior se pueden definir tres ámbitos de utilidad de los modelos en la
Investigación de operaciones:
• Aprender / Entender
La experiencia demuestra que el principal beneficio en la generación de un
modelo es el entendimiento que el modelador adquiere del
comportamiento de la realidad. Puede ocurrir, y de hecho ocurre con
frecuencia, que una vez finalizado el modelo, los objetivos perseguidos
inicialmente se hayan alcanzado sin hacer ningún tipo de experimento.
Modelar como proceso puede tener más valor que el modelo en sí mismo.
• Implementar en un computador
La aparición de los computadores es la que le ha dado a la investigación de
operaciones el impulso necesario. La implementación y automatización de
procesos exige el modelado previo del problema planteado. Si se desea
gestionar la información que genera una empresa, o implementar un sistema
de gestión de recursos humanos es necesario realizar un modelo de dicha
empresa que comprenda de la manera más eficiente posible toda la
información vinculada. Cuanto más general sea el modelo, mayor será la
cantidad de empresas a las que se las podrá aplicar el mismo programa
(software).

• Tomar decisiones
Los modelos construidos permiten mediante su resolución ayudar a la toma
de decisiones generando soluciones óptimas, o suficientemente cercanas al
óptimo, dado un objetivo establecido. Asimismo pueden ser utilizados para
evaluar el impacto de tomar decisiones, antes de tomarlas, y de este modo
elegir la que más se ajuste a la solución.
 METODOLOGÍA DE LA INVESTIGACION
DE OPERACIONES

Desarrollo de un modelo matemático Es la

I) Identificacion de las variables
 Xij = # de consultores que viajan del traducción del problema a términos matemáticos.
origen i al destino j
 II) Identificacion de la funcion objetivo
 Max Es formular un modelo matemático:
540X11+300X12+420X13+ Identificando variables
 500X21+330X22+330X23+ 
520X31+310X32+350X33  Identificando la Función Objetivo
III) Identificacion de las restricciones Identificando las restricciones
 X11+X12+X13 ≤ 2 
X21+X22+X23 ≤ 1 
X31+X32+X33 ≤ 4  Objetivos: función objetivo
X11+X21+X31 = 3 
X12+X22+X32 = 2  alternativas: variables de decisión
X13+X23+X33 = 1  limitaciones del sistema: restricciones
Xij ≥ 0 ; entero
METODOLOGÍA DE LA INVESTIGACION
DE OPERACIONES

Resolución del modelo

Es resolver el modelo usando una técnica

adecuada, es decir obtener valores numéricos
para la variable de decisión.

Es determinar los valores de las variables de

decisión de modo que la solución sea óptima (o
satisfactoria) sujeta a las restricciones.

Puede haber distintos algoritmos y formas de

aplicarlos. En esta parte se usa el Software WIN
QSB. Hay otros como el LINDO, MLP y TORA
 VENTAJA DE LOS MODELOS
Un método óptimo para lograr un objetivo.
Una forma de evaluar preguntas de sensibilidad de la forma:
¿Qué sucedería sí ...?
 EL MODELO DE
PROGRAMACIÓN LINEAL
PROVEE UNA SOLUCIÓN
INTELIGENTE PARA ESTE
PROBLEMA
 Es un Arte que mejora con la
práctica…

¡ PRACTIQUEMOS!
METODOS DE SOLUCION DE PROBLEMAS LINEALES

Métodos:
Gráfico. Fácilmente comprensible y permite visualizar
algunas propiedades.
Analítico. El método simplex ha demostrado ser
eficiente por el uso del computador.
Algeibraíco

Método Gráfico: Este método consiste en delinear sobre el primer

cuadrante (debido a la condición de no negatividad) la región de
soluciones factibles; luego sobre ella se grafica la función objetivo.

Ejemplo 1
Xi = Número de unidades del producto i

Max (Z) = 6X1 + 4X2

Sujeto a:
2 X1 + 2 X2 ≤ 160
1 X1 + 2 X2 ≤ 120
4 X1 + 2 X2 ≤ 280
X1 , X 2 ≥ 0
0, 60

40, 40

60, 20

70, 0
Región Factible. Es aquella que cumple con todas las
restricciones y las condiciones de no negatividad.

Solución Factible. Es cualquier punto situado en la región factible.

Solución Básica. Es aquella que se encuentra en la intersección
de rectas o hiperplanos o en la intersección con los ejes
coordenados.

Solución Básica Factible. Es una solución básica que pertenece a

la región factible.

Solución Optima. Es una solución factible que maximiza o

minimiza la función objetivo según sea el caso

Solución Básica Factible Degenerada. Es una solución factible

básica en la que una o más variables básicas toman el valor de
cero.
 PUNTOS EXTREMOS (GRÁFICOS)

• Dada una región factible, un punto extremo no puede hallarse en

una línea entre dos otros puntos factibles (debe estar en un vértice)

Not Extreme
Feasible
Points
Region
Punto Extremo

• En un espacio n-dimensional, un punto extremo está localizado en

la intersección de n restricciones
 PUNTOS EXTREMOS Y ÓPTIMOS

Punto de Inicio

• Tenemos un problema de maximización, así que queremos ir tan

lejos como sea posible en la dirección del vector c (función objetivo)
• ¿Podemos determinar algo sobre la ubicación del punto óptimo?
 PUNTOS EXTREMOS Y ÓPTIMOS

• Si iniciamos en una línea, podemos movernos a lo largo de la línea

en la dirección de la función objetivo hasta llegar a un vértice
• De hecho, para cualquier vector c, el punto óptimo siempre será en
un vértice
 SOLUCIONES BÁSICAS FACTIBLES)

• En un espacio n-dimensional, una solución básica factible es

formada por la intersección de n ecuaciones.
• En 2-D:

Solución Básica Factible

Restricción 1

Restricción 2

• Pero, solo vimos que un punto extremo es también el punto en un

vértice. Entonces, una solución básica factible corresponde a un
Punto Extremo.
 ENLAZÁNDOLOS

• Acabamos de ver que una solución básica factible corresponde a

un punto extremo.
• Esto es muy importante porque para los problemas de LP , el punto
óptimo es siempre un punto extremo.
• Entonces, si podemos resolver para todos las BFS's (EP's),
podemos comprarlos para encontrar el óptimo.
Desafortunadamente, esto toma mucho tiempo.
INTRODUCCIÓN AL MÉTODO SIMPLEX

• El método simplex es el método más común para resolver

problemas de LP.
• Trabaja encontrando una BFS; determinando si ésta es óptima; y
si no lo es, se mueve a una "mejor" BFS hasta que la óptima es
alcanzada.
• De esta manera, no tenemos que calcular cada solución.
TEOREMA 1. El conjunto de todas las soluciones factibles al problema
de programación lineal es un conjunto convexo.

TEOREMA 2. La función objetivo alcanza su máximo en un punto

extremo del conjunto convexo, generado por el conjunto de soluciones
factibles al problema de programación lineal.

1. Existe un punto extremo del polígono (poliedro) convexo en el

cual la función objetivo tiene su máximo (mínimo).
2. Cada solución factible básica corresponde a un punto extremo
del polígono (poliedro) convexo.

Se tendrá que buscar que investigar únicamente los puntos extremos

del polígono (poliedro) convexo y buscar aquel punto que proporcione
el mayor (menor) valor para que la función objetivo y así obtendremos
la solución buscada.
 Restricción de mayor o igual que cero, límite mínimo

Ejemplo 2
Min (Z) = 2 X1 + 6 X2
Sujeto a:
12 X1 + 6 X2 ≥ 16
4 X1 + 12 X2 ≥ 12
X1 , X2 ≥ 0
Ejemplo 3
Min (Z) = 2 X1 + 3 X2
Sujeto a:
X1 + X2 ≤ 4
6 X1 + 2 X2 = 8
X1 + 5 X2 ≥ 4 B

X1 ≤3
X2 ≤ 3
A
X1 , X2 ≥ 0

La solución se encuentra en el segmento A y B, donde X1 = 8/7 y X2

= 4/7. la función objetivo toma el valor de 4.
Ejemplo 4
Max (Z) = X1 + X2
Sujeto a:
- 4 X1 + 2 X2 ≤ 2
2 X1 ≤4 (2/3,7/3)

2 X1 + 2 X2 ≤ 6 B
(2,1)
X1 , X2 ≥ 0
C

Se aprecia que la recta de la función objetivo no es ahora tangente

a un vértice del polígono factible, si no es coincidente con uno de
los lados del mismo.
¿Cuál es entonces la solución?
En este caso es posible definir cualquier punto sobre la recta BC y
hallar en consecuencia los valores X1 y X2.
X = 2 ; X = 1; Z = 3, otro resultado X = 2/3 , X = 7/3 ; Z = 3
Ejemplo 5
(6,5)
Max (Z) = 2 X1 + 2 X2
Sujeto a:
X1 - X2 ≥ 1
1/ 2 X1 + X2 ≤ 2
X1 , X2 ≥ 0

No tiene un valor máximo finito.

En problemas prácticos no puede presentarse este tipo de
solución
Ejemplo 6
Max (Z) = 3 X1 + 2 X2
Sujeto a:
X1 + X2 ≤ 1
2 X1 + 2 X2 ≥ 4
X1 , X2 ≥ 0

Ejemplo 7
Max (Z) = X1 + X2
Sujeto a:
3 X1 - X2 ≥ - 3
X1 + X2 ≤ 4
X1 , X2 ≥ 0
No se puede garantizar que todo problema tenga solución
factible.
 METODO SIMPLEX
1. bi ≤ 0
2. Restricciones ≤
3. Restricciones ≥
4. Restricciones =
5. Xj ≤ 0; xi = - Xi, donde Xi ≥ 0
6. Xi Sin Restricción de Signo (SRS)
+,-,0
X1 ; SRS
X1 = X1+ - X1-
X1 = A1 - D1
A1 > D1; X1 > 0; X1 = A1 - 0
A1 = D1; X1 = 0; X1 = 0 - 0
A1< D1; X1 < 0; X1 = 0 - D1
donde :
A 1, D 1 ≥ 0
7. Empate en el criterio en la variable que ingresa
se escoge arbitrariamente cualquiera.
Seleccionamos la variable que sale {θi menor}

8. Empate en el criterio en la variable que sale se

escoge arbitrariamente cualquiera.
Criterio de Optimalidad
Max Zj - Cj ≥ 0 ; Cj - Zj ≤ 0
Min Zj - Cj ≤ 0 ; Cj - Zj ≥ 0

9. Tipo de soluciones.
 ARTEFACTO A ARTEFACTO B DISPONIBILIDAD
(min/unid) (min/unid)
Maquinado 4 8 480
Armado 5 6 600
Montaje 12 6 540
Beneficio 100 120

¿Cuántos artefactos de A y B deben de producir para obtener el

máximo beneficio?
Xi: Cantidad de artefactos del tipo i a producirse al día.

FUNCIÓN OBJETIVO
• Max (Z) = 100 X1 + 120 X2
• Sujeto a:
4 X1 + 8 X2  480 → Area de Maquinado
5 X1 + 6 X2  600 → Area de Armado
12 X1 + 8 X2  540 → Area de Montaje
X1, X2  0
(0, 60)

(15/2, 225/4)

(45, 0)
 Solución
Iteración N° 1
Cj 100 120 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
0 S1 4 8 1 0 0 480 60
0 S2 5 6 0 1 0 600 100
0 S3 12 8 0 0 1 540 135/2
Cj -Zj 100 120 0 0 0 0
Iteración N° 2
Cj 100 120 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
120 X2 1/2 1 1/8 0 0 60 120
0 S2 2 0 -3/4 1 0 240 120
0 S3 8 0 -1 0 1 60 15/2
Cj -Zj 40 0 -15 0 0 7200
Iteración N° 3
Cj 100 120 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
120 X2 0 1 3/16 0 -1/16 225/4
0 S2 0 0 -1/2 1 -1/4 225
100 X1 1 0 -1/8 0 1/8 15/2
Cj -Zj 0 0 -10 0 -5 7500
Xi: Variable de decisión

FUNCIÓN OBJETIVO
• Max (Z) = 4 X1 + 3 X2
Sujeto a:
4 X1 + 2 X2  12
X1 + 3 X2  9
7 X1 + 2 X2  28
X1, X2  0
 Tipos de Solución
Iteraciones
Cj 4 3 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
0 S1 2 8 1 0 0 12 3
0 S2 3 6 0 1 0 9 9
0 S3 7 8 0 0 1 28 4
Cj -Zj 4 3 0 0 0 0
4 X1 1 1/2 1/4 0 0 3 6
0 S2 0 5/2 -1/4 1 0 6 12/5
0 S3 0 -3/2 -7/4 0 1 7 -
Cj -Zj 0 1 -1 0 0 24
4 X1 1 0 3/10 -1/5 0 9/5
3 X2 0 1 -1/10 2/5 0 12/5
0 S3 0 0 -19/10 3/5 1 53/5
Cj -Zj 0 0 -9/10 -2/5 0 72/5

Solución Optima Unica

Xi: Variable de decisión

FUNCIÓN OBJETIVO
• Max (Z) = 3 X1 + 5 X2
Sujeto a:
X1  4
2 X2  12
3 X1 + 2 X2  18
X1, X2  0
 Tipos de Solución
Iteraciones
Cj 3 5 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
0 S1 1 0 1 0 0 4 -
0 S2 0 2 0 1 0 12 6
0 S3 3 2 0 0 1 18 9
Cj - Zj 3 5 0 0 0 0
0 S1 1 0 1 0 0 4 4
5 X2 0 1 0 1/2 0 6 -
0 S3 3 0 0 -1 1 6 2
Cj - Zj 3 0 0 -5/2 0 30
0 S1 0 0 1 1/3 -1/3 2
5 X2 0 1 0 1/2 0 6
3 X1 1 0 0 -1/3 1/3 2
Cj - Zj 0 0 0 -3/2 -1 36

Solución Optima Unica

Xi: Variable de decisión

FUNCIÓN OBJETIVO
• Min (Z) = - X1 - 3 X2
Sujeto a:
X1 + X2  6
- X1 + 2 X2  8
X1, X2  0
 Solución
Iteración N° 1
Cj -1 -3 0 0
Ci XB X1 X2 S1 S2 bi θi
0 S1 1 1 1 0 6 6
0 S2 -1 2 0 1 8 4
Cj -Zj -1 -3 0 0 0

Iteración N° 2
Cj -1 -3 0 0
Ci XB X1 X2 S1 S2 bi θi
0 S1 3/2 0 1 -1/2 2 4/3
-3 X2 -1/2 1 0 1/2 4
Cj -Zj -5/2 0 0 3/2 -12
 Solución
Iteración N° 3

Cj -1 -3 0 0
Ci XB X1 X2 S1 S2 bi θi
-1 X1 1 0 2/3 -1/3 4/3
-3 X2 0 1 1/3 1/3 14/3
Cj -Zj 0 0 5/3 2/3 -46/3
Xi: Variable de decisión

FUNCIÓN OBJETIVO
• Max (Z) = 3 X1 + 2 X2
Sujeto a:
X1  4
2 X2  12
3 X1 + 2 X2  18
X1, X2  0
 Tipos de Solución
Iteraciones
Cj 3 2 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
0 S1 1 0 1 0 0 4 4
0 S2 0 2 0 1 0 12 -
0 S3 3 2 0 0 1 18 6
Cj - Zj 3 2 0 0 0 0
3 X1 1 0 1 0 0 4 -
0 S2 0 2 0 1 0 12 6
0 S3 0 2 -3 0 1 6 3
Cj - Zj 0 2 -3 0 0 12
3 X1 1 0 1 0 0 4
0 S2 0 0 3 1 -1 6
2 X2 0 1 -3/2 0 1/2 3
Cj - Zj 0 0 0 0 -1 18
 3 X1 1 0 0 -1/3 1/3 2
0 S1 0 0 1 1/3 -1/3 2
2 X2 0 1 0 1/2 0 6
Cj - Zj 0 0 0 0 -1 18

Solución Optima Altenativa

Xi: Variable de decisión

FUNCIÓN OBJETIVO
• Max (Z) = 10 X1 + 5 X2
Sujeto a:
-3 X1 + 4 X2  12
X1 - 2 X2  2
X1 + 2 X2  8
X1, X2  0
 Tipos de Solución
Iteraciones
Cj 10 5 0 0 0 -M
Ci XB X1 X2 S1 S2 S3 A3 bi θi
0 S1 -3 4 1 0 0 0 12 3
0 S2 1 -2 0 1 0 0 2 -
-M A3 1 2 0 0 -1 1 8 4
Cj - Zj 10+M 5 + 2M 0 0 -M 0 0
5 X2 -3/4 1 1/4 0 0 0 3 -
0 S2 -1/2 0 1/2 1 0 0 8 -
-M A3 5/2 0 -1/2 0 -1 1 2 4/5
Cj - Zj 55/4+5M/2 0 -5/4-M/2 0 -M 0 15

5 X2 0 1 1/10 0 -3/10 3/10 18/5

0 S2 0 0 4/10 1 -1/5 1/5 42/5
10 X1 1 0 -1/5 0 -2/5 2/5 4/5
Cj - Zj 0 0 3/2 0 11/2 -M-11/2 26

Solución No Acotada
Xi: Variable de decisión

FUNCIÓN OBJETIVO
• Min (Z) = X1 + X2
Sujeto a:
9 X1 + 3 X 2  9
3 X1 + 3 X2  15
3 X1 + 4 X2 = 12
X1, X2  0
 Tipos de Solución
Iteraciones
Cj 1 1 0 0 M M
Ci XB X1 X2 S1 S2 A1 A3 bi θi
M A1 9 3 -1 0 1 0 9 1
0 S2 3 3 0 1 0 0 15 5
M A3 3 4 0 0 0 1 12 4
Cj – Zj 1-12M 1-7M M 0 0 0
1 X1 1 1/3 -1/9 0 1/9 0 1 3
0 S2 0 2 1/3 1 -1/3 0 12 6
M A3 0 3 1/3 0 -1/3 1 9 3
Cj - Zj 0 2/3-3M 1/9-M/3 0 -1/9+4M/3 0

1 X1 1 0 -4/27 0 4/27 -1/9 0

0 S2 0 0 1/9 1 -1/9 -2/3 6
1 X2 0 1 1/9 0 -1/9 1/3 3
Cj - Zj 0 0 1/27 0 M-1/27 M-2/9 3

Solución Degenerada
Xi: Variable de decisión

FUNCIÓN OBJETIVO
• Min (Z) = X1 + X2
Sujeto a:
9 X1 + 3 X 2  9
X1 - 2 X2  15
X1 + 2 X2 = 12
X1, X2  0
 Tipos de Solución
Iteraciones
Cj 1 1 0 0 M M
Ci XB X1 X2 S1 S2 A1 A3 bi θi
M A1 9 3 -1 0 1 0 9 1
0 S2 1 -2 0 1 0 0 15 15
M A3 1 2 0 0 0 1 12 12
Cj – Zj 1-10M 1-5M M 0 0 0
1 X1 1 1/3 -1/9 0 1/9 0 1 3
0 S2 0 -7/3 1/9 1 -1/9 0 14 -
M A3 0 5/3 1/9 0 -1/9 1 11 33/5
Cj - Zj 0 2/3-5M/3 1/9-M/9 0 -1/9+M/9 0

1 X2 3 1 -1/3 0 1/3 0 3 -
0 S2 7 0 -2/3 1 2/3 0 21 -
M A3 -5 0 2/3 0 -2/3 1 6 9
Cj - Zj -2+5M 0 1/3-2M/3 0 5M/3-1/3 0 3
Cj XB X1 X2 S1 S2 A1 A3 bi

1 X2 1/2 1 0 0 0 1/2 6

0 S2 2 0 0 1 0 1 27
0 S1 -15/2 0 1 0 -1 3/2 9

Cj - Zj 1/2 0 0 0 M M-1/2 6
Xi: Variable de decisión

FUNCIÓN OBJETIVO
• Max (Z) = 3X1 + 5X2
Sujeto a:
X1  8
2 X2  12
3 X1 + 2 X2 = 18
X1, X2  0
GRAFICA
 Tipos de Solución
Iteraciones
Cj 3 5 0 0 0 -M
Ci XB X1 X2 S1 S2 S3 A1 Bi θi
-M A1 1 0 -1 0 0 1 8 8
0 S2 0 2 0 1 0 0 12 -
-M A3 3 2 0 0 1 0 18 6
Cj – Zj 3+M 5 + 2M -M 0 0 0
-M A1 0 -2/3 -1 0 -1/3 0 2
0 S2 0 2 0 1 0 0 12
3 X1 1 2/3 0 0 1/3 1 6
Cj - Zj 0 5-2M/3 -M 0 -M/3-1 0

Solución No Factible
Xi: Variable de decisión

FUNCIÓN OBJETIVO
• Max (Z) = 460X1 + 200X2
Sujeto a:
18 X1 + 3 X2 ≤ 800
9 X1 + 4 X2  600
X1 ≥ 80
X1, X2  0
 Tipos de Solución
Iteraciones
Cj 460 200 0 0 0 -M
Ci XB X1 X2 S1 S2 S3 A3 bi θi
0 S1 18 3 1 0 0 0 800 400/9
0 S2 9 4 0 1 0 0 600 200/3
-M A3 1 0 0 0 -1 1 80 80
Cj – Zj 460+M 200 0 0 -M 0
460 X1 1 1/6 1/18 0 0 0 400/9
0 S2 0 5/2 -1/2 1 0 0 200
-M A3 0 -1/6 -1/18 0 -1 1 320/9
Cj – Zj 0 370/3-M/6 230/9-M/18 0 -M 0

Solución No Factible
Xi: Variable de decisión

FUNCIÓN OBJETIVO
• Max (Z) = X1 + X2
Sujeto a:
2 X1 + 2 X 2 ≤ 8
6 X1 + 2 X2  18
2 X1 + 4 X2 ≤ 16
X1, X2  0
 Tipos de Solución
Iteraciones
Cj 1 1 0 0 0
Ci XB X1 X2 S1 S2 S3 bi θi
0 S1 2 2 1 0 0 8 4
0 S2 6 2 0 1 0 18 3
0 S3 2 4 0 0 1 16 8
Cj - Zj 1 1 0 0 0 0
0 S1 0 4/3 1 -1/3 0 2 3/2
1 X1 1 1/3 0 1/6 0 3 6
0 S3 0 10/3 0 -1/3 1 10 3
Cj - Zj 0 2/3 0 -1/6 0 3
1 X2 0 0 3/4 -1/4 0 3/2
1 X1 1 0 -1/4 1/4 0 5/2
0 S3 0 1 -5/2 -1/2 1 5
Cj - Zj 0 0 -1/2 0 0 4
 1 X2 1 1 1/2 0 0 4
0 S2 4 0 -1 1 0 10
0 S3 2 0 -3 0 1 10
Cj - Zj 0 0 -1/2 0 0 4

Solución Optima Altenativa

Max (Z) = 4 X1 + 8 X2

Sujeto a:

6 X1 + 8 X2 ≤ 24
20 X1 = 10X2
8 X1 - 4 X2 ≤ 16
X 1, X2  0
 Tipos de Solución
Iteraciones
Cj 4 8 0 -M 0
Ci XB X1 X2 S1 A2 S3 bi θi
0 S1 6 8 1 0 0 24 4
-M A2 20 -10 0 1 0 0 0
0 S3 8 -4 0 0 1 16 2
Cj - Zj 4+20M 8 -10M 0 0 0
0 S1 0 11 1 -3/10 0 24 24/11
1 X1 1 -1/2 0 1/20 0 0 -
0 S3 0 0 0 -2/5 1 16 -
Cj - Zj 0 10 0 -1/6 0
1 X2 0 1 1/11 -3/110 0 24/11
1 X1 1 0 1/22 2/55 0 12/11
0 S3 0 0 0 -2/5 1 16
Cj - Zj 0 0 -10/11 -M-4/55 0 240/11
Hoy en día, la toma de decisiones abarca una gran cantidad
de problemas reales cada más complejos y especializados,
que necesariamente requieren del uso de metodologías para
la formulación matemática de estos problemas y,
conjuntamente, de métodos y herramientas de resolución,
como los que provee la Investigación de Operaciones.
 FORMULACION DE UN PROBLEMA
PROGRAMACIÓN LINEAL
Función Objetivo: Max o Min (Z) = C X

Sujeto a :
AXB
Xi  0 ; i = 1, 2,...., n

La Programación Lineal es una herramienta para resolver problemas

de optimización que se caracterizan por tener como función objetivo y
restricciones combinaciones lineales de las variables de decisión.

Conceptos Básicos:
• Variables de Decisión
• Función Objetivo
• Restricciones
• Restricciones de Signo
Consideremos los siguientes ejemplos para describir los conceptos
básicos presentes en todo problema de programación lineal (PPL)
 CONSTRUCCIÓN DE MODELOS DE PROGRAMACION
LINEAL
Ejemplo N° 1
La Compañía PARGOLF es un pequeño fabricante de equipo y suministros
para golf. El distribuidor de PARGOLF cree que existe un mercado tanto
para una bolsa de golf de precio moderado, denominada modelo estándar,
como para una bolsa de precio elevado, denominada modelo de lujo. El
distribuidor está tan confiado en el que, si PARGOLF puede hacer las
bolsas a un precio competitivo, el distribuidor comprará todas las bolsas
que PARGOLF pueda fabricar durante los siguientes tres meses. Un
análisis cuidadoso de los requerimientos de tiempo de producción para
las cuatro operaciones de manufactura y la estimación hecha por el
departamento de contabilidad de la contribución a la ganancia por bolsa.

Tiempo de producción (horas/bolsa)

Corte y Inspección Ganancia
Producto teñido Costura Terminado y empaque por bolsa

Estándar 7/10 1/2 1 1/10 S/. 10

De lujo 1 5/6 2/3 1/4 S/. 9

El director de manufactura estima que dispondrán de 630 horas de
tiempo de corte y teñido, 600 horas de tiempo de costura, 708 horas de
tiempo de terminado y 135 horas de tiempo de inspección y empaque
para la producción de bolsas de golf durante los siguientes tres meses.

a) Si la compañía desea maximizar la contribución a la ganancia

total, ¿Cuántas bolsas de cada modelo debería fabricar?
b) ¿Cuántas horas de tiempo de producción se programaran para
cada operación?
c) ¿Cuántas horas de tiempo de ocio se tendrán en cada operación?
Formulación:

Variable de decisión:

Xi = Número de bolsas de modelo i a fabricar por trimestre

 i = 1, 2

Objetivo:

Maximizar: Ganancia/trimestre

Restricciones: Corte y teñido

Corte
Tiempo disponible por trimestre
Acabado
Condiciones técnicas. Inspección y empaque

X1, X2 > 0
Modelo Matemático de Programación Lineal:

Máx: Ganancia
Max. (Z) = 10X1 + 9X2

S/. = S/. Bolsa

Trimestre Bolsa Trimestre

Sujeto a:
Hora Bolsas Horas
=
Bolsa Trimestre Trimestre

7/10X1 + X2 < 630 Corte y teñido

1/2X1 + 5/6X2 < 600 Costura
X1 + 2/3X2 < 708 Acabado
1/10X1 + 1/4X2 < 135 Inspección y empaque
X1, X2 > 0
 Ejemplo N° 2: El problema de la industria
de juguetes “Galaxia”.

• Galaxia produce dos tipos de juguetes:

* Space Ray
* Zapper

• Los recursos están limitados a:

* 1200 libras de plástico especial.
* 40 horas de producción semanalmente.
• Requerimientos de Marketing.

* La producción total no puede exceder de 800 docenas.

* El número de docenas de Space Rays no puede exceder al
número de docenas de Zappers por más de 450.

• Requerimientos Tecnológicos.

* Space Rays requiere 2 libras de plástico y 3 minutos de

producción por docena.
* Zappers requiere 1 libra de plástico y 4 minutos de producción

por docena.
• Plan común de producción para:

* Fabricar la mayor cantidad del producto que deje mejores

ganancias, el cual corresponde a Space Ray (S/. 8 de utilidad

por docena).
* Usar la menor cantidad de recursos para producir Zappers,
porque estos dejan una menor utilidad (S/. 5 de utilidad por
docena).
 Solución
• Variables de decisión

* X1 = Cantidad producida de Space Rays (en docenas por

semana).
* X2 = Cantidad producida de Zappers (en docenas por
semana).

• Función objetivo

* Maximizar la ganancia semanal.

• Modelo de Programación Lineal

Max (Z) = 8X1 + 5X2 (ganancia semanal)

Sujeto a:
2X1 + 1X2  1200 (Cantidad de plástico)
3X1 + 4X2  2400 (Tiempo de producción)
X1 + X2  800 (Limite producción total)
X1 - X2  450 (Producción en exceso)
Xj  0, j = 1, 2. (Resultados positivos)

• El plan común de producción consiste en:

Space Rays = 550 docenas

Zappers = 100 docenas

Utilidad = S/. 4900 por semana

 EJEMPLO N° 3

Una firma industrial elabora dos productos, en los cuales entran

cuatro componentes en cada uno. Hay una determinada
disponibilidad de cada componente y un beneficio por cada
producto. Se desea hallar la cantidad de cada articulo que debe
fabricarse con el fin de maximizar los beneficios.
El siguiente cuadro resume los coeficientes de transformación o
sea la cantidad de cada componente que entra en cada producto.

Producto P1 P2 Disponibilidad
Componente (kilogramos)
A 1 3 15,000
B 2 1 10,000
C 2 2 12,000
D 1 1 10,000
Beneficios
4 3
S/./unidad
X1 = Nº de unidades de producto P1
X2 = Nº de unidades de producto P2

Entonces el programa lineal correspondiente es:

Max (Z) = 4X1 + 3X2
Sujeto a :
1X1 + 3X2 ≤ 15,000
2X1 + 1X2 ≤ 10,000
2X1 + 2X2 ≤ 12,000
1X1 + 1X2 ≤ 10,000
X1 , X 2 ≥ 0
 EJEMPLO Nº 4

En una fábrica de cerveza se producen dos tipos: rubia y negra. Su

precio de venta es de S/. 0.5 / litro y S/. 0.3 / litro, respectivamente.
Sus necesidades de mano de obra son de 3 y 5 empleados, y de
5,000 y 2,000 soles de materias primas por cada 10,000 litro.

La empresa dispone semanalmente de 15 empleados y 10,000 soles

para materias primas, y desea maximizar su beneficio. ¿Cuántos
litros debe producir?
 FORMULACIÓN

Max (Z) = 5,000X1 + 3,000X 2

S. A.
3X1 + 5X2  15
5,000X1 + 2,000X 2  10,000
X1, X2  0
 Ejemplo N° 5
Una mueblería produce mesas y sillas de madera. Cada mesa es
vendida en $27.000 y se requiere $10.000 en materiales para su
construcción, además, el costo unitario por mano de obra es de
$14.000. En el caso de las sillas, el precio de venta es de $21.000 y
los costos de materiales y mano de obra son $9.000 y $10.000
respectivamente.

La fabricación de cada producto requiere de dos labores: carpintería

y terminaciones. Una mesa requiere de 1 hora de carpintería y 2 de
terminaciones, mientras que la silla requiere de 1 hora en cada labor.
Cada semana, la mueblería puede obtener todos los materiales que
desee, sin embargo, se pueden dedicar hasta 100 horas a las
terminaciones y hasta 80 horas a la carpintería. La demanda por
mesas no está limitada, mientras que la demanda por sillas es de 40
unidades.

Formule un modelo matemático que permita maximizar las utilidades

de la mueblería.
 Formulación
Variables de decisión:
Se debe comenzar definiendo las variables de decisión relevantes. En
un PPL las variables de decisión deben ser capaces de describir
completamente las decisiones que puedan ser tomadas y todas las
variantes que existan.

Antes de definir las variables de decisión es importante definir las

unidades involucradas en el problema.

En este caso, se habla de unidades de sillas y mesas, de horas de

trabajo por unidad y de demanda semanal. De acuerdo a ello, una
buena opción para definir las variables de decisión consiste en
asociar las variables al número de unidades de sillas y mesas a
producir por semana. Por lo tanto, podemos definir:

X1 = Número de mesas producidas por semana.

X2 = Número de sillas producidas por semana.
Función Objetivo:

En un PPL, se debe tomar la decisión de maximizar (usualmente las

utilidades) o de minimizar (usualmente los costos) cierta función de
las variables de decisión.

La función que se va a optimizar se llama Función Objetivo y en ella

no aparece ningún término independiente o constante. Los valores
de las variables de decisión son independientes de cualquier
constante.

En el ejemplo, los costos e ingresos no dependen del valor de X 1 o

X2 por lo tanto basta concentrarse en maximizar la diferencia entre:

Ingresos Semanales – Costos de Materiales – Costos por mano de obra

Luego se deben expresar los términos anteriores en función de las
variables de decisión X1 y X2.
Por lo que la función objetivo queda (expresada en miles de $):

(27X1 + 21X2) – (10X1 + 9X2) – (14X1 + 10X2) = 3X1 + 2X2

Así, el objetivo de la mueblería es escoger los valores X1 y X2 tal que se

maximice 3X1 + 2X2

Denotando por Z el valor de la Función Objetivo para cualquier

Problema de Programación Lineal, la función de la mueblería es:

Max Z = 3X1 + 2X2

El coeficiente que acompaña a cada variable en la Función Objetivo se

denomina coeficiente en la función objetivo de la variable y refleja el
aporte unitario de dicha variable.
Restricciones:

En las medidas que las variables crecen, la Función Objetivo

aumenta su valor. Por lo tanto si se pudiera escoger arbitrariamente
el valor de la variables, la mueblería podría hacer crecer el valor de
sus utilidades en forma infinita. En la práctica esto no es posible y en
el ejemplo el valor que toman las variables está limitado por las
siguientes 3 restricciones:

• Máximo 100 horas semanales para terminaciones.

• Máximo 80 horas semanales para carpintería.
• Producción máxima de 40 sillas semanales.

Luego, el próximo paso consiste en formular matemáticamente las

restricciones anteriores en función de las variables de decisión.
Para formular la primera restricción en función de las variables X 1 y
X2 observamos que:

Hrs. terminaciones x mesa + hrs. terminaciones x silla  hrs.

disponibles para terminación

Por lo que la restricción queda:

2X1 + X2  100

Es importante notar que todos los valores en la expresión anterior

son por semana, ya que las variables de decisión se han escogido
con esa referencia.
 Análogamente la segunda restricción queda:

X1 + X2  80

Finalmente, la tercera restricción sólo limita el valor de la variable X 2

X2  40

Restricciones de Signo:

Para completar la formulación del modelo es importante definir si

existe alguna restricción de signo para cada variable de decisión.

Si una variable de decisión Xi debe cumplir condiciones de NO

NEGATIVIDAD, debemos agregar la siguiente restricción:

Xi  0
Si la variable de decisión Xi puede asumir valores positivos o
negativos se dice que Xi no tiene restricción de signo (SRS).

En el ejemplo ambas variables de decisión se refieren a cantidades

a producir, por lo tanto son no negativas. Sin embargo, en otros
ejemplos las variables pueden ser SRS, por ejemplo en el caso de
que Xi se refiere al saldo de alguna cuenta.

Combinando todas las expresiones anteriores, es posible

completar el modelo matemático para este problema de
optimización, quedando de la siguiente forma:
Definición de variables:

X1: número de mesas producidas por semana.

X2: número de sillas producidas por semana.

Función Objetivo:

Max Z = 3X1 + 2X2

Sujeto a:

2X1 + X2  100 Horas disponibles para terminaciones por semana

X1 + X2  80 Horas disponibles para carpintería por semana

X2  40 Producción máxima de sillas por semana

Xj  0 j=1y2 No negatividad
 MODELO GENERAL DE PROGRAMACIÓN LINEAL

Optimizar Coeficientes objetivo

Variables de decisión

Max(Z) = C1 X 1 + C 2 X 2 +...... + Cn Xn
Coeficientes recurso
Sujeto a: Coeficientes tecnológicos

a X +a X + ..... + a X ( ≤ , = , ≥ ) b
1
11 1 12 2 1n n

a X +a X + ..... + a X n ( ≤ , = , ≥ ) b2
21 1 22 2 2n
. . . . .
. . . . .
. . . . .
a X +a X + ..... + a X (≤ , = , ≥ )b
m1 1 m2 2 mn n m

X1,2,.....n > 0 Condiciones técnicas o

No negatividad
• Donde el vector c también conocido como el vector costos,
viene dado por:

C =  c1 c 2 ... c n-1 c n 

• El vector de lado derecho o b, viene dado por:

 b1 
 
 b 2 
 . 
b 
 . 
b 

 b 
m-1

 m 
• Este es un vector columna, que representa los recursos de
las m actividades. Es por lo tanto el elemento de la mano
derecha de cada una de las m ecuaciones.
• La matriz A, representa los coeficiente tecnológicos; es la
matriz para el sistema de ecuaciones Ax = b:

 a11 a12 ... a1n 

 
 a21 a2 2 ... a2n 
A
 . . ... . 
 
 am,1 am,2 ... am,n 
• El sistema de ecuaciones o el modelo de PL, queda
representado por:

Max (Z) = C X
Sujeto a:
A X = bi
A X ≤ bi
A X ≥ bi
X≥0
 EL MODELO DE P.L.

Z: función objetivo
C (c1,...,cn): vector de coeficientes de la f. o.
X (x1,...,xn): vector de variables de decisión
A (...,aij,...): matriz de coeficientes técnicos
b (b1,...,bm): vector de demandas

Matricialmente,

Optimización Max o Min = CX

S.A.
AX b
x0 Forma canónica
 Problema N° 1
X2 X4

X1 Día 1 Día 2 Día 3

(40) (70) (60)

X3

Variables de Decisión
X1 = Cantidad de Manteles comprados (sólo se puede comprar el
primer día).
X2 = Cantidad de Manteles mandados a lavar en servicio rápido el
primer día.
X3 = Cantidad de Manteles mandados a lavar en servicio normal el
primer día.
X4 = Cantidad de Manteles mandados a lavar en servicio rápido el
segundo día.
Restricciones.
a) Satisfacción de la necesidad de manteles al primer día X1 ≥ 40
b) Satisfacción de la necesidad de manteles al segundo día.
(X1 − 40) + X2 ≥ 60 ↔ X1 + X2 ≥ 100
c) Satisfacción de la necesidad de manteles al tercer día.
(X1 − 40) + X2 − 60 + X3 + X4 ≥ 70 ↔ X1 + X2 + X3 + X4 ≥ 170
d) El número de manteles mandados a lavar el primer día, puede a lo
mas ser igual al número de manteles usados ese día.
X2 + X3 ≥ 40
e) El número de manteles mandados a lavar hasta el segundo día,
puede a lo mas ser igual al número de manteles usados hasta
ese día.
X2 + X3 + X4 ≥ 40 + 60 ↔ X2 + X3 + X4 ≥ 100
f ) No negatividad.
X1, X2, X3, X4 ≥ 0

Función Objetivo
Min (Z) = 20X1 + 15X2 + 8X3 + 15X4
 Problema N° 2
Variables de Decisión
X1 = numero de libras de carne molida de res empleadas en cada libra
de albóndigas.
X2 = numero de libras de carne molida de cerdo empleadas en cada
libra de albóndigas.
Restricciones
Cada libra de albóndigas tendrá 0.20 X1, libras de grasa provenientes
de la carne de res y 0.32 X2 libras de grasa de la carne de cerdo. El
contenido total de grasa de una libra de albóndigas no debe ser
mayor de 0.25 libras. Entonces:
0.20X1 + 0.32X2 ≤ 0.25
El número de libras de carne de res y de cerdo empleadas en cada
libra de albóndigas debe sumar 1; entonces:
X1 + X 2 = 1
Finalmente, la tienda no puede usar cantidades negativas de ninguna
de las carnes, así que hay dos restricciones de no negatividad: X1≥ 0
y X2 ≥ 0.
Función Objetivo
Min (Z) = 80X1 + 60X2
 Problema N° 3

• Variables de decisión
X1: Unidades de A producidas en total
X2: Unidades de B producidas en total
X3: Unidades de C producidas en total
X4: Unidades de A vendidas
X5: Unidades de B vendidas

• Función Objetivo
Max (Z) = 700 X4 + 3,500 X5 + 7,000 X3

• Restricciones
Sujeto a:
X1 + 2X2 + 3X3 ≥ 40
X1 = X4 + 2X2
X2 = X 5 + X 3
X1, X2, X3, X4, X5 ≥ 0
 Problema N° 5
Un fabricante cuyo negocio es mezclar aguardiente, compra tres grados A, B, y C. Los
combina de acuerdo a las recetas que especifican los porcentajes máximo y mínimo
de los grados A y C en cada mezcla. Estos porcentajes se dan en la tabla N° 1.
TABLA N° 1 ESPECIFICACIONES DE MEZCLAS
MEZCLA ESPECIFICACION PRECIO POR BOTELLA
No menos de 60% de A S/. 6.80
Súper Fuerte No mas de 20% de C
No más de 60% de C S/. 5.70
Fuerte No menos de 15% de A
Menos Fuerte No más de 50% de C S/. 4.50

La provisión de los tres grados de aguardientes básicos, junto con sus costos se presente
en la tabla N° 2.
TABLA N° 2 DISPONIBILIDAD Y COSTOS DE AGUARDIENTE
MAXIMA CANTIDAD COSTO POR BOTELLA
AGUARDIENTE DISPONIBLE
BOTELLAS POR DIA
A 2000 S/. 7.00
B 2500 S/. 5.00
C 1200 S/. 4.00

Indique cómo se obtiene la primera matriz en un modelo de programación lineal de una

política de producción que haga máxima la ganancia.
 Solución

X11 : Cantidad de A usada para el super fuerte

X21 : Cantidad de B usada para el super fuerte
X31 : Cantidad de C usada para el super fuerte
X12 : Cantidad de A usada para el fuerte
X22 : Cantidad de B usada para el fuerte
X32 : Cantidad de C usada para el fuerte

Max (Z) = 6.80 (X11 + X21 + X31) + 5.7 (X12 + X22 + X32) – [ 7(X11 + X12) +
5(X21 + X22) + 4(X31 + X32)]
Sujeto a:
X11 + X12 ≤ 2,000
X21 + X22 ≤ 2,500 Disponibilidad
X31 + X32 ≤ 1,200

X11 ≥ 0.60 (X11 + X21 + X31)

X31 ≤ 0.20 (X11 + X21 + X31)
X32 ≤ 0.60 (X12 + X22 + X32)
X12 ≥ 0.15 (X12 + X22 + X32)
Xij ≥ 0 : i = 1, 2, 3 ; j = 1, 2
 PROBLEMA
La empresa Talleres de Carpintería fabrica tres estilos diferentes de
mesas. A, B y C. Cada modelo de mesa requiere de una cierta cantidad
de tiempo para el corte de las piezas, su montaje y el correspondiente
proceso de pintura. La empresa puede vender todas las unidades que
fabrica. Es más, el modelo B también se puede vender sin pintar. Los
datos técnico - económicos se muestran a continuación.

CORTE MONTAJE PINTURA GANANCIA

MODELO
(horas) (horas) (horas) Unitaria (S/.)
Modelo 1: Mesa A pintada 1 2 4 35
Modelo 2: Mesa B pintada 2 4 4 40
Modelo 3: Mesa B sin pintar 2 4 0 20
Modelo 4: Mesa C pintada 3 7 5 50
Capacidad (horas/mes) 200 300 240
 SOLUCIÓN
El siguiente modelo de programación lineal permite obtener el plan de
producción mensual óptimo.

Xi = Número de mesas del tipo i a producirse al mes, donde i = 1, 2, 3, 4.

Función Objetivo:
Max (Z) = 35 X1 + 40 X2 + 20 X3 + 50 X4

Sujeto a:
X1 + 2 X2 + 2 X3 + 3 X4 ≤ 200 Corte
2 X1 + 4 X2 + 4 X3 + 7 X4 ≤ 300 Montaje
4 X1 + 4 X2 + 0 X3 + 5 X4 ≤ 240 Pintura
X1, X 2, X3, X4 ≥ 0
Se pide:
1. Definir el plan de producción óptimo y el uso asociado de los recursos.
2. Dado el éxito de los modelos de mesa sin pintar, la empresa está
valorando la posibilidad de fabricar el modelo C sin pintar (que se
diferencian de las mesas pintadas solo en el proceso de pintado). Estima
que la contribución unitaria al beneficio de ese modelo sería de 42 soles
por unidad. Justificar el interés de la fabricación y venta de mesas C sin
pintar y, en caso de haber un nuevo plan óptimo de producción, describir
cuál sería.
3. Realizar un análisis de sensibilidad para la capacidad del taller de
montaje.
4. Un estudio preliminar de métodos y tiempos permite afirmar que el tiempo
de pintado de las mesas B podría reducirse. En particular, atendiendo a
diferentes mejoras se podría reducir el valor pero nunca podría bajar de 2
horas. Se pide indicar cuál es el beneficio obtenido en función de las
horas de reducción λ, que puede tomar cualquier valore entre 0 y 2.
 PROBLEMA
Suponga que una persona dispone de S/. 6.000 y desea invertirlos. Al
enterarse de esta noticia, dos amigos distintos le ofrecen la oportunidad
de participar como socio en sus negocios. En ambos casos, la inversión
significa dedicar un poco de tiempo el verano siguiente, al igual que
invertir efectivo. Con el primer amigo, al convertirse en socio completo,
tendría que invertir S/. 5.000 y 400 horas, con una ganancia estimada
(ignorando el valor del tiempo) de S/. 4.500. Las cifras correspondientes
a la proposición del segundo amigo son S/. 4.000 y 500 horas, con una
ganancia estimada de S/. 4500. Sin embargo, ambos amigos son
flexibles y le permitirán entrar al negocio con cualquier fracción de la
sociedad. La participación de las utilidades sería proporcional a esa
fracción. Como de todas maneras esta persona está buscando un
trabajo interesante para el verano (600 horas a lo sumo), ha decidido
participar en una o ambas sociedades, con la combinación que
maximice la ganancia total estimada.
Formule un modelo de programación lineal para este problema.
X
• 1: Cantidad de dinero invertido en el primer negocio en el verano
X2: Cantidad de dinero invertido en el segundo negocio en el verano

Función Objetivo:
Max (Z) = +
Sujeto a:
 Problema N° 6

Una compañía fabrica dos clases de cinturones de cuero. El cinturón

A es de alta calidad, y el cinturón B es de baja calidad. La ganancia
respectiva por cinturón es de S/. 0.40 y S/. 0.30. Cada cinturón de tipo
A requiere el doble de tiempo que el que usa el de tipo B, y si todos
los cinturones fueran de tipo B, la compañía podría fabricar 1000 día,
el abastecimiento de cuero es suficiente únicamente para 800
cinturones diarios (A y B combinados) el cinturón A requiere una
hebilla elegante, de las que solamente se dispone 400 diarias. Se
tiene únicamente 700 hebillas al día para el cinturón B. Establezca las
ecuaciones de programación lineal para el problema.

Tipo de cinturón Ganancia Disponibilidad

S/. / Cin hebillas/día
A 0.4 400
B 0.3 700
Xi: Número de cinturones producidos por día del tipo i; donde i
=
A, B
tA = 2tB

FUNCIÓN OBJETIVO: Max (Z) = 0.4 XA + 0.3 XB

Sujeto a:
2 XA + XB ≤ 1,000
XA + XB ≤ 800
XA ≤ 400
XB ≤ 700
XA, XB ≥ 0
 Problema N° 5
Un fabricante cuyo negocio es mezclar aguardiente, compra tres grados A, B, y C. Los
combina de acuerdo a las recetas que especifican los porcentajes máximo y mínimo
de los grados A y C en cada mezcla. Estos porcentajes se dan en la tabla N° 1.
TABLA N° 1 ESPECIFICACIONES DE MEZCLAS
MEZCLA ESPECIFICACION PRECIO POR BOTELLA
No menos de 60% de A S/. 6.80
Súper Fuerte No mas de 20% de C
No más de 60% de C S/. 5.70
Fuerte No menos de 15% de A
Menos Fuerte No más de 50% de C S/. 4.50

La provisión de los tres grados de aguardientes básicos, junto con sus costos se presente
en la tabla N° 2.
TABLA N° 2 DISPONIBILIDAD Y COSTOS DE AGUARDIENTE
MAXIMA CANTIDAD COSTO POR BOTELLA
AGUARDIENTE DISPONIBLE
BOTELLAS POR DIA
A 2000 S/. 7.00
B 2500 S/. 5.00
C 1200 S/. 4.00

Indique cómo se obtiene la primera matriz en un modelo de programación lineal de una

política de producción que haga máxima la ganancia.
 Solución

X11 : Cantidad de A usada para el super fuerte

X21 : Cantidad de B usada para el super fuerte
X31 : Cantidad de C usada para el super fuerte
X12 : Cantidad de A usada para el fuerte
X22 : Cantidad de B usada para el fuerte
X32 : Cantidad de C usada para el fuerte

Max (Z) = 6.80 (X11 + X21 + X31) + 5.7 (X12 + X22 + X32) – [ 7(X11 + X12) +
5(X21 + X22) + 4(X31 + X32)]
Sujeto a:
X11 + X12 ≤ 2,000
X21 + X22 ≤ 2,500 Disponibilidad
X31 + X32 ≤ 1,200

X11 ≥ 0.60 (X11 + X21 + X31)

X31 ≤ 0.20 (X11 + X21 + X31)
X32 ≤ 0.60 (X12 + X22 + X32)
X12 ≥ 0.15 (X12 + X22 + X32)
Xij ≥ 0 : i = 1, 2, 3 ; j = 1, 2
 Problema N° 7

Mineral N° 1

Mineral N° 2

X1 = toneladas de mineral 1 en el molde

X2 = toneladas de mineral 2 en el molde
Mineral 1 Mineral 2
Hierro forjado 60% 13%
Plomo 10% 3%
Min (Z) = 260 X1 + 80 X2
Sujeto a:
0.60 X1 + 0.13 X2 ≥ 0.20 (X1 + X2)
0.10 X1 + 0.03 X2 ≥ 0.05 (X1 + X2)
X1, X 2, ≥ 0
 Problema N° 8

Una industria de muebles requiere de 350 barras de 2x4x20

cm. y de 200 barras de 2x3x20 cm., si dicha empresa dispone
de barras cuyas dimensiones son 7x5x20 cm., cual debe ser
el programa que debe seguir para minimizar desperdicios
sabiendo que el máximo debe ser de 140 cm3.
 Solución

X3 X2
3 3 1 3 4 3 4

2 2 2

2 2
3
1 1
2 2 2 1

2 2 2 1 2 2 2 1

20
4 3

2
1
3 3
5

X1
7
140 cm3 = 7 cm2
20 cm
350 2 x 4 x 20
200 2 x 3 x 20
Xi = cantidad de barras a obtenerse en la modalidad de corte i
Min (Z) = 100 X1 + 60 X2 + 140 X3
X1 X2 X3
2 x 4 x 20 0 1 2
2 x 3 x 20 5 4 2
Sujeto a:
X2 + 2 X3 ≥ 350
5 X1 + 4 X2 + 2 X3 ≥ 200
X1 , X2, X3 ≥ 0
 Problema N° 9
Un fabricante de láminas metálicas recibe un pedido para producir
2000 láminas de tamaño 2’ x 4’ y 1000 láminas de tamaño 4’ x 7’. Se
dispone de dos láminas estándar de tamaño 10’ x 3000’ y 11’ x 2000’.
El personal del departamento de ingeniería decide que los tres
siguientes patrones de corte son adecuados para satisfacer el
pedido y minimizar el desperdicio. Formule el problema como un
modelo de programación lineal.
Patron N° 1 Patron N° 2

4' 4'

2' 2' 7'

2' 7

Patron N° 3

4'

2' 2' 2' 2' 2'

 Solución

4 Láminas 2 x 4 2,000 10’ x 3,000’

2 4x7 1,000 11’ x 2,000’

Xij = Cantidad de patrones i utilizado para cortar

1 3
750 para
7
cortar
en la lámina j
1

Sujeto a:
4
2’ x 4’ 1 X11 + 5 X31 + 2 X22 + 5 X32 ≥ 2,000
2
4’ x 7’ 1 X11 + 0 X31 + 1 X22 + 0 X32 ≥ 1,000
2
X11 + X31 ≥ 3,000/4
2 3 500 para X22 + X32 ≥ 2,000/4 X11,
cortar
7 X31, X22, X32 ≥ 0

Min (Z) = 4 X11 + 0 X31 + 0 X22 + 4 X32

 Problema N° 10

• El Real Hotel opera los 7 días a la semana. Las mucamas son

contratadas para trabajar seis horas diarias. El contrato
colectivo especifica que cada mucama debe trabajar 5 días
consecutivos y descansar 2 días. Todas las mucamas reciben el
mismo sueldo semanal. El Real hotel requiere como mínimo las
horas de servicio.

Lunes 150, Martes 200, Miércoles 400, Jueves 300, Viernes 700,
Sábado 800 y Domingo 300. El administrador desea encontrar
un plan de programación de empleos que satisfaga estos
requerimientos y a un costo mínimo.

Formule este problema como un modelo de programación

lineal.
 Solución

L Ma Mi J V S D L Ma Mi J V S D L Ma Mi J
XL
XMa
XMi
XJ
XV
XS
XD
XL
XMa
XMi
XJ
XV
XS
XV
 Continuación…..

Xi = Número de mucamas que empiezan a trabajar el día i

durante
cinco dias consecutivos

XJ + XV + XS + XD + XL ≥ 150 / 6
XV + XS + XD + XL + XMa ≥ 200 / 6
XS + XD + XL + XMa+ XMi ≥ 400 / 6
XD + XL + XMa+ XMi+ XJ ≥ 300 / 6
XL + XMa+ XMi+ XJ + XV ≥ 700 / 6
XMa+ XMi+ XJ + XV +XS ≥ 800 / 6
XMi+ XJ + XV +XS + XD ≥ 300 / 6
XL , XMa, XMi, XJ , XV , XS , XD ≥ 0

Min (Z) = XL + XMa+ XMi+ XJ + XV + XS + XD

 Problema

• El hospital ESSALUD ha decidido ampliar su servicio de urgencias (abierto las 24

horas) con la consiguiente necesidad de nuevo personal de enfermería. La gerencia
del hospital ha estimado las necesidades mínimas de personal por tramos horarios
para poder cubrir las urgencias que se presenten. Se definieron 6 tramos de 4 horas.
La necesidad mínima de personal en cada tramo se indica en el cuadro mostrado.
Por otro lado, el departamento de recursos humanos ha informado a gerencia que los
contratos laborales han de ser de ocho horas seguidas, según el Convenio firmado
con los sindicatos, independientemente de los horarios de entrada y salida del
personal.
El problema es encontrar el número mínimo de personal necesario para cubrir la

demanda.
Cuadro: Necesidades de personal por tramos horarios
Tramos Horarios
J 1 2 3 4 5 6
0:00 - 4:00 4:00 – 8:00 8:00 – 12:00 12:00-16:00 16:00-20:00 20:00-24:00
Personal
9 5 3 7 5 6
Nj
 Solución
Cuadro: Necesidades de personal
Tramos Horarios
Hora 1 2 3 4 5 6
0:00 - 4:00 4:00 – 8:00 8:00 – 12:00 12:00-16:00 16:00-20:00 20:00-24:00
0:00 X1 X1
4:00 X2 X2
8:00 X3 X3
12:00 X4 X4
16:00 X5 X5
20:00 X6 X6
Personal
9 5 3 7 5 6
Nj

Min (Z) = X1 + X2 + X3 + X4 + X5 + X6
Sujeto a: 
X1 + X 2 ≥5
X2 + X 3 ≥3
X3 + X 4 ≥7
X4 + X 5 ≥5
X5 + X 6 ≥6
X6 + X 1 ≥ 9
 
Xj ≥ 0, j= 1,...,6
 PROBLEMA

Lácteos la Moderna» tiene una capacidad de recepción de 50.000 litros de

leche diarios. La administración exige que al menos 30.000 litros sean
embotellados diariamente y el resto sea empleado para producir leche
especial o mantequilla. La contribución de cada litro de leche a la utilidad,
según el uso que se le dé, es la siguiente: embotellada S/. 10, especial S/. 15
y S/. 16 la unidad de mantequilla (que se consume un litro de leche). El
equipo de fabricación de mantequilla puede manejar hasta 6.000 litros diarios
de leche, el equipo de envase puede manejar hasta 40.000 litros diarios, y el
de leche especial procesar hasta 20.000 litros por día. La empresa desea
conocer qué cantidad de leche en litros es convertida en mantequilla o en
leche especial y cuánto se debe embotellar (leche corriente) para maximizar
la ganancia.
Objetivo: Lácteos la Moderna desea maximizar sus ganancias, para lo cual
debe establecer cómo distribuir la leche que diariamente se recibe en la
producción de leche especial, mantequilla y cuánto embotellar.

Definición de variables
X1: cantidad de leche corriente que se embotellará diariamente
X2: cantidad de leche que se destinará diariamente a la producción de
mantequilla
X3: cantidad de leche que se destinará diariamente a la producción de leche
especial
Diseño del modelo
Max (Z) = 10 X1 + 16X2 + 15 X3
Sujeto a:
X1 + X2 + X3 ≤ 50.000 Capacidad de recepción diaria
X1 ≥ 30.000 Exigencia de leche por embotellar
X2 ≤ 6.000 Capacidad de fabricación de mantequilla
X1 ≤ 40. 000 Capacidad del equipo de envase
X3 ≤ 20.000 Capacidad del equipo de leche especial
X1, X2, X3 ≥ 0 No negatividad
 PROBLEMA
Una cadena de almacenes tiene 1,5 millones para asignarlos a uno
de sus almacenes. Tres productos, 1,2,3, requieren, respectivamente,
30, 3 y 15 pies cúbicos de espacio. Hay disponibles 300.000 pies3. El
producto 1 cuesta S/.12,00, el producto 2, S/. 4,50, y el 3, S/.15,00.

¿Qué cantidad debe adquirirse de cada grupo si los precios de venta

de 1,2,3 son, respectivamente, de S/.15,00, S/. 6,00, S/. 21,00?
Plantee este problema como un modelo de programación lineal.
Definición de variables
Xi : cantidad del producto i que se debe adquirir i = 1,2,3
Max (Z) =15X1 + 6X2 + 21 X3 – 12X1 - 4,5X2 -15 X3
Sujeto a: 
12X1 + 4.5X2 + 15 X3 ≤ 1.500.000 Capital
30X1 + 3X2 + 15 X3 ≤ 300.000 Requerimiento de espacio
X1, X2, X3 ≥ 0 No negatividad
 Problema
Un granjero tiene 200 cerdos que consumen 90 libras de comida especial todos los días.
El alimento se prepara como una mezcla de maíz y harina de soya con las siguientes
composiciones:
Libras por Libra de Alimento

Alimento Calcio Proteína Fibra Costo (S/. /lb)

Maíz 0.001 0.09 0.02 0.2
Harina de Soya 0.002 0.6 0.06 0.6

Los requisitos de alimento de los cerdos son:

1. Cuando menos 1% de calcio
2. Por lo menos 30% de proteína
3. Máximo 5% de fibra

Determine la mezcla de alimentos con el mínimo de costo por día

 Solución

¿Qué es lo que vamos a Minimizar?

X1 = la Cantidad de Maíz Libra por libra de Alimento

X2 = la Cantidad de Harina de Soya Libra por libra de Alimento

Función Objetivo

Min (Z) = 0.2X1 + 0.6X2

Sujetos a:

0.001X1 + 0.002X2 ≤ (90)(0.01) Calcio

0.09 X1 + 0.6 X2 ≤ (90)(0.3) Proteína
0.02 X1 + 0.06 X2 ≥ (90)(0.05) Fibra
X1, X2 ≥ 0
 Problema

Un pequeño banco asigna un máximo de S/. 200,000 para préstamos personales y para
artefactos eléctricos durante el mes siguiente. El banco cobra una tasa de interés anual
del 14% a préstamos personales y del 12% a préstamos para artefactos eléctricos.
Ambos tipos de préstamos se saldan en periodos de tres años. El monto de los
préstamos para artefactos eléctricos debe ser cuando menos de dos veces mayor que el
de los préstamos personales. La experiencia pasada ha demostrado que los adeudos no
cubiertos constituyen el 1% de todos los préstamos personales ¿Cómo deben asignarse
los fondos?
 Solución

¿Qué es lo que vamos a Maximizar?

X1 = La Cantidad fondos de préstamos personales
X2 = La Cantidad fondos de préstamos para artefactos eléctricos

Función objetivo
Max (Z) = 0.2 X1 + 0.6 X2

Sujetos a:
(0.14)(20,000) X1 + (0.12)(20,000) X2 ≤ 200,000
X2 ≥ (2)(0.14)(200,000)
X1 ≥ (0.01)(0.12)(200,000)
X1, X2 ≥ 0
Una planta armadora de radios produce dos modelos HiFi-1 y HiFi-2 en la misma
línea de ensamble. La línea de ensamble consta de tres estaciones. Los tiempos
de ensamble en la estaciones de trabajo son:
  Minutos por Unidad Minutos por Unidad
Estación de Trabajo HiFi-1 HiFi-2
1 6 4
2 5 5
3 4 6

Cada estación de trabajo tiene una disponibilidad máxima de 480 minutos por
día. Sin embargo, las estaciones de trabajo requieren mantenimiento diario, que
contribuye al 10%, 14% y 12% de los 480 minutos totales de que se dispone
diariamente para las estaciones 1, 2 y 3 respectivamente. La compañía desea
determinar las unidades diarias que se ensamblarán de HiFi-1 y HiFi-2 a fin de
minimizar la suma de tiempos no usados (inactivos) en la tres estaciones.
 Problema
Dos aleaciones, A y B, están hechas de cuatro metales diferentes: I, II, III y IV, según las
especificaciones siguientes:
Aleación Especificaciones
A Cuando mucho el 80% de I
Cuando mucho el 30% de II
Por lo menos el 50% de IV

B Entre 40% y el 60% de II

Cuando menos el 30% de III
A lo más el 70% de IV

Los cuatro metales se extraen de tres minerales metálicos diferentes:

Capacidad Constituyentes (%)

Mineral máxima Precio
(ton) (US$ / ton)
I II III IV Otros
1 1000 20 10 30 30 10 30
2 2000 10 20 30 30 10 40
3 3000 5 5 70 20 0 50

Suponiendo que los precios de venta de las aleaciones A y B son US$ 200 y US$ 399 por tonelada,
formule el problema como un modelo de programación lineal. 

Sugerencia: supóngase que Xijk representa el número de toneladas del i-ésimo metal obtenido de la j-
ésimo mineral metálico y asignado a la k-ésima aleación.
 Solución

Xijk = número de toneladas del i – esimo metal obtenido de la j – esimo mineral metálico
asignado a la k – esima aleación
Max (Z) = [(X11A + X21A + X31A + X41A + X12A + X22A + X32A + X42A + X13A + X23A + X33A + X43A)200
(X11B + X21B + X31B + X41B + X12B + X22B + X32B + X42B + X13B + X23B + X33B + X43B)399] -
(X11A + X21A + X31A + X41A )30 – (X11B + X21B + X31B + X41B)30 – (X12A + X22A + X32A + X42A)40 -
(X12B + X22B + X32B + X42B)40 – (X13A + X23A + X33A + X43A)50 – (X13B + X23B + X33B + X43B)50
Sujeto a: 
  X11A + X21A + X31A + X41A + X11B + X21B + X31B + X41B ≤ 1,000
X12A + X22A + X32A + X42A + X12B + X22B + X32B + X42B ≤ 2,000 Disponibilidad
X13A + X23A + X33A + X43A + X13B + X23B + X33B + X43B ≤ 3,000

X11A + X12A + X13A ≤ 0.80 [X11A + X21A + X31A + X41A + X12A + X22A + X32A + X42A + X13A +
X23A + X33A + X43A]

Xijk ≥ 0
 Problema N° 11

La Compañía XYZ produce tornillos y clavos. La materia Prima para

los tornillos cuesta S/. 2 por unidad, mientras que la materia prima
para el clavo cuesta S/. 2.50. Un clavo requiere dos horas de mano de
obra en el departamento N° 1 y tres en el departamento N° 2, mientras
que un tornillo requiere 4 horas en el departamento N° 1 y 2 horas en
departamento N° 2, el jornal por hora en ambos departamentos es de
S/. 2. Si ambos productos se venden a S/. 18, y el número de horas de
mano de obra disponibles por semana en los departamentos son de
160 y 180 respectivamente. Expresar el problema propuesto como un
programa lineal, tal que maximice las utilidades.

MATERIA
DPTO 1 DPTO 2 JORNAL PRECIO
PRIMA
Clavos 2 hrs. 3 hrs. S/. 2 / unid S/. 2 / hora S/. 18 / unid.
Tornillo 4 hrs. 2 hrs. S/. 2.5/unid. S/. 2 / hora S/. 18 / unid
Disponibilidad 160 hrs./sem. 180 hrs./sem.
 Solución

X1 : unidades de clavos a producirse por semana

X2 : unidades de tornillos a producirse por semana

Max (Z) = 18(X1 + X2) – [10 X1 + 2 X1 + 12 X2 + 2.5 X2]

Sujeto a:
2 X1 + 4 X2 ≤ 160
3 X1 + 2 X2 ≤ 180
X1 , X2 ≥ 0
 Problema N° 12

Xi : cantidad de unidades del tipo i a ser fabricados para ser

vendidos a la semana
i : 1, 2, y 3
1 = válvula globo
2 = válvula aguja
3 = módulo

Max (Z) = 10 X1 + 20 X2 + 60 X3
Sujeto a:
10X1 + 15X2 + (25 + 2 x 10)X3 ≤ 25,000
5X1 + 5X2 + (10 + 2 x 5) X3 ≤ 15,000
5X1 + 5X2 + 10 X3 ≤ 45,000
5X2 + 10 X3 ≤ 45,000
5X2 + 20 X3 ≤ 45,000
X3 ≥ 200
X1, X2 , X3 ≥ 0
 Problema N° 13

TAKAGAKI S. A. fabrica dos tipos de alimentos balanceados,

recibe un pedido especial de 200 TN de una mezcla de proteínas
y carbohidratos, la mezcla debe contener a lo más 40% de
proteínas y por lo menos 30% de carbohidratos, el costo de cada
TN de proteínas es de S/. 3 y de cada TN de carbohidratos es de
8, determinar la mezcla óptima.
XP: TN. de proteínas utilizadas en la mezcla
Xc: TN. de carbohidratos utilizadas en la mezcla

Max (Z) = 3 XP + 8 XC
Sujeto a:
XP + XC = 200
XP ≤ 0.40 ( XP + XC)
XC ≥ 0.30 ( XP + XC)

XP , XC ≥ 0
 Problema N° 14

Xi: Número de acres que se destinan a cada cosecha en cada comunidad

I = 1, 2, 3, 4, 5, 6, 7, 8, 9
Comunidad Comunidad
Cosecha Cosecha
1 2 3 1 2 3
1 Remolacha X1 X2 X3 1 Remolacha X11 X12 X13
2 Algodón X4 X5 X6 2 Algodón X21 X22 X23
3 Sorgo X7 X8 X9 3 Sorgo X31 X32 X33

Max (Z) = 1,000 (X1 + X2 + X3) + 750 (X4 + X5 + X6) + 250 (X7 + X8 + X9)

Sujeto a:
Terreno para uso en cada comunidad
X1 + X4 + X7 ≤ 400
X2 + X5 + X8 ≤ 600
X3 + X6 + X9 ≤ 300
 Continuación
Asignación de agua para cada comunidad
3 X1 + 2 X4 + X7 ≤ 600
3 X2 + 2 X5 + X8 ≤ 800
3 X3 + 2 X6 + X9 ≤ 375

Total de acres para cada cosecha

X1 + X2 + X3 ≤ 600
X4 + X5 + X6 ≤ 500
X7 + X8 + X9 ≤ 325

Igual proporción del área planteada

X1 + X 4 + X 7 = X 2 + X 5 + X 8
400 600
X2 + X 5 + X 8 = X 3 + X 6 + X 9
600 300

Xi ≥ 0 , i = 1,………,9
 Problema N° 15

Variable de decisión
Xi = El uso de cada uno de los tres métodos de abatimiento en cada
tipo de horno, expresado como una fracción de la capacidad de
abatimiento de tal manera que Xi no exceda a 1

Función Objetivo
Min (Z) = 8X1 + 10X2 + 7X3 + 6X4 + 11X5 + 9X6 Método de
Sujeto a: abatimiento
12X1 + 9X2 + 25X3 + 20X4 + 17X5 + 13X6 ≥ 60
35X1 + 42X2 + 18X3 + 31X4 + 56X5 + 49X6  150
37X1 + 53X2 + 28X3 + 24X4 + 29X5 + 20X6  125 Tecnología

X1 + X2 + X3 + X4 + X5 + X6 ≤ 1
X1, X2 , X3 , X4, X5, X6  0
 Problema

Un municipio ha obtenido recursos para mejorar su sistema de

recolección de residuos sólidos. Se ha estimado que la generación de
residuos del municipio es de cerca de las 22 toneladas métricas, muy
superior a la capacidad de recolección, ya que actualmente cuenta con
sólo dos camiones de volteo y un camión cilíndrico, los primeros
pueden recolectar 2500 kg diarios cada uno y el segundo alrededor de
5600 kg. Los costos diarios de operación de cada vehículo son de S/.
400 y S/. 350 respectivamente; mientras que los costos diarios de la
mano de obra son S/. 650 y S/. 550 y no deben superar los S/. 4,000. Se
tiene un presupuesto de S/. 1,200,000 para equipo nuevo y gracias a un
programa federal se pueden adquirir los camiones de volteo a un costo
de S/. 360,000 y los cilíndricos a S/. 420,000.

Plantee un programa lineal en forma canónica para determinar cuál es la

combinación de vehículos con el menor costo de operación, tras la
compra de nuevos camiones y obtenga su solución.
 Solución

Definimos las variables de decisión:

X1 : número total de camiones de volteo tras la compra de vehículos nuevos
X2 : número total de camiones cilíndricos tras la compra de vehículos nuevos
Función Objetivo:
MIN ( Z ) = 400 X1 + 350 X2
Sujeto a:
• Residuos a recolectar: 2.5 X1 + 3.6 X2 ≥ 22
• Costo de mano de obra: 650 X1 + 550 X2 ≤ 4000
• Presupuesto para vehículos nuevos:
360,000 (X1 - 2) + 420,000 (X2 - 1) ≤ 1,200, 000
• Camiones de volteo en operación: X1 ≥ 2
• Camiones cilíndricos en operación: X2 ≥ 1
• No negatividad: X1 , X2 ≥ 0
 Ejemplo – Método Simplex

La compañía SONYT S. A. produce radios y televisores, cada radio se vende con una ganancia de S/.
30, mientras que cada televisor vendido se gana S/. 50.

Ambos productos deben pasar por los departamentos A y B (impresión de circuitos y ensamble)
respectivamente: mensualmente se dispone de 200 horas en el departamento A y 140 horas en el
departamento B. Cada radio requiere de una hora en departamento A como en el departamento B,
cada televisor requiere de 2 horas en departamento A y una hora en el departamento B. Cuál es el
programa de producción que maximiza la ganancia.

REQUERIMIENTOS
DEPARATMENTO DISPONIBILIDAD
RADIO TELEVISOR
A 1 hr. 2 hrs. 200 hrs / mes
B 1 hr. 1 hr. 140 hrs. / mes
Xi: Numero de unidades del producto tipo i que se deben producir
mensualmente.

Max (Z) = 30 X1 + 50 X2

Sujeto a:
X1 + 2 X2 ≤ 200
X1 + X2 ≤ 140
X1 , X2 ≥ 0
 Solución

(0,100)

(80,60)

(140,0)
 Solución
Iteración N° 1
Cj 30 50 0 0
Ci XB X1 X2 S1 S2 bi θi
0 S1 1 2 1 0 200 100
0 S2 1 1 0 1 140 140
Cj -Zj 30 50 0 0 0

Iteración N° 2
Cj 30 50 0 0
Ci XB X1 X2 S1 S2 bi θi
50 X2 1/2 1 1/2 0 100 200
0 S2 1/2 0 -1/2 1 40 80
Cj -Zj 5 0 -25 0 5000
 Solución
Iteración N° 3

Cj 30 50 0 0
Ci XB X1 X2 S1 S2 bi θi
50 X2 0 1 1 -1 60
30 X1 1 0 -1 2 80
Cj -Zj 0 0 -20 -10 5400
SOLUCION GRAFICA
 Cualquier punto dentro de la región cumple simultáneamente con las tres
restricciones y con la no negatividad.
Ahora el problema consiste en maximizar la función objetivo Z = X 1+X2
sobre la región sombreada que representa a las restricciones del
problema lineal en estudio:

X1+X2 = 0 M = - X2
X1

Z=2

Z=0

La recta X1+X2 = 4 representa el máximo valor de Z, Sujeta a las

restricciones del programa lineal propuesto. Cualquier valor de Z > 6, no
tendrá ningún punto con la región sombreada
Región Factible. Es aquella que cumple con todas las
restricciones y las condiciones de no negatividad.

Solución Factible. Es cualquier punto situado en la región factible.

Solución Básica. Es aquella que se encuentra en la intersección
de rectas o hiperplanos o en la intersección con los ejes
coordenados.

Solución Básica Factible. Es una solución básica que pertenece a

la región factible.

Solución Optima. Es una solución factible que maximiza o

minimiza la función objetivo según sea el caso

Solución Básica Factible Degenerada. Es una solución factible

básica en la que una o más variables básicas toman el valor de
cero.
TEOREMA 1. El conjunto de todas las soluciones factibles al problema
de programación lineal es un conjunto convexo.

TEOREMA 2. La función objetivo alcanza su máximo en un punto

extremo del conjunto convexo, generado por el conjunto de soluciones
factibles al problema de programación lineal.

1. Existe un punto extremo del polígono (poliedro) convexo en el

cual la función objetivo tiene su máximo (mínimo).
2. Cada solución factible básica corresponde a un punto extremo
del polígono (poliedro) convexo.

Se tendrá que buscar que investigar únicamente los puntos extremos

del polígono (poliedro) convexo y buscar aquel punto que proporcione
el mayor (menor) valor para que la función objetivo y así obtendremos
la solución buscada.
 Restricción de mayor o igual que cero, límite mínimo

Ejemplo 2
Min (Z) = 2 X1 + 6 X2
Sujeto a:
12 X1 + 6 X2 ≥ 16
4 X1 + 12 X2 ≥ 12
X1 , X2 ≥ 0
Ejemplo 3
Min (Z) = 2 X1 + 3 X2
Sujeto a:
X1 + X2 ≤ 4
6 X1 + 2 X2 = 8
X1 + 5 X2 ≥ 4 B

X1 ≤3
X2 ≤ 3
A
X1 , X2 ≥ 0

La solución se encuentra en el segmento A y B, donde X1 = 8/7 y X2

= 4/7. la función objetivo toma el valor de 4.
Ejemplo 4
Max (Z) = X1 + X2
Sujeto a:
- 4 X1 + 2 X2 ≤ 2
2 X1 ≤4 (2/3,7/3)

2 X1 + 2 X2 ≤ 6 B
(2,1)
X1 , X2 ≥ 0
C

Se aprecia que la recta de la función objetivo no es ahora tangente

a un vértice del polígono factible, si no es coincidente con uno de
los lados del mismo.
¿Cuál es entonces la solución?
En este caso es posible definir cualquier punto sobre la recta BC y
hallar en consecuencia los valores X1 y X2.
X = 2 ; X = 1; Z = 3, otro resultado X = 2/3 , X = 7/3 ; Z = 3
Ejemplo 5
(6,5)
Max (Z) = 2 X1 + 2 X2
Sujeto a:
X1 - X2 ≥ 1
1/ 2 X1 + X2 ≤ 2
X1 , X2 ≥ 0

No tiene un valor máximo finito.

En problemas prácticos no puede presentarse este tipo de
solución
Ejemplo 6
Max (Z) = 3 X1 + 2 X2
Sujeto a:
X1 + X2 ≤ 1
2 X1 + 2 X2 ≥ 4
X1 , X2 ≥ 0

Ejemplo 7
Max (Z) = X1 + X2
Sujeto a:
3 X1 - X2 ≥ - 3
X1 + X2 ≤ 4
X1 , X2 ≥ 0
No se puede garantizar que todo problema tenga solución
factible.
 USANDO UN GRAFICO SE
PUEDEN REPRESENTAR TODAS
LAS RESTRICCIONES, LA
FUNCION OBJETIVO Y LOS
TRES TIPOS DE PUNTOS DE
FACTIBILIDAD.
Ejemplo: El problema de la industria de
juguetes “Galaxia”.

• Galaxia produce dos tipos de juguetes:

* Space Ray
* Zapper

• Los recursos están limitados a:

* 1200 libras de plástico especial.
* 40 horas de producción semanalmente.
• Requerimientos de Marketing.

* La producción total no puede exceder de 800 docenas.

* El número de docenas de Space Rays no puede exceder al
número de docenas de Zappers por más de 450.

• Requerimientos Tecnológicos.

* Space Rays requiere 2 libras de plástico y 3 minutos de

producción por docena.
* Zappers requiere 1 libra de plástico y 4 minutos de producción

por docena.
• Plan común de producción para:

 Fabricar la mayor cantidad del producto que deje mejores

ganancias, el cual corresponde a Space Ray (S/. 8 de utilidad
por docena).

 Usar la menor cantidad de recursos para producir Zappers, porque

estos dejan una menor utilidad (S/. 5 de utilidad por docena).
 Solución

• Variables de decisión

X1 = Cantidad producida de Space Rays (en docenas por

semana).
X2 = Cantidad producida de Zappers (en docenas por
semana).

• Función objetivo

Maximizar la ganancia semanal.

• Modelo de Programación Lineal

Max (Z) = 8X1 + 5X2 (ganancia semanal)

Sujeto a:
2X1 + 1X2  1200 (Cantidad de plástico)
3X1 + 4X2  2400 (Tiempo de producción)
X1 + X2  800 (Limite producción total)
X1 - X2  450 (Producción en exceso)
Xj  0, j = 1, 2. (Resultados positivos)

• El plan común de producción consiste en:

Space Rays = 550 docenas

Zappers = 100 docenas

Utilidad = S/. 4900 por semana

 Tipos de Puntos de factibilidad
X2

1200
Restricción del plástico:
2X1 + X2  1200
Restricción del total de producción:
X1 + X2  800
600 No Factible

Restricción del
Horas de Factible exceso de producción:
Producción X1 - X2  450
3X1 + 4X2  2400
X1
600 800

Punto Inferior Punto Extremo

Punto Medio
• Resolución gráfica para encontrar la solución
optima
 comenzar con una ganancia dada de = S/. 2,000...

X2 Entonces aumente la ganancia...

1200
...y continúe hasta que salga de la región factible

Ganancia
Util. = S/.= S/.
2,0005,040
3,
4,
800

600

X1

400 600 800

 X2
1200
Se toma un valor cercano al
punto óptimo

800 Región no
factible
600

Feasible
Región
region
Factible
X1

400 600 800

• Resumen de la solución óptima

Space Rays = 480 docenas

Zappers = 240 docenas
Ganancia = S/. 5,040

*Esta solución utiliza todas las materias primas (plástico) y

todas las horas de producción.
* La producción total son 720 docenas (no 800).
* La producción de Space Rays excede a la de Zappers por
solo 240 docenas y no por 450.
• Soluciones óptimas y puntos extremos.

* Si un problema de programación lineal tiene una solución

óptima, entonces esta corresponde a un punto extremo.

• Múltiples soluciones óptimas.

* Cuando existen múltiples soluciones óptimas

implica que la función objetivo es una recta paralela
a uno de los lados de la región factible.
* Cualquier promedio ponderado de la solución óptima
es también una solución óptima.
 SOLUCION EXAMEN PARCIAL
1. Dos productos se elaboran al pasar en forma sucesiva por tres máquinas, de
diferente capacidad y rendimiento. El tiempo por máquina asignado a los
productos es de 12 horas por día para la máquina 1, 10 para la máquina 2 y
por lo menos 8 horas para la máquina 3, por su gran rendimiento. El tiempo
de producción y el costo por unidad de cada producto son:

Minutos por unidad

Producto Máquina 1 Máquina 2 Máquina 3 Costo
1 10 6 8 S/ 2
2 5 20 15 S/. 3

Formule el modelo matemático

Determine la combinación óptima de los productos.

En estación de trabajo no se utiliza la totalidad de las horas disponibles

Qué tipo de solución es.

¿Qué es lo que vamos a Minimizar?

x1 = la Cantidad de Unidades del Producto 1/día

x2 = la Cantidad de Unidades del Producto 2/día

Min Z = 2X1 + 3X2 ……..(1)

Sujeto a:
10X1 + 5X2 < 720 …….. (2)
6X1 + 20X2 < 600 …… ..(3)
8X1 + 15X2 ≥480 ............(4)
X1, X2 ≥ 0

Min Z = 2X1 + 3X2 + 0S1 + OS2 + 0S3 +MA3……..(1)

Sujeto a:
10X1 + 5X2 + S1 = 720 …….. (2)
6X1 + 20X2 + S2 = 600 …… ..(3)
8X1 + 15X2 - S3 + A3 = 480 ..........(4)
X1, X2, S1, S2, S3, A3 ≥ 0
 Solución
Iteraciones
Cj 2 3 0 0 0 M
Ci XB X1 X2 S1 S2 S3 A3 bi θi
M S1 10 5 1 0 0 0 720 144
0 S2 6 20 0 1 0 0 600 30
M A3 8 15 0 0 -1 1 480 32
Cj – Zj 2-8M 3-15M 0 0 M 0
1 S1 17/2 0 1 1/4 0 0 570 1140/1
7

0 X2 3/10 1 0 1/20 0 0 30 100

M A3 7/2 0 0 -3/4 -1 1 30 60/7
Cj - Zj 11/10-7M/2 0 0 -3/10+3M/4 M 0

1 S1 0 0 1 29/140 17/7 -17/7 3480/

7

0 X2 0 1 0 4/35 3/35 -3/35 192/7

1 X1 1 0 0 -3/14 -2/7 2/7 60/7

Cj - Zj 0 0 0 3/35 11/35 M-2/9 696/7

Solución óptima única

 SOLUCIÓN EXAMEN PARCIAL

(Purificación del mineral) Una compañía posee dos minas, P y Q. En el cuadro

siguiente se muestra la producción de los elementos por cada tonelada
producida por ambas minas respectivamente:

MINAS COBRE ZINC MOLIBDENO COSTO POR TON. DE

OBTENCIÓN DE MINERAL
P 50 lb 4 lb 1 lb S/. 50
Q 15 lb 8 lb 4 lb S/. 60

La compañía debe producir cada semana, las siguientes cantidades de los

metales que se muestran a continuación:
- Al menos 875 libras de cobre
- A los más 160 libras de zinc
- Al menos 50 libras de molibdeno

Formule el modelo matemático

Que mineral se produce en exceso

Qué tipo de solución es.

• ¿Cuánto mineral deberá obtenerse de cada mina con objeto de
cumplir los requerimientos de producción a un costo mínimo?

Variables:
x1 = La cantidad de TN de Mineral de la MINA P que se debe extraer
x2 = La cantidad de TN de Mineral de la MINA Q que se debe extraer

Max Z = 50X1 + 60X2 …….(1)

Sujeto a:

50X1 + 15X 2 ≥ 875 ......... (2) (COBRE)

4X1 + 8X2 < 160….......(3) (ZINC)
X1 + 4X2 ≥ 50 ............(4) (MOLIBDENO)
X1 X2 ≥ 0
 Solución
Iteraciones
Cj 50 60 0 0 0 M M

Ci XB X1 X2 S1 S2 S3 A1 A3
bi ᶱ
M A1 50 15 -1 0 0 1 0 875 35/2
0 S2 4 8 0 1 0 0 0 160 40
M A3 1 4 0 0 -1 0 1 50 50
Cj – Zj 50-51M 60- M 0 M 0 0
50 X1 1 3/1019 -1/50 0 0 1/50 0 35/2 175/3
M
0 S2 0 34/5 2/25 1 0 -2/50 0 90 225/17

M A3 0 37/10 1/50 0 -1 -1/50 -1 65/2 325/37

Cj – Zj 0 45-37/10M 1-M/50 0 M 51/50M-1 0

50 X1 1 0 -4/185 0 3/37 4/185 -3/37 550/37

0 S2 0 0 8/185 1 68/37 -8/185 -68/37 1120/37

60 X2 0 1 1/185 0 -10/37 -1/185 10/37 325/37

Cj - Zj 0 0 28/37 0 450/37 M-28/37 M-

450/37 47500/37

Solución óptima única