Masalah Transportasi Memaksimumkan

Halo Sixtyfourians! Dalam Riset Operasi (Operations Research), kita sering bertemu dengan masalah transportasi yang bertujuan untuk meminimumkan biaya. Namun, bagaimana jika tujuannya adalah untuk mendapatkan keuntungan sebesar-besarnya?. Inilah yang disebut dengan Masalah Transportasi Pola Memaksimumkan. Pada postingan kali ini, kita akan membahas cara menyelesaikannya.

Apa Itu Masalah Transportasi Pola Memaksimumkan?

Berbeda dengan pola minimum yang fokus pada biaya (cost), pola maksimum biasanya berkaitan dengan keuntungan (profit), pendapatan, atau efisiensi kerja. Bentuk Umum Model Matematikanya:

Tujuannya adalah Memaksimumkan f = ΣΣ(Cᵢⱼ·Xᵢⱼ)

Dengan kendala (constraints):

• Barang yang keluar dari pabrik tidak boleh melebihi stok.

• Barang yang sampai ke tujuan harus sesuai permintaan.

• Jumlah barang tidak boleh minus (X ≥ 0).

Dua Cara Mencari Solusi

Ada dua pendekatan utama untuk menyelesaikan masalah ini:

• Mengubah menjadi Pola Minimum: Mengonversi masalah maksimasi menjadi minimasi agar bisa diselesaikan dengan metode standar.

• Prosedur Memaksimumkan Langsung: Menyelesaikan langsung dengan aturan yang disesuaikan untuk maksimasi.

Mari kita bahas satu per satu.

Metode 1: Mengubah Menjadi Pola Minimum

Cara ini paling sering digunakan jika sudah terbiasa dengan metode minimasi (seperti Least Cost atau VAM standar). Langkahnya: Lakukan transformasi pada matriks keuntungan (Cᵢⱼ) menjadi matriks biaya semu (C̅ᵢⱼ) dengan rumus:

C̅ᵢⱼ = P – Cᵢⱼ

• P adalah sembarang bilangan yang sangat besar (harus memenuhi P ≥ Cᵢⱼ untuk semua sel). Biasanya diambil nilai Cᵢⱼ terbesar dalam tabel.

• Setelah diubah, selesaikan tabel tersebut dengan prosedur meminimumkan biasa.

• Solusi optimal yang didapat akan sama dengan solusi maksimalnya.

Rumus Nilai Maksimum Akhir:

f max = (P·Σaᵢ) – f*

Metode 2: Prosedur Memaksimumkan Langsung

Jika tidak ingin mengubah matriks, kita bisa menghitung langsung dengan sedikit penyesuaian pada algoritmanya.

A. Menyusun Solusi Awal

• Metode VAM Modifikasi

Jika menggunakan metode VAM (Vogel Approximation Method) untuk maksimasi, aturannya adalah:

1. Hitung selisih dua nilai Cᵢⱼ terbesar pada setiap baris dan kolom.

2. Pilih baris/kolom dengan selisih terbesar.

3. Isi alokasi pada kotak dengan nilai Cᵢⱼ terbesar di baris/kolom terpilih tersebut (ini kebalikan dari minimasi yang memilih biaya terkecil).

• Metode Most Profit

Alternatif lainnya kita bisa menggunakan metode Most Profit yang merupakan kebalikan dari Least Cost, dimana pengisian dimulai dari sel dengan keuntungan terbesar,

B. Uji Keoptimuman (Metode MODI)

Setelah tabel awal terisi, lakukan uji optimalitas:

Tentukan nilai baris (Uᵢ) dan kolom (Vⱼ) dengan rumus: Cᵢⱼ = Uᵢ + Vⱼ (pada sel isi).

Hitung Indeks Perbaikan (IP) untuk sel kosong: I = Uᵢ + Vⱼ – Cᵢⱼ

Kriteria Pivot: Pilih kotak kosong dengan IP Negatif Terbesar sebagai titik tolak perbaikan.

Kriteria Henti: Solusi optimal tercapai jika semua nilai I ≥ 0.

Contoh Soal

Sebuah perusahaan memiliki 3 orang pekerja (O1, O2, O3) dan 3 cara pengemasan (D1, D2, D3):

D1: Cara Tradisional

D2: Cara Setengah Mesin

D3: Cara Mesin Penuh

Setiap pekerja memiliki efisiensi kerja yang berbeda (jumlah unit per jam) tergantung cara yang digunakan. Datanya adalah sebagai berikut:

Pekerja	D1 (Trad)	D2 (1/2 Mesin)	D3 (Mesin)	Kapasitas (ai​)
O1	4	3	2	40
O2	5	4	6	40
O3	2	7	5	40
Kebutuhan (bj​)	50	50	20	Total: 120

Keterangan:

Cᵢⱼ (angka di dalam kotak): Efisiensi kerja (unit/jam).

Tujuannya: Mengatur penugasan pekerja agar total unit produk yang dihasilkan maksimum.

Cara 1 : Mengubah Menjadi Pola Minimum

Dalam soal, efisiensi terbesar adalah 7, kurangkan masing-masing dari 7 menjadi:

Isikan sehingga diperoleh PBFA:

Ketika dicek, PBFA ini sudah optimal.

f max = 7·120 – (3·30 + 4·10 + 2·20 + 1·20 + 0·40) = 840 – 190 = 650.

Cara 2: Memaksimumkan Langsung

Cara memaksimumkan langsung juga memberikan hasil yang sama.

f max = 4·30 + 3·10 + 5·20 + 6·20 + 7·40 = 650.