Leave a Comment / Matematika Bisnis / By

Module 08: Linear Programming

Optimasi Sumber Daya Bisnis: Metode Sudut, Simpleks, dan Dualitas. Materi LEAN dengan visualisasi SVG native.

📺 Video Pembelajaran

Tonton video ini untuk pemahaman visual yang lebih baik tentang konsep pemrograman linear.

7.1 Pertidaksamaan Linear & Daerah Layak (Feasible Region)

Pemrograman linear dimulai dengan memodelkan batasan (kendala) sumber daya sebagai pertidaksamaan linear. Irisan dari semua pertidaksamaan ini membentuk daerah layak (feasible region), yaitu kumpulan semua solusi yang mungkin.

Bentuk Umum: ax + by ≤ c, dengan x ≥ 0, y ≥ 0
x (Produk A) y (Produk B) Titik Sudut
📌 Contoh Kasus UMKM (Produksi Keripik):
UMKM memproduksi Keripik A (x) dan Keripik B (y).
Kendala Tepung: 2x + y ≤ 100 kg
Kendala Minyak: x + 2y ≤ 80 liter
Non-negativitas: x ≥ 0, y ≥ 0
Daerah layak adalah area yang diarsir di atas. Setiap titik di dalam atau di batas area ini adalah kombinasi produksi yang memungkinkan tanpa melebihi sumber daya.
7.2 Metode Titik Sudut (Corner-Point Method)

Teorema fundamental pemrograman linear menyatakan: Jika solusi optimal ada, ia pasti terletak di salah satu titik sudut (corner point) dari daerah layak. Kita cukup mengevaluasi fungsi tujuan (objective function) di setiap titik sudut.

Maksimumkan Z = cx + dy, subjek pada kendala.
📌 Contoh Kasus E-commerce (Maksimisasi Laba):
Fungsi Laba: Z = 50.000x + 40.000y
Titik Sudut Daerah Layak: (0,0), (50,0), (40,20), (0,40).
Evaluasi:
• Z(0,0) = 0
• Z(50,0) = 2.500.000
• Z(40,20) = 2.000.000 + 800.000 = 2.800.000 (Maksimum)
• Z(0,40) = 1.600.000
Keputusan optimal: Produksi 40 unit Produk A dan 20 unit Produk B untuk laba maksimum Rp 2.800.000.
7.3 Metode Simpleks (Simplex Method)

Untuk masalah dengan lebih dari 2 variabel, metode grafik tidak mungkin digunakan. Metode Simpleks adalah algoritma matriks yang secara sistematis bergerak dari satu titik sudut layak ke titik sudut lainnya yang lebih baik, hingga solusi optimal tercapai.

Variabel Slack (s): Mengubah pertidaksamaan ≤ menjadi persamaan. Contoh: 2x + y + s = 100
📌 Contoh Kasus Riset Bisnis (Alokasi Budget Iklan):
Maksimumkan Z = 3x + 2y (dalam jutaan)
Kendala: x + y ≤ 10 (Budget), 2x + y ≤ 14 (Waktu), x, y ≥ 0.
Tabel Simpleks Awal akan memiliki variabel slack s1 dan s2. Algoritma akan memilih variabel masuk (kolom dengan indikator negatif terbesar) dan variabel keluar (rasio terkecil), lalu melakukan operasi baris elementer (OBE) hingga semua indikator baris tujuan ≥ 0.
Metode ini sangat efisien dan menjadi dasar dari hampir semua solver optimasi di software bisnis modern (seperti Excel Solver atau Python PuLP).
7.4 & 7.5 Minimisasi & Variabel Artifisial

Untuk kendala ≥ atau =, kita menggunakan variabel surplus (dikurangkan) dan variabel artifisial (ditambahkan dengan bobot hukuman ‘M’ yang sangat besar) untuk mendapatkan solusi layak awal. Untuk minimisasi, kita cukup memaksimumkan negatif dari fungsi tujuan: Min Z ≡ Max (−Z).

📌 Contoh Kasus Logistik (Minimisasi Biaya Pengiriman):
Minimalkan Biaya C = 5x + 8y
Kendala: 2x + 3y ≥ 12 (Permintaan minimum), x, y ≥ 0.
Persamaan: 2x + 3y − s1 + a1 = 12.
Fungsi Tujuan Baru: Maksimumkan W = −5x − 8y − Ma1.
Variabel artifisial ‘a1‘ dipaksa menjadi 0 oleh algoritma simpleks karena koefisien ‘M’ yang sangat besar, memastikan solusi akhir tetap layak untuk masalah asli.
7.6 Dualitas & Harga Bayangan (Shadow Price)

Setiap masalah maksimisasi (Primal) memiliki pasangan masalah minimisasi (Dual). Solusi optimal dari Dual memberikan Harga Bayangan (Shadow Price), yaitu nilai marginal dari satu unit tambahan sumber daya.

Jika Primal: Max Z = CX subjek AX ≤ B, maka Dual: Min W = BTY subjek ATY ≥ CT
📌 Contoh Kasus Perencanaan Pensiun 2027 (Evaluasi Sumber Daya):
Anda mengelola portofolio investasi dengan kendala waktu dan modal. Solusi dual menunjukkan harga bayangan untuk “Modal” adalah 0,15.
Artinya, setiap tambahan Rp 1.000.000 modal yang Anda suntikkan akan meningkatkan nilai portofolio optimal sebesar Rp 150.000. Jika biaya mendapatkan modal tambahan lebih murah dari 15%, Anda harus melakukannya. Ini adalah alat pengambilan keputusan strategis yang sangat kuat.
📝 Latihan Soal Pilihan (per Section)

Klik pada setiap soal untuk melihat jawaban dan pembahasan singkat.

Soal 1 (7.2): Daerah layak memiliki titik sudut (0,0), (6,0), (4,3), dan (0,5). Fungsi tujuan: Max Z = 4x + 5y. Berapa nilai maksimum Z?
Jawaban: 31
Pembahasan: Evaluasi di setiap titik:
Z(0,0) = 0
Z(6,0) = 24
Z(4,3) = 4(4) + 5(3) = 16 + 15 = 31 (Maksimum)
Z(0,5) = 25.
Soal 2 (7.3): Dalam tabel simpleks, apa arti jika semua indikator di baris tujuan sudah bernilai ≥ 0?
Jawaban: Solusi optimal telah tercapai.
Pembahasan: Tidak ada variabel non-basis yang dapat masuk untuk meningkatkan nilai fungsi tujuan lebih lanjut. Iterasi simpleks berhenti di sini.
Soal 3 (7.5): Ubah masalah Min Z = 3x + 2y menjadi masalah maksimisasi.
Jawaban: Max W = −3x − 2y
Pembahasan: Meminimumkan Z sama dengan memaksimumkan negatif dari Z. Nilai minimum Z adalah negatif dari nilai maksimum W.
Soal 4 (7.6): Jika harga bayangan (shadow price) untuk kendala tenaga kerja adalah Rp 50.000, apa artinya?
Jawaban: Setiap penambahan 1 jam tenaga kerja akan meningkatkan laba optimal sebesar Rp 50.000.
Pembahasan: Ini berlaku selama penambahan tersebut berada dalam rentang kelayakan (allowable increase) di mana basis solusi optimal tidak berubah.

🎯 Chapter 7 Review Problems (Komprehensif)

Soal-soal kunci untuk menguji penguasaan konsep pemrograman linear. Klik untuk melihat pembahasan.

Review 1: Formulasi Masalah (UMKM)
Soal: Sebuah toko online menjual Paket Hemat (x) dan Paket Premium (y). Laba per paket masing-masing Rp 20.000 dan Rp 30.000. Kendala gudang: x + 2y ≤ 100. Kendala berat: 2x + y ≤ 120. x, y ≥ 0. Tuliskan fungsi tujuan dan kendalanya.
🔍 Lihat Pembahasan
Fungsi Tujuan: Maksimumkan Z = 20.000x + 30.000y
Kendala:
1) x + 2y ≤ 100 (Gudang)
2) 2x + y ≤ 120 (Berat)
3) x ≥ 0, y ≥ 0 (Non-negativitas)
Review 2: Metode Titik Sudut
Soal: Dari soal di atas, temukan titik sudut daerah layak dan tentukan kombinasi produksi untuk laba maksimum.
🔍 Lihat Pembahasan
Titik Sudut:
• (0, 0) → Z = 0
• (60, 0) → Z = 1.200.000
• (0, 50) → Z = 1.500.000
• Perpotongan: x + 2y = 100 dan 2x + y = 120 → x = 140/3 ≈ 46,67, y = 80/3 ≈ 26,67.
Z(46,67; 26,67) = 20.000(140/3) + 30.000(80/3) = 2.800.000/3 + 2.400.000/3 = 5.200.000/3 ≈ 1.733.333.
Keputusan: Produksi sekitar 47 Paket Hemat dan 27 Paket Premium (dengan penyesuaian bilangan bulat jika diperlukan).
Review 3: Variabel Slack
Soal: Ubah pertidaksamaan 3x + 4y ≤ 24 menjadi persamaan menggunakan variabel slack.
🔍 Lihat Pembahasan
Jawaban: 3x + 4y + s = 24, dengan s ≥ 0.
Interpretasi: ‘s’ mewakili jumlah sumber daya yang tidak terpakai (idle capacity). Jika x=4 dan y=2, maka s = 24 − (12 + 8) = 4.
Review 4: Dualitas
Soal: Tuliskan masalah Dual dari Primal berikut:
Maksimumkan Z = 5x1 + 6x2
Kendala: x1 + 2x2 ≤ 10, 3x1 + x2 ≤ 15, x1, x2 ≥ 0.
🔍 Lihat Pembahasan
Masalah Dual:
Minimumkan W = 10y1 + 15y2
Kendala:
1) y1 + 3y2 ≥ 5
2) 2y1 + y2 ≥ 6
3) y1, y2 ≥ 0
Nilai minimum W akan sama persis dengan nilai maksimum Z pada solusi optimal.
Review 5: Interpretasi Solusi Simpleks
Soal: Pada tabel simpleks akhir, nilai variabel slack s1 adalah 0, dan s2 adalah 5. Apa artinya secara bisnis?
🔍 Lihat Pembahasan
Jawaban:
• s1 = 0: Kendala pertama bersifat binding (mengikat). Sumber daya pertama telah digunakan sepenuhnya. Harga bayangannya kemungkinan > 0.
• s2 = 5: Kendala kedua bersifat non-binding. Masih ada 5 unit sumber daya kedua yang menganggur (tidak terpakai). Harga bayangannya pasti 0.
Catatan Efisiensi: Pemrograman linear bukan sekadar teori akademis. Kemampuan memformulasikan masalah bisnis nyata (seperti alokasi budget, jadwal produksi, atau strategi investasi pensiun) ke dalam model matematis adalah keterampilan tingkat tinggi yang membedakan manajer biasa dengan pengambil keputusan strategis. Gunakan modul ini sebagai referensi saat Anda merancang model optimasi untuk aurinoworks.com.
🎨

Studi Kasus Visual: Produksi Kursi & Meja

Masalah: Maksimalkan Profit $Z = 3x + 2y$ (x: Kursi, y: Meja) dengan kendala:

  • Tenaga Kerja: $2x + y \le 8$
  • Bahan Baku: $2x + 3y \le 12$
Langkah Strategis:
  1. Gambar Garis Kendala: Tentukan titik potong (intercept) tiap garis.
    Garis 1: (0,8) dan (4,0). Garis 2: (0,4) dan (6,0).
  2. Arsir Feasible Region: Daerah di bawah kedua garis tersebut (karena tanda $\le$).
  3. Cari Titik Pojok (Corner Points):
    • A (0,0)
    • B (4,0) – Potongan Garis 1 dengan sumbu x
    • C (3,2) – Titik temu kedua garis (hitung dengan eliminasi!)
    • D (0,4) – Potongan Garis 2 dengan sumbu y
  4. Uji Profit di Setiap Titik:
    Z(A) = 0 | Z(B) = 12 | Z(C) = 13 (Optimal!) | Z(D) = 8

Insight: Manajer harus memproduksi 3 kursi dan 2 meja untuk mencapai profit tertinggi $13. Titik lain mungkin “layak”, tapi tidak “maksimal”.

🤔 Pikir: Apa itu Slack sebenarnya?

Dalam bisnis, Slack ($s$) adalah sumber daya yang “menganggur” atau sisa kapasitas.

Persamaan: 2x + y + s₁ = 8
  • Jika s₁ = 0: Artinya sumber daya terpakai habis (Binding Constraint).
  • Jika s₁ > 0: Artinya ada sisa kapasitas yang tidak menghasilkan profit.

Tugas Manajer: Meminimalkan Slack pada sumber daya yang mahal!

Eksekusi: Ritual Pivot Simplex

Gunakan tabel dari materi di atas. Bagaimana kita memulainya?

Langkah 1: Menentukan “Jalan Pintas” Tercepat

Lihat baris Z: Ada angka -3 dan -2.
Pilih -3 (Kolom x) sebagai Kolom Pivot. Ini adalah produk yang memberi profit terbesar per unit.

Langkah 2: Menemukan Penghambat (Bottleneck)

Bagi RHS dengan angka di Kolom Pivot:

  • Baris s₁: 8 / 2 = 4
  • Baris s₂: 12 / 2 = 6

Pilih yang terkecil (4). Maka Baris s₁ adalah Baris Pivot. Elemen Pivot kita adalah angka 2.

Langkah 3: Transformasi (Tindak)

Bagi seluruh Baris s₁ dengan angka 2 (Pivot) agar menjadi 1. Lalu gunakan baris baru ini untuk menolkan angka lain di kolom x.
Hasilnya: Variabel x masuk menggantikan s₁ dalam basis.

🎯 Quiz: Strategi Operasional

Soal:

Jika hasil akhir Tabel Simplex menunjukkan $s₂ = 15$, apa artinya bagi manajer pabrik?

👁️ Lihat Analisis
Artinya terdapat 15 unit sumber daya ke-2 yang tidak terpakai. Keputusannya:
1. Kurangi pemesanan bahan baku s₂ untuk menghemat biaya, atau
2. Cari produk baru yang bisa memanfaatkan kelebihan s₂ tersebut.

📋 Kasus 1: Optimasi Produksi Furnitur

Masalah: Sebuah pabrik memproduksi Meja (x) dan Kursi (y).
Fungsi Profit: Z = 3x + 2y (dalam jutaan Rupiah).

Kendala Sumber Daya:

  • Tenaga Kerja: 2x + y ≤ 100 (Maks 100 jam)
  • Bahan Baku: x + y ≤ 80 (Maks 80 unit kayu)
  • Non-Negativitas: x, y ≥ 0
Langkah-Langkah Pengerjaan:
  1. Gambar Garis Kendala:
    • Garis 1 (2x + y = 100): Jika x=0, y=100. Jika y=0, x=50. Titik: (0, 100) dan (50, 0).
    • Garis 2 (x + y = 80): Jika x=0, y=80. Jika y=0, x=80. Titik: (0, 80) dan (80, 0).
  2. Tentukan Area Layak (Feasible Region): Arsir daerah yang memenuhi kedua pertidaksamaan (di bawah kedua garis).
  3. Identifikasi Titik Pojok (Vertices):
    • Titik A: (0, 0)
    • Titik B: (50, 0) – Potongan Garis 1 dengan sumbu x.
    • Titik C: (20, 60) – Titik potong Garis 1 & 2 (hitung dengan eliminasi).
    • Titik D: (0, 80) – Potongan Garis 2 dengan sumbu y.
  4. Uji Nilai Z pada Setiap Titik Pojok:
    • Z(A) = 3(0) + 2(0) = 0
    • Z(B) = 3(50) + 2(0) = 150
    • Z(C) = 3(20) + 2(60) = 180 (MAKSIMAL)
    • Z(D) = 3(0) + 2(80) = 160

Kesimpulan: Untuk profit maksimal Rp180 Juta, produksi 20 Meja dan 60 Kursi.

📊 Kasus 2: Algoritma Simpleks (Standard Form)

Masalah: Maksimalkan Z = 5x₁ + 4x₂

Kendala:

  • x₁ + x₂ ≤ 20
  • 2x₁ + x₂ ≤ 35
  • x₁, x₂ ≥ 0
Langkah Pengerjaan:
  1. Ubah ke Bentuk Standar: Tambahkan Slack Variables (s₁, s₂).
    • x₁ + x₂ + s₁ = 20
    • 2x₁ + x₂ + s₂ = 35
    • -5x₁ – 4x₂ + Z = 0
  2. Susun Tabel Awal (Tableau):
    Basicsx₁x₂s₁s₂RHS
    s₁111020
    s₂210135
    Z-5-4000
  3. Pilih Kolom & Baris Pivot:
    • Kolom Pivot: x₁ (karena -5 adalah negatif terbesar).
    • Baris Pivot: Hitung rasio RHS/Pivot (20/1=20, 35/2=17.5). Pilih yang terkecil (17.5). Maka Baris s₂ adalah pivot.
  4. Iterasi (Eliminasi Gauss-Jordan):
    • Ubah elemen pivot (angka 2) menjadi 1 dengan membagi baris s₂ dengan 2.
    • Nolkan elemen lain di kolom x₁ menggunakan operasi baris.
  5. Hasil Akhir: Ulangi sampai baris Z tidak ada lagi yang negatif.
    Setelah iterasi selesai, didapat: x₁ = 15, x₂ = 5, sehingga Z = 95.
⌨️

Lab Praktik: Excel Sebagai “Kertas Kerja” Digital

Dalam sesi ini, kita tidak akan menggunakan fitur otomatis. Kita akan menggunakan Excel sebagai media untuk melakukan Operasi Baris Dasar (OBD) secara manual agar Anda memahami setiap pergeseran di dalam Tabel Simpleks.

Filosofi Coba-Pikir-Tindak:
  • Coba: Susunlah Tabel Simpleks awal di atas grid Excel. Gunakan alamat sel (misal: =A10/B10) untuk menghitung rasio.
  • Pikir: Analisis baris Z secara manual. Tentukan kolom pivot berdasarkan logika “profit terbesar”, bukan klik tombol otomatis.
  • Tindak: Eksekusi OBD dengan rumus Excel (seperti =Baris_Lama - (Koefisien * Baris_Pivot)) untuk menghasilkan tabel baru.

“Tonton bagaimana saya mentransformasi tabel simpleks langkah demi langkah menggunakan kekuatan rumus sel Excel.”

Keuntungan Metode Ini:

Dengan metode ini, Anda tidak akan pernah tersesat dalam hitungan pecahan yang rumit, namun otak Anda tetap menjadi Verifikator Akhir yang menentukan arah algoritma. Inilah cara membangun intuisi seorang manajer yang menguasai teknologi, bukan dikuasai teknologi.

Module 07 – Mid-Semester Review
MAT BIS
Module 09 – Limits & Continuity

Leave a Comment

Your email address will not be published. Required fields are marked *