Tengo un programa lineal entero (ILP) con algunas variables que están destinadas a representar valores booleanos. Las están restringidas a ser enteros y a contener 0 o 1 ( ).x i 0 ≤ x i ≤ 1xixix_ixixix_i0≤xi≤10≤xi≤10 \le x_i \le 1 Quiero expresar operaciones booleanas en estas variables con valor...
Un sorprendente número de problemas tiene reducciones bastante naturales a la programación lineal (LP). Consulte el Capítulo 7 de [1] para ver ejemplos como flujos de red, emparejamiento bipartito, juegos de suma cero, rutas más cortas, una forma de regresión lineal e incluso evaluación de...
Dado que la programación lineal entera es NP-completa, hay una reducción de Karp de cualquier problema en NP. Pensé que esto implicaba que siempre hay una formulación de ILP de tamaño polinómico para cualquier problema en NP. Pero he visto documentos sobre problemas específicos de NP en los que la...
El problema de la programación lineal: encuentre un algoritmo de tiempo fuertemente polinomial que para la matriz dada A ∈ Rm × ny b ∈ Rm decida si existe x ∈ Rn con Ax ≥ b. Sé que Steve Smale enumera algunos de los problemas no resueltos en matemáticas. Pero tal problema de programación lineal es...
El algoritmo simplex camina con avidez por las esquinas de un politopo para encontrar la solución óptima al problema de programación lineal. Como resultado, la respuesta es siempre una esquina del politopo. Los métodos de punto interior recorren el interior del politopo. Como resultado, cuando un...
Me gustaría aprender algo sobre este problema de optimización: para números enteros no negativos dados , encuentre una función minimice la expresiónai,j,kai,j,ka_{i,j,k}fff maxk∑iai,f(i),kmaxk∑iai,f(i),k\max_k \sum_i a_{i,f(i),k} Un ejemplo que utilice una formulación diferente podría aclararlo:...
Según tengo entendido, el problema de asignación está en P ya que el algoritmo húngaro puede resolverlo en tiempo polinómico - O (n 3 ). También entiendo que el problema de asignación es un problema de programación lineal de enteros , pero la página de Wikipedia dice que esto es NP-Hard. Para mí,...
Quiero expresar la siguiente restricción, en un programa lineal entero: y={01if x=0if x≠0.y={0if x=01if x≠0.y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases} Ya tengo las variables enteras y me prometieron que . ¿Cómo puedo expresar la restricción anterior, en una forma...
Considere los programas lineales. Primal:Ax⃗ ≤b⃗ maxc⃗ Tx⃗ Primal:Ax→≤b→maxc→Tx→\begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} Dual:c⃗ ≤y⃗ TAminy⃗ Tb⃗ Dual:c→≤y→TAminy→Tb→\begin{array}{|ccc|} \hline Dual: & \vec{c} \leq...
Para el método de ramificación y corte, es esencial conocer muchas facetas de los politopos generados por el problema. Sin embargo, actualmente es uno de los problemas más difíciles calcular todas las facetas de dichos politopos a medida que crecen rápidamente. Para un problema de optimización...
Tradicionalmente, la programación lineal se utiliza para encontrar la solución óptima para un conjunto de restricciones, variables y un objetivo (todos descritos como relaciones lineales). A veces, cuando el objetivo es paralelo a una restricción, hay infinitas o muchas soluciones óptimas...