Makalah Program Linier
MAKALAH PROGRAM LINEAR
DISUSUN OLEH:
ADIYA RAHIM RAMADHAN (1805045008)
DINA INDA ROBBIKA (1805045033)
KHAFIFAH NURIYAH (1805045031)
PUTRI SUCI RAMADHANTY (1605045058)
PROGRAM STUDI PENDIDIKAN MATEMATIKA
FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN
UNIVERSITAS MULAWARMAN
SAMARINDA
2020
Kata Pengantar
Puji syukur kehadirat Tuhan Yang Maha Esa atas segala rahmatNYA sehingga makalah ini dapat tersusun hingga selesai. Tidak lupa saya juga mengucapkan banyak terimakasih atas bantuan dari pihak yang telah berkontribusi dengan memberikan sumbangan baik materi maupun pikirannya.
Dan harapan kami semoga makalah ini dapat menambah pengetahuan dan pengalaman bagi para pembaca, Untuk ke depannya dapat memperbaiki bentuk maupun menambah isi makalah agar menjadi lebih baik lagi.
.
Karena keterbatasan pengetahuan maupun pengalaman saya, saya yakin masih banyak kekurangan dalam makalah ini, Oleh karena itu saya sangat mengharapkan saran dan kritik yang membangun dari pembaca demi kesempurnaan makalah ini.
Samarinda, 30 Maret 2020
Penulis
DAFTAR ISI
KATA PENGANTAR..............................................................................................i
DAFTAR ISI............................................................................................................ii
BAB I PENDAHULUAN
A. Latar Belakang..........................................................................................1
B. Rumusan Masalah.....................................................................................2
C. Tujuan Masalah.........................................................................................2
BAB II TINJAUAN PUSTAKA
A. Sejarah Progam Linier................................................................................3
B. Definisi Peograman Linear.........................................................................3
C. Formulasi Model Program Linear...............................................................4
D. Karakteristik Program Linear.....................................................................5
E. Bentuk Umum Program Linear .................................................................6
F. Metode Penyelesaian Masalah Program Linear ..........................................7
BAB III PEMBAHASAN
A. Hasil Wawancara dan Model Matematikanya ............................................12
BAB III PENUTUP
A. Kesimpulan..............................................................................................16
B. Saran........................................................................................................16
DAFTAR PUSTAKA
BAB I
PENDAHULUAN
A. Latar Belakang
Sembilan bahan pokok atau sering disingkat sembako adalah Sembilan jenis kebutuhan pokok masyarakat yang terdiri atas berbagai bahan-bahan makanan dan minuman. Menurut keputusan Menteri Industri dan Perdagangan no 115/mpp/kep/2/1998 tanggal 27 Februari 1998, kesembilan bahan pokok itu adalah beras, sagu dan jagung, gula pasir sayur-sayuran dan buah-buahan, daging sapi dan ayam, minyak goreng dan margarin, susu, telur, minyak tanah atau gas elpiji, garam beryodium dan bernatrium. Semua masyarakat dari yang tingkat ekonominya rendah sampai tinggi pasti membutuhkan sembako untuk memenuhi kebutuhannya setiap hari. Oleh karena itu, sembako mempunyai peranan penting dalam kehidupan masyarakat sehingga mudah didapatkan di warung-warung kecil, pasar tradisional, swalayan sampai mall sekalipun.
Kebutuhan akan sembako meningkat setiap tahunnya. Peningkatan kebutuhan akan sembako berbanding lurus dengan jumlah penduduk. Hal ini berarti semakin tinggi jumlah penduduk maka semakin tinggi pula kebutuhan akan sembako. Menurut sumber dari Badan Pusat Statistik, jumlah penduduk Indonesia mengalami peningkatan setiap tahun. Badan Pusat Statistik mencatat bahwa jumlah penduduk Indonesia dalam 5 tahun terakhir adalah 231 juta jiwa pada tahun 2009, 237 juta jiwa pada tahun 2010 dan meningkat terus hingga tahun 2013.
Penentuan hasil keuntungan warung sembako dengan melihat keterbatasan sumber daya warung tersebut dapat diselesaikan dengan menggunakan metode program linier. Ada beberapa cara menyelesaikan masalah dengan model program linier, diantaranya yaitu diselesaikan dengan Metode Grafik. Metode Grafik merupakan salah satu metode yang dapat digunakan untuk memecahkan permasalahan linier programming. Metode ini menggunakan pendekatan grafik dalam pengambilan keputusannya, dimana seluruh fungsi kendala dibuat dalam satu bagian gambar kemudian diambil keputusan yang optimum.
B. Rumusan Masalah
1. Bagaimana perkembangan usaha Toko Sembako di Toko Daniah Jln. Moh. Hatta, Handil 8 ?
2. Bagaimana cara menghitung keuntungan dan kerugian Toko Sembako Ibu Daniah menggunakan Metode Grafik?
C. Tujuan Masalah
1. Untuk mengetahui Perkembangan Toko Sembako di Toko Daniah Jln. Moh. Hatta, Handil 8.
2. Untuk mengetahui Keuntungan dan Kerugian di Toko Sembako Ibu Daniah menggunakan Metode Grafik.
BAB II
TINJAUAN PUSTAKA
A. Sejarah Program Linear
Program linier (Linier Programming) merupakan pengembangan lebih lanjut dari konsep-konsep aljabar linier. Model ini dikembangkan oleh George B. Dantzig, seorang matematikawan AS tahun 1947. Benih - benih model ini sesungguhnya sudah ditemukan jauh sebelumnya. Seorang matematisian Rusia bernama L.V. Kontrovich memperkenalkan penerapan program linier dalam bidang produksi tahun 1939. Lebih dari seabad sebelumnya tahun 1928, Fourier asal Perancis juga telah merumuskan masalah program linier. Akan tetapi baru setelah Dantzig mengembangkan dan mempopulerkannya, model ini memperoleh perhatian yang berarti. Dantzig pulalah yang dikenal dunia sebagai “Bapak Program Linier.”
B. Definisi Pemograman Linear
Pemprograman linier adalah metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimalkan keuntungan atau meminimummkan biaya. Program linier berkaitan dengan penjelasan suatu kasusdalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsitujuan linier dengan beberapa kendala linier (Taha, 1993).
Semula model program linier dimanfaatkan dibidang kemiliteran, khususnyaoleh Angkatan Udara AS (USAF), untuk merencanakan dan memecahkan masalah - masalah logistik di masa perang. Kini penggunaan program linier sudah sangat meluas terutama di bidang bisnis. Selain itu banyak digunakan untuk menyelesaikan masalah optimasi didalam industri, perbankan, pendidikan, dan masalah-masalah lain yang dapat dinyatakan dalam bentuk linier.
C. Formulasi Model Pogram Linear
Langkah yang paling menentukan dalam program linier adalah memformulasikan model program linier. Langkah ini mencakup identifikasi hal‐hal yang terkait dengan tujuan dan batasan yang membatasi tujuan rersebut. Dalam membangun model dari formulasi permasalahan yang ada akan digunakan beberapa unsur yang biasa digunakan dalam penyusunan program linier yaitu perumusan variabel keputusan, fungsi tujuan, fungsi kendala/pembatas, dan batasan variabel.
a. Variabel Keputusan
Variabel Keputusan adalah variabel yang dapat menentukan keputusan‐keputusan yang akan dibuat dalam pencapaian solusi optimal. Kesalahan dalam menentukan variabel keputusan akan menyebabkan perusahaan salah dalam mengambil keputusan dan solusi yang dicapai tidak optimal. Untuk itu diperlukan pemahaman yang baik tentang karakteristik problem riil yang model program liniernya akan disusun. Berdasarkan karakteristiknya, program linier dapat dikatagorikan ke dalam beberapa kelas problem program linier yang secara umum meliputi: proses produksi, penganggaran, program diet, penjadwalan, perencanaan keuangan jangka pendek, masalah blending, transportasi, penugasan, dan pengiriman. Khusus untuk problem proses produksi, variabel keputusan akan menghantarkan kepada keputusan tentang berapa banyak produk yang akan diproduksi sehingga perusahaan dapat mencapai tujuan
b. Fungsi Tujuan
Fungsi tujuan merupakan fungsi yang menggambarkan tujuan atau sasaran dalam permasalahan program linier yang berkaitan dengan pemanfaatan sumber daya secara optimal untuk memperoleh keuntungan maksimum atau untuk penggunaan biaya minimum.
c. Fungsi Kendala / Pembatas
Fungsi kendala/pembatas merupakan bentuk rumusan terhadap kendala yang dihadapi dalam mencapai tujuan. Kendala tersebut biasanya terkait keterbatasan sumber daya yang dimiliki di dalam mencapai tujuan yang telah dirumuskan di atas. Dengan ketersediaan sumber daya yang terbatas, perusahaan diarahkan untuk dapat mencapai tujuan tersebut baik memaksimumkan laba/keuntungan pendapatan yang maksimum yang diperoleh atau meminimumkan biaya yang digunakan tanpa harus menambah biaya produksi.
d. Batasan Variabel
Batasan variabel menggambarkan tentang wilayah variabel. Jumlah sumber daya yang tersedia untuk persoalan ini tidak boleh bernilai negatif. untuk dan
D. Karakteristik Program Linear
1. Sifat linieritas suatu kasus dapat ditentukan dengan menggunakan beberapacara. Secara statistik, cara ini dapat diperiksa kelinieran menggunakan grafik(diagram pencar).
2. Sifat proposional dipenuhi jika kontribusi setiap variabel pada fungsi tujuanatau penggunaan sumber daya yang membatasi proposional terhadap level nilaivariabel. Jika harga per unit produk misalnya adalah sama berapa pun jumlahyang dibeli, maka sifat proposional dipenuhi. Atau jika pembelian dalam jumlah besar mendapatkan diskon, maka sifat proposional tidak dipenuhi. Jikapenggunaan sumber daya per unit tergantung dai jumlah yang diproduksi,maka sifat proposional tidak dipenuhi.
3. Sifat additivitas mengasumsikan bahwa tidak ada bentuk perkalian silangdiantara berbagai aktivitas, sehingga tidak dapat ditemukan bentuk perkaliansilang pada model. Sifat aditivitas berlaku baik bagi sifat tujuan maupunpembatas (kendala). Sifat aditivitas dipenuhi jika fungsi tujuan merupakanpenambahan langsung kontribusi masing-masing variabel keputusan.
4. Sifat divisiabel berarti unit aktivitas dapat dibagi dalam sembarang levelfraksional, sehingga nilai variabel keputusan non integer dimungkinkan.
5. Sifat kepastian menunjukkan bahwa semua parameter model berupa konstanta.Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan suatu nilaipasti, bukan merupakan nilai dengan peluang tertentu.
E. Bentuk Umum Program Linear
Secara umum bentuk program linear dapat dituliskan :
Fungsi tujuan (objective function) :
Keterangan dari simbol yang digunakan sebgai berikut :
banyaknya jenis sumber yng terbatas atau fsilits yang tersedia.
banyaknya kegiatan – kegiatan yang menggunakan sumber atau fasilits terbatas tersebut.
variabel keputusan untuk kegiatan ke – j (j = 1, 2, ..., n)
banyaknya sumber i yang diperlukan untuk menghasilkan setiap unit keluaran (output) kegiatan j (i = 1, 2, ..., m; j = 1, 2,..., n)
banyaknya sumber (fasilitas) i yang tersedia untuk dialokasikan ke setipa unit kegiatan ( .
kenaikan nilai f apabila pertambahan tingkat kegiatan ( dengan satu satuan (unit) atau merupakan sumbangan setiap satuan keseluruhan kegiatan j terhadap nilai f.
nilai yang dioptimalkan (maksimum atau minimum).
Bentuk program linier di atas juga dapat disajikan dengan memanfaat konsep matrik menjadi bentuk:
Fungsi Tujuan :
Maksimum / Minimum
Dengan Kendala :
Dimana :
C adalah vektor baris,
X dan b adalah vektor kolom, dan
Dan A adalah matriks
Atau bentuk bakunya adalah
Fungsi tujuan :
Maksimum / Minimum
Dengan Kendala :
dan
F. Metode Penyelesaian Masalah Program Linear
1. Metode Grafik
Ada metode untuk mengidentifikasi solusi optimum pada ruang/ daerah feasible yaitu metode kesamaan garis (isoline) dan metode titik ekstrim.
a. Langkah- langkah penyelesaian masalah program linier dengan Metode Isoline:
1. Tentukan kemiringan garis fungsi tujuan (merupakan himpunan infinitif dari isoline).
· Pilihlah dua titik tertentu di daerah feasible
· Gambarlah garis fungsi tujuan yang mengenai titik-titik tersebut
2. Tentukan arah peningkatan (penurunan) dari fungsi tujuan persoalanmaksimum (minimum). Pilihlah dua garis (isoline) fungsi tujuan di daerah feasible dan evaluasi nilai fungsi tujuan pada kedua garis isoline tersebut.
3. Ikuti arah peningkatan atau penurunan sampai mencapai titik batas (sudut)dimana peningkatan atau penurunan dari fungsi tujuan keluar dari daerah feasible
4. Solusi optimum diperoleh dari titik batas di mana peningkatan atau penurunan dari fungsi tujuan (Z) akan meninggalkan daerah feasible.
b. Langkah- langkah penyelesaian masalah program linier dengan Metode Titik Ekstrim
1. Tentukan interseksi dari semua daerah feasible yang didefinisikansemua pembatasan sehingga diperoleh daerah feasible.
2. Tentukan titik ekstrim (sudut) dari daerah feasible. Setiap titik ekstrim merupakan titik interseksi dari dua pembatasan linier.
3. Tentukan nilai fungsi tujuan (Z) pada setiap titik ekstrim daerah feasible. Solusi optimum terletak pada salah satu titik ekstrim daerah feasible
2. Metode Simpleks
Menyelesaikan program linier dengan jumlah variabel keputusan yang sembarang (bila lebih dari 2 atau bahkan ribuanvariabel keputusan). Metode simplex merupakan metode yang secara sistematis dimulai dari suatu pemecahan dasar yang fisibel ke pemecahaan lainnya yang dilakukan berulang‐ulang (iterasi) dengan jumlah ulangan yang terbatas, sehingga akhirnya tercapaisuatu pemecahaan dasar yang optimum. Metode simplex dimulai dari suatu titik sembarang pada daerah fisibel (ruang solusi) menuju titik ekstrim yang optimum. Bila banyaknya variabel keputusan adalah ribuan, maka bisa dipakai software LINDO, GINO, atau LINGO.
Sebelum membahas metode simpleks, perlu diingat bahwa kendala yang terdapat dalam fungsi kendala model program linier diklasifikasi menjadi 3 macam tanda hubungan matematis :
≤ (Pertidaksamaan kurang dari)
= (persamaan)
≥ (pertidaksamaan lebih dari)
Berdasarkan klasifikasi tersebut maka program linier harus diformat ke bentuk kanonik agar metode simpleks bisa diterapkanuntuk menyelesaikan program linier tersebut.
Cara memformat program linier ke bentuk kanonik adalah dengan mengubah sistem ketidaksamaan kendala menjadi sistem persamaan melalui penambahan beberapa variabel penolong pada setiap ruas kiri kendala sedemikian sehingga terdapat sub‐matrik identitas di dalam matrik koefisien atau matrik sistem persamaan. Variabel penolong tersebut adalah variabel slack (kekurangan) atau variabel surplus/exceess (kelebihan) dan variabel artificial(semu). Penambahan variabel penolong merupakan implikasi dari pengubahan ketidaksamaan menjadi persamaan. Untuk kendala dengan tanda ketidaksamaan ≤ maka ruas kiri dari kendala tersebut perlu ditambah variabel slack yang merepresentasikan kekurangan ruas kiri terhadap ruas kanan. Penambahan variabel slack ini akan langsung menciptakan sub‐matrik identitas di dalam matrik koefisien. Sedangkan untuk kendala dengan tanda ketidaksamaan ≥ maka ruas kiri dari kendala harus dikurangi variabel surplus yang mengindikasikan kelebihan ruas kiri terhadap ruas kanan dan menambah variabel artifisial agar terdapat sub‐matrik identitas di dalam matrik koefisien. Prosedur penambahan variabel penolong tersebut akan memformat kendala berbentuk sistem pertidaksamaan menjadi sistem persamaan. Format sistem persaman dari kendala inilah yang disebut sebagaibentuk kanonik. Aturan penambahan variabel penolong sebagaimana dijelaskan di atas direkapitulasi ke dalam tabel :
Tabel Penambahan variabel penolong
|
Nama Variabel |
Notasi |
|
Slack |
S |
|
Surplus / excess |
E |
|
Artificial |
A |
Sebagai ilustrasi penambahan variabel penolong, lihat contoh berikut
Fungsi tujuan :
Memaksimumkan
Fungsi Kendala :
Pekerja :
Persediaan :
Syarat non negatif :
Setelah dilakukan penambahan variabel penolong maka model program linier menjadi model persamaan linier sebagai berikut :
Fungsi tujuan :
Maks
Fungsi Kendala :
Pekerja :
Persediaan :
Syarat non negatif :
Proses untuk memperoleh solusi optimal dengan metode simpleks dilakukan dengan menggunakan tabel yang diinamakan tabel simpleks sebagai berikut :
Dimana :
Variabel basis/dasar adalah variabel yang nilainya sama dengan sisi kanan dari persamaan
NK adalah nilai kanan persamaan, yaitu nilai di belakang tanda sama dengan (=)
BAB III
PEMBAHASAN
A. Hasil Wawancara dan Model Matematikanya
Wawancara dilakukan di Handil, tepatnya di alamat Jl. Moh. Hatta, Handil 8 pada tanggal 22 Maret 2020. Wawancara dilakukan oleh salah satu anggota kelompok 7 yang berdomisili di Handil 8, yaitu Khafifah Nuriyah dengan narasumber yaitu Ibu Daniah. Ibu Daniah adalah seorang IRT (Ibu Rumah Tangga) yang kegiatan sehari-harinya berjualan sembako. Adapun hasil wawancaranya sebagai berikut:
A : Khafifah Nuriyah
B : Ibu Daniah
A : Assalamu’alaikum Wr. Wb.
B : Wa’alaikumussalam Wr. Wb.
A : Sebelumnya mohon maaf mengganggu waktunya Bu. Saya Ingin mewawancarai mengenai toko Ibu.
B : Silahkan.
A : Pertanyaan pertama, siapa nama Ibu ?
B : Ibu Daniah.
A : Sudah berapa lama Ibu berjualan sembako ?
B : Sekitar 10 tahun.
A : Dari beberapa bahan sembako yang Ibu jual, bahan sembako mana yang paling laku terjual Bu?
B : Gula dan Kopi.
A : Sekarang berapa harga jual gula dan kopi Bu ?
B : Sekarang harga gula Rp 18.000,00 per kg dan kopi Rp 6.000,00 per bungkus.
A : Keuntungan yang diperoleh dari penjualan gula dan kopi berapa Bu ?
B : Keuntungan yang diperoleh dari gula yaitu Rp 2.000,00 per kg dan untuk kopi Rp 1000,00 per bungkus.
A : Bagaimana modal awal untuk membeli bahan sembako tersebut Bu ?
B : modalnya gula Rp 850.000,00 per karung untuk per kg nya Rp 16.000,00 dan untuk kopi Rp 250.000,00 per kotak untuk per bungkusnya Rp 5.000,00.
Berdasarkan hasil wawancara tersebut diketahui bahwa bahan sembako yang paling laku terjual adalah gula dan kopi. Modal awal gula Rp 16.000,00 pe kg kemudian dijual seharga Rp 18.000,00 per kg dengan keuntungan yang diperoleh Rp 2.000,00 tiap kg. Sedangkan modal awal untuk kopi yaitu Rp 5000,00 per bungkus dan dijual seharga Rp 6000,00 per bungkusnya dengan keuntungan yang didapatkan sebesar Rp 1000,00 per bungkusnya. Biasanya Ibu Daniah membeli gula per karung dan kopi per kotak. Harga gula per karung Rp 850.000,00 dan kopi per kotak Rp 250.000,00. Sehingga total modal seluruhnya untuk membeli gula dan kopi yaitu Rp 1.100.000,00. Agar Ibu Daniah memperoleh keuntungan yang maksimum, maka berapa banyak gula dan kopi yang harus terjual ?
Dari permasalahan tersebut dapat dibuatkan dalam bentuk tabel sebagai berikut :
|
Kendala |
Gula (kg) |
Kopi (bungkus) |
Batasan |
|
Modal Awal |
16000 |
5000 |
1100000 |
|
Harga Jual |
18000 |
6000 |
1100000 |
|
Keuntungan |
2000 |
1000 |
|
Model matematika :
Misalkan : x = banyaknya gula per kg
y = banyaknya kopi per bungkus
Maksimumkan : Z =
Kendala / Batasan :
........ ( 1 )
........ ( 2 )
Penyelesaian :
Karena hanya menggunakan 2 variabel yang sederhana, di sini penulis menggunakan Metode Grafik untuk menyelesaikan permasalahan tersebut.
Langkah pertama : mencari titik potong masing-masing persamaan (1) dan (2) terhadap sumbu-x dan sumbu-y.
Sebelum mencari titik potong masing-masing persamaan (1) dan (2), kedua persamaan tersebut diubah ke dalam pembuat nol terlebih dahulu, sehingga diperoleh :
..... (1)
..... (2)
Persamaan (1) :
Jika , maka diperoleh titik
Jika , maka diperoleh titik
Persamaan (2) :
Jika , maka diperoleh titik
Jika , maka diperoleh titik
|
Y |
|
X |
|
Daerah Penyelesaian |
|
|
|
|
|
|
|
|
|
|
Langkah ketiga : mencari nilai Z berdasarkan titik pada daerah penyelesaian
Z =
Langkah keempat : menarik kesimpulan
Nilai Z akan mencapai maksimum di titik . Ini berarti Ibu Daniah akan memperoleh keuntungan maksimum sebesar Rp 220000,00 apabila hanya menjual kopi sebanyak 220 bungkus dengan harga Rp 6000,00 per bungkusnya.
BAB IV
PENUTUP
A. Kesimpulan
Pemprograman linier adalah metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimalkan keuntungan atau meminimummkan biaya. Program linier berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier. Dalam membangun model dari formulasi permasalahan yang ada akan digunakan beberapa unsur yang biasa digunakan dalam penyusunan program linier yaitu perumusan variabel keputusan, fungsi tujuan, fungsi kendala/pembatas, dan batasan variabel. Program linier bisa di selesaikan menggunakan metode grafik untuk menentukan persoalan maksimum maupun minimum.
Berdasarkan hasil wawancara yang dilakukan diketahui bahwa bahan sembako yang paling laku terjual adalah gula dan kopi. Karena hanya menggunakan 2 variabel yang sederhana, di sini penulis menggunakan Metode Grafik untuk menyelesaikan permasalahan(keuntungan maksimum dari kedua barang).
B. Saran
Diharapkan dengan adanya pembahasan dalam makalah ini penulis dan pembaca dapat mengetahui dan memahami materi program linear ini terutama pengaplikasiannya di bidang sosial ekonomi perdagangan.
DAFTAR PUSTAKA
Dwi Kurniasih, Meyta. 2015. Handout Mata Kuliah Program Linier. Jakarta : Universitas Muhammadiyah Prof Dr Hamka.
Rafflesia, Ulfasari dan Harya Widodo, Fanani. 2014. Pemrograman Linier. Bengkulu : Badan Penerbitan Fakultas Pertanian UNIB.
Syahputra, Edi. 2015. Program Linear. Medan : Unimed Press.
Komentar
Posting Komentar