SECRETARA DE EDUCACIN PBLICA

INSTITUTO TECNOLGICO DE VERACRUZ

INVESTIGACION DE OPERACIONES II

UNIDAD 1: MODELOS DE REDES

EJERCICIOS

ALUMNO:

RODRGUEZ SARMIENTO DIANA KAREN

INGENIERIA INDUSTRIAL

CLAVE DE LA ASIGNATURA: INC-1019

CLAVE DEL GRUPO: 5X4

TITULAR DE LA MATERIA: CRUZ ROMERO RENE

H. VERACRUZ, VER. AGOSTO-DICIEMBRE 2017

 INDICE

INDICE ..................................................................................................................................................... 1
1. Introduccin a la Programacin Entera .......................................................................................... 2
Programacin Entera .............................................................................................................................. 3
Tipos de modelos de Programacin Entera ................................................................................. 5
2. Mtodo grfico de la Programacin Entera ................................................................................... 6
3. Redondeo ....................................................................................................................................... 8
4. Mtodo de planificacin y acotamiento ........................................................................................ 8
5. Algoritmo de Gomory ................................................................................................................... 14
6. Programacin Entera Mixta.......................................................................................................... 15
7. Problemas ms comunes.............................................................................................................. 16
Conclusin ............................................................................................................................................. 23
Bibliografa ............................................................................................................................................ 23
PROGRAMACION ENTERA
1. Introduccin a la Programacin Entera

En muchos problemas prcticos, las variables de decisin son realistas

nicamente si estas son enteras. Hombres, mquinas y vehculos deben ser
asignados a tareas en cantidades enteras. Hay muchos
recursos que deben existir en forma indivisible donde
las asignaciones en fracciones son insignificantes. La
programacin entera obtiene soluciones a problemas de
asignacin que requieren enteros. Cuando cada
variable debe ser un entero, es llamada programacin
entera pura; cuando nicamente algunas variables,
deben ser enteras, es llamada programacin entera
mixta.
Un enfoque para obtener soluciones enteras a un problema es resolver de la
solucin ptima obtenida de la solucin del Simplex y redondear las soluciones a
nmeros enteros. Aunque el enfoque de redondeo es en ocasiones adecuado, esto
tiene errores y puede conducir a una solucin subptima. La solucin ptima no-
entera no es necesariamente factible u ptima despus de que esta es redondeada.
Cuando las variables son grandes y sus valores es la funcin objetivo son pequeas,
un simple redondeo es apropiado. En problemas que involucran pequeas
magnitudes para las variables y grandes valores en la funcin objetivo, una solucin
entera ptima es necesaria.
La programacin entera est relacionada con funciones discretas y no distingue
entre nmeros mixtos y enteros. Problemas de Programacin Lineal generalmente
requieren que las variables sean enteras no-negativas. Si la mejor solucin factible a
un problema de Programacin Lineal es una solucin entera, esta es tambin la
mejor solucin factible a un problema de Programacin Entera.
La programacin Entera es una forma de programacin no-Lineal. Es casi lo
mismo que Programacin Lineal con la excepcin de que las variables en la solucin
final deben ser nmeros enteros no-negativos. Los problemas de programacin
entera pueden ser resueltos transformando el problema en una forma que permita la
aplicacin del mtodo Simplex de Programacin Lineal.
Un mtodo para resolver problemas de Programacin Lineal Entera Mixta y Pura
es el procedimiento del Plano Cortante de Gomory. Este procedimiento que produce
la mejor solucin cuando las variables deben ser expresadas en nmeros enteros;
inicia resolviendo el problema por el mtodo Simplex sin considerar el requerimiento
de enteros. Despus de que la solucin ptima no entera es obtenida a travs del
Simplex, una nueva restriccin Lineal es desarrollada para satisfacer los
requerimientos de enteros.
La nueva restriccin Lineal, llamada Plano Cortante modifica el problema original
eliminado algunas soluciones no enteras, pero no elimina las soluciones factibles
enteras. La nueva restriccin corta o divide la solucin ptima no entera previa y la
considera no factible.
La nueva ecuacin restrictiva es aadida a la tabla del Simplex y una nueva
variable entra en solucin. Cuando la nueva variable entra en solucin, causa que al
menos una de las variables bsicas tome un valor entero. El proceso continua hasta
que todas las variables bsicas sean enteras. A travs de esta tcnica iterativa se
alcanza una solucin ptima entera despus de que han sido Programacin Entera,
aadidas las suficientes nuevas restricciones para recortar todas las soluciones
superiores no enteras . Este mtodo resulta incmodo, pero garantiza una solucin
ptima no-negativa entera. Observe el algoritmo del plano cortante.
Una operacin clave en el algoritmo implica la seleccin de una nueva ecuacin
restrictiva la cual es tambin llamada Plano Cortante. Una nueva regla es elegir la
variable bsica que tenga la mayor fraccin en la solucin ptima no-entera. Si dos o
ms variables bsicas estn empatadas en su parte fraccional, seleccione aquella
variable que su coeficiente en la funcin objetivo tenga la menor contribucin por
unidad (para un problema de minimizacin seleccione las variables bsicas cuyo
coeficiente en la funcin objetivo que tenga el menor costo) . Para empates en las
fracciones, la variable con la menor contribucin por unidad es elegida debido a que
esta variable se convertir en un entero en la prxima iteracin. Debido a que el
valor de Z no puede aumentar y puede decrecer (prob. de maximizacin) al hacer la
variable entera, la variable bsica con la menor contribucin reducir el valor de Z en
una cantidad muy pequea. Para generar la nueva restriccin, reemplace todos los
coeficientes en la ecuacin restrictiva en cuestin por los menores nmeros no-
negativos que son congruentes a esos coeficientes y la expresin resultantes debe
ser mayor que o igual a la parte fraccional de la constante en el lado derecho del
signo igual.

Programacin Entera

Un problema de Programacin Entera es un problema de programacin lineal en

el cual algunas de las variables, o todas, tienen que ser nmeros enteros no
negativos. El objetivo de la Programacin Lineal Entera es encontrar el valor de la
funcin que
Max (Min) z = c1 x1 + c2 x2 + + cn xn
denominada funcin objetivo.

La funcin objetivo se encuentra sujeta a una serie de restricciones:

a11 x1 + a12 x2 + + a1n xn ( , , =) b1
a21 x1 + a22 x2 + + a2n xn ( , , =) b2 .
am1 x1 + am2 x2 + + a mn xn ( , , =) bm
xj > 0 (j=1, 2, ...., n)
xj entero
 Cuando se nos presente la resolucin de un Problema de Programacin Entera,
lo resolvemos como un problema de Programacin Lineal. Si sus soluciones son
enteras, sta es la solucin para el problema de programacin lineal entera.
En cualquier problema se verifica que la solucin ptima
zop (PL) > zop (PLE)

sta relacin se cumple siempre porque cualquier solucin factible para un

problema de PLE es tambin una solucin factible para la su relajacin lineal (PL).

Definicin 1. El problema de programacin lineal que se obtiene al omitir todas

las restricciones enteras variables 0-1 se llama relajacin de programacin lineal
para la programacin entera.

Definicin 2. Criterio de optimalidad en un problema de PLE: Una solucin

entera factible xF es ptima para el problema de PLE si es solucin ptima de una
relajacin lineal. En tal caso se cumple que z op (PL) = z op (PLE)=zF

Un problema de programacin entera en el cual solamente algunas de las

variables tienen que ser nmeros enteros, se llama un problema de programacin
entera mixta. Por ejemplo:
max z = 3 x1 + 2 x2
st x1 + x2 < 5
x1 , x2 > 0 ; x1 entero

Un problema de programacin entera en el cual todas las variables toman

valores 0 1, se denomina problema de programacin entera 0-1 (programacin
lineal binaria).
La relajacin de programacin lineal para la programacin mixta del ejemplo
anterior es:

max z = 3x1 + 2x2

st x1 + x2 = 5
x1 , x2 > 0

Por lo tanto, la relajacin programacin lineal es una versin menos restringida, o

ms relajada, de la programacin entera.
Esto significa que la regin factible para cualquier programacin entera tiene que
estar incluida en la regin factible de la relajacin programacin lineal
correspondiente.
Tipos de modelos de Programacin Entera

Programacin Entera es un trmino general para los modelos de programacin

matemtica que presentan condiciones de integridad (condiciones que estipulan que
algunas o todas las variables de decisin deben tener valores enteros). Ya hemos
apuntado que los modelos de programacin lineal entera son modelos de
programacin lineal que tienen la caracterstica adicional de que algunas de las
variables de decisin deben tener valores enteros. Existen diversas clasificaciones
de esta categora de modelos.

Programas Enteros Puros

Un modelo entero puro (PLE) es, como su nombre lo indica, un problema en

el que se exige que todas las variables de decisin tengan valores enteros. Por
ejemplo

Min 6x1 + 5x2 + 4x3

s.a. 108x1 + 92x2 + 58x3 >= 576
7x1 + 18x2 + 22x3 >= 83

x1, x2, x3 ><0 y enteros

Es un modelo entero puro. Sin las restricciones adicionales de que x1, x2, x3
sean enteros (o sea las condiciones de integralidad) seria un problema de
programacin lineal

Programas Enteros Mixtos

Un problema en el que solo se requieren que algunas variables tengan

valores enteros mientras que otras pueden asumir cualquier numero no negativo (es
decir, cualquier valor continuo) se llama programacin lineal entera mixta (PLEM).
Por ejemplo, supngase que en el problema anterior solo x1 y x2 deben ser enteros
y x3 no. El problema resultante es:

Min 6x1 + 5x2 + 4x3

s.a. 108x1 + 92x2 + 58x3 >= 576
7x1 - 8x2 + 22x3 >= 83

x1, x2, x3 >=0; x1 y x2 enteros

 Programas Enteros 0-1

En algunos problemas se restringe el valor de las variables a 0 o 1. Dichos

problemas se llaman binarios o programas lineales enteros 0-1. Son de particular
inters debido a que se pueden usar las variables 0-1 para representar decisiones
dicotmicas (s o no). Diversos problemas de asignacin, ubicacin de plantas,
planes de produccin y elaboracin de cartera, son de programacin lineal entera 0-
1.

Existen dos mtodos para generar las restricciones especiales que fuercen la
solucin ptima del problema, hacia la solucin ptima entera deseada:

- Mtodo de ramificar y acotar.

- Mtodo de planos de corte.

En ambos mtodos las restricciones agregadas eliminan partes del espacio

de soluciones, pero nunca alguno de los puntos enteros factibles.
Desafortunadamente, ninguno de los dos mtodos es efectivo en la solucin de
problemas de programacin lineal entera. No obstante los mtodos de ramificar y
acotar son mucho mejores en cuanto al clculo se refiere que los mtodos de plano
de corte. Por esta razn, la mayora de los cdigos comerciales se basan en el
procedimiento de ramificar y acotar.

2. Mtodo grfico de la Programacin Entera

El mtodo grfico (resolucin grfica) constituye una excelente alternativa de

representacin y resolucin de modelos de Programacin Lineal que tienen 2
variables de decisin. Para estos efectos existen herramientas computacionales que
facilitan la aplicacin del mtodo grfico como los software como: TORA, IORTutorial
y Geogebra

Para resolver un problema mediante el mtodo Grfico utilizamos los siguientes

pasos:

1. Inicialmente se dibuja el sistema de coordenadas asociando a un eje la variable

"x" y al otro la "y" (generalmente se asocia 'x' al eje horizontal e 'y' al vertical),
como se puede ver en la figura.

2. Se marca en dichos ejes una escala numrica apropiada a los valores que
pueden tomar las variables de acuerdo a las restricciones del problema. Para ello
en cada restriccin se hacen nulas todas las variables excepto la correspondiente
a un eje concreto, determinndose as el valor adecuado para dicho eje. Este
proceso se repite para cada uno de los ejes.
3. A continuacin se representan las restricciones. Comenzando con la primera, se
dibuja la recta que se obtiene al considerar la restriccin como igualdad. Aparece
representada como el segmento que une A con B y la regin que delimita sta
restriccin viene indicada por el color AMARILLO. Se repite el proceso con las
dems restricciones, quedando delimitadas la regin de color AZUL y ROJO para
la segunda y tercera restriccin respectivamente.

4. La regin factible es la interseccin de las regiones delimitadas tanto por el

conjunto de restricciones, como por las condiciones de no negatividad de las
variables, es decir, por ambos ejes de coordenadas. Dicha regin factible est
representada por el polgono O-F-H-G-C, de color VIOLETA.

5. Como existe una regin factible, se procede a determinar sus puntos extremos, o
vrtices del polgono que representa. Estos vrtices son los puntos candidatos a
soluciones ptimas. En este ejemplo son los puntos O-F-H-G-C de la figura.

Maximizar Z = f(x,y) = 3x + 2y
sujeto a: 2x + y 18
2x + 3y 42
3x + y 24
x0,y0
6. Finalmente, se evala la funcin objetivo (3x + 2y) en cada uno de esos puntos
(resultado que se recoge en la tabla siguiente). Como el punto G proporciona el
mayor valor a la funcin Z y el objetivo es maximizar, tal punto constituye la
solucin ptima: Z = 33 con x = 3 e y = 12.

Punto extremo Coordenadas (x,y) Valor objetivo (Z)

O (0,0) 0
C (0,14) 28
G (3,12) 33
H (6,6) 30
F (8,0) 24

3. Redondeo

Redondeo es el proceso y el resultado de redondear (eliminar ciertas cifras o

diferencias para considerar una unidad entera). Gracias al proceso de redondeo, se
facilitan los clculos.

El redondeo consiste en no considerar los decimales, cortando el nmero para

quedarse slo con el entero. Esto quiere decir, si queremos redondear el nmero
2,3, eliminaremos el 0,3 y nos quedaremos con el 2. En cambio, si el objetivo es
redondear 4,9, el mecanismo de redondeo llevar a dejar de lado el 0,9 y a sumar un
0,1 para poder trabajar con el nmero 5.

4. Mtodo de planificacin y acotamiento

En la prctica, la mayora de los problemas de programacin entera se resuelven

mediante el uso de la tcnica de ramificar y acotar.

Los mtodos de ramificar y acotar encuentran la solucin ptima para un

problema de programacin entera mediante la enumeracin eficiente de los puntos
en la regin factible.
 El mtodo de ramificacin y acotacin, ms conocido por su nombre en ingls
Branch and Bound, recibe su nombre precisamente por las dos tcnicas en las que
basa su desarrollo, que son la ramificacin y la acotacin.
El mtodo de ramificacin y acotacin comienza por resolver el PLA, de modo
que si la solucin al PLA verifica las condiciones de integridad, entonces tambin es
la solucin al problema entero, en caso contrario se comienza con la ramificacin del
problema.
La ramificacin consiste en dividir cada problema en dos nuevos subproblemas,
obtenidos mediante la imposicin de restricciones excluyentes que dividen el
conjunto de oportunidades del problema original en dos partes, pero eliminando en
ambas partes la solucin no entera del problema original.
Cuando en la solucin al PLA una variable que ha de ser entera xi toma el valor
xbi no entero, entonces se generan a partir de dicho valor dos restricciones xi [xbi]
y xi [xbi]+1 (siendo [xbi] la parte entera por defecto de xbi ), que aadidas cada uno
por separado al problema original, da lugar a dos nuevos subproblemas. Vamos a
explicar este proceso a traves de un ejemplo particular:
Consideremos el siguiente problema
(
1
Max F(x) = 4x1 + 5x2 )
s.a. 2x1 + x2 8 x2
5
x1,x2 0 y enteras

la solucin al PLA, prescindiendo de la condicin de que las variables han de ser

enteras es

x1 = 1,5, x2 =5 y F(x) = 31
como dicha solucin no verifica las condiciones de integridad se elige la variable
x1 que no es entera y a partir de ella se generan dos restricciones

x1 1 y x1 2
que aadidas cada una de ellas al problema original dan lugar a dos nuevos
subproblemas que seran los siguientes:

Max F(x) = 4x1 + 5x2 (1.1) Max F(x) = 4x1 + 5x2 (1.2)
s.a. 2x1 + x2 8 s.a. 2x1 + x2 8
x2 5 x2 5
x1 1 x1 2
x1,x2 0 x1,x2 0
 de este modo se han eliminado todas las posibles soluciones no enteras del
conjunto de oportunidades tales que 1< x1 < 2.
El proceso se repite con cada uno de los dos subproblemas obtenidos, los cuales
darn lugar a otros dos subproblemas cada uno de ellos y as sucesivamente hasta
que en todos los subproblemas tengan solucin entera o infactible.
Utilizando nicamente la ramificacin, el nmero de subproblemas a resolver
crece exponencialmente, por este motivo para evitar el tener que resolver todos los
subproblemas , la ramificacin se combina con la acotacin.
La acotacin se basa en el hecho de que dado que los conjuntos de
oportunidades del subproblema 1.1. (S11) y del subproblema 1.2 (S12) son a su vez
subconjuntos del conjunto de oportunidades del problema 1 (S1) la solucin ptima
de los dos subproblemas siempre ser inferior (problema de mximo o superior para
problemas de mnimo) que la solucin ptima del problema 1 por ser los conjuntos
de eleccin menores.
As pues, el proceso de acotacin consiste, para problemas de mximo, en tomar
como cota inferior aquella solucin entera con mayor valor de la funcin objetivo
obtenida y dado que cualquier otro subproblema con solucin no entera sabemos
que al ramificarlo nos dar como resultado valores de la funcin objetivo menores o
iguales, nos permite descartar como subproblemas a ramificar todos aquellos que
tengan como solucin ptima un valor de la funcin inferior a la cota establecida.
De este modo se reduce el nmero de subproblemas a ramificar y por lo tanto el
tiempo necesario para la resolucin de los problemas enteros.
El proceso a seguir en la resolucin de problemas enteros mediante el mtodo
de ramificacin y acotacin se resume en el siguiente esquema algortmico:

Esquema del algoritmo de ramificacin y acotacin.

Ejemplo
Max F(X) = 8x1 + 10x2 s.a.
4x1 + 6x2 24

8x1 + 3x2 24

x10,x20, x1,x2Z+

Resolviendo en primer lugar el PLA, es decir

Max F(X) = 8x1 + 10x2 s.a.

4x1 + 6x2 24
8x1 + 3x2 24

x10,x20

se obtiene la solucin x1 = 2, x2 = 8/3, f(x) = 128/3, dado que sta solucin no es

entera se ramifica a partir de la variable x2 del siguiente modo

subproblema 1 subproblema 2
Max F(X) = 8x1 + 10x2 . Max F(X) = 8x1 + 10x2
s.a. 4x1 + 6x2 24 s.a. 4x1 + 6x2 24
8x1 + 3x2 24 8x1 + 3x2 24
x2 3 x2 2
x10,x20 x10,x20
solucin x1=1,5, x2=3,F(x)=42 solucin x1=2,5, x2=2,F(x)=38
como la solucin del subproblema 1, tiene el mayor valor de la funcin objetivo y no
es entera ramificaremos este subproblema a partir de la variable x1, del siguiente
modo:

subproblema 1.1 subproblema 1.2

Max F(X) = 8x1 + 10x2 . Max F(X) = 8x1 + 10x2

s.a. 4x1 + 6x2 24 s.a. 4x1 + 6x2 24

8x1 + 3x2 24 8x1 + 3x2 24

x2 3 x2 3

x1 1 x1 2

x10,x20 x10,x20

solucin x1=1, x2=10/3,F(x)=124/3 solucin infactible.

dado que de todos los subproblemas todava no ramificados (subproblemas 2, 1.1 y

1.2) el que tiene una mayor solucin factible no entera es el subproblema 1.1,
ramificaremos este subproblema a partir de la variable x2, es decir
 subproblema 1.1.1 subproblema 1.1.2

Max F(X) = 8x1 + 10x2 . Max F(X) = 8x1 + 10x2

s.a. 4x1 + 6x2 24 s.a. 4x1 + 6x2 24

8x1 + 3x2 24 8x1 + 3x2 24

x2 3 x2 3

x1 1 x1 1

x2 3 x2 4

x10,x20 x10,x20

solucin x1=1, x2=3,F(x)=38 solucin x1=0, x2=4,F(x)=40

Dado que ya conocemos una solucin entera x1=0, x2=4,F(x)=40, sta solucin
actuar como cota inferior y solamente debern ser ramificados aquellos
subproblemas con soluciones factible no enteras que tengan un valor para la funcin
objetivo que 40. Como el nico subproblema por ramificar es el subproblema 2 y la
funcin objetivo vale 38, el proceso se d por terminado, siendo por tanto la solucin
ptima al problema entero

x1 = 0, x2 = 4, F(x) = 40
el arbol del problema resuelto es el siguiente:
5. Algoritmo de Gomory

El algoritmo puro de Gomory es una variacin del mtodo fraccional de Gomory, al

igual que este mtodo la matriz A debe ser entera. Adems debe cumplir las
condiciones para aplicar el mtodo dual simplex (optimalidad inicial y al menos un
negativo en la solucin):
1) Condicin de optimalidad

2) Valor de variable bsica < 0.

Definicin: Un vector es lexicogrficamente positivo si el primer componente

diferente de cero es positivo. Cuando un vector X es lexicogrficamente positivo se
escribe X}0.
Ejemplo:
X= (0. 3, -2, 9) X=0
X = (0,0,-3,12) X no es 0

Definicin: un vector X es lexicogrficamente mayor que otro vector Y si X - Y =0

Ejemplo:
X = (0, 3, -2) Y = (1, 2, 2)
X Y = (-1, 1, -4) X no es lxico grficamente mayor que Y
Y X = (1, -1, 4) X - Y = 0, por tanto Y es lexicogrficamente mayor que X.
Los pasos del mtodo son:

1) Elige la XBi ms negativa. Se designa a esa fila con r. Si el mtodo dual simplex
genera un pivote -1, aplicar el mtodo dual simplex. Si no continuar con el mtodo.
2) Elige aquella columna no-bsica con arj<0 que sea lexicogrficamente la menor.
Se designa una columna por k. Al primer elemento distinto de cero de dicha columna
se le designa por apk(>0) siendo su fila correspondiente la p.
3) Para la columna arj<0 se calcula el ndice uij = [akj/apk] si es que apj es el primer
elemento diferente de cero en la columna j. De otra manera u j=.
4) Se calcula =max [ !arj! / uj ]para arj<0 y uj.
5) Se deriva el corte:

6) Se anexa este a la tabla junto con su variable de holgura correspondiente y se

aplica el mtodo dual simplex sobre el entero. Si el resultado es XB0 entonces se
tiene la solucin ptima, si no ir al paso 1.

6. Programacin Entera Mixta

En este tipo de problemas, encontramos condiciones de ciertas variables de

decisin, que deben cumplir valores enteros y las dems con la suposicin de
divisibilidad.

Un problema en el que solo se requieren en que algunas variables tengan valores

enteros mientras que en otras pueden asumir cualquier nmero no negativo (es
decir, cualquier valor continuo) se llama programacin lineal entera mixta (PLEM).

EJEMPLO:

Supongamos un sistema que cumple las siguientes condiciones y donde X 1, X2,

deben ser enteras y X3 no entera, resolver el problema por Programacin Lineal
Entera Mixta (PLEM).

Funcin Objetivo: Maximizar Z = 10X1 + 9X2 + 9X3

 Sujeto a:

10X1 + 9X2 + 9X3 1700

21X1 +12X2 +18X3 1650

17X1 + 24X2 + 31X3 1100

X1, X2, X3 0

Resolviendo por cualquier metodo de Programacin Lineal, obtenemos

valores para una solucin inicial de:X1 = 66,7 X2 = 0 y X3 = 16,7.

Con un valor de la Funcin Objetivo de Z = $ 816,7

Sin embargo, aplicando las condiciones iniciales del Problema, bajo las condiciones
de resultados enteros, aplicando la tcnica ms usada, denominada Ramas y Cotas,
que en lecciones posteriores se explicara, tenemos:

X1 = 66 X2 = 0 y X3 = 17,4

Con un valor de la Funcin Objetivo de $817.

7. Problemas ms comunes

Para determinar la variable que entra en solucin.

Maximizacin
= ( zk-ck ) / yr k = max { (zj-ci) / yr j , yr j < 0 }
j
Minimizacin
= ( zk-ck ) / yr k = min { (zj-cj) / yr j , yr j < 0 }
j

Ejemplo:
Max.Z= 4x1+5x2+x3
Sujeto a;
 3x1 + 2x2 10
1x1 + 4x2 11

3x1 + 3x2 + x3 13x1

x2 ,x3 0 , enteros

Tabla inicial

z x1 x2 x3 x4 x5 x6 b

1 -4 -5 -1 0 0 0 0

0 3 2 0 1 0 0 10

0 1 4 0 0 1 0 11

0 3 3 1 0 0 1 13

Tabla
optima
Z x1 x2 x3 x4 x5 x6 b

1 0 0 0 2/10 4/10 1 194/10

0 1 0 0 4/10 -2/10 0 18/10

0 0 1 0 -1/10 3/10 0 23/10

 0 0 0 1 -9/10 -3/10 1 7/10

Programacin Entera
1a. Restriccin
x1+4/10 x4+8/10 x5 = 1 + 8/10 a [a] f= a-[a]

x1=1 1 10
4/10 x4+8/10 x5 8/10 4/10 0 4/10
s1 = 4/10 x4+8/10 x5-8/10 -2/10 -1 +8/10
s1 - 4/10 x4-8/10 x5 =-8/10

2da. Restriccin
x2 + 9/10 x4 + 3/10 x5 = 2 + 3/10 a [a] f= a-[a]

x2 =2 2 20
+9/10 x4 + 3/10 x5 3/10 -1/10 -1 + 9/10
s1=+9/10 x4 +3/10 x5-3/10 3/10 0 3/10
s1-9/10 x4-3/10 x5 =-3/10

3a. Restriccin
x3 + 1/10 x4 + 7/10 x5 =7/10 a [a] f= a-[a]
x3=1
1/10 x4 + 7/10 x5 7/10 1 10
s1 =+1/10 x4+7/10 x5 -7/10 -9/10 -1 +1/10
s1-1/10 x4-7/10 x5 = -7/10 -3/10 -1 +7/10
como f1 (8/10) > f2 (3/10) y f1(8/10) > f3 (7/10) ( f1 tiene la mayor fraccin) se trabaja
con la ecuacin un 1 ecuacin

z x1 x2 x3 x4 x5 x6 s1 b

1 0 0 0 2/10 4/10 1 0 194/10

0 1 0 0 4/10 -2/10 0 0 18/10=1+8/10

0 0 1 0 -1/10 3/10 0 0 23/10=2+3/10

0 0 0 1 -9/10 -3/10 1 0 7/10

0 0 0 0 -4/10 -8/10 0 1 -8/10

Utilizando el Dual-Simplex para determinar la variable que entra en solucin:

Max {(z4 -c4 )/y44 , (z5 -c5 )/y45 } = Max {(2/10)/(- 4/10) , (4/10)/(- 8/10)} = Max {-1/2 ,
-1/2} (empate), entra (arbitrariamente) x4 en solucin.

z x1 x2 x3 x4 x5 x6 s1 b

1 0 0 0 0 0 1 19

0 1 0 0 0 -1 0 1 1

0 0 1 0 0 1/2 0 -1/4 25/10=2+5/10

0 0 0 1 0 3/2 1 -9/4 25/1002+5/10

0 0 0 0 1 2 0 -10/4 2
2da. Ecuacin
x2 +1/2 x5 +3/4 x1 = 2 + 5/10 a [a] f=a -[a]

x2 = 2 1/2 0 1/2
s2 = 1/2 x5 +3/4 s1-1/2 -1/4 -1 3/4

s2-1/2x5-3/4 s1=-1/2

3a. Ecuacin
x3 +1/2 x5 +x6 +3/4 s1 = 2 + 5/10 a [a] f =a-[a]
1/2 x5 +3/4 s1 5/10
x3 +x6 = 2 (1 1/2 ) 3/2 1 1/2

s2=1/2 x5+3/4 s1-1/2 (-21/4 ) -9/4 -3 3/4

como son iguales sus partes fraccionales, se elige la ecuacin que corresponda a la
variable bsica con la mayor contribucin en la funcin objetivo (la ecuacin 2).

z x1 x2 x3 x4 x5 x6 s1 S2 b

1 0 0 0 0 0 1 1/2 0 19

0 1 0 0 0 -1 0 1 0 1

0 0 1 0 0 0 -1/4 0 25/10

0 0 0 1 0 3/2 1 -9/4 0 25/10

0 0 0 0 1 2 0 -10/4 0 2

0 0 0 0 0 -1/2 0 -3/4 1 -1/2

Utilizando Dual-Simplex para determinar la variable que entra en solucin

z x1 x2 x3 x4 x5 x6 s1 s2 b

1 0 0 0 0 0 1 1/2 1 19

0 1 0 0 0 0 0 5/2 -2 2

0 0 1 0 0 0 0 -1 1 2

0 0 0 1 0 0 1 -18/4 3 1

0 0 0 0 1 0 0 0 0 0

0 0 0 0 0 1 0 3/2 -2 1

Solucin ptima:
Por
Programacin lineal Programacin entera
x1= 1.8 x1= 2
x2= 2.3 x2= 2
x3= .7 x3= 1
x4= 0
x5= 1

Z*= 19.4 Z*=19

Si el sistema de ecuaciones fuera:

3x1+ 2x2 10
y su funcin objetivo
x1+ 4x2 11
Max Z = 4x1 +5x2 +x3
3x1+ 3x2+ x3 13
x1+ 2x2 6 Corresponde al 1er corte

5x1+14x2 38 Corresponde al 2do corte

La solucin ptima sera:

x1 = 2
x2 = 2
x3 = 1
z = 19

Obtencin de las ecuaciones de los cortes

1er Corte
Dado que inicialmente 3x1+2x2 10 y que 3x1+2x2
+x4 = 10, as x4 = 10- 3x1-2x2
Y dado que inicialmente 11 y que x1+4x2 +
x1+4x2 x5 = 11, as x5 = 11- x1- 4x2
Del primer corte, tenemos;
s1-4/10x4 -8/10x5 = -8/10
sustituyendo el valor de x4 y de x5 tenemos;

s1-4/10 (10-3x1-2x2) - 8/10 (11-x1-4x2) = -

8/10 s1-128/10 +2x1+4x2= -8/10 ;
s1+2x1+4x2= 12
Reduciendo, tenemos;
2x1+4x2 12 x1+2x2 6
2do Corte
Dado que inicialmente x1+2x2 6 y que x1+2x2 + s1 = 6, as s1 = 6- x1-
2x2 Del 2do. Corte tenemos que;
s2 -1/2 x5-3/4 s1 = -1/2
Sustituyendo el valor de s2, tenemos que;

s2 -1/2(11-x 1-4x2) -3/4(6-x1- 2x2) = -1/2 s2-

11/2+1/2 x1+2x2-9/2+3/4 x1+3/2 x2 = -1/2

s2-10+5/4 x1+7/2 x2 = 19/2

Reduciendo, tenemos;
5/4 x1+7/2 x2 19/2

5/2 x 1+7 x2 19
5x1+ 142 38
 8. Conclusin

En conclusin, podemos afirmar que la programacin lineal no solo es utilizada en

mbitos relacionados con las matemticas sino en situaciones de la vida diaria, en los
cuales uno desea desenvolverse y prosperar; ya que es uno de los mtodos ms
eficientes, por lo tanto podemos afirmar que la programacin lineal es una
herramienta muy til, tanto para personas con empresas independientes como para
grandes compaas. Te permite administrar de la mejor manera los recursos con los
que se cuenta para poder aprovecharlos al mximo, como tambin te ayuda a obtener
mayores ganancias y a minimizar tus costos.

9. Bibliografa

http://documents.tips/documents/metodo-de-gomory.html
http://www.geocities.ws/mdmoli/archivos/ioi2/unidad2ioi
https://www.iit.comillas.edu/aramos/simio/transpa/t_mod2_ar.pdf
https://www.google.com.mx/?gfe_rd=cr&ei=7kYtWM_1NIPW8gf5rI_wDQ#q=met
odo+de+gomory+investigacion+de+operaciones
http://datateca.unad.edu.co/contenidos/102016/CONTENIDOS/Exe_nuevo/lecci
n_7_programacin_entera_mixta.html
http://www.gestiondeoperaciones.net/programacion-entera/que-es-la-
programacion-entera/
http://www.phpsimplex.com/ejemplo_metodo_grafico.htm