LINEAR PROGRAMMING

SEJARAH

            Ide Linear Programming pertama kali dicetuskan oleh seorang ahli matematika asal Rusia bernama L.V. Kantorivich dalam bukunya yang berjudul ”MATHEMATICAL METHODS IN THE ORGANIZATION AND PLANNING OF PRODUCTION”. Dengan buku ini, ia telah merumuskan pertama kalinya persoalan “Linear Programming”. Namun, cara-cara pemecahan persoalan in di Rusia tidak berkembang dengan baik dan ternyata para ahli di negara Barat dan AS yang menggunakan cara ini dimanfaatkan dengan baik.

            Pada tahun 1947, seorang ahli matematika dari AS yang bernama George B. Dantzig menemukan suatu cara untuk memecahkan persoalan-persoalan linear programming. Cara pemecahan ini dinamakan ” Simplex Method”, yang diuraikan dalam bukunya ”LINEAR PROGRAMMING AND EXTENTION”. Selanjutnya teori ini berkembang pesat sekali terutama dibidang kemiliteran yang menyangkut optimisasi dalam strategi perang dan di bidang-bidang lainnya.

LINEAR PROGRAMMING (LP)

            Linear programming adalah teknik matematika yang dirancang untuk membantu manager dalam merencanakan dan membuat keputusan dalam mengalokasikan sumber daya yang terbatas untuk mencapai tujuan perusahaan.

            Linear Programming memiliki empat ciri khusus, 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 linier

Untuk membentuk suatu model linear programming perlu diterapkan asumsi-asumsi dasar, yaitu :

1.      Linearity

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

Nilai variabel keputusan dapat berupa bilangan pecahan. Apabila diinginkan solusi berupa bilangan bulat (integer), aka harus digunakan metoda untuk integer programming.

3.      Non negativity variable

Nilai variabel keputusan haruslah tidak negatif ( ³ 0)

4.      Certainty

Semua konstanta (parameter) diasumsikan mempunyai nilai yang pasti. Bila nilai-nilai parameternya probabilistik, maka harus digunakan formulasi pemrograman masalah stokastik.

            Pada umumnya persoalan-persoalan yang dipecahkan dalam linear programming, yaitu :

a.       Allocation Problem

Ini merupakan pemecahan dalam alokasi bahan-bahan / barang dalam produksi

b.      Blending Problem

Ini merupakan cara pemecahan persoalan dari berbagai bahan campuran yang masing-masing unit dipecahkan dan digabung (blending) untuk menghasilkan output.

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

d.      Persoalan Personil

Ini merupakan penempatan personil sesuai dengan jabatan/tempatnya (assigment problem).