REPÚBLICA BOLIVARIANA DE VENEZUELA

MINISTERIO DEL PODER POPULAR PARA LA DEFENSA

UNIVERSIDAD NACIONAL EXPERIMENTAL POLITÉCNICA
DE LA FUERZA ARMADA NACIONAL BOLIVARIANA
UNEFA- NÚCLEO ARAGUA - EXTENSIÓN CAGUA
CARRERA: CONTADURIA PUBLICA NOCTURNO

UNIDAD IV: EXTENSIONES DE LA PROGRAMACIÓN LINEAL

Profesor (a):
Lcda. Sofía Olivares
Estudiante:
Julia J. Narea
C.I.: 23.792.603

Cagua, diciembre 2024

 INTRODUCCIÓN
La programación lineal es una técnica matemática fundamental utilizada para la
optimización de recursos en diversas áreas como la economía, la ingeniería, la
logística y la investigación operativa. Sin embargo, en muchas situaciones prácticas,
las limitaciones y requerimientos específicos de los problemas no pueden ser
abordados adecuadamente mediante la programación lineal clásica. En este contexto,
surgen las extensiones de la programación lineal, que permiten manejar problemas
más complejos y variados. Este informe se centra en tres de estas extensiones: la
programación entera, el modelo de transporte y la programación dinámica. Cada uno
de estos métodos ofrece herramientas únicas para resolver problemas específicos,
ampliando así el alcance y la aplicabilidad de la programación lineal. La
programación entera se presenta como una extensión crucial que se utiliza cuando las
variables de decisión deben tomar valores enteros. A lo largo del informe, se
explorarán los métodos de solución más comunes, como el algoritmo de Branch and
Bound y las técnicas de corte, así como ejemplos prácticos que ilustran su aplicación
en el mundo real. El modelo de transporte es otro enfoque importante que se utiliza
para optimizar la distribución de bienes desde varios orígenes a múltiples destinos. Se
analizarán los métodos para resolver este modelo, incluyendo el Método de la
Esquina Noroeste y el Método MODI, proporcionando una comprensión clara de
cómo se pueden aplicar estos enfoques en situaciones logísticas reales. El modelo de
transporte es particularmente útil en la gestión de cadenas de suministro y la
planificación logística, donde la eficiencia en el transporte puede tener un impacto
significativo en los costos operativos o gastos. Se finalizará con la programación
dinámica, un método poderoso que permite resolver problemas complejos
dividiéndolos en subproblemas más simples. Se presentarán ejemplos clásicos, como
el problema de la mochila y los algoritmos para encontrar rutas más cortas,
destacando cómo esta metodología puede ofrecer soluciones eficientes a problemas
que parecen intratables mediante enfoques tradicionales.
En resumen, la Unidad IV sobre Extensiones de la Programación Lineal ofrece
una visión integral sobre cómo se pueden aplicar técnicas avanzadas para abordar
problemas complejos en optimización. A través del estudio de la programación
entera, el modelo de transporte y la programación dinámica, este informe busca
proporcionar un entendimiento profundo de cada uno de estos métodos y su
relevancia en contextos prácticos. La exploración detallada de estos temas no solo
enriquecerá el conocimiento teórico, sino que también equipará a los lectores con
herramientas prácticas para enfrentar desafíos reales en sus respectivas disciplinas.
 EXTENSIONES DE LA PROGRAMACIÓN LINEAL
Un problema de programación lineal es un problema de optimización en el cual tanto
la función (función objetivo) como las restricciones son lineales. La programación
lineal constituye un importante campo de la optimización por varias razones, muchos
problemas prácticos de la investigación de operaciones pueden plantearse como
problemas de programación lineal. Algunos casos especiales de programación lineal,
tales como los problemas de flujo de redes y problemas de flujo de mercancías se
consideraron en el desarrollo de las matemáticas lo suficientemente importantes como
para generar por sí mismos mucha investigación sobre algoritmos especializados en
su solución. Una serie de algoritmos diseñados para resolver otros tipos de problemas
de optimización constituyen casos particulares de la más amplia técnica de la
programación lineal. Históricamente, las ideas de programación lineal han inspirado
muchos de los conceptos centrales de la teoría de optimización tales como la
dualidad, la descomposición y la importancia de la convexidad y sus
generalizaciones. Del mismo modo, la programación lineal es muy usada en la
microeconomía, la ingeniería y la administración de empresas, ya sea para aumentar
al máximo los ingresos o reducir al mínimo los costos de un sistema de producción.
El aprendizaje de la metodología programación lineal es importante en la formación
del ingeniero industrial y el administrador porque le da herramientas para mejorar la
toma de decisiones en las empresas, lo que llevará a mejorar los procesos de las
mismas. Algunos ejemplos son la mezcla de alimentos, la gestión de inventarios, la
cartera y la gestión de las finanzas, la asignación de recursos humanos y recursos de
máquinas, la planificación de campañas de publicidad, etc.

PROGRAMACIÓN ENTERA
Cuando algunas variables están limitadas a valores enteros y otras no, hablamos de
problemas de programación entera mixta. La programación entera es una extensión
de la programación lineal donde algunas o todas las variables de decisión están
restringidas a ser números enteros. Esto es particularmente útil en problemas donde
las decisiones son discretas, como la asignación de recursos, la planificación de
producción o la gestión de inventarios.
Tipos de Programación Entera
Programación Entera Mixta (MIP): La Programación Entera Mixta (PEM) es
un método de optimización matemática que busca solucionar problemas
específicos de programación lineal en los cuales algunas de las variables de
decisión están restringidas a ser valores enteros, mientras que otras pueden ser
 no enteras o continuas. Este enfoque combina elementos tanto de la
programación entera como de la programación lineal, permitiendo abordar
una gama más amplia de problemas prácticos.
Programación Entera Total: En un modelo de números enteros totales, todas
las variables de decisión tienen valores de solución enteros . Existen tres tipos
básicos de modelos de programación lineal entera: un modelo de números
enteros totales, un modelo de números enteros 0-1 y un modelo de números
enteros mixtos. En un modelo de números enteros totales, se requiere que
todas las variables de decisión tengan valores de solución enteros.
Aplicaciones
Problemas de asignación.
Rutas de transporte.
Problemas de planificación y horarios.
Métodos de Solución:
Método del Branch and Bound. El método Branch and Bound o Rami cación
y Acotación, consiste en subdividir sucesivamente la región factible del
problema de partida y resolver las versiones relajadas de los problemas
resultantes, hasta encontrar la solución óptima del problema. La subdivisión
se realiza de forma que sigue una estructura de árbol binario. Un árbol binario
es un árbol no dirigido tal que el grado de cada vértice es menor o igual a 3.
Intuitivamente, es una estructura de datos formada por un nodo inicial, y en la
cual cada nodo puede tener hasta "dos hijos", que pasarán a ser dos nodos
más.
Algoritmos de corte. El problema de corte consiste en obtener una asignación
entre los perfiles disponibles demandados para un horizonte de planificación,
persiguiendo objetivos como la minimización de restos.
Heurísticas. Problemas con variables enteras únicamente se encuentran para
tamaños muy pequeños y alejados de lo que es habitual en las decisiones
reales de planificación industrial, así que los métodos basados en
procedimientos de aproximación heurística son en muchos casos las técnicas
empleadas para su resolución. Un método heurístico frente a uno exacto
suministra una solución al problema que se considera buena aunque no
necesariamente sea la óptima. A diferencia de los métodos exactos que
proporcionan una solución óptima del problema. Una forma de agrupar las
técnicas heurísticas podría realizarse utilizando las siguientes categorías:
- Métodos de descomposición: el problema se va descomponiendo en
problemas más sencillos.
- Métodos Inductivos: A partir de los casos más simples del problema, se
identifican buenas técnicas y por inducción se generalizan al problema
completo.
- Métodos de Reducción: Añaden nuevas restricciones al problema de
forma que limitan el espacio de soluciones. Estas restricciones se
formulan a partir de las propiedades comunes identificadas sobre conjunto
de buenas soluciones al problema.
- Métodos Constructivos: consisten en ir añadiendo elementos en cada una
de las iteraciones hasta llegar a la solución. En cada iteración se elige el
elemento que mejor rendimiento ha obtenido.
- Métodos de Búsqueda Local: Exploran el entorno de una solución original
mediante operaciones llamadas movimientos. Buscan las soluciones al
problema dentro del entorno de la solución inicial y las evalúan. La mejor
pasa a ser la nueva solución. Mientras la solución pueda mejorarse el
algoritmo continua.
La combinación de los métodos heurísticos de búsqueda local y los
constructivos constituyen la base inicial sobre la que se desarrollaron algunos
métodos metaheurísticos.
Metaheurísticas: Las Metaheurísticas están diseñadas para hacer frente a
problemas complejos de optimización, donde otros métodos de optimización
no han podido ser eficaces o eficientes. Estas técnicas han llegado a ser
reconocidas como uno de los mejores enfoques para resolver muchos
problemas complejos como es el caso en la mayoría de los problemas reales
de tipo combinatorio. La principal ventaja de las metaheurísticas radica tanto
en su eficacia como en su aplicabilidad general. Originalmente, se
desarrollaban complejas heurísticas muy específicas para resolver un
determinado problema de optimización combinatoria, y esta especialización
no siempre permitía su extrapolación a otro tipo diferente de problemas. Sin
embargo, al ser las metaherurísticas estrategias de resolución de carácter
general, el principal desafío en su uso, ha sido la adaptación concreta de la
metaheurística para un determinado tipo de problema. Lo que normalmente
requiere mucho menos trabajo que el desarrollo de una heurística específica
para una aplicación específica. La idoneidad de utilizar metaheurísticas frente
a otros métodos de optimización radica en el hecho de que éstas son capaces
de encontrar buenas soluciones en problemas que contienen muchos óptimos
locales y que no poseen una estructura capaz de orientar la búsqueda del
óptimo global. El procedimiento que utilizan las metaheurísticas comienza por
obtener una solución inicial (o un conjunto inicial de soluciones) y, a
continuación, iniciar una búsqueda de soluciones mejores guiada por ciertos
 principios. La estructura de búsqueda tiene muchos elementos comunes para
numerosas metaheurísticas. En cada etapa del algoritmo de búsqueda, se parte
de una solución (o un conjunto de soluciones), lo que representa el estado
actual del algoritmo. En la etapa siguiente se evalúa un nuevo candidato (o
conjunto de candidatos) dentro del entorno de la solución (o conjunto de
soluciones) de la etapa anterior. Esta evaluación consiste en calcular o estimar
el rendimiento del candidato o candidatos y compararlo con el rendimiento de
la etapa previa, e incluso a veces entre sí. Basándose en esta evaluación, el
candidato/s puede ser aceptado, entra a formar parte de la solución (o conjunto
de soluciones) de esa etapa, o rechazada, en cuyo caso la solución (o
conjunto) se mantiene. El proceso se repite hasta que se cumple un
determinado criterio de fin.
Frente a las heurísticas, las metaheurísticas especifican estrategias generales
de orientación de la búsqueda sin concretar todos los detalles relativos a la
búsqueda. Por ejemplo, la estrategia de la búsqueda tabú es utilizar una lista
de soluciones llamada lista

MODELO DE TRANSPORTE
El modelo de transporte es un tipo específico de programación lineal que se utiliza
para optimizar el transporte de bienes desde varios orígenes (como fábricas) a varios
destinos (como almacenes o puntos de venta), minimizando los costos de transporte.
El problema de transporte surge en la planeación de la distribución de bienes desde
varios puntos de oferta (orígenes o fuentes) hasta varios puntos de demanda
(destinos). En general, se tiene la capacidad (oferta) de bienes en cada fuente, un
requerimiento (demanda) de bienes en cada destino, y el costo de envío por unidad de
cada fuente a cada destino. El objetivo de este problema es programar los envíos de
manera que se minimice el costo total de transporte.
Características del Modelo
Se basa en una matriz que representa los costos de transporte entre orígenes y
destinos. Es de vital importancia satisfacer la oferta y la demanda en cada punto.
Métodos para Resolver el Modelo
Método del Transporte:
- Método de la Esquina Noroeste, El método de la esquina Noroeste es un
algoritmo heurístico capaz de solucionar problemas de transporte o
distribución, mediante la consecución de una solución básica inicial que
 satisfaga todas las restricciones existentes, sin que esto implique que se
alcance el costo óptimo total.
- Método del Costo Mínimo, El método de costo mínimo trata de localizar
una mejor solución inicial del modelo de transporte, utilizando las rutas
baratas. El procedimiento es como sigue: asigne tanto como sea posible a
la variable con el costo unitario más pequeño en la tabla completa.
- Método de Aproximación, Uno de los objetivos del método de Vogel es
reducir al mínimo posible los costos de transportar mercaderías desde los
m orígenes (plantas productoras) hasta los n destinos (mercado
demandante), con lo cual estamos mejorando los niveles de rentabilidad de
la empresa.
Algoritmo MODI (Método del Análisis de Costo Mínimo). El método Modi
también calcula costos marginales pero sólo se busca la trayectoria asociada a
la variable no básica que va a entrar al sistema.

PROGRAMACIÓN DINÁMICA
La programación dinámica es un método para resolver problemas complejos al
dividirlos en subproblemas más simples. Es especialmente útil en problemas donde
las decisiones deben tomarse en etapas y donde cada decisión afecta las decisiones
futuras.
La programación dinámica toma normalmente uno de los dos siguientes enfoques:
- Top-down: El problema se divide en subproblemas, y estos se resuelven
recordando las soluciones por si fueran necesarias nuevamente. Es una
combinación de memorización y recursión.
- Bottom-up: Todos los problemas que puedan ser necesarios se resuelven
de antemano y después se usan para resolver las soluciones a problemas
mayores. Este enfoque es ligeramente mejor en consumo de espacio y
llamadas a funciones, pero a veces resulta poco intuitivo encontrar todos
los subproblemas necesarios para resolver un problema dado.

Características
El problema se puede dividir por etapas, y cada una de las etapas requiere de
una política de decisión.
Cada etapa tiene cierto número de estados, los estados son las distintas
condiciones posibles en las que se puede encontrar el sistema en cada etapa.
 El efecto de la política de decisión en cada etapa es transformar el estado
actual en un estado asociado con el inicio de la siguiente etapa, entonces
podemos decir que un estado es una columna de nodos, cada nodo representa
un estado y cada rama una política de decisión.
El procedimiento de resolución de la programación dinámica está diseñado
para encontrar una política óptima para cada etapa logrando así la política
óptima general.
Dado el estado actual, una política óptima para las etapas restantes es
independiente de la política adoptada en etapas anteriores, por ende, la
decisión inmediata óptima solo depende del estado actual y no de cómo se
llegó ahí.
Se dispone de una relación recursiva que identifica la política óptima para la
etapa n, dada la política óptima para la etapa n+1.
Cuando se hace uso de la relación recursiva, el procedimiento de solución
comienza al final se mueve hacia atrás etapa por etapa hasta encontrar la
política óptima en cada etapa hasta la etapa inicial.
Aplicaciones
Problemas de optimización en logística.
Estrategias de inversión.
Problemas de secuenciación y planificación.
Ejemplos Clásicos
El problema de la mochila (knapsack problem). El problema de la mochila se
puede formular como sigue: Un excursionista debe decidir qué cosas incluir
en su mochila. Tiene n objetos entre los que elegir y cada objeto tiene un peso
pj y una utilidad uj. El excursionista quiere maximizar la utilidad de la
mochila que se encuentra sujeta a una restricción, el peso de la mochila P ≥ 0.
Problemas de Localización. Uno de los problemas clásicos de la programación
entera, es el problema de localización. Su desarrollo a lo largo del tiempo ha
sido tal, que existen múltiples versiones de este problema. Supongamos que
disponemos de una empresa con m potenciales ubicaciones distintas en donde
situar un almacén de distribución para atender las demandas de n clientes. El
problema que se plantea, es decidir qué almacenes deberían abrirse y qué
cantidad de mercancías se deben enviar desde cada almacén a cada cliente.
 CONCLUSIÓN
La programación entera se presenta como una herramienta esencial cuando se
requiere que las variables de decisión tomen valores enteros. Este enfoque es
particularmente relevante en situaciones donde las decisiones son discretas, como la
asignación de recursos, la planificación de producción y la gestión de inventarios. A
diferencia de la programación lineal estándar, que permite variables continuas, la
programación entera enfrenta el desafío adicional de encontrar soluciones enteras
óptimas. Se ha destacado el uso de métodos como el algoritmo de Branch and Bound
y las técnicas de corte, que son esenciales para resolver problemas de programación
entera. Estos métodos permiten descomponer el problema en subproblemas más
manejables y aplicar restricciones adicionales que guían la búsqueda hacia soluciones
viables. A través de ejemplos prácticos, se ha ilustrado cómo la programación entera
puede ser aplicada en contextos reales, como la optimización de rutas de entrega o la
asignación eficiente de tareas en un entorno de producción.
El modelo de transporte se ha analizado como una técnica clave para optimizar la
distribución de bienes desde múltiples orígenes a varios destinos, minimizando así los
costos de transporte. Este modelo se basa en una matriz que representa los costos
asociados a cada ruta y busca satisfacer las restricciones de oferta y demanda. Se han
presentado métodos específicos para resolver este modelo, como el Método de la
Esquina Noroeste y el Método MODI, que facilitan la identificación de soluciones
óptimas. La aplicabilidad del modelo de transporte es notable en la gestión de
cadenas de suministro y logística, donde una distribución eficiente puede generar
ahorros significativos y mejorar el servicio al cliente. La comprensión de este modelo
permite a las organizaciones tomar decisiones informadas sobre cómo mover
productos y recursos de manera efectiva.
La programación dinámica se ha discutido como un enfoque poderoso para
resolver problemas complejos que requieren decisiones secuenciales. Esta técnica
permite dividir un problema en etapas más pequeñas y manejables, donde cada
decisión influye en el futuro. La programación dinámica es especialmente útil en
situaciones como la planificación financiera, la optimización de rutas y el diseño de
algoritmos eficientes para problemas como el problema de la mochila. A través de
ejemplos clásicos, se ha demostrado cómo esta metodología puede ofrecer soluciones
efectivas a problemas que parecen intratables mediante enfoques más simples. La
programación entera, el modelo de transporte y la programación dinámica no solo
enriquecen el marco teórico de la optimización, sino que también ofrecen
herramientas prácticas para enfrentar desafíos reales en áreas como la logística, la
producción y la toma de decisiones estratégicas.
 REFERENCIAS
Masiá, Arturo Elizalde. “Introducción a la programación lineal y entera:
métodos del Simplex y de B&B”. Universitat de Barcelona, Facultat de
Matematiques i informática. Barcelona, Junio 2020. Pp 3 – 39.
Caballero, Ricardo. Msc. “Investigación de Operaciones I” Universidad
Tecnológica de Panamá, Facultad de Ingeniería Industrial. Panamá, 2021.
F. Glover and G. A. Kochenberger, “Handbook of Metaheuristics,” Kluwer
Academic Publishers, New York, 2003.