Program Linier PDF

Preview

Summary

1 KATA PENGANTAR Buku ini disusun bab demi bab dengan mengikuti sistematika dan ketentuan yang telah disesuaikan dengan aturan. Tujuan utama penulisan buku ini adalah untuk memenuhi tugas pada mata kuliah program linier. Selain dari itu, buku ini juga dimaksudkan sebagai referensi pembelajaran progr...

Description

1

KATA PENGANTAR Buku ini disusun bab demi bab dengan mengikuti sistematika dan ketentuan yang telah disesuaikan dengan aturan. Tujuan utama penulisan buku ini adalah untuk memenuhi tugas pada mata kuliah program linier. Selain dari itu, buku ini juga dimaksudkan sebagai referensi pembelajaran program linier sehingga diharapkan dapat membantu proses pembelajaran dan pemahaman bagi para pembaca. Oleh karena itu dianjurkan kepada pembaca, khususnya mahasiswa agar mempelajari buku ini dari satu bab ke bab berikutnya secara berurutan. Jangan berusaha melampaui suatu bab dan beralih ke bab berikutnya sebelum bab tersebut dikuasai dengan baik. Penulis menyadari bahwa buku ini masih banyak kekurangan-kekurangan

serta

kesalahan-kesalahan

yang

pada

dasarnya

disebabkan oleh keterbatasan kemampuan penyusun dalam bidang Program Linier, serta kelalaian sebagai manusia biasa. Karena itu penulis sangat berterima kasih atas saran dan kritik para pembaca, agar dapat melengkapi dan memperbaiki isi buku ini.

Penulis Desember, 2020

i

DAFTAR ISI KATA PENGANTAR ...................................................................................... i DAFTAR ISI ...................................................................................................... ii BAB I PENGANTAR PROGRAM LINIER (MODEL MATEMATIKA) .................. 1 A.Sejarah Singkat Program Linier .................................................................... 1 B.Pengertian Program Linier ............................................................................ 4 C.Asumsi Dasar Dalam Program Linier ........................................................... 5 D.Ruang Lingkup Program Linier .................................................................... 7 E.Formulasi Model Program Linier ................................................................... 8 F.Bentuk Umum Program Linier ...................................................................... 9 G.Contoh ............................................................................................................ 10 H.Latihan ........................................................................................................... 14 BAB II METODE GRAFIK .......................................................................................... 16 A.Program Linier Metode Grafik Maksimasi .................................................... 16 B.Program Linier Metode Grafik Minimasi ...................................................... 22 C.Latihan ............................................................................................................ 23 BAB III METODE SIMPLEKS ...................................................................................... 24 A.Simpleks Maksimasi ...................................................................................... 27 B.Simpleks Minimasi ......................................................................................... 30

ii

C.Latihan ............................................................................................................ 32 BAB IV METODE BIG-M ............................................................................................. 34 BAB V PENUTUP ......................................................................................................... 38 A.Ringkasan ....................................................................................................... 38 DAFTAR PUSTAKA ....................................................................................... 40

iii

BAB I PENGANTAR PROGRAM LINIER (MODEL MATEMATIKA) A. Sejarah Singkat Program Linier Program linear ditemukan dan dikembangkan oleh beberapa matematikawan di masa sebelum Perang Dunia ke-II. Penemuan dan pengembangan oleh beberapa matematikawan tersebut rata-rata didasarkan karena persoalan atau masalah yang sedang berkembang saat itu, yaitu dalam hal industri dan peperangan. Beberapa matematikawan tersebut adalah Leonid V. Kartovich, George B. Dantzig, John von Neumann, Leonid Khachiyan dan Naranda Karmarkar. Berikut ini pemaparan sejarah penemuan program linear oleh beberapa matematikawan tersebut di atas. 1. Lenoid Vitalevich Kartovich Leonid V. Kartovich lahir pada bulan Januari tahun 1912 di kota Leningrad, Rusia. Leonid tumbuh menjadi seorang anak dengan rasa keingin tahuan yang besar, ia tertarik dengan politik dan sejarah modern. Pada usaianya yang baru 14 tahun, ia sudah masuk ke Mathematical Department of the Leningrad University, di sini ia mulai menyadari bahwa ia berminat pada bidang ilmu pengetahuan dan matematika. Pada tahun keduanya di universitas, Leonid

sudah

mengungguli

teman-temannya

di

bidang

matematika, bahkan ia sudah menguasai matematika kompleks dan abstrak. Di usianya yang ke 18 tahun ia sudah menjadi penulis di bidang matematika.1 Setelah lulus, Leonid terus melanjutkan penelitiannya di bidang matematika teoritis, tetapi seiring berjalannya waktu ia mulai memindahkan konsentrasinya pada matematika terapan, pada ahirnya kontribusi terbesar Leonid adalah pada matematika ekonomi. 1

Abdillah, Program Linear, (Makassar: Dua Satu Press, 2013), h. 2

1

Pada masa itu Uni Soviet sedang menghadapi masa industrialisasi di bawah wewenang Joseph Stalin dimana perekonomian yang semula terpusat pada pertanian berubah menjadi industri. Keadaan seperti inilah yang membuat Leonid menemukan masalah di tempat ia berkerja yaitu sebagai konsultan laboratorium pemerintah. Persoalan tersebut berkaitan dengan kegiatan

produksi,

ia

harus

menyelesaikan

masalah

mengefisiensikan biaya produksi dan pemakaian bahan baku tetapi produksi tetap maksimal. Pada awalnya masalah ini dinilai sederhana, hanya sebuah kasus kalkulus diferensial, tetapi ternyata lebih rumit dari kelihatannya. Inilah hal yang menjadi awal keinginan Leonid untuk menggunakan matematika sebagai aplikasi untuk ekonomi. Akhirnya pada tahun 1939, Leonid mengajukan sebuah hasil pemikirannya berdasarkan masalah yang ada dan perencanaan solusinya. Ternyata hasil pemikirannya ini adalah yang kita kenal sekarang sebagai Program Linear. Pemikirannya tersebut pada awalnya diragukan oleh banyak orang, tetapi dengan cepat terbukti ketika ia menghitung jumlah maksimum suatu pabrik harus memakai baja agar biaya produksi tetap efisien, dan ternyata pemikirannya tersebut terbukti biaya produksi dapat diefisienkan secara signifikan. Penemuan Leonid mengantarkan era baru bagi perekonomian bagi Uni Soviet. Hal ini menimbulkan minat yang besar bagi Uni Soviet dalam matematika terapan, dan sejak itu Leonid menjadi revolusioner di bidang ekonomi matematika. 2. George Bernard Dantzig George Bernard Dantzig lahir pada tanggal 8 November 1914 di Portland, Oragon, Amerika Serikat. Ayah Dantzig adalah seorang profesor matematika dan ibunya adalah seorang ahli bahasa Slavia. Dantzig mendapatkan gelar sarjananya di University of Maryland pada tahun 1936. Ia tidak

2

suka semua mata kuliah matematik yang ia ambil di sana karena ia tidak melihat aplikasi dari semua itu. Tahun berikutnya ia mengambil program pasca sarjana di Mathematics School of the University of Michigan. Selain mata kuliah

statistika,

ia

tetap

melihat

semua

mata

kuliah

matematikanya terlalu abstrak maka ia meninggalkan sekolahnya dan mencari pekerjaan. Lalu ia bekerja di Biro Statistik Tenaga Kerja, dua tahun kemudian ia berkuliah di Berkley untuk mengambil doktor dalam bidang statistika. Setelah mendapatkan gelar doktor pada tahun 1947 ia bergabung di Angkatan Udara Amerika sebagai penasehat matematik untuk pusat kontrol Angkatan Udara. Angkatan udara membutuhkan cara cepat untuk menghitung durasi tahapan program, latihan, dan distibusi logistik. Berasal dari sinilah pemikirian Dantzig tentang program linear. Dantzig menyatakan bahwa : “I began noticing that the feasible regionis a convex body, that is, a polyhedral set.Therefore, the process would be able to be improved if the movements were maded along theborders from one extreme point toward the following. However, this procedure seemed to be too inefficient. In three dimensions, the regioncould be visualized like a diamond with faces, edges and vertex. In the cases of many borders, the process would take an a journey along them before the diamond’s point optimal corner would be reached”. Kesimpulannya, sebuah permasalahan dijadikan dalam bentuk 3 dimensi seperti berlian dimana ada tampak depan, garis pinggir dan puncak lalu mereka akan saling bertemu disuatu titik hingga titik optimum akan terpenuhi. Begitulah awal terciptanya program linear dengan metode simpleks oleh Dantzig 3. John Von Neumann

3

Leonid Khachiyan dan Naranda Karmarkar mengembangkan program linear untuk masalah-masalah yang lebih rumit pada tahuntahun berikutnya sampai di temukannya metode grafik. B. Pengertian Program Linier Ada beberapa pengertian Program Linear menurut para ahli, di antaranya: a. Siringoringo Pemrograman Linier disingkat PL merupakan metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. PL banyak diterapkan dalam masalah ekonomi, industri, militer, social dan lain-lain. PL berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier.2 b.

Jaz Heizer dan Barry Rander Linear Programming menurut Jay Heizer dan Barry Rander mengemukakan

bahwa: “A mathematical technique designed to help operations managers plan and make decisions relative to the trade-offs necessary to allocate resources” . Yang artinya : “Sebuah teknik matematik yang didesain untuk membantu para manajer operasi dalam merencanakan dan membuat keputusan yang diperlukan untuk mengalokasikan sumber daya”.

c. Tjutju Tarliah Dimyati dan Ahmad Dimyati Menurut Tjutju Tarliah Dimyati dan Ahmad Dimyati mengemukakan bahwa “Program linier (LP) adalah perencanaan aktivitas-aktivitas untuk memperoleh suatu hasil yang optimum, yaitu suatu hasil yang mencapai tujuan terbaik diantara seluruh alternatif yang fisibel”. 3 Secara umum Program Linear dapat diartikan bahwa suatu teknis matematika yang dirancang untuk membantu manajer dalam merencanakan dan membuat

2 Hotniar Siringoringo, Seri Teknik Riset Operasional. Pemrograman Linear. (Yogyakarta: Penerbit Graha Ilmu, 2005), h. 1 3 Tjutju Tarliah Dimyati dan Ahmad Dimyati, Operations Research: Model-model Pengambilan Keputusan. (Bandung: Sinar Baru Algensindo, 2003), h. 17

4

keputusan dalam mengalokasikan sumber daya yang terbatas untuk mencapai tujuan perusahaan. Secara khusus, persoalan program linear adalah suatu persoalan untuk menentukan besarnya masing-masing nilai variabel (variabel pengambilan keputusan) sedemikian rupa sehingga nilai funsi tujuan atau objektif (objective function) yang linier menjadi optimum (maksimum

atau

minimum)

dengan

memperhatikan

pembatasan-

pembatasan (kendala-kendala) yang ada yaitu pembatasan ini harus dinyatakan dengan ketidaksamaan yang linier (linear inequalities). Pendapat pakar yang lain menyatakan bahwa linear programming adalah merupakan suatu teknik perencanaan yang bersifat analitis yang analisisanalisisnya memakai model matematika, dengan tujuan untuk menemukan beberapa kombinasi alternatif pemecahan masalah, lalu dipilih yang terbaik dalam rangka menyusun strategi dan alokasi sumber daya dan dana untuk mencapai tujuan dan sasaran yang diinginkan secara optimal. Secara singkat, program linear adalah teknik matematika yang dirancang untuk membantu manager dalam merencanakan dan membuat keputusan dalam mengalokasikan sumber daya yang terbatas untuk mencapai tujuan perusahaan. C. Asumsi Dasar Dalam Program Linier Untuk membentuk suatu model program linear perlu diterapkan asumsiasumsi dasar, yaitu: 1. Linearitas Fungsi obyektif dan kendala haruslah merupakan fungsi linier dan variabel keputusan. Hal ini akan mengakibatkan fungsi bersifat proporsional dan additif, misalnya untuk memproduksi 1 kursi dibutuhkan waktu 5 jam, maka untuk memproduksi 2 kursi dibutuhkan waktu 10 jam. 2. Pembagian Nilai variabel keputusan dapat berupa bilangan pecahan. Apabila diinginkan solusi berupa bilangan bulat (integer), aka harus digunakan metoda untuk integer programming.

5

3. Variabel non negatif Nilai variabel keputusan haruslah tidak negatif (≥0). 4. Kepastian Semua konstanta (parameter) diasumsikan mempunyai nilai yang pasti. Bila nilai-nilai parameternya probabilistik, maka harus digunakan formulasi pemrograman masalah stokastik. 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 fungsi kendala. 3. Additivity (penambahan). Artinya aktivitas total sama dengan penjumlahan aktivitas individu. 4. Divisibility (bisa dibagi-bagi). Maksudnya solusi tidak harus merupakan bilangan integer (bilangan bulat), tetapi bisa juga berupa pecahan. Non-negative variable (variabel tidak negatif). Artinya bahwa semua nilai jawaban atau variabel tidak negatif. Untuk merumuskan suatu masalah ke dalam bentuk model program linear, harus dipenuhi syarat-syarat berikut: 1. Tujuan masalah harus jelas. 2. Harus ada sesuatu atau beberapa alternatif yang ingin dibandingkan. 3. Adanya sumber daya yang terbatas. 4. Bisa dilakukan perumusan kuantitatif. 5. Adanya keterkaitan peubah (variabel). Program Linear 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

6

3. Ada beberapa alternatif penyelesaian 4. Hubungan matematis bersifat linear D. Ruang Lingkup Program Linier Pada umumnya persoalan-persoalan yang dipecahkan dalam program linear yaitu meliputi: 1. Allocation Problem Ini

merupakan

pemecahan

dalam

alokasi

bahan-

bahan/barang dalam produksi 2. Blending Problem Ini merupakan cara pemecahan persoalan dari berbagai bahan campuran yang masing-masing unit dipecahkan dan digabung (blending) untuk menghasilkan output. 3. Persoalan Transportasi Ini merupakan pemecahan persoalan yang menyangkut adanya unit/barang/pasokan dan lain-lain pada beberapa tempat yang akan dipindahkan ke beberapa tempat lainnya. 4. Persoalan Personil Ini

merupakan

penempatan

personil

sesuai

dengan

jabatan/tempatnya (assigment problem). Suatu persoalan disebut persoalan program linear apabila memenuhi hal-hal sebagai berikut: 1. Tujuan (objective) Apa yang menjadi tujuan permasalahan yang dihadapi yang ingin dipecahkan dan dicari jalan keluarnya. Tujuan ini harus jelas dan tegas yang disebut fungsi tujuan (objective function). Fungsi tujuan tersebut dapat berupa dampak positip, manfaatmanfaat, atau dampak negatip, kerugian-kerugian, resikoresiko, biaya-biaya, jarak, waktu yang ingin diminimumkan. 2. Alternatif perbandingan Harus

ada

sesuatu

atau

alternatif

yang

ingin

diperbandingkan, misalnya antara kombinasi waktu tercepat dan biaya tertinggi dengan waktu terlambat dan biaya terendah,

7

atau alternatif padat modal dengan padat karya, proyeksi permintaan tinggi dengan rendah, dan seterusnya.

3. Sumber Daya Sumber daya yang dianalisis harus berada dalam keadaan terbatas. Misalnya keterbatasan tenaga, bahan mentah terbatas, modal terbatas, ruangan untuk menyimpan barang terbatas, dan lain-lain. Pembatasan harus dalam ketidaksamaan linier (linear inequality).

Keterbatasan

dalam

sumber

daya

tersebut

dinamakan sebagai fungsi kendala atau syarat ikatan.

4. Perumusan Kuantitatif Fungsi tujuan dan kendala tersebut harus dapat dirumuskan secara kuantitatif dalam model matematika.

5. Keterikatan Perubah Perubah-perubah yang membentuk fungsi tujuan dan fungsi kendala

tersebut

harus

memiliki

hubungan

keterikatan

hubungan keterikatan atau hubungan fungsional. E. Formulasi Model Program Linier 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.4 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

4

dan

Ulfasari Rafflesia, Pemrograman Linier, (Bengkulu: Badan Penerbitan Fakultas Pertanian UNIB, 2002), h. 2

8

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 yang telah dirumuskan. 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. F. Bentuk Umum Program Linier Pemrograman linear dapat dirumuskan seperti berikut mencari nilai-nilai peubah/variabel 𝑥1 , 𝑥2, … , 𝑥𝑛 yang memaksimumkan atau

meminimumkan 𝑍 =𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 dengan kendala: 9

𝑎11 𝑥1 + 𝑎12 𝑥12 + ⋯ + 𝑎1𝑛 𝑥𝑛 (≤, =, ≥)𝑏1

𝑎21 𝑥1 + 𝑎22 𝑥12 + ⋯ + 𝑎2𝑛 𝑥𝑛 (≤, =, ≥)𝑏2

………………………………………………………….. …………………………………………………………..

𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥12 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛(≤, =, ≥)𝑏𝑚

Dengan syarat peubah/variabel 𝑥1 , 𝑥2 , … 𝑥𝑛 ≥ 0, 𝑐𝑖 , 𝑖 = 1,2, … , 𝑛, 𝑎𝑖𝑗, 𝑖 =

1,2, … , m, j = 1,2, … , n adala...