Quiz Matematika Bisnis : Linear Programming

LINEAR PROGRAMING :SIMPLEKS

A. MAKSIMASI PROFIT

Maksimasi Profit :

Kendala:

I. TABEL SIMPLEKS AWAL

I.1. Ubah persamaan dengan menambahkan variable slack

I.2. Ubah persamaan kendala ke dalam bentuk matriks

I.3. Susun Bentuk variabel simpleks awal (Bentuk baku) : Initial Basic Feasible Regression

Atau

• Slack variabel (s1, s2, s3) masih merupakan basic variabel (memiliki nilai masing-masing 1 dan entry 0) yang membentuk matriks indentitas.
• X1 dan x2 merupakan non basic variabel (karena nilai x1 dan x2 = 0 / belum ada output) karena itu s1 = 36, s2 = 40 dan s3 = 28

II. ELEMEN PIVOT DAN PERUBAHAN DASAR

Lakukan proses perubahan basis yaitu pemilihan variable yang dimasukkan dan dikeluarkan.

II.1. Cari Indikator negatif dengan niali absolut terbesar akan menentukan variabel yang masuk dalam basis.

-5 (kolom pertama atau x1) merupakan indikator negatif dengan nilai absolut terbesar sehingga x1 masuk dalam basis (KOLOM x1 menjadi KOLOM PIVOT)

II.2. Variabel yang dieliminasi ditentukan dari rasio pemindahan. Rasio pemindahan ditentukan dengan membagi elemen kolom konstan dengan kolom pivot (dengan mengabaikan rasio-rasio yang lebih kecil atau sama dengan nol).

Maka baris 1 adalah baris pivot.

Elemen pivot adalah 6 (perpotongan kolom varaibel yang masuk ke basis dan baris yang berhubungan dengan variabel yang meninggalkan basis)

III. PIVOTING

• Pengubahan elemen pivot menjadi 1 dan elemen lainnya menjadi matriks identitas

III.1. Kalikan baris pivot dengan kebalikan nilai elemen pivot (kalikan 1/6)

Tabel Kedua:

III.2. Selesaikan kolom pivotnya

• Kurangkan 5 kali baris 1 dari baris 2
• 2 kali baris 1 dari baris 3
• Tambahkan 5 kali baris 1 ke baris 4

Hasil mendasar dengan menetapkan x2= 0 dan s1=0 maka x1=6, s2= 10 dan s3=16.

IV. OPTIMASI

 

• -4/3 satu-satunya indikator negatif maka x2 masuk dalam kolom basis dan kolom 2 merupakan kolom pivot
• Bagi kolom konstanta dengan dengan kolom pivot, ambil rasio terkecil menjadi elemen pivot baru (10/3)
• Kalikan baris 2 dengan 3/10

• Kurangkan1/3 kali baris 2 dari baris 1
• 10/3 kali baris 2 dari baris 3
• Tambahkan 4/3 kali baris 2 ke baris 4

Karena tidak ada indikator negatif yang tertinggal dalam baris terakhir maka ini merupakan penyelesaian yang optimal, sehingga x1 = 5, x2 = 3, s1 = 0, s2 = 0, s3 = 6.

Fungsi objektif maksimum pada Π = 34.

Atau

Interpretasi :

Laba maksimum sebesar 34 hanya dapat dicapai jika s1 dan s2 = 0 dengan nilai (jumlah x1 = 5 dan x2 = 3 unit serta s3 (sisa kapasitas yang tidak tercapai pada unit 3)

Cek:

Π = 5 (5) + 3 (3)= 34 (OK)

Nilai ½ dan 2/5 pada kolom s1 dan s2 merupakan SHADOW PRICE atau IMPUTED PRICES atau marginal value dari tiap-tiap unit di masing-masing kendala.

Jika ½ (36) + 2/5 (40) = 34 (OK)

B. MINIMISASI BIAYA

C = 2x1 + 4x2

Kendala:

I. Tabel Simpleks Awal

I.1. Ubah pertidaksamaan menjadai persamaan dengan mengurangkan variabel surplus

I.2. Ubah dalam Bentuk Matriks

 

Jika x1 = 0 dan x2 = 0 maka s1 =-14, s2= -12 dan s3= -18 (nilai negatif tidak mungkin, untuk mengatasi tersebut dibuat VARIABEL BUATAN (ARTIFICIAL VARIABLES)

III.3. Tambahakan variable buatan V ≥ 0

• dipakai untuk menghasilka penyelesaian dasar awal yang mungkin
• tidak mempunyai makna ekonomi
• ditambahkan terpisah bersifat “lebih besar datau sama dengan”.

II. Tabel Simpleks (Yang disesuaikan untuk minimisasi)

II.1. Buat Matriks Simpleks Awal

Fungsi objektif memiliki  koefisien nol untuk variable surplus dan koefisien M (variable buatan) nilainya bilangan sangat besar dan tidak mungkin.

II.2. Pindahkan M dari kolom variebl buatan : M kali (baris 1 + baris 2 + baris 3) ke baris 4

Menghasilkan tabel awal:

 

Penyelesaian mendasar pertama jika x1=x2=s1=s2=s3=0 maka A1=14, A2= 12 dan A3=18 dan fungsi objektif sama dengan 44M (Bilangan besar yang tidak mungkin) Cari perubahan basis untuk menurunkan biaya.

III. ELEMEN PIVOT

III.1. Untuk minimisasi, indicator positif terbesar akan menentukan kolom pivot dan variabel basis. (44 M bukan indikator)

Jadi 5M-4 merupakan indikator positif terbesar. X2 dimasukkan ke basis dan kolom 2 adalah kolom pivot

III.2. Cari rasio konstanta dan kolom 2 yang memiliki rasio terkecil. Rasio terkecil adalah 18/3, maka baris 3 adalah baris pivot dan elemen pivot adalah 3.

IV. Pivoting

IV.1. Kurangi elemen pivot menjadi 1 dengan mengalikan baris 3 dengan 1/3

IV.2. Rampungkan kolom Pivot

• Mengurangkan baris 3 dari baris 1 dan baris 2
• (5M-4) kali baris 3 dari baris 4

V. Pengulangan (Reiterasi)

• Selama masih ada indikator positif , proses terus berjalan.
• Kolom pivot baru adalah baris 1. X1 masuk dalam basis dan A1 meninggalkan basis. Elemen pivot 5/3 (Rasio Konstanta dan kolom pivot yang memiliki nilai terkecil)

 

• Kalikan baris 1 dengan 3/5

• Rampungkan kolom 1

·         Mengurangkan 2/3 baris 1 dari baris 2

·         1/3 baris 1 dari baris 3

·         (7M – 2)/3 baris 1 dari baris 4

• Cari Kembali nilai indokator terbesar yaitu kolom 3 dan Rasio terkecil yaitu 2/5

 

VI. Pivot Keempat

VI.1. Kalikan Baris 2 dengan 5/2

VI.2. Selesaikan pivoting :

• Tambahkan 3/5 baris 2 ke baris 1
• Kurangkan 1/5 baris 2 dari baris ke 3
• (2M-2)/5 baris 2 dari baris 4

Sehingga:

• Semua indikator negatif, suatu penyelesaian optimal telah tercapai

Hasil x1 = 9; x2 = 3 dan s1 = 7 dan Biaya opyimum minimal sebesar Rp 30,-

Keslimpulan:

1. dengan s2 = s3 = 0 kebutuhan kedua dan ketiga dipenuhi secara tepat tidak ada yang berlebih, s1 = 7, kebutuhan pertama terpenuhi secara berlebih sebesar 7 unit.
2. nilai absolut s2 dan s3 = 1 maka pengurangan 1 unit kebutuhan kedua dan ketiga akan mengurangai biaya sebesar Rp 1,-. Sedangkan s1 = 0 maka pengurangan satu unit dalam kebutuhan gizi pertama tidak akan mengurangi biaya.

SOAL:

1.  (maksimasi profit)

Kendala :

6x1 + 3 x2 + 5x3 ≤ 30

2x1 + 2x2 + 10x3 ≤ 50

X1, x2, x3 ≥ 0

2. c= 60x1 + 80x2

Kendala:

2x1 + 3 x2 ≥ 36

2x1 + 2x2 ≥ 28

8x1 + 2x2 ≥ 32

X1, x2 ≥ 0