LAPORAN PRAKTIKUM LINEAR PROGRAMMING
Disusun Oleh:
Denov Israel Siagian
NPM: 2305102010001
(No Komputer: 21)
Laboran:
Ridwan Saputra S.Pt., M.Si.
LABORATORIUM STATISTIKA DAN SOSIAL
DEPARTEMEN AGRIBISNIS FAKULTAS PERTANIAN
DEPARTEMEN AGRIBISNIS FAKULTAS PERTANIAN
UNIVERSITAS SYIAH KUALA
DARUSSALAM-BANDA ACEH
2025
DARUSSALAM-BANDA ACEH
2025
II. TINJAUAN PUSTAKA
A. Sejarah Program Linear
Model program linier dikembangkan dalam tiga tahap, antara 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; ke-2 oleh Tjalillng Charles Koopmans, ahli ekonomi dari Belanda yang memulai karir intelektualnya sebagai fisikawan yang melontarkan teori Kuantum mekanik; dan ke-3 oleh 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 lain, Koopmans sejak awal sudah bergelut dengan matematika ekonomi dan ekonometri. Dia mengembangkan teknik Activity Analysis yang sekarang dikenal dengan Pemrograman Linear.
Namun demikian, ada nama-nama lain yang juga berperan dalam pengembangan model ini, yaitu J. Von Neuman. Bahkan dia mengembangkan “Activity Analysis of Production Set” sebelum dilanjutkan oleh Koopmans. Pada saat itu, teknik yang mereka kembangkan dikenal dengan istilah “Programming of Interdependent Activities in a Linear Structure”. Istilah programan linear 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
Fungsi Kendala:
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 tergantung dari banyaknya sumber daya yang terbatas.
Pertidaksamaan terakhir (x1, x2, …, xn ≥ 0) menunjukkan batasan non negatif. Dalam membuat model matematik dari suatu permasalahan bukan hanya menuntut kemampuan matematik, tapi juga menuntut seni permodelan dan 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 di antaranya 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
E. Cara Penyelesaian Program Linear Dengan Metode Aljabar
Pemecahan persoalan PL dengan metode aljabar adalah pemecahan persoalan dengan cara substitusi antar persamaan 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
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.
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
F. Cara Penyelesaian Program Linear Dengan Metode Simplex
Metode Simpleks, yaitu metode pemecahan persoalan program linear yang begitu kompleks, luas dan besar karena 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 matematika 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), yang berarti 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), yang berarti aktivitas total sama dengan penjumlahan aktivitas individu.
4. Divisibility Coisa dibagi-bagi, yaitu solusi tidak harus merupakan bilangan integer (bilangan bulat), tetapi bisa juga berupa pecahan.
5. Non-Negative Variable (variabel tidak negatif), yang berarti bahwa semua nilai jawaban atau variabel tidak negatif.
III. TUGAS LINEAR PROGRAMMING
IV. REFERENSI
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.
0 Komentar