República Bolivariana de Venezuela

Ministerio del Poder Popular para la Educación

Universidad Nacional Experimental Politécnica de la

Fuerza Armada Nacional

UNEFA

Zaraza- Guárico

Profesora: Bachiller:

Lic. Marujelys Brito Emmily Marín

Zaraza- junio-2021
 Índice

La Programación Entera___________________________________________________4

Formulación de Programación Lineal Entera _________________________________5

Modelos de Programación Lineal Entera_____________________________________5

Métodos de solución_______________________________________________________6

Formulación y Construcción de Modelos Lineales de Transporte. _______________10

Método Del Simplex Y Problema Del Transporte_____________________________14

Resolución del problema del transporte_____________________________________14

Análisis de sensibilidad. __________________________________________________15

Usos De Paquetes Computarizados_________________________________________16

Programación Dinámica__________________________________________________17

Usos de paquetes computarizados QSB – STORM____________________________17

Conclusion_____________________________________________________________18

Analisis________________________________________________________________19
 Introducción

La presente investigación se realizará con la finalidad de desarrollar el tema de la

programación entera en la investigación de operaciones, a su vez, hacer énfasis en el uso de
la misma para la formulación, resolución y métodos de solución de problemas en os que se
emplea esta herramienta.

Del mismo modo, dar a conocer, el modelo de transporte el método simplex como
herramienta para la solución de problemas de transporte, su análisis e sensibilidad, y lo
paquetes computarizados que se emplean para el uso de estos.
 La Programación Entera

La programación lineal también conocida como optimización lineal, es la

maximización o minimización de una función lineal sobre un poliedro convexo definido por
un conjunto de restricciones lineales no negativas. La teoría de la programación lineal cae
dentro de la teoría de la optimización convexa y es también considerada como parte
importante de la investigación de operaciones.

Es el método empleado para resolver problemas que tienen variables de decisión

enteras. Estos modelos se han considerado submodelos de la programación lineal con la
característica de enteridad.

Los creadores e investigadores de esta técnica fueron Wagner (1950) y Manne (1959),
quienes desarrollaron varios métodos de solución. Uno de los primeros enfoques de solución
al tipo de problemas que plantea la programación entera, fue el de evaluación de cada posible
solución, es decir, cada una de las combinaciones de valores enteros para las variables del
problema, conduciendo a una solución óptima exacta.

A este tipo de resoluciones se les dio el nombre de métodos exactos. Por otro lado, se
desarrollaron otro tipo de técnicas que recibieron el nombre de métodos heurísticos, los
cuales hacen referencia a la intuición y conducen a una solución próxima a la óptima en un
tiempo razonable. Si se requiere que todas las variables sean enteras se habla de
programación lineal entera pura; si se necesita que algunas de las variables de decisión sean
números enteros, se tiene un problema de programación lineal entera mixta.

Formulación de Programación Lineal Entera

Un problema de PLE puede describirse de la siguiente forma:

Optimizar una función objetivo z=c.x

Bajo las restricciones Ax = ó = b, x = 0

Donde:

x -Vector con variables enteras

c -Vector de coeficientes de la función objetivo

A -Matriz de coeficientes de las restricciones

b -Vector de términos independientes

Modelos de Programación Lineal Entera

Existen modelos diferentes manejados por WINQSB.

Problema De La Diligencia (Stagecoach Problem) Este problema se refiere a un

vendedor mítico que tuvo que viajar hacia el oeste por diligencia, a través de tierras indias
hostiles, aproximadamente hace 125 años. Aun cuando su punto de partida y destino eran
fijos, tenía un número considerable de opciones para elegir, qué estados recorrer en su ruta

Problema De La Mochila, comúnmente abreviado por KP (del inglés Knapsack

problem) es un problema de optimización combinatoria, es decir, que busca la mejor solución
entre un conjunto finito de posibles soluciones a un problema. Modela una situación análoga
al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de
un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados

Programación de la Producción, es un término asignado a dicha planificación en

todos los aspectos de las actividades de la fuerza de trabajo para la entrega del producto. Se
observa casi exclusivamente en entornos de fabricación, sin embargo, muchas de las técnicas
empleadas en la planificación de la producción pueden ser y son utilizadas por muchas
empresas orientadas a los servicios.

Se basa principalmente en el uso eficiente de los recursos. Si bien se refiere a veces

como la planificación de las operaciones, y verdaderamente emplea muchas de las mismas
técnicas, la característica distintiva principal es que la planificación de la producción se
centra en la producción real, mientras que la planificación de las operaciones observa la
operación en su conjunto.

Control de inventario: Mientras que una gran parte de la producción se planifica, el

control de inventario es visto con frecuencia en un subconjunto de menor importancia de la
gestión de la cadena de suministro, sin embargo, es una parte crucial del sistema de
producción. Aparte de la determinación del nivel mínimo de acciones que una empresa puede
mantener como la seguridad contra un globo en la demanda del cliente, el control de
inventario observa los costos asociados con el mantenimiento de inventario. Puede
comprender el inventario de un producto acabado o de los materiales utilizados en la
fabricación de dichos productos. El control de inventario se ve afectado por los cambios en
la demanda de los clientes, costos de inversión, gastos de pedido y costos de pedido de nuevo.

Métodos de solución

Pudiera pensarse que los métodos de obtención de soluciones a problemas de

programación lineal entera pudieran ser menos difíciles que los de programación lineal
generales, pero resulta lo contrario. Los algoritmos que permiten resolver los problemas
restringidos a enteros son más complejos y requieren mucho más tiempo computacional.

Para la resolución de los problemas de programación lineal entera existen diferentes

métodos. Los métodos exactos son los que encuentran, si existe, el óptimo absoluto. Muchos
de estos métodos parten de la resolución del modelo dejando a un lado las restricciones
enteras y buscando el mejor valor para las variables reales. A partir del supuesto de que la
solución entera no debe estar muy lejos, se aplican diferentes técnicas que permiten llegar al
óptimo entero.

Una breve introducción a los métodos de la programación lineal: Simplex y Punto

interior, permitirá tener una idea de cómo operan los mismos.

El método del simplex se utiliza para hallar las soluciones óptimas de un problema de
programación lineal con tres o más variables. Este se basa en el hecho de que la solución
óptima se encuentra siempre en uno de los vértices del poliedro formado por el conjunto de
restricciones. Su forma de buscar la solución es recorrer sobre estos vértices hasta encontrar
el óptimo. Aun cuando no corre en tiempo polinomial en el caso peor, su mayor valor radica
en su capacidad de revolver nuevos problemas y resulta muy útil cuando no se tiene
un algoritmo eficiente de solución.

Los métodos de punto interior se denominan así precisamente porque los puntos
generados por estos algoritmos se hallan en el interior de la región factible. Esta es una clara
diferencia respecto al método del simplex. En la actualidad los métodos de punto interior más
eficientes tienen una complejidad de orden T(nL), donde n es el número de variables y L una
medida del tamaño del problema (el número de bits necesarios para representar los datos).

En la modelación lineal no entera se demuestra que el óptimo es un vértice de la

región factible. En los modelos enteros, esto no tiene por qué ser así, de manera general los
vértices no tienen que ser números enteros. Por ello la solución óptima se encontrará en el
interior de la región factible, por lo que los métodos exactos, como el simplex o punto
interior, empleado de forma directa no aportarán la solución óptima en la generalidad de los
casos.

Como el conjunto de soluciones enteras factibles es un número finito pudiera pensarse

en recorrerlas todas en busca de la solución, pero esto puede resultar ineficiente pues según
el número de variables el conjunto de soluciones se incrementa exponencialmente. Para
enfrentar esto se han desarrollado un conjunto de técnicas basadas en la lógica de que la
solución entera no debe encontrarse muy lejos de la óptima del modelo con variables reales,
conocidas como Ramificar y Podar (Branch and Bound).

Este método se basa en que existe un número finito de soluciones posibles, no todas
factibles, para un problema con enteros, que pueden representarse mediante un diagrama de
árbol. Pero no es necesario enumerar todas las soluciones posibles si se pueden eliminar
algunas ramas. Para eliminar una rama basta demostrar que no contiene una solución factible
que sea mejor que una ya obtenida.
 Existen otros métodos de resolución de la PLE, como el procedimiento de los cortes
de Gomory. En esta técnica, se resuelve el problema original relajado en el que se incluyen
restricciones adicionales, que reducen la región factible sin excluir soluciones que cumplen
las condiciones de optimalidad. En cada iteración se añade una restricción que se denomina
corte de Gomory.

En los modelos de PLE es importante valorar el número de variables a manejar pues

si el modelo tiene algunos cientos de variables y no tiene una estructura especial, puede
resultar demasiado costoso de resolver. Los modelos enteros son no polinomiales, o sea
el tiempo de resolución es exponencial con respecto al número de restricciones y
especialmente con respecto al número de variables de decisión enteras, como expone Castillo
et al[3]En los casos en que los métodos generales de PLE, por las dimensiones del problema,
resultan ineficientes, resulta válido introducir métodos heurísticos que obtienen soluciones
aproximadas satisfactorias.

El problema del transporte consiste en satisfacer de forma óptima (costos mínimos de

transportación) n destinos desde m orígenes, donde están definidos los costos de
transportación de cada origen a cada destino, la demanda de los destinos y la oferta de cada
origen. Los métodos para hallar la solución se basan en una metaheurística que consiste en
buscar una solución factible inicial, e ir mejorándola hasta llegar a la solución óptima.

Existe gran diversidad de técnicas para obtener la solución inicial y de formas para
las mejoras iterativas.

Estos problemas son casos particulares de PLE en los que métodos especiales de
solución resultan más eficientes que los métodos tradicionales.

La PLE es una rama de la investigación de operaciones que está presente en muchos

problemas reales, entre ellos resultan muy interesantes los de organización de tiempos
de trabajo que existen en diferentes ramas de la producción y los servicios. La selección de
los métodos de solución más eficientes depende en gran medida de las particularidades del
escenario que se ha modelado.
 Programación Lineal de Transporte es una técnica cuantitativa creada para minimizar
los costos asociados a la distribución de un bien o servicio desde diferentes orígenes hasta
diferentes destinos. Las condiciones de linealidad están presentes, como en cualquier técnica
de programación lineal.

Debido al éxito alcanzado en los Sistemas de Transporte, esta técnica se utilizó

posteriormente en otros sistemas. En ellos, el problema no implica transporte físico
de bienes pero existen relaciones lineales, y el modelo formulado tiene las características de
un Modelo de Transporte.

El modelo usado en esta técnica es un modelo lineal, con características especiales,

llamado Modelo Lineal de transporte.

Las características que hacen del Modelo Lineal de Transporte un modelo de

programación lineal especial son: a) Los coeficientes de las variables, en las restricciones,
son uno o cero.

Las cantidades demandadas deben ser iguales a las cantidades ofrecidas

para poder solucionar el modelo.

El producto a transportar debe ser único y homogéneo. Si se ofrece cemento, por

ejemplo, la demanda debe ser de cemento, es decir, un producto único. Si se ofrecen sacos
de cemento la demanda debe ser de sacos de cemento y no a granel, es decir, es homogéneo.
En caso de multiproductos, se puede hacer una multi-formulación.

En la Formulación y Construcción del Modelo Lineal de Transporte deben

considerarse aspectos ya estudiados en la formulación de modelos lineales generales tales
como a) Definir claramente las variables de decisión y expresarlas simbólicamente b) Definir
claramente la Función Objetivo y las restricciones y expresarlas matemáticamente
como funciones lineales.

Debe cuidarse que los elementos componentes del modelo sean expresados para el
mismo período de tiempo. Se debe estipular que las variables de decisión sean mayores o
iguales a cero. Esto acerca el modelo a la realidad.
 La Función Objetivo del Modelo Lineal de Transporte es la
formulación matemática de una meta establecida. Es una función Lineal a ser maximizada o
minimizada. En el modelo original de transporte representa los costos totales de transporte a
ser minimizados. Los orígenes o sitios, desde donde se transporta el bien, están simbolizados
en el subíndice i y los destinos, hasta los que se transporta el bien, con el subíndice j. Tiene
la siguiente forma general: m n Minimizar å å Cij Xij i=1 j=1 9. Xij, matemáticamente,
simboliza a las variables de decisión. Son los valores numéricos que se determinan con la
solución del modelo y están relacionadas con la actividad de transporte. En el Modelo de
Transporte representan la cantidad del bien a transportar desde el origen i hasta el destino j.
Los orígenes i pueden existir en cualquier cantidad, desde 1 hasta m orígenes; igualmente
puede existir cualquier cantidad de destinos j, desde 1 hasta n.

Toda la información de un Modelo de Transporte puede ser resumida en las llamadas

Tablas de Transporte, al igual que el modelo lineal general se resumía en tablas simplex.
Estas tablas presentan la forma siguiente, en un modelo de tres orígenes y tres destinos.

Formulación y Construcción de Modelos Lineales de Transporte.

NOTA: Debe recordarse que las cifras, las unidades monetarias y cualquier otro dato
utilizado en los ejemplos, son convencionales. Pueden o no coincidir con datos reales.
 Ejemplo 1. Problema en un Sistema de Transporte.

La empresa Gal elabora cerveza, como uno de sus productos, en

tres plantas localizadas en tres ciudades del país, A, B y C. Este producto se transporta a
cuatro almacenes localizados en cuatro ciudades del país, 1, 2, 3 y 4 para su posterior
distribución. Los costos de transporte (en miles de bolívares) por camión de cerveza, se
indican en la matriz de costos que se le presenta. Cada camión puede transportar 1000 cajas
de cerveza. La cantidad de cajas de cerveza, disponible en las plantas, para transportar es la
siguiente: A: 90.000; B: 40.000; C: 80.000. Las cajas de cerveza que requiere
cada almacén son las siguientes: 1: 40.000; 2: 60.000; 3: 50.000; 4: 60.000.

Variables de Decisión: Xij: camiones de cerveza a transportar desde la Planta de la

ciudad i hasta el almacén de la ciudad j i = A,B,C j = 1,2,3,4 Las variables son 12 en total:
(mxn) (3x4). Pueden ser definidas una por una, pero es suficiente hacerlo con una cualquiera
de ellas para expresar lo que representan. Por ejemplo:

XA3: camiones de cerveza a transportar desde la planta en la Ciudad A hasta el

almacén de la Ciudad 3.

Nota: Para ayudarse en la definición conceptual de las variables imagine que el valor
de ella ya lo ha encontrado y es un número cualquiera. Por ejemplo 8. Coloque ese 8 antes
de la definición dada a la variable y compruebe que puede leerlo con coherencia. Así, en este
caso, Usted puede leer: 8 camiones de cerveza a transportar desde la planta de la ciudad A
hasta el almacén de la ciudad 3.

Restricciones de Oferta: Disponibilidades limitadas de cajas de cerveza en las

plantas de las 3 ciudades:
 XA1 + XA2 + XA3 + XA4 £ 90 XB1 + XB2 + XB3 + XB4 £ 40 XC1 + XC2 + XC3
+ XC4 £ 80 La cantidad del lado derecho de la restricción es el resultado de transformar la
cantidad de cajas de cerveza disponibles, en camiones. Esto es así porque la variable Xij se
ha definido en "camiones" y no se puede sumar camiones y obtener un total de cajas de
cerveza. Se debe ser coherente y lo que se suma debe ser lo que se obtiene, recuerde la
Aditividad de los modelos lineales.

Definición conceptual de una específica restricción de Oferta. La tercera, por

ejemplo:

Representa la suma de camiones de cerveza transportados desde la planta de la ciudad

C hasta el almacén de la ciudad 1 (XC1), más los transportados desde esa misma planta hasta
el almacén 2 (XC2), más los transportados hasta el almacén 3 (XC3), más los transportados
hasta el almacén 4 (XC4). Esta suma debe ser menor o igual a la cantidad de camiones
disponibles en la planta de la ciudad C. En este caso 80, ya que dispone de 80.000 cajas de
cerveza equivalente a 80 camiones.

Restricciones de Demanda: Requerimientos de cajas de cerveza en los almacenes de

las 4 ciudades:

XA1 + XB1 + XC1 ³ 40 XA2 + XB2 + XC2 ³ 60 XA3 + XB3 + XC3 ³ 50 XA4 + XB4
+ XC4 ³ 60 De nuevo la cantidad del lado derecho es el resultado de transformar la cantidad
de cajas de cerveza disponibles, en camiones. Cada ecuación del modelo debe ser coherente.
Lo que se suma son camiones y eso es lo que debe obtenerse. Definición conceptual de una
específica restricción de demanda: La primera, por ejemplo: Representa la suma de camiones
de cerveza transportados hasta el almacén de la ciudad 1 desde las plantas de la ciudad
A(XA1) más los transportados desde la planta de la ciudad B (XB1), más los transportados
desde la planta de la ciudad C (XC1), para satisfacer la demanda de ese almacén de la ciudad
1. Esta suma debe ser mayor o igual a la cantidad de camiones demandados en el almacén de
la ciudad 1. En este caso 40, ya que demanda 40.000 cajas de cerveza equivalente a 40
camiones.
 Restricciones de no-negatividad de las variables: Las variables están restringidas
a ser no-negativas. No se pueden transportar cantidades negativas, no existentes, de cerveza.
Por eso, esta restricción acerca el modelo a la realidad.

Función Objetivo: Se define como Minimizar los costos totales de transporte de los
camiones de cerveza desde las 3 plantas hasta los cuatro almacenes.

Min 10 XA1 + 20 XA2 + 5 XA3 + 9 XA4 + 2 XB1 + 10 XB2 + 8 XB3 + 30 XB4 +

1XC1 + 20 XC2 + 7 XC3 + 10 XC4 Esta expresión matemática representa la suma de los
costos totales de transporte desde todas las plantas hasta todos los almacenes. Así por
ejemplo, 20 XC2 representa los costos totales de los camiones de cerveza transportados desde
la planta de la ciudad C hasta el almacén de la ciudad 2. Donde 20 es el costo unitario de
transporte; es decir, el costo de transporte de un camión de cerveza desde la planta de la
ciudad C hasta el almacén de la ciudad 2; XC2 es la cantidad transportada.

Resumiendo, el modelo y colocando las variables en la posición de las variables

similares, se puede observar más claramente la característica esencial que hace especial al
Modelo Lineal de Transporte: "Los coeficientes de las variables en las restricciones son 1 o
cero".

Analizando la variable XA3 se observa que tiene coeficiente 1 en la primera

restricción, cero en la segunda; es decir, no existe en esa restricción. Tiene coeficiente cero
en la tercera, cero en la cuarta, cero en la quinta, uno en la sexta y cero en la séptima. Igual
característica se observa en las demás variables. El resumen del modelo formulado y
construido es el siguiente:

Min 10 XA1 + 20 XA2 + 5 XA3 + 9 XA4 + 2 XB1 + 10 XB2 + 8 XB3 + 30 XB4 +

1XC1+ 20XC2 + 7 XC3 + 10 XC4 Sujeto a:

XA1 + XA2 + XA3 + XA4 £ 90 XB1 + XB2 + XB3 + XB4 £ 40 XC1 + XC2 + XC3
+ XC4 £ 80 XA1 + XB1 + XC1 ³ 40 XA2 + XB2 + XC 2 ³ 60 XA3 + XB3 + XC3 ³ 50 XA4
+ XB4 + XC4 ³ 60 Todas las variables no-negativas
 Método Del Simplex Y Problema Del Transporte

La programación lineal se ha constituido en un método ampliamente utilizado para

resolver problemas de optimización y planificación empresarial. En este contexto, se han
definido varios procedimientos operativos avanzados, entre los que cabe citar el método del
simplex y la solución de los llamados problemas del transporte.

El problema del transporte es un planteamiento clásico de las técnicas de

programación lineal. En este problema se pretende elegir el camino óptimo de envío de una
mercancía desde varios orígenes (por ejemplo, plantas de producción) a
diferentes destinos (centros de almacenamiento o consumo), de forma que el coste sea
mínimo. Como en todo problema de programación lineal, han de cumplirse las siguientes
etapas:

 Definir las variables del problema (por ejemplo, las cantidades de partida
solicitadas en cada destino, el coste de envío de una unidad de mercancía a cada destino).
 Escribir conceptualmente el sistema de inecuaciones asociado a las
restricciones del problema (por ejemplo, el número de unidades máximas producidas en
cada origen y las requeridas en cada destino).
 Definir conceptualmente la función objetivo, que determina el coste.

Resolución del problema del transporte

Una vez planteado el problema, se construye una tabla de distribución, de la que se

obtienen las expresiones matemáticas de las inecuaciones del sistema y la función objetivo.
Para resolverla se usan los métodos gráficos o algebraicos comunes de la programación
lineal.
 Análisis de sensibilidad.

Es una herramienta útil cuando no tenemos una certeza absoluta sobre los valores que
se han dado a los términos independientes de las restricciones o los coeficientes de la función
objetivo, en este sentido el análisis de sensibilidad consiste en estudiar cómo evoluciona el
óptimo y el valor de la función objetivo del optimo ante variaciones de dichos términos
independientes y coeficientes.

Estudia los intervalos para los cuales la modificación de un valor en el programa lineal
de forma individualizada, no cambia las variables que componen la base de nuestra solución,
hallando para el rango de valores definido en el intervalo, la evolución de la función objetivo
expresado a través de los precios sombra.

Objetivo del Análisis de Sensibilidad.

Establecer un intervalo de números reales en el cual el dato que se analiza puede estar
contenido, de tal manera que la solución sigue siendo óptimo siempre que el dato pertenezca
a dicho intervalo.
 Importancia del Análisis de Sensibilidad.

El análisis de sensibilidad es una de las partes más importantes en la programación

lineal, sobre todo para la toma de decisiones; pues permite determinar cuándo una solución
sigue siendo óptima, dados algunos cambios ya sea en el entorno del problema, en la empresa
o en los datos del problema mismo.

Este análisis consiste en determinar qué tan sensible es la respuesta óptima del
Método Simplex, al cambio de algunos datos como las ganancias o costos unitarios
coeficientes de la función objetivo, o la disponibilidad de los recursos términos
independientes de las restricciones

Usos De Paquetes Computarizados.

El problema del transporte como un modelo especial dentro de la programación

lineal, presenta una metodología de resolución que resulta ser mucho más sencilla que los
problemas de programación tradicionales. La herramienta de resolución de problemas
atinentes a la investigación de operaciones por excelencia WinQSB también distingue el
problema de transporte como un caso especial y desarrolla un módulo dedicado de manera
exclusiva al trabajo con este tipo de modelos en el llamado Network Modeling módulo que
estudiaremos a continuación.

Network Modeling (NET): Este programa resuelve los problemas de red, incluyendo
flujo de red capacitados (transbordo), transporte, asignación, la ruta más corta, flujo máximo,
árbol de expansión mínima, y problemas del vendedor viajero. Una red incluye nodos y
conexiones (arcos / enlaces) Cada nodo tiene una capacidad para el flujo de red y los
problemas de transporte. Si hay una conexión entre dos nodos, puede haber un costo, un
beneficio, una distancia o la capacidad de flujo asociado a la conexión. Con base en el tipo
de problema específico, NET resuelve la conexión o el envío satisfaciendo las restricciones
con el ánimo de optimizar la función objetivo especificada.
 Programación Dinámica

La programación dinámica es una técnica muy útil para la toma de decisiones de

problemas complejos que pueden ser discretizados y secuencializados, proporciona un
procedimiento sistemático para determinar la combinación óptima de decisiones; este método
no tiene una formulación estándar ya que las ecuaciones que se planteen responden al
problema específico.

Esta técnica es muy útil para la reducción el tiempo de ejecución de un algoritmo

mediante la utilización de subproblemas y subestructuras óptimas, todo ello haciendo uso del
principio de optimalidad

Usos de Paquetes Computarizados QSB –STORM

El QSB Es un programa de aseguramiento de la calidad que fue desarrollado por

General Motors (GM) para ser aplicado a sus proveedores, con el objeto de mejorar sus
Sistemas de Gestión de la Calidad, por medio de la utilización de herramientas básicas de la
calidad, orientadas a robustecer los procesos de mejora continua.

Se emplea para desarrollar la formulación de problemas de programación lineal de

una marera más compleja y que a su vez, permita encontrar la solución óptima de una marea
más eficaz.
 Conclusión

Un modelo de programación entera es un modelo que contiene restricciones y una

función objetivo idénticas a las formuladas por planeación lineal. La única diferencia es que
una o más de las variables de decisión tienen que tomar un valor entero en la solución final.

El problema del transporte o distribución es un problema de redes especial en

programación lineal que se funda en la necesidad de llevar unidades de un punto específico
llamado Fuente u Origen hacia otro punto específico llamado Destino. Los principales
objetivos de un modelo de transporte son la satisfacción

La programación dinámica es una técnica matemática que se utiliza para la solución

de problemas matemáticos seleccionados, en los cuales se toma una serie de decisiones en
forma secuencial.
 ANALISIS FINAL

Los problemas de programación entera surgen con frecuencia cuando los valores de
algunas o todas las variables de decisión deben restringirse a valores enteros. Existen también
muchas aplicaciones que necesitan decisiones de sí o no - incluyendo las relaciones
combinatorias que se puedan expresar en términos de tales decisiones - que se pueden
representar por variables binarias (0-1).

Estos problemas son más difíciles de lo que serían sin la restricción de valores
enteros, de manera que los algoritmos disponibles para programación entera, en general, son
mucho menos eficientes que el método simplex.

Los factores que determinan el tiempo de cálculo son el número de variables enteras
y la estructura del problema. Para un número fijo de variables enteras, casi siempre es más
fácil resolver problemas de PEB que problemas con variables enteras generales, pero agregar
variables continuas (PEM) puede no significar un incremento en el tiempo de cálculo.

Para problemas especiales de PEB que contienen alguna estructura especial que se
puede aprovechar mediante un algoritmo especial, es posible resolver problemas muy
grandes (muy por encima de mil variables binarias) en forma rutinaria. Puede ser que otros
problemas mucho más pequeños sin estructura especial no se puedan resolver.

En la actualidad es común que se disponga de paquetes de computadora para

algoritmos de programación entera en el software de programación matemática. Estos
algoritmos casi siempre se basan en la técnica de ramificación y acotamiento o en alguna
variación de ésta, como es el caso de los paquetes computarizados QSB – STORM