Progrmacion Lineal Entera Mixta

PROGRAMACIÓN ENTERA MIXTA

Sea xk una variable entera del problema mixto. De nuevo, como en la casa entero puro, considere la ecuación xk en la solución continua óptima. Esta se da como

xk=βk-∑_(j=1)^n▒〖∝■(j@k)〗 wj=[βk]+fk-∑_(j=1)^n▒〖x■(j@k)wj〗 (Renglón fuente)

O bien

xk-[βk]=fk-∑_(j=1)^n▒〖∝■(j@k)wj〗

Debido a que en este caso algunas de las variables wj pueden no estar restringidas a valores enteros, es incorrecto usar el corte fraccional de la sección anterior. Pero puede emplearse un nuevo corte basado en la misma idea general.

Para que xk sea entera, debe satisfacerse xk ≤ [βk] o bien xk ≥ [βk] + 1. Del renglón fuente, estas condiciones nos equivalentes a

∑_(j=1)^n▒〖∝■(j@k)wj≥fk〗 (1)

∑_(j=1)^n▒〖∝■(j@k)wj≥fk-1〗 (2)

Sea

J+= conjunto de subíndices j para los cuales ∝■(j@k)≥0

j- = conjunto de subíndices j para los cuales ∝■(j@k)<0

Luego entonces, de (1) y (2), se obtiene

(3)

∑_(jϵJ+)▒〖∝■(j@k)wj≥fk〗

(4)

fk/(fk-1) ∑_(jϵJ-)▒〖∝■(j@k)wj≥fk〗

Ya que (1) y (2), tanto, (3) y (4) no pueden ocurrir simultáneamente, se deduce que (3) y (4) pueden combinarse en una restricción de la forma

Corte mixto

sk-{∑_(j∈k)▒〖∝■(j@k)wj+fk/(fk-1) ∑_jϵJ▒〖∝■(j@k)wj〗〗}=-fk

Donde sk ≥ 0 es una variable de holgura no negativa. La última ecuación es el corte mixto requerido y representa una condición necesaria para que xk sea entera. Ya que todas las wj son 0 en la tabla optima actual, se deduce que el corte anterior es infactible. Por consiguiente, se usa el método dual simplex para eliminar la infactibilidad.

El corte mixto se desarrolla sin tomar ventaja del hecho que algunas de las variables wj pueden ser enteras. Si esto se toma en cuenta resultara el siguiente corte más fuerte:

sk=-fk+∑_(j=1)^n▒λjwj

Donde λj={█(█(■(∝■(j@k) si∝■(j@k)≥0 y wj no es entera@fk/(fk-1)∝■(j@k) si∝■(j@k)<0 y wj no es entera)@fkj si fkj≤fk y wj es entera)@fk/(1-fk) (1-fkj) si fkj>fk y wj es entera)}

Ejemplo:

Programación de la Producción de

...