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

Post a Comment

Popular posts from this blog

Aljabar Python

-
Python dapat mengoprasikan Aljabar dengan bantuan library numpy. Sedikit operasi vektor dan matriks yang penting diketahui In [1]: import numpy as np import math Vektor ¶ Penting : Bedakan ketika menulis u=[1,2,3] dan u=np.array([1,2,3]) yang pertama adalah list, yang kedua adalah vektor Tampilan vektor pada python selalu tertulis menyamping , walaupun kita tambahkan transpose, tampilan akan tetap menyamping. Hal ini sangat penting dan harus berhati-hati. u=np.array([1,2,3]) artinya $\mathbb{u}=\begin{bmatrix}1\\2\\3\end{bmatrix}$, tampilan pada python u= [1 2 3] np.transpose(u)=$\mathbb{u}^T=\begin{bmatrix}1&2&3\end{bmatrix}$, tampilan pada python u= [1 2 3] In [2]: u = [ 1 , 2 , 3 ] #ini adalah list, bukan vektor v = [ 4 , 5 , 6 ] #ini adalah list, bukan vektor print ( "List u=" , u ) print ( "List v=" , v ) print ( "Penjumlahan list : u+v
Read more

Fungsi Rekursif

-
Fungsi Rekursif ¶ Fungsi yang memanggil dirinya sendiri untuk melakukan perhitungan Faktorial Misalkan $f(n)$ menyatakan faktorial dari $n$, dengan $n$ adalah bilangan bulat lebih dari 1. Maka $f(n)=n\times (n-1)\times (n-2)\times (n-3)\times ...\times 1$ Bisa juga dituliskan dalam bentuk rekursif, yaitu $f(n)=n\times f(n-1)$ Contoh : $f(5)=5\times 4\times 3\times 2\times 1$ $f(5)=5 \times f(4)$ $f(4)=4 \times f(3)$ $f(3)=3 \times f(2)$ $f(2)=2 \times f(1)$ In [1]: #Menghitung faktorial dari n, TANPA fungsi dan tanpa rekursif print ( "Masukkan bilangan bulat lebih dari 1 yang akan dihitung faktorialnya" ) n = int ( input ()) if ( n == 0 or n == 1 ): hasil = 1 else : hasil = n print ( "n saat ini =" , n , "-hasil saat ini" , hasil ) while n >= 2 : n = n - 1 hasil = hasil * n print ( "n saat ini =" , n , "-hasil saat ini" ,
Read more

Metode Penalti

-
Metode Penalti ¶ --Catatan kuliah MA3071 20210802 Minimumkan $𝑓(𝐱)$ terhadap kendala $𝐱∈𝑆$ Dengan $𝑓$ merupakan fungsi yang kontinu pada $ℝ^𝑛$ dan $𝑆$ adalah himpunan kendala $𝑆=\{𝑥:h_i(𝐱)= 0,i=1,2,...,m\}$ Ide dari Metode penalti adalah mengubah masalah optimisasi berkendala menjadi masalah optimisasi tanpa kendala, Kendala tersebut dikalikan dengan suatu konstanta positif (yang membesar) sehingga berfungsi menjadi suatu penalti pada masalah meminimumkan. Masalah dimodifikasi menjadi : Minimumkan $𝑓(𝐱)+𝑐𝑃(𝐱)$ Dengan $𝑐$ suatu konstanta positif dan $𝑃(𝐱)$ adalah fungsi pada $ℝ^𝑛$ yang memenuhi $𝑃(𝐱)$ fungsi kontinu $𝑃(𝐱)≥0$ untuk semua $𝐱∈ℝ^𝑛$ Biasanya dipilih fungsi penalti $\displaystyle 𝑃(𝐱)=\frac{1}{2} \sum_{i=1}^{m}[ℎ_i(\mathbf{𝑥})]^2$ $𝑃(𝐱)=0$ jika dan hanya jika $𝐱∈𝑆$ Contoh ¶ Minimumkan $$f(x_1,x_2)=x_1^2+x_2^2$$ Terhadap kendala $x_1+x_2-1=0$ =====================
Read more

Pengolahan Matriks (manual)

-
Pengolahan Matriks dan Vektor ¶ Pada tulisan berikut, akan diberikan contoh algoritma dan program untuk mengolah matriks dan vektor tanpa menggunakan library atau fungsi yang sudah tersedia. Transpose Matriks ¶ Misalkan matriks $A=\begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n} \\a_{2,1}&a_{2,2}&\cdots&a_{2,n} \\\vdots&\ddots&\ddots&\vdots \\a_{m,1}&a_{m,2}&\cdots&a_{m,n}\end{bmatrix}$ Transpose dari matriks $A$ adalah $A^T=\begin{bmatrix}a_{1,1}&a_{2,1}&\cdots&a_{m,1} \\a_{1,2}&a_{2,2}&\cdots&a_{m,2} \\\vdots&\ddots&\ddots&\vdots \\a_{1,n}&b_{2,n}&\cdots&a_{n,m}\end{bmatrix}$, atau $B=\begin{bmatrix}b_{1,1}&b_{1,2}&\cdots&b_{1,m} \\b_{2,1}&b_{2,2}&\cdots&b_{2,m} \\\vdots&\ddots&\ddots&\vdots \\b_{n,1}&b_{n,2}&\cdots&b_{n,m}\end{bmatrix}$ , untuk setiap $i\in\{1,2,...,m\}$ dan $j\in\{1,2,..
Read more