Program Studi Manajemen • FEB UNDIP
Matematika Bisnis Pertemuan 12 — Linear Programming: Ketika produk bertambah menjadi tiga atau lebih, grafik tidak cukup — kita butuh metode simpleks dan bantuan spreadsheet.
RPS Minggu 13 • Sub-CPMK 4 • Durasi 2 × 50 Menit
Pertemuan ke-12 tatap muka; Minggu RPS ke-13 karena Minggu 8 = UTS
Selamat datang di Pertemuan 12. Di pertemuan sebelumnya kita sudah belajar bagaimana menyelesaikan masalah LP (linear programming — pemrograman linear) dengan dua variabel keputusan menggunakan metode grafis — kita gambar daerah fisibel, cari titik-titik pojok, lalu evaluasi fungsi tujuan di setiap pojok. Metode itu elegan dan intuitif, tetapi bayangkan situasi nyata: sebuah pabrik makanan ringan di Jawa Tengah memproduksi keripik, kacang goreng, dan biskuit sekaligus — tiga variabel keputusan, bukan dua. Grafiknya sudah tidak bisa digambar di bidang datar lagi. Hari ini kita pelajari alat yang benar untuk situasi ini: metode simpleks (metode iteratif untuk memecahkan LP dengan banyak variabel), sebuah algoritma sistematik yang bisa menangani puluhan variabel dan kendala — dan kita akan pelajari juga bagaimana Excel Solver mengotomatiskan proses tersebut. Siapkan kalkulator dan buka laptop Anda. Tujuan Pembelajaran & Peta Alur Setelah pertemuan ini, Anda diharapkan mampu memecahkan LP lebih dari dua variabel (Sub-CPMK 4). Secara rinci:
Kemampuan 1
01
Merumuskan model LP tiga variabel dari deskripsi verbal
Kemampuan 2
02
Menjelaskan keterbatasan metode grafis untuk n > 2
Kemampuan 3
03
Menyusun tabel simpleks & melakukan iterasi pivot
Kemampuan 4
04
Menggunakan Excel Solver & menginterpretasikan hasilnya
Blok 1 Keterbatasan Grafis
→
Blok 2 Tabel Simpleks
→
Blok 3 Dua Kasus dari Nol
→
Blok 4 Excel Solver
Mari kita lihat peta perjalanan kita hari ini. Ada empat blok materi yang akan kita lalui secara berurutan — saya sengaja merancang urutan ini seperti membangun sebuah gedung: fondasi dulu (kenapa kita butuh metode baru), lalu batu bata (komponen tabel simpleks), lalu konstruksi penuh (dua kasus dari nol), dan akhirnya finishing (otomasi dengan Excel). Keempat kemampuan ini saling berkaitan — Anda tidak bisa menggunakan Solver secara bermakna kalau tidak memahami apa yang dilakukan simpleks di balik layar. Di akhir pertemuan, saya harap Anda tidak hanya bisa menekan tombol di Excel, tetapi juga bisa menjelaskan kepada atasan Anda mengapa angka itu yang keluar dan apa artinya secara bisnis. Mengapa 3 Produk, Bukan 2? UMKM (Usaha Mikro, Kecil, dan Menengah — kategori usaha per PP 7/2021) makanan ringan Jawa Tengah biasanya memproduksi lebih dari dua produk sekaligus.
Keripik Singkong
x₁ — Rp 4.000/kg
Kacang Goreng
x₂ — Rp 5.000/kg
Biskuit Kelapa
x₃ — Rp 3.000/kg
Tiga sumber daya terbatas: bahan baku , jam mesin , kapasitas distribusi . Pertanyaan bisnis: berapa unit tiap produk agar laba maksimal?
Metode grafis Pertemuan 11 tidak bisa diterapkan untuk tiga variabel → butuh algoritma baru.
Saya ingin mulai dengan situasi yang sangat dekat dengan realitas bisnis Jawa Tengah. Bayangkan Anda seorang manajer operasional di CV Rejeki Snack, sebuah UMKM makanan ringan di kawasan Ungaran — mereka memproduksi tiga produk: keripik singkong, kacang goreng, dan biskuit kelapa. Setiap hari, mereka menghadapi keterbatasan bahan baku, jam mesin yang tersedia, dan kapasitas truk distribusi ke minimarket di Semarang dan sekitarnya. Pertanyaannya sama seperti LP biasa: produksi berapa unit tiap produk agar laba maksimal? Bedanya, sekarang ada tiga variabel keputusan, bukan dua — dan segera kita akan lihat bahwa grafik di papan tulis tidak cukup untuk membantu kita menjawab pertanyaan ini. Blok Materi
01
Keterbatasan Grafis
Dari bidang datar ke ruang berdimensi banyak — mengapa grafik tidak cukup
Kita mulai dari fondasi: memahami mengapa kita memerlukan metode baru. Di pertemuan sebelumnya, metode grafis bekerja dengan sempurna untuk dua variabel — kita gambar sumbu x₁ dan x₂, arsir daerah fisibel, dan evaluasi pojok. Tapi coba bayangkan Anda menambah satu variabel keputusan saja — langsung kita butuh sumbu ketiga, dan daerah fisibel bukan lagi bidang datar melainkan volume tiga dimensi. Menggambar itu di papan tulis sudah sangat sulit; untuk empat variabel atau lebih, sama sekali tidak ada representasi visual yang memadai. Blok pertama ini akan menegaskan batasan tersebut dan langsung mengajak Anda merumuskan model LP tiga variabel — supaya kita tahu persis masalah apa yang harus kita pecahkan sebelum kita belajar cara memecahkannya. Metode Grafis: Sampai di Mana? x₁ x₂ Daerah Fisibel A B C Gambar di bidang 2D — sumbu x₁ dan x₂ Daerah fisibel = poligon konveks Solusi optimal = sudut (vertex) terbaik ✓ Praktis secara manual Polihedron 3D n=3 → ruang 3D (sulit digambar) n=4 → hiperruang (tidak bisa divisualisasi) ✗ Tidak praktis untuk n ≥ 3 Kunci: Daerah fisibel LP bersifat konveks (seperti bukit tunggal tanpa lembah). Solusi optimal selalu di salah satu vertex (sudut) . Metode simpleks bergerak dari sudut ke sudut secara sistematik.
Mengapa kita bisa yakin bahwa metode grafis tidak akan berhasil untuk tiga variabel? Jawabannya sederhana secara geometri: setiap variabel keputusan membutuhkan satu dimensi — dua variabel butuh bidang 2D, tiga variabel butuh ruang 3D. Yang tetap sama di semua dimensi adalah prinsip fundamentalnya: solusi optimal LP selalu terletak di salah satu vertex (sudut) dari daerah fisibel, karena daerah fisibel LP bersifat konveks. Konveksitas itu penting: bayangkan mendaki bukit tunggal tanpa lembah tersembunyi — ke mana pun Anda terus mendaki, pasti sampai di puncak tertinggi, tidak ada puncak palsu. Metode simpleks mengeksploitasi konveksitas ini — ia bergerak secara sistematik dari satu vertex ke vertex tetangga yang memberikan Z lebih besar, dan karena tidak ada lembah, gerakan ini pasti menuju puncak. Konsep vertex dan konveks ini penting untuk dipahami sebelum kita masuk ke prosedur algoritmanya. Model LP Tiga Variabel — Struktur Standar Maks/Min Z = c₁x₁ + c₂x₂ + c₃x₃(kendala 1) (kendala 2) (kendala 3) (non-negatif)
xᵢ = Variabel Keputusan
Kuantitas yang dicari (mis. unit produksi)
cᵢ = Koefisien Kontribusi
Laba/biaya per unit variabel di fungsi tujuan
bᵢ = RHS (Right-Hand Side)
Kapasitas/batas sumber daya ke-i
Sebelum kita masuk ke contoh angka, mari kita pahami struktur umumnya. Fungsi tujuan Z adalah kombinasi linear dari tiga variabel keputusan — perhatikan, strukturnya persis sama dengan LP dua variabel, hanya ditambah satu suku c₃x₃. Kendala-kendala juga linear: setiap kendala menyatakan bahwa penggunaan sumber daya di seluruh produk tidak boleh melebihi kapasitas yang tersedia (bᵢ). Syarat non-negatif x₁, x₂, x₃ ≥ 0 tetap wajib ada — Anda tidak bisa memproduksi jumlah negatif. Yang berubah hanya jumlah variabel dan jumlah kendala — struktur matematisnya identik, dan itulah mengapa metode yang kita pelajari hari ini bisa digeneralisasi ke n variabel dan m kendala berapapun. Istilah RHS (right-hand side — sisi kanan pertidaksamaan) adalah kapasitas batas yang sering kita sebut dalam analisis sensitivitas nanti. Hitung dari Nol 1 — Formulasi LP: Tiga Produk Snack Produk Variabel Laba/kg BhBaku JamMsn Distr. Keripik singkong x₁ Rp 4.000 2 1 1 Kacang goreng x₂ Rp 5.000 3 1 1 Biskuit kelapa x₃ Rp 3.000 1 2 1 Kapasitas/hari 120 kg 80 jam 60 kg
s.t. = subject to (dengan kendala-kendala berikut)
Maks Z = 4x₁ + 5x₂ + 3x₃(dalam ribuan rupiah)
Sekarang kita formulasikan masalah CV Rejeki Snack secara formal. Langkah pertama selalu mengidentifikasi variabel keputusan — di sini tiga variabel: x₁ = kg keripik, x₂ = kg kacang, x₃ = kg biskuit yang diproduksi per hari. Fungsi tujuan adalah total laba, yaitu Rp 4.000×x₁ + Rp 5.000×x₂ + Rp 3.000×x₃ — saya tulis dalam ribuan supaya angkanya lebih bersih. Perhatikan kendala pertama: 2x₁ + 3x₂ + x₃ ≤ 120 — ini berarti setiap kg keripik butuh 2 kg bahan baku, setiap kg kacang butuh 3 kg bahan baku, dan setiap kg biskuit butuh 1 kg bahan baku; total tidak boleh melebihi 120 kg yang tersedia. Kendala ketiga (distribusi) mungkin yang paling intuitif: total produk yang bisa dikirim ke pasar hari itu maksimal 60 kg — bukan karena pabrik tidak bisa produksi lebih, tetapi karena truk distribusinya terbatas. Inilah seni formulasi LP: menerjemahkan narasi bisnis menjadi pertidaksamaan linear. Coba Sendiri: Jalankan Iterasi Simpleks Langkah demi Langkah Klik maju melalui tabel simpleks CV Rejeki Snack — pilih kolom pivot, baris pivot, lalu amati tabel ter-update otomatis tiap iterasi.
Mari kita coba widget ini bersama — silakan satu mahasiswa maju ke depan. Klik untuk memilih kolom pivot (variabel yang masuk), lalu lihat widget otomatis menjalankan min-ratio test untuk menentukan baris pivot (variabel yang keluar). Klik lagi untuk melakukan operasi baris dan amati tabel baru muncul — ulangi sampai tidak ada lagi koefisien negatif di baris tujuan, tandanya solusi optimal tercapai. Widget ini adalah versi interaktif dari tabel simpleks tiga produk snack yang baru saja kita formulasikan. Sekarang mari kita lihat detail konsep simpleks: bergerak dari sudut ke sudut daerah layak. Blok Materi
02
Metode Simpleks
Variabel slack (sisa kapasitas ), tabel standar, dan cara membaca setiap kolom
Kita masuk ke inti pertemuan ini: metode simpleks. Nama "simpleks" berasal dari geometri — simplex adalah bentuk geometri paling sederhana dalam suatu dimensi (segitiga di 2D, tetrahedron di 3D). Algoritma ini dikembangkan oleh George Dantzig pada 1947 dan sampai hari ini tetap menjadi tulang punggung perangkat lunak optimasi di seluruh dunia. Kita akan pelajari metode ini secara manual supaya Anda benar-benar memahami mekanismenya — setelah itu, Blok 4 akan menunjukkan bagaimana Excel Solver mengerjakan hal yang sama dalam hitungan detik. Fokus di Blok 2 ini adalah memahami "bahasa" tabel simpleks: apa itu variabel slack, bagaimana tabel awal dibentuk, dan apa arti setiap sel di dalamnya. Simpleks: Berjalan dari Sudut ke Sudut A(Z=0) B C D E(Z*) Jalur simpleks: A → C → E 1
Mulai dari titik sudut yang mudah: titik asal (0,0,0) — selalu fisibel selama RHS ≥ 0
2
Pindah ke sudut tetangga yang meningkatkan Z — pilih yang paling menguntungkan
3
Berhenti saat tidak ada tetangga lebih baik → solusi optimal ditemukan
Tidak perlu cek semua 2ⁿ kemungkinan sudut — biasanya konvergen dalam beberapa iterasi (satu siklus pivot).
Intuisi di balik metode simpleks sangat elegan. Bayangkan Anda berdiri di salah satu sudut (vertex) daerah fisibel — sudut pertama yang kita pilih biasanya titik asal (semua variabel = 0), yang selalu fisibel selama semua konstanta RHS bernilai positif. Dari sudut itu, Anda melihat ke tetangga-tetangga yang terhubung langsung; jika ada tetangga yang memberikan nilai Z lebih tinggi, Anda pindah ke sana. Anda terus bergerak seperti ini — selalu ke arah yang memperbaiki Z — sampai tidak ada lagi tetangga yang lebih baik. Saat itulah Anda sudah di puncak: solusi optimal ditemukan. Karena daerah fisibel LP bersifat konveks (seperti bukit tunggal tanpa lembah tersembunyi), lokal optimal = global optimal — Anda tidak akan terperangkap di "puncak palsu" seperti pada masalah optimasi non-linear. Kata "iterasi" berarti satu siklus perhitungan yang memindahkan solusi dari satu vertex ke vertex lain yang lebih baik. Variabel Slack — Mengubah ≤ Menjadi = Untuk setiap kendala ≤, tambahkan satu variabel slack sᵢ ≥ 0.
Bentuk Asli (Pertidaksamaan)
2x₁ + 3x₂ + x₃ ≤ 120
Bentuk Standar (Persamaan + Slack)
2x₁ + 3x₂ + x₃ + s₁ = 120s₂ = 80s₃ = 60
s₁ = sisa bahan baku
s₁ > 0 → ada bahan baku menganggur
s₁ = 0 → bahan baku habis (binding )
s₂ = sisa jam mesin
Koefisien di fungsi tujuan = 0
(sisa kapasitas tidak menghasilkan laba)
s₃ = sisa distribusi
Z = 4x₁+5x₂+3x₃+0s₁+0s₂+0s₃
Fungsi tujuan tidak berubah
Metode simpleks bekerja dengan sistem persamaan linear, bukan pertidaksamaan — jadi langkah pertama adalah mengubah semua kendala ≤ menjadi = dengan menambahkan variabel slack. Variabel slack bukan rekayasa matematika semata; ia punya makna ekonomi yang nyata. Misalkan s₁ = 15 — itu berarti dari 120 kg bahan baku yang tersedia, hanya 105 kg yang digunakan, dan masih ada 15 kg bahan baku yang menganggur. Informasi ini sangat berguna untuk keputusan manajerial: kalau s₁ besar, berarti bahan baku bukan bottleneck dan mungkin kita bisa arahkan sumber daya ke kapasitas lain yang lebih ketat. Kendala "binding" (dari Bahasa Inggris: mengikat) berarti slacknya = 0 — sumber daya habis terpakai sepenuhnya dan menjadi pembatas aktif. Perhatikan juga bahwa koefisien slack di fungsi tujuan adalah nol — Anda tidak mendapat laba dari sisa kapasitas yang tidak terpakai, tetapi slack itu tetap harus ada di model supaya sistem persamaannya konsisten. Tabel Simpleks Awal (Initial Simplex Tableau) BV = basic variable (variabel basis: yang "aktif" di solusi saat ini, nilainya = RHS).
BV x₁ x₂ x₃ s₁ s₂ s₃ RHS s₁ 2 3 1 1 0 0 120 s₂ 1 1 2 0 1 0 80 s₃ 1 1 1 0 0 1 60 Z −4 −5 −3 0 0 0 0
Solusi awal: x₁=x₂=x₃=0, s₁=120, s₂=80, s₃=60, Z=0. Semua kapasitas masih penuh — belum produksi apa pun.
Baris Z: koef dinegasikan. Koef −5 di kolom x₂ berarti setiap unit x₂ yang masuk basis menaikkan Z sebesar 5 (rb rupiah). Kolom paling negatif = paling menguntungkan.
Ini adalah inti dari metode simpleks — tabel yang merangkum seluruh sistem persamaan linear kita dalam satu format standar. Mari saya jelaskan setiap bagian. Kolom BV (basic variable) mencatat variabel mana yang saat ini "di dalam basis" — di solusi awal, yang di dalam basis adalah tiga variabel slack (s₁, s₂, s₃), dengan nilai masing-masing sama dengan RHS (s₁=120, s₂=80, s₃=60). Artinya, di titik awal kita belum produksi apa pun (x₁=x₂=x₃=0) dan semua kapasitas masih tersisa penuh. Baris Z adalah cara kita melacak nilai fungsi tujuan — perhatikan koefisiennya dinegasikan: −4 di kolom x₁ berarti setiap unit x₁ yang masuk basis akan meningkatkan Z sebesar 4 (ribuan rupiah). Kolom dengan koefisien baris Z paling negatif adalah kolom yang paling "menguntungkan" untuk dimasukkan ke dalam basis — itulah cara kita memilih langkah berikutnya. Langkah 1 Simpleks: Pilih Kolom Pivot (Entering Variable ) Aturan Maksimasi: Pilih kolom dengan koefisien baris Z paling negatif → variabel tersebut = entering variable .
Kolom Koef Baris Z Keterangan x₁ −4 — x₂ −5 ▲ PALING NEGATIF x₃ −3 —
➜ x₂ terpilih sebagai entering variable . Kolom x₂ = kolom pivot .
Kondisi Berhenti (Optimal): semua koef baris Z ≥ 0 → solusi sudah optimal, berhenti!
Intuisi: koef −5 artinya memasukkan 1 unit x₂ ke basis menaikkan Z sebesar Rp 5.000 — paling besar di antara semua opsi. Karena itu x₂ dipilih pertama.
Langkah pertama setiap iterasi simpleks adalah memilih variabel mana yang akan masuk ke basis — ini disebut entering variable. Aturannya sederhana untuk kasus maksimasi: lihat baris Z, cari koefisien yang paling negatif. Di contoh kita, baris Z menunjukkan −4, −5, −3 untuk x₁, x₂, x₃ — yang paling negatif adalah −5 di kolom x₂, sehingga x₂ terpilih sebagai entering variable. Mengapa paling negatif? Karena koefisien −5 berarti setiap unit x₂ yang diproduksi akan menaikkan Z sebesar 5 ribu rupiah — paling besar pengaruhnya dibanding opsi lain. Perhatikan kondisi berhenti: kalau semua koefisien baris Z sudah ≥ 0, tidak ada variabel yang bisa meningkatkan Z lagi, dan solusi saat ini adalah optimal. Kondisi inilah yang kita tuju di setiap iterasi. Langkah 2 Simpleks: Min-Ratio Test — Pilih Baris Pivot (Leaving Variable ) Hitung rasio RHS ÷ koef kolom pivot (hanya untuk koef > 0 ). Pilih baris dengan rasio minimum positif .
BV Koef x₂ (kolom pivot) RHS Rasio RHS ÷ Koef s₁ 3 120 120 ÷ 3 = 40 ▲ minimum s₂ 1 80 80 ÷ 1 = 80 s₃ 1 60 60 ÷ 1 = 60
Hasil: Rasio minimum = 40 (baris s₁)s₁ adalah leaving variable ; baris s₁ = baris pivot .3 (perpotongan baris s₁ & kolom x₂).
Penting: Koefisien ≤ 0 di kolom pivot diabaikan dalam min-ratio test. Mengambil lebih dari rasio minimum → slack negatif → melanggar fisibilitas.
Setelah kita tahu x₂ akan masuk basis, pertanyaan berikutnya: seberapa banyak x₂ bisa kita naikkan tanpa melanggar satu pun kendala? Jawabannya diberikan oleh min-ratio test. Untuk setiap baris kendala, kita hitung rasio RHS dibagi koefisien di kolom pivot — rasio ini memberitahu kita "batas atas" berapa besar x₂ bisa dinaikkan sebelum kendala baris tersebut menjadi habis. Kita pilih minimum dari semua rasio positif — karena kalau kita ambil lebih dari minimum itu, salah satu slack akan menjadi negatif, yang berarti fisibilitas dilanggar. Di contoh kita: rasio terkecil adalah 40 (dari baris s₁) — artinya x₂ bisa dinaikkan maksimal ke 40 kg sebelum bahan baku habis. Saat itu, s₁ keluar dari basis (nilainya menjadi 0) dan x₂ masuk menggantikannya. Elemen di perpotongan baris pivot dan kolom pivot (yaitu angka 3 dari baris s₁, kolom x₂) disebut elemen pivot dan menjadi pusat operasi baris berikutnya. Langkah 3 Simpleks: Operasi Baris — Menjadikan Pivot = 1 Elemen pivot = 3 (baris s₁, kolom x₂). Tujuan: kolom pivot berbentuk vektor identitas.
LANGKAH A: Bagi Baris Pivot dengan Elemen Pivot (3)
Sel Nilai Lama Operasi Nilai Baru x₁ 2 2 ÷ 3 2/3 x₂ 3 3 ÷ 3 1 ← elemen pivotx₃ 1 1 ÷ 3 1/3 s₁ 1 1 ÷ 3 1/3 s₂ 0 0 ÷ 3 0 s₃ 0 0 ÷ 3 0 RHS 120 120 ÷ 3 40
LANGKAH B: Update Baris Lain (contoh baris s₂)
Baris s₂ baru =
Aturan Tanda Kritis: −1/3 +1/3 Minus dikali minus = plus!
Setelah pivot: x₂ masuk basis , s₁ keluar . Kolom x₂ berbentuk [1,0,0,0]ᴝ.
Sekarang kita lakukan operasi pivot — ini adalah operasi aljabar linear yang mungkin sudah pernah Anda temui dengan nama eliminasi Gauss-Jordan. Sebelum mengerjakan seluruh baris sekaligus, mari kita fokus ke satu sel dulu agar tidak ada yang tersesat. Ambil sel pertama baris s₁ di kolom x₁ (angka 2): setelah dibagi 3, hasilnya 2/3. Lakukan ini untuk setiap sel — perhatikan sel di kolom s₁ (angka 1): 1/3. Setelah baris pivot selesai, kita proses baris lain. Baris s₂ punya koefisien 1 di kolom x₂ (kolom pivot), jadi: baris s₂ baru = baris s₂ lama − 1 × baris pivot baru. Aturan tanda yang sering membingungkan: kalau ada −(−1/3), itu sama dengan +1/3 — minus dikali minus menghasilkan plus. Satu slip tanda bisa menghasilkan tabel yang sama sekali berbeda, jadi periksa setiap sel secara satu-satu. Setelah semua operasi selesai, kolom x₂ akan berbentuk vektor identitas dari atas ke bawah — tanda bahwa x₂ sudah masuk basis dengan nilai yang sama dengan RHS baris pivot (40). Blok Materi
03
Dua Studi Kasus
Keripik-Kacang-Biskuit (maksimasi, 3 iterasi) & Distribusi FMCG (minimasi)
Blok ini adalah puncak teknis pertemuan kita. Kita akan menjalani dua kasus lengkap dari awal sampai akhir — ini bukan demonstrasi cepat; kita akan menuliskan setiap angka di setiap sel tabel, menghitung setiap rasio, dan menginterpretasikan setiap langkah. Kasus pertama adalah HDN-2 dari CV Rejeki Snack yang sudah kita formulasikan: masalah maksimasi dengan tiga produk dan tiga kendala. Kasus kedua adalah masalah minimasi biaya distribusi FMCG ke tiga kota Jawa Tengah — ini akan menunjukkan bahwa metode simpleks bisa diterapkan untuk minimasi juga, dengan sedikit penyesuaian. Saya sarankan Anda membuka buku catatan dan mengerjakan setiap langkah bersama saya — metode simpleks hanya bisa dipahami dengan tangan, bukan hanya dengan mata. Hitung dari Nol 2 — Simpleks Iterasi 1: Entering x₂, Leaving s₁ TABEL AWAL
BV x₁ x₂ x₃ s₁ s₂ s₃ RHS s₁ 2 3 1 1 0 0 120 s₂ 1 1 2 0 1 0 80 s₃ 1 1 1 0 0 1 60 Z −4 −5 −3 0 0 0 0
Kolom pivot: x₂ (koef −5). Elemen pivot: 3 .40 ▼, 80/1=80, 60/1=60 → leaving=s₁
TABEL SETELAH ITERASI 1
BV x₁ x₂ x₃ s₁ s₂ s₃ RHS x₂ 2/3 1 1/3 1/3 0 0 40 s₂ 1/3 0 5/3 −1/3 1 0 40 s₃ 1/3 0 2/3 −1/3 0 1 20 Z −2/3 0 −4/3 5/3 0 0 200
Z = 200 (Rp 200.000). Baris Z masih ada −2/3 dan −4/3 → belum optimal , lanjut iterasi 2.
Mari kita kerjakan iterasi pertama secara lengkap. Dari tabel awal, kita sudah tahu: entering variable = x₂ (koefisien baris Z paling negatif = −5), leaving variable = s₁ (rasio minimum 120/3 = 40), dan elemen pivot = 3. Langkah satu: bagi seluruh baris s₁ dengan 3 → hasilnya baris x₂ baru: [2/3, 1, 1/3, 1/3, 0, 0 | 40]. Langkah dua untuk baris s₂: baris s₂ lama − 1 × baris x₂ baru = [1/3, 0, 5/3, −1/3, 1, 0 | 40]. Langkah dua untuk baris s₃: baris s₃ lama − 1 × baris x₂ baru = [1/3, 0, 2/3, −1/3, 0, 1 | 20]. Baris Z baru: baris Z lama − (−5) × baris x₂ baru = [−2/3, 0, −4/3, 5/3, 0, 0 | 200]. Perhatikan Z sudah naik dari 0 ke 200 — kita sudah produksi x₂ = 40 kg kacang dan mendapatkan laba Rp 200.000. Tapi baris Z masih ada angka negatif (−2/3 dan −4/3) → kita masih bisa meningkatkan Z lebih lanjut. HDN-2 (lanjutan): Iterasi 2 (Entering x₃) → Iterasi 3 → Optimal ITERASI 2: Entering x₃, Leaving s₂ (elemen pivot = 5/3)
Min-ratio (kolom x₃): 40/(1/3)=120, 40/(5/3)=24▼ , 20/(2/3)=30 → leaving=s₂
BV x₁ x₂ x₃ s₁ s₂ s₃ RHS x₂ 3/5 1 0 2/5 −1/5 0 32 x₃ 1/5 0 1 −1/5 3/5 0 24 s₃ 1/5 0 0 −1/5 −2/5 1 4 Z −2/5 0 0 21/15 4/5 0 232
Z=232, tapi kolom x₁ = −2/5 (negatif) → belum optimal, lanjut iterasi 3.
ITERASI 3: Entering x₁, Leaving s₃ (elemen pivot = 1/5)
Min-ratio: 32/(3/5)=53,3; 24/(1/5)=120; 4/(1/5)=20▼ → leaving=s₃
BV x₁ x₂ x₃ s₁ s₂ s₃ RHS x₂ 0 1 0 1 1 −3 20 x₃ 0 0 1 0 1 −1 20 x₁ 1 0 0 −1 −2 5 20 Z 0 0 0 1 0 2 240
Semua baris Z ≥ 0 → OPTIMAL Rp 240.000/hari
Iterasi kedua menghasilkan Z = 232.000, tetapi jangan buru-buru menyimpulkan "optimal" — periksa dulu baris Z dengan seksama. Kolom x₁ masih bernilai −2/5 (negatif), artinya memasukkan keripik (x₁) ke dalam produksi masih bisa meningkatkan laba. Kita perlu iterasi ketiga: entering variable = x₁, leaving variable = s₃ (rasio minimum 20), elemen pivot = 1/5. Setelah operasi baris iterasi 3, tabel akhir menunjukkan semua koefisien baris Z ≥ 0 — sekarang benar-benar optimal. Solusi akhir yang benar: produksi ketiga produk secara seimbang, masing-masing 20 kg per hari (keripik, kacang, dan biskuit), dengan laba total Rp 240.000 per hari — lebih tinggi Rp 8.000 dari hasil iterasi 2 yang prematur. Pelajaran penting: selalu periksa SELURUH baris Z, bukan hanya satu atau dua kolom, sebelum menyatakan optimal. Studi Kasus 3 — Formulasi Minimasi: Distribusi FMCG Jawa Tengah Distributor FMCG (Fast-Moving Consumer Goods — produk konsumen perputaran cepat: mi instan, minyak, snack) perlu mengalokasikan truk ke tiga wilayah:
Rute Variabel Biaya/Truk Semarang x₁ Rp 2 juta Solo x₂ Rp 3 juta Kudus x₃ Rp 1 juta
Min Z = 2x₁ + 3x₂ + x₃(armada) (Semarang min) (Solo min) (Kudus min)
Kendala ≥ → tambahkan variabel surplus (eᵢ). Teknik penanganan (metode dua fase/Big-M) di luar cakupan — kita selesaikan via Solver.
Kasus kedua memperkenalkan dimensi baru: minimasi biaya. Konteksnya sangat realistis — distributor FMCG seperti distributor mi instan atau snack di Jawa Tengah setiap harinya harus memutuskan berapa truk yang dikirim ke setiap kota, dengan mempertimbangkan biaya bahan bakar ditambah sopir yang berbeda-beda, kapasitas armada yang terbatas, dan permintaan minimum dari tiap kota yang harus dipenuhi. Perhatikan bahwa kita sekarang punya kendala campuran: satu kendala ≤ (kapasitas armada) dan tiga kendala ≥ (permintaan minimum). Kendala ≥ memerlukan perlakuan khusus dalam simpleks — kita perlu variabel surplus (kebalikan dari variabel slack: ditambahkan ke kendala ≥ untuk mengubahnya menjadi persamaan), dan untuk memulai dari titik fisibel pada umumnya diperlukan teknik tambahan yang disebut metode dua fase atau metode Big-M. Teknik tersebut di luar cakupan pertemuan ini dan tidak akan diujikan; cukup ketahui bahwa Solver menanganinya secara otomatis. Studi Kasus 3 (lanjutan): Solusi Minimasi via Penalaran Langsung & Solver Karena semua koef biaya positif dan semua kendala adalah batas bawah, minimum tercapai tepat di batas bawah:
Kendala Sisi Kiri RHS Status Armada: x₁+x₂+x₃ 3+2+1=6 10 ✓ 6 ≤ 10 Semarang: x₁ 3 ≥3 ✓ Binding Solo: x₂ 2 ≥2 ✓ Binding Kudus: x₃ 1 ≥1 ✓ Binding
x₁=3, x₂=2, x₃=1Rp 13 juta/hari Verifikasi Solver: konfirmasi Rp 13 juta ✓
Kapan deduksi langsung bisa vs kapan pakai Solver? Bisa deduksi: semua koef fungsi tujuan bertanda sama & hanya ada batas bawah → minimum jelas di titik batas minimum.Harus pakai Solver: ada dua kendala batas-atas yang saling bersaing, koefisien beragam tanda, atau >3 variabel → intuisi gagal.Selalu verifikasi dengan Solver meski terasa intuitif — membangun kebiasaan yang benar.
Untuk masalah minimasi ini, solusinya ternyata bisa dideduksi secara logis — tetapi ada alasan spesifik mengapa ini bisa dilakukan: semua koefisien biaya positif dan semua kendala adalah batas bawah, sehingga solusi minimum jelas ada di titik batas bawah. Ini adalah kasus yang sangat sederhana secara struktur, dan saya sengaja memilihnya untuk memperlihatkan bahwa kadang berpikir logis sebelum menghitung bisa menghemat waktu. Namun saya harus tegas: begitu struktur model lebih kompleks — misalnya ada dua kendala batas-atas yang saling bersaing, atau koefisien biaya campur positif dan negatif — deduksi intuitif akan gagal dan menghasilkan jawaban yang salah. Itulah tepatnya alasan kita belajar simpleks: untuk kasus-kasus di mana intuisi tidak bisa diandalkan. Selalu verifikasi dengan Solver, bahkan untuk kasus yang "terasa" intuitif — Solver untuk kasus ini mengonfirmasi Rp 13 juta, dan verifikasi itu membangun kebiasaan yang tepat untuk kasus yang lebih kompleks. Interpretasi Tabel Akhir Simpleks Dari tabel akhir HDN-2 (iterasi 3, optimal: Z=240):
BV RHS Interpretasi Bisnis x₂ 20 Produksi kacang = 20 kg/hari x₃ 20 Produksi biskuit = 20 kg/hari x₁ 20 Produksi keripik = 20 kg/hari Z 240 Laba optimal = Rp 240.000/hari
Semua slack = 0: ketiga kendala binding (bahan baku, jam mesin, distribusi habis seluruhnya).
SHADOW PRICE (Harga Bayangan) dari Baris Z Akhir
Sumber Daya Koef Z Akhir Makna s₁ (bahan baku) 1 +1 kg → Z naik Rp 1.000 s₂ (jam mesin) 0 +1 jam → Z tidak naik s₃ (distribusi) 2 +1 kg → Z naik Rp 2.000
Shadow price (harga bayangan) = nilai marginal dari menambah satu unit sumber daya binding. Dibahas lebih lanjut di Slide 24a.
Membaca tabel akhir simpleks bukan hanya soal mengambil angka BV dan RHS-nya — ada lebih banyak informasi yang tersembunyi di sana. Di solusi optimal HDN-2, ketiga produk diproduksi secara seimbang masing-masing 20 kg, dan yang menarik adalah semua variabel slack bernilai nol — artinya semua tiga kendala (bahan baku, jam mesin, distribusi) habis terpakai sepenuhnya. Yang paling berguna secara manajerial adalah koefisien baris Z untuk variabel slack — angka ini disebut shadow price (harga bayangan). Shadow price s₁ = 1 berarti menambah 1 kg bahan baku menaikkan laba Rp 1.000; shadow price s₂ = 0 berarti jam mesin bukan bottleneck yang membatasi laba (menambah jam tidak membantu); shadow price s₃ = 2 berarti menambah 1 kg kapasitas distribusi menaikkan laba Rp 2.000 — distribusi adalah sumber daya paling berharga untuk diinvestasikan. Blok Materi
04
Excel Solver
Otomasi simpleks dengan spreadsheet — dari formula ke keputusan bisnis
Blok terakhir ini adalah jembatan antara teori dan praktik sehari-hari. Anda sudah memahami cara kerja simpleks secara manual — sekarang kita gunakan Excel Solver, yang mengimplementasikan simpleks (dan metode lanjutannya) di balik layar dengan antarmuka yang jauh lebih mudah. Penting untuk diingat: memahami cara kerja manual itu prasyarat untuk menggunakan Solver dengan benar. Kalau Anda tidak mengerti apa itu entering variable atau min-ratio test, Anda tidak akan bisa mendeteksi apakah Anda salah memasukkan model ke Solver — dan hasilnya bisa salah tanpa peringatan. Di blok ini, kita akan setup Solver langkah demi langkah untuk kasus HDN-2, lalu melihat satu aplikasi nyata dari konteks bisnis Indonesia. Setup Excel Solver untuk LP Tiga Variabel 1
Sel keputusan: B2:D2 → x₁, x₂, x₃ (isi awal = 0)
2
Sel tujuan: E2 → =4*B2 + 5*C2 + 3*D2 (laba Z)
3
Sel kendala: F2=2*B2+3*C2+D2 ≤ 120 G2=B2+C2+2*D2 ≤ 80 H2=B2+C2+D2 ≤ 60
4
Data → Solver ; Set Objective: E2, Max ; By Changing: B2:D2
5
Add Constraints: F2≤120, G2≤80, H2≤60, B2:D2≥0
6
Pilih Simplex LP → klik Solve → centang "Sensitivity" sebelum OK
Sel Label Formula / Nilai B2:D2 x₁,x₂,x₃ 0 (awal) → 20,20,20 E2 Fungsi Tujuan Z =4*B2+5*C2+3*D2 F2 Bahan Baku =2*B2+3*C2+D2 G2 Jam Mesin =B2+C2+2*D2 H2 Distribusi =B2+C2+D2
Hasil Solver: x₁=20, x₂=20, x₃=20240 ✓ (cocok hasil manual 3 iterasi)
Sekarang kita terjemahkan model yang sudah kita buat ke dalam Excel Solver. Langkah yang paling krusial adalah menyusun sel dengan benar: sel keputusan adalah sel di mana Solver akan mengubah-ubah nilainya (B2:D2 untuk x₁, x₂, x₃), sel tujuan adalah formula yang menghitung Z (harus merujuk ke sel keputusan), dan sel kendala adalah formula yang menghitung sisi kiri setiap pertidaksamaan. Perhatikan: semua formula harus linear — jangan ada perkalian antarvariabel atau pangkat. Di dialog Solver, pastikan Anda memilih "Simplex LP" sebagai solving method (bukan GRG Nonlinear atau Evolutionary), karena model kita adalah LP linier. Jika hasilnya tidak cocok dengan perhitungan manual, langkah pertama debugging adalah memeriksa apakah sel tujuan dan sel kendala sudah merujuk ke sel keputusan yang benar. Langkah memilih laporan Sensitivity sebelum klik OK itu penting — nanti kita butuh laporan itu untuk shadow price dan allowable range yang kita bahas di slide berikutnya. Aplikasi Nyata: Alokasi Armada PERUM Damri Semarang PERUM Damri (Perusahaan Umum Djawatan Angkoetan Motor Repoeblik Indonesia — BUMN angkutan darat) cabang Semarang mengoperasikan:
Rute Var. Laba/rit Min rit Semarang–Ungaran x₁ Rp 500 rb 4 Semarang–Demak x₂ Rp 600 rb 3 Semarang–Kendal x₃ Rp 400 rb 2
Total armada tersedia: ≤20 bus. Rit = satu perjalanan pulang-pergi.
Maks Z = 500x₁ + 600x₂ + 400x₃
Solusi logis: Setelah min. 4+3+2=9, sisa 11 rit ke x₂ (Rp 600rb, tertinggi).14 , x₃=2Rp 11.200 ribu/hari
Deduksi ini berhasil karena ada satu rute dominan & satu jenis kapasitas. Begitu muncul batas ganda → pakai Solver.
Studi kasus ini menggunakan PERUM Damri — BUMN yang sangat dikenal di Semarang — untuk menunjukkan bahwa LP bukan hanya tentang pabrik dan produksi, tapi juga tentang manajemen armada transportasi publik. Solusi optimal dalam kasus ini dapat dideduksi secara logis: karena Rute Demak memberikan laba tertinggi per rit (Rp 600 ribu), kita alokasikan sebanyak mungkin bus ke sana — setelah memenuhi komitmen minimum di ketiga rute (4+3+2=9), sisa 11 rit semuanya ke Demak, menghasilkan total laba Rp 11,2 juta per hari. Penting untuk saya tekankan: deduksi logis ini bekerja karena kasus ini sederhana — ada satu rute yang jelas dominan dan satu jenis kapasitas yang dibagi. Begitu muncul dua batas-atas yang saling bersaing, atau ada biaya bahan bakar yang berbeda-beda antar musim, intuisi akan gagal dan kita butuh Solver. Itulah pesan inti pertemuan ini: gunakan logika untuk memahami dan memverifikasi, tapi gunakan simpleks/Solver untuk memecahkan secara andal. Shadow Price — Nilai Marginal Kapasitas Shadow price (harga bayangan): koefisien baris Z kolom slack di tabel akhir = nilai marginal dari menambah 1 unit sumber daya binding.
Sumber Daya Slack Shadow Price Binding? Interpretasi Bahan baku (s₁) 0 Rp 1.000/kg Ya +1 kg bahan baku → laba +Rp 1.000 Jam mesin (s₂) 0 Rp 0/jam Ya* +1 jam mesin → laba tidak naik Distribusi (s₃) 0 Rp 2.000/kg Ya +1 kg distribusi → laba +Rp 2.000
Contoh keputusan: Sewa 5 kg kapasitas distribusi tambahan seharga Rp 1.500/kg .Net gain Rp 2.500. Layak. Jika harga sewa ≥ Rp 2.000/kg (di atas shadow price) → tidak layak.
Setelah Solver menemukan solusi optimal, kita klik "Sensitivity Report" untuk mendapatkan informasi lebih dalam. Shadow price menjawab pertanyaan yang paling sering ditanyakan manajemen: "Apakah layak kita tambah kapasitas sumber daya X?" Dari tabel akhir HDN-2, shadow price bahan baku = Rp 1.000/kg — artinya setiap kg bahan baku tambahan menaikkan laba Rp 1.000; kalau harga sewa/beli tambahan di pasar kurang dari Rp 1.000/kg, membeli lebih banyak menguntungkan. Shadow price distribusi = Rp 2.000/kg — artinya setiap kg kapasitas distribusi tambahan menaikkan laba Rp 2.000. Contoh keputusan: bila kita bisa menyewa 5 kg kapasitas distribusi tambahan seharga Rp 1.500/kg, maka tambah laba = 5 × Rp 2.000 = Rp 10.000 dan biaya = 5 × Rp 1.500 = Rp 7.500, net gain = Rp 2.500 — layak. Sebaliknya, jika harga sewa Rp 2.500/kg (di atas shadow price), maka net = Rp 10.000 − Rp 12.500 = −Rp 2.500 — tidak layak. Shadow price jam mesin = 0 menunjukkan bahwa menambah jam mesin tidak akan meningkatkan laba dalam kondisi saat ini. Allowable Range — Batas Validitas Shadow Price Allowable range (rentang yang diizinkan): interval perubahan RHS di mana shadow price masih berlaku (basis optimal tidak berubah).
Sumber Daya RHS Sekarang Allow. Decrease Allow. Increase Rentang Valid Bahan baku (b₁) 120 20 20 100 — 140 kg Distribusi (b₃) 60 4 ≈6,67 56 — 66,67 kg
*Dihitung dari matriks basis optimal (Lampiran A materi). Untuk angka eksak: ambil dari kolom "Allowable Increase/Decrease" di Sensitivity Report Excel Solver.
b₁ Z 100 120 140 SP=Rp1.000 SP berubah di luar range Jangan ekstrapolasi shadow price di luar allowable range — seperti menggunakan harga marginal yang sudah kedaluwarsa.
Shadow price adalah "harga" yang hanya berlaku dalam kondisi tertentu — itulah gunanya allowable range. Bayangkan Anda ingin menambah kapasitas bahan baku dari 120 kg menjadi 150 kg (tambah 30 kg). Apakah shadow price Rp 1.000/kg masih berlaku? Hanya jika 30 kg itu masih dalam allowable increase — kalau allowable increase-nya hanya 20 kg, maka untuk tambahan 21 kg dan seterusnya, shadow price-nya sudah berubah karena solusi optimal beralih ke basis yang berbeda. Dalam praktik, cara termudah mendapatkan allowable range adalah dari Sensitivity Report Excel Solver: kolom "Allowable Increase" dan "Allowable Decrease" di bagian Constraints langsung memberikan angka ini. Gunakan informasi ini sebelum membuat keputusan investasi kapasitas besar — jangan hanya mengalikan shadow price dengan jumlah tambahan tanpa mengecek batas validitasnya. Degenerasi (kondisi di mana beberapa variabel basis bernilai nol atau beberapa kendala aktif sekaligus) bisa menyebabkan shadow price tidak unik dan rentang menjadi asimetris. Cheat Sheet — Lima Langkah Metode Simpleks Langkah Tindakan Kondisi Berhenti 0 SetupTambahkan slack sᵢ ke tiap kendala ≤; tulis tabel awal; BV awal = {s₁,...,sᵕ} — 1 Kolom PivotKoef baris Z paling negatif → entering variable Semua baris Z ≥ 0 → OPTIMAL 2 Min-RatioRHS ÷ koef kolom pivot (hanya koef > 0) → baris pivot; leaving variable Semua koef ≤ 0 → TAK TERBATAS 3 Operasi BarisBaris pivot ÷ elemen pivot; baris lain: baris − k × baris pivot baru — 4 Update BVGanti leaving dengan entering di kolom BV — 5 UlangKembali ke Langkah 1 —
Catatan praktis: Gunakan Excel Solver (pilih "Simplex LP") untuk masalah >3 variabel. Prosedur manual hanya untuk belajar & memahami mekanisme dasar.
Ini adalah ringkasan yang bisa Anda tempel di meja belajar. Lima langkah ini mencakup seluruh algoritma simpleks untuk kasus maksimasi standar. Perhatikan dua kondisi berhenti yang berbeda: jika semua koefisien baris Z non-negatif, Anda sudah di solusi optimal — berhenti dan baca solusinya. Jika di langkah min-ratio test Anda mendapati semua koefisien di kolom pivot ≤ 0, itu berarti fungsi tujuan tidak terbatas (tak ada batas atas untuk Z) — dalam konteks bisnis, ini sinyal bahwa ada kesalahan formulasi model karena di dunia nyata sumber daya selalu terbatas. Untuk masalah minimasi, caranya sama setelah Anda mengalikan fungsi tujuan dengan −1. Dan untuk segala masalah LP dengan lebih dari 3 variabel dalam praktik, selalu gunakan Solver — tapi tetap pahami manual agar bisa memverifikasi dan mendeteksi kesalahan input. Pertemuan 12 — Recap & Tugas Minggu Depan Formulasi LP tiga variabel dari narasi bisnis (CV Rejeki Snack) Batasan metode grafis untuk n > 2 variabel Tabel simpleks: variabel slack, kolom pivot, min-ratio test, operasi baris HDN-2 lengkap 3 iterasi: x₁=x₂=x₃=20, Z=Rp 240.000 Studi kasus minimasi FMCG: x₁=3, x₂=2, x₃=1, Z=Rp 13 juta Excel Solver setup & Sensitivity Report Shadow price & allowable range Kerjakan Soal 1 & Soal 3 dari Lampiran B materi — manual dulu, bukan Solver Baca Haeussler, Paul & Wood (2018) Ch. 7 (sisa bagian) Eksplorasi: cari satu UMKM di sekitar Anda, formulasikan LP-nya, selesaikan dengan Solver "Setiap LP yang kita selesaikan adalah keputusan yang lebih baik dari intuisi semata."
Kita sudah menempuh perjalanan yang cukup panjang hari ini — dari memahami mengapa grafik tidak cukup, membangun tabel simpleks dari nol, mengerjakan dua kasus numerik penuh, sampai menggunakan Excel Solver dan membaca Sensitivity Report. Ini adalah pertemuan yang paling padat secara teknis dalam Sub-CPMK 4, dan saya bangga bahwa Anda sudah sampai di sini. Untuk tugas, kerjakan soal 1 dan 3 dari Lampiran B secara manual — jangan gunakan Solver dulu, karena yang kita nilai adalah proses berpikirnya, bukan hanya jawaban akhirnya. Setelah itu, sebagai eksplorasi mandiri, saya tantang Anda untuk mengidentifikasi satu UMKM atau bisnis keluarga di sekitar Anda, formulasikan masalah alokasi sumber dayanya sebagai model LP, dan selesaikan dengan Solver. Kalau Anda berhasil melakukan itu, Anda sudah satu langkah lebih maju dari banyak fresh graduate yang melamar posisi analis operasional. Sampai jumpa di pertemuan berikutnya. Referensi Haeussler, E. F., Paul, R. S., & Wood, R. J. (2018). Introductory Mathematical Analysis for Business, Economics, and the Life and Social Sciences (14th ed.). Pearson. Ch. 7. Dumairy. (1985). Matematika Terapan untuk Bisnis dan Ekonomi . Yogyakarta: BPFE. Bab 8. Hillier, F. S., & Lieberman, G. J. Introduction to Operations Research (edisi terbaru). McGraw-Hill. Winston, W. L. Operations Research: Applications and Algorithms (4th ed.). Thomson. Microsoft Excel Solver Help Documentation (built-in, via Data → Solver → Help). Konteks bisnis: CV Rejeki Snack (UMKM snack Jawa Tengah), PERUM Damri Semarang, PT Sinar Distribusi FMCG — semua bersifat ilustratif.
Ini adalah slide referensi yang bisa Anda gunakan untuk menelusuri sumber lebih lanjut. Haeussler, Paul & Wood adalah buku teks utama yang digunakan di kelas ini — Chapter 7 membahas LP secara lengkap termasuk metode simpleks. Hillier & Lieberman adalah referensi standar internasional untuk operation research yang lebih mendalam. Winston adalah alternatif yang lebih berorientasi aplikasi. Semua konteks bisnis yang saya gunakan hari ini — CV Rejeki Snack, PERUM Damri, PT Sinar Distribusi — bersifat ilustratif, dirancang untuk mencerminkan realitas bisnis Jawa Tengah yang relevan dengan keseharian Anda. Jika Anda ingin mendalami lebih jauh, terutama metode dua fase dan Big-M untuk kasus minimasi, Hillier & Lieberman Bab 4 adalah tempat yang tepat untuk memulai. Selamat belajar.