Masalah Minimum Cost Flow

-

Pengenalan Optimisasi Jaringan

Masalah Minimum Cost 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 47 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 2

Mia ingin berangkat dari kota A ke kota D,
Terdapat beberapa alternatif untuk mencapai tujuan.
Jalur alternatif dan biaya untuk masing-masingnya terlampir pada gambar
Tentukan biaya minimum untuk Mia berangkat dari kota A ke D ! image.png

Formulasi Contoh 2 :


Misalkan :

  • $x_{i,j}$ merupakan jalur dari kota-$i$ ke kota-$j$
    • $x_{i,j}=1$ apabila jalur terpilih
    • $x_{i,j}=0$ apabila jalur TIDAK dipilih
  • $c_{i,j}$ merupakan biaya perjalanan kpta-$i$ ke kota-$j$

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

Minimumkan biaya perjalanan : $$f(\mathbb{x})=2x_{0,1}+10x_{0,2}+20x_{0,3}+10x_{1,2}+2x_{1,3}+5x_{2,3}$$

Kendala Aliran (Flow), misalkan "keluar" dari kota bertanda +, dan "masuk" ke kota bertanda negatif

  • Pilihan Mia keluar dari kota A adalah menuju kota B atau C atau D, Mia perlu memilih satu jalur, jadi
    • $x_{0,1}+x_{0,2}+x_{0,3}=1$
  • Andaikan Mia berada di kota B, artinya Mia masuk dari kota A ke kota B (-), dan pilihan keluar dari kota B adalah menuju kota C atau D, jadi
    • $ -x_{0,1}+x_{1,2}+x_{1,3}=0$
  • Andaikan Mia berada di kota C, artinya Mia masuk dari kota A ke kota C (-) atau dari kota B ke kota C (-), dan selanjutnya Mia ergi ke kota D, jadi
    • $ -x_{0,2}-x_{1,2}+x_{2,3}=0$
  • Andaikan Mia berada di kota D, artinya Mia masuk dari kota A ke kota D (-) atau dari kota B ke kota D (-), atau dari kota C ke kota D (-), jadi
    • $ -x_{0,3}-x_{1,3}-x_{2,3}=-1$
In [4]:
m = mip.Model("Contoh Masalah Minimum Cost Flow")
x = [[m.add_var(var_type=mip.BINARY) for j in range(4) ] for i in range(3) ]

m.objective = mip.minimize( 2*x[0][1]+10*x[0][2]+20*x[0][3]+10*x[1][2]+
                           3*x[1][3]+5*x[2][3] )
#Kendala
m += x[0][1]+x[0][2]+x[0][3] == 1
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] == -1


m.optimize()
print(m.status)
print('Biaya minimum perjalanan Mia =',m.objective_value)
print('Jalur terpilih :')
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
Biaya minimum perjalanan Mia = 5.0
Jalur terpilih :
x[ 0 , 1 ]= 1.0
x[ 1 , 3 ]= 1.0
In [ ]:
m = mip.Model("Contoh Masalah Minimum Cost Flow")
x = [[m.add_var(var_type=mip.BINARY) for j in range(4) ] for i in range(3) ]

m.objective = mip.minimize( 2*x[0][1]+10*x[0][2]+20*x[0][3]+10*x[1][2]+
                           3*x[1][3]+5*x[2][3] )
#Kendala
m += x[0][1]+x[0][2]+x[0][3] == 1
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] == -1


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

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
minimum dari f objektif = 5.0
x[ 0 , 1 ]= 1.0
x[ 1 , 3 ]= 1.0

Ada yang mau didiskusikan?
Silahkan hubungi Ridwan

Comments

Post a Comment

Popular posts from this blog

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

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

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

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