BAHAN AJAR
PROGRAM LINIER
Bahan Ajar ini disusun dengan dana hibah dari dikti Untuk STKIP YPM Bangko
HAYATUL MUGHIROH,S.Pd.I NIDN. 1010108002
PROGRAM STUDI PENDIDIKAN MATEMATIKA JURUSAN PENDIDIKAN MIPA STKIP YPM BANGKO 2013
KATA PENGANTAR
Syukur
Alhamdulillah penulis ucapkan kepada Allah SWT, karena berkat
rahmat dan karunia-Nya jugalah penulis berhasil menyelesaikan bahan ajar ini. Penulisan bahan ajar ini bertujuan untuk membantu mahasiswa melengkapi bahan bacaan yang diperlukan dalam mengikuti perkuliahan
Program Linier (PL) yang
merupakan salah satu mata kuliah wajib diikuti pada Program Studi Pendidikan Matemtika STKIP YPM Bangko. Bahan ajar ini terdiri dari beberapa Bab sesuai standar kompetensi program linier yang mengacu dengan kebutuhan dan tuntunan kurikulum di STKIP YPM Bangko. Setelah mempelajari program linier, mahasiswa diharapkan mampu memahami : (1) Sistem persamaan linier (2) Persoalan Optimasi dalam PL dan menyelesaikan PL dengan metode grafik PL, (3) Metode Simpleks : pengantar metode simpleks, metode simpleks maksimasi dan minimasi, contoh – contoh persoalan PL maksimasi dan minimasi dan penyelesaiannya dengan dengan metode simpleks, (4) Persoalan Dualitas : kaidah – kaidah transformasi dual, teorema – teorema dual, dan pemecahan dual, serta mampu menerapkan konsep PL untuk memecahkan masalah dalam kehidupan sehari – hari. Penyusunan bahan ajar ini telah banyak dibantu oleh berbagai pihak, untuk itu pada kesempatan ini penyusun mengucapkan terima kasih yang setulus-tulusnya kepada: 1. Dra. Elfa Eriyani,M.Pd., selaku Ketua STKIP YPM Bangko. 2. Dr. Yusrizal,M.Pd., selaku Pembantu Ketua I STKIP YPM Bangko. 3. Dra. Fatimah AS,M.Pd, selaku pembimbing penyusunan bahan ajar. 4. Ahde Fitri,S.Pd.,M.Pd., selaku Ketua Jurusan Pendidikan MIPA STKIP YPM Bangko. 5. Semua dosen di lingkungan Program Studi Pendidikan Matematika. Penyusunan bahan ajar ini masih jauh dari sempurna. Saran dan kritik yang konstruktif akan sangat membantu dalam menyempurnakan bahan ajar ini di masa yang akan datang. Semoga bahan ajar ini akan membantu kelancaran perkuliahan dan bermanfaat bagi para pembaca.
Penyusun ii
DAFTAR ISI
KATA PENGANTAR .................................................................................... DAFTAR ISI .................................................................................................. BAB I
BAB II
BAB III
i ii
SISTEM PERSAMAAN LINIER A. Pendahuluan ................................................................................
1
B. Sistem Persamaan .......................................................................
1
C. Sistem Pertidaksamaan Linier ....................................................
13
D. Rangkuman .................................................................................
17
E. Uji Kompetensi ...........................................................................
17
PERSOALAN OPTIMASI A. Pendahuluan ................................................................................
20
B. Permasalahan Optimasi...............................................................
21
C. Model Matematika Masalah Program Linier ..............................
24
D. Rangkuman .................................................................................
27
E. Uji Kompetensi ...........................................................................
27
METODE SIMPLEKS A. Pendahuluan ................................................................................
29
B. Masalah Dua Variabel......................................................... .......
31
C. Masalah Tiga Variabel..................................................... ...........
38
D. Rangkuman .................................................................................
43
E. Uji Kompetensi ...........................................................................
44
BAB IV METODE SIMPLEX SEBAGAI PROSEDUR PERHITUNGAN DAN PERMASALAHAN DUAL A. Pendahuluan...................................................................... .......
47
B. Metode Simpleks sebagai Prosedur Perhitungan .....................
48
C. Rumus Transformasi ... ..........................................................
55
D. Analisis Primal Dual.................................................................
66
E. Uji Kompetensi .........................................................................
75
DAFTAR PUSTAKA.......................................................................................
iii
79
BAB I SISTEM PERSAMAAN LINIER
Kompetensi Dasar 1. Menyelesaikan persoalan sistem persamaan linier 1, 2 dan 3 variabel 2. Merubah persamaan linier ke dalam bentuk matriks
Indikator Mahasiswa diharapkan mampu: 1.1. 1.2. 1.3. 2.1. 2.2. 2.3.
menyelesaikan permasalahan sistem persamaan linier menganalisis sistem persamaan linier dalam soal cerita menciptakan masalah persamaam linier dari kehidupan sehari hari mengidentifikasi permasalahan sistem persamaan linir merubah sistem persamaan linier ke dalam bentuk mat memberikan contoh persamaan linier yang dapat diubah dalam bentuk matrik
A. Pendahuluan Hans Frederich Blichfieldt lahir di kota Illear, Denmark pada tanggal 9 Januari 1873. Sejak kecil dia sudah menunjukkan kemampuannya dalam matematika. Ia mendapat gelar sarjana dalam bidang matematika. Beberapa topik yang ditemukannya antara lain penyelesaian persamaan linier. Frederich meninggal di Paloseto, Calivornia tanggal 16 November 1945. Penyelesaian persamaan linier ini akan bermanfaat dalam kehidupan sehari-hari, karena masalah-masalah yang disajikan dalam persamaan linier berawal dari aktivitas nyata yang ditemukan di sekitar kita. Penyelesaian ini akan lebih banyak digunakan oleh pedangang, pengusaha atau pembeli dalam hal berbisnis
B. Sistem Persamaan Sebuah garis dalam bidang xy merupakan himpunan pasangan berurutan (x,y), secara aljabar dapat dinyatakan dengan persamaan yang berbentuk: a11 x + a12y = b1 ................1) disebut persamaan linier, sebab pangkat dari variabel (peubah) x dan y adalah satu.
Program Linier
4
Secara lebih umum, sebuah persamaan linier dalam n variaberl x1,x2,. . . xn dapat dinyatakan dalam bentuk : a11 x
1
+ a12x2 + ... + a1nx
n
=b1 ................2) dimana a11, a12, ... ain, dan b1
adalah konstanta linier. Sebuah pemecahan (penyelesaian/solusi) dari persamaan ................2) mengandung pengertian terdapat sebuah urutan dari n bilangan s1, x2, . . . . , sn yang apabila disubtitusikan secara berurutan menggantikan x 1, x2 , . . . , xn akan memenuhi persamaan itu (persamaan menjadi kesamaan yang benar). Himpunan semua persamaan seperti itu disebut himpunan pemecahan (bilangan penyelesaian). Sebuah sistem persamaan linier adalah kumpulan (himpunan terhingga) persamaan linier ini di dalam variabel x1, x2, . . . , xn. Dalam bentuk umum, sebuah sistem persamaan dapat dirumuskan sebagai berikut : a11x1 + a12x2 + . . . + a1nxn = b1 a21x1 + a22x2 + . . . + a2nxn = b2 . .................... 3) . . am1x1 + am2x2 + . . . + amnxn = bm Sama halnya dengan sebuah persamaan, himpunan pemecahan sebuah sistem persamaan linier adalah sebuah urutan dari bilangan-bilangan s1, x2, . . . . , sn yang bila dipakai untuk menggantikan x1, x2 , . . . , xn memenuhi sistem persamaan itu. Pada sistem persamaan linier akan ada 3 kemungkinan yaitu : . 1. Pemecahan dengan menggunakan aturan Cramer Perhatikan : a11x1 + a12x2 = b1 a21x1 + a22x2 = b2
Program Linier
5
Dengan bantuan pengertian matrik sistem linier diatas dapat dinyatakan sebagai sebuah persamaan matriks. [
][ ]
dengan
[ ]
[
]
[ ]
[ ]
terdapat dua kemungkinan : 1. Bila determinan (A) = 0, maka tidak terdapat A-1 2. Bila determinan (A) ≠ 0, maka terdapat A-1 Ingat, determinan (A) atau det (A) = a11a22 - a12x21 . Selanjutnya, untuk memperoleh pasangan (x1 memperoleh
pemecahan
sistem
persamaan
,
diatas
x2) yang Cramer
mengembangkan aturan sebagai berikut :
Dimana :
Dengan demikian terdapat kemungkinan : 1. memeperlihatkan sistem persamaan tidak mempunyai pemecahan. Secara geometris kedua garis lurus itu sejajar.
tidak ada pemecahan
Contoh : sistem persamaan yang tidak mempunyai penyelesaian
Program Linier
6
tidak (konsisten)
2.
memperlihatkan sistem persamaan mempunyai
banyak pemecahan. Secara
geometris kedua garis lurus itu berimpit.
tak terhing ga pemeca han
Contoh : sistem persamaan yang mempunyai tak terhingga banyaknya penyelesaian (konsisten) 3.
memperlihatkan sistem persamaan mempunyai satu pemecahan. Secara geometris, kedua garis berpotongan
satu pemecahan
Contoh : sistem persamaan yang mempunyai satu penyelesaian (konsisten) Penyelesaian :
Program Linier
7
Maka ;
dan
Aturan Cramer dapat juga digunakan untuk mencari penyelesaian sistem persamaan untuk a11x1 + a12x2 + a13x3 = b1 a21x1 + a22x2 + a23x3 = b2 a31x1 + a32x2 + a33x3 = b3 [
[
]
[
]
]
[
]
Syarat untuk mempunyai penyelesaian tunggal, tidak ada penyelesaian dan mempunyai tak terhingga banyaknya penyelesaian ditentukan dengan nilai det (A) seperti pada sistem persamaan dengan dua varabel. :
,
, dan
Contoh : Carilah penyelesaian sistem persamaan:
[
Program Linier
]
[
]
8
[
]
[
]
Dengan demikian Catatan : Menurut Howard Anton (dalam Pantur Silaban, 1985), apabila kita bermaksud mencari penyelesaian sistem persamaan, disini
atau lebih dengan aturan Cramer maka terlebih
dahulu perhatikan teorema berikut : 1.
Jika
A
adalah
sebarang
matriks
bujursangkar
yang
mengandung paling sedikit satu baris bilangan nol, maka . 2.
Jika A adalah sebuah matriks segitiga yang berukuran maka
adalah hasil perkalian semua unsur pada kolom
utama 3.
Jika sebuah matriks bujursangkar mempunynyai dua baris yang sebanding mala nilai determinan matriks tersebut sama degnan nol.
2. Penyelesaian sistem persamaan dengan Eliminasi Gauss Prosedur penyelesaian sistem persamaan dengan menggunakan Eliminasi Gauss didasarkan pada upaya mereduksi matriks yang diperbesar menjadi bentuk eselon baris yang direduksi. Dari sistem persamaan : a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 . . .
an1x1 + an2x2 + annxn = bn
Program Linier
9
Matriks yang diperbesar (matriks lengkap) dari sistem persamaan di atas adalah sebagai berikut : a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 . . .
an1x1 + an2x2 + annxn = bn Proses mereduksi baris didalam matriks yang diperbesar yang bersesuaian dengan pengerjaan pada sistem persamaan disebut operasi baris elementer, yaitu : 1) Kalikan sebuah baris dengan konstanta tertentu yang tidak sama denga nol 2) Pertukaran dua baris 3) Tambahkan kelipatan suatu baris kepada baris yang lain Contoh :
matriks lengkapnya adalah :
[
]
Kalikan
baris
satu
denga
(-3)
kamudian
tambahkan ke baris 2, kalikan 1 degnan (-2) kemudian tambahkan kebaris 3. [
] Kalikan baris ke 3 dengan (-1) kemudian pertukarkan dengan baris 2
[
] Kalikan baris 2 dengan (-2) kamudian tambahkan ke baris 1, kalikan baris 2
Program Linier
10
degnan 5 sesudah itu tambahkan kebaris 3. [
] Kalikan baris 3 dengan 1/22
[
] Kalikan baris 3 dengan 10 kemudian tambahkan ke baris 1; kalikan baris 3 dengan (-7) kemudian tambahkan ke baris 2.
[
] Jadi diperoleh nila
3. Penyelesaian dengan penerapan invers matriks Dari sistem persamaan: a11x1 + a12x2 = b1 a21x1 + a22x2 = b2 Maka,
; dimana :
[
]
Apabila
[ ]
[ ]
maka invers A ada
Misal, invers A adalah A-1 maka : A x A-1 = 1, sehingga dikalikan dengan A-1 diperoleh : ; identitas
Contoh 1 : Carilah penyelesaian dari sistem persamaan berikut :
Jawab : [
Program Linier
]
[ ]
[ ]
11
Untuk mendapat
(invers A) dapat dilakukan dengan 2 cara :
1. Dengan Rumus
Jadi
[
]
[
] [
[
Sehingga
]
][ ]
[
]
[ ]
Jadi : nila
2. Dengan
Menggunakan
Matriks
Elemter
Dan
Operasi
Elementer [ ⟨
] maka : |
⟩ baris 1 dikurang denga baris 2 ; baris 2 dikalikan
denga 1/3. ⟨
|
⟩ baris 1 dikalikan dengan (-1) ; baris 2 dijumlahkan dengan baris 1
⟨ ⟨
|
⟩ kalikan baris 2 dengan (-1/3)
|
⟩ kalikan baris 2 dengan (-5) kemudian tambahkan ke baris 1
⟨
|
Jadi,
Sehingga :
Program Linier
⟩ [
]
[
][ ]
[
]
[ ]
12
Jadi : nila
Contoh 2: Tentukan penyelesaian dari sistem persamaan berikut
Jawab : [
]
[ ]
[
]
Sama halnya denga contoh 1 diatas dimana dalam menentukan invers matriks A dapat dilaukan dengan 2 cara yaitu : 1. Dengan rumus karena
Untuk mendapatkan Adj (A) terlebih dahulu tentukan matriks kofaktor dari A. Setelah dapat kofaktor dari matriks A, maka transposisi matriks kofaktor dari A dinamakan adjoint matriks A dan dinyatakan adj (A). [
Kofaktor A adalah : [
] maka transposisi dari matriks
]
Nilai k11= (-1)i+j Mij ; Mij adalah minor dari aij Dari matriks A diatas maka Minor Elemen (entri) adalah :
Program Linier
[
]
[
]
13
[
]
[
]
[
]
[
]
[
]
[
]
[
]
Maka : ;
;
;
;
;
;
Sehingga , [
]
[
]
Jadi : [
]
[
]
Dengan demikan, Program Linier
14
[
[
][
]
[
]
] Jadi : nila
2. Dengan menggunakan matriks elementer dan operasi baris elementer [
]
⟨
|
⟨
|
⟩ kalikan baris 1 dengan ½
⟩ kalikan baris 1 dengan (-2) kemudian tambahkan ke baris 2 dan baris 3
⟨
|
⟩ kalikan baris 2 dengan (-3) kemudian tambahkan kebaris 1 baris ke 3 dengan baris 2.
⟨
|
⟨
|
Jadi :
⟩ baris 1 kurangi 3 kali baris 3
⟩
[
]
Sehingga, [
Program Linier
][
]
15
[
]
[
]
Jadi nilai :
C. Sistem Pertidaksamaan Linier Perhatikah contoh di bawah ini : 1) Pengusaha membel ingin memproduksi almari kualitas tinggi dan almari kualitas sedang dari kayu jati dan kayu ramin yang tersedia dalam jumlah tertentu. Tiap unit kayu jati maupun kayu ramin digunakan secara menyebar dalam proposisi tertentu untuk menghasilkan dua macam almari. 2) Menurut dokter, Amin dan Ani (suami istri) perlu mengatur menu makanan dengan baik. Untuk itu mereka membutuhkan daging miskin lemak dan daging berlemak dalam jumlah/porsi tertentu. Kebutuhan Amin dan Ani sedikitnya
sejumlah daging miskin lemak dalam seminggu.
Kedua kriteria daging dapat dipenuhi oleh daging sapi dan ayam salah satu.
Hal pokok yang tersirat dalam contoh 1) adalah : (a) variabel aktivitas ada 2 dan (b) terdapat dua masukan yang ternyata terbatas yaitu paling banyak kayu yang tersedia itu habis terpakai. Bentuk pertidaksamaannya adalah : a11x1 + a12x2 ≥b1 → untuk kayu jati a21x1 + a22x2 ≥b2 → untuk kayu ramin Hal pokok yang tersurat dalam contoh 2) adalah (a) variabel bebas daging sapi dan ayam, (b) jumlah lemak menurut kriteria kebutuhan Amin dan Ani yang terdapat dalam daging sapi dan ayam dalam batasan paling sedikit dan dibutuhkan (non negatif). Bentuk pertidaksamaannya adalah : a11x1 + a12x2 ≥ b1 a21x1 + a22x2 ≥ b2
Program Linier
16
Karena terdapat dua pertidaksamaan linier yang terjalin dalam sautu kesatuan (keterkaitan), maka gabungan dua pertidaksamaan itu dimaksudkan di sini sebagai suatu sistem pertidaksamaan. Kombinasi lain yang dapat ditampilkan sebagai pembatas suatu program linier seperti berikut : a11x1 + a12x2 + a21x1 + a22x2 + a31x1 + a32x2 + dan lainnya pada rumusan
a13x3 ≤, = ≥ b1 a23x3 ≥,≥,≤ b2 a33x3 ≥,≤,≤ b3 pembatas (kendala) yang ada dalam suatu
masalah pemograman linier. 1. Sistem Petidaksamaan Linier Dua Variabel Perhatikan persamaan : a11x + a12y = b1 pemecahan himpunan pasangan (x,y) secara geometris dinyatakan dengan garis lurus. Bagaimana dengan pertidaksamaan linier ax + by ≤ c dan ax + by ≥ c dimana a, b, dan c adalah konstanta, untuk itu , (1) Buat garis ax + by = c (2) Dengan memperhatikan nilai konstanta kita peroleh bidang datar (dengan garis ax +by = c sebagai pembatas ) sebagai himpunan (xy) yang merupakan pemecahan pertidaksamaan. (3) Kalau a, b, c adalah konstanta real positif i.
Bidang datar sebelah kiri ax + by = c (termasuk garis itu) segai daerah pemecahan ax + by ≤ c
ii.
Bidang datar sebelah kanan ax + by = c (termasuk ax + by = c) sebagai daerah pemecahan ax by ≥ c
Contoh 1: Perhatikan :
Program Linier
17
Tunjukan pemecahan dari ketiga bentuk diatas : y
y
→
2
2
→
0
3
2
→ x+
0
3
3
x+
Gambar i)
x+
Gambar ii)
0
Gambar iii)
Garis yang ditunjukan gambar i) menunjukan daerah penyelesaian i), daerah arsiran yang ditunjukkan gambar ii) memperlihatkan daerah hasil pertidaksamaan yang layak ii), dan daerah
arsiran
gambar
iii)
memperlihatkan
daerah
hasil
pertidaksamaan yang layak iii). Kalau x dan y non negatif maka : 1) Daerah hasil persamaan i) ialah sepanjang garis termasuk titik potong sb.x dan sb.y 2) Daerah hasil/penyelesaian pertidaksamaan ii) adalah daerah bidang segitiga OAB 3) Daerah penyelesaian pertidaksamaan iii) ialah bagian kuadran I (x+, y+) diluar segitiga OAB dengan segmen AB sebagai pembatas.
2. Sistem Petridaksamaan Linier Tiga Variabel Perhatikan : a11x1 + a12x2 + a13x3 = b ..............i) a11x1 + a12x2 + a13x3 ≤ b ..............ii) a11x1 + a12x2 + a13x3 ≥ b ..............iii) Pertama-tama mengambil a11, a12, a13 dan b konstanta positif atau secara geometris akan kita bahas daerah dalam ruang yang dibatasi oleh bidang X1+ OX2+, X1+ OX3+, dan X2+ OX3+, ; x1, x2, dan x3 ≥ 0
Program Linier
18
1) Daerah pemecahan a11x1 + a12x2 + a13x3 = b terdapat pada bidang melaui (b/a11,0,0) ; B (0, b/a12,0) ; C(0, 0, b/a13,). 2) Daerah pemecahan a11x1 + a12x2 + a13x3 ≤ b ; x1, x2, x3 ≤ 0 adalah bangun ruang yang dibatasi oleh bidang X1 OX2, X1 OX3, dan X2 OX3, dan a11x1 + a12x2 + a13x3 = b 3) Daerah pemecahan a11x1 + a12x2 + a13x3 ≥ b ; x11, x12, x13 ≥ b adalah bangun ruang pada permukaan bidang a11x1 + a12x2 + a13x3 ≥ b adalah bangun ruang dalam permukaan bidang a11x1 + a12x2 + a13x3 = b Contoh : 4x1 + 3x2 + 2x3 = 12 4x1 + 3x2 + 2x3 ≤12 4x1 + 3x2 + 2x3 ≥12 Tunjukan dengan gambar daerah pemecahan ke tiga bentuk di atas ! i)
A (3,0,0)
x3 → 4x1 + 3x2 + 2x3 = 12
B (0,4,0) C (0,0,6)
A
0
B
x2
x3
ii)
x3
A 0
B
x2
x1 4x1 + 3x2 + 2x3 ≤12
Program Linier
19
iii)
x3 4x1 + 3x2 + 2x3 ≥12
A
0
B
x2
x1
D. Rangkuman 1. Hans Frederich Blichfieldt adalah matematikawan yang lahir di Denmark, 9 Januari 1873 yang menemukan topik penyelesaian persamman linier 2. Penyelesaian persamaan linier ini akan bermanfaat bagi pedagang, pengusaha, atau pembeli dalam hal berbisnis. 3. Penyelesaian persamaan linier dapat dilakukan dengan menggunkan aturan Cramer, Eliminasi Gauss, dan penerapan invers matriks. 4. Persamaan linier dicirikan dengan tanda sama dengan (=) sedangkan pertidaksamaan ditandai dengan <, >, ≤ , dan ≥ .
Uji Kompetensi 1. Carilah penyelesaian sistem persamaan berikut : 5x1 – 2x2 = 19 7x1 – 3x2 = 15 Dengan : a) aturan Cramer b) eliminasi Gauss c) invers matriks i. denga rumus ii. dengan operasi baris elenter.
Program Linier
20
2. Diketahui : 2x1 + x2 + x3 = 7 3x1 + 2x2 + x3 = -7 x2 + x3 = 5 carilah penyelesaianya dari sistem persamaan ini dengan : a) Menggunakan aturan cramer b) Menggunakan eliminasi Gauss/obe kofaktor 3. Diketahui sistem persamaan sebagai berikut x1 + x2 + 2x3 = 8 -x1 - 2x2 + 3x3 = 1 3x1 - 7x2 + 4x3 = 10 Pertanyaan sama dengan pertanyaan soal 1. 4. Perhatikan sistem persamaan x1 + 2x2 + 2x3 = p x1 - 3x2 + x3 = q x1 - 3x2 + 3x3 = r
; p, q, dan r adalah konstanta
a) Carilah hubungan antara p,q,dan r supaya sistem persamaan itu konstanta b) Apabila x1 = 7, x2 = 4, x3 = -1 maka tentukan p,q, dan r. 5. Diketahui sistem persamaan : 3x1 + 2x2 – 4x3 = 10 x1 + x2 + 2x3 = 3 2x1 - x2 - 3x3 = 7 a) Nyatakan dalam bentuk A x X = N b) Tunjukan minor a22 matriks A c) Nilai kofaktor K31 positif atau negatif ? beri alasan d) Carilah det (A) = a31k31 + a32k32 + a33k33 e) Tentukan matriks kofaktor A f) Carilah penyelesaian dari A x X = B dengan A-1 dan det (A)
Program Linier
21
6. Diketahui sistem persamaan A x X = B dengan persamaan pembentuknya x1 + x2 + x3
=3
3x1 + x2 + 2x3 = 4 x1 - x2 - x3 = 1 a) Carilah A-1 dengan bantuan operasi baris elementer b) Carilah A-1 dengan mencari dulu matriks kofaktor dari matriks A ! c) Carilah A-1 manakah menurut anda lebih efisien ? 7. Gambarkanlah daerah pemecahan pertidaksamaan berikut : a) 2x – y < 6 b) 2x -5y > 10 c) x + 2y ≤ 4 d) 5x + 7y ≥ 35 8. Gambarkanlah daerah yang memenuhi sistem pertidaksamaan dan kordinat titik sudut yang terbentuk a. x + y ≤ 1 x-y≤1 b. 2y - x ≤ 2 y – 3x ≤ -1
c. x + 2y ≤ 1 2x + y ≤ 12 x ≤ 0, y ≤ 0 d. 3x1 + 4x2 ≤ 12 5x1 + 6x2 ≤ 30 1 ≤ x1 ≤ 3
Program Linier
22
9. Gambarkanlah daerah yang memenuhi sistem pertidaksamaan berikut : a. 2x + 5y + 4z ≤ 40 5x + 4y + 2z ≤ 40 x ≥ 0, y ≥ 0, z ≥ 0 b. 2x1 + 4x2 + 5x3 ≤ 60 4x1 + 5x2 + 2x3 ≤ 60 5x1 + 2x2 + 4x3 ≤ 60 x1 ≤ 0, x2 ≤ 0, x3 ≤ 0
BAB II PERSOALAN OPTIMASI
Kompetensi Dasar 3. Menentukan suatu persoalan apakah termasuk persoalan optimasi dalam Program Linier 4. Memberikan contoh – contoh persoalan optimasi Program Linier 5. Menentukan suatu persoalan apakah termasuk persoalan optimasi dalam Program Linier
Indikator: Mahasiswa diharapkan mampu: 3.1 Menentukan suatu persoalan Pl maksimum atau persoalan Pl minimum 4.2. Memberikan contoh – contoh persolan PL maksimum 4.3. Memberikan contoh – contoh persoalan PL minimum. 5.1. Menuliskan model Matematika dari suatu persoalan PL maksimum dan minimum. 5.2. Menggambarkan himpunan penyelesaiannya dari suatu system pertidaksaam linier sebagai daerah penyelesaian. 5.3. Menentukan titik ekstrim dari batas – batasnya. 5.4. Mencari nilai optimum ( maksimum atau minimum ) dari suatu tujuan.
A. Pendahuluan Seorang matematikawan Rusia L.V. Kantorovich pada 1939 berhasil menemukan pemecahan masalah yang berkaitan dengan program linier. Pada waktu itu Kantorovich bekerja untuk Kantor Pemerintah Uni Soviet. Ia diberi tugas untuk mengoptimalkan produksi pada industri Plywood. Ia kemudian muncul dengan teknik matematis yang dikenal dengan pemrograman linier. Matematikawan Amerika, George B. Dantzig secara independen juga Program Linier
Page 66
mengembangkan pemecahan masalah tersebut, dimana hasil karyanya pada masalah tersebut pertema kali dipublikasikan pada tahun 1947. Selanjutnya, sebuah teknik yang lebih cepat, tetpai lebih rumit, yang cocok untuk memecahkan masalah program linier dengan ratusan atau bahkan ribuan variabel, dikembangkan oleh matematikawan Bell laboratories, Naranda karmarkar pada tahun 1983. Program linier sangat penting khususnya dalam perencanaan militer dan industri. Salah satu cabang matematika yang saat ini banyak digunakan adalah masalahmasalah yang bersifat pengoptimasian, dan salah satu diantaranya adalah masalh program linier. Program linier kata benda dari pemograman linier (linier programing). Jadi program linier berasal dari kata programing dan linier. Programing adalah : alokasi sumber-sumber yang terbatas untuk memenuhi tujuan tertentu. Dan linier menunjukan pengertian bahwa variabel-varibel yang bekerja pada masalah tersebut berpangkat (berderajat) satu. Jadi Program Linier adalah : programing yang menyangkut masalah-masalah dimana hubungan antara variabel-variabelnya semua linier. Secara matematis pengertian program linier merupakan bagian matematika terapan, dengan model matematika yang terdiri atas persamaan atau pertidaksamaa-pertidaksamaan linier, yang memuat pembuatan program untuk memecahkan berbagai persoalan. Persoalan program linier dapat terjadi dikalangan pemerintahan, perusahaan,militer dan sebagainya. Suatu keputusan adalah suatu pemulihan terhadap alternatif-alternatif. Program linier membantu pembuat keputusan (decision maker) untuk memilih suatu alternatif yang paling tepat yang merupakan pemecahan paling baik (the best solution). Selain untuk memecahkan persoalan transportasi, program linier juga berguna untuk memecahkan persoalan : persoalan assigment, optimum crop rotation plan, alloccating manufactured product, optimal bombing patterns, design of weapons system, optimal purchasing policy.
B. Permasalahan Optimasi Persoalan pemograman linier adalah : suatu persoalan untuk menentukan besarnya masing-masing nilai variabel yang mengoptimasikan (maksimum atau minimum) nilai objek, dengan memperhatikan pembatasan-pembatasan yang ada yaitu yang dinyatakan dalam bentuk persamaan-persamaan atau pertidaksamaan-pertidaksamaan linier.
Program Linier
Page 67
Suatu persoalan dikatakan persoalan program linier, bila memenuhi ketentuanketentuan sebagai berikut : 1. Tujuan (objektif) persoalan yang akan dicapai harus dapat dinyatakan dalam bentuk fungsi linier. Fungsi ini disebut fungsi tujuan (objective function). 2. Harus ada alternatif pemecahan. Pemecahan yang membuat nilai fungsi tujuan optimum (keuntungan yang maksimum, biaya yang minimum dan sebagainya) yang harus dipilih. 3. Sumber-sumber yang tersedia dalam jumlah yang terbatas (bahan mentah terbatas, modal terbatas, ruang untuk menyimpan barang terbatas dan sebagainya). Pembatasanpembatasan dari sumber yang tersedia harus dinyatakan dalam bentuk pertidaksamaan linier (linier inequality). Secara umum, persoalan program linier dapat disumuskan sebagai berikut: Cari x1, x2, . . ., xn Sedemikian rupaa (s.r.s) : Z = c11x1 + c12x2 + . . . + c1n + xn → optimum (maksimum atau minimum) Dengan persyaratan : a11x1 + a12x2 + . . . a1nxn ≤ = ≥ h1 a21x1 + a22x2 +
. . . .
a2nxn ≤ = ≥ h2
. . . a31x1 + a32x2 +
. . . .
a3nxn ≤ = ≥ hn
Pada dasarnya persoalan program linier ini dapat dibagi menjadi dua persoalan yaitu : 1) Persoalan program linier maksimasi Maksimiasi adalah suatu proses memaksimumkan fungsi objektif
z = c1x1 + c2x2 + . . . cnxn ; fungsi objektif maksimum (fungsi keuntungan) dimana xj ( j = 1, 2, . . . n ) menunjukan banyaknya barang yang dihasilkan. Disini kita memisalkan, bahwa perusahaan yang bersangkutan mempunyai n buah aktivasi, yaitu menghasilkan satu barang ke-j atau keuntungan yang diperoleh jika tingkat aktivasi ke-j sama dengan satu satuan. Disini selalu
Program Linier
Page 68
dianggap bahwa setiap tambahan satu dari setiap aktivasi menghasilkan keuntungan (atau tambahan keuntungan) yang sama.
Persyaratan :
a11x1 + a12x2 + . . . a1nxn ≤ h1 a21x1 + a22x2 +
a2nxn ≤ h2
. . . .
. . . Am1x1 + am2x2 +
. . . .
amnxn ≤ hm, dimana x1, x2, . . . xn ≥ 0
oleh karena x1, x2, . . . xn telah menunjukan output yang dihasilkan, maka interpretasi yang dapat diberikan kepada aij tidak boleh sembarang lagi. Salah satu interpretasi yang mungkin diberikan pada aij ialah banyaknya input ke-1 yang diperlukan untuk menghasilkan satu satuan barang ke-j. Jadi ini berarti bahwa h1 adalah banyakanya input ke-i yang tersedia. Batasan diatas dapatlah diartikan sebagai batasan input yang tersedia bagi perusahaan itu. Dengan demikian jelaslah bahwa jika input ke-i yang tersedia hanya sebanya hi saja, maka pemakaian input itu tidak boleh melebihi hi. Dari kedua tafsiran diatas ini, kita telah memisalkan bahwa suatu preusahaan menghasilkan atau memperdagangkan n macam barang. Untuk menghasilkan atau memperdagangkan barang-barang tersebut, perusahaan itu memakai m macam input, yang masing-masing dengan jumlah terbatas. Jadi kedua persoalan itu adalah mencari nilai-nilai x (tingkat-tingkat aktivasi) yang mana harus diambil untuk memaksimumkan keuntungan atau penerimaan.
2) Persoalan program linier minimisasi Minimisasi adalah suatu proses meminimkan fungsi objektif.
z = c1x1 + c2x2 + . . . + cnxn ; funsi objektif minimum
Persyaratan : a11x1 + a12x2 + . . . + a1nxn ≥ h1 a21x1 + a22x2 +
Program Linier
. . . .
+ a2nxn ≥ h2 Page 69
. . . Am1x1 + am2x2 +
. . . .
+ amnxn ≥ hm ; dimana x1, x2, . . . xn ≥ 0
Yang ditentukan adalah nilai x1, x2
Kedua persoalan program linier diatas (maksimasi dan minimasi) sering disebut Model Matematika. Model matematika adalah suatu hasil interpretasi manusia dalam menerjemahkan atau merumuskan persoalan sehari-hari kebentuk matematika, hingga persoalan itu dapat diselesaiakan secara matematis.
C. Model Matematika Masalah Program Linier Untuk melihat bagaimana suatu masalah diterjemahkan kedalam model matematika sehingga dapat dianalisis dengan lebih seksama. Tentu saja upaya menerjemahkan masalah ke dalam model matematika tidak terlepas dari hakikat dari program linier sebagai suatu teknik perencanaan yang bersifat analisis memakai model matematika. Untuk itu, dapat kita lihat contoh yang dikemukakan oleh Brian D. Bunday sebagai berikut : Sebuah Firma memproduksi sendiri rak buku dalam dua model, yaitu model A dan B. Produksi rak buku dibatasi oleh persediaan material (papan kualitas tinggi) dan waktu yang terbatas mesin pemroses. Tiap unit A memerlukan 3m3 papan dan tiap unit B memerlukan 4m3 papan. Firma memeproleh 1.700m2 papan tiap minggu dari pemasok sendiri. Tiap unit A membutuhkan 12 menit dari mesin pemroses dan tiap unit B membutuhkan 30 menit. Setiap minggu memungkinkan total waktu mesin 160 jam. Jika keuntungan (profit) tiap unit A sebersar $2 dan tiap unit B sebesar $4, berapa banyak unit dari tiap model akan perusahaan rencanakan untuk produksi tiap minggu. Rumusam masalah yang ditampilkan oleh Brian telah memenuhi syarat: 1) Terdapat tujuan yang dicapai yaitu mencapai keuntungan melalui produksi rak buku jenis A dan B dimana tiap jenis produksi itu telah direncanakan mempunyai harga (nilai, konstanta, parameter) tertentu. Program Linier
Page 70
Apabila jenis rak buku A dan B disebut x1 dan x2 dengan harga tiap jenis / unit c1 dan c2 maka fungsi objektif (tujuan) tersebut ialah : Z = c1x1 + c2x2 ; maksimum X1 dan x2 adalah keluaran (output) perusahaan dan di sebut variabel aktivitas. Fungsi tujuan diatas berbentuk fungsi linier, karena tersirat perbandingan (proposional) jika terjadi pertambahan pada tiap unit keluaran akan terjadi perubahan menyebar dalam proporsi (rasio) yang sama c1 terhadap tiap x1 dan c2 terhadap x2 atau dalam rumusan yang lebih umum Z = cjxj ; j = 1, 2, . . . , n Jadi aspek penting dalam masalah program linier jika fungsi tujuan berbentuk fungsi linier, ada asumsi linieritas dan proposionalitas. 2) Terdapat sumber daya atau masukan (input) yang berada dalam keadaan terbatas dalam hal ini, Firma mempunnyai persediaan melalui pemasok sendiri yaitu tiap minggu 1700m2 ; dan waktu kerja mesin pemroses yang terbatas yaitu tiap minggu 160 jam.
: untuk tiap x1 unit A diperlukan 3x1 m2
Papan
x2 unit B diperlukan 4x2 m2
Jam mesin
: untuk tiap x1 unit A diperlukan 0,2x1 jam x2 unit B diperlukan 0,5x2 jam
Masukan (persediaan) yang terbatas itu proporsional dan ada keterkaitan dengan keluaran (variabel aktivasi) sehingga dapat dirumuskan dalam hubungan yang linier yaitu pertidaksamaan linier. Papan
: 3x1 + 4x2 ≤ 1700
Jam mesin
: 0,2x1 + 0,5x2 ≤ 160
Pembatas (kendala) tersebut harus memenuhi syarat yang terkait dengan keluaran (output) yaitu non negatif, x1 ≥ 0 ; x1 ≥ 0 Rumusan masalah yang direncanakan oleh firma tersebut dan disajikan dalam bentuk rumusan kuantitatif menjadi model matematika program linier adalah : Fungsi
Z = 2x1 + 4x2 ; maksimum
Pembatas (kendala
3x1 + 4x2 ≤ 1700 2x1 + 5x2 ≤ 160
Syarat keterkaitan keluaran x1 ≥ 0 ; x2 ≥ 0 Program Linier
Page 71
Catatan : 1.
Keluaran non negatif berarti paling sedikit tidak memproduksi, yaitu : x1 = 0 atau x2 = 0
2.
Tanda pertidaksamaan kurang dari/lebih kecil dari mengandung makna paling banyak papan yang tersedia 1700m2 habis terpakai dan jam kerja mesin tidak boleh lebih dari 160 jam/minggu.
3.
Masukan (input) positif berarti papan dan mesin yang akan dipakai untuk memproses tersedia. Rumusan masalah yang dihadapi Firma tersebut dan diklasifikasikan
sebagai suatu program linier, selain aspek linierisasi dan proposionalitas, terdapat pengertian mendasar yaitu : 1.
Kriteria optimal fungsi tujuan ditentukan oleh jumlah sesuai dengan harga masing-masing variabel (aditivitas)
2.
Nilai variabel pengambilan keputusan dapat merupakan bilangan bulat atau kalau diperlukan dapat saja sebagai pecahan (divisibilitas)
3.
Semua konstanta atau parameter (nilai ci pada fungsi tujuan, b3 sebagai sumber dana atau masukan yang tersebar menjadi a1 secara proposional menunjang variabel aktivitas) tetap atau ditentukan secara pasti.
D. Rangkuman 1. Pemecahan masalah pertama kali dikembangkan oleh matematikawan Rusia, L.V Kantorovich pada tahun 1939. 2. Cabang matematika yang saat ini banyak digunakan adalah masalah pengoptimasian. 3. Suatu persoalan dikatakan persoalan program linier bila dapat dinyatakan dalam bentuk fungsi tujuan (objective function), memiliki alternatif pemecahan, dan sumber yang tersedia dalam jumlah terbatas. 4. Persoalan program linier dibagi menjadi persoalan maksimasi dan minimasi. 5. Rumusan masalah yang dikalasifikasikan program linier adalah aspek linierisasi, proposionalitas, addivitas, divisibilitas dan parameternya tetap (ditentukan secara pasti).
Program Linier
Page 72
Uji Kompetensi 1. Perusahaan aneka mendapat jatah merakit sepeda dan sepeda motor. Karena jumlah pekerja terbatas, perusahaan hanya dapat merakit sepeda 120 unit tiap bulan dan sepeda motor paling sedikit 10 unit dan paling banyak 60 unit. Pendapatan dari tiap unit sepeda sebesar Rp. 40.000,00 dan tiap unit sepeda motor Rp. 268.000,00. Berapa pendapatan maksimum tiap bulan kalau kapasitas produksi dua jenis 160 unit. a) Rumuskan fungsi tujuan b) Rumuskan pembatas c) Tanpa menghitung terlebih dahulu, perlihatkan daerah pemecahan yang ditunjukan dengan pembatas dengan gambar. 2. Seorang penjahit mempunyai 60m wol dan 40m katun. Dengan yang tersedia itu, penjahit membuat setelan jas dan rok kepada beberapa orang pelanggan. Satu stel jas memerlukan 3m wol dan 1m katun, satu rok memerlukan 2m wol, 2m katun. Berapa stel jas dan rok harus dibuat oleh penjahit kalau harga satu stel jas Rp. 120. 000,00 dan harga satu stel rok (baju wanita) Rp. 75.000,00. Untuk memperoleh pendapatan maksimum. a) Tentukan fungsi tujuan b) Tentukan pertidaksamaan yang menunjukan pembatas lengkap dengan syarat yang diperlukan. c) Gambarlah daerah pemecahan pertidaksamaan pembatas itu, kemudian tentukan koordinator titik sudut poligon (segi banyak) pada pembatas itu. 3. Seorang tuakang roti mempunyai bahan A, B, dan C dengan persediaan berturutturut 300 unit, 180 unit, dan 300 unit. Dengan bahan yang tersedia, tukang membuat dua macam roti sesuai dengan pesanan langganan. Pembuat roti menetapkan keperluan bahan sebagai berikut :
Program Linier
Macam roti
Bahan A
Bahan B
Bahan C
I
2
2
4
II
10
4
2
Page 73
Harga roti I sebesar Rp. 350,- dan harga roti kedua Rp. 800,Rumuskan fungsi tujuan dan pembatas !
BAB III METODE SIMPLEKS
Kompetensi Dasar : 6. Merubah system pertidaksamaan linier menjadi system persamaan linier. 7. Menyelesaikan persoalan Pl maksimum dan persoalan minimum dengan metode simpleks 8. Memberikan contoh – contoh penyelesaian Pl dengan metode Simpleks
Indikator Mahasiswa diharapkan mampu : 6.1. Menentukan variable slack atau surplus untuk suatu system pertidaksamaan linier 6.2. Menambahkan variable slack atau mengurangkan variable surplus dari system pertidaksamaan linier. 7.1. Membuat table simpleks permulaan 7.2. Menentukan penyelesaian dasar dalam suatu table simpleks 7.3. Mencari penyelesaian optimal untuk penyelesaian mungkin dasar 7.4. Mencari nilai maksimum atau minimum dari suatu fungsi tujuan ( obyektif ) 8.1. Memberikan contoh penyelesaian Pl maksimum dengan metode Simpleks 8.2. Memberikan contoh penyelesaian Pl minimum dengan metode Simpleks
A. Pendahuluan Hingga saat ini yang telah kita pelajari adalah penyelesaian permasalahan linear programming dengan tanda pertidaksamaan ≤ yang biasanya kita jumpai dalam permasalahan dengan fungsi tujuan maksimisasi. Prosedur dalam penyelesaian permasalahan maksimisasi dapat juga kita gunakan untuk menyelesaikan permasalahan minimisasi yang biasanya mempunyai tanda ≥ dan atau = pada fungsi kendalanya.
Program Linier
Page 74
Pada bab ini akan kita bahas penyelesaian permasalahan program linier dengan fungsi tujuan minimisasi. Pembahasan akan dimulai dengan memformulasikan permasalahan sesuai dengan standard simpleks, kemudian dilanjutkan dengan melakukan iterasi atau perbaikan tabel hingga optimal dan bagian terakhir pada bab ini akan dikemukakan beberapa issue teknis yang sering kita jumpai dalam metode 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). 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 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.
Program Linier
Page 75
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.
B. Masalah Dua Variabel Contoh 1: Z = 4x1 + 5 x2 ; maksimum d.p
3x1 + 2x2 ≤ 12 3x1 + 4x2 ≤ 18 x1 = 0, 2x2 ≤ 0
Tentukan nila x1 , x2 dan nilai Z maksimum. 1. Dengan cara aljabar
Program Linier
Page 76
Untuk memecahakan pertidaksamaan diatas kita tidak bisa secara langsung, akan tetapi pertidaksamaan tersebut harus dirubah dulu menjadi persamaan denga jalan memasukan “Slack Varibel” di sebelah kiri pertidaksamaan, agar pertidaksamaan menjadi persamaan. Dengan memasukan slack variabel x3 dan x4 kita peroleh dua persamaan sebagai berikut : 3x1 + 2x2 + x3 = 12 3x1 + 4x2 + x3 = 18 Dalam prakteknya x3 dan x4 merupakan bahan mentah sisa, yaitu yang tidak diproduksi. Maka dari itu c3 dan c4 masing-masing nilainya sama dengan nol, sebab tidak dijual. Persoalan program linier, dimana pertidaksamaan sudah menjadi persamaan disebut persoalan program linier yang standar. Persoalan program linier yang standard dari persoalan program linier di atas adalah sebagai barikut : Z = 4x1 + 5x2 + 0x3 + 0x4 ; maksimum d.p
3x1 + 2x2 + x3 = 12 3x1 + 4x2 + x4 = 18 x1 ≤ 0, x2 ≤ 0, x3 ≤ 0, x4 ≤ 0
x1, x2, x3, dan x4 disebut pemecahan dari persamaan tersebut apabila nila-nilai x1, x2, x3, dan x4 memenuhi persamaan tersebut. Karena ada 4 variabel akan tetapi hanya tersedia 2 persamaan maka hanya ada 2 variabel yang nilainya dapat diperoleh dari dua persamaan tersebut, sisanya sebanyak (4-2) = 2 nilainya harus nol. Pada umumnya kalau ada n variabel = x2, x3, ... xn akan tetapi hanya ada m persamaan, maka hanya ada m variabel yang nilainya dapat diperoleh dari m persamaan tersebut. Variabel yang diperoleh dari m persamaan tersebut dinamakan variabel dasar (basic variables), sedangkan pemecahanya disebut pemecahan dasar (basic solution). Pemecahan yang memenuhi semua syarat pembatasan (semua variabel bernilai positif/non negatif) disebut pemecahan fisibel (feasible solution). Kalau pemecahan fisibel merupakan pemecahan dasar, maka disebut pemecahan dasar fisibel (feasible basic solution). Pemecahan yang menghasilkan paling sedikit satu variabel yang negatif tidak fisiabel (not feasible). Pada umumnya, kalau ada n variabel x2, x3, . . . xn akan tetapi hanya ada m persamaan, maka bisa diperoleh sebanyak k persamaan dimana k = kombinasi, dihitung berdasarkan rumus : Program Linier
Page 77
(n! Dibaca : n faktorial) Pada contoh 1) diatas banyak variabel (n) = 4 dan banyak persamaan (m) = maka terdapat 4k2 pemecahan dasar, yaitu :
Jadi ada 6 buah persamaan dasar, dengan demikian ada 6 buah pemecahan darar (basis). Dari 6 pemecahan dasar ini, kita pilih pemecahan dasar yang fisisbel. Nilai variabel dasar sebagai pemecahan dasar yang fisibel ini, dimasukan ke dalam Z = 4x1 + 5x2 + 0x3 + 0x4. Kemudian dipilih pemecahan dasar fisibel yang memuat nilai z menjadi maksimum. Pemecahan dasar fisibel inilah yang merupakan pemecahan optimal. Sehingga 6 persamaan dasar dengan pemecahan dasarnya adalah sebagai berurut : Variabel Non
Variabel Basis
Keterangan
Z = 4x1 + 5x2
x1= 0 ; x2 = 0
x3= 12 ; x4 = 12
Fisibel → (Z1)
0
x1= 0 ; x3 = 0
x2= 6 ; x4 = -6
Tidak Fisibel
-
x1= 0 ; x4 = 0
x2= 4,5 ; x3 = 3
Fisibel → (Z2)
22,5
x2= 0 ; x3 = 0
x1= 4 ; x4 = 6
Fisibel → (Z3)
16
x2= 0 ; x4 = 0
x1= 6 ; x4 = -6
Tidak Fisibel
-
x3= 0 ; x4 = 0
x1= 2 ; x2 = 3
Fisibel → (Z4)
23
Basis
Dari tabel di atas diperoleh bahwa z1 = 0, maka tidak ada produksi/penjualan. Dan yang memberikan nilai tersebesar (maksimum) adalah Z4 = 23 = Z maks. Jadi keputusan yang harus dibuat oleh pemilik perusahaan adalah bahwa barang A dan B masing-masing harus diproduksi sebesar 2 satuan dan 3 satuan. Untuk cara aljabar ini dapat juga dilakukan dengan mempergunakan determinan. Z = 4x1 + 5x2 ; Maksimum d.p
3x1 + 2x2 ≤ 12 3x1 + 4x2 ≤ 18
Program Linier
Page 78
x1 ≥ 0, x2 ≥ 0 Persamaan standarnya : Z = 4x1 + 5x2 + 0x3 + 0x4 ; maksimum d.p
3x1 + 2x2 + x3 = 12 3x1 + 4x2 + x4 = 18 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 3x1 + 2x2 + x3 = 12 → 3x1 + 2x2 = 12 - x3 3x1 + 4x2 + x4 = 18 → 3x1 + 4x2 = 18 - x4 [
] [
]
[
] [
]
Agar Z maksimum maka nilai x3 dan x4 harus sekecil mungkin, untuk itu x3 dan x4 mendekati nol. Jadi
Sehingga Z = 4x1 + 5x2 = 4.2 + 5,3 = 23 2. Dengan cara grafik d.p
Z = 4x1 + 5x2 ; Maksimum 3x1 + 2x2 ≤ 12 3x1 + 4x2 ≤ 18 x1 ≥ 0, x2 ≥ 0
x2
Program Linier
Page 79
0
A
B
x1
3x1 + 2x2 = 12
3x1 + 4x2 = 18
Daerah yang diarsir pada gambar merupakan daerah penyelesaian. Dengan titik-titik kestirm O, A, B, dan C dimana kordinat titik O = (0,0), A = (4,0), C = (0,4 ½ ) dan koordinat titik B adalah merupakan perpotongan garis 3x 1 + 2x2 = 12 dengan garis 3x1 + 4x2 = 18 yaitu : [
]
[
]
[
]
[
]
Jadi koordinat titik B adalah (2,3). Maka nilai-nilai Z adalah : O = (0,0)
→ Z = 4x1 + 5x2 = 4,0 + 5,0 = 0
A = (4,0)
→ Z = 4x1 + 5x2 = 4,4 + 5,0 = 16
B = (2,3)
→ Z = 4x1 + 5x2 = 4,2 + 5,3 = 23
C = (0,4 ½ )
→ Z = 4x1 + 5x2 = 4,0 + 5,4 ½ = 22,5
Jadi nilai Z = 4x1 + 5x2 terbesar (maksimum) adalah pada x1 = 2 dan x2 = 3 yaitu dengan nilai = 23 Contoh 2: Z = 5x1 + 3x2 ; Minimum d.p
2x1 + x2 ≥ 3 x1 + x2 ≥ 2 x1 ≥ 0, x2 ≥ 0
tentukan nilai x1, x2 dan nilai Z minimum.
1. Dengan cara aljabar Sama halnya dengan contoh 1) di atas, dimana kita harus merubah pertidaksamaan terlebih dahulu menjadi persamaan. Oleh karena persoalan program linier di atas merupakan persoalan minimisasi, maka untuk mendapatkan persamaan standarnya dapat dilakukan dengan jalan memasukkan surplus Program Linier
Page 80
variables x3 dan x4. Surplus variabel yaitu variabel yang harus dikurangkan didalam sautu pertidaksamaan agar menjadi persamaan. Persoalan yang standard adalah sebagai berikut : Z = 5x1 + 3x2 + 0x3 + 0x4; Minimum d.p 2x1 + x2 - x3 = 3 x1 + x2 – x4 = 2 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 Variabel Non Variabel Basis Keterangan Basis
Z = 4x1 + 5x2
x1= 0 ; x2 = 0
x3= -3; x4 = -2
Tidak Fisibel
-
x1= 0 ; x3 = 0
x2= 3 ; x4 = 1
Fisibel → (Z1)
9
x1= 0 ; x4 = 0
x2= 2 ; x3 = -1
Tidak Fisibel
-
x2= 0 ; x3 = 0
x1= 3/2 ; x4 = -1/2
Tidak Fisibel
-
x2= 0 ; x4 = 0
x1= 2 ; x4 = 1
Fisibel → (Z2)
10
x3= 0 ; x4 = 0
x1= 1 ; x2 = 1
Fisibel → (Z3)
8
Jadi nilai minimum pada Z3 = 8 yaitu dengan nilai x1 = 1, x2 = 1. Seperti halnya pada contoh 1) diatas, pada masalah minimum ini juga dapat dilakukan dengan determinan : Z = 5x1 + 3x2 ; Minimum d.p
2x1 + x2 ≥ 3 x1 + x2 ≥ 2 x1 ≥ 0, x2 ≥ 0
Tentukan nilai x1, x2 dan nilai Z minimum.
Persamaan standarnya adalah : Z = 5x1 + 3x2 + 0x3 + 0x4; Minimum d.p
2x1 + x2 - x3 = 3 x1 + x2 – x4 = 2 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
maka : Program Linier
Page 81
2x1 + x2 - x3 = 3
→
2x1 + x2 = 3 + x3
x1 + x2 – x4 = 2
→
x1 + x2 = 2 + x4
[
] [
]
[
] [
]
Agar Z mimimum, maka x3 dan x4 harus mendekati nol. Jadi :
Dengan demikian nilai Z minimum adalah 5x1 + 3x2 = 5.1 + 3.1 =8 2. Dengan grafik Z = 5x1 + 3x2 ; Minimum d.p
2x1 + x2 ≥ 3 x1 + x2 ≥ 2 x1 ≥ 0, x2 ≥ 0
Tentukan nilai x1, x2 dan nilai Z minimum. x2 C
2x1 + x2 = 3
B
0
A
x1 + x2 = 2
x2
Daerah yang diarsir adalah daerah penyelesaian, dengan titik-titik ekstrim A, B, dan C. Dimana koordinat titik A adalah (2,0), C = (0,3) dan koordinat titik C adalah merupakan perpotongan garis 2x1 + x2 = 3 dengan garis x1 + x2 = 2, yaitu : x1 + x2 = 2 yaitu : Program Linier
Page 82
Jadi kordinat titik B adalah (1,1) dan nilai-nilai Z adalah : A = (2,0)
→ Z = 5x1 + 3x2 = 5,2 + 3,0 = 10
B = (1,1)
→ Z = 5x1 + 3x2 = 5,1 + 3,1 = 8
C = (0,4 ½ )
→ Z = 5x1 + 3x2 = 5,0 + 3,3 = 9
C. Masalah tiga variabel Contoh 1: Z = x1 + 3x2 + 3x3 ; Maksimum d.p
x1 + 2x2 + 3x3 ≤ 14 1/2x1 + 2x2 + 1/2x3 ≤ 10 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 tentukan nilai maksimum dari persoalan program linier tersebut.
1. Dengan aljabar Z = x1 + 3x2 + 3x3 + 0x4 + 0x5 + 0x6 ; Maksimum d.p
x1 + 2x2 + 3x3 + x4 = 14 1/2x1 + 2x2 + 1/2x3 + x5 = 10 x1 + 5x2 + x3 + x6 = 26 xi ≥ 0 ; i =1,2,3,4,5,6
Oleh karena banyak variabel = 6 dan banyak persamaan = 3, maka terdapat buah pemecahan.
Variabel Non Variabel Basis Basis 1 2 x1 = 0, x2 = 0, x3 = 0 x4 = 14, x5 = 10, x6 = 16 x1 = 0, x2 = 0, x4 = 0 x3 = 14/3, x5 = 23/3, x6 = 16 x1 = 0, x2 = 0, x5 = 0 x3=20, x4 =-46, x6 = -64 x1 = 0, x2 = 0, x6 = 0 x3 =13/2, x4 = -11, Program Linier
Keterngan
Z = x1 + 3x2 + 3x3
3 Fisibel → (Z1) Fisibel → (Z2)
4 0 14
Tidak Fisibel Tidak Fisibel
Page 83
x1 = 0, x3 = 0, x4 = 0 x1 = 0, x3 = 0, x5 = 0 x1 = 0, x3 = 0, x6 = 0 x1 = 0, x4 = 0, x5 = 0 x1 = 0, x4 = 0, x6 = 0 x1 = 0, x5 = 0, x6 = 0 x2 = 0, x3 = 0, x4 = 0 x2 = 0, x3 = 0, x5 = 0 x2 = 0, x3 = 0, x6 = 0 x2 = 0, x4 = 0, x5 = 0 x2 = 0, x4 = 0, x6 = 0 x2 = 0, x5 = 0, x6 = 0 x3 = 0, x4 = 0, x5 = 0 x3 = 0, x4 = 0, x6 = 0 x3 = 0, x5 = 0, x6 = 0 x4 = 0, x5 = 0, x6 = 0
x5 = 22/7 x2=7, x5 =-4, x6 = -9 x2=5, x4 =4, x6 = 1 x2=26/5, x4 =18/5, x5 = -2/5 x2=23/5, x3 =8/5, x6 = -97/5 x2=22/7, x3 =18/7, x5 = 17/7 x2=54/11, x3 =4/11, x4 = 34/11 x1=14, x5 =3, x6 = 12 x1=20, x4 =-6, x6 = 6 x1=26, x4 =-12, x5 = -3 x1=-23, x3 =-3, x5 = -7 x1=-22, x3 =12, x5 = -7 x1=46/3, x3 =-16/3, x4 =-2/3 x1=8, x2 =3, x6 = 3 x1=6, x4 =4, x5 = -1 x1=-4, x2 =6, x4 = 6 x1=17/4,x2 =14/4,x=3/4
Tidak Fisibel Fisibel → (Z3) Tidak Fisibel
15 -
Tidak Fisibel
-
Fisibel → (Z4)
120/7
Fisibel → (Z5)
174/11
Fisibel → (Z6) Tidak Fisibel Tidak Fisibel Tidak Fisibel
11 -
Tidak Fisibel Tidak Fisibel
-
Fisibel → (Z7) Tidak Fisibel Tidak Fisibel Fisibel → (Z8)
17 71/14
Jadi nilai maksimum pada Z8 = 71/14 yaitu pada x1=17/4, x2 =14/4, x=3/4 2. Dengan grafik Z = x1 + 3x2 + 3x3 ; Maksimum d.p
x1 + 2x2 + 3x3 ≤ 14 1/2x1 + 2x2 + 1/2x3 ≤ 10 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 tentukan nilai maksimum dari persoalan program linier tersebut.
x3
(0,0,14/3) (0,0,6 1/2)
Program Linier
(0,0,20)
(0,23/5,8/5) (0,54/11,14/11) (0,22/7,18/7)
Page 84
(18,0,2) (6,4,0)
(0,7,0) (17/14,15/144,3/4)
x2
(0,3,0)
(26,0,0)
x1
Yang merupakan daerah penyelesaiannya adalah daerah yang diarsir dengan nilai-nilai Z adalah : (0, 0, 0)
; maka Z = x1 + 3x2 + 3x3 = 0
(14, 0, 0)
; maka Z = x1 + 3x2 + 3x3 = 14
(8, 3, 0)
; maka Z = x1 + 3x2 + 3x3 = 17
(0, 5, 0)
; maka Z = x1 + 3x2 + 3x3 = 15
(0, 54/11, 44/11)
; maka Z = x1 + 3x2 + 3x3 = 174/11
(0, 22/7, 18/7)
; maka Z = x1 + 3x2 + 3x3 = 120/7
(0, 0, 14/3)
; maka Z = x1 + 3x2 + 3x3 = 14
(17/4, 15/4, 3/4)
; maka Z = x1 + 3x2 + 3x3 = 71/4
Jadi nilai Z maksimum = 71/4 dengan nilai x1=17/4, x2 =14/4, x=3/4 Contoh 2: Z = 60x1 + 40x2 + 80x3 ; Minimum d.p
3x1 + 2x2 + x3 ≥ 2 4x1 + x2 + 3x3 ≥ 4 2x1 + 2x2 + 2x3 ≥ 3 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
1. Dengan cara aljabar Persamaan standardnya adalah Z = 60x1 + 40x2 + 80x3 + 0x4 + 0x5+ 0x6; Minimum d.p
3x1 + 2x2 + x3 - x4 = 2 4x1 + x2 + 3x3 – x5 = 4 2x1 + 2x2 + 2x3 – x6 = 3 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0
Variabel Non Variabel Basis Basis 1 2 x1 = 0, x2 = 0, x3 = 0 x4 = -2, x5 = -4, x6 = -3 x1 = 0, x2 = 0, x4 = 0 x3 = 2, x5 = 2, x6 = 1 Program Linier
Keterngan
Z = x1 + 3x2 + 3x3
3 Tidak Fisibel Fisibel → (Z1)
4 160 Page 85
x1 = 0, x2 = 0, x5 = 0 x3=4/3, x4 = -2/3, x6 = -1/3 x1 = 0, x2 = 0, x6 = 0 x3 =3/2, x4 = -1/2, x5 = 1/2 x1 = 0, x3 = 0, x4 = 0 x2=1, x5 =-3, x6 = -1 x1 = 0, x3 = 0, x5 = 0 x2=4, x4 =6, x6 = 5 x1 = 0, x3 = 0, x6 = 0 x2=3/2, x4 = -5/2, x5 = 1 x1 = 0, x4 = 0, x5 = 0 x2=2/5, x3 =6/5, x6 = 1/5 x1 = 0, x4 = 0, x6 = 0 x2=1/2, x3 =1, x5 = 1 x1 = 0, x5 = 0, x6 = 0 x2=1/4, x3 = 5/4, x4 = -1/4 x2 = 0, x3 = 0, x4 = 0 x1=2/3, x5 =-4/3, x6 = -5/3 x2 = 0, x3 = 0, x5 = 0 x1=1, x4 =1, x6 = -6 x2 = 0, x3 = 0, x6 = 0 x1=3/2, x4 =-5/2, x5 = 0 x2 = 0, x4 = 0, x5 = 0 x1=-2/5, x3 =4/5, x5 = -3/5 x2 = 0, x4 = 0, x6 = 0 x1=1/4, x3 =5/4, x2 = 0, x5 = 0, x6 = 0 x5 = 7/4 x3 = 0, x4 = 0, x5 = 0 x1=-1/2, x3 =2, x3 = 0, x4 = 0, x6 = 0 x4 =-3/2 x3 = 0, x5 = 0, x6 = 0 x1=6/5, x2 =-2/5, x4 = 0, x5 = 0, x6 = 0 x6 = -7/5 x1=-1, x4 =5/2, x5 = -11/2 x1 = 5/6, x2 =2/3, x4 = 11/6 x1=1/10, x2 = 7/10, x=7/10
Tidak Fisibel
-
Tidak Fisibel Tidak Fisibel Fisibel → (Z2) Tidak Fisibel
160 -
Fisibel → (Z3)
112
Fisibel → (Z4) Tidak Fisibel
100 -
Tidak Fisibel
-
Tidak Fisibel Fisibel → (Z5) Tidak Fisibel
90 -
Fisibel → (Z6)
115
Tidak Fisibel
-
Tidak Fisibel
-
Tidak Fisibel
-
Fisibel → (Z7)
230/3
Fisibel → (Z8)
90
Jadi Z minimum Z6 = 230/7 dengan nilai x1 = 5/6, x2 =2/3, x4 = 11/6 2. Dengan cara grafik Z = 60x1 + 40x2 + 80x3 ; Minimum d.p
3x1 + 2x2 + x3 ≥ 2 4x1 + x2 + 3x3 ≥ 4 2x1 + 2x2 + 2x3 ≥ 3 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Program Linier
Page 86
tentukan nilai maksimum dari persoalan program linier tersebut. C (0.0,2) (0.0,3/2)
x3
(0.0,4/3)
(0.1/2,1) (1/4.0,5/4)
(0.1/4,5/4) B (0.4,0)
x3
(5/6.2/3,0) (1.0,0)
A (3/2.0,2)
x3 Daerah penyelesaian adalah daerah bagian luar dari segi banyak OABCDEFGH Nilai – nilai ekstrimnya adalah : (0, 0, 0)
; maka Z = 60x1 + 40x2 + 80x3 = 0
(0, 0, 2)
; maka Z = 60x1 + 40x2 + 80x3 = 160
(0, 4, 0)
; maka Z = 60x1 + 40x2 + 80x3 = 160
(0, 1/2, 0)
; maka Z = 60x1 + 40x2 + 80x3 = 100
(0, 1/14, 5/4)
; maka Z = 60x1 + 40x2 + 80x3 = 110
(3/2, 0, 0)
; maka Z = 60x1 + 40x2 + 80x3 = 90
(1/4, 0, 4/5)
; maka Z = 60x1 + 40x2 + 80x3 = 115
(5/6, 2/3, 0)
; maka Z = 60x1 + 40x2 + 80x3 = 230
(1/10, 7/10,7/10)
; maka Z = 60x1 + 40x2 + 80x3 = 90
Jadi nilai terkecil (minimum) pada Z8 = 60x1 + 40x2 + 80x3 dengan nilai x1 = 5/6, x2 2/3, x3 = 0)
D. Rangkuman
Program Linier
Page 87
1. Salah satu teknik penentuan solusi optimal yang digunakan dalam pemrograman linier adalah metode simpleks. 2. Beberapa istilah yang sangat sering digunakan dalam metode simpleks, diantaranya iterasi, variabel non basis, variabel basis, solusi atau nilai kanan, variabel slack, variabel surplus, variabel buatan, kolom pivot (kolom kerja), baris pivot (baris kerja), elemen pivot (elemen kerja), variabel masuk, dan variabel keluar. 3. Penyelesaian dua dan tiga variabel dapat dilakukan dengan metode grafikd dan metode aljabar.
Uji Kompetensi 1.
Pemilik perusahaan mempunyai 3 macam bahan mentah, katakan bahan mentah I, II, III masing-masing tersedia 50 satuan, 80, satuan dan 140 satuan. Dari ketiga bahan mentah tersebut akan dibuat 2 macam barang produksi yaitu baran A dan B. 1 satuan barang A memerlukan bahan mentah i, II, dan III masing-masing sebesar 1, 1 dan 3 satuan. 1 satuan barang B memerlukan bahan mentah i, II, dan III masing-masing sebesar 1, 2 dan 2 satuan. Apabila barang A dan B dijual masing-masing dijual dan masing-masing laku Rp. 4000,00 dan Rp. 3000,00 persatuan. Berapakah besaranya jumlah produsi barang A dan B agar jumlah hasil penjualan maksimal 2 jumlah bahan mentah yang dipergunakan tidak boleh melebihi persediaan yang ada. Rumuskan persoalan tersebut menjadi persolan program linier, kemudian pecahkan dengan cara aljabar dan grafik.
2.
Seorang petani modern menghadapi suatu persoalan sebagai berikut : Setiap sapi agar supaya sehat harus diberi makan yang mengandung paling sedikit 27, 21, dan 30 satuan unsur nutrisi jenis A, B dan C setiap harinya. Dua jenis makanan katakan M1 dan M2 diberikan kepada sapi tersebut. Satu pon jenis makanan M1 mengandung unsur nitrisi jenis A, B, dan C masing-masing 3, 1 dan 1 satuan. Sedangkan satu pon jenis M2 mengandung jenis unsur nutrisi jenis A, B, dan C masing-masing sebesar 1, 1, dan 2 satuan. Perlu diketahui bahwa harga satu pon M1 dan M2 masing-masing
Program Linier
Page 88
sebesar 4 dan 2 satuan uang. Petani tersebut harus memutuskan apakah membeli satu jenis makanan saja atau kedua-duanya kemudian mencampurkanya. Tujuannya adalah agar jumlah pengeluaran petani tersebut minimum. Rumuskan persolan ini menjadi persoalan program linier, kemudian pecahkan baik dengan cara grafik maupun cara aljabar.
3.
Ada 3 mesin produksi M1, M2 dan M3 yang dipergunakan untuk memproduksi 4 barang yaitu A, B, C, dan D. Proses pembuatan ke 4 barang produksi tersebut harus melalui ketiga mesin tersebut. Proses produksi bagi setiap barang dumulai dari M1, M2 dan M3. Masing-masing hanya dapat dipergunakan 2000, 8000, dan 5000 satuan waktu (tidak lebih lama dari itu). Satu-satuan barang A memerlukan waktu dari M1, M2 dan M3. Masing-masing 1,5 satuan 1 satuan, dan 1,5 satuan waktu. Satu satuan barang B memerlukan waktu dari M1, M2 dan M3. Masiing-masing selama 1 satuan, 5 satuan, dan 3 satuan waktu. Satu satuan barang C memerlukan waktu dari M1, M2 dan M3 masing-masing selama1 satuan, 3,5 satuan, dan 1 satuan waktu. Satu satuan barang D memerlukan waktu dari M1, M2 dan M3 masing-masing selama 3 satuan, 1 satuan, dan 1 satuan waktu. Satu satuan barang A, B, C, dan D apabila dijual masingmasing memeberikan keuntungan sebesar Rp. 5.240,00 , Rp. 7.300,00 , Rp. 8.340,00, dan Rp. 4.180,00. Berapa besarnya masing-masing barang produksi agar diperoleh jumlah keuntungan maksimum denga memperhatikan pembatasan tersedianya waktu bagi setiap mesin. Rumusakan persoalan ini menjadi persoalan program linier.
4.
Sebuah perusahaan yang memproduksi mainan anak-anak akan membuat bingkisan lebaran yang setiap bingkisan berisi kombinasi mainan, alat olahraga, dan buku. Untuk itu dibuat 3 tipe bingkisan S, M, dan L. Tipe S berisi 4 mainan, 4 alat olah raga, dan 2 buku dengan harga jual 30 satuan uang. Tipe M berisi 5 mainan, 6 alat olah raga, dan 5 buku dengan harga jual 40 satuan uang. Sedangkan Tipe L berisi 6 mainan, 5 alat olah raga, dan 5 buku dengan harga jual 60 satuan uang. Berkenaan dengan itu tersedia 60.000 mainan, 75.000 alat olahraga, dan 45.0000 buku. Berapa masing-masing tipe bingkisan harus diproduksi agar diperoleh harga jual yang maksimum.
Program Linier
Page 89
5.
Suatu diet yang sekurangnya terdiri dari 10 unit nutrien P, 12 unit nutrien Q dan 20 unit nutrien R. Nutrien ini berisi kombinasi beberapa zat-zat makanan A, B, dan C. 1 unit A berharga 4 satuan uang mengandung 4 unit P, 2 unit Q, dan 4 unit R. Sedangkan 1 unit C berharga 5 satuan uang mengandung 1 unit Q, dan 5 unit R. Dengan menggunakan cara aljabar dan grafik, tentukan harga minimum campuran beserta komposisinya.
6.
Diketahui : Z = 2x1 + 3x2 + x3 ; Maksimum Dp : 3x1 + 2x2 + x3 ≤ 8 2x1 + 3x2 + x3 ≤ 10 5x1 + 3x2 + 2x3 ≤ 17 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 tentukan nilai Z maksimum, dengan cara aljabar dan grafik.
7.
Diketahui : Z = 28x1 + 400x2 + 20x3 ; Minimum Dp : x1 + 5x2 + x3 ≥ 8 2x1 + 3x2 + x3 ≥ 15 3x1 + x2 + 2x3 ≥ 10 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 tentukan nilai Z minimum
BAB IV METODE SIMPLEX SEBAGAI PROSEDUR PERHITUNGAN DAN PERMASALAHAN DUAL Kompetensi Dasar 9. Menentukan persoalan dual yang berkaitan dengan persoalan primal yang diberikan. dan sebaliknya. 10. Menjelaskan kaidah - kaidah transformasi untuk mendapatkan dual dan teorema – teorema dual 11. Menyelesaikan persoalan optimal primal melalui persoalan optimal dual , dan sebaliknya
Indikator Mahasiswa diharapkan dapat: 9.1. Merubah persoalan primal menjadi persolan dual 9.2. Merubah persoalan dual menjadi persoalan primal
Program Linier
10.1. Menyebutkan kaidah – kaidah transformasi untuk mendapatkan dual 10.2. Menyebutkan teorema – teorema dual 10.3. Memberikan contoh penggunaan kaidah transformasi dual. 11.1. Menentukan penyelesaian persoalan PL maksimum primal melalui persoalan
Page 90
A. Pendahuluan Metode simpleks ialah metode yang secara sistematis dimulai dari suatu pemecahan dasar yang fisibel kepemecahan dasar yang fisibel (feasible) lainya dan ini dilakukan berulang-ulang (dengan jumlah ulangan yang terbatas) sehingga akhirnya 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. Metode simpleks ialah metode yang secara sistematis dimulai dari suatu pemecahan dasar yang fisibel kepemecahan dasar yang fisibel (feasible) lainya dan ini dilakukan berulang-ulang (dengan jumlah ulangan yang terbatas) sehingga akhirnya 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.
B. Metode Simplex sebagai Prosedur Perhitungan Metode simpleks ialah metode yang secara sistematis dimulai dari suatu pemecahan dasar yang fisibel kepemecahan dasar yang fisibel (feasible) lainya dan ini dilakukan berulang-ulang (dengan jumlah ulangan yang terbatas) sehingga akhirnya 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. Di sini kita tidak akan membicarakan teori Simplex secara mendalam, akan tetapi hanya akan diuraikan hal-hal yang erat hubunganya dengan teknik perhitungan metode Simplex. Metode simplex lebih efisien serta dilengkapi dengan suatu tes criteria yang bisa memberitahukan kapan perhitungan harus diberhentikan dan kapan harus dilanjutkan, sampai diperoleh suatu optimal solution (pemecahan optimal).
Program Linier
Page 91
Dalam hal ini pada umumnya dipergunakan tabel-tabel, dari tabel I yang memberikan pemecahan dasar permulaan yang fisibel sampai pada pemecahan terakhir yang memberikan optimal solution. Yang lebih menarik adalah bahwa semua informasi yang kita perlukan (tes criteria, nilai variabel-variabel, nilai fungsi tujuan) akan terdapat pada setiap tabel. Selain dari itu nilai fungsi tujuan dari suatu tabel akan lebih besar/kecil atau sama dengan tabel sebelumnya. Pada umumnya suatu persoalan program linier diklarifikasikan menjadi 3 kategori : 1. Tidak ada pemecahan yang fisibel 2. Ada pemecahan optimum (maximum/minimum) 3. Fungsi objektif tiada ada batasnya. Persoalan program linier Z = C1X1 + C2X2 + . . . CmXm + . . . Cm+nXm+n d.p ;
a11x1 + a12x2 + . . . a1mxm ≤ h1 a21x1 + a22x2 + . . . a2mxm ≤ h2 . . . an1x1 + an2x2 + . . . anmxm ≤ hn x1 , x2 + . . . xm ≥ 0
persamaan standardnya adalah : a11x1 + a12x2 + . . . a1mxm + xm+1 = h1 a21x1 + a22x2 + . . . a2mxm + xm+2 = h2 . . . an1x1 + an2x2 + . . . a1nmxm + xm+n = hn x1 , x2
. . . xm , xm+1
, . . .
xm+n
,
≥ 0
persamaan matriksnya
a11 Program Linier
a12 . . . a1m 1
0 . . . 0
x1
h1 Page 92
a21
↑
a22 . . . a2m1
0 . . . 0
x2
h2
.
.
.
.
.
.
.
.
xm+n
hn
an1
an2 . . . anm 0
0 . . . 1
↑
↑
↑ ↑
A1
A2
Am Am+1 Am+2 Am+n
↑
↑
=
.
↑ x
H
Maka A x X = H ; matriks A = (A1, A2,. . . Am,Am+1, . . . Am+n) dari matriks diatas terlihat bahwa Am+1,Am+2, . . . Am+n dalam baris. Yang perlu diingat disini adalah bahwa selalu diusahakan adanya Identitiy Matriks dalam matriks A. Pada matriks diatas Am+1,Am+2, . . . Am+n memberikan identity matriks yang sekaligus merupakan basis. Dengan demikian Am+1,Am+2, . . . Am+n merupakan pemecahan dasar fisibel permulaan. Bentuk metriks diatas kalau dipindahakan kedalam tabel sebagai berikut : cj
c1
c2
...
cm
cm+1
cm+2
...
cm+n
H
A1
A2
...
Am
Am+1
Am+2
...
Am+n
cAm+1 Am+1
h1
a11
a12
...
a1m
1
0
...
0
cAm+2 Am+2
h2
a21
a22
...
a2m
0
1
...
0
Vektor dalam
CB
basis
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Hn
an1
an2
anm
0
0
z
Z1 – C1
Z2 – C2
Zm – Cm
ZAm + 1 -
ZAm + 2 -
CAm + 1
CAm + 2
cAm+n Am+n zj - cj
...
1 ...
ZAm + n CAm + n
Kolom pertama dari pada tabel memberikan CB yaitu prices dari vektor-vektor dalam basis.
Program Linier
Kolom kedua memberikan vektor-vektor yang ada dalam basis (sebanyak m). Page 93
Kolom ketiga dari tabel dengan huruf H, memberikan nilai h yang baru (current value), dengan nilai fungsi obyektif Z pada baris yang terakhir, sebagai pemecahan dasar fisibel yang bersangkutan. Z = (cAm+1)(h1) + (cAm+2)(h2). . . + (cAm+n)(hn)
Baris pertama dari pada tabel memberikan prices yang berasosiasi dengan vektorvektor yang bersangkutan, misalnya prices cj untuk vektor Aj
Jadi tabel diatas merupakan tabel I yang memeberikan pemecahan dasar permulaan yang fisibel. Untuk mendapatkan pemecahan yang optimal diperlukan tabel-tabel berikutnya sehingga memberikan pemecahan terakhir yang optimal. Contoh 1: Tentukan nilai x1, x2 s.r.s ; Z = 5x1+3x2 d.p ; 3x1+5x2 ≤15 5x1+2x2 ≤10 x1 ≥ 0, x2 ≤ 0
persamaan standard : s.r.s ; Z = 5x1+3x2 +0x3+0x4 d.p ; 3x1+5x2 +x3 =15 5x1+2x2 +x4 =10 x1 ≥ 0, x2 ≤ 0, x3 ≥ 0, x4 ≤ 0 persamaan matriksnya [ A3 dan A4 dalam basis Tabel 1 cj CB VDB H 0 A3 15 0 A4 10 Zj - Cj 0
][ ]
5 A1 3 5 -5
[
]
3 A2 5 2 -3
0 A3 1 0 0
0 A4 0 1 0
Pemecahan ini belum optimal, sebab masih ada nilai Zj – Cj < 0 (pada kolom A1), maka daripada itu kolom A1 masuk ke basis. Jadi karena pemecahan pada tabel I belum optimal, maka kita harus melanjutkan ke tabel 2. Untuk memperoleh tabel 2 kita harus menentukan kunci terlebih dahulu. Program Linier
Page 94
Dalam hal pemilihan kunci dapat dilakukan hal sebagai berikut : 1) Pada baris Zj – Cj tentukan nilai yang paling negatif, maka kolom pada nilai terkecil tersebut dinamakan dengan kolom kunci (k) 2) Masing-masing nilai kolom H dibagi dengan nilai-nilai yang ada pada kolom k yang bersesuaian. Maka pada nilai hasil bagi terkecil (minimum) merupakan baris kunci (r) 3) Perpotongan kolom k dengan baris r merupakan kunci Tabel 2 cj VDB A3 A1 Zj - Cj
CB 0 5
H 9 2 10
5 A1 0 1 0
3 A2 19/5 2/5 -1
0 A3 1 0 0
0 A4 -3/5 1/5 1
Keterangan : Dalam pengisian tabel 2 ini dapat dilakukan hal sebagai berikut : Untuk baris kunci (r), masing-masing elemen pada baris r dibagi dengan kunci Untuk kolom kunci (k), masing-masing elemen pada kolom k ini diganti dengan nol kecuali elemen kunci; dimana elemen kunci ini di ganti dengan 1. Sedangkan untuk pengisian elemen-elemen yang lainya agar lebih mudah dapat digunakan determinan, dalam hal ini yang menjadi diagonal utamanya adalah yang mengandung kunci dan elemen lama yang akan diganti, kemudian nilai determinan ini dibagi dengan kunci. Contoh : 9 diperoleh dari 1 diperoleh dari -1 diperoleh dari Dan seterusnya. Program Linier
Page 95
Dari pemecahan dasar yang baru (tabel 2), juga masih belum optimal karena masih ada baris Zj - Cj < 0 . untuk itu diperlukan tabel selanjutnya, yaitu tabel 3. Dari tabel 2 diatas Z2 – C2 = -1 yang merupakan satu-satunya kolom yang negatif, maka dari itu A2 kita masukan ke basis (merupakan kolom kunci). Sedangkan nilai hasil bagi minimum antara elemen-elemen pada kolom H dengan elemen-elemen pada kolo A2 yang bersesuaian adalah 45/19, yaitu pada baris A3 (merupakan baris kunci) maka dari itu A3 keluar dari basis, jadi A3 digantikan oleh A2. Maka kunci adalah merupakan perpotongan antara kolom kunci dengan baris kunci 19/5. Selanjutnya untuk pengisian elemen-elemen lainya dapat dilakukan seperti cara pengisian tabel 2 diatas. Tabel 3 cj VDB A2 A1 Zj - Cj
CB 3 5
H 45/19 24/19 85/7
5 A1 0 1 0
3 A2 1 0 0
0 A3 5/19 -2/19 5/19
0 A4 -1/7 5/19 6/7
Dikarenakan semua Zj - Cj ≥ 0 untuk setiap Aj, maka tabel 3 sudah memberikan pemecahan yang optimal. Dimana A1 dan A2 dalam basis. Jadi pemecahan optimal diperoleh dengan x1 = 24/19, x2 = 45/19 dan nilai fungsi tujuan Z = 85/7 (dari kolom H). Jadi nilai maksimum dari Z = 85/7 Contoh 2: Tentukan nilai x1, x2 s.r.s ; Z = 4x1+6x2 d.p ; 0,5x1 + x2 ≤ 4 2x1+ x2 ≤ 8 4x1+ 2x2 ≤ 2 x1 ≥ 0, x2 ≤ 0
; Maksimum
persamaan standard : s.r.s d.p
Program Linier
; Z = 4x1+6x2 +0x3+0x4 ; Maksimum ; 0,5x1 + x2 +x3 = 4 2x1+ x2 + x4 = 8 4x1+ 2x2 + x5 = 2 x1 ≥ 0, x2 ≤ 0, x3 ≥ 0, x4 ≤ 0, x5 ≤ 0
Page 96
Persamaan matriksnya :
[
]
[ ] [ ]
Tabel 1 cj VDB A3 A4 A4 Zj - Cj
CB 0 0 0
H 15 10 2 0
5 A1 ½ 2 4 -4
3 A2 1 1 -2 -6
0 A3 1 0 0 0
0 A4 0 1 0 0
0 A5 0 0 1 0
A2 harus masuk kebasisdan A3 dari baris I harus diganti A2 kerana A2 merupakan kolom kunci (yaitu nilai Zj - Cj paling negatif) dan A3 merupakan baris kunci (nilai hasil bagi terkecil dari masing-masing elemen pada kolom H dengan masing-masing elemen pada kolom kunci yang bersesuaian). Tabel 2 cj VDB A2 A4 A5 Zj - Cj
CB 0 0 0
H 4 5 10 0
5 A1 ½ 3/2 5 -1
3 A2 1 0 0 -1
0 A3 1 -1 0 0
0 A4 0 1 0 0
0 A5 0 0 1 0
H 3 1 2 0
5 A1 0 0 1 -1
3 A2 1 0 0 -1
0 A3 0,8 -1,6 0,4 6,4
0 A4 0 1 0 0
0 A5 0,1 -0,3 0,2 0
Tabel 3 cj VDB A2 A4 A1 Zj - Cj
CB 0 0 0
Karena semua Zj - Cj ≥ 0, optimal solution diperoleh tabel 3. Jadi nilai fungsi tujuan yang maksimum (Z maksimum) adalah pada x1 = 2 dan x2 = 3.
Program Linier
Page 97
C. Rumus transformasi Dalam menentukan nilia optimum dari fungsi tujuan dengan metode simplex ini, untuk menghitung nilai-nilai baru pada setiap tabel berdasarkan tabel sebelumnya, selain dengan menggunakan cara diatas juga dapat dilakukan dengan mempergunakan rumus transformasi . [
]
Dengan menggunakan rumus transformasi ini, pertama kita harus mencari vektor kolom T berdasarkan nilai-nilai yang terdapat pada kolom kunci (k). Kemudian nilai baru pada kolo (Aj) diperoleh dengan jalan menambahkan nilai lama dari kolom yang bersangkutan (Aj) denga arj T dimana arj adalah elemen lama dari kolom tersebut.
[
] [
]
Contoh : Tentukan nilai x1 dan x2 s.r.s ; Z = 2,5x1+2x2 d.p ; x1 + 2x2 ≤ 8000 3x1+ 2x2 ≤ 9000 x1 ≥ 0, x2 ≤ 0 persamaan standard : s.r.s ; Z = 4x1+6x2 +0x3+0x4 d.p ; x1 + 2x2 +x3 = 8000 3x1+ 2x2 + x4 = 9000 x1 ≥ 0, x2 ≤ 0, x3 ≥ 0, x4 ≤ 0
; Maksimum
; Maksimum
Tabel 1 CB 0 0
Program Linier
cj VDB A3 A4 Zj - Cj
H 8000 9000 0
2,5 A1 1 3 -2,5
2 A2 2 2 -2
0 A3 1 0 0
0 A4 0 1 0
Page 98
Karena Z2 – C2 terkecil maka A1 masuk dalam basis dan hasil bagi terkecil adalah 9000/3 = 3000, jadi baris 2 harus diganti, maksudnya A4 keluar dari basis diganti A1 dalam tabel berikutnya dengan demikian kunci adalah 3. → r =2 [
[
]
[
]
]
[
]
(
[
[
]
[
]
[
]
[
[
]
[
]
[ ]
[
[
]
[
]
[ ]
[
]
[
]
[ ]
)
]
[
]
[ ]
]
[
]
[
]
[ ]
[
]
[
]
]
Berdasarkan hasil perhitungan diatas dapat disusun tabel 2 sebagai berikut Tabel 2 cj VDB A3 A1 Zj - Cj
CB 0 5/2
H 5000 3000 7500
2,5 A1 0 1 0
2 A2 4/3 2/3 -1/3
0 A3 1 0 0
0 A4 -1/3 1/3 5/6
Karena Zj – Cj = -1/3 (terkecil), makadalam tabel 3 A2 masuk dalam basis . Sedangkan hasil bagi terkecil adalah 3750 (yaitu baris I), maka vektor dari baris peertama (=A3) harus keluar dignti dengan A2. → r =1
Program Linier
Page 99
[
[
]
[
]
]
[
]
[
]
[
]
[
]
[
]
[
]
[
]
(
[
]
[
]
]
[
]
[ ]
[
]
[
]
[
[
]
[ ]
[ ] [
[
)
[
]
]
]
[
[
]
]
[
]
Berdasarkan hasil perhitungan diatas kemudian dapat dibentuk tabel 3 sebagai berikut : Tabel 2 cj
2,5
2
0
0
CB
VDB
H
A1
A2
A3
A4
0
A2
3750
0
1
3/4
-1/4
5/2
A1
500
1
0
-1/2
½
Zj - Cj
8750
0
0
1/4
¾
Oleh karena semua nilai Zj – Cj ≤ 0, maka sudah tercapailah pemecahan optimal, yang memberikan nilai fungsi tujuan sebesar 8750 (maksimum) dengan nilai x1 = 500 dan x2 = 3750.
Program Linier
Page 100
1. Pemecahan Dasar Awal yang Fisibel dan Variabel Buatan Berdasarkan contoh-contoh permasalahan program linier diatas selalu berdasarkan kepada kenyataan bahwa telah diperoleh pemecahan dasar awal atau pemecahan fisibel. Hal ini dikemukakan dengan adanya identity matriks dari matriks A. Perhatikan contoh berikut : A x X = H, maka : A1 A1 A1 A1 A1 [
][ ]
[ ]
I = identity Matriks, sekaligus basis Akan tetapi tidak selamanya matriks A mengandung identity matriks. Pada hal untuk menggunakan metode simplex, harus mulai dengan adanya pemecahan awal yang fisibel. Untuk itu harus dimasukan variabel buatan (artificial variabel). Banyaknya variabel buatan bisa lebih dari satu. Pembuatan variabel buatan ini hanya merupakan manipulasi matematika untuk memungkinkan memperoleh pemecahan. Variabel buatan diberu simbol xa1 dengan koefisien harga yang sering disebut „price‟ cai . kolom yang bersangkutan dengan variabel buatan xai ialah qi . vektor buatan q1 tidak boleh selamanya berada dalam basis, dia harus kelur dari basis. Agar supaya keluar dari basis, harus diberi koefisien yang tidak menguntungkan artinya tidak dapat menambah fungsi tujuan menjadi lebih besar, didalam persoalan yang maksimum. Penentuan koefisien harga bagi xa1 adalah sebagai berikut : Cai = - M ; M > 0, kalau Z harus maksimum Cai = - M ; M > 0, kalau Z harus minimum M adalah suatu nilai yang besar sekali. Untuk perhitungan dengan tangan tetap saja disebut M, tanpa diberi nilai angka. Akan tetapi suatu pemecahan program linier yang menggunakan electronic data processing (computer) M harus, paling sedikit 1000 kali koefisien harga tersbesar dari variabel lainya.
Contoh 1) Tentukan nilai x1 dan x2 Program Linier
Page 101
s.r.s d.p
; Z = 7x1+ 5x2 ; 3x1 + 2x2 ≤ 4 x1+ x2 = 3 x1 ≥ 0, x2 ≥ 0 3x1 + 2x2 + x3 = 4 x1+ x2 = 3 [
][ ]
; Maksimum
[ ]
A tidak mengandung identity matriks. Maksudnya variabel buatan xa 3x1 + 2x2 + x3 + 0x4= 4 x1+ x2 + 0x3 + 0x4= 3
[
][ ]
[ ]
I = identity matriks, sekaligus basis → Z = 7x1+ 5x2 +0x3 + (-M)xn ; maksimum Contoh 2) Cari x1 dan x2 s.r.s ; Z = 3x1+ 2x2 + x3+ 5x4 ; Maksimum d.p ; 3x1 + 4x2 + 5x3 + 6x4 ≤ 5 2x1 + 6x2 + x3 + 5x4 ≥ 6 x1 + x2 + 5x3 + x4 ≥ 7 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 persamaan standardna adalah : s.r.s : Z = 3x1+ 2x2 + x3+ 5x4 + 0x5+ 0x6 ; maksimum d.p ; 3x1 + 4x2 + 5x3 + 6x4 + x5 = 5 2x1 + 6x2 + x3 + 5x4 + x6 = 6 x1 + x2 + 5x3 + x4 + x7 = 7 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0
[
]
[ ] [ ]
A tidak ada mengandung identity matriks
Program Linier
Page 102
Untuk memperoleh identity matriks A, perhatikan hal berikut ini : 1. Geser kolom 5 ke kolom 6 (tukar tempat) 2. Masukan variabel xa1 dan xa2 masing-masing dibaris 2 dan baris ke 3
[
]
[ ]
[ ] I = identity matriks Z = 3x1+ 2x2 + x3+ 5x4 - 0x5 - 0x6 – Mxa1 - Mxa2 Karena A1, A1 , A2 , A3 , A4 , A5 , dan A6 tidak berada dalam basis, maka x1, x2 , x3 , x4, x5 , dan x6 masing-masing nilainya nol.
[
][
]
[ ]
[
]
[ ]
merupakan pemecahan awal yang fisibel.
Nilai-nilai dari Zj – Cj adalah :
Z = (0, -M, -M) [ ] = 0 - 6M - 7M = -13M
Z1 = (0, -M, -M) [ ] = 0 - 2M - M = -3M , maka Z1 – C1 = -3M - 3
Z2 = (0, -M, -M) [ ] = 0 - 6M - M = -7M, maka Z2 – C2 = -7M - 2
Z3 = (0, -M, -M) [ ] = 0 - M - 5M = -6M , maka Z3 – C3 = -6M - 1
Z4 = (0, -M, -M) [ ] = 0 - 5M - M = -6M, maka Z4 – C4 = -6M - 5
Program Linier
Page 103
Z6 = (0, -M, -M) [
] = 0 - M - 0 = M, maka Z6 – C6 = M – 0 = M
Tabel 1 CB 0 -M -M
cj VDB A5 q1 q2
H 5 6 7
Zj - Cj
-3M
2,5 A1 3 2 1 -3M – 2
2 A2 4 6 1 -7M 2
0 A3 5 1 5 -6M 1
0 A4 6 5 1 -6M 5
0 A5 0 -1 0 M
0 A6 1 0 0 0
-M q1 0 1 0 0
-M q2 0 0 1 0
Baris kedua memberikan hasil bagi minimum (q1) keluar dari basis. Jadi kunci = 6. Tabel berikutnya dibuat seperti yang sudah-sudah, akhirnya semua variabel dasar akan keluar dari basis sampai dicapai suatu pemecahan optimal. Contoh pemecahan persoalan secara lengkap akan diberikan kemudia.
2. Merubah Persoalan Minimum Menjadi Maksimum Pada dasarnya persoalan program linier yang minimum dapat dirubah menjadi persoalan program liner yang maksimum, dengan jalan merubah tanda koefisien harga pada fungsi tujuan. Sebagai ilustrasi, misalkan kita menentukan kita menentukan nilai minimum dri f = (6,5,4,3,2) → fminimum = min(6,5,4,3,2) = 2. Akan tetapi nilai –f = (-6, -5, -4, -3, -2) maka nilai (-f) maksimum = maks (-6, -5, -4, -3, -2) = -2. Jadi jelaslah kalau f yang minimum dikalikan dengan (-1) menjadi f yang maksimum. Oleh karena persoalan aslinya persoalan minimum, maka dari itu kalau nilai maksimumnya sudah diperoleh, kemudian dikalikan lagi dengan (-1). Perubahan persoalan program linier yang minimum menjadi maksimum, maksudnya agar upaya metode perhitungan yang diterapkan kepada persoalan program linier yang maksimum dapat dipergunakan untuk yang minimum. Akan tetapi jangan lupa, apabila nilai maksimum sudah diperoleh harus dikalikan lagi dengan (-1), agar diperoleh hasil yang minimum. Dengan demikian dapat disimpulkan bahwa kalau : Z
= c1x1+ c2x2 + x3 + . . . + cmxm + cm+nxm+n = CX ; C = (c1, c2 . . . , cm , . . . , cm+n) = vektor baris X = (x1, x2 . . . , xm , . . . , xm+n) = vektor kolom
Program Linier
Page 104
Min Z = - maks (-CX) = - maks (-C) x Fungsi yang harus dimaksimumkan ialah : Z* = (-CX) = c1x1 - c2x2 - . . . - cmxm - . . . - cm+nxm+n Akhirnya : Min Z = - Maks ; Z* → Zmin = - Z*maks Contoh 1: Cari x1 dan x2 s.r.s ; Z = 5x1+ 3x2 d.p ; 2x1 + x2 ≥ 3 x1 + x2 ≥ 2 x1 ≥ 0, x2 ≥ 0
; Minimum
Persoalan minimum dirubah menjadi maksimum -Z = -5x1+ 3x2 → -Z = Z* Z* = -5x1- 3x2 ; maksimum 2x1 + x2 + x3 = 3 x1 + x2 + x4 = 2 [
][ ]
[ ]
Matriks A tidak memuat identity matriks Jadi perlu ditambah 2 variabel buatan xa1 dan xa2, dengan koefisien harga masingmasing -M 2x1 + x2 + x3 + xa1 = 3 x1 + x2 + x4 + xa2 = 2
[
]
[ ] [
]
Identity matriks Z* = -5x1- 3x2 + 0x4 + Mxa1 + Mxa2 Tabel 1 cj Program Linier
-5
-3
0
0
-M
-M Page 105
CB -M -M
VDB q1 q2 Zj - Cj
H 3 2 -5M
A1 2 1 -3M + 5
A2 1 1 -2M + 3
A3 -1 0 M
-5 A1 1 0
-3 A2 1/2 1/2 -1/2M + 1/2
0 A3 -1/2 1/2 -1/2M + 5/2
-3 A2 1 1 0
0 A3 0 1 1
Tabel 2 cj CB VDB H -5 A1 3/2 -M q2 1/2 -1/2 Zj - Cj 15/2M
CB -5 -3
Tabel 3 cj VDB A1 A2 Zj - Cj
H 1 1 -8
0
-5 A1 1 0 0
A4 0 -1 M
0 A4 0 -1 M
0 A4 -2 -1 1
q1 1 0 0
q2 0 1 0
-M q1 ½ -1/2 3/2M – 5/2
-M q2 0 1 0
-M q1 ½ -1/2 M-2
-M q2 0 1 M-1
Oleh karena itu Zj - Cj ≥ 0, maka perhitungan sudah selesai. Tabel 3 memberikan pemecahan optimal, dimana Zmaks = -8, dicapai pada nilai x1 = 1, x2 =1. Dengan demikian Zmin = - Z*maks = -(-8) = 8. Contoh 2) Cari x1, x2 , x3 dan x4 s.r.s ; Z = -2x1 - x2 - 4x3 - 4x4 ; Minimum d.p ; x1 + 3x2 +2x3 +5x4 ≤ 20 2x1 + 16x2 +x3 +x4 ≥4 3x1 - x2 - 5x3 +10x4 ≤ -10 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 * Z = 2x1+ x2 + x3 + 5x4 Zmin = - Z*maks Persamaan ketiga, sebelah kanan tanda ketidaksamaan ada tanda minus, harus dikalikan -1 supaya tanda minus berubah menjadi plus. -3x1 + x2 + 5x3 -10x4
-10 → awas tanda ketidaksamaan berubah. Dengan
menambah slack variabel dan surplus variabel ketidak samaan menjadi : x1 + 3x2 +2x3 +5x4 + x4 = 20 2x1 + 16x2 +x3 +x4 – x6 = 4 3x1 - x2 - 5x3 - 10x4 -x4 = 10
Program Linier
Page 106
[
]
[
]
[ ] Matriks A tidak mempunyai identity matriks Jadi diperlukan 2 vaktor buatan q1 dan q1, serta variabel buatan xa1 + xa2 dengan koefisen harga masing-masing –M. Tabel 1 cj VDB A5 q1 q2
H 20 4 10
2 A1 1 2 -3
Zj - Cj
-14M
M-2
CB
Tabel 2 cj VDB
H
0 1 -M
A5 q2 q2 Zj - Cj
CB 0 -M -M
1 A2 3 16 1 -17M –1
4 A3 2 1 5 -6M 4
5 A4 5 1 10
2 A1
1 A2
4 A3
5 A4
19,25 0,25 9,75
0,63 0,13 -3,13
0 1 0
1,81 0,06 4,94
4,81 0,06 -10,06
-9,75M +0,25
3,13M -1,88
0
-4,94M -3,94
10,06M -4,94
9M - 5
0 A5 1 0 0 0
0 A6 0 -1 0 M
0 A7 0 0 -1 M
-M q1 0 1 0 0
-M q2 0 0 1 0
0 A5 1 0 0
0 A6 0,19 -0,6 0,06M
0 A7 0 0 -1
-M q1 -0,19 0,06 -0,06
-M q2 0 0 1
0
-0,06M -0,06
M
1,06M +0,06
0
Tabel 3 CB
cj VDB
H
2 A1
1 A2
4 A3
5 A4 8,51 0,19 -0,24
0 A5 1 0 0
0 A6 0,17 0,06 0,01
0 1 4
A5 A2 A3
15,67 0,13 1,98
1,77 0.17 -0,63
0 1 0
0 0 1
Zj - Cj
80,03
- 4,37
0
0
0 A7 0,37 0,01
-12,96
0
0,01M
0,20 0,80
-M q1 -0,17 0,06 -0,01
-M q2 -0,37 -0,01
0,20
M+0,01
M+0,80
Tabel 4 CB 0 5 4
cj VDB A5 A2 A3
H 10,00 0,67 3,33
2 A1 5,60 0,87 1,13
1 A2 -44,79 5,35 10,73
4 A3 0 0 1
5 A4 0 1 0
Zj - Cj
-16,67
6,87
68,27
0
0
0 A5 1 0 0 0
0 A6 3,00 -0,33 -0,67 -4,33
0 A7 -2,00
0,07 -0,07 -0,07
-M q1 -3,00 0,03 -0,67 M+ 43,30
-M q2 -0,37 -0,01 0,020 M– 0,07
Tabel 5 Program Linier
Page 107
CB 0 0 4
CB 0 2 4
cj VDB A6 A4 A3 Zj - Cj
H 3,33 1,78 3,33 31,33
2 A1 -1,87 0,24 -0,11 - 1,22
1 A2 -14,93 0,29 0,78 3,56
4 A3 0 0 1 0
5 A4 0 1 0 0
0 A5 0,33 0,11 0,22 1,44
0 A6 0 -1 0 0
Tabel 6 cj VDB A6 A1 A3 Zj - Cj
H 16,91 7,27 6,36 40,002
2 A1 0 1 0 0
1 A2 -12,74 1,18 0,91 5,00
4 A3 0 0 1 0
5 A4 7,64 4,09 0,46 5,00
0 A5 1,18 0,46 0,27 2,00
0 A6 1 0 0 0
0 A7
M
-M q1 -1 0 0 -
-M q2 -0,37 -0,01 0,20 -
0 A7 0,27 0,182 -0,09 0,002
-M q1 -1 0 0 -
-M q2 -0,27 -0,18 -0,09 -
-0,07
0,04 -0,01
Oleh karean semua Zj - Cj ≥ 0j, maka pemecahan optimal sudah tercapai. Dari kolom H dapat dilihat Z*maks = 40,002, x6 = 16,91 → x1 = 7,27 dan x3 = 6,36. Zmin = - Z*maks = 40,002. Zmin = -40,002 tercapai kalau x1 = 7,27 , x3 = 6,36 dan x6 = 16,91.
D. Analisis Primal Dual Setiap persoalan program linier selalu mempunyai dua macam analisis, yaitu : analisis primal dan analisis dual yang biasanya disebut analisis primal-dual. Untuk menjelaskan hubungan antara Primal dengan Dual akan ditunjukan dengan contoh kasus di bawah ini: PT. Maju Jaya adalah sebuah perusahaan yang menghasilkan dua macam produk yaitu A dan B. Setiap Produk A menghasilkan laba Rp. 40,- dan Produk B Rp. 60,-. Kedua macam produk tersebut harus diproduksi melalui dua tahap proses yaitu proses I dan proses II. Kapasitas dan waktu proses bagi kedua macam produk tersebut adalah sebagai berikut : Proses I II
Waktu Proses A B 3 2 1 2
Kapasitas per bulan (jam) 2.000 1.000
Model matematika Kasus diatas adalah : Fungsi Tujuan : Memaksimumkan : Z = 40A + 60B, Fungsi Kendala : 1.
3A +2B ≤ 2000
Program Linier
Page 108
A + 2B ≤ 1000,
2.
A,B ≥ 0,
3.
Model matematika diatas disebut model Primal. Dual pada dasarnya adalah masalah penentuan harga, yaitu : Harga dari sumber-sumber yang dipergunakan untuk berproduksi secara optimal, dimana harga tersebut merupakan nilai minimum sehingga dapat dipergunakan sebagai bahan pertimbangan untuk menambah atau mengurangi sumber-sumber tersebut secara tepat. Misalkan C dan D sebagai biaya sewa per jam yang harus dibebankan kepada proses I dan II. Karena jumlah kapasitas yang tersedia untuk proses I adalah 2000 jam dan proses II 1000 jam, maka biaya sewa total
Untuk kedua macam proses tersebut adalah : F = 2000C + 1000D. Selagi F merupakan jumlah biaya sewa kedua macam proses tersebut maka manajeman PT. Maju Jaya tersebut berusaha untuk meminimumkannya. Pandang jika model Primal sebagai pihak penjual yang ingin memaksimumkan laba, di sisi lain model Dual sebagai pihak pembeli yang menginginkan harga pembelian yang minimum. Setiap unit produk A memerlukan waktu 3 jam pada proses I dan 1 jam pada prose II, sehingga biaya untuk menghasilkan setiap unit produk A adalah 3C + 1D. Dipandang dari pihak pembeli tentu saja harga tesebut tidak boleh lebih rendah dari sumbangan laba yang akan diberikan oleh produk A terhadap penjualan yaitu sebesar Rp. 40,- (bila penjual mendapat laba Rp. 40,- untuk setiap penjualan produk A, maka tentu saja pembeli menginginkan agar harga yang ia bayar untuk biaya pemrosesan produk tersebut paling sedikit harus sama dengan laba yang diperoleh penjual yaitu sebesar Rp. 40,-). Sehingga biaya untuk memroses setiap unit produk A adalah 3C + 1D ≥ 40. Dengan cara yang sama biaya untuk memroses setiap unit produk B adalah 2C +2D ≥ 60 dan selanjutnya karena harga tidak mungkin negatif maka C ≥ 0 dan D ≥0. 1. Asumsi Dasar : Untuk dapat menyusun suatu persoalan primal Program Linier ke dalam bentuk dual, maka selalu harus dirumuskan terlebih dahulu ke dalam bentuk kanonik. Untuk persoalan maksimasi, maka semua rumusan fungsi kendala mempunyai tanda lebih kecil dari pada Program Linier
Page 109
atau sama dengan ( ≤ ). Untuk persoalan minimasi maka tanda fungsi syarat ikatannya harus lebih besar dari pada atau sama dengan ( ≥ ) . ( Ingat bahwa tidak perlu semua konstanta atau nilai sebelah kanan (nsk) fungsi kendala yang bersangkutan harus selalu non-negatif dalam suatu rumusan yang berbentuk kanonik). Jika suatu persoalan dalam rumusan Program Linier mempunyai fungsi kendala kesamaan (nilai nsk-nya bertanda sama dengan), maka fungsi kendalanya tersebut dapat ditukar atau diganti dengan dua fungsi lainnya, yang pertama, bertanda “lebih kecil dari pada atau sama dengan ( ≤ )” dan yang kedua, bertanda “lebih besar dari-pada atau sama dengan ( ≥ )”. Salah satu diantara kedua fungsi kendala lain tersebut (dipilih salah satu), kemudian diambil, dan kalikan dengan (−1) untuk mendapatkan fungsi kendala yang sesuai dengan aturan yang diminta oleh bentuk kanonik tersebut.
2. Model Umum Persoalan Primal - Dual Bentuk Primal: n Maksimumkan : Z = C j X j j=1 n syarat ikatan : a ij X j ≤ b i untuk i= 1, 2, 3, ...,m. j=1 dan Xj ≥ 0, j = 1, 2, ... , n Kalau akan dinyatakan menjadi Bentuk Dual : m Minimumkan : F = b i Yi i=1 syarat ikatan :
m a ij Yi ≥ C j untuk j= 1, 2, 3, ...,n. i=1
dan Yi ≥ 0, i = 1, 2, ... , m m
n opt
j j
dimana : Z
Program Linier
= C X * adalah sama dengan F j=1
op t
i =
i
b Y* i= 1 Page 110
Aturan umum dalam perumusan persoalan Program Linier menyangkut Bentuk Primal dan Dual adalah : Bentuk Primal
Bentuk Dual
Memaksimumkan fungsi tujuan
Meminimumkan fungsi tujuan, dan sebaliknya.
Koefisien fungsi tujuan (Cj )
Nilai Sebelah Kanan (NSK) fungsi kendala
NSK fungsi kendala primal-primal (bi )
Koefisien fungsi tujuan
Koefisien peubah ke-j
Koefisien kendala ke-j
Koefisien kendala ke-i
Koefisien peubah ke-i
Peubah ke-j yang positif (≥ 0)
Kendala ke-j dengan tanda ketidaksamaan “lebih besar daripada atau sama dengan “ (≥).
Peubah ke-j tandanya tidak dibatasi
Kendala ke-j yang bertanda sama dengan
Kendala ke-i yang bertanda sama dengan
Peubah ke-i tandanya tidak dibatasi
Kendala ke-i yang bertanda ketidaksamaan (≤)
Peubah ke-i yang positif (≥)
Cntoh Soal : Andaikan terdapat suatu persoalan Program Linier sebagai berikut : Memaksimumkan : Z = 10X1 + 6X2
........ (1),
Syarat ikatan : a). 2X1 + 3X2 ≤ 90 .......... (2) b). 4X1 + 2X2 ≤ 80 .......... (3) X2 ≥ 15 ..........
(4)
d). 5X1 + X2 = 25 ..........
(5)
c).
dan X1 , X2 ≥ 0 Ubahlah ke dalam Bentuk Dualnya ! Penyelesaian : Langkah 1, Transfomasikan ke dalam bentuk kanonik primal ( karena fungsi tujuannya memaksimumkan maka tanda ketidaksamaannya dibuat ≤ ). Manipulasi dilakukan pada rumus (4) dan (5) dengan berikut :
Program Linier
Page 111
*) Kalikan rumus (4) dengan (−1) didapatkan : − X2 ≤ −15 *) Ganti rumus (5) menjadi ketidaksamaan : 5X1 + X2 ≤ 25 (5a) dan 5X1 + X2 ≥ 25 (5b) dan rumus (5b) dikalikan dengan (-1) didapat : − 5X1 − X2 ≤ −25 Dengan demikian diperoleh bentuk kanonik primal menjadi : Memaksimumkan : Z = 10X1 + 6X2 Syarat ikatan : a). 2X1 + 3X2 ≤ 90 b). 4X1 + 2X2 ≤ 80 c). − X2 ≤ −15 d). 5X1 + X2 ≤ 25 e). − 5X1 − X2 ≤ −25 dan X1 , X2 ≥ 0
Langkah 2, Rumuskan bentuk kanonik dari persoalan primal tersebut ke dalam bentuk dual, dan diperoleh : Meminimumkan : F = 90Y1 + 80Y2 − 15Y3 + 25Y4 − 25Y5 syarat ikatan : a). 2Y1 + 4Y2 − 0Y3 + 5Y4 − 5Y5 ≥ 10 b). 3Y1 + 2Y2 − Y3 + Y4 − Y5 ≥ 6 dan Y1 , Y2 , Y3 , Y4 , Y5 ≥ 0 atau Yi ≥ 0, untuk i = 1, 2, …, 5. 3. Masalah Peubah (Variabel) yang tidak Dibatasi Jika sebuah peubah Xj tidak dibatasi sebagai perubah non-negatif, maka dapat diganti dengan dua buah perubah yang baru yaitu Xj+ dan X-j sehingga : Xj = Xj+ − X-j dimana Xj+ ≥ 0 dan X-j ≥ 0. Variabel Xj merupakan beda atau sisa dari dua perubah non-negatif Xj+ dan X-j . Dengan kata lain Xj merupakan nilai tengah, sedangkan Xj+ dan X-j adalah perubah deviasi atau simpanan terhadap perubah nilai tengah atau perubah target. Program Linier
Page 112
Contoh : Andaikan suatu persoalan Program Linier dengan X2 tidak dibatasi syarat non negatif sebagai berikut : Maksimumkan Z = 2X1 + 5X2
(1)
Syarat Ikatan : 3X1 + 2X2 ≤ 6 (2) 2X1 + 9X2 ≤ 8 (3) dan X1 ≥ 0, X2 tidak dibatasi syarat non-negatif. Penyelesaian : Perumusan model Program Linier di atas tidak baik karena tidak memenuhi peraturan Program Linier yang ada, yaitu semua perubah Xj yang menjadi perubah keputusan tidak boleh negatif. Oleh karena itu X2 disempurnakan menjadi : X2 = X2+ − X2- dimana X2+ ≥ 0 dan X2- ≥ 0, maka persoalan diatas menjadi : Memaksimumkan Z = 2X1 + 5(X2+ − X2- ) Syarat ikatan : 3X1 + 2X2+ − 2X2- ≤ 6 2X1 + 9X2+ − 9X2- ≤ 8 dan X1 ≥ 0, X2+ ≥ 0, X2- ≥ 0.
4. Penyelesaian Permasalahan Program Linier lewat Dualnya Contoh soal : Tentukan X1 , X2 , X3 , ≥ 0 yang meminimumkan F = 30X1 + 60X2 + 72X3 dan memenuhi kendala-kendala : a). 2X1 + 2X2 + 4X3 ≥ 3 b). X1 + 3X2 + 3X3 ≥ 3, Lewat dualnya ! Program Linier
Page 113
Penyelesaian : Bentuk dual dari Permasalahan Program Linier diatas adalah : Tentukan Y1 ≥ 0, Y2 ≥ 0 yang memaksimumkan Z = 3Y1 + 3Y2 yang memenuhi kendala-kendala : a). 2Y1 + Y2 ≤ 30 b). 2Y1 + 3Y2 ≤ 60 c). 4Y1 + 3Y2 ≤ 72 Dengan metode grafik diperoleh penyelesaian sebagai berikut.
Program Linier
Page 114
Daerah yang Memenuhi Kendala (DMK) adalah daerah OABCD yang mempunyai titik sudut-titik sudut sebagai berikut : Titik O (0,0) → Z = 3.0 + 3.0 = 0, Titik A (15,0) → Z = 3.15 + 3.0 = 45, Titik B(9,12) → Z = 3.9 + 3.12 = 63, Titik C(6,16) → Z = 3.6 + 3.16 = 66, Titik D(0,20) → Z = 3.0 + 3.20 = 60,
Jadi Z max = 66, untuk titik C(6,16) masuk dalam syarat, Untuk Y1 = 6 (jadi Y1 > 0) dan Y2 = 16 (jadi Y2 > 0), dari Fungsi Kendala Bentuk Dual diperoleh :
Program Linier
Page 115
a). 2.6 + 16 = 28 < 30 (tanda dari kendala dual “<”). b). 2.6 + 3.16 = 60 = 60 (tanda dari kendala dual adalah “=”) c). 4.6 + 3.16 = 72 = 72 (tanda dari kendala dual adalah “=”) Variabel Dual Y1 > 0 Y2 > 0
X1 = 0 2 1 <30
Variabel Primal X2 > 0 2 3 =60
X3 > 0 4 3 =72
=3 =3
Karena pada Kendala (1) masalah dual bertanda ketidaksamaan (“<”) (< 30) maka variabel pertama masalah primal bertanda “=“ yaitu X1 = 0, dan tanda kendala 2 (= 60) dan kendala 3(= 72) masalah dual bertanda “=” maka variabel kedua dan ketiga masalah primal (X2 dan X3 yang positif). Karena variabel-variabel masalah dual (Y1 = 6, dan Y2 = 16) yang positif maka tanda kendala masalah primal adalah “=” (= 3)., sehingga diperleh persamaan berikut: 2X1 + 2X2 + 4X3 = 3 → 2.0 + 2X2 + 4X3 = 3 → 2X2 + 4X3 =3 a) X1 + 3X2 + 3X3 = 3 → 1.0 + 3X2 + 3X3 = 3 → 3X2 + 3X3 = 3 (b) dari rumus (a) dan (b) diperoleh : 6X2 + 12X3 = 9 6X2 + 6X3 = 6
_ 6X3 = 3 → X3 = 1/2
untuk X3 = 1/2 maka dari persamaan (a) diperoleh 2X2 + 4(1/2) = 3 → X2= ½. Jadi penyelesaian dari Permasalahan Program Linier diatas adalah : X1 = 0, X2 = 1/2, X3 = 1/2. Sehingga Fmin = 30(0) + 60 (1/2) + 72 (1/2) = 66.
Program Linier
Page 116
Uji Kompetensi 1. Tentukan X1 ≥ 0, X2 ≥ 0 yang meminimumkan Z = 6 X1 + 8 X2 yang memenuhi kendala-kendala : a. 3X1 + 3X2 ≥ 4 b. 5X1 + 2X2 ≤ 10 c. X1 + 2X2 = 3 Selesaikan persoalan diatas lewat dualnya ! 2. Tentukanlah X1, X2 ≥ 0 yang memaksmumkan Z = 3 X1 + 5 X2 dan memenuhi kendala : a.
2 X1 ≤ 8
b. 3 X2 ≤ 15
c. 6 X1 + 5 X2 ≤ 30
Lewat dualnya ! 3. Ubahlah ke dalam Bentuk Dualnya persoalan Program Linier berikut ini: a.
Memaksimumkan Z = 23X1 + 32X2 Fungsi Kendala : 10X1 + 6X2 ≤ 2500 8X1 + 10X2 ≤ 2000 X1 + 2X2 ≤ 500 dan X1 , X2 ≥ 0
b. Meminimumkan Z = 20000X1 + 22000X2 + 18000X3 Fungsi Kendala: 4X1 + 6X2 + X3 ≥ 54 4X1 + 4X2 + 6X3 ≥ 65 ≥ 7
X1
≥ 7
X2 X3
≥ 7 dan X1 , X2 , X3 ≥ 0
c. Memaksimumkan Z = 2X1 − 7X2 Fungsi Kendala : −2X1 + 3X2 = 3 4X1 + 5X2 ≥ 10 6X1 + 5X2 ≤ 3 4X1 + 8X2 ≥ 5 dan X1 , X2 ≥ 0 d. Meminimumkan Z = 4X1 + 6X2 Program Linier
Page 117
Fungsi Kendala : −2X1 + 3X2 = 3 4X1 + 5X2 ≥ 10 6X1 + 5X2 ≤ 3 4X1 + 8X2 ≥ 5 dan X1 , X2 ≥ 0 4. Tentukan nilai optimum dari fungsi tujuan-fungsi tujuan berikut : 1) Z = 3x1 + 2x1 ; maksimum d.p :
2x1 + x2 ≤ 5 x1 + x2 ≤ 3 x1 ≥ 0, x2 ≥ 0
2) Z = 3x1 + 7x2 + 6x3 ; maksimum d.p :
2x1 + 2x2 + 2x3 ≤ 8 x1 + x2 ≤ 3 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
3) Z = 28x1 + 400x2 + 20x3 ; minimum d.p :
x1 + 9x2 + 0,83x3 ≥ 8 0,6x1 + 2x2 + 0,7x3 ≥ 3 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
4) Z = x1 + 1,5x2 ; maximum d.p :
2x1 + 3x2 ≤ 6 x1 + x2 ≤ 4 x1 ≥ 0, x2 ≥ 0
5) Z = 6x1 + 4x2 ; minimum d.p :
2x1 + x2 ≥ 1 3x1 + 4x2 ≥ 1,5 x1 ≥ 0, x2 ≥ 0
6) Z = 1,5x1 + 2,5x2 ; minimum d.p :
x1 + 3x2 ≥ 3 x1 + x2 ≥ 2 x1 ≥ 0, x2 ≥ 0
7) Z = x1 + 0,75x2 ; maximum Program Linier
Page 118
d.p :
x1 + 3x2 ≥ 0 -0,5x1 + x2 ≤ 1 x1 ≥ 0, x2 ≥ 0
a. selesaikan persoalan di atas dengan metode grafik b. Rumuskan persoalan rangkap (dual problem) berdasarkan persoalan utama tersebut, kemudian selesaikan dengan metode simpleks dua fase
8) Z = 3x1 + 4x2 + x3+ 3x4 ; maximum d.p :
8x1 + 3x2 + 4x3 + x4 ≤ 7 2x1 + 6x2 + x3 + 5x4 ≤ 8 x1 + 4x2 + 5x3 + 2x4 ≤ 8 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0
c. selesaikan persoalan di atas dengan metode grafik d. Rumuskan persoalan rangkap (dual problem) berdasarkan persoalan utama tersebut, kemudian selesaikan dengan metode simpleks dua fase
9) Z = 2x1 - 3x2 + 4x3+ x4 ; maximum d.p :
x1 + 5x2 + 9x3 - 6x4 ≥ -2 3x1 - x2 + x3 + 3x4 ≤ 10 -2x1 - 3x2 + 7x3 - 8x4 ≥ 0 x1, x2, x3, dan x4 ≥ 0
e. selesaikan persoalan di atas dengan metode grafik f. Rumuskan persoalan rangkap (dual problem) berdasarkan persoalan utama tersebut, kemudian selesaikan dengan metode simpleks dua fase
10) Z = 3x1 + 4x2 + x3+ 6x4 ; minimum d.p :
5x1 - 2x2 + x3 - x4 ≥ 2 6x1 + x2 - 5x3 - 3x4 ≥ 5 -x1 + 4x2 + 3x3 + 7x4 ≥ 16 x1, x2, x3, dan x4 ≥ 0
g. selesaikan persoalan di atas dengan metode grafik Program Linier
Page 119
h. Rumuskan persoalan rangkap (dual problem) berdasarkan persoalan utama tersebut, kemudian selesaikan dengan metode simpleks dua fase
11) Z = 60x1 + 24x2 + 84x3 ; minimum d.p :
5x1 + 3x2 + 12x3 ≥ 20 15x1 + 4x2 + 7x3 ≥ 15 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
i. selesaikan persoalan di atas dengan metode grafik j. Rumuskan persoalan rangkap (dual problem) berdasarkan persoalan utama tersebut, kemudian selesaikan dengan metode simpleks dua fase
Program Linier
Page 120
DAFTAR PUSTAKA
Howard Anton, (Pantur Silaban), 1984, Aljabar Linier Elementer. Jakarta: Erlangga Marten Tapilouw, 1986, Program Linier, Jakarta: Dekdikbud UT Marwan, 1979, Mengenal Linier Programing dan Komputer, Yogyakarta: FE Universitas Gadjah Mada Negoro dan B. Harahap, 1998, Ensiklopedia Matematika, Jakarta: Ghalia Indonesia Reseffendi, 2004, Matematika Modern, Bandung: Jurusan Matematika UPI Yuli, 2003, Diktat Program Linier, Yogyakarta: IAIN Sunan Kalijaga Yogyakarta
Program Linier
Page 121
