TUGAS 3
MATA KULIAH RISET OPERASI
UNIVERSITAS MUSLIM INDONESIA
OLEH :
A. M. IQRA REZKY HATTA
13020210005
KELAS C1
PRODI TEKNIK INFORMATIKA
FAKULTAS ILMU KOMPUTER
TAHUN 2025
\
Selesaikan soal transportasi di atas menggunakan metode solusi
awal dan solusi optimal Metode NWC dan Least Cost & MODI
Data Tabel Transportasi
Pabrik (P) Toko1 Toko2 Toko3 Penawaran
Pb1 10 20 20 120
Pb2 30 40 - 160
Pb3 10 20 40 140
Permintaan 100 200 120 420
A. Solusi Awal
a.1. Metode Northwest Corner Rule (NWC)
Alokasi dimulai dari pojok kiri atas dan disesuaikan dengan permintaan dan penawaran.
Pabrik (P) Toko1 Toko2 Toko3 Penawaran
Pb1 100 (10) 20 (20) 0 120
Pb2 0 180 (40) - 160
Pb3 0 0 120 (40) 140
Permintaan 100 200 120 420
Total Biaya =
= (100×10) + (20×20) + (180×40) + (120×40)
= 1000 + 400 + 7200 + 4800
= 13,400
a.2. Metode Least Cost Method
Urutkan sel berdasarkan biaya terkecil lalu alokasikan sebanyak mungkin.
Urutan berdasarkan biaya terkecil:
1. Pb1–T1 (10), Pb3–T1 (10)
2. Pb1–T2 (20), Pb3–T2 (20)
3. Pb1–T3 (20), Pb2–T1 (30), Pb2–T2 (40), Pb3–T3 (40)
Langkah Alokasi :
Pabrik (P) Toko1 Toko2 Toko3 Penawaran
Pb1 100 (10) 20 (20) 0 120
Pb2 0 180 (40) 0 160
Pb3 0 0 120 (40) 140
Permintaan 100 200 120 420
Total Biaya =
(100×10) + (20×20) + (180×40) + (120×40)
= 13,400
B. Solusi Optimal dengan MODI (Modified Distribution Method)
Langkah-langkah:
1. Buat tabel alokasi awal dari Least Cost (karena efisien).
2. Hitung nilai u dan v dari tiap baris dan kolom.
3. Hitung nilai opportunity cost (Δij = Cij - (ui + vj)) untuk semua sel kosong.
4. Jika semua Δij ≥ 0, maka solusi optimal tercapai.
Karena pada solusi awal di atas semua sel terisi secara optimal dan sudah memenuhi
permintaan dan penawaran, kita cek Δij:
Misal:
u1 = 0
v1 = C11 = 10 → v1 = 10
v2 = C12 = 20 → v2 = 20
v3 = C13 = 20 → v3 = 20
Cek baris ke-2 (Pb2):
C22 = 40 = u2 + v2 → u2 = 20
Cek baris ke-3 (Pb3):
C33 = 40 = u3 + v3 → u3 = 20
Δij:
C21 = 30 − (20 + 10) = 0
C23 = NA
C31 = 10 − (20 + 10) = -20
Ada nilai Δij < 0, yaitu Δ31 = -20
Langkah MODI – Iterasi Pertama
1. Alokasi Awal dari Least Cost (digunakan sebagai basis):
Pabrik (P) Toko1 Toko2 Toko3 Penawaran
Pb1 100 (10) 20 (20) - 120
Pb2 - 180 (40) - 160
Pb3 - - 120 (40) 140
Permintaan 100 200 120 420
2. Hitung nilai u dan v (dengan u1 = 0 sebagai acuan)
Gunakan rumus:
Jika alokasi ada di sel (i,j), maka: Cij = ui + vj
C11 = 10 → u1 + v1 = 10 → u1 = 0 ⇒ v1 = 10
C12 = 20 → u1 + v2 = 20 → u1 = 0 ⇒ v2 = 20
C22 = 40 → u2 + v2 = 40 → v2 = 20 ⇒ u2 = 20
C33 = 40 → u3 + v3 = 40 → u3 = 20, v3 = 20
3. Hitung Δ (Opportunity Cost) untuk sel kosong
Δij = Cij − (ui + vj)
Sel (i,j) Cij Ui + vj Δij
C21 30 20 + 10 = 30 0
C23 30 20 + 20 = 40 -10
C31 10 20 + 10 = 30 -20
C32 20 20 + 20 = 40 -30
Karena ada Δij < 0, solusi belum optimal.
🔄 Langkah 4: Pilih Sel Δij Terkecil → C31 = -20
Kita akan optimasi alokasi di sekitar sel (3,1) (Pb3–Toko1), karena punya Δ terkecil (-20).
Buat loop segiempat (±) di sekitar sel (3,1) dengan arah bergantian:
Tambah ( + ) di (3,1)
Kurang ( – ) di (1,1)
Tambah ( + ) di (1,2)
Kurang ( – ) di (2,2)
Tambah ( + ) di (2,3)
Kurang ( – ) di (3,3)
Alokasi minimum pada simpul minus = min(100, 20, 180, 120) = 20
Update Alokasi
Pabrik (P) Toko1 Toko2 Toko3 Penawaran
Pb1 80 (100) 40 (20) - 120
Pb2 - 160 (40) 20 (30) 160
Pb3 20 (10) - 100 (40) 140
Permintaan 100 200 120 420
🔍 Hitung Total Biaya Baru
= (80×10) + (40×20) + (160×40) + (20×30) + (20×10) + (100×40)
= 800 + 800 + 6400 + 600 + 200 + 4000
= 12,800
Biaya Baru = 12,800 < 13,400
# Re-import necessary packages after kernel reset
import numpy as np
from [Link] import linear_sum_assignment
# Data waktu pengerjaan (biaya) dari tabel (metode minimisasi)
cost_matrix = [Link]([
[210, 150, 180, 130],
[140, 160, 200, 190],
[150, 175, 220, 200],
[200, 115, 160, 190]
])
# Karena ini kasus maksimasi, kita ubah menjadi minimisasi dengan cara:
# maksimum - nilai asli
max_value = cost_matrix.max()
profit_matrix = max_value - cost_matrix
# Gunakan metode Hungarian untuk optimasi
row_ind, col_ind = linear_sum_assignment(profit_matrix)
# Hitung total keuntungan maksimum dan pasangan penugasan
total_benefit = cost_matrix[row_ind, col_ind].sum()
assignments = list(zip(row_ind, col_ind))
total_benefit, assignments
Hasil
(780, [(0, 0), (1, 1), (2, 2), (3, 3)])
Berdasarkan perhitungan menggunakan metode penugasan (Hungarian Method) untuk kasus
maksimasi, berikut hasilnya:
Penugasan Optimal
Pekerjaan Mesin Yang ditugaskan Biaya/Waktu
J1 Mesin1 210
J2 Mesin2 160
J3 Mesin3 270
J4 Mesin4 190
Total Maksimum Nilai Penugasan (Keuntungan/Produktivitas):
780