Descargar

Programación lineal

Enviado por Pablo Turmero


    Monografias.com

    Problema I

    Dado el programa lineal.

    edu.red

    Se ha obtenido como tabla final solución del Simplex la siguiente

    x1

    x2

    x3

    s1

    s2

    Sol

    Max z

    0

    2

    0

    2

    1

    19

    x1

    1

    5

    0

    3

    -1

    1

    x3

    0

    -7

    1

    -5

    2

    2

    Se pide en tal caso describir independientemente para cada eventualidad las consecuencias producidas, y en su caso la nueva solución, si ocurre que:

    a) (Un punto). Se añade una nueva restricción de la forma

    b) (Un punto). El coeficiente de x3 en la segunda restricción pasa de valer 3 a valer 4.

    c) (Un punto). Se añade una nueva variable de decisión x4 con coeficientes 2 y 3 en la primera y segunda restricción respectivamente y con coeficiente 1 en la función objetivo.

    Solución al problema I

    a) La solución x1 = 1, x2 = 0, x3 = 2 no verifica la nueva restricción (1+0+3.2 = 7 > 4) y por tanto esta no será redundante. En efecto añadiéndola a la tabla original, tendremos la tabla

    x1

    x2

    x3

    s1

    s2

    s3

    SOL

    Max z

    0

    2

    0

    2

    1

    0

    19

    x1

    1

    5

    0

    3

    -1

    0

    1

    x3

    0

    -7

    1

    -5

    2

    0

    2

    s3

    1

    1

    3

    0

    0

    1

    4

    Esta tabla no está dispuesta de acuerdo con los requisitos del Simplex puesto que dos variables básicas (x1 y x2) no tienen asociados vectores de la base canónica, lo cual corregimos restándole a la última fila la primera y también la segunda multiplicada por 3. Obtenemos en consecuencia:

    x1

    x2

    x3

    s1

    s2

    s3

    SOL

    Max z

    0

    2

    0

    2

    1

    0

    19

    x1

    1

    5

    0

    3

    -1

    0

    1

    x3

    0

    -7

    1

    -5

    2

    0

    2

    s3

    0

    17

    0

    12

    -5

    1

    -3

    Resulta inmediato constatar que la solución es obviamente sobreoptimal pero no factible (lo que era de esperar al no ser la nueva restricción redundante con las previamente establecidas). Por tanto podremos aplicar el algoritmo dual. Sus reglas de actuación señalan que el primer pivote a elegir es el señalado en negrita y cursiva en la tabla anterior. Pivotando obtenemos

    x1

    x2

    x3

    s1

    s2

    s3

    SOL

    Max z

    0

    27/5

    0

    22/5

    0

    1/5

    92/5

    x1

    1

    8/5

    0

    3/5

    0

    -1/5

    8/5

    x3

    0

    -1/5

    1

    -1/5

    0

    2/5

    4/5

    s2

    0

    -17/5

    0

    -12/5

    1

    -1/5

    3/5

    Solución que resulta ser factible y, en consecuencia la solución final buscada.

    b) Como x3 es una variable básica va a cambiar la matriz que en nuestra nomenclatura denominamos Ab. En consecuencia variará su inversa lo que afecta simultáneamente a la fila de multiplicadores (optimalidad), a los lados derechos (factibilidad) y al valor de la solución. Por tanto tendremos:

    edu.red

    Para que la nueva solución sea factible tendrá que verificarse que

    edu.red

    Y en efecto no hay cambios en la factibilidad, aunque si en el valor de la función objetivo como es natural.

    Pero además la fila de multiplicadores valdrá:

    edu.red

    Como son todos positivos permaneceremos en la optimalidad. En consecuencia la nueva solución será

    x1 = 5/3

    x2 = 0

    x3 = 2/3

    s1 = 0

    s2 = 0

    z = 55/3

    c) Para obtener la nueva variable decisión tendremos que considerar

    edu.red

    y el valor del multiplicador que se obtiene por medio de

    edu.red

    Por tanto, al ser positivo, permanecemos en la optimalidad y la nueva variable resulta irrelevante.

    Problema II

    Dado el programa lineal:

    Se pide:

    a) Determinar su programa dual.

    b) Representar este último gráficamente, una vez efectuado el conveniente cambio de variable necesario para conseguir que todas las variables de decisión sean positivas.

    c) A la vista de esta representación, y ante la inexistencia de una solución básica factible inicial, efectuar las operaciones de pivotado necesarias, que no tienen por que seguir las reglas del Simplex, para alcanzar la solución del programa. Señalar en el gráfico el camino seguido para alcanzar el óptimo.

    d) Determinar la solución del programa original mediante las relaciones de holgura complementaria.

    Solución al problema II

    a) Utilizando las reglas de determinación del programa dual obtenemos directamente como expresión del programa dual el siguiente:

    En efecto, el problema ha de ser Min pues el primal es Max; las ecuaciones segunda y tercera son con signo ( pues las variables asociadas son negativas; mientras que la variable y1 es negativa porque la restricción asociada lleva el signo ( y el problema es de Max.

    b) Para representar este último gráficamente y para atenernos a la costumbre de considerar todas las variables de decisión positivas efectuamos el cambio de variable y1 = -v1, y, para mantener la homogeneidad en la escritura, y2 = v2.

    Entonces el programa quedará:

    La representación gráfica será:

    c) A la vista de esta representación, y ante la inexistencia de una solución básica factible inicial, veamos la tabla correspondiente introduciendo las variables de holgura:

    v1

    v2

    s1

    s2

    s3

    s4

    Sol

    Min w

    1

    -2

    0

    0

    0

    0

    0

    s1

    1

    1

    -1

    0

    0

    0

    10

    s2

    -1

    1

    0

    1

    0

    0

    4

    s3

    -1

    2

    0

    0

    1

    0

    14

    s4

    2

    -1

    0

    0

    0

    1

    8

    Como resulta evidente la solución no es factible. Pero si realizamos el trayecto marcado por la flecha horizontal (que entre en la base v1 y que salga de ella s1) y después hacemos el ascendente (que entre en la base v2 y que salga de ella s4) hallaremos la solución. Resulta evidente que podemos realizar otros muchos trayectos con el mismo resultado. Así pues, pivotando sucesivamente alrededor de los elementos marcados en cursiva y negrita, obtenemos:

    v1

    v2

    s1

    s2

    s3

    s4

    Sol

    Min w

    0

    -3

    1

    0

    0

    0

    -10

    v1

    1

    1

    -1

    0

    0

    0

    10

    s2

    0

    2

    -1

    1

    0

    0

    14

    s3

    0

    3

    -1

    0

    1

    0

    24

    s4

    0

    -3

    2

    0

    0

    1

    -12

    v1

    v2

    s1

    s2

    s3

    s4

    Sol

    Min w

    0

    0

    -1

    0

    0

    -1

    2

    v1

    1

    0

    -1/3

    0

    0

    1/3

    6

    s2

    0

    0

    1/3

    1

    0

    2/3

    6

    s3

    0

    0

    1

    0

    1

    1

    12

    v2

    0

    1

    -2/3

    0

    0

    -1/3

    4

    d) Si h1 y h2 son las holguras del programa original, entonces se ha de verificar que

    Por tanto de las restricciones originales y de lo anterior deducimos que

    Sistema que tiene como solución x1 = x4 = 1, siendo z = 2.

    Problema III

    Dado el programa lineal:

    Se pide:

    a) Resolverlo utilizando el método del Simplex.

    b) Alcanzada la solución, constatar la existencia de soluciones múltiples mostrando las tablas representativas de los vértices que las definen.

    c) Escribir una expresión general que resuma el conjunto de las soluciones.

    Solución al problema III

    a) La tabla inicial del simplex, en la que se constata la existencia de una solución factible básica inicial es:

    x1

    x2

    s1

    s2

    s3

    SOL

    Max z

    1

    -2

    0

    0

    0

    0

    s1

    1

    0

    1

    0

    0

    8

    s2

    -1

    1

    0

    1

    0

    4

    s3

    -3

    6

    0

    0

    1

    42

    Pivotando según las reglas del simplex alrededor de los elementos marcados en negrita y cursiva obtenemos sucesivamente:

    x1

    x2

    s1

    s2

    s3

    SOL

    Max z

    -1

    0

    0

    2

    0

    8

    s1

    1

    0

    1

    0

    0

    8

    x2

    -1

    1

    0

    1

    0

    4

    s3

    3

    0

    0

    -6

    1

    18

    x1

    x2

    s1

    s2

    s3

    SOL

    Max z

    0

    0

    0

    0

    1/3

    14

    s1

    0

    0

    1

    2

    -1/3

    2

    x2

    0

    1

    0

    -1

    1/3

    10

    x1

    1

    0

    0

    -2

    1/3

    6

    Que es un óptimo.

    b) Sin embargo, el multiplicador correspondiente a la variable no básica s2 es nulo, lo que implica la existencia de soluciones múltiples. Partiendo de la tabla anterior

    x1

    x2

    s1

    s2

    s3

    SOL

    Max z

    0

    0

    0

    0

    1/3

    14

    s1

    0

    0

    1

    2

    -1/3

    2

    x2

    0

    1

    0

    -1

    1/3

    10

    x1

    1

    0

    0

    -2

    1/3

    6

    si forzamos la entrada en la base de s2, obtendremos la nueva tabla solución

    x1

    x2

    s1

    s2

    s3

    SOL

    Max z

    0

    0

    0

    0

    1/3

    14

    s2

    0

    0

    1/2

    1

    -1/6

    1

    x2

    0

    1

    1

    0

    -1/6

    11

    x1

    1

    0

    1

    0

    0

    8

    Resulta claro que no hay más soluciones factibles básicas óptimas pues lo único que podemos hacer a partir de esta solución es forzar la entrada de s1 en la base, lo que trae aparejado la entrada forzosa en ella de s2 volviendo a obtener la solución original.

    c) Las soluciones anteriores son, para un valor de la función objetivo 14, las siguientes:

    La solución general será de la forma (A + (1-()B y en consecuencia se expresará como:

     

     

    Autor:

    Iván José Pablo Turmero Astros