Masalah Penugasan

Pengenalan Optimisasi Jaringan

Masalah Penugasan

In [2]:
#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 49 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 2

Terdapat 3 orang (Anisa,Balqis,Cantika) yang akan ditugaskan untuk menjadi Ketua, Bendahara dan sekertaris suatu organisasi.
"Biaya" untuk menempatkan mereka ke masing-masing posisi terlampir pada gambar. "Biaya" dalam hal ini bisa jadi biaya untuk melakukan pelatihan posisi tersebut kepada seseorang.
Tentukan biaya minimum untuk masalah penugasan ini ! image.png

Formulasi Tugas 2 :

Misalkan :

  • $x_{i,j}$ merupakan penugasan terpilih orang ke-$i$ ditugaskan ke posisi ke-$j$ .
    • $x_{i,j}=1$ apabila orang ke-$i$ diberi posisi ke-$j$
    • $x_{i,j}=0$ apabila orang ke-$i$ TIDAK diberi posisi ke-$j$
  • $c_{i,j}$ merupakan "biaya" untuk mencocokkan orang-posisi

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

Minimumkan biaya "pencocokan" : $$f(\mathbb{x})=c_{0,0}x_{0,0}+c_{0,1}x_{0,1}+c_{0,2}x_{0,2}+...+c_{2,2}x_{2,2}$$ $$f(\mathbb{x})=\sum_{j=0}^2\sum_{i=0}^2 c_{i,j}x_{i,j}$$

Kendala 1 - setiap orang hanya bisa diberi 1 jabatan :

  • $x_{0,0}+x_{0,1}+x_{0,2} = 1$
  • $x_{1,0}+x_{1,1}+x_{1,2} = 1$
  • $x_{2,0}+x_{2,1}+x_{2,2} = 1$

Kendala 2 - setiap jabatan hanya bisa diisi oleh 1 orang :

  • $x_{0,0}+x_{1,0}+x_{2,0} = 1$
  • $x_{0,1}+x_{1,1}+x_{2,1} = 1$
  • $x_{0,2}+x_{1,2}+x_{2,2} = 1$
In [6]:
#Definisikan matriks cost
cost=np.array([[2,5,7],
            [4,2,1],
            [2,6,5]])

m = mip.Model("Contoh Masalah Penugasan 1")
x = [[m.add_var(var_type=mip.BINARY) for j in range(3)] for i in range(3)]

m.objective = mip.minimize( mip.xsum(cost[i][j]*x[i][j] for i in range(3) for j in range(3) ) )

#1 orang menempati 1 jabatan
m += x[0][0]+x[0][1]+x[0][2] == 1 
m += x[1][0]+x[1][1]+x[1][2] == 1 
m += x[2][0]+x[2][1]+x[2][2] == 1

#1 jabatan diisi oleh 1 orang
m += x[0][0]+x[1][0]+x[2][0] == 1
m += x[0][1]+x[1][1]+x[2][1] == 1
m += x[0][2]+x[1][2]+x[2][2] == 1

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

print('Variabel keputusan : ')
for i in range(3): 
    for j in range(3): 
        if(x[i][j].x>=0.5): print("x[",i,",",j,"]=",x[i][j].x)
OptimizationStatus.OPTIMAL
minimum dari f objektif = 8.0
Variabel keputusan : 
x[ 0 , 1 ]= 1.0
x[ 1 , 2 ]= 1.0
x[ 2 , 0 ]= 1.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