UNIVERSIDAD NACIONAL DE SAN AGUSTÍN DE AREQUIPA

FACULTAD DE INGENIERÍA DE PRODUCCIÓN Y SERVICIOS

ESCUELA PROFESIONAL DE INGENIERÍA ELÉCTRICA

MÉTODOS ESTADÍSTICOS PARA LA INGENIERÍA

PROGRAMACIÓN LINEAL

ALUMNO:
ACO MENDOZA, Angelito Rosendo

AREQUIPA-2017
1. Generalidades

La programación lineal es el campo de la optimización matemática dedicado

a maximizar o minimizar (optimizar) 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 expresadas mediante un sistema de ecuaciones o
inecuaciones también lineales. El método tradicionalmente usado para resolver
problemas de programación lineal es el Método Simplex.
El desarrollo de computadoras electrónicas de procesamiento de alta
velocidad ha aportado recientemente muchos avances a la programación lineal,
de forma que ahora esta técnica se utiliza extensamente en operaciones
industriales y militares.
A lo largo de la historia han existido diversos acontecimientos importantes
relativos a la programación lineal, como son estos:

 Durante la Segunda Guerra Mundial se mantuvo en secreto y fue utilizada

como mecanismo para poder gestionar y planificar todos los gastos. De
esta manera se pretendía, gestionar mejor los recursos propios y reducir
lo máximo posible lo que eran los costos del ejército.
 Tres se consideran sus padres o creadores: el húngaro-estadounidense
John von Neumann, el profesor norteamericano George Dantzig y el
matemático de origen ruso Leonid Kantoróvich, que recibió el Premio
Nobel de Economía en 1975.

1.1. Historia de la programación lineal

El problema de la resolución de un sistema lineal de inecuaciones se remonta,

al menos, a Joseph Fourier, después de quien nace el método de eliminación de
Fourier-Motzkin. La programación lineal se plantea como un modelo matemático
desarrollado durante la Segunda Guerra Mundial para planificar los gastos y los
retornos, a fin de reducir los costos al ejército y aumentar las pérdidas del
enemigo. Se mantuvo en secreto hasta 1947. En la posguerra, muchas industrias
lo usaron en su planificación diaria.
Los fundadores de la técnica son George Dantzig, quien publicó el algoritmo
simplex, en 1947, John von Neumann, que desarrolló la teoría de la dualidad en
el mismo año, y Leonid Kantoróvich, un matemático de origen ruso, que utiliza
técnicas similares en la economía antes de Dantzig y ganó el premio Nobel en
economía en 1975. En 1979, otro matemático ruso, Leonid Khachiyan, diseñó el
llamado Algoritmo del elipsoide, a través del cual demostró que el problema de la
programación lineal es resoluble de manera eficiente, es decir, en tiempo
polinomial. Más tarde, en 1984, Narendra Karmarkar introduce un nuevo método
del punto interior para resolver problemas de programación lineal, lo que
constituiría un enorme avance en los principios teóricos y prácticos en el área.
El ejemplo original de Dantzig de la búsqueda de la mejor asignación de 70
personas a 70 puestos de trabajo es un ejemplo de la utilidad de la programación
lineal. La potencia de computación necesaria para examinar todas las
permutaciones a fin de seleccionar la mejor asignación es inmensa (factorial de
70, 70!) ; el número de posibles configuraciones excede al número de partículas
en el universo. Sin embargo, toma sólo un momento encontrar la solución
óptima mediante el planteamiento del problema como una programación lineal y
la aplicación del algoritmo simplex. La teoría de la programación lineal reduce
drásticamente el número de posibles soluciones factibles que deben ser
revisadas.

1.2. Elementos de la programación lineal

 Variables: Las variables son números reales mayores o iguales a cero.

X i =≥ 0

En caso que se requiera que el valor resultante de las variables sea un

número entero, el procedimiento de resolución se denomina Programación
entera.
 Restricciones: Las restricciones pueden ser de la forma:

N
Tipo 1: A j=∑ Ai , j × X i
i=1
N
Tipo 2: B j ≤ ∑ Bi , j × X i
i=1
N
Tipo 3: C j=∑ C i , j × X i
i=1

Dónde:
A = valor conocido a ser respetado estrictamente;
B = valor conocido que debe ser respetado o puede ser superado;
C = valor conocido que no debe ser superado;
j = número de la ecuación, variable de 1 a M (número total de restricciones);
a; b; y, c = coeficientes técnicos conocidos;
X = Incógnitas, de 1 a N;
i = número de la incógnita, variable de 1 a N.
En general no hay restricciones en cuanto a los valores de N y M. Puede
ser N = M; N > M; ó, N < M. Sin embargo si las restricciones del Tipo 1 son N, el
problema puede ser determinado, y puede no tener sentido una optimización.
Los tres tipos de restricciones pueden darse simultáneamente en el mismo
problema.

 Función Objetivo: La función objetivo puede ser:

N
Max !=∑ fi∗x i
i=1
 N
Min!=∑ fi∗xi
i=1

Donde f i=¿ Coeficientes

1.3. Programación entera

En algunos casos se requiere que la solución óptima se componga de valores

enteros para algunas de las variables. La resolución de este problema se obtiene
analizando las posibles alternativas de valores enteros de esas variables en un
entorno alrededor de la solución obtenida considerando las variables reales.
Muchas veces la solución del programa lineal truncado está lejos de ser el
óptimo entero, por lo que se hace necesario usar algún algoritmo para hallar esta
solución de forma exacta. El más famoso es el método de 'Ramificar y Acotar' o
Branch and Bound por su nombre en inglés. El método de Ramificar y Acotar
parte de la adición de nuevas restricciones para cada variable de decisión
(acotar) que al ser evaluado independientemente (ramificar) lleva al óptimo
entero.

1.4. Pasos para formular un Modelo de Programación Lineal

 Identificación de las variables de decisión

 Identificación de los datos del problema
 Identificación de la función (objetivo)
 Identificación de las restricciones

1.5. Desigualdades Lineales

Una línea recta queda determinada por la unión de dos puntos, manteniendo
la misma dirección.

Una función
lineal puede ser expresada de las siguientes formas:
 𝑦=𝑚𝑥+𝑏 Ecuación pendiente ordenada en el origen
𝑎𝑥+𝑏𝑦+𝑐=0 Ecuación general
Ejemplo: La ecuación de la recta 2𝑥+3𝑦−6=0 , puede expresarse así:

2𝑥+3𝑦=6
𝑦=−2/3𝑥+2
Dónde:
𝑚=−2/3 Pendiente de la recta
𝑏=2 Punto de corte de la recta con el eje "𝑦"

2. Algoritmo Simplex

El algoritmo Simplex es un método analítico de solución de problemas de

programación lineal capaz de resolver modelos más complejos que los resueltos
mediante el método gráfico sin restricción en el número de variables.
El algoritmo Simplex es un método iterativo que permite ir mejorando la solución
en cada paso. La razón matemática de esta mejora radica en que el método
consiste en caminar del vértice de un poliedro a un vértice vecino de manera que
aumente o disminuya (según el contexto de la función objetivo, sea maximizar o
minimizar), dado que el número de vértices que presenta un poliedro solución es
finito siempre se hallará solución.
Este famosísimo método fue creado en el año de 1947 por el estadounidense
George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich, con el ánimo de
crear un algoritmo capaz de solucionar problemas de m restricciones y n
variables.
Una matriz puede definirse como una ordenación rectangular de elementos,
(o listado finito de elementos), los cuales pueden ser números reales o
complejos, dispuestos en forma de filas y de columnas.
La matriz idéntica o identidad es una matriz cuadrada (que posee el mismo
número tanto de columnas como de filas) de orden n que tiene todos los
elementos diagonales iguales a uno (1) y todos los demás componentes iguales a
cero (0), se denomina matriz idéntica o identidad de orden n, y se denota por:

1 … 0 1 0 0
(
ln= ⋮ ⋱ ⋮
0 … 1 )nxn
l 2=
1 0
( )
0 1 2x 2 ( )
l 3= 0 1 0
0 0 1 3 x3

La importancia de la teoría de matrices en el algoritmo Simplex es fundamental,

dado que el algoritmo se basa en dicha teoría para la resolución de sus
problemas.
Ejemplo:
“La empresa el SAMÁN Ltda. Dedicada a la fabricación de muebles, ha ampliado
su producción en dos líneas más. Por lo tanto actualmente fabrica mesas, sillas,
camas y bibliotecas. Cada mesa requiere de 2 piezas rectangulares de 8 pines, y
2 piezas cuadradas de 4 pines. Cada silla requiere de 1 pieza rectangular de 8
pines y 2 piezas
cuadradas de 4 pines, cada cama requiere de 1 pieza rectangular de 8 pines, 1
cuadrada de 4 pines y 2 bases trapezoidales de 2 pines y finalmente cada
biblioteca requiere de 2 piezas rectangulares de 8 pines, 2 bases trapezoidales
de 2 pines y 4 piezas rectangulares de 2 pines. Cada mesa cuesta producirla
$10000 y se vende en $ 30000, cada silla cuesta producirla $ 8000 y se vende
en $ 28000, cada cama cuesta producirla $ 20000 y se vende en $ 40000, cada
biblioteca cuesta producirla $ 40000 y se vende en $ 60000. El objetivo de la
fábrica es maximizar las utilidades.”

a)PASO 1: MODELACIÓN MEDIANTE PROGRAMACIÓN LINEAL

Las variables:

X 1 = Cantidad de mesas a producir (unidades)

X 2 = Cantidad de sillas a producir (unidades)
X 3 = Cantidad de camas a producir (unidades)
X 4= Cantidad de bibliotecas a producir (unidades)

Las restricciones:

2 X 1 + 1 X 2 + 1 X 3 + 2 X 4 <= 24
2 X 1 + 2 X 2 + 1 X 3 <= 20
2 X 3 + 2 X 4 <= 20
4 X 4 <= 16

La función Objetivo:

ZMAX = 20000 X 1 + 20000 X 2 + 20000 X 3 + 20000 X 4

b)PASO 2: CONVERTIR LAS INECUACIONES EN ECUACIONES

En este paso el objetivo es asignar a cada recurso una variable de Holgura, dado
que todas las restricciones son "<=".

2 X 1 + 1 X 2 + 1 X 3 + 2 X 4 + 1 S1 + 0 S2 + 0 S3 + 0 S4 = 24
2 X 1 + 2 X 2 + 1 X 3 + 0 X 4 + 0 S1 + 1 S2 + 0 S3 + 0 S4 = 20
0 X 1 + 0 X 2 + 2 X 3 + 2 X 4 + 0 S1 + 0 S2 + 1 S3 + 0 S4 = 20
0 X 1 + 0 X 2 + 0 X 3 + 4 X 4 + 0 S1 + 0 S2 + 0 S3 + 1 S4 = 16

De esta manera podemos apreciar una matriz identidad (n = 4), formado

por las variables de holgura las cuales solo tienen coeficiente 1 en su respectivo
recurso, por el ejemplo la variable de holgura " S1" solo tiene coeficiente 1 en la
restricción correspondiente a el recurso 1.
La función objetivo no sufre variaciones:

ZMAX = 20000 X 1 + 20000 X 2 + 20000 X 3 + 20000 X 4

c) PASO 3: DEFINIR LA SOLUCIÓN BÁSICA INICIAL

El Algoritmo Simplex parte de una solución básica inicial para realizar todas
sus iteraciones, esta solución básica inicial se forma con las variables de
coeficiente diferente de cero (0) en la matriz identidad.

1 S1 = 24
1 S2 = 20
1 S3 = 20
1 S4 = 16

d)PASO 4: DEFINIR LA TABLA SIMPLEX INICIAL

Solución: (segundo término)= En esta fila se consigna el segundo término de la

solución, es decir las variables, lo más adecuado es que estas se consignen de
manera ordenada, tal cual como se escribieron en la definición de restricciones.
 C j = La fila "C j" hace referencia al coeficiente que tiene cada una de las variables
de la fila "solución" en la función objetivo.
Variable Solución = En esta columna se consigna la solución básica inicial, y a
partir de esta en cada iteración se van incluyendo las variables que formarán
parte de la solución final.
C b = En esta fila se consigna el valor que tiene la variable que se encuentra a su
derecha "Variable solución" en la función objetivo.
Z j = En esta fila se consigna la contribución total, es decir la suma de los
productos entre término y C b.
Cj - Zj = En esta fila se realiza la diferencia entre la fila C j y la fila Z j, su
significado es un "Shadow price", es decir, la utilidad que se deja de recibir por
cada unidad de la variable correspondiente que no forme parte de la solución.
Solución inicial:

e)PASO 5: REALIZAR LAS ITERACIONES NECESARIAS

Este es el paso definitivo en la resolución por medio del Método Simplex, consiste
en realizar intentos mientras el modelo va de un vértice del poliedro objetivo a
otro.
El procedimiento a seguir es el siguiente:
i. Evaluar que variable entrará y cual saldrá de la solución óptima:
ii. El hecho de que una variable distinta forme parte de las variables solución
implica una serie de cambios en el tabulado Simplex, cambios que se
explicarán a continuación. Lo primero es no olvidar el valor del "a"
correspondiente a la variables a entrar, en este caso el "a = 4".
iii.
iii.
iii.
iii.
iii.
iii.
iii.
iii.
iii.
iii.
iii.
iii.
iii.
iii.
iii.
Lo siguiente es comenzar a rellenar el resto de la tabla, fila x fila.
iv. Se repite este procedimiento con las dos filas restantes, ahora se harán los
cálculos correspondientes en el resto de las celdas.

v. De
esta manera se culmina la primera iteración, este paso se repetirá cuantas
veces sea necesario y solo se dará por terminado el método según los

siguientes criterios.

vi. Continuamos con las iteraciones para lo cual tenemos que repetir los pasos
anteriores.
En esta última iteración podemos observar que se cumple con la consigna C j - Z j
<= 0, para ejercicios cuya función objetivo sea "Maximizar", por ende hemos
llegado a la respuesta óptima.

X1 = 3
X2 = 4
X3 = 6
X4 = 4
Con una utilidad de: $ 340000

3. Aplicación en Ingeniería Eléctrica

Ejemplo: Planificación de la generación de energía eléctrica

Una empresa de producción, transporte y distribución de energía eléctrica está
estudiando la evolución de su demanda, de potencia y de energía, y cómo
satisfacer su incremento los próximos 10 años.
El mercado tecnológico dispone de cuatro formas consolidadas y aceptadas de
generar electricidad a gran escala: centrales termoeléctricas de gas natural,
centrales hidráulicas, aerogeneradores y centrales de carbón.

El patrón de su demanda eléctrica futura está definido por:

 El consumo anual adicional de energía, estimado en 1.750 TWh (1 TWh
=109 kWh) para el conjunto de los diez años;
 La demanda máxima de potencia adicional, estimada en 30 GW (1
GW=106kW) para el año número 10;
 La potencia diaria media demandada en un día de invierno, estimándose
que crecerá en 20 GW para el año número 10.

Los parámetros esenciales de las centrales contempladas son estos.

4. Bibliografía

 Recuperado de [Link]
economica/programacion-lineal
 Recuperado de
[Link]
[Link]
 Recuperado de [Link]
 Recuperado de
[Link]
_lineal_lbc/didactico_pl.htm
 Recuperado de [Link]
para-el-ingeniero-industrial/investigaci%C3%B3n-de-operaciones/m
%C3%A9todo-simplex/