CONTENIDO

INTRODUCCIÓN........................................................................................2
PROGRAMACIÓN ENTERA......................................................................3
METODO DE SOLUCIÓN DE PROGRAMCIÓN ENTERA.....................4
TÉCNICA DE RAMIFICACIÓN Y ACOTAMIENTO......................................................4
Ramificación.......................................................................................................................5
Acotamiento........................................................................................................................6
Sondeo.................................................................................................................................6
PROGRAMACIÓN HEURÍSTICA....................................................................................15
Heurística codiciosa..........................................................................................................22
Metaheurística..................................................................................................................25
Aplicando el método r y a................................................................................................27
aplicando el algoritmo de programación lineal entera – tipo binario. (Ramificación y
Acotamiento).....................................................................................................................34
PLANO DE CORTE............................................................................................................37
Plano de corte fraccional..................................................................................................37
Plano cortante mixto........................................................................................................58
Aplicando el método algortimo fraccional......................................................................64
BIBLIOGRAFÍA.........................................................................................70

1
 INTRODUCCIÓN

La programación lineal entera (PLE) se ocupa básicamente de programas lineales en los

que algunas o todas las variables suponen valores enteros o discretos. Se dice que la
PLE es mixta o pura si alguna o todas las variables están restringidas a tomar sólo
valores enteros.
Aunque se han creado varios algoritmos para la PLE, ninguno de ellos es totalmente
confiable desde el punto de vista del cálculo, sobre todo, cuando el número de variables
enteras se incrementa. A diferencia de la PL, donde problemas con miles de variables y
miles de restricciones se pueden resolver en un tiempo razonable, la experiencia de
cálculo con la PLE, después de más de 30 años de haberse creado, permanece
imprecisa.
A fin de acentuar la importancia de los problemas en los cuales se utilizan las variables
“codificadas”, lo siguiente presenta aplicaciones comunes en esta área. Esto servirá
también para ilustrar la importancia de la programación entera en general.

2
 PROGRAMACIÓN ENTERA

DEFINICIÓN DE LA PROGRAMACIÓN ENTERA

Un modelo de programación entera es aquel que contiene restricciones y una función
objetivo idénticas a las formuladas en programación lineal, la única diferencia en que
una o más variables de decisión deben tomar valor entero en la solución final.
 PURA: Son modelos similares a los de programación entera
Forma general:

Max (Min ) = a 1 x 1+ a2 x 2 + a3 x3 +a 4 x 4 + a5 x 5 +… +a n x n

Sujeto a :  a 1 x 1+ a2 x 2 + a3 x3 +a 4 x 4 + a5 x 5 +… +a n x n ≥ (≤ ¿(¿) Bi

No negatividad :   x i ≥ 0y  ENTERA

 BINARIA : Estos modelos lineales , las variables sólo toman valores 0 y 1 , son
usadas para uso probabilístico Donde 0 se rechaza la opción y 1 se acepta
la opción

Forma General :

Max (Min ) = a 1 y 1 +a2 y 2 +a 3 y 3 +a 4 y 4 + a5 y 5 + …+ an y n

Sujeto a y 1 + y 2+ y 3+ y 4 + y 5 +…+ y n ≥ (≤ ¿(¿) Bi

No negatividad :  y i ≥0 ∨1

 MIXTA : En estos tipos de modelos , integra las variables puras y las mixtas

Max (Min ) =
a 1 x 1+ a2 x 2 + a3 x3 +a 4 x 4 + a5 x 5 +… +a n x n +a1 y 1+ a2 y2 +a3 y 3 + a4 y 4 +a 5 y 5 +… +a n y n

Sujeto a : 
a 1 x 1+ a2 x 2 + a3 x3 +a 4 x 4 + a5 x 5 +… +a n x n ≥ (≤ ¿(¿) Bi
y 1 + y 2+ y 3+ y 4 + y 5 +…+ y n ≥ (≤ ¿(¿) Bi

No negatividad :
   x i ≥ 0 y ENTERO  ∧ y i ≥0 ∨1

3
 METODO DE SOLUCIÓN DE PROGRAMCIÓN ENTERA

En la PL, el método simplex se basa en aceptar que la solución óptima ocurre en un

punto extremo del espacio de soluciones. Este poderoso resultado reduce la búsqueda de
la solución óptima de un número infinito a un número finito de soluciones posibles. Por
otra parte, la PLE comienza con un número finito de puntos solución. Sin embargo, la
naturaleza entera de las variables hace difícil diseñar un algoritmo eficaz que localice
los puntos enteros factibles del espacio de soluciones. En vista de esta dificultad, los
investigadores han creado un procedimiento de solución que se basa en el gran éxito
obtenido al resolver problemas de PL.
Existen dos métodos para generar las restricciones especiales que fuercen la solución
óptima del problema PL relajado, hacia la solución entera deseada:
1. Método de ramificar y acotar
2. Método del plano de corte
En ambos métodos las restricciones agregadas eliminan partes del espacio de solución
relajado, pero nunca alguno de los puntos enteros factibles. Desafortunadamente,
ninguno de los dos métodos es efectivo en la solución de problemas de PLE. No
obstante, los métodos de ramificar y acotar son muchos mejores en cuanto al cálculo se
refiere que los métodos del plano de corte. Por esta razón, la mayoría de los códigos
comerciales se basan en el procedimiento de ramificar y cortar.

TÉCNICA DE RAMIFICACIÓN Y ACOTAMIENTO

La idea básica del método es “divide y conquistaras”. El problema de PL se divide en
subproblemas cada vez más pequeños. La división (ramificación) se hace mediante una
partición del completo, de soluciones factibles en subconjuntos más pequeños.
En parte, el sondeo se hace mediante el acotamiento de la mejor solución para después
descartar los subconjuntos cuya cota indique que no es posible que contenga una
solución óptima para el problema original.
Ejemplo:
Máx Z= 9X1 + 5X2 6X3 + 4X4
Sujeto a restricciones:
6X1 + 3X2 + 5X3 + 2X4 ≤10
X3 + X4 ≤1
-X1 + X3 ≤0
-X2 + X4 ≤0
Y Xj es binaria, j= 1,2,3,4.

4
5
Ramificación
Cuando se manejen variables binarias, la forma más sencilla de partir el conjunto de
soluciones factibles es fijar el valor de una variable (ejemplo X1 = 0, denominada
variable de ramificación) X=0 para un subconjunto.
Subconjunto (1) X1 = 0
Máx Z = 5X2 + 6X3 + 4X4
Sujeto a restricciones:
3X2 +5X3 + 2X4 ≤10
X3 + X4 ≤1
X3 ≤0
-X2 + X4 ≤0
Y Xj es binaria, j= 2,3,4.
Subconjunto (2) X1 = 1
Máx Z= 9 + 5X2 6X3 + 4X4
Sujeto a restricciones:
3X2 + 5X3 + 2X4 ≤4
X3 + X4 ≤1
X3 ≤1
-X2 + X4 ≤0
Y Xj es binaria, j= 2,3,4.

X1 = 0
Árbol de
TODO
soluciones
X1 = 1

Más adelante se verá que uno de estos subproblemas se puede sondear, mientras que el
otro requiere una nueva división en subproblemas más pequeños si se establece X2= 0.
En otros problemas de PE, donde las variables enteras pueden tener más de dos valores
posibles, la ramificación se puede hacer a través de establecer las variables de
ramificación igual a cada valor, lo que crea más de dos subproblemas.
6
Acotamiento
Para cada subproblema, es necesario obtener una cota que muestre nivel de precisión de
su mejor solución factible. La forma más común de resolver con rapidez un relajamiento
(eliminando un conjunto de restricciones que dificulten obtener una solución).
Ejemplo:
0 ≤ x j ≤ 1 j=1 , 2 ,3 , 4 ; Xj es binario

Usando método simplex:

5 1
( )
( x 1 , x 2 , x 3 , x 4 ) = 6 ,1 , 0 , 1 z=16 2

1
Por tanto z ≤ 16 Para todas las soluciones factibles del problema original de PEB.
2
Como los coeficientes de la función objetivo son enteros y, por ende, debe ser un valor
entero de Z-.
Cota de todo el problema Z≤ 16 ,

De lo misma manera se obtendrá las cotas de los subproblemas 1 donde x 1=0 se

expreso de manera apropiada en su relajación PL mediante la suma de la restricción que
x 1 ≤ 0 que cuando se combinan con la actual restricción 0 ≤ x1 ≤1obliga a que x 1=0.

De manera similar se observa para subproblema 2, para x 1=1. Relajamiento de PL del

subproblema 1: x 1 ≤ 0 y 0 ≤ x1 ≤1 .

Solución óptima ( x 1 , x 2 , x 3 , x 4 ¿=( 0 ,1 , 0 , 1 ) con z=9

Relajamiento de PL del subproblema z x 1 ≥ 1 y 0 ≤ x1 ≤1 para j=1, 2, 3, 4

4 4 1
(
Solución óptima ( x 1 , x 2 , x 3 , x 4 )= 1 ,
5 )
,0 , con t=16 .
5 5

Entonces se obtienen las siguientes cotas.

Cota de subproblemas 1: z ≤ 9
Cota de subproblemas 2: z ≤ 16

Sondeo
Se ilustra los resultados del subproblema 1 que se dieron en el nodo x=0 con un
relajamiento de PL ( x 1 , x 2 , x 3 , x 4 ¿y z (0, 1, 0, 1) es una solución entera, y, en
consecuencia, esta solución se le conoce como solución de apoyo actual.
z ¿ =valor de z de la solución de apoyo actual
De manera que en este punto z*=9, como ya se resolvió el subproblema 1 se sondea
(elimina).

7
De, los resultados anteriores sugieren un segundo sondeo. Como z*= 9 no existe, razón
alguna para tomar en cuenta ningún subproblema cuya cota sea ≤ 9 , puesto que tales
subproblemas no pueden tener soluciones factibles mejores que de apoyo, en forma
general, se sondea un subproblema siempre que su cota ≤ z¿ .
A medida que se encuentran nuevas soluciones de apoyo con valores más grandes de z ¿
será más fácil sondear de esta forma.
La tercera forma es bastante directa. Si el método simplex encuentra que el relajamiento
de PL de un subproblema no tiene soluciones factibles, es decir, no debe tener
soluciones factibles, de forma que pueda eliminarse (sondearse).
En los 3 casos, se lleva a cabo la búsqueda de una solución óptima mediante la
investigación de solo aquellos subproblemas que es posible que tengan una mejor
solución que la del apoyo actual.
Método de ramificación y acotamiento para resolver problemas de programación mezclados
con enteros (programación mixta)

En un PE mezclado, algunas variables requieren ser enteros y otras pueden ser enteros o
no enteros. Para resolver un PE mezclado mediante el método de ramificación y
acotamiento, se ramifica sólo sobre las variables que deban asumir necesariamente
valores enteros. También, para resolver un subproblema que sea una solución probable
(candidata), se requiere sólo asignar valores enteros a aquellas variables que necesiten
ser enteros.
Ejemplo.
- Resolver el PE mezclado siguiente:
Max Z= 2x1 + x2
Sujeto a:
5x1 + 2x2 ≤ 8
x1 + x2 ≤ 3
x1, x2 ≥0; x1 entero

Iniciamos por resolver la relajación del PL del PE.

8
Como la restricción de valores enteros se hace sobre x1; se ramifica sobre esta variable.

Subproblema 1

Z=11/3, X1=2/3, X2= 7/3

x1 ≤ 0 x1 ≥ 1

Subproblema 2 Subproblema 3
Z=3, X1=0, X2=3 Z=4.5, X1=1, X2=1.5

Se inicia resolviendo el subproblema 2, su solución óptima es Z=3, x1=0, x2=3. Luego

se resuelve el subproblema 3 y se obtiene como solución probable z=3.5, x1=1, x2=2.5.
El valor de Z en el subproblema 3 excede al valor de la solución probable del
subproblema 2, por eso el subproblema 2 se deja de considerar y la solución probable
del subproblema 3 se vuelve la solución óptima para el PE mezclado.
Ejemplo:
Resolver el siguiente problema:
Max Z= 16x1 + 22x2 + 12x3 + 8x4 (en millones de dólares)
Sujeto a:
5x1 + 7x2 + 4x3 + 3x4 ≤ 14 (en millones de dólares)
XJ = 0 ó 1; (j=1,2,3, ...n)
Este caso suele denominarse “problemas de mochila” en los cuales cada variable puede
ser 0 a 1.

9
Sea: Max Z= C1X1 + C2X2 + C3X3 + … CnXn
S.A a1X1 + a2X2 + a3X3 + … anXn ≤ b
XJ = 0 ó 1; (i=1,2,3, ...n)
Recuerde que el beneficie obtenido si se elige el objeto “i”, “b” es la cantidad disponible
de un recurso y ai es la cantidad del recurso disponible que usa el objeto “i”. Se define el
cociente Ci/ai como el beneficio que el objeto “i” gana por cada unidad del recurso que
utiliza el objeto “i”. Por lo tanto, los mejores objetos tienen valores más grandes de Ci/ai.
Se calcula los cocientes y se pone el mejor objeto en la mochila, después coloque el
siguiente mejor objeto en la mochila, continúe con este tenor hasta que el mejor objeto
restante exceda la capacidad de la mochila. Luego llene la mochila con lo mayor
cantidad de este objeto que sea posible. Primero resolveremos la relajación de esta PE.
En el ejercicio, cálculo de los cocientes:

Objeto Ci/ai Clasificación (1=el

mejor, 4= el peor)
1 3.20 1
2 3.14 2
3 3.00 3
4 2.67 4

Entonces, X1 adopta el valor de 1, se resta la cantidad de recursos que utiliza del total
de recursos disponibles:
7x2 + 4x3 + 3x4 ≤ 9
Luego, el siguiente mejor valor es el objeto 2, X2 adopta el valor de 1, se introduce en
la mochila y se resta la cantidad de recursos que utiliza del total de recursos disponibles:
4x3 + 3x4 ≤ 2
Luego, el siguiente mejor valor es el objeto 3, X2 adopta el valor de:
4x3 ≤ 2
x3 ≤ 1/2
Con esto, el valor de Z es 44.

10
 Ahora, usando el método de distribución y acotación:

Subproblema 1
Z=44, X1 = X2 = 1, X3= 1/2

X3 =0 X3 =1

Subproblema 2 Subproblema 3
Z=43 1/3, X1 = X2 = 1, X3= 0, X4= 2/3 Z=43 5/7, X1 = X3 = 1, X2= 5/7, X4= 0
Límite inferior Límite inferior

X4 =0 X4 =1 X2 =0 X2 =1

Subproblema 4 Subproblema 5
Subproblema 8 Subproblema 9
Z=36 Z=43 3/5
Z=38 Z=42 6/7
X1 = X3 = 1 X1 = 3/5
X1 = X2 = 1 X1 = X4 = 1
X2 =0 X2 = X3 = 1
X3= X4=0 X2= 6/7
X4= 1 X4 = 0
LI=42 X3=0
Solución probable
LI = 42

X1 =0

X1 =1
Subproblema 6

Z=42, X1 = 0, X2 = 1 Subproblema 7
X3 = 1, X4 = 1 LB= 42
Solución probable No factible
LI=36

11
 1) Se inicia la ramificando la variable X3, se resuelve el subproblema 3, como la
variable X2 adopta un valor fraccionario, se ramifica esta variable
2) El subproblema 4 genera la solución probable x1=x3=z4 =1; Z=36. Luego se fija
el límite inferior LI=36.
3) El subproblema 6 proporciona una solución probable con Z= 42. Por lo tanto, el
subproblema 4 se dejó de considerar y el LI se actualizo a 42.
4) El subproblema 7 fue no factible, porque requirió x1=x2=x3=1, y tal solución
necesita por lo menos 16 millones de dólares.
5) El subproblema 8 se eliminó porque su valor Z (Z=38) no excedió el LI actual
de 42.
6) El subproducto 9 tenía un valor de z de 42 6/7. Puesto que el valor de Z para
cualquier solución de puros enteros tiene que ser también un entero, esto
significaba que la ramificación sobre el subproducto 9 nunca podría dar un valor
de Z mayor que 42. Por lo tanto, se eliminó este subproblema.

Ejemplo 2:
Maximizar z = 5x1 + 4x2
Sujeto a
x1 + x2 <= 5
10x1 + 6x2 <= 45
x1, x2 enteras no negativas

Los puntos de cuadrícula definen el espacio de

soluciones de PLE.
El problema PL1 continúo asociado en el nodo 1
(área sombreada) se define a partir de la PLE
eliminando las restricciones enteras. La solución
óptima de PL1 es x1 = 3.75, x2 = 1.25 y z =
23.75.

PL1 no satisface las restricciones enteras, el

espacio de soluciones se subdivide de una
manera sistemática que finalmente localiza el
óptimo de la PLE.

Tanto x1 como x2 califican.

Seleccionando x1 = 3.75

12
Arbitrariamente, la región 3 < x1 < 4 del espacio de soluciones de PL1 contiene valores
no enteros de x1, y por lo tanto puede ser eliminada.
Esto equivale a reemplazar el PL1 original con dos problemas de PL nuevos.

Espacio de PL2 = Espacio de PL1 + (x1 <= 3)

Espacio de PL3 = Espacio de PL1 + (x1 => 4)

Las nuevas restricciones, x1 <= 3 y x1 => 4, son mutuamente excluyentes, de modo que
el PL2 y el PL3 en los nodos 2 y 3 deben tratarse como programaciones lineales
distintas.
x1: variable de ramificación.

13
La PL óptima puede ser PL2 o PL3. Analizando PL2 asociada con X<= 3
Maximizar z = 5x1 + 4x2

Sujeto a

X1 + X2 <= 5
10X1 + 6X2 <= 45
X1 <= 3
X1 , X2 => 0
Utilizando el acotamiento la solución de PL2 es X1= 3, X2 = 2 y Z= 23 satisfaciendo
los requerimientos enteros para X1 y X2. Entonces aplicamos el sondeo a fondo.
Sea Z = 23 como cota inferior de la PLE en general y se procede al análisis de PL3:
Debido al óptimo z = 23.75 en el PL1 ya qué sucede que todos los coeficientes de la
función objetivo son enteros, es imposible que PL3 pueda producir una mejor solución
entera (con z > 23). En consecuencia, desechamos PL3 y concluimos que fue sondeado
a fondo.

Problema del Pisco

Se desea construir una planta para la producción de Pisco Portón, a nivel industrial. La destilería
“La Caravero”, ubicada en Ica, contrató a un ingeniero químico, para estimar la mayor cantidad
de equipos, tratando de invertir lo menos posible en maquinaria de costo elevado. Se necesita de
una prensa hidráulica, una despalilladora, un fermentador, un alambique, cuyos costos se verán
en la siguiente tabla. La primera sección del proceso cuenta con la despalilladora, cuyo
funcionamiento es de una hora por día y la prensa, 5 horas por día. La productividad entre
despalilladora, fermentador y prensa no debe ser mayor a una tonelada por hora, tomando en
cuenta que la prensa debe tener la menor productividad posible. La potencia de la
despalilladora, respecto a los fermentadores es de no mayor a cinco sextos. La sección de
prueba de equipos cuenta con abastecimiento para las despalilladoras, fermentadores y

14
alambiques, cuyo funcionamiento son de 1,2 y 2 horas respectivamente, disminuyendo el uso de
las despalilladoras y alambiques ya que tienen un elevado costo de electricidad. La primera
sección cuenta con disponibilidad de 10 horas diarias; la sección de prueba con 3 horas por día.
El beneficio adquiriendo despalilladoras es 4 a 7 con respecto a las prensas y el beneficio de los
alambiques es el doble de los fermentadores. ¿Cuál ha de ser la cantidad de equipos adquiridos
para que el beneficio sea máximo?

x 1=cantidad de despalilladoras (unidades)

x 2=cantidad de fermentadores( unidades)

x 3=cantidad de prensas neumáticas(unidades)

x 4 =cantidad de alambiques(unidades)
máx z=4 x 1−2 x 2 +7 x 3−4 x 4
 
Sujeto a:
1.  Horas disponibles en sección uno por día:
x 1+ 5 x 3 ≤10
2. Productividad de los equipos adquiridos en toneladas:

x 1+ x2−x 3 ≤1
3. Relación entre la potencia de despalilladora y fermentador:
6 x 1−5 x 2 ≤ 0
4. Horas disponibles en la sección de prueba:

−x 1+ 2 x 2−2 x 4 ≤3
5. Condición de no negatividad:

  x 1 ; x 2 ; x 3 ; x 4 ≥ 0 y enteros

15
16
APLICANDO DOBLE FASE

- PRIMERA FASE:

- SEGUNDA FASE:

17
18
APLICANDO DOBLE FASE PARA EL OTRO VALOR

- Primera fase:

19
- Segunda fase:

20
PROGRAMACIÓN HEURÍSTICA
Existen problemas de Investigación de Operaciones que pueden ser tan complicados que
no es posible resolverlos para encontrar una solución óptima. En tales situaciones, aún
21
es importante encontrar una buena solución factible que al menos esté razonablemente
cerca de ser óptima. Por lo general, para buscar esa solución se utilizan métodos
heurísticos.
¿QUÉ ES UN MÉTODO HEURÍSTICO?

Un método heurístico es un procedimiento que trata de descubrir una solución factible

muy buena, pero no necesariamente una solución óptima, para el problema específico
bajo consideración.
La heurística está diseñada para encontrar buenas soluciones aproximadas de problemas
combinatorios difíciles que de lo contrario no pueden resolverse mediante los
algoritmos de optimización disponibles. Una heurística es una técnica de búsqueda
directa que utiliza reglas favorables prácticas para localizar soluciones mejoradas.
Con frecuencia, el procedimiento es un algoritmo iterativo novedoso, donde cada
iteración implica la realización de una búsqueda de una nueva solución que puede ser
mejor que la solución que se encontró con anterioridad. Cuando el algoritmo termina
después de un tiempo razonable, la solución que proporciona es la mejor que se pudo
encontrar en cualquier iteración.
Los métodos heurísticos se basan en ideas bastante simples, de sentido común,
acerca de la forma en que se debe buscar una buena solución.
Estas ideas deben ajustarse al problema específico de interés. En consecuencia,
los métodos heurísticos tienden a ser ad hoc por naturaleza.
Esto es, por lo general cada método se diseña para abordar un tipo específico de
problema en vez de una variedad de aplicaciones.
Para comprender el concepto de heurística, se presenta como ejemplo la manera de
abordar un problema matemático mediante la heurística.
Ej. Encuentra el último dígito de la siguiente multiplicación: 92008 x 162009
Por las dimensiones de la potencia, una calculadora no nos dará el resultado. Como la
pregunta se refiere únicamente al último digito, es posible emplear la heurística para dar
respuestas a esa pregunta.
El punto de partida es hacer un análisis de los resultados de elevar las bases (9 y 16 en
este caso) a distintas potencias.

Es posible notar que cuando el número 9 se

eleva a una potencia impar, el resultado
termina en 9, mientras que cuando se eleva a
una, el resultado termina en 1.

22
El punto de partida es hacer un análisis de los resultados de elevar las bases (9 y 16) en
este caso) a distintas potencias

En el caso de 16, indistintamente de que se

eleve a una potencia par o impar, el resultado
termina en 6

Retomando el enunciado:
9 elevado a potencia par, termina en 1.
16 elevado a potencia para o impar, termina en 6, por tanto, la respuesta es 6.

Las primeras generaciones de heurísticas se basan en la regla de búsqueda codiciosa

que dicta que se mejore el valor de la función objetivo con cada movimiento de
búsqueda. La búsqueda termina en un óptimo local donde ya no son posibles más
mejoras.
En la década de 1980, una nueva generación de meta heurística busco mejorar la calidad
de las soluciones heurísticas al permitir la búsqueda de una trampa de escape en óptimos
locales. La ventaja obtenida se logra a expensas de los cálculos incrementados.

23
Heurística codiciosa
Las primeras generaciones de heurística se basan en la regla de búsqueda codiciosa que
dicta que se mejore el valor de la función objetivo con cada movimiento de búsqueda.
La búsqueda termina en un óptimo local donde ya no son posibles más mejoras.
La heurística codiciosa también se le denomina búsqueda local.
Las ideas principales de la heurística codiciosa se explican por medio de un problema de
una sola variable.
Defina el problema de optimización con espacio de soluciones S como:
Minimizar z = F(x), x ϵ S
El proceso iterativo de una heurística codiciosa se inicia en un punto factible (aleatorio)
y luego intenta moverse a un punto de mejor solución en las inmediaciones (vecindad)
del punto de solución actual.
Específicamente, en la iteración k, dado el punto de solución xk, la heurística examina
todos los puntos factibles en las inmediaciones N(xk) en busca de una mejor solución.
La búsqueda finaliza cuando ya no son posibles más mejoras. La definición de N(xk) es
importante en el diseño de la heurística. Por ejemplo, para x entera, N(xk) = [xk- 1, xk +
1] define la vecindad inmediata de xk.
Alternativamente, una vecindad expandida puede incluir puntos de solución cercanos
adicionales.
La primera definición implica menos cálculos de búsqueda local, pero podría
deteriorar la calidad de la solución final.
La segunda definición (vecindad expandida) requiere más cálculos de búsqueda
local, pero podría mejorar la calidad de la solución.

Heurística de Variable discreta

Para la explicación de la heurística de variable discreta se presentarán dos ejemplos, el
primero utiliza la vecindad inmediata y el segundo expande el dominio para incluir más
puntos de solución l. Ambos casos se refieren a una sola variable discreta.
Ejemplo1:
Vecindad Inmediata
Considere la función F(x) dada en la figura y defina el problema de optimización como
Minimizar F(x), x ϵ S = {1, 2, ..., 8}
La función tiene un mínimo local en x =3(B) y un mínimo global en x = 7(D)

24
Vecindad Expandida
La búsqueda de vecindad expandida puede basarse en la evaluación de todos los puntos
cercanos, una estrategia que incrementa la carga computacional.
Alternativamente, es posible determinar el siguiente movimiento de búsqueda mediante
la selección aleatoria de la vecindad. Específicamente, en la iteración k, el siguiente
movimiento, xk+1, se selecciona de N (xk) con probabilidad de 1/m, donde m es el
número de elementos en el conjunto de vecindades.
El muestreo de la vecindad se repite, si es necesario, hasta que se determina una
solución mejorada, o hasta que un número especificado de iteraciones se ha alcanzado.

25
La regla de selección aleatoria describe lo que se conoce como heurística de caminata
aleatoria
Ejemplo de Vecindad Expandida
Este ejemplo se aplica una vez más a F(x) de la figura presentada previamente.
Arbitrariamente definimos el conjunto de vecindades expandidas N(xk) como {1,2,
…,xk-1, xk+1,…,8}. La búsqueda continúa durante cinco iteraciones comenzando en
x0=1. Indique [seleccionada de entre N(xk)] como un posible siguiente movimiento. Se
acepta como el nuevo movimiento de búsqueda sólo si mejora la solución. Si no lo hace,
se intenta una nueva selección aleatoria de N(xk).
La tabla que se presenta a continuación detalla la aplicación de la heurística de caminata
aleatoria. En contraste con la heurística de vecindad inmediata del ejemplo anterior, la
heurística de caminata aleatoria produce la solución x=7y F(x)=40 en la iteración 4, la
que por accidente resulta ser mejor que la obtenida en el ejemplo de vecindad
inmediata.
En la iteración 3, el posible movimiento aleatorio desde N(xk)= 2 ={1,3,4,5,6,7,8} no
mejora la solución. Por consiguiente, en la iteración 4 se intenta otro movimiento
aleatorio desde la misma vecindad. En esta ocasión el movimiento produce la solución
superior x* = 6.

26
Desventaja de la Heurística Codiciosa
Cuando se aplica un procedimiento de mejora local bien diseñado a un problema de
optimización con múltiples óptimos locales, el procedimiento convergirá hacia un
óptimo local y se detendrá.
El óptimo local que encuentre dependerá del punto en el que el procedimiento inicia su
búsqueda. Por lo tanto, el procedimiento encontrará el óptimo global sólo si inicia la
búsqueda en la vecindad de dicho óptimo global.
Para tratar de evitar esta desventaja se puede reiniciar el procedimiento de mejora local
cierto número de veces a partir de soluciones de prueba aleatorias.
Con frecuencia, cuando se reinicia desde una parte nueva de la región factible se llega a
un nuevo óptimo local.
Si se repite esta rutina cierta cantidad de veces se incrementa la posibilidad de que el
mejor óptimo local que se obtuvo en realidad sea el óptimo global.
Este enfoque funciona bien con problemas pequeños. Sin embargo, es mucho menos
exitoso en problemas grandes con muchas variables y una región factible complicada,
en estos casos se aplica la meta heurística que será explicada.
Metaheurística
La heurística codiciosa presentada comparte una estrategia común. En la iteración k la
búsqueda se mueve a un nuevo punto Xk+1 ϵ N(Xk) sólo si el nuevo punto mejora el
valor de la función objetivo F(X). Si no se puede hallar una Xk+1 mejor en N(Xk) o si
se llega a una cantidad de iteraciones especificada por el usuario, la solución se
encuentra atrapada en un óptimo local y la búsqueda termina.
La metaheurística está diseñada principalmente para escapar del entrampamiento en el
óptimo local al permitir movimientos inferiores, si es necesario. Se espera que la
flexibilidad agregada a la búsqueda conduzca a una mejor solución.
A diferencia de la heurística codiciosa, la cual siempre termina cuando se llega a un
óptimo local, la terminación de una búsqueda metaheurística se basa en los siguientes
puntos de referencia:
La cantidad de iteraciones de búsqueda excede una cantidad especificada.
La cantidad de iteraciones desde la última mejor solución excede una cantidad
especificada.
La vecindad asociada con el punto de búsqueda actual, o está vacía o no puede
conducir a un nuevo movimiento de búsqueda viable.
La calidad de la mejor solución actual es aceptable.

27
Algoritmo búsqueda Tabú
Cuando la búsqueda se queda atrapada en un óptimo local, la búsqueda Tabú (BT)
selecciona el siguiente movimiento de búsqueda (posiblemente inferior) de una manera
que prohíbe temporalmente, volver a examinar las soluciones anteriores. El instrumento
principal para alcanzar este resultado es la lista tabú que “recuerda” los movimientos
de la búsqueda anterior y los deshabilita durante un periodo de tendencia especificada.
Cuando un movimiento tabú completa su tendencia, se elimina de la lista tabú y se hace
disponible para futuros movimientos.
Ejemplo: Minimización de una función de una sola variable
Este ejemplo detalla la aplicación de la BT a la minimización de la función F(x) en la
figura 1 . Para la iteración k sean:
Xk = Solución de prueba actual
N(xk) = Vecindad de xk
Lk = Lista Tabú de valores inadmisibles de x en la iteración k
τ = Periodo de permanencia tabú expresado en cantidad de iteraciones sucesivas
x* = Mejor solución encontrada durante la búsqueda.
En términos de la F(x) de la figura 1 los valores factibles son 1, 2, ... , 8.
En la iteración k, el conjunto de vecindades de xk puede definirse como N(xk) = ( xk –
q, … xk – 1, xk + 1 , …., xk + q) – Lk.
Dónde: q = constante entera,
La definición excluye implícitamente los puntos de solución no factibles.

Por ejemplo, en el caso en que xk = 3, q = 4 y Lk = (6), N(xk) = (-1,0,1,2,4,5,6,7,) – (6)

= (1,2,,4,5,7).
Los elementos sombreados son no factibles.
Como se explica, le siguiente movimiento de búsqueda xk+1 puede seleccionarse como
el mejor entre todas las soluciones en N(xk), o como un elemento aleatorio de N(xk)
(selección de caminata aleatoria).

28
La tabla 10.5 proporciona 5 iteraciones del algoritmo de BT. La búsqueda se inicia en
X0 = 1 (seleccionado al azar dese (1,2, ..., 8), utilizando R= 0.0935).
Definimos la vecindad con q=4 y consideramos un periodo de permanencia fijo τ =3
iteraciones (el periodo de permanencia puede ser aleatorio).
Para ilustrar los cálculos, N (x0 =1) = {2, 3, 4, 5}.
En la iteración 1, L1 = {1} y R1=0.4128 seleccione x1=3 a partir de N(x0), la cual
resulta N(x1) = {1, 2, 4, 5, 6, 7} - {1} = {2, 4, 5, 6, 7} y actualiza la lista tabú en la
iteración 2 para L2 = {1, 3}.

Se elimina un elemento de la lista tabú según el primero en entrar es el primero en salir

después de un periodo de permanencia de t=3 iteraciones sucesivas.
Por ejemplo, el elemento {1} permanece en la lista tabú durante las iteraciones 1, 2, y 3
hasta que se elimina en la iteración 4.

RESOLUCIÓN DE PROBLEMAS

Se muestra diversos problemas aplicando lo visto en este trabajo.

Aplicando el método r y a

1. Suponga que la empresa ABS produce 3 tipos de productos. El producto X se vende

en forma unitaria y produce una utilidad de 50 dólares la pieza: el producto y se
vende en forma unitaria y produce una utilidad de 60 dólares la pieza; y el producto
Z se vende a granel produce una utilidad de 20 dólares el Kilogramo. Los tres
productos requieren un mismo tipo de materia prima y horas de mano de obra. Se
dispone 30 Kg de materia prima y 40 horas de mano de obra a la semana.
Determine el plan de producción óptimo que permita maximizar las utilidades, Los
requerimientos de materia prima y mano de obra se dan en la siguiente tabla:

Recurso 1 pieza X 1 pieza Y 1 pieza Z

Materia prima 1.9 kg 2.2 kg 1 kg

Mano de obra 2.4horas 2.8 horas 1 hora

PASOS PARA EL ALGORITMO R Y A

En un problema de maximización, con cota inferior Z=-∞ inicialmente e i=0
 Agotamiento y ramificación: El subproblema se resuelve y analiza
- Si está agotado, se actualiza Z si es necesario o si es solución óptima.
- Si no está agotado se pasa a ramificación.
 Ramificación: Se escoge una variable xj con valor óptimo xj* y se establece
nuevas restricciones

29
SP , x j ≤ x¿j

SP , x j > x ¿j+1

Resolver el modelo de
programación lineal
entera relajado

Elegir una variable

cuyo valor en la
¿La solución sea
Solución
solución fraccional
óptima
es entera?

Resolver dos problemas

Final
iguales al anterior con las
restricciones añadidas

Xj<xj*Y

Xj>xj*+1

Analizar solamente el
Elegir el problema problema con mejor
con mejor valor de solución que
función objetivos cualquiera de las
otras soluciones
enteras conocidas

CONSIDERACIONES
 Ramificación a partir de subproblema con valor más cercano a la solución
óptima.
 Aplicación de nuevas restricciones una a una
 Pueden haber varias soluciones óptimas para un problema

Solución:

Definiendo variables de decisión:

X1=Número de productos X vendidos (unidades)

X2=Número de productos Y vendidos (unidades)
X3=Número de kilogramos Z venidos (kilogramos)

30
Función objetivo:

MaxZ= 50($/un)*X1(un) + 60($/un)*X2(un) + 20($/kg)*X3(kg)

Restricciones:

 Máxima cantidad de materia prima

1.9 X1 + 2.2 X2 + 1X3 ≤ 30
 Máxima cantidad de horas en mano de obra
2.4 X1 + 2.8 X2 + 1 X3 ≤ 40

Iterando por el método simplex:

  Cj 50 60 20 0 0    
CB XB X1 X2 X3 S1 S2 bi Oi
0 S1 1.9 2.2 1 1 0 30 13.636
0 S2 2.4 2.8 1 0 1 40 14.286
  Z -50 -60 -20 0 0 0  
60 X2 0.8636 1 0.4545 0.4545 0 13.636  
0 S2 -0.018 0 -0.273 -1.273 1 1.8182  
  Z 1.8182 0 7.2727 27.273 0 818.18  

Solución:

X2= 13.636
Z= 818.18

31
32
 Most
rando
iterac
iones Cj 50 60 20 0 0 0    
para
el
PL1: 
CB XB X1 X2 X3 S1 S2 S3 bi Oi
0 S1 1.9 2.2 1 1 0 0 30 13.636
0 S2 2.4 2.8 1 0 1 0 40 14.286
0 S3 0 1 0 0 0 1 13 13
  Z -50 -60 -20 0 0 0 0  
0 S1 1.9 0 1 1 0 -2.2 1.4 0.7368
0 S2 2.4 0 1 0 1 -2.8 3.6 1.5
60 X2 0 1 0 0 0 1 13 -
  Z -50 0 -20 0 0 60 780  
50 X1 1 0 0.5263 0.5263 0 -1.158 0.7368  
0 S2 0 0 -0.263 -1.263 1 -0.021 1.8316  
60 X2 0 1 0 0 0 1 13  
  Z 0 0 6.3158 26.316 0 2.1053 816.84  

Solución:
X1=0.737, X2=13, Z=816.84
Continuando con los pasos del algoritmo R y A
Debemos investigar PL1 más a fondo, se crea PL3 y PL4 usando las ramas respectivas
X1≤0 Y 1≤X1.

33
34
Para
PL3:  Cj 50 60 20 0 0 0 0    

CB XB X1 X2 X3 S1 S2 S3 S4 S5 bi
0 S1 1.9 2.2 1 1 0 0 0 0 30
0 S2 2.4 2.8 1 0 1 0 0 0 40
0 S3 0 1 0 0 0 1 0 0 13
0 S4 1 0 0 0 0 0 1 0 0
0 S5 0 0 1 0 0 0 0 1 1
  Z -50 -60 -20 0 0 0 0 0 0
0 S1 1.9 0 1 1 0 -2.2 0 0 1.4
0 S2 2.4 0 1 0 1 -2.8 0 0 3.6
60 X2 0 1 0 0 0 1 0 0 13
0 S4 1 0 0 0 0 0 1 0 0
0 S5 0 0 1 0 0 0 0 1 1
  Z -50 0 -20 0 0 60 0 0 780
0 S1 0 0 1 1 0 -2.2 -1.9 0 1.4
0 S2 0 0 1 0 1 -2.8 -2.4 0 3.6
60 X2 0 1 0 0 0 1 0 0 13
50 X1 1 0 0 0 0 0 1 0 0
0 S5 0 0 1 0 0 0 0 1 1
  Z 0 0 -20 0 0 60 50 0 780
0 S1 0 0 0 1 0 -2.2 -1.9 -1 0.4
0 S2 0 0 0 0 1 -2.8 -2.4 -1 2.6

35
Para PL15:
  Cj 50 60 20 0 0 0 0      
CB XB X1 X2 X3 S1 S2 S3 S4 S5 bi Oi
0 S1 1.9 2.2 1 1 0 0 0 0 30 13.636
0 S2 2.4 2.8 1 0 1 0 0 0 40 14.286
0 S3 0 1 0 0 0 1 0 0 13 13
0 S4 1 0 0 0 0 0 1 0 0 -
0 S5 0 0 1 0 0 0 0 1 1 -
  Z -50 -60 -20 0 0 0 0 0 0  
0 S1 1.9 0 1 1 0 -2.2 0 0 1.4 0.7368
0 S2 2.4 0 1 0 1 -2.8 0 0 3.6 1.5
60 X2 0 1 0 0 0 1 0 0 13 -
0 S4 1 0 0 0 0 0 1 0 0 0
0 S5 0 0 1 0 0 0 0 1 1 -
  Z -50 0 -20 0 0 60 0 0 780  
0 S1 0 0 1 1 0 -2.2 -1.9 0 1.4 1.4
0 S2 0 0 1 0 1 -2.8 -2.4 0 3.6 3.6
60 X2 0 1 0 0 0 1 0 0 13 -
50 X1 1 0 0 0 0 0 1 0 0 -
0 S5 0 0 1 0 0 0 0 1 1 1
  Z 0 0 -20 0 0 60 50 0 780  
0 S1 0 0 0 1 0 -2.2 -1.9 -1 0.4  
0 S2 0 0 0 0 1 -2.8 -2.4 -1 2.4  
60 X2 0 1 0 0 0 1 0 0 11  
50 X1 1 0 0 0 0 0 1 0 2  
20 X3 0 0 1 0 0 0 0 1 2  
  Z 0 0 0 0 0 60 50 20 800  

36
SOLUCIÓN ÓPTIMA:

X1: 2 unidades de producto X vendidas

X2: 11unidades de producto Y vendidas
X3: 2 kilogramos de producto Z vendidos
S2: 2.4 horas de mano de obra sobrantes
Z: $ 800 de utilidad

37
Aplicando el algoritmo de programación lineal entera – tipo binario. (Ramificación
y Acotamiento)

Ejemplo:

La Quemist chemical Company está considerando 3 posibles proyectos de mejora para

su planta: un nuevo convertidor catalítico, un nuevo programa de computadora para
controlar sus operaciones y la expansión de su almacén. Los requerimientos de capital y
las limitaciones de presupuesto en los dos años siguientes impiden que la firma
emprenda todos los proyectos en este momento, el valor actual neto (VAN) de cada uno
de los proyectos, los requerimientos de capital y los fondos disponibles para los dos
años siguientes se presentan en la siguiente tabla.
¿Qué proyectos deberían ejecutarse para maximizar la inversión?
Observación:
Si se realizan los 3 proyectos a la vez, los fondos disponibles son insuficientes. Por lo
tanto, la solución trivial de hacer de manera parcial los 3, no es posible.
Proyecto VAN ($) Año 1($) Año 2($)
Convertidor catalítico 25000 8000 7000
Software 18000 6000 4000
Almacén 32000 12000 8000
fondos disponibles   20000 16000

Formulación del Modelo Binario

Variables de decisión: Debemos emprender que proyecto o mezcla de proyectos se
deben emprender.
X1: Proyecto “Convertidor catalítico” realizado
X2: Proyecto “Software” realizado
X3: Proyecto “Almacén” realizado
Donde los X1 tomarán los siguientes valores:
Xi={1(el proyecto se realiza), 0 (el proyecto no se realiza)}

38
Función Objetivo:
Max el VAN total, producto de la ejecución de los proyectos.
MaxZ($)=25000*X1 + 18000*X2 + 32000*X3
Restricciones:
Que los requerimientos de capital no excedan el presupuesto.
Año 1:
8000*X1 + 6000*X2 + 12000*X3 ≤ 20000 ($)
Año 2:
7000*X1 + 4000*X2 + 8000*X3 ≤ 16000 ($)

39
CAMINO A TOMAR:

Valores de Valores de variables Valores de la

Elección
variables fijos obtenidas función objetivo
X1=0 X2=3.3, X3=0 60000 No
X1=1 X2=2, X3=0 61000 Si
Se toma el camino X1=1
X2=0 X3=1 57000(*) No
X2=1 X3=0.5 59000 SI
Se toma el camino X2=1
X3=0 - 43000(#) si
X3=1 - No se puede No

Si se compara el valor de Z obtenido en (*) y (#), el mayor valor de Z es 57000, por lo

que este será nuestro resultado óptimo.
MaxZ($)= 25000*(1) + 18000*(0) + 32000*(1) ($)

Z=57000$, por lo que este será nuestro resultado óptimo.

MaxZ($)= 25000*(1) + 18000* (0) + 32000*(1) ($)
Z=57000$
Y los proyectos que se deberán llevar a cabo son los de la obtención del convertidor
catalítico y la expansión de almacén.

Método aditivo de balas

Se debe realizar una transformación a nuestra función objetivo con tal de que podamos
resolver nuestro problema con este método:
Max Z($) = 25000*X1 + 18000*X2 + 32000*X3 ($)
S.a.
8000*X1 + 6000*X2 + 12000*X3 ≤ 20000 ($)
7000*X1 + 4000*X2 + 8000*X3 ≤ 16000 ($)
Min W($)= -25000*X1 -18000*X2 – 32000*X3
s.a.
8000*X1 + 6000*X2 + 12000*X3 ≤ 20000 ($)
7000*X1 + 4000*X2 + 8000*X3 ≤ 16000 ($)

40
Se realiza el cambio e X1=1-X1
MinX($)=25000*X1 + 18000*X2 +32000*X3 -75000
s.a.
-8000*X1 -6000*X2-12000*X3 + 6000 ≤ 0
-7000*X1 -4000*X2 -8000*X3 + 3000 ≤ 0
En el siguiente recuadro se encuentran todas las iteraciones para la realización del
método:

X1 0 1 0 0 10 1
X2 0 0 1 0 11 0
X3 0 0 0 1 01 1
- -
R1 6000 -2000 0 -6000 -8000
12000 14000
-
R2 3000 -4000 -1000 -5000 -8000 -9000
12000
Z 0 25000 18000 32000 43000 50000 57000

Del cuadro se obtiene el mismo resultado que con el método pasado, en la fila Z es
57000 $ y siguen realizándose los mismos proyectos.

PLANO DE CORTE

ALGORITMO DE PLANOS DE CORTE

Este método al igual que el de B&B inicia en la solución óptima continua de PL y
consiste en agregar restricciones especiales al espacio de soluciones con el objetivo que
se pueda producir un punto extremo óptimo entero. Estas restricciones que serán
agregadas son denominadas cortes. En otras palabras, con este algoritmo se busca
cambiar el conjunto convexo del espacio de soluciones, de tal forma que los puntos
extremos lleguen a ser todos enteros. A pesar de los cambios que se efectuarán a las
fronteras del espacio de soluciones, permanecerán los conjuntos convexos. Po otro lado,
este cambio deberá realizarse sin que se ‘parta’ alguna de las soluciones enteras
factibles del problema original.

Plano de corte fraccional

ALGORITMO FRACCIONAL (ENTERO PURO)

Para la aplicación de este algoritmo es necesario que todos los coeficientes y el término
independiente o derecho de cada restricción sean enteros. Esto se debe a que en el
algoritmo entero puro todas las variables deben ser enteras, incluyendo a las holguras.

41
La presencia de coeficientes fraccionarios no permitirá que dichas variables tomen
valores enteros. Es en ese caso que el problema tendrá una solución entera factible, mas
solo en función de las variables que no son holguras.
A continuación es explicará de manera algebraica este algoritmo. Sea la tabla Óptima
final para el PL cuya solución no es entera:

Básic w1 wj ⋯
x1 ⋯ xi ⋯ xm ⋯ wn Solución
a
x1 1 ⋯ 0 ⋯ 0 α 11 ⋯ α 1j ⋯ α n1 β1
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
xi 0 ⋯ 1 ⋯ 0 α 1i ⋯ α ij ⋯ α ni βi
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
xm 0 ⋯ 0 ⋯ 1 α 1m ⋯ α mj ⋯ α 1m βm
Z 0 ⋯ 0 ⋯ 0 ć 1 ⋯ ć j ⋯ ć n β0

En la tabla, las variables xi (i=1, 2, 3,…, m) representan a las variables básicas y las
variables no básicas wi (i=1, 2, 3,…, n), representan a las variables no básicas. Ahora, de
definirá como la ecuación de restricción de la variable básica no entera xi:

x i+ α 1i w1 + α 2i w2 +…+ α ni w n=β i
n
x i=β i−∑ α ij w j (1)
j=1

A estas ecuaciones se les denominará renglón fuente o fila origen, donde también
puede incluirse a la ecuación de Z.
Luego, se define:
β i=[ β i ] +f i (2)

α ij= [ α ij ] +f ij (3)

Donde [ β i ] y [ α ij ] son los mayores enteros posibles para β i y α ij respectivamente. Por lo

que se deduce que f i y f ij están son fracciones dentro del rango ¿ 0 ; 1>¿. Reemplazando
(2) y (3) en la fila origen (1):
n n
f i−∑ f ij w j=x i− [ βi ] + ∑ [ α ij ] w j
j=1 j=1

42
Como el objetivo de este algoritmo es que todas las variables sean enteras, el segundo
miembro debe ser entero, es así que el primer miembro también deberá serlo. Se sabe
además que f ij , w j ≥ 0 . De esto, puede deducirse:
n n

∑ f ij w j ≥ 0 y f i−∑ f ij w j ≤ f i
j=1 j=1

n
Como f i−∑ f ij w j debe ser entero por construcción, la expresión anterior también
j=1

puede ser escrita como:

n
f i−∑ f ij w j ≤0
j=1

Esta restricción podrá ser representada mediante:

n
Si=∑ f ij w j−f i
j=1

La expresión anterior será el denominado corte fraccional. En la siguiente tabla se

presenta luego de agregar el corte fraccional:

Básica x1 ⋯ xi ⋯ xm w1 ⋯ wj ⋯ wn Si Solución
x1 1 ⋯ 0 ⋯ 0 α 11 ⋯ α 1j ⋯ α n1 0 β1
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
xi 0 ⋯ 1 ⋯ 0 α 1i ⋯ α ij ⋯ α nj 0 βi
⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮
xm 0 ⋯ 0 ⋯ 1 α 1m ⋯ α mj ⋯ α 1m 0 βm
Si 0 ⋯ 0 ⋯ 0 −f i 1 ⋯ −f i j ⋯ −f i n 1 −f i
Z 0 ⋯ 0 ⋯ 0 ć 1 ⋯ ć j ⋯ ć n 0 β0

Debido a que la solución anterior no cumplirá el criterio de factibilidad, se empleará el

método simplex dual para realizar la siguiente iteración. En caso la nueva solución sea
entera, el procedimiento termina; caso contrario, se deberán agregar nuevos cortes
fraccionarios y emplear el método simplex dual hasta que se determine una solución
entera. Sin embargo, en caso que en alguna de las iteraciones el algoritmo simplex dual
determina que existe solución factible, esto querrá decir que el problema no presenta
una solución factible entera. Se debe tomar en cuenta que solo podrán agregarse cortes
fraccionarios hasta que el número de restricciones no sobrepase m+n.

Fuerza o vigor del corte fraccional

Esta puede medirse en términos de qué tan profundamente corta la desigualdad dentro
del espacio de soluciones. Se expresa de la siguiente manera:

43
Sean dos desigualdades
n

∑ f ij w j ≥ f i … … . 1
j=1

∑ f kj w j ≥ f k … . ..2
j=1

El corte 1 será más fuerte que el corte siempre y cuando f i ≥ f k y f ij ≤ f kj , para toda j. A
partir de esta expresión, se generan dos reglas empíricas, siendo la más efectiva:

fi
Máx
{ }n

∑ f ij
j=1

APLICACIÓN DEL ALGORTIMO DE PLANO CORTANTE A UN PROBLEMA DE PLE

EJERCICIO 1
MAXIMIZAR Z=2990 X 1 +1075 X 2 MAXIMIZAR Z=2990 X 1 +1075 X 2

1 X 1 +0.75 X 2 ≤100 1 X 1 +0.75 X 2 +S 1=100

0.75 X 1 +0.6 X 2 ≤ 80 0.75 X 1 +0.6 X 2+ S 2=80

13 X 1 +9 X 2 ≤ 900 13 X 1 +9 X 2 + S3 =900

4 X 1 +3 X 2 ≤320 4 X 1 +3 X 2 + S4 =320

1 X 1 +0.8 X 2 ≤80 1 X 1 +0.8 X 2 + S5=80

0.5 X 1 +0.5 X 2 ≤ 60 0.5 X 1 +0.5 X 2+ S6 =60

X 1 , X 2 ≥0

Resolviendo mediante el método simplex

44
TABLA INICIAL

cj 2990 1075 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 bj θj
0 S1 1 3/4 1 0 0 0 0 0 100 100
0 S2 3/4 3/5 0 1 0 0 0 0 80 320/3
0 S3 13 9 0 0 1 0 0 0 900 900/13
0 S4 4 3 0 0 0 1 0 0 320 320/3
0 S5 1 4/5 0 0 0 0 1 0 80 80
0 S6 1/2 1/2 0 0 0 0 0 1 60 120
Z - - 0 0 0 0 0 0 0
2990 1075

TABLA ÓPTIMA

cj 2990 1075 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 bj
0 S1 0 3/52 1 0 - 1/13 0 0 0 30 10/13
0 S2 0 21/260 0 1 - 3/52 0 0 0 28 1/13
2990 X1 1 9/13 0 0 1/13 0 0 0 69 3/13
0 S4 0 3/13 0 0 - 4/13 1 0 0 43 1/13
0 S5 0 7/65 0 0 - 1/13 0 1 0 10 10/13
0 S6 0 2/13 0 0 - 1/26 0 0 1 25 5/13
Z 0 995 0 0 230 0 0 0 207000

De la tabla óptima podemos observar que la solución óptima corresponde a:

 Z = 207000

3  S3=0
 X 1 =69
13 1
 S4 =43
 X 2 =0 13
10 10
 S1=30  S5=10
13 13
1 5
 S2=28  S6 =25
13 13

Se observa que el valor de las variables son fraccionarias o cero. Se determinará una
solución entera mediante el método de plano cortante:

45
De la tabla óptima, pueden escribirse las siguientes ecuaciones de restricción:

 Ecuación Z : Z+ 995 X 2+ 230 S 3=207000

9 1 900
 Ecuación X 1 : X 1 + X 2 + S3 =
13 13 13

3 1 10
 Ecuación S1 :S 1+ X 2− S 3=30
52 13 13

21 3 1
 Ecuación S2 :S 2+ X 2− S 3=28
260 52 13

3 4 1
 Ecuación S4 : S 4+ X − S =43
13 2 13 3 13

7 1 10
 Ecuación S5 :S 5 + X 2− S3 =10
65 13 13

2 1 5
 Ecuación S6 :S 6 + X − S =25
13 2 26 3 13

Empleamos arbitrariamente como fila de origen para generar el primer corte a la

ecuación de X1, pues esta cumple con el requisito que su lado derecho sea fraccionario.
Es así que factorizamos dicha ecuación y colocamos los componentes enteros al lado
izquierdo y todos los componentes fraccionarios al lado derecho:
9 1 900
X1+ X 2 + S3 =
13 13 13
9 1 3
X1+ X 2+ S3 =69+
13 13 13
3 9 1
X 1 −69= − X2− S3
13 13 13
Dado que X2 y S3 son no negativas, el lado derecho debe satisfacer la siguiente
desigualdad:
3 9 1 3
− X 2 − S3 ≤
13 13 13 13

46
Por construcción, el lado izquierdo inicial debe es entero, el lado derecho también debe
serlo, es así que la desigualdad anterior, puede reemplazarse mediante:
3 9 1
− X 2 − S3 ≤ 0
13 13 13

Es así que se obtiene el primer corte o también denominado corte fraccionario debido a
sus coeficientes. Al ser las variables X2 = S3=0, se dice que la solución actual infringe el
3
corte, ya que al reemplazar los valores en el corte resulta ≤ 0. Es debido a esto que si
13
se agrega este corte a la tabla óptima el punto extremo óptimo moverá la solución con el
objetivo de cumplir las restricciones enteras.
Es posible implementar el corte mediante:

3 9 1
− X 2− S3 + S7 =0 ; S 7 ≥0
13 13 13

cj 2990 1075 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 bj
0 S1 0 3/52 1 0 - 0 0 0 0 30 10/13
1/13
0 S2 0 21/260 0 1 - 0 0 0 0 28 1/13
3/52
2990 X1 1 9/13 0 0 1/13 0 0 0 0 69 3/13
0 S4 0 3/13 0 0 - 1 0 0 0 43 1/13
4/13
0 S5 0 7/65 0 0 - 0 1 0 0 10 10/13
1/13
0 S6 0 2/13 0 0 - 0 0 1 0 25 5/13
1/26
0 S7 0 - 9/13 0 0 - 0 0 0 1 - 3/13
1/13
Z 0 995 0 0 230 0 0 0 0 207000

47
Aplicando el método simplex dual:

cj 2990 1075 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 bj
0 S1 0 3/52 1 0 - 0 0 0 0 30 10/13
1/13
0 S2 0 21/260 0 1 - 0 0 0 0 28 1/13
3/52
2990 X1 1 9/13 0 0 1/13 0 0 0 0 69 3/13
0 S4 0 3/13 0 0 - 1 0 0 0 43 1/13
4/13
0 S5 0 7/65 0 0 - 0 1 0 0 10 10/13
1/13
0 S6 0 2/13 0 0 - 0 0 1 0 25 5/13
1/26
0 S7 0 - 9/13 0 0 - 0 0 0 1 - 3/13
1/13
Z 0 995 0 0 230 0 0 0 207000

cj 2990 1075 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 bj
0 S1 0 0 1 0 - 1/12 0 0 0 1/12 30 3/4
0 S2 0 0 0 1 - 1/15 0 0 0 7/60 28 1/20
2990 X1 1 0 0 0 0 0 0 0 1 69
0 S4 0 0 0 0 - 1/3 1 0 0 1/3 43
0 S5 0 0 0 0 - 4/45 0 1 0 7/45 10 11/15
0 S6 0 0 0 0 - 1/18 0 0 1 2/9 25 1/3
1075 X2 0 1 0 0 1/9 0 0 0 -1 4/9 1/3
Z 0 0 0 0 119 0 0 0 1437 206668
4/9 2/9 1/3

Como podemos observar en la tabla, el valor de algunas variables continúa siendo

fraccionario, por lo que añadiremos un segundo corte. El corte asociado corresponderá a
la Ecuación de X2:
1 4 1
 Ecuación X 2 : X 2 + S3 −1 S7 =
9 9 3

48
 Efectuamos la factorización y operaciones correspondientes al igual que en el primer
corte:

1
X 2 + S 3−¿
9
1 1 4
X 2 −S 7= − S3 + S7
3 9 9
1 1 4 1
− S3 + S 7 ≤
3 9 9 3
1 1 4
− S3 + S 7 ≤0
3 9 9
−1 4 1
S 3 + S 7 ≤−
9 9 3

Se agregará a la tabla la expresión anterior en forma de igualdad:

−1 4 −1
S + S +S = ; S8 ≥ 0
9 3 9 7 8 3

cj 2990 1075 0 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 S8 bj
0 S1 0 0 1 0 - 1/12 0 0 0 1/12 0 30 3/4
0 S2 0 0 0 1 - 1/15 0 0 0 7/60 0 28 1/20
2990 X1 1 0 0 0 0 0 0 0 1 0 69
0 S4 0 0 0 0 - 1/3 1 0 0 1/3 0 43
0 S5 0 0 0 0 - 4/45 0 1 0 7/45 0 10 11/15
0 S6 0 0 0 0 - 1/18 0 0 1 2/9 0 25 1/3
1075 X2 0 1 0 0 1/9 0 0 0 -1 4/9 0 1/3
0 S8 0 0 0 0 -1/9 0 0 0 4/9 1 -1/3
Z 0 0 0 0 119 0 0 0 1437 0 206668
4/9 2/9 1/3

49
 Aplicamos nuevamente el método simplex dual:

cj 2990 1075 0 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 S8 bj
0 S1 0 0 1 0 - 1/12 0 0 0 1/12 0 30 3/4
0 S2 0 0 0 1 - 1/15 0 0 0 7/60 0 28 1/20
2990 X1 1 0 0 0 0 0 0 0 1 0 69
0 S4 0 0 0 0 - 1/3 1 0 0 1/3 0 43
0 S5 0 0 0 0 - 4/45 0 1 0 7/45 0 10 11/15
0 S6 0 0 0 0 - 1/18 0 0 1 2/9 0 25 1/3
1075 X2 0 1 0 0 1/9 0 0 0 -1 4/9 0 1/3
0 S8 0 0 0 0 -1/9 0 0 0 4/9 1 -1/3
Z 0 0 0 0 119 0 0 0 1437 0 206668
4/9 2/9 1/3

cj 2990 1075 0 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 S8 bj
0 S1 0 0 1 0 0 0 0 0 - 1/4 - 3/4 31
0 S2 0 0 0 1 0 0 0 0 - 3/20 - 3/5 28 1/4
2990 X1 1 0 0 0 0 0 0 0 1 0 69
0 S4 0 0 0 0 0 1 0 0 -1 -3 44
0 S5 0 0 0 0 0 0 1 0 - 1/5 - 4/5 11
0 S6 0 0 0 0 0 0 0 1 0 - 1/2 25 1/2
1075 X2 0 1 0 0 0 0 0 0 -1 1 0
0 S3 0 0 0 0 1 0 0 0 -4 -9 3
Z 0 0 0 0 0 0 0 0 1915 1075 206310

Se observa que nuevamente existen variables no enteras, por lo que añadiremos un

tercer corte. Esta vez, se empleará la ecuación de restricción de S2 :
3 3 1
 Ecuación S2 :S 2− S − S =28
20 7 5 8 4

50
 Efectuamos la factorización y operaciones correspondientes al igual que en los cortes
anteriores:

3 3 1
S2 −
20 (
S 7− S 8= 28+
5 4 )
1 3 3
S2−28= + S7 + S 8
4 20 5
1 3 3 1
+ S7 + S 8 ≤
4 20 5 4
1 3 3
+ S7 + S 8 ≤ 0
4 20 5
3 3 1
S7 + S8 ≤−
20 5 4

Se agregará a la tabla la expresión anterior en forma de igualdad:

3 3 −1
S7 + S8 + S 9 = ; S9≥ 0
20 5 4

Sin embargo, antes de agregar la nueva restricción a la tabla podemos notar que esta
igualdad no podrá ser satisfecha puesto que S7 , S 8 , S9 ≥ 0. Ahora comprobaremos
mediante la aplicación del algoritmo simplex dual que no existe solución factible entera:

cj 2990 1075 0 0 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 S8 S9 bj
0 S1 0 0 1 0 0 0 0 0 - 1/4 - 3/4 0 31
0 S2 0 0 0 1 0 0 0 0 - 3/20 - 3/5 0 28 1/4
2990 X1 1 0 0 0 0 0 0 0 1 0 0 69
0 S4 0 0 0 0 0 1 0 0 -1 -3 0 44
0 S5 0 0 0 0 0 0 1 0 - 1/5 - 4/5 0 11
0 S6 0 0 0 0 0 0 0 1 0 - 1/2 0 25 1/2
1075 X2 0 1 0 0 0 0 0 0 -1 1 0 0
0 S3 0 0 0 0 1 0 0 0 -4 -9 0 3
0 S9 0 0 0 0 0 0 0 0 3/20 3/5 1 -1/4
Z 0 0 0 0 0 0 0 0 1915 1075 0 206310

51
Sabemos que para la aplicación del algoritmo simplex dual debe existir un b j negativo,
el cual se encuentra en la fila S9, la cual es nuestra fila pivote. No obstante, es imposible
seleccionar una columna pivote debido a que en ninguna de ellas se cumplirá
z j−c j
Max {aij
/aij < 0 .}
Como se mencionó al inicio, para poder aplicar el algoritmo de plano cortante
fraccional, es necesario que todos los términos de lado derecho de las restricciones
iniciales sean enteros. Se puede observar, que al resolver el problema planteado sin
convertir a enteros los términos independientes, repercute en la solución óptima, al no
proporcionar que todas las variables sean enteras.
Ahora resolveremos el problema planteado, cumpliendo la condición que los bj sean
enteros
MAXIMIZAR Z=2990 X 1 +1075 X 2 MAXIMIZAR Z=2990 X 1 +1075 X 2

1 X 1 +0.75 X 2 ≤100 4 X 1 +3 X 2 + S1=400

0.75 X 1 +0.6 X 2 ≤ 80 15 X 1 +12 X 2 +S 2=1600

13 X 1 +9 X 2 ≤ 900 13 X 1 +9 X 2 + S3 =900

4 X 1 +3 X 2 ≤320 4 X 1 +3 X 2 + S4 =320

1 X 1 +0.8 X 2 ≤80 5 X 1 +4 X 2 +S 5=400

0.5 X 1 +0.5 X 2 ≤ 60 1 X 1 +1 X 2+ S 6=120

X 1 , X 2 ≥0

Resolviendo mediante el método simplex

TABLA INICIAL

cj 2990 1075 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 bj θj
0 S1 4 3 1 0 0 0 0 0 400 100
0 S2 15 12 0 1 0 0 0 0 1600 106
2/3
0 S3 13 9 0 0 1 0 0 0 900 69
3/13
0 S4 4 3 0 0 0 1 0 0 320 80
0 S5 5 4 0 0 0 0 1 0 400 80
0 S6 1 1 0 0 0 0 0 1 120 120
Z - - 0 0 0 0 0 0 0
2990 1075

52
53
TABLA ÓPTIMA

cj 2990 1075 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 bj
0 S1 0 3/13 1 0 - 4/13 0 0 0 123 1/13
0 S2 0 1 8/13 0 1 -1 0 0 0 561 7/13
2/13
2990 X1 1 9/13 0 0 1/13 0 0 0 69 3/13
0 S4 0 3/13 0 0 - 4/13 1 0 0 43 1/13
0 S5 0 7/13 0 0 - 5/13 0 1 0 53 11/13
0 S6 0 4/13 0 0 - 1/13 0 0 1 50 10/13
Z 0 995 0 0 230 0 0 0 207000

De la tabla óptima podemos observar que la solución óptima corresponde a:

 Z = 207000

3
 X 1 =69
13
 X 2 =0
1
 S1=123
13
7
 S2=561
13
 S3=0
1
 S4 =43
13
11
 S5=53
13

54
 10
S6 =50 Se observa que el valor de las variables son fraccionarias o cero. Se
13
determinará una solución entera mediante el método de plano cortante:
De la tabla óptima, pueden escribirse las siguientes ecuaciones de restricción:
 Ecuación Z : Z+ 995 X 2+ 230 S 3=207000

9 1 3
 Ecuación X 1 : X 1 + X + S =69
13 2 13 3 13

3 4 1
 Ecuación S1 :S 1+ X 2− S3=123
13 13 13

8 2 7
 Ecuación S2 :S 2+ 1 X 2−1 S3 =561
13 13 13

3 4 1
 Ecuación S4 : S 4+ X 2− S3 =43
13 13 13

7 5 11
 Ecuación S5 :S 5 + X 2− S3 =53
13 13 13

4 1 10
 Ecuación S6 :S 6 + X − S =50
13 2 13 3 13

Empleamos arbitrariamente como fila de origen para generar el primer corte a la

ecuación de X1, pues esta cumple con el requisito que su lado derecho sea fraccionario.
Es así que factorizamos dicha ecuación y colocamos los componentes enteros al lado
izquierdo y todos los componentes fraccionarios al lado derecho:
9 1 900
X1+ X 2 + S3 =
13 13 13
9 1 3
X1+ X + S =69+
13 2 13 3 13
3 9 1
X 1 −69= − X2− S3
13 13 13
Dado que X2 y S3 son no negativas, el lado derecho debe satisfacer la siguiente
desigualdad:
3 9 1 3
− X 2 − S3 ≤
13 13 13 13
Por construcción, el lado izquierdo inicial debe es entero, el lado derecho también debe
serlo:

55
 3 9 1
− X 2 − S3 ≤ 0
13 13 13
Es así que se obtiene el primer corte:
3−9 X 2−1 S 3 +S 7=0; S 7 ≥ 0

cj 2990 1075 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 bj
0 S1 0 3/13 1 0 - 4/13 0 0 0 123 1/13 0
0 S2 0 1 0 1 -1 2/13 0 0 0 561 7/13 0
8/13
299 X1 1 9/13 0 0 1/13 0 0 0 69 3/13 1
0
0 S4 0 3/13 0 0 - 4/13 1 0 0 43 1/13 0
0 S5 0 7/13 0 0 - 5/13 0 1 0 53 11/13 0
0 S6 0 4/13 0 0 - 1/13 0 0 1 50 10/13 0
0 S7 0 - 9 0 0 - 1 0 0 0 1 - 3
Z 0 995 0 0 230 0 0 0 0 20700
0

Aplicando el método simplex dual:

cj 299 1075 0 0 0 0 0 0 0
0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 bj
0 S1 0 3/13 1 0 - 4/13 0 0 0 123 0
1/13
0 S2 0 1 8/13 0 1 -1 2/13 0 0 0 561 0
7/13
299 X1 1 9/13 0 0 1/13 0 0 0 69 3/13 1
0
0 S4 0 3/13 0 0 - 4/13 1 0 0 43 1/13 0
0 S5 0 7/13 0 0 - 5/13 0 1 0 53 11/13 0
0 S6 0 4/13 0 0 - 1/13 0 0 1 50 10/13 0
0 S7 0 - 9 0 0 - 1 0 0 0 1 - 3
Z 0 995 0 0 230 0 0 0 0 20700
0

cj 2990 1075 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 bj
0 S1 0 0 1 0 - 1/3 0 0 0 1/3 123
0 S2 0 0 0 1 -1 1/3 0 0 0 2 1/3 561
299 X1 1 0 0 0 0 0 0 0 1 69
0

56
 0 S4 0 0 0 0 - 1/3 1 0 0 1/3 43
0 S5 0 0 0 0 - 4/9 0 1 0 7/9 53 2/3
0 S6 0 0 0 0 - 1/9 0 0 1 4/9 50 2/3
107 X2 0 1 0 0 1/9 0 0 0 -1 4/9 1/3
5
Z 0 0 0 0
119 0 0 0 1437 206668
4/9 2/9 1/3
Como podemos observar en la tabla, el valor de algunas variables continúa siendo
fraccionario, por lo que añadiremos un segundo corte. El corte asociado corresponderá a
la Ecuación de X2:
1 4 1
 Ecuación X 2 : X 2 + S3 −1 S7 =
9 9 3

Efectuamos la factorización y operaciones correspondientes al igual que en el primer

corte:
1
X 2 + S 3−¿
9
1 1 4
X 2 −S 7= − S3 + S7
3 9 9
1 1 4 1
− S3 + S 7 ≤
3 9 9 3
1 1 4
− S3 + S 7 ≤0
3 9 9
−1 4 1
S 3 + S 7 ≤−
9 9 3

Se agregará a la tabla la expresión anterior en forma de igualdad:

−1 S 3+ 4 S7 + S 8=−3 ; S 8 ≥0

cj 2990 1075 0 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 S8 bj
0 S1 0 0 1 0 - 1/3 0 0 0 1/3 0 123
0 S2 0 0 0 1 -1 1/3 0 0 0 2 1/3 0 561
299 X1 1 0 0 0 0 0 0 0 1 0 69
0
0 S4 0 0 0 0 - 1/3 1 0 0 1/3 0 43
0 S5 0 0 0 0 - 4/9 0 1 0 7/9 0 53 2/3
0 S6 0 0 0 0 - 1/9 0 0 1 4/9 0 50 2/3
107 X2 0 1 0 0 1/9 0 0 0 -1 4/9 0 1/3
5
0 S8 0 0 0 0 -1 0 0 0 4 9 -3
Z 0 0 0 0 119 4/9 0 0 0 1437 0 206668

57
2/9 1/3

58
 Aplicamos nuevamente el método simplex dual:

cj 2990 1075 0 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 S8 bj
0 S1 0 0 1 0 - 1/3 0 0 0 1/3 0 123
0 S2 0 0 0 1 -1 1/3 0 0 0 2 1/3 0 561
299 X1 1 0 0 0 0 0 0 0 1 0 69
0
0 S4 0 0 0 0 - 1/3 1 0 0 1/3 0 43
0 S5 0 0 0 0 - 4/9 0 1 0 7/9 0 53 2/3
0 S6 0 0 0 0 - 1/9 0 0 1 4/9 0 50 2/3
107 X2 0 1 0 0 1/9 0 0 0 -1 4/9 0 1/3
5
0 S8 0 0 0 0 -1 0 0 0 4 9 -3
Z 0 0 0 0 119 4/9 0 0 0 1437 0 206668
2/9 1/3

TABLA FINAL

cj 2990 1075 0 0 0 0 0 0 0 0
cb Xb X1 X2 S1 S2 S3 S4 S5 S6 S7 S8 bj
0 S1 0 0 1 0 0 0 0 0 -1 -3 124
0 S2 0 0 0 1 0 0 0 0 -3 -12 565
2990 X1 1 0 0 0 0 0 0 0 1 0 69
0 S4 0 0 0 0 0 1 0 0 -1 -3 44
0 S5 0 0 0 0 0 0 1 0 -1 -4 55
0 S6 0 0 0 0 0 0 0 1 0 -1 51
1075 X2 0 1 0 0 0 0 0 0 -1 1 0
0 S3 0 0 0 0 1 0 0 0 -4 -9 3
Z 0 0 0 0 0 0 0 0 1915 1075 206310

Finalmente, el problema propuesto tiene solución entera factible:

 Z = 207000
 X 1 =69
 X 2 =0
 S1=124
 S2=565
 S3=0
 S4 =44
 S5=55
 S6 =51

59
  Ahora, determinaremos cuál es el corte más fuerte:

PRIMER CORTE:
9 X 2 +1 S 3 ≥ 3

SEGUNDO CORTE:
1 S 3−4 S 7 ≥ 3

fi
n
Al comparar las relaciones de
∑ f ij
j =1

3 3
>
9+1 1−4

Obtenemos que el primer corte efectuado es más fuerte que el segundo.

PROBLEMA TALLER
Resolver mediante el corte fraccionario:

Maximizar Z=4 x 1+ 6 x2 +2 x 3

Sujeto a:

4 x1 −4 x 2 ≤ 5

−x 1+ 6 x2 ≤5

−x 1+ x2 + x 3 ≤ 5

x 1 , x 2 , x 3 ≥ 0 , enteras

SOLUCIÓN

PASO 1: Se verifican que los coeficientes sean enteros y se expresan las restricciones
como igualdades mediante la adición de variables de holgura.

4 x1 −4 x 2 +S 1=5

−x 1+ 6 x2 + S2=5

−x 1+ x2 + x 3 +S 3=5

60
 Cj 4 6 2 0 0 0
Cb Xb X1 X2 X3 S1 S2 S3 bj
0 S1 4 -4 0 1 0 0 5 -
0 S2 -1 6 0 0 1 0 5 5/6
0 S3 -1 1 1 0 0 1 5 5
Z -4 -6 -2 0 0 0 0
0 S1 3 1/3 0 0 1 2/3 0 8 1/3 2.5
6 X2 - 1/6 1 0 0 1/6 0 5/6 -
0 S3 - 5/6 0 1 0 - 1/6 1 4 1/6 -
Z -5 0 -2 0 1 0 5
4 X1 1 0 0 3/10 1/5 0 2 1/2 -
6 X2 0 1 0 1/20 1/5 0 1 1/4 -
0 S3 0 0 1 1/4 0 1 6 1/4 6.25
Z 0 0 -2 1.2 2 0 17 1/2
4 X1 1 0 0 3/10 1/5 0 2 1/2
6 X2 0 1 0 1/20 1/5 0 1 1/4
2 X3 0 0 1 1/4 0 1 6 1/4
Z 0 0 0 1 7/10 2 2 30
De la tabla óptima se obtiene la solución óptima:
 Z= 30

 X1= 2 1/2  S1=0

 X2=1 1/4  S2=0
 X3=6 1/4  S3=0

PASO 2: Se define las ecuaciones de restricción de cada variable con solución fraccional

3 1 1
Ecuación X 1 : X 1 + S + S 2=2
10 1 5 2

1 1 1
Ecuación X 2 : X 2 + S + S2=1
20 1 5 4

1 1
Ecuación X 3 : X 3 + S + S3=6
4 1 4

61
PASO 3: Se escoge arbitrariamente una fila origen para el primer corte y separamos los
términos izquierda (enteros) y derecha (fraccionarios)
Escogemos ecuación X1
3 1 1
X1+ S + S2=2+
10 1 5 2
3 1 1
X 1 −2=− S − S 2+
10 1 5 2

PASO 4: El segundo término debe cumplir

3 1 1 1
− S − S2 + ≤
10 1 5 2 2
PASO 5: Debe ser entero y por construcción
3 1 1
− S − S2 + ≤ 0
10 1 5 2
PASO 6: Se expresa el primer corte de manera que pueda ser agregado a la tabla óptima

3 1 −1
− S − S +S =
10 1 5 2 4 2
PASO 7: Tabla óptima con primer corte

Cj 4 6 2 0 0 0 0
Cb Xb X1 X2 X3 S1 S2 S3 S4 bj
4 X1 1 0 0 3/10 1/5 0 0 2 1/2
6 X2 0 1 0 1/20 1/5 0 0 1 1/4
2 X3 0 0 1 1/4 0 1 0 6 1/4
0 S4 0 0 0 - 3/10 - 1/5 0 1 - 1/2
Z 0 0 -2 1 7/10 2 2 0 30

PASO 8: Aplicación algoritmo simplex dual

Cj 4 6 2 0 0 0 0
Cb Xb X1 X2 X3 S1 S2 S3 S4 bj
4 X1 1 0 0 3/10 1/5 0 0 2 1/2
6 X2 0 1 0 1/20 1/5 0 0 1 1/4
2 X3 0 0 1 1/4 0 1 0 6 1/4
0 S4 0 0 0 - 3/10 - 1/5 0 1 - 1/2
Z 0 0 -2 1 7/10 2 2 0 30
4 X1 1 0 0 0 0 0 1 2
6 X2 0 1 0 0 1/6 0 1/6 1 1/6
2 X3 0 0 1 0 -1/6 1 5/6 5 5/6

62
 0 S1 0 0 0 1 2/3 0 -3 1/3 1 2/3
Z 0 0 0 0 2/3 2 6 2/3 26 2/3

PASO 9: Como aún hay valores fraccionarios se procede a un segundo corte. Esta vez se
empleará a la ecuación X2

1 1 1
Ecuación X 2 : X 2 + S + S 4=1
6 2 6 6

1 1 1
X 2 + S + S 4=1+
6 2 6 6

1 1 1
X 2 −1=− S − S 4 +
6 2 6 6
PASO 10: Se realiza el mismo procedimiento anterior y se obtiene el segundo corte
1 1 1
− S − S 4 + ≤0
6 2 6 6

1 1 −1
− S − S 4 + S5 =
6 2 6 6

PASO 11: Tabla óptima con segundo corte y aplicación simplex dual (Se observará
incumplimiento del criterio de optimalidad: aplicar algoritmo simplex)

4 6 2 0 0 0 0 0
Cb Xb X1 X2 X3 S1 S2 S3 S4 S5 bj
4 X1 1 0 0 0 0 0 1 0 2
6 X2 0 1 0 0 1/6 0 1/6 0 1 1/6
2 X3 0 0 1 0 - 1/6 1 5/6 0 5 5/6
0 S1 0 0 0 1 2/3 0 -3 1/3 0 1 2/3
0 S5 0 0 0 0 - 1/6 0 - 1/6 1 - 1/6
Z 0 0 0 0 2/3 2 6 2/3 0 26 2/3
4 X1 1 0 0 0 -1 0 0 6 1
6 X2 0 1 0 0 0 0 0 1 1
2 X3 0 0 1 0 -1 1 0 5 5
0 S1 0 0 0 1 4 0 0 -20 5
0 S4 0 0 0 0 1 0 1 -6 1
Z 0 0 0 0 -6 2 0 40 20
4 X1 1 0 0 0 0 0 1 0 2
6 X2 0 1 0 0 0 0 0 1 1
2 X3 0 0 1 0 0 1 1 -1 6
0 S1 0 0 0 1 0 0 -4 4 1
0 S2 0 0 0 0 1 0 1 -6 1

63
 Z 0 0 0 0 0 2 6 4 26

Finalmente se obtiene la solución entera factible:

 Z= 26

64
  X1= 2
 X2=1
 X3=6
 S1=1
 S2=1
 S3=0

Plano cortante mixto

Corte especial que sólo permite que un subconjunto de las variables asuma valores
enteros, permaneciendo las demás variables (incluyendo de holgura y de exceso)
continuas. En general, la cantidad de cortes es independiente del tamaño del problema,
aunque finita, en el sentido que un problema con una cantidad pequeña de variables y
restricciones puede necesitar más cortes que un problema mayor.

Sea x k una variable entera del problema mixto. Como en el caso entero puro, se
considera la ecuación x k en la solución continua óptima. Esta se da como:
n
x k =β k −∑ x kj × w j
j=1

Debido que en este caso algunas variables w j pueden no estar restringidas a valores
enteros; como es el caso del entero puro, donde x iy w j son enteros, se emplea un nuevo
corte basado en la misma idea general.

Para que x k sea entera, debe satisfacer x k ≤ [ β k ] o bien x k ≥ [ β k ] +1. Del reglón fuente, estas
condiciones son equivalentes a:
n

∑ x kj × w j ≥ f k … ecuación(1)
j=1

∑ x kj × w j ≤ f k −1… ecuación(2)
j=1

Sea:
j

J +¿=conjuntode subindices j paralos cualesα k ≥0 ¿

J −¿=conjunto de subindices j paralos cuales α <0 ¿

k

Entonces se obtiene, de (1) y (2), se obtiene

❑
∑ x kj × w j ≤ f k … ecuación(3)
j∈ J

fk ❑
× ∑ x kj ×w j ≤ f k … ecuación(3)
f k −1 j ∈J

65
Ya que (1) y (2), y por tanto, (3) y (4) no pueden ocurrir simultáneamente, se deduce,
que (3) y (4) pueden combinarse en una restricción de la forma:
❑
fk ❑
Sk − { j
∑ x k ×w j +
j ∉J
j
}
× ∑ x k ×w j =−f k
f k −1 j ∈J

Donde Sk ≥ 0 es una variable de holgura no negativo. La última ecuación es el corte

mixto requerido y representa una condición necesaria para que x k sea entera. Ya que
todas las w j son 0 en la tabla óptima actual, se deduce que el corte anterior es infactible.
Por consiguiente, se usa el método dual simplex para eliminar la infactibilidad.

El corte mixto se desarrolla sin tomar ventaja del hecho que algunas de las variables w j
pueden ser enteras. Si esto se toma en cuenta resultará el siguiente corte más fuerte:
n
Sk =−f k + ∑ λ j × w j
j=1

Donde

α kj Si α kj ≥ 0 y w j no es entera

fk j
λ j=¿ α Si α kj <0 y w j no es entera
f k −1 k

f kj Si f kj ≤ f k y w j es entera

fk
(1−f kj) Si f kj > f k y w j es entera
1−f k

Los cortes agregados no eliminan alguno de los puntos enteros factibles originales, pero
deben pasar por al menos un punto entero, factible o no factible. Requisito básico de
cualquier corte.

Algoritmo de los planos de corte mixtos

o Paso 1. Resolver la relajación lineal de (P). Si es infactible. PARAR (el
problema (P) es infactible). Si su solución óptima x́verifica que x j es entero ∀j ∈
J, PARAR (x́es solución óptima de (P)).
o Paso 2. Seleccionar el reglón fuente, calcular la ecuación del plano de corte
mixto (fortalecido) e introducirla en el problema (P). Ir al Paso 1.

 Criterios de selección de la fila fuente

Análogos a los del Algoritmo de planos de corte fraccionales.
66
Plano de corte mixto de Gomory:
fk
∑ yl , N j x N j + f × ∑ ¿
j∈ J k −1 j ∈J−¿ y , N x N ≥f ¿
l j j k

Plano de corte mixto fortalecido de Gomory:

n−m n −m
f Bl f Bl
∑ yl , N j x N j + × ∑ y , N x N j+ ∑ fl , N j x N j+ × ∑ (fl , N j−1) x N j ≥ f Bl
j ∈ J+¿ N j ∉J f Bl−1 j ∈J−¿ N ∉J l j
j j=1 f Bl−1 j=1
N j ∈J N j∈ J
f Bl ≥fl , N j f Bl< fl, N j

APLICACIÓN:

MAXIMIZAR Z=7 X 1 +9 X 2

−1 X 1 +3 X 2 ≤6

7 X 1 + X 2 ≤ 35

X 1 , X 2 ≥0

Para tener una mejor visión de la solución y de la nueva solución cuando una de las
variables sea entera, el problema se desarrollará primero por el método gráfico.
SOLUCIÓN GRÁFICA:

67
 *La solución gráfica se obtuvo usando la calculadora online PHP Simplex.

PUNTOS QUE DESCRIBEN EL ÁREA FACTIBLE:

Valor de la
Coordenada Y
Punto Coordenada X (X1) función objetivo
(X2)
(Z)
O 0 0 0
A 0 2 18
B 4.5 3.5 63
D 5 0 35

APLICANDO EL MÉTODO SIMPLEX

MAXIMIZAR Z=7 X 1 +3 X 2

−1 X 1 +3 X 2 +S 1=6

7 X 1 + X 2+ S 2=35

X1 , X 2 , S1, S2≥ 0

TABLA INICIAL:

cj 7 9 0 0
cb Xb X1 X2 S1 S2 bj θj
0 S1 -1 3 1 0 6 2
0 S2 7 1 0 1 35 35
Z -7 -9 0 0 0 0

TABLA FINAL ÓPTIMA:

cj 7 9 0 0
cb Xb X1 X2 S1 S2 bj
7 X1 1 0 -1/22 3/22 9/2
9 X2 0 1 7//22 1/22 7/2
Z 0 0 28/11 15/11 63

VALORES ÓPTIMOS:

68
 1
 X 1 =4
2
1
 X 2 =¿3
2
 S1=0
 S2=0
 Z=63

Se tiene valores no enteros tanto como para X1 y X2; se desea que X1 tenga un valor
entero, ante esto se aplicará el método de plano cortante mixto y se debe agregar un
corte mixto a la tabla, eligiendo como renglón fuente al que corresponde con la variable
que se desea hacer entera.
A partir de la tabla óptima se puede tomar el renglón fuente para X1 y luego obtener el
corte mixto:

1 3 1
X1−
22 22 2 ( )
S 1+ S2= 4+ …(1)

Se toma el corte mixto, teniendo en cuenta la ecuación siguiente:

n
Sk −1 ∑ λ j × w j =−f k
j=1

Donde

α kj Si α kj ≥ 0 y w j no es entera

fk j
λ j=¿ αk Si α kj <0 y w j no es entera
f k −1

f kj Si f kj ≤ f k y w j es entera

fk
(1−f kj) Si f kj > f k y w j es entera
1−f k

Entonces, teniendo en cuenta las condiciones anteriormente planteadas, se tiene el λ j

fk −1 3
para el coeficiente de S1 como α j , debido a que ≤ 0 y para S2, ≥ 0,
f k −1 k 22 22
entonces se toma el coeficiente α kj tal como se encuentra.

69
 n
Sk −1 ∑ λ j × w j =−f k
j=1

Reemplazando:

1
S3−
{( )
1
2
−1
( 2
−1
22 ) 3
S+ S
22 1 2
}
=
−1
2

Simplificando:
1 3
S3 − S− S
22 1 22 2
Ahora que ya se obtuvo el corte mixto, se añadirá a la tabla óptima para obtener un
nuevo valor óptimo y hacer que X1 cumpla con la condición de tener solución entera, si
en caso no se obtiene un valor entero, se tiene que obtener un nuevo renglón fuente y un
nuevo corte mixto para X1.

NUEVA TABLA
cj 7 9 0 0 0
cb Xb X1 X2 S1 S2 S3 bj
7 X1 1 0 -1/22 3/22 0 9/2
9 X2 0 1 7//22 1/22 0 7/2
0 S3 0 0 0 0 1 -1/2
Z 0 0 28/11 15/11 0 63

A partir de la nueva tabla se hallará la nueva solución, aplicando el método simplex

dual.
TABLA FINAL
cj 7 9 0 0 0
cb Xb X1 X2 S1 S2 S3 bj
7 X1 1 0 -1/11 0 1 4
9 X2 0 1 10/33 0 -1/3 10/3
0 S2 0 0 1/3 1 -22/3 11/3
Z 0 0 23/11 0 10 58

VALORES ÓPTIMOS
 X1 = 4
 X2 = 10/3
 S2 = 11/3

70
  Z = 58

Como se observa, en esta tabla se obtiene un valor entero de 4 para X 1 y un Z óptimo de

58, menor al obtenido en la solución del problema relajado.
Según la solución del problema relajado X 1 tenía un valor de 4.5, pero según las
condiciones del problema, X1 tenía que ser entero; esto explica la aparición de una
holgura de 11/3, debido a que en esta nueva solución se tendrán recursos sin utilizar,
pero al mismo tiempo estos recursos no son lo suficiente como para producir una unidad
más del producto.
Aplicando el método algortimo fraccional

Ejercicio:
En una empresa textil produce dos tipos de productos. Esta empresa dispone de 6
unidades de materia prima y 9 horas de tiempo productivo. Para la producción de
pantalones se requiere de 2 unidades de materia prima y 2 de horas de tiempo, mientras
que la producción faldas requiere 3 horas de tiempo y 1 unidades de materia prima.
Los precios de venta de pantalones y faldas 3$ y 4$. Determine el número de productos
de cada tipo que ha de producir la empresa para maximizar su beneficio.
Solución:
Variable de decisión:
X1= número de unidades de pantalones producidas.
X2= número de unidades de faldas producidas.
Restricciones:
 Máxima disponibilidad de materia prima
2(u.m.p/u.p)*X1(u.p) + 1(u.m.p/u.p)*X2(u.p) ≤ 6 (unidades m.p.)
 Máxima cantidad de hora para la producción de las prendas
2(horas/u.p)*X1(u.p) + 3(horas/u.p)*X2(u.p) ≤ 9 (horas)

FUNCIÓN OBJETIVOS:
Max Z=3($/u.p)*X1(u.p) + 4($/u.p)*X2(u.p)
Se realizará el método simplex:

71
APLICANDO EL MÉTODO ALGORITMO FRACCIONAL

1. Se Tiene los resultados :

X1= 2.25 X2=1.5 Z=12.75, se elige el menor

2. Se elige X2=1.5 , se toma la restricción de la tabla

X1 X2 S1 S2 SOLUCIÓN

0X1 + X2 – 0.5*S1 + 0.5*S2 =1.5

3. Se debe descomponer la restricción en ENTEROS y fracciones menores que

1(+)

0X1 + X2 – 0.5*S1 + 0.5*S2 =1.5

X2 + (-1+0.5)*S1 + 0.5*S2 = (1+0.5)

4. Se acomodan los enteros de lado izquierdo y fracciones de lado derecho

72
 X2 + (-1+0.5)*S1 + 0.5*S2 = 1.5
X2 – S1= -0.5*S1 -0.5*S2 + 0.5

5. Se agrega el ≤ a la restricción y se elimina los enteros

=-0.5*S1 – 0.5*S2 + 0.5 ≤ 0

6. Se pasan al lado derecho los valores sin variable y se agrega una variable de
holgura
-0.5*S1 -0.5*S2 + 0.5 ≤ 0
-0.5*S1 -0.5*S2 ≤ -0.5
-0.5*S1 -0.5*S2 + S3 ≤ -0.5

7. Método simplex

  X1 X2 S1 S2 S3 bi
Z -0.3 0 0 1.33 12 12
X1 1 0 0.75 -0.3 0 2.25
X2 0 1 -0.5 0.5 0 1.5
S3 0 0 -0.5 -0.5 1 -0.5
Z 0 0 0.25 1.25 0 12.75
X1 1 0 0 -1 1.5 1.5
X2 0 1 0 1 -1 2
S1 0 0 1 1 -2 1
Z 0 0 0 1 0.5 12.5

Para eliminar la nueva fracción se produce igual que los anteriores pasos

X1 +0*X2 + 0*S1 -1*S2 + 1.5*S3 =1.5

X1 + -1*S2 + (1+0.5)*S3 =(1+0.5)

X1 – 1*S2 + S3 +1 = -0.5*S3 + 0.5

=-0.5*S3 +0.5 ≤ 0

-0.5*S3 ≤ -0.5

-0.5*S3 +S4 ≤ -0.5

8. Insertando la nueva restricción a la tabla

Cj S
X1 X2 S1 S2 S3 bi
4
X1 1 0 0 -1 1.5 0 1.5
X2 0 1 0 1 -1 0 2
S1 0 0 1 1 -2 0 1

73

Todos los valores son

enteros
 S4 0 0 0 0 -0.5 1 -0.5
12.5
Z 0 0 0 1 0.5
0 0
X1 1 0 0 -1 0 3 0
X2 0 1 0 1 0 -2 4
S1 0 0 1 1 0 -4 3
S3 0 0 0 0 1 -2 1
Z 0 0 0 1 0 1 12

Solución:
X1=0 pantalones
X2=4 faldas
S1=3
S3=1
Z=$12

PROBLEMA TALLER:
Teniendo en cuenta el problema planteado en la explicación del método de plano
cortante mixto, resuelva el problema si se desea una solución entera para X2.
MAXIMIZAR Z=7 X 1 +9 X 2

−1 X 1 +3 X 2 ≤6

7 X 1 + X 2 ≤ 35

X 1 , X 2 ≥0

SOLUCIÓN
APLICANDO EL MÉTODO SIMPLEX

MAXIMIZAR Z=7 X 1 +3 X 2

−1 X 1 +3 X 2 +S 1=6

7 X 1 + X 2+ S 2=35

X1 , X 2 , S1, S2≥ 0

TABLA INICIAL:

74
 cj 7 9 0 0
cb Xb X1 X2 S1 S2 bj θj
0 S1 -1 3 1 0 6 2
0 S2 7 1 0 1 35 35
Z -7 -9 0 0 0 0

TABLA FINAL ÓPTIMA:

cj 7 9 0 0
cb Xb X1 X2 S1 S2 bj
7 X1 1 0 -1/22 3/22 9/2
9 X2 0 1 7//22 1/22 7/2
Z 0 0 28/11 15/11 63

VALORES ÓPTIMOS:
1
 X 1 =4
2
1
 X 2 =¿3
2
 S1=0
 S2=0
 Z=63

A partir de la tabla óptima se puede tomar el renglón fuente para X1 y luego obtener el corte
mixto:

7 1 1
X1+
22 22 2 ( )
S1 + S 2= 3+ …(1)

Se toma el corte mixto, teniendo en cuenta la ecuación siguiente:

n
Sk −1 ∑ λ j × w j =−f k
j=1

Donde

α kj Si α kj ≥ 0 y w j no es entera

fk
λ j=¿ α kj Si α kj <0 y w j no es entera
f k −1

f kj Si f kj ≤ f k y w j es entera

fk
(1−f kj) Si f kj > f k y w j es entera
1−f k

75
Entonces, teniendo en cuenta las condiciones anteriormente planteadas, se tiene el λ j para el
7 1
coeficiente de S1 y S2 ≥ 0 y para , ≥ 0, entonces se toma el coeficiente α kj tal como se
22 22
encuentra.
n
Sk −1 ∑ λ j × w j =−f k
j=1

Reemplazando:

S3− {227 S + 221 S }= −12

1 2

7 1 −1
S3 − S1 − S 2 =
22 22 2
Ahora que ya se obtuvo el corte mixto, se añadirá a la tabla óptima para obtener un nuevo valor
óptimo y hacer que X2 cumpla con la condición de tener solución entera, si en caso no se obtiene
un valor entero, se tiene que obtener un nuevo renglón fuente y un nuevo corte mixto para X 1.

NUEVA TABLA

cj 7 9 0 0 0
cb Xb X1 X2 S1 S2 S3 bj
7 X1 1 0 -1/2 3/22 0 9/2
9 X2 0 1 7/22 1/22 0 7/2
0 S3 0 0 -7/22 -1/22 1 -1/2
Z 0 0 28/11 15/11 0 63

Seleccionamos el bi negativo y luego la variables que entrará a la base, s1 entra a la base

A partir de la nueva tabla se hallará la nueva solución, aplicando el método simplex dual.
TABLA FINAL

cj 7 9 0 0 0
cb Xb X1 X2 S1 S2 S3 bj
7 X1 1 0 0 1/7 - 1/7 32/7
9 X2 0 1 0 0 1 3
0 S1 0 0 1 1/7 -22/7 11/7
Z 0 0 0 1 8 59

VALORES ÓPTIMOS
 X1 = 32/7
 X2 = 3
 S1 = 11/7
 Z = 59

76
77
BIBLIOGRAFÍA

LIBRO:

 Hamdy A. Taha, “INVESTIGACIÓN DE OPERACIONES”, 7ª.edición

 Wayne L. Winston, “INVESTIGACIÓN DE OPERACIONES – Aplicaciones y

algoritmo”, 2010, CENGAGE Learning Editors, México

78