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

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

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

Contoh Fungsi : Standar Deviasi

-
Hitung Standar Deviasi dari Barisan Bilangan Bulat ¶ Diberikan sebuah barisan bilangan bulat dengan n elemen, $A = (a_1,a_2,...,a_n)$. Hitunglah standar Deviasinya. Menghitung Rata-Rata : $$\bar{a}=\frac{1}{n}\sum_{i=1}^n a_i$$ Menghitung Standar Deviasi : $$\sigma=\sqrt{\frac{1}{n-1}\sum_{i=1}^n (a_i-\bar{a})^2}$$ Algoritma Hitung Rata-Rata Deskripsi : Hitung rata-rata Masukkan : list/array dengan n elemen, Keluaran : rata-rata Langkah-langkah : Masukkan list/array bilangan, A deklarasi tempat penyimpanan jumlah, sum=0 untuk setiap i pada (1,2,...,panjang A) sum=sum+A[i] rata-rata=sum/panjang A 3. Hitung Standar Deviasi Deskripsi : Hitung Standar Deviasi Masukkan : list/array bilangan dengan n elemen, Keluaran : nilai standar deviasinya Langkah-langkah : Masukkan n (banyak elemen list/array) Buat list/array berukuran n, A Hitung rata-rata dari A, simpan pada variabel rata Masukkan list/array bilanga
Read more