BAB I
PENDAHULUAN
A. Latar Belakang
Sebuah perusahaan atau organisasi perlu
merencanakan strategi yang dapat mengoptimalkan hasil yang ingin dicapai, baik
itu berupa keuntungan maksimal atau biaya minimal. Pada dasarnya setiap
perusahaan memiliki keterbatasan atas sumber dayanya, baik keterbatasan dalam
jumlah bahan baku, mesin dan peralatan, ruang, tenaga, kerja, maupun model.
Dengan keterbatasan ini, setiap perusahaan melakukan beberapa cara untuk
melakukan optimasi dengan hasil yang dicapai, salah satunya dengan program
linear (Linear Programming).
Pemrograman linear (linear proramming) adalah
teknik pengambilan keputusan untuk memecahkan masalah mengalokasikan sumber
daya yang terbatas diantara berbagai kepentingan seoptimal mungkin. Pemrograman
linear merupakan salah satu metode dalam riset operasi yang memungkinkan para
manajer mengambil keputusan dengan menggunakan pendekatan analisis kuantitatif.
Teknik ini telah diterapkan secara luas pada berbagai persoalan dalam
perusahaan, untuk menyelesaikan masalah yang berkaitan dengan penugasan
karyawan, penggunaan mesin, distribusi, dan pengangkutan, penentuan kapasitas
produk, ataupun dalam penentuan portofolio investasi.
Linear Programming (LP) adalah suatu metode
programasi yang variabelnya disusun dengan persamaan linier. Oleh berbagai
analist, maka LP diterjemahkan ke dalam Bahasa Indonesia menjadi “programasi
linier”, “pemrograman garis lurus”, “programasi garis lurus” atau lainnya.
Sebagai alat kuantitatif untuk melakuakn pemrograman, maka metode LP juga ada
kelebihan dan kelemahannya. Oleh karena itu, pembaca atau peneliti harus mampu
mengidentifikasi kapan alat ini dipergunakan dan kapan tidak dipergunakan.
B. Rumusan
Masalah
1. Bagaimana sejarah Program Linear?
2. Apa pengertian Program Linear?
3. Bagaimana bentuk umum Program Linear?
C. Tujuan
1. Mengetahui sejarah Program Linear
2. Mengetahui pengertian Program Linear
3. Mengetahui bentuk umum Program Linear
4. Mengetahui cara penyelesaian Program Linear
dengan metode grafik
BAB II
PEMBAHASAN
A.
Sejarah
Program Linear
Model program linier dikembangkan dalam tiga
tahap, anatara lain pada tahun 1939-1947. Pertama kali dikembangkan oleh Leonid
Vitaliyevich Kantorovich, ahli matematika Rusia yang memperoleh Soviet
government’s Leinin Prize pada tahun 1965 dan the Order of Lenin pada tahun
1967; kedua, oleh Tjalillng Charles Koopmans, ahli ekonomi dari belanda yang
memulai karir intelektualnya sebagai fisikawan yang melontarkan teori Kuantum
mekanik; dank e-3, George Bernard Dantzig yang mengembangkan Algoritma
Simpleks.
Pada tahun 1930, Kantorovich dihadapkan pada
kasus nyata optimisasi sumber-sumber yang tersedia di pabrik. Dia mengembangkan
sebuah analisis baru yang nantinya akan dinamakan Pemrograman Linear.
Kemudian pada tahun 1939, Kantorovich menulis buku “The Mathematical Method of
Production Planning and Organization”, di mana Kantorovich menunjukkan bahwa
seluruh masalah ekonomi dapat dilihat sebagai usaha untuk memaksimumkan suatu
fungsi terhadap kendala-kendala. Kuliah Kantotovich pada saat menerima hadiah
Nobel, 11 desember 1975 adalah Mathematics in Economic Achievements,
Difficulties, Perspectives. Di sisi ain, Koopmans sejak awal sudah bergelut
dengan matematika ekonomi dan ekonometri. Dia mengembangkan teknik activity
analiysis yang sekarang dikenal dengan Pemrograman linear. Namun demikian, juga
ada nama-nama lain yang berperan dalam pengembangan model ini, yaitu J. Von
Neuman. Bahkan dia mengembangkan “Activity analiysis of production set” sebelum
dilanjutkan oleh Koopmans. Pada saat itu, teknik yang mereka kembangkan dikenal
dengan istilah “programming of interdependent activities in a linier
structure”. Istilah programan linier diusulkan oleh Koopmans ketika mengunjungi
Dantzig di RAND Corporation pada tahun 1948. Istilah ini menjadi popular hingga
sekarang.
B.
Pengertian
Program Linear
Program
linier adalah merumuskan masalah dengan menggunakan sejumlah informasi yang
tersedia kemudian menerjemahkan masalah tersebut dalam bentuk model matematika.
Sifat linier mempunyai arti bahwa seluruh fiungsi dalam model ini merupakan
fungsi yang linier.
Program
linier (linear programming) adalah merupakan metode matematik dalam
mengalokasikan sumber daya yang langka atau terbatas untuk mencapai tujuan
tunggal seperti memaksimumkan keuntungan atau meminimumkan biaya. Sumber daya
tersebut dapat berupa sumber daya fisik seperti uang, tenaga ahli, material
(bahan dan mesin) ataupun bukan fisik.
Pemrograman
linier berasal dari kata pemrograman dan linier. Pemrograman disini mempunyai
arti kata perencanaan, dan linier ini berarti bahwa fungsi-fungsi yang
digunakan merupakan fungsi linier. Secara umum arti dari pemrograman linier
adalah suatu teknik perencanaan yang bersifat analisis yang
analisis-analisisnya memakai model matematika, dengan tujuan menemukan beberapa
kombinasi alternatif pemecahan masalah kemudian dipilih yang terbaik di
antaranya dalam rangka menyusun strategi dan langkah-langkah kebijaksanaan
lebih lanjut tentang alokasi sumber daya dan dana yang terbatas guna mencapai
tujuan dan sasaran yang di inginkan secara optimal.
C.
Bentuk
Umum Program Linear
Bentuk umum linear programming adalah sebagai
berikut:
Fungsi
tujuan :
Maksimumkan atau minimumkan z = c1x1 + c2x2 +
... + cnxn
Sumber daya yang membatasi :
a11x1 + a12x2 + ... + a1nxn = /≤ / ≥ b1
a21x1 + a22x2 + … + a2nxn = /≤ / ≥ b2
…
am1x1 + am2x2 + … + amnxn = /≤ / ≥ bm
x1, x2, …, xn ≥ 0
Simbol
x1, x2, ..., xn (xi) menunjukkan variabel keputusan. Jumlah variabel
keputusan (xi) oleh karenanya tergantung dari jumlah 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 matematiknya.Simbol a11, ...,a1n,...,amn merupakan penggunaan
per unit variabel keputusan akan sumber daya yang membatasi, atau disebut juga
sebagai koefisien fungsi kendala pada model matematiknya. 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 matematik dari suatu permasalahan bukan hanya menuntut kemampuan
matematik tapi juga menuntut seni permodelan. Menggunakan seni akan membuat
permodelan lebih mudah dan menarik.
D.
Cara
Penyelesaian Program Linear Dengan Metode Grafik
1)
Langkah Penyelesaian Metode Grafik
Ada
beberapa langkah penyelesaian diantaranya sebagai berikut:
a) Buat model yang sesuai
dengan masalah yang ada.
b) Gambar grafik kendala-kendalanya.
c) Tentukan daerah fisibel,
yaitu daerah dalam grafik yang memenuhi semua kendala.
d) Hitung nilai fungsi di
titik-titik sudut segi-n daerah fisibel.
e) Cari titik yang
menghasilkan nilai fungsi yang paling optimal
2) Kasus dan
Penyelesaian Dalam Metode Grafik
Contoh :
Seorang pengusaha Laptop membuat dua macam
tipe, yaitu tipe portable touchscreen (A1) dan tipe flip standar (A2). Kedua
jenis laptop dibuat dari bahan yang sama yaitu X dan Y, dengan komposisi yang
berbeda.
Setiap tipe laptop portable touchscreen dibuat
dari campuran 1 unit bahan X dan 3 bahan Y, sedangkan setiap tipe laptop flip
standar dibuat dari campuran 2 unit bahan X dan 1 unit bahan Y. Karena
keterbatasan pasokan, setiap hari ia hanya memperoleh 20 unit bahan X dan 20
unit bahan Y.
Untuk setiap laptop tipe portable touchscreen
yang ia buat, ia memperoleh keuntungan sebesar 300.000. Untuk setiap laptop
tipe flip standar, ia memperoleh keuntungan sebesar 200.000.
Jika diasumsikan bahwa semua laptop laku
terjual, berapa laptop masing-masing tipe harus ia buat agar keuntungan yang
didapatkan maksimum?
Penyelesaian:
Bahan
|
Laptop tipe portabletouchscreen (A1)
|
Laptop tipe flip
standar (A2)
|
Pasokan Maksimum
|
X
|
1
|
2
|
20
|
Y
|
3
|
1
|
20
|
Untung
|
300.000
|
200.000
|
Maksimumkan, f(x1, x2) = 300.000 x1 + 200.000
x2 è 3 x1 + 2 x2 (dalam ratusan ribu)
Kendala :
x1 + 2 x2 ≤ 20
3 x1 + x2 ≤ 20
x1, x2 ≥ 0
Penggambaran kendala x1 + 2 x2 ≤ 20, 3 x1 + x2
≤ 20 dan x1, x2 ≥ 0
Metode Grafik
Kasus 1.1
Perpotongan bidang yang memenuhi semua kendala
disebut daerah fisibel. Daerah fisibel dalam kasus ini disebut daerah fisibel
AEDO (bagian yang diarsir pada bagian perpotongan bidang AOB dan bidang COD).
Koordinat E dapat dicari dari perpotongan x1 +
2 x2 ≤ 20 dan 3 x1 + x2 ≤ 20 sehingga diperoleh E(4,8).
Titik-titik sudut daerah fisibel dapat melihat
keuntungan maksimum yang ingin dicapai pengusaha:
Titik-titik sudut
daerah fisibel
|
Nilai fungsi , f(x1,
x2) = 3 x1 + 2 x2
3 x1 +
2 x2 (dalam ratusan ribu)
|
O (0,0)
|
3(0) + 2(0) = 0
|
A (0,10)
|
3(0) + 2 (10) = 20
|
E (4,8)
|
3(4) + 2(8) = 12 + 16 = 28
|
D (20/3,0)
|
3(20/3) + 2(0) = 20
|
E.
Cara
Penyelesaian Program Linear Dengan Metode Aljabar
Pemecahan
persoalan PL dengan metode aljabar adalah pemecahan persoalan dengan cara
substitusi antarpersamaan linear pada fungsi pembatas dan fungsi tujuan.
Prinsip
yang digunakan ialah mencari seluruh kemungkinan pemecahan dasar feasible
(layak), kemudian pilih salah satu yang memberikan nilai objektif optimal,
yaitu paling besar (maksimum) atau paling kecil (minimum).
Pemecahan
persoalan Program Linear dengan metode aljabar ini dibagi 3 (tiga) kasus,
yaitu:
a. Kasus Maksimisasi.
kasus
pemecahan persoalan PL yang bertujuan mencari seluruh kemungkinan pemecahan
yang memberikan nilai objektif maksimum.
Langkah-langkah penyelesaian
1) Merubah ketidaksamaan fungsi pembatas
menjadi kesamaan dengan menambah slack variabel
2) Merubah fungsi tujuan dengan menambah
slack variabel bernilai nol
3) Substitusikan fungsi pembatas dan
fungsi tujuan
Contoh-1
: Perusahaan konveksi “Maju” akan memproduksi baju dan celana, dengan:
Fungsi
Tujuan:
Maksimumkan
Z = 8 X1 + 6 X2 (dalam Rp 1.000).
Fungsi
Pembatas :
•
P-Bahan : 4 X1 + 2 X1 ≤ 60
•
Penjahitan : 2 X1 + 4 X2 ≤ 48 X1, X2 ≥ 0
b. Kasus Minimasi
Kasus
pemecahan masalah program linear yang bertujuan seluruh kemungkinan pemecahan
yang memberikan nilai objektif minimum.
Langkah-langkah Penyelesaian
1) Merubah ketidaksamaan fungsi pembatas
menjadi kesamaan dengan mengurangi dengan surplus variabel (S).
2) Merubah fungsi tujuan dengan menambah
surplus variabel bernilai nol.
3) Substitusikan fungsi pembatas dan
fungsi tujuan.
CONTOH:
Seorang
petani modern menghadapi suatu persoalan sebagai berikut: Setiap sapi
peliharaan agar supaya sehat harus diberi makanan yang mengandung paling
sedikit: 27, 21, dan 30 satuan unsur nutrisi jenis A, B, dan C setiap harinya.
Dua jenis makanan M1 dan M2 diberikan kepada sapi peliharaan tersebut. Satu
gram makanan jenis M1 mengandung unsur nutrisi jenis A, B, dan C masing-masing
sebesar 3, 1, dan 1 satuan. Sedangkan satu gram makanan jenis M2 mengandung
unsur nutrisi jenis A,B, dan C masing-masing 1,1, dan 2 satuan. Harga satu gram
M1 dan M2 masing-masing sebesar Rp40.000 dan Rp20.000.- Petani tersebut harus
memutuskan apakah membeli satu jenis makanan saja atau kedua-duanya kemudian
mencampurnya. Tujuan adalah agar jumlah pengeluaran petani tersebut minimum.
c. Kasus-kasus khusus
Beberapa
kasus khusus selain kasus maksimisasi dan minimisasi adalah kasus solusi
optimum ganda dan tidak memiliki solusi yang layak.
LANGKAH-LANGKAH PENYELESAIAN
1) Merubah ketidaksamaan fungsi pembatas
menjadi kesamaan dengan menambah slack variabel
2) Merubah fungsi tujuan dengan menambah
slack variabel bernilai nol
3) Substitusikan fungsi pembatas dan
fungsi tujuan
Contoh :
1)
Solusi Optimum Ganda
a)
Fungsi Tujuan :
Maksimumkan
Z = 4X1 + 4X2
b)
Fungsi Pembatas :
X1 + 2X2
≤ 10
X1 +
6X2 ≤ 36
X1
≤ 4
X1,
X2 ≥ 0
2)
Tidak Memiliki Solusi Layak
a)
Fungsi Tujuan :
Maksimumkan
Z = 5X1 + 3X2
b)
Fungsi Pembatas :
4X1 +
2X2 ≤ 8
X1 ≥ 3
X2 ≥ 7
X1, X2 ≥
0
F.
Cara Penyelesaian
Program Linear Dengan Metode Simplex
Metode
Simpleks: metode pemecahan persoalan program linear yang begitu kompleks dan
luas, dan besar dengan metode aljabar (sederhana) dan grafik sulit dan tidak
dapat diandalkan
Ciri
khas metode simpleks ialah dengan memasukkan kegiatan disposal (disposal
activities). Peranan kegiatan disposal ini adalah untuk menampung sumber daya
yang tersisa atau tidak digunakan. Dengan adanya kegiatan disposal ini kita
dapat membuat ketidaksamaan suatu rumusan matetematika menjadi suatu persamaan.
Metode
simpleks hanya diperkenankan nilai positif dari peubah-peubah Xij.
1. Rumuskan persoalan PL ke dalam model
umum PL (fungsi tujuan dan fungsi pembatas).
2. Merubah model umum PL menjadi model
simpleks:
a. Fungsi Pembatas: tambahkan slack
variabel dan/atau surplus variabel, dan/atau variabel buatan (artifisial var).
b. Fungsi tujuan :
Rubahlah
bentuk fungsi tujuan implisit menjadi persamaan bentuk eksplisit.
Tambahkan/kurangi
dengan slack var, surplus var dan/atau variabel buatan yang bernilai nol.
3. Formulasikan ke dalam Tabel Simpleks.
4. Lakukan langkah-langkah penyelesaian.
Langkah
Penyelesaian
Langkah
1:
Mengubah fungsi tujuan dan batasan-batasan
Langkah
2:
Menyusun persamaan-persamaan di dalam tabel
Langkah
3: Memilih
kolom kunci
Kolom kunci adalah kolom yang merupakan dasar
untuk mengubah table simpleks. Pilihlah kolom yang mempunyai nilai pada garis
fungsi tujuan yang bernilai negatif dengan angka terbesar.
Langkah
4:
Memilih baris kunci
Baris kunci adalah baris yang merupakan dasar
untuk mengubah tabel simpleks, dengan cara mencari indeks tiap-tiap baris
dengan membagi nilai-nilai pada kolom NK dengan nilai yang sebaris pada kolom
kunci.
Pilih baris yang mempunyai indeks positif
dengan angka terkecil. Dalam hal ini batasan ke-2 yang terpilih sebagai baris
kunci. Beri tanda segi empat pada baris kunci. Nilai yang masuk dalam kolom
kunci dan juga masuk dalam baris kunci disebut angka kunci.
Langkah
5:
Mengubah nilai-nilai baris kunci.
Nilai baris kunci diubah dengan cara membaginya
dengan angka kunci
Langkah
6:
Mengubah nilai-nilai selain pada baris kunci
Langkah
7:
Melanjutkan perbaikan
Ulangilah langkah-langkah perbaikan mulai
langkah 3 sampai langkah ke-6 untuk memperbaiki tabel-tabel yang telah
diubah/diperbaiki nilainya. Perubahan baru berhenti setelah pada baris pertama
(fungsi tujuan) tidak ada yang bernilai negatif.
G. Ciri – ciri program liner
Tujuan perusahaan pada umumnya adalah
memaksimalisasi keuntungan, namun karena terbatasnya sumber daya, maka dapat juga
perusahaan meminimalkan biaya.
Linear Programming memiliki empat ciri khusus
yang melekat, yaitu :
1. penyelesaian masalah mengarah pada
pencapaian tujuan maksimisasi atau minimisasi
2. kendala yang ada membatasi tingkat
pencapaian tujuan
3. ada beberapa alternatif penyelesaian
4. hubungan matematis bersifat linear
Secara teknis, ada lima syarat tambahan dari
permasalahan linear programming yang harus diperhatikan yang merupakan asumsi
dasar, yaitu:
1. certainty (kepastian). Maksudnya adalah
fungsi tujuan dan fungsi kendala sudah diketahui dengan pasti dan tidak berubah
selama periode analisa.
2. proportionality (proporsionalitas). Yaitu
adanya proporsionalitas dalam fungsi tujuan dan fimgsi kendala.
3. additivity (penambahan). Artinya aktivitas
total sama dengan penjumlahan aktivitas individu.
4. divisibility Coisa dibagi-bagi). Maksudnya
solusi tidak harus merupakan bilangan integer (bilangan bulat), tetapi bisa
juga berupa pecahan.
5. non-negative variable (variabel tidak
negatif). Artinya bahwa semua nilai jawaban atau variabel tidak negatif.
BAB 3
PENUTUP
A. Kesimpulan
Program
linear adalah suatu cara matematis yang digunakan untuk menyelesaikan masalah
yang berkaitan dengan pengalokasian sumberdaya yang terbatas untuk mencapai
optimasi, yaitu memaksimumkan atau meminimumkan fungsi tujuan yang bergabung
pada sejumlah variabel input. • Yang termasuk dalam komponen model program
linear adalah variable keputusan, fungsi tujuan, dan batasan model.
Program linier bisa di selesaikan menggunakan metode grafik untuk
menentukan persoalan maksimum maupun minimum.
B. Saran
Semoga penulis dan pembaca dapat mengetahui dan
memahami materi program linear ini terutama pengaplikasiannya di bidang sosial
ekonomi pertanian. Jika ada kesalahan dalam penulisan makalah ini penulis
mengharapkan kritikan atau saran dari pembaca.
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.
Taha,
Hamdy A. (1997). Operations Research, an Introduction, sixth edition,
Upper Saddle River, New Jersey, Prentice Hall, Inc.
Nufus ,
Hayatun dan Nurdin, Erdawati .(2016).program linier ,pekanbaru.
mantab banget gan
BalasHapusElemen solder uap
izin copy ya
BalasHapus