PERANGKAT PEMBELAJARAN

PERANGKAT PEMBELAJARAN

MATA KULIAH KODE DOSEN

: PROGRAM LINEAR : MKK206515 : ERIKA LARAS ASTUTININGTYAS, M.Pd.

PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS VETERAN BANGUN NUSANTARA SUKOHARJO

KONTRAK PEMBELAJARAN

PROGRAM LINEAR MKK206515

Semester II / 3 SKS Program Studi Pendidikan Matematika

Oleh : ERIKA LARAS ASTUTININGTYAS, M.Pd.

FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS VETERAN BANGUN NUSANTARA SUKOHARJO

A.

Identitas Mata Kuliah Mata Kuliah Semester / SKS Pengampu Mata Kuliah Kode Mata Kuliah

B.

: : : :

PROGRAM LINEAR II / 3 SKS ERIKA LARAS ASTUTININGTYAS, M.Pd. MKK206515

Manfaat Mata Kuliah Setelah mengikuti kuliah ini diharapkan mahasiswa dapat : 1. Mengenal program linear sebagai penunjang pengambilan keputusan 2. Memahami syarat-syarat pemecahan persoalan program linear dengan metode grafik 3. Memahami masalah teknis dalam program linear 4. Memahami bentuk standar model program linear 5. Memahami metode simpleks untuk memecahkan permasalahan program linear

C.

Deskripsi Mata Kuliah Program Linear adalah mata kuliah yang mempelajari tentang metode optimasi untuk menentukan nilai optimum dari fungsi tujuan linear pada kondisi pembatasan-pembatasan tertentu. Metode yang digunakan dalam optimasi adalah : metode grafik dengan titik ekstrim, metode grafik dengan isoline, serta metode simpleks. Kejadian-kejadian khusus dalam permasalahan program linear juga dipelajari dan disertai pula dengan cara pengambilan keputusan apabila terjadi kejadian khusus, baik untuk metode grafik maupun metode simpleks.

D.

Kompetensi Dasar dan Indikator Kompetensi Dasar

Indikator

1. Membentuk model matematika dari permasalahan program linear

1.1 Menentukan variabel keputusan dari permasalahan program linear 1.2 Menentukan fungsi kendala dari permasalahan program linear 1.3 Menentukan fungsi tujuan dari permasalahan program linear 2.1 Menentukan daerah layak (feasible region) dari permasalahan program linear 2.2 Menentukan nilai optimum permasalahan program linear dengan metode grafik menggunakan isoline 2.3 Menentukan nilai optimum permasalahan program linear menggunakan metode grafik dengan menentukan titik ekstrim 2.4 Menentukan nilai optimum dari kejadian khusus yang muncul saat optimasi dengan metode grafik 3.1 Menentukan bentuk standar dari model matematika 3.2 Menentukan nilai optimum permasalahan program linear dengan metode simpleks 3.3 Menentukan nilai optimum permasalahan program linear dengan metode simpleks menggunakan teknik M 3.4 Menentukan nilai optimum permasalahan program linear dengan metode simpleks dua tahap 3.5 Melakukan Interpretasi terhadap Tablo Optimal Simpleks 3.6 Menentukan nilai optimum dari kejadian khusus yang muncul saat optimasi dengan metode simpleks

2. Menyelesaikan permasalahan program linear dengan metode grafik

3. Menyelesaikan permasalahan program linear dengan metode simpleks

E.

Organisasi Materi

KD I F.

KD II KD III

Pendekatan Dan Strategi Pembelajaran Strategi pembelajaran yang digunakan mengarah pada Active Learning. Metode-metode yang digunakan adalah sebagai berikut : 1. Questions Students Have 2. Kelompok Belajar (The Study Group) 3. Concept Sentences 4. The Learning Cell

G.

Sumber Belajar [1] Aminudin . 2005 . Prinsip–prinsip Riset Operasi . Jakarta : Erlangga [2] Ruminta . 2009 . Matriks, Persamaan Linear dan Pemorograman Linear . Bandung : Rekayasa Sains [3] Siswanto . 2006 . Operations Research Jilid I . Jakarta : Erlangga [4] Handout Kuliah

H.

Penilaian Dan Kriteria Pembelajaran 1. 2. 3. 4.

I.

Presensi dan Keaktifan Tugas Terstruktur UTS UAS

: : : :

30 % 20 % 20 % 30 % 100 %

Jadwal Perkuliahan Pertemuan

PEMBELAJARAN Materi :

1

2

a. Pengenalan Pemrograman Linear b. Membentuk permasalahan program linear ke dalam model matematika, yang menyangkut :  Menentukan variabel keputusan dari permasalahan program linear  Menentukan fungsi kendala dari permasalahan program linear  Menentukan fungsi tujuan dari permasalahan program linear

Materi : a. Menggambar daerah penyelesaian dari pertidaksamaan linear b. Menentukan daerah layak (feasible region) dari permasalahan program linear

Materi : 3

 Menentukan nilai optimum permasalahan program linear dengan metode grafik menggunakan isoline

Materi : 4

 Menentukan nilai optimum permasalahan program linear dengan metode grafik menggunakan titik ekstrim

Materi : 5

 Menentukan nilai optimum dari kejadian khusus yang muncul saat optimasi dengan metode grafik

6

QUIZ 1 : KD 1 dan KD 2

7 8 9 10

11

12

13 14 15 16

Materi : a. Bentuk standart dari permasalahan program linear b. Konsep dasar dan algoritma metode simpleks

Materi : Penyelesaian permasalahan program linear dengan metode simpleks Ujian Tengah Semester

Materi : a. Peyelesaian awal semu b. Metode simpleks dengan teknik M

Materi : Metode simpleks dua tahap

Materi : Interpretasi tablo optimal simpleks

Materi :  Berbagai kejadian khusus pada metode simpleks

QUIZ II Materi : KD 3

REVIEW:  Persiapan Ujian Semester

Ujian Akhir Semester

UNIVERSITAS VETERAN BANGUN NUSANTARA SUKOHARJO FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN

SILABUS Program Studi Kode Mata Kuliah Mata Kuliah Bobot Semester Mata Kuliah Prasyarat Standar Kompetensi

: : : : : : :

PENDIDIKAN MATEMATIKA MKK206515 PROGRAM LINEAR 3 SKS II Aljabar Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode

Kompetensi Dasar

Indikator

Pengalaman Belajar

1. Membentuk model

1.1 Menentukan variabel keputusan

Tatap muka  Memberikan deskripsi tentang program linear  Memberi contoh permasalaahan program linear  Memberikan gambaran tentang variabel, fungsi kendala dan fungsi tujuan

matematika dari permasalahan program linear

1.2 1.3

2. Menyelesaikan

permasalahan program linear dengan metode grafik

dari permasalahan program linear Menentukan fungsi kendala dari permasalahan program linear Menentukan fungsi tujuan dari permasalahan program linear

2.1 Menentukan daerah layak 2.2

2.3

(feasible region) dari permasalahan program linear Menentukan nilai optimum permasalahan program linear dengan metode grafik menggunakan isoline Menentukan nilai optimum permasalahan program linear menggunakan metode grafik

Kegiatan terstruktur  Pre-test  Mendiskusikan pemodelan dengan menentukan variabel keputusan, fungsi kendala dan fungsi tujuan pada permasalahan pemrograman linear  Post-test Tatap muka  Memberikan deskripsi singkat tentang daerah layak (feasible region)  Memberikan definisi dari titik ekstrim cara penentuan nilai optimum dengan evaluasi nilai fungsi tujuan pada titik ekstrim  Menjelaskan secara singkat tentang isoline dan cara penentuan nilai optimum dengan isoline Kegiatan terstruktur

Materi Pokok  Pengenalan 

 

3  50

Pemrograman Linear Membentuk permasalahan program linear ke dalam model matematika

 Daerah penyelesaian 

Alokasi Waktu (menit)

dari pertidaksamaan linear Penentuan daerah layak (feasible region). Meetode grafik dengan titik ekstrim. Metode grafik dengan isoline

Sumber/ Bahan/ Alat Sumber :  Buku panduan mata kuliah Program Linear  Modul Alat :

9  50

Sumber :  Buku panduan mata kuliah Program Linear  Modul Alat :

Penilaian/ Evaluasi Bentuk evaluasi :  Pre-test  Post-test Instrumen :  Lembar Kerja Individu

Bentuk evaluasi :  Pre-test  Post-test Instrumen :  Lembar Diskusi Kelompok

dengan menentukan titik ekstrim

2.4 Menentukan nilai optimum dari

3. Menyelesaikan

permasalahan program linear dengan metode simpleks

3.1 3.2 3.3

3.4

3.5

kejadian khusus yang muncul saat optimasi dengan metode grafik Menentukan bentuk standar dari model matematika Menentukan nilai optimum permasalahan program linear dengan metode simpleks Menentukan nilai optimum permasalahan program linear dengan metode simpleks menggunakan teknik M Menentukan nilai optimum permasalahan program linear dengan metode simpleks dua tahap Menentukan nilai optimum dari kejadian khusus yang muncul saat optimasi dengan metode simpleks

Pre-test Mendiskusikan berbagai kejadian khusus yang muncul saat optimasi dengan metode grafik  Post-test Tatap muka  Menjelaskan tentang bentuk standar (bentuk kanonik) dalam pemodelan matematika permasalahan program linear  Menjelaskan optimasi permasalahan pemrograman linear dengan metode simpleks, metode simpleks dengan teknik M, dan metode simpleks dua tahap  

Kegiatan terstruktur  Post test

 Menentukan nilai

optimum dari kejadian khusus

 Bentuk      

standart/bentuk kanonik Metode simpleks. Interpretasi tablo optimal simpleks Kejadian khusus pada metode simpleks Peyelesaian awal semu Metode simpleks dengan teknik M Metode simpleks dua tahap

18  50

Sumber :  Buku panduan mata kuliah Program Linear  Modul Alat :

Bentuk evaluasi :  Post-test Instrumen :  Lembar Kerja Individu  Lembar diskusi kelompok

RENCANA MUTU PERKULIAHAN (RMP) Nama Dosen NIP Fakultas Program Studi

: : : :

ERIKA LARAS ASTUTININGTYAS, M.Pd. 19860715 2013032174 KEGURUAN DAN ILMU PENDIDIKAN PENDIDIKAN MATEMATIKA

Mata Kuliah Kode Mata Kuliah Bobot Semester Pertemuan keStandart Kompetensi

: : : : : :

Kompetensi Dasar Indikator

: :

Tujuan

:

PROGRAM LINEAR MKK206515 3 SKS II 1 Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode 1. Membentuk model matematika dari permasalahan program linear 1.1 Menentukan variabel keputusan dari permasalahan program linear 1.2 Menentukan fungsi kendala dari permasalahan program linear 1.3 Menentukan fungsi tujuan dari permasalahan program linear Menentukan model matematika dari permsalahan pemrograman linear

MATERI A. DEFINISI PEMROGRAMAN LINEAR Suatu perusahaan atau organisasi harus membuat keputusan mengenai cara mengalokasikan sumber-sumbernya dan tidak ada organisasi yang beroperasi secara permanen dengan sumber yang tidak terbatas, akibatnya manajemen harus secara terus menerus mengalokasikan sumber langka untuk mencapai tujuan yang optimal. Tiap organisasi mencoba untuk mencapai tujuan tertentu sesuai dengan batasan sumber daya, seperti : bahan mentah, uang, waktu, tenaga, dll. Pemrograman Linear adalah metode optimasi untuk menentukan nilai optimum dari fungsi tujuan linear pada kondisi pembatasan-pembatasan (constrains) tertentu. Persoalan pemrograman linear dapat ditemukan pada berbagai bidang dan dapat digunakan untuk membantu membuat keputusan, memilih suatu alternatif yang paling tepat. Aplikasi program linear misalnya untuk keperluan : perencanaan produksi, produksi campuran, penjadwalan, relokasi sumber daya, masalah transportasi, dll.

B. MODEL PEMROGRAMAN LINEAR Bentuk umum model program linear adalah : Optimumkan : Z = c1x1 + c2x2 + ... + cnxn Dengan batasan : a11x1 + a12x2 + ... + a1nxn   b1 a21x1 + a22x2 + ... + a2nxn   b2 ⁞ ⁞ ⁞ ⁞ ⁞ am1x1 + am2x2 + ... + amnxn   bm x1, x2,... , xn  0 Terminologi umum untuk model program linear di atas adalah : 1. Fungsi yang akan dicari nilai optimumnya (Z) disebut fungsi tujuan (objective function) 2. Fungsi batasan (constrains) yang dikelompokkan menjadi dua, yaitu : a. Fungsi batasan fungsional, yaitu fungsi-fungsi batasan sebanyak m. b. Fungsi batasan non-negatif (non-negative constrains)

3. 4.

Variabel keputusan (decision variables) Parameter model

C. PERSOALAN PEMROGRAMAN LINEAR Persoalan pemrograman linear adalah persoalan optimasi yang memenuhi ketentuan sebagai berikut : 1. Fungsi tujuan merupakan fungsi linear dari variable keputusan. 2. Nilai variabel keputusan harus memenuhi pembatasan-pembatasan yang berbentuk persamaan atau ketaksamaan. 3. Setiap variabel keputusan harus dibatasi yaitu non negatif. Model adalah sebuah tiruan terhadap realitas. Langkah yang dilakukan untuk membuat peralihan dari realita ke model kuantitatif disebut perumusan model. Ada beberapa tahap dalam memformulasikan persoalan pemrograman linear ke model kuantitatif, yaitu : 1. Mengidentifikasi variabel keputusan 2. Mendeskripsikan fungsi tujuan sebagai kombinasi linear dari variabel keputusan 3. Mendeskripsikan pembatasan-pembatasan sebagai kombinasi linear dari variabel keputusan 4. Mengidentifikasi batas bawah atau batas atas dari variabel keputusan 5. Mengekspresikan semua hasil identifikasi tersebut dalam model kuantitatif

Contoh 1.1 : Sebuah perusahaan memproduksi sofa, meja dan kursi. Sumber daya untuk produksi tersebut adalah kayu, bahan pelapis, dan waktu produksi. Sumber daya yang dibutuhkan untuk pembuatan tiap unit barang per minggunya ditunjukkan sebagai berikut : Jenis Produk

Kebutuhan sumber daya Kayu (lembar)

Pelapis (m)

Waktu kerja (jam)

Sofa

7

12

6

Meja

5

-

9

Kursi

4

7

5

Sumber daya tersedia

1400

840

540

Pembuatan produk dibatasi perminggunya 500 buah karena keterbatasan tempat penyimpanan. Laba masing-masing produk per unit adalah Rp. 50.000,00 untuk sofa, Rp. 25.000,00 untuk meja dan Rp. 40.000,00 untuk kursi. Perusahaan ingin mengetahui berapa banyak masing-masing produk harus dibuat agar mencapai laba maksimum. Tentukan model matematikanya!

Penyelesaian : 

Variabel keputusan

:



Fungsi tujuan (Z)

:



Fungsi pembatas

:

 

Batas variabel keputusan Model matematisnya Tentukan nilai a, b, c 

: :

METODE PEMBELAJARAN Learning Cell

a = banyak produksi sofa b = banyak produksi meja c = banyak produksi kursi Memaksimumkan laba Memaksimumkan Z = 50.000a + 25.000b + 40.000c 7a + 5b + 4c  1400 (keterbatasan kayu) 12a + 7b  840 (keterbatasan pelapis) 6a+ 9b + 5c  540 (keterbatasan waktu) a + b + c  500 (keterbatasan tempat penyimpanan) a, b, c  0 Memaksimumkan : Dengan pembatas :

Z = 50.000a + 25.000b + 40.000c 7a + 5b + 4c  1400 12a + 7b  840 6a+ 9b + 5c  540 a + b + c  500 a, b, c  0

LANGKAH PEMBELAJARAN No.

Tahap

1.

Pendahuluan

2.

Penyajian

Kegiatan Pembelajaran a. Apersepsi Memberi gambaran tentang permasalahan program linear b. Motivasi Memberikan gambaran tentang permasalahan program linear dalam kehidupan sehari-hari

Eksplorasi a. Memberikan permasalahan program linear kemudian menjelaskan tentang penentuan variabel keputusan, fungsi kendala dan fungsi tujuan. b. Membentuk siswa dalam beberapa kelompok

Elaborasi a. Memberikan lembar kerja kepada setiap kelompok yang berisi contoh permasalahan. b. Setiap kelompok dibagi lagi menjadi 2 grup. Setiap grup menuliskan pertanyaan berkaitan dengan materi. c. Pada kesempatan pertama, grup I bertugas sebagai penanya dan grup II menjawab pertanyaan. Setelah itu, bergantian grup II bertanya, dan grup I menjawab.

Alokasi Waktu 10 menit 15 menit 15 menit 10 menit 5 menit 10 menit 30 menit

Eksplanasi Menunjuk perwakilan dari setiap kelompok untuk menyampaikan hasil diskusinya, untuk kemudian dibahas secara klasikal. 3.

Penutup

Refleksi dan Evaluasi Secara individu, mahasiswa diminta membuat satu permasalahan program linear kemudian membentuknya dalam model matematika

25 menit 30 menit

MEDIA PEMBELAJARAN Whiteboard, LCD, Laptop

SUMBER BELAJAR [1] [2] [3] [4]

Aminudin . 2005 . Prinsip–prinsip Riset Operasi . Jakarta : Erlangga Ruminta . 2009 . Matriks, Persamaan Linear dan Pemorograman Linear . Bandung : Rekayasa Sains Siswanto . 2006 . Operations Research Jilid I . Jakarta : Erlangga Handout Kuliah

PENILAIAN 1. 2.

Teknik : Bentuk Instrumen :

Hasil diskusi, keaktifan dalam diskusi, hasil post-test Tes Uraian


: : : :



: : : : : :


: :

Tujuan

:

PROGRAM LINEAR MKK206515 3 SKS II 2 Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode 2. Menyelesaikan permasalahan program linear dengan metode grafik 2.1 Menentukan daerah layak (feasible region) dari permasalahan program linear. Menentukan daerah feasible dari permalsalahan program linear

MATERI PENYELESAIAN PERMASALAHAN PROGRAM LINEAR DAERAH LAYAK (FEASIBLE REGION) Pada setiap kasus pemrograman linear, susunan dari kendala-kendala akan membentuk suatu bidang yang menjadi tempat kedudukan bagi variabel-variabel yang memenuhi seluruh kendala. Fungsi Pembatasnya : a – b  1 (i) 3a + 2b  12 (ii)

a7 b6

(i)

(iii) (iv)

b3

(v)

(ii)

b

b 6

1 -1

(iii)

a

4

(iv) dan (V)

b

a

b 6

3

7

a

a Gambar 1.1

Jika keempat daerah tersebut dijadikan satu bidang kemudian dicari irisannya diperoleh :

6

3 1 -1

4

7

Gambar 1.2 Masing-masing kendala pertidaksamaan di atas menjangkau suatu bidang penyelesaian dimana variabel-variabel keputusan memenuhi fungsi-fungsi matematikanya. Perpotongan antara bidang penyelesaian dari masing-masing kendala membentuk suatu bidang baru yang dinamakan dengan daerah layak (feasible region). Oleh karena itu, penyelesaian optimum, yaitu variabel-variabel keputusan yang memenuhi seluruh kendala dan mengakibatkan fungsi tujuan bernilai ekstrim, pasti terletak pada daerah layak.



Tahap

1.

Pendahuluan

2.

Penyajian

Kegiatan Pembelajaran a. Apersepsi Memberikan permasalahan program linear kemudian menjelaskan tentang penentuan variabel keputusan, fungsi kendala dan fungsi tujuan b. Motivasi Memberikan gambaran tentang permasalahan program linear dalam kehidupan sehari-hari

Eksplorasi a. Memberikan permasalahan program linear kemudian meminta mahasiswa menjelaskan tentang penentuan variabel keputusan, fungsi kendala dan fungsi tujuan. b. Membentuk siswa dalam beberapa kelompok

Elaborasi a. Memberikan lembar kerja kepada setiap kelompok yang berisi contoh permasalahan penetuan daerah feasible. b. Setiap kelompok dibagi lagi menjadi 2 grup. Setiap grup menuliskan pertanyaan berkaitan dengan materi. c. Pada kesempatan pertama, grup I bertugas sebagai penanya dan grup II menjawab pertanyaan. Setelah itu, bergantian grup II bertanya, dan grup I menjawab.

Alokasi Waktu 10 menit 15 menit

15 menit 10 menit 5 menit 10 menit 30 menit


Penutup

Refleksi dan Evaluasi Secara individu, mahasiswa diminta membuat satu permasalahan program linear kemudian membentuknya dalam model matematika


25 menit 30 menit



PENILAIAN 1. 2.




: : : :



: : : : : :


: :

Tujuan

:

PROGRAM LINEAR MKK206515 3 SKS II 3 Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode 2. Menyelesaikan permasalahan program linear dengan metode grafik 2.2 Menentukan nilai optimum permasalahan program linear dengan metode grafik menggunakan isoline. 2.2.1 Menentukan penyelesaian basis awal yang feasible. 2.2.2 Menggunakan bantuan isoline untuk mengevaluasi optimasi nilai fungsi tujuan

MATERI METODE GRAFIK DENGAN ISOLINE Ada dua cara untuk menentukan solusi optimum pada daerah layak (feasible region) dengan metode grafik. Teknik yang pertama adalah dengan teknik kesamaan garis (isoline). Langkah yang dilakukan untuk menentukan solusi optimum dengan teknik isoline adalah : 1. Tentukan kemiringan garis fungsi tujuan (merupakan himpunan infinitif dari isoline)  Pilihlah titik tertentu pada daerah layak  Gambarkan garis fungsi tujuan yang mengenai titik tersebut 2. Tentukan arah peningkatan/penurunan dari fungsi tujuan persoalan maksimum/minimum. Pilih dua garis (isoline) fungsi tujuan di daerah layak dan evaluasi nilai fungsi tujuan pada kedua garis isoline. 3. Ikuti arah peningkatan/penurunan sampai mencapai titik batas (sudut) dimana peningkatan/penurunan dari fungsi tujuan keluar dari daerah layak. 4. Solusi optimum diperoleh dari titik batas dimana peningkatan atau penurunan dari fungsi tujuan akan meninggalkan daerah layak. Contoh 1.3 Untuk mengetahui proses penentuan solusi optimum dari suatu permasalahan program linear menggunakan metode grafik dengan teknik isoline, lebih jelasnya perhatikan gambar berikut.

Z4 (Solusi Optimum)

Z2

 Maksimum

Z3 Z4

Z3 (Solusi Optimum)  Minimum

Z1


No.

Tahap

1.

Pendahuluan

2.

3.

Penyajian

Penutup

Kegiatan Pembelajaran a. Apersepsi Memberi permasalahan program linear kemudian menentukan daerah layaknya serta memberikan gambaran penggunaannya dalam menentukan nilai optimum fungsi b. Motivasi Memberikan gambaran tentang kaitan titik ekstrim dan daerah layak dari sistem pertidaksamaan linear untuk penentuan nilai optimum dari permasalahan program linear Eksplorasi a. Memberikan permasalahan program linear kemudian meminta mahasiswa membentuk dalam model matematis, yang meliputi penentuan variabel keputusan, fungsi kendala dan fungsi tujuan. b. Membentuk siswa dalam beberapa kelompok Elaborasi d. Memberikan lembar kerja kepada setiap kelompok yang berisi contoh permasalahan beserta langkah pemecahannya dengan metode titik ekstrim menggunakan isoline. e. Setiap kelompok dibagi lagi menjadi 2 grup. Setiap grup menuliskan pertanyaan berkaitan dengan materi. f. Pada kesempatan pertama, grup I bertugas sebagai penanya dan grup II menjawab pertanyaan. Setelah itu, bergantian grup II bertanya, dan grup I menjawab. Eksplanasi Menunjuk perwakilan dari setiap kelompok untuk menyampaikan hasil diskusinya, untuk kemudian dibahas secara klasikal. Refleksi dan Evaluasi Secara individu, mahasiswa diminta membuat satu permasalahan program linear kemudian di selesaikan sendiri dengan metode grafik menggunakan isoline.

Alokasi Waktu 15 menit

10 menit

15 menit 10 menit 5 menit 10 menit 30 menit

25 menit 30 menit




PENILAIAN 1. 2.




: : : :



: : : : : :


: :

Tujuan

:

PROGRAM LINEAR MKK206515 3 SKS II 4 Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode 2. Menyelesaikan permasalahan program linear dengan metode grafik 2.3 Menentukan nilai optimum permasalahan program linear menggunakan metode grafik dengan menentukan titik ekstrim. Menggunakan bantuan titik ekstrim untuk mengevaluasi optimasi nilai fungsi tujuan

MATERI METODE GRAFIK DENGAN BANTUAN TITIK EKSTRIM Teknik kedua untuk menentukan solusi optimum pada daerah layak (feasible region) dengan metode grafik adalah titik ekstrim. Titik ekstrim merupakan titik-titik sudut pada daerah layak. Nilai ekstrim dari fungsi tujuan pasti terletak pada salah satu titik ekstrim. Langkah yang dilakukan untuk menentukan solusi optimum dengan teknik titik ekstrim adalah : 1. Tentukan irisan (intersection) daerah penyelesaian dari semua fungsi kendala, sehingga diperoleh daerah layak (feasible region). 2. Tentukan tiitik ekstrim (titik sudut) dari daerah layak. 3. Evaluasi nilai fungsi tujuan pada setiap titik ekstrim daerah layak. Solusi optimum terletak pada salah satu titik ekstrim daerah layak. 4. Tentukan nilai optimumnya, dengan aturan: nilai terbesar dari evaluasi pada langkah 3 menjadi nilai maksimum, dan nilai terkecilnya menjadi nilai minimum Contoh 1.4 Untuk mengetahui proses penentuan solusi optimum dari suatu permasalahan program linear menggunakan metode grafik dengan teknik isoline, lebih jelasnya perhatikan gambar berikut.

C B

O

A

Jika fungsi tujuan dari permasalahan diatas adalah Z, setelah ditentukan koordinat titik O, A, B, dan C, maka selanjutnya eveluasi nilai Z di setiap titik tersebut. Tentukan Z O, ZA, ZB, dan ZC.  Nilai maksimum = maks (ZO, ZA, ZB, ZC)  Nilai minimum = min (ZO, ZA, ZB, ZC)

METODE PEMBELAJARAN Kelompok belajar (The Study Group)


Tahap

Kegiatan Pembelajaran

1.

Pendahuluan

a. Apersepsi Memberi permasalahan program linear kemudian menentukan daerah layaknya serta memberikan gambaran penggunaannya dalam menentukan nilai optimum fungsi b. Motivasi Memberikan gambaran tentang kaitan titik ekstrim dan daerah layak dari sistem pertidaksamaan linear untuk penentuan nilai optimum dari permasalahan program linear

2.

Penyajian

Eksplorasi a. Memberikan berbagai permasalahan program linear yang memuat kejadian khusus berikut : b. Membentuk siswa dalam beberapa kelompok

Elaborasi Setiap kelompok diminta menentukan nilai optimum dari berbagai permasalahan pemrograman linear.


5 menit 10 menit 50 menit


Penutup

Refleksi dan Evaluasi Secara individu, mahasiswa diminta membuat satu permasalahan program linear kemudian di selesaikan sendiri dengan metode grafik menggunakan titik ekstrim.

50 menit 20 menit




PENILAIAN 1. 2.




: : : :



: : : : : :


: :

Tujuan

:

PROGRAM LINEAR MKK206515 3 SKS II 5 Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode 2. Menyelesaikan permasalahan program linear dengan metode grafik 2.4 Menentukan nilai optimum dari kejadian khusus yang muncul saat optimasi dengan metode grafik. 2.4.1 Mengidentifikasi ciri kasus degenerasi 2.4.2 Mengidentifikasi ciri kasus optimal alternatif 2.4.3 Mengidentifikasi ciri kasus penyelesaian tidak terbatas 2.4.4 Mengidentifikasi ciri kasus penyelesaian tidak feasible

MATERI KEJADIAN KHUSUS PADA METODE GRAFIK Permasalahan program linear terkadang ada yang memiliki lebih dari satu penyelesaian, atau memiliki penyelesaian yang nilainya tidak terbatas, bahkan ada permasalahan yang tidak dapat dicari penyelesaiannya. Berikut akan dibahas berbagai kejadian khusus yang dapat muncul saat optimasi fungsi tujuan dengan menggunakan metode grafik. 1.

Degenerasi Satu titik terbentuk dari perpotongan antara dua buah garis. Apabila terjadi perpotongan tiga garis melalui satu titik maka kejadian ini disebut dengan over determined. Over deternimed inilah yang menyebabkan salah satu kejadian khusus pada metode grafik, yaitu degenerasi. Dengan alasan ini dapat dikatakan bahwa terdapat satu batasan yang melimpah atau berlebih. Batasan yang seperti ini dinamakan dengan batasan redundan (redundant constarins).

2.

Optimal Alternatif Dalam kejadian ini terdapat beberapa alternatif penyelesaian optimal pada suatu permasalahan. Hal ini terjadi apabila fungsi tujuan sejajar dengan fungsi batasan pembentuk penyelesaian optimal. Akibatnya, fungsi tujuanakan bernilai optimal sama pada lebih dari satu titik penyelesaian.

3.

Penyelesaian tidak feasible Suatu model pemrograman linear dikatakan memiliki penyelesaian tak feasible apabila fungsi-fungsi batasan dalam model tersebut tidak dapat dipenuhi secara simultan. Dengan kata lain, Interseksi dari semua fungsi batasan yang ada tidak dapat ditemukan.

4.

Penyelesaian tidak terbatas Pada model masalaah program linear ada beberapa model dimana variabel-variabel tersebut dapat dinaikkan sampai tak terhingga tanpa melanggar fungsi batasan. Hal ini berarti ruang penyelesaian atau daerah penyelesaian dari permasalahan pemrograman linear tersebut tidak terbatas. Akibatnya, nilai fungsi tujuan dalam kasus memaksimumkan dapat naik sampai tak terhingga. Melihat kejadian

ini dikatakan bahwa permasalahan pemrograman linear tersebut memiliki daerah penyelesaian yang tak terbatas dan nilai fungsi tujuannya pun tidak terbatas.



Tahap

1.

Pendahuluan


Apersepsi dan Motivasi


Memberikan gambaran tentang kejadian khusus permasalahan program linear, karena kemungkinan ada permasalahan yang tidak memiliki penyelesaian atau bahkan penyelesaiannya tidak tunggal. 2.

Penyajian

Eksplorasi a. Memberikan berbagai permasalahan program linear yang memuat kejadian khusus berikut : 1). Degenerasi 2). Optimal alternatif 3). Penyelesaian tidak terbatas 4). Penyelesaian tidak layak b. Membentuk siswa dalam beberapa kelompok


5 menit

10 menit 50 menit


Penutup

Refleksi dan Evaluasi Secara individu, mahasiswa diminta membuat satu permasalahan program linear kemudian di selesaikan sendiri dengan metode grafik menggunakan titik ekstrim.

50 menit 20 menit




PENILAIAN 1. 2.




: : : :



: : : : : :

Kompetensi Dasar Indikator Tujuan

: : :

PROGRAM LINEAR MKK206515 3 SKS II 7 Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode 3. Menyelesaikan permasalahan program linear dengan metode simpleks 3.1 Menentukan bentuk standar dari model matematika. Mengubah permasalahan pemrograman linear menjadi bentuk standar

MATERI PENDAHULUAN Apabila suatu persoalan program linear hanya mengandung dua variabel keputusan, maka untuk menentukan solusinya dapat dilakukan dengan metode grafik. Akan tetapi apabila permasalahan mengandung tiga variabel atau lebih, maka akan sangat sulit, bahkan tidak bisa dilakukan optimasi dengan metode grafik sehingga diperlukan metode lain untuk menentukan titik serta nilai optimumnya. Salah satu metode yang bisa digunakan adalah metode simpleks. Gagasan metode simpleks adalah menerjemahkan definisi geometris atau grafik dari titik ekstrim atau titik sudut menjadi definisi aljabar. Metode simpleks adalah suatu teknik penyelesaian pemrograman linear secara iterasi. Metode simpleks mencari suatu penyelesaian dasar yang feasible ke penyelesaian dasar feasible lainnya yang dilakukan secara berulang-ulang sehingga akhirnya tercapai suatu penyelesaian optimum. Setiap tahap penyelesaian menghasilkan nilai fungsi tujuanyang selalu lebih optimum atau sama dari tahap-tahap penyelesaian sebelumnya. Metode simpleks sangat sistematik dan dilengkapi test kriteria yang dapat memberitahukan kapan perhitungan harus dilanjutkan atau dihentikan sampai diperoleh solusi optimum.

BENTUK STANDAR MODEL PROGRAM LINEAR Pada metode simpleks permasalahan pemrograman linear selalu diubah menjadi bentuk standart (bentuk kanonik). Ciri dari bentuk kanonik adalah sebagai berikut : 1. Semua batasan atau kendala adalah persamaan dengan sisi kanan yang non negatif. 2. Semua variabel keputusan adalah non negatif. 3. Fungsi tujuan dapat berupa maksimasi dan minimasi. Secara umum bentuk kanonik dari permasalahan program linear adalah sebagai berikut : Optimumkan : Z = c1x1 + c2x2 + ... + cnxn Dengan batasan : a11x1 + a12x2 + ... + a1nxn = b1 a21x1 + a22x2 + ... + a2nxn = b2 ⁞ ⁞ ⁞ ⁞ ⁞ am1x1 + am2x2 + ... + amnxn = bm x1, x2,... , xn  0 b1, b2,... , bm  0

Berikut ini adalah cara pengubahan dari masalah program linear ke dalam bentuk kanonik. No 1

Tinjauan Fungsi Batasan

Cara Pengubahan ke Bentuk Kanonik Fungsi batasan berupa pertidaksamaan dengan tanda  Tambahkan variabel slack pada ruas kiri. Variabel slack biasa disimbolkan dengan S dengan S  0. Contoh : 3a + 2b  36 dengan a, b  0 Bentuk kanoniknya menjadi 3a + 2b + S = 36 dengan a, b, S 0

Fungsi batasan berupa pertidaksamaan dengan tanda  Tambahkan variabel slack pada ruas kiri. Variabel surplus biasa disimbolkan dengan S dengan S  0. Contoh : 3a + 2b  36 dengan a, b  0 Bentuk kanoniknya menjadi 3a + 2b  S = 36 dengan a, b, S 0 Fungsi batasan dengan nilai kanan negatif Mengalikan masing-masing sisi dari fungsi batasan dengan 1. Contoh : 3a + 2b  12 dengan a, b  0 3a + 2b + S = 12 dengan a, b, S  0 Bentuk kanoniknya menjadi 3a  2b  S = 12 dengan a, b, S  0 2

Variabel Keputusan

Variabel yang tidak dibatasi tanda Misalkan ada variabel x yang nilainya tidak dibatasi, maka x harus disubstitusi dengan x1 – x2 dengan x1, x2  0. Substitusi ini menyebabkan perubahan pada fungsi tujuan dan fungsi batasannya.

3

Fungsi Tujuan

Catatan :  

Sisi kanan dari fungsi tujuan dibuat nol (0) Bentuk memaksimumkan fungsi tujuan ekuivalen dengan meminimumkan negatif dari fungsi tujuan tersebut.



Tahap

1.

Pendahuluan


Apersepsi dan Motivasi Memberikan gambaran tentang kelemahan metode grafik, yang dapat diselesaikan dengan metode simpleks

2.

Penyajian

Eksplorasi a. Memberikan sebuah contoh permasalahan program linear, dan meminta siswa mengidentifikasi cara mengubahnya kedalam bentuk standar. b. Memberikan beberapa permasalahan program linear dan membentuk siswa dalam beberapa kelompok

Elaborasi Setiap kelompok diminta menentukan bentuk standar dari berbagai permasalahan pemrograman linear berikut. 1. Memaksimumkan : Z = 8p + 6q Terhadap batasan : 4p + 3q  18 6p + 5q  30 2p + q  8 p, q  0 2. Meminimumkan : P = 3x + 2y + 4z Terhadap batasan : x + y – z  12 2x + y  3 x, z  0, y tidak dibatasi

Alokasi Waktu 15 menit 15 menit 10 menit 40 menit

50 menit

3.

Meminimumkan Terhadap batasan

: :

W = 6a + 5b + 2c 3a + 2b + 5c  30 2a + 7b  28 3a  5c  15 a, b  0, c tidak dibatasi


Penutup

Refleksi dan Evaluasi Secara individu, mahasiswa diminta membuat dua buah permasalahan program linear kemudian mengubahnya ke dalam bentu standar.

20 menit




PENILAIAN 1. 2.




: : : :



: : : : : :


: :

Tujuan

:

PROGRAM LINEAR MKK206515 3 SKS II 8 Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode 3. Menyelesaikan permasalahan program linear dengan metode simpleks 3.2 Menentukan nilai optimum permasalahan program linear dengan metode simpleks. Menentukan penyelesaian permasalahan pemrograman linear dengan metode simpleks

MATERI KONSEP DASAR METODE SIMPLEKS Konsep dasar metode simpleks bertolak dari konsep dasar metode grafik, yaitu penyelesaian optimum terjadi pada titik ekstrim. Metode simpleks dalam bekerja menggunakan proses iterasi dimulai dari titik ekstrim feasible awal ke titik ke titik ekstrim feasible lain yang terhubung (adjecent), dan iterasi akan berhenti jika penyelesaian optimal telah diperoleh. Perhatikan contoh permasalahan program linear dan penyelesaiannya dengan metode grafik berikut ini: Memaksimumkan Terhadap batasan

: :

Z = 3a + 5b 2a  6 3b  15 6a + 4b  24 a, b  0

D C

B O

A

Algoritma simpleks dimulai dari titik feasible awal (misalkan titik asal O) dan akan menghasilkan penyelesaian awal. Kemudian iterasi dilanjutkan ke titik ekstrim lain yang terhubung dengan O. Dalam permasalahan ini ada dua kemungkinan titik ekstrim yang terhubung dengan O yaitu titik A dan D. Untuk menentukan titik mana yang terpilih untuk iterasi selanjutnya dapat dilihat dari koefisien-koefisien pada fungsi tujuannya. Jika koefisien a  b dan masalahnya memaksimumkan maka penyelesaian akan bergerak sejalan dengan kenaikan b. Jadi,iterasi selanjutnya terjadi di titik D. Di titik D ini proses diulang untuk melihat apakah ada titik ekstrim lain yang dapat memperbaiki nilai fungsi tujuan. Demikian seterusnya sehingga diperoleh nilai optimum. Cara penentuan titik awal feasible pada metode simpleks adalah sebagai berikut : 

Ubah permasalahan program linear kedalam bentuk kanonik.





A.

Misal permasalahan tersebut terdiri atas n buah variabel dan m buah fungsi batasan, titik ekstrim feasible awal ditentukan dengan terlebih dahulu mengambil sebanyak (n – m) variabel yang disamadengankan nol, dan disebut sebagai variabel non basis. Variabel selain variabel non basis, disebut sebagai variabel basis. Penyelesaian tunggal yang dihasilkan dengan menetukan variabel basis, disebut dengan penyelesaian basis. Untuk dapat menyelesaikan dengan metode simpleks penyelesaian basis awal yang diperoleh harus merupakan penyelesaian basis awal yang feasible, yang memenuhi syarat non negatif.

ALGORITMA SIMPLEKS

Berikut ini merupakan algoritma penyelesaian permasalahan pemrograman linear dengan menggunakan Metode Simpleks.

1.

Langkah 1 : Ubah permasalahan menjadi bentuk kanonik.

2.

Langkah 2 : Tentukan variabel basis dan variabel non basis dari bentuk kanonik persamaan linear untuk mencari penyelesaian basis awal yang feasible.

3.

Langkah 3 : Susun persamaan-persamaan ke dalam tablo simpleks. Berikut ini adalah cara menyusun bentuk kanonik kedalam tablo simpleks. Variabel Bais

Z

X1

X2

...

Xn

Xn+1

Xn+2

...

Xn+m

Nilai Kanan

Z Xn+1 Xn+2 ... Xn+m

1 0 0 ... 0

-c1 a11 a21 ... am1

-c2 a12 a22 ... am2

... ... ... ...

a1n a2n ... amn

0 1 0 ... 0

0 0 1 ... 0

... ... ... ... ...

0 0 0 ... 1

0 b1 b2 ... bm

Rasio

Keterangan :  Nilai kanan adalah nilai di belakang tanda sama dengan dan sering disebut sebagai penyelesaian.  Xn+1, Xn+2, ... , Xn+m merupakan simbol lain dari variabel slack yang biasa disimbolkan S 1, S2, ... , Sm.

4.

Langkah 4 : Memilih entering variable yang biasa disimbolkan dengan ev. Entering variable adalah variabel non basis yang masuk sebagai variabel basis pada iterasi berikutnya. Cara menentukan ev adalah :  Jika fungsi tujuan memaksimumkan Pilih nilai yang terletak pada baris fungsi tujuan yang memiliki nilai negatif dengan angka terbesar. Variabel yang memiliki koefisien nilai terpilih (variabel pada tablo terletak di atas nilai terpilih), ditentukan sebagai ev. Jika pada baris fungsi tujuan, semua koefisien sudah bernilai non negatif, maka penyelesaian selesai dan iterasi berhenti.  Jika fungsi tujuan meminimumkan Pilih nilai yang terletak pada baris fungsi tujuan yang memiliki nilai positif dengan angka terbesar. Variabel yang memiliki koefisien nilai terpilih (variabel pada tablo terletak di atas nilai terpilih), ditentukan sebagai ev. Jika pada baris fungsi tujuan, semua koefisien sudah bernilai non positif, maka penyelesaian selesai dan iterasi berhenti.

5.

Langkah 5: Memilih leaving variable yang biasa disimbolkan dengan lv. Leaving variable adalah variabel basis yang akan keluar menjadi variabel non basis pada iterasi berikutnya. Berikut adalah cara penentuan lv.



Baik untuk fungsi tujuan memaksimumkan dan meminimumkan lv. Dipilih diantara variabal basis yang memiliki nilai rasio terkecil. Rasio ditentukan dengan cara sebagai berikut : Rasio =

Nilai Kanan Elemen kolom ev



Hal yang perlu diperhatikan dalam mencari nilai rasio adalah sebagai berikut :  Baris fungsi tujuan tidak dicari nilai rasionya.  Jika elemen pada kolom ev nol atau negatif maka nilai rasio diabaikan. Baris yang memuat variabel yang terpilih sebagai lv disebut sebagai baris pivot. Irisan antara baris pivot dan kolom pivot disebut sebagai elemen pivot.

Langkah 6 :

6.

Memperbaiki nilai-nilai pada baris persamaan pivot, caranya : Nilai baris pivot baru =

7.

Nilai baris pivot lama Elemen pivot

Langkah 7 : Memperbaiki nilai pada baris lain selain baris pivot, dengan aturan : Nilai baris baru = nilai baris lama – (koefisien kolom ev  nilai baris pivot baru )

8.

Langkah 8 : Ulangi langkah 4 sampai dengan 8 sampai diperoleh penyelesaian optimal.

METODE PEMBELAJARAN Two Stay Two Stray dan Gallery of Learning


Tahap

1.

Pendahuluan


Apersepsi dan Motivasi Mengulas pengubahan permasalahan program linear menjadi bentuk standar

2.

Penyajian

Eksplorasi Memberi penjelasan tentang algoritma metode simpleks.

Elaborasi a. Memberikan permaslahan program linear b. Kegiatan Kelompok  Meminta mahasiswa secara berkelompok untuk menentukan penyelesaiannya menggunakan metode simpleks  Setiap kelompok menempelkan hasil diskusinya pada tempat yang telah disediakan. c. Diskusi antar kelompok  3 orang anggota kelompok diberi tugas untuk tetap berada di posisi semua untuk menjelaskan apabila ada pertanyaan atau koereksi yang nantinya diberikan kelompok lain.  3 orang yag lain ditugaskan untuk berkeliling dari satu kelompok ke kelompok yang lain untuk mengomentari dan bertanya pekerjaan kelompok lain.

Eksplanasi Diskusi kelas untuk membahas beberapa permasalahan yang sudah dibuat dikerjakan mahasiswa. 3.

Penutup

Refleksi dan Evaluasi Penarikan kesimpulan mengenai kelebihan metode simpleks.


Alokasi Waktu 10 menit 35 menit 5 menit 30 menit 5 menit 40 menit

20 menit

5 menit



PENILAIAN 1. 2.




: : : :



: : : : : :


: :

Tujuan

:

PROGRAM LINEAR MKK206515 3 SKS II 10 Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode 3. Menyelesaikan permasalahan program linear dengan metode simpleks 3.3 Menentukan nilai optimum permasalahan program linear dengan metode simpleks menggunakan teknik M. 3.3.1 Menetukan bentuk kanonik dari permasalahan dengan penyelesaian awal semu. 3.3.2 Menggunakan algoritma simpleks untuk menyelesaikan permasalahan yang mengandung variabel semu dengan metode simpleks teknik M.

MATERI PENYELESAIAN AWAL SEMU Perhatikan contoh permasalahan linear berikut : Permasalahan Program Linear Meminimumkan Terhadap batasan

: :

W = 6i + 15j + 24k 2i + 6k  3 3j + 4k  5 i, j, k  0

Bentuk Kanonik (1) (2)


: :

W  6i  15j  24k = 0 2i + 6k  S1 = 3 (1) 3j + 4k  S2 = 5 (2) i, j, k, S1, S2  0

Bentuk kanonik tersebut terdiri atas dua persamaan dan lima variabel tek diketahui. Sehingga untuk menentukan penyelesaian basis awal terlebih dahulu harus menentukan sebanyak n – m = 5 – 2 = 3 variabel non basis. Misalkan dipilih i = j = k = 0 maka diperoleh variabel basisnya adalah S 1, dan S2 dengan nilai S1 = -3 dan S2 = -5. Karena terdapat variabel basis yang nilainya negatif, berarti penyelesaian basis awal yang diperoleh merupakan penyelesaian basis awal yang tidak feasible. Untuk mengatasi hal tersebut maka pada bentuk kanonik untuk setiap persamaan yang tidak mengandung variabel slack ditambah variabel semu pada ruas kirinya. Variabel semu biasa disimbolkan R dengan R  0. Penambahan variabel ini diperlakukan seperti variabel slack maupun variabel surplus. Sebagai konsekuensi dari penggunaan variabel semu ini adalah penambahan sebesar MR pada ruas kanan fungsi tujuan yang meminimalkan dan adanya pengurangan sebesar MR pada ruas kanan fungsi tujuan yang memaksimalkan (M adalah bilangan positif yang sangat besar) Karena variabel semu tidak berarti pada masalah aslinya, maka prosedur akan valid hanya apabila pada saat optimasi, variabel semu ini bernilai nol. Dengan kata lain, variabel semua hanya digunakan pada awal penyelesaian dan sebagai konsekuensinya harus dinolkan pada penyelesaian akhirnya. Apabila ada variabel semu yang tidak sama dengan nol pada penyelesaian akhirnya berarti penyelesaian tersebut tidak feasible.

METODE PENALTI / TEKNIK M Metode ini merupakan salah satu metode yang dapat digunakan untuk menyelesaikan permasalahan program linear yang bentuk kanoniknya mengandung variabel semu.

Perhatikan contoh berikut. Permasalahan Program Linear Meminimumkan Terhadap batasan

: :

Bentuk Kanonik

W = 6i + 15j + 24k 2i + 6k  3 3j + 4k  5 i, j, k  0

Karena (1) 2i + 6k  S1 + R1 = 3  (2) 3j + 4k  S2 + R2 = 5 


(1) (2)

R1 = 3 – 2i – 6k + S1 R2 = 5 – 3j – 4k + S2

: :

W = 6i + 15j + 24k + M (R1 + R2) 2i + 6k  S1 + R1 = 3 (1) 3j + 4k  S2 + R2 = 5 (2) i, j, k, S1, S2, R1, R2  0

Maka R1 + R2 = 8 – 2i – 3j – 10k + S1 + S2

Sehingga bentuk kanoniknya menjadi : Meminimumkan : W = 6i + 15j + 24k + M (R1 + R2) = 6i + 15j + 24k + M (8 – 2i – 3j – 10k + S1 + S2) W = (6 – 2M)i + (15 – 3M)j + (24 – 10M)k + MS1 + MS2 + 8M W + (–6 + 2M)i + (–15 + 3M)j + (–24 + 10M)k – MS1 – MS2 = 8M Terhadap batasan : 2i + 6k  S1 + R1 = 3 3j + 4k  S2 + R2 = 5 i, j, k, S1, S2, R1, R2  0 Permasalahan tersebut memiliki 2 persamaan dengan 7 variabel yang tidak diketahui. Selanjutnya permasalahan ini diselesaikan dengan metode simpleks sebagai berikut : 

Mencari penyelesaian basis awal feasible. Ambil sebanyak 7 – 2 = 5 variabel non basis yaitu : i = j = k = S1 = S2 = 0. Akibatnya R1 = 3, R2 = 5 sebagai variabel basis. Hal ini menghasilkan nilai awal fungsi tujuan W = 8M.



Tablo Simpleks secara lengkap dari masalah tersebut adalah sebagai berikut : Ket

Var. Basis

W

I

Iterasi Awal

W

1

-6+2M

ev = k

R1

0

2

0

lv = R1

R2

0

0

3

Iterasi (1)

W

1

ev = j

k

0

1/3

lv = R2

R2

0

Iterasi (2)

W

1

Optimal

k j

j

k

S1

S2

R1

R2

-M

-M

0

0

8M

-

6

-1

0

1

0

3

1/2

4

0

-1

0

1

5

5/4

0

-4+(2M/3)

-M

4-(5M/3)

0

12+3M

-

0

1

-1/6

0

1/6

0

½

-

-4/3

3

0

2/3

-1

-2/3

1

3

1

-14/3

0

0

-2/3

-5

4/6 - M

5–M

27

0

1/3

0

1

-1/6

0

1/6

0

½

0

-4/9

1

0

2/9

-1/3

-2/9

1/3

1

-15+3M -24+10M

2-(4M/3) -15+3M

Nilai Kanan Rasio

Karena pada iterasi (2) semua nilai pada baris fungsi tujuan sudah non positif maka penyelesaian

 

optimal tercapai. Jadi permasalahan tersebut mencapai nilai optimal di titik (i, j, k) =  0, 1, Wmin = 27.

1

 dengan

2

METODE PEMBELAJARAN Two Stay Two Stray dan Gallery of Learning


Tahap

1.

Pendahuluan

2.

Penyajian


Apersepsi dan Motivasi

 Mengulas tentang metode simpleks Eksplorasi Memberi penjelasan tentang algoritma metode simpleks untuk


menyelesaiakan permasalahan yang penyelesaian awalnya semu.

Elaborasi a. Memberikan permaslahan program linear b. Kegiatan Kelompok  Meminta mahasiswa secara berkelompok untuk menentukan penyelesaiannya menggunakan metode simpleks teknik M.  Setiap kelompok menempelkan hasil diskusinya pada tempat yang telah disediakan. c. Diskusi antar kelompok  3 orang anggota kelompok diberi tugas untuk tetap berada di posisi semua untuk menjelaskan apabila ada pertanyaan atau koereksi yang nantinya diberikan kelompok lain.  3 orang yag lain ditugaskan untuk berkeliling dari satu kelompok ke kelompok yang lain untuk mengomentari dan bertanya pekerjaan kelompok lain.

Eksplanasi Diskusi kelas untuk membahas beberapa permasalahan yang sudah dibuat dikerjakan mahasiswa. 3.

Penutup

Refleksi dan Evaluasi Penarikan kesimpulan mengenai kejadian penyelesaian awal semu.

5 menit 30 menit 5 menit 40 menit

20 menit

5 menit




PENILAIAN 1. 2.




: : : :



: : : : : :


: :

Tujuan

:

PROGRAM LINEAR MKK206515 3 SKS II 11 Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode 3. Menyelesaikan permasalahan program linear dengan metode simpleks 3.4 Menentukan nilai optimum permasalahan program linear dengan metode simpleks Dua Tahap. 3.4.1 Menentukan prasyarat awal pemakaian metode dua tahap 3.4.2 Menentukan fungsi tujuan pada tahap I dan tahap II 3.4.3 Menentukan kriteria optimum pada tahap I dan tahap II 3.4.3 Menentukan nilai optimum dari permasalahan program linear

MATERI METODE SIMPLEKS DUA TAHAP Pemberian koefisien M pada variabel semu fungsi tujuan untuk metode penalti, ternyata menghambat sekali. Karena pemberian bilangan yang sangat besar tersebut akan mengurangi kecepatan perhitungan. Jika pada tablo optimal simpleks dari permasalahan yang mengandung variabel semu ternyata R tidak sama dengan nol, maka penyelesaian yang diperoleh adalah penyelesaian optimal yang tidak feasible. Untuk mengatasi hal tersebut maka dikembangkan metode dua tahap. Sesuai dengan namanya, cara kerjanya dibagi menjadi dua tahap. Tahap I bertujuan untuk mengetahui apakah R dalam suatu permasalahan dapat mencapai nilai nol atau tidak. Jika R mencapai nilai nol berarti penyelesaian optimal yang akan diperoleh pada tahap II merupakan penyelesaian optimal yang feasible. Jika R tidak nol berarti penyelesaian optimal yang akan diperoleh pada tahap II merupakan penyelesaian optimal yang tidak feasible. Jika hal ini terjadi maka tahap II pada metode dua tahap tidak perlu dikerjakan. Tahap II pada metode duan tahap bertujuan untuk mencari penyelesaian optimal dari permasalahan aslinya.

LANGKAH METODE DUA TAHAP Tahap I Mencari nilai minimal dari jumlah variabel-variabel semu terhadap fungsi batasan pada masalah aslinya. n

Meminimumkan r =

R i1

i

Jika rmin = 0 maka dilanjutkan ke tahap II Jika rmin > 0 maka tidak dilanjutkan ke tahap II

Tahap II Menggunakan penyelesaian basis optimal pada tahap I sebagai penyelesaian basis awal pada masalah aslinya. Untuk lebih jelasnya perhatikan conoth berikut.

Contoh Tahap I Permasalahan Program Linear Meminimumkan Terhadap batasan

: :

W = 6i + 15j + 24k 2i + 6k  3 3j + 4k  5 i, j, k  0

Bentuk Kanonik 2

(1) (2)

Meminimumkan

:

r=

R i1

Terhadap batasan

Karena (1) 2i + 6k  S1 + R1 = 3  R1 = 3 – 2i – 6k + S1 (2) 3j + 4k  S2 + R2 = 5  R2 = 5 – 3j – 4k + S2 Sehingga bentuk kanoniknya menjadi :

:

i

2i + 6k  S1 + R1 = 3 3j + 4k  S2 + R2 = 5 i, j, k, S1, S2, R1, R2  0

(1) (2)

Maka R1 + R2 = 8 – 2i – 3j – 10k + S1 + S2

2

Meminimumkan : r =

R i1

i

= 8 – 2i – 3j – 10k + S1 + S2

r + 2i + 3j + 10k – S1 – S2 = 8 Terhadap batasan : 2i + 6k  S1 + R1 = 3 3j + 4k  S2 + R2 = 5 i, j, k, S1, S2, R1, R2  0 Permasalahan tersebut memiliki 2 persamaan dengan 7 variabel yang tidak diketahui. Selanjutnya permasalahan tahap I ini diselesaikan dengan metode simpleks sebagai berikut : 

Mencari penyelesaian basis awal feasible. Ambil sebanyak 7 – 2 = 5 variabel non basis yaitu : i = j = k = S 1 = S2 = 0. Akibatnya R1 = 3, R2 = 5 sebagai variabel basis. Hal ini menghasilkan nilai awal fungsi tujuan r = 8.



Tablo Simpleks secara lengkap dari masalah tersebut adalah sebagai berikut : Keterangan

Var. Basis

R

i

j

K

S1

S2

R1

R2

Nilai Kanan

Rasio

Iterasi Awal

r

1

2

3

10

-1

-1

0

0

8

-

ev = k

R1

0

2

0

6

-1

0

1

0

3

1/2

lv = R1

R2

0

0

3

4

0

-1

0

1

5

5/4

Iterasi (1)

r

1

-4/3

3

0

2/3

-1

-5/3

0

3

-

ev = j

K

0

1/3

0

1

-1/6

0

1/6

0

1/2

-

lv = R2

R2

0

-4/3

3

0

2/3

-1

-2/3

1

3

1

Iterasi (2)

r

1

0

0

0

-5/3

0

-1

-1

0

Optimal

k

0

1/3

0

1

-1/6

0

1/6

0

1/2

j

0

-4/9

1

0

2/9

-1/3

-2/9

1/3

1

Karena pada iterasi (2) semua nilai pada baris fungsi tujuan sudah non positif maka penyelesaian optimal tercapai. Berdasarkan iterasi pada tahap I diperoelh bahwa r min = 0 berarti masalah tersebut memiliki penyelesaian yang feasible dan dapat dilanjutkan pada tahap II.

TAHAP II Karena rmin = 0 berarti R1 = R2 = 0 sehingga variabel-variabel semu pada perhitungan tahap II dapat diabaikan. Sehingga tablo optimal tahap I dapat ditulis dalam bentuk persamaan menjadi : 1 4 1 1 1 2 i + k – S1 = (1) dan  i + j + S1  S2 = 1 (2) 6 9 9 3 3 2 Sehingga permasalahan pada tahap II menjadi : Meminimumkan : W = 6i + 15j + 24k

1

Terhadap batasan :

i+k–

1

S1 =

1

6 2

3 4

2 1  i + j + S1  S2 = 1 9 9 3 i, j, k, S1, S2  0

Permasalahan tersebut memiliki 2 persamaan dengan 5 variabel yang tidak diketahui. Selanjutnya permasalahan ini diselesaikan dengan metode simpleks sebagai berikut : 

Mencari penyelesaian basis awal feasible. Pada tahap II ini penyelesaian basis awal feasible telah diperoleh dari tablo optimal permasalahan pada tahap I. Jadi dari tablo optimal permasalahan tahap I diperoleh bahwa : 1 1 1 1 1 1 (1) i + k – S1 =  k = – i + S1 6 6 3 2 2 3 4 4 1 1 2 2 (2)  i + j + S1 – S2 = 1  j = 1 + i – S1 + S2 9 9 9 9 3 3 1 4 2 1 1 1 Sehingga penyelesaian basis awal tahap II terjadi pada saat : k = – i + S1 dan j = 1 + i– S1 + S2 6 9 9 2 3 3 dengan : W = 6i + 15j + 24

 

 W = 6i + 15  1 + W =  W 

14

2

i+

3

14 3

4 9

i-

1  1 1 1  S1 + S2  + 24  - i  S1  9 3  2 3 6  2

S1 +5S2 + 27

3

i

2 3

S1 5S2 = 27


Variabel Basis

W

i

j

k

S1

S2

Nilai Kanan

Iterasi awal

W

1

-14/3

0

0

-2/3

-5

27

(0)

k

0

1/3

0

1

-1/6

0

1/2

Optimum

j

0

-4/9

1

0

2/9

-1/3

1

Rasio

Karena pada iterasi awal (0) semua nilai pada baris fungsi tujuan sudah non positif maka penyelesaian optimal telah tercapai. Jadi permasalahan tersebut mencapai nilai optimal di titik (i, j, k)

 

=  0, 1,

1

 dengan nilai Wmin = 27.

2

METODE PEMBELAJARAN Practice Rehearsal Pairs


Tahap

1.

Pendahuluan

Kegiatan Pembelajaran a. Apersepsi Mengulas kembali tentang metode penalti. b. Motivasi 1. Memberikan permasalahan program linear yang penyelesaian awalnya semu 2. Mengungkapkan kesulitasn yang dialami pada saat menyelesaikan permasalahan program linear dengan metode penalti


2.

Penyajian

3. Memberikan wawasan tentang metode dua tahap sebagai salah satu alternatif untuk menyelesaikan permasalahan program linear Eksplorasi Memberi penjelasan tentang metode simpleks dua tahap untuk menyelesaiakan permasalahan yang penyelesaian awalnya semu. Elaborasi a. Memberikan permaslahan program linear yang penyelesaian awalnya semu. b. Meminta mahasiswa berkelompok. c. Setiap kelompok dibagi menjadi dua tim, dan setiap tim harus menyelesaiakan permassalahan meggunakan metode simpleks dua tahap dan menjawab pertanyaan yang ada pada LKM. d. Setelah selesai, salah satu tim diminta menjelaskan kepada tim yang lain. Pada tahap berikutnya kedua tim bertukar peran. Eksplanasi Dosen memberikan beberapa pertanyaan kepada siswa tentang konsep yang harus dipahami mahasiswa.

10 menit

5 menit 5 menit 30 menit

30 menit

15 menit 3.

Penutup

Refleksi dan Evaluasi Menyimpulkan apa yang dipelajari secara klasikal, yang menyangkut : a. Penentuan prasyarat awal pemakaian metode dua tahap b. Penentuan fungsi tujuan pada tahap I dan tahap II c. Penentuan kriteria optimum pada tahap I dan tahap II d. Penentuan nilai optimum dari permasalahan program linear

10 menit




PENILAIAN 1. 2.




: : : :



: : : : : :

Kompetensi Dasar Indikator Tujuan

: : :

PROGRAM LINEAR MKK206515 3 SKS II 12 Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode 3. Menyelesaikan permasalahan program linear dengan metode simpleks 3.5 Melakukan Interpretasi terhadap Tablo Optimal Simpleks 3.5.1 Menentukan penyelesaian optimal dari tablo optimal simpleks 3.5.2 Menentukan bobot satuan pada tablo optimal simpleks 3.5.3 Menentukan status sumber pada tablo optimal simpleks

MATERI INTERPRETASI TABLO OPTIMAL SIMPLEKS Dalam suatu tablo optimal simpleks terdapat beberapa informasi penting yang dapat digunakan sebagai bahan pertimbangan dalam meningkatkan nilai keoptimalan fungsi tujuan. Informasi penting tersebut meliputi : 1. Penyelesaian optimal 2. Status sumber 3. Bobot satuan (unit worth) suatu sumber Contoh 2.5 Sebuah industri rumah tangga memproduksi dua jenis roti, yaitu roti jenis A dan B dengan bahan dasar berupa terigu, keju dan daging. Kebutuhan dasar utama per unit produksi dan batas maksimum persediaan bahan dasar utama untuk satu masa produksi serta laba dari penjualan kue tertera pada tabel berikut : Jenis Kue

Bahan Dasar Utama

A

B

Persediaan Maksimum

Terigu

12

8

52

Kg

Keju

0

6

30

ons

Daging

4

0

12

ons

Laba

6

10

Satuan

Ratusan Rupiah

Permasalahan tersebut dapat diubah ke dalam bentuk matematis menjadi : Permasalahan Program Linear Memaksimumkan Terhadap batasan

: :

P = 6a + 10b 12a + 8b  52 6b  30 4a  12 a, b  0

Bentuk Kanonik (1) (2) (3)

Memaksimumkan Terhadap batasan

: :

P – 6a – 10b = 0 12a + 8b + S1 = 52 6b + S2 = 30 4a + S3 = 12 a, b, S1, S2, S3  0

(1) (2) (3)

Apabila permasalahan tersebut diselesaikan dengan metode simpleks, maka diperoleh tablo simpleks berikut :

Keterangan

Variabel Basis

P

a

b

S1

S2

S3

Nilai Kanan

Rasio

Iterasi Awal

P

1

-6

-10

0

0

0

0

-

0

S1

0

12

8

1

0

0

52

13/2

ev = b

S2

0

0

6

0

1

0

30

5

lv = S2

S3

0

4

0

0

0

1

12

-

Iterasi

P

1

-6

0

0

5/3

0

50

-

(1)

S1

0

12

0

1

4/3

0

12

1

ev = a

b

0

0

1

0

1/6

0

5

-

lv = S1

S3

0

4

0

0

0

1

12

3

Iterasi

P

1

0

0

1/2

1

0

56

(2)

a

0

1

0

1/12

-1/9

0

1

b

0

0

1

0

1/6

0

5

S3

0

0

0

-1/3

4/9

1

28/3

Optimal

PENYELESAIAN OPTIMAL Dalam membaca informasi penyelesaian optimal, klasifikasi variabel sebagai variabel basis maupun non basis tidak begitu penting. Variabel yang tidak tercantum dalam kolom variabel basis berarti bernilai nol. Sedangkan nilsi variabel-variabel yang terletak pada kolom variabel basis dapat dilihat pada kolom nilai kanan. Dari tablo optimal simpleks pada contoh 2.5 dapat diperoleh informasi seperti yang terlihat pada tabel berikut: Variabel Keputusan

Nilai Optimal

a B P

1 5 56

Keputusan Dalam satu masa produksi membuat roti jenis A sebanyak 1 Dalam satu masa produksi membuat roti jenis B sebanyak 5 Keuntungan yang diperoleh sebesar Rp. 5.600,-

STATUS SUMBER Status dari sumber dalam satu masa produksi diklasifikasikan menajdi dua jenis, yaitu :  

Scarce, sumber dikatakan scarce apabila kapasitas persediaan sumber tersebut dipakai semua Abundant, sumber dikatakan abundant apabila kapasitas persediaan sumber tersebut tidak dipakai semua

Dalam pembahasan mengenai status sumber ini berkaitan dengan persediaan sumber yang mempunyai batas maksimal, yang ebrarti fungsi batasan yang berkaitan dengan sumber tersebut merupakan pertidaksamaan dengan tanda . Sehingga untuk permasalahan program linear dengan fungsi batasan berupa pertidaksamaan dengan tanda  secara fisik tidak dapat dikaji tentang status sumber dari permasalahan tersebut. Informasi mengenai status sumber dapat dilihat langsung dari tablo optimal simpleks dengan cara memperhatikan nilai-nilai variabel slacknya. Untuk lebih jelasnya, berikut ini akan dibahas status sumber pada permaslaahan dari contoh 2.5. Sumber

Variabel slack

Status sumber

Sumber 1 (terigu) Sumber 2 (keju) Sumber 3 (daging)

S1 = 0 S2 = 0 S3 = 28/3

Scarce / terpakai semua Scarce / terpakai semua Abundant / melimpah

Variabel slack yang bernilai positif berarti kapasitas dari sumber melimpah atau tidak digunakan seluruhnya. Sedangkan apabila variabel slack bernilai nol berarti persediaan sumber dipakai semua dalam produksi. Berdasar tabel di atas terlihat bahwa terigu dan keju dipakai semua dalam produksi roti. Sehingga, baik terigu maupun keju apabila kapasitasnya ditambah akan menigkatkan keuntungan. Untuk daging kapasitas sebesar 12 ons dalam satu masa produksi ternyata tidak dipakai seluruhnya, jadi masih ada

sisa. Sehingga apabila kapasitas daging ditambah maka akan sia-sia karena tidak akan menambah keuntungan.

BOBOT SATUAN (UNIT WORTH) SUATU SUMBER Unit worth suatu sumber adalah laju penambahan nilai optimal dari fungsi tujuan sebagai akibat kenaikan persediaan/kapasitas sumber. Informasi mengenai unit worth suatu sumber dapat diperoleh langsung dari tablo optimal simpleks. Untuk lebih jelasnya akan dilihat unit worth dari tablo optimal simpleks pada contoh 2.5 berikut : Variabel Nilai Keterangan P a b S1 S2 S3 Rasio Basis Kanan Iterasi

P

1

0

0

1/2

1

0

56

(2)

a

0

1

0

1/12

-1/9

0

1

Optimal

b

0

0

1

0

1/6

0

5

S3

0

0

0

-1/3

4/9

1

28/3

Dari tabel di atas diperoleh informasi bahwa : 

Unit worth dari sumber 1 (terigu) sebesar 1/2 Berarti penambahan kapasitas terigu setiap 1 kg menyebabkan kenaikan keuntungan sebesar Rp. 50,Unit worth dari sumber 2 (keju) sebesar 1 Berarti penambahan kapasitas keju setiap 1 ons menyebabkan kenaikan keuntungan sebesar Rp. 100,Unit worth dari sumber 3 (daging) sebesar 0 Berarti penambahan kapasitas daging tidak akan mempengaruhi keuntungan

 

Penambahan kapasitas sumber 2 (keju) seharusnya lebih diprioritaskan dibandingkan sumber yang lain.

METODE PEMBELAJARAN Practice Rehearsal Pairs


Tahap

1.

Pendahuluan

2.

Penyajian

Kegiatan Pembelajaran Apersepsi dan motivasi Mengulas kembali tentang metode penalti.

Eksplorasi Memberi penjelasan tentang cara menginterpretasikan tablo optimal simpleks

Elaborasi a. Memberikan permaslahan program linear. b. Meminta mahasiswa berkelompok. c. Setiap kelompok dibagi menjadi dua tim, dan setiap tim harus menyelesaiakan permassalahan dengan metode simpleks dan menginterpretasi hasilnya. d. Setelah selesai, salah satu tim diminta menjelaskan kepada tim yang lain. Pada tahap berikutnya kedua tim bertukar peran.

Alokasi Waktu 10 menit 20 menit 5 menit 5 menit 40 menit 30 menit

Eksplanasi 3.

Penutup


Dosen memberikan beberapa pertanyaan kepada siswa tentang konsep yang harus dipahami mahasiswa. Refleksi dan Evaluasi Menyimpulkan apa yang dipelajari secara klasikal, yang menyangkut : a. Menentukan penyelesaian optimal dari tablo optimal simpleks b. Menentukan bobot satuan pada tablo optimal simpleks c. Menentukan status sumber pada tablo optimal simpleks

25 menit 15 menit



PENILAIAN 1. 2.




: : : :



: : : : : :


: :

Tujuan

:

PROGRAM LINEAR MKK206515 3 SKS II 13 Menentukan penyelesaian dari permasalahan program linear dengan menggunakan berbagai metode 3. Menyelesaikan permasalahan program linear dengan metode simpleks 3.6 Menentukan nilai optimum dari kejadian khusus yang muncul saat optimasi dengan metode simpleks. 2.6.1 Mengidentifikasi ciri kasus degenerasi 2.6.2 Mengidentifikasi ciri kasus optimal alternatif 2.6.3 Mengidentifikasi ciri kasus penyelesaian tidak terbatas 2.6.4 Mengidentifikasi ciri kasus penyelesaian tidak feasible

MATERI KEJADIAN KHUSUS PADA METODE SIMPLEKS DEGENERASI Dalam penggunaan metode simpleks syarat ke-feasible-an ditunjukkan dengan rasio minimal. Dalam aplikasinya dimungkinkan terjadi rasio minimal tersebut lebih dari satu. Apabila hal itu terjadi maka satu atau lebih variabel basis akan bernilai nol pada iterasi berikutnya. Kejadian seperti ini dikatakanbahwa penyelesaian baru yang diperoleh adalah degenerate. Peristiwa ini terjadi disebabkan permasalahan program linear tersebut memiliki satu fungsi batasan yang berlebih. Contoh 2.6 Permasalahan Program Linear Memaksimumkan : Terhadap batasan :

Z = 3a + 9b a + 4b  8 a + 2b  4 a, b  0


Memaksimumkan : Z – 3a – 9b = 0 Terhadap batasan : a + 4b + S1 = 8 (1) a + 2b + S2 = 4 (2) a, b, S1, S2  0

Berikut adalah tablo simpleks dari permasalahan di atas : Keterangan

Variabel Basis

Z

a

b

S1

S2

Nilai Kanan

Rasio

Iterasi Awal (0) ev = b

Z

1

-3

-9

0

0

0

-

S1

0

1

4

1

0

8

2

lv = S2

S2

0

1

2

0

1

4

2

Iterasi (1)

Z

1

-3/4

0

9/4

0

18

-

ev = a

B

0

1/4

1

1/4

0

2

8

lv = S1

S2

0

1/2

0

-1/2

1

0

0

Iterasi (2)

Z

1

0

0

3/2

3/2

18

Optimal

B

0

0

1

1/2

-1/2

2

a

0

1

0

-1

2

0

Secara umum, pada peristiwa degenerasi, prosedur simpleks akan terulang dalam iterasi pada baris yang sama, nilai fungsi tujuan tidak berubah dan perhitungan tidak pernah berhenti. Peristiwa ini disebut cycling. Tabel pada contoh 2.6 diatas memperlihatkan degenerasi terjadi karena pada iterasi (1) dan (2) walaupun variabel basis dan non basisnya berbeda, namun tetap menghasilkan nilai yang sama untuk semua variabel dalam fungsi tujuan, yaitu : a = 0, b = 2, S 1 = 0, dan S2 = 0 menghasilkan Wmaks = 18. Jadi peristiwa degenerasi tidak selamanya seperti pada cycling, namun ada kemungkinan degenerasi tersebut sifatnya hanya sementara saja (temporarily degenerate).

OPTIMAL ALTERNATIF Dalam kejadian ini terdapat beberapa alternatif penyelesaian optimal pada suatu permasalahan. Artinya, fungsi tujuanakan bernilai optimal sama pada lebih dari satu titik penyelesaian. Perhatikan contoh berikut ini : Permasalahan Program Linear Memaksimumkan Terhadap batasan

: :

P = 2a + 4b a + 2b  5 a+b4 a, b  0

Bentuk Kanonik Memaksimumkan Terhadap batasan

(1) (2)

: :

P – 2a – 4b = 0 a + 2b + S1 = 5 a + b + S2 = 4 a, b, S1, S2  0

(1) (2)

Berikut adalah tablo simpleks dari permasalahan di atas : Variabel Basis

P

a

B

S1

S2

Nilai Kanan

Iterasi Awal (0)

P

1

-2

-4

0

0

0

-

ev = b

S1

0

1

2

1

0

5

5/2

lv = S1

S2

0

1

1

0

1

4

4

Iterasi (1) Optimal

P

1

0

0

2

0

10

-

ev = a

b

0

1/2

1

1/2

0

5/2

5

lv = S2

S2

0

1/2

0

-1/2

1

3/2

3

Iterasi (2)

P

1

0

0

2

0

10

Optimal

b

0

0

1

1

1

1

a

0

1

0

-1

2

3

Keterangan

Rasio

Pada metode simpleks iterasi terjadi dari satu titik ekstrim ke titik ekstrim lain yang saling terhubung. Pada tabel diatas terlihat bahwa penyelesaian optimal tercapai di titik (a, b) = (0, 5/2) dan menghasilkan Pmaks = 10. Perhatikan iterasi (1), koefisien dari variabel non basis a pada fungsi tujuan adalah nol, selanjutnya a masuk sebagai variabel basis pada iterasi berikutnya tanpa mengubah nilai P, tetapi berakibat pada perubahan nilai variabelnya. Pada iterasi (2), a masuk menjadi variabel basis dan memaksa S2 keluar menjadi variabel non basis. Pada iterasi (2) penyelesaian optimal baru terjadi di (a, b) = (3, 1) dan menghasilkan Pmaks = 10.

PENYELESAIAN TIDAK TERBATAS Perhatikan contoh permasalahan pemrograman linear berikut : Permasalahan Program Linear Memaksimumkan Terhadap batasan

: :

T = 2a + b a  b  10 2b  40 a, b  0



: :

T – 2a – b = 0 a  b + S1 = 5 2a + S2 = 40 a, b, S1, S2  0

(1) (2)


Variabel Basis

P

a

b

S1

S2

Nilai Kanan

Rasio

Iterasi Awal (0)

T

1

-2

-1

0

0

0

-

ev = b

S1

0

1

-1

1

0

10

10

lv = S1

S2

0

2

0

0

1

40

20

Iterasi (1)

T

1

0

-3

2

0

20

-

ev = b

A

0

1

-1

1

0

10

-

lv = S2

S2

0

0

2

-2

1

20

10

Iterasi (2)

T

1

0

0

-1

3/2

50

-

A

0

1

0

0

1/2

30

-

b

0

0

1

-1

1/2

10

-

Perhatikan tabel di atas. Pada iterasi (2) penyelesaian optimal belum tercapai, S 1 terpilih sebagai entering variable, akan tetapi leaving variable-nya tidak dapat ditentukan. Jadi permasalahan tersebut memiliki penyelesaian yang tidak terbatas. Secara umum, perhatikan tabel diatas, a dan b merupakan variabel non basis. Salah satu variabel ini akan terpilih menjadi entering variable yang akan masuk sebagai variabel basis pada iterasi selanjutnya. Tetapi perhatikan bahwa semua fungsi batasan di kolom b adalah non-positif. Artinya, nilai b dapat dinaikkan sampai tak hingga tanpa melanggar satupun batasan. Jadi dengan melihat tablo awal simpleks, tanpa melalui perhitungan pun dapat disimpulkan bahwa permasalahan tersebut memiliki penyelesaian yang tidak terbatas.

PENYELESAIAN TIDAK FEASIBLE Perhatikan contoh permasalahan pemrograman linear berikut : Permasalahan Program Linear Memaksimumkan Terhadap batasan

: :

K = 3a + 2b 2a + b  2 3a + 4b  12 a, b  0

Bentuk Kanonik Memaksimumkan Terhadap batasan

(1) (2)

: :

K – 3a – 2b + M(12 – 3a – 4b + S2)= 0 2a + b + S1 = 2 (1) 3a + 4b – S2+ R = 12 (2) a, b, S1, S2, R  0


Variabel Basis

K

a

b

S1

S2

R

Nilai Kanan

Rasio

Iterasi Awal (0)

K

1

–3 – 3M

–2 – 4M

0

M

0

0

-

ev = b

S1

0

2

1

1

0

0

2

2

lv = S1

R

0

3

4

0

-1

1

12

3

Iterasi (1)

T

1

1 + 3M

0

2 + 4M

M

0

4 – 4M

Optimum

b

0

2

1

1

0

0

2

R

0

-5

0

-4

-1

1

4

Pada tabel tersebut terlihat bahwa pada iterasi (1) telah tercapai penyelesaian optimum. Untuk penyelesaian optimum tersebut diperoleh nilai variabel semu R = 4. Hal ini menunjukkan bahwa penyelesaian permasalahan tersebut merupakan penyelesaian yang tidak feasible.


LANGKAH PEMBELAJARAN

No.

Tahap

1.

Pendahuluan


Apersepsi dan Motivasi Memberikan gambaran tentang kejadian khusus permasalahan program linear, karena kemungkinan ada permasalahan yang tidak memiliki penyelesaian atau bahkan penyelesaiannya tidak tunggal.

2.

Penyajian

Eksplorasi a. Memberikan berbagai permasalahan program linear yang memuat kejadian khusus berikut : 1). Degenerasi 2). Optimal alternatif 3). Penyelesaian tidak terbatas 4). Penyelesaian tidak layak b. Membentuk siswa dalam beberapa kelompok



5 menit

10 menit 50 menit


Penutup

Refleksi dan Evaluasi Menyimpulkan ciri kejadian khusus pada metode simpleks

50 menit 20 menit




PENILAIAN 3. 4.



METODE PENALTI (TEKNIK M) Tentukan nilai a dan b dari permasalahan berikut dengan Metode Penalti (Teknik M) Meminimumkan : P = 6a + 4b Terhadap batasan : 3a + b  30 a + b = 15 a + 2b  24 a, b  0 \ SOLUSI

Bentuk Kanonik Permasalahan

Bentuk Kanonik

Meminimumkan : P = 6a + 4b Terhadap batasan: 3a + b  30 a + b = 15 a + 2b  24 a, b  0

Variabel basis dan non basis __________________________________________________________________________________________ __________________________________________________________________________________________

Tablo Simpleks

Kesimpulan : ___________________________________________________________________________________ ___________________________________________________________________________________ ___________________________________________________________________________________

PENDALAMAN MATERI 1.

Pada kasus seperti apa metode penalti (Teknik M) digunakan? Jawab : ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________

2.

Batasan apa saja yang ditambah dengan variabel semu? Berikan Alasannya! Jawab : ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________

3.

Apa ciri batasan yang harus ditambah dengan variabel semu? Jawab : ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________

4.

Pada fungsi tujuan (meminimumkan) apa arti penambahan MR? Bagaimana jika kasusnya meminimumkan? Jawab : ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________ ______________________________________________________________________

Anggota Kelompok : 1. 2. 3. 4.

__________________________ ( ______________________ ) __________________________ ( ______________________ ) __________________________ ( ______________________ ) __________________________ ( ______________________ )

METODE DUA TAHAP PERMASALAHAN Tentukan penyelesaian dari permasalahan berikut dengan metode simpleks dua tahap :  Meminimumkan : P = 20r + 30s Terhadap batasan : 2r + s  10 r + 4s  12 r, s  0

PENYELESAIAN TAHAP I Permasalahan Program Linear Meminimumkan : Terhadap batasan :

P = 20r + 30s 2r + s  10 r + 4s  12 r, s 

Bentuk Kanonik 2

(1) (2)

Meminimumkan

:

W=

R i1

Terhadap batasan :

Karena (1) 2r + s  S1 + R1 = 10  R1 = 10 – 2r – s + S1 (2) r + 4s  S2 + R2 = 12  R2 = 12 – r – 4s + S2 Sehingga bentuk kanoniknya menjadi :

i

2r + s  S1 + R1 = 10 (1) r + 4s  S2 + R2 = 12 (2) i, j, k, S1, S2, R1, R2  0 ..... [ 10 ]

Maka R1 + R2 = 22 – 3r – 5s + S1 +

2

Meminimumkan : W =

R i1

i

= 22 – 3r – 5s + S1 + S2 W + 3r + 5s – S1 – S2 = 22

Terhadap batasan : 2r + s  S1 + R1 = 10 r + 4s  S2 + R2 = 12 r, s, S1, S2, R1, R2  0 Permasalahan tersebut memiliki ___ persamaan dengan ___ variabel yang tidak diketahui. Selanjutnya permasalahan tahap I ini diselesaikan dengan metode simpleks sebagai berikut : 

Mencari penyelesaian basis awal feasible. Ambil sebanyak ____ variabel non basis yaitu : _________________. Akibatnya R 1 = ___, R2 = ___ sebagai variabel basis. Hal ini menghasilkan nilai awal fungsi tujuan W = ____




Var. Basis

Nilai Rasio Kanan

Iterasi Awal ev = ..... lv = ..... Iterasi (1) ev = ..... lv = .....

Karena pada iterasi _____ semua nilai pada baris fungsi tujuan sudah non positif maka penyelesaian optimal tercapai. Berdasarkan iterasi pada tahap I diperoelh bahwa W min = ______.

TAHAP II Sehingga tablo optimal tahap I dapat ditulis dalam bentuk persamaan menjadi :

Sehingga permasalahan pada tahap II menjadi : Meminimumkan : Terhadap batasan :

Permasalahan tersebut memiliki ____ persamaan dengan ____ variabel yang tidak diketahui. Selanjutnya permasalahan ini diselesaikan dengan metode simpleks sebagai berikut : 

Mencari penyelesaian basis awal feasible. Pada tahap II ini penyelesaian basis awal feasible telah diperoleh dari tablo optimal permasalahan pada tahap I. Jadi dari tablo optimal permasalahan tahap I diperoleh bahwa : (1) (2)

Penyelesaian basis awal tahap II terjadi pada saat : r = ________________ dan s = ________________ dengan : P = 20r + 30s  P =




Variabel Basis

P

r

s

S1

S2

Nilai Kanan

P

1

0

0

–50/7

–40/7

140

r

0

1

0

4/7

1/7

4

s

0

0

1

1/7

2/7

2

Rasio

Kesimpulan: ______________________________________________________________________________________ ______________________________________________________________________________________ ______________________________________________________________________________________ ______________________________________________________________________________________ ______________________________________________________________________________________ Anggota

:

1. ________________________ 2. ________________________ 3. ________________________ 4. ________________________

ISOLINE Suatu industri kecil memproduksi kue jenis A dan B. Kue tersebut dibuat dari 2 bahan pokok. Kebutuhan bahan setiap kue sebagai berikut : Bahan Pokok Jenis Kue

Keterangan (dalam ribuan)

X

Y

Bahan Baku

Biaya Produksi

Harga Jual

A

3 ons

1 ons

9

2

14

B

2 ons

2 ons

12

3

19

Kapasitas Bahan

180 ons

100 ons

Pada satu periode produksi, industri kecil tersebut paling tidak harus membuat kue sebanyak 20 buah. Jika industri tersebut menginginkan laba sebesar-besarnya, maka tentukan model matematika dari permasalahan tersebut, kemudian cari penyelesaiannya dengan Metode grafik teknik isoline.

POST TEST Tentukan solusi dari permasalahan berikut ini menggunakan metode grafik dengan teknik isoline : 1.

Tentukan nilai a dan b yang memenuhi : Fungsi Tujuan : Memaksimumkan Z = 40a + 30b Terhadap kendala : 2a + b  20 2a + 3b  32 2a – b  0 b  2 dan a  0

2.

Tentukan nilai t dan u yang memenuhi : Fungsi Tujuan : Meminimumkan P = 20t + 30u Terhadap kendala : 2t + u  10 t + u  14 t + 4u  12 t  8 dan u  0

KEJADIAN KHUSUS METODE GRAFIK ANGGOTA KELOMPOK

1. 2. 3. 4. 5.

1.

______________________________ ______________________________ ______________________________ ______________________________ ______________________________

NIM : NIM : NIM : NIM : NIM :

___________________ ___________________ ___________________ ___________________ ___________________

Tentukan nilai a dan b yang memenuhi : Fungsi tujuan : Memaksimumkan W = 3a + 9b Terhadap kendala : a + 4b  8 a + 2b  4 a, b  0 SOLUSI :

Nilai maksimum Wmaks = ____________ dicapai pada titik ( __ , __ ) Perhatikan daerah feasiblenya kemudian jawab pertanyaan berikut : 1.

Titik mana saja yang menjadi batas dari daerah feasiblenya ? Jawab : _____________________________________________________________________

2.

Adakah batasan yang sama sekali tidak mempengaruhi daerah feasible ? Jawab : _____________________________________________________________________

3.

Apabila batasan yang tidak mempengaruhi daerah feasible tersebut direduksi (dihilangkan) apakah daerah feasible-nya berubah ? Jawab : _____________________________________________________________________

Batasan yang memiliki sifat seperti pada pertanyaan 2 dan 3 disebut sebagai batasan redundan (redundant constrains) Kesimpulan :

2.

Permasalahan program linear yang memiliki sifat khusus seperti pada contoh di atas disebut dengan ________________________________________

Tentukan nilai x dan y yang memenuhi : Fungsi tujuan : Memaksimumkan T = 2x + 4y Terhadap kendala : x + 2y  5 x+y4 x, y  0 (Kerjakan dengan isoline dan titik ekstrim, kemudian bandingkan hasilnya)

SOLUSI : Titik ekstrim (x, y)

T = 2x + 4y

Nilai maksimum Tmaks = ____________ dicapai pada titik ( __ , __ ) Penjelasan :

_______________________________________________________________________ _______________________________________________________________________ _______________________________________________________________________

Adakah keanehan yang anda temukan ? atau kesulitan yang anda hadapi dalam menentukan titik optimumnya ? Jika ada, tuliskan : ___________________________________________________________________________________ ___________________________________________________________________________________ ___________________________________________________________________________________ Kesimpulan : 3.


Tentukan nilai r dan s yang memenuhi : Fungsi tujuan : Memaksimumkan K = 3r + 2s Terhadap kendala : 2r + s  2 3r + 4s  12 r, s  0 SOLUSI :

Nilai maksimum Kmaks = ____________ dicapai pada titik ( __ , __ ) Penjelasan :

_______________________________________________________________________ _______________________________________________________________________ _______________________________________________________________________

Kesimpulan :


4.

Tentukan nilai t dan u yang memenuhi : Fungsi tujuan : Memaksimumkan S = 2t + u Terhadap kendala : t – u  10 2t  40 t, u  0 (Kerjakan dengan isoline dan titik ekstrim, kemudian bandingkan hasilnya) SOLUSI : Titik ekstrim (t, u)

T = 2t + u

Nilai maksimum Smaks = ____________ dicapai pada titik ( __ , __ ) Penjelasan :

_______________________________________________________________________ _______________________________________________________________________ _______________________________________________________________________

Kesimpulan :


MODEL MATEMATIKA PERMASALAHAN PROGRAM LINEAR 1.

Suatu perusahaan memproduksi 3 jenis barang dengan 2 bahan yang tersedia. Kebutuhan barang dan ketersediaan sumber terlihat pada tabel berikut ini: Barang

Sumber P Q Waktu Biaya Produksi Biaya Transport Harga Jual

K 3 5 8 jam 45 15 90

L 4 1 5 jam 30 12 75

Kapasitas Sumber M 2 3 7 jam 50 13 80

Minimal 60 unit Minimal 75 unit Maksimal 450 jam (dalam ribuan)

Kebijakan yang diambil perusahaan : Dalam satu periode produksi, produk K dibuat lebih banyak dari pada produk L dengan selisih tidak kurang dari 10 unit. Tentukan model matematika dari permsalahan tersebut apabila : a.

Perusahaan ingin menekan biaya pengeluaran

b.

Perusahaan ingin memperoleh hasil penjualan barang yang sebesar-besarnya

MENENTUKAN DAERAH FEASIBLE PERMASALAHAN PROGRAM LINEAR Suatu perusahaan memproduksi 2 jenis barang dengan 2 buah bahan mentah. Kebutuhan bahan untuk setiap unit barang terlihat pada tabel berikut!. Bahan Baku X

Y

Biaya Produksi (Jutaan Rp.)

Biaya Distribusi (Jutaan Rp.)

Harga Jual (Jutaan Rp.)

A

1

3

70

13

113

B

2

2

60

12

82

Barang

Dalam satu periode produksi, perusahaan tersebut memiliki bahan X paling tidak 240 unit, dan bahan Y tidak lebh dari 400 unit. Banyak produkdi barang A tidak boleh diproduksi melebihi 4 kali banyak produksi barang B. Perusahaan menginginkan pendapatan sebesar-besarnya.

 Tentukan model matematikanya!  Gambarkan Daerah Feasible.nya!

QUIZ I (Tipe A) Suatu perusahaan memproduksi 2 macam barang dengan 2 jenis bahan utama. Kebutuhan bahan untuk setiap barang terlihat pada tabel berikut. Jenis Barang A B Kapasitas Bahan Utama

Bahan Utama X Y 3 2 1 2 Bahan X disediakan tidak kurang dari 60 unit Bahan Y disediakan tetapi tidak melebihi tidak melebihi 120 unit 240 unit

Keuntungan per unit Rp. 30.000,00 Rp. 20.000,00

Untuk memenuhi permintaan konsumen, barang A diproduksi paling tidak 10 unit. Kebijakan perusahaan menetapkan bahwa 3 kali banyak produksi barang A tidak boleh kurang dari 2 kali banyak produksi barang B. Tentukan model matematikanya dan banyak produksi setiap jenis barang agar perusahaan mendapatkan keuntungan sebesar-besarnya!

QUIZ I (Tipe B) Suatu perusahaan memproduksi 2 macam barang dengan 2 jenis bahan utama. Kebutuhan bahan untuk setiap barang terlihat pada tabel berikut. Jenis Barang

Bahan Utama

X

Y

A

2

3

B

2

1

Biaya Produksi

Rp. 400.000,00

Rp. 600.000,00

Kapasitas Bahan A disediakan tidak kurang dari 60 unit tetapi tidak melebihi 240 unit Bahan B disediakan tidak melebihi 120 unit

Untuk memenuhi permintaan konsumen, barang Y diproduksi paling tidak 10 unit. Kebijakan perusahaan menetapkan bahwa 3 kali banyak produksi barang Y tidak boleh kurang dari 2 kali banyak produksi barang X. Tentukan model matematikanya dan banyak produksi setiap jenis barang agar perusahaan mengeluarkan biaya produksi sekecil-kecilnya!

QUIZ I (Tipe C) Suatu perusahaan memproduksi 2 macam barang dengan 2 jenis bahan utama. Kebutuhan bahan untuk setiap barang terlihat pada tabel berikut. Jenis Barang X Y Kapasitas Bahan Utama

Bahan Utama P 1 1 Bahan P disediakan tidak kurang dari 90 unit

Q 1 3 Bahan Q disediakan tidak kurang dari 150 unit

Keuntungan per unit Rp. 30.000,00 Rp. 20.000,00

Untuk memenuhi permintaan konsumen, barang A diproduksi paling tidak 20 unit. Kebijakan perusahaan menetapkan bahwa banyak produksi barang A tidak boleh kurang dari 2 kali banyak produksi barang B. Tentukan model matematikanya dan banyak produksi setiap jenis barang agar perusahaan mendapatkan keuntungan sebesar-besarnya!

UJIAN TENGAH SEMESTER GENAP TA 2014/2015 UNIVERSITAS VETERAN BANGUN NUSANTARA SUKOHARJO FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN PROGRAM STUDI : PENDIDIKAN MATEMATIKA Jl. Letjend. S. Humardani No. 1, Jombor Sukoharjo. Telp. (0271) 593156

Mata Kuliah Waktu Semester Dosen Pengampu

: : : :

PROGRAM LINEAR 90 Menit II Erika Laras Astutiningtyas, S.Pd., M.Pd.

KETENTUAN UJIAN:  

Sifat ujian : Closed Book Boleh menggunakan alat bantu hitung selain handphone.

KASUS: UD. Bahagia adalah suatu industri yang bergerak dalam bidang handycraft. Ada 2 jenis handycraft yang dibuat, yaitu jenis X dan jenis Y. Kedua jenis handycraft tersebut akan dipasarkan per lusin. Untuk membuat 1 lusin handycraft X diperlukan 2m kayu dan 1m papan. Sedangkan untuk membuat 1 lusin handycraft Y diperlukan 3m kayu dan 1m papan. Handycraft jenis X lebih digemari dari pada jenis Y sehingga X harus diproduksi lebih banyak daripada Y. Disisi lain, industri tersebut memiliki kebijakan bahwa selisih produksi kedua jenis produk tersebut tidak lebih dari 6 lusin. Pada satu periode produksi, industri tersebut hanya memiliki 72m kayu dan 26m papan. Tabel berikut menunjukkan biaya operasional dari UD. Bahagia. Jenis Hadycraft X Y

Biaya Operasional (per unit) Biaya Biaya Produksi Pengemasan Rp. 1.800,00 Rp. 300,00 Rp. 2.000,00 Rp. 400,00

Harga Jual (per unit) Rp. 2.700,00 Rp. 3.000,00

UD. Bahagia ingin menghitung berapa laba terbesar yang bisa diperoleh dan menentukan berapa lusin masingmasing jenis handycraft harus diproduksi untuk mencapai laba terbesar itu. SOAL 1. 2.

Tentukan model matematika untuk permasalahan di atas! Selesaikan permasalahan tersebut dengan metode grafik teknik isoline!

_Semoga Berhasil dengan Jujur_

UJIAN AKHIR SEMESTER GENAP TA 2014/2015 UNIVERSITAS VETERAN BANGUN NUSANTARA SUKOHARJO FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN PROGRAM STUDI : PENDIDIKAN MATEMATIKA Jl. Letjend. S. Humardani No. 1, Jombor Sukoharjo. Telp. (0271) 593156

Mata Kuliah Waktu

KETENTUAN UJIAN:

: PROGRAM LINEAR : 90 Menit

Semester : II Dosen Pengampu : Erika Laras Astutiningtyas, M.Pd.

 Sifat ujian : Closed Book  Boleh menggunakan alat bantu hitung selain handphone.  Tuliskan tanggal, bulan dan tahun lahir pada lembar jawab

A. Kasus I : Untuk mahasiswa yang bulan lahir bulan Januari, Pebruari, Maret, April Suatu perusahaan memproduksi barang A dan B dengan 2 jenis bahan mentah P dan Q. Kebutuhan bahan untuk setiap barang terlihat pada tabel berikut. Bahan Laba per unit Barang (ratusan) P Q A 2 2 12 B 3 1 18 Maksimal 96 Minimal 48 Kapasitas unit unit Tentukan keuntungan optimal yang dapat diperoleh perusahaan dengan Metode grafik dan metode simpleks. Kemudian interpretasikan tablo optimal simpleksnya. Jika ada kejadian khusus, jelaskan! B. Kasus II : Untuk mahasiswa yang bulan lahirnya bulan Mei, Juni, Juli, dan Agustus Suatu perusahaan memproduksi barang P dan Q dengan 2 jenis bahan mentah A dan B. Kebutuhan bahan untuk setiap barang terlihat pada tabel berikut. Barang Bahan Kapasitas P Q A 3 2 Maksimal 90 unit B 3 5 Minimal 90 unit Laba per unit 24 16 (ratusan) Tentukan keuntungan optimal yang dapat diperoleh perusahaan dengan Metode grafik dan metode simpleks. Kemudian interpretasikan tablo optimal simpleksnya. Jika ada kejadian khusus, jelaskan! C. Kasus IV : Untuk mahasiswa yang bulan lahirnya bulan September, Oktober, Nopember dan Desember Suatu perusahaan memproduksi barang P dan Q dengan 2 jenis bahan mentah A dan B. Kebutuhan bahan untuk setiap barang terlihat pada tabel berikut. Barang Bahan Kapasitas P Q A 3 2 Maksimal 144 unit B 1 2 Minimal 72 unit Laba per unit 24 16 (ratusan) Tentukan keuntungan optimal yang dapat diperoleh perusahaan dengan Metode grafik dan metode simpleks. Kemudian interpretasikan tablo optimal simpleksnya. Jika ada kejadian khusus, jelaskan!

QUIZ II Waktu : 90 menit Tentukan penyelesaian dari permasalahan berikut dengan metode simpleks. 1.


: :

Z = 15a + 30b 2a – 3b  30 a + 2b  40 a  0, b tidak dibatasi

2.


: :

T = 20x + 30y x + y  15 4x + 3y  75 3x + 2y  60 x tidak dibatasi, y  0

: :

P = 24a + 16b a + b  10 2a + 3b  40 3a + 4b  50 a  0, b tidak dibatasi

: :

Y = 24t + 36u t + u  20 4t + 3u  60 3t + 2u  48 t tidak dibatasi, u  0

: :

M = 45p + 30q p + q  20 2p + 3q  80 3p + 4q  100 a  0, b tidak dibatasi

: :

G = 32a + 48b a + b  30 8a + 6b  80 9a + 6b  96 a tidak dibatasi, b  0



: :

W = 50x + 25y 6x – 4y  –60 2x + y  40 x tidak dibatasi, y  0

2.




: :

F = 18r + 36s 6r – 9s  90 r + 2s  40 r  0, s tidak dibatasi

2.




: :

W = 40x + 20y 3x – 2y  –45 2x + y  30 x tidak dibatasi, y  0

2.




: :

H = 18p + 36q 6p – 9q  45 p + 2q  20 p  0, q tidak dibatasi

2.


PERANGKAT PEMBELAJARAN

Recommend Documents