GRUPO 4

CAPÍTULO 3: INTRODUCCIÓN A
LA PROGRAMACIÓN LINEAL
INTEGRANTES:

DOCENTE:

ACOSTA DONNA VÁZQUEZ GENARO

CASAS MICAELA
LIZANO LUCERO
REVOREDO ADRIANA
SOTO GERALDINE
TREJO JHON
IV CICLO
INTRODUCCIÓN
PROGRAMACIÓN Es un método matemático que sirve para optimizar

LINEAL
una función cuyas variables están sujetas a
restricciones, siempre y cuando la función y las
restricciones sean linealmente dependientes de las
variables.
Generalmente la función a optimizar modela una
situación práctica.

Función objetivo

Variables de decisión

Restricciones
3.1 EJEMPLO PROTOTÍPICO
La empresa WYNDOR GLAS CO produce
artículos de vidrio de alta calidad, como
ventanas y puertas de vidrio que se realizan en
tres plantas.
Hubo una reducción de las ganancias y la alta
administración decidió reorganizar la línea de
producción de la compañía, se dejaran de
fabricar productos no rentables y se dejará libre
una parte de la capacidad de producción para
emprender la fabricación de dos productos
nuevos cuyas ventas potenciales son
prometedores.
-Puerta de vidrio de 8 pies de altura con marco
de aluminio.
-Ventana corrediza con marco de madera de 4
por 6 pies.
 PROBLEMA: Ambos productos
compiten compiten por la capacidad
de producción en una de las plantas
debido a esto se tenia que buscar la
forma de producción mas rentable

El equipo de Investigación de Operaciones (IO) que se encarga de

determinar las tasas de producción, considerando las restricciones de
capacidad de producción limitada en las tres plantas. Se harán en
lotes de 20 unidades y la producción se medirá por la cantidad de
lotes que se hacen por semana. Se puede hacer cualquier combinación
de tasas de producción, incluso no fabricar uno de los productos y
elaborar todo lo que sea posible del otro.
El equipo de IO también identifica los datos que necesita reunir para
resolver el problema.
·# de horas de producción
·# de horas de fabricación
·La ganancia por lote de cada producto nuevo.
PROBLEMA: Determinar las tasas de producción óptimas para los dos nuevos
productos, considerando las restricciones de capacidad de producción limitada
en las tres plantas.
Para resolver este problema, se formula como un PROBLEMA DE PROGRAMACIÓN
LINEAL, donde las decisiones son el número de lotes de los productos que se
fabricarán semanalmente, y se busca maximizar la ganancia total.
RESTRICCIONES
 CONTINUACIÓN DEL PROCESO DE
APRENDIZAJE CON OR COURSEWARW

Describe cómo el OR Courseware puede ser una

herramienta útil para aprender y aplicar los conceptos de
investigación de operaciones. Se menciona que el OR
Courseware incluye un programa llamado OR Tutor que
contiene un ejemplo de demostración completa del método
gráfico que se estudia en el documento. Además, se destaca
que el OR Courseware también incluye un programa
llamado IOR Tutorial que realiza muchos procedimientos
interactivos para ejecutar los diferentes métodos de solución
que se presentan en el libro, lo que permite que el lector se
enfoque en el aprendizaje y la ejecución de la lógico del
método en forma eficiente, mientras que la computadora
realiza los cálculos numéricos. También se menciona que el
OR Courseware es una introducción a los tres paquetes de
software comerciales que más se usan para resolver una
variedad de modelos de IO, incluidos Excel Solver,
LINGO/LINDO y MPL/CPLEX.
 3.2 MODELO DE
PROGRAMACIÓN LINEAL
La primera columna de la tabla
3.2 resume los componentes
del problema de la Wyndor
Glass Co. La segunda
introduce términos más
generales de estos
componentes, que se
ajustarán a muchos problemas
de programación lineal. Los
términos clave son recursos y
actividades en los que m
denota el número de tipos de
recursos que se pueden usar y
n el número de actividades
que se consideran.
FORMA ESTÁNDAR DEL
MODELO

OTRAS FORMAS
Cualquier problema que
incluye una, varias o todas
estas formas con las otras
partes del modelo anterior
también se clasifica como
un problema de
programación lineal.

 TERMINOLOGÍA DE LAS
SOLUCIONES DEL MODELO
Una solución factible es aquella para la que

todas las restricciones se satisfacen.

Una solución no factible es una solución para la
que al menos una restricción se viola.
Una solución óptima es una solución factible que
proporciona el valor más favorable de la función
objetivo.
El valor más favorable significa el valor más
grande si la función objetivo debe maximizarse,
o el valor más pequeño si la función objetivo
debe minimizarse.
Una solución factible en un vértice (FEV),
también conocidas como puntos extremos o
esquinases una solución que se encuentra en una
esquina de la región factible.

RELACIÓN ENTRE LAS SOLUCIONES

ÓPTIMAS Y LAS SOLUCIONES FEV:

El ejemplo tiene exactamente una

solución óptima, (x1, x2) = (2, 6), que es
FEV.
Cuando se modifica el ejemplo para que
tenga soluciones óptimas múltiples, dos
de
estas soluciones óptimas son soluciones
factibles en los vértices.

 3.3 SUPUESTOS DE
PROGRAMACIÓN LINEAL

1.Proporcionalidad: 2. Aditividad
Aunque el supuesto de
La proporcionalidad es un proporcionalidad elimina los
exponentes diferentes de uno, no
supuesto sobre la función prohíbe los términos de productos

objetivo y sobre las cruzados, términos que incluyen el

producto de dos o más variables. El
restricciones funcionales. supuesto de aditividad elimina esta
posibilidad.

 3.3 SUPUESTOS DE
PROGRAMACIÓN LINEAL

2. Aditividad
Aunque el supuesto de
proporcionalidad elimina los
1.Proporcionalidad:
La proporcionalidad es un exponentes diferentes de uno, no
supuesto sobre la función prohíbe los términos de productos
objetivo y sobre las cruzados, términos que incluyen el
restricciones funcionales. producto de dos o más variables. El

supuesto de aditividad elimina esta

posibilidad.

 3. Divisibilidad 4. Certidumbre
El siguiente supuesto se refiere a los
El último supuesto se refiere a los
valores permitidos para las variables de
parámetros del modelo, es decir, a
decisión.
Supuesto de divisibilidad: En un modelo los coeficientes cj, en la función
de programación lineal, las variables de objetivo, los coeficientes aij, en las
decisión pueden tomar cualquier valor, restricciones funcionales y los bi en
incluso valores no enteros, que el lado derecho de las restricciones
satisfagan las restricciones funcionales funcionales.
y de no negatividad. En consecuencia, Supuesto de certidumbre: Se
estas variables no están restringidas a supone que los valores
sólo valores enteros. Como cada variable
asignados a cada parámetro de
de decisión representa el nivel de
un modelo de programación
alguna actividad, se supondrá que las
actividades se pueden realizar a niveles lineal son constantes conocidas.
fraccionales.

 EL PROBLEMA DE
WYNDOR GLASS CO.
Comprende la asignación de recursos limitados.

Su modelo se ajusta a la forma estándar.

Contexto tradicional de planeación para

mejorar la administración.
3.4.EJEMPLO ADICIONAL
Desarrollaremos un problema de minimización, tiene una mezcla de
formas para proporcionar la fracción de dosis de radiación de cada
rayo en el punto de entrada que se absorbe en promedio en las
áreas respectivas. Por ejemplo, si el nivel de la dosis en el punto de
entrada del rayo 1 es 1 kilorad, se absorberán 0.4 kilorad en toda la
anatomía sana en el plano de dos dimensiones, un promedio de 0.3
kilorad en los tejidos críticos cercanos, un promedio de 0.5 kilorad
en las distintas partes del tumor y 0.6 kilorad en el centro del
tumor. En particular, la absorción promedio de la dosis por la
anatomía sana debe ser tan pequeña como sea posible, los tejidos
críticos no deben exceder 2.7 kilorads, el promedio sobre todo el
tumor debe ser igual a 6 kilorads y en el centro del tumor debe ser
por lo menos de 6 kilorads.
TABLA 3.7. DATOS PARA EL DISEÑO DEL TRATAMIENTO DE
RADIACIÓN DE MARY

X1 X2
 A TENER EN CUENTA......
1. Utilizaremos la "Programación lineal" (Método Símplex).

2. Sistema de Ecuaciones

a. Igualación

b. Eliminación

c. Sustitución
PRIMER PASO: Incógnitas: X1 , X2

SEGUNDO PASO: Función objetivo

Z = 0.4X1 + 0.5 X2 (Minimizar)

TERCER PASO:
Restricciones:

0.3X1 + 0.1X2 ≤ 2.7 1

X1 ≥ 0
0.5X1 + 0.5X2 = 6 2
X2 ≥ 0
0.6X1 + 0.4X2 ≥ 6 3
 CUARTO PASO: Conjunto de soluciones factibles

Si : X1 = 0 Si : X2 = 0
1 0.3X1 + 0.1X2 ≤ 2.7 0.3X1 + 0.1X2 ≤ 2.7
0.3(0) + 0.1X2 = 2.7 0.3X1 + 0.1(0) = 2.7
0.1X2 = 2.7 0.3X1 = 2.7
X2 = 2.7 / 0.1 X1 = 2.7 / 0.3
X2 = 27 X1 = 9

X1 = (9,0)
X2 = (0,27)
GRÁFICO: 0.3X1 + 0.1X2 ≤ 2.7
X2

15

14

13

12

11

10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 X1
 RESOLUCIÓN

Si : X1 = 0 Si : X2 = 0
2
0.5X1 + 0.5X2 = 6 0.5X1 + 0.5X2 = 6
0.5(0) + 0.5X2 = 6 0.5X1 + 0.5(0) = 6
0.5X2 = 6 0.5X1 = 6
X2 = 6 / 0.5 X1 = 6 / 0.5
X2 = 12 X1 = 12

X1 = (12,0)
X2 = (0,12)
GRÁFICO: 0.3X1 + 0.1X2 ≤ 2.7
X2

15

14

13

12

11

10

1 0.5X1 + 0.5X2 = 6

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 X1
 RESOLUCIÓN

Si : X1 = 0 Si : X2 = 0
3
0.6X1 + 0.4X2 ≥ 6 0.6X1 + 0.4X2 = 6
0.6(0) + 0.4X2 = 6 0.6X1 + 0.4(0) = 6
0.4X2 = 6 0.6X1 = 6
X2 = 6 / 0.4 X1 = 6 / 0.6
X2 = 15 X1 = 10

X1 = (10,0)
X2 = (0,15)
GRÁFICO: 0.3X1 + 0.1X2 ≤ 2.7
X2

15
0.6X1 + 0.4X2 ≥ 6
14

13

12

11

10

1 0.5X1 + 0.5X2 = 6

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 X1
GRÁFICO: 0.3X1 + 0.1X2 ≤ 2.7
X2

15
0.6X1 + 0.4X2 ≥ 6
14

13

12

11

10

1 0.5X1 + 0.5X2 = 6

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 X1
 SISTEMA DE ECUACIONES

1 0.3X1 + 0.1X2 = 2.7 ... (x5) 0.3X1 + 0.1X2 = 2.7

2 0.5X1 + 0.5X2 = 6 ... (x-1) 0.3(7.5) + 0.1X2 = 2.7
1.5X1 + 0.5X2 = 13.7 2.25 + 0.1X2 = 2.7
-0.5X1 - 0.5X2 = -6 0.1X2 = 2.7 - 2.25
0.1X2 = 0.45
1.0X1 = 7.5
X2 = 0.45/0.1
X1 = 7.5 / 1.0 X2 = 4.5
X1 = 7.5

X1 = 7.5
X2 = 4.5
 SISTEMA DE ECUACIONES

2 0.5X1 + 0.5X2 = 6 ... (x6) 0.5X1 + 0.5X2 = 6

3 0.6X1 + 0.4X2 = 6 ... (x-5) 0.5X1 + 0.5(6) = 6
3X1 + 3X2 = 36 0.5X1 + 3 = 6
-3X1 - 2X2 = -30 0.5X1 = 6 - 3
0.5X1 = 3
1X2 = 6
X1 = 0.5/3
X2 = 6 / 1 X1 = 6
X2 = 6

X1 = 6
X2 = 6
GRÁFICO: 0.3X1 + 0.1X2 ≤ 2.7
X2

15 0.6X1 + 0.4X2 ≥ 6

14

13

12

11

10

8
(6,6)
7

6 (7.5,4.5)
5

1 0.5X1 + 0.5X2 = 6

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 X1
QUINTO PASO: Funcion objetivo del valor mínimo

1 f(7.5,4.5) = 0.4X1 + 0.5X2

f(7.5,4.5) = 0.4(7.5) + 0.5(4.5)
f(7.5,4.5) = 3 + 2.25
f(7.5,4.5) = 5.25
2
f(6,6) = 0.4X1 + 0.5X2
f(6,6) = 0.4(6) + 0.5(6)
f(6,6) = 2.4 +3
f(6,6) =5.4 VALOR MÍNIMO
GRÁFICO: 0.3X1 + 0.1X2 ≤ 2.7
X2

15
0.6X1 + 0.4X2 ≥ 6 Entonces el diseño
14
óptimo implica utilizar
13
una dosis total
12 en el punto óptimo de
11 7.5 kilorads para el
10 rayo 1 y 4.5 kilorads
9 para el rayo 2
8
(6,6)
7

6 (7.5,4.5)
5
Z = 0.4X1 + 0.5X2 = 5.25
4

1 0.5X1 + 0.5X2 = 6

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 X1
 3.5 FORMULACION Y
SOLUCION DE MODELOS DE
PROGRAMACION LINEAL
EN UNA HOJA DE CALCULO

Los paquetes de hojas de cálculo, como Excel, son una

herramienta conocida para analizar y resolver
problemas pequeños de programación lineal. Es
sencillo introducir en una hoja de cálculo las
características principales de un modelo de
programación lineal, entre ellas, todos sus
parámetros.
 Formulación del modelo en una hoja de
cálculo
SE PUEDE OBSERVAR QUE SE HA FACILITADO SU INTERPRETACIÓN MEDIANTE EL EMPLEO DE NOMBRES DE RANGO.
UN NOMBRE DE RANGO ES EL TÍTULO DESCRIPTIVO QUE SE DA A UN CONJUNTO DE CELDAS QUE DE INMEDIATO
IDENTIFI CA LO QUE ÉSTAS CONTIENEN. ASÍ, LAS CELDAS DE DATOS EN EL PROBLEMA DE WYNDOR HAN RECIBIDO
LOS NOMBRES DE RANGO GANANCIA UNITARIA (C4:D4), HORAS USADAS POR LOTEPRODUCIDO (C7:D9), Y HORAS
DISPONIBLES (G7:G9).
En la siguiente figura se muestra la forma como estas respuestas se pueden incorporar a una hoja de cálculo.
Con base en la primera respuesta, las tasas de producción de los dos productos se colocan en las celdas C12 y
D12 para ubicarlas en las columnas de estos productos justo debajo de las celdas de datos. Como aún no se
sabe cuáles deben ser las tasas de producción, en este punto se introducen sólo como ceros. Estos números
cambiarán a medida que se busca la mejor mezcla de tasas de producción. Por ello, las celdas que contienen
las decisiones
La esquina inferior derecha de la figura
muestra las fórmulas que deben
introducirse en la columna de Horas
Usadas y en la celda de Ganancia Total.
También se presenta un resumen de los
nombres de rango (en orden alfabético) y
las direcciones de celda correspondientes.
Lo anterior completa la formulación del
modelo en una hoja de cálculo del
problema de Wyndor. Con esta
formulación es sencillo analizar cualquier
solución de prueba para las tasas de
producción.
 3.6 CONSTRUCCIÓN DE
MODELOS GRANDES DE Los modelos de programación lineal son de muchos
tamaños diferentes. Los ejemplos de las diapositivas
PROGRAMACIÓN LINEAL anteriores oscilan desde tres restricciones funcionales
y dos variables de decisión —para la
Wyndor y la terapia de radiación— hasta 17
restricciones funcionales y 12 variables de decisión —
en el problema de Save-It Company—. El último caso
puede parecer un modelo algo grande.
Después de todo, lleva bastante tiempo elaborar uno
de este tamaño. Sin embargo, los modelos de los
recuadros de aplicación que se presentan en este
capítulo son mucho más grandes. Por ejemplo, el
modelo para la aplicación de United Airlines en la
sección 3.4 tiene más de 20 000 variables de
decisión.
CONCLUSIONES
IT'S TIME!