modul mata k ul iah p em rogram an linearmasalah ekonomi, industri, militer, sosial, dan lain -lain....
TRANSCRIPT
Modul Mata Kuliah
“Pemrograman Linear”
MAT 3224
Disusun Oleh:
Rully Charitas Indra Prahmana
Program Studi Pendidikan Matematika
Sekolah Tinggi Keguruan dan Ilmu Pendidikan Surya
Tangerang
2013
ii
Kata Pengantar
Puji syukur, saya haturkan kehadirat Allah SWT, karena berkat rahmat dan
hidayah-Nya, Modul Pemrograman Linier ini, dapat selesai tepat pada waktunya,
walaupun dengan banyak kekurangan disana sini, karena saya hanyalah manusia biasa
yang tidak pernah luput dari kesalahan. Tak lupa Shalawat beriring salam, kita
panjatkan kehadirat Nabi Besar Muhammad SAW, yang telah membawa syiar Islam,
agama yang paling sempurna di muka bumi ini, dengan seluruh jiwa raga-nya.
Modul ini, saya bagi menjadi 8 bagian, mulai dari defenisi Program Linear sampai
beberapa metode yang digunakan dalam penyelesaian masalah, yang berhubungan
dengan Program Linier. Harapannya, target pembelajaran mata kuliah Pemrograman
Linier dapat tercapai. Amin...
Dalam menyelesaikan modul ini, penyusun sadar bahwa semuanya tidak terlepas
dari berbagai pihak yang selama ini selalu mendukung, baik secara material maupun
non material, semangat, dan segalanya. Untuk itu, penyusun ingin mengucapkan terima
kasih kepada semua pihak yang telah membantu dalam penyelesaian modul ini.
Akhir kata, disadari bahwa modul ini, masih memiliki banyak kekurangan. Untuk
itu, penyusun berbesar hati menerima segala kritik dan saran, yang dapat dialamatkan
ke [email protected]. Semoga modul ini, dapat memberikan banyak
manfaat bagi kita semua, terutama bagi kemajuan pendidikan matematika ke depannya.
Amin...
Tangerang, Agustus 2013
Penyusun
iii
Daftar Isi
Kata Pengantar ii
Daftar Isi iii Silabus Perkuliahan iv
Bagian Pertama
Program Linier 1
Bagian Kedua Pemodelan Matematika 3
Bagian Ketiga
Contoh dan Latihan Kasus Pemodelan Matematika 9 Bagian Keempat
Metode Grafik 16 Bagian Kelima
Metode Simpleks 25
Bagian Keenam Alur Penyelesaian Metode Simpleks 30
Bagian Ketujuh Contoh Kasus Metode Simpleks 32
Bagian Kedelapan
Variasi Kasus 38
Daftar Pustaka 48
Revisi-1 Pemrograman Linear | iv
Program Studi : Pendidikan Matematika Nama Mata Kuliah : Pemrograman Linear Kode Mata Kuliah : MAT 3224 Jumlah SKS : 3 Tahun Akademik : 2013/2014 Semester : 5 Mata KuliahPra Syarat : Kalkulus 1, Aljabar Linear, dan Komputer 2 Hari/Waktu : Ruangan : Dosen Pengampu : Rully Charitas Indra Prahmana, M.Pd Email : [email protected]
KOMPETENSI DASAR
1. Mahasiswa mampu menjelaskan berbagai hal tentang pengantar Program Linear. 2. Mahasiswa mampu menjelaskan dan memodelkan suatu permasalahan dalam bentuk Program Linear (PL). 3. Mahasiswa mampu menjelaskan persoalan Optimasi dalam PL dan menyelesaikan PL dengan Metode Grafik dan Metode Simpleks. 4. Mahasiswa mampu menjelaskan dan menyelesaikan berbagai permasalahan Dualitas dan Analisis Sensitivitas. 5. Mahasiswa mampu menerapkan konsep PL untuk memecahkan masalah dalam kehidupan sehari – hari.
DESKRIPSI MATA KULIAH
Program linier (PL) adalah salah satu bagian dari penerapan ilmu matematika yang dapat digunakan untuk membantu memecahkan persoalan – persoalan dalam bidang ekonomi, industri, managemen dan pertanian. Materi dalam perkuliahan ini, lebih menekankan pada aplikasi program linier dan interpretasi-nya. Adapun isi pokok materi dalam perkuliahan ini meliputi sejarah PL, pembuatan model permasalahan PL, berbagai metoda penyelesaian PL (Tabel, Simpleks, dan Dualitas), serta analisis sensitivitas.
KURIKULUM PENDIDIKAN MATEMATIKA STKIP – SURYA Kode:
SATUAN ACARA PERKULIAHAN (SAP)
Revisi-1 Pemrograman Linear | v
TABEL
Pertemuan
(Sesi) Kompetensi
Dasar Indikator
Metode Perkuliahan
Materi Perkuliahan Penilaian
1 1 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu menyebutkan:
1. Defenisi Program Linear (PL) 2. Karakteristik PL 3. Berbagai istilah yang digunakan dalam PL
Ceramah Diskusi Studi kasus Tanya jawab
1. Rencana dan kontrak perkuliahan
2. Pengantar Program Linear
Tugas Portofolio, tes essay
2 2 dan 3 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu:
1. Memformulasikan dan memodelkan permasalahan progam linear
2. Menyelesaikan PL dengan metode grafik
Ceramah Diskusi Studi kasus Tanya jawab
1. Formulasi program linear
2. Metode Grafik
Tugas Portofolio, tes essay
3 2 dan 3 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu:
1. Memodelkan suatu permasalahan dalam bentuk PL 2. Menyelesaikan PL dengan metode grafik 3. Menginterpretasikan solusi PL
Studi kasus Tanya jawab
Studi kasus permasalahan pemodelan matematika
Tes essay
4 3 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu:
1. Memformulasikan & menyajikan masalah PL dalam matrik 2. Membedakan kegunaan slack dan artificial variable 3. Mengetahui syarat perubahan variabel
Ceramah Diskusi Studi kasus Tanya jawab
1. Formulasi bentuk matriks
2. Slack dan artificial variabel
Tugas Portofolio, tes essay
5 3 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu:
1. Membuat tabel simpleks awal 2. Menjelaskan istilah dan syarat dalam metode simpleks
Ceramah Diskusi Studi kasus Tanya jawab
Pengantar Metode Simpleks Tugas Portofolio, tes essay
6 3 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu:
1. Membuat metode simpleks yang direvisi 2. Membuat prosedur komputasi metode simpleks yang
direvisi
Diskusi Studi kasus Tanya jawab
Metode Simpleks lanjut Tugas Portofolio, tes essay
Revisi-1 Pemrograman Linear | vi
7 3 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu:
1. Memodelkan suatu permasalahan dalam bentuk PL 2. Menyelesaikan PL dengan metode simpleks 3. Menginterpretasikan solusi PL
Studi kasus Tanya jawab
Studi kasus menyelesaikan permasalahan PL menggunakan Metode Simpleks
Tes essay
8 1, 2, dan 3 Review Materi pertemuan 1-7 Studi kasus 1. Metode grafik 2. Metode simpleks
Tes essay
9 Ujian Tengah Semester (UTS)
10 4 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu melakukan analisis sensitivitas menggunakan metode grafik
Ceramah Diskusi Studi kasus Tanya jawab
Analisis sensitivitas metode grafik
Tugas Portofolio, tes essay
11 4 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu melakukan analisis sensitivitas menggunakan metode simpleks
Ceramah Diskusi Studi kasus Tanya jawab
Analisis sensitivitas metode simpleks
Tugas Portofolio, tes essay
12 4 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu mengubah dan menyelesaikan masalah PL Primal menjadi PL Dual
Ceramah Diskusi Studi kasus Tanya jawab
Dualitas Tugas Portofolio, tes essay
13 4 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu menjelaskan pengertian model transportasi, berikut aplikasi yang ada didalamnya (penerapannya)
Ceramah Diskusi Studi kasus Tanya jawab
Model transportasi Tugas Portofolio, tes essay
14 4 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu menentukan solusi layak optimal berdasarkan solusi layak awal
Ceramah Diskusi Studi kasus Tanya jawab
Solusi layak optimal Tugas Portofolio, tes essay
Revisi-1 Pemrograman Linear | vii
15 5 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu menyelesaikan permasalahan aplikasi PL dalam kehidupan sehari-hari
Ceramah Diskusi Studi kasus Tanya jawab
Aplikasi PL dalam kehidupan sehari-hari
Tugas Portofolio, tes essay
16 5 Setelah mengikuti perkuliahan ini mahasiswa diharapkan mampu menyelesaikan permasalahan tingkat lanjut dari penerapan PL dalam kehidupan sehari-hari
Ceramah Diskusi Studi kasus Tanya jawab
Aplikasi PL dalam kehidupan sehari-hari lanjut
Tugas Portofolio, tes essay
17 4 dan 5 Review materi pertemuan 10-16 Studi kasus tes essay
18 Ujian Akhir Semester (UAS)
REFERENSI R1 = Taha, Hamdy A. (1997). Operations Research, an Introduction, sixth edition, Upper Saddle River, New Jersey, Prentice Hall, Inc R2 = Siringoringo, Hotniar. (2005). Seri Teknik Riset Operasional. Pemrograman Linear. Yogyakarta: Penerbit Graha Ilmu R3 = Steven J. Miller. (2007). An Introduction to Linear Programming. Mathematics Department: Brown University
PEDOMAN PENILAIAN
Penilaian meliputi: 1. Nilai Tugas (Quiz dan Kehadiran) = 30% 2. Nilai Ujian Tengah Semester (UTS) = 30% 3. Nilai Ujian Akhir Semester (UAS) = 40%
Nilai akhir dihitung dengan menggunakan rumus:
Nilai Akhir = (0,3 x Tugas) + (0,3 x UTS) + (0, 4 x UAS)
Revisi-1 Pemrograman Linear | viii
Konversi Nilai
Mengetahui Menyetujui
Ketua Prodi Pendidikan Matematika
(Johannes H. Siregar, Ph.D.)
Penanggung Jawab Mata Kuliah
(Rully Charitas Indra Prahmana, M.Pd)
Mahasiswa
(……………...................)
Nilai Akhir (x) Nilai Keterangan Angka Huruf
90 ≤ x ≤100 4,00 A Lulus 85≤ x < 90 3,67 A- Lulus 80 ≤ x < 85 3,33 B+ Lulus 75 ≤ x < 80 3,00 B Lulus 70 ≤ x < 75 2,67 B- Lulus 65 ≤ x < 70 2,33 C+ Lulus 60 ≤ x < 65 2,00 C Lulus 55 ≤ x < 60 1,67 C- Lulus Bersyarat 50 ≤ x < 55 1,00 D Tidak Lulus 0 ≤ x < 50 0,00 E Tidak Lulus
1
Bagian Pertama
Program Linear
Program linier merupakan suatu metode matematika dalam mengalokasikan
sumber daya yang terbatas, untuk mencapai suatu tujuan seperti memaksimumkan
keuntungan dan meminimumkan biaya. Pemrograman linier banyak diterapkan dalam
masalah ekonomi, industri, militer, sosial, dan lain-lain. Program linier juga berkaitan
dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematika yang
terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier.
Program linier memiliki empat ciri khusus yang melekat pada dirinya, yaitu :
1. Penyelesaian masalah mengarah pada pencapaian tujuan maksimalisasi atau
minimalisasi.
2. Kendala yang ada membatasi tingkat pencapaian tujuan.
3. Ada beberapa alternatif penyelesaian.
4. Hubungan matematis bersifat linear.
Karakteristik Pemrograman Linier
Secara teknis, program linier memiliki beberapa sifat atau karakteristik dari
permasalahan program linier yang harus diperhatikan, yang merupakan asumsi dasar,
yaitu sifat linearitas, proporsionalitas, additivitas, divisibilitas, kepastian, dan non
negative variable. Untuk lebih jelasnya, berikut kita jelaskan dengan lebih terperinci.
Sifat linearitas suatu kasus dapat ditentukan dengan menggunakan beberapa
cara. Secara statistik, kita dapat memeriksa kelinearan menggunakan grafik (diagram
pencar) ataupun menggunakan uji hipotesa. Secara teknis, linearitas ditunjukkan oleh
adanya sifat proporsionalitas, additivitas, divisibilitas dan kepastian fungsi tujuan dan
pembatas.
Sifat proporsionalitas dipenuhi, jika kontribusi setiap variabel pada fungsi
tujuan atau penggunaan sumber daya yang membatasi proporsional terhadap level nilai
variabel. Jika harga per unit produk misalnya adalah sama berapapun jumlah yang
2
dibeli, maka sifat proporsionalitas dipenuhi. Atau dengan kata lain, jika pembelian
dalam jumlah besar mendapatkan diskon, maka sifat proporsionalitas tidak dipenuhi.
Jika penggunaan sumber daya per unitnya tergantung dari jumlah yang diproduksi,
maka sifat proporsionalitas tidak dipenuhi.
Sifat additivitas mengasumsikan bahwa tidak ada bentuk perkalian silang
diantara berbagai aktivitas, sehingga tidak akan ditemukan bentuk perkalian silang pada
model. Sifat additivitas berlaku baik bagi fungsi tujuan maupun pembatas (kendala).
Sifat additivitas dipenuhi jika fungsi tujuan merupakan penambahan langsung
kontribusi masing-masing variabel keputusan. Untuk fungsi kendala, sifat additivitas
dipenuhi jika nilai kanan merupakan total penggunaaan masing-masing variabel
keputusan. Jika dua variabel keputusan misalnya merepresentasikan dua produk
substitusi, dimana peningkatan volume penjualan salah satu produk akan mengurangi
volume penjualan produk lainnya dalam pasar yang sama, maka sifat additivitas tidak
terpenuhi.
Sifat divisibilitas berarti unit aktivitas dapat dibagi ke dalam sembarang level
fraksional, sehingga nilai variabel keputusan non integer dimungkinkan.
Sifat certainty (kepastian) menunjukkan bahwa semua parameter model
berupa konstanta. Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan
suatu nilai pasti, bukan merupakan nilai dengan peluang tertentu.
Sifat non-negative variable (variabel tidak negatif), artinya bahwa semua nilai
jawaban atau variabel tidak negatif.
Keenam asumsi (sifat) ini dalam dunia nyata tidak selalu dapat dipenuhi. Untuk
meyakinkan dipenuhinya keenam asumsi ini, dalam pemrograman linier, diperlukan
analisis sensitivitas terhadap solusi optimal yang diperoleh.
3
Bagian Kedua
Pemodelan Matematika
Formulasi Permasalahan
Urutan pertama dalam penyelesaian pemograman linier adalah mempelajari
sistem yang relevan dan mengembangkan pernyataan permasalahan yang
dipertimbangkan dengan jelas. Penggambaran sistem dalam pernyataan ini termasuk
pernyataan tujuan, sumber daya yang membatasi, alternatif keputusan yang mungkin
(kegiatan atau aktivitas), batasan waktu pengambilan keputusan, hubungan antara
bagian yang dipelajari dan bagian lain dalam perusahaan, dan lain-lain.
Penetapan tujuan yang tepat merupakan aspek yang sangat penting dalam
formulasi permasalahan. Untuk membentuk tujuan optimalisasi, diperlukan identifikasi
anggota manajemen yang benar-benar akan melakukan pengambilan keputusan dan
mendiskusikan pemikiran mereka tentang tujuan yang ingin dicapai.
Pembentukan Model Matematika
Tahap berikutnya yang harus dilakukan setelah memahami permasalahan
optimasi adalah membuat model yang sesuai untuk analisis. Pendekatan konvensional
riset operasional untuk pemodelan adalah membangun model matematika yang
menggambarkan inti permasalahan. Studi kasus yang berbentuk cerita, akan
diterjemahkan ke dalam model matematika. Model matematika merupakan representasi
kuantitatif tujuan dan sumber daya yang membatasi sebagai fungsi variabel keputusan.
Model matematika permasalahan optimal terdiri dari dua bagian.
Bagian pertama, memodelkan tujuan optimasi. Model matematika yang
merupakan tujuan optimasi, selalu menggunakan bentuk persamaan. Bentuk persamaan
digunakan, karena kita ingin mendapatkan solusi optimum pada satu titik. Fungsi tujuan
yang akan dioptimalkan hanya satu. Bukan berarti bahwa permasalahan optimasi hanya
dihadapkan pada satu tujuan. Tujuan dari suatu usaha bisa lebih dari satu. Tetapi pada
bagian ini kita hanya akan tertarik dengan permasalahan optimal dengan satu tujuan.
4
Bagian kedua merupakan model matematika yang merepresentasikan sumber
daya yang membatasi. Fungsi pembatas bisa berbentuk persamaan (=) atau
pertidaksamaan (≤ atau ≥). Fungsi pembatas disebut juga sebagai konstrain. Konstanta
(baik sebagai koefisien maupun nilai kanan) dalam fungsi pembatas maupun pada
tujuan dikatakan sebagai parameter model. Model matematika mempunyai beberapa
keuntungan dibandingakan pendeskripsian permasalahan secara verbal. Salah satu
keuntungan yang paling jelas adanya model matematika menggambarkan permasalahan
secara lebih ringkas. Hal ini cenderung membuat struktur keseluruhan permasalahan
lebih mudah dipahami, dan sangat penting membantu mengungkapkan relasi sebab
akibat. Model matematika juga memfasilitasi yang berhubungan dengan permasalahan
dan keseluruhannya dan mempertimbangkan semua keterhubungannya secara
simultan. Disamping itu, model matematika juga membentuk jembatan ke penggunaan
teknik matematika dan komputer kemampuan tinggi untuk menganalisis
permasalahannya.
Di sisi lain, model matematika juga memiliki kelemahan, diantaranya tidak semua
karakteristik sistem, dapat dengan mudah dimodelkan menggunakan fungsi
matematika. Meskipun dapat dimodelkan dengan fungsi matematika, kadang-kadang
penyelesaiannya sulit diperoleh karena kompleksitas fungsi dan teknik yang
dibutuhkan.
Bentuk umum pemrograman linier adalah sebagai berikut:
Fungsi tujuan:
Maksimumkan atau minimumkan,
z = c1x1 + c2x2 + ... + cnxn
Sumber daya yang membatasi (fungsi kendala):
a11x1 + a12x2 + ... + a1nxn = atau ≤ atau ≥ b1
a21x1 + a22x2 + … + a2nxn = atau ≤ atau ≥ b2
…
am1x1 + am2x2 + … + amnxn = atau ≤ atau ≥ bm
x1, x2, …, xn ≥ 0
5
Simbol x1, x2, ..., xn (xi) menunjukkan variabel keputusan. Banyak variabel
keputusan (xi), dipengaruhi dari banyak kegiatan atau aktivitas yang dilakukan untuk
mencapai tujuan. Simbol c1,c2,...,cn merupakan kontribusi masing-masing variabel
keputusan terhadap tujuan, disebut juga koefisien fungsi tujuan pada model
matematikanya. Simbol a11, ...,a1n,...,amn merupakan penggunaan per unit variabel
keputusan akan sumber daya yang membatasi, atau disebut juga sebagai koefisien
fungsi kendala pada model matematikanya. Simbol b1,b2,...,bm menunjukkan jumlah
masing-masing sumber daya yang ada. Jumlah fungsi kendala akan tergantung dari
banyaknya sumber daya yang terbatas.
Pertidaksamaan terakhir (x1, x2, …, xn ≥ 0) menunjukkan batasan non negatif.
Membuat model matematika dari suatu permasalahan bukan hanya menuntut
kemampuan matematika tapi juga menuntut seni pemodelan. Menggunakan seni akan
membuat pemodelan lebih mudah dan menarik.
Kasus pemrograman linier sangat beragam. Dalam setiap kasus, hal yang penting
adalah memahami setiap kasus dan memahami konsep pemodelannya. Meskipun fungsi
tujuan misalnya hanya mempunyai kemungkinan bentuk maksimalisasi atau
minimalisasi, keputusan untuk memilih salah satunya bukan pekerjaan mudah. Tujuan
pada suatu kasus bisa menjadi batasan pada kasus yang lain. Harus hati-hati dalam
menentukan tujuan, koefisien fungsi tujuan, batasan, dan koefisien pada fungsi
pembatas.
Contoh kasus
Pada sub bagian ini, terdapat sebuah kasus dengan karakteristik tertentu dan
sudah diselesaikan sampai tahapan pemodelan matematika-nya. Selanjutnya, akan
diberikan contoh kasus-kasus dengan karakteristik yang berbeda-beda, sehingga dapat
memperkaya pembaca dalam ilmu dan seni pemodelan matematika. Pahami dan
perhatikan teknik pemodelannya dengan hati-hati.
6
Soal
Seorang pengrajin menghasilkan satu tipe meja dan satu tipe kursi. Proses yang
dikerjakan adalah merakit meja dan kursi. Dibutuhkan waktu 2 jam untuk merakit 1 unit
meja dan 30 menit untuk merakit 1 unit kursi. Perakitan dilakukan oleh 4 orang
karyawan dengan waktu kerja 8 jam perhari. Pelanggan pada umumnya membeli paling
banyak 4 kursi untuk 1 meja. Oleh karena itu pengrajin harus memproduksi kursi paling
banyak empat kali jumlah meja. Harga jual per unit meja adalah Rp 1,2 juta dan per unit
kursi adalah Rp 500 ribu.
Formulasikan kasus tersebut ke dalam model matematikanya !
Solusi:
Hal pertama yang harus dilakukan adalah mengidentifikasi tujuan, alternatif
keputusan, dan sumber daya yang membatasi. Berdasarkan informasi yang diberikan
pada soal, tujuan yang ingin dicapai adalah memaksimumkan pendapatan. Alternatif
keputusan adalah jumlah meja dan kursi yang akan diproduksi. Sumber daya yang
membatasi adalah waktu kerja karyawan dan perbandingan jumlah kursi dan meja
yang harus diproduksi (pangsa pasar).
Langkah berikutnya adalah memeriksa sifat proporsionalitas, additivitas,
divisibilitas, dan kepastian. Informasi di atas tidak menunjukkan adanya pemberian
diskon, sehingga harga jual per meja maupun kursi akan sama meskipun jumlah yang
dibeli semakin banyak. Hal ini mengisyaratkan bahwa total pendapatan yang diperoleh
pengrajin proposional terhadap jumlah produk yang terjual. Penggunaan sumber daya
yang membatasi, dalam hal ini waktu kerja karyawan dan pangsa pasar juga
proporsional terhadap jumlah meja dan kursi yang diproduksi. Dengan demikian dapat
dinyatakan sifat proporsionalitas dipenuhi. Total pendapatan pengrajin merupakan
jumlah pendapatan dari keseluruhan meja dan kursi yang terjual. Penggunaan sumber
daya (waktu kerja karyawan dan pangsa pasar) merupakan penjumlahan waktu yang
digunakan untuk memproduksi meja dan kursi. Maka dapat dinyatakan juga sifat
additivitas dipenuhi. Sifat divisibilitas dan kepastian juga dipenuhi.
Ada dua variabel keputusan dan dua sumber daya yang membatasi. Fungsi tujuan
merupakan maksimalisasi, karena semakin besar pendapatan akan semakin disukai oleh
pengrajin. Fungsi kendala pertama (batasan waktu) menggunakan relasi ≤, karena
7
waktu yang tersedia dapat digunakan sepenuhnya atau tidak, tapi tidak mungkin
melebihi waktu yang ada. Fungsi kendala yang kedua bisa menggunakan relasi ≤ atau ≥
tergantung dari pendefinisian variabelnya.
Kita definisikan:
x1 = banyak meja yang akan diproduksi
x2 = banyak kursi yang akan diproduksi
Model umum Pemrograman Linier, untuk kasus di atas, adalah sebagai berikut:
Fungsi tujuan:
Maksimumkan
z = 1200000 x1 + 500000 x2
Kendala:
2x1 + 0.5 x2 ≤ 32
௫భ௫మ
≥ ¼ atau 4x1≥ x2 atau 4x1 – x2 ≥ 0
x1 , x2 ≥ 0
Interpretasi:
z = 1200000 x1 + 500000 x2
Persamaan ini memiliki arti, berapa banyak kursi dan meja yang harus di buat
untuk memaksimalkan keuntungan (z), dimana harga satu unit meja adalah Rp.
1,2 jt dan kursi Rp. 500000.
2x1 + 0.5 x2 ≤ 32
Persamaan ini menjelaskan bahwa untuk merakit satu unit meja, dibutuhkan
waktu 2 jam dan untuk merakit satu unit kursi, dibutuhkan waktu 30 menit (0.5
8
jam), dimana dalam sehari, mereka memiliki waktu maksimal pengerjaan adalah
32 jam (8 jam x 4 karyawan).
4x1 – x2 ≥ 0
Persamaan ini diperoleh dari asumsi bahwa pelanggan pada umumnya membeli
paling banyak 4 kursi untuk 1 meja. Dengan kata lain, perbandingan pembuatan
meja dan kursi adalah 1:4.
x1 , x2 ≥ 0
Ini merupakan syarat wajib, yang artinya banyak kursi dan meja yang dihasilkan
perusahaan, minimal 0 unit (tidak memproduksi sama sekali). Sehingga, nilai x1
dan x2 tidak boleh sama dengan nol.
9
Bagian Ketiga
Contoh dan Latihan Kasus Pemodelan Matematika
1. Seorang peternak memiliki 200 kambing yang mengkonsumsi 90 kg pakan
khusus setiap harinya. Pakan tersebut disiapkan menggunakan campuran jagung
dan bungkil kedelai dengan komposisi sebagai berikut:
Bahan Tiap kg bahan memiliki komposisi berikut (dalam
Kalsium Protein Serat Biaya (Rp/kg)
Jagung 0.001 0.09 0.02 2000
Bungkil kedelai 0.002 0.60 0.06 5500
Kebutuhan pakan kambing setiap harinya adalah paling banyak 1% kalsium, paling
sedikit 30% protein, dan paling banyak 5% serat.
Formulasikan permasalahan di atas kedalam model matematikanya!
Solusi:
Hal pertama yang harus dilakukan adalah mengidentifikasi tujuan, alternatif
keputusan dan sumber daya yang membatasi. Berdasarkan informasi yang diberikan
pada soal, tujuan yang ingin dicapai adalah meminimumkan biaya pembelian bahan
pakan. Alternatif keputusan adalah jumlah jagung dan bungkil kedelai yang akan
digunakan. Sumber daya yang membatasi adalah kandungan kalsium, protein dan
serat pada jagung dan bungkil kedelai, serta kebutuhan jumlah pakan per hari.
Langkah berikutnya adalah memeriksa sifat proporsionalitas, additivitas,
divisibilitas, dan kepastian. Informasi di atas tidak menunjukkan adanya pemberian
diskon, sehingga harga pembelian jagung dan bungkil kedelai per kg tidak berbeda
meskipun pembelian dalam jumlah besar. Hal ini mengisyaratkan bahwa total biaya
yang harus dikeluarkan peternak proporsional terhadap banyak jagung dan bungkil
10
kedelai yang dibeli. Penggunaan sumber daya yang membatasi, dalam hal ini komposisi
jagung dan bungkil kedelai akan serat, protein dan kalsium proporsional terhadap
banyak jagung dan bungkil.
Dengan demikian, dapat dinyatakan sifat proporsionalitas dipenuhi. Total
pengeluaran pembelian bahan pakan merupakan penjumlahan pengeluaran untuk
jagung dan bungkil kedelai. Banyak-nya masing-masing serat, protein, dan kalsium yang
ada di pakan khusus merupakan penjumlah serat, protein, dan kalsium yang ada pada
jagung dan bungkil kedelai. Jumlah pakan khusus yang dihasilkan merupakan
penjumlahan jagung dan bungkil kedelai yang digunakan. Dengan demikian sifat
additivitas dipenuhi. Sifat divisibilitas dan kepastian juga dipenuhi.
Ada dua variabel keputusan dan empat sumber daya yang membatasi. Fungsi
tujuan merupakan minimalisasi, karena semakin kecil biaya akan semakin disukai oleh
peternak. Fungsi kendala pertama (batasan banyak pakan yang dibutuhkan per hari)
menggunakan persamaan (=), fungsi kendala kedua (kebutuhan kalsium) dan kendala
keempat (kebutuhan serat) menggunakan relasi ≤, dan fungsi kendala ketiga (kebutuhan
akan protein) menggunakan relasi ≥.
Kita definisikan:
x1 = banyak jagung yang akan digunakan
x2 = banyak bungkil kedelai yang akan digunakan
Model umum Pemrograman linier kasus di atas adalah:
Fungsi tujuan:
Minimumkan,
z = 2000 x1 + 5500 x2
Kendala:
x1 + x2 = 90
0.001 x1 + 0.002 x2 ≤ 0.9
0.09 x1 + 0.6 x2 ≥ 27
11
0.02 x1 + 0.06 x2 ≤ 4.5
x1, x2 ≥ 0
Latihan
Interpretasikan pemodelan matematika di atas!!!
2. Suatu bank kecil mengalokasikan dana maksimum Rp 180 juta untuk pinjaman
pribadi dan pembelian mobil satu bulan kedepan. Bank mengenakan biaya suku
bunga per tahun 14% untuk pinjaman pribadi dan 12% untuk pinjaman
pembelian mobil. Kedua tipe pinjaman itu dikembalikan bersama dengan
bunganya satu tahun kemudian. Jumlah pinjaman pembelian mobil paling tidak
dua kali lipat dibandingkan pinjaman pribadi. Pengalaman sebelumnya
menunjukkan bahwa 1% pinjaman pribadi merupakan kredit macet.
Formulasikan masalah di atas kedalam bentuk model matematikanya !
Solusi:
Hal pertama yang harus dilakukan adalah mengidentifikasi tujuan, alternatif
keputusan dan sumber daya yang membatasi. Berdasarkan informasi yang diberikan
pada soal, tujuan yang ingin dicapai adalah memaksimumkan pendapatan bunga dan
pengembalian pinjaman. Alternatif keputusan adalah jumlah alokasi pinjaman
pribadi dan pinjaman mobil. Sumber daya yang membatasi adalah jumlah alokasi
anggaran untuk kredit bulan depan dan perbandingan antara jumlah kredit pribadi
dan pembelian mobil.
Sifat proporsionalitas, additivitas, divisibilitas, dan kepastian dipenuhi.
Ada dua variabel keputusan yaitu jumlah anggaran untuk pinjaman pribadi dan
pinjaman pembelian mobil, dan dua sumber daya yang membatasi. Fungsi tujuan
merupakan maksimalisasi, karena semakin besar pendapatan akan semakin disukai oleh
manajemen bank.
12
Kita definisikan:
x1 = banyak anggaran untuk pinjaman pribadi
x2 = banyak anggaran untuk pinjaman pembelian mobil.
Model umum Pemrograman Linier kasus diatas adalah:
Fungsi tujuan:
Maksimumkan,
z = (0.14 – 0.01) x1 + 0.12 x2
Kendala:
x1 + x2 ≤ 180
x2 ≥ 2x1 atau -2x1 + x2 ≥ 0
x1, x2 ≥ 0
Latihan
Interpretasikan pemodelan matematika di atas!!!
3. Suatu pabrik perakitan radio menghasilkan dua tipe radio, yaitu HiFi-1 dan HiFi-2
pada fasilitas perakitan yang sama. Lini perakitan terdiri dari 3 stasiun kerja.
Waktu perakitan masing-masing tipe pada masing-masing stasiun kerja adalah
sebagai berikut:
Stasiun
kerja
Waktu perakitan per unit (menit)
HiFi-1 HiFi-2
1 6 4
2 5 5
3 4 6
13
Waktu kerja masing-masing stasiun kerja adalah 8 jam per hari. Masing-masing
stasiun kerja membutuhkan perawatan harian selama 10%, 14% dan 12% dari
total waktu kerja (8 jam) secara berturut-turut untuk stasiun kerja 1,2 dan 3.
Formulasikan permasalahan ini kedalam model matematikanya !
Solusi:
Alternatif keputusan adalah: radio tipe HiFi-1 (x1) dan radio tipe HiFi-2 (x2).
Tujuannya adalah memaksimumkan jumlah radio HiFi-1 dan HiFi-2 yang diproduksi.
Sumber daya pembatas adalah: jam kerja masing-masing stasiun kerja dikurangi
dengan waktu yang dibutuhkan untuk perawatan. Waktu produktif masing-masing
stasiun kerja adalah:
Stasiun 1: 480 menit – 48 menit = 432 menit
Stasiun 2 : 480 menit – 67.2 menit = 412.8 menit
Stasiun 3 : 480 menit – 57.6 menit = 422.4 menit.
Model umum pemrograman linier kasus di atas adalah:
Fungsi tujuan:
Maksimumkan,
z = x1 + x2
Kendala:
6x1 + 4x2 ≤ 432
5x1 + 5x2 ≤ 412.8
4x1 + 6x2 ≤ 422.4
x1, x2 ≥ 0
Latihan
Interpretasikan pemodelan matematika di atas!!!
14
Latihan Kasus
1. Dua produk dihasilkan menggunakan tiga mesin. Waktu masing-masing mesin
yang digunakan untuk menghasilkan kedua produk dibatasi hanya 10 jam per
hari. Produk 1 dijual dengan harga Rp. 2500 dan produk 2, Rp. 3500. Waktu
produksi masing-masing produk ditunjukkan pada tabel di bawah ini:
Produk Waktu produksi (menit)
Mesin 1 Mesin 2 Mesin 3 Mesin 4
1 10 6 8 2
2 5 20 15 3
Formulasikan permasalahan di atas ke dalam model matematikanya dan
interpretasikan hasilnya!
2. Empat produk diproses secara berurutan pada 2 mesin. Waktu produksi per unit
produk pada kedua mesin ditunjukkan tabel di bawah ini:
Mesin Waktu per unit (jam)
Produk 1 Produk 2 Produk 3 Produk 4
1 2 3 4 2
2 3 2 1 2
Biaya total untuk memproduksi setiap unit produk didasarkan secara langsung
pada jam mesin. Asumsikan biaya operasional per jam mesin 1 dan 2 secara
berturut-turut adalah Rp. 10 dan Rp. 5. Waktu yang disediakan untuk
memproduksi keempat produk pada mesin 1 adalah 500 jam dan mesin 2 adalah
380 jam. Harga jual per unit keempat produk secara berturut-turut adalah Rp. 65,
Rp. 70, Rp. 55, dan Rp. 45.
15
Formulasikan permasalahan di atas ke dalam model matematikanya dan
interpretasikan hasilnya !
3. Suatu perusahaan manufaktur menghentikan produksi salah satu produk yang
tidak menguntungkan. Penghentian ini menghasilkan kapasitas produksi yang
menganggur (berlebih). Kelebihan kapasitas produksi ini oleh manajemen
sedang dipertimbangkan untuk dialokasikan ke salah satu atau ke semua produk
yang dihasilkan (produk 1, 2, dan 3). Kapasitas yang tersedia pada mesin yang
mungkin akan membatasi output diringkaskan pada tabel berikut:
Tipe
mesin
Waktu yang dibutuhkan produk pada
masing-masing mesin (jam) Waktu yang
tersedia (jam per
minggu) Produk 1 Produk 2 Produk 3
Mesin
milling 9 3 5 500
Lathe 5 4 0 350
Grinder 3 0 2 150
Bagian penjualan mengindikasikan bahwa penjualan potensial untuk produk 1
dan 2 tidak akan melebihi laju produksi maksimum dan penjualan potensial
untuk produk 3 adalah 20 unit per minggu. Keuntungan per unit masing-masing
produk secara berturut-turut adalah Rp. 50, Rp. 20, dan Rp. 25.
Formulasikan permasalahan diatas kedalam model matematika dan
interpretasikan hasilnya!
16
Bagian Keempat
Metode Grafik
Dalam menyelesaikan permasalahan program linier, ada dua pendekatan yang
dapat kita gunakan, yaitu metode grafik dan metode simpleks. Metode grafik hanya bisa
digunakan untuk menyelesaikan permasalahan dimana variabel keputusan sama dengan
dua. Sedangkan metode simpleks bisa digunakan untuk menyelesaikan permasalahan
dimana variabel keputusan dua atau lebih.
Pada bagian ini, akan dibahas pendekatan penyelesaian permasalahan program
linier dengan menggunakan metode grafik untuk fungsi tujuan baik maksimum maupun
minimum. Untuk metode simpleks, akan dibahas pada bagian berikutnya.
Target yang ingin di capai pada bagian ini, adalah kita dapat menyelesaikan
permasalahan program linier dengan menggunakan metode grafik dan memahami
permasalahan infeasibility, unboundedness, alternative optima, dan redundancy.
Sebelum masuk ke formulasi permasalahan, ada baiknya kita membahas sedikit
mengenai permasalahan-permasalahan khusus pada pemograman linier, diantaranya
masalah Infeasibility, yaitu suatu kondisi dimana tidak ada area layak (daerah hasil)
yang memenuhi semua kendala, Redundancy, yaitu menargetkan sesuatu diluar batas
kemampuan produksi, Unboundedness, yaitu suatu kondisi dimana area layak tidak
terbatas, dan Alternatif Optima, yaitu situasi dimana terdapat lebih dari satu solusi
optimal. Untuk lebih detailnya, akan kita bahas pada bagian terakhir buku ini, berikut
contoh kasusnya.
Formulasi Permasalahan
Metode grafik hanya bisa digunakan untuk menyelesaikan permasalahan dimana
hanya terdapat dua variabel keputusan. Untuk menyelesaikan permasalahan tersebut,
langkah pertama yang harus dilakukan adalah memformulasikan permasalahan yang
ada ke dalam bentuk Linear Programming (LP).
Berikut ini, langkah-langkah yang harus kita lakukan dalam memformulasikan
permasalahan tersebut:
17
1. Pahamilah secara menyeluruh permasalahan manajerial yang dihadapi
2. Identifikasikan tujuan dan kendalanya
3. Definisikan variabel keputusannya
4. Gunakan variabel keputusan untuk merumuskan fungsi tujuan dan fungsi
kendala secara matematis.
Sebagai contoh dalam memformulasikan permasalahan, berikut ini akan dibahas
perusahaan Krisna Furniture yang akan membuat meja dan kursi. Keuntungan yang
diperoleh dari satu unit meja adalah Rp. 7,- sedangkan keuntungan yang diperoleh dari
satu unit kursi adalah Rp. 5,-. Namun, untuk meraih keuntungan tersebut, Krisna
Furniture menghadapi kendala keterbatasan jam kerja. Untuk pembuatan 1 unit meja
dia memerlukan 4 jam kerja. Untuk pembuatan 1 unit kursi dia membutuhkan 3 jam
kerja. Untuk pengecatan 1 unit meja dibutuhkan 2 jam kerja, dan untuk pengecatan 1
unit kursi dibutuhkan 1 jam kerja. Jumlah jam kerja yang tersedia untuk pembuatan
meja dan kursi adalah 240 jam per minggu sedangkan jumlah jam kerja untuk
pengecatan adalah 100 jam per minggu. Berapa jumlah meja dan kursi yang sebaiknya
diproduksi agar keuntungan perusahaan maksimum?
Dari kasus di atas dapat diketahui bahwa tujuan perusahaan adalah
memaksimumkan profit. Sedangkan kendala perusahaan tersebut adalah terbatasnya
waktu yang tersedia untuk pembuatan dan pengecatan. Apabila permasalahan tersebut
diringkas dalam satu tabel akan tampak sebagai berikut:
Jam kerja untuk membuat 1 unit produk Total waktu yang tersedia per
minggu
Meja Kursi Pembuatan 4 2 240
Pengecatan 2 1 100
Profit per unit 7 5
18
Mengingat produk yang akan dihasilkan adalah meja dan kursi, maka dalam
rangka memaksimumkan profit, perusahaan harus memutuskan berapa jumlah meja
dan kursi yang sebaiknya diproduksi. Dengan demikian dalam kasus ini, yang
merupakan variabel keputusan adalah meja (x1) dan kursi (x2).
Setelah kita mendefinisikan variabel keputusan, maka langkah selanjutnya adalah
menuliskan secara matematis fungsi tujuan dan fungsi kendala.
1. Fungsi Tujuan
Tujuan perusahaan adalah maksimalisasi keuntungan, sehingga kita dapat
menuliskan fungsi tujuan sebagai berikut:
Maksimalkan,
z = 7x1 + 5x2
2. Fungsi kendala
Berkaitan dengan sumber daya yang digunakan, perusahaan tidak bisa
memperkirakan secara tepat kebutuhan sumber daya yang digunakan untuk mencapai
keuntungan tertentu. Biasanya perusahaan menyediakan sumber daya tertentu yang
merupakan kebutuhan minimum atau maksimum. Kondisi seperti ini secara matematis
diungkapkan dengan pertidaksamaan.
Kendala yang pertama adalah waktu yang tersedia di departemen pembuatan.
Total waktu yang diperlukan untuk pembuatan x1 (meja) dimana untuk membuat satu
unit meja diperlukan waktu 4 jam kerja dan untuk pembuatan x2 (kursi) dimana untuk
membuat satu unit kursi diperlukan waktu 3 jam kerja adalah 240 jam. Kalimat ini bisa
dirumuskan dalam pertidaksamaan matematis menjadi:
4x1 + 3x2 ≤ 240
Seperti halnya pada kendala yang pertama, maka pada kendala kedua dapat
diketahui bahwa total waktu yang diperlukan untuk pengecatan x1 (meja) dimana untuk
mengecat satu unit meja diperlukan waktu 2 jam kerja dan untuk pembuatan x2 (kursi)
19
dimana untuk mengecat satu unit kursi dibutuhkan waktu 1 jam kerja adalah 100 jam.
Kalimat ini bisa dirumuskan dalam pertidaksamaan matematis menjadi:
2x1 + x2 ≤ 100
Salah satu syarat yang harus dipenuhi dalam Linear Programming adalah asumsi
nilai x1 dan x2 tidak negatif, yang artinya bahwa:
x1 ≥ 0 (jumlah meja yang diproduksi adalah lebih besar atau sama dengan nol)
x2 ≥ 0 (jumlah kursi yang diproduksi adalah lebih besar atau sama dengan nol)
Dari uraian di atas dapat dirumuskan formulasi permasalahan secara lengkap
sebagai berikut:
Fungsi tujuan:
Maksimalkan,
z = 7x1 + 5x2
Fungsi kendala:
4x1 + 3x2 ≤ 240 (kendala departemen pembuatan)
2x1 + x2 ≤ 100 (kendala departemen pengecatan)
x1, x2 ≥ 0 (kendala non negatif pertama dan kedua)
Penyelesaian Program Linier Menggunakan Metode Grafik
Kasus Krisna Furniture tersebut akan kita selesaikan dengan metode grafik.
Keterbatasan metode grafik adalah bahwa hanya tersedia dua sumbu ordinat, sehingga
tidak bisa digunakan untuk menyelesaikan kasus yang lebih dari dua variabel
keputusan.
Langkah pertama dalam penyelesaian dengan metode grafik adalah
menggambarkan fungsi kendalanya. Untuk menggambarkan kendala pertama secara
20
grafik, kita harus merubah tanda pertidaksamaan menjadi tanda persamaan seperti
berikut:
4x1 + 3x2 = 240
Kendala ini akan memotong salah satu atau kedua sumbu. Sebagaimana halnya
yang sudah kita pelajari dalam aljabar, bahwa untuk menggambarkan fungsi linear yang
tidak lain merupakan garis lurus, maka kita akan mencari titik potong garis tersebut
dengan kedua sumbu. Suatu garis akan memotong salah satu sumbu apabila nilai
variabel yang lain sama dengan nol. Dengan demikian kendala pertama akan memotong
x1, pada saat x2 = 0, demikian juga kendala ini akan memotong x2, pada saat x1 = 0.
Kendala I: 4x1 + 3x2 = 240
Memotong sumbu x1 pada saat x2 = 0
4x1 + 0 = 240
x1 = 240/4
x1 = 60.
Memotong sumbu x2 pada saat x1 = 0
0 + 3x2 = 240
x2 = 240/3
x2 = 80
Kendala I memotong sumbu x1 pada titik (60, 0) dan memotong sumbu x2 pada
titik (0, 80).
Kendala II: 2x1 + x2 = 100
Memotong sumbu x1 pada saat x2 = 0
21
2x1 + 0 = 100
x1 = 100/2
x1 = 50
Memotong sumbu x2 pada saat x1 =0
0 + x2 = 100
x2 = 100
Kendala II memotong sumbu x1 pada titik (50, 0) dan memotong sumbu x2 pada
titik (0, 100).
Berikut gambar grafik, yang kita rangkum dari kendala I dan II diatas:
Gambar 4. 1
Titik potong kedua kendala, bisa dicari dengan cara metode substitusi atau eliminasi,
yaitu:
2x1 + x2 = 100
22
x2 = 100 – 2x1
4x1 + 3 x2 = 240
4x1 + 3 (100 – 2x1) = 240
4x1 + 300 – 6x1 = 240
- 2x1 = 240 - 300
- 2x1 = - 60
x1 = -60/-2 = 30.
x2 = 100 – 2x1
x2 = 100 - 2 * 30
x2 = 100 - 60
x2 = 40
Sehingga kedua kendala akan saling berpotongan pada titik (30, 40).
Tanda ≤ pada kedua kendala ditunjukkan pada area sebelah kiri dari garis
kendala. Sebagaimana nampak pada gambar diatas, feasible region (area layak) meliputi
daerah sebelah kiri dari titik A (0, 80), B (30, 40), dan C (60, 0).
Untuk menentukan solusi yang optimal, ada dua cara yang bisa kita gunakan,
yaitu:
1. Dengan menggunakan garis profit (iso profit line)
2. Dengan titik sudut (corner point)
Penyelesaian dengan menggunakan garis profit adalah penyelesaian dengan
menggambarkan fungsi tujuan. Kemudian fungsi tujuan tersebut digeser ke kanan
sampai menyinggung titik terjauh dari dari titik nol, tetapi masih berada pada area layak
(feasible region).
23
Untuk menggambarkan garis profit, kita mengganti nilai z dengan sembarang
nilai yang mudah dibagi oleh koefisien pada fungsi profit. Pada kasus ini angka yang
mudah dibagi angka 7 (koefisien x1) dan 5 (koefisien x2) adalah 35. Sehingga fungsi
tujuan menjadi 35 = 7x1 + 5x2. Garis ini akan memotong sumbu x1 pada titik (5, 0) dan
memotong sumbu x2 pada titik (0, 7).
Gambar 4. 2
Dari gambar 4. 2, dapat dilihat bahwa iso profit line menyinggung titik B yang
merupakan titik terjauh dari titik nol. Titik B ini merupakan titik optimal. Untuk
mengetahui berapa nilai x1 dan x2, serta nilai z pada titik B tersebut, kita mencari titik
potong antara kendala I dan kendala II (karena titik B merupakan perpotongan antara
kendala I dan kendala II).
Dengan menggunakan eliminiasi atau subustitusi diperoleh nilai x1 = 30, x2 = 40.
dan z = 410. Dari hasil perhitungan tersebut maka dapat disimpulkan bahwa keputusan
perusahaan yang akan memberikan profit maksimal adalah memproduksi x1 sebanyak
30 unit, x2 sebanyak 40 unit dan perusahaan akan memperoleh profit sebesar 410.
Sekarang, kita akan menyelesaikan permasalahan diatas dengan menggunakan
metode yang berbeda, yaitu menggunakan titik sudut (corner point), artinya kita harus
mencari nilai tertinggi dari titik-titik yang berada pada area layak (feasible region). Dari
24
gambar yang pertama diatas, dapat dilihat bahwa ada 4 titik yang membatasi area layak,
yaitu titik O (0, 0), A (0, 80), B (30, 40), dan C (50, 0).
Keuntungan pada titik O (0, 0) adalah (7 * 0) + (5 * 0) = 0.
Keuntungan pada titik A (0, 80) adalah (7 * 0) + (5 * 80) = 400.
Keuntungan pada titik B (30, 40) adalah (7 * 30) + (5 * 40) = 410.
Keuntungan pada titik C (50, 0) adalah (7 * 50) + (5 * 0) = 350.
Karena keuntungan tertinggi jatuh pada titik B, maka sebaiknya perusahaan
memproduksi meja sebanyak 30 unit dan kursi sebanyak 40 unit, dan perusahaan
memperoleh keuntungan optimal sebesar 410.
Latihan
PT Padat Karya memproduksi dua macam batako: batako semen dan batako
kapur. Biaya pembuatan batako semen diperkirakan Rp. 150,- sedang biaya pembuatan
batako kapur diperkirakan Rp. 100,-. Batako semen dijual seharga Rp. 400,- dan batako
kapur dijual seharga Rp. 250,-.
Untuk pembuatan kedua macam batako tersebut dipergunakan 2 macam mesin,
yaitu mesin pencampur (A) dan mesin pencetak (B). Untuk mencampur batako semen
diperlukan waktu 1 jam, dan untuk mencetak batako semen diperlukan waktu 2 jam.
Batako kapur dicampur selama 1.5 jam dan dicetak selama 1 jam. Selama satu bulan
kapasitas mesin A adalah 320 jam kerja. Sedang kapasitas mesin B adalah 480 jam kerja.
Tentukan keuntungan maksimum perusahaan dan apa yang harus dilakukan perusahaan,
untuk mencapainya dengan menggunakan metode grafik.
Latihan tambahan
Selesaikan semua permasalahan optimalisasi (maksimum maupun minimum),
baik berupa contoh kasus maupun latihan kasus, yang terdapat pada bagian kedua dan
ketiga, dengan menggunakan metode grafik (menggunakan garis profit dan titik sudut).
25
Bagian Kelima
Metode Simpleks
Salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman
linier adalah metode simpleks. Penentuan solusi optimal menggunakan metode
simpleks didasarkan pada teknik eleminasi Gauss Jordan. Penentuan solusi optimal
dilakukan dengan memeriksa titik ekstrim satu per satu dengan cara perhitungan
iteratif. Sehingga penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap
yang disebut dengan iterasi. Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1).
Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks,
diantaranya:
1. Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung
dari nilai tabel sebelumnya.
2. Variabel non basis adalah variabel yang nilainya diatur menjadi nol pada
sembarang iterasi. Dalam terminologi umum, jumlah variabel non basis selalu sama
dengan derajat bebas dalam sistem persamaan.
3. Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang iterasi.
Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala
menggunakan relasi ≤) atau variabel buatan (jika fungsi kendala menggunakan
relasi ≥ atau =). Secara umum, jumlah variabel basis selalu sama dengan jumlah
fungsi pembatas (tanpa fungsi non negatif).
4. Solusi atau nilai kanan merupakan nilai sumber daya pembatas yang masih
tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah sumber daya
pembatas awal yang ada, karena aktivitas belum dilaksanakan.
5. Variabel slack adalah variabel yang ditambahkan ke model matematika kendala
untuk mengkonversikan relasi ≤ menjadi relasi =. Penambahan variabel ini terjadi
pada tahap inisialisasi. Pada solusi awal, variabel slack akan berfungsi sebagai
variabel basis.
6. Variabel surplus adalah variabel yang dikurangkan dari model matematika kendala
untuk mengkonversikan relasi ≥ menjadi relasi =. Penambahan ini terjadi pada tahap
26
inisialisasi. Pada solusi awal, variabel surplus tidak dapat berfungsi sebagai variabel
basis.
7. Variabel buatan adalah variabel yang ditambahkan ke model matematika kendala
dengan bentuk ≥ atau = untuk difungsikan sebagai variabel basis awal. Penambahan
variabel ini terjadi pada tahap inisialisasi. Variabel ini harus bernilai 0 pada solusi
optimal, karena kenyataannya variabel ini tidak ada. Variabel hanya ada di atas
kertas.
8. Kolom pivot (kolom kerja) adalah kolom yang memuat variabel masuk. Koefisien
pada kolom ini akn menjadi pembagi nilai kanan untuk menentukan baris pivot
(baris kerja).
9. Baris pivot (baris kerja) adalah salah satu baris dari antara variabel basis yang
memuat variabel keluar.
10. Elemen pivot (elemen kerja) adalah elemen yang terletak pada perpotongan
kolom dan baris pivot. Elemen pivot akan menjadi dasar perhitungan untuk tabel
simpleks berikutnya.
11. Variabel masuk adalah variabel yang terpilih untuk menjadi variabel basis pada
iterasi berikutnya. Variabel masuk dipilih satu dari antara variabel non basis pada
setiap iterasi. Variabel ini pada iterasi berikutnya akan bernilai positif.
12. Variabel keluar adalah variabel yang keluar dari variabel basis pada iterasi
berikutnya dan digantikan oleh variabel masuk. Variabel keluar dipilih satu dari
antara variabel basis pada setiap iterasi. Variabel ini pada iterasi berikutnya akan
bernilai nol.
Bentuk Baku
Sebelum melakukan perhitungan iteratif (perhitungan yang berdasarkan pada
iterasi-iterasi) untuk menentukan solusi optimal, pertama sekali bentuk umum
pemrograman linier dirubah ke dalam bentuk baku terlebih dahulu. Bentuk baku dalam
metode simpleks tidak hanya mengubah persamaan kendala ke dalam bentuk sama
dengan, tetapi setiap fungsi kendala harus diwakili oleh satu variabel basis awal.
Variabel basis awal menunjukkan status sumber daya pada kondisi sebelum ada
27
aktivitas yang dilakukan. Dengan kata lain, variabel keputusan semuanya masih bernilai
nol. Dengan demikian, meskipun fungsi kendala pada bentuk umum pemrograman linier
sudah dalam bentuk persamaan, fungsi kendala tersebut masih harus tetap berubah.
Ada beberapa hal yang harus diperhatikan dalam membuat bentuk baku, yaitu:
1. Fungsi kendala dengan relasi ≤ dalam bentuk umum, dirubah menjadi persamaan (=)
dengan menambahkan satu variabel slack.
2. Fungsi kendala dengan relasi ≥ dalam bentuk umum, dirubah menjadi persamaan (=)
dengan mengurangkan satu variabel surplus.
3. Fungsi kendala dengan persamaan dalam benttuk umum, ditambahkan satu artificial
variabel (variabel buatan).
Perhatikan kasus A berikut:
Fungsi tujuan:
Minimumkan,
z = 2x1 + 5.5x2
Kendala:
x1 + x2 = 90
0.001x1 + 0.002x2 ≤ 0.9
0.09x1 + 0.6x2 ≥ 27
0.02x1 + 0.06x2 ≤ 4.5
x1, x2 ≥ 0
Bentuk di atas adalah bentuk umum pemrograman liniernya. Jika bentuk diatas,
kita ubah kedalam bentuk baku, model matematika-nya, akan berubah menjadi:
28
Fungsi tujuan:
Minimumkan,
z = 2x1 + 5.5x2
Kendala:
x1 + x2 + s1 = 90
0.001 x1 + 0.002 x2 + s2 = 0.9
0.09 x1 + 0.6 x2 – s3 + s4 = 27
0.02 x1 + 0.06 x2 + s5 = 4.5
x1, x2 , s1, s2, s3, s4, s5 ≥ 0
Fungsi kendala pertama mendapatkan variabel buatan (s1), karena bentuk
umumnya sudah menggunakan bentuk persamaan. Fungsi kendala kedua dan keempat
mendapatkan variabel slack (s2 dan s5) karena bentuk umumnya menggunakan relasi ≤,
sedangkan fungsi kendala ketiga mendapatkan variabel surplus (s3) dan variabel buatan
(s4) karena bentuk umumnya menggunakan relasi ≥.
Perhatikan pula kasus B berikut ini:
Maksimumkan,
z = 2x1 + 3x2
Kendala:
10 x1 + 5 x2 ≤ 600
6 x1 + 20 x2 ≤ 600
8 x1 + 15 x2 ≤ 600
x1, x2 ≥ 0
29
Bentuk di atas juga merupakan bentuk umum. Perubahan ke dalam bentuk baku
hanya membutuhkan variabel slack, karena semua fungsi kendala menggunakan bentuk
relasi ≤ dalam bentuk umumnya. Maka bentuk bakunya adalah sebagai berikut:
Maksimumkan,
z = 2x1 + 3x2 + 0s1 + 0s2 + 0s3
Kendala:
10 x1 + 5 x2 + s1 = 600
6 x1 + 20 x2 + s2 = 600
8 x1 + 15 x2 + s3 = 600
x1, x2 , s1 , s2 , s3 ≥ 0
s1 , s2 , s3 merupakan variabel slack.
30
Bagian Keenam
Alur Penyelesaian Metode Simpleks
Pada bagian ini, kita akan membahas alur penyelesaian permasalahan program
linier dengan menggunakan metode simpleks, dimulai dengan pembentukan tabel
simpleks, sampai penentuan nilai maksimum ataupun minimum-nya, sesuai permintaan
perusahaan.
Pembentukan Tabel Simpleks
Dalam perhitungan iteratif, kita akan bekerja menggunakan tabel dan bentuk
baku yang sudah diperoleh, juga harus dibuat ke dalam bentuk tabel.
Semua variabel, yang bukan variabel basis mempunyai solusi (nilai kanan) sama
dengan nol dan koefisien variabel basis pada baris tujuan harus sama dengan 0. Oleh
karena itu kita harus membedakan pembentukan tabel awal berdasarkan variabel basis
awal. Dalam sub bab ini kita hanya akan memperhatikan fungsi kendala yang
menggunakan variabel slack dalam bentuk bakunya, sedangkan yang menggunakan
variabel buatan akan dibahas pada sub bab lainnya.
Gunakan kasus B di atas, maka tabel awal simpleksnya adalah:
VB x1 x2 s1 s2 s3 solusi
z -2 -3 0 0 0 0
s1 10 5 1 0 0 600
s2 6 20 0 1 0 600
s3 8 15 0 0 1 600
Langkah-Langkah Penyelesaian
Langkah-langkah penyelesaian adalah sebagai berikut:
31
1. Periksa apakah tabel layak atau tidak. Kelayakan tabel simpleks dilihat dari solusi
(nilai kanan). Jika solusi ada yang bernilai negatif, maka tabel tidak layak. Tabel yang
tidak layak tidak dapat diteruskan untuk dioptimalkan.
2. Tentukan kolom pivot. Penentuan kolom pivot dilihat dari koefisien fungsi tujuan
(nilai di sebelah kanan baris z) dan tergantung dari bentuk tujuan. Jika tujuan
maksimalisasi, maka kolom pivot adalah kolom dengan koefisien paling negatif. Jika
tujuan minimalisasi, maka kolom pivot adalah kolom dengan koefisien positif
terbesar. Jika kolom pivot ditandai dan ditarik ke atas, maka kita akan mendapatkan
variabel keluar. Jika nilai paling negatif (untuk tujuan maksimalisasi) atau positif
terbesar (untuk tujuan minimalisasi) lebih dari satu, pilih salah satu secara
sembarang.
3. Tentukan baris pivot. Baris pivot ditentukan setelah membagi nilai solusi dengan
nilai kolom pivot yang bersesuaian (nilai yang terletak dalam satu baris). Dalam hal
ini, nilai negatif dan 0 pada kolom pivot tidak diperhatikan, artinya tidak ikut
menjadi pembagi. Baris pivot adalah baris dengan rasio pembagian terkecil. Jika
baris pivot ditandai dan ditarik ke kiri, maka kita akan mendapatkan variabel keluar.
Jika rasio pembagian terkecil lebih dari satu, pilih salah sau secara sembarang.
4. Tentukan elemen pivot. Elemen pivot merupakan nilai yang terletak pada
perpotongan kolom dan baris pivot.
5. Bentuk tabel simpleks baru. Tabel simpleks baru dibentuk dengan pertama sekali
menghitung nilai baris pivot baru. Baris pivot baru adalah baris pivot lama dibagi
dengan elemen pivot. Baris baru lainnya merupakan pengurangan nilai kolom pivot
baris yang bersangkutan dikali baris pivot baru dalam satu kolom terhadap baris
lamanya yang terletak pada kolom tersebut.
6. Periksa apakah tabel sudah optimal. Keoptimalan tabel dilihat dari koefisien fungsi
tujuan (nilai pada baris z) dan tergantung dari bentuk tujuan. Untuk tujuan
maksimalisasi, tabel sudah optimal jika semua nilai pada baris z sudah positif atau 0.
Pada tujuan minimalisasi, tabel sudah optimal jika semua nilai pada baris z sudah
negatif atau 0. Jika belum, kembali ke langkah no. 2 , jika sudah optimal baca solusi
optimalnya.
32
Bagian Ketujuh
Contoh Kasus Metode Simpleks
Selesaikan kasus berikut ini menggunakan metode simpleks:
Maksimumkan,
z = 8x1 + 9x2 + 4x3
Kendala:
x1 + x2 + 2x3 ≤ 2
2x1 + 3x2 + 4x3 ≤ 3
7x1 + 6x2 + 2x3 ≤ 8
x1,x2,x3 ≥ 0
Solusi:
Bentuk bakunya adalah:
Maksimumkan,
z = 8 x1 + 9 x2 + 4x3 + 0s1 + 0s2 + 0s3
atau
z - 8 x1 - 9 x2 - 4x3 + 0s1 + 0s2 + 0s3 = 0
Kendala:
x1 + x2 + 2x3 + s1 = 2
2x1 + 3x2 + 4x3 + s2 = 3
7x1 + 6x2 + 2x3 + s3 = 8
x1,x2,x3 ,s1 , s2 , s3 ≥ 0
33
Tabel awal simpleks:
VB x1 x2 x3 s1 s2 s3 NK Rasio
z -8 -9 -4 0 0 0 0
s1 1 1 2 1 0 0 2
s2 2 3 4 0 1 0 3
s3 7 6 2 0 0 1 8
Karena nilai negatif terbesar ada pada kolom x2, maka kolom x2 adalah kolom pivot, dan x2
adalah variabel masuk. Rasio pembagian nilai kanan dengan kolom pivot terkecil adalah 1
bersesuaian dengan baris s2, maka baris s2 adalah baris pivot dan s2 adalah variabel keluar.
Elemen pivot adalah 3.
VB x1 x2 x3 s1 s2 s3 NK Rasio
z -8 -9 -4 0 0 0 0
s1 1 1 2 1 0 0 2 2
s2 2 3 4 0 1 0 3 1
s3 7 6 2 0 0 1 8 8/6
Iterasi 1
Nilai pertama yang kita miliki adalah nilai baris pivot baru (baris x2). Semua nilai pada baris
s2 pada tabel solusi awal dibagi dengan 3 (elemen pivot).
VB x1 x2 x3 s1 s2 s3 NK Rasio
z
s1
x2 2/3 1 4/3 0 1/3 0 1
s3
34
Perhitungan nilai barisnya:
Baris z:
-8 -9 -4 0 0 0 0
-9 ( 2/3 1 4/3 0 1/3 0 1 ) -
-2 0 8 0 3 0 9
Baris s1:
1 1 2 1 0 0 2
1 (2/3 1 4/3 0 1/3 0 1 ) -
1/3 0 2/3 1 -1/3 0 1
Baris s3:
7 6 2 0 0 1 8
6 ( 2/3 1 4/3 0 1/3 0 1 ) -
3 0 -6 0 -2 1 2
Maka tabel iterasi 1 ditunjukkan tabel di bawah. Selanjutnya kita periksa apakah tabel sudah
optimal atau belum. Karena nilai baris z di bawah variabel x1 masih negatif, maka tabel belum
optimal. Kolom dan baris pivotnya ditandai pada tabel di bawah ini:
VB x1 x2 x3 s1 s2 s3 NK Rasio
z -2 0 8 0 3 0 9 -
s1 1/3 0 2/3 1 -1/3 0 1 3
x2 2/3 1 4/3 0 1/3 0 1 3/2
s3 3 0 -6 0 -2 1 2 2/3
35
Variabel masuk-nya adalah x1 dan variabel keluar-nya, s3 . Hasil perhitungan iterasi ke-2
adalah sebagai berikut:
Iterasi 2:
VB x1 x2 x3 s1 s2 s3 NK Rasio
z 0 0 4 0 5/3 2/3 31/3
s1 0 0 4/3 1 -1/9 -1/9 7/9
x2 0 1 8/3 0 7/9 -2/9 5/9
x1 1 0 -2 0 -2/3 1/3 2/3
Tabel sudah optimal, ini terlihat dari nilai pada baris z sudah bernilai positif atau nol,
sehingga perhitungan iterasi dihentikan.
Perhitungan dalam simpleks menuntut ketelitian tinggi, khususnya jika angka yang
digunakan adalah pecahan. Pembulatan harus diperhatikan dengan baik. Disarankan jangan
menggunakan bentuk bilangan desimal, akan lebih teliti, jika menggunakan bilangan pecahan.
Pembulatan dapat menyebabkan iterasi lebih panjang atau bahkan tidak selesai karena
ketidaktelitian dalam melakukan pembulatan.
Perhitungan iteratif dalam simpleks pada dasarnya merupakan pemeriksaan satu per satu
titik-titik ekstrim layak pada daerah penyelesaian. Pemeriksaan dimulai dari kondisi nol (dimana
semua aktivitas atau variabel keputusan bernilai nol). Jika titik ekstrim berjumlah n, kemungkinan
terburuknya kita akan melakukan perhitungan iteratif sebanyak n kali.
Membaca Tabel Optimal
Membaca tabel optimal adalah bagian penting bagi pengambil keputusan. Ada beberapa hal
yang bisa dibaca dari tabel optimal, yaitu sebagai berikut:
1. Solusi optimal variabel keputusan
2. Status sumber daya
3. Harga bayangan (dual atau shadow prices).
36
Menggunakan tabel optimal:
VB x1 x2 x3 s1 s2 s3 NK
z 0 0 4 0 5/3 2/3 31/3
s1 0 0 4/3 1 -1/9 -1/9 7/9
x2 0 1 8/3 0 7/9 -2/9 5/9
x1 1 0 -2 0 -2/3 1/3 2/3
Solusi optimal:
x1 = 2/3, x2 = 5/9, x3 = 0, dan Z = 31/3, artinya untuk mendapatkan keuntungan maksimum sebesar
31/3, maka perusahaan sebaiknya menghasilkan produk 1 sebesar 2/3 unit dan produk 2 sebesar
5/9 unit.
Status sumber daya:
Sumber daya pertama dilihat dari keberadaan variabel basis awal dari setiap fungsi kendala pada
tabel optimal. Dalam kasus di atas, untuk fungsi kendala pertama periksa keberadaan s1 pada
variabel basis tabel optimal. Periksa keberadaan s2 pada variabel basis tabel optimal untuk fungsi
kendala kedua. Periksa keberadaan s3 pada variabel basis tabel optimal untuk fungsi kendala
ketiga.
s1 = 7/9, artinya sumber daya ini, berlebih (abundant)
s2 = s3 = 0, maksudnya kedua sumber daya ini habis terpakai (scarce).
Harga bayangan:
Harga bayangan dilihat dari koefisien variabel slack atau surplus pada baris fungsi tujuan. Berikut
ini, hasil dari setiap koefisien:
Koefisien s1 pada baris fungsi tujuan tabel optimal = 0, dengan demikian harga bayangan
sumber daya pertama adalah 0.
37
Koefisien s2 pada baris fungsi tujuan tabel optimal = 5/3, dengan demikian harga bayangan
sumber daya kedua adalah 5/3.
Koefisien s3 pada baris fungsi tujuan tabel optimal = 2/3, dengan demikian harga bayangan
sumber daya kedua adalah 2/3.
Latihan
Maksimumkan,
z = 2x1 + 4x2 + x3
Dengan kendala:
x1 + 4x2 + 8x3 ≤ 9
8x1 + 7x2 + 4x3 ≤ 3
3x1 + x2 + 5x3 ≤ 5
x1,x2,x3 ≥ 0
38
Bagian Kedelapan
Variasi Kasus
Penyelesaian Linear Programming Secara Grafik Untuk Fungsi Tujuan
Minimalisasi
Permasalahan minimalisasi dapat juga diselesaikan secara grafik. Langkah-
langkah penyelesaian permasalahan-nya sama dengan penyelesaian permasalahan
untuk fungsi tujuan maksimalisasi yaitu formulasi permasalahan, menentukan area
layak, kemudian menentukan solusi optimal.
Dalam menentukan solusi optimal, seperti halnya pada permasalahan
maksimalisasi, dapat menggunakan pendekatan garis profit atau titik sudut. Untuk lebih
memahami penyelesaian permasalahan minimalisasi, kita akan membahas kasus
Valentine Meal berikut ini.
Valentine Meal adalah makanan yang terbuat dari Jagung dan Kacang. Makanan
ini memiliki kandungan sekurang-kurangnya 30% Protein dan Serat maksimal 5%
sebagaimana tampak pada tabel berikut ini:
Kandungan gizi per kilogram
Protein Serat Biaya
Jagung 0.09 0.02 0.3
Kacang 0.6 0.06 0.9
Valentine Meal ingin menentukan biaya terendah dari makanan tersebut. Karena
makanan tersebut terbuat dari Jagung dan Kacang, variabel keputusan untuk model
tersebut dapat dirumuskan sebagai berikut:
x1 = banyaknya jagung yang digunakan untuk campuran makanan
x2= banyaknya kacang yang digunakan untuk campuran makanan
39
Fungsi tujuan adalah meminimumkan biaya dari campuran makanan, yang
dirumuskan sebagai berikut,
Minimalkan,
z = 0,3x1 + 0,9x2
Kendala dari model mencerminkan jumlah yang diperlukan dan persyaratan
kandungan gizi yang diperlukan. Karena Valentine Meal memerlukan 800 kg makanan
per hari, kendala tersebut bisa dirumuskan demikian:
x1 + x2 ≥ 800
Kandungan protein dalam jagung (x1) dan kacang (x2) adalah (0,09x1 + 0,6x2).
Kandungan protein ini sekurang-kurangnya 30% dari campuran makanan. Oleh karena
itu persamaannya menjadi demikian
0,09x1 + 0,6x2 ≥ 0,3 (x1+ x2)
0,09x1 + 0,6x2 ≥ 0,3x1 + 0,3x2
(0,3x1 - 0,09x1) + (0,3x2- 0,6x2) ≤ 0
0,21x1 - 0,3x2 ≤ 0
Dengan cara yang sama, kendala dari kandungan serat bisa dirumuskan
demikian:
0,02x1 + 0,06x2 ≤ 0,05 (x1 + x2)
0,02x1 + 0,06x2 ≤ 0,05x1 + 0,05x2
(0,05x1 - 0,02x1) + (0,05x2 - 0,06 K) ≥ 0
0,03x1 – 0,01x2 ≥ 0
Dari uraian di atas dapat dirumuskan formulasi permasalahan secara lengkap
sebagai berikut:
40
Fungsi tujuan:
Minimalkan,
z = 0,3x1 + 0,9x2
Fungsi kendala:
x1 + x2 ≥ 800 (kendala kebutuhan makanan per hari)
0,21x1 - 0,3x2 ≤ 0 (kendala kandungan protein)
0,03x1 – 0,01x2 ≥ 0 (kendala kandungan serat)
x1, x2 ≥ 0 (kendala non negatif pertama dan kedua)
Langkah pertama untuk menyelesaikan kasus Valentine Meal adalah dengan
menggambarkan fungsi kendala sebagaimana tampak pada gambar berikut:
Gambar 8. 1
41
Titik potong ketiga kendala bisa dicari dengan cara substitusi atau eliminasi
Titik potong kendala 1 (Protein: 0.21x1 – 0.3x2 ≤ 0) dan 3 (Kebutuhan per hari: 1 Jagung
+ 1 Kacang ≥ 800).
0.21x1 - 0.3x2 = 0
0.21x1 = 0.3x2
x1 = (0.3/ 0.21) x2
x1 + x2 = 800
(0.3 / 0.21) x2 + x2 = 800
2,43 x2 = 800
x2 = 800/2,43
x2 = 329,22 dibulatkan menjadi 329.
x1 + 329,22 = 800
x1 = 470,78 dibulatkan menjadi 471.
Jadi, titik potong kendala 1 (Protein: 0.21x1 – 0.3x2 ≤ 0) dan 3 (Kebutuhan per
hari: 1 Jagung + 1 Kacang ≥ 800) terletak pada titik B (471, 329).
Titik potong kendala 2 (Serat: 0.03x1 – 0.01x2 ≥ 0) dan kendala 3 (Kebutuhan per
hari: 1 Jagung + 1 Kacang ≥ 800).
0.03x1 – 0.01x2 = 0
0.03x1 = 0.01x2
x1 = (0.01/ 0.03) x2
x1 = 0.33 x2
x1 + x2 = 800
0.33 x2 + x2 = 800
42
1.33 x2 = 800
x2 = 800 / 1.33
x2 = 600
x1 + 600 = 800
x1 = 200
Jadi titik potong kendala 2 (Serat: 0.03x1 – 0.01x2 ≥ 0) dan kendala 3 (Kebutuhan
per hari: 1 Jagung + 1 Kacang ≥ 800) terletak pada titik B (200, 600).
Tanda ≥ pada kendala Serat dan Kebutuhan per hari ditunjukkan pada area
sebelah kanan dari garis kendala. Sebagaimana nampak pada gambar 8. 1, feasible region
(area layak) meliputi daerah sebelah kanan dari titik A (200, 600), B (471, 329), atau di
sebelah kanan kendala II dan III serta di sebelah kiri kendala I.
Untuk menentukan solusi yang optimal, ada dua cara yang bisa digunakan yaitu
1. Dengan menggunakan garis biaya (iso cost line)
2. Dengan titik sudut (corner point)
Penyelesaian dengan menggunakan isocost line adalah penyelesaian dengan
menggambarkan fungsi tujuan. Kemudian fungsi tujuan tersebut digeser ke kiri sampai
menyinggung titik terdekat dari titik nol, tetapi masih berada pada area layak (feasible
region). Untuk menggambarkan garis isocost, kita mengganti nilai z dengan sembarang
nilai yang mudah dibagi oleh koefisien pada fungsi biaya. Pada kasus ini angka yang
mudah dibagi angka 0.3 (koefisien x1) dan 0.9 (koefisien x2) adalah 270. Sehingga fungsi
tujuan menjadi 270= 0.3x1 + 0.9x2. Garis ini akan memotong sumbu x1 pada titik (900, 0)
dan memotong sumbu x2 pada titik (0, 300).
43
Gambar 8. 2
Dari gambar 8. 2, kita dapat melihat bahwa iso cost line menyinggung titik A yang
merupakan titik terdekat dari titik nol. Titik A ini merupakan titik optimal. Untuk
mengetahui berapa nilai x1 dan x2, serta nilai z pada titik A tersebut, kita mencari titik
potong antara kendala I dan kendala III (karena titik A merupakan perpotongan antara
kendala I dan kendala III).
Dengan menggunakan eliminiasi atau substitusi diperoleh nilai x1 = 471, x2 = 329.
dan z = 437. Dari hasil perhitungan tersebut maka dapat disimpulkan bahwa keputusan
perusahaan yang akan memberikan biaya minimal adalah x1 sebanyak 471 unit, x2
sebanyak 329 unit dan perusahaan akan mengalokasikan biaya sebesar 437.
Penyelesaian dengan menggunakan titik sudut (corner point) dari gambar 8. 1,
dapat dilihat bahwa ada 2 titik yang dekat yang membatasi area layak, yaitu titik A yang
merupakan perpotongan kendala I dan III serta titik B yang merupakan perpotongan
kendala II dan III. Untuk penyelesaian dengan menggunakan titk sudut kita mencari nilai
z di kedua titik tersebut kemudian kita pilih nilai z yang paling kecil.
44
Titik A nilai x1 = 471 dan x2 = 329. Dengan substitusi angka tersebut ke fungsi
tujuan kita peroleh 0,3x1 + 0,9x2 = (0,3 * 471) + (0,9 * 329) = 437,4 dibulatkan menjadi
437. dan pada titik B nilai x1 = 200 dan x2 = 600.
Dengan mensubstitusikan nilai x1 dan x2 pada fungsi tujuan, kita peroleh: 0,3x1 +
0,9x2 = (0,3 * 200) + (0,9 * 600) = 600. Ternyata nilai z pada titik A lebih kecil daripada
titik B. Dengan demikian titik A adalah titik optimal.
Permasalahan Teknis dalam Program Linier
Dalam penyelesaian permasalahan program linear, yang menggunakan metode
grafik, sering dijumpai permasalahan-permasalahan secara teknis, seperti:
1. Infeasibility
2. Unboundedness
3. Redundancy
4. Alternate optimal solutions
Infeasibility adalah suatu kondisi dimana tidak ada area layak yang memenuhi
semua kendala. Sebagai contoh Apabila kasus Krisna Furniture ditambah kendala dari
bagian pemasaran yang memberi syarat bahwa penjualan Meja minimal 60 buah dan
penjualan Kursi minimal 60 buah, maka akibatnya tidak ada area layak (feasible region).
Kondisi seperti ini disebut infeasibility.
Fungsi tujuan:
Maksimalkan,
z = 7x1 + 5x2
Fungsi kendala:
4x1 + 3x2 ≤ 240 (kendala departemen pembuatan)
2x1 + x2 ≤ 100 (kendala departemen pengecatan)
x1, x2 ≥ 60
x1, x2 ≥ 0 (kendala non negatif pertama dan kedua)
45
Gambar 8. 3. infeasibility
Unboundedness adalah suatu kondisi dimana area layak tidak terbatas. Kasus ini
biasanya muncul pada fungsi tujuan maksimalisasi. Misalkan saja Krisna Furniture lebih
dahulu menentukan kendala dari pemasaran dan belum menentukan kendala dari segi
operasi untuk assembling dan finishing. maka objective function menjadi tidak berhingga.
Fungsi tujuan :
Maksimalkan,
z = 7x1 + 5x2
Fungsi kendala :
x1, x2 ≥ 60
x1, x2 ≥ 0 (kendala non negatif pertama dan kedua)
Gambar 8. 4. Unboundedness
46
Redundancy constraint merupakan Constraint yang tidak mempengaruhi
feasible region. Misalkan pada kasus Krisna Furniture, bagian marketing mengatakan
bahwa tidak bisa menjual lebih dari 50 buah kursi, maka pernyataan ini disebut
redundant. Karena kenyataannya, bagian produksi maksimal hanya bisa memproduksi
40 kursi.
Gambar 8. 5. Redundancy constraint
Alternatif Optima adalah situasi dimana terdapat lebih dari satu solusi optimal.
Hal ini akan terjadi apabila garis profit sejajar dengan salah satu kendala. Misalkan kita
rubah profit margin untuk Meja dan Kursi pada kasus Krisna Furniture menjadi 8 dan 6.
Garis profit ini jika kita gambarkan akan sejajar dengan kendala I karena kemiringannya
sama. Solusi optimalnya terletak sepanjang garis AB. Jadi solusi optimalnya bisa terletak
pada alternatif I x1 = 0 dan x2 = 80 atau x1 = 30 dan x2 = 40 atau kombinasi lain
sepanjang garis AB.
Fungsi tujuan:
Maksimalkan,
z = 8x1 + 6x2.
Fungsi kendala :
4x1 + 3x2 ≤ 240 (kendala departemen pembuatan)
2x1 + x2 ≤ 100 (kendala departemen pengecatan)
47
x1, x2 ≥ 0 (kendala non negatif pertama dan kedua)
Gambar 8. 6. Alternatif Optima
48
Daftar Pustaka
Levin, Richard I., David S. Rubin, Joel P. Stinson, dan Everette S. Gardner, Jr. (1992).
Quantitative Approaches to Management, eighth edition, New York, McGraw-Hill.
Render, Barry dan Jay Heizer. (1997). Principles of Operations Management, second
edition, Upper Saddle River, New Jersey, Prentice Hall, Inc.
Render, Barry, Ralph M. Stair Jr., dan Michael E. Hanna. (2003). Quantitative Analysis for
Management, eighth edition, Upper Saddle River, New Jersey, Prentice Hall, Inc.
Siringoringo, Hotniar. Seri Teknik Riset Operasional. Pemrograman Linear. Penerbit
Graha Ilmu. Yogyakarta. 2005.
Taha, Hamdy A. (1997). Operations Research, an Introduction, sixth edition, Upper Saddle
River, New Jersey, Prentice Hall, Inc.