PROBLEMA 7 Un contratista está considerando una propuesta para la pavimentación de una

carretera. Las especificaciones requieren un espesor mínimo de doce pulgadas

(12"), y un máximo de 18". La carretera debe ser pavimentada en concreto,

asfalto, gravilla, o cualquier combinación de estos tres elementos. Sin embargo,

las especificaciones requieren una consistencia final igual o mayor que la

determinado que 3" de su asfalto son tan resistentes como 1" de concreto, y 6" de

gravilla son tan resistentes como 1" de concreto. Cada pulgada de espesor por

yarda cuadrada de concreto le cuesta $10, el asfalto $3.80, y la gravilla $1.50.

Determine la combinación de materiales que el contratista debería usar para

minimizar su costo.

Como la restricción 1 es del tipo '≥' se agrega la variable de exceso X4 y la variable artificial X7.

Como la restricción 2 es del tipo '≤' se agrega la variable de holgura X5. Como la restricción 3 es del tipo '≥' se agrega la variable de exceso X6 y la

variable artificial X8.

MINIMIZAR: 10 X1 + 3,8 X2 + 1,5 X3

1 X1 + 1 X2 + 1 X3 ≥ 121 X1 + 1 X2 + 1 X3 ≤ 181 X1 + 1/3 X2 + 1/6 X3 ≥ 9X1, X2, X3 ≥ 0

Tabla 1

    0 0 0 0 0 0 -1 -1

Base Cb P0 P1 P2 P3P4

P5P6

P7 P8

P7 -1 12 1 1 1 -1 0 0 1 0

P5 0 18 1 1 1 0 1 0 0 0

P8 -1 9 1 1 / 3 1 / 6 0 0 -1 0 1

Z   -21 -2 -4 / 3 -7 / 6 1 0 1 0 0

La variable que sale de la base es P8 y la que entra es P1.

Tabla 2     0 0 0 0 0 0 -1 -1

Base CbP0

P1 P2 P3P4

P5P6

P7 P8

P7 -1 3 0 2 / 3 5 / 6 -1 0 1 1 -1

P5 0 9 0 2 / 3 5 / 6 0 1 1 0 -1

P1 0 9 1 1 / 3 1 / 6 0 0 -1 0 1

Z   -3 0-2 / 3

-5 / 6 1 0 -1 0 2

Fila pivote (Fila 3):9 / 1 = 91 / 1 = 11 / 3 / 1 = 1 / 3

1 / 6 / 1 = 1 / 60 / 1 = 00 / 1 = 0-1 / 1 = -10 / 1 = 01 / 1 = 1

Fila 1:12 - (1 * 9) = 31 - (1 * 1) = 01 - (1 * 1 / 3) = 2 / 31 - (1 * 1 / 6) = 5 / 6-1 - (1 * 0) = -10 - (1 * 0) = 00 - (1 * -1) = 11 - (1 * 0) = 10 - (1 * 1) = -1

Fila 2:18 - (1 * 9) = 91 - (1 * 1) = 01 - (1 * 1 / 3) = 2 / 31 - (1 * 1 / 6) = 5 / 60 - (1 * 0) = 01 - (1 * 0) = 10 - (1 * -1) = 10 - (1 * 0) = 00 - (1 * 1) = -1

Fila Z:-21 - (-2 * 9) = -3-2 - (-2 * 1) = 0-4 / 3 - (-2 * 1 / 3) = -2 / 3-7 / 6 - (-2 * 1 / 6) = -5 / 61 - (-2 * 0) = 10 - (-2 * 0) = 0

1 - (-2 * -1) = -10 - (-2 * 0) = 00 - (-2 * 1) = 2

La variable que sale de la base es P7 y la que entra es P6.

Tabla 3

    0 0 0 0 0 0 -1 -1

Base Cb P0 P1 P2 P3P4

P5 P6 P7 P8

P6 0 3 0 2 / 3 5 / 6 -1 0 1 1 -1

P5 0 6 0 0 0 1 1 0 -1 0

P1 012

1 1 1 -1 0 0 1 0

Z   0 0 0 0 0 0 0 1 1

Fila pivote (Fila 1):3 / 1 = 30 / 1 = 02 / 3 / 1 = 2 / 35 / 6 / 1 = 5 / 6-1 / 1 = -10 / 1 = 01 / 1 = 11 / 1 = 1-1 / 1 = -1

Fila 2:9 - (1 * 3) = 60 - (1 * 0) = 02 / 3 - (1 * 2 / 3) = 0

5 / 6 - (1 * 5 / 6) = 00 - (1 * -1) = 11 - (1 * 0) = 11 - (1 * 1) = 00 - (1 * 1) = -1-1 - (1 * -1) = 0

Fila 3:9 - (-1 * 3) = 121 - (-1 * 0) = 11 / 3 - (-1 * 2 / 3) = 11 / 6 - (-1 * 5 / 6) = 10 - (-1 * -1) = -10 - (-1 * 0) = 0-1 - (-1 * 1) = 00 - (-1 * 1) = 11 - (-1 * -1) = 0

Fila Z:-3 - (-1 * 3) = 00 - (-1 * 0) = 0-2 / 3 - (-1 * 2 / 3) = 0-5 / 6 - (-1 * 5 / 6) = 01 - (-1 * -1) = 00 - (-1 * 0) = 0-1 - (-1 * 1) = 00 - (-1 * 1) = 12 - (-1 * -1) = 1

Tabla 1

    -10 -19 / 5 -3 / 2 0 0 0

Base Cb P0 P1 P2 P3 P4 P5 P6

P6 0 3 0 2 / 3 5 / 6 -1 0 1

P5 0 6 0 0 0 1 1 0

P1 -10 12 1 1 1 -1 0 0

Z   -120 0 -31 / 5-17 /

210 0 0

Eliminar las columnas correspondientes a las variables artificiales.

Modificar la fila de la función objetivo por la del problema original.

Calcular la línea Z:-(0) + (0 * 3) + (0 * 6) + (-10 * 12) = -120-(-10) + (0 * 0) + (0 * 0) + (-10 * 1) = 0-(-19 / 5) + (0 * 2 / 3) + (0 * 0) + (-10 * 1) = -31 / 5-(-3 / 2) + (0 * 5 / 6) + (0 * 0) + (-10 * 1) = -17 / 2-(0) + (0 * -1) + (0 * 1) + (-10 * -1) = 10-(0) + (0 * 0) + (0 * 1) + (-10 * 0) = 0-(0) + (0 * 1) + (0 * 0) + (-10 * 0) = 0

La variable que sale de la base es P6 y la que entra es P3.

Tabla 2     -10 -19 / 5-3 / 2

0 0 0

Base Cb P0 P1 P2 P3 P4P5

P6

P3-3 / 2

18 / 5 0 4 / 5 1 -6 / 5 0 6 / 5

P5 0 6 0 0 0 1 1 0

P1 -10 42 / 5 1 1 / 5 0 1 / 5 0 -6 / 5

Z   -447 / 5 0 3 / 5 0 -1 / 5 0 51 / 5

Fila pivote (Fila 1):3 / 5 / 6 = 18 / 50 / 5 / 6 = 02 / 3 / 5 / 6 = 4 / 55 / 6 / 5 / 6 = 1-1 / 5 / 6 = -6 / 50 / 5 / 6 = 01 / 5 / 6 = 6 / 5

Fila 2:6 - (0 * 18 / 5) = 60 - (0 * 0) = 00 - (0 * 4 / 5) = 00 - (0 * 1) = 01 - (0 * -6 / 5) = 11 - (0 * 0) = 10 - (0 * 6 / 5) = 0

Fila 3:12 - (1 * 18 / 5) = 42 / 51 - (1 * 0) = 11 - (1 * 4 / 5) = 1 / 51 - (1 * 1) = 0-1 - (1 * -6 / 5) = 1 / 50 - (1 * 0) = 00 - (1 * 6 / 5) = -6 / 5

Fila Z:-120 - (-17 / 2 * 18 / 5) = -447 / 50 - (-17 / 2 * 0) = 0-31 / 5 - (-17 / 2 * 4 / 5) = 3 / 5-17 / 2 - (-17 / 2 * 1) = 010 - (-17 / 2 * -6 / 5) = -1 / 50 - (-17 / 2 * 0) = 00 - (-17 / 2 * 6 / 5) = 51 / 5

La variable que sale de la base es P5 y la que entra es P4.

Tabla 3     -10 -19 / 5-3 / 2

0 0 0

Base Cb P0 P1 P2 P3 P4 P5 P6

P3-3 / 2

54 / 5 0 4 / 5 1 0 6 / 5 6 / 5

P4 0 6 0 0 0 1 1 0

P1 -10 36 / 5 1 1 / 5 0 0-1 / 5

-6 / 5

Z   -441 / 5 0 3 / 5 0 0 1 / 5 51 / 5

Fila pivote (Fila 2):6 / 1 = 60 / 1 = 00 / 1 = 00 / 1 = 01 / 1 = 11 / 1 = 10 / 1 = 0

Fila 1:18 / 5 - (-6 / 5 * 6) = 54 / 50 - (-6 / 5 * 0) = 04 / 5 - (-6 / 5 * 0) = 4 / 51 - (-6 / 5 * 0) = 1-6 / 5 - (-6 / 5 * 1) = 00 - (-6 / 5 * 1) = 6 / 56 / 5 - (-6 / 5 * 0) = 6 / 5

Fila 3:42 / 5 - (1 / 5 * 6) = 36 / 51 - (1 / 5 * 0) = 11 / 5 - (1 / 5 * 0) = 1 / 50 - (1 / 5 * 0) = 0

1 / 5 - (1 / 5 * 1) = 00 - (1 / 5 * 1) = -1 / 5-6 / 5 - (1 / 5 * 0) = -6 / 5

Fila Z:-447 / 5 - (-1 / 5 * 6) = -441 / 50 - (-1 / 5 * 0) = 03 / 5 - (-1 / 5 * 0) = 3 / 50 - (-1 / 5 * 0) = 0-1 / 5 - (-1 / 5 * 1) = 00 - (-1 / 5 * 1) = 1 / 551 / 5 - (-1 / 5 * 0) = 51 / 5

La solución óptima es Z = 441 / 5X1 = 36 / 5X2 = 0X3 = 54 / 5

La respuesta seria el contratista para su propuesta requerirá de 36/5 de espesor de concreto y 54/5 pulgadas de espesor de gravilla. Lo cual le permitirá minimizar sus costos los cuales serán igual a 441/5