BAB I

PENDAHULUAN

1.1 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.

1.2 Rumusan Masalah

1. Bagaimana sejarah Program Linear?
 2. Apa pengertian Program Linear?
3. Bagaimana bentuk umum Program Linear?
4. Bagaimana metode grafik dalam Program Linear?
5. Bagaimana metode Aljabar dalam Program Linear?
6. Bagaimana metode simplex dalam Program Linear
7. Contoh penerapan Program Linear di Bidang Sosial Ekonomi Pertanian

1.3 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
5. Mengetahui cara penyelesaian Program Linear dengan metode aljabar
6. Mengetahui cara penyelesaian Program Linear dengan metode simplex
7. Mengetahui contoh-contoh penerapan Program Linear dalam kehidupan
sehari-hari terutama di bidang Sosial ekonomi pertanian
 BAB II
PEMBAHASAN

2.1 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 governments
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.
2.2 Materi Program Linear
A. 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.

B. 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 [Link] 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.

C. 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 Laptop tipe flip Pasokan
portabletouchscreen (A1) standar (A2) 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 Nilai fungsi , f(x1, x2) = 3 x1 + 2 x2

daerah fisibel
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

D. 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

E. 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.

2.3 Penerapan Konsep Program Linear di Bidang Sosial Ekonomi

Pertanian
1. Fungsi Permintaan
2. Fungsi Penawaran
3. Keseimbangan Pasar
4. Pengaruh Pajak Terhadap Keseimbangan Pasar
5. Pengaruh Subsidi Terhadap Keseimbangan Pasar
6. Fungsi Biaya dan Fungsi Penerimaan
7. Analisis Pulang Pokok
 BAB 3
PENUTUP

3.1 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.

3.2 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.

Ramadhan, Firdi. 2015. Linear Program, [Online]. Tersedia :

[Link] [2 Desember 2015]

Taha, Hamdy A. (1997). Operations Research, an Introduction, sixth edition, Upper

Saddle River, New Jersey, Prentice Hall, Inc.
 MAKALAH

PROGRAM LINIER

DISUSUN OLEH :

SISKA WILIA SAPITRI

XI MIPA 7

SMAN 4 PRAYA