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 un Ensamble

Cierta empresa produce un artículo que se forma con cuatro piezas del componente A y tres piezas del componente B.

Las piezas se pueden fabricar en cualquiera de las tres máquinas diferentes que posee la compañía, las cuales transforman las dos materias primas en las piezas que van al ensamble del producto final.

La tabla siguiente muestra el número de gramos de cada materia prima que deben utilizarse en cada máquina para realizar un ciclo de producción de las componentes. La misma tabla muestra el número de componentes de cada tipo que se obtienen en cada ciclo de producción de cada una de las maquinas, así como el número de gramos disponibles de las materias primas.

¿Cómo debe programarse la producción para obtener la máxima cantidad de artículos?

Construcción del modelo

Para un mejor entendimiento elaboremos un diagrama de la situación

Definición de variables

Xi = Número de tandas de producción que realiza la máquina i.

Cada tanda de producción de las máquinas utiliza cierta cantidad de las materias primas y produce cierta cantidad de los componentes A y B, con los cuales se obtiene el ensamble del producto final.

Como para cada unidad del ensamble se utilizan cuatro unidades del componente A y tres del componente B, se concluye que el número total de ensambles obtenidos será el resultado de dividir por cuatro el número de componentes tipo A, pero también debe ser igual al número de componentes

...