Capitulo II – Investigación Operativa I

Programación
Lineal

Univ: Ibarra Sansuste Luis Adolfo

Doc: M.Sc. Ing. Gregorio Fernando Ureña Mérida
Paralelo: Sis 2510 “A”
 Formulación de Programación Lineal

1. INTRODUCCIÓN
EL TÉRMINO IO SE UTILIZA POR PRIMERA VEZ EN EL AÑO 1939 DURANTE LA 2DA GUERRA MUNDIAL,
ESPECÍFICAMENTE CUANDO SURGE LA NECESIDAD DE INVESTIGAR LAS OPERACIONES TÁCTICAS Y
ESTRATÉGICAS DE LA DEFENSA AÉREA, ANTE LA INCORPORACIÓN DE UN NUEVO RADAR, EN
OPORTUNIDAD DE LOS ATAQUES ALEMANES A GRAN BRETAÑA. EL AVANCE ACELERADO DE LA
TECNOLOGÍA MILITAR HACE QUE LOS EJECUTIVOS Y ADMINISTRADORES MILITARES BRITÁNICOS DEBAN
RECURRIR A LOS CIENTÍFICOS, EN POS DE APOYO Y ORIENTACIÓN EN LA PLANIFICACIÓN DE SU
DEFENSA.
LA PROGRAMACIÓN LINEAL ES UN PROCEDIMIENTO O ALGORITMO MATEMÁTICO
MEDIANTE EL CUAL SE RESUELVE UN PROBLEMA INDETERMINADO, FORMULADO A TRAVÉS
DE ECUACIONES LINEALES, OPTIMIZANDO LA FUNCIÓN OBJETIVO, TAMBIÉN LINEAL.
CONSISTE EN OPTIMIZAR (MINIMIZAR O MAXIMIZAR) UNA FUNCIÓN LINEAL, DENOMINADA
FUNCIÓN OBJETIVO, DE TAL FORMA QUE LAS VARIABLES DE DICHA FUNCIÓN ESTÉN SUJETAS
A UNA SERIE DE RESTRICCIONES QUE EXPRESAMOS MEDIANTE UN SISTEMA DE
INECUACIONES LINEALES.
• Método de las dos fases
• El Método de las Dos Fases es una variante del Algoritmo simplex, que es usado
como alternativa al Método de la Gran M, donde se evita el uso de la constante M
para las variables artificiales. Se puede resumir así:
• Taha, Handy (1995). «Investigación de Operaciones». Investigación de Operaciones.
México DF. 970-15-0115-2.
• Fase Uno:
• Minimizar la suma de las variables artificiales del modelo. Si el valor de la Z
óptima es cero, se puede proseguir a la Fase Dos, de lo contrario el problema no
tiene solución.
• Fase Dos:
• Con base en la tabla reclinable de la fase uno, se elimina de las restricciones las
variables artificiales, y se reemplaza la función objetivo, por la función objetivo
original y se resuelve a partir de la resultante, con el método Simplex tradicional.
 3. Planteamiento del Problema
La firma PRODUCTOS LO MEJOR S.A. fabrica tres productos en dos máquinas. En una semana típica
hay disponible 40 horas en cada máquina.
La contribución a las utilidades y el tiempo de producción en horas por unidad son los siguientes:

Se requieren dos operarios para la maquina 1, por ello se debe programar dos hora de mano de obra
para cada hora del tiempo de la maquina 1; En la maquina 2 solo se requiere un operario.
Existe un total de 100 horas de mano de obra disponible para asignarlas a las maquinas en la semana siguiente.
El producto 1 no puede constituir más de 50% de las unidades que se fabrican y que el producto 3 debe
constituir cuando menos el 20% de las unidades que se producen.
¿Cuántas unidades de cada producto deben fabricarse?
Formular el modelo.
Resolver el Modelo.
4. Objetivo General
Encontrar un método de programación lineal y resolverlo, en este caso método de la doble
fase.
La investigación de operaciones tiene como objetivo general encontrar la solución óptima de
un problema (transporte, construcción, logístico etc.) y asi garantizar elecciones mejoradas al
momento de la toma de decisiones, respetando las restricciones no controlables por quien
debe hacer la elección; es decir, nos permite plantear una RESOLUCION a cualquier problema
operacional dentro de una organización.
5. Objetivo específicos
Resolver el ejercicio propuesto, para poder determinar cuántas unidades de cada
producto pueden fabricarse, para que la empresa pueda cumplir con sus
expectativas de producción.
6. Marco Teórico
Tipo de optimización.
Objetivo de maximización
Condición de parada: cuando en la fila Z no aparece ningún valor negativo.
Condición de entrada a la base: el menor valor negativo en la fila Z (o el de mayor valor
absoluto entre los negativos) indica la variable Pj que entra a la base.
Condición de salida de la base: una vez obtenida la variable entrante, la variable que sale
se determina mediante el menor cociente P0/Pj de los estrictamente positivos.
Objetivo de minimización
Condición de parada: cuando en la fila Z no aparece ningún valor positivo.
Condición de entrada a la base: el mayor valor positivo en la fila Z indica la variable Pj que
entra a la base.
Condición de salida de la base: una vez obtenida la variable entrante, la variable que sale
se determina mediante el menor cociente P0/Pj de los estrictamente negativos.
 7. Construcción del Modelo

MÉTODO DE PENALIZACIÓN.
A este método se le conoce como Método de la M Grande, o la Gran M, ("Big M
Method" en la literatura inglesa). Implica la introducción de variables
artificiales con coeficiente M en la función objetivo.
 Con signo negativo cuando se quiera maximizar
 Con signo positivo cuando se quiera minimizar

Min Z = cX + MYn Max Z = cX - MYn

s.a. s.a.
AX – Y + Yn=b AX – Y + Yn=b
X ≥ 0, Y ≥ 0, Yn ≥ 0 X ≥ 0, Y ≥ 0, Yn ≥ 0

Se obtiene la solución óptima del problema sí y solo sí el vector Yn (vector

de las variables artificiales) es igual a cero. Tipo de
Tipo de variable que aparece
desigualdad
En caso de haber llegado a la solución óptima; pero el vector Yn > 0,
entonces el problema original no tiene solución. ≥ - exceso + artificial

= + artificial

≤ + holgura
Pasos
1) Expresar el problema en forma estándar,
2) Introducir las variables artificiales (Yn) en las restricciones que tengan la
característica ( ≥ b, ó = b ).
3) Asignar la penalización para cada unidad de las variables en la función
objetivo designada como (–M) para problemas de maximización y (+M)
para minimización, con M>0.
4) Elaborar la primera tabla con todo lo anterior señalado.
5) Mediante el uso de las operaciones de renglón elementales, hacer cero
el valor del coeficiente de la variable artificial Yn (última fila)
6) Continuar con el algoritmo del Método Simplex.
Ojo: No es un vector
unitario
MÉTODO DE LA DOBLE FASE

El método de la Doble Fase, consiste esencialmente en introducir

variables artificiales al problema. de tal manera que se tenga:

Siendo W el vector de las variables artificiales

1ª Fase.-.
En la primera fase se resuelve el problema

(n variables artificiales con coeficientes 1s)

Sujeto a:

La solución óptima debe ser W = 0 para esta fase. Si W >0, el problema original no
tiene solución
2ª Fase.-
En caso de que la primera fase sea óptima con W= 0 y la base asociada a la tabla
sea B.
En la segunda fase, se aplicará el Método Simplex para resolver el problema:

Sujeto a

Es importante tener en cuenta que la solución óptima a esta segunda fase, es

la solución óptima al problema original.

NOTA.-Al empezar la segunda fase, todos los vectores de la base óptima que provienen de la
primera fase deberán estar expresados en forma unitaria (valores Zj – Cj correspondientes a los
vectores base deben hacerse iguales a cero.
Segunda fase:
Max h + 25x1 + 18x2 = 0

Solución:
X1=2
X2=3/2
Min Z= 77
8. Resolución del Modelo (Analítico, Resumiendo:

Herramienta Software) MAX Z = 30𝑥1 + 50 𝑥2 + 20 𝑥3

VARIABLES REALES: 0,5 𝑥1 + 2 𝑥2 + 0,75 𝑥3 ≤ 40

𝑥1 : Producto 1 𝑥1 + 𝑥2 + 0,5 𝑥3 ≤ 40
𝑥2 : Producto 2 2𝑥1 + 5𝑥2 + 2 𝑥3 ≤ 100
𝑥3 : Producto 3 0,5𝑥1 - 0,5𝑥2 - 0,5 𝑥3 ≤0
FUNCION OBJETIVO −0,2𝑥1 -0,2𝑥2 + 0,8 𝑥3 ≥0
MAX Z = 30𝑥1 + 50 𝑥2 + 20 𝑥3 𝑥1 , 𝑥2 ,𝑥3 ≥ 0
0,5 𝑥1 + 2 𝑥2 + 0,75 𝑥3 ≤ 40
𝑥1 + X2 + 0,5 𝑥3 ≤ 40
2 (0,5 𝑥1 + 2 X2 + 0,75 𝑥3 ) + (𝑥1 + X2 + 0,5 𝑥3 ) ≤ 100
𝑥1 ≤ 0,5 (𝑥1 + X2 + 𝑥3 )
𝑥3 ≤ 0,2 (𝑥1 + X2+ 𝑥3 )
𝑥1 , 𝑥2 ,𝑥3 ≥ 0
Tabla 1 30 50 20 0 0 0 0 0
Base Cb P0 P1 P2 P3 P4 P5 P6 P7 P8
P4 0 40 1/2 2 3/4 1 0 0 0 0
P5 0 40 1 1 1/2 0 1 0 0 0

P6 0 100 2 5 2 0 0 1 0 0

P7 0 0 1/2 -1 / 2 -1 / 2 0 0 0 1 0
P8 0 0 1/5 1/5 -4 / 5 0 0 0 0 1
Z 0 -30 -50 -20 0 0 0 0 0

La variable que sale de la base es P8 y la que entra es P2.

Tabla 2 30 50 20 0 0 0 0 0
Base Cb P0 P1 P2 P3 P4 P5 P6 P7 P8
P4 0 40 -3 / 2 0 35 / 4 1 0 0 0 -10
P5 0 40 0 0 9/2 0 1 0 0 -5
P6 0 100 -3 0 22 0 0 1 0 -25
P7 0 0 1 0 -5 / 2 0 0 0 1 5/2
P2 50 0 1 1 -4 0 0 0 0 5
Z 0 20 0 -220 0 0 0 0 250

La variable que sale de la base es P6 y la que entra es P3.

Tabla 3 30 50 20 0 0 0 0 0
P
Base Cb P0 P1 P2 P3 P4 P5 P6 P8
7
P4 0 5 / 22 -27 / 88 0 0 1 0 -35 / 88 0 -5 / 88
P5 0 215 / 11 27 / 44 0 0 0 1 -9 / 44 0 5 / 44
P3 20 50 / 11 -3 / 22 0 1 0 0 1 / 22 0 -25 / 22
P7 0 125 / 11 29 / 44 0 0 0 0 5 / 44 1 -15 / 44
P2 50 200 / 11 5 / 11 1 0 0 0 2 / 11 0 5 / 11
Z 1000 -10 0 0 0 0 10 0 0

La variable que sale de la base es P7 y la que entra es P1.

Tabla 4 30 50 20 0 0 0 0 0
Base Cb P0 P1 P2 P3 P4 P5 P6 P7 P8
P4 0 160 / 29 0 0 0 1 0 -10 / 29 27 / 58 -25 / 116
P5 0 260 / 29 0 0 0 0 1 -9 / 29 -27 / 29 25 / 58
P3 20 200 / 29 0 0 1 0 0 2 / 29 6 / 29 -35 / 29
P1 30 500 / 29 1 0 0 0 0 5 / 29 44 / 29 -15 / 29
P2 50 300 / 29 0 1 0 0 0 3 / 29 -20 / 29 20 / 29
34000 /
Z 0 0 0 0 0 340 / 29 440 / 29 -150 / 29
29

La variable que sale de la base es P2 y la que entra es P8.

Tabla 5 30 50 20 0 0 0 0 0
Base Cb P0 P1 P2 P3 P4 P5 P6 P7 P8
P4 0 35 / 4 0 5 / 16 0 1 0 -5 / 16 1/4 0
P5 0 5/2 0 -5 / 8 0 0 1 -3 / 8 -1 / 2 0
P3 20 25 0 7/4 1 0 0 1/4 -1 0
P1 30 25 1 3/4 0 0 0 1/4 1 0
P8 0 15 0 29 / 20 0 0 0 3 / 20 -1 1
Z 1250 0 15 / 2 0 0 0 25 / 2 10 0

9. Análisis de Resultados y Selección de la

Solución
Como podemos apreciar los resultados obtenidos, para que la
empresa puede maximizar la obtención de los productos
elaborados, usando los tiempos y porcentajes de restricción.

La solución óptima es Z = 1250

X1 = 25
X2 = 0
X3 = 25
10. Conclusiones y Recomendaciones
En conclusiones la firma deberá fabricar producto 1: 25 y del
producto2: 25 ya que si se podría fabricar el producto 3 no se
podría obtener la máxima ganancia para la firma que es lo que
se pide en el enunciado.

11. Bibliografía
˙ Ackoff, R y Sasieni M. Fundamentos de la
investigación de Operaciones. Limusa
˙ Taha H. Investigación de Operaciones. Alfa omega
˙ Hillier y Lieberman Introducción a la Investigación
de Operaciones. Mc Graw Hill
˙ Prawda. Investigación Operativa. C.E.C.S.A.
˙ Hillier y Lieberman Introducción a la Investigación
de Operaciones. Mc Graw Hill
˙ Marín I. Investigación Operativa. Centro Estudiantes
Ingeniería “La Línea Recta” UBA
˙ Kauffman. Métodos y Modelos de Investigación de
Operaciones, CECSA
˙ Investigación de operaciones Schaum
12. Anexos x1 x2 s1 s2 p1 p2 SOL

OTROS EJERCICIOS Min z’ 0 0 0 0 -1 -1 0

Min z = 20x1 + 28x2
p1 4 3 -1 0 1 0 1
S.a.
4x1 + 3x2  1 p2 0 9 0 -1 0 1 1

9x2  1
x1 , x2  0 Como la tabla no tiene el formato correcto para aplicar el
Determinar su solución mediante el algoritmo del SIMPLEX. simplex, pues no son nulos los coeficientes de las
Utilizar el método de las dos fases ante la falta de una solución variables básicas en la línea de z, sumamos la segunda y
factible básica inicial. tercera fila a la primera y obtenemos
x1 x2 s1 s2 p1 p2 SOL
El programa lineal no tiene una solución factible básica inicial Min z’ 4 12 -1 -1 0 0 2
dado el sentido de las desigualdades. Para obtener una
p1 4 3 -1 0 1 0 1
solución factible básica inicial utilizaremos el método de las dos
p2 0 9 0 -1 0 1 1
fases introduciendo dos variables artificiales p1 y p2 y tratando
de hacer Min z’ = p1 + p2. La tabla simplex de esta Fase I es
Pivotaremos alrededor del elemento señalado en
negrita y en cursiva (notación que utilizaremos en todo
el proceso), lo que nos da la tabla
 x1 x2 s1 s2 SOL
x1 x2 s1 s2 p1 p2 SOL

Min z -20 -28 0 0 0

Min z’ 4 0 -1 1/3 0 -4/3 2/3
x1 1 0 -1/4 1/12 1/6
p1 4 0 -1 1/3 1 -1/3 2/3
x2 0 1 0 -1/9 1/9

x2 0 1 0 -1/9 0 1/9 1/9

Tabla que no se adapta a los requisitos del simplex

en los que debe aparecer un cero en la línea de z en
Siguiendo el proceso del algoritmo del simplex obtenemos la
las variables básicas. Para lograrlo sumamos a esta
tabla
x1 x2 s1 s2 p1 p2 SOL
fila la segunda multiplicada por 20 y la tercera
multiplicada por 28, obteniendo
Min z’ 0 0 0 0 -1 -1 0 x1 x2 s1 s2 SOL

x1 1 0 -1/4 1/12 1/4 -1/12 1/6 Min z 0 0 -5 -13/9 58/9

x2 0 1 0 -1/9 0 1/9 1/9

x1 1 0 -1/4 1/12 1/6

x2 0 1 0 -1/9 1/9
Con la que se finaliza la Fase I al obtener una base factible.
Recuperamos nuestro problema sustituyendo en la fila de z’ los x1 = 1/6
coeficientes de la función objetivo original y obtenemos la
x2 = 1/9
tabla
s1 = 0
s2 = 0
z = 58/9