Problema de redondeos en una tabla, Salazar González (2000)

Un centro de Investigaciones Sociológicas dispone de la siguiente tabla y desea publicarla tras redondear cada valor numérico fraccionario a su entero por exceso o por defecto. Se quiere minimizar la suma de las diferencias entre los valores redondeados y los valores originales.

Planteamiento matemático del problema

Asociado a cada celda (interior o marginal) de la tabla anterior consideremos la siguiente variable \(\small{x_{ij}}\) que toma los siguientes valores

• \(1\) si el redondeo en la celda \(\small(i,j)\) es por exceso.
• \(0\) si el redondeo en la celda \(\small(i,j)\) es por defecto.

Nótese que la introducción de las variable \(\small{x_{ij}}\) es equivalente a introducir una condición lógica ,si no se cumple una opción se cumple otra.

Por tanto nuestro objetivo sera resolver el siguiente problema de optimización :

\(\text{Min}\)
\[0.66666*(1-x_{11})+0.333333*x_{11}+0.666666*(1-x_{12})+0.333333*x_{12}+0.333333*(1-x_{13})+0.666666*(x_{13}+0.75*(1-x_{22})+0.25*x_{22}+0.75*(1-x_{23})+0.25*x_{23}+0.25*(1-x_{31})+0.75*x_{31}+0.25*(1-x_{32})+0.75*x_{32}+0.5*(1-x_{33})+0.5*x_{33}+0.916666*(1-x_{41})+0.083334*x_{41}+0.666666*(1-x_{42})+0.333333*x_{42}+0.583332*(1-x_{43})+0.416668*x_{43}\] \(\text{ST}\)

Fila 1 \[ (1+x_{11})+(2+x_{12})=(4+x_{13})\]
Fila 2 \[ 2+(4+x_{22})=(6+x_{23}) \]
Fila 3 \[ (1+x_{31})+(4+x_{32})=(5+x_{33})\]
Fila 4 \[ (4+x_{41i})+(11+x_{42})= (16+x_{43})\]
Columna1 \[ (1+x_{11})+2+(1+x_{31})= (4+x_{41})\]
Columna2 \[ (2+x_{12})+(4+x_{22})+(4+x_{32})= (11+x_{42})\]

Columna3 \[ (4+x_{13})+(6+x_{23})+(5+x_{33})=(16+x_{43})\]

Codigo R I

library("lpSolve")
f.obj=c(-0.333333,-0.333333,0.333333,0,-0.5,-0.5,0.5,0.5,0,-0.833332,-0.333333,-0.166664)
r1= c(1,2,-1,0,0,0,0,0,0,0,0,0) 
r2= c(0,0,0,0,1,-1,0,0,0,0,0,0)
r3= c(0,0,0,0,0,0,1,1,-1,0,0,0)
r4= c(0,0,0,0,0,0,0,0,0,1,1,-1)
c1= c(1,0,0,0,0,0,-1,0,0,0,0,0)
c2= c(0,1,0,0,1,0,0,-1,0,0,0,0)
c3= c(0,0,1,0,0,1,0,0,-1,0,0,0)
f.con= as.matrix(rbind(r1,r2,r3,r4,c1,c2,c3))
f.dir= rep("=",7)
f.rhs= c(1,0,0,1,1,1,1)
res=lp("min", f.obj, f.con, f.dir, f.rhs,binary.vec=1:12)
solucion=res$solution
valorobjetivo=res$objval

Código R II

Veamos una versión de código más robusta.

library("lpSolveAPI")
f.obj=c(-0.333333,-0.333333,0.333333,0,-0.5,-0.5,0.5,0.5,0,-0.833332,-0.333333,-0.166664)
r1= c(1,2,-1,0,0,0,0,0,0,0,0,0) 
r2= c(0,0,0,0,1,-1,0,0,0,0,0,0)
r3= c(0,0,0,0,0,0,1,1,-1,0,0,0)
r4= c(0,0,0,0,0,0,0,0,0,1,1,-1)
c1= c(1,0,0,0,0,0,-1,0,0,0,0,0)
c2= c(0,1,0,0,1,0,0,-1,0,0,0,0)
c3= c(0,0,1,0,0,1,0,0,-1,0,0,0)
f.dir= rep("=",7)
f.rhs= c(1,0,0,1,1,1,1)
### Ahora indicamos que nuestro problema tiene 2 variables y 4 restricciones:



D<-make.lp(7,12)

### Introducimos por filas los coeficientes de las restricciones

set.row(D,1,r1)
set.row(D,2,r2)
set.row(D,3,r3)
set.row(D,4,r4)
set.row(D,5,c1)
set.row(D,6,c2)
set.row(D,7,c3)
### Indicamos los tipos de desigualdad

set.constr.type(D,rep("=",7))
### Introducimos los coeficientes de las restricciones del lado derecho
set.rhs(D,f.rhs)
### Introducimos los coeficientes de la función objetivo
set.objfn(D,f.obj)
### Indicamos que la solución sea binaria
set.type(D,1:12,type="binary")
### Indicamos que queremos minimizar

optimizar=lp.control(D,sense="min")
### Con el siguiente comando podemos saber si existe soluci?n, en caso afirmativo toma el valor 0:
existsol=solve(D)
### Y finalmente obtenemos las soluciones
n= length(get.primal.solution(D))
i= n-12
sol= get.primal.solution(D)[i:n] 

Soluciones

El valor de la función objetivo en el mínimo es:

## [1] -2.666662

El valor de la solución es:

##  [1] 1 0 0 0 1 1 0 0 0 1 1 1

Asignación de Barcos

Se deben utilizar cuatro barcos cargueros para transportar carbón del puerto de El Musel (Gijón) a otros cuatro puertos (A Coruña, Ferrol, Oporto y Southampton). Se puede usar cualquier barco para hacer cualquiera de los cuatro viajes. Sin embargo, dadas algunas diferencias entre los barcos y las cargas, el coste total de carga, transporte y descarga de carbón de las distintas combinaciones de barcos y puertos varía de manera considerable. Estos costes (en euros) se muestran en la siguiente tabla:

Formulación matemática

A cada barco y destino le asociamos una variable \(x_{ij}\) donde \(i\in{\{1,2,3,4\} }\) y \(j\in{\{1,2,3,4\}}\), existiendo la siguiente correspondencía biunívoca:

• i=1, Barco 1
• i=2, Barco 2
• i=3, Barco 3
• i=4, Barco 4
• j=1, Coruña
• j=2, Ferrol
• j=3, Southampton
• j=4, Oporto

La variable \(x_{ij}\) además tomara unicamente los siguientes valores:

• \(1\) Si el barco \(i\) va al destino \(j\)
• \(0\) en caso contrario

Como cada barco solo puede ir a un único destino ,entonces imponemos la siguiente restrición:

\(\sum_{j=1}^{4} x_{ij}=1\) con \(i\in\{1,2,3,4\}\)

Como a cada destino solo puede llegar un barco , esto nos conduce a imponer:

\(\sum_{i=1}^{4} x_{ij}=1\) con \(j\in\{1,2,3,4 \}\)

En definita, nuestro problema de optimización lo podemos escribir como:

\(\text{Min}\)

\[500*x_{11}+400*x_{12}+600*x_{13}+700*x_{14}+600*x_{21}+600*x_{22}+700*x_{23}+500*x_{24}+700*x_{31}+500*x_{32}+700*x_{33}+600*x_{34}+500*x_{41}+400*x_{42}+600*x_{43}+600*x_{44}\]

\(\text{ST}\)

\(\sum_{j=1}^{4} x_{ij}=1\) con \(i\in\{1,2,3,4\}\)

\(\sum_{i=1}^{4} x_{ij}=1\) con \(j\in\{1,2,3,4\}\)

Codigo R

library("lpSolve")
f.obj= c(500,400,600,700,600,600,700,500,700,500,700,600,500,400,600,600)
r1= c(1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0)
r2= c(0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0)
r3= c(0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0)
r4= c(0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1)
r5= c(1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0)
r6= c(0,1,0,0,0,1,0,0,0,1,0,0,0,1,0,0)
r7= c(0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,0)
r8= c(0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1)
f.con= as.matrix(rbind(r1,r2,r3,r4,r5,r6,r7,r8))
f.dir= rep("=",8)
f.rhs= c(1,1,1,1,1,1,1,1)
res=lp("min", f.obj, f.con, f.dir, f.rhs,binary.vec=1:8)

Soluciónes

El valor de la función objetivo es:

## [1] 2100

La solución es:

##  [1] 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0

Es decir el barco 1 va a Southampton, el barco 2 a Oporto, el barco 3 a Ferrol, y el barco 4 a A Coruña.

Nótese que el siguiente problema podría resolverse de forma sencilla utilizando fuerza bruta con las 24 combinaciones posibles.