Program linear ( metode grafik dan metode simpleks )
Dik : Fungsi Tujuan Z=60x+30y
Fungsi Batasan a. 2x+4y≥16
b. 4x+3y≥24
Ditanya : Buat Program linearnya dengan metode Grafik ?
Mencari nilai x dan y pada fungsi batasan
2x+4y≥16
Mencari nilai x maka nilai y = 0 Mencari nilai y maka x = 0
2x+4y≥16 2x+4y≥16
2x+4(0)=16 2(0)+4y=16
2x=16 4y=16
x=8 y=4
4x+3y≥24
Mencari nilai x maka nilai y = 0 Mencari nilai y maka x = 0
4x+3y≥24 4x+3y≥24
4x+3(0)=24 4(0)+3y=24
4x=24 3y=24
x=6 y=8
Gambar grafik :
Mengevaluasi titik ABC
Titik A (8,0)
Z=60x+30y
Z=60(8)+30(0)
Z=480
Titik B (…,…)
Merupakan perpotongan antara garis 2x+4y≥16 dengan 4x+3y≥24
2x+4y≥16 x2 4x+8y=32
4x+3y≥24 x1 4x+3y=24
5y=8
y=1,6
Selanjutnya mencari nilai x dengan menggunakan salah satu persamaan:
2x+4y≥16
2x+4(1,6)=16
2x+6,4=16
2x=16-6,4
2x=9,6
x=4,8
Jadi titik B (4,8 ; 1,6)
Z=60x+30y
Z=60(4,8)+30(1,6)
Z=288+48
Z=336
Titik C (0,8)
Z=60x+30y
Z=60(0)+30(8)
Z=240
Karena harus menggunakan kedua jenis merk pupuk, maka yang diambil adalah titik B(4,8 ; 1,6) yakni 4,8 sak pupuk merk Super dan 1,6 sak pupuk merk Top.
Dik : Fungsi Tujuan Z=200x+400y
Fungsi Batasan a. x+y=30
b. 2x+8y≥80
c. x≤20
Ditanya : Buat Program linearnya dengan metode Grafik ?
Mencari nilai x dan y pada fungsi batasan :
x+y=30
Mencari nilai x maka nilai y = 0 Mencari nilai y maka x = 0
x+y=30 x+y=30
x+(0)=30 (0)+y=30
x=30 y=30
2x+8y≥80
Mencari nilai x maka nilai y = 0 Mencari nilai y maka x = 0
2x+8y≥80 2x+8y≥80
2x+8(0)=80 2(0)+8y=80
2x=80 8y=80
x=40 x=10
x≤20
x=20
Menggambar grafiknya
Mengevaluasi titik ABCD
Titik A (0,10)
Z=200x+400y
Z=200(0)+400(10)
Z=4000
Titik B (20,…)
Merupakan perpotongan antara garis 2x+8y≥80 dengan garis x≤20
x=20, maka y 2x+8y≥80
2(20)+8y=80
40+8y=80
8y=80-40
8y=40
y=5
Jadi titik B (20,5)
Z=200x+400y
Z=200(20)+400(5)
Z=4000+2000
Z=6000
Titik C (20,…)
Merupakan perpotongan antara garis x+y=30 dengan garis x≤20
x=20, maka y x+y=30
(20)+y=30
y=30-20
y=10
Jadi titik C (20,10)
Z=200x+400y
Z=200(20)+400(10)
Z=4000+4000
Z=8000
Titik D (0,30)
Z=200x+400y
Z=200(0)+400(30)
Z=12000
Keuntungan maksimal yaitu pada titik C(20, 10) yakni memproduksi 20 tas jenis LV dan 10 tas jenis CH
Dik : Fungsi Tujuan Z=5p+8q
Fungsi Batasan a. 4p+8q≤24
b. 2p+q≤18
c. 3p+9q≤36
Merubah fungsi tujuan dan batasan
Z-5p-8q=0
4p+8q+r=24
2p+q+s=18
3p+9q+t=36
Menyusun persamaan dalam table
Variabel Dasar Z p q r s t Nilai Kanan
Z 1 -5 -8 0 0 0 0
r 0 4 8 1 0 0 24
s 0 2 1 0 1 0 18
t 0 3 9 0 0 1 36
Memilih kolom kunci
Memililih kolom dengan nilai baris fungsi tujuan bernilai negative dengan angka terbesar.
Variabel Dasar Z p q r s t Nilai Kanan
Z 1 -5 -8 0 0 0 0
r 0 4 8 1 0 0 24
s 0 2 1 0 1 0 18
t 0 3 9 0 0 1 36
Memilih baris kunci
Sebelumnya kita cari index dengan rumus :
Index=(Nilai kanan)/(Nilai kolom kunci)
Dan baris yang mempunyai index positif dengan angka terkecil merupakan baris kunci.
Variabel Dasar Z p q r s t Nilai Kanan Indeks
Z 1 -5 -8 0 0 0 0 0
r 0 4 8 1 0 0 24 3
s 0 2 1 0 1 0 18 18
t 0 3 9 0 0 1 36 4
Maka diketahui pula angka kunci yang merupakan perpotongan antara kolom kunci dan baris kunci yaitu 8.
Merubah nilai-nilai baris kunci
Nilai baris kunci dirubah dengan cara membaginya dengan angka kunci
r 0 4 8 1 0 0 24
8 8 8 8 8 8 8
r = 0 1/2 1 1/8 0 0 3
Merubah nilai-nilai selain baris kunci
Rumus :
Baris baru=baris lama-(koefisien pada kolom kunci* nilai baris kunci baru)
Nilai baru Z
1 -5 -8 0 0 0 0
(-8) 0 1/2 1 1/8 0 0 3
1 -1 0 1 0 0 24
Nilai baru s
0 2 1 0 1 0 18
(1) 0 1/2 1 1/8 0 0 3
0 3/2 0 -1/8 1 0 15
Nilai baru t
0 3 9 0 0 1 36
(9) 0 1/2 1 1/8 0 0 3
0 -3/2 0 -9/8 0 1 9
Maka tabelnya menjadi :
Variabel Dasar Z p q r s t Nilai Kanan
Z 1 -1 0 1 0 0 24
r 0 1/2 1 1/8 0 0 3
s 0 3/2 0 -1/8 1 0 15
t 0 -3/2 0 -9/8 0 1 9
Karena masih ada nilai negative pada fungsi tujuan berarti belum optimal, maka kita kembali kelangkah c yaitu memilih kolom kunci
Variabel Dasar Z p q r s t Nilai Kanan
Z 1 -1 0 1 0 0 24
r 0 1/2 1 1/8 0 0 3
s 0 3/2 0 -1/8 1 0 15
t 0 -3/2 0 -9/8 0 1 9
Menentuka indeks dan memilih baris kunci
Variabel Dasar Z p q r s t Nilai Kanan Indeks
Z 1 -1 0 1 0 0 24 -24
r 0 1/2 1 1/8 0 0 3 6
s 0 3/2 0 -1/8 1 0 15 10
t 0 -3/2 9 -9/8 0 1 9 -6
Merubah nilai-nilai baris kunci dengan menbaginya dengan angka kunci 1/2
r 0 1/2 1 1/8 0 0 3
1/2 1/2 1/2 1/2 1/2 1/2 1/2
0 1 2 1/4 0 0 6
Merubah nilai-nilai selain baris kunci
Nilai baru Z
1 -1 0 1 0 0 24
(-1) 0 1 2 1/4 0 0 6
1 0 -2 5/4 0 0 30
Nilai baru s
0 3/2 0 -1/8 1 0 15
3/2 0 1 2 1/4 0 0 6
0 0 -3 -1/2 1 0 6
Nilai baru t
0 -3/2 0 -9/8 0 1 9
(-3/2) 0 1 2 1/4 0 0 6
0 0 3 -3/4 0 0 18
Maka tabelnya menjadi :
Variabel Dasar Z p q r s t Nilai Kanan
Z 1 0 -2 5/4 0 0 30
r 0 1 2 1/4 0 0 6
s 0 0 -3 -1/2 1 0 6
t 0 0 3 -3/4 0 0 18
Namun masih ada nilai negative pada fungsi tujuan berarti belum optimal, maka kembali lagi kelangkah c yaitu memilih kolom kunci :
Variabel Dasar Z p q r s t Nilai Kanan
Z 1 0 -2 5/4 0 0 30
r 0 1 2 1/4 0 0 6
s 0 0 -3 -1/2 1 0 6
t 0 0 3 -3/4 0 0 18
Menentukan indeks dan memilih baris kunci :
Variabel Dasar Z p q r s t Nilai Kanan Indeks
Z 1 0 -2 5/4 0 0 30 -15
r 0 1 2 1/4 0 0 6 3
s 0 0 -3 -1/2 1 0 6 -2
t 0 0 3 -3/4 0 0 18 6
Merubah nilai-nilai baris kunci dengan membaginyadengan angka kunci 2
r 0 1 2 1/4 0 0 6
2 2 2 2 2 2 2
0 1/2 1 1/8 0 0 3
Merubah nilai-nilai selain baris kunci :
Nilai baru Z
1 0 -2 5/4 0 0 30
(-2) 0 1/2 1 1/8 0 0 3
1 1 0 3/2 0 0 36
Nilai baru s
0 0 -3 -1/2 1 0 6
(-3) 0 1/2 1 1/8 0 0 3
0 3/2 0 -1/8 1 0 15
Nilai baru t
0 0 3 -3/4 0 0 18
3 0 1/2 1 1/8 0 0 3
0 -3/2 0 -9/8 0 0 9
Maka tabelnya menjadi :
Variabel Dasar Z p q r s t Nilai Kanan
Z 1 1 0 3/2 0 0 36
r 0 1/2 1 1/8 0 0 3
s 0 3/2 0 -1/8 1 0 15
t 0 -3/2 0 -9/8 0 0 9
Karena tidak ada lagi nilai negative pada fungsi tujuan, maka table tersebut sudah optimal
Masalah transportasi dan penugasan
Table transportasinya adalah :
Asal Tujuan Penawaran
T1 T2 T3 T4
A1 2 3 11 7 6
A2 1 0 6 1 1
A3 5 8 15 9 10
Permintaan 7 5 3 2 17
Mencari solusi awal dengan menggunakan metode Vogel’s Approximation
Mencari opportunity cost dan mengalokasikan semaksimal mungkin sesuai dengan permintaan dan penawaran:
Asal Tujuan Penawaran OC. Baris
T1 T2 T3 T4
A1 2 3 11 7 6 1
A2 1 0 6 1 1 1
A3 5 8 15 2 9 10 3
Permintaan 7 5 3 2 17
OC. Kolom 1 3 5 6
Mencari opportunity cost baru :
Asal Tujuan Penawaran OC. Baris
T1 T2 T3 T4
A1 2 3 11 7 6 1
A2 1 0 6 1 1 1
A3 5 8 3 15 2 9 10 3
Permintaan 7 5 3 2 17
OC. Kolom 1 3 5 --
Mencari opportunity cost baru :
Asal Tujuan Penawaran OC. Baris
T1 T2 T3 T4
A1 2 3 11 7 6 1
A2 1 0 6 1 1 1
A3 5 5 8 3 15 2 9 10 3
Permintaan 7 5 3 2 17
OC. Kolom 1 3 -- --
Mengalokasikan semua sisa permintaan dan penawaran :
Asal Tujuan Penawaran
T1 T2 T3 T4
A1 6 2 3 11 7 6
A2 1 1 0 6 1 1
A3 5 5 8 3 15 2 9 10
Permintaan 7 5 3 2 17
Biaya transportasi :
6(2) + 1(1) + 5(8) + 3(15) + 2(9) = 116
Mencari solusi optimal dengan metode MODI
Karena berada dalam kondisi degenerasi, maka harus diberi angka nol pada A2T2, sehingga tabelnya menjadi :
Asal Tujuan Penawaran
T1 T2 T3 T4
A1 6 2 3 11 7 6
A2 1 1 0 0 6 1 1
A3 5 5 8 3 15 2 9 10
Permintaan 7 5 3 2 17
Untuk kotak terisi : dik R1 = 0
C11 = R1 + K1
2 = 0 + K1 K1 = 2
C21 = R2 + K1
1 = R2 + 2 R2 = -1
C22 = R2 + K2
0 = (-1) + K2 K2 = 1
C32 = R3 + K2
8 = R3 + 1 R3 = 7
C33 = R3 + K3
15 = 7 + K3 K3 = 8
C34 = R3 + K4
9 = 7 + K4 K4 = 2
Untuk kotak kosong :
IP X12 = C12 - R1 - K2 = 3 - 0 - 1 = 2
IP X13 = C13 - R1 - K3 = 11 - 0 - 8 = 3
IP X14 = C14 - R1 - K4 = 7 - 0 - 2 = 5
IP X23 = C23 - R2 - K3 = 6 - (-1) - 8 = -1
IP X24 = C24 - R2 - K4 = 1 - (-1) - 2 = 0
IP X31 = C31 - R3 - K1 = 5 - 7 - 2 = -4
Nilai negative dengan angka terbesar terletak pada kotak X31, maka yang harus digeser adalah kotak X31, sehingga tabelnya menjadi :
Asal Tujuan Penawaran
T1 T2 T3 T4
A1 6 2 3 11 7 6
A2 1 1 0 6 1 1
- +
A3 1 5 4 8 3 15 2 9 10
+ -
Permintaan 7 5 3 2 17
Untuk kotak terisi : dik R1 = 0
C11 = R1 + K1
2 = 0 + K1 K1 = 2
C31 = R3 + K1
5 = R3 + 2 R3 = 3
C32 = R3 + K2
8 = 3 + K2 K2 = 5
C22 = R2 + K2
0 = R2 + 5 R2 = -5
C33 = R3 + K3
15 = 3 + K3 K3 = 12
C34 = R3 + K4
9 = 3 + K4 K4 = 6
Untuk kotak kosong :
IP X12 = C12 - R1 - K2 = 3 - 0 - 5 = -2
IP X13 = C13 - R1 - K3 = 11 - 0 - 12 = -1
IP X14 = C14 - R1 - K4 = 7 - 0 - 6 = 1
IP X21 = C21 - R2 - K1 = 1 - (-5) - 2 = 4
IP X23 = C23 - R2 - K3 = 6 - (-5) - 12 = -1
IP X24 = C24 - R2 - K4 = 1 - (-5) - 6 = 0
Nilai negative dengan angka terbesar terletak pada kotak X12, maka yang harus digeser adalah kotak X12, sehingga tabelnya menjadi :
Asal Tujuan Penawaran
T1 T2 T3 T4
A1 2 2 4 3 11 7 6
- +
A2 1 1 0 6 1 1
A3 5 5 8 3 15 2 9 10
+ -
Permintaan 7 5 3 2 17
Untuk kotak terisi : dik R1 = 0
C11 = R1 + K1
2 = 0 + K1 K1 = 2
C12 = R1 + K2
3 = 0 + K2 K2 = 3
C22 = R2 + K2
0 = R2 + 3 R2 = -3
C31 = R3 + K1
5 = R3 + 2 R3 = 3
C33 = R3 + K3
15 = 3 + K3 K3 = 12
C34 = R3 + K4
9 = 3 + K4 K4 = 6
Untuk kotak kosong :
IP X13 = C13 - R1 - K3 = 11 - 0 - 12 = -1
IP X14 = C14 - R1 - K4 = 7 - 0 - 6 = 1
IP X21 = C21 - R2 - K1 = 1 - (-3) - 2 = 2
IP X23 = C23 - R2 - K3 = 6 - (-3) - 12 = -3
IP X24 = C24 - R2 - K4 = 1 - (-3) - 6 = -2
IP X32 = C32 - R3 - K2 = 8 - 3 - 3 = 2
Nilai negative dengan angka terbesar terletak pada kotak X23, maka yang harus digeser adalah kotak X23, sehingga tabelnya menjadi :
Asal Tujuan Penawaran
T1 T2 T3 T4
A1 1 2 5 3 11 7 6
- +
A2 1 0 1 6 1 1
- +
A3 6 5 8 2 15 2 9 10
+ -
Permintaan 7 5 3 2 17
Untuk kotak terisi : dik R1 = 0
C11 = R1 + K1
2 = 0 + K1 K1 = 2
C12 = R1 + K2
3 = 0 + K2 K2 = 3
C31 = R3 + K1
5 = R3 + 2 R3 = 3
C33 = R3 + K3
15 = 3 + K3 K3 = 12
C23 = R2 + K3
6 = R2 + 12 R2 = -6
C34 = R3 + K4
9 = 3 + K4 K4 = 6
Untuk kotak kosong :
IP X13 = C13 - R1 - K3 = 11 - 0 - 12 = -1
IP X14 = C14 - R1 - K4 = 7 - 0 - 6 = 1
IP X21 = C21 - R2 - K1 = 1 - (-6) - 2 = 5
IP X22 = C22 - R2 - K2 = 0 - (-6) - 3 = 3
IP X24 = C24 - R2 - K4 = 1 - (-6) - 6 = 1
IP X32 = C32 - R3 - K2 = 8 - 3 - 3 = 2
Nilai negative dengan angka terbesar terletak pada kotak X13, maka yang harus digeser adalah kotak X13, sehingga tabelnya menjadi :
Asal Tujuan Penawaran
T1 T2 T3 T4
A1 2 5 3 1 11 7 6
- + +
A2 1 0 1 6 1 1
A3 7 5 8 1 15 2 9 10
+ - -
Permintaan 7 5 3 2 17
Untuk kotak terisi : dik R1 = 0
C12 = R1 + K2
3 = 0 + K2 K2 = 3
C13= R1 + K3
11 = 0 + K3 K3 = 11
C23 = R2 + K3
6 = R2 + 11 R2 = -5
C33 = R3 + K3
15 = R3 + 11 R3 = 4
C31 = R3 + K1
5 = 4 + K1 K1 = 1
C34 = R3 + K4
9 = 3 + K4 K4 = 5
Untuk kotak kosong :
IP X11 = C11 - R1 - K1 = 2 - 0 - 1 = 1
IP X14 = C14 - R1 - K4 = 7 - 0 - 5 = 2
IP X21 = C21 - R2 - K1 = 1 - (-5) - 1 = 5
IP X22 = C22 - R2 - K2 = 0 - (-5) - 3 = 2
IP X24 = C24 - R2 - K4 = 1 - (-5) - 5 = 1
IP X32 = C32 - R3 - K2 = 8 - 4 - 3 = 1
Karena tidak ada lagi nilai negative maka table tersebut sudah optimal dengan biaya transportasi :
5(3) + 1(11) + 1(6) + 7(5) + 1(15) + 2(9) = 100
Table transportasinya adalah :
Gudang Lokasi Proyek Penawaran
L1 L2 L3
G1 5 10 10 35
G2 20 30 20 40
G3 5 8 12 40
Permintaan 45 50 20 115
Mencari solusi awal dengan metode LC :
memilih variable dengan biaya transportasi terkecil dan mengalokasikannya sebanyak mungkin berdasarkan permintaan dan penawaran :
Gudang Lokasi Proyek Penawaran
L1 L2 L3
G1 35 5 10 10 35
G2 20 30 20 40
G3 5 8 12 40
Permintaan 45 50 20 115
selanjutnya :
Gudang Lokasi Proyek Penawaran
L1 L2 L3
G1 35 5 10 10 35
G2 20 30 20 40
G3 10 5 8 12 40
Permintaan 45 50 20 115
selanjutnya
Gudang Lokasi Proyek Penawaran
L1 L2 L3
G1 35 5 10 10 35
G2 20 30 20 40
G3 10 5 30 8 12 40
Permintaan 45 50 20 115
selanjutnya
Gudang Lokasi Proyek Penawaran
L1 L2 L3
G1 35 5 10 10 35
G2 20 30 20 20 40
G3 10 5 30 8 12 40
Permintaan 45 50 20 115
terakhir mengalokasikan semua sisa permintaan dan penawaran
Gudang Lokasi Proyek Penawaran
L1 L2 L3
G1 35 5 10 10 35
G2 20 20 30 20 20 40
G3 10 5 30 8 12 40
Permintaan 45 50 20 115
Biaya transportasi :
35(5) + 20(30) + 20(20) + 10(5) + 30 (8) = 1465
Mencari solusi optimal dengan metode Stepping Stone
Gudang Lokasi Proyek Penawaran
L1 L2 L3
G1 35 5 10 10 35
G2 20 20 30 20 20 40
G3 10 5 30 8 12 40
Permintaan 45 50 20 115
Menghitung indeks sel pada table transportasi yang tidak terpakai :
X12=G1L2-G1L1+G3L1-G3L2
X12=10-5+5-8=2
X13=G1L3-G1L1+G3L1-G3L2+G2L2-G2L3
X13=10-5+5-8+30-20=12
X21=G2L1-G2L2+G3L2-G3L1
X21=20-30+8-5=-7
X33=G3L3-G3L2+G2L2-G2L3
X33=12-8+30-20=14
Nilai negative terbesar yaitu pada X21, maka yang harus digeser adalah kotak X21
Gudang Lokasi Proyek Penawaran
L1 L2 L3
G1 35 5 10 10 35
G2 10 20 10 30 20 20 40
+ -
G3 5 40 8 12 40
- +
Permintaan 45 50 20 115
Selanjutnya menghitung kembali indeks sel tidak terpakai pada table transportasi baru :
X12=G1L2-G1L1+G2L1-G2L2
X12=10-5+20-30=-5
X13=G1L3-G1L1+G2L1-G2L3
X13=10-5+20-20=5
X31=G3L1-G3L2+G2L2-G2L1
X31=5-8+30-20=7
X33=G3L3-G3L2+G2L2-G2L3
X33=12-8+30-20=14
Nilai negative terbesar yaitu pada X12, maka yang harus digeser adalah kotak X12
Gudang Lokasi Proyek Penawaran
L1 L2 L3
G1 25 5 10 10 10 35
- +
G2 20 20 30 20 20 40
+ -
G3 5 40 8 12 40
Permintaan 45 50 20 115
Selanjutnya menghitung kembali indeks sel tidak terpakai pada table transportasi baru :
X13=G1L3-G1L1+G2L1-G2L3
X13=10-5+20-20=5
X22=G2L2-G2L1+G1L1-G1L2
X22=30-20+5-10=5
X31=G3L1-G3L2+G1L2-G1L1
X31=5-8+10-5=2
X33=G3L3-G3L2+G1L2-G1L1+G2L1-G2L3
X33=12-8+10-5+20-20=9
Karena tidak ada lagi nilai negative pada indeks sel, maka table tersebut sudah optimal, dan biaya transportasinya adalah :
25(5) + 10(10) + 20(20) + 20(20) + 40(8) = 1345
Tabel kinerja perawat
Pasien Waktu yang dibutuhkan (jam) perawat dalam
penanganan pasien
Perawat 1 Perawat 2 Perawat 3 Perawat 4
A 3 5 4 3
B 2 1 3 2
C 3 4 2 2
D 4 3 3 4
Mengubah matriks biaya menjadi matriks opportunity Cost yaitu dengan mengurangkan semua angka dengan angka terkecil dalam satu baris
Pasien Waktu yang dibutuhkan (jam) perawat dalam
penanganan pasien
Perawat 1 Perawat 2 Perawat 3 Perawat 4
A 0 2 1 0
B 1 0 2 1
C 1 2 0 0
D 1 0 0 1
Melakukan tes optimalisasi dengan menarik sejumlah minimum garis
Pasien Waktu yang dibutuhkan (jam) perawat dalam
penanganan pasien
Perawat 1 Perawat 2 Perawat 3 Perawat 4
A 0
2
1
0
B 1 0 2 1
C 1 2 0 0
D 1 0 0 1
Karena hanya ada 4 garis, maka table tersebut sudah optimum
Mencari baris atau kolom yang memiliki satu angka nol, yaitu :
Pasien Waktu yang dibutuhkan (jam) perawat dalam
penanganan pasien
Perawat 1 Perawat 2 Perawat 3 Perawat 4
A 0 2 1 0
B 1 0 2 1
C 1 2 0 0
D 1 0 0 1
Maka selanjutnya menjadi :
Pasien Waktu yang dibutuhkan (jam) perawat dalam
penanganan pasien
Perawat 1 Perawat 2 Perawat 3 Perawat 4
A 0 2 1 0
B 1 0 2 1
C 1 2
0
0
D 1 0 0 1
Maka penugasan perawat sehingga total waktu perawatan minimum adalah :
Perawat 1 menangani pasien A dengan waktu 3 jam
Perawat 2 menangani pasien B dengan waktu 1 jam
Perawat 3 menangani pasien D dengan waktu 3 jam
Perawat 4 menangani pasien C dengan waktu 2 jam
Jadi total waktu penanganan pasien yaitu 3 + 1 + 3 + 2 = 9 jam
Table waktu pengerjaan
Produk Mesin
1 2 3 4 5
A 17 10 15 16 20
B 12 9 16 9 14
C 11 16 14 15 12
D 14 10 10 18 17
E 13 12 9 15 11
Mengubah matriks biaya menjadi matriks opportunity Cost yaitu dengan mengurangkan semua angka dengan angka terkecil dalam satu baris
Produk Mesin
1 2 3 4 5
A 7 0 5 6 10
B 3 0 7 0 5
C 0 5 3 4 1
D 4 0 0 8 7
E 4 3 0 6 2
Mengurangkan semua angka dengan angka terkecil dalam satu kolom
Produk Mesin
1 2 3 4 5
A 7 0 5 6 9
B 3 0 7 0 4
C 0 5 3 4 0
D 4 0 0 8 6
E 4 3 0 6 1
Melakukan tes optimalisasi dengan menarik sejumlah minimum garis
Produk Mesin
1 2 3 4 5
A 7 0
5
6
9
B 3 0 7 0 4
C 0
5 3 4 0
D 4 0 0 8 6
E 4 3 0 6 1
Berarti belum optimal karena jumlah garis tidak sama dengan jumlah baris atau kolom.
Mengurangkan semua angka yang belum dilalui oleh garis dengan angka terkecil menambahkan semua angka yang dilewati oleh 2 garis dengan angka terkecil :
Produk Mesin
1 2 3 4 5
A 7-1 0
5
6
9-1
B 3-1 0 7 0 4-1
C 0
5+1 3+1 4+1 0
D 4-1 0 0 8 6-1
E 4-1 3 0 6 1-1
Sehingga tabelnya menjadi :
Produk Mesin
1 2 3 4 5
A 6 0 5 6 8
B 2 0 7 0 3
C 0 6 4 5 0
D 3 0 0 8 5
E 3 3 0 6 0
Kembali melakukan tes optimalisasi dengan menarik sejumlah minimum garis
Produk Mesin
1 2 3 4 5
A 6
0
5
6
8
B 2 0 7 0 3
C 0 6 4 5 0
D 3 0 0 8 5
E 3 3 0 6 0
Berarti sudah optimal.
Mencari baris atau kolom yang memiliki satu angka nol, yaitu :
Produk Mesin
1 2 3 4 5
A 6 0 5 6 8
B 2 0 7 0 3
C 0 6 4 5 0
D 3 0 0 8 5
E 3 3 0 6 0
Maka selanjutnya menjadi :
Produk Mesin
1 2 3 4 5
A 6 0 5 6 8
B 2 0
7 0 3
C 0 6 4 5 0
D 3 0
0 8 5
E 3 3 0
6 0
Ket = angka nol yang sudah tidak memungkinkan lagi
Maka penugasan yang paling optimal adalah :
Produk A dikerjakan pada Mesin 2 dengan waktu 10 menit
Produk B dikerjakan pada Mesin 4 dengan waktu 9 menit
Produk C dikerjakan pada Mesin 1 dengan waktu 11 menit
Produk D dikerjakan pada Mesin 3 dengan waktu 10 menit
Produk E dikerjakan pada Mesin 5 dengan waktu 11 menit
Jadi total waktu pengerjaan =10 + 9 + 11 + 10 + 11 = 51 menit
Tidak ada komentar:
Posting Komentar