Masalah Transportasi Jaringan (2)

Pengenalan Optimisasi Jaringan

Masalah Transportasi Jaringan (2)
Tautan Masalah Transportasi Jaringan (1) : https://www.ridwanreza.com/2021/08/masalah-transportasi-jaringan.html

In [ ]:
#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
Collecting mip
  Downloading mip-1.13.0-py3-none-any.whl (48.0 MB)
     |████████████████████████████████| 48.0 MB 50 kB/s 
Requirement already satisfied: cffi in /usr/local/lib/python3.7/dist-packages (from mip) (1.14.6)
Requirement already satisfied: pycparser in /usr/local/lib/python3.7/dist-packages (from cffi->mip) (2.20)
Installing collected packages: mip
Successfully installed mip-1.13.0

Tugas 1

Terdapat 4 buah pabrik yang memiliki kapasitas produksi 30,80,10, dan 60
Terdapat 4 orang penjual yang meminta barang sejumlah 10,50,20, dan 80.

  • Masalah ini serupa dengan Contoh 1, tetapi tidak ada penjual kelima
    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 Tugas 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$

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\}$ (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,3}x_{3,3}$$ $$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}=30$
  • Pabrik ke-1 produksi sebanyak 80 : $x_{1,0}+x_{1,1}+x_{1,2}+x_{1,3}=80$
  • Pabrik ke-2 produksi sebanyak 10 : $x_{2,0}+x_{2,1}+x_{2,2}+x_{2,3}=10$
  • Pabrik ke-3 produksi sebanyak 60 : $x_{3,0}+x_{3,1}+x_{3,2}+x_{3,3}=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$
In [ ]:
#Definisikan matriks cost
cost=np.array([[3,4,6,8],
            [2,2,4,5],
            [2,2,2,3],
            [3,3,2,4]])

m = mip.Model("Tugas 1 Masalah Transportasi")
x = [[m.add_var(var_type=mip.INTEGER) for j in range(4)] 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(4) ) )

#barang yang dikirim boleh kurang dari yang diproduksi
m += x[0][0]+x[0][1]+x[0][2]+x[0][3] == 30 # kendala pengiriman dari S0
m += x[1][0]+x[1][1]+x[1][2]+x[1][3] == 80 # kendala pengiriman dari S1
m += x[2][0]+x[2][1]+x[2][2]+x[2][3] == 10 # kendala pengiriman dari S0
m += x[3][0]+x[3][1]+x[3][2]+x[3][3] == 60 # kendala pengiriman dari S1


#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

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(4): 
        if(x[i][j].x>=0.5): print("x[",i,",",j,"]=",x[i][j].x,' dan cost[',i,',',j,'] =',cost[i][j])
OptimizationStatus.INFEASIBLE
minimum dari f objektif = None
Variabel keputusan : 
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-4636ae87acc5> in <module>()
     34 for i in range(4):
     35     for j in range(4):
---> 36         if(x[i][j].x>=0.5): print("x[",i,",",j,"]=",x[i][j].x,' dan cost[',i,',',j,'] =',cost[i][j])

TypeError: '>=' not supported between instances of 'NoneType' and 'float'

Kode di atas tidak mengeluarkan hasil karena memang tidak memiliki solusi (solusi infeasible).
Penyebabnya adalah kendala kita meminta banyak barang yang diproduksi harus sama dengan banyak permintaan.
Pada kasus ini permintaan kurang dari produksi, sehingga ada barang yang berlebih.
Salah satu solusinya adalah mengubah kendala menjadi :

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}\leq 30$
  • Pabrik ke-1 produksi sebanyak 80 : $x_{1,0}+x_{1,1}+x_{1,2}+x_{1,3}\leq 80$
  • Pabrik ke-2 produksi sebanyak 10 : $x_{2,0}+x_{2,1}+x_{2,2}+x_{2,3}\leq 10$
  • Pabrik ke-3 produksi sebanyak 60 : $x_{3,0}+x_{3,1}+x_{3,2}+x_{3,3}\leq 60$

Artinya barang yang kirimkan boleh kurang dari yang diminta

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

m = mip.Model("Tugas 1 Masalah Transportasi")
x = [[m.add_var(var_type=mip.INTEGER) for j in range(4)] 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(4) ) )

#barang yang dikirim boleh kurang dari yang diproduksi
m += x[0][0]+x[0][1]+x[0][2]+x[0][3] <= 30 # kendala pengiriman dari S0
m += x[1][0]+x[1][1]+x[1][2]+x[1][3] <= 80 # kendala pengiriman dari S1
m += x[2][0]+x[2][1]+x[2][2]+x[2][3] <= 10 # kendala pengiriman dari S2
m += x[3][0]+x[3][1]+x[3][2]+x[3][3] <= 60 # kendala pengiriman dari S3


#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

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(4): 
        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 = 510.0
Variabel keputusan : 
x[ 0 , 0 ]= 10.0  dan cost[ 0 , 0 ] = 3
x[ 1 , 1 ]= 50.0  dan cost[ 1 , 1 ] = 2
x[ 1 , 3 ]= 30.0  dan cost[ 1 , 3 ] = 5
x[ 2 , 3 ]= 10.0  dan cost[ 2 , 3 ] = 3
x[ 3 , 2 ]= 20.0  dan cost[ 3 , 2 ] = 2
x[ 3 , 3 ]= 40.0  dan cost[ 3 , 3 ] = 4

Salah satu solusi lain adalah menambahkan titik dummy yang berfungsi sebagai tempat "menyimpan"/"membuang" kelebihan produksi, yaitu 20 barang.
Artinya masalah kembali ke Contoh 1. Misalkan penjual 4 adalah "menyimpan"/"membuang" kelebihan produksi. dengan biaya pengantaran 0 (kita bisa mengubah sesuai dengan kondisi)

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

m = mip.Model("Tugas 1 Masalah Transportasi")
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 S0
m += x[1][0]+x[1][1]+x[1][2]+x[1][3]+x[1][4] == 80 # kendala pengiriman dari S1
m += x[2][0]+x[2][1]+x[2][2]+x[2][3]+x[2][4] == 10 # kendala pengiriman dari S2
m += x[3][0]+x[3][1]+x[3][2]+x[3][3]+x[3][4] == 60 # kendala pengiriman dari S3


#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 = 523.0
Variabel keputusan : 
x[ 0 , 1 ]= 10.0  dan cost[ 0 , 1 ] = 4
x[ 0 , 4 ]= 20.0  dan cost[ 0 , 4 ] = 0
x[ 1 , 0 ]= 10.0  dan cost[ 1 , 0 ] = 2
x[ 1 , 1 ]= 40.0  dan cost[ 1 , 1 ] = 2
x[ 1 , 2 ]= 3.0  dan cost[ 1 , 2 ] = 4
x[ 1 , 3 ]= 27.0  dan cost[ 1 , 3 ] = 5
x[ 2 , 3 ]= 10.0  dan cost[ 2 , 3 ] = 3
x[ 3 , 2 ]= 17.0  dan cost[ 3 , 2 ] = 2
x[ 3 , 3 ]= 43.0  dan cost[ 3 , 3 ] = 4

Ada yang mau didiskusikan?
Silahkan hubungi Ridwan

Comments

Popular posts from this blog

Aljabar Python

MA3071 : Algoritma Newton & Conjugate Gradien

Contoh Program Linear di Python & R

Kuis 1 MA2151 2021