Linier
programming adalah suatu teknis matematika yang dirancang untuk membantu
manajer dalam merencanakan dan membuat keputusan dalam mengalokasikan sumber
daya yang terbatas untuk mencapai tujuan perusahaan. Tujuan dari perusahaan itu
sendiri adalah memaksimumkan laba atau meminimkan biaya. Dalam mencapai tujuan
tersebut terdapat kendala sumber daya, oleh karena itu linier programming
memberikan pemecahan masalah dalam pengambilan keputusan tersebut.
Linier
programming mempunyai persyaratan yang diperlukan dalam linier programming
yaitu, perusahaan mempunyai tujuan, adanya kendala yang membatasi pencapaian
tujuan, perusahaan mempunyai beberapa alternative penyelesaian dan hubungan matematis
yang bersifat linier.
Dalam
linier programming juga terdapat 5 ansumsi yang berlaku, yaitu
yang pertama
certainty (kepastian) yaitu fungsi tujuan dan fungsi kendala sudah diketahui
dengan pasti dan tidak berubah selama periode analisa, yang kedua proporsionality
(proporsionalitas) yaitu adanya proporsionalitas dalam fungsi tujuan dan fungsi
kendala, yang ketiga divisibility (dapat dibagi-bagi) yaitu solusi tidak harus
bilangan bulat tetapi bias berupa pecahan, yang keempat additify (penambahan)
yaitu aktivitas total sama dengan penjumlahan aktivitas individu, dan yang
terakhir adalah non-negatif variable (variable tidak negatif) yaitu semua nilai
jawaban atau variabel tidak negatif.
Dalam
menyelesaikan masalah dengan menggunakan linier programming, ada dua pendekatan
yang bias digunakan, yaitu metode grafik dan metode simpleks. Metode grafik
hanya bisa digunakan untuk menyelesaikan permasalahan dimana variabel keputusan
sama dengan dua. Sedangkan metode simpleks digunakan untuk menyelesaikan
permasalahan dimana variabel keputusan dua atau lebih.
1.1
Formulasi LP dengan Metode Grafik dengan
Tujuan Memaksimalkan Keuntungan.
1.1.1
Formula Matematika
Metode grafik hanya bisa
digunakan untuk menyelesaikan permasalahan dimana hanya terdapat dua variabel
keputusan. Untuk menyelesaikan permasalahan tersebut, langkah pertama yang
harus dilakukan adalah memformulasikan permasalahan yang ada ke dalam bentuk
Linear Programming (LP). Langkah-langkah dalam formulasi permasalahan adalah :
1.
Pahamilah secara menyeluruh permasalahan manajerial yang dihadapi
2.
Identifikasikan tujuan dan kendalanya
3.
Definisikan variabel keputusannya
4.
Gunakan variabel keputusan untuk merumuskan fungsi tujuan dan
fungsi kendala secara matematis.
perusahaan “Sido Makmur”
mempunyai kendala keterbatasan jam kerja. Untuk pembuatan 1 unit meja dia
memerlukan 4 jam kerja. Untuk pembuatan
1 unit kursi dia membutuhkan 3 jam kerja. Untuk pengecatan 1 unit meja dibutuhkan 2
jam kerja, dan untuk pengecatan 1
unit kursi dibutuhkan 1 jam kerja.
Jumlah jam kerja yang
tersedia untuk pembuatan meja dan kursi adalah
240 jam per minggu sedang jumlah jam kerja untuk pengecatan adalah 100
jam per minggu. Berapa jumlah meja dan
kursi yang sebaiknya diproduksi agar keuntungan perusahaan maksimum? Contohnya: Suatu perusahaan mebel “ Sido
Makmur” memproduksi meja dan kursi. Keuntungan dari meja adalah Rp 5.000,00 dan
keuntungan dari kursi Rp 3.000,00.
Dari soal di atas dapat diketahui bahwa tujuan perusahaan adalah
memaksimumkan profit. Sedangkan kendala perusahaan tersebut adalah terbatasnya
waktu yang tersedia untuk pembuatan dan pengecatan. Apabila ditabelkan akan
seperti berikut :
|
Jam kerja untuk membuat 1 produk
|
Total waktu tersedia
|
Meja
|
Kursi
|
Pembuatan
|
4
|
3
|
240
|
Pengecatan
|
2
|
1
|
100
|
Keuntungan
|
5.000
|
3.000
|
-
|
Variabel
keputusan :
Meja = X1
Kursi
= X2
Penulisan
secara sistematis :
a. Memaksimalkan
Z = 5.000X1+3.000X2 (fungsi tujuan )
b. 4X1+3X2
≤ 240 (fungsi kendala)
c. 2X1+X2
≤ 100 (fungsi kendala)
d. X1,X2
≥0 (fungsi kendala)
1.2
Formulasi LP dengan Metode Grafik dengan
Tujuan meminimalkan biaya.
1.2.1
Formula Matematika
Permasalahan minimisasi
dapat juga diselesaikan secara grafik. Langkah-langkah
penyelesaian
permasalahan sama dengan penyelesaian permasalahan untuk fungsi tujuan
maksimisasi yaitu: formulasi permasalahan, menentukan area layak,
serta menentukan solusi. Dalam menentukan solusil, seperti halnya pada
permasalahan maksimisasi, dapat digunakan pendekatan garis profit atau titik sudut. Untuk lebih memahami penyelesaian permasalahan minimisasi berikut akan dicontohkan dalam
soal.
Contoh soal :
Ole Meal adalah makanan yang terbuat dari jagung
dan kacang.Ole meal memerlukan 800 kg makanan per hari. Makanan ini memiliki
kandungan sekurang-kurangnya 30% Protein dan
Serat maksimal 5% dan juga
seperti pada table berikut :
Kandungan Gizi Per Kilogram
|
|
Protein
|
Serat
|
Biaya
|
Jagung
|
0,09
|
0,02
|
0,30
|
Kacang
|
0,60
|
0,06
|
0,90
|
Ole
meal ingin menentukan biaya terendah dari makanan tersebut. Karena makanan
tersebut terbuat dari Jagung dan Kacang, variabel keputusan tersebut dapat
dirumuskan demikian
X1 = banyaknya jagung yang digunakan untuk campuran
makanan
X2= banyaknya kacang yang digunakan untuk campuran
makanan
Fungsi
tujuan adalah meminimumkan biaya dari campuran makanan, yang dirumuskan menjadi
:
Meminimalkan Z = 0,3 X1 + 0,9 X2
Sedangkan, fungsi kendala adalah :
Karena Ole Meal membutuhkan 800kg per hari maka = X1+X2 ≥
800
Kandungan protein dalam jagung adalah
0.09X1+0.02X2 , maka apabila kandungan protein sekurang-kurangnya 30% menjadi :
0,09 X1 + 0,6 X2
= 0,3 (X1 + X2)
0,09 X1 + 0,6 X2
= 0,3 X1 + 0,3 X2
(0,3 X1 - 0,09 X1) + (0,3X2 - 0,6 X2) = 0
0,21 X1 - 0,3 X2
= 0 0,21
X1 -
0,3 X2 ≤ 0
Kandungan protein dalam kacang adalah
0.60X1+0.06X2, maka apabila kandungan serat maksimal 5% menjadi :
0,02 X1+ 0,06 X2 = 0,05 (X1 + X2)
0,02 X1 + 0,06 X2 = 0,05 X1 + 0,05 X2
(0,05 X1 - 0,02 X1) + (0,05 X2 - 0,06 X2) = 0
0,03 X1 – 0,01 X2 = 0 0,03
X1 – 0,01 X2 ≤ 0
Kendala non-negatif adalah X1,X2 ≥ 0
1.2.2
Gambar grafik linier programming
Gambar fungsi kendala :
Titik
potong ketiga kendala bisa dicari dengan
cara substitusi atau eliminasi
Titik potong kendala 1 (Protein: 0.21 X1 – 0.3 X2 = 0) dan kendala 3 (Kebutuhan per hari: X1 + X2 =
800)
0.21
X1 -
0.3 X2 = 0
0.21 X1 =
0.3 X2
X1 =
(0.3/ 0.21 X2
X1 +
X2 = 800
(0.3
/ 0.21) K + K = 800
2,43
X2 = 800
X2 =
800/2,43
X2 =
329,22 dibulatkan menjadi 329.
X1 +
329,22 = 800
X1 =
470,78 dibulatkan menjadi 471.
Jadi titik potong kendala 1 (Protein: 0.21 X1– 0.3 X2 = 0) dan
kendala 3 (Kebutuhan per hari: X1 + X2 = 800) terletak pada titik A
(471, 329).
Titik potong kendala 2 (Serat: 0.03 X1 – 0.01 X2 = 0) dan kendala 3
(Kebutuhan per hari: X1 + X2 = 800)
0.03
X1J – 0.01 X2 = 0
0.03
X1 = 0.01 X2
X1 =
(0.01/ 0.03) X2
X1=
0.33 X2
X1
+ X2 = 800
0.33
X2 + X2 = 800
1.33
X2 = 800
X2 =
800 / 1.33
X2 =
600
X1 +
600 = 800
X1 =
200
Jadi
titik potong kendala 2 (Serat: 0.03 X1 –
0.01 X2 = 0) dan kendala 3 (Kebutuhan per
hari: X1+ X2
= 800) terletak pada titik B (200, 600).
feasible region
(area layak) meliputi daerah sebelah kanan dari titik A (200; 600),
B (471; 329), atau di sebelah kanan kendala II dan III serta di sebelah
kiri kendala I.
Untuk
menentukan solusi yang optimal, ada dua cara yang bisa digunakan yaitu
1. dengan
menggunakan garis biaya (iso cost line)
2. dengan
titik sudut (corner point)
Penyelesaian dengan
menggunakan isocost line adalah penyelesaian dengan
menggambarkan
fungsi tujuan. Kemudian fungsi tujuan tersebut digeser ke kiri sampai
menyinggung titik terdekat dari titik nol, tetapi masih berada
pada area layak (feasible region). Untuk menggambarkan garis isocost, kita
mengganti nilai Z dengan sembarang nilai yang mudah dibagi oleh koefisien pada
fungsi biaya. Pada kasus ini angka yang mudah dibagi angka 0.3 (koefisien X1)
dan 0.9 (koefisien X2) adalah 270.
Sehingga fungsi tujuan menjadi 270= 0.3 X1 + 0.9 X2. Garis ini akan
memotong sumbu X1 pada titik (900, 0) dan memotong sumbu X2 pada titik (0,
300).
Dari gambar di atas dapat dilihat bahwa iso cost line menyinggung
titik A yang merupakan titik terdekat dari titik nol. Titik A ini merupakan
titik optimal. Untuk mengetahui berapa nilai
X1
dan X2, serta nilai Z pada titik A tersebut, kita
mencari titik potong antara kendala I dan kendala III (karena titik A merupakan perpotongan antara kendala I
dan kendala III). Dengan menggunakan eliminiasi
atau substitusi diperoleh nilai X1 = 471,
X2 = 329. dan Z = 437. Dari hasil perhitungan
tersebut maka dapat disimpulkan bahwa keputusan perusahaan yang akan memberikan biaya minimal adalah X1 sebanyak 471 unit, X2
sebanyak 329 unit dan perusahaan akan
mengalokasikan biaya sebesar 437.
Penyelesaian dengan
menggunakan titik sudut (corner point) dari gambar di atas dapat dilihat bahwa
ada 2 titik yang dekat yang membatasi area layak, yaitu titik A yang merupakan
perpotongan kendala I dan III serta titik B yang merupakan perpotongan kendala
II dan III. Untuk penyelesaian dengan menggunakan titik sudut kita mencari
nilai Z di kedua titik tersebut kemudian kita pilih nilai Z yang paling kecil.
Titik A nilai X1 = 471 dan X2 = 329. Dengan substitusi angka tersebut ke fungsi
tujuan kita peroleh:
0,3 X1 + 0,9 X2 = (0,3 x 471) + (0,9 x 329) =
437,4 = 437.
Pada titik B nilai X1 = 200
dan X2 = 600. Dengan mensubstitusikan nilai X1 dan X2 pada fungsi tujuan, kita
peroleh:
0,3 J + 0,9 K = (0,3 x 200)
+ (0,9 x 600) = 600.
Ternyata nilai Z pada titik
A lebih kecil daripada titik B. Dengan demikian titik A adalah titik
optimal.
http://hentoel.blogspot.co.id/2014/06/linier-programming-dengan-metode-grafik.html
2.
