http://optlab-server.sce.carleton.ca/POAnimations2007/BranchAndBound.html
A company is assembling a team to carry out a series of operations. There are four members of the team: A, B, C and D, and four operations to be carried out. Each team member can carry out exactly one operation. All four operations must be carried out successfully for the overall project to succeed, however the probability of a particular team member succeeding in a particular operation varies, as shown in the table below. For example, if the team members were assigned to operations in the order ABCD, then the overall probability of successful completion of the project is (0.9)(0.6)(0.85)(0.7) = 0.3213. If there is any possible way that the team can be arranged such that the overall probability of success exceeds 45%, then the manager will approve the project. Will the manager approve the project? If yes, what is the arrangement of the team that gives the highest probability of success?
a <- c(0.9, 0.8, 0.9, 0.85)
b <- c(0.7, 0.6, 0.8, 0.7)
c <- c(0.85, 0.7, 0.85, 0.8)
d <- c(0.75, 0.7, 0.75, 0.7)
dat <- rbind(a,b,c,d)
colnames(dat) <- c(1,2,3,4)
dat## 1 2 3 4
## a 0.90 0.8 0.90 0.85
## b 0.70 0.6 0.80 0.70
## c 0.85 0.7 0.85 0.80
## d 0.75 0.7 0.75 0.70over_45_pct <- c()
row_names <- rownames(dat)
permutations <- combinat::permn(row_names)
for(p in permutations){
success_rate <- dat[p[1],1] * dat[p[2],2] * dat[p[3],3] * dat[p[4],4]
summary_of_success <- cat(p," => ", success_rate, "= (",dat[p[1],1],"*",dat[p[2],2],"*",dat[p[3],3],"*",dat[p[4],4],")")
print(summary_of_success)
if(success_rate >= 0.45){
over_45_pct <- c(over_45_pct, summary_of_success)
}
} ## a b c d => 0.3213 = ( 0.9 * 0.6 * 0.85 * 0.7 )NULL
## a b d c => 0.324 = ( 0.9 * 0.6 * 0.75 * 0.8 )NULL
## a d b c => 0.4032 = ( 0.9 * 0.7 * 0.8 * 0.8 )NULL
## d a b c => 0.384 = ( 0.75 * 0.8 * 0.8 * 0.8 )NULL
## d a c b => 0.357 = ( 0.75 * 0.8 * 0.85 * 0.7 )NULL
## a d c b => 0.37485 = ( 0.9 * 0.7 * 0.85 * 0.7 )NULL
## a c d b => 0.33075 = ( 0.9 * 0.7 * 0.75 * 0.7 )NULL
## a c b d => 0.3528 = ( 0.9 * 0.7 * 0.8 * 0.7 )NULL
## c a b d => 0.3808 = ( 0.85 * 0.8 * 0.8 * 0.7 )NULL
## c a d b => 0.357 = ( 0.85 * 0.8 * 0.75 * 0.7 )NULL
## c d a b => 0.37485 = ( 0.85 * 0.7 * 0.9 * 0.7 )NULL
## d c a b => 0.33075 = ( 0.75 * 0.7 * 0.9 * 0.7 )NULL
## d c b a => 0.357 = ( 0.75 * 0.7 * 0.8 * 0.85 )NULL
## c d b a => 0.4046 = ( 0.85 * 0.7 * 0.8 * 0.85 )NULL
## c b d a => 0.325125 = ( 0.85 * 0.6 * 0.75 * 0.85 )NULL
## c b a d => 0.3213 = ( 0.85 * 0.6 * 0.9 * 0.7 )NULL
## b c a d => 0.3087 = ( 0.7 * 0.7 * 0.9 * 0.7 )NULL
## b c d a => 0.312375 = ( 0.7 * 0.7 * 0.75 * 0.85 )NULL
## b d c a => 0.354025 = ( 0.7 * 0.7 * 0.85 * 0.85 )NULL
## d b c a => 0.325125 = ( 0.75 * 0.6 * 0.85 * 0.85 )NULL
## d b a c => 0.324 = ( 0.75 * 0.6 * 0.9 * 0.8 )NULL
## b d a c => 0.3528 = ( 0.7 * 0.7 * 0.9 * 0.8 )NULL
## b a d c => 0.336 = ( 0.7 * 0.8 * 0.75 * 0.8 )NULL
## b a c d => 0.3332 = ( 0.7 * 0.8 * 0.85 * 0.7 )NULLprint("over_45_pct:")## [1] "over_45_pct:"print(over_45_pct)## NULLThere are no additional nodes left to expand. We have found the maximum probability solution, CDBA.