ALGORITMA TITIK INTERIOR DAN IMPLEMENTASINYA PADA

PROGRAM LINEAR (Studi Kasus : Peternakan Mitra Tani Andini,

Kelurahan Gunungpati, Semarang)

Ahmad Husni Mubarok, Marsudi, Kwardiniya A

Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas

Brawijaya, Malang, Indonesia (ahmadmubarok42@yahoo.co.id)

Abstrak. Program linear merupakan suatu model yang melibatkan fungsi linear dan dapat digunakan dalam pemecahan

masalah pengalokasian sumber–sumber terbatas secara optimal. Algoritma Titik Interior merupakan alat baru yang dapat

digunakan untuk menyelesaikan masalah yang sangat besar. Metode Titik Interior ini merupakan algoritma yang memotong

daerah fisibel untuk mencapai suatu penyelesaian yang optimal. Oleh karena itu, pada artikel ini akan dibahas tentang

penyelesaian program linear menggunakan metode Titik Interior. Contoh penerapannya pada kasus pemenuhan gizi harian

dengan biaya minimum. Dari tiga kasus kombinasi makanan yang berbeda, yang paling optimal kandungan gizinya dan biaya

termurah dihasilkan pada kasus I dengan kombinasi makanan jerami padi, ketela, ampas tahu, dan bekatul, dimana rata–rata

biaya minimum harian yang dibutuhkan dalam dua kali makan adalah sebesar Rp. 13.500/kg.

Kata kunci: Program linear, Titik Interior, Gizi

1. PENDAHULUAN

Dalam dunia usaha yang mempunyai beberapa resiko yang sangat besar, tentunya sangat

dibutuhkan analisis yang sangat teliti dan akurat agar resiko kerugian dalam usaha dapat dihindari.

Oleh karena itu diperlukan metode–metode yang tepat untuk memecahkannya. Dalam penyelesaian

suatu masalah secara optimal di kehidupan sehari–hari, program linear merupakan cara yang dapat

digunakan dalam pemecahan berbagai masalah pengalokasian sumber–sumber yang terbatas

(Dimyati, 1987). Pada tahun 1947, Dantzig berhasil menemukan suatu prosedur aljabar yang dapat

menyelesaikan masalah–masalah program linear dengan cepat dan efisien, yang dikenal dengan

algoritma simpleks (Lejasa, 2009). Algoritma simpleks memerlukan waktu yang cukup lama untuk

menyelesaikan masalah program linear dengan ukuran besar. Program linear yang ditemukan oleh

L.W Kantorovich pada tahun 1939 dengan metode yang masih terbatas, sampai saat ini belum banyak

diperhatikan orang (Susanta,1994). Masalah yang sering dijumpai dalam kehidupan sehari–hari adalah

masalah memaksimumkan laba dan meminimumkan ongkos produksi. Dan masalah disini

dititikberatkan pada meminimumkan biaya dan mengoptimalkan kandungan nutrisi untuk kebutuhan

akan zat gizi pada Sapi Potong. Metode yang digunakan dalam menyelesaikan masalah pemrograman

linear ini adalah Metode Titik Interior atau Algoritma Titik Interior. Algoritma Titik Interior adalah

algoritma yang memotong atau menembus titik dalam dari daerah fisibel untuk mencapai solusi yang

optimum (Hillier and Lieberman, 2005).

2. METODOLOGI

Formulasi ransum ke program linear prosesnya antara lain menyiapkan daftar harga makanan

dan diletakkan sebagai fungsi tujuan, daftar kebutuhan zat pakan dari Kearl (1982) dan diletakkan

sebagai fungsi pembatas, kandungan nutrisi dari skripsi Akramuzzein (2009) dan diletakkan sebagai

fungsi kendala. Formulasi masalah program linear umum ke dalam bentuk titik interior prosesnya

antara lain mengubah masalah program linear umum ke dalam bentuk yang diperluas, menentukan

arah pergerakan mula–mula dari titik interior, memproyeksikan titik yang berada di luar daerah layak,

pemusatan, mengubah kembali menjadi koordinat semula. Ada contoh tiga kasus dalam

mengimplementasikan metode ini. Contoh kasus I adalah kombinasi makanan berupa jerami padi,

ketela, ampas tahu, dan bekatul pada ransum sapi potong. Kasus II adalah kombinasi makanan berupa

jerami padi, dedak halus padi, bungkil kelapa, dan ketela. Kasus III adalah kombinasi makanan berupa

tepung ikan, dedak halus padi, bungkil kelapa, dan bungkil kedelai.

Langkah–langkah Algoritma Titik Interior:

1. Mengidentifikasi variabel keputusan, fungsi tujuan, kendala, dan pembatas.

2. Memformulasikan variabel keputusan, fungsi tujuan, dan kendala ke dalam bentuk program linear.

3. Jika permasalahan program linear masih dalam bentuk umum, maka harus diubah ke dalam bentuk

Titik Interior dengan langkah–langkah sebagai berikut:

- Bentuk umum program linear

(1) kendaladengan

in

ox

bAx

cxZM

,

x

x

x

x

x anadim

n

3

2

1

,

b

b

b

b

b

n

3

2

1

,

0

0

0

0

o

2n dan ,

a...aa

a...aa

a...aa

a...aa

A

mxn2m1m

n33231

n22221

n11211

- Diubah dalam bentuk maximize (diperluas) dengan menambahkan variabel slack pada fungsi

kendala sehingga bentuknya menjadi

(2) kendaladengan

ox

xb,

x

xI][A,

xc

ss

T

ZMin

4. Jika program linear sudah dalam bentuk minimize (diperluas), maka permasalahan dapat

diselesaikan dengan Algoritma Titik Interior dengan langkah–langkah sebagai berikut:

- Langkah 1: Diketahui penyelesaian percobaan awal )x,...x,x( mn21 yang diambil dari fungsi

kendala dengan D adalah matriks diagonal dari percobaan awal.

mn

2

1

x00

0x0

00x

D

- Langkah 2 : Hitung ADA (3)

A : Matrik Koefisien Kendala

A : Pekalian antara matriks koefisien kendala dan matriks diagonal dari percobaan awal

- Langkah 3 : Hitung Dcc (4)

c : vektor kolom dari koefisien fungsi tujuan

c : Tingkat kemiringan

- Langkah 4 : Hitung A)AA(AIP1 tt , (5)

cPCp (6)

P : Matriks proyeksi

Cp : Tingkat kemiringan yang diproyeksikan

- Langkah 5 : Tentukan komponen negatif pC yang mempunyai nilai absolut terbesar, dan tetapkan

v sama dengan nilai absolut tersebut.

Hitung pC )v/(

1

1

1

x

(7)

x : Penyelesaian percobaan awal sekarang

dengan 0< <1

- Langkah 6 : Hitung xDX , (8)

sebagai penyelesaian percobaan awal untuk iterasi berikutnya.

Jika penyelesaian percobaan ini tidak berubah dari yang sebelumnya maka algoritma telah

memuat ke suatu penyelasaian optimal.

89

3.1 Kasus 1 dengan bobot badan(Bobot badan >350–400 kg): Kombinasi makanan berupa jerami

padi, ketela, ampas tahu, dan bekatul

Model Matematika dalam bentuk minimize yang diperluas

9,...,1 ,0

261,023,1839,009,0292,0

348,0079,039,017,0413,0

186,108,123,306,215,4

43,699,699,775,782,43

364,2886,145,795,87

:kendaladengan

20001500800500Z'

nMaksimumka

94321

84321

74321

64321

54321

4321

ix

xxxxx

xxxxx

xxxxx

xxxxx

xxxxx

xxxx

i Langkah–langkah penyelesaian menggunakan Algoritma Titik Interior (ada sebanyak 8 iterasi)

dengan 95,0 . Diperoleh hasil:

0.2564433=x;0.26108858=x; 70.00000814=x; 0.00001547=x116.1969;=x

; 277202x104.24827977=x; 0.1541108=x; 0.00001058=x; 5685791.32925798=x

98765

-84321

dan biaya minimum yang diperoleh adalah Rp. 895.8,-/kg. Dengan demikian dapat diartikan bahwa

untuk memenuhi persyaratan gizi harian bagi sapi potong kasus I dengan kebutuhan sehari sebesar 15

kg, rata–rata perhari dari 4 ekor sapi dibutuhkan jumlah bahan makanan jerami padi sebanyak 1,33x15

kg = 19,95 kg, ampas tahu 0,154x15 kg= 2,31 kg. Biaya minimum yang dikeluarkan dengan dua kali

makan perhari adalah Rp. 895,8,-/kg atau Rp. 900 x 15 kg = Rp. 13.500/kg.

3.2 Kasus 2 dengan bobot badan(Bobot badan >350–400 kg): Kombinasi makanan berupa jerami

padi, dedak halus padi, bungkil kelapa, dan ketela

Bentuk Titik Interior dari kasus 2 diperoleh dengan mengubah program linear umum menjadi bentuk

minimize yang diperluas.

9,...,1 ,0

261,009,067,055,1292,0

348,017,008,006,0413,0

186,106,26,215,1215,4

43,695,7866702,43

364,25,7986865,87

:kendaladengan

80025001550500Z'

nMaksimumka

94321

84321

74321

64321

54321

4321

ix

xxxxx

xxxxx

xxxxx

xxxxx

xxxxx

xxxx

i Berdasarkan perhitungan menggunakan MAPLE 15 dengan 95,0 , dapat diketahui ba

0.52088=x0.1888;=x; 4.11359x10=x; 60.00002598=x

; 128.67935=x; 101.3811174x=x; 0.2304244=x; 580.00000100=x; 1.255137=x

987-

76

5-7

4321

dengan banyaknya iterasi ada 10 iterasi dan biaya minimum yang diperoleh adalah Rp. 1.203,6,-/kg.

Dengan demikian dapat diartikan bahwa untuk memenuhi persyaratan gizi harian bagi sapi potong

kasus II dengan kebutuhan 15 kg perhari, rata–rata dari 4 ekor sapi dibutuhkan jumlah bahan makanan

jerami padi sebanyak 1,25x15 kg= 18,75 kg, bungkil kelapa 0,23x15 kg=3,45 kg. Biaya minimum

yang dikeluarkan dengan dua kali makan perhari adalah Rp. 1.203,6,-/kg atau Rp. 1.200,-/kg x 15 kg

= Rp. 18.000/kg.

3. HASIL DAN PEMBAHASAN

90

3.3 Kasus 3 dengan bobot badan (Bobot badan >350–400 kg): Kombinasi makanan berupa tepung

ikan, dedak halus padi, bungkil kelapa, dan bungkil kedelai

Bentuk Titik Interior dari kasus 3 diperoleh dengan mengubah program linear umum menjadi bentuk

minimize yang diperluas.

9,...,1 ,0

261,074,067,055,134.4

348,02,008,006,061.6

186,10456,215,122.61

43,6978667069

364,286868686

:kendaladengan

1050250015502000Z'

nMaksimumka

94321

84321

74321

64321

54321

4321

ix

xxxxx

xxxxx

xxxxx

xxxxx

xxxxx

xxxx

i Berdasarkan perhitungan menggunakan MAPLE 15 dengan 95,0 , dapat diketahui ba

0.49507=x; 6.05069x10=x; 30.46499 =x

; 0.00000238=x; 74.449218=x; 0.8667546=x; 04.706167x1=x; 2.4738x10=x; 0.0264=x

97-

87

654-8

3-7

21

dengan banyaknya iterasi ada 8 iterasi dan biaya minimum yang diperoleh adalah Rp. 962,9,-/kg.

Dengan demikian dapat diartikan bahwa untuk memenuhi persyaratan gizi harian bagi sapi potong

kasus III dengan kebutuhan 15 kg perhari, rata–rata dari 4 ekor sapi dibutuhkan jumlah bahan

makanan tepung ikan sebanyak 0,0264x15 kg= 0,369 kg, bungkil kedelai 0,8667x15 kg =13,0005 kg.

Biaya minimum yang dikeluarkan dengan dua kali makan perhari adalah Rp. 962,9,-/kg atau 950 x 15

kg = Rp. 14.250/kg.

4 KESIMPULAN

Metode Titik Interior dapat diterapkan pada optimalisasi kandungan nutrisi untuk kebutuhan

gizi pada Sapi Potong. Dari tiga kasus kombinasi makanan yang berbeda, yang paling optimal

kandungan gizinya dan biaya termurah dihasilkan pada kasus I dengan kombinasi makanan jerami

padi, ketela, ampas tahu, dan bekatul, dimana rata–rata biaya minimum yang dibutuhkan dengan dua

kali makan perhari adalah sebesar Rp. 13.500/kg dengan kebutuhan jerami padi sebanyak 19,95 kg,

dan ampas tahu 2,31 kg. Untuk bahan makanan ketela dan bekatul tidak terpakai dalam pembuatan

ransum, karena harga bahan terlalu tinggi. Sehingga jika ingin dimasukkan dalam ransum(bahan

pakan), maka harus menekan harga bahan tersebut semurah mungkin agar dua bahan makanan tersebut

dapat memenuhi pembuatan ransum(bahan pakan) Sapi Potong. Dengan dua jenis bahan makanan

berupa jerami padi dan ampas tahu, komposisi dan kualitas bahan pakan yang diberikan sudah dapat

memenuhi kebutuhan gizi harian pada Sapi Potong.

5 DAFTAR PUSTAKA

Akramuzzein, (2009), Program Evaluasi Pemberian Pakan Sapi Perah untuk Tingkat Peternak dan

Koperasi Menggunakan Microsoft Acces, Skripsi, Fakultas Peternakan, Institut Pertanian

Bogor.

Dimyati, T.T dan Ahmad, D, (1987), Oprations Research: Model–model Pengambilan Keputusan, PT

Sinar Baru Algesindo, Bandung.

Hillier, F.S and Lieberman, G.J, (1994), Pengantar Riset Operasi, Edisi kelima, Penerbit Erlangga.

Kearl, L.C, (1982), Nutrition Requirement of Ruminant in Developing Countries.

International Feedstuffs Institute, Utah Agricultural Experiment Station, Utah State University,

Logan.

Lejasa, G., (2009), Introduction Interior-Point Methods for Introductory Operations Research Courses

and/or Linier Programming Courses, Journal Departement of Matematical Sciences, Georgia

Southerm University, USA.

91