administracion de empresas

CONTENIDO

1.- INTRODUCCIÓN A LA PROGRAMACIÓN ENTERA 2
2. PLANTEAMIENTO DE PROBLEMA DE PROGRAMACIÓN ENTERA 4
3-.METODO DE RAMIFICACION Y ACOTAMIENTO PARA RESOLVER PROBLEMAS DE PROGRAMACION PURA CON ENTEROS 14
4.- METODO DE RAMIFICACIÓN Y ACOTAMIENTO PARA RESOLVER PROBLEMAS DE PROGRAMACIÓN MEZCLADOS CON ENTEROS (PROGRAMACIÓN MIXTA) 16
5.- RESOLUCIÓN DE PROBLEMAS DE LA MOCHILA POR EL METODODE RAMIFICACIÓN Y ACOTAMIENTO 17
6.- SOLUCIÓN DE PROBLEMAS DE OPTIMIZACIÓN COMBINATORIA MEDIANTE EL MÉTODO DE RAMIFICACIÓN Y ACOTAMIENTO 19
7.- ENUMERACIÓN IMPLÍCITA 22
8.- EL ALGORITMO DEL PLANO DE CORTE 24
9.- BIBLIOGRAFÍA 25










PROGRAMACIÓN ENTERA
1.- INTRODUCCIÓN A LA PROGRAMACIÓN ENTERA
Para la programación entera se requiere que todas las variables tienen que serentero se denomina un problema puro de programación con enteros.
Ejemplo: Max z =3x1 +2x2
s. a. x1 + x2 ≤ 6
x1 , x2 ≥ 0, x1, x2 enteros
Una programación entera en la cual se requiere que sólo una de las variables sean números enteros, se llama problema combinado de programación con enteros.
Ejemplo:
Max z = 3x1 + 2x2
s.a. x1 + x2 ≤ 6
x1, x2 ≥ 0, x1 enteros
En este tipo de problemasen el cual todas las variables tienen que ser iguales a 0 ó a 1 recibe el nombre de PE 0-1 Ó PE binaria.
Ejemplo:
Max z = x1 – x2
s.a. x1 + x2 ≤ 2
2x1 – x2 ≤1
X1, x2 = 0 ó bien 1

El concepto de relajación del PL de un problema de programación entera es un punto clave en la solución de la PE.
El PL obtenido cuando se omiten todos los enteros o las restricciones 0-1 enlas variables se llama relajación del PL de la PE.
Ejemplos:
La relajación del PL de (1)
Max z = 3x1+ 2x2
s.a x1 + x2 ≤ 6
x1, x2 ≥ 0
La relajación del PL de (2)
Max z = x1 – x2
s.a. x1 + x2 ≤ 2
2x1 – x2 ≤ 1
X1, x2 ≥ 0
Cualquier PE se podría considerar como la relajación del PL más restricciones adicionales. La relajación del PL es una versión de la PE conmenos restricciones, o bien, más relajada, significa que la región factible para cualquier PE debe estar contenida en la región factible para la relajación del PL correspondiente. Para cualquier PE que es un problema de maximización, vemos que:
Valor óptimo de z para la relajación del PL > valor óptimo de z para PE.
Con el fin de ver las propiedades de los problemas de programación entera, debemosconsiderar la PE simple como:
Max z = 21x1 + 11x2
s.a 7x1 + 4x2 ≤ 13
x1, x2 ≥ 0; x1; x2 enteros
REGIÓN FACTIBLE PARA EL PE SIMPLE
Considerando aún cuando la región factible para la relajación del PL de PE, el PE es por lo regular mucho más difícil de resolver que la relajación del PL del PE.
2. PLANTEAMIENTO DE PROBLEMA DE PROGRAMACIÓN ENTERA

En esta sección se muestra la manera deplantear soluciones prácticas como PE. Cuando el estudiante termine esta sección habrá logrado un buen nivel en arte de elaborar planteamientos con la programación entera. Se empieza con algunos problemas simples, pero de modo gradual se llega a planteamientos más complicados. El primer ejemplo es un problema de presupuesto de capital que trae a la mente el problema de StarOil de la sección 3.6Ejemplo 1 PE de un presupuesto de capital
Stockco proyecta cuatro inversiones. La inversión 1 genera un valor neto actual (VNA) de 16000 $us : la inversión 2, un VNA de 22000 $us; la inversión 3, un VNA de 12000 $us, y la inversión 4, una VNA de 8000 $us. Para cada inversión se requiere una cierta salida de efectivo en el tiempo presente: la inversión 1, 5000 $us; la inversión 2, 7000 $us; lainversión 3, 4000 $us; la inversión 4, 3000 $us. Dispone en la actualidad de 14000 $us para invertir. Plantee un PE cuya solución le indique a Stockco el modo de maximizar el VNA obtenido de las inversiones 1 a 4 .
Solución: al igual que en los planteamientos de los PE, se empieza por definir una variable por cada decisión que Stockco debe tomar. Esto lleva a definir una variable 0-1:
x_(j )...