Problem

The Bavarian Motor Company (BMC) manufactures expensive luxury cars in Hamburg, Germany, and exports cars to sell in the United States. The exported cars are shipped from Hamburg to ports in Newark, New Jersey and Jacksonville, Florida. From these ports, the cars are transported by rail or truck to distributors located in Boston, Massachusetts; Columbus, Ohio; Atlanta, Georgia; Richmond, Virginia; and Mobile, Alabama. The below figure shows the possible shipping routes available to the company along with the transportation cost for shipping each car along the indicated path. Currently, 200 cars are available at the port in Newark and 300 are available in Jacksonville. The numbers of cars needed by the distributors in Boston, Columbus, Atlanta, Richmond, and Mobile are 100, 60, 170, 80, and 70, respectively. BMC wants to determine the least costly way of transporting cars from the ports in Newark and Jacksonville to the cities where they are needed. Formulate the LP and solve it using software of your choice. Conduct sensitivity analysis and interpret. Provide the duals and demonstrate strong duality.

Network Diagram

Decision Variables

How much from Newark to Boston, Newark to Richmond, Boston to Columbus, Columbus to Atlanta, Atlanta to Columbus, Atlanta to Richmond, Atlanta to Mobile, Mobile to Atlanta, Jacksonville to Richmond, Jacksonville to Atlanta, Jacksonville to Mobile

We literally just enumerate the possible paths. Since we are importing to Newark and Jacksonville, we can only ship the amount provided (\(\le\) constraints). Everywhere else, we seek to achieve at least the demand (\(\ge\) constraints). Avoid equality any time you can when seeking solutions to LPs.

Set Up Objective Function

dir = "min"   #Build direction
cost=c(30, 40, 50, 35, 40, 30, 35, 25, 50, 45, 50)  #Build objective

Build Constraint Matrix and RHS

A=matrix(
  c(1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    1, 0,-1, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 1,-1, 1, 0, 0, 0, 0, 0, 0,
    0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0,
    0, 0, 0, 1,-1,-1,-1, 1, 0, 1, 0,
    0, 0, 0, 0, 0, 0, 1,-1, 0, 0, 1,
    0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1), byrow=TRUE, nrow=7)
rownames(A)=c('Nwk', 'Bstn', 'Clmbus', 'Rchmnd', 'Atl','Mbl', 'Jck')
colnames(A)=c('N_B', 'N_R', 'B_C', 'C_A', 'A_C', 
              'A_R', 'A_M', 'M_A', 'J_R', 'J_A', 'J_M')
const.dir=c('<=',rep('>=',5),'<=')  #Constraint Direction
b=c(200,100,60,80,170,70,300)  #Right-Hand Side Values

Set up Problem

x=lp(dir,cost,A,const.dir,b,transpose.constraints="T",compute.sen=1)

Get Solution from Primal

noquote(paste0('Objective Value=$',x$objval))
## [1] Objective Value=$22350
answer=rbind(round(x$solution,2),
             round(cost,2),
             round(x$sens.coef.from,2),
             round(x$sens.coef.to,2))
answer[abs(answer)>1000]='INF'
answer=noquote(answer)
colnames(answer)=colnames(A)
rownames(answer)=c('Solution','Initial Cost', 'Reduced Cost From', 'Reduced Cost To' )
myprint(answer)
N_B N_R B_C C_A A_C A_R A_M M_A J_R J_A J_M
Solution 120 80 20 0 40 0 0 0 0 210 70
Initial Cost 30 40 50 35 40 30 35 25 50 45 50
Reduced Cost From 25 -5 45 -40 35 0 5 -5 45 40 20
Reduced Cost To 35 45 55 INF 45 INF INF INF INF 50 80

Get Solution from Dual

#Strong Duality Theorem:  $c^tx=b^ty$.
noquote(paste0('Objective Value=$',sum(t(b)*x$duals[1:7])))
## [1] Objective Value=$22350
duals=noquote(rbind(round(x$duals,2),
                    round(x$duals.from,2), 
                    round(x$duals.to,2)))
duals[abs(duals)>1000]='INF'
duals=noquote(duals)
colnames(duals)=c(rownames(A), colnames(A))
rownames(duals)=c('Shadow Prices', 'From', 'To')
myprint(duals)
Nwk Bstn Clmbus Rchmnd Atl Mbl Jck N_B N_R B_C C_A A_C A_R A_M M_A J_R J_A J_M
Shadow Prices -5 35 85 45 45 50 0 0 0 0 75 0 30 30 30 5 0 0
From 180 60 20 40 -40 0 INF INF INF INF -40 INF -20 -210 -70 -20 INF INF
To 240 120 80 100 190 90 INF INF INF INF INF INF 40 70 210 40 INF INF