program linier - · pdf filevariabel (peubah) x dan y adalah satu. kompetensi dasar 1....

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

ii

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

iii

DAFTAR ISI

KATA PENGANTAR .................................................................................... i

DAFTAR ISI .................................................................................................. ii

BAB I SISTEM PERSAMAAN LINIER

A. Pendahuluan ................................................................................ 1

B. Sistem Persamaan ....................................................................... 1

C. Sistem Pertidaksamaan Linier .................................................... 13

D. Rangkuman ................................................................................. 17

E. Uji Kompetensi ........................................................................... 17

BAB II PERSOALAN OPTIMASI

A. Pendahuluan ................................................................................ 20

B. Permasalahan Optimasi ............................................................... 21

C. Model Matematika Masalah Program Linier .............................. 24

D. Rangkuman ................................................................................. 27

E. Uji Kompetensi ........................................................................... 27

BAB III 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....................................................................................... 79

Program Linier 4

BAB I

SISTEM PERSAMAAN LINIER

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.

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. menyelesaikan permasalahan sistem persamaan linier

1.2. menganalisis sistem persamaan linier dalam soal cerita

1.3. menciptakan masalah persamaam linier dari kehidupan sehari hari

2.1. mengidentifikasi permasalahan sistem persamaan linir

2.2. merubah sistem persamaan linier ke dalam bentuk mat

2.3. memberikan contoh persamaan linier yang dapat diubah dalam bentuk matrik

Program Linier 5

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 x1, 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 6

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 , x2) yang

memperoleh pemecahan sistem persamaan diatas 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 7

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 8

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 9

[

]

[

]

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 10

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 11

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 12

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 13

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

[

] maka transposisi dari matriks

Kofaktor A adalah : [

]

Nilai k11= (-1)i+j

Mij ;

Mij adalah minor dari aij

Dari matriks A diatas maka Minor Elemen (entri) adalah :

[

]

[

]

Program Linier 14

[

]

[

]

[

]

[

]

[

]

[

]

[

]

Maka :

; ;

; ;

; ;

Sehingga ,

[

]

[

]

Jadi :

[

] [

]

Dengan demikan,

Program Linier 15

[

] [

] [

]

[

]

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.

⟨

|

⟩ baris 1 kurangi 3 kali baris 3

⟨

|

⟩

Jadi : [

]

Sehingga,

[

] [

]

Program Linier 16

[

] [

]

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 17

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 + a13x3 ≤, = ≥ b1 a21x1 + a22x2 + a23x3 ≥,≥,≤ b2 a31x1 + a32x2 + a33x3 ≥,≤,≤ b3

dan lainnya pada rumusan 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 18

Tunjukan pemecahan dari ketiga bentuk diatas :

y y

2 → 2 → 2

→

0 3 x+

0 3 x+

0

3 x+

Gambar i) Gambar ii) 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 19

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

B (0,4,0) → 4x1 + 3x2 + 2x3 = 12

C (0,0,6)

A 0 B x2

x3

ii) x3

A 0 B x2

x1

4x1 + 3x2 + 2x3 ≤12

Program Linier 20

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

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.

Uji Kompetensi

Program Linier 21

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 22

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 Page 66

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

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

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.


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

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


Suatu persoalan dikatakan persoalan program linier, bila memenuhi ketentuan-

ketentuan 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). Pembatasan-

pembatasan 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


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 + . . . . + a2nxn ≥ h2


.

.

.

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.700m

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


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.

Papan : untuk tiap x1 unit A diperlukan 3x1 m2

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


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


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

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

Macam roti Bahan A Bahan B Bahan C

I

II

2

10

2

4

4

2

Uji Kompetensi


Harga roti I sebesar Rp. 350,- dan harga roti kedua Rp. 800,-

Rumuskan fungsi tujuan dan pembatas !

BAB III

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.

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


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.


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


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 :


(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

Basis

Variabel Basis Keterangan Z = 4x1 + 5x2

x1= 0 ; x2 = 0

x1= 0 ; x3 = 0

x1= 0 ; x4 = 0

x2= 0 ; x3 = 0

x2= 0 ; x4 = 0

x3= 0 ; x4 = 0

x3= 12 ; x4 = 12

x2= 6 ; x4 = -6

x2= 4,5 ; x3 = 3

x1= 4 ; x4 = 6

x1= 6 ; x4 = -6

x1= 2 ; x2 = 3

Fisibel → (Z1)

Tidak Fisibel

Fisibel → (Z2)

Fisibel → (Z3)

Tidak Fisibel

Fisibel → (Z4)

0

-

22,5

16

-

23

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


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

Z = 4x1 + 5x2 ; Maksimum

d.p 3x1 + 2x2 ≤ 12

3x1 + 4x2 ≤ 18

x1 ≥ 0, x2 ≥ 0

x2


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 3x1 + 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.


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


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

Basis Variabel Basis Keterangan Z = 4x1 + 5x2

x1= 0 ; x2 = 0

x1= 0 ; x3 = 0

x1= 0 ; x4 = 0

x2= 0 ; x3 = 0

x2= 0 ; x4 = 0

x3= 0 ; x4 = 0

x3= -3; x4 = -2

x2= 3 ; x4 = 1

x2= 2 ; x3 = -1

x1= 3/2 ; x4 = -1/2

x1= 2 ; x4 = 1

x1= 1 ; x2 = 1

Tidak Fisibel

Fisibel → (Z1)

Tidak Fisibel

Tidak Fisibel

Fisibel → (Z2)

Fisibel → (Z3)

-

9

-

-

10

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 :


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 :


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


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 :


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

Basis Variabel Basis Keterngan Z = x1 + 3x2 + 3x3

1 2 3 4

x1 = 0, x2 = 0, x3 = 0

x1 = 0, x2 = 0, x4 = 0

x1 = 0, x2 = 0, x5 = 0

x1 = 0, x2 = 0, x6 = 0

x4 = 14, x5 = 10, x6 = 16

x3 = 14/3, x5 = 23/3,

x6 = 16

x3=20, x4 =-46, x6 = -64

x3 =13/2, x4 = -11,

Fisibel → (Z1)

Fisibel → (Z2)

Tidak Fisibel

Tidak Fisibel

0

14

-

-


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

Tidak Fisibel

Fisibel → (Z4)

Fisibel → (Z5)

Fisibel → (Z6)

Tidak Fisibel

Tidak Fisibel

Tidak Fisibel

Tidak Fisibel

Tidak Fisibel

Fisibel → (Z7)

Tidak Fisibel

Tidak Fisibel

Fisibel → (Z8)

-

15

-

-

120/7

174/11

11

-

-

-

-

-

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


x3 (0,0,20)

(0,0,6 1/2)

(0,0,14/3)

(0,22/7,18/7) (0,23/5,8/5)

(0,54/11,14/11)


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


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

Basis Variabel Basis Keterngan Z = x1 + 3x2 + 3x3

1 2 3 4

x1 = 0, x2 = 0, x3 = 0

x1 = 0, x2 = 0, x4 = 0

x4 = -2, x5 = -4, x6 = -3

x3 = 2, x5 = 2, x6 = 1

Tidak Fisibel

Fisibel → (Z1)

-

160

x2

x1 (26,0,0)

(18,0,2) (0,7,0)

(6,4,0)

(0,3,0)

(17/14,15/144,3/4)


x1 = 0, x2 = 0, x5 = 0

x1 = 0, x2 = 0, x6 = 0

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

x3=4/3, x4 = -2/3,

x6 = -1/3

x3 =3/2, x4 = -1/2,

x5 = 1/2

x2=1, x5 =-3, x6 = -1

x2=4, x4 =6, x6 = 5

x2=3/2, x4 = -5/2,

x5 = 1

x2=2/5, x3 =6/5,

x6 = 1/5

x2=1/2, x3 =1, x5 = 1

x2=1/4, x3 = 5/4,

x4 = -1/4

x1=2/3, x5 =-4/3,

x6 = -5/3

x1=1, x4 =1, x6 = -6

x1=3/2, x4 =-5/2, x5 = 0

x1=-2/5, x3 =4/5,

x5 = -3/5

x1=1/4, x3 =5/4,

x5 = 7/4

x1=-1/2, x3 =2,

x4 =-3/2

x1=6/5, x2 =-2/5,

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

Fisibel → (Z3)

Fisibel → (Z4)

Tidak Fisibel

Tidak Fisibel

Tidak Fisibel

Fisibel → (Z5)

Tidak Fisibel

Fisibel → (Z6)

Tidak Fisibel

Tidak Fisibel

Tidak Fisibel

Fisibel → (Z7)

Fisibel → (Z8)

-

-

-

-

160

-

112

100

-

-

-

90

-

115

-

-

-

230/3

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



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

x3

x3

x3

C (0.0,2)

B (0.4,0)

A (3/2.0,2)

(0.0,3/2)

(0.0,4/3)

(1/4.0,5/4)

(1.0,0)

(5/6.2/3,0)

(0.1/2,1)

(0.1/4,5/4)


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.

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

Uji Kompetensi


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

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


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

minimum dual ( dengan grafik atau metode simpleks ).


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.






B. Metode Simplex sebagai Prosedur Perhitungan






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


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 a12 . . . a1m 1 0 . . . 0 x1 h1


a21 a22 . . . a2m1 0 . . . 0 x2 h2

. . = .

. . .

. . .

an1 an2 . . . anm 0 0 . . . 1 xm+n hn

↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑

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

CB

Vektor

dalam

basis

H A1 A2 ... Am Am+1 Am+2 ... Am+n

cAm+1

cAm+2

.

.

.

cAm+n

Am+1

Am+2

.

.

.

Am+n

h1

h2

.

.

.

Hn

a11

a21

.

.

.

an1

a12

a22

.

.

.

an2

...

...

.

.

.

a1m

a2m

.

.

.

anm

1

0

.

.

.

0

0

1

.

.

.

0

...

...

.

.

.

0

0

.

.

.

1

zj - cj

z

Z1 – C1

Z2 – C2 ...

Zm – Cm

ZAm + 1 -

CAm + 1

ZAm + 2 -

CAm + 2

...

ZAm + n -

CAm + n

Kolom pertama dari pada tabel memberikan CB yaitu prices dari vektor-vektor

dalam basis.

Kolom kedua memberikan vektor-vektor yang ada dalam basis (sebanyak m).


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

vektor 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 5 3 0 0

CB VDB H A1 A2 A3 A4

0

0

A3

A4

15

10

3

5

5

2

1

0

0

1

Zj - Cj 0 -5 -3 0 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.


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 5 3 0 0


0

5

A3

A1

9

2

0

1

19/5

2/5

1

0

-3/5

1/5

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


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 5 3 0 0


3

5

A2

A1

45/19

24/19

0

1

1

0

5/19

-2/19

-1/7

5/19

Zj - Cj 85/7 0 0 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 ; Maksimum

d.p ; 0,5x1 + x2 ≤ 4

2x1+ x2 ≤ 8

4x1+ 2x2 ≤ 2

x1 ≥ 0, x2 ≤ 0


s.r.s ; Z = 4x1+6x2 +0x3+0x4 ; Maksimum

d.p ; 0,5x1 + x2 +x3 = 4

2x1+ x2 + x4 = 8

4x1+ 2x2 + x5 = 2

x1 ≥ 0, x2 ≤ 0, x3 ≥ 0, x4 ≤ 0, x5 ≤ 0


Persamaan matriksnya :

[

]

[

]

[ ]

Tabel 1

cj 5 3 0 0 0

CB VDB H A1 A2 A3 A4 A5

0

0

0

A3

A4

A4

15

10

2

½

2

4

1

1

-2

1

0

0

0

1

0

0

0

1

Zj - Cj 0 -4 -6 0 0 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 5 3 0 0 0


0

0

0

A2

A4

A5

4

5

10

½

3/2

5

1

0

0

1

-1

0

0

1

0

0

0

1

Zj - Cj 0 -1 -1 0 0 0

Tabel 3

cj 5 3 0 0 0


0

0

0

A2

A4

A1

3

1

2

0

0

1

1

0

0

0,8

-1,6

0,4

0

1

0

0,1

-0,3

0,2

Zj - Cj 0 -1 -1 6,4 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.


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 ; Maksimum

d.p ; x1 + 2x2 ≤ 8000

3x1+ 2x2 ≤ 9000

x1 ≥ 0, x2 ≤ 0


s.r.s ; Z = 4x1+6x2 +0x3+0x4 ; Maksimum

d.p ; x1 + 2x2 +x3 = 8000

3x1+ 2x2 + x4 = 9000

x1 ≥ 0, x2 ≤ 0, x3 ≥ 0, x4 ≤ 0

Tabel 1

cj 2,5 2 0 0


0

0

A3

A4

8000

9000

1

3

2

2

1

0

0

1

Zj - Cj 0 -2,5 -2 0 0


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 2,5 2 0 0


0

5/2

A3

A1

5000

3000

0

1

4/3

2/3

1

0

-1/3

1/3

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


[

] (

)

[

] [

] [

] [

] [

]

[

] [

] [

] [

] [ ]

[

] [

] [

]

[

]

[ ]

[

] [

] [ ] [

] [

]

[

] [

] [

]

[

] [

]

Berdasarkan hasil perhitungan diatas kemudian dapat dibentuk tabel 3 sebagai

berikut :

Tabel 2

cj 2,5 2 0 0


0

5/2

A2

A1

3750

500

0

1

1

0

3/4

-1/2

-1/4

½

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.


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


s.r.s ; Z = 7x1+ 5x2 ; Maksimum

d.p ; 3x1 + 2x2 ≤ 4

x1+ x2 = 3

x1 ≥ 0, x2 ≥ 0

3x1 + 2x2 + x3 = 4

x1+ x2 = 3

[

] [

] [ ]

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


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


Z6 = (0, -M, -M) [

] = 0 - M - 0 = M, maka Z6 – C6 = M – 0 = M

Tabel 1

cj 2,5 2 0 0 0 0 -M -M

CB VDB H A1 A2 A3 A4 A5 A6 q1 q2

0

-M

-M

A5

q1

q2

5

6

7

3

2

1

4

6

1

5

1

5

6

5

1

0

-1

0

1

0

0

0

1

0

0

0

1

Zj - Cj -3M -3M –

2

-7M -

2

-6M -

1

-6M -

5

M 0 0 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


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 ; Minimum

d.p ; 2x1 + x2 ≥ 3

x1 + x2 ≥ 2

x1 ≥ 0, x2 ≥ 0

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

masing -M

2x1 + x2 + x3 + xa1 = 3

x1 + x2 + x4 + xa2 = 2

[

]

[

]

[ ]

Identity matriks

Z* = -5x1- 3x2 + 0x4 + Mxa1 + Mxa2

Tabel 1

cj -5 -3 0 0 -M -M


CB VDB H A1 A2 A3 A4 q1 q2

-M

-M

q1

q2

3

2

2

1

1

1

-1

0

0

-1

1

0

0

1

Zj - Cj -5M -3M + 5 -2M + 3 M M 0 0

Tabel 2

cj -5 -3 0 0 -M -M


-5

-M

A1

q2

3/2

1/2

1

0

1/2

1/2

-1/2

1/2

0

-1

½

-1/2

0

1

Zj - Cj -1/2 -

15/2M 0

-1/2M +

1/2

-1/2M +

5/2 M

3/2M –

5/2

0

Tabel 3

cj -5 -3 0 0 -M -M


-5

-3

A1

A2

1

1

1

0

1

1

0

1

-2

-1

½

-1/2

0

1

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


[

]

[

]

[

]

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 2 1 4 5 0 0 0 -M -M

CB VDB H A1 A2 A3 A4 A5 A6 A7 q1 q2

0

-M

-M

A5

q1

q2

20

4

10

1

2

-3

3

16

1

2

1

5

5

1

10

1

0

0

0

-1

0

0

0

-1

0

1

0

0

0

1

Zj - Cj -14M M - 2 -17M

– 1

-6M -

4 9M - 5

0 M M 0 0

Tabel 2

cj 2 1 4 5 0 0 0 -M -M


0

1

-M

A5

q2

q2

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

1

0

0

0,19

-0,6

-

0,06M

0

0

-1

-0,19

0,06

-0,06

0

0

1

Zj - Cj -9,75M

+0,25

3,13M

-1,88 0

-4,94M

-3,94 10,06M

-4,94

0 -0,06M

-0,06 M 1,06M

+0,06

0

Tabel 3

cj 2 1 4 5 0 0 0 -M -M


0

1

4

A5

A2

A3

15,67

0,13

1,98

1,77

0.17

-0,63

0

1

0

0

0

1

8,51

0,19

-0,24

1

0

0

0,17

-

0,06

0,01

0,37

0,01 -

0,20

-0,17

0,06

-0,01

-0,37

-0,01

0,20

Zj - Cj 80,03 - 4,37 0 0 -12,96 0 -

0,01M -

0,80 M+0,01 M+0,80

Tabel 4

cj 2 1 4 5 0 0 0 -M -M


0

5

4

A5

A2

A3

10,00

0,67

3,33

5,60

0,87

1,13

-44,79

5,35

10,73

0

0

1

0

1

0

1

0

0

3,00

-0,33

-0,67

-2,00

0,07 -0,07

-3,00

0,03

-0,67

-0,37

-0,01

0,020

Zj - Cj -16,67 6,87 68,27 0 0 0 -4,33 -0,07 M +

43,30

M –

0,07

Tabel 5


cj 2 1 4 5 0 0 0 -M -M


0

0

4

A6

A4

A3

3,33

1,78

3,33

-1,87

0,24

-0,11

-14,93

0,29

0,78

0

0

1

0

1

0

0,33

0,11

0,22

0

-1

0

-0,07

0,04 -0,01

-1

0

0

-0,37

-0,01

0,20

Zj - Cj 31,33 - 1,22 3,56 0 0 1,44 0 M - -

Tabel 6

cj 2 1 4 5 0 0 0 -M -M


0

2

4

A6

A1

A3

16,91

7,27

6,36

0

1

0

-12,74

1,18

0,91

0

0

1

7,64

4,09

0,46

1,18

0,46

0,27

1

0

0

0,27

0,182

-0,09

-1

0

0

-0,27

-0,18

-0,09

Zj - Cj 40,002 0 5,00 0 5,00 2,00 0 0,002 - -

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

Waktu Proses Kapasitas per bulan

(jam) A B

I 3 2 2.000

II 1 2 1.000

Model matematika Kasus diatas adalah :

Fungsi Tujuan : Memaksimumkan : Z = 40A + 60B,

Fungsi Kendala :

1. 3A +2B ≤ 2000


2. A + 2B ≤ 1000,

3. A,B ≥ 0,

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


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

j=1

dan Xj ≥ 0, j = 1, 2, ... , n

untuk i= 1, 2, 3, ...,m.

Kalau akan dinyatakan menjadi Bentuk Dual :

m Minimumkan : F = b i Yi

i=1

m syarat ikatan : a ij Yi ≥ C j untuk j= 1, 2, 3, ...,n.

i=1

dan Yi ≥ 0, i = 1, 2, ... , m

n

opt j

j

op

t

m i i

dimana : Z = C X *

j=1

adalah sama dengan F =

i=

1

b Y *


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)

c). X2 ≥ 15 .......... (4)

d). 5X1 + X2 = 25 .......... (5)

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 :


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


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 !


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.


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 :


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 Primal

Variabel Dual X1 = 0 X2 > 0 X3 > 0

Y1 > 0

Y2 > 0

2 1

2 3

4 3

=3 =3

<30 =60 =72

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.


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

X1 ≥ 7

X2 ≥ 7

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

Uji Kompetensi


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


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


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


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


h. Rumuskan persoalan rangkap (dual problem) berdasarkan persoalan utama


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



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 - · pdf filevariabel (peubah) x dan y adalah satu. kompetensi dasar 1....

Documents