Programacion entera

Programación entera

La programación entera es aquella que cuya solución tiene sentido solo en una parte o todas las variables de decisión toman valores restringidos a números enteros, esto puede permitir incorporar en el modelamiento matemático aspectos que quedan fuera de la programación lineal.

Para el problema planteado es necesario considerar que la programación entera (PE) se le exige que las variables de decisión adopten valores enteros.

Este problema consiste en encontrar el valor optimo siendo este un problema de minimización es necesario realizarlo por el método simplex o doble fase según las restricciones que nos muestren envase a sus propiedades las cual determinara el meto por la que se iniciara el planteamiento.

[pic 1]

Una vez conocido las propiedades del problema se determinó que en el planteamiento de su propiedad se encuentra lo que es las variables. Se aplica el método de doble fase  cuando luego de llevar un modelo de programación lineal a su forma estándar no se dispone de una solución básica factible inicial.

En la fase l, se considera un problema auxiliar que resulta de agregar tantas variables auxiliares a las restricciones del problema, de modo de obtener una solución básica factible, luego se debe resolver utilizando el Método Simplex un nuevo problema que considera como función objetivo la suma de las variables auxiliares.

[pic 2]

En la fase 1 una vez planteado las propiedades, lo que se realiza es que nuestra variable R cuenta con un auxiliar o este caso una variable la cual es A1, porque es necesario restablecer el vector unitario de A1, mediante la eliminación de gauss, utilizando una suma de filas como muestra la captura entre F1+F3 siendo F1 nuestra variable R y F3 la variable A1, esto se realiza ya que en la propiedades de la variable A1 se encuentra la solución para que en la columna A1 donde está la artificial se elimine, dejando un nuevas propiedades en R.

[pic 3]

Entra la variable “x”, que corresponde al más positivo y sale la de menor cociente que es A1.

La intersección de la variable de entrada con la variable de salida se denomina pivote, y este es el cual debe convertiré en uno y el resto de elementos de la columna en cero. Por lo cual se multiplica 1/3.  Para hacer ceros el resto de elemento de la columna “x” se multiplica al reglón de x de la tabla y se restan los valores de la columna x por -3 de igual manera la F2A – F3A.

[pic 4]

Termina la fase 1 porque ya no se cuenta con variables de entrada (el más positivo),

 Inicia fase ll.

Se cambia la función objetivo de R a Z y se restablece los vectores unitarios.

[pic 5]

Resolver a través del Método Simplex el problema original a partir de la solución básica factible inicial hallada en la Fase 1.

[pic 6]

Entra la variable “y”, que corresponde al más positivo y sale la de menor cociente que es S1.

La intersección de la variable de entrada con la variable de salida se denomina pivote, y este es el cual debe convertiré en uno y el resto de elementos de la columna en cero. Por lo cual siendo 4/3 el valor del pivote para hacerlo 1 se tiene que multiplicar por ¾ de igual manera toda la fila de S1 siendo la de menor cociente sele tiene que multiplicar por este valor dando unos nuevas variables en esta fila.

[pic 7]

Una vez obtenido las nuevas variables, para hacer ceros el resto de la columna de entra que es “y” se debe de restar en la fila Z  los 5/3 que se encuentra en la columna de entrada de “y” por la fila de la nuevas variables que es S1 de igual manera el resto de la fila tiene que restarse por estas nuevas variables y la fila de “x” restarles los 2/3 que se encuentra en la columna de entrada.

Dando fin al método de doble fase e iniciando con la ramificación con la variable X ya que está más alejada de un entero.

Z=66.25, y=4.25, x=4.5

Inicio del subproblema 1

Tomado encuentra que los enteros que estén más cerca de algún entero siendo x el más alejado de ellos y el propósito es que debemos de encontrar valores enteros en este problema de programación entera. Iniciando un subproblema el cual determinara el número entero más cercano.

[pic 8]

Se determinara cuál de los enteros se encuentra más cercano en el valor de “x” si es 4 o 5 tomando la ramificación del 4 para el planteamiento del subproblema 1.

Tomando las variables obtenidas al terminar la fase ll se planteara con la ramificación de x<=4 por el método simplex ya que esta no cuento con artificiales, implementando S2 como otra variable más, siendo la ecuación X+S2=4 plasmándola en cuadro según corresponda su valores en X y S2 que serían 1 y 1.

Una vez realizado esto se deberá restablecer el vector unitario en la fila S2 por lo cual se realiza una resta ya que lo que se ha de restablecer es el valor en la columna en x y la fila s2 cambiando por completo su variables de estas.

[pic 9] 

Al restablecerse el vector unitario en S2, se debe de tomar la variable de entrada más negativa y el variable de salida menor cociente pero al ver que nuestro valor será negativo en la de menor cociente este imposibilita seguir realizando el subproblema por lo cual no tiene solución, entonces la ramificación de x<=4 no puede determinar el valor entero más cercano de “x” por lo que se plante un subproblema 2 el cual es con la ramificación de x>=5.

Subproblema 2

[pic 10]

En el subproblema 2 se tomara la segunda ramificación de “x” que es 5 por los que se le agregara ala tabla una S3 que esta determinará que ”x=>5”, y su planteamiento es –X+S3=5,  por lo que en la tabla se cambia el S2, por S3 y los demás valores se mantienen.

De mismo modo se recure a restablecer los vectores por lo que la F4 (S3) se suma con la F3 (x) la cual eliminara la variable -1 de S3 ya que solo se está buscando el valor en S3.

[pic 11]

Una vez realizado la anterior operación se toman la quesera nuestra variable de entrada la cual pueden ser dos ya que se llegaran al mismo resultado, se tomaran en cuenta las dos entradas de  variable pero la que se explicara será la menso negativa -5/4, en este caso se tomara  la variable de entrada en la columna S1 y la fila de salida S3.

...