Descomposición de Danzig-Wolfe

El método de descomposición de Danzig-Wolfe es una versión especializada del método simplex .

En 1960, George Dantzig y Philip Wolf método de descomposición para resolver problemas de alta dimensión con una estructura matricial de restricción especial [1] .

Este método resultó ser el más efectivo para resolver problemas cuya matriz de restricciones tiene forma de bloque diagonal con un número pequeño de variables. Sin embargo, como mostraron estudios posteriores, el método también es aplicable a problemas de programación lineal con una matriz general. El método correspondiente fue propuesto por D. B. Yudin y E. G. Holstein y se llama programación de bloques .

Una característica distintiva del método de descomposición es el uso de un problema de coordinación que, en comparación con el original, tiene un pequeño número de filas y un gran número de columnas.

Método de generación de columnas

Es esencial que la solución del problema de coordinación no requiera la especificación explícita de todas las columnas. Se generan en el proceso de utilizar el método simplex. Este enfoque se denomina método de generación de columnas .

Basta con poder generar una columna y tener un procedimiento que seleccione una columna para ingresar a la base.

A menudo, dicho procedimiento se reduce a resolver un subproblema específico (no necesariamente programación lineal).

El principio de descomposición

Lema Sea un conjunto acotado cerrado no vacío en el espacio euclidiano y tenga un número finito de puntos extremos, que se denotarán aquí . Entonces cualquier punto del conjunto se puede representar como una combinación convexa de puntos extremos del conjunto R, es decir pues hay números no negativos cuya suma total es uno ( ) y tales que $R$ $k$ $z_{k=1:K}$ $z$ $R$ $z$ $\delta_{k}$ ${\ estilo de visualización \ suma _ {k = 1} ^ {K} \ delta _ {m} = 1}$

(1) . ${\displaystyle z=\sum_{k=1}^{K}\delta_{k}z_{k))$

Deja que la tarea

Maximizar

(2) ${\ estilo de visualización c [N] x [N]}$

bajo restricciones

(3) $A[M_{1},N]x[N]=b[M_{1}]$

(cuatro) $A[M_{2},N]x[N]=b[M_{2}]$

(5) ${\ estilo de visualización x [N] \ geq 0 [N]}$

Las restricciones (3) definen un simplex S, sean sus puntos extremos. ${\ estilo de visualización z [K]}$

Sea x una solución admisible por el lema $x=z[N,K]\cdot\delta [K]$

Sustituyamos la última expresión en (2) y (3).

La tarea tomará la forma

maximizar (6) $(c[N]\cdot z[N,K])\cdot \delta [K]=g[K]\cdot \delta [K]$

bajo restricciones

(7) $(A[M_{1},N]\cdot z[N,K])\cdot \delta [K]=D[M_{1},K]\cdot \delta [K]=b[M_ {una}]$

(8) . ${\ estilo de visualización \ delta [K] \ cdot 1 [K] = 1}$

Esta tarea es equivalente a la original (2)-(5) y se denomina tarea de coordinación .

Tiene solo filas de restricciones en comparación con las filas del problema original, y un número muy grande de columnas igual al número de puntos extremos del conjunto . Para no almacenar todas estas columnas en la memoria de la computadora, las recibiremos según sea necesario, utilizando el método de generación de columnas. ${\ estilo de visualización | M_ {1} | +1}$ ${\ estilo de visualización |M_{1}|+|M_{2}|}$ $|K|$ $S$

Algoritmo

Resolvemos el problema (6)-(8) por el método símplex utilizando el método de generación de columnas.

Para simplificar, supongamos que ya se conoce alguna solución básica admisible.

Denote por la restricción (8), entonces las variables duales son el vector . $\delta$ $d[M_{1}\cup {\delta }]$

Para ingresar la base, es necesario encontrar , tal que ${\ estilo de visualización z [N, m]}$

$d[M_{1}]D[M_{1},K]+d[\delta]<g[m]$

Por lo tanto, basta con encontrar m en el que se alcanza el mínimo

(9) $d[M_{1}]A[M_{1},N]\cdot z[N,m]+d[\delta ]-c[N]z[N,m]$

lo que equivale a resolver el problema

minimizar (10) $(d[M_{1}]A[M_{1},N]-c[N])\cdot x[N])$

bajo las restricciones (4) y (5).

Si el mínimo encontrado no es mayor que , el problema está resuelto. ${\ estilo de visualización -d [\ delta]}$

De lo contrario, se ingresa en la base la columna correspondiente a la solución encontrada. $D[M_{1},k]$

Bloquear tareas

Deje que las restricciones (4) tengan una estructura de bloque

{\begin{pmatrix}A[M_{1},N_{1}]&0[M_{1},N_{2}]&\cdots &0[M_{1},N_{n}]\\ 0[M_{2},N_{1}]&A[M_{2},N_{2}]&\cdots &0[M_{2},N_{n}]\\\cdots &\cdots &\cdots & \cdots &\\0[M_{n},N_{1}]&0[M_{n},N_{2}]&\cdots &A[M_{n},N_{n}]\\\end{pmatriz }}

El problema (10), (4), (5) se divide en subtareas separadas

Encuentra el mínimo

(once) $(d[M_{k}]A[M_{k},N_{k}]-c[N_{k}])z[N_{k}]+d[\delta]$

bajo condiciones

(12) $A[M_{k},N_{k}]z[N_{k}]=b[M_{k}]$

Notas

↑ George B. Dantzig; Felipe Lobo. Principio de descomposición para programas lineales (indefinidos) // Investigación de operaciones. - 1960. - T. 8 . - S. 101-111 .

Literatura

Hemdy A. Taha. Capítulo 3. El Método Simplex // Introducción a la Investigación Operativa = Investigación Operativa: Una Introducción. - 7ª ed. - M. : "Williams" , 2007. - S. 95-141. — ISBN 0-13-032374-8 .

Holstein E. G., Yudin D. B. Nuevas direcciones en programación lineal .. - M . : Radio soviética, 1966.

Yudin D. B., Goldstein E. G. Programación lineal (teoría, métodos y aplicaciones). - M. : Nauka, 1969.

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial