Problema do casamento e da casa própria
Vanessa Manhães Almeida
05/06/2022
Este trabalho trata-se de uma atividade proposta na disciplia de Teoria da Decição II, ministrada
pela professora Luciane Alcoforado, na Pós-Civil - UFF.O problema
Uma agência de casamento procura promover a melhor união possível entre os casais de seu banco de dados. Para a solução desse problema existe uma série de critérios a adotar.O índice de compatibilidade final, que é calculado levando em conta vários condicionantes, é o fator preponderante.
O sistema de dados da agência pode facilmente obter a adequação feminina fij, ou seja, a variável que diz o quanto a moça i é adequada ao rapaz j, e a masculina, hij, que expressa a situação inversa. Quando os valores de f e h estão entre determinados limites, o casal pode ser formado, sendo formação cada vez mais adequada, na medida do crescimento da soma desses fatores.
Além desse indicador, existe uma enorme condicionante econômica a ser levada em conta: a casa própria. As experiências dessa agência dizem queumcasal só é admissível quando ambos possuem interesse pela mesma casa, ela puder ser disponibilizada e seu preço estiver dentro da poss do casal. Existem W = {1, … , w} casas no banco de dados.
Formular o problema de maximizar o número de uniões estáveis dentro do banco de dados.
Dados do problema
No atual banco de dados, estão cadastrados, Ana, Bia, Cida, Dan, Edu e Fábio.
Ana tem 25 anos, é servidora pública e tem remuneração mensal de 2600 reais.
Bia tem 24 anos, é decoradora e tem remunarção mensal de 1800 reais.
Cida tem 22 anos, é maquiadora e tem remuneração mensal média de 1500 reais.
Dan tem 27 anos, é vendedor e tem remuneração mensal de 1900 reais.
Edu tem 25 anos, é bancário e tem remuneração mensar de 2200 reais.
Fábio tem 26 anos, é técnico de enfermagem e tem remuneração mensal de 1700 reais.
Além disso, se encontram disponíveis as casa X, Y e Z.
A casa X está avaliada em 400 mil reais com financiamento aprovado em parcelas no valor de 2600 reais.
A casa Y está avaliada em 300 mil reais com financiamento aprovado em parcelas no valor de 2090 reais.
A casa Z está avaliada em 240 mil reais com financiamento aprovado em parcelas no valor de 1500 reais.
Representação das possíveis uniões:
Variáveis do problema
\(x147\) = Casamento de Ana e Dan na casa X
\(x148\) = Casamento de Ana e Dan na casa Y
\(x149\) = Casamento de Ana e Dan na casa Z
\(x157\) = Casamento de Ana e Edu na casa X
\(x158\) = Casamento de Ana e Edu na casa Y
\(x159\) = Casamento de Ana e Edu na casa Z
\(x167\) = Casamento de Ana e Fábio na casa X
\(x168\) = Casamento de Ana e Fábio na casa Y
\(x169\) = Casamento de Ana e Fábio na casa Z
\(x247\) = Casamento de Bia e Dan na casa X
\(x248\) = Casamento de Bia e Dan na casa Y
\(x249\) = Casamento de Bia e Dan na casa Z
\(x257\) = Casamento de Bia e Edu na casa X
\(x258\) = Casamento de Bia e Edu na casa Y
\(x259\) = Casamento de Bia e Edu na casa Z
\(x267\) = Casamento de Bia e Fábio na casa X
\(x268\) = Casamento de Bia e Fábio na casa Y
\(x269\) = Casamento de Bia e Fábio na casa Z
\(x347\) = Casamento de Cida e Dan na casa X
\(x348\) = Casamento de Cida e Dan na casa Y
\(x349\) = Casamento de Cida e Dan na casa Z
\(x357\) = Casamento de Cida e Edu na casa X
\(x358\) = Casamento de Cida e Edu na casa Y
\(x359\) = Casamento de Cida e Edu na casa Z
\(x367\) = Casamento de Cida e Fábio na casa X
\(x368\) = Casamento de Cida e Fábio na casa Y
\(x369\) = Casamento de Cida e Fábio na casa Z
Restrições do problema
- Restrição associada aos limites de compatibilidade
R1 \(9x14k + 7x24k + 8x34k \geq 7\)
R2 \(9x15k + 8x25k + 7x35k \geq 7\)
R3 \(7x16k + 7x26k + 8x36k \geq 7\)
R4 \(7x14k + 10x15k + 6x16k \geq 6\)
R5 \(9x24k + 8x25k + 9x26k \geq 6\)
R6 \(8x34k + 9x35k + 6x36k \geq 6\)
para \(k = {7, 8, 9}\)
- Restrições associadas à monogamia:
R7 \(x14k + x15k +x16k \leq 1\)
R8 \(x24k + x25k +x26k \leq 1\)
R9 \(x34k + x35k +x36k \leq 1\)
R10 \(x14k + x24k +x34k \leq 1\)
R11 \(x15k + x25k +x35k \leq 1\)
R12 \(x16k + x26k + x36k \leq 1\)
para \(k = {7, 8, 9}\)
- Resrições associadas à restrição da capacidade financeira:
R13 \(45x147+48x157 + 43x167 + 37x247 + 40x257 + 35x267 + 34x347 + 37x357 +32x367\geq 26\)
R14 \(45x148+48x158 + 43x168 + 37x248 + 40x258 + 35x268 + 34x348 + 37x358 +32x368 \geq 20.9\)
R15 \(45x149+48x159 + 43x169 + 37x249 + 40x259 + 35x269 + 34x349 + 37x359 +32x369\geq 15\)
- Restrições associadas à disponibilidade da casa:
R16 \(x147+x157+x167+x247+x257+x267+x347+x357+x367\leq1\)
R17\(x148+x158+x168+x248+x258+x268+x348+x358+x368\leq1\)
R18\(x149+x159+x169+x249+x259+x269+x349+x359+x369\leq1\)
Função Objetivo
\(max z = x147 + x148 + x149 + x157 + x158 + x159 + x167 + x168 + x169 + x247 + x248 + x249 + x257 + x258 + x259 + x267 + x268 + x269 + x347 + x248 + 249 + x347 + x348 + x349 + x357 + x358 + x359 + x367 + x368 + x369\)
Solução do problema
Todas as variávei e restrições do problema foram tabeladas em uma planilha para melhor organização do programa.
######## Carregar pacotes lpSolve#################
suppressMessages(require(lpSolve))
######## Dados do problema #######################
library(readxl)
Dados <- read_excel("restcasa.xlsx")
kableExtra::kable(Dados)| restr | x147 | x148 | x149 | x157 | x158 | X159 | X167 | X168 | X169 | X247 | X248 | X249 | X257 | X258 | X259 | x267 | x268 | x269 | x347 | x348 | x349 | x357 | x358 | x359 | x367 | x368 | x369 | direcoes | limite |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| R1 | 9 | 9 | 9 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 7 | 7 | 0 | 0 | 0 | 0 | 0 | 0 | 8 | 8 | 8 | 0 | 0 | 0 | 0 | 0 | 0 | >= | 7.0 |
| R2 | 0 | 0 | 0 | 9 | 9 | 9 | 0 | 0 | 0 | 0 | 0 | 0 | 8 | 8 | 8 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 7 | 7 | 0 | 0 | 0 | >= | 7.0 |
| R3 | 0 | 0 | 0 | 0 | 0 | 0 | 7 | 7 | 7 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 9 | 9 | 0 | 0 | 0 | 0 | 0 | 0 | 8 | 8 | 8 | >= | 7.0 |
| R4 | 7 | 7 | 7 | 10 | 10 | 10 | 6 | 6 | 6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | >= | 6.0 |
| R5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 9 | 9 | 8 | 8 | 8 | 9 | 9 | 9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | >= | 6.0 |
| R6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 8 | 8 | 8 | 9 | 9 | 9 | 6 | 6 | 6 | >= | 6.0 |
| R7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | <= | 1.0 |
| R8 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | <= | 1.0 |
| R9 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | <= | 1.0 |
| R10 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | <= | 1.0 |
| R11 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | <= | 1.0 |
| R12 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | <= | 1.0 |
| R13 | 45 | 0 | 0 | 48 | 0 | 0 | 43 | 0 | 0 | 37 | 0 | 0 | 40 | 0 | 0 | 35 | 0 | 0 | 34 | 0 | 0 | 37 | 0 | 0 | 32 | 0 | 0 | >= | 26.0 |
| R14 | 0 | 45 | 0 | 0 | 48 | 0 | 0 | 43 | 0 | 0 | 37 | 0 | 0 | 40 | 0 | 0 | 35 | 0 | 0 | 34 | 0 | 0 | 37 | 0 | 0 | 32 | 0 | >= | 20.9 |
| R15 | 0 | 0 | 45 | 0 | 0 | 48 | 0 | 0 | 43 | 0 | 0 | 37 | 0 | 0 | 40 | 0 | 0 | 35 | 0 | 0 | 34 | 0 | 0 | 37 | 0 | 0 | 32 | >= | 15.0 |
| R16 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | <= | 1.0 |
| R17 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | <= | 1.0 |
| R18 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | <= | 1.0 |
# coeficientes na função objetivo
func.objetivo = rep(1, 27)
# coeficientes nas restrições.
coeficientes.restricoes = as.matrix(Dados[2:28])
# sinal das restrições. Deve obedecer a ordem da matriz de coeficientes
direcao.restricoes = Dados$direcoes
# limite das restrições. Deve obedecer a ordem da matriz de coeficientes
limites.restricoes = Dados$limite
######## Solução ###############
solucao.problema <- lpSolve::lp(direction = "min",
objective.in = func.objetivo,
const.mat = coeficientes.restricoes,
const.dir = direcao.restricoes,
const.rhs = limites.restricoes,
all.bin = T)
######### Resultado #############
# valor da função objetivo na solução
solucao.problema$objval[1] 3# Valores para as variáveis de escolha que geram máximo ou mínimo dependendo do problema
solucao.problema$solution [1] 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1Após rodar o algoritmo, obtemos três resultados possíveis:
Casamento de Ana e Dan morando na casa X;
Casamento de Bia e Edu morando na casa Y;
Casamento de Cida e Fábio morando na casa Z.
######## Solução ###############
solucao.problema <- lpSolve::lp(direction = "min",
objective.in = func.objetivo,
const.mat = coeficientes.restricoes,
const.dir = direcao.restricoes,
const.rhs = limites.restricoes,
all.int = T)
######### Resultado #############
# Valores para as variáveis de escolha que geram máximo ou mínimo dependendo do problema
solucao.problema$solution [1] 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0Outra possibilidade também pode ser esses mesmos casamentos, porém para outras casas:
Casamento de Ana e Dan morando na casa Z;
Casamento de Bia e Edu morando na casa X;
Casamento de Cida e Fábio morando na casa Y.
Analizando a situação financeira dos casais, a agência acredita que a primeira possibilidade é a mais favorável.
Referência
Goldbarg, Marco Cesar. Otimização combinatória e programação linear: modelos e algoritmos / Marco Cesar Goldbarg, Henrique Pacca L. Luna. -2.ed. – Rio de Janeiro: Elsevier, 2005