Online Course Material
We present as an LP the network flow formulation of the Remodelling Chemical Laboratory problem from R.B. Harris, Precedence and Arrow Networking Techniques for Construction. The first formulation below computes longest paths from the start to each node, both Si and Fi where Si is th estart of activity i and Fi is the finish of activity i. A quick change results in a second formulation that computes the logest paths from each node to the finish.
max 3s1f1+4s2f2+s3f3+s4f4+5s5f5+2s6f6+3s7f7+s8f8+s9f9
+5s10f10+s11f11+6s12f12+3s13f13+5s14f14+10s15f15+10s16f16
+10s17f17+20s18f18+2s19f19
st
start)starts1+starts2+starts14+starts15+starts16+starts17+starts18
-s1start-f1start-s2start-f2start-s3start-f3start-s4start-f4start-s5start-f5start-s6start-f6start-s7start-f7start
-s8start-f8start-s9start-f9start-s10start-f10start-s11start-f11start-s12start-f12start-s13start-f13start
-s14start-f14start-s15start-f15start-s16start-f16start-s17start-f17start-s18start-f18start-s19start-f19start=0
s1)starts1-s1f1-s1start=0
s2)f1s2+f5s2+f7s2-s2f2-s2start=0
s3)f1s3+f5s3-s3f3-s3start=0
s4)f3s4+f12s4+f13s4+f14s4-s4f4-s4start=0
s5)f1s5-s5f5-s5start=0
s6)f2s6+f3s6+f5s6+f9s6+f10s6+f11s6+f19s6-s6f6-s6start=0
s7)f1s7-s7f7-s7start=0
s8)f2s8+f3s8+f16s8-s8f8-s8start=0
s9)f2s9+f3s9+f8s9+f15s9-s9f9-s9start=0
s10)f2s10+f3s10+f7s10+f15s10-s10f10-s10start=0
s11)f2s11+f3s11+f5s11+f9s11+f17s11-s11f11-s11start=0
s12)f6s12+f8s12+f9s12+f10s12+f11s12+f18s12-s12f12-s12start=0
s13)f2s13+f3s13+f6s13+f8s13+f9s13+f10s13+f18s13-s13f13-s13start=0
s14)starts14-s14f14-s14start=0
s15)starts15-s15f15-s15start=0
s16)starts16-s16f16-s16start=0
s17)starts17-s17f17-s17start=0
s18)starts18-s18f18-s18start=0
s19)f2s19+f3s19+f9s19+f15s19-s19f19-s19start=0
f1)s1f1-f1s2-f1s3-f1s5-f1s7-f1start=0
f2)s2f2-f2s6-f2s8-f2s9-f2s10-f2s11-f2s13-f2s19-f2start=0
f3)s3f3-f3s4-f3s6-f3s8-f3s9-f3s10-f3s11-f3s13-f3s19-f3start=0
f4)s4f4-f4start=0
f5)s5f5-f5s2-f5s3-f5s6-f5s11-f5start=0
f6)s6f6-f6s12-f6s13-f6start=0
f7)s7f7-f7s2-f7s10-f7start=0
f8)s8f8-f8s9-f8s12-f8s13-f8start=0
f9)s9f9-f9s6-f9s11-f9s12-f9s13-f9s19-f9start=0
f10)s10f10-f10s6-f10s12-f10s13-f10start=0
f11)s11f11-f11s6-f11s12-f11start=0
f12)s12f12-f12s4-f12start=0
f13)s13f13-f13s4-f13start=0
f14)s14f14-f14s4-f14start=0
f15)s15f15-f15s9-f15start=0
f16)s16f16-f16s8-f16start=0
f17)s17f17-f17s11-f17start=0
f18)s18f18-f18s12-f18s13-f18start=0
f19)s19f19-f19s6-f19start=0
s1val)s1start<1
f1val)f1start<1
s2val)s2start<1
f2val)f2start<1
s3val)s3start<1
f3val)f3start<1
s4val)s4start<1
f4val)f4start<1
s5val)s5start<1
f5val)f5start<1
s6val)s6start<1
f6val)f6start<1
s7val)s7start<1
f7val)f7start<1
s8val)s8start<1
f8val)f8start<1
s9val)s9start<1
f9val)f9start<1
s10val)s10start<1
f10val)f10start<1
s11val)s11start<1
f11val)f11start<1
s12val)s12start<1
f12val)f12start<1
s13val)s13start<1
f13val)f13start<1
s14val)s14start<1
f14val)f14start<1
s15val)s15start<1
f15val)f15start<1
s16val)s16start<1
f16val)f16start<1
s17val)s17start<1
f17val)f17start<1
s18val)s18start<1
f18val)f18start<1
s19val)s19start<1
f19val)f19start<1
end
The optimal flow determined is a sum of longest start to si or fi nodes (so 38 such paths)
The following formulation computes the longest paths from each node to the finish which in this case is f4. I've used fin to represent finish not because I wanted to use French names but because LINDO only likes 8 character variable names.
max 3s1f1+4s2f2+s3f3+s4f4+5s5f5+2s6f6+3s7f7+s8f8+s9f9
+5s10f10+s11f11+6s12f12+3s13f13+5s14f14+10s15f15+10s16f16
+10s17f17+20s18f18+2s19f19
st
fin)fins1+finf1+fins2+finf2+fins3+finf3+fins4+finf4+fins5+finf5+fins6+finf6
+fins7+finf7+fins8+finf8+fins9+finf9+fins10+finf10+fins11+finf11+fins12+finf12
+fins13+finf13+fins14+finf14+fins15+finf15+fins16+finf16+fins17+finf17
+fins18+finf18+fins19+finf19-f4fin=0
s1)fins1-s1f1=0
s2)fins2+f1s2+f5s2+f7s2-s2f2=0
s3)fins3+f1s3+f5s3-s3f3=0
s4)fins4+f3s4+f12s4+f13s4+f14s4-s4f4=0
s5)fins5+f1s5-s5f5=0
s6)fins6+f2s6+f3s6+f5s6+f9s6+f10s6+f11s6+f19s6-s6f6=0
s7)fins7+f1s7-s7f7=0
s8)fins8+f2s8+f3s8+f16s8-s8f8=0
s9)fins9+f2s9+f3s9+f8s9+f15s9-s9f9=0
s10)fins10+f2s10+f3s10+f7s10+f15s10-s10f10=0
s11)fins11+f2s11+f3s11+f5s11+f9s11+f17s11-s11f11=0
s12)fins12+f6s12+f8s12+f9s12+f10s12+f11s12+f18s12-s12f12=0
s13)fins13+f2s13+f3s13+f6s13+f8s13+f9s13+f10s13+f18s13-s13f13=0
s14)fins14+starts14-s14f14=0
s15)fins15+starts15-s15f15=0
s16)fins16+starts16-s16f16=0
s17)fins17+starts17-s17f17=0
s18)fins18+starts18-s18f18=0
s19)fins19+f2s19+f3s19+f9s19+f15s19-s19f19=0
f1)finf1+s1f1-f1s2-f1s3-f1s5-f1s7=0
f2)finf2+s2f2-f2s6-f2s8-f2s9-f2s10-f2s11-f2s13-f2s19=0
f3)finf3+s3f3-f3s4-f3s6-f3s8-f3s9-f3s10-f3s11-f3s13-f3s19=0
f4)finf4+s4f4-f4fin=0
f5)finf5+s5f5-f5s2-f5s3-f5s6-f5s11=0
f6)finf6+s6f6-f6s12-f6s13=0
f7)finf7+s7f7-f7s2-f7s10=0
f8)finf8+s8f8-f8s9-f8s12-f8s13=0
f9)finf9+s9f9-f9s6-f9s11-f9s12-f9s13-f9s19=0
f10)finf10+s10f10-f10s6-f10s12-f10s13=0
f11)finf11+s11f11-f11s6-f11s12=0
f12)finf12+s12f12-f12s4=0
f13)finf13+s13f13-f13s4=0
f14)finf14+s14f14-f14s4=0
f15)finf15+s15f15-f15s9=0
f16)finf16+s16f16-f16s8=0
f17)finf17+s17f17-f17s11=0
f18)finf18+s18f18-f18s12-f18s13=0
f19)finf19+s19f19-f19s6=0
s1val)fins1<1
f1val)finf1<1
s2val)fins2<1
f2val)finf2<1
s3val)fins3<1
f3val)finf3<1
s4val)fins4<1
f4val)finf4<1
s5val)fins5<1
f5val)finf5<1
s6val)fins6<1
f6val)finf6<1
s7val)fins7<1
f7val)finf7<1
s8val)fins8<1
f8val)finf8<1
s9val)fins9<1
f9val)finf9<1
s10val)fins10<1
f10val)finf10<1
s11val)fins11<1
f11val)finf11<1
s12val)fins12<1
f12val)finf12<1
s13val)fins13<1
f13val)finf13<1
s14val)fins14<1
f14val)finf14<1
s15val)fins15<1
f15val)finf15<1
s16val)fins16<1
f16val)finf16<1
s17val)fins17<1
f17val)finf17<1
s18val)fins18<1
f18val)finf18<1
s19val)fins19<1
f19val)finf19<1
end
|