PERTEMUAN II.
FORMULASI PL DAN METODE GRAFIK
2.
2.1. RUANG LINGKUP MATERI PEMBELAJARAN
Pada pertemuan ini akan dilakukan formulasi masalah program linier dan
penyelesaiannya dengan metode grafik.
2.2. SASARAN PEMBELAJARAN
Mahasiswa memiliki wawasan yang luas dalam menganalisis masalah
program linier (PL) dengan metode grafik.
2.3. KEGIATAN BELAJAR
2.3.1
Pendahuluan
Setelah mengikuti matakuliah ini, mahasiswa dapat merumuskan masalah
yang terjadi pada dunia nyata ke dalam masalah program linier dan
menyelesaikannya dengan metode grafik.
2.3.2
Uraian Materi
[Link] Formulasi Pemrograman Linier dan Asumsi-Asumsinya
Linear programming (pemrograman linier) merupakan teknik mathematical
programming yang digunakan untuk mengoptimalisasikan sumber daya yang
digunakan. Optimalisasi sangat diperlukan karena sumber daya di dunia ini sangat
terbatas. Pemakaian yang tidak optimal akan sangat merugikan tidak hanya karena
biaya yang membengkak dan menurunksn daya saing, tapi juga bagi kelangsungan
keberadaan sumber daya itu sendiri.
Optimalisasi, atau biasa disebut juga optimisasi, berarti memaksimalisasi atau
meminimalisasi. Maksimalisasi digunakan bila menghitung laba atau pendapatan,
sedangkan minimalisasi untuk menghitung biaya (cost) atau waktu (time). Sebagai
contoh, optimalisasi laba berarti maksimalisasi laba dan optimalisasi biaya berarti
minimalisasi biaya.
Pemrograman linier terdiri atas fungsi objectif/tujuan/sasaran (Objective function)
dan fungsi kendala (Constraints) yang semuanya merupakan fungsi linier. Fungsi
tujuan adalah sebuah fungsi yang menyatakan tujuan dari optimalisasi, sedangkan
fungsi kendala adalah kumpulan dari beberapa fungsi yang menyatakan kendala
atau penghambat dalam usaha pencapaian optimalitas. Umumnya, fungsi tujuan
merupakan sebuah persamaan linier dan fungsi kendala merupakan sekumpulan
pertidaksamaan yang linier. Selanjutnya, fungsi kendala dibedakan atas kendala
struktural dan kendala nonnegatif. Kendala struktural menyatakan kendala yang
menghambat pencapaian optimalitas, sedangkan kendala nonnegative menyatakan
bahwa output yang diperlukan dalam pencapaian optimalitas tersebut tidak boleh
negative. Kesemuanya ini disusun dalam suatu formulasi yang dikenal sebagai
formulasi pemrograman linier.
[Link] Asumsi-Asumsi Dasar Pemrograman Linier
Dalam setiap formulasi masalah, setiap orang harus membuat penyederhanaan
dengan membuat beberapa asumsi. Dalam pemrograman linier, terdapat beberapa
asumsi sebagai berikut:
a.
Proportionality
Ini berarti bahwa naik turunnya nilai fungsi tujuan dan penggunaan sumber
atau fasilitas yang tersedia akan berubah secara sebanding (proportional)
dengan perubahan tingkat kegiatan.
Contoh:
Misalkan Z = c1 x1 + c 2 x 2 + c3 x3 +
+ c n x n , maka setiap pertambahan 1 unit
x1 akan menaikan Z dengan c1. Demikian juga setiap pertambahan 1 unit x2
akan menaikan Z dengan c2. dan seterusnya.
Misalkan a11 x1 + a12 x 2 + a13 x3 +
+ a1n x n b1 , maka setiap pertambahan 1
unit x1 akan menaikan penggunaan sumber/fasilitas 1 dengan a11. Demikian
juga
setiap
pertambahan
unit
x2
akan
menaikan
penggunaan
sumber/fasilitas 1 dengan a12. dan seterusnya.
b.
Additivity
Ini berarti bahwa nilai fungsi tujuan tiap kegiatan tidak saling
mempengaruhi, atau dalam pemrograman linier dianggap bahwa kenaikan
dari nilai fungsi tujuan yang diakibatkan oleh kenaikan suatu kegiatan dapat
ditambahkan tanpa mempengaruhi bagian dari nialia fungsi tujuan yang
diperoleh dari kegiatan lain.
Misalnya:
z = 3x1 + 5 x2 dimana x1 = 10; x2 = 2
Sehingga z = 40
Jika x1 bertambah 1 unit, maka sesuai dengan asumsi pertama, nilai z
menjadi 40 + 3 = 43. Jadi nilai 3 karena kenaikan x1 dapat langsung
ditambahkan pada nilai z mula-mula tanpa mengurangi bagian z yang
diperoleh dari kegiatan 2 ( x 2 ).
c.
Divisibility
Asumsi ini menyatakan bahwa keluaran (output) yang dihasilkan oleh setiap
kegiatan dapat berupa bilangan pecahan. Demikian pula nilai z yang
dihasilkan.
d.
Deterministic (Certainty)
Asumsi ini menyatakan bahwa setiap parameter yang ada dalam
pemrograman linier aij , bi , c j dapat diperkirakan dengan pasti, meskipun
jarang dengan tepat.
[Link] Langkah-langkah Formulasi Pemrograman Linier
Dalam menformulasikan suatu masalah nyata ke dalam pemrograman linier, maka
langkah-langkah berikut akan diperhatikan:
a.
Memahami permasalahan.
b.
Mengidentifikasikan variabel-variabel keputusan.
c.
Menyatakan fungsi tujuan sebagai kombinasi linier dari variabel-variabel
keputusan.
d.
Menyatakan kendala-kendala struktural sebagai kombinasi linier dari
variabel-variabel keputusan.
e.
Menyatakan kendala non negatif dari variabel-variabel keputusan.
Contoh: (masalah maksimalisasi)
Sebuah perusahaan memproduksi dan menjual dua model pipa pemanas yaitu
model A dan model B. komponen penting dari tiap model berupa pompa dan pipa,
yang diperoleh dari supplier. Supplier ini memiliki kemampuan untuk
menyediakan sebanyak yang dibutuhkan. Tiap model membutuhkan sebuah
pompa. Perbedaan kedua model terletak pada panjang pipa yang digunakan dan
waktu untuk memproduksinya. Tiap model A membutuhkan 12 kaki pipa dan 9
jam waktu produksi, sedangkan setiap model B membutuhkan 16 kaki pipa dan 6
jam waktu produksi. Pemilik sekaligus manajer perusahaan ingin memutuskan
berapa banyak tiap model yang sebaiknya diproduksi selama siklus periode
berikunya. Untuk itu, ia melakukan pendataan dan hasilnya adalah perusahaan
hanya memiliki 200 pompa, 2880 kaki pipa dan 1566 jam waktu produksi selama
siklus produksi berikutnya. Dari tiap model A yang terjual akan diperoleh laba
$350, dan $300 dari setiap model B yang terjual. Permasalahannya adalah berapa
banyak model A dan model B yang sebaiknya diproduksi selama siklus produksi
berikut bila ingin memaksimalkan keuntungan?
Penyelesaian:
Untuk memformulasikan masalah di atas, maka kita akan mengikuti langkahlangkah formulasi yang telah disebutkan pada bagian sebelumnya.
1.
Memahami permasalahan.
Untuk kasus di atas sangat mudah dipahami karena permasalahannya
muncul secara eksplisit. Namun kebanyakan masalah menyatakan
permasalahan secara implicit. Untuk menentukan inti permasalahannya,
maka perlu diperhatikan kata-kata kunci seperti:hitung, tentukan, atau
cari.
2.
Mengidentifikasikan variabel-variabel keputusan.
Setelah mampu memahami permasalahan, maka selanjutnya variabelvariabel
keputusan
akan
diidentifikasi.
Variabel-variabel keputusan
menyatakan apa yang ingin dicari dalam upaya pengoptimalan. Dengan kata
lain variabel-variabel keputusan merupakan variabel dari apa yang akan
menjadi keputusan dalam upaya optimalisasi. Dalam kasus di atas, yang
ingin diputuskan adalah banyaknya tiap model yang harus diproduksi untuk
memaksimalkan keuntungan. Sehingga tiap model itulah yang dinyatakan
sebagai variabel keputusan yaitu:
x1 = banyaknya model A yang diproduksi
x2 = banyaknya model B yang diproduksi
3.
Menyatakan fungsi tujuan
sebagai kombinasi linier dari variabel-
variabel keputusan.
Kata kunci untuk menentukan fungsi tujuan adalah optimalisasi,
maksimalisasi, atau, minimalisasi. Kasus di atas bertujuan untuk
memaksimalkan laba, sementara laba yang diperoleh dari tiap model yang
terjual adalah sebesar $350 untuk model A dan $300 untuk model B.
Dengan demikian, fungsi tujuannya dinyatakan sebagai:
Max Z = 350 x1 + 300 x2
4.
Menyatakan kendala-kendala struktural sebagai kombinasi linier dari
variabel-variabel keputusan.
Untuk menemukan apa-apa saja yang menjadi kendala dalam upaya
optimalisasi, cukup dengan memperhatikan setiap angka yang tercantum
dalam soal, tentu saja yang mengandung makna. Kasus di atas
memperlihatkan ada empat objek yang dinyatakan dalam angka yaitu:
pompa, panjang pipa, waktu produksi dan laba. Karena laba yang menjadi
10
tujuan pengoptimalan, maka kendala strukturalnya adalah ketiga objek yang
tersisa. Sehingga untuk kendala pompa: x1 + x2 200 , kendala waktu
produksi: 9 x1 + 6 x2 1566 , dan kendala panjang pipa: 12 x1 + 16 x2 2880 .
5.
Menyatakan kendala non negatif dari variabel-variabel keputusan.
Kendala ini harus selalu ada dalam setiap formulasi pemrograman linier,
baik tercantum dalam soal maupun tidak. Untuk kasus di atas, kendala
nonnegatifnya adalah x1 , x2 0 . Hal ini menunjukkan bahwa output yang
dibutuhkan untuk pencapaian optimalitas tidak mungkin negatif.
Secara ringkas, kasus di atas dapat di tulis sebagai berikut:
Max Z = 350 x1 + 300 x2
Dengan kendala
x1 + x2 200
(kendala pompa)
9 x1 + 6 x2 1566
(kendala waktu produksi)
12 x1 + 16 x2 2880 (kendala panjang pipa)
x1 , x2 0
[Link] Penyelesaian Masalah Program Linier dengan Metode Grafik
Misalkan suatu masalah program linier yang telah diformulasikan
sebagai berikut:
Max z = 140x1 + 160x2
Dengan kendala
2 x1 + 4 x 2 28
(1)
5 x1 + 5 x2 50
(2)
x1 8
(3)
11
x2 6
(4)
x1 , x2 0
Jika masalah program linier di atas diselesaikan dengan metode grafik, maka
diperoleh sebagai berikut:
x2
10
(2)
7
6
Titik
(4)
F
Optimal (6,4)
(3)
D
Feasible Region
(1)
C
B
x1
8
10
Ada paling sedikit dua cara untuk untuk menentukan nilai optimal dari sebuah
masalah program linier yaitu dengan menghitung nilai nilai ekstrim dari daerah
feasible, kemudian menentukan nilai optimalnya yaitu nilai terbesar untuk
masalah maksimum dan nilai terkecil untuk masalah minimum. Karena kasus di
atas merupakan masalah maksimum, maka nilai maksimumnya akan ditentukan
sebagai berikut. Perlu dicatat bahwa angka dalam kurung pada gambar
menunjukkan nomor urut dari setiap persamaan kendalanya.
Koordinat koordinat dari titik sudut daerah feasible adalah berturut-turut
A(0,0), B(8,0), C(8,2), D(6,4), E(2,6) dan F(0,6). Nilai maksimum pada setiap
koordinat seperti terlihat pada tabel berikut:
12
Titik
x1
x2
Nilai fungsi tujuan
z = 140 x1 + 160x2
1120
1440
1480
1240
960
Jadi, berdasarkan hasil dari tabel di atas, dapat disimpulkan bahwa nilai
maksimum dari masalah program linier adalah 1480 dengan x1 = 6 dan x2 = 4 .
Namun masalah yang muncul adalah jika daerah feasibelnya mempunyai
banyak titik sudut. Jadi untuk menentukan nilai optimalnya, kita harus
menghitung semua nilai fungsi tujuan pada setiap titik sudutnya yang merupakan
pekerjaan yang tidak efisien.
Oleh karena itu, cara lain untuk menentukan nilai optimal masalah program
linier dengan metode grafik adalah dengan menggunakan garis slidik. Garis ini di
buat dari persamaan fungsi tujuan. Dari contoh di atas, persamaan dari slidik bisa
dibuat dengan mengambil nilai z = 1120 sehingga diperoleh garis putus putus
pada gambar berikut. Jika garis tersebut geser ke atas, maka akan berakhir pada
suatu titik yang merupakan nilai maksimum dari masalah program linier. Tahap
terakhir adalah menentukan koordinat dari titik terakhir tersebut. Kadang
kadang garis slidik tersebut akan berimpit dengan sebuah garis kendalanya. Dalam
kasus ini disebut ada alternatif penyelesaian yang tak berhingga banyaknya.
Keunikan dari kasus ini adalah nilai optimal dari suatu masalah program linier
akan tetap tetapi nilai keputusannya berbeda beda. Jadi nilai maksimum dari
masalah program linier di atas adalah 1480 dengan x1 = 6 dan x2 = 4 .
13
x2
10
(2)
7
Titik
(4)
Optimal (6,4)
(3)
D
Feasible Region
(1)
C
B
x1
8
10
Dari contoh-contoh yang telah dibahas mengillustrasikan sifat-sifat program
linier sebagai berikut:
a. Daerah feasible dari sebuah program linier adalah himpunan konveks.
b. Jenis solusi dari program linier adalah tepat satu, tidak ada atau tak
berhingga banyaknya solusi. Jika sebuah program linier (PL) mempunyai
dua solusi optimal, maka PL tersebut mempunyai tak berhingga
banyaknya solusi optimal. Ini disebabkan karena sebarang titik pada
segmen garis yang menghubungkan dua titik optimal adalah optimal.
c. Jika sebuah PL mempunyai sebuah solusi optimal, maka PL tersebut
mempunyai paling sedikit satu titik ekstrim yang merupakan titik optimal.
d. Himpunan konveks dari daerah feasible sebuah PL mempunyai titik
ekstrim yang berhingga.
Ada sebuah algoritma yang disebut algoritma simpleks yang memberikan
sebuah prosedur untuk menyelesaikan masalah program linier yang akan dibahas
pada bagian selanjutnya. Pada dasarnya, algoritma simpleks menguji titik ekstrim
dari sebuah himpunan konveks. Mulai dari sebuah titik ekstrim, algoritma
simpleks memilih titik ekstrim yang ada di sekitarnya, jika ada, sedemikian
14
sehingga nilai fungsi tujuan adalah lebih baik atau tetap sama dengan yang
sebelumnya. Karena terdapat berhingga banyaknya titik ekstrim dari sebuah
himpunan konveks dari solusi-solusi feasible, maka algoritma simpleks akan
menemukan solusi optimal atau menunjukkan bahwa masalah PL yang sedang
dikaji adalah tak terbatas dengan berhingga langkah.
2.3.3 Penutup
[Link] Soal Tes Formatif
Formulasikan masalah program linier berikut:
Tersedia dua macam kapsul obat flu katakanlah fluin dan fluon yang masingmasing mengandung unsur-unsur aspirin, bikarbonat dan kodein. Kandungan
unsur dalam masing-masing kapsul dan syarat kebutuhan minimum pasien akan
unsur-unsur tersebut supaya sembuh tertera dalam tabel berikut:
Satu Kapsul
unsur
Minimum
kebutuhan
Fluin
Fluon
Aspirin
12
Bikarbonat
74
Kodein
24
Harga satuan
$20
$30
Tentukanlah banyaknya fluin dan fluon yang harus dibeli supaya pasien sembuh
dan ongkos beli seminimal mungkin.
[Link] Bacaan Yang Dianjurkan
Mahasiswa diharapkan membaca buku Susanta (1978), Bazaraa et al.
(2010), Gass (2003), Hillier and Lieberman (2001), Taha (2006) dan beberapa
sumber dari internet yang berhubungan dengan topik perkuliahan.
15