Makalah
Pemerograman linier untuk menentukan
Nilai maksimum dan minimum
Dengan garis selidik
 |
Nama
Kelompok 3 :
1.
HARNITA APRIANI
2.
DELLA AGUSTIYANA
3.
CICIA API OKTARI
4.
KHUSNUL ATIMA
5.
RAHMAN HAKIM
DINAS PENDIDIKAN DAN KEBUDAYAAN
SMAN 7 BENGKULU SELATAN
2019
Kata Pengantar
Puji syukur kita
panjatkan kehadirat Allah SWT, dengan rahmat dankaruniaNYA penyusunan
makalah ini selesai sesuai dengan apa yangdiharapkan.
Shalawat serta salam
selalu tercurahkan kepada junjungan kitanabi besar Muhammad SAW dan tak
lupa saya ucapkan terimakasih atassemua pihak yang ikut membantu
penyusunan makalah tentang Persamaandan tidak persamaan.
Semoga semua ini
bisa memberikan sedikit kebahagiaan dan menuntun padalangkah yang lebih baik
lagi. Meskipun saya berharap isi dari makalah ini bebasdari kekurangan dan
kesalahan, namun selalu ada yang kurang. Oleh karenaitu, penulis mengharapkan
kritik dan saran yang membangun agar skripsi inidapat lebih baik lagi. Akhir kata
saya berharap agar makalah ini bermanfaatbagi semua pembaca
Penulis,
DAFTAR ISI
Kata Pengantar…………………………………………………………
Daftar Isi……………………………………………………………..
BAB I Pendahuluan
A. Latar Belakang…………………………………………..
B. Rumusan Masalah
………………………………………..
C. Tujuan ………………………………………………………..
BAB II Pembahasan
A. Sejarah
Program Linear ……………………………………..
B. Pengertian
Program Linear……………………………………….
C. Bentuk
Umum Program Linear ………………………………….
D. Cara
Penyelesaian Program Linear Dengan Metode Grafik) ………………….
E. Cara
Penyelesaian Program Linear Dengan Metode Aljabar…………………
F. Cara
Penyelesaian Program Linear Dengan Metode Simplex…………………..
G. Ciri
– ciri program liner…………………………………………………………..
BAB III Penutup
A. Kesimpulan ……………………………………………………………
B. Saran……………………………………………………………
Daftar Pustaka
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 III
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 ,
No comments:
Post a Comment