dosen pengampuh : meyta dwi kurniasih,...

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

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

iii

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

Meyta Dwi Kurniasih, M. Pd. Pemrograman Linier

iv

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

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 masalah-

masalah 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

2

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 satuan-

satuan 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

Handout Program Linier : Model Matematika

3

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 :

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

Aktivitas 1


4

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


5

memerlukan tenaga kerja, biaya dan memberikan keuntungan masing-masing

sebagai berikut :

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 :

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

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

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

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

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

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

Tanaman Orang hari/ ha Biaya/ ha (Rp) Keuntungan/ ha (Rp)

Padi 6 100.000 60.000

Jagung 8 150.000 100.000

Kedelai 10 120.000 80.000


6

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 :

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

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

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

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

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

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

Dari kelima masalah di atas, apakah perbedaan dari setiap

masalah tersebut!

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

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

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

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

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

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

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

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

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

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

Aktivitas 2


7

Tentukan langkah- langkah dalam membuat model

matematika dari sebuah masalah program liner!

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

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

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

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

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

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

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

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

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

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

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

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

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

Tanggal Nilai Paraf Dosen

Aktivitas 3

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

9

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 8 6Z x y dengan syarat

4 2 60;2 4 48; 0; 0x y x y x y adalah ....

Penyelesaian :

Fungsi tujuan → 8 6maksZ x y

a. Jadikan setiap kendala menjadi bentuk persamaan

4 2 60x y → 2 30x y

2 4 48x y → 2 24x y

b. Buat grafik untuk setiap kendala dan tentukan daerah penyelesaiannya

(HP):

Fungsi Kendala Titik potong terhadap sumbu

Titik potong terhadap sumbu

2 30x y

2 24x y


10

c. Dari grafik diatas garis I : 2 30x y dan garis II : 2 24x y . Dengan

menggunakan metode titik ekstrim, setelah menentukan himpunan

penyelesaian (HP) lalu tentukan titik-titik terluar/ titik ekstrim di dapat

seperti tabel berikut :

d. Ditentukan nilai maksimumnya adalah 132 pada titik (12, 6).

Dengan menggunakan Metode Isoline :

( , )x y 8 6Z x y

(0, 12) (12, 6) (15, 0)

72 132 120


11

2. Nilai maksimum dari ( , ) 2 3f x y x y pada himpunan penyelesaian sistem

pertidaksamaan: 3 2 24x y ; 2 8x y ; , 0x y adalah …..

Penyelesaian :

Fungsi tujuan : 2 3maksZ x y


3 2 24x y → 3 2 24x y

2 8x y → 2 8x y


Fungsi Kendala Titik potong terhadap sb Titik potong terhadap sb

3 2 24x y .... ....

2 8x y .... ....

c. Dari grafik diatas garis I : 2 8x y dan garis II : 3 2 24x y . Setelah

menentukan himpunan penyelesaian (HP) lalu tentukan titik-titik terluar di

dapat seperti tabel berikut :


12

d. Ditentukan nilai maksimumnya adalah .... pada titik (....,....)

3. Nilai maksimum dari 20 8Z x untuk dan yang memenuhi ,

, , dan adalah ….

Penyelesaian :

Fungsi tujuan : ....maksZ


→ ....

→ ....


(HP)

( , )x y 2 3maksZ x y

(0, 4) ....

(4, 6) ....

(8, 0) ....


13

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

Petunjuk : Diskusikan dengan kelompokmu soal-soal dibawah ini,

kemudian buat langkah-langkah penyelesaiannya!

Isilah kolom di bawah ini!

No. Sistem pertidaksamaan Grafik

1.

0,

1232

2

yx

yx

yx

Aktivitas 1


14

No. Sistem pertidaksamaan Grafik

2.

0

3 5 15

, 0

x y

x y

x y

3.


15

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

Aktivitas 2


16

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 :


17

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 :


18

Dari diskusi yang telah kalian lakukan, tentukan langkah-

langkah dalam menyelesaikan sebuah masalah program linier

dengan metode grafik!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Aktivitas 3


19

B. Metode Grafik dengan Tiga Variabel

2.1. Soal Latihan

Diskusikan dengan kelompokmu soal-soal berikut ini, kemudian

buat langkah-langkah penyelesaiannya!

No. Sistem

pertidaksamaan Grafik

1.

4 3 2 12

2 4 3 12

, , 0

x y z

x y z

x y z

2.

Aktivitas 1


20

Kerjakan soal-soal berikut dan langkah-langkah penyelesaiannya!

1. Nilai maksimum dari pada himpunan

penyelesaian sistem pertidaksamaan ;

; , adalah ...

Jawaban :

Aktivitas 2


21

2. Nilai minimum dari untuk x dan y yang memenuhi

; ; ;

adalah....

Jawaban :


22

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 Waktu yang dibutuhkan produk pada masing-masing mesin (jam)

Waktu yang tersedia (jam per minggu)

Produk 1 Produk 2 Produk 3

Mesin milling 9 3 5 500

Lathe 5 4 0 350

Grinder 3 0 2 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 masing-

masing 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 :


23

Dari diskusi yang telah kalian lakukan, tentukan langkah- langkah

dalam menyelesaikan sebuah masalah program linier dengan

metode grafik 3 variabel!

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

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

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

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

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

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

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


Aktivitas 3

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

25

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.


26

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

4.

5. , , , , ,

6. , , , , ,

7. , , , , , ,

8. ,

,

9. , , , , , ,

10. , , , , ,


27

Jadi dari data table diatas maka nilai maksimumnya adalah 60 pada titik (10,0) 2. Untuk (x,y) yang memenuhi , , ≤ , maka

nilai maksimum untuk ( , ) adalah . . .

Jawab: ( , , , , )

No Variabel Variabel non Basis

Ket Titik

1 , , TL

2 , , TL

3 , , TL

4 , , TL

5 , , L ( , ) ....

6 , , L ( , ) ....

7 , , L ( , ) ....

8 , , L ( , ) ....

9 , , TL

10 , , L ( , ) ....


28

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 ( .......................)

C. Simpleks dengan Tabel Berkolom Variabel Dasar (VD)

3.1. Langkah- langkah mengerjakan :

1. Rumuskan dan standarisasi modelnya

Optimumkan :

0...2211 nn xcxcxcz

Terhadap :

11 1 12 2 1n 1 1

mnm1 1 m2 2

a a ... a

..

a a ... a

n

n n n

x x x s b

x x x s b

Dari dua contoh soal di atas, bagaimana cara menentukan banyaknya penyelesaian dasar ?

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


29

2. Bentuk table awal VD

VD Z 1x 2x … nx 1S 2S … nS NK

Z 1 1c 2c … nc 0 0 … 0 0

1s 0 11a 12a … 1na 0 1 … 0 1b

2s 0 21a 22a … 2na 1 0 … 0 2b

… … … … … … … … … … …

ms 0 m1a m2a … mna 0 0 … 1 nb

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 :

Transformasi baris-baris yang lain :

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 :

Baris kunci baru =

Baris baru = baris lama – (baris pada kolom kunci x baris kunci baru)


30

Kendala :

Tabel Awal

VD Z NK r

Z 1 -3 -5 0 0 0 -

0 1 2 1 0 10 5

0 3 1 0 1 10 10

Tabel 1

VD Z NK r

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 : untuk nilai dan dimana semua

sumber daya habis terpakai.

2. Maksimum

Pembatas:

≤

≤

≤


31

,

Penyelesaian:

Optimumkan:

Kendala :

Tabel Awal

VD Z NK r

Z

Tabel 1

VD Z NK

Z


32

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 x1 x2 x3 s1 s2 s3 NK

Z 0 0 4 0 5/3 2/3 31/3

s1 0 0 4/3 1 -1/9 -1/9 7/9

x2 0 1 8/3 0 7/9 -2/9 5/9

x1 1 0 -2 0 -2/3 1/3 2/3

1. Solusi optimal

,

, dan

, artinya untuk mendapatkan

keuntungan maksimum sebesar $

, maka perusahaan sebaiknya

menghasilkan produk 1 sebesar

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 S1 pada variable

basis table optimal. Periksa keberadaan S2 pada variable basis table

optimal untuk fungsi kendala kedua. Periksa keberadaan S3 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


33

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

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 :

Aktivitas 1


34

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 :


35

Buatlah simpulan dari pembelajaran yang telah di lakukan? ................................................................................................................................................................................................................................................................................................................................................................................ ................................................................................................................................................................................................................................................................................................................................ ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ ................................................................................................................................................................................................................................................................................................................................................................................ ................................................................................................................................................................................................................................................................................................................................ ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................


Aktivitas 2

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

37

Tabel Awal:

Cj -3 -2 0 0 -M -M HB Rasio

VB x y a B c D

C -M 1 1 -1 0 1 0 2 2

D -M 2 1 0 -1 0 1 3 1,5

Zj-Cj 3 2 0 0 0 0 0

-3 -2 1 1 0 0 -5

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 -2 0 0 -M -M HB r

VB x Y a b c D

C -M 0

-1

1

1

X -3 1

0

0

3

Zj-Cj

0

0

0

0

1

0

Tabel 3

Cj -3 -2 0 0 -M -M

HB Variabel

Basis X Y a B C D

Y -2 0 1 -2 1 2 -1 1

X -3 1 0 1 -1 -1 1 1

Zj-Cj 0 1 1 -1 -1 -5

0 0 1 1 0

Dari baris Zj-Cj yang kedua sudah tidak ada yang negatif maka iterasi

selesai. sehingga dapat di simpulkan :

1

2B2


38

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 x y →


39

dengan fungsi kendala menjadi,

≤ 6 → 6

→

Tabel Awal

Cj -3 -2 0 0 -M HB

r VB CB x Y a B c a 0 1 1 1 0 0 6 6 C -M 2 5 0 -1 1 10 2

Zj-Cj -3 -2 0 0 0 -5

-2M -5M 0 M 0 -7M

Cj -3 -2 0 0 -M HB

VB CB x Y a b c A 0 1 1 1 0 0 6

Y -2

1 0

2

Zj-Cj -3 -2 0 0 0 -5

-2M -5M 0 M 0 -7M

Tabel 1

Cj -3 -2 0 0 -M HB

VB CB x Y a b c

A 0

0 1

4

Y -2

1 0

2

Zj-Cj

0 0

- 0 0 0 M 0

Karena pada baris objektif (B3) sudah tidak ada yang negatif maka iterasi

selesai. Dari perhitungan di atas dapat diambil kesimpulan :

1

5𝐵2

𝐵1−𝐵2


40

C. Soal Latihan

Kerjakan soal berikut dengan menggunakan metode M Charnes atau simpleks 1 fase!

1. Minimumkan : 1 2

Kendala : 1 2 ≤ 1 2 6 1 2 ≤ 1 2

2. Minimumkan : 6 1 2 Kendala : 1 2

1 2

1 2

3. Minimumkan : Kendala :

4. Minimumkan : 1 2 Kendala : 1 2

1 2 1 2

Aktivitas 1


41


42


43

Buatlah simpulan dari pembelajaran yang telah di lakukan?

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

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

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

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

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

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

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

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

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

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

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


Aktivitas 2

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


45

Tabel Awal Fase 1

Cj 0 0 0 -1 0 -1 HB r

VB x y -1 4 2 -1 1 0 0 60 30 -1 2 4 0 0 -1 1 48 12

Zi-Cj -6 -6 1 0 1 0 -108

Cj 0 0 0 -1 0 -1 HB

VB x y -1 4 2 -1 1 0 0 60

0

1 0 0

12

Zj-Cj -6 -6 1 0 1 0 -108 Tabel 2

Cj 0 0 0 -1 0 -1 HB R

VB x Y

-1 3 0 -1 1

36 12

0

1 0

12 24

Zj-Cj -3 0 1 0

-36

Cj 0 0 0 -1 0 -1 HB

VB x y

x 0 1 0

12

0

1 0

12

Zj-Cj -3 0 1 0

-36

Tabel Akhir Fase 1

Cj 0 0 0 -1 0 -1 HB

VB x y

0 1 0

12

0 0 1

6

Zj-Cj 0 0 0 1 0 1 0

→1

4𝐵2

B1-2B2

B3+6B2

B2-1

2𝐵1

B3+3𝐵1

→1

3𝐵1


46

Tabel Awal Fase 2

Cj 8 6 HB

VB x y

8 1 0 12

6 0 1 6

Zj-Cj 0 0 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

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 Bahan yang diperlukan

Kayu Plastik Baja

P 1 3 2

Q 3 4 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

Aktivitas 1


47

Jawaban


48

2.

min 1 2

1 2 1 2 1 2 1 2

2 3

: 2 16; 3 20; 10; , 0

z x x

pembatas x x x x x x x x

Jawaban :


49

3.

2 3 5

: 7;2 5 10; , , 0

maksz x y z

pembatas x y z x y z x y z

Jawaban :


50

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 :


51


52

Buatlah simpulan dari pembelajaran yang telah di lakukan?

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

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

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

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

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

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

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

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


Aktivitas 2

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.

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.

Maks Min DUAL

Min Maks DUAL


54

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 sumber-

sumber 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 batasan-

batasan <, sedangkan model minimisasi dual memiliki batasan-batasan

>.

Handout Program Linier : Dual, Primal dan Kemerosotan

55

1.2. Contoh Kasus :

Maksimum :

Kendala :

Maka dualnya menjadi :

Minimumkan :

Kendala :

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

]

Primal

Dual


56

Dual, matriks koefisien dualnya : [

5

]

Masalah dualnya dapat ditulis sbb :

Maksimumkan :

Kendala :

PL menjadi :

Tabel Awal VD

VD Z u v a b NB

Z 1 -40 -50 0 0 0

a 0 2 3 1 0 3

b 0 4 2 0 1

VD Z u v a b NK

Z 1 -40 -50 0 0 0

v 0

1

0 1

b 0 4 2 0 1

𝐵

B1+50B2

B3-2B2


57

Tabel 2

VD Z u v a b S

Z 1

0

0 50

v 0

1

0 1

B 0

0

1

VD Z u v a b S

Z 1

0

0 50

V 0

1

0 1

U 0 0

Tabel Akhir

VD Z u v a b S

Z 1 0

0

v 0 1

0

u 0 0

Karena dari baris objektif (B1) sudah tidak ada yang negatif maka iterasi selesai.

Dari perhitungan di atas di dapat bahwa ⁄ .

𝐵

𝐵

𝐵

B2-

3𝐵


58

Untuk memastikan kebenaran ini, akan dihitung juga masalah primalnya

yaitu :

Minimumkan : 5

Kendala :

Penyelesaian :

Tabel Awal Simpleks

Cj 0 0 0 -1 -1 Harga

Basis Rasio Variabel

Basis x y a b c d

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 0 0 -1 -1 Harga

Basis Variabel

Basis x y a b c d

y -1

1

0

0 10

d -1 3 2 0 -1 0 1 50

Zj-Cj -5 -6 1 1 0 0 -90

B2-2B1

B3+6B1

1

4B1


59

Tabel 1

Cj 0 0 0 -1 -1 Harga

Basis r Variabel

Basis x Y a b c d

y 0

1

0

0 10 20

d -1 2 0

-1

1 30 15

Zj-Cj -2 0

1

0 -30

Cj 0 0 0 -1 -1 Harga

Basis Variabel

Basis x y a b c d

y 0

1

0

0

5

x 0 0

15

Zj-Cj 0 0 0 1 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

𝐵

B1-1

B2

B3+2B2


60

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 Pemilihan variabel secara sembarangan Siklus


61

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

Selesaikan setiap permasalahan berikut:

1. Seseorang memerlukan 10, 12 dan 12 unit bahan kimia A, B, dan C berturut-

turut 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

Aktivitas 1


62

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 :


63

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 Lemari Meja Kursi Ketersediaan waktu

Kayu Finishing 4 jam 2 jam 1,5 jam 20 jam

Pengecatan 2 jam 1,5 jam 0,5 jam 8 jam Harga Jual (Ribuan Rp) 600 300 200

Formulasikan persolaan utama (primal problem) dan persoalan rangkap (dual

problem) dari pemprograman linier tersebut di atas.

Jawaban :


64

3. Formulasikan persolaan utama (primal problem) dan persoalan rangkap (dual

problem) pemprograman linier berikut dan cari solusi optimumnya.

Minimumkan :

Fungsi kendala :

Jawaban:


65


66

Berikan kesimpulan dari pembelajaran yang telah

dilakukan!

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

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

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

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

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

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

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

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

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

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


Aktivitas 2

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-


68

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 : dan

dengan 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 :

Handout Program Linier : Model Transportasi

69

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

ORIGIN DESTINATION

Kapasitas Origin Per

Priode D1 D2 D3 Dn (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 komponen-

komponen positif.


70

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)


71

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.


72

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)


73

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


74

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.

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

Biaya kesempatan = implied cost – biaya sebenarnya


75

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) =


76

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)

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.

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

Langkah 1

Langkah 2


77

diperbaiki.

Merancang peningkatan program Sel kosong yang memiliki

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.

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

Langkah 3

Langkah 4


78

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 perhitungan-

perhitungan 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:


79

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)


80

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 :

b1 = 50 a1 = 30

b2 = 40 a2 = 60

O1

O2

D1

D2


81

Penyajian : c11 = 3, c12 = 5 , c21 = 1, c22 = 2

Origin D1 D2 bi

3 5

O1 30 20 50

1 2

O2 0 40 40

ai 30 60

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 bi

3 5

O1 29(-) 21(+) 50

1 2

O2 1+ 39(-) 40

ai 30 60

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)


82

jadi solusinya adalah:

30

50 30

20

40 60

40

Jadi dalam contoh ini tabel pertama langsung memberikan hasil yang optimum.

2. Perhatikan skema model transportasi berikut :

b1 = 80 a1 = 50

b2=20 a2 = 50

Penyajian: c11 = 4 c12 = 3 c21 = 2 c22 = 5

Penyelesaian :

Langkah 1 :

D1 D2 bi

3 5

O1 50 (+)30 80

1 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 :

O2 D2

O1

D1

O2 D2

O1

D1


83

D1 D2 bi

4 3

O1 49 (+)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 X21 satu-satunya kotak dengan c21* = 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 bi

4 3

O1 30(+) (-)50 80

2 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:


84

80 30 =50

50

20 20 =50

G. Soal Latihan

Kerjakan soal berikut :

1. 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 masing-

masing 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

D1 D2 D3 D4 Supply

bi

O1 4 5 6 7

100

O2 5 2 1 7

100

O3 6 6 2 5

100

O4 1 3 6 4

100

Demand ( a)j 75 75 160 90 400 400

Atau pakai North West Corner (mulai dari barat laut)

Atau pakai Least Cost Method (pilih yang costnya terkecil)

O2 D2

O1

D1

Aktivitas 1


85

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)


86

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, k-

14, 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 = ...............................................................................................


87

Jadi solusinya adalah sebagai berikut:

100 75 -75

25

100 100 -75

60

100 -160

75 40

100 25 -90

2. 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 D3 bi

O1 8 5 6

120

O2 15 10 12

80

O3 3 9 10

80

aj 150 70 60 280 280

O1 = pabrik di Cirebon D1 = gudang di Semarang

O2 = pabrik di Bandung D2 = gudang di Jakarta

O3 = pabrik di Cilacap D3 = gudang di Purwokerto

O1 D1

O2 D2

O3 D3

D4 O4


88

3.

Jawaban :

O1 D1

O2

O3

D2

D3


89


90


91

Kesimpulan apa yang dapat Anda ambil pada pembelajaran ini :

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

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

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

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

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

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

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

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

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

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


Aktivitas 2


92

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

dosen pengampuh : meyta dwi kurniasih,...

Documents