Masalah Maksimum Flow

Pengenalan Optimisasi Jaringan

Maksimum Flow

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
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

Contoh 3

Mia ingin mengirimkan sebanyak banyaknya barang dari kota A ke kota D.
Terdapat beberapa alternatif untuk mengirimkan barang. Dan masing-masing alternatif memiliki kapasitas pengiriman.
Jalur alternatif dan kapasitas pengiriman untuk masing-masingnya terlampir pada gambar
Tentukan maksimal banyaknya barang yang bisa dikirimkan! image.png

Formulasi Contoh 3 :

Misalkan :

  • $x_{i,j}$ merupakan banyaknya barang yang dikirimkan dari kota-$i$ ke kota-$j$
  • $q[0]$ merupakan total banyaknya barang yang dikirimkan dari kota-A ke kota-D.

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

Maksimumkan banyaknya barang yang bisa dikirimkan : $$f(\mathbb{x})=q[0]$$

Kendala 1 - setiap pabrik mengirimkan barang sesuai kapasitas produksinya :

  • Banyaknya barang yang keluar dari kota A sebanyak q[0] : $x_{0,1}+x_{0,2}+x_{0,3}=q[0]$
  • Kekekalan aliran di kota B, -banyak barang masuk + barang keluar = 0 : $ -x_{0,1}+x_{1,2}+x_{1,3}=0$
  • Kekekalan aliran di kota C, -banyak barang masuk + barang keluar = 0 : $ -x_{0,2}-x_{1,2}+x_{2,3}=0$
  • Banyaknya barang yang diterima kota D sebanyak -q[0] : $ -x_{0,3}-x_{1,3}-x_{2,3}=-q[0]$

Kendala 2 - setiap jalur memiliki kapasitas pengiriman :

  • $x_{0,1}\leq 2$
  • $x_{0,2}\leq 10$
  • $x_{0,3}\leq 20$
  • $x_{1,2}\leq 10$
  • $x_{1,3}\leq 3$
  • $x_{2,3}\leq 5$
In [3]:
m = mip.Model("Contoh Masalah Maximum Flow")
x = [[m.add_var(var_type=mip.INTEGER) for j in range(4) ] for i in range(3) ]
q = [m.add_var(var_type=mip.INTEGER) for i in range(1) ] 
m.objective = mip.maximize( q[0] )
#Kendala
m += x[0][1]+x[0][2]+x[0][3]  == q[0]
m += -x[0][1]+x[1][2]+x[1][3] == 0
m += -x[0][2]-x[1][2]+x[2][3] == 0
m += -x[0][3]-x[1][3]-x[2][3]  == -q[0]

m += x[0][1] <=2
m += x[0][2] <=10
m += x[0][3] <=20
m += x[1][2] <=10
m += x[1][3] <=3
m += x[2][3] <=5


m.optimize()
print(m.status)
print('Maksimal banyak barang yang bisa dikirmkan =',m.objective_value)

print("Barang yang dikirim di masing-masing jalur :")
for i in range(3): 
    for j in range(4): 
        if(x[i][j].x>=0.5): print("x[",i,",",j,"]=",x[i][j].x)
OptimizationStatus.OPTIMAL
Maksimal banyak barang yang bisa dikirmkan = 27.0
Barang yang dikirim di masing-masing jalur :
x[ 0 , 1 ]= 2.0
x[ 0 , 2 ]= 5.0
x[ 0 , 3 ]= 20.0
x[ 1 , 3 ]= 2.0
x[ 2 , 3 ]= 5.0

Alternatif lain, seolah-olah kita membuat jalur baru, yaitu jalur dari D ke kota A.
Maksimalkan barang yang dikirimkan dari kota D ke kota A image.png

Formulasi Contoh 3 :

Misalkan :

  • $x_{i,j}$ merupakan banyaknya barang yang dikirimkan dari kota-$i$ ke kota-$j$
  • $x[3][0]$ merupakan barang yang dikirimkan dari kota D ke kota A, ekivalen dengan total banyaknya barang yang dikirimkan dari kota-A ke kota-D.

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

Maksimumkan banyaknya barang yang bisa dikirimkan : $$f(\mathbb{x})=x[3][0]$$

Kendala 1 - setiap pabrik mengirimkan barang sesuai kapasitas produksinya :

  • Banyaknya barang yang keluar dari kota A sebanyak q[0] : $x_{0,1}+x_{0,2}+x_{0,3}=x[3][0]$
  • Kekekalan aliran di kota B, -banyak barang masuk + barang keluar = 0 : $ -x_{0,1}+x_{1,2}+x_{1,3}=0$
  • Kekekalan aliran di kota C, -banyak barang masuk + barang keluar = 0 : $ -x_{0,2}-x_{1,2}+x_{2,3}=0$
  • Banyaknya barang yang diterima kota D sebanyak -q[0] : $ -x_{0,3}-x_{1,3}-x_{2,3}=-x[3][0]$

Kendala 2 - setiap jalur memiliki kapasitas pengiriman :

  • $x_{0,1}\leq 2$
  • $x_{0,2}\leq 10$
  • $x_{0,3}\leq 20$
  • $x_{1,2}\leq 10$
  • $x_{1,3}\leq 3$
  • $x_{2,3}\leq 5$
In [4]:
m = mip.Model("Contoh Masalah Maximum Flow")
x = [[m.add_var(var_type=mip.INTEGER) for j in range(4) ] for i in range(4) ]

m.objective = mip.maximize( x[3][0] )
#Kendala
m += x[0][1]+x[0][2]+x[0][3]  == x[3][0]
m += -x[0][1]+x[1][2]+x[1][3] == 0
m += -x[0][2]-x[1][2]+x[2][3] == 0
m += -x[0][3]-x[1][3]-x[2][3]  == -x[3][0]

m += x[0][1] <=2
m += x[0][2] <=10
m += x[0][3] <=20
m += x[1][2] <=10
m += x[1][3] <=3
m += x[2][3] <=5


m.optimize()
print(m.status)
print('Maksimal banyak barang yang bisa dikirmkan =',m.objective_value)

print("Barang yang dikirim di masing-masing jalur :")
for i in range(3): 
    for j in range(4): 
        if(x[i][j].x>=0.5): print("x[",i,",",j,"]=",x[i][j].x)
OptimizationStatus.OPTIMAL
Maksimal banyak barang yang bisa dikirmkan = 27.0
Barang yang dikirim di masing-masing jalur :
x[ 0 , 1 ]= 2.0
x[ 0 , 2 ]= 5.0
x[ 0 , 3 ]= 20.0
x[ 1 , 3 ]= 2.0
x[ 2 , 3 ]= 5.0

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