Cajera

Tema 4: Teor´ de Dualidad. Algoritmo Dual del Simplex ıa Curso 2004-05 1. Dado el problema: Min s.a.: 2x1 + 3x2 + 5x3 + 6x4 x1 + 2x2 + 3x3 + x4 ≥ 2 −2x1 + x2 − x3 + 3x4 ≤ −3 x1 , x2 , x3 , x4 ≥ 0Problemas

a) Formular su dual. a b) Resolver gr´ficamente el problema dual. c) Resolver el problema primal con la informaci´n recopilada en el apartado o anterior. 2. Dado el siguiente problema deProgramaci´n Lineal, o Min s.a.: z=− 3x1 + 2x2 + 2x3 2x1 + x3 ≤ 8 −x1 + x2 + x3 ≥ 13 x1 , x2 , x3 ≥ 0

a a) Resolverlo utilizando el algoritmo m´s adecuado. b) Formular el problema dual. c) Plantearlas Condiciones de Holgura Complementaria asociadas. d ) Utilizar la informaci´n del apartado anterior para resolver el problema dual. o 3. Resolver con el algoritmo dual del simplex el siguienteproblema: Min s.a.: 2x3 − x1 + 2x2 − 2x3 − x1 + x2 + x3 2x1 − x2 + 4x3 x1 , x2 , x3 ≥ 8 ≤ 4 ≤ 10 ≥ 0

Obtener a partir de la tabla ´ptima todas las soluciones ´ptimas alternativas. o o o 4. Dado elsiguiente problema de Programaci´n Lineal, Min s.a.: z= x1 x1 x1 x1 x1 , − 2x2 + 2x2 − x2 − x2 x2 ≤ 9 ≤ 2 ≥ −3 ≥ 0

a) Resu´lvelo utilizando el algoritmo Simplex. e b) Formula el problema dual. c)Plantea las Condiciones de Holgura Complementaria para ambos problemas. o d ) Utiliza la informaci´n del apartado anterior para resolver el problema dual. 1

5. Un panadero fabrica tres tipos de pan,integral, blanco y panecillos de leche, para su elaboraci´n necesita principalmente harina y levadura. Si semanalmente o solamente puede disponer de 250 kilos de harina y de 300 gramos de levadura ¿c´modeber´ planificar su producci´n semanal para que el beneficio sea m´ximo? o ıa o a A continuaci´n se dan los precios de venta de los diferentes tipos de pan y las o cantidades de harina y levaduranecesarios para su elaboraci´n. o Harina (Kilos) Levadura (Gramos) Precio (pts.) Integral Blanco 1 2 2 1 20 60 Panecillos 2 3 30

a) Formular y resolver el problema dual. b) Un comercial le ofrece m´s...