Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Programación lineal




Enviado por Pablo Turmero




    Monografias.com

    Problema I

    Dado el programa lineal.

    Monografias.com

    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:

    Monografias.com

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

    Monografias.com

    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á:

    Monografias.com

    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

    Monografias.com

    y el valor del multiplicador que se obtiene por medio
    de

    Monografias.com

    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

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter