Curso

: ING4520 – Programación Matemática – Semestre 2011 - II

Profesor

: Juan Pérez Retamales

Auxiliares

: Francisco Vergara – Matías Mujica – Manuel Pavez

PAUTA PREGUNTA 3 - PRUEBA 2 Pregunta 3 (Total: 2.0 puntos) Las posiciones verticales suman 35 Las posiciones horizontales suman 15 pos.1

pos.2

pos.3

pos.4

pos.5

pos.6

pos.7

pos.8

pos.9

Ilustración 1 Pregunta (i): (i) (0.5 puntos) En cada una las nueve celdas de la Ilustración 1 puede poner números dígitos, cada número se puede poner sólo una vez. Se pide que plantee USANDO SÓLO VARIABLES BINARIAS la restricción que la suma horizontal sea 15, y que la suma vertical sea 35. Para lo anterior debe indicar claramente qué significan las variables binarias que definió, identificando el significado de los subíndices, y escribir explícitamente las dos restricciones que antes se le indicaron sobre suma horizontal y vertical. NOTA: No se le está preguntando que exprese alguno de los resultados, no tendrá puntaje el indicarlo. Respuesta (i): Primero definimos las variables y sus subíndices: 

(0.10 puntos)

x pd

0,1

: Es una variable binaria que indica 1 si la posición

p

tiene el dígito

d,

y es 0 en caso contrario.  

p indica la posición, y como se puede desprender de la Ilustración, son 9 1,...,9 . posiciones, luego p 0,...,9 ó (0.05 puntos) El subíndice d indica el número dígito al que se alude, por ende: d d 1,..., 9 (ambas formas son válidas). (0.05 puntos ) El subíndice

1

En segundo lugar se definen las restricciones para la suma horizontal y vertical. 

(0.15 puntos) Suma horizontal: 9

5

d

x pd

15

d 1 p 1



(0.15 puntos) Suma vertical: 9

9

d

x pd

35

d 1 p 5

Pregunta (ii): (ii) (0.3 puntos) Para la Ilustración 2. Indique si es verdadero o falso que la figura de la derecha representa gráficamente a la envoltura convexa del dominio graficado en el lado izquierdo (nota: en la figura del lado izquierdo, los puntos indican los elementos del dominio). Debe justificar su afirmación, en caso contrario no se le asignará puntaje.

x2

x2

3

3

2

2

1

1

1

2

3

x1

1

2

3

x1

Ilustración 2 Respuesta (ii): La afirmación es FALSA, lo anterior es simple y se explica por la NO CONVEXIDAD (0.3 puntos) del poliedro de la figura de la derecha.

2

x2 5 4,5

4 3,5

3 2 1

1

1,5

2

3

3,5

4

5

5,5

6

x1

Ilustración 3 Pregunta (iii): (iii) (0.2 puntos) Para la Ilustración 3: Escriba las restricciones que definen la formulación lineal continua. Es decir las desigualdades con variables continuas positivas que están dibujadas. No basta con marcarlo en el dibujo, debe expresarlo algebraicamente (en caso contrario no habrá puntaje). Respuesta (iii): Las restricciones son desigualdades que definen la formulación de la figura, éstas son 5, cada una tiene 0.04 puntos. 

(0.04 puntos)

x1

1.5



(0.04 puntos)

x1

5.5



(0.04 puntos)

x2

0



(0.04 puntos)

x2

4.5



(0.04 puntos)

x1

x2

3.5

Pregunta (iv): (iv) (0.3 puntos) Para la Ilustración 3: Escriba el conjunto todas las soluciones enteras factibles de dicho dominio. Puede escribirlo algebraicamente a partir de la respuesta de la parte anterior, con la correspondiente indicación matemática del conjunto, o hacerlo por extensión con cada uno de los elementos del conjunto. No basta con marcarlo en el dibujo, debe expresarlo algebraicamente (en caso contrario no habrá puntaje). Respuesta (iv): La respuesta tenía dos formas posibles:

3



(0.3 puntos) La primera es la descripción del conjunto, la cual queda:

X 

x

n

: x1

x1

1.5

x2

5.5

x1

4.5

x2

3.5

La segunda es el conjunto por extensión (cada uno de los 17 vectores tiene (0.3/17) puntos que es aprox. 0.018 puntos):

2, 4 ; 3, 4 ; 4, 4 ; 5, 4 ; 2, 3 ; 3, 3 ; 4, 3 ; 5, 3 ; X

2,2 ; 3,2 ; 4,2 ; 5,2 ; 3,1 ; 4,1 ; 5,1 ; 4, 0 ; 5, 0

Pregunta (v): (v) (0.3

x

puntos)

x1, x 2

desigualdad

Para 2

la

Ilustración

3:

Si

la

función

objetivo

z

fuera

min

2x1

x2

y

, y tuviera las restricciones de la figura (punto a) y tuviese que escoger entre la

D1 : x 1

x2

4 o D2 : x 1

5 para agregar (y mejorar) su formulación a modo de

poder encontrar una solución entera a partir de la relajación lineal: ¿cual utilizaría y por qué? Debe justificar, sino lo hace no habrá puntaje. Respuesta (v): En esta pregunta había que darse cuenta que:

x2

D2

5 4,5

4 3,5

3 2

D1

1

1 

1,5

2

3

3,5

4

5

5,5

x1

6

En un contexto de variables positivas, la función se hace mínima en la medida que esté más cerca del origen.



Adicionalmente había que observar que el gradiente de z recomendable reducir la variable

x1

que la variable

4

x2 .

z

2,1

lo cual hace más

x

x1, x 2

2,2



Por ende se podía deducir por inspección, que el óptimo es



En este contexto, una restricción (o desigualdad o corte) que me acerca más al origen es aquella que

.

esté más cera al punto aludido. 

Entonces la restricción

D1 : x 1

x2

4 permite acotar el espacio de soluciones continuas justo en

la dirección del gradiente, y en la zona en la cual está el óptimo. Por su parte, la restricción

D2 : x 1 

5 no hace lo mismo.

Otra forma de verlo era darse cuenta que al imponer D1 la solución del problema relajado cambia, mientras que al imponer D2 esto no sucede.

Pregunta (vi): (vi) (0.4 puntos) Para la Ilustración 3: Escriba explícitamente en forma algebraica todas las desigualdades que definen la envoltura convexa. Debe encontrarlas por inspección. Respuesta (vi): Tal como se conversó en clase la envoltura convexa viene dada por aquellas restricciones que tienen como vértices a los puntos extremos del dominio entero de la figura.

x2 5 4,5

4 3,5

3 2 1

1 

(0.08 puntos)

x1

2



(0.08 puntos)

x1

5



(0.08 puntos)

x2

0



(0.08 puntos)

x2

4



(0.08 puntos)

x1

x2

1,5

2

3

3,5

4

5

5,5

6

x1

4

Como pueden notar los vértices de este dominio son todos enteros, y por ende el problema se podría resolver sin poner explícitamente que las variables son enteras. ES DECIR, CON ESTAS RESTRICCIONES, LA SOLUCIÓN DE LA RELAJACIÓN LINEAL SERÍA IGUAL A LA DEL PROBLEMA ENTERO ORIGINAL.

5