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

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