PROGRAMACION NO LINEAL.METODO SEPARAVLE

Antes de adentrarnos al ejemplo, se explicara la notación usada.

〖a_i^k y t〗_(i→indica a que variable esta asociada.)^(k→indica el punto de reptura asociado.)

g_(l→indica a que restriccion hace referencia )^(i→indica a que variable hace referencia)

Ejemplo

Maximizar z=x_1+x_2^4

sujeta a g(x)=3x_1+2x_2^2≤9

x_1 〖,x〗_2≥0

Definamos primero las siguientes funciones separables de z:

f(x_1 )=x_1; f(x_2 )=x_2^4

De igual modo, para la restricción g(x):

g_1^1 (x_1 )=3x_1; g_1^2 (x_2 )=2x_2^2

Notemos primero que f(x_1 )=x_1 y g_1^1 (x_1 )=3x_1 quedan iguales pues ya son funciones lineales.

Se usara el siguiente intervalo (0,3) para la variable x_2.

Usaremos 4 puntos de ruptura, por lo tanto Δx_2=3/3=1

Con lo anterior tenemos que:

k a_2^k f_2 (a_2^k) g_1^2 (a_2^k)

1 0 0 0

2 1 1 2

3 2 16 8

4 3 81 18

Luego

f(x_2 )≈t_2^1 f_2 (a_2^1 )+t_2^2 f_2 (a_2^2 )+t_2^3 f_2 (a_2^3 )+t_2^4 f_2 (a_2^4)

Es decir,

f(x_2 )≈t_2^2+〖16t〗_2^3+〖81t〗_2^4

De igual modo g_1^2 (x_2 )≈〖2t〗_2^2+〖8t〗_2^3+〖18t〗_2^4

Con estos resultados obtenidos, podemos aproximar el problema original, con este problema de optimización lineal:

Maximizar z=x_1+t_2^2+〖16t〗_2^3+〖81t〗_2^4

sujeta a g(x)=3x_1+〖2t〗_2^2+〖8t〗_2^3+〖18t〗_2^4≤9;

t_2^1+t_2^2+t_2^3+t_2^4=1;

t_2^k≥0,con k=1,2,3,4;

x_1≥0

Resolvamos este problema usando el método simplex con base restringida.

Recordemos que la base restringida específica que que no más de dos t_i^kpositivas puede aparecer en la base, y además solo pueden ser dos t_i^k si son adyacentes.

Primera tabla simplex:

NOTA. La variable s, es una variable de holgura correspondiente a la restriccion.

base x_1 t_2^1 t_2^2 t_2^3 t_2^4 s z

s 3 0 2 8 18 1 0 9

〖 t〗_2^1 0 1 1 1 1 0 0 1

z -1 0 -1 -16 -81 0 1 0

El candidato para ser la variable entrante es t_2^4, pero notemos que siguiendo las condiciones de factibilidad, la variable saliente seria s, pero descartamos este caso pues en la base estarían t_(2 )^1 y t_2^4 que no son adyacentes y no cumple con las condiciones de la base restringida.

El siguiente candidato para ser la variable entrante es t_2^3 y la condición de factibilidad señala que la variable saliente es t_2^1 lo cual no viloa las condiciones de base restringida.

Segunda tabla simplex:

base x_1 t_2^1 t_2^2 t_2^3 t_2^4 s z

s 3 -8 -6 0 10 1 0 16

〖 t〗_2^3 0 1 1 1 1 0 0 1

z -1 16 -15 0 -65 0 1 1

El siguiente candidato

...