Riset Operasi (Model Grafik)

I. Program Linear: Metode Grafik Program linear adalah suatu pendekatan problem-solving yang dikembangkan untuk membantu manager dalam membuat keputusan. Pada program linear terdapat dua elemen dasar (properties) yaitu tujuan (objective) dan kendala (constraints). Kedua elemen kunci tersebut dinyatakan dalam suatu fungsi dari variabel keputusan (decision variables). Fungsi tujuan dapat berupa maksimisasi atau minimisasi dari suatu kuantitas, sedangkan kendala adalah fungsi yang membatasi tingkat pencapaian dari fungsi tujuan tersebut. A. Problem Maksimisasi Sederhana 1. Ilustrasi TAS Inc. adalah suatu industri kecil yang memproduksi tas sekolah. Para distributor TAS sangat antusias pada rencana perusahaan untuk membuat dua desain baru tas sekolah yaitu model ransel dan model klasik dan mereka bersedia untuk membeli semua produk baru tersebut dalam 3 bulan mendatang. Setelah melalui serangkaian penelitian mengenai semua tahap pekerjaan, manajemen perusahaan menyatakan bahwa kedua produk baru tersebut akan melalui tahapan pengerjaan yang meliputi: 1. Pemotongan 2. Penjahitan 3. Penyelesaian akhir 4. Pemeriksaan dan pengepakan Manager produksi telah menganalisa bahwa untuk menghasilkan satu tas model Ransel memerlukan 2 jam pengerjaan pada bagian pemotongan, 2 jam pada bagian penjahitan, 1 jam pada bagian penyelesaian, dan 2 jam pada bagian pemeriksaan dan pengepakan. Pada sisi lain, untuk menghasilkan satu tas model Klasik diperlukan 2 jam pengerjaan pada bagian pemotongan, 3.3 jam pada bagian penjahitan, 0.5 jam pada bagian penyelesaian dan 1.5 jam pada bagian pemeriksaan dan pengepakan. Informasi pengerjaan tersebut disajikan pada tabel berikut: Waktu yang diperlukan (jam) Jenis Produksi Pemotongan Penjahitan Penyelesaian Pemeriksaan dan Pengepakan Model Ransel 2 2 1 2 Model Klasik 2 3.3 0.5 1.5 Bagian akuntansi telah menganalisis bahwa setelah menghitung semua perkiraan biaya produksi dan harga jual maka akan diperoleh keuntungan sebesar Rp. 30.000,- untuk setiap tas model Ransel dan Rp. 20.000,- untuk model Klasik yang diproduksi. Dari departemen produksi diperoleh informasi bahwa untuk 3 bulan mendatang hanya tersedia 800 jam kerja pada bagian pemotongan, 1000 jam pada bagian penjahitan, 300 jam pada bagian penyelesaian dan 650 jam pada bagian pemeriksaan dan pengepakan. Masalah yang dihadapi oleh perusahaan TAS Inc. adalah menentukan berapa banyak tas model Ransel, dan berapa banyak model Klasik yang harus diproduksi untuk memaksimumkan keuntungan dengan memperhatikan ketersediaan waktu kerja pada setiap bagian tersebut. Jika anda ditugaskan bada bagian produksi, keputusan apa yang anda buat, yaitu berapa banyak tas Model Ransel dan Model Klasik masing-masing harus diproduksi dalam waktu 3 bulan mendatang? Tulislah keputusan anda pada tempat berikut dan anda akan memeriksa keputusan tersebut nanti. Jumlah tas Model Ransel Jumlah tas Model Klasik Total Keuntungan 2. Fungsi Tujuan Seperti dinyatakan di depan bahwa pada setiap program─── linear terdapat fungsi tujuan untuk memaksimumkan atau meminimumkan sesuatu. Pada kasus perusahaan TAS Inc., tujuannya adalah memaksimumkan keuntungan. Kita dapat menuliskan tujuan tersebut kedalam notasi matematik yaitu: X1 = jumlah tas model Ransel yang diproduksi X2 = jumlah tas model Klasik yang diproduksi Keuntungan perusahaan berasal dari dua sumber yaitu dari produksi tas model Ransel (X1) dan dari model Klasik (X2). Karena keuntungan dari model Ransel adalah Rp. 30.000,- per unit dan model Klasik Rp. 20.000,- per unit maka total keuntungan perusahaan adalah Rp. 30.000 X1 + Rp. 20.000 X2, dimana 30.000X1 merupakan kontribusi keuntungan model Ransel dan Rp. 20.000 X2 merupakan kontribusi dari model Klasik. Bila total keuntungan dilambangkan oleh simbol Ζ dalam puluhan ribu rupiah (Rp. 10.000) maka: Total keuntungan = Ζ = 3 X1 + 2 X2 Problem perusahaan TAS adalah menentukan nilai variabel X1 dan variabel X2 yang memberikan nilai maksimum Ζ. Dalam termonologi program linear variabel X1 , X2 disebut variabel keputusan (decision variables). Karena tujuan -- yaitu memaksimumkan keuntungan-- merupakan fungsi dari variabel keputusan maka persamaan Ζ = 3 X1 +2 X2 disebut dengan fungsi tujuan (objective function). Dengan demikian tujuan dari perusahaan TAS dapat dinyatakan dengan: Max Ζ = 3 X1 + 2 X2 Setiap kombinasi produksi tas Model Ransel dan Klasik merupakan solusi dari masalah ini. Namun demikian hanya solusi yang memenuhi semua kendala atau pembatas yang dinyatakan sebagai solusi yang layak (feasible solusions). Kombinasi produksi yang layak (feasible solusions) dan memberikan keuntungan maksimum merupakan kombinasi yang optimum atau disebut juga solusi optimum (optimal solusion). Sejauh ini kita belum dapat menentukan optimal solusion bahkan feasible solusions dari perusahaan TAS karena kita belum melihat semua kendala yang ada. Untuk mengetahui feasible solusions maka kita perlu mengidentifikasi semua kendala (constraints). 3. Kendala atau Pembatas (constraints) Setiap tas model ransel atau klasik harus melalui empat tahapan pengerjaan seperti yang telah disebut di atas dan karena adanya kendala ketersediaan waktu pada masing-masing bagian maka dapat diperkirakan bahwa jumlah produksi tas oleh perusahaan akan terbatas. Dari informasi produksi diketahui bahwa setiap unit tas model Ransel memerlukan 2 jam pengerjaan pada bagian pemotongan sehingga total waktu yang dibutuhkan untuk memotong X1 tas model Ransel adalah 2X1. Di sisi lain untuk menghasilkan satu unit tas model klasik juga dibutuhkan 2 jam pengerjaan pada bagian pemotongan sehingga total waktu yang dibutuhkan untuk memotong X2 tas model Klasik adalah 2X2 . Dengan demikian total waktu yang dibutuhkan untuk memotong X1 tas model Ransel dan X2 tas model Klasik dinyatakan sebagai: Total waktu pemotongan yang diperlukan = 2 X1 + 2 X2 Karena manager produksi menyatakan bahwa waktu kerja yang tersedia pada bagian pemotongan adalah 800 jam maka produksi kedua model tas tersebut harus memenuhi persyaratan pembatas berikut: 2 X1 + 2 X2 ≤ 800 dimana simbol ≤ menyatakan lebih kecil atau sama dengan. Pertidaksamaan di atas menunjukkan bahwa jumlah jam kerja yang digunakan untuk proses pemotongan tas sebanyak X1 dari model Ransel dan X2 untuk model Klasik harus lebih kecil atau sama dengan jumlah maksimum jam kerja yang masih tersedia di bagian tersebut. Dari tabel di atas juga terlihat bahwa untuk menghasilkan satu unit tas model Ransel memerlukan 2 jam penjahitan sedangkan setiap tas model Klasik memerlukan 3.3 jam. Oleh karena jam kerja yang tersedia hanya 1000 jam, maka fungsi pembatas untuk bagian panjahitan adalah: 2 X1 + 3.3 X2 ≤ 1000 Dengan cara yang sama kita dapat menyusun fungsi pembatas untuk bagian penyelesaian, yaitu: X1 + 0.5 X2 ≤ 300 dan fungsi pembatas untuk bagian pemeriksaan dan pengepakan adalah: 2 X1 + 1.5 X2 ≤ 650 Sejauh ini kita telah merumuskan model matematik dari semua kendala jam kerja pada setiap bagian proses produksi. Apakah masih ada kendala yang terlupakan? Mungkinkah perusahaan TAS memproduksi X1 tas model Ransel dan atau X2 model klasik yang negatif ? Jawabnya sudah jelas tidak mungkin. Oleh karena itu untuk mencegah X1 dan X2 bernilai negatif maka perlu dimasukkan dua kendala tambahan dalam model yaitu: X1 ≥ 0 dan X2 ≥ 0 tanda ≥ berarti lebih besar atau sama dengan. Dua kendala yang terakhir ini memastikan bahwa solusi dari masalah program linear tidak akan pernah bernilai negatif sehingga ia dikatakan sebagai kendala non negatif (non-negativity constraints). Kendala non negatif merupakan hal yang umum dijumpai pada program linear dan dituliskan sebagai: X1, X2 ≥ 0 4. Formulasi Matematik Formulasi matematik dari masalah perusahaan TAS sekarang sudah lengkap dengan mentranslasikan masalah riil perusahaan menjadi suatu model matematik. Model lengkap dari perusahaan TAS adalah: Max 3 X1 + 2 X2 dengan kendala (subject to, = s.t.) 2 X1 + 2 X2 ≤ 800 pemotongan (P) 2 X1 + 3.3 X2 ≤ 1000 penjahitan (J) X1 + 0.5 X2 ≤ 300 penyelesaian (S) 2 X1 + 1.5 X2 ≤ 650 pemeriksaan dan pengepakan (R&K) X1, X2 ≥ 0 Langkah berikutnya adalah mencari kombinasi nilai X1 dan X 2 yang memenuhi semua kendala serta menghasilkan nilai dari fungsi tujuan yang lebih besar atau sama dengan nilai pada feasible solusion. Bila hal ini telah dilakukan maka solusi optimum akan tercapai. 5. Solusi Grafik Program linear yang hanya melibatkan dua variabel (X1, X2 ) dapat diselesaikan dengan metode grafik. Untuk masalah yang melibatkan lebih dari dua variabel keputusan maka penyelesaianya dilakukan dengan metode Simplex. Setelah tahun 1980-an seiring dengan perkembangan mikrokomputer maka solusi dari masalah program linear dapat dilakukan dengan komputer. Beberapa program yang dapat digunakan adalah: LINDO, LINGGO, dan THE MANAGEMENT SCIENTIST. Penggunaan metode grafik dimulai dengan menentukan sumbu horisontal (X1)dan sumbu vertikal (X2) sehingga nilai dari variabel keputusan X1 berada pada sumbu horisontal dan nilai dari variabel keputusan X2 berada pada sumbu vertikal. Karena setiap titik merupakan solusi yang mungkin (possible), maka titik-titik pada grafik merupakan solusion points (titik-titik solusi). Solusion point dimana X1 = 0 dan X2 = 0 disebut titik origin. Langkah berikutnya adalah menentukan manakah dari titik-titik solusi yang berhubungan dangan feasibel solusion. Karena X1, X2 adalah nonnegatif maka kita hanya mempertimbangan sebagian saja dari grafik tersebut yang memenuhi persyaratan nonnegatif X1, X2 ≥ 0 [lihat panel (a) pada grafik]. Selanjutnya adalah menggambarkan grafik dari semua fungsi pembatas (constraints) seperti diformulasikan pada model matematik. Dari model tersebut terlihat bahwa fungsi pembatas pemotongan dicerminkan oleh pertidaksamaan: 2 X1 + 2 X2 ≤ 800 Untuk mendapatkan titik-titik solusi yang memenuhi kondisi ini dimulai dengan menggambarkan hubungan tersebut sebagai suatu persamaan yaitu titik-titik yang memenuhi persamaan 2 X1 + 2 X2 = 800. Karena persamaan ini merupakan garis lurus maka ia dapat digambarkan dengan mencari dua titik yang memenuhi persamaan tersebut dan selanjutnya menarik garis yang melalui kedua titik tersebut. Titik pertama diperoleh dengan menetapkan nilai X1 = 0 dan mendapatkan nilai X2 = 40 yang memenuhi persamaan tersebut. Titik kedua diperoleh dengan menetapkan X2 = 0 dan mendapatkan nilai X1 = 40. Apabila titik pertama (X1 = 0, X2 = 40) dan titik kedua (X1 = 40, X2 = 0) dihubungkan maka diperoleh garis lurus seperti pada grafik panel (b). Karena fungsi pembatas proses pemotongan merupakan pertidaksamaan 2 X1 + 2 X2 ≤ 800 manakah titik-titik solusi yang memenuhi pertidaksamaan tersebut? Karena semua titik pada garis memenuhi persamaan 2X1 + 2X2 = 800 maka kita yakin bahwa semua titik pada garis tersebut memenuhi fungsi kendala. Namun manakah titik-titik solusi yang memenuhi pertidaksamaan 2X1 + 2X2 < 800? Setiap titik yang berada di bagian dalam kurva menuju titik origin seperti ditunjukkan oleh tanda panah adalah titik-titik solusi. Dengan cara yang sama kita dapat menggambarkan fungsi pembatas untuk bagian penjahitan (panel c), bagian penyelesaian (panel d), serta bagian pemeriksaan dan pengepakan (panel e). Sekarang kita telah mendapatkan empat grafik terpisah untuk masing-masing fungsi kendala. Dalam program linear kita perlu mengidentifikasi titik-titik solusi yang memenuhi semua kendala secara simultan. Untuk itu kita perlu menggambarkan keempat kendala tersebut dalam satu salib sumbu dan memperhatikan daerah yang terdiri dari titik-titik yang memenuhi keempat kendala secara simultan (panel f). Karena solusi yang memenuhi keempat kendala tersebut dikenal dengan feasible solusion, maka daerah yang merupakan titik-titik solusi disebut feasible solusion region atau sederhananya feasible region. Setiap titik pada garis batas feasible region atau di dalam feasible region adalah titik solusi yang feasible (feasible solusion point). Gambar 2 menampilkan kembali feasible region yang memenuhi keempat fungsi pembatas dengan skala yang lebih besar agar lebih memudahkan menemukan solusi optimal. Solusi optimal dapat diketahui dengan mengevaluasi setiap feasible solusion dan solusi yang memberikan nilai fungsi tujuan yang terbesar adalah solusi optimal. Masalahnya adalah feasible solusion tersebut jumlahnya tidak terhingga. Oleh karena itu langkah yang paling efisien adalah dengan menentukan satu nilai feasible solusion dan menggambarkannya pada kurva feasible region. Setelah itu menggeser garis fungsi tujuan tersebut hingga menyinggung titik dari daerah feasible yang terluar (Gambar 3). Titik singgung itulah yang merupakan solusi optimal dari program linear tersebut. X2 X2 400 P Non negativity 200 0 X1 0 200 400 X1 0 200 400 X1 0 200 400 600 X1 0 X2 400 200 200 400 X1 0 200 400 X1 X2 600 400 200 J S (a) (b) (c) (d) X2 (e) (f) 400 200 X2 600 400 200 R&K Gambar 1. Feasible solusion untuk setiap fungsi pembatas • • • • 0 200 400 600 X1 X2 600 400 200 Pemotongan Penjahitan Penyelesaian Pemeriksaan dan pengepakan Gambar 2. Feasible region yang memenuhi keempat fungsi pembatas secara simultan Feasible region • • c • Feasible region 0 200 400 600 X1 X2 600 400 200 3X1 + 2X2 = 950 persamaan fungsi tujuan Solusi optimal a b d (250 , 100) Gambar 3. Solusi optimal dari perusahaan TAS Inc. • Untuk memperoleh solusi optimal yang tepat sangat tergantung pada tingkat ketelitian skala pembuatan grafik. Dengan mengacu pada gambar 3 tersebut di atas dapat disimpulkan bahwa kombinasi produksi yang memberikan keuntungan maksimum ditunjukkan oleh titik ekstrim c yaitu 250 unit tas model Ransel (X1) dan 100 unit tas model Klasik (X2). Untuk lebih meyakinkan akurasi solusi optimal dapat dilakukan dengan menyelesaikan persamaan simultan yang berhubungan dengan titik perpotongan dua garis. Dengan memperhatikan gambar 2 dan gambar 3 terlihat bahwa solusi optimal berada pada titik c yang merupakan perpotongan fungsi pembatas penyelesaian X1 + 0.5 X2 = 300 (1) dengan fungsi pembatas pemeriksaan dan pengepakan yaitu : 2 X1 + 1.5 X2 = 650 (2) Dari persamaan (1) diperoleh X1 = 300 - 0.5 X2 . (3) Dengan mensubstitusikan nilai X1 ke dalam persamaan (2) didapat nilai X2 , yaitu: 2(300 - 0.5 X2) + 1.5 X2 = 650 600 - X2 + 1.5 X2 = 650 0.5 X2 = 650 - 600 X2 = 50/0.5 = 100 Setelah memasukkan nilai X2 = 100 ke dalam persamaan (3) untuk diperoleh nilai X1 yaitu: X1 = 300 - 0.5 X2 = 300 - 0.5 (100) = 300 - 50 = 250 Solusi dari persamaan simultan tersebut menghasilkan nilai X1 = 250 dan X2 = 100 yang sesuai dengan hasil dari metode grafik. Dengan memasukkan nilai solusi optimal tersebut ke dalam fungsi tujuan maka diperoleh Z = 3 X1 + 2 X2 = 3 (250) + 2 (100) = 950 Karena fungsi tujuan tersebut dinyatakan dalam puluhan ribu rupiah maka keuntungan perusahaan adalah 9.500.000 rupiah. Tingkat keuntungan ini merupakan keutungan tertinggi yang dapat dicapai oleh perusahaan TAS Inc. Ringkasan prosedur problem maksimisasi 1. Persiapkan grafik feasible solusion points untuk setiap fungsi pembatas 2. Tentukan feasible region dengan mengidentifikasi titik-titik solusi yang memenuhi semua fungsi pembatas secara simultan. 3. Gambarkan garis fungsi tujuan yang menunjukkan nilai dari variabel X1 dan X2 serta menghasilkan nilai tertentu dari fungsi tujuan. 4. Geser garis fungsi tujuan ke arah luar paralel dengan garis pertama (menjauhi titik origin) hingga menyinggung bagian terluar dari feasible region. 5. Sebuah titik feasible solusion yang memberikan nilai tertinggi pada fungsi tujuan merupakan solusi optimal. 6. Solusi optimal terletak pada salah satu titik ekstrim dari feasible region. Slack variables Sebagai tambahan dari solusi optimal yaitu X1 = 250 unit tas model Ransel dan X2 = 100 unit tas model klasik dan keuntungan yang diharapkan yaitu Rp. 9.500.000,- manajemen perusahaan juga ingin mendapatkan informasi mengenai waktu kerja yang digunakan pada masing-masing bagian produksi. Kita dapat memperoleh informasi ini dengan mensubstitusikan nilai variabel X1 = 250 dan X2 = 100 kedalam setiap fungsi pembatas, yaitu: 2 (250) + 2 (100) = 700 jam pada bagian pemotongan 2 (250) + 3.3 (100) = 830 jam pada bagian penjahitan (250) + 0.5 (100) = 300 jam pada bagian penyelesaian 2 (250) + 1.5 (100) = 650 jam pada bagian pemeriksaan dan pengepakan Hasil di atas menunjukkan bahwa produksi X1 = 250 unit tas model Ransel dan X2 = 100 unit tas model Klasik telah menggunakan semua kapasitas waktu yang tersedia pada bagian penyelesaian serta bagian pemeriksaan dan pengepakan namun masih tersisa 100 jam (yaitu 800-700) pada bagian pemotongan dan 170 jam (yaitu 1000-830) pada bagian penjahitan. Bagian dari sumberdaya yang tidak habis digunakan ini dalam terminology riset operasi disebut slack untuk kendala yang terkait dengan sumberdaya tersebut. B. Problem Minimisasi Sederhana Kasus perusahaan TAS Inc. adalah contoh masalah maksimisasi; namun banyak masalah program linear berhubungan dengan minimisasi. Berikut adalah masalah minimisasi yang dihadapi oleh perusahaan SBN. 1. Ilustrasi Perusahaan SBN memproduksi dua jenis bahan kimia untuk pembuatan sabun yaitu untuk sabun mandi (soaps) dan sabun cuci (detergens). Berdasarkan pada analisa ketersediaan bahan baku dan permintaan bulan mendatang maka manajemen memutuskan untuk menghasilkan total barang 1 dan barang 2 seperti tersebut di atas minimal sebanyak 350 galon. Untuk bulan depan telah diperoleh pesanan barang 1 tidak kurang dari 125 galon. Untuk menghasilkan setiap galon barang 1 memerlukan 2 jam pengerjaan sedangkan barang 2 memerlukan 1 jam waktu pengerjaan. Ketersediaan waktu pengerjaan untuk bulan depan hanya tersisa 600 jam. Tujuan perusahaan SBN adalah menghasilkan barang 1 dan 2 yang memenuhi persyaratan di atas dengan total biaya produksi yang minimum. Biaya produksi untuk menghasilkan barang 1 adalah $ 2 per galon sementara biaya untuk barang 2 adalah $ 3 per galon. Untuk menyelesaikan masalah perusahaan SBN maka model linear dari masalah tersebut perlu disusun. Pertama adalah menetapkan variabel keputusan dan fungsi tujuan, sebagai berikut: X1 = jumlah barang 1 yang harus diproduksi (galon) X2 = jumlah barang 2 yang harus diproduksi (galon) Oleh karena biaya produksi barang 1 sebesar $ 2 per galon dan biaya untuk barang 2 adalah $ 3 per galon maka fungsi tujuan yang menyangkut minimisasi dinyatakan oleh persamaan berikut: Min 2 X1 + 3 X2 Berikutnya adalah menyusun kendala yang dihadapi yaitu pertama, permintaan untuk barang 1 minimal 125 galon. Jadi kendalanya adalah: X1 ≥ 125 Oleh karena total kombinasi kedua barang paling tidak 350 galon maka kendala kedua dapat ditulis sebagai berikut: X1 + X2 ≥ 350 Akhirnya karena ketersediaan waktu pengerjaan hanya 600 jam sementara untuk menghasilkan satu galon barang 1 memerlukan 2 jam pengerjaan dan untuk menghasilkan satu galon barang 2 memerlukan 1 jam maka kita menuliskan kendala ketiga sebagai berikut: 2X1 + X2 ≤ 600 Setelah menambahkan kendala non negatif maka model linear dari masalah di atas dapat ditulis sebagai berikut: Min 2 X1 + 3 X2 s.t. X1 ≥ 125 Permintaan barang 1 X1 + X2 ≥ 350 Total produksi 2X1 + X2 ≤ 600 Waktu pengerjaan X1 , X2 ≥ 0 Karena masalah linear tersebut hanya memiliki dua variabel keputusan maka metode grafik dapat digunakan untuk menyelesaikannya. Langkah pertama adalah dengan menggambarkan garis fungsi kendala secara terpisah maka feasible solution untuk masing-masing kendala dapat ditentukan. Dengan menggabungkan semua feasible solution yang ada maka diperoleh feasible region seperti pada gambar berikut: Minimum X1 = 125 Waktu pengerjaan 2X1 + X2 = 600 Produksi X1 + X2 = 350 0 100 200 300 400 500 600 X1 X2 600 500 400 300 200 100 Gambar 4. Feasible region yang memenuhi semua fungsi pembatas 2X1 + 3X2 = 1200 2X1 + 3X2 = 800 • X2 600 500 400 300 200 100 0 100 200 300 400 500 600 X1 Solusi Optimum (X1= 250, X2 = 100) Gambar 5. Solusi optimal dari perusahaan SBN Untuk menemukan solusi biaya minimum, maka perlu digambarkan garis fungsi tujuan dengan nilai biaya tertentu. Misalkan kita menggambarkan garis fungsi tujuan dengan nilai 1200 yaitu 2X1 + 3X2 = 1200 seperti terlihat pada gambar 5 di atas. Dari gambar tersebut terlihat jelas bahwa terdapat titik-titik solusi yang memberikan nilai 1200. Untuk mendapatkan nilai X1 dan X2 yang menghasilkan biaya minimum maka kita menggeser garis fungsi tujuan tersebut kearah yang menghasilkan nilai yang lebih kecil yaitu ke arah kiri-bawah hingga memotong titik terluar dari feasible region. Titik terluar umumnya merupakan salah satu dari titik-titik ekstrim pada feasible region. Dari gambar tersebut terlihat bahwa garis fungsi tujuan 2X1 + 3X2 = 800 memotong feasible region di titik ekstrim X1 = 250 dan X2 = 100. Titik ekstrim inilah yang memberikan solusi biaya yang minimum dengan nilai 800. Dari kedua gambar tersebut juga terlihat bahwa pada solusi optimum kendala waktu pengerjaan dan kendala produksi total saling bersilangan (binding). Ringkasan prosedur problem Minimisasi 1. Persiapkan grafik feasible solusion points untuk setiap fungsi pembatas 2. Tentukan feasible region dengan mengidentifikasi titik-titik solusi yang memenuhi semua fungsi pembatas secara simultan. 3. Gambarkan garis fungsi tujuan yang menunjukkan nilai dari variabel X1 dan X2 serta menghasilkan nilai tertentu dari fungsi tujuan. 4. Geser garis fungsi tujuan ke arah kiri-bawah paralel dengan garis pertama (menuju titik origin) hingga menyinggung bagian terluar dari feasible region. 5. Sebuah titik feasible solusion yang memberikan nilai terkecil pada fungsi tujuan merupakan solusi optimal. 6. Solusi optimal terletak pada salah satu titik ekstrim dari feasible region. C. Penyusunan model (Modeling) Modeling adalah suatu proses mentranslasikan pernyataan verval dari suatu problem ke dalam suatu pernyataan matematik. Pada kasus sederhana yang melibatkan dua variabel keputusan dan beberapa fungsi pembatas, formulasi model dapat dilakukan dengan cepat. Namun pada kasus yang besar dan rumit dengan melibatkan banyak variabel keputusan dan kendala maka diperlukan suatu pedoman penyusunan model untuk membantu menemukan solusi dari persoalan tersebut. Proses formulasi program linear merupakan suatu seni dengan imajinasi tinggi yang memerlukan banyak latihan dan pengalaman. Meskipun setiap problem memiliki keunikan tersendiri namun ia juga memiliki kesamaan-kesamaan umum. Pedoman penyusunan model akan sangat berguna terutama bagi mereka yang baru mempelajari program linear. 1. Pahami persoalan secara komprehensif Bacalah persoalan secara cepat dan cermat untuk membayangkan faktor apa saja yang terlibat. Identifikasi faktor-faktor tersebut untuk dimasukkan kedalam model. Jika persoalan tersebut sangat rumit, buatlah catatan seperlunya karena ia akan membantu dalam menentukan fokus dari persoalan tersebut. 2. Tulislah pernyataan verbal dari fungsi tujuan dan kendala Pernyataan verbal ini nantinya akan ditraslasikan ke dalam pernyataan matematik. Pada tahap ini fungsi tujuan dapat berupa maksimumkan keuntungan atau minimumkan biaya operasi. Meskipun mereka yang sudah berpengalaman sering mengalami kesulitan bila meninggalkan tahap ini. 3. Definisikan setiap variabel keputusan Renungkan, keputusan apa yang harus dibuat oleh sang manager. Faktor-faktror apa saja yang dapat dikontrol. Pendefinisian variabel keputusan harus ditujukan untuk memudahkan formulasi matematik dari fungsi tujuan dan sisi kiri dari fungsi pembatas. 4. Tulislah fungsi tujuan sebagai fungsi dari variabel keputusan Translasikan pernyatan verbal dari fungsi tujuan pada tahap 2 ke dalam pernyataan matematik. Fungsi tujuan haruslah merupakan fungsi linear dari variabel keputusan. 5. Tulislah kendala sebagai fungsi dari variabel keputusan Translasikan pernyatan verbal dari semua kendala pada tahap 2 ke dalam pernyataan matematik. Sisi kiri dari persamaan/pertidaksamaan haruslah merupakan fungsi linear dari variabel keputusan. Setelah melalui tahap tersebut kita mendapatkan model liner yang merepresentasikan persoalan yang dikaji. Penyelesaian dari model tersebut akan menghasilkan solusi optimal berupa nilai dari variabel keputusan, nilai dari slack/surplus variabel. Solusi dengan komputer akan memberikan tambahan informasi seperti reduced cost, dual prices, dan analisis sensitivitas bagi fungsi tujuan dan semua kendala. Melalui interpretasi yang benar terhadap semua informasi yang diperoleh dapat menghasilkan keputusan yang dapat dipertanggungjawabkan secara ilmiah.