tugas program linier
TRANSCRIPT
PROGRAM LINEAR
(METODE SIMPLEKS)
Oleh :
ANDRIYA SWARSIH10536 4183 11
UNIVERSITAS MUHAMMADIYAH MAKASSARFAKULTAS KEGURUAN DAN ILMU PENDIDIKAN
JURUSAN PENDIDIKAN MATEMATIKA2013
PROGRAM LINEAR DENGAN METODE SIMPLEX
1) Fungsi Tujuan : z = 8x + 3y
Fungsi Pembatas : 50x + 100y ≤ 1.200.000
50x ≥ 3.000
5x + 4y ≥ 60.000
Bentuk baku diperoleh dengan menambahkan variabel slack pada kendala
pertama, mengurangkan variabel surplus pada kendala kedua. Sehingga
diperoleh :
Minimumkan : Z = 8x + 3y + 0S1 + 0S2 + 0S3 +MA1 + MA2
50x + 100y + S1 = 1.200.000
50x - S2 + A1 = 3.000
5x + 4y – S3 + A2 = 60.000
Table Simpleks Awal
Basi
s
X1 X2 S1 S2 S3 A1 A2 NK Rasio
Z 55M
-8
4M
-3
0 -
M
-
M
0 0 63.000M
S1 50 100 1 0 0 0 0 1.200.00
0
1.200.000:50=24.00
0
A1 50 0 0 -1 0 1 0 3.000 3.000:50 = 60
A2 5 4 0 0 -1 0 1 60.000 60.000 : 5 = 12.000
Iterasi Pertama
Basi
s
X1 X2 S1 S2 S3 A1 A2 NK Rasio
Z 0 4M
-3
0 0,1M
-0,16
0 -
1,1M+0,1
6
0 59.700M+48
0
S1 0 100 1 1 0 -1 0 1.197.000 11.97
0
X1 1 0 0 -0,02 0 0,02 0 60
A2 0 4 0 0,1 -1 -0,1 1 5700 1.425
Iterasi Kedua
Basis X1 X2 S1 S2 S3 A1 A2 NK
Z 0 0 0 -
0,085
M-
0,75
-
M+0,085
-
M+0,75
54.000M+4755
S1 0 0 1 -1,5 25 1,5 -25 1.054.500
X1 1 0 0 -0.02 0 0.02 0 60
X2 0 1 0 0,025 -
0,25
-0,025 0,25 1425
Iterasi kedua adalah optimal karena koefisien pada persamaan Z semuanya nonpositif, dengan X1= 60, X2 = 1425 dan Z = 54.000M+4755
2) PT Yummy food memiliki sebuah pabrik yang akan memproduksi dua jenis
produk yaitu vanilla dan violette. Untuk memproduksi kedua produk
tersebut diperlukan bahan baku A, bahan baku B dan jam tenaga kerja.
Maksimum pengerjaan bahan baku A adalah 60kg per hari, bahan baku B
30kg per hari dan tenaga kerja 40jam per hari. Kedua jenis produk
memberikan sumbangan keuntungan sebesar Rp40,00 untuk vanilla dan
Rp30,00 untuk violette. Masalah yang dihadapi adalah bagaimana
menentukan jumlah unit setiap produk yang akan diproduksi setiap hari.
Kebutuhan setiap unit produk akan bahan baku dan jam tenaga kerja dapat
diliha pada tabel berikut ini:
Jenis bahan baku dan
tenaga kerja
Kg bahan baku dan jam tenaga
kerja
Maksimum
Penyediaan
Vanilla Violette
Bahan baku A 2 3 60Kg
Bahan baku B - 2 30Kg
Tenaga Kerja 2 1 40jam
Sumbangan
keuntungan
Rp40,00 Rp30,00
Penyelesaian:
Z = Rupiah keuntungan per hari
X1 = Jumlah vanilla yang diproduksi/perhari
X2 = jumlah violette yang diproduksi/hari
Langkah 1
Formulasi LP (bentuk standar)
Fungsi tujuan Zmax = 40X1 + 30X2
Fungsi kendala I. 2X1 + 3X2 ≤ 60
II. 2X2 ≤ 30
III. 2X1 + 1X2 ≤ 40
IV. X1,X2 ≥ 0
Diubah menjadi:
2X1 + 3X2 + S1 + 0S2 + 0S3 = 60
2X2 + 0S1 + S2 + 0S3 = 30
2X1 + 1X2 + 0S1 + 0S2 + S3 = 40
40X1 + 30X2 + 0S1 + 0S2 + 0S3
C1 = 40, C2 = 30, C3 = 0, C4= 0, C5 = 0
Langkah 2
Tabel simplex awal masalah PT Yummy Food
Cj 40 30 0 0 0
Ci BV X1 X2 S1 S2 S3 Bi
0 S1 2 3 1 0 0 60
0 S2 0 2 0 1 0 30
0 S3 2 1 0 0 1 40
Zj 0 0 0 0 0 0
Cj-ZJ 40 30 0 0 0
Langkah 3
Apakah tabel tersebut sudah optimal?
Belum, karena tabel optimal bila nilai yang terdapat pada baris Cj – Zj ≤ 0
Langkah 4
Penyelesaian dengan cara iterasi
1. Menentukan kolom kunci, yaitu kolom yang memiliki nilai Cj-Zj
terbesar yaitu kolom x1. Dengan demikian x1 akan masuk dalam basis
2. Menentukan baris kunci, yaitu baris yang memiliki angka indeks
terkecil dan bukan negatif. Dalam hal ini baris s3. Dengan demikian
s3 akan keluar dari basis dan tempatnya akan digantikan oleh x1
3. Menetukan angka kunci. Angka kunci adalah angka yang terdapat
pada persilangan kolom kunci dengan baris kunci, dalam hal ini angka
kunci = 2
4. Mencari angka baru yang terdapat pada baris kunci, dengan cara
membagi semua angka yang terdapat pada baris kunci dengan angka
kunci
Angka baru = 40/2, 2/2, ½, 0/2, 0/2, ½
Atau = 20, 1, ½, 0,0 ½
5. Mencari angka baru pada baris lain, yaitu :
Baris S1
Angka lama = [ 60 2 3 1 0 0 ]
Angka baru = [ 20 1 ½ 0 0 ½] (2)
_
Angka baru = [20 0 2 0 0 -1]
Baris S2
Angka lama = [ 30 0 2 0 1 0]
Angka baru = [ 20 1 ½ 0 0 1/2] (0)
_
Angka baru = [ 30 0 2 0 1 0]
Hasil perhitungan di atas, akan nampak pada tabel baru simplex yaitu
tabel yang merupakan hasil iterasi pertama.
Cj 40 30 0 0 0
Ci BV X1 X2 S1 S2 S3 Bi
0 S1 0 2 1 0 -1 20
0 S2 0 2 0 1 0 30
40 X1 1 ½ 0 0 ½ 20
Zj 40 20 0 0 20
Cj-ZJ 0 10 0 0 0
Tabel iterasi 1 belum optimal sehingga harus diulang langkah di atas dan
akan di dapat tabel iterasi 2:
Cj 40 30 0 0 0
Ci BV X1 X2 S1 S2 S3 Bi
30 X1 0 1 ½ 0 -1/2 10
0 S2 0 0 -1 1 1 10
40 S3 1 0 -1/4 0 ¾ 15
Zj 40 30 5 0 15
Cj-ZJ 0 0 -5 0 -15 900
Solusi optimum tabel iterasi 2 menunjukan bahwa total nilai Z = 900
dengan masing-masing variabel keputusan X1 = 15 dan X2 = 10.
Variabel basis Koefisien fungsi
tujuan
Nilai variabel
basis
X2 30 10 300
S2 0 10 0
X1 40 15 600
JUMLAH 900
KESIMPULAN:
1. Pada tabel iterasi 2 merupakan tabel akhir simplex, dengan solusi optimal
adalah :
X1 (vanilla) = 15 unit
X2 (violette) = 10 unit
Z (keuntungan) = Rp 900,00
2. Kendala kedua (bahan baku B) masih tersisa sebanyak 10 Kg yang
ditunjukan oleh nilai S2 =10, pada tabel optimal
3. Kendala 1 dan 3 tidak ada sisa (full capacity), yang ditunjukan oleh nilai
S1 = S3 = 0 ( variabel nonbasis). Hal ini juga dapat dibuktikan dengan
memasukan nilai S1 dan S2 ke dalam kendala 1 dan 3
Kendala 1 : 2X1 + 3X2 = 60
2 (15) + 3 (10) =60
60 = 60
Bahan baku yang digunakan = yang tersedia
Kendala 3 : 2X1 + 1X2 = 40
2 (15) + 1(10) =40
40 = 40
Jam kerja yang digunakan = yang tersedia
3) Gunakan metode simpleks untuk memaksimumkan
= 8000 X1 + 7000 X2
Dengan kendala :
2 X1 +3 X2≤242 X1 + X2≤16X1+4 X 2≤27
X1≥0 dan X2≥0
Penyelesaian :
1. Fungsi tujuan dalam bentuk implisit :
- + 8000 X1 + 7000 X2 = 0≤
2. Karena masalah maksimisasi, maka kendala harus ditambah
variabel slack
2 X1+3 X2+S1 =242 X1+ X2+S2 =16X1+4 X2+S3 =27
3. Tabel Simpleks I (awal)
Variabel Dasar
X1 X2 S1 S2 S3 Nilai kanan (konstanta)
Baris 1 =
Baris 2 = S1
Baris 3 = S2
Baris 4 = S3
-1 8000 7000 0 0 0
0 2 3 1 0 0
0 2 1 0 1 0
0 1 4 0 0 0
0
24
16
27
Kolom kunci adalah kolom X1
Baris kunci adalah baris 3
Langkah-langkah Membentuk Tabel Simpleks II
1. Kolom kunci adalah kolom yang berada pada angka positif terbesar dalam
baris pertama, yaitu kolom X1.
2. Baris kunci adalah :
Baris 2 =
Nilai kanan ( NK )Angka kolom kunci ( AKK )
=242
=12
Baris 3 =
Nilai kananAngka kolom kunci
=162
=8→ positif terkecil
Baris 4 =
Nilai kolomAngka kolom kunci
=271
=27
Baris kunci adalah baris 3
3. Baris kunci baru (baris 3 baru) :
Baris kunci lama :
X1 X2 S1 S2 S3 NK
0 2 1 0 1 0 16
Baris kunci baru = Baris lama dibagi angka kunci
0 1 ½ 0 ½ 0 8
4. Baris lain yang baru
Baris (1) Baru = Baris (1) lama – (Baris kunci baru x 8000)
Baris (2) Baru = Baris (2) lama – (Baris kunci baru x 2)
Baris (4) Baru = Baris (4) lama – (Baris kunci baru x 1)
5. Tabel Simpleks II
Variabel Dasar
X1 X2 S1 S2 S3 Nilai
Kanan
Baris (1) =
Baris (2) = S1
Baris (3) = X1
Baris (4) = S3
-1 0 3000 0 -4000 0
0 0 2 1 -1 0
0 1 ½ 0 ½ 0
0 0 3,5 0 -½ 0
-64.000
8
8
19
Langkah Membentuk Tabel Simpleks III
Kolom kunci = Kolom X2
Baris kunci =
Baris 2 =
NKAKK
=82=4→ positif terkecil
Baris 3 =
NKAKK
= 81 /2
=16
Baris 4 =
NKAKK
=193,5
=5 , 43
Baris kunci adalah baris 2
Baris kunci baru (baris 2 baru) =
X1 X2 S1 S2 S3 NK
0 0 1 ½ -½ 0 4
Baris lain yang baru =
Baris (1) Baru = Baris (1) lama – (Baris kunci baru x 3000)
Baris (3) Baru = Baris (3) lama – (Baris kunci baru x ½)
Baris (4) Baru = Baris 94) lama – (Baris kunci baru x 3,5)
Tabel Simpleks III
Variabel Dasar
X1 X2 S1 S2 S3 Nilai
Kanan Baris (1) =
Baris (2) = X2
Baris (3) = X1
Baris (4) = S4
-1 0 0 -1500 -2500 0
0 0 1 ½ -½ 0
0 1 0 -1/4 ¾ 0
0 0 0 -7/4 5/4 1
-76.000
4
6
5
Karena pada baris (1) tidak ada lagi yang bernilai positif, penyelesaian optimal
selesai.
X1 = 6 ; X2 = 4 ; - = -76.000
*= 76.000.
4) Minimumkan: Z = 2X1 + 10X2
Kendala : 2X1 + X2 ≤ 6 5X1 + 4X2 ≥ 20
X1 ≥ 0 dan X2 ≥ 0
Tentukan X1, X2 yang meminimum Z=…?
Penyelesaian:
Tahap 1: Memasukkan Variable Slack dan Variable Buatan
Fungsi Tujuan : Z = 2X1 + 10X2 + M.A1Kendala :2X1 + X2 + S1 = 65X1 + 4X2 - S2 + A1 = 20
Keterangan: S1 dan S2: variabel SlackA1 : Variabel Buatan (variabel artifisial).
Tahap 2: Langkah Membentuk Tbl Simpleks I:
Membentuk fungsi tujuan untuk siap dimasukkan ke Tabel Simpleks I:
Minimumkan: - Z + 2X1 + 10X2 + M.A1 = 0
Karena nilai M pada fungsi tujuan harus nol, maka fungsi tujuan semula harus diubah menjadi funsi tujuan yang disesuaikan.
Fungsi Tujuan
X1 X2 S1 S2 A1 NK
Fungsi Tujuan
2 10 0 0 M 0
Kendala (2) x M
5M 4M 0M -1M 1M 20M
Fungsi Tujuan Baru
(2-5M) (10-4M) 0 +M 0 -20M
Tabel Simpleks I:
Variabel dasar
X1 X2 S1 S2 A1 NK
F.Tujuan(Cj-Zj)
(2-5M) (10-4M) 0 +M 0 -20M
S1 2 1 1 0 0 6S2 5 4 0 -1 1 20
Tahap 3: Langkah Membentuk Tabel Simpleks II.
(1). Kolom Kunci : Kolom X1 karena memiliki nilai negatif terbesar pada baris Cj-Zj.
(2). Baris Kunci (NK/ AKK):
Baris 2 (Baris S1): NK/AKK = 6/2 = 3....(BK)Baris 3 (Baris S2): NK/AKK = 20/5 = 4.
(3). Baris Kunci Baru (Baris 2) Baru: BKB = (BKL/AK) Baris Kunci X1 X2 S1 S2 A NKBKB=BKL/AK
2/2 ½ ½ 0/2 0/2 6/2
BKB 1 ½ ½ 0 0 3
(4). Baris Lain yang Baru: a. Baris 1 (Baris Cj-Zj) baru = Baris Lama – (AKK.BKB)
Baris 1(Cj-Zj)
X1 X2 S1 S2 A1 NK
Baris 1 Lama
(2-5M) (10-4M) 0 M 0 -20M
BKB 1 ½ ½ 0 0 3AKKxBKB
(2-5M)(1) (2-5M)(1/2) (2-5M)(1/2) (2-5M)(0) (2-5M)(0)
(2-5M) (1-5/2M) (1-5/2M) 0 0
(2-5M).(3)
(6-15M)Baris 1 Baru
0 (9-3/2M) (-1+5/2M) M 0 (-6-5M)
b. Baris 3 (Baris S2) Baru:Baris 3 X1 X2 S1 S2 A1 NKBaris 3 Lama
5 4 0 -1 1 20
BKB 1 ½ ½ 0 0 3BKBxAKK
5(1) 5(1/2) 5(1/2) 5(0) 5(0)
5 2,5 2,5 0 0
5(3)
15Baris 3 Baru
0 3/2 -2,5 -1 1 5
Tabel Simpleks IIVariabel Dasar X1 X2 S1 S2 A1 NKBaris 1Cj-Zj
0 (9-3/2M) (-1+5/2M) M 0 (-6-5M)
Baris S1.... Baris (X1)
1 ½ ½ 0 0 3
Baris S2 0 3/2 -5/2 -1 1 5
Tahap IV: Langkah Membentuk Tabel Simpleks III
Dengan cara yang sama dapat ditentukan:(1). Kolom Kunci: Kolom X2 (Negatif terbesar)(2). Baris Kunci: Baris 3 (Baris S2);(3). Baris Kunci Baru;(4). Baris Lain yang baru.
Tabel Simpleks IIIVariabel Dasar X1 X2 S1 S2 A1 NKBaris 1Cj-Zj
1 0 14 6 (-6+M) -36
Baris S1...(X1) 1 0 4/3 1/3 -1/3 4/3Baris S2...(X2) 0 1 -5/3 -2/3 2/3 10/3.
Karena : Baris 1 (Cj-Zj) sudah positif semua dan telah terbentuk matrik Identity untuk kolom 1 dan kolom 2, maka Tabel Simpleks selesai;
Nilai Optimum:
-Zj = -36...... Zj = 36, X1 = 4/3, X2 = 10/3.
5) Minimumkan : C = 6X1 + 24X2
Kendala: X1 + 2X2 ≥ 3 X1 + 4X2 ≥ 4
Dan X1, X2 ≥ 0
Penyelesaian:
Langkah membentuk Tabel Simpleks I:
1. Penyesuaian Fungsi tujuan dan Kendala:
Minimisasi: C = 6X1 + 24X2 +M.A1+ M.A2 Kendala : X1 + 2X2 –S1 + A1 = 3 X1 + 4X2 – S2+ A2 = 4 Keterangan: S1, S2 : Variabel Slack A1,A2 : Variabel Buatan
2. Penyesuaian Fungsi tujuan agar siap masuk pada Tabel Simpleks I, karena
nilai M akan dianggap Nol.
a. Fungsi Tujuan dalam bentuk Implisit
- C + 6X1 + 24X2 + MX1 + MX2 = 0
b. Penyesuain Fungsi Tujuan :Fungsi Tujuan
X1 X2 S1 A1 S2 A2 NK.....?
Cj-Zj 6 24 0 M 0 M 0Kendala (1) x M
1M 2M -M M 0 0 3M
Cj-Zj (6-M) (24-2M) M 0 0 M -3MKendala (2) xM
1M 4M 0 0 -M M 4M
Cj-Zj (6-2M) (24-6M) M 0 M 0 -7M (nilai M =0)
c.Tabel Simpleks I
Variabel Dasar
X1 X2 S1 A1 S2 A2 NK
Cj-Zj (6-2M) (24-6M) M 0 M 0 0A1 1 2 -1 1 0 0 3A2 1 4 0 0 -1 1 4
Langkah Membentuk Tabel Simpleks II:
1. Kolom Kunci: Kolom X2 (Negatif terbesar)2. Baris Kunci:
Baris 2 =NK/AKK = 3/2 = 1,5 Baris 3 : NK/AKK = 4/4 = 1 ...Baris Kunci
3. Baris Kunci Baru (BKB = BL/AK);
4. Baris lain (Baris 1 dan Baris 2) yang baru;
5. Tabel Simpleks II:
Variabel Dasar
X1 X2 S1 A1 S2 A2 NK
Cj-Zj (-1/2M) 0 M 0 (6-1/2M) (-6+3/2M) (-24+6M)A1 ½ 0 -1 1 ½ -1/2 1A2...X2 ¼ 1 0 0 -1/4 1/4 1
Langkah Membentuk Tabel Simpleks III:
Kolom Kunci: Kolom X1(Negatif terkecil)Baris Kunci:
Baris 2= NK/AKK = 1/(1/2)=2..Baris Kunci Baris 3 : NK/AKK = 1/(1/4) = 4.
Baris Kunci Baru (BKB = BL/AK);
Baris lain (Baris 1 dan Baris 3) yang baru.
Tabel Simpleks III:
Variabel Dasar
X1 X2 S1 A1 S2 A2 NK.....?
Cj-Zj 0 0 0 M 6 (-6+M) (-24+7M)A1...X1 1 0 -2 2 1 -1 2X2 0 1 ½ -1/2 -2/4 2/4 1/2
Titik Optimal:X1 = 2 ; X2 = ½; -Zj = -24+7M....Zj=C= 24.
6) Maksimumkan Z=3 X1+2 X 2
dengan syarat :
X1+X2≤152 X1+ X2≤28X1+2 X2≤20
X1 , X2≥0
Bentuk baku masalah LP tersebut adalah :
Z−3 X1−2 X2−0S1−0S2−0S3=0X1+X2 + S1 =152 X1+ X2 + S2 =28
X1+2 X2 + S3 =20
Berdasarkan bentuk baku diatas, tentukan solusi awal (initial basic solution)
dengan menetapkan n-m variable non basis sama dengan nol. Dimana n jumlah
variabel dan m banyaknya kendala. Yaitu, n sebanyak 2 buah dan m sebanyak 3
kendala. Solusi dengan menggunakan tabel simpleks adalah sbb :
Tabel Simpleks Awal
Basis X1 X2 S1 S2 S3 Solusi RasioZ -3 -2 0 0 0 0S1 1 1 1 0 0 15 15S2 (2) 1 0 1 0 28 14S3 1 2 0 0 1 20 20
Tabel Iterasi Pertama
Basis X1 X2 S1 S2 S3 Solusi RasioZ 0 - ½ 0 3/2 0 42S1 0 (½) 1 - ½ 0 1 2X1 1 ½ 0 ½ 0 14 28S3 0 3/2 0 - ½ 1 6 4
Tabel Simpleks Kedua (optimum)
Basis X1 X2 S1 S2 S3 SolusiZ 0 0 1 1 0 43X2 0 1 1 - ½ 0 2X1 1 0 -1 1 0 13S3 0 3/2 0 - ½ 1 6
Pada iterasi kedua telah tercapai solusi optimum dengan X1 = 13, X2 = 2 dan Z
= 43. Pada tabel iterasi kedua (optimum) S3 = 0 artinya pengambil keputusan
akan menggunakan seluruh persediaan sumber daya pertama dan kedua, tetapi
masih memiliki sumber daya ketiga sebanyak 6 karena tidak digunakan.
7) Persamaan matematis suatu program linier adalah sebagai berikut :
Minimasi : Z = 6X1 + 7,5X2
Dengan pembatas :
7X1 + 3X2 ≥ 210
6X1 + 12X2 ≥ 180
4X2 ≥ 120
X1, X2 ≥ 0
Carilah harga X1 dan X2 ?
JAWABAN
Pada kasus ini kita akan menggunakan metode simplex M (BIG – M), hal ini
dikarenakan pada kasus ini pertidk samaan pembatasnya menggunakan ≥ (lebih
dari sama dengan).
Persamaan Tujuan : Z - 6x1 - 7,5X2 - 0S1 - 0S2 - 0S3 = 0 Baris 0
Persamaan Kendala : 7x1 + 3x2 - S1 +A1 = 210 Baris 1
6x1 + 12x2 - S2 +A2 = 180 Baris 2
4x2 - S3 + A3 = 120 Baris 3
Bagi kendala pertidaksamaan jenis ≤, maka variabel slack ditambahkan untuk
menghabiskan sumber daya yang digunakan dalam kendala. Cara ini tidak dapat
diterapkan pada kendala pertidaksamaan jenis ≥ dan kendala persamaan (=)
persamaan diatas diperoleh karena tanda ≥ harus mengurangi variable surplus.
Untuk mengarahkan artifisial variabel menjadi nol, suatu biaya yang besar
ditempatkan pada A1, A2, dan A3 sehingga fungsi tujuannya menjadi :
Z = 6x1 + 7,5X2 + 0S1 + 0S2 + 0S3 + MA1 + MA2 + MA3
Table simplex awal dibentuk dengan A1, A2, dan A3 sebagai variable basis,
seperti table berikut :
Basis X1 X2 S1 S2 S3 A1 A2 A3 NK RASIO
Z 13M-
6
19M-
7,5
-
M
-
M
-M 0 0 0 510M
A1 7 3 -1 0 0 1 0 0 210 210 : 3 =
70
A2 6 12 0 -1 0 0 1 0 180 180 : 12
= 15
A3 0 4 0 0 -1 0 0 1 120 120 : 4 =
30Dari table diatas kita ketahui bahwa semua BFS belum optimal. Hal ini
dikarenakan seluruh NBV masih mempunyai koefisien yang berharga positif.
Oleh karena itu Untuk x2 terpilih sebagai entry variable karena x2 memiliki nilai
koefisien positif yang paling besar, dan A3 menjadi Leaving Variable. Dan yang
akan menjadi pivot adalah baris 2 karena memiliki rasio paling kecil.
Langkah-langkah ERO Iterasi Pertama :
ERO 1 : Menjadikan nilai koefisien x2 berharga 1 pada baris 2
½ x1 + x2 - 1/12 S2 +1/12 A2 = 15
ERO 2 : Menjadikan nilai koefisien x2 berharga 0 pada baris 0
Z = 9/4 x1 + 0S1 + 15/24 S2 + 0S3 + MA1 + [ M - 15/24]A2 + MA3 + 112,5
ERO 3 : Menjadikan nilai koefisien x2 berharga 0 pada baris 1
11/2 x1 + ¼ S2 + A1 - 1/4 A2= 165
ERO 4 : Menjadikan nilai koefisien x2 berharga 0 pada baris 3
-2x1 + 1/3 S2 - S3 - 1/3 A2 + A3 = 60
Konversi bentuk standard iterasi Pertama :
Z = 9/4 x1 + 0S1 + 15/24 S2 + 0S3 + MA1 + [ M - 15/24]A2 + MA3 + 112,511/2 x1 + ¼ S2 + A1 - 1/4 A2 = 165
-2x1 + 1/3 S2 - S3 - 1/3 A2 + A3 = 60
½ x1 + x2 - 1/12 S2 +1/12 A2 = 15
Tabel Iterasi Pertama
Basis X1 X2 S1 S2 S3 A1 A2 A3 NK RASIO
Z -13/2M-
6
0 0 7/12 -15/24
-M 0 1/24 -
M
0 225M –
112,5
*
A111/2 0 0 1/4 0 1 -1/4 0 165 165 : 5,5
= 30
A3 -2 0 0 1/3 -1 0 -1/3 1 60 *
X2 ½ 1 0 -1/12 0 0 1/12 0 15 15 : 0,5
= 30
Pada fungsi tujuan masih terdapat variable dengan nilai koefisien positif, oleh
karena itu lakukan iterasi kedua.
Langkah-langkah ERO Iterasi Kedua:
ERO 1 : Menjadikan nilai koefisien x1 berharga 1 pada baris 1
x1 + 1/22 S2 + 2/11A1 - 1/22 A2 = 30
ERO 2 : Menjadikan nilai koefisien x1 berharga 0 pada baris 0
Z = 0S1 + 0,725 S2 + 0S3 + MA1 -0,4A1 + [ M – 0,725]A2 + MA3 + 180
ERO 3 : Menjadikan nilai koefisien x1 berharga 0 pada baris 2
0.5 A2 = 0
ERO 4 : Menjadikan nilai koefisien x1 berharga 0 pada baris 3
0,39 S2 - S3 +0,36A1 + 0,21 A2 + A3 = 120
Konversi bentuk standard iterasi kedua :
Z = 0S1 + 0,725 S2 + 0S3 + [M -0,4]A1 + [ M – 0,725]A2 + MA3 + 180
x1 + 1/22 S2 + 2/11A1 - 1/22 A2 = 30
0.5 A2 = 0
0,39 S2 - S3 + 0,36A1 + 0,21 A2 + A3 = 120
Tabel Iterasi Kedua
Basi
s
X1 X2 S1 S2 S3 A1 A2 A3 NK
Z 0 0 0 -
0,72
5
0 -
M+0,
4
-1/2M+0,725
M -
18
0
x1 1 0 0 1/22 0 2/11 -1/22 0 30
A3 0 0 0 0 0 0 ½ 0 0
X2 0 0 0 0,39 -1 0,36 0,21 1 12
0
Iterasi kedua adalah optimum karena koefisien pada persamaan Z
semuanya non positif, dengan x1 = 30, x2 = 120 dan z=-180.
8) PT Unilever bermaksud membuat 2 jenis sabun, yakni sabun bubuk dan
sabun batang. Untuk itu dibutuhkan 2 macam zat kimia, yakni A dan B.
jumlah zat kimia yang tersedia adalah A=200Kg dan B=360Kg. Untuk
membuat 1Kg sabun bubuk diperlukan 2 Kg A dan 6 Kg B. untuk membuat
1 Kg sabun batang diperlukan 5 Kg A dan 3 Kg B. bila keuntungan yang
akan diperoleh setiap membuat 1Kg sabun bubuk = $3 sedangkan setiap 1
Kg sabun batang = $2, berapa Kg jumah sabun bubuk dan sabun batang
yang sebaiknya dibuat ?
JAWABAN
Pemodelan matematika :
Maksimumkan : Z = 3x1 + 2x2
Pembatas : 2x1 + 5x2 = 200
6x1 + 3x2 = 360
Persamaan Tujuan : Z - 3x1 - 2x2 = 0 Baris 0
Persamaan Kendala : 2x1 + 5x2 + A1 = 200 Baris 1
6x1 + 3x2 + A2 = 360 Baris 2
Untuk mengarahkan artifisial variabel menjadi nol, suatu biaya yang besar
ditempatkan pada A1, A2, dan A3 sehingga fungsi tujuannya menjadi :
Z = 3x1 - 2X2 + MA1 + MA2
Basis x1 x2 A1 A2 NK Rasio
Z 8M-3 8M+2 0 0 560M
A1 2 5 1 0 200 200:5=40
A2 6 3 0 1 360 360:3=120
Dari table diatas kita ketahui bahwa semua BFS belum optimal. Hal ini
dikarenakan belum seluruhnya NBV mempunyai koefisien yang berharga
positif. Oleh karena itu Untuk x2terpilih sebagai entry variable karena
x2 memiliki nilai koefisien negatif, dan A1 menjadi Leaving Variable. Dan
yang akan menjadi pivot adalah baris 1 karena memiliki rasio paling kecil.
Langkah-langkah ERO Iterasi Pertama :
ERO 1 : Menjadikan nilai koefisien x2 berharga 1 pada baris 1
0,4x1 + x2 + 0,2A1 = 40
ERO 2 : Menjadikan nilai koefisien x2 berharga 0 pada baris 0
Z = 3,8x1 + [M-0,4]A1 + MA2 - 80
ERO 3 : Menjadikan nilai koefisien x2 berharga 0 pada baris 2
4,8x1 – 0,6A1 + A2 = 240
Konversi bentuk standard iterasi pertama :
Z = 3,8x1 + [M-0,4]A1 + MA2 - 80
0,4x1 + x2 + 0,2A1 = 40
4,8x1 – 0,6A1 + A2 = 240
Basis x1 x2 A1 A2 NK Rasio
Z 4,8M-
3,8
0 0,4-
0,4M
0 240M+80
X2 0,4 1 0,2 0 40
A2 4,8 0 0,6 1 240
Iterasi pertama adalah optimum karena koefisien pada persamaan Z
semuanya positif, dengan x1 = 40, x2 = 240 dan z=240M+80.
9) Memaksimalkan : Z=8 x+6 y
Dengan pembatas 4 x+2 y ≤60
2 x+4 y ≤48
x1 , x2≥0
Selesaikan dengan metode simpleks.Jawab:
(1) Mengubah ke dalam berntuk persamaan linier.
4 x+2 y +s1=60
2 x+4 y +s2=48
(2) Nyatakan ke dalam bentuk matriks.
(4 2 1 02 4 0 1 )(
xys1
s2)=(60
48 )(3) Table simpleks.
I C j 8 6 0 0
C i x1 x2 s1 s2 b i Ri
0 s1 4 2 1 0 60 15
0 s2 2 4 0 1 48 24
Z j 0 0 0 0 Z=0
Z j−C j -8 -6 0 0
X j( j=1,2, . .. ) : macam variabel (x1 , x2 , s1 , s2 )
x1 , x2 : variabel keputusans1 , s2 : variabel basisC j
( j=1,2, . . .) : koefisien dari fungsi tujuan (8, 6, 0, 0) dari f =8 x1+6 x2+0 s1+0 s2
C i : koefisien variabel basis dalam fungsi tujuanC j
( j=1,2, . . .) : ∑ (Ci×aik )
Agar f maksimal maka Z j−C j harus non negatif.Melanjutkan ke tabel ke-2:
– Kolom Kunci (KK) = Z j−C j yang paling kecil
– Baris Kunci (BK) = Ri yang paling kecil di mana
Ri=b i
aik
– Nomor Kunci = pertemuan antara KK & BK
Pada tabel berikutnya, nomor kunci harus = 1 dan elemen lain yang satu kolom dengan nomor kunci harus = 0
Sehingga dari tabel I ke II:
B1×14 dan
B2−12
B1
I C j 8 6 0 0
C i x1 x2 s1 s2 b i Ri
8 x1 1 1/2 1/4 0 15 30
0 s2 0 3 -1/2 1 18 6
Z j 8 4 2 0 Z=120
Z j−C j 0 -2 2 0
Dari tabel II ke III:
B2×13 dan
B1−16
B2
III C j 8 6 0 0
C i x1 x2 s1 s2 b i Ri
8 x1 1 0 1/3 -1/6 12
6 x2 0 1 -1/6 1/3 6
Z j 8 6 5/3 2/3 Z=132
Z j−C j 0 0 5/3 2/3
Karena Z j−C j≥0
maka Zmaks=132
Untuk x1=12
; x2=6
; s1 , s2=0
10) Memaksimalkan : Z=40 x1+20 x2+60 x3
Dengan pembatas 2 x1+4 x2+10 x3≥24
5 x1+x2+5 x3 ≥48
x1 , x2 , x3≥0
Jawab:
(1) Mengubah ke dalam bentuk persamaan linier.
2 x1+4 x2+10 x3−t1+v1=24
5 x1+x2+5 x3−t1+v1 =8
(2) Nyatakan ke dalam bentuk matriks.
(2 4 10 −1 0 1 05 1 5 0 −1 0 1 )(
x1
x2
x3
t1
t2
v1
v2
)=(248 )
Untuk meminimumkan Z=40 x1+20 x2+60 x3+0 t1+0t2+Mv 1+Mv 2
dengan M adalah bilangan positif yang besar.
(3) Tabel Simpleks
– Simpleks minimum, optimal dapat dicapai jika ∀(Z j−C j )≤0
– Pilih KK dari Z j−C j
yang paling besar diantara harga
Z j−C j≥0
– Hitung Ri kemudian tentukan BK dari harga Ri yang paling kecil.
I C j 40 20 60 0 0 M M
C i x1 x2 x3 t1 t2 v1 v2 b i Ri
M v1 2 4 10 -1 0 1 0 24 24/10
M v2 5 1 5 0 -1 0 1 8 8/5
Z j 7M 6M 15M-M
-M
M M Z=32 M
Z j−C j7M-40
6M-20
15M-60
-M
-M
0 0
Dari tabel I ke II:
B2×15 dan B1−2B2
I C j 40 20 60 0 0 M M
C i x1 x2 x3 t1 t2 v1 v2 b i Ri
M v1 -8 2 0 -1 2 1 -2 8 4
60 x3 1 1/5 1 0 -1/5 0 1/5 8/5 8
Z j -8M+60 2M+12 60 -M 2M-12 M -2M+12 Z=8 M+96
Zj – Cj -8M-20 2M-8 0 -M -M 0 -3M+12
Dari tabel II ke III:
B1×12 dan
B2−12
B1
I C j 40 20 60 0 0 M M
C i x1 x2 x3 t1 t2 v1 v2 b i Ri
20 x2 -4 1/2 0 -1/2 1 1/2 -1 4
60 x3 9/5 0 1 1/10 -2/5 -1/10 2/5 4/5
Z j 28 20 60 -4 -4 4 4 Z=128
Zj – Cj -12 0 0 -4 -4 4-M 4-M
Jadi
Zmin=128 , untuk
x1=0
;
x2=4
;
x3=4
5
;
t1 , t2 , v1 , v2=0