Formulación Y Resolución Computacional

1 Introducción

La siguiente tarea trata sobre la formulación y resolución computacional de un modelo de optimización de Programación Entera con restricciones binarias que busca la minimización de costos de transporte de alumnos de enseñanza media trasladados hacia 3 colegios ubicados en nuestra comuna. El problema propuesto se analizará con herramientas de Microsoft Office Excel. Particularmente, el complemento Solver.

Este complemento nos permitirá resolver de manera eficiente la asignación de alumnos a los colegios considerando todas las restricciones propuestas.

El presente informe es la continuación del trabajo realizado anteriormente, en el que se buscaron los mínimos costos de transporte que planteaba nuestra función objetivo. Hemos dicho que es la continuación porque ahora, de manera adicional a lo planteado en primer informe, debemos restringir el envío de alumnos de una determinada zona a un único colegio.

Para el desarrollo plantearemos los siguientes pasos:

• Determinación de variables de decisión

• Determinación de la función objetivo

• Determinación de las restricciones asociadas al problema

• Ingresar los datos y ecuaciones a una planilla Excel de manera que puedan ser determinados los requerimientos a través de la herramienta Solver.

2 Descripción del problema

El Consejo de Educación de nuestra comuna ha adoptado una decisión respecto del cierre de uno de los establecimientos de Enseñanza Media, al final de este año escolar, y debe reasignar todos los estudiantes a los restantes tres colegios de la comuna. El municipio dispone de buses para todos aquellos alumnos que viajen más de 1 Km. para llegar su colegio, de modo que se busca una reasignación que minimice los costos totales del transporte de dichos alumnos. La siguiente tabla incluye los costos de transporte por alumno (en miles de pesos por alumno) desde cada una de las áreas en que se ha dividido a los alumnos hasta los 3 colegios disponibles. Un costo cero significa que un alumno en esa área no necesita bus para acceder a ese colegio y un guión que no resulta factible asignar en esa combinación. Completa la tabla las estimaciones de alumnos que habrá que reasignar en los tres últimos niveles de enseñanza media durante el próximo año.

área Nº de alumnos % 2o medio % 3o medio % 4o medio Costo a colegio 1 Costo a colegio 2 Costo a colegio 3

1 450 32 38 30 300 0 700

2 600 37 28 35 - 400 500

3 550 30 32 38 600 300 200

4 350 28 40 32 200 500 -

5 500 39 34 27 0 - 400

6 450 34 28 38 500 300 0

Capacidad 900 1100 1000

Tabla n°1:Costos de transporte por alumno desde cada una de las áreas hasta los 3 colegios.

Otra restricción impuesta en este problema es que cada uno de los niveles de enseñanza media represente entre el 30 y 35% de los alumnos reasignados en cada colegio.

Una nueva restricción es que todos los alumnos de un área deben ser asignados a un sólo colegio.

3 Modelo propuesto

3.1 Definición de Variables

Xij: número de alumnos de 2° medio que pertenecen al área i, y se trasladan al colegio j.

Yij: número de alumnos de 3° medio que pertenecen al área i, y se trasladan al colegio j.

Zij: número de alumnos de 4° medio que pertenecen al área i, y se trasladan al colegio j.

Mij: número de alumnos totales del área i, que se trasladan únicamente al colegio j.

Mij = Xij + Yij + Zij: número de alumnos de 4° medio que pertenecen al área i, y se trasladan al colegio j.

i: 1, 2, 3, 4, 5 y 6. j: 1, 2 y 3

3.2 Función Objetivo

Minimizar:

{300∙(M11) + 0∙(M12) + 700∙(M13+ 400∙(M22) + 500∙(M23) + 600∙(M31) + 300∙(M32) + 200∙(M33) + 200∙(M41) + 500∙(M42) + 0∙(M51) + 400∙(M53) + 500∙(M61) + 300∙(M62) + 0∙(M63)}

También podría ser:

Minimizar:

{300∙(X11+ Y11+Z11) + 0∙(X12+ Y12+Z12) + 700∙(X13+ Y13+Z13) + 400∙(X22+ Y22+Z22)

500∙(X23+ Y23+Z23) + 600∙(X31+ Y31+Z31) + 300∙(X32+ Y32+Z32) + 200∙(X33+ Y33+Z33) + 200∙(X41+ Y41+Z41) + 500∙(X42+ Y42+Z42) + 0∙(X51+ Y51+Z51) + 400∙(X53+ Y53+Z53) + 500∙(X61+ Y61+Z61) + 300∙(X62+ Y62+Z62) + 0∙(X63+ Y63+Z63)}

3.3 Restricciones

(1) Mi1 ≤ 950, i: 1, 3, 4, 5 y 6

(2) Mi2 ≤ 1.150, i: 1, 2, 3, 4 y 6

(3) Mi3 ≤ 1.050, i: 1, 2, 3, 5 y

(4) Mij = 1, si el alumno del área i, es asignado al colegio j.

(5) Mij = 0, si es un caso distinto al anterior.

(6) = 1

(7) = 1

(8) = 1

(9) = 1

(10) = 1

(11) = 1

(12) 0,3 ≤ ≤ 0,35 i: 1, 3, 4, 5 y 6

(13) 0,3 ≤ ≤ 0,35 i: 1, 3, 4, 5 y 6

(14) 0,3 ≤ ≤ 0,35 i: 1, 3, 4, 5 y 6

(15) 0,3 ≤ ≤ 0,35 i: 1, 2, 3, 4 y 6

(16) 0,3 ≤ ≤ 0,35 i: 1, 2, 3, 4 y 6

(17) 0,3 ≤ ≤ 0,35 i: 1, 2, 3, 4 y 6

(18) 0,3 ≤ ≤ 0,35 i: 1, 2, 3,

...