![HANDOUT MATA KULIAH. Dosen Pengampuh - Meyta Dwi Kurniasih, M.pd. [PDF]](https://pdfs.asia/img/200x200/handout-mata-kuliah-dosen-pengampuh-meyta-dwi-kurniasih-mpd.jpg)
5 0 6 MB
HANDOUT MATA KULIAH
Dosen Pengampuh :
Meyta Dwi Kurniasih, M.Pd.
NAMA : ....................................................................................................... KELAS : ....................................................................................................... NIM : ...........................................................................................................
PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS MUHAMMADIYAH PROF DR HAMKA JAKARTA- 2015
Page 1
Kata Pengantar Puji syukur kami panjatkan ke hadirat Allah SWT atas karunia dan hidayah-Nya, kami dapat menyusun bahan ajar modul manual untuk mahasiswa Pendidikan Matematika, yakni mata kuliah Statistika Matematika. Handout yang disusun ini berdasarkan silabus perkuliahan Program Linier yang berlaku di Universitas Muhammadiyah Prof. DR. HAMKA. Prasyarat mengikuti mata kuliah Program Linier ini adalah lulus mata kuliah Aljabar Linier. Deskripsi mata kuliah ini adalah formulasi model-model optimasi linier, representasi aljabar dan geometri, metode simpleks, uji kesensitivitasan dan duaalitas, transportasi serta analisis pasca optimum. Penyusunan handout ini tidak lepas dari dorongan semua pihak baik berupa moril maupun materil yang tidak dapat kami sebutkan satu persatu, terutama pada seluruh keluarga besar Program Studi Pendidikan Matematika. Kami menyadari masih banyak kekurangan atas modul ini, oleh sebab itu kritik dan saran terhadap penyempurnaan modul ini kami harapkan. Demikian, semoga modul ini dapat bermanfaat bagi semua, khususnya mahasiswa Pendidikan Matematika FKIP UHAMKA. Jakarta, Maret 2015 Penyusun,
Meyta Dwi Kurniasih, M.Pd.
Meyta Dwi Kurniasih, M.Pd. P. Matematika UHAMKA
Daftar Isi Kata Pengantar........................................................................................................................................................ii Dafta Isi......................................................................................................................................................................iii BAB I Model Matematika ....................................................................................................................................1 A. Pendahuluan......................................................................................................................................1 B. Definisi Pemprograman Linier..................................................................................................1 C. Ide Dasar Program Linier.............................................................................................................1 D. Karakteristik Pemprograman Linier.......................................................................................2 E. Formulasi Masalah Pemprograman Linier...........................................................................3 F. Soal Latihan........................................................................................................................................3 BAB II Pendekatan Geometris ..........................................................................................................................8 A. Metode Grafik dengan Dua Variabel.......................................................................................8 B. Metode Grafik dengan Tiga Variabel....................................................................................19 BAB III Analisis Simpleks..................................................................................................................................24 A. Pengantar Simpleks.....................................................................................................................24 B. Metode Pemecahan Dasar (Basis).........................................................................................26 C. Simpleks dengan Tabel Berkolom Variabel Dasar..........................................................28 D. Membaca Tabel Optimal............................................................................................................32 E. Soal Latihan.....................................................................................................................................33 BAB IV Metode Simpleks I ...............................................................................................................................36 A. Metode M Charnes........................................................................................................................36 B. Metode Simpleks Fase 1.............................................................................................................38 C. Soal Latihan.....................................................................................................................................40 BAB V Metode Simpleks II ...............................................................................................................................44 A. Langkah-langkah Metode Simpleks 2 Fase........................................................................44 B. Contoh Soal......................................................................................................................................44 C. Soal Latihan.....................................................................................................................................46 BAB VI Primal, Dual dan Kemerosotan ......................................................................................................53 A. Primal dan Dual.............................................................................................................................53 B. Kemerosotan...................................................................................................................................60
iii
Meyta Dwi Kurniasih, M. Pd. Pemrograman Linier C. Soal Latihan.....................................................................................................................................61 BAB VII Model Transportasi ...........................................................................................................................67 A. Pendahuluan...................................................................................................................................67 B. Formulasi Model Matematika..................................................................................................68 C. Pendekatan Model Transportasi............................................................................................70 D. Skenario Model Transportasi..................................................................................................78 E. Langkah-langkah Penyelesaian...............................................................................................78 F. Contoh Soal......................................................................................................................................80 G. Soal Latihan.....................................................................................................................................84 Daftar Pustaka......................................................................................................................................................92
iv
BAB I Model Matematika
A. Pendahuluan Program linier (Linier Programming) merupakan pengembangan lebih lanjut dari konsep-konsep aljabar linier. Model ini dikembangkan oleh George B. Dantzig, seorang matematikawan AS tahun 1947. Benih- benih model ini sesungguhnya sudah ditemukan jauh sebelumnya. Seorang matematisian Rusia bernama L.V. Kontrovich memperkenalkan penerapan program linier dalam bidang produksi tahun 1939. Lebih dari seabad sebelumnya tahun 1928, Fourier asal Perancis juga telah merumuskan masalah program linier. Akan tetapi baru setelah Dantzig mengembangkan dan mempopulerkannya, model ini memperoleh perhatian yang berarti. Dantzig pulalah yang dikenal dunia sebagai “Bapak Program Linier.”
B. Definisi Pemprograman Linier Pemprograman linier adalah metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimalkan keuntungan atau meminimummkan biaya. Program linier berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier (Taha, 1993). Semula model program linier dimanfaatkan dibidang kemiliteran, khususnya oleh Angkatan Udara AS (USAF), untuk merencanakan dan memecahkan masalahmasalah logistik di masa perang. Kini penggunaan program linier sudah sangat meluas terutama di bidang bisnis. Selain itu banyak digunakan untuk menyelesaikan masalah optimasi didalam industri, perbankan, pendidikan, dan masalah-masalah lain yang dapat dinyatakan dalam bentuk linier.
C. Ide Dasar Program Linier Telah disampaikan sebelumnya bahwa program linier adalah suatu model optimasi persamaan linier berkenaan dengan kendala-kendala linier yang dihadapinya
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA Masalah program linier berarti adalah masalah pencarian nilai-nilai optimum (maksimum atau minimum) sebah fungsi linier pada suatu sistem atau sehimpun kendala linier. Fungsi linier yng hendak dicari nilai optimumnya, berbentuk sebuah persamaan, disebut fungsi tujuan, sedangkan fungsi-fungsi linier yang harus terpenuhi dalam optimasi fungsi tujuan tadi, dapat berbentuk persamaan atau pertidaksamaan, disebut fungsi kendala. Agar suatu masalah optimasasi dapat diselesaiakan dengan program linier, ada beberapa syarat yang harus dipenuhi : 1. Masalah itu harus dapat diubah menjadi permasalahan matematis. Ini berarti bahwa masalah tadi harus bisa dituangkan kedalam bentuk model matematik, dalam hal ini model linier, baik berupa persamaan atau pertidaksamaan. 2. Keseluruhan sistem permasalahan harus dapat dipilih-pilih menjadi satuansatuan aktivitas, misal :
di mana
dan
adalah aktivitas.
3. Masing-masing aktivitas hars dapat ditentukan dengan tepat, baik jenis maupun letaknya dalam model program linier. 4. Setiap aktivitas harus dapat dikualivikasikan sehingga masing-masing nilainya dapat dihitung dan dibandingkan. Dengan demikian di dalam suatu masalah program linier dapat dilakukan langkah sebagai berikut : 1. Menentukan aktivitas 2. Menentukan sumber-sumber (masukan) 3. Menghitung jumlah mtas 4. Masukan dan keluaran untuk setiap satuan aktivitas 5. Merumuskan model, yakni membentuk fungsi tujuan dan fungsi-fungsi kendala.
D. Karakteristik Program Linier 1. Sifat linieritas suatu kasus dapat ditentukan dengan menggunakan beberapa cara. Secara statistik, cara ini dapat diperiksa kelinieran menggunakan grafik (diagram pencar). 2. Sifat proposional dipenuhi jika kontribusi setiap variabel pada fungsi tujuan atau penggunaan sumber daya yang membatasi proposional terhadap level nilai variabel. Jika harga per unit produk misalnya adalah sama berapa pun jumlah yang dibeli, maka sifat proposional dipenuhi. Atau jika pembelian dalam jumlah
2
Handout Program Linier : Model Matematika besar mendapatkan diskon, maka sifat proposional tidak dipenuhi. Jika penggunaan sumber daya per unit tergantung dai jumlah yang diproduksi, maka sifat proposional tidak dipenuhi. 3. Sifat additivitas mengasumsikan bahwa tidak ada bentuk perkalian silang diantara berbagai aktivitas, sehingga tidak dapat ditemukan bentuk perkalian silang pada model. Sifat aditivitas berlaku baik bagi sifat tujuan maupun pembatas (kendala). Sifat aditivitas dipenuhi jika fungsi tujuan merupakan penambahan langsung kontribusi masing-masing variabel keputusan. 4. Sifat divisiabel berarti unit aktivitas dapat dibagi dalam sembarang level fraksional, sehingga nilai variabel keputusan non integer dimungkinkan 5. Sifat kepastian menunjukkan bahwa semua parameter model berupa konstanta. Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan suatu nilai pasti, bukan merupakan nilai dengan peluang tertentu.
E. Formulasi permasalahan
☺ Masalah keputusan yang sering dihadapi analis adalah alokasi optimum sumber daya.
☺ Sumber daya dapat berupa uang, tenaga kerja, bahan mentah, kapasitas mesin, waktu, ruangan atau teknologi.
☺ Tugas analis adalah mencapai hasil terbaik dengan keterbatasan sumber daya itu.
☺ Setelah
masalah diidentifikasikan, tujuan ditetapkan, langkah selanjutnya adalah formulasi model matematik.
☺ Formulasi model matematik . F. Soal Latihan : Aktivitas 1
Buatlah model matematik dari setiap permasalahan berikut :
1. Seorang penjahit mempunyai bahan 60 m woll dan 40 m katun, dari bahan tersebut ia akan membuat setelan jas dan rok untuk di jual. Satu stel jas memerlukan 3 m woll dan 1 m katun. Sedangkan satu rok memerlukan 2 m woll dan 2 m katun. Berapa stel jas dan rok yang harus penjahit tersebut buat agar mendapat
3
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA keuntungan sebesar- besarnya. Bila satu stel jas Rp. 1.500.000 dan 1 stel rok Rp.1.000.000? Jawab : .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. ..................................................................................................................................................................
2. Seorang anak diharuskan meminum dua jenis obat setiap hari. Obat jenis I mengandung 5 unit vitamin A dan 3 unit vitamin B. Sedangkan obat jenis II mengandung 10 unit vitamin A dan 1 unit vitamin B. Dalam satu hari anak itu memerlukan 20 unit vitamin A dan 5 unit vitamin B. Jika harga obat jenis I Rp. 400 dan obat jenis II Rp. 800 per biji. Susunlah model matematikanya dan fungsi sasaran agar pengeluaran sekecil mungkin? Jawab : .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. ..................................................................................................................................................................
3. Seorang petani besar memiliki tanah seluas 50 ha. yang akan ditanami padi, jagung dan kedelai. Untuk mengelola tanahnya ini dia memiliki modal sebesar Rp 6.000.000,- untuk biaya persiapan penanaman.Ketiga jenis tanaman ini
4
Handout Program Linier : Model Matematika memerlukan tenaga kerja, biaya dan memberikan keuntungan masing-masing sebagai berikut :
Tanaman Padi Jagung Kedelai
Orang hari/ ha
Biaya/ ha (Rp)
6 8 10
100.000 150.000 120.000
Keuntungan/ ha (Rp) 60.000 100.000 80.000
Susunlah model matematikanya dan fungsi sasaran agar pendapatan sebesar mungkin? Jawab : .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. ..................................................................................................................................................................
4. Seorang ahli pertanian ingin mencampur dua jenis pupuk dengan memberikan 15 g kalium karbonat, 20 g nitrat dan 24 g fosfat seminimal mungkin pada suatu takaran. Satu takaran pupuk merek I yang harganya Rp. 75.000 per bungkus memerlukan 3 g kalium karbonat, 1 g nitrat dan 1 g fosfat. Pupuk merek II yang harganya Rp. 60.000 per bungkus memerlukan 1 g kalium karbonat, 5 g nitrat dan 2 g fosfat. Susunlah model matematikanya dan fungsi sasaran agar pengeluaran sekecil mungkin? Jawab : .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. ..................................................................................................................................................................
5
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA 5. PT. “WAHYU” mempunyai 600 orang pegawai dan menghadapi persoalan untuk mengurangi biaya- biaya umum. Tiap pegawai mendapat penggantian ongkos jalan Rp 50,- per hari. Untuk menggurangi biaya transportasi ini, direncanakan untuk membeli sejumlah micro bus dan bus yang masing-masing dapat memuat 15 dan 40 orang untuk antar jemput pegawai. Untuk itu perusahaan menyediakan dana dalam jumlah terbatas, masing-masing untuk maintanance kendaraan Rp 225.000,- per bulan dan bensin 450 liter per hari. Selanjutnya dari tiap kendaraan diketahui : Keterangan Micro Bus Bus Maintanance per bulan (Rp) 7.500 10.000 Pemakaian bensin (liter) 10 30 Tentukan model matematika dari masalah di atas, jika Micro Bus memiliki life time yang relatif lebih panjang dari Bus! Jawab : .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. .................................................................................................................................................................. ..................................................................................................................................................................
Aktivitas 2
Dari kelima masalah di atas, apakah perbedaan dari setiap masalah tersebut!
........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ...........................................................................................................................................................................
6
Handout Program Linier : Model Matematika
Aktivitas 3
Tentukan langkah- langkah dalam membuat model matematika dari sebuah masalah program liner!
........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ...........................................................................................................................................................................
Tanggal
Nilai
Paraf Dosen
7
BAB II Pendekatan Geometris Bab ini akan dibahas upaya menganalisis persoalan program linier dua variabel atau tiga variabel dengan pendekatan geometris atau metode grafik. Program linier adalah teknik analisis kuantitatif yang tergabung dalam penelitian operasional. Analisis kualitatif maksudnya proses pengembangan secara bertahap dan sistematis dengan memperhatikan tiga tahap yaitu: (1) identifikasi persoalan dan penyusunan model matematika, (2) analisis model, dan (3) merumuskan kesimpulan dan implementasi hasil. Berikut beberapa cara penyelesaian masalah progran linier dengan metode grafik..
A. Metode Grafik dengan Dua Variabel Ada metode untuk mengidentifikasi solusi optimum pada ruang/ daerah feasible yaitu metode kesamaan garis (isoline) dan metode titik ekstrim.
1.1. Langkah- langkah penyelesaian masalah program linier dengan Metode Isoline : 1. Tentukan kemiringan garis fungsi tujuan (merupakan himpunan infinitif dari
isoline). Pilihlah dua titik tertentu di daerah feasible Gambarlah garis fungsi tujuan yang mengenai titik-titik tersebut 2. Tentukan arah peningkatan (penurunan) dari fungsi tujuan persoalan maksimum (minimum). Pilihlah dua garis ( isoline) fungsi tujuan di daerah
feasible dan evaluasi nilai fungsi tujuan pada kedua garis isoline tersebut. 3. Ikuti arah peningkatan atau penurunan sampai mencapai titik batas (sudut) dimana peningkatan atau penurunan dari fungsi tujuan keluar dari daerah
feasible 4. Solusi optimum diperoleh dari titik batas di mana peningkatan atau penurunan dari fungsi tujuan (Z) akan meninggalkan daerah feasible.
Handout Program Linier : Pendekatan Geometris
1.2. Langkah- langkah penyelesaian masalah program linier dengan Metode Titik Ekstrim 1. Tentukan interseksi dari semua daerah feasible yang didefinisikan semua pembatasan sehingga diperoleh daerah feasible. 2. Tentukan titik ekstrim (sudut) dari daerah feasible. Setiap titik ekstrim merupakan titik interseksi dari dua pembatasan linier. 3. Tentukan nilai fungsi tujuan (Z) pada setiap titik ekstrim daerah
feasible. Solusi optimum terletak pada salah satu titik ekstrim daerah feasible 1.3. Contoh Soal : 1. Nilai
maksimum
fungsi
sasaran
Z 8x 6 y
dengan
syarat
4 x 2 y 60;2 x 4 y 48; x 0; y 0 adalah .... Penyelesaian : Fungsi tujuan → Z maks 8x 6 y a. Jadikan setiap kendala menjadi bentuk persamaan
4 x 2 y 60 → 2 x y 30
2 x 4 y 48 → x 2 y 24 b. Buat grafik untuk setiap kendala dan tentukan daerah penyelesaiannya (HP): Fungsi Kendala
2 x y 30 x 2 y 24
Titik potong terhadap sumbu
Titik potong terhadap sumbu
9
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA c. Dari grafik diatas garis I : 2 x y 30 dan garis II : x 2 y 24 . Dengan menggunakan metode titik ekstrim, setelah menentukan himpunan penyelesaian (HP) lalu tentukan titik-titik terluar/ titik ekstrim di dapat seperti tabel berikut :
( x, y)
Z 8x 6 y
(0, 12) (12, 6) (15, 0)
72 132 120
d. Ditentukan nilai maksimumnya adalah 132 pada titik (12, 6).
Dengan menggunakan Metode Isoline :
10
Handout Program Linier : Pendekatan Geometris 2. Nilai maksimum dari f ( x, y) 2 x 3 y pada himpunan penyelesaian sistem
pertidaksamaan: 3x 2 y 24 ; x 2 y 8 ; x, y 0 adalah ….. Penyelesaian : Fungsi tujuan : Zmaks 2 x 3 y a. Jadikan setiap kendala menjadi bentuk persamaan
3x 2 y 24 → 3x 2 y 24
x 2 y 8 → x 2 y 8 b. Buat grafik untuk setiap kendala dan tentukan daerah penyelesaiannya Fungsi Kendala
Titik potong terhadap sb
3x 2 y 24
x 2 y 8
Titik potong terhadap sb
....
....
....
....
c. Dari grafik diatas garis I : x 2 y 8 dan garis II : 3x 2 y 24 . Setelah menentukan himpunan penyelesaian (HP) lalu tentukan titik-titik terluar di dapat seperti tabel berikut :
11
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
( x, y)
Zmaks 2 x 3 y
(0, 4)
....
(4, 6)
....
(8, 0)
....
d. Ditentukan nilai maksimumnya adalah .... pada titik (....,....) 3. Nilai maksimum dari Z 20 x 8 untuk
,
, dan
dan
yang memenuhi
adalah ….
Penyelesaian : Fungsi tujuan : Z maks .... a. Jadikan setiap kendala menjadi bentuk persamaan → .... → .... b. Buat grafik untuk setiap kendala dan tentukan daerah penyelesaiannya
(HP)
12
,
Handout Program Linier : Pendekatan Geometris c. Dari grafik diatas setelah menentukan himpunan penyelesaian (HP) lalu tentukan titik-titik terluar Titik Potong
20x + 8
....
....
....
....
....
....
....
....
d. Jadi, nilai maksimumnya adalah ....
1.4. Soal Latihan Aktivitas 1
Petunjuk : Diskusikan dengan kelompokmu soal-soal dibawah ini, kemudian buat langkah-langkah penyelesaiannya!
Isilah kolom di bawah ini!
No.
Sistem pertidaksamaan
Grafik
x y 2 1.
2 x 3 y 12 x, y 0
13
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA No.
Sistem pertidaksamaan
x y 0 2.
3.
14
3x 5 y 15 x, y 0
Grafik
Handout Program Linier : Pendekatan Geometris
Aktivitas 2
Petunjuk : Kerjakan soal-soal berikut beserta langkah-langkah penyelesaiannya!
1. Nilai minimum dari -2x - 4y – 6 = 0 untuk x dan y yang memenuhi da adalah.... Jawaban
15
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA 2. Sebuah pabrik baku akan memproduksi buku jenis polos dan buku jenis bergaris. Dalam satu hari pabrik itu paling banyak memproduksi 1000 buku. Dari bagian penjualan diperoleh keterangan bahwa tiap hari terjual tidak lebih dari 800 buku polos dan 600 buku bergaris. Keuntungan tiap buku jenis polos adalah Rp.100,00 dan bergaris adalah Rp.150,00. Berapakah keuntungan bersih sebesar-besarnya yang dapat diperoleh tiap hari ? Berapa banyak buku polos dan bergaris yang harus diproduksi tiap hari ! Jawaban :
16
Handout Program Linier : Pendekatan Geometris 3. Luas daerah parkir 1.760 m2. Luas rata-rata untuk mobil kecil 4 m2 dan mobil besar 20 m2. Daya tampung maksimum hanya 200 kendaraan, biaya parkir mobil kecil Rp. 2000/jam dan mobil besar Rp. 3000/jam. Jika dalam satu jam terisi penuh dan tidak ada kendaraan yang pergi dan datang. Tentukan hasil pendapatan maksimum tempat parkir tersebut! Jawaban :
17
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA Dari diskusi yang telah kalian lakukan, tentukan langkahAktivitas 3
langkah dalam menyelesaikan sebuah masalah program linier dengan metode grafik!
.................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... .................................................................................................................................................................................... ....................................................................................................................................................................................
Tanggal
18
Nilai
Paraf Dosen
Handout Program Linier : Pendekatan Geometris
B. Metode Grafik dengan Tiga Variabel 2.1.
Soal Latihan
Aktivitas 1
No.
1.
Diskusikan dengan kelompokmu soal-soal berikut ini, kemudian buat langkah-langkah penyelesaiannya!
Sistem pertidaksamaan
Grafik
4 x 3 y 2 z 12 2 x 4 y 3z 12 x, y , z 0
2.
19
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
Kerjakan soal-soal berikut dan langkah-langkah penyelesaiannya!
Aktivitas 2
1. Nilai
maksimum
dari
penyelesaian sistem pertidaksamaan ; Jawaban :
20
, adalah ...
pada ;
himpunan
Handout Program Linier : Pendekatan Geometris 2. Nilai minimum dari
untuk x dan y yang memenuhi ;
;
;
adalah.... Jawaban :
21
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA 3. Suatu perusahaan manufaktur menghentika salah satu produk yang tidak menguntungkan. Penghentian ini menghasilkan kapasitas produksi yang menganggur (berlebih). Kelebihan kapasitas produksi ini oleh manajeman sedang dipertimbangkan untuk di alokasikan ke salah satu atau ke semua produk yang dihasilkan (produk 1, 2 dan 3). Kapasitas yang tersedia pada mesin yang mungkin akan membatasi output diringkas pada tabel berikut: Tipe Mesin
Mesin milling Lathe Grinder
Waktu yang dibutuhkan produk pada masing-masing mesin (jam) Produk 1 Produk 2 Produk 3 9 5 3
3 4 0
5 0 2
Waktu yang tersedia (jam per minggu) 500 350 150
Bagian penjualan mengidentifikasi bahwa penjualan potensial pada produk 1 dan 2 tidak akan melebihi laju produksi maksimum dan penjualan potensial untuk produk 3 adalah 20 unit per minggu. Keuntungan per unit masingmasing produk secara berturut-turut adalah $50, $20 dan $25. Formulasi masalah di atas ke dalam model matematik? Dan tentukan banyak produksi masing-masing produk agar keuntungan maksimal! Jawaban :
22
Handout Program Linier : Pendekatan Geometris
Aktivitas 3
Dari diskusi yang telah kalian lakukan, tentukan langkah- langkah dalam menyelesaikan sebuah masalah program linier dengan metode grafik 3 variabel!
..................................................................................................................................................................................... ..................................................................................................................................................................................... ..................................................................................................................................................................................... ..................................................................................................................................................................................... ..................................................................................................................................................................................... ..................................................................................................................................................................................... .....................................................................................................................................................................................
Tanggal
Nilai
Paraf Dosen
23
BAB III Analisis Simpleks A. Pengantar Simpleks Salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier adalah metode simpleks.
Penentuan solusi optimal
menggunakan metode simpleks didasarkan pada teknik eleminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim satu per satu dengan cara perhitungan iteratif. Sehingga penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap yang disebut dengan iterasi. Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1). Dapat disimpulkan juga bahwa metode simplek adalah Suatu metode yang secara sistematis di mulai dari suatu pemecahan dasar yang fleksibel ke pemecahan dasar yang fisibel lainnya dan ini di lakukan berulang- ulang (dengan jumlah ulangan yang terbatas) sehingga tercapai sesuatu pemecahan dasar yang optimum dan pada setiap step menghasilkan suatu nilai dari fungsi tujuan yang selalu lebih besar atau sama dari step- step sebelumnya. Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks, diantaranya : 1. Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya. 2. Variabel non basis adalah variabel yang nilainya diatur menjadi nol pada sembarang iterasi. Dalam terminologi umum, jumlah variabel non basis selalu sama dengan derajat bebas dalam sistem persamaan. 3. Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala merupakan pertidaksamaan ≤ ) atau variabel buatan (jika fungsi kendala menggunakan
pertidaksamaan ≥ atau =). Secara umum, jumlah
variabel basis selalu sama dengan jumlah fungsi pembatas (tanpa fungsi non negatif). 4. Solusi atau nilai kanan merupakan nilai sumber daya pembatas yang masih tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah sumber
Handout Program Linier : Analisis Simpleks daya pembatas awal yang ada, karena aktivitas belum dilaksanakan. 5. Variabel slack adalah variabel yang ditambahkan ke model matematik kendala untuk mengkonversikan pertidaksamaan ≤ menjadi persamaan (=). Penambahan variabel ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel slack akan berfungsi sebagai variabel basis. 6. Variabel surplus adalah variabel yang dikurangkan dari model matematik kendala untuk mengkonversikan pertidaksamaan ≥ menjadi persamaan (=). Penambahan ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel surplus tidak dapat berfungsi sebagai variabel basis. 7. Variabel buatan adalah variabel yang ditambahkan ke model matematik kendala dengan bentuk ≥ atau = untuk difungsikan sebagai variabel basis awal. Penambahan variabel ini terjadi pada tahap inisialisasi. Variabel ini harus bernilai 0 pada solusi optimal, karena kenyataannya variabel ini tidak ada. Variabel hanya ada di atas kertas. 8. Kolom pivot (kolom kerja) adalah kolom yang memuat variabel masuk. Koefisien pada kolom ini akn menjadi pembagi nilai kanan untuk menentukan baris pivot (baris kerja). 9. Baris pivot (baris kerja) adalah salah satu baris dari antara variabel basis yang memuat variabel keluar. 10. Elemen pivot (elemen kerja) adalah elemen yang terletak pada perpotongan kolom dan baris pivot. Elemen pivot akan menjadi dasar perhitungan untuk tabel simpleks berikutnya. 11. Variabel masuk adalah variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. Variabel masuk dipilih satu dari antara variabel non basis pada setiap iterasi. Variabel ini pada iterasi berikutnya akan bernilai positif. 12. Variabel keluar adalah variabel yang keluar dari variabel basis pada iterasi berikutnya dan digantikan oleh variabel masuk. Variabel keluar dipilih satu dari antara variabel basis pada setiap iiterasi. Variabel ini pada iterasi berikutnya akan bernilai nol.
25
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
B. Metode Pemecahan Dasar (Basis) atau Simplek 1 2.1. Langkah-langkah : 1. Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum, dirubah
menjadi persamaan (=) dengan menambahkan satu variabel slack (yaitu u, v, dan w) 2. Menentukan variabel basis dan variabel non basis. Menentuka keterangan
Layak/ Tidak Layak dan menentukan nilai Z untuk variabel yang Layak, dimana : Layak (L) karena memenuhi syarat nilai variabel non-negatif Tidak Layak (TL) karena ada variabel yang bernilai negatif. 3. Nilai Z bernilai Layak merupakan daerah penyelesaian, menentukan nilai Z
sesuai dengan yang di tuju (nilai maksimum atau minimum) 2.2. Contoh Soal 1. Nilai maksimum dari ( , )
pada himpunan penyelesaian system
pertidaksamaan ....
≤ ≤ ≤ ( , , , , )
1.
,
,
2.
,
3.
,
,
5.
,
,
,
,
,
6.
,
,
,
,
,
7.
,
,
,
,
,
,
,
4.
,
8.
,
,
,
,
, ,
26
9.
,
10.
,
,
, ,
,
, ,
, ,
,
Handout Program Linier : Analisis Simpleks
No
Variabel
1
,
2 3
, ,
4
Variabel non Basis
,
TL
,
TL
, ,
Ket
Titik
TL ,
TL
5
,
,
L
(
, )
6
,
,
L
(
, )
7
,
,
L
( , )
,
L
(
8
,
9
,
10
, ,
.... .... ....
, )
....
TL ,
( , )
L
....
Jadi dari data table diatas maka nilai maksimumnya adalah 60 pada titik (10,0) 2. Untuk (x,y) yang memenuhi
nilai maksimum untuk ( , )
,
,
≤
, maka
adalah . . .
Jawab:
( , , , , )
27
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA No
Variabel Basis
Variabel Non Basis
Ket
Titik
1 2 3 4 5 6 7 8 9 10 Jadi dari data diatas nilai maksimumnya adalah .... pada titik ( .......................)
Dari dua contoh soal di atas, bagaimana cara menentukan banyaknya penyelesaian dasar ?
................................................................................................................................................................................
C. Simpleks dengan Tabel Berkolom Variabel Dasar (VD) 3.1. Langkah- langkah mengerjakan : 1. Rumuskan dan standarisasi modelnya Optimumkan :
z c1 x1 c2 x2 ... cn xn 0 Terhadap :
a11 x1 a12 x2 ... a1n xn s1 b1 .. a m1 x1 a m2 x2 ... a mn xn sn bn
28
Handout Program Linier : Analisis Simpleks 2. Bentuk table awal VD VD
Z
x1
x2
…
xn
S1
S2
…
Sn
NK
Z
1
c1
c2
…
cn
0
0
…
0
0
s1
0
a 11
a 12
…
a1n
0
1
…
0
b1
s2 …
0 … 0
a 21 … a m1
a 22 … a m2
… … …
a 2n … a mn
1 … 0
0 … 0
… … …
0 … 1
b2 … bn
sm
3. Tentukan “variable pendatang” (entering variable) yaitu kolom kunci 4. Menentukan “variable perantau” (leaving variable) yaitu baris kunci 5. Memasukkan variable pendatang ke kolom VD Transformasi baris kunci : Baris kunci baru =
Transformasi baris-baris yang lain : Baris baru = baris lama – (baris pada kolom kunci x baris kunci baru) 6. Pengujian optimalisasi Jika semua baris dasar baris-Z sudah tidak ada lagi yang negatif→max Jika semua baris dasar baris-Z sudah tidak ada lagi yang positif→min Berarti sudah cukup (SELESAI) 3.2. Contoh Soal: 1. Maksimum Pembatas: ≤ ≤ , Penyelesaian : Optimumkan :
29
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA Kendala :
Tabel Awal VD Z
Z 1 0 0
-3 1 3
-5 2 1
0 1 0
0 0 1
NK 0 10 10
r 5 10
NK
r
Tabel 1 VD
Z
Z
1
0
0
25
-
0
1
0
5
10
0
0
1
5
2
Tabel 2 VD
Z
NK
Z
1
0
26
0
1
4
0
0
2
Pada baris Z sudah tidak ada nilai negatif (kasus maksimum) maka iterasi selesai. Didapat : sumber daya habis terpakai. 2. Maksimum Pembatas: ≤ ≤ ≤
30
untuk nilai
dan
dimana semua
Handout Program Linier : Analisis Simpleks , Penyelesaian: Optimumkan: Kendala :
Tabel Awal VD
Z
NK
r
Z
Tabel 1 VD
Z
NK
Z
31
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
D. Membaca Tabel Optimal Membaca tabel optimal adalah bagian penting bagi pengambil keputusan. Ada beberapa hal yang bisa dibaca dari table optimal : 1. Solusi optimal variable keputusan 2. Status sumber daya 3. harga bayangan (shadow prices). Menggunakan table optimal : VD Z s1 x2 x1
x1 0 0 0 1
x2 0 0 1 0
x3 4 4/3 8/3 -2
s1 0 1 0 0
s2 5/3 -1/9 7/9 -2/3
s3 2/3 -1/9 -2/9 1/3
NK 31/3 7/9 5/9 2/3
1. Solusi optimal
,
,
dan
, artinya untuk mendapatkan
keuntungan maksimum sebesar $ menghasilkan produk 1 sebesar
, maka perusahaan sebaiknya
unit dan produk 2 sebesar unit.
2. Status sumber daya :
Sumber daya pertama dilihat dari keberadaan variable basis awal dari setiap fungsi kendala pada table optimal. Dalam kasus di atas, untuk fungsi kendala pertama periksa keberadaan S 1 pada variable basis table optimal. Periksa keberadaan S2 pada variable basis table optimal untuk fungsi kendala kedua. Periksa keberadaan S 3 pada variable basis table optimal untuk fungsi kendala ketiga. S1 = . Sumber daya ini disebut berlebih (abundant) S2 = S3 = 0. Kedua sumber daya ini disebut habis terpakai (scarce). 3. Harga bayangan :
Harga bayangan dilihat dari koefisien variable slack atau surplus pada baris fungsi tujuan. Koefisien S1 pada baris fungsi tujuan table optimal = 0, dengan demikian harga bayangan sumber daya pertama adalah 0 32
Handout Program Linier : Analisis Simpleks Koefisien S2 pada baris fungsi tujuan table optimal = , dengan demikian harga bayangan sumber daya kedua adalah Koefisien S3 pada baris fungsi tujuan table optimal = , dengan demikian harga bayangan sumber daya kedua adalah .
E. Soal Latihan Tentukan solusi setiap masalah berikut dengan Aktivitas 1
menggunakan metode simpleks, serta berikan kesimpulannya!
1. Suatu perusahaan menghasilkan dua produk, meja dan kursi yang diproses melalui dua bagian fungsi: perakitan dan pemolesan. Pada bagian perakitan tersedia 60 jam kerja sedangkan pada bagian pemolesan hanya 48 jam kerja. Untuk menghasilkan 1 meja diperlukan 4 jam kerja perakitan dan 2 jam kerja pemolesan, sedangkan untuk menghasilkan 1 kursi diperlukan 2 jam kerja perakitan dan 4 jam kerja pemolesan. Laba untuk setiap meja dan kursi yang dihasilkan masing-masing Rp. 80.000 dan Rp.60.000;. berapa jumlah meja dan kursi yang optimal dihasilkan? Jawaban :
33
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA 2. Pesawat penumpang mempunyai tempat duduk 48 kursi setiap penumpang kelas utama boleh membawa bagasi 60 kg, sedangkan kelas ekonomi 20 kg. Pesawat hanya dapat membawa bagasi 1.440 kg, harga tiket kelas utama Rp. 1.500.000 dan kelas ekonomi Rp.1.000.0000, supaya mendapat penjualan tiket pada saat pesawat penuh mencapai maksimum, maka jumlah masing-masing kelas adalah.... Jawaban :
34
Handout Program Linier : Analisis Simpleks
Aktivitas 2
Buatlah simpulan dari pembelajaran yang telah di lakukan?
........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................ ........................................................................................................................................................................................
Tanggal
Nilai
Paraf Dosen
35
BAB IV Metode Simpleks I
A. Metode M Charnes 1.1. Pendahuluan Untuk kasus di mana fungsi kendala ada tanda lebih dari atau lebih dari sama dengan (
t u
maka perlu menambahkan variabel pengurang (surplus)dan
variabel penambah (variabel slack) yang non-negatif. Akan menjadi sebuah persoalan bagaimana variabel slack tersebut dapat digunakan untuk membantu mencari penyelesaian masalah program linier. Salah satu caranya, dipaparkan oleh Charnes dengan menggunakan metode simpleks agar variabel slack menjadi nol, dengan menentukan nilai konstanta (-M) jika masalah yang dihadapi adalah memaksimumkan fungsi tujuan, dan menentukan nilai konstanta (M) pada variabel slack jika masalah yang dihadapi meminimumkan.
1.2. Contoh Soal Minimumkan : Kendala :
Penyelesaian : Masalah PL menjadi : dengan kendala,
Menggunakan prosedur memaksimalkan : Sehingga fungsi objektif menjadi :
d maks
Handout Program Linier : Metode Simpleks 1 Tabel Awal: Cj VB C D
-3 x 1 2 3 -3
-M -M
Zj-Cj
-2 y 1 1 2 -2
0 a -1 0 0 1
0 B 0 -1 0 1
-M c 1 0 0 0
-M D 0 1 0 0
HB
Rasio
2 3 0 -5
2 1,5
1 2
B2
Keterangan : Baris Zj-Cj baris pertama tidak mengandung unsur M sedangkan baris Zj-Cj baris kedua mengandung unsur M. Variabel masuk (variabel pendatang) = x, variabel keluar (variabel perantau) = d Tabel 2 Cj
-3 x
VB
-2 Y
0 a
0 b
-M c
-M D
HB
r
C
-M
0
-1
1
1
X
-3
1
0
0
3
0
0
0
0
1
0
Zj-Cj
Tabel 3 Cj Variabel Basis Y X Zj-Cj
-2 -3
-3
-2
0
0
-M
-M
X
Y
a
B
C
D
0 1 0 0
1 0
-2 1 1 0
1 -1 1
2 -1 -1 1
-1 1 -1 1
HB 1 1 -5 0
Dari baris Zj-Cj yang kedua sudah tidak ada yang negatif maka iterasi selesai. sehingga dapat di simpulkan :
37
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
B. Metode Simpleks Fase 1 2.1. Langkah- langkah 1.
Menambahkan variabel pada pertidaksamaan yang telah diketahui, jika pertid ks m n tersebut tel h memenuhi sy r t simpleks y itu
≤
ber rti
pertidaksamaan tersebut ditambahkan satu variabel(variabel slack), jika pertid ks m n tersebut tid k memenuhi sy r t simpleks t u
berarti
dikurangi variabel surplus dan ditambah variabel slack. 2.
Fungsi Z ditambahkan variabel dari persamaan yang tidak memenuhi syarat tersebut dengan simbol M yang berarti M = 106
3.
Persamaan tersebut disusun fungsi Z diletakkan paling atas, lalu dari fungsi Z yang koefisiennya adalah M maka hasilnya harus nol.
4.
Setelah dikalikan dan ditambahkan dengan fungsi Z, maka dicari nilai yang paling kecil dari hasilnya.
5.
Lalu dicari kunci dari peersamaan yang diketahui dengan cara membagi gasil dengan persamaan dengan angka yang telah diberi tanda pada gasil yang paling kecil tersebut.
6.
Dari kunci tersebut dibuat menjadi 1(satu) dan angka yang berada satu kolom dengan angka 1(satu tersebut dijadikan nol.
7.
Lalukan hal tersebut berulang-ulang hingga tidak ada yang bernilai negatif pada hasil yang berada paling bawah kecuali nilai Z.
2.2. Contoh Soal : Minimumkan
Z = 3x + 2y
Kendala : x
y ≤6
2x + 5y x y Penyelesaian Fungsi Objektif : Z
38
x
y→
:
Handout Program Linier : Metode Simpleks 1 dengan fungsi kendala menjadi, ≤6→
6 →
Tabel Awal Cj VB a C
CB 0 -M
Zj-Cj
Cj VB A
CB 0
Y
-2 Zj-Cj
-3 x 1 2 -3 -2M
-2 Y 1 5 -2 -5M
0 a 1 0 0 0
0 B 0 -1 0 M
-M c 0 1 0 0
-3 x 1
-2 Y 1
0 a 1
0 b 0
-M c 0
1
0
-3 -2M
-2 -5M
0 0
0 M
0 0
-5 -7M
-3 x
-2 Y
0 a
0 b
-M c
HB
HB 6 10 -5 -7M
r 1 𝐵 5 2
6 2
HB 6
𝐵1 −𝐵2
2
Tabel 1 Cj VB
CB
A
0
0
1
4
Y
-2
1
0
2
0
0
0
0
Zj-Cj
-
0
M
0
Karena pada baris objektif (B3) sudah tidak ada yang negatif maka iterasi selesai. Dari perhitungan di atas dapat diambil kesimpulan :
39
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
C. Soal Latihan Kerjakan soal berikut dengan menggunakan metode M Charnes atau simpleks 1 fase!
Aktivitas 1
1. Minimumkan : Kendala : 1
2 ≤
1 1
2 ≤ 2
40
6
1
2
4. Minimumkan : Kendala : 1
2
1 1
3. Minimumkan : Kendala :
2
6
2
1
2. Minimumkan : Kendala : 1
1
1 2
2
1
1 2 2
2
2
Handout Program Linier : Metode Simpleks 1
41
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
42
Handout Program Linier : Metode Simpleks 1
Aktivitas 2
Buatlah simpulan dari pembelajaran yang telah di lakukan?
........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ...........................................................................................................................................................................
Tanggal
Nilai
Paraf Dosen
43
BAB V Metode Simpleks II A. Langkah- langkah Metode Simpleks 2 Fase 1. Sistem pertidaksamaan 1 & seterusnya dibuat sama seperti simpleks dengan 1 fase. 2. Nilai Z di minimumkan ( dikalikan denagan - ) . 3. Z pindah ruas menjadi bernilai + . 4. Selanjutnya sama seperti pada simpleks dengan 1 fase . namun pembedanya adalah yg mempunyai nilai hanya fariabel M dan Z . Variabel yang mengandung nilai M bernilai = -1 dan Z = 1 selebihnya bernilai 0 . 5. Cari nilai pada sistem pertidaksamaan yg membentuk identitas dan pada posisi 1 di sebelah kiri (pengali ) di letakkan nilai x . lalu setelah 2 fariabel dikali & di jumlahkan, dikurang nilai x di atasnya . 6. Selanjutnya sama seperti pada simpleks 2 dengan 1 fase hingga berakhir pada nilai baris terakhir yang bernilai positif . 7. Hilangkan kolom yang mengandung nilai M pada Z lalu letakkan nilai keseluruhan Z pada atas baris ( nilai x ). 8. Lalu seperrti cara pada no 5 hingga nilai baris terakhir bernilai positif . 9. Dan itulah nilai Z (jangan lupa nilai Z dalah –Z).
B. Contoh Soal : Minimumkan : Kendala :
Penyelesaian : 3
4
5
6 4
6
Handout Program Linier : Metode Simpleks 2 Tabel Awal Fase 1 Cj VB -1 -1 Zi-Cj
Cj VB -1
0 x 4 2 -6
0 y 2 4 -6
0
-1
0
-1
-1 0 1
1 0 0
0 -1 1
0 1 0
0 x 4
0 y 2
0
-1
0
-1
-1
1
0
0
1
0
0
-6
-6
1
0
1
0
0 x
0 Y
0
-1
0
-1
3
0
-1
1
0 Zj-Cj
HB
r
60 48 -108
30 12
1
→4 𝐵2
HB 60 12 -108
B1-2B2 B3+6B2
Tabel 2 Cj VB -1
HB
R
36
12 1
0
1
0
12 -36
Zj-Cj
-3
0
1
0
Cj
0 x
0 y
0
-1
1
0
VB x
0 0
Zj-Cj
-1
24
HB 12
1 -3
0
→3 𝐵1
0
12 -36
0
1
0
0 x
0 y
0
-1
0
1
0
12
0
0
1
6
0
0
1
B2-2 𝐵1 B3+3𝐵1
Tabel Akhir Fase 1 Cj VB
Zj-Cj
0
1
0
0
-1
1
HB
0 45
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA Tabel Awal Fase 2 8 x 1 0 0
Cj VB 8 6 Zj-Cj
6 y 0 1 0
HB 12 6 132
Karena sudah tidak ada yang negatif pada baris objektif maka iterasi selesai. Dapat di simpulkan :
3
4
5
6
(nilai minimum).
C. Soal Latihan : Tentukan solusi setiap masalah berikut dengan Aktivitas 1
menggunakan metode simpleks, serta berikan kesimpulannya!
1. Sebuah peusahaan industri mempunyai, berturut-turut 240kg, 360kg, dan 180kg bahan yaitu kayu, plastik dan baja. Perusahaan itu akan membuat dua macam produk yaitu P dan Q yang berturut-turut memerlukan bahan-bahan (dalam kg) seperti data berikut: Produk P Q
Kayu 1 3
Bahan yang diperlukan Plastik 3 4
Baja 2 1
Keuntungan produk P ialah Rp. 40.0000 dan tiap produk Q ialah Rp. 60.000 a. Rumuskan persoalan perusahaan ini dalam model matematika suatu program linier? b. Gunakan analisis simpleks untuk memperoleh nilai maksimum fungsi
tujuan? Jawaban
46
Handout Program Linier : Metode Simpleks 2
Jawaban
47
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
zmin 2 x1 3x2 2.
pembatas : 2 x1 x2 16; x1 3x2 20; x1 x2 10; x1 , x2 0 Jawaban :
48
Handout Program Linier : Metode Simpleks 2
zmaks 2 x 3 y 5 z 3.
pembatas : x y z 7; 2 x 5 y z 10; x, y, z 0 Jawaban :
49
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
4. Sebuah lembaga penelitian harus mengirimkan 10.000 kuisioner (daftar pernyataan) kepada sasaran responden-respondennya di pulau Jawa, Sumatera, dan Sulawesi. Biaya kirim seberkas kuisioner ke tiap responden adalah Rp. 80 (Jawa), Rp. 100 (Sumatera) dan Rp.110 (Sulawesi). Lembaga tersebut menetapkan tidak lebih dari 3.000 kuisioner yang akan dikirim ke responden di pulau Jawa, serta setidak-tidaknya 1500 dan 200 kuisioner harus dikirimkan masing-masing responden di pulau Sumatera dan Selawesi. Berapa berkas kuisioner harus dikirimkan ke masing-masing pulau agar biaya kirim totalnya minimum? Jawaban :
50
Handout Program Linier : Metode Simpleks 2
51
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
Aktivitas 2
Buatlah simpulan dari pembelajaran yang telah di lakukan?
................................................................................................................................................................................................... ................................................................................................................................................................................................... ..................................................................................................................................................................................................... ................................................................................................................................................................................................. ................................................................................................................................................................................................... ................................................................................................................................................................................................... ................................................................................................................................................................................................... ...................................................................................................................................................................................................
Tanggal
52
Nilai
Paraf Dosen
BAB VI Dual, Primal dan Kemerosotan
A. Primal dan Dual 1.1. Pendahuluan Biasanya, setelah solusi optimal dari masalah program linier ditemukan maka peneliti cenderung untuk berhenti menganalisis model yang telah dibuat. Padahal sesungguhnya dengan menganalisis lebih jauh atas solusi optimal akan dapat menghasilkan informasi lain yang berguna. Analisis yang dilakukan terhadap solusi optimal untuk mendapatkan informasi tambahan yang berguna tersebut dikenal dengan analisis post-optimal. Analisis ini dapat dilakukan dengan dua cara, yaitu Analisis Dualitas dan Analisis Sensitivitas. Analisis dualitas dilakukan dengan merumuskan dan menginterpretasikan bentuk dual dari model. Bentuk dual adalah suatu bentuk alternatif dari model program linier yang telah dibuat dan berisi informasi mengenai nilai-nilai sumber biasanya membentuk sebagai batasan model. Setiap masalah prolin yang bertujuan mencari nilai maksimum selalu bertalian dengan suatu masalah prolin dengan tujuan mencari nilai minimum, yang disebut dual masalah yang pertama. Sebaliknya setiap masalah prolin yang berrtujuan mencari nilai minimum selalu bertalian dengan suatu masalah program linier yang bertujuan mencari nilai maksimum yang disebut dual. Masalah pertama disebut primal sedangkan masalah kedua dengan tujuan berlawanan disebut dual.
Maks
Min
DUAL
DUAL
Min
Maks
Kegunaan analisis dualitas bagi pengambilan keputusan adalah :
Model primal akan menghasilkan solusi dalam bentuk jumlah laba yang diperoleh dari memproduksi barang atau biaya yang dibutuhkan untuk memproduksi barang.
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
Model dual akan menghasilkan informasi mengenai nilai (harga) dari sumber-sumber yang membatasi tercapainya laba tersebut.
Solusi pada model dual memberikan informasi tentang sumber-sumber yang digunakan untuk menentukan apakah perlu menambah sumbersumber daya, serta berapa biaya yang harus dikeluarkan untuk tambahan tersebut. Hubungan khusus antara primal dan dual adalah : 1. Variabel dual Y1 , Y2 , Y3 berhubungan dengan batasan model primal. Dimana untuk setia batasan dalam primal terdapat satu variabel dual. Misal, dalam kasus di atas model primal mempunyai 3 batasan, maka dualnya akan mempunyai 3 variabel keputusan. 2. Nilai kuantitas pada sisi kanan pertidaksamaan pada model primal merupakan koefisien fungsi tujuan dual. 3. Koefisien batasan model primal merupakan koefisien variabel keputusan dual. 4. Koefisien fungsi tujuan primal, merupakan nilai kuantitas pada sisi kanan pertidaksamaan pada model dual. 5. Pada bentuk standar, model maksimisasi primal memiliki batasanbatasan .
54
Handout Program Linier : Dual, Primal dan Kemerosotan
1.2. Contoh Kasus : Maksimum : Kendala :
Primal
Maka dualnya menjadi : Minimumkan : Kendala : Dual
Agar lebih mudah dapat dibuat matriks sebagai berikut : Matriks Koefisien dari masalah primal yaitu [
Matriks koefisien dari masalah dual yaitu [
]
]
Contoh Soal : Selesaikan dengan cara primal/dual Minimumkan :
5
Kendala :
Penyelesaian : Primal Minimumkan :
5
Kendala :
Matriks koefisien primal : [
5
]
55
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
5
Dual, matriks koefisien dualnya : [
]
Masalah dualnya dapat ditulis sbb : Maksimumkan : Kendala :
PL menjadi :
Tabel Awal VD
56
VD Z a
Z 1 0
u -40 2
v -50 3
a 0 1
b 0 0
b
0
4
2
0
1
VD Z
Z 1
u -40
v -50
a 0
b 0
NK 0
v
0
0
1
b
0
1 4
2
0
1
NB 0 3
𝐵
B1+50B2 B3-2B2
Handout Program Linier : Dual, Primal dan Kemerosotan Tabel 2 VD
Z
Z
1
v
u
v
b
S
0
0
50
0
1
0
1
B
0
0
1
VD
Z
Z
1
V U
u
a
v
a
𝐵
b
S
0
0
50
0
1
0
1
0
0
𝐵
𝐵
B2-3 𝐵
Tabel Akhir VD
Z
u
v
a
b
Z
1
0
0
v
0
1
0
u
0
0
S
Karena dari baris objektif (B1) sudah tidak ada yang negatif maka iterasi selesai. Dari perhitungan di atas di dapat bahwa
⁄ .
57
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA Untuk memastikan kebenaran ini, akan dihitung juga masalah primalnya yaitu : 5
Minimumkan : Kendala :
Penyelesaian :
Tabel Awal Simpleks Cj
0
Variabel
x
Basis
0
-1
-1
a
b
c
d
Harga Basis
Rasio 1 4
c
-1
2
4
-1
0
1
0
40
10
d
-1
3
2
0
-1
0
1
50
25
Zj-Cj
-5
-6
1
1
0
0
-90
Cj
0
Variabel
x
Basis y
-1
d
-1 Zj-Cj
58
y
0
y
0
0
-1
-1
a
b
c
d
Basis
0
10
1
0
Harga
3
2
0
-1
0
1
50
-5
-6
1
1
0
0
-90
B2-2B1 B3+6B1
B1
Handout Program Linier : Dual, Primal dan Kemerosotan Tabel 1 Cj
0
Variabel
x
Basis y
0
d
-1
Y
0
0
-1
-1
a
b
c
d
Basis
Harga
r
1
0
0
10
20
2
0
-1
1
30
15
Zj-Cj
-2
0
1
0
-30
Cj
0
Variabel
x
Basis
y
y
0
1
x
0
0
Zj-Cj
0
0
0
-1
-1
a
b
c
d
0
Harga Basis
0
5 1
15
0
0
𝐵
1
B1- B2 B3+2B2
0
Iterasi selesai karena baris objektif (Zj-Cj) sudah tidak ada yang negatif. Dari data di atas di dapat :
(
fungsi objektif untuk primal :
)
(
)
( )
Dari penyelesaian di atas mempunyai hasil yang sama :
5 4
59
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
B. Kemerosotan (degeneracy) 2.1. Pengertian Kemerosotan Metode simpleks didasarkan pada beberapa aturan yang di proses dari sebuah program awal yang memenuhi syarat, yang diperbaiki dan diperbaiki kembali sehingga tercapai suatu penyelesaian optimal. Pemilihan terhadap kolom kunci/ pivot ialah tugas simpleks, karena harus mengenai kolom yang memiliki nilai positif terbesar (kasus maks) atau nilai negatif terbasar (kasus min) dalam baris penilaian/ objektif dari tabel simpleks. Tetapi dalam memilih baris kunci dengan tujuan mengganti salah satu vektor basis, akan dihadapkan pada 2 kesulitan : 1. Tabel program simpleks awal dapat sedemikian sehingga satu/ lebih variabel dalam kolom kuantitas bernilai nol. Jika terjadi, maka nilai hasil pembagian yang menentukan minimum penggantian ialah nol. Maka proses penggantian tidak dapat dilaksanakan karena variabel yang harus diganti sudah bernilai nol. 2. Nilai hasil pembagian yang tidak negatif yang menentukan baris kunci mungkin sama untuk dua atau lebih variabel yang sedang dalam basis. Jika ini terjadi maka akan terjalin ada keterikatan dalam pemilihan terhadap beris kunci. Penghapusan terhadap salah satu variabel yang terikat akan menakibatkan variabel terikat lain akan susut menjadi nol. Ini berakibat satu/ lebih vektor basis akan memiliki nilai nol. Kedua peristiwa tersebut, menimbulkan gejala yang di kenal sebagai kemerosotan. Usaha terhadap penyelesaian PL yang mengalami kemerosotan dapat mengakibatkan salah satu peristiwa berikut : 1. Setelah berkali-kali iterasi akan diperoleh penyelesaian optimal, atau 2. Masalah
akan
menjadi
siklus
sehingga
menghalangi
tercapainya
penyelesaian optima Penyebab kemerosotan adalah jika pada kolom kuantitas terdapat nilai nol, dan jika hasil pembagian yang tidak negatif yang menentukan baris kunci sama untuk dua variabel atau lebih.
kemerosotan
60
Pemilihan variabel secara sembarangan
Siklus
Handout Program Linier : Dual, Primal dan Kemerosotan 2.2. Contoh Kasus Kemerosotan : Maksimumkan : Kendala :
Tahukan Anda mengapa masalah di atas di sebut kemerosotan? Penanggulangan kemerosotan (Charnes dan Cooper) : 1. Tentukan semua variabel terikat/ baris variabel itu. 2. Untuk setiap kolom dalam identitas (dimulai dari kolom paling kiri dalam identitas dengan
memproses satu
demi
satu
kekanan), hitunglah
perbandingan dengan membagi angka setiap baris terikat dengan bilangan kolom kunci yang ada di dalam baris tersebut. 3. Bandingkan hasil bagi ini, kolom demi kolom, di proses ke kanan. Untuk pertama kali perbandingan tidak sama, ikatan sudah putus. 4. Diantara baris yang terikat, baris dengan perbandingan aljabar lebih kecil di tunjuk sebagai baris kunci 5. Jika nilai perbandingan dalam identitas tidak mematahkan ikatan, bentuklah perbandingan untuk kolom-kolom dari ‘badan utama’ dan pilihlah baris kunci seperti yang di jelaskan pada langkah 3 dan 4.
C. Soal Latihan Aktivitas 1
Selesaikan setiap permasalahan berikut:
1. Seseorang memerlukan 10, 12 dan 12 unit bahan kimia A, B, dan C berturutturut untuk halamannya. Pupuk berupa cairan mengandung 5, 2, dan 1 unit dari A, B, dan C berturut-turut perbotolnya, dan pupuk berupa serbuk mengandung 1, 2 dan 4 unit A, B dan C berturut-turut perkotak karton. Harga 61
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA pupuk cair Rp. 30.000 per botol dan serbuk Rp. 20.000 per kotak. Beberapa pupuk dari masing-masing harus di beli agar biaya serendah mungkin tetapi masih memenuhi persyaratan?(Kerjakan dengan Dual) Jawaban :
62
Handout Program Linier : Dual, Primal dan Kemerosotan 2. Sebuah perusahaan mebel membuat lemari, meja dan kursi. Setiap produk mebel tersebut dibutuhkan bahan/ pekerjaan yaitu kayu, finishing, dan pengecatan. Informasi dalam pembuatan mebel tersebut sebagai berikut : Bahan/ Pekerjaan Kayu Finishing Pengecatan Harga Jual (Ribuan Rp)
Lemari
Meja
Kursi
Ketersediaan waktu
4 jam 2 jam 600
2 jam 1,5 jam 300
1,5 jam 0,5 jam 200
20 jam 8 jam
Formulasikan persolaan utama (primal problem) dan persoalan rangkap (dual problem) dari pemprograman linier tersebut di atas. Jawaban :
63
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA 3. Formulasikan persolaan utama (primal problem) dan persoalan rangkap (dual problem) pemprograman linier berikut dan cari solusi optimumnya. Minimumkan : Fungsi kendala :
Jawaban:
64
Handout Program Linier : Dual, Primal dan Kemerosotan
65
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
Aktivitas 2
Berikan kesimpulan dari pembelajaran yang telah dilakukan!
........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ...........................................................................................................................................................................
Tanggal
66
Nilai
Paraf Dosen
BAB VII Model Transportasi
A. Pendahuluan Model transportasi merupakan kasus khusus dari persoalan program linier dengan tujuan untuk ‘Mengangkut’ barang tunnggal dari berbagai asal ( origin) ke berbagai tempat tujuan (destination), dengan biaya angkut serendah mungkin. Model transportasi ialah suatu kasus khusus PL sehingga dapat di selesaikan dengan metode simpleks. Tetapi ‘algoritma’ yang digunakan lebih efisien untuk menengani masalah transportasi= algoritma transportasi. Ciri khasnya ialah bahwa koefisiennya dari variabel struktur yaitu
terbatas pada nilai-nilai 0 atau 1.
Telah dijelaskan bahwa model transportasi merupakan suatu kasus khusus dalam masalah program linear, namun dapat susut menjadi masalah transportasi jika : (1) koefisien dari variabel struktural , yaitu amn terbatas pada nilai-nilai 0 atau 1. (2) terdapat adanya kehomogenan antara unit-unit dalam persyaratan. Ada 2 macam -
Transportasi standar (Single Delivery System) O1
D1
O2
D2
Masalah transportasi di mana origin hanya berfungsi sebagai daerah asal dan destination hanya berfungsi sebagai daerah tujuan. -
Transshipment / Multi Delivery System Masalah transportasi dimana origin maupun destination berfungsi sebagai daerah asal dan tujuan. O1
D2
O2
D2
Alokasi produk ini harus diatur sedemikian rupa, karena terdapat perbedaan biaya-biaya alokasi dari satu sumber ke tempat-tempat tujuan yang berbeda-beda, dan dari beberapa sumber ke suatu tempat tujuan juga berbeda-beda. Tujuan penyelesaian masalah trransportasi adalah menentukan jalur pengangkutan barang-
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
barang yang berkaitan dengan biaya pengangkutan termurah dan tetap memenuhi persyaratan. Langkah kedua bertujuan untuk menentukan ‘opportunity cost’ setiap sel kosong. Jika ‘opportunity cost’ setiap sel kosong tidak positif maka kemungkinan optimal telah di peroleh
dan
dan toko sebagai pelanggan ditandai dengan
. Data relevan.
B. Formulasi Model Matematika Model transportasi memiliki ciri-ciri khas seperti yang dimiliki oleh program linear, yaitu : 1. Fungsi obyektif yang linear ( )
∑
2. Struktur persyaratan yang linear Setiap masalah program linear memiliki sekumpulan persyaratan linear. ∑ Dimana : dengan
∑
dan
merupakan koefisien struktural yang mencerminkan spesifikasi teknik
dari masalah yang dibahas, dan ditampil sebagai koefisien dari variabel struktural dalam persyaratan-persyaratan struktural. Sedangkan
adalah
konstanta yang menggambarkan kapasitas maksimum atau minimum dari fasilitas-fasilitas yang ada maupun sumber-sumber yang tersedia. Bentuk persyaratan struktural yang linear dituliskan secara lengkap sebagai berikut :
68
Handout Program Linier : Model Transportasi
3. Persyaratan tidak negatif Variabel struktural, variabel slack, variabel slack buatan dari masalah program linear terbatas pada nilai-nilai tidak negatif, ditulis :
Tabel Model Transportasi
DESTINATION
ORIGIN D1
D2
D3
Dn
Kapasitas Origin Per Priode (Waktu)
Permintaan tujuan per priode (waktu)
Keterangan :
(asal) (tujuan) biaya pengangkutan unit barang dari asal m ke tujuan n banyak unit barang yang dapat diangkut dari daerah asal m ke tujuan n banyak unit barang yang diangkut dari daerah asal m ke tujuan n kapasitas per priode aktu
Jika m adalah jumlah baris dan n adalah jumlah kolom dalam suatu masalah transportasi, kita dapat menyatakan masalah secara lengkap dengan m+n-1 persamaan. Ini berarti bahwa suatu penyelesaian dasar yang memenuhi persyaratan dari suatu masalah transportasi hanya memiliki m+n-1 komponenkomponen positif.
69
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
C. Pendekatan Model Transportasi Model transportasi terdiri atas 3 langkah dasar : 1.
Melibatkan penentuan
pengiriman awal, sedemikian rupa sehingga
diperoleh solusi dasar yang memenuhi syarat. Ini berarti bahwa m+n-1 sel atau
rute
dari
matriks
transformasi
digunakan
untuk
tujuan
pengangkutan. Sel yang digunakan untuk pengangkutan disebut sel yang ditempati, sedang sel lainnya dari matriks transportasi akan disebut sel kosong. 2.
Bertujuan
menentukan
biaya
kesempatan
(opportunity
cost)
yang
berkaitan dengan sel kosong. Biaya kesempatan dari sel kosong dapat dihitung untuk setiap sel kosong tersendiri, atau dihitung untuk semua sel kosong secara keseluruhan. Jika biaya kesempatan dari semua sel kosong tidak positif, maka telah diperoleh solusi optimal. Di lain pihak, jika terdapat hanya satu sel saja memiliki biaya kesempatan bernilai positif, solusi pasti belum optimal dan kita harus melangkah ketiga. 3.
Melibatkan penentuan solusi dasar yang memenuhi syarat, baru dan lebih baik. Sekali solusi dasar yang baru dan memenuhi syarat telah dicapai, kita ulangi langkah 2 dan langkah 3 sampai suatu solusi optimal telah ditentukan. Sebelum masuk ke dalam penyelesaian model transportasi, sesuai langkah pertama harus ditentukan dahulu solusi awalnya. Ada beberapa cara menentukan solusi awal, yaitu
1. Metode Pojok Barat-Laut 2. Metode Inspeksi 3. Metode Batu Loncatan 4. Metode Modified Distribution (MODI) 5. Metode Vogel Approximation (VAM)
70
Handout Program Linier : Model Transportasi
Lebih jelas mengenai beberapa metode di atas akan di jabarkan sebagai berikut : 2.1. Metode Pojok Barat Laut Metode ini dikenal juga dengan nama North West Corner Method. Metode ini ditemukan oleh Charnes dan Cooper, dan kemudian dikembangkan oleh Danzig. Sesuai nama aturan ini, maka penempatan pertama dilakukan di sel paling kiri dan paling atas dari matriks, yaitu sel O1D1. Bandingkan persediaan di O1 dengan kebutuhan di D1, yaitu masing-masing d1 dan b1. Buat x11 = Min (b1, d1).
Bila b1 > d1, maka x11 = d1. Teruskan ke sel O1D2, yaitu gerakan horizontal dimana x12 = min. (b1 - d1, d2).
Bila b1 < d1, maka x11 = b1. Teruskan ke sel O2D1, yaitu gerakan vertikal dimana x21 = min. (d1 - b1, b2).
Bila b1 = d1, maka buatlah x11 = d1 dan teruskan ke sel O2D2 (gerakan miring). Teruskan langkah ini menjauhi pojok barat laut menuju pojok tenggara dari
tabel, hingga akhirnya semua permintaan terpenuhi. Setelah program awal ini selesai ditentukan, maka perlu diuji persyaratan bahwa m+n-1 sel harus terisi. Bila m+n-1 sama dengan jumlah sel yang terisi, maka solusi tidak merosot. Metode pojok barat-laut ini memperlihatkan bahwa tiap langkah yang dilakukan akan memenuhi satu kendala. Hingga akhirnya berhenti di langkah ke m+n-1, karena pada langkah ini sudah terpenuhi m+n-1 kendala. Metode pojok barat-laut ini belum bisa dibilang optimal, dikarenakan metode ini mengabaikan biaya yang relevan dari tiap-tiap rute.
2.2. Metode Inspeksi Penyelesaian
masalah
transportasi,
diperlukan
adanya
inspeksi
dan
pertimbangan. Untuk masalah transportasi berdimensi kecil, hal ini akan memberi pengurangan terhadap waktu.
71
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
Alokasi pertama dibuat terhadap sel yang berkaitan dengan biaya pengangkutan terendah. Sel dengan ongkos terendah ini diisi sebanyak mungkin dengan mengingat persyaratan kapasitas origin maupun persyaratan permintaan tempat tujuan. Lalu beralih mengalokasikan ke sel termurah berikutnya dengan memperhatikan kapasitas yang tersisa dan permintaan baris dan kolomnya. Ada kemungkinan terdapat adanya ikatan antara sel-sel termurah. Ikatan tersebut dapat dipatahkan atau dengan memilih sembarang sel untuk diisi. Banyaknya sel yang terisi harus sedemikian hingga diperoleh m+n-1 sel yang terisi. Secara singkat, pendekatan metode transportasi didasarkan atas tiga langkah, yaitu : 1.) menentukan program awal untuk mencapai solusi dasar yang memenuhi syarat, 2.) menentukan biaya kesempatan dari setiap sel kosong, dan 3.) memperbaiki program yang sedang berjalan untuk memperoleh program yang lebih baik, hingga akhirnya mencapai solusi optimal. Metode pojok barat-laut dan metode inspeksi merupakan metode untuk menentukan solusi awal. Selanjutnya, terdapat beberapa cara penyelesaian masalah dalam model transportasi. Semua cara penyelesaian ini mengarah pada penyelesaian optimal dari masalah-masalah transportasi yang terjadi, yaitu Metode Batu Loncatan, Metode MODI, dan Metode Pendekatan Vogel.
2.3. Metode Batu Loncatan Metode ini dikenal juga dengan nama Stepping Stone Method. Metode ini digunakan untuk menentukan optimal atau tidaknya solusi dasar yang didapat pada langkah pertama. Sebelum mengaplikasikan metode batu loncatan ini, harus ditentukan terlebih dahulu biaya kesempatan atau opportunity cost dari sel yang kosong. Dalam model transportasi melibatkan pengambilan keputusan dengan kepastian, maka suatu solusi optimal tidak akan menimbulkan suatu biaya kesempatan yang positif.
Untuk
menentukan adanya suatu biaya kesempatan yang bernilai positif dalam suatu program, maka setiap sel kosong (sel yang tidak ikut dalam jalur pengangkutan) 72
Handout Program Linier : Model Transportasi
harus diselidiki. Metode batu loncatan ini dapat dipergunakan untuk setiap matriks yang berukuran m x n. Dalam metode ini, sebuah loop tertutup dilengkapi dengan tanda (+) dan (-) harus ditentukan untuk setiap sel kosong sebelum menentukan biaya kesempatannya. Setelah loop-loop tersebut ditentukan, barulah ditentukan biaya kesempatannya. Tiap loop tersebut dihitung dengan cara menambah dan mengurangi secara bergantian
biayanya dimulai dari sel kosong yang akan
dicari. Jika ternyata biaya kesempatan dari tiap loop tersebut tidak ada yang bernilai positif, maka program telah optimal. Sebaliknya, jika terdapat satu saja sel kosong yang memiliki biaya kesempatan positif, maka program belum optimal. Sehingga program tersebut masih perlu diperbaiki. Perbaikan program awal diarahkan oleh loop tertutup yang bernilai positif dari sel kosong. Tentukan bilangan dengan tanda negatif (-) yang terkecil dalam sel yang terdapat dalam loop tersebut. Dalam loop tersebut, tambahkan bilangan tersebut ke semua sel yang bertanda positif (+) dan kurangkan semua sel yang bertanda negatif (-) dengan bilangan tersebut. Metode batu loncatan dapat digunakan untuk setiap matriks yang berukuran m x n. Inti dari prosedur batu loncatan dalam penyelesaian masalah transportasi secara singkat yaitu : 1.) menyusun solusi dasar yang memenuhi syarat, 2.) setelah memperoleh solusi dasar yang memenuhi syarat, lalu dilakukan penentuan biaya kesempatan dari sel-sel yang kosong, dan 3.) jika tidak ada satu sel pun memiliki biaya kesempatan yang bernilai positif, maka program sudah optimal. Sebaliknya, jika ada satu saja sel yang memiliki biaya kesempatan yang bernilai postitif, maka program belum optimal. Maka harus dilakukan perbaikan program dengan mengikut sertakan sel kosong yang memiliki biaya kesempatan tertinggi.
2.4. Metode MODI a. Pengertian Metode MODI Metode MODI disebut juga Modified Distribution Method, sangat mirip dengan metode batu loncatan, kecuali bahwa ia menyajikan cara yang lebih efisien untuk 73
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
menghitung tanda-tanda peningkatan dari sel-sel yang kosong. Perbedaan utama antara dua metode ini menyangkut langkah dalam penyelesaian masalah, dimana diperlukan
adanya
suatu
lintasan
tertutup.
Untuk
menghitung penunjuk
peningkatan suatu solusi khusus, maka dalam metode batu loncatan perlu digambar suatu lintasan tertutup untuk setiap sel kosong. Ditentukan sel kosong dengan biaya kesempatan tertinggi, kemudian dipilih untuk ikut dalam program perbaikan berikutnya. Metode MODI penunjuk peningkatan dapat dihitung tanpa menggambar lintasan tertutup. Dalam kenyataannya metode MODI memerlukan hanya satu lintasan tertutup. Lintasan ini digambar setelah sel kosong yang memiliki biaya kesempatan tertinggi positif ditemukan. Seperti dalam metode batu loncatan, kegunaan lintasan ini ialah untuk menentukan jumlah unit maksimum yang dapat dipindahkan ke sel kosong dalam program perbaikan berikutnya. Maka, prosedur untuk menghitung biaya kesempatan dari sel kosong dalam MODI tidak tergantung pada lintasan loop tersebut. Biaya kesempatan = implied cost
– biaya sebenarnya
Cara menentukan implied cost dari sebuah sel kosong tanpa menggambarkan lintasan loop terlebih dahulu, dengan menyusun kerangka utama dari metode MODI, kemudian mengurangkan biaya sebenarnya dari implied cost sel kosong yang telah dihitung. Sesuai itu dapat ditunjukkan bahwa dalam kasus masalah transportasi, kesempatan dari setiap sel terisi (sel berisi variable basis) adalah nol. Dengan perkataan lain, jika variable basis tidak akan diubah, maka pemasukan dan pemindahan 1 unit di sembarang sel terisi tidak akan mengakibatkan perubahan biaya. Sekarang, tentukan sekumpulan bilangan baris (ditempatkan di sebelah paling kanan) dan sekumpulan bilangan kolom (ditempatkan di bawah setiap kolom dari tabel) sedemikian rupa sehingga ongkos pengangkutan per unit dari setiap sel terisi sama dengan jumlah dari bilangan baris dan bilangan kolom. Selanjutnya, kerana jumlah bilangan baris dan bilangan kolom dari 74
Handout Program Linier : Model Transportasi
sembarang sel terisi sama dengan ongkos dari sel tersebut (suatu variable basis), maka jumlah bilangan baris dan bilangan kolom dari setiap sel kosong memberikan implied cost dari sel kosong tersebut. Maka implied cost dari sembarang sel kosong diberikan oleh :
.
Maka dengan menentukan bilangan baris dan bilangan kolom secara lengkap, dapat menghitung implied cost untuk setiap sel kosong tanpa menggambar lintasan loop. Untuk setiap sel terisi, pilih um (bilangan baris) dan vn (bilangan kolom) sehingga cmn (biaya pengangkutan sebenarnya per unit di sel terisi) sama dengan jumlah dari um dan vn. Misalkan untuk sel terisi yang terletak di baris 1 dan kolom 1, maka c11 = u1 + v1 dan c12 = u1 +v2 dan seterusnya. Proses ini harus dilakukan untuk setiap sel terisi. Tetapi harap disadari bahwa walaupun solusi dasar yang memenuhi syarat dalam suatu model transportasi terdiri atas m+n–1 variabel (dengan perkataan lain, terdapat m+n–1 sel terisi), tentukan m+n nilai untuk memperoleh sekumpulan bilangan baris dan kolom, harus dipilih satu bilangan sembarang yang mewakili suatu baris atau suatu kolom. Sekali suatu bilangan baris atau kolom telah dipilih secara sebarang, bilangan baris dan bilangan kolom lainnya dapat ditentukan oleh hubungan cmn = um + vn. Hubungan ini harus berlaku untuk semua sel isi karena sembarang bilangan dapat dipilih untuk mewakili salah satu dari um atau vn, ikuti secara praktis dengan memisahkan u1 = 0. Tabel Metode MODI Implied Cost
Biaya Sebenarnya
Tindakan Program yang lebih baik dapat disusun dengan mengikut sertakan sel ini Tidak berpengaruh Sel ini jangan diikut sertakan dalam program
Jika implied cost (um + vn) dari suatu sel kosong lebih besar dari ongkos sebenarnya (cmn), maka sel kosong ini dapat diikut sertakan dalam perbaikan program berikutnya. Jika implied cost (um + vn) dari suatu sel kosong kurang dari ongkos sebenarnya (cmn), maka sel kosong ini jangan diikut sertakan. Jika (um + vn) = 75
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
cmn maka sel kosong ini tidak berpengaruh terhadap perbaikan program. Singkatnya, untuk menilai dan meningkatkan suatu program dimana tujuannya ialah meminimumkan fungsi obyektif, maka aturan yang tertera pada tabel aturan MODI diatas berlaku. Langkah terakhir dalam metode MODI persis sama seperti langkah berkaitan dalam metode batu loncatan. Setelah mengenali sel kosong yang memiliki biaya kesempatan terbesar positif, sel kosong ini harus diikut sertakan dalam program perbaikan dan sebuah lintasan tertutup harus digambar untuk sel ini. Solusi dasar yang baru dan memenuhi syarat diturunkan dari program awal dengan menggeser unit barang sebanyak mungkin kedalam sel kosong tanpa melanggar persyaratan rim.
iaya kesempatan
biaya sebenarnya
b. Prosedur Metode MODI (untuk kasus minimum) Langkah 1
Memperoleh solusi dasar yang memenuhi syarat. Metode yang digunakan metode pojok barat-laut atau inspeksi. Harus diperoleh m+n–1 sel terisi. Jika jumlah sel terisi melebihi m+n–1, maka ada salah hitung. Jika jumlah sel terisi kurang dari m+n-1, maka solusi ini mengalami kemerosotan.
Langkah 2
Menentukan biaya kesempatan dari setiap sel kosong. a. Tentukan bilangan baris dan bilangan kolom secara lengkap. b. Untuk setiap sel terisi berlaku cmn = um + vn ambillah u1 = 0. Hitunglah implied cost dari setiap sel kosong. Implied cost = bilangan baris + bilangan kolom. b. Tentukan biaya kesempatan dari setiap sel kosong. Opportunity cost = um + vn - cmn. Jika semua sel kosong memiliki biaya kesempatan tidak positif, maka solusi sudah optimal. Jika masih ada sel kosong yang memiliki biaya kesempatan positif, program masih dapat
76
Handout Program Linier : Model Transportasi
diperbaiki. Merancang peningkatan program Sel kosong yang memiliki
Langkah 3
biaya
kesempatan
positif
terbesar diikut sertakan dalam
program perbaikan. a.
Gambarlah suatu loop melalui sel kosong tersebut menuju sel- sel terisi kemudian kembali lagi ke sel kosongnya.
b.
Beri tanda (+) pada sel kosong yang akan diisi, kemudian berganti-ganti letakkan tanda (+) dan (-) pada sel-sel terisi yang dilalui loop.
c.
Banyaknya barang yang harus digeser ditentukan oleh alokasi terendah dari sel yang bertanda (-).
Ulangi langkah 2 dan 3 sampai diperoleh program yang optimal.
Langkah 4
c.
Prosedur Metode MODI (untuk kasus maksimum) Kecuali untuk satu transformasi, suatu masalah transportasi dengan tujuan
menentukan nilai maksimum dari suatu fungsi, dapat diselesaikan dengan algoritma MODI seperti telah dijelaskan. Transformasi dilakukan dengan mengurangkan semua cmn
dari cmn tertinggi dari matriks transportasi. Nilai cmn yang telah
mengalami transformasi memberikan ongkos relevan, dan masalah menjadi masalah menentukan minimum. Jika suatu solusi optimal telah dicapai untuk masalah transformasi minimum ini, nilai dari fungsi obyektif dapat dihitung dengan memasukan nilai asli dari cmn kedalam rute yang merupakan basis (sel terisi) dalam solusi optimal.
2.5. Metode VAM Metode ini disebut juga Vogel Approximation Metod (VAM). Metode ini didasarkan atas suatu beda kolom dan suatu beda baris, yang menentukan beda antara dua ongkos. Setiap beda dapat dianggap sebagai penalti karena tidak menggunakan rute termurah. Setelah dilakukan perhitungan penalti sesuai 77
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
metode pendekatan Vogel, ditentukanlah penalti tertinggi. Baris atau kolom berkaitan dengan penalti tertinggi, akan dijadikan alokasi yang pertama. Alokasi pertama ini ditempatkan pada sel dengan penalti tertinggi pada baris atau kolom yang berkaitan dengan biaya termurah. Alokasi pertama ini menentukan baris atau kolom mana yang akan dihapus dari matriks transportasi, akibat terpenuhinya keperluan dari alokasi pertama tadi. Metode ini memiliki kelemahan dikarenakan harus melakukan perhitunganperhitungan yang banyak, sebelum tercapainya solusi dasar yang memenuhi syarat. Akan tetapi, metode pendekatan Vogel dapat menghasilkan biaya pengangkutan yang jauh lebih murah dibanding dengan menggunakan metode pojok barat-laut.
D. Skenario Model Transportasi Masalah transportasi diformulasikan berdasarkan skenario sebagai berikut : 1. Ada sumber/daerah asal (origin) dengan kapasitas (supply) maksimumnya. 2. Ada tujuan (destination) dengan permintaan (demand) minimumnya. 3. Ada jalur angkutan dari setiap sumber ke setiap tujuan beserta ongkos angkut satuan. (Ongkos sifatnya linier proporsional terhadap jarak) 4. Ada satu macam komoditi saja yang diangkut 5. Meminimalkan ongkos angkut. 6. Adanya fungsi sasaran (objective function) yang diasumsikan linear.
E. Langkah-Langkah Penyelesaian : Akibatnya banyaknya variabel basis adalah m+n-1, sebab m+n-1 merupakan banyaknya persamaan yang saling independen. Oleh karena itu penyelesaian fisibel basis (pfb) terdiri atas m+n-1 variabel basis. Untuk mencari solusi optimal (minimal) masalah transportasi, dikerjakan dengan 3 langkah:
78
Handout Program Linier : Model Transportasi
5.1. Langkah 1 : Menyusun solusi awal (tabel awal) Maksud menyusun solusi awal: untuk mencari pfb. Dasar hukum (dalil) : Hukum 1: Tabel transportasi akan memberikan suatu pfb bila dalam setiap pengisian alokasi dipilih alokasi yang memaksimalkan kotak dengan batasan supply & demand. Hukum 2: pfb paling tidak memuat satu solusi optimal. Berdasarkan kedua hukum di atas, ada beberapa metode peyusunan tabel awal antara lain : yaitu metode sudut barat laut (North West Corner) dan metode inspeksi.
5.2. Uji Optimalitas Ada beberapa metode untuk menguji optimalisasi, antara lain Metode Batu Loncatan, Metode MODI, dan Metode Pendekatan Vogel. Berikut adalah langkah untuk metode Stepping-Stone (Metode Batu Loncat). Uji optimalitas metode stepping-stone dikerjakan sebagai berikut : a. Untuk setiap kotak kosong xij dicari lintasan horisontal & vertikal (tertutup/loop) melewati kotak-kotak yang sudah isi. Loop ini selalu bisa diperoleh, karena kita sudah mempunyai m+n-1 kotak isi. Sebagai gambaran misalkan Ada kotak kosong yang mempunyai lintasan tertutup x13 x14 x34 x33 x13, maka “opportunity Cost” c13* didefinisikan sebagai : c13* = --Δf13 di mana Δf13 = c13 – c14 + c34 – c33. Hitunglah opportunity cost cij untuk setiap kotak kosong xij. b. Solusi sudah optimal, bila dan hanya bila /jika opportunity cost cij* ≤ 0, untuk semua kotak kosong xij. c. Solusi belum optimal, jika terdapat opportunity cost cij* > 0, untuk suatu kotak kosong xij jika ini terjadi, maka langkah selanjutnya adalah memperbaiki tabel (langkah III) 79
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
5.3. Memperbaiki Tabel Memperbaiki tabel pada dasarnya adalah menentukan variabel basis yang keluar dan sekaligus menentukan variabel baru yang masuk sebagai basis. Caranya sebagai berikut : a. Kotak kosong yang diisi (yaitu variabel baru yang masuk sebagai basis) adalah kotak kosong xij yang mempunyai opportunity cost cij* > 0 (mxn)-(n terbesar) b. Untuk kotak kosong yang terpilih untuk diisi, ditentukan loop dulu. Lintasan tertutup (loop) seperti langkah II (metode stepping-stone) dan diberi tanda berselang-seling positif negatip mulai dengan kotak kosong terpilih. Pilih alokasi kotak bertanda negatip paling kecil (paling melarat), itulah alokasi maksimum yang bisa digeser dan masuk kotak terpilih melalui loop tadi. Tanda negatip berarti alokasi doner & alokasi donor paling melarat itulah variabel basis yang keluar. Ia menjadi kotak kosong pada tabel berikutnya. c. Setelah kotak kosong tersebut diisi, kemudian dikerjakan langkah II (uji optimalitas) lagi. Demikian seterusnya sampai diperoleh solusi optimal.
F. Contoh Soal 1. Diketahui model transportasi seperti gambar berikut :
80
b1 = 50
O1
b2 = 40
O2
D1
a1 = 30
D2
a2 = 60
Handout Program Linier : Model Transportasi
Penyajian :
c11 = 3, c12 = 5 , c21 = 1, c22 = 2
Origin
D1
D2 3
O1
bi 5
30
20
50
1
2
O2
0
40
ai
30
60
40 90
Tabel awal diisi dengan metode North-West-Corner -
Setiap pengisian harus full kolom/ baris
-
Alokasi kosong tak perlu diisi, x21 = 0
Nilai f = 30(3) + 20(5) + 2(40) + 0(1) = 270 Andaikan x21 diisi 1 alokasi, maka tabel menjadi D1
D2 3
O1
29(-)
bi 5
21(+) 1
50 2
O2
1+
39(-)
ai
30
60
40
Dan akibatnya f baru = 29(3) + 21(5) + 1(1) + 39(2) = 271 f lama = 270 maka Δ f21
= f baru – f lama = 1
Perhatikan Δf = (-1)3 + (1)(5) (+1)(1) + (-1)(2) = 1 → f bertambah besar x-21 mempunyai opportunity cost c21* = -Δ f21 = -1 (lawan Δ f21) Jadi tabel sudah optimum (minimum)
81
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
jadi solusinya adalah: 30 50
D1
O1
30
20 40
D2
60
O2
40 Jadi dalam contoh ini tabel pertama langsung memberikan hasil yang optimum. 2.
Perhatikan skema model transportasi berikut :
b1 = 80
O1
b2=20
O2
Penyajian:
D1
a1 = 50
D2
c11 = 4
c12 = 3
a2 = 50 c21 = 2
c22 = 5
Penyelesaian : Langkah 1 : D1
D2 3
O1
50
5 (+)30
1
80 2
O2
+
(-)20
20
ai
50
50
100
x21 = 0 Tabel awal diisi dengan metode North West Corner : f = 4(50) + 3(30) + 0(2) + 5(20) = 390 Jika x21 diisi 1 alokasi, maka tabel berubah menjadi : 82
bi
Handout Program Linier : Model Transportasi
D1
D2 4
O1
49
bi 3
(+)31
80
2
5
O2
1+
(-)19
20
ai
50
50
100
Dengan fbaru = 4(49) + 3(31) + (1)(2) + 5(19) = 386 Δ f21 = fbaru – flama = - 4 Jadi c21* = - Δ f21 = 4 solusi belum optimal (minimal). Langkah 2 : Karena kotak X 21 satu-satunya kotak dengan c 21* = 4 > 0, maka X21 harus diisi dengan alokasi donor yang paling melarat ialah X22 = 20 (digeser sepanjang lintasan(loop)) tertutup : x21, x11, x12. x22 keluar dari basis X21 masuk basis Jadi tabel pada langkah II, ialah: D1
D2 4
O1
30(+)
bi 3
(-)50 2
80 5
O2
20(-)
(+)
20
ai
50
50
100
x22 = 0. c22* = -Δf = - (+5+4-2-3) = -4 < 0. Karena c22* < 0, maka solusi sudah optimal. Jadi solusi optimalnya ialah: 83
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
80
D1
30
O1
=50
50
20
O2
D2
20
=50
G. Soal Latihan
Aktivitas 1
1.
Kerjakan soal berikut :
perusahaan mempunyai 4 buah pabrik dengan 4 daerah pemasaran. Ke empat pabrik mempunyai kapasitas produksi yang sama yaitu 100 ton. Sedangkan ke empat daerah pemasaran masing-masing mempunyai demand 75, 75, 160 dan 90 ton per bulan. Tentukan besarnya komoditi yang seharusnya diikirim dari masingmasing pabrik ke masing-masing daerah pemasaran agar ongkos angkut total minimal, jika diketahui ongkos angkut satuan dari setiap pabrik ke daerah pemasaran sebagai berikut:
Destination Origin O1 O2 O3 O4 Demand ( a)j
D1
D2
D3
4
5
6
7
5
2
1
7
6
6
2
5
1
3
6
4
75
75
160
Atau pakai North West Corner (mulai dari barat laut) Atau pakai Least Cost Method (pilih yang costnya terkecil) 84
Supply bi
D4
90
100 100 100 100 400
400
Handout Program Linier : Model Transportasi
k23 b2=100, a3 = 160 (pilih yang min) = 100 baris 2 penuh yang 1dipilih k41 b4=100, a1=75 (pilih yan min) =75 kolom 1 penuh. yang 2 dipilih k33 160-100 = 60 baris 3 penuh dan seterusnya. Penyelesaian : Destination Origin
D1
D2
D3
D4
Supply bi
O1 O2 O3 O4 Demand ( a)j
Tabel awal diisi dengan cij terkecil. Urutan : k23, k41, k33, k42, k12, k34, k14. Kotak isi = m+n-1 = 4 + 4 – 1 = 7 c11* = -Δf = - (4-5+3-1) = -1 lintasan k11, k12, k42, k41 c13* = -Δf = - ( .............................................) = ............. lintasan k13, k14, k34, k33 c21* = -Δf = - (...................................................) = ....... lintasan k21, k23, k33, k34, k14, k12, k42, k41 c22* = -Δf = - (...............................................................) = .......... lintasan k22, k23, k33, k34, k14, k12 c24* = -Δf = - (...............................................................) = .............. lintasan k24, k34, k33, k23 c31* = -Δf = - (...............................................................) = ............ lintasan k31, k34, k14, k12, k42, k41 c32* = -Δf = - (............................................................) = .............. lintasan k32, k12, k14, k34 c43* = -Δf = - (...............................................................) = ............ lintasan k43, k42, k12, k14, k34,k33, c44* = -Δf = - (...............................................................) = ............ > 0 lintasan k44, k42, k12, k14, k44 solusi belum optimal, sebab c44* = ........... > 0. Maka tabel baru: (II) 85
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
Destination Origin
D1
D2
D3
D4
Supply bi
O1 O2 O3 O4 Demand ( a)j
Alokasi donor yang paling melarat ialah x42 = 25 digeser ke x44 melewati lintasan k42, k44, k14,
k12
Periksa opportunity cost: c11* = -Δf = - (.....................................................) = ............... lintasan k11, k14, k44, k41, k11 c13* = -Δf = - (.....................................................) = ............... lintasan k13, k14, k34, k33, k13 c21* = -Δf = - (..................................................... )= .......... lintasan k21, k23, k33, k34, k44, k41 c22* = -Δf = - (.....................................................) = ......... lintasan k22, k23, k33, k34, k14, k12 c24* = -Δf = - (..................................................) = ....... lintasan k24, k23, k33, k34, k24. c31* = -Δf = - (...................................................) = ......... lintasan k31, k34, k44, k41, k31 c32* = -Δf = - (...................................................) =.......... lintasan k32, k34, k14, k12, k32 c42* = -Δf = - (...................................................) = ........... lintasan k42, k44, k14, k12, k42 c43* = -Δf = - (....................................................) = ........... lintasan k43, k44, k34, k33, karena cij* ≤ 0, untuk semua kotak kosong xij, maka solusi sudah optimum (minimum), dengan min = ...............................................................................................
86
Handout Program Linier : Model Transportasi
Jadi solusinya adalah sebagai berikut: 100
O1
75
D1
-75
25 100
100
O2
O3
D2
100 60 75
D3
2.
-160
40
O4
100
-75
25
D4
-90
Jaka Sebuah perusahaan pupuk mempunyai 3 pabrik di Cirebon, Bandung dan Cilacap yang masing-masing mampu memproduksi 120, 80 dan 80 ton per bulan. Perusahaan tersebut juga mempunyai 3 gudang di Semarang, Jakarta dan Purwoketo yang masing-masing mampu menampung 150, 70, dan 60 ton per bulan. Tentukan banyaknya pupuk yang seharusnya dikirim dari masing-masing pabrik ke masing-masing gudang, agaraongkostotal minimum, jika diketahui ongkos angkut sasaran dari masing-masing pabrik ke masing-masing gudang sebagai berikut Gudang Pabrik
D1
D2
O1 O2 O3
D3
bi
8
5
6
15
10
12
3
9
10
120 80 80 280
aj
150
70
O1 = pabrik di Cirebon
D1 = gudang di Semarang
O2 = pabrik di Bandung
D2 = gudang di Jakarta
O3 = pabrik di Cilacap
D3 = gudang di Purwokerto
60
280
87
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
O1
D1
O2 D2
O3
3. Jawaban :
88
D3
Handout Program Linier : Model Transportasi
89
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
90
Handout Program Linier : Model Transportasi
Aktivitas 2
Kesimpulan apa yang dapat Anda ambil pada pembelajaran ini :
........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ........................................................................................................................................................................... ...........................................................................................................................................................................
Tanggal
Nilai
Paraf Dosen
91
Meyta Dwi Kurniasih, M.Pd. Pendidikan Matematika UHAMKA
Daftar Pustaka Bintang K, Yosep. 2005. Matematika Ekonomi dan Bisnis. Jakarta : Salemba Empat Dumairy. 1991. Matematika Terapan Untuk Bisnis dan Ekonomi (Edisi 2). Yogjakarta : BPFE Levin, Richard I., et al. 1992. Quantitative Approaches to Management, eighth edition. New York : McGraw-Hill. Render, Barry dan Jay Heizer. 1997. Principles of Operations Management, second edition, Upper Saddle River. New Jersey : Prentice Hall, Inc. Ruminta. 2009. Matriks, Persamaan Linier dan Pemprograman Linier. Bandung: Rekayasa Sains. Siringoringo, Hotniar. 2005. Seri Teknik Riset Operasional: Pemrograman Linear. Yogjakarta: Graha Ilmu. Sudrajat. 2008. Pendahuluan Penelitian Operasional. Bandung : Univ. Padjajaran. Taha, Hamdy A. 1997. Operations Research, an Introduction, sixth edition, Upper Saddle River. New Jersey : Prentice Hall, Inc. Tapilouw, Marten & Soemartojo. 2007. Program Linier. Jakarta : UT. Yuwono, Bambang & Putri Istiani. 2007. Riset Operasional. Yogjakarta : UPN Veteran
92
