Métodos de Solución de Programación Entera: Cuestionarios y Ejercicios

Question 1

¿Qué tipo de problemas de Programación Entera suelen implicar un elevado número de variables binarias?

Accepted Answer

Problemas de mochila

Answer

Problemas de itinerancia

Answer

Problemas de flujo de red

Answer

Problemas de asignación

Question 2

¿Cuál de las siguientes NO es una ventaja de aplicar métodos heurísticos en la Programación Entera?

Accepted Answer

Generación garantizada de soluciones óptimas

Answer

Obtención de soluciones factibles en tiempos de cálculo razonables

Answer

Fácil implementación

Question 3

Los planos cortantes de Miller-Tucker-Zemlin se utilizan para cortar:

Accepted Answer

La envolvente convexa del policoro solución

Answer

La región de enteros

Answer

La envolvente convexa de la solución fraccionaria

Answer

El conjunto factible del modelo

Question 4

¿Cuál de los siguientes métodos NO es aplicable a modelos de Programación Entera?

Accepted Answer

Programación Dinámica

Answer

Ramificación y poda

Answer

Métodos heurísticos

Answer

Planos cortantes

Question 5

En el método de planos cortantes, ¿qué condición se aprovecha para generar un nuevo corte?

Accepted Answer

Violación de la desigualdad de factibilidad

Answer

Ninguna de las anteriores

Answer

Satisfacción de la desigualdad de factibilidad

Answer

Igualdad de la desigualdad de factibilidad

Question 6

Identifica un método heurístico empleado en la resolución de problemas de Programación Entera:

Accepted Answer

Algoritmo Voraz

Answer

Método de Descomposición de Columnas

Answer

Método de Simplex

Answer

Programación Lineal

Question 7

En el contexto de la Programación Entera, explica el propósito de la relajación lineal:

Accepted Answer

Sustituir las restricciones de enteros por restricciones continuas

Answer

Sustituir las variables continuas por variables enteras

Answer

Eliminar las restricciones de factibilidad

Question 8

Dentro del método de ramificación y poda, ¿qué estrategia determina la elección de la variable a ramificar?

Accepted Answer

Regla de ramificación

Answer

Regla de corte

Answer

Regla de factibilidad

Answer

Regla de poda

Question 9

¿Cuál de las siguientes no es una técnica de ramificación y poda?

Accepted Answer

Ajuste dinámico

Answer

Búsqueda de primer fallo

Answer

Retroceso cronológico

Answer

Poda por límite inferior

Question 10

El plano cortante que fuerza una variable binaria a ser igual a 1 se denomina:

Accepted Answer

Forzamiento

Answer

Relajación

Answer

Valuación

Question 11

El método heurístico que resuelve iterativamente el problema de Programación Lineal relajado se llama:

Accepted Answer

Frank-Wolfe

Answer

Columna de generación

Answer

Descenso subgradiente

Answer

Lagrangeano

Question 12

¿Cuál de las siguientes afirmaciones sobre la Programación Entera Mixta es correcta?

Accepted Answer

Puede modelar problemas con variables tanto continuas como enteras.

Answer

Solo puede manejar problemas con variables binarias.

Answer

Siempre tiene una solución óptima.

Question 13

El método de planos cortantes de Chvátal-Gomory se utiliza para generar planos cortantes para:

Accepted Answer

Variables enteras no negativas

Answer

Variables binarias

Answer

Variables discretas

Answer

Variables continuas

Question 14

¿Cuál de las siguientes es una ventaja del método de ramificación y poda frente a los planos cortantes?

Accepted Answer

Puede encontrar soluciones factibles rápidamente.

Answer

Siempre encuentra la solución óptima.

Answer

Maneja mejor los problemas con muchas variables enteras.

Question 15

El problema de seleccionar un conjunto de elementos que maximice una función objetivo sujeta a restricciones enteras se denomina:

Accepted Answer

Programación Entera

Answer

Programación Dinámica

Answer

Programación No Lineal

Answer

Programación Lineal

Question 16

El método de resolución de Programación Entera que utiliza una red de trayectorias se conoce como:

Accepted Answer

Programación Entera Basada en Columnas

Answer

Programación Lineal Entera

Answer

Programación Entera Mixta

Question 17

¿Cuál de las siguientes restricciones enteras no puede modelarse directamente mediante Programación Lineal?

Accepted Answer

x es un múltiplo de 3

Answer

x es menor o igual que 5

Answer

x es binario

Answer

x es mayor o igual que 10

Question 18

El plano cortante que fuerza una variable binaria a ser igual a 0 se denomina:

Accepted Answer

Cobertura

Answer

Forzamiento

Answer

Estabilización

Answer

Valuación

Question 19

¿Cuál de las siguientes afirmaciones sobre la Ramificación y Poda (Branch and Bound) es FALSA?

Accepted Answer

El método siempre explora todas las posibles soluciones del problema.

Answer

Divide el problema original en subproblemas más pequeños.

Answer

Se utiliza para resolver problemas de Programación Entera.

Question 20

Un problema de mochila (knapsack) con restricciones de capacidad y variables de decisión binarias se puede resolver utilizando:

Accepted Answer

Programación Entera

Answer

Método Gráfico

Answer

Método Simplex

Answer

Programación Lineal

Question 21

En el contexto de Planos Cortantes, ¿cuál es el objetivo de añadir desigualdades válidas al problema original?

Accepted Answer

Mejorar la relajación lineal del problema entero.

Answer

Convertir el problema entero en un problema lineal.

Answer

Aumentar el número de variables del problema.

Answer

Encontrar soluciones factibles para el problema entero.

Question 22

¿Cuál de los siguientes NO es un método heurístico para la resolución de problemas de Programación Entera?

Accepted Answer

Método Simplex

Answer

Algoritmos Genéticos

Answer

Recocido Simulado

Answer

Búsqueda Tabú

Question 23

En un problema de asignación de tareas a trabajadores, ¿qué tipo de variable se utilizaría para representar si un trabajador es asignado a una tarea?

Accepted Answer

Variable binaria

Answer

Variable continua

Answer

Variable de holgura

Answer

Variable entera

Question 24

¿Qué significa que un algoritmo de Programación Entera sea "exacto"?

Accepted Answer

Garantiza encontrar la solución óptima global.

Answer

Encuentra una solución factible en un tiempo razonable.

Answer

Aproxima la solución óptima con un error aceptable.

Answer

Utiliza métodos heurísticos para encontrar la mejor solución posible.

Question 25

En la Ramificación y Poda, ¿qué ocurre cuando se encuentra una solución entera mejor que la mejor solución entera encontrada hasta el momento?

Accepted Answer

Se actualiza la mejor solución encontrada y se continúa la búsqueda.

Answer

Se detiene la búsqueda y se devuelve la solución encontrada.

Answer

Se ignora la solución y se continúa la búsqueda en otras ramas.

Question 26

¿Cuál de las siguientes es una ventaja de utilizar métodos heurísticos para resolver problemas de Programación Entera?

Accepted Answer

Pueden encontrar soluciones buenas en un tiempo computacional razonable para problemas grandes.

Answer

Son fáciles de implementar para cualquier tipo de problema entero.

Answer

Garantizan encontrar la solución óptima global.

Question 27

Un plano cortante generado a partir de una restricción del problema original se conoce como:

Accepted Answer

Plano cortante Gomory

Answer

Plano cortante de intersección

Answer

Plano cortante de flujo

Answer

Plano cortante disyuntivo

Question 28

En el contexto de los métodos de solución de Programación Entera, ¿qué significa "relajación lineal"?

Accepted Answer

Eliminar las restricciones de integralidad de las variables.

Answer

Aproximar la función objetivo por una función lineal.

Answer

Resolver el problema original utilizando solo variables enteras.