Linear Programming – Excel

Linear Programming atau Pemrograman Linier adalah salah satu teknik Operations Research yang paling banyak digunakan perusahaan-perusahaan di Amerika menurut penelitian Turban, Russel, Ledbetter, Cox, dll. Di samping itu, teknik ini telah menjadi dasar pengembangan teknik Operations Research yang lain seperti Goal Programming, Binary Integer Programming atau Zero-One Programming. Juga, teknik ini bisa digunakan untuk menyelesaikan teknik Operations Research yang lain, seperti Transportation, Assignment, Crash Time and Crash Cost program pada Critical Path Method, Equilibrium condition pada Markov analysis, Dual programming pada Game Theory, dan Network analysis seperti Transhipment, Shortest Route, Minimum Spanning Tree, dan Maximal Flow. Memahami materi ini dengan baik bukan hanya menjadi landasan yang kokoh untuk mempelajari Integer Programming dan Goal Programming serta penerapan penggunaannya pada teknik Operations Research yang lain tetapi juga membuat penjelasan atau pembahasan berulang pada hal yang sama tidak perlu dilakukan.

Model Linear Programming dikembangkan dalam tiga tahap, antara lain pada tahun 1939-19479[1]. Pertama kali dikembangkan oleh Leonid Vitaliyevich Kantorovich[2], ahli matematika Rusia yang memperoleh Soviet government’s Lenin Prize pada tahun 1965 dan the Order of Lenin pada tahun 1967; ke dua, oleh Tjalling Charles Koopmans [3], ahli ekonomi dari Belanda yang memulai karir intelektualnya sebagai fisikawan yang melontarkan teori Kuantum Mekanik[4]; dan ke-3, George Bernard Dantzig[5] yang mengembangkan Algoritma Simplex[6].

Pada tahun 1930, Kantorovich dihadapkan pada kasus nyata optimisasi sumber-sumber yang tersedia di pabrik. Dia mengembangkan sebuah analisis baru yang nantinya akan dinamakan Linear Programming. Kemudian pada tahun 1939, Kantorovich menulis buku “The Mathematical Method of Production Planning and Organization”, dimana Kantorovich menunjukkan bahwa seluruh masalah ekonomi dapat dilihat sebagai usaha untuk memaksimumkan suatu fungsi terhadap kendala-kendala[7]. Kuliah Kantorovich pada saat menerima hadiah Nobel, 11 Desember 1975 adalah Mathematics in Economics: Achievements, Difficulties, Perspectives [8]. Di sisi yang lain, Koopmans sejak awal sudah bergelut dengan matematika ekonomi dan ekonometri. Dia mengembangkan teknik Activity Analiysis[9] yang sekarang dikenal dengan Linear Programming. Makalah-makalah yang dipublikasikan Koopmans selama tahun 1960 an mengupas masalah tentang bagaimana membagi pendapatan nasional antara konsumsi dan investasi secara optimal[10]. Kuliah Koopmans pada saat menerima hadiah Nobel, 11 Desember 1975 adalah Concepts of Optimality and Their Uses[11].

Leonid Vitaliyevich Kantorovich dan Tjalling Charles Koopmans telah memberi kontribusi pada teori optimisasi alokasi sumber-sumber dan memperoleh hadiah Nobel di bidang Economics.  Pada tahun 1975. Bagaimanapun juga ada nama-nama lain yang berperan di dalam pengembangan model ini, yaitu J. von Neuman[12]. Bahkan dia yang mengembangkan “Acitivity Analysis” of Production Set sebelum dilanjutkan oleh Koopmans[13]. Pada saat itu, teknik yang mereka kembangkan dikenal dengan istilah “Programming of Interdependent Acitivities in a Liniear Structure”[14]. Istilah Linear Programming diusulkan oleh Koopmans ketika mengunjungi Dantzig di RAND Corporation pada tahun 1948[15]. Istilah ini menjadi populer hingga sekarang. Nobel e-Museum,[16]

Model

Model pemrograman linier mempunyai tiga unsur utama yaitu:

  1. Variabel Putusan
  2. Fungsi Tujuan
  3. Fungsi kendala-kendala

Variabel Putusan adalah variabel persoalan yang akan mempengaruhi nilai tujuan yang hendak dicapai. Di dalam proses pemodelan, penemuan variabel keputusan tersebut harus dilakukan terlebih dahulu sebelum merumuskan fungsi tujuan dan kendala-kendalanya.

Fungsi Tujuan. Dalam model pemrograman linier, tujuan yang hendak dicapai harus diwujudkan ke dalam sebuah fungsi matematik linier. Selanjutnya, fungsi itu dimaksimumkan atau diminimumkan terhadap kendala-kendala yang ada.

Kendala-kendala Fungsional. Manajemen menghadapi berbagai kendala untuk mewujudkan tujuan-tujuannya. Kenyataan tentang eksistensi kendala-kendala tersebut selalu ada.

Berikut adalah sebuah kasus Pemrograman Linier. Kasus ini akan diselesaikan dengan MS Excel.

Maksimumkan 2X1 + 3X2
Terhadap fungsi‑fungsi kendala,
1. Dept. 5X1 + 6X2 ≤ 60
2. Dept. II X1 + 2X2 ≤ 16
3. Permintaan X1 X1≤ 10
4. Permintaan X2 X2 ≤ 6
X1, X2 ≥ 0

Agar dapat diselesaikan dengan Solver Excel maka model tersebut perlu dituangkan ke dalam format lembar kerja Excel sehingga manipulasi aritmatik mungkin dilakukan[1. Pembahasan dan contoh  yang lebih lengkap bisa dilihat di Siswanto, Operations Research, Erlangga 2007]

Peraga 5.51 Format Bawika dalam Excel

Agar model bisa diselesaikan dengan Solver Excel  sel-sel sisi ruas kanan E4:E7 dan Fungsi Tujuan di sel F11 harus didefinisikan.

Peraga 5.52 Formulasi Bawika dalam Excel

Untuk menjalankan Solver Excel, klik saja Tools dan gerakkan cursor ke Solver kemudian klik.

Peraga 5.53 Solver di menu Tools

Di layar kemudian akan tertayang:

Peraga 5.54 Menu Solver Parameters

[1] Target Cell, adalah sel yang mencerminkan nilai yang akan dimaksimumkan atau diminimumkan pada parameter ke dua. Dalam kasus ini, target sel adalah E11. Dengan kata lain, sel ini akan berisi nilai marjin total atau nilai fungsi tujuan Maka, letakkan saja kursor di sel tersebut dan kemudian tekan tombol “Enter”.

[2] Equal To, mencerminkan tujuan yang hendak kita capai dengan menggunakan Solver. Ada tiga pilihan yaitu Max (Maksimum), Min (Minimum, dan Value of. Dua yang pertama kita sudah mengenalnya, sedang Value of menandai nilai yang hendak kita tetapkan terhadap nilai fungsi tujuan atau marjin total dalam kasus ini. Bagaimanapun juga, bila nilai yang kita tetapkan itu berada diatas nilai maksimum penyelesaian maka nilai itu tidak akan tercapai. dalam kasus Bawika ini, klik saja Max untuk menandai bahwa kita meminta Solver untuk memaksimumkan fungsi tujuan atau marjin total.

[3] By Changing Cells, berisi nilai yang akan menentukan nilai fungsi tujuan atau marjin total. Sel ini sebenarnya mencerminkan variable putusan atau variable yang dicari. Untuk kasus Bawika ini, sel itu berada di B11 dan C11. maka, blok saja kedua sel tersebut dan kemudian tekan “Enter”

Setelah Seluruh pengisian tiga parameter ini lengkap , maka langkah selanjutnya adalah mengisi parameter kendala.

[4] Subject to Constraints, adalah kendala-kendala yang akan membatasi pemaksimuman atau peminimuman nilai fungsi tujuan atau marjin total. dalam kasus ini. Kendala itu tercermin di Penggunaan Kapasitas yang tidak boleh lebih besar dari Kapasitas Tersedia. Pertama kali, klik icon “Add” yang kemudian akan memunculkan menu Add Constraint. Karena seluruh kendala Bawika adalah kendala Pembatas, yaitu dengan tanda kendala maka dengan fasilitas Excel kita mungkin memasukkan keempat kendala itu sekaligus. Letakkan cursor di Cell Refrence dan kemudian pindahkan kursor ke sel E5:E8. Maka, “$E$5:$E8$” akan muncul di Cell Preference. Kemudian, karena Penggunaan Kapasitas tidak boleh melampaui Kapasitas Tersedia maka pilih saja tanda kendala “<=”. Ke empat, arahkan kursor ke Constraint dan kemudian pindahkan kursor ke sel F5:F8. Maka, “=$F$5:$F$8″ muncul di Constraint. Selanjutnya tekan saja ikon “OK” yang akan membawa kita kembali ke menu Solver Parameters.

Isian lengkap Solver Parameter yang siap diselesaikan atau “Solve”:

Klik saja “Solve” dan Solver akan segera bekerja.

Hasil akhir yang diharapkan dari penyelesaian kasus Pemrograman Linier adalah[1. lebih lengkap di Siswanto, Operations Research, Erlangga 2007]:

  1. Penyelesaian optimal
  2. Analisis sensitivitas parameter nilai ruas kanan dan parameter fungsi tujuan.

Penyelesaian Optimal

Peraga 5.61 Solver Report kasus Bawika

Analisis Sensitivitas

Peraga 5.62 Sensitivity Analysis Kasus Bawika

____________________

  1. Robert Dorfman, the Discovery of Linear Programming, IEEE ANALS July-September 1984, Vol. 6, No. 3. pp. 283-295, on line http://csdl.computer.org/comp/mags/an/1984/03/a3283abs.htm []
  2. J J O’Connor and E F Robertson , Leonid Vitalyevich Kantorovich, University of St Andrews, Scotland , on line, 26 June 2004, http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Kantorovich.html []
  3. Tjailling C Koopmans, Eficient Aloocation of Resources, Econometrica, Journal of the Econometric Society, Vol 19, No. 4, October, 1951, The University of Chicago, Reprinted dalam Cowles Foundation Paper 52, on line 08 July 2004, http://cowles.econ.yale.edu/P/cp/p00b/p0052.pdf; The Concise Encyclopaedia of economics, Tjalling Charles Koopmans (1910-85), The Library of Economics and Liberty, on line 26 June 2004, http://www.econlib.org/library/Enc/bios/Koopmans.html;
    Herbert E. Scarf, Tjalling Charles Koopmans August 28, 1910 – February 26, 1985, National Academic of Sciences, on line 26 June 2004, http://www.nap.edu/html/biomems/tkoopmans.html []
  4. Thayer Watkins, Tjalling Koopmans. Physicist and Economist, on line 26 June 2004, http://www2.sjsu.edu/faculty/watkins/koopmans.htm []
  5. George Bernard Dantzig, The Basic George B. Dantzig, on line review 14 January 2004, http://www.booksmatter.com/b0804748349.htm []
  6. Michael L. Overton, Linear Programming, Draft for Encyclopedia Americana, December 20, 1997, on line 25 June 2004, http://www.cs.nyu.edu/cs/faculty/overton/g22_lp/encyc/article_web.html []
  7. The Concise Encyclopaedia of Economics, Leonid Vitaliyevich Kantorovich (1912-86), The Library of Economics and Liberty, on line 26 June 2004, on line 26 June 2004, http://www.econlib.org/library/Enc/bios/Kantorovich.html []
  8. Nobel e-Museum, Leonid Vitaliyevich Kantorovich – Prize Lecture, on line 27 June 2004, http://www.nobel.se/economics/laureates/1975/kantorovich-lecture.html []
  9. Koopmans, T.C. (ed.), Activity analysis of production and allocation, John Wiley & Sons, New York, 339-347, 1951; Tjalling C. Koopmans Institute, On Tjalling C. Koopmans, Utrecgt Sgool of Economics, on line 26 June 2004, http://www.uu.nl/unpublish/tjallingkoopmans/abouttheinstitut/ontjallingckoopm/26768main.html; The History Of Economic Thought, The Cowles Commission, Economics New Shool, on line 26 June 2004, http://cepa.newschool.edu/het/schools/cowles.htm;The History Of Economic Thought, Production-The Cowles Contribution, Economics New School, on line 26 June 2004, http://cepa.newschool.edu/het/essays/get/production.htm []
  10. Nobel e-Museum, The Bank of Sweden Prize in Economic Sciences in Memory of Alfred Nobel 1975, on line 26 June 2004, http://www.nobel.se/economics/laureates/1975/presentation-speech.html []
  11. Nobel e-Museum, Tjalling C. Koopmans-Prize Lecture, on line 26 June 2004, http://www.nobel.se/economics/laureates/1975/koopmans-lecture.html []
  12. J J O’Connor and E F Robertson, School of Mathematics and Statistics
    University of St Andrews, Scotland,, John von Neumann, on line 14 January 2004, http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Von_Neumann.html; E. A. Fox., DEC Alpha, ei.cs.vt.edu, John von Neumann, on line 25 June 2004, http://ei.cs.vt.edu/~history/VonNeumann.html; BCC, John von Neumann, Condensed from “The Legend of John von Neumann” by P. Halmos, American Mathematical Monthly, April, 1973, pages 382-394, and “The Legacy of John von Neumann” by Barry Cipra, SIAM News, Sept., 1988, p. 28, 22-23., on line 25 June 2004, http://scidiv.bcc.ctc.edu/Math/vonNeumann.html []
  13. Tjailling C Koopmans, Activity Analysis and Its Application, Reprinted from American Economic Review, 43(2), Cowles Foundation Paper 75c, May 1953, on line 08 July 2004, http://cowles.econ.yale.edu/P/cp/p00b/p0075c.pdf; Tjailling C Koopmans, Concepts of Optimality and Their Uses, Reprinted from American Economic Review, 67*(3), 1977, Cowles Foundation Paper 449, on line 08 July 2004, http://cowles.econ.yale.edu/P/cp/p04a/p0449.pdf; The History Of Economic Thought, John von Neumann, 1903-1957, Economics Newshool, on line, 26 June 2004, http://cepa.newschool.edu/het/profiles/neumann.htm []
  14. Irvin J. Lustig & Jean-Franc¸ois Puget, Program Does Not Equal Program: Constraint Programming and Its Relationship to Mathematical Programming, on line 25 June 2004, http://pubsonline.informs.org/feature/pdfs/0092.2102.01.3106.29.pdf []
  15. J J O’Connor and E F Robertson, George Dantzig, School of Mathematics and Statistics, University of St Andrews, Scotland on line 14 January 2004, http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Dantzig_George.html []
  16. Leonid Vitaliyevich Kantorovich -Autobiography, on line 26 June 2004, http://www.nobel.se/economics/laureates/1975/kantorovich-autobio.html []

Leave a Reply

Your email address will not be published. Required fields are marked *