1

MONOGRAFA

PROGRAMACION LINEAL



INTEGRANTES:

lvarez Tapore, Iris
Caballero Glvez, David
Chvez Curo, Evelyn

ASESOR:

SONIA ELSELINA FERNANDEZ LPEZ


LNEA DE INVESTIGACIN:




LIMA - PER

2014
2











Dedicatoria

A nuestros Padres, por la confianza que
depositan en nosotros cada da, aplaudir
nuestros triunfos e incentivarnos a alcanzar
nuestros objetivos.

















3











Agradecimiento

Agradecemos a Dios por darnos la vida y a
nuestros profesores por sus enseanzas, en
especial a la profesora Sonia Fernndez Lpez,
por guiarnos en este trabajo de investigacin.


4

NDICE
Caratula1
Dedicatoria..2
Agradecimiento...................3
ndice...4
Introduccin5

I. Programacin lineal.6
1.1 introduccin a la investigacin de operaciones...6
1.1.1 Definicin..6
1.1.2 Clasificacin ...7
1.1.3 Mtodo...7

1.2 Introduccin a la programacin Lineal8
1.2.1 Modelo Matemtico9

1.3 El Mtodo grfico.10

1.4 El Mtodo Simplex...15
1.4.1. El Mtodo Simplex algebraico..16
1.4.2. El Mtodo Simplex en forma Tabular..23

1.5 Anlisis de sensibilidad.29
1.5.1. Cambio en el coeficiente en la funcin objetivo de una
variable no bsica. 33
1.5.2. Cambio en el coeficiente en la funcin objetivo de una
variable bsica..34
Conclusiones...34
Bibliografa..35
5

INTRODUCCION

Qu es programacin lineal? Para qu sirve? Cul es su futuro en las
industrias y empresas? En el presente trabajo de investigacin vamos a dar
respuesta estas interrogantes y explicaremos en cmo plantear un problema,
los mtodos que podemos utilizar y finalmente veremos cmo hacer un anlisis
de sensibilidad.

Este tema es importante debido que la programacin lineal ha sido
considerado como uno de los avances cientficos ms importantes de
mediados de siglo XX, que se utiliza en muchas empresas, compaas y
negocios, por otro lado como futuros ingenieros industriales es necesario que
tengamos este conocimiento para estar aptamente capacitados cuando nos
desempeemos laboralmente y tengamos que aplicar estos conceptos para la
solucin de los diferentes tipos de problemas que ocurren en las empresas.

A medida que vayamos analizando los diferentes subtemas, nos daremos
cuenta que la Programacin Lineal es una de las herramientas ms
importantes de la Investigacin Operativa; por lo que vale la pena estudiarla
con mucho inters de aprender.








6

CAPITULO I
PROGRAMACION LINEAL


1.1 Introduccin a la investigacin de Operaciones
1.1.1 Definicin
Aunque muchos de nosotros hemos escuchado hablar o ledo alguna
vez sobre la Investigacin Operativa; sin embargo muy pocos sabemos
en realidad En qu consiste? Veamos algunas definiciones dadas al
respecto:

"La investigacin de operaciones puede definirse como un grupo de
mtodos y tcnicas aplicables a la solucin de problemas operativos
de los sistemas" (Isar, 1996, p. 11).

La ciencia que estudia el modelado de sistemas probabilsticos y
determinsticos que se originan en la vida real desde un punto de vista
de toma de decisiones optimas (Hillier y Lieberman, 1990).

Un mtodo cientfico para dotar a los departamentos ejecutivos de
una base cuantitativa para las decisiones que tengan que ver con las
operaciones bajo su control (McCord y Kimball, 1951).


En resumen podemos decir que la investigacin de operaciones es la
ciencia que estudia las tcnicas aplicables a la solucin de problemas que
nos permita tomar la decisin ms ptima posible.







7

1.1.2 Clasificacin
Los problemas que aborda la Investigacin Operativa se pueden
clasificar de diferentes formas.

Atendiendo la certidumbre de los
datos
Determinsticos (datos son conocidos)
Probabilsticos (datos son inciertos)
Hibrido (combinacin de los anteriores)
Segn el objetivo del problema
Optimizacin(maximizar o minimizar):
- Secuenciacin
- Asignacin
- Rutas
- Bsqueda de informacin
Prediccin:
- Sustitucin
- Inventario
- Lneas de espera
- Teora de juegos


1.1.3 Mtodo
En cuanto al mtodo que emplea esta ciencia, puede resumirse en los
siguientes pasos:

1. Anlisis de la realidad y formulacin del problema
2. Modelado matemtico y representativo
3. Resolucin del modelo
4. Presentacin de resultados
5. Implementacin de resultados








8

1.2 Introduccin a la Programacin Lineal
Actualmente la toma de decisiones es inherente a la mayora de los
aspectos de las finanzas, la empresa, industria, economa e instituciones de
gobierno. Una buena prctica en la gestin y organizacin de las empresas,
son las decisiones basados en modelos; para lo cual una de las herramientas
que nos proporciona decisiones mas fiables es la optimizacin. La
optimizacin se refiere al anlisis y resolucin de problemas en que se debe
tomar una solucin entre un conjunto de soluciones factibles, con el objetivo
de encontrar la mejor solucin y esta se compara de acuerdo a la funcin
objetivo. Al respecto una de las reas mas importantes y activas de la
optimizacin es la Programacin Lineal.

Si queremos definir qu es la Programacin Lineal, podemos decir que Es
una rama de la Programacin matemtica que estudia problema de
optimizacin en los cuales se desea maximiza o minimizar una funcin
restringida mediante ecuaciones o desigualdades lineales (Hernndez, 2007,
p. 33).

En efecto la programacin lineal es una clase de modelos matemticos en
la que se busca asignar de manera eficiente los recursos que muchas veces
son escasos o limitados (materiales, mquinas, tiempo, capital, etc.), con el fin
de minimizar los costos y maximizar las ganancias.

En general tiene gran aplicacin en una amplia variedad de contextos que
incluyen los siguientes dos grupos especiales: las redes de distribucin de
mercanca, servicios de agua y energa, as como de personal; otro grupo de
aplicacin son las redes de flujo, en las que se tienen diversos lugares a
comunicar mediante algn medio (rama) por el cual se transportan unidades,
que tambin pueden ser bienes, servicios, informacin y personas.





9

1.2.1 Modelo Matemtico
Para construir un modelo matemtico de programacin lineal, se
tiene que cumplir de forma obligatoria con los siguientes pasos:
a) FUNCION OBJETIVO, nos indica el objetivo que queremos
alcanzar. Cuando hablamos de optimizar una funcin objetivo
hablamos de maximizar o minimizar.

b) RESTRICCIONES DEL MODELO, son las limitaciones o
requerimientos que forman el entorno de la empresa que estamos
estudiando. Las expresiones que encontraremos al final de estas
restricciones son las siguientes:

Entonces hablamos de limitaciones o disponibilidades
mximas (Materia prima, mano de obra, maquinaria, etc.).

Entonces hablamos de requerimientos (exigencias legales
tcnicas, etc. que la empresa deber cumplir).

c) LA CONDICION DE NO NEGATIVIDAD, nos indica que todas las
variables tienen que ser no negativas, es decir mayores o iguales
a cero, ya que en caso de no serlo, la solucin al modelo no sera
factible, puesto que cada variable nos indica la cantidad de cada
producto a producir por la empresa y, por tanto, como mnimo la
empresa no producir nada.

Para construir un modelo matemtico tenemos dos formas que son:
- Cannico, cuando la funcin objetivo se maximiza, las
restricciones de los recursos son presentados por desigualdades
menor o igual a los recursos limitados () y todas las variables de
decisin deben ser mayores que cero.

10

- Estndar, todas las restricciones del problema deben ser
igualdades, las variables de decisin no deben ser negativas y la
funcin objetivo puede ser maximizacin o de minimizacin.
Por ejemplo:
Forma cannica
Maximizar P= 3X + 2Y
Sujeto a: 2X + 3Y 12
2X + Y 8
X, Y 0

Forma estndar

2X + 3Y + h1 = 12
2X + Y + h2 = 8
P - 3X 2Y + h3 =0


1.3 El mtodo grfico:
Es un mtodo de solucin para resolver problemas de programacin lineal,
solo resulta eficiente en el plano cartesiano, es decir para un espacio de
dimensin. Correspondientes a las restricciones en coordenadas cartesianas,
siendo cada variable representada en uno de los ejes, de tal forma que quede
perfectamente delimitada la zona factible de solucin, procedindose
entonces a tratar de localizar en ella al punto que optimice la funcin objetivo.
Este mtodo es muy limitado en cuanto al nmero de variables pero muy rico
en materia de interpretacin de resultados e incluso en anlisis de
sensibilidad.
El mtodo grfico lo podemos resolver siguiendo los siguientes pasos:
11

Se igualan las restricciones.
Se grafican las ecuaciones, obteniendo la tabla de valores
correspondientes.
Se representan grficamente ambas rectas en los ejes coordenados.
El objetivo de la solucin grfica es encontrar todos los puntos del conjunto
factible, el punto o los puntos que optimicen la funcin objetivo.
A fin de poder entender bien este mtodo es importante que tengamos
presente los siguientes conceptos:

- Conjunto factible: Es el conjunto de puntos que integran la regin
de resolucin.
- Solucin factible: Cada punto que integra la regin (plana) que
resuelve el problema.
- Solucin ptima: Constituye la solucin al problema de
programacin lineal.

Ejemplo:
Maximizar P= 3X + 2Y
Sujeto a: 2X + 3Y 12
2X + Y 8
X, Y 0
Paso 1: se igualan las restricciones
2X + 3Y = 12
2X + Y = 8
Paso 2: Se grafican las ecuaciones, obteniendo la tabla de valores
correspondientes:
12

Para la ecuacin 1
2X + 3Y = 12



x Y
0 4
6 0
Para la ecuacin 2
2X + Y = 8



x Y
0 8
4 0
Con estos puntos obtendremos la siguiente grfica.


El rea sombreada de turquesa es la que corresponde al conjunto
factible, cada punto que contiene el conjunto factible es un candidato
para resolver el problema.

13




Paso 3: Identifica las coordenadas de todas las esquinas (vrtices) del
conjunto factible.

Para poder encontrar las coordenadas del punto B tienes que resolver el
sistema de ecuaciones conformado por las dos ecuaciones anteriores
2X + 3Y = 12 y 2X + Y = 8
Utilizaremos el mtodo de sustitucin.
2X + 3Y = 12 Ecuacin 1
2X + Y = 8 Ecuacin 2
Se despeja Y de la ecuacin 2
Y= 8 - 2X
Se sustituye el valor de Y en la ecuacin 1
2 X + 3 (8 2X) = 12

14

Se resuelve la ecuacin para encontrar el valor de X.
2 X + 24 6 X = 12
-4 X = 12 24
-4 X = -12
X= -12/-4
X =3
Sustituye el valor de X en el despeje que hiciste en el paso 1.
Y = 8 2(3)
Y= 8 6
Y= 2
Y con esto se obtiene el resultado del vrtice B (3,2)

Paso 4: Sustituir el valor de cada una de ellas en la funcin objetivo, para
encontrar el valor mximo (o mnimo, segn sea el caso).
Sustituyendo el valor del vrtice A en la funcin objetivo: P = 3X + 2 Y
Vrtice A (0,4)
3 X + 2 Y = P
3 (O) + 2 (4) = 8
Vrtice B (3,2)
3 X + 2 Y = P
3 (3) + 2 (2) = 13
Vrtice (4,0)
3 X + 2 Y = P
3 (4) + 2 (0) = 12
15

Resultados:
Vrtice A (0,4) Valor = 8
Vrtice B (3,2) Valor =13
Vrtice C (4,0) Valor = 12
Observando los resultados podemos concluir que el mximo se
encuentra en el vrtice B.

1.4 El mtodo Simplex:

Anteriormente utilizamos el mtodo grafico para resolver problemas de dos
variables, sin embargo en la vida real pocos casos tienen solo dos variables,
por lo que es importante contar con herramientas que nos permitan resolver
modelos con ms variables.

En 1947 el matemtico norteamericano Jorge Dantzig desarrollo un
algoritmo para resolver problemas de programacin lineal de dos o ms
variables conocido como el mtodo simplex.

Frederick, hiller y Gerald, Liberman (2010, p.81) indican que el mtodo
simplex es Un procedimiento algebraico. Sin embargo sus conceptos
fundamentales son geomtricos. La comprensin de estos conceptos
proporciona una fuerte intuicin sobre la forma en que opera el mtodo simple
y las razones de su elevada eficiencia. Por lo tanto podemos decir que este
mtodo es un procedimiento de clculo algebraico, iterativo que se utiliza para
solucionar problemas de programacin lineal ms complejos que los resueltos
mediante el mtodo grfico ya que no tiene restriccin en el nmero de
variables ni restricciones.

Este mtodo es otra de las herramientas importantes con que cuenta la
investigacin de operaciones para apoyar la toma de decisiones cuantitativas.
Sin embargo una observacin importante sobre este mtodo es que puede
16

ser muy sensible a errores de redondeo, dado que se llevan a cabo gran
cantidad de operaciones. Para evitar este tipo de errores, se recomiendan dos
acciones:

1. Utilizar el redondeo simtrico con la cantidad de decimales adecuados
a la magnitud de las variables de decisin.
2. Realizar las operaciones con fracciones.
.
1.4.1 El Mtodo Simplex en Forma Algebraica.
En la necesidad de desarrollar un mtodo para resolver problemas
de programacin lineal de ms de dos variables, los matemticos
implementaron el mtodo algebraico, el que ms tarde se convertira en
el tan afamado mtodo simplex.

Como su nombre lo indica, el mtodo usa como su principal
herramienta, el lgebra, que ligada a un proceso de lgica
matemtica dio como resultado el mtodo algebraico.
Algoritmo del mtodo Algebraico:
1) Hallar una solucin bsica y factible (Solucin inicial).
- Expresar las inecuaciones (desigualdades) como
ecuaciones (igualdades).
- Hallar una variable bsica para cada ecuacin.
- Organizar el sistema de ecuaciones lineales

2) Escoger la variable que entra.
3) Escoger la variable que sale.
4) Reorganizar el sistema de ecuaciones.
5) Repetir los pasos 2, 3 y 4 hasta encontrar la solucin.

A continuacin vamos a desarrollar un ejercicio siguiendo los pasos
antes mencionados.

17

Ejemplo:
Maximizar Z = X1 + X2
S.A:
5X1 + 3X2 15
3X1 + 5X2 15

1) Hallar una solucin bsica y factible (Solucin inicial).
- Expresar todas las inecuaciones como ecuaciones lineales, para
ello usamos variables de holgura, para igualar el lado izquierdo al
lado derecho de la inecuacin.

5X1 + 3X2 15 3X1 + 5X2 15
3X1 + 5X2 + X4 = 15 5X1 + 3X2 + X3 = 15

Aqu X3 y X4 son las variables de holgura o relleno, que al
adicionarlas al lado izquierdo, establecen la igualdad con el lado
derecho de la inecuacin lineal.
Las variables X1 y X2 se denominan variables de decisin o
variables reales, las variables de relleno o holgura, se usan para
convertir una inecuacin en una ecuacin.

- Escoger en cada ecuacin una variable que sirva como solucin
inicial al problema y que tome un valor positivo ( > 0), NO son
elegibles las variables de decisin o variables reales. Entonces, las
variables de holgura o relleno (si las hay), son las primeras
opcionadas a ser escogidas como variables bsicas y factibles, lo
que significa que deben tomar un valor mayor o igual a cero ( > 0),
dicho de otra forma, las variable bsicas factibles, deben cumplir
con la condicin de no negatividad. De no conseguirse una variable
de holgura que sea factible, se utiliza el recurso de las variables de
sper-avit o artificiales, pero de ste caso nos ocuparemos en el
segundo ejemplo, para el que usaremos el denominado mtodo de
la gran M. Aqu tanto X3 como X4 , variables de holgura, son
18

escogidas como variables bsicas factibles, ya que ambas asumen
valores positivos al ser X1 y X2 variables no bsicas e iguales a
cero (0), esto es:

5X1 + 3X2 + X3 = 15 3X1 + 5X2 + X4 = 15
X1 = X2 = 0, entonces X1 = X2 = 0, entonces
X3 = 15, valor 0 X4 = 15, valor 0
- Organizamos el sistema de ecuaciones de la siguiente manera:
z X1 - x2 = 0
5 X1 + 3X2 + X3 = 15
3X1 + 5X2 X4 = 15

Fjese que en cada ecuacin existe una y solo una variable bsica con
coeficiente ( 1 ), lo que permite leer su valor de manera automtica al
lado derecho; esto es: Z = 0 ; X3 = 15 y X4 = 15 ; esto es una
SOLUCIN BSICA FACTIBLE.
Una lista clasificada de las variables es:

X1 = 0 Variable de decisin variable real Variable no bsica
X2 = 0 Variable de decisin variable real Variable no bsica
X3 = 15 Variable de holgura relleno Variable bsico
X4 = 15 Variable de holgura relleno Variable bsica
Z = 0 Variable de decisin variable real Variable bsica


2) Escoger la variable que entra
Aqu analizamos si existe una solucin mejor que la solucin bsica
factible, para ello despejamos de la ecuacin ( 0 ) del sistema de
ecuaciones inmediatamente anterior a Z y hacemos la siguiente
pregunta:



19

Cul es la variable que al crecer hace que z crezca ms?

Aqu la velocidad de crecimiento, tanto de X1 como de X2 es uno ( 1 ),
coeficiente de las variables X1 y X2 , luego se presenta un empate, el
cual se dirime al azar, escogemos como variable para entrar a X1 .
Como regla general, la variable para entrar es aquella que al crecer
haga que Z crezca ms, ya que el objetivo es Maximizar el valor de Z,
Dicho de otra forma, entrar la variable que tenga el coeficiente ms
positivo, si estuvisemos minimizando se escoge la variable que haga
que Z disminuya ms, o sea la que tenga el coeficiente ms negativo.
Si no hubiese variable para entrar, ello indica que nos encontramos en la
solucin ptima.

3) Escoger la variable que sale
(1) X3 = 15 5X1 3X2
(2) X4 = 15 3X1 5X2

Como de las variables no bsicas X1 y X2 ya fue escogida X1 para
entrar a la base, entonces X2 seguir siendo variable no bsica e igual a
cero ( 0 ), esto simplifica las ecuaciones as:
(1) X3 = 15 5X1
(2) X4 = 15 3X1

Fjese que para todos los casos, siempre quedarn despejadas las
variables bsicas en funcin de la variable escogida para entrar.


Aqu la pregunta es: cul es la variable bsica que restringe ms el
crecimiento de la variable que entra?
Para averiguarlo, hacemos que las variables bsicas X3 y X4 asuman su
menor valor factible o sea cero (0) y observamos el valor que asume la
variable escogida para entrar (X1).

20

(1) 15 5X1 = X3
(1) 15 5X1 = 0
X1 = 3
X3 deja crecer a X1, como mximo hasta 3
2) 15 3X1 = X4
(2) 15 3X1 = 0
X1 = 5

X4 deja crecer a X1 , como mximo hasta 5

Resumiendo:


La variable bsica que debe salir es aquella que restringa ms el
crecimiento de la variable que entra, en caso de empate, se dirime
arbitrariamente. Aqu se est cuidando la factibilidad de las variables,
esto es, que todas sean positivas ( > 0 ) . En el caso de ser un problema
de minimizacin, la presente regla de seleccin es igual.
Para nuestro problema, la variable que sale es X3 ya que como mximo
dejar crecer a X1 hasta 3, mientras que X4 la deja crecer como mximo
hasta 5.

4) Reorganizar el sistema de ecuaciones
Observe que al entrar X1 y salir X3, el sistema de ecuaciones ya no
tendr una sola variable bsica en cada fila con coeficiente uno ( 1 ),
esto es:


21

Fjese que en la ecuacin ( 1 ) se encuentra la variable que entra X1 y la
variable que sale X3 por ello en sta fila solo queda como variable
bsica X1 , lo molo aqu es que tiene coeficiente diferente de uno ( 1 ),
por ello multiplicamos toda la fila por el inverso del coeficiente de X1
(1/5) y la ecuacin resultante la llamamos Fila Pivote ya que
posteriormente servir para eliminar a X1 de las ecuaciones (0) y (2).

(1) 5X1 + 3X2 + X3 = 15 (1/5)
(1) X1 + 3/5X2 + 1/5X3 = 3 Fila pivote

Para encontrar el nuevo sistema de ecuaciones en el que en cada fila
figure una y solo una variable bsica con coeficiente uno (1), de tal
forma que se pueda leer automticamente su valor en el trmino
independiente de cada ecuacin, multiplicamos la fila pivote por el
coeficiente de X1 (multiplicado por 1), de cada una de las otras
ecuaciones y sumamos la fila pivote con cada una de las otras
ecuaciones para encontrar las nuevas ecuaciones del sistema. Para
nuestro problema, esto es:
Multiplicamos la fila pivote, fila (1) por uno (1) y le sumamos la fila (0). El
resultado es la nueva fila (0).

(1) X1 + 3/5X2 + 1/5X3 = 3 (-3) . (2) 3X1 + 5X2 + X4 = 15
(1) -3X1 - 9/5X2 - 3/5X3 = -9
(2) 16/5X2 - 3/5X3 + X4 = 6
Nueva fila (2)


Fjese que hemos eliminado a X1 de la ecuacin (2)
El nuevo sistema de ecuaciones es:





22

Fjese en las siguientes caractersticas que siempre debe tener el
sistema de ecuaciones
En cada fila hay una y solo una variable bsica con coeficiente uno
(1)
En la funcin objetivo, ecuacin cero (0), la variable bsica siempre
es Z y estar acompaada por las variables no bsicas.
Los trminos independientes, siempre sern los valores de las
variables bsicas para cada ecuacin.

Por ltimo la solucin ptima la hallaremos si encontramos una variable
que al entrar haga que la funcin objetivo crezca ms, lo anterior
significa que debemos repetir los pasos 2, 3 y 4 hasta que no se
encuentre una variable que haga que Z crezca, cuando ello ocurra
estamos en el ptimo.

1.4.2 El Mtodo Simplex en Forma Tabular.
Para poder desarrollar el mtodo simplex de forma tabular se
requiere que el modelo lineal para ser solucionado cumpla con las
condiciones:

a) Pasar del modelo cannico al estndar.

b) Para transformar las restricciones en igualdades se deben
incorporar las llamadas variables de holgura, las cuales tiene
coeficiente cero en la funcin objetivo.

c) Construir la tabla inicial e ingresar los datos.

d) Prueba de solucin, calculando los renglones de costo (Zj)y del
criterio simplex (cj-zj), la solucin es ptima si todos los valores cj-
zj son negativos cuando se est maximizando y positivos cuando
se est minimizando.

23

e) Si la solucin no es ptima se identifica la variable que entra y la
variable que sale (se divide el valor de la solucin por cada
variable bsica entre el coeficiente de cada columna pivote de su
mismo rengln).

f) Se revisa la solucin para desarrollar una nueva tabla. Primero se
encuentra el nuevo rengln pivote.

g) Repetimos la operacin hasta que todos los elementos de Zj sean
positivos, lo que indica que hemos hallado la funcin ptima.

CASO PRCTICO
Un joven Bachiller de Ingeniera industrial se encuentra practicando en una
empresa dedicada a la venta de granel, necesita tomar la mejor decisin con
respecto al siguiente problema:
La empresa se dedica a la venta a granel de tres tipos de grano sper, regular
y saldo requiere maximizar sus utilidades. Se sabe que la utilidad que generan
es $5.00, $6.00 y $5.50 por kilogramo, respectivamente. Para la
comercializacin elaboran paquetes combinados de 100 kg cada uno y la
cantidad de kg del grano regular debe ser por lo menos el doble de la cantidad
de kg de grano sper y saldo juntos. Slo se pueden vender 30 kg del grano
saldo debido a su disponibilidad.
En qu cantidad se deben mezclar los diferentes tipos de granos en
cada paquete para obtener una utilidad mxima?
1. Primero formulamos el problema:

X1 = cantidad de grano superior
X2= cantidad de grano regular
X3= cantidad de grano saldo


24


2. Ingresamos los datos a la tabla:

Base Cj Z X1 X2 X3 H1 H2 H3 Cd
H1 0 0 1 1 1 1 0 0 100
H2 0 0 -2 1 -2 0 1 0 0
H3 0 0 0 0 1 0 0 1 30
Z 0 1 -5 -6 -5.5 0 0 0 0

3. Se determina la variable bsica entrante con de la seleccin de la variable
cuyo coeficiente negativo tenga el mayor valor absoluto, en otras palabras
el coeficiente ms negativo de los elementos en Z.
Base Cj Z X1 X2 X3 H1 H2 H3 Cd
H1 0 0 1 1 1 1 0 0 100
H2 0 0 -2 1 -2 0 1 0 0
H3 0 0 0 0 1 0 0 1 30
Z 0 1 -5 -6 -5.5 0 0 0 0



Forma cannica Forma estndar


Funcin objetivo:
Z= 5X1 + 6X2 + 5.5X3

Sujeto a:

X1 + X2 + X3 100
X2 2(X1+X3)1800;X2 -2(X1+X3) 0
X3 30
X1, X2,X3 0




X1 + X2 + X3 + H1 = 100
-2X1 + X2 - 2X3 + H2 = 0
X3 + H3 = 30
Z 5X1 6X2 5.5X3 = 0


25

4. Se divide el coeficiente del CD entre el elemento correspondiente de la
columna seleccionada en el punto anterior, al cual se le llamar columna
pivote y de los resultados de la divisin se selecciona el menor valor
positivo y todo el rengln asociado a este valor. sta es la variable que
sale de la base (pasa a ser no bsica).
Nota: Las divisiones entre cero o entre nmeros negativos no se toman
en cuenta. Si todas son negativas o indeterminadas, el problema no
tiene solucin y termina el proceso.

Base Cj Z X1 X2 X3 H1 H2 H3 Cd
H1 0 0 1 1 1 1 0 0 100
H2 0 0 -2 1 2 0 1 0 0
H3 0 0 0 0 1 0 0 1 30
Z 0 1 -5 -6 -5.5 0 0 0 0


5. La celda que se encuentra en la interseccin de la columna con el rengln
seleccionado contiene un elemento al que, por medio de operaciones
elementales entre renglones, se convierte en elemento pivote. Aplicacin
de la prueba del cociente mnimo para determinar la variable bsica que
sale.

Base Cj Z X1 X2 X3 H1 H2 H3 Cd
H1 0 0 1 1 1 1 0 0 100
H2 0 0 -2 1 -2 0 1 0 0
H3 0 0 0 0 1 0 0 1 30
Z 0 1 -5 -6 -5.5 0 0 0 0







26

6. Se despeja la nueva solucin BF mediante operaciones algebraicas
elementales con renglones, para construir una nueva tabla en la forma
apropiada de eliminacin gaussiana, abajo de la actual y despus se
realiza la prueba de optimalidad. Las operaciones elementales con
renglones que deben realizarse son:

Despejar la nueva solucin bsica factible mediante
operaciones elemntales (multiplicacin, divisin, suma o
resta) para poder construir una nueva tabla simplex debajo de
la tabla actual.

Obtenemos la nueva tabla matriz (sale H2 y entra X3)

Base Cj Z X1 X2 X3 H1 H2 H3 Cd
H1 0 0 3 0 3 1 -1 0 100
X2 6 0 -2 1 -2 0 1 0 0
H3 0 0 0 0 1 0 0 1 30
Z 0 1 -17 0 -17.5 0 6 0 0


7. Se repite el proceso operando sobre las matrices hasta obtener todos los
coeficientes del rengln 0, con valores mayores o iguales a cero.

Base Cj Z X1 X2 X3 H1 H2 H3 Cd
H1 0 3 0 3 1 -1 0 100
X2 6 0 -2 1 -2 0 1 0 0
H3 0 0 0 1 0 0 1 30
Z 1 -17 0 -17.5 0 6 0 0



27

8. La nueva tabla simplex se escribe as: debido a que existen an
elementos negativos en la fila de los elementos Z, se deber continuar
con la operacin.

Base Cj Z X1 X2 X3 H1 H2 H3 Cd
H1 0 3 0 0 1 -1 -3 10
X2 6 0 -2 1 0 0 1 2 60
X3 5.5 0 0 0 1 0 0 1 30
Z 1 -17 0 0 0 6 17.5 525


Base Cj Z X1 X2 X3 H1 H2 H3 Cd
H1 0 3 0 0 1 -1 -3 10
X2 6 0 -2 1 0 0 1 2 60
X3 5.5 0 0 0 1 0 0 1 30
Z 1 -17 0 0 0 6 17.5 525


9. Luego de repetir el proceso, nos queda la tabla de la siguiente manera:

Base Cj Z X1 X2 X3 H1 H2 H3 Cd
X1 5 0 1 0 0 0.33 -0.3 -1 3.33
X2 6 0 0 1 0 0.67 0.33 0 66.67
X3 5.5 0 0 0 1 0 0 1 30
Z 1 0 0 0 5.67 0.33 0.5 581.67

Como en esta ltima tabla todos los coeficientes de los elementos Z no son
negativos, sino mayores o iguales a cero, se ha concluido el proceso.
La ltima operacin por realizar es transferir los valores de la solucin de la
tabla a las variables bsicas:


X1= 3.33
X2 66.67
X3 30
28

Retomando la definicin de las variables de decisin, los paquetes de 100 kg
se conforman de 3.33 kg de grano sper, 66.67 kg de grano regular y 30 kg de
grano saldo para tener una utilidad mxima de $581.67. Con esta
interpretacin, el encargado de tomar una decisin estar en posicin de
generar diversas estrategias para alcanzar el objetivo de comercializar
paquetes de 100 kg.

1.5 Anlisis De Sensibilidad

El anlisis de sensibilidad concierne el estudio de posibles cambios en
la solucin ptima disponible como resultado de hacer cambios en el
modelo original. Al respecto Rafael Lpez expresa: El anlisis de
sensibilidad es una forma eficiente de tratar las modificaciones, que
despus de haber resuelto el modelo, surgen como consecuencia de
errores o modificaciones en los datos originales o por informacin
adicional disponible (1993, p. 107).

Esta tcnica analiza la sensibilidad de la solucin ptima de un modelo
en la incertidumbre de los datos, su importancia radica en la posibilidad
de generar nuevas soluciones con un nmero limitado de simples
operaciones sin la necesidad de resolver el modelo de nuevo.

Obviamente las tcnicas de anlisis de sensibilidad son instrumentos
poderosos en la toma de decisiones econmicas. Recordemos que los
parmetros de un modelo de programacin lineal representan
magnitudes como: precios, costos, disponibilidad de factores e insumos
de recursos y es en base a los cambios que se presentan en estos datos,
que debemos tomar decisiones, tales como: producir cierto producto que
antes no producamos, modificar la cantidad de produccin, etc.

29

La idea general consiste en determinar rangos de variacin de los
parmetros del LP de forma de mantener una cierta base optima,
teniendo en cuenta que una solucin bsica es factible solo si todas las
variables basales tienen un valor no negativo. Debido a que el estudio de
la variacin simultanea de varios parmetros puede ser difcil, nos
centraremos en primer lugar en modicaciones de un parmetro a la vez
manteniendo los restantes jos. Se puede analizar cinco posibles de
cambio:
- Cambio del coeciente en la funcin objetivo de una variable no
bsica.
- Cambio del coeciente en la funcin objetivo de una variable bsica.
- Cambio del coeciente del lado derecho de una restriccin.
- Incorporacin de una nueva variable.
- Incorporacin de una nueva restriccin.

De las cuales vamos a analizar los dos primeros; para ello consideremos
el siguiente ejemplo en su versin estndar:

Max z = 60x1 + 30x2 + 20x3
s.a.
8x1 + 6x2 + x3 + h1 = 48
4x1 + 2x2 + 1.5x3 + h2 = 20
2x1 + 1.5x2 + 0.5x3 + h3 = 8
Z - 60x1 - 30x2 - 20x3 = 0
Base Cj Z X1 X2 X3 h1 h2 h3 Cd
h1 0 0 0 -2 0 1 2 --8 24
X3 20 0 0 -2 1 0 2 -4 8
X1 60 0 1 1.25 0 0 -0.5 1.5 2
Z 1 60 35 20 0 10 10 280
30

1.5.1 Cambio en el coeficiente en la funcin objetivo de una
variable no bsica.
El anlisis de sensibilidad para un coeficiente de la funcin objetivo
implica determinar un margen para los valores del coeficiente. A tal
gama se le denomina intervalo de optimidad. Mientras el valor del
coeficiente de la funcin objetivo se mantenga dentro del citado margen
de optimidad la solucin bsica factible seguir siendo ptima. Debido a
que solo se est cambiando el coeficiente de una variable en la funcin
objetivo, la regin factible del problema se ve inalterada, es decir, no se
ve modificada la factibilidad del ptimo actual.

En la base ptima del problema la nica variable de decisin no
basal es x2. Dicha variable posee como coeficiente en la funcin
objetivo: c2 = 30.

60 30+ 20 0 0 0
Base Cj Z X1 X2 X3 h1 h2 h3 Cd
h1 0 0 0 -2 0 1 2 --8 24
X3 20 0 0 -2 1 0 2 -4 8
X1 60 0 1 1.25 0 0 -0.5 1.5 2
Z 1 60 35 20 0 10 10 280
Cj-zj 0
-5+
0 0 -10 -10

Debido a que la modificacin es en una variable no basal, solo se
ve alterado el precio sombra de la variable no basal modificada, es decir,
c2- z2. Para que la base no se altere, el precio sombra de x2 debe
seguir siendo no negativo (caso maximizacin):

C2 - Z2 = -5+ 0 ----------- 5

En este caso, cualquier variacin inferior a 5 no cambiara la base.
Un incremento exactamente igual 5 implica que x2 puede pasar a ser
31

una variable basal (optimo alternativo). Valores mayores a 5 representan
un cambio en el ptimo y requerir efectuar iteraciones adicionales para
obtener la nueva solucin ptima.

A modo de ejemplo, consideremos un incremento = 10;
verificamos que la variable X2 pueda entrar. En este caso solo puede
salir X1 y X2 entrara con el valor 1.6, como lo vemos en la tabla.


Z nueva = z actual + x2 (c2- z2) = 280 + 1.6 * 5 = 288

Base Cj Z X1 X2 X3 h1 h2 h3 Cd
h1 0 0 0 -2 0 1 2 --8 24
X3 20 0 0 -2 1 0 2 -4 8
X1 60 0 1 1.25 0 0 -0.5 1.5 2
Z 1 60 35 20 0 10 10 280
Cj - zj 0 5 0 0 -10 -10


Completamos la iteracin en la tabla, donde verificamos el nuevo
valor mximo de la funcin objetivo y la combinacin de valores de las
variables basales. Como hemos visto, el cambio del coeficiente de una
variable no basal es lo suficiente para alterar el ptimo pero en ningn
caso se altera la regin factible del problema.

60 40 20 0 0 0
Base Cj Z X1 X2 X3 h1 h2 h3 Cd
h1 0 0 1.6 0 0 1 1.2 -5.6 27.2
X3 20 0 1.6 0 1 0 1.2 -1.6 11.2
X2 40 0 0.8 1 0 0 -0.4 1.2 1.6
Z 1 64 40 20 0 8 16 288
Cj - zj -4 0 0 0 -8 -16



32

1.5.2 Cambio del Coeficiente en la Funcin Objetivo de una
variable Bsica
La variacin en coeficientes de la funcin objetivo de las variables
bsicas, sigue la misma lgica en que las variables no bsicas.

Nuestro objetivo es cmo varan los Cj - Zj de todas las variables
y obtener a partir de ello un rango en el cual la base se vea inalterada.
Una modificacin de este tipo no afecta la regin factible y solo puede
cambiar la optimalidad de la solucin si la variacin es lo
sufrientemente importante.

Para ilustrar el anlisis consideremos una variacin sobre el
coeficiente c1, es decir, modifiquemos el valor del coeficiente en la
funcin objetivo de la variable x1.

60 + 30 20 0 0 0
Base Cj Z X1 X2 X3 h1 h2 h3 Cd
h1 0 0 0 -2 0 1 2 -8 24
X3 20 0 0 -2 1 0 2 -4 8
X1
60 +
0 1 1.25 0 0 -05 1.5 2
Z 1 60+ 35+1.25 20 0 10-0.5 10+1.5 280
Cj - zj 0 0 -5-1.25 0 0 -10+0.5 -10-1.5


Por otro lado para determinar el rango de variacin que mantiene
la base debemos imponer (caso maximizacin):
(Ck Zk) aik * 0
Donde el subndice K se refiere a la variable no bsica k y aik es
el coeficiente en la restriccin i de la variable no bsica k. En este
caso se debe imponer:
-5 1.25 0 . -5/1.25 =-4
-10 + 0.5 0 10/0.5 = 20
-10 1.5 0 -10/1.5 = -20/3

33

Por lo tanto, el parmetro debe variar en el siguiente rango de
optimalidad: -4 20
En caso la variacin supere este rango cambiar la combinacin
de variables en la base y el valor de la funcin objetivo, hacindose
necesario iterar para determinar el nuevo valor de las variables
basales.

1.5.3 Cambio del coeficiente del lado derecho de una restriccin
La variacin del coeficiente del lado derecho de una restriccin
modifica la regin factible del problema, por lo tanto puede afectar la
optimalidad de la solucin optima y la condicin de las restricciones
(activas o no activas).
El efecto de la variacin del coeficiente bi asociado a la restriccin
deber ser analizado considerando la condicin de la restriccin
afectada. Desde este punto de vista existen dos posibilidades:

Caso 1 La variacin afecta a una restriccin no activa, es decir, una
restriccin de tipo con su variable de holgura en la base, o bien una
restriccin de tipo con su variable de exceso en la base.

Caso 2 La variacin afecta una restriccin activa, es decir, una
restriccin de tipo con su variable de holgura igual a cero, o bien una
restriccin de tipo con su variables de exceso igual a cero.









34

CONCLUSIONES


La programacin lineal no solo se utiliza en campos relacionados con
las matemticas, sino en situaciones de la vida diaria, en los cuales
uno desea desenvolverse y prosperar.

Para lograr maximizar los beneficios en una empresa, productora,
etc.; es necesario un complejo mtodo, en este caso sera la
programacin lineal. No es algo que se debe calcular o estimar ya
que puede interferir en la poltica econmica de una empresa y
afectar en su desarrollo.

35

BIBLIOGRAFA

FREDERICK, Hiller., GERALD, Liberman. Introduccin a la
Investigacin de operaciones.9 ed. Mxico: Mc Graw- Hill, 2010.
2 p.

ISAR, Juan M. Investigacin de Operaciones para Administracin.
Mxico: Editorial Universitaria Potosina, 1996. 11 p.


HERNANDEZ, Mara. Introduccin a la Programacin Lineal. Mxico:
Universidad Nacional Autnoma de Mxico, 2007. 1 p.


LOPEZ, Rafael C. Programacin Lineal y Decisiones Econmicas. 3era
ed. Caracas: Eslibris, 1993. 57 p.


WEBGRAFIAS
http://investigaciondeoperacionesind331.blogspot.com/p/analisis-de-
sensibilidad.html