Masalah Transportasi Jaringan

Pengenalan Optimisasi Jaringan

Masalah Transportasi

In [1]:
#Install library Mixed Integer Programming sebagai tools yang digunakan dalam workshop ini
!pip install mip #Apabila library mip sudah terinstall, berikan comment (tanda #) sebelum !pip
import mip #memanggil library Mixed Integer Programminh
import numpy as np #memanggil library Numerical Python
Using Python-MIP package version 1.6.4

Contoh 1

Terdapat 4 buah pabrik yang memiliki kapasitas produksi 30,80,10, dan 60
Terdapat 5 orang penjual yang meminta barang sejumlah 10,50,20,80, dan 20.
Biaya pengiriman barang dari satu pabrik ke penjual bisa berbeda. (terlampir pada matriks C pada gambar)
Tentukan biaya minimum untuk mengirimkan barang ! image.png

Formulasi Contoh 1 :

Misalkan :

  • $x_{i,j}$ merupakan banyaknya barang yang dikirimkan dari pabrik $i$ ke penjual $j$
  • $c_{i,j}$ merupakan biaya antar barang yang dikirimkan dari pabrik $i$ ke penjual $j$

dengan $i\in\{0,1,2,3\}$ dan $j\in\{0,1,2,3,4\}$ (indeks pada python dimulai dari nol)

Minimumkan biaya pengantaran : $$f(\mathbb{x})=c_{0,0}x_{0,0}+c_{0,1}x_{0,1}+c_{0,2}x_{0,2}+...+c_{3,4}x_{3,4}$$ $$f(\mathbb{x})=\sum_{j=0}^4\sum_{i=0}^3 c_{i,j}x_{i,j}$$

Kendala 1 - setiap pabrik mengirimkan barang sesuai kapasitas produksinya :

  • Pabrik ke-0 produksi sebanyak 30 : $x_{0,0}+x_{0,1}+x_{0,2}+x_{0,3}+x_{0,4}=30$
  • Pabrik ke-1 produksi sebanyak 80 : $x_{1,0}+x_{1,1}+x_{1,2}+x_{1,3}+x_{1,4}=80$
  • Pabrik ke-2 produksi sebanyak 10 : $x_{2,0}+x_{2,1}+x_{2,2}+x_{2,3}+x_{2,4}=10$
  • Pabrik ke-3 produksi sebanyak 60 : $x_{3,0}+x_{3,1}+x_{3,2}+x_{3,3}+x_{3,4}=60$

Kendala 2 - setiap penjual menerima sesuai dengan permintaannya :

  • Penjual ke-0 meminta 10 barang : $x_{0,0}+x_{1,0}+x_{2,0}+x_{3,0}=10$
  • Penjual ke-1 meminta 50 barang : $x_{0,1}+x_{1,1}+x_{2,1}+x_{3,1}=10$
  • Penjual ke-2 meminta 20 barang : $x_{0,2}+x_{1,2}+x_{2,2}+x_{3,2}=10$
  • Penjual ke-3 meminta 80 barang : $x_{0,3}+x_{1,3}+x_{2,3}+x_{3,3}=10$
  • Penjual ke-4 meminta 20 barang : $x_{0,4}+x_{1,4}+x_{2,4}+x_{3,4}=10$
In [2]:
#Definisikan matriks cost
cost=np.array([[3,4,6,8,9],
            [2,2,4,5,5],
            [2,2,2,3,2],
            [3,3,2,4,2]])

m = mip.Model("Contoh Masalah Transportasi 1")
x = [[m.add_var(var_type=mip.INTEGER) for j in range(5)] for i in range(4)]

#m.objective = mip.minimize( 3*x[0][0]+ 4*x[0][1]+ 6*x[0][2]+ ... )
m.objective = mip.minimize( mip.xsum(cost[i][j]*x[i][j] for i in range(4) for j in range(5) ) )

#barang yang dikirim sama dengan kapasitas produksi
m += x[0][0]+x[0][1]+x[0][2]+x[0][3]+x[0][4] == 30 # kendala pengiriman dari pabrik 0
m += x[1][0]+x[1][1]+x[1][2]+x[1][3]+x[1][4] == 80 # kendala pengiriman dari pabrik 1
m += x[2][0]+x[2][1]+x[2][2]+x[2][3]+x[2][4] == 10 # kendala pengiriman dari pabrik 2
m += x[3][0]+x[3][1]+x[3][2]+x[3][3]+x[3][4] == 60 # kendala pengiriman dari pabrik 3


#penjual 0 hanya butuh 10
m += x[0][0]+x[1][0]+x[2][0]+x[3][0] == 10
#penjual 1 hanya butuh 50
m += x[0][1]+x[1][1]+x[2][1]+x[3][1] == 50
#penjual 2 hanya butuh 50
m += x[0][2]+x[1][2]+x[2][2]+x[3][2] == 20
#penjual 3 hanya butuh 80
m += x[0][3]+x[1][3]+x[2][3]+x[3][3] == 80
#penjual 4 hanya butuh 20
m += x[0][4]+x[1][4]+x[2][4]+x[3][4] == 20


m.optimize()
print(m.status)
print('minimum dari f objektif =',m.objective_value)

print('Variabel keputusan : ')
for i in range(4): 
    for j in range(5): 
        if(x[i][j].x>=0.5): print("x[",i,",",j,"]=",x[i][j].x,' dan cost[',i,',',j,'] =',cost[i][j])
OptimizationStatus.OPTIMAL
minimum dari f objektif = 610.0
Variabel keputusan : 
x[ 0 , 0 ]= 10  dan cost[ 0 , 0 ] = 3
x[ 0 , 1 ]= 20  dan cost[ 0 , 1 ] = 4
x[ 1 , 1 ]= 30  dan cost[ 1 , 1 ] = 2
x[ 1 , 3 ]= 50  dan cost[ 1 , 3 ] = 5
x[ 2 , 3 ]= 10  dan cost[ 2 , 3 ] = 3
x[ 3 , 2 ]= 20  dan cost[ 3 , 2 ] = 2
x[ 3 , 3 ]= 20  dan cost[ 3 , 3 ] = 4
x[ 3 , 4 ]= 20  dan cost[ 3 , 4 ] = 2

Andaikan penjual 2 ingin menerima minimal 3 barang dari pabrik 1, maka terdapat tambahan kendala $$x_{1,2}\geq 3$$

In [3]:
#Definisikan matriks cost
cost=np.array([[3,4,6,8,9],
            [2,2,4,5,5],
            [2,2,2,3,2],
            [3,3,2,4,2]])

m = mip.Model("Contoh Masalah Transportasi 1")
x = [[m.add_var(var_type=mip.INTEGER) for j in range(5)] for i in range(4)]

#m.objective = mip.minimize( 3*x[0][0]+ 4*x[0][1]+ 6*x[0][2]+ ... )
m.objective = mip.minimize( mip.xsum(cost[i][j]*x[i][j] for i in range(4) for j in range(5) ) )

#barang yang dikirim sama dengan kapasitas produksi
m += x[0][0]+x[0][1]+x[0][2]+x[0][3]+x[0][4] == 30 # kendala pengiriman dari pabrik 0
m += x[1][0]+x[1][1]+x[1][2]+x[1][3]+x[1][4] == 80 # kendala pengiriman dari pabrik 1
m += x[2][0]+x[2][1]+x[2][2]+x[2][3]+x[2][4] == 10 # kendala pengiriman dari pabrik 2
m += x[3][0]+x[3][1]+x[3][2]+x[3][3]+x[3][4] == 60 # kendala pengiriman dari pabrik 3


#penjual 0 hanya butuh 10
m += x[0][0]+x[1][0]+x[2][0]+x[3][0] == 10
#penjual 1 hanya butuh 50
m += x[0][1]+x[1][1]+x[2][1]+x[3][1] == 50
#penjual 2 hanya butuh 50
m += x[0][2]+x[1][2]+x[2][2]+x[3][2] == 20
#penjual 3 hanya butuh 80
m += x[0][3]+x[1][3]+x[2][3]+x[3][3] == 80
#penjual 4 hanya butuh 20
m += x[0][4]+x[1][4]+x[2][4]+x[3][4] == 20

#penjual 2 ingin menerima minimal 3 barang dari pabrik 1
m += x[1][2] >= 3

m.optimize()
print(m.status)
print('minimum dari f objektif =',m.objective_value)

print('Variabel keputusan : ')
for i in range(4): 
    for j in range(5): 
        if(x[i][j].x>=0.5): print("x[",i,",",j,"]=",x[i][j].x,' dan cost[',i,',',j,'] =',cost[i][j])
OptimizationStatus.OPTIMAL
minimum dari f objektif = 613.0
Variabel keputusan : 
x[ 0 , 0 ]= 10  dan cost[ 0 , 0 ] = 3
x[ 0 , 1 ]= 20  dan cost[ 0 , 1 ] = 4
x[ 1 , 1 ]= 30  dan cost[ 1 , 1 ] = 2
x[ 1 , 2 ]= 3  dan cost[ 1 , 2 ] = 4
x[ 1 , 3 ]= 47  dan cost[ 1 , 3 ] = 5
x[ 2 , 3 ]= 10  dan cost[ 2 , 3 ] = 3
x[ 3 , 2 ]= 17  dan cost[ 3 , 2 ] = 2
x[ 3 , 3 ]= 23  dan cost[ 3 , 3 ] = 4
x[ 3 , 4 ]= 20  dan cost[ 3 , 4 ] = 2

Andaikan ada kondisi dimana pabrik 0 tidak bisa mengirimkan barang ke penjual 0.
Kondisi di sini bisa dibagi menjadi 2.

  1. Tidak bisa mengirimkan barang karena akses yang sama sekali tidak ada
    Untuk ini kendala ditambahkan $x_{0,0}=0$
  2. Tidak ingin mengirimkan barang karena biaya yang mahal.
    Untuk ini biaya pengiriman ditambahkan menjadi $c_{0,0}=100000$
In [4]:
#Definisikan matriks cost
cost=np.array([[3,4,6,8,9],
            [2,2,4,5,5],
            [2,2,2,3,2],
            [3,3,2,4,2]])

m = mip.Model("Contoh Masalah Transportasi 1")
x = [[m.add_var(var_type=mip.INTEGER) for j in range(5)] for i in range(4)]

#m.objective = mip.minimize( 3*x[0][0]+ 4*x[0][1]+ 6*x[0][2]+ ... )
m.objective = mip.minimize( mip.xsum(cost[i][j]*x[i][j] for i in range(4) for j in range(5) ) )

#apa yang dikirim harus harus sama dengan kapasitas
m += x[0][0]+x[0][1]+x[0][2]+x[0][3]+x[0][4] == 30 # kendala pengiriman dari pabrik 0
m += x[1][0]+x[1][1]+x[1][2]+x[1][3]+x[1][4] == 80 # kendala pengiriman dari pabrik 1
m += x[2][0]+x[2][1]+x[2][2]+x[2][3]+x[2][4] == 10 # kendala pengiriman dari pabrik 2
m += x[3][0]+x[3][1]+x[3][2]+x[3][3]+x[3][4] == 60 # kendala pengiriman dari pabrik 3


#penjual 0 hanya butuh 10
m += x[0][0]+x[1][0]+x[2][0]+x[3][0] == 10
#penjual 1 hanya butuh 50
m += x[0][1]+x[1][1]+x[2][1]+x[3][1] == 50
#penjual 2 hanya butuh 50
m += x[0][2]+x[1][2]+x[2][2]+x[3][2] == 20
#penjual 3 hanya butuh 80
m += x[0][3]+x[1][3]+x[2][3]+x[3][3] == 80
#penjual 4 hanya butuh 20
m += x[0][4]+x[1][4]+x[2][4]+x[3][4] == 20

#penjual 2 ingin menerima minimal 3 barang dari pabrik 1
m += x[1][2] >= 3

#pabrik 0 tidak memiliki akses mengirimkan barang ke penjual 0
m += x[0][0] == 0

m.optimize()
print(m.status)
print('minimum dari f objektif =',m.objective_value)

print('Variabel keputusan : ')
for i in range(4): 
    for j in range(5): 
        if(x[i][j].x>=0.5): print("x[",i,",",j,"]=",x[i][j].x,' dan cost[',i,',',j,'] =',cost[i][j])
OptimizationStatus.OPTIMAL
minimum dari f objektif = 623.0
Variabel keputusan : 
x[ 0 , 1 ]= 30  dan cost[ 0 , 1 ] = 4
x[ 1 , 0 ]= 10  dan cost[ 1 , 0 ] = 2
x[ 1 , 1 ]= 20  dan cost[ 1 , 1 ] = 2
x[ 1 , 2 ]= 3  dan cost[ 1 , 2 ] = 4
x[ 1 , 3 ]= 47  dan cost[ 1 , 3 ] = 5
x[ 2 , 3 ]= 10  dan cost[ 2 , 3 ] = 3
x[ 3 , 2 ]= 17  dan cost[ 3 , 2 ] = 2
x[ 3 , 3 ]= 23  dan cost[ 3 , 3 ] = 4
x[ 3 , 4 ]= 20  dan cost[ 3 , 4 ] = 2
In [5]:
#Definisikan matriks cost
#Biaya kirim pabrik 0 ke penjual 0 sangat mahal
#Tidak ingin mengirimkan barang karena biaya yang mahal.
cost=np.array([[100000,4,6,8,9],
            [2,2,4,5,5],
            [2,2,2,3,2],
            [3,3,2,4,2]])

m = mip.Model("Contoh Masalah Transportasi 1")
x = [[m.add_var(var_type=mip.INTEGER) for j in range(5)] for i in range(4)]

#m.objective = mip.minimize( 3*x[0][0]+ 4*x[0][1]+ 6*x[0][2]+ ... )
m.objective = mip.minimize( mip.xsum(cost[i][j]*x[i][j] for i in range(4) for j in range(5) ) )

#apa yang dikirim harus harus sama dengan kapasitas
m += x[0][0]+x[0][1]+x[0][2]+x[0][3]+x[0][4] == 30 # kendala pengiriman dari pabrik 0
m += x[1][0]+x[1][1]+x[1][2]+x[1][3]+x[1][4] == 80 # kendala pengiriman dari pabrik 1
m += x[2][0]+x[2][1]+x[2][2]+x[2][3]+x[2][4] == 10 # kendala pengiriman dari pabrik 2
m += x[3][0]+x[3][1]+x[3][2]+x[3][3]+x[3][4] == 60 # kendala pengiriman dari pabrik 3


#penjual 0 hanya butuh 10
m += x[0][0]+x[1][0]+x[2][0]+x[3][0] == 10
#penjual 1 hanya butuh 50
m += x[0][1]+x[1][1]+x[2][1]+x[3][1] == 50
#penjual 2 hanya butuh 50
m += x[0][2]+x[1][2]+x[2][2]+x[3][2] == 20
#penjual 3 hanya butuh 80
m += x[0][3]+x[1][3]+x[2][3]+x[3][3] == 80
#penjual 4 hanya butuh 20
m += x[0][4]+x[1][4]+x[2][4]+x[3][4] == 20

#penjual 2 ingin menerima minimal 3 barang dari pabrik 1
m += x[1][2] >= 3

m.optimize()
print(m.status)
print('minimum dari f objektif =',m.objective_value)

print('Variabel keputusan : ')
for i in range(4): 
    for j in range(5): 
        if(x[i][j].x>=0.5): print("x[",i,",",j,"]=",x[i][j].x,' dan cost[',i,',',j,'] =',cost[i][j])
OptimizationStatus.OPTIMAL
minimum dari f objektif = 623.0
Variabel keputusan : 
x[ 0 , 1 ]= 30  dan cost[ 0 , 1 ] = 4
x[ 1 , 0 ]= 10  dan cost[ 1 , 0 ] = 2
x[ 1 , 1 ]= 20  dan cost[ 1 , 1 ] = 2
x[ 1 , 2 ]= 3  dan cost[ 1 , 2 ] = 4
x[ 1 , 3 ]= 47  dan cost[ 1 , 3 ] = 5
x[ 2 , 3 ]= 10  dan cost[ 2 , 3 ] = 3
x[ 3 , 2 ]= 17  dan cost[ 3 , 2 ] = 2
x[ 3 , 3 ]= 23  dan cost[ 3 , 3 ] = 4
x[ 3 , 4 ]= 20  dan cost[ 3 , 4 ] = 2

Tidak ingin mengirimkan barang karena biaya yang mahal.
Untuk ini biaya pengiriman ditambahkan menjadi $c_{0,0}=100000$

Pabrik 0 masih bisa mengirimkan barang ke penjual 0, jika memang penjual 0 sangat menginginkan 2 barang yang berasal dari penjual 0 dengan biaya berapapun
Untuk ini tambahkan kendala $x_{0,0}=2$

In [6]:
#Definisikan matriks cost
#Biaya kirim pabrik 0 ke penjual 0 sangat mahal
#Tidak ingin mengirimkan barang karena biaya yang mahal.
cost=np.array([[100000,4,6,8,9],
            [2,2,4,5,5],
            [2,2,2,3,2],
            [3,3,2,4,2]])

m = mip.Model("Contoh Masalah Transportasi 1")
x = [[m.add_var(var_type=mip.INTEGER) for j in range(5)] for i in range(4)]

#m.objective = mip.minimize( 3*x[0][0]+ 4*x[0][1]+ 6*x[0][2]+ ... )
m.objective = mip.minimize( mip.xsum(cost[i][j]*x[i][j] for i in range(4) for j in range(5) ) )

#apa yang dikirim harus harus sama dengan kapasitas
m += x[0][0]+x[0][1]+x[0][2]+x[0][3]+x[0][4] == 30 # kendala pengiriman dari pabrik 0
m += x[1][0]+x[1][1]+x[1][2]+x[1][3]+x[1][4] == 80 # kendala pengiriman dari pabrik 1
m += x[2][0]+x[2][1]+x[2][2]+x[2][3]+x[2][4] == 10 # kendala pengiriman dari pabrik 2
m += x[3][0]+x[3][1]+x[3][2]+x[3][3]+x[3][4] == 60 # kendala pengiriman dari pabrik 3


#penjual 0 hanya butuh 10
m += x[0][0]+x[1][0]+x[2][0]+x[3][0] == 10
#penjual 1 hanya butuh 50
m += x[0][1]+x[1][1]+x[2][1]+x[3][1] == 50
#penjual 2 hanya butuh 50
m += x[0][2]+x[1][2]+x[2][2]+x[3][2] == 20
#penjual 3 hanya butuh 80
m += x[0][3]+x[1][3]+x[2][3]+x[3][3] == 80
#penjual 4 hanya butuh 20
m += x[0][4]+x[1][4]+x[2][4]+x[3][4] == 20

#penjual 2 ingin menerima minimal 3 barang dari pabrik 1
m += x[1][2] >= 3

#penjual 0 ingin menerima 2 barang dari pabrik 0 walaupun biayanya mahal
m += x[0][2] == 2


m.optimize()
print(m.status)
print('minimum dari f objektif =',m.objective_value)

print('Variabel keputusan : ')
for i in range(4): 
    for j in range(5): 
        if(x[i][j].x>=0.5): print("x[",i,",",j,"]=",x[i][j].x,' dan cost[',i,',',j,'] =',cost[i][j])
OptimizationStatus.OPTIMAL
minimum dari f objektif = 625.0
Variabel keputusan : 
x[ 0 , 1 ]= 28  dan cost[ 0 , 1 ] = 4
x[ 0 , 2 ]= 2  dan cost[ 0 , 2 ] = 6
x[ 1 , 0 ]= 10  dan cost[ 1 , 0 ] = 2
x[ 1 , 1 ]= 22  dan cost[ 1 , 1 ] = 2
x[ 1 , 2 ]= 3  dan cost[ 1 , 2 ] = 4
x[ 1 , 3 ]= 45  dan cost[ 1 , 3 ] = 5
x[ 2 , 3 ]= 10  dan cost[ 2 , 3 ] = 3
x[ 3 , 2 ]= 15  dan cost[ 3 , 2 ] = 2
x[ 3 , 3 ]= 25  dan cost[ 3 , 3 ] = 4
x[ 3 , 4 ]= 20  dan cost[ 3 , 4 ] = 2

Ada yang mau didiskusikan?
Silahkan hubungi Ridwan

Comments

Popular posts from this blog

Aljabar Python

MA3071 : Algoritma Newton & Conjugate Gradien

Contoh Fungsi : Standar Deviasi

Contoh Program Linear di Python & R