(bahan kuliah ummu)-tentang lp (materi)

PENDAHULUAN

Pada dasarnya, metode-metode yang dikembangkan untuk memecahkan model program

linear ditujukan untuk mencari solusi dari beberapa alternatif solusi yang dibentuk untuk

persamaan-persamaan pembatas sehingga diperoleh nilai fungsi tujuan yang optimal. Ada

dua cara yang bisa digunakan untuk menyelesaikan persoalan program

cara grafis dan metode simplex

dikembangkan untuk memecahkan persoalan program

variabel keputusan dan pembatas yang besar.

Dalam program linear yang mensyaratkan nilai

bergantung pada nilai variabel tersebut. Untuk menyelesaikan persoalan program

digunakan metode simplex

optimal. Metode simplex yang dimodifikas

Menggunakan Working basis”

Teori Dualitas

Dalam kebanyakan pembahasan program

masalah primal, bergantung pada jenis batasan tanda dari variabel dan arti optima

permasalahan dual, sedemikian hingga permasalahan semua yang disebut primal solusinya

dapat diperoleh dengan menyelesaikan permasalahan dualnya.

Bentuk umum masalah primal dual adalah :

Primal : Meminimalkan

Kendala

Dual : Memaksimalkan

Kendala

Bahan kuliah Riset OperasiTek. Informatika UMMU Ternate

metode yang dikembangkan untuk memecahkan model program

ditujukan untuk mencari solusi dari beberapa alternatif solusi yang dibentuk untuk

persamaan pembatas sehingga diperoleh nilai fungsi tujuan yang optimal. Ada

dua cara yang bisa digunakan untuk menyelesaikan persoalan program linear

simplex. Metode simplex merupakan teknik yang paling berhasil

dikembangkan untuk memecahkan persoalan program linear yang mempunyai jumlah

variabel keputusan dan pembatas yang besar.

yang mensyaratkan nilai variabelnya terbatas, fungsi tujuan sangat

bergantung pada nilai variabel tersebut. Untuk menyelesaikan persoalan program

yang dimodifikasi sedemikian hingga diperoleh solusi yang

yang dimodifikasi ini dikenal sebagai “ Metode

Menggunakan Working basis”.

Dalam kebanyakan pembahasan program linear, masalah dual didefenisikan untuk berbagai

masalah primal, bergantung pada jenis batasan tanda dari variabel dan arti optima


dapat diperoleh dengan menyelesaikan permasalahan dualnya.

Bentuk umum masalah primal dual adalah :

: Z = cx

Ax ≥ b

X ≥ 0

W = wb

wA ≤ c

W ≥ 0


Zufri Hasrudy Siregar

1 of 22

metode yang dikembangkan untuk memecahkan model program

ditujukan untuk mencari solusi dari beberapa alternatif solusi yang dibentuk untuk

persamaan pembatas sehingga diperoleh nilai fungsi tujuan yang optimal. Ada

linear ini yaitu dengan

merupakan teknik yang paling berhasil

yang mempunyai jumlah

variabelnya terbatas, fungsi tujuan sangat

bergantung pada nilai variabel tersebut. Untuk menyelesaikan persoalan program linear ini

yang dimodifikasi sedemikian hingga diperoleh solusi yang

“ Metode Simplex Primal

, masalah dual didefenisikan untuk berbagai

masalah primal, bergantung pada jenis batasan tanda dari variabel dan arti optimasi. Setiap




2 of 22

Perubahan tanda ketidaksamaan tergantung pada fungsi tujuannya, yaitu untuk kasus

meksimal semua pembatas bertanda ≤, sedangkan untuk kasus minimal semua pembatas

bertanda ≥ dan semua variabel non negatif. Permasalahan maksimal/minimal semacam ini

disebut permasalahan maksimal/minimal normal. Sedangkan untuk permasalahan

maksimal/minimal yang tidak normal perubahannya adalah :

Untuk permasalahan maksimal jika kendala primal xi bertanda ≥ maka variabel dual

yang berkorespondensi dengan kendala itu akan memenuhi wi ≤ 0. Sebaliknya, untuk

permasalahan minimal jika kendala primal xi bertanda ≤, maka variabel dual yang

berkorespondensi dengan variabel tersebut akan memenuhi wi ≤ 0.

Jika kendala primalnya xi bertanda =, maka variabel dual wi yang berkorespondensi

dengan kendala tersebut tidak terbatas dalam tanda.

Jika variabel primal xi tidak terbatas dalam tanda, maka kendala dualnya yi akan

bertanda =.

Program Linear dengan Nilai variabel Terbatas

Program linear dimana satu atau beberapa semua variabelnya terbatas pada batas bawah dan

batas atas tertentu dikenal dengan Program Linear dengan Variabel Terbatas. Dalam

aplikasinya dimana variabel terbatas pada bilangan tertentu (berhingga), misalnya yj, terbatas

diatas kj dan terbatas dibawah oleh lj, dimana lj ≤ kj dan lj ≥ 0, bentuk awalnya adalah :

Meminimalkan Z (y) = cy

Kendala Ay = b’

lj ≤ yj ≤ kj untuk j ε J = {1,2,...., n1}

yj ≥ 0 untuk j ε J = { n1 + 1, n1 + 2,...,n} (1)

dimana A adalah matriks order m x n. Batas 1j dan kj berhingga dan 1j ≤ kj untuk semua j ε J

Dengan mensubstitusi yj = xj + 1j untuk semua j ε J dan yj = xj untuk semua j ε J dengan

kendala variabel didapat :

1j ≤ xj + 1j ≤ kj untuk j ε J = {1,2,..., n1}

yj = xj ≥ untuk j ε J = {n1 + 1, n1 +2 ..., n}



3 of 22

atau

xj ≤ Uj = kj – 1j untuk j ε J = {1,2,...,n1}

xj ≥ 0 untuk semua j

Dengan mengubah kendala Ay = b’ dengan substitusi yj = xj + 1j untuk semua j ε J dan yj = xj

untuk j ε J maka kendalanyaberbentuk Ay = b’, dan fungsi tujuannya berbentuk Z(y) = Min

(cx + cl) dimana cl adalah konstanta, maka fungsi tujuan yang diminimalkan hanya cx. Jadi

fungsi tujuan barunya adalah Z(x) = cx, sedangkan Z(y)= Min Z (x) + cl.

Perubahan-perubahan di atas berbentuk (1) ekivalen dengan bentuk berikut:

Minimalkan Z (x) = cx

Kendala Ax = b

Xj ≤ Uj = kj – 1j untuk j ε J = {1,2,..., n1}

(2)

Xj ≥ 0 untuk semua j

Bentuk permasalahan ini merupakan bentuk umum persamaan program linear dengan nilai

variabel terbatas.

Solusi Basis Fisibel

Solusi fisibel untuk (2) adalah solusi basis fisibel jika dan hanya jika himpunan

vektor kolom yang berkorespondensi dengan basis yaitu { A.j : j sedemkian hingga 0 < j <

Uj} ∪ { Aj : j sedemikian hingga j > 0} adalah basis linear, (2) didefinisikan sebagai

working basis dari A order m. Jika diberikan working basis untuk (2), maka variabel-variabel

yang berkorespondensi dengan vektor-vektor kolom dari working basis ini disebut variabel

basis. Variabel-variabel selain itu disebut variabel non basis.

Dengan diberikannya working basis ini, maka solusi fisibbel adalah solusi basis

fisibel jika dan hanya jika ada working basis dimana solusi variabel non basis ini sama batas

bawahnya (nol) atau batas atasnya. Nilai dari variabel basis harus berbeda diantara bawah

(nol) dan batas atas untuk masing-masing variabel.

Kriteria Optimasi



4 of 22

Kriteria optimasi untuk program ini diperoleh dari hubungan primal dan duualnya. Dari

permasalahan (2) dapat juga ditulis dalam bentuk :

Minimalkan Z(x) = cx.

Kendala

.

-xj≥ -Uj untuk j ε J = { 1,..., n1} (3)

Xj ≥ 0 untuk semua j

Permasalahan di atas adalah meminimalkan yang tidak normal, selanjutnya memisalkan

variabel dual kendala Ax =b adalah η1,...ηm, dan η1,...,ηn1 bagi kendala variabel –xj ≥ - Uj

maka dualnya adalah :

Maksimalkan : ηb – μU

Kendala : ηA.j – μj xj ≤ cj untuk j ε J

ηA.j ≤ cj untuk j ε J (4)

η tidak terbatas tanda

μ ≥ 0

Dari (3) dan (4) nilai variabel slack untuk masing-masing kendalanya adalah

cj – ηA.j + μj xj ≥ 0 untuk j ε J

cj – ηA.j + μj xj ≥ 0 untuk j ε J

Uj – xj ≥ 0 untuk j ε J

Oleh karena itu solusi fisibel untuk (4) dipenuhi hanya jika variabel primal dan dualnya

memenuhi complementary slackness condition sebagai berikut :

Xj (cj – ηA.j + μj) = 0 untuk j ε J (5a)

Xj (cj – ηA.j) = 0 untuk j ε J (5b)

Xj (Uj – xj ) = 0 untuk j ε J (5c)



5 of 22

Dengan memisalkan cj – ηA.j = cj merupakan koefisien fungsi tujuan ke-j pada iterasi ke-k

yang optimal maka nilai xj juga harus optimal. Fisibilitas dual mensyaratkan bahwa cj + μj ≥

0 untuk semua untuk j ε J dan cj ≥ 0 untuk j ε J. Dari fisibilitas dual maka diperoleh beberapa

kemungkinan sebagi berikut :

Untuk j ε J, jika cj < 0 maka untuk memenuhi fisibilitas (4) diperlukan nilai μj ≥ 0

(karena cj + μj ≥ 0 untuk j ε J), karena μj > 0 maka dari (5c) didapat xj = Uj.

Untuk j ε J, jika xj nilainya berbeda diantara batas atas dan bawah maka dari (5a) dan

(5c) dipenuhi hanya jika cj = 0 dan μj = 0.

Untuk j ε J, jika cj > 0 maka dari (5b) didapat xj = 0.

Dari kemungkinan ini solusi fisibel untuk (2) yaitu x adalah optimal jika dan hanya

jika terdapat η sedemikian hingga c = ηA, nilai xj dimana cj > 0 adalah nol dan nilai xj

dimana cj < 0 adalah Uj.

Misalkan x adalah solusi fisibel untuk (2) yang berkorespodensi dengan working basis

B. Jika xj adalah variabel basis, maka nilai xj terdapat diantara 0 dan Uj dengan cj = 0,

oleh karena itu η yang bersesuaian dengan working basis B dapat diperoleh dengan

menyelesaikan cj – ηA.j = 0 untuk semua j, dengan A.j adalahvektor kolom pada B.

Misalkan CB adalah vektor koefisien harga fungsi tujuan variabel basis, maka η

diperoleh dengan menyelesaikan CB = ηB, yaitu η = cb B-1. Setelah η didapat

selanjutnya, nilai c diperoleh dari c = c – ηA. Dengan memandang c kriteria

optimalitas untuk program linear variabel terbatas adalah :

Untuk j ε J dan cj < 0 dimana xj = Uj

Untuk j ε J dan cj > 0 dimana xj = 0

Untuk j ε J dimana cj ≥ 0

Formulasi Model LP

Masalah keputusan yang biasa dihadapi para analis adalah alokasi optimum sumber daya

yang langka. Sumber daya dapat berupa modal, tenaga kerja, bahan mentah, kapasitas mesin,

waktu, ruang datau teknologi. Tugas analis adalah mencapai hasil terbaik yang mungkin

dengan keterbatasan sumber daya. Hasil yang diinginkan mungkin ditujukan sebagai

maksimasi dari beberapa ukuran seperti profit, penjualan dan kesejahteraan, atau miniasi

seperti biaya, waktu dan jarak.



6 of 22

Setelah diidentifikasi, tujuan diterapkan, langkah selanjutnya adalah formulasi model

matematik yang meliputi tiga tahap :

1. Menentukan variabel yang tak diketahui (variabel keputusan) dan menyatakan

dalam simbol matematik.

2. Membentuk fungsi tujuan yang ditunjukkan sebagai suatu hubungan linear

(bukan perkalian) dari variabel keputusan

3. Menentukan semua kendala masalah tersebut dan mengekspresikan dalam

persamaan dan pertidaksamaan yang juga merupakan hubungan linear dari

variabel keputusan yang mencerminkan keterbatasan sumberdaya tersebut

Linear programming memiliki empat ciri khusus yang melekat, yaitu :

1. Penyelesaian masalah mengarah pada pencapaian tujuan maksimisasi atau

minimisasi

2. Kendala yang ada membatasi tingkat pencapaian tujuan

3. Ada beberapa alternatif penyelesaian

4. Hubungan matematis bersifat linear

Secara teknis, ada lema syarat tambahan dari permasalahan lenear programming yang harus

diperhatikan yang merupakan asumsi dasar, yaitu :

1. Certainty ( kepastian). Maksudnya adalah fungsi tujuan dan fungsi kendala sudah

diketahui dengan pasti dan tidak berubah selama periode analisa

2. Proportionality (proporsionalitas). Yaitu adanya proporsionalitas dalam fungsi tujuan

dan fungsi kendala

3. Additivity (penambahan). Artinya aktivitas total sama dengan penjumlahan aktivitas

individu

4. Divisibility (bisa dibagi-bagi). Maksudnya solusi tidak harus merupakan bilangan

integer (bilangan bulat), tetapi bisa juga berupa pecahan

5. Non-negative variabel (variabel tidak negatif). Artinya bahwa semua nilai jawaban

atau variabel tidak negatif



7 of 22

Contoh masalah kombinasi produk

Sebuah perusahaan ingin menentukan berapa banyak masing-masing dari tiga produk yang

berbeda yang akan dihasilkan dengan tersedianyasumber daya yang terbatas agar diperoleh

keuntungan maksimu. Kebutuhan buruh dan bahan mentah dan sumbangan keuntungan

masing-masing produk adalah sebagai berikut :

Produk

kebutuhan Sumber Daya Keuntungan

(Rp/unit)Buruh (jam/unit) Bahan (Kg/unit)

A 5 4 3

B 2 6 5

C 4 3 2

Tersedia 240 jam kerja dan bahan mentah sebanyak 400 kg. Masalahnya adalah menentukan

jumlah masing-masing produk agar keuntungan maksimum. Rumusan model LP-nya adalah :

A. Variabel Keputusan

Tiga variabel dalam masalah ini adalah produk A, B dan C yang harus dihasilkan. Jumlah

ini dapat dilambangkan sebagai berikut :

X1 = jumlah produk A

X2 = jumlah produk B

X3 = jumlah produk C

B. Fungsi Tujuan

Tujuan masalah kombinasi produk adalah memaksimumkan keuntungan total. Jelas

bahwa keuntungan adalah jumlah keuntungan yang diperoleh dari masing-masing produk.

Keuntungan dari produk A adalah perkalian antara jumlah produk A dengan keuntungan

per unit (Rp. 3,-). Keuntungan produk B dan C ditentukan dengan cara serupa. Sehingga

keuntungan total Z, dapat dituliskan :

Z = 3X1 + 5X2 + 2X3



8 of 22

C. Sistem Kendala

Dalam masalah ini kendalanya adalah jumlah buruh dan bahan mentah yang terbatas.

Masing-masing produk membutuhkan buruh maupun bahan mentah. Produk A, buruh

yang dibutuhkan untuk menghasilkan tiap unit adalah 5 jam, sehingga buruh yang

dibutuhkan untuk produk A adalah 5X1 jam. Dengan cara yang serupa produk B

membutuhkan 2X2 jam buruh, dan produk C butuh 4X3 jam, sementara jumlah buruh

yang tersedia adalah 240 jam. sehingga dapat ditulis:

5X1 + 2X2 + 4X3 ≤ 240

Kendala bahan mentah dirumuskan dengan cara yang sama, yaitu untuk produk A butuh

bahan mentah sebanyak 4 kg per unit, produk B membutuhkan 6 kg per unit dan produk C

butuh 3 kg per unit. Karena yang tersedia adalah sebanyak 400 kg bahan mentah, maka

ditulis :

4X1 + 6X2 +3X3 ≤ 400

Kita juga membatasi masing-masing variabel hanya nilai positif, karena tidak mungkin untuk

menghasilkan jumlah produk negatif. Kendala-kendala ini dikenal dengan non negativity

constraints dan secara matematis dapat ditulis :

X1 ≥ 0, X2 ≥ 0, X3 ≥ 0 atau X1, X2, X3 ≥ 0

Pertanyaan yang timbul adalah mengapa kendala dituliskan dengan tanda pertidaksamaan ( ≤

), bukan persamaan ( = ). Persamaan secara tidak langsung mengatakan bahwa seluruh

kapasitas sumber daya digunakan, sementara dalam pertidaksamaan memperbolehkan

penggunaan kapasitas secara penuh maupun penggunaan sebagian kapasitas. Dalam beberapa

kasus suatu solusi dengan mengizinkan adanya kapasitas sumberdaya yang tak terpakai akan

memberikan solusi yang lebih baik, yang bearti keuntungan lebih besar, dari pada

penggunaan seluruh sumber daya. Jadi, pertidaksamaan menunjukan keluwesan.

Dari masalah diatas, formulasi LP secara lengkap dapat ditulis :

Maksimumkan Z = 3X1 +5X2 + 2X3

dengan syarat 5X1 + 2X2 +4X3 ≤ 240

4X1 + 6X2 + 3X3 ≤ 400

X1, X2, X3 ≥ 0



9 of 22

Contoh 2 : masalah Diet

Untuk menjaga kesehatan, seorang harus memenuhi kebutuhan minimum perhari akan

beberapa zat makanan, misalkan hanya ada tiga jenis zat makanan yang dibutuhkan yaitu

kalsium, protein, dan vitamin A. Sementara makanan yang tersedia ada tiga jenis juga yaitu,

makanan A,B dan C yang harganya, zat-zat yang terkandung didalamnya, dan kebutuhan

minimum perhari akan zat-zat makanan tersebut dapat dilihat pada tabel

Kandungan Makanan Kebutuhan

minimumI II III

Kalsium

Protein

Vitamin A

5

2

1

1

2

5

0

1

4

8

12

22

HARGA/UNIT 0,5 0,8 0,6

Masalahnya adalah bagaimana kombinasi ketiga makanan itu akan memenuhi kebutuhan

minimum perhari dan memberikan biaya terendah.

1. Variabel Keputusan

Masalah ini terdiri dari tiga variabel yang menunjukkan jumlah masing-masing jenis

makanan yang diterapkan dalam menu, yaitu :

X1 = jumlah makana A

X2 = jumlah makanan B

X3 = jumlah makanan C

2. Fungsi Tujuan

Tujuan masalah ini adalah meminimumkan biaya total menu perhari. Biaya total dalam

konteks ini adalah jumlah biaya dari masing-masing jenis makanan yang disajikan dalam

menu. Sehingga biaya total, Z, ditulis :

Z = 0,5X1 +0,8X2 + 0,6X3

3. Sistem kendala

Dalam masalah ini , kendalanya adalah kebutuhan minimum akan zat-zat makanan

perhari yang telah ditetapkan. Kendala untuk kalsium ditulis :



10 of 22

5X1 + X2 ≥ 8

5X1 adalah sumbangan kalsimum dari makanan A

X2 adalah sumbangan kalsium dari makanan B

Pada contoh ini digunakan pertidak samaan “≥” yang menunjukkan jumlah minimum kalsium

yang dibutuhkan. Dengan kata lain , sekurang-kurangnya 8 unit kalsium harus dipenuhi.

Kendala untuk protein dan vitamin A dibuat dengan cara yang sama, yaitu :

2X1 + 2X2 + X3 ≥ 10 Protein

X1 + 5X2 + 4X3 ≥ 22 vitamin A

Masalah LP secara lengkap dapat ditulis :

Minimumkan Z = 0,5X1 + 0,8X2 + 0,6X3

Dengan syarat 5X1 + X2 ≥ 8

2X1 + 2X2 + X3 ≥ 10

X1 + 5X2 + 4X3 ≥ 22

X1, X2, X3 ≥ 0

BENTUK UMUM MODEL LP

Dari contoh yang sudah ditulis diatas secara mendalam terlihat adanya suatu pola yang khas

untuk merumuskan secara umum suatu masalah LP. Pada setiap masalah, ditentukan variabel

keputusan, fungsi tujuan, dan sistem kendala, yang bersama-sama membentuk suatu model

matematik dari dunia nyata. Bentuk umum model LP itu adalah :

Maksimumkan (minimumkan) Z =∑

Dengan syarat : (≤, =, ≥ ) bi , untuk semua i (i = 1,2,...m) semua xj ≥ 0

Keterangan :

xj : banyaknya kegiatan j, dimana j = 1,2,...,n, yang bearti terdapat n variabel keputusan

Z : nilai fungsi tujuan



11 of 22

Cj : sumbangan per unit kegiatan j, untuk masalah maksimasi Cj menunjukkan atau

penerimaan per unit, sementara dalam kasus minimasi ia menunjukkan biaya per unit.

bi : jumlah sumber daya ke i (i = 1,2,...m), bearti terdapat m jenis semberdaya.

xij : banyaknya semberdaya i yang dikonsumsi sumberdaya j.

Yang perlu diingat adalah tanda pertidaksamaan tidak harus sama untuk setiap kendala !

ASUMSI MODEL LP

Model LP mengandung asumsi-asumsi implisit tertentu yang harus dipenuhi agar

defenisinya sebagai suatu masalah LP menjadi absah. Asumsi itu menuntut bahwa hubungan

fungsional dalam masalah itu adalah linear dan additif, dapat dibagi dan deterministik.

Linear dan additivity

Bahwa fungsi tujuan dan semua kendala harus linear. Dengan kata lain, jika suatu

kendala melibatkan dua variabel keputusan, dalam diagram dimensi dua ia akan berupa

garis lurus. Begitu juga, suatu kendala yang melibatkan tiga variabel akan menghasilkan

suatu bidang datar dan kendala yamg melibatkan n variabel akan menghasilkan

hyperplane (bentuk geometris yang rata) dalam ruang berdimensi n. Kata linear secara tidak

langsung mengatakan bahhwa hubunggan proporsional yang berarti bahwa tingkat perubahan

atau kemiringan hubungan fungsional itu adalah konstan dan karena nilai variabel akan

mengakibatkan perubahan relatif nilai fungsi tujuan dalam jumlah yang sama. LP juga

mensyaratkan bahwa jumlah variabel kriteria dan jumlah penggunaan sumber daya harus

bersifat additif. Contohnya, keuntunga total Z yang merupakan variabel kriiteria, sama

dengan jumlah keuntungan yang diperoleh dari maing-masing kegiatan, Cj Xj. Juga, seluruh

sumber daya yang digunakan untuk seluruh kegiattan, harus sama dengan jumlah sumber

daya yang digunakan untuk masing-masing kegiatan.

Additif dapat diartikan sebagai tak adanya penyesuaian pada perhitungan variabel kriteria

karena terjadi interaksi. Contohnya, dalam masalah kombinasi produk disebutkan bahwa

keuntungan per unit produk A Rp.3,-, produk B Rp.5,- dan produk C Rp. 2,-. Jika masing-

masing produk dijual secara terpisah. Tetapi bisa jadi, kalau dijual secara serentak pada

daerah yang sama dapat menyebabkan penurunan keuntungan, sehingga perlu memasukkan

penyesuaian interaksi ke dalam variabel kriteria, misalnya saja menjadi :



12 of 22

Z = 3X1 +5X2 +2X3 – X1 X2 X3

Devisibility

Asumsi ini bearti bahwa nilai solusi yang diperoleh Xj, tidak harus bilangan bulat. Ini

bearti nilai Xj dapat berupa nilai pecah. Karena itu variabel keputusan merupakan variabel

kontinyu, sebagai lawan dari variabel diskrit atau bilangan bulat.

Deterministic

Semua parameter model (cj, aij dan bi ) diasumsikan diketahui konstan. LP secara tak

langsung mengasumsikan suatu masalah keputusan dalam suatu kerangka statis dimana

semua parameter diketahui dengan kapastian. Dalam kenyataannya, parameter model jarang

bersifat deterministik, karena mereka mencerminkan kondisi masa depan maupun sekarang,

dan keadaan masa depan jarang diketahui secara pasti.

Ada beberapa cara untuk mengatasi ketidak pastian parameter dalam model LP. Analisa

sensitivitas adalah suatu teknik yang dikembangkan untuk menguji nilai solusi. Bagaimana

kepekaannya terhadap perubahan-perubahan parameter.

PENYELESAIAN GRAFIK MODEL LP

Masalah LP dapat diilustrasikan dan dipecahkan secara grafik jika ia hanya memiliki

dua variabel keputusan. Meski masalah-masalah dengan dua variabel jarang terjadi dalam

dunia nyata, penafsiran seametris dari metode grafik ini sangat bermanfaat. Dari sini, kita

dapat menarik kesimpulan yang akan menjadi dasar untuk pembentukan metode pemecahan

masalah (solusi) yang umum melalui algoritma simplex.

Contoh permasalahan maksimasi

Sumber daya Produk 1 Produk 2 Sumber daya yang

tersedia

Bahan mentah

Buruh

1

6

2

6

10

36

Keuntungan/unit 4 5

Disamping itu, menurut bagian penjualan diramalkan, bahwa permintaan produk 1 tidak akan

melebihi 4 unit

Masalah dapat dirumuskan :



13 of 22

Maksimalkan Z = 4X1 + 5X2

X1 + 2X2 ≤ 10

6X1 + 6X2 ≤ 36

X1 ≤ 4

X1, X2 ≥ 0

Suatu cara sederhana untuk menggambarkan masing-masing persamaan garis adalah dengan

menetapkan salah satu variabel dalam suatu persamaan sama dengan nol dan kemudian

mencari nilai variabel yang lain. Misalnya pada kendala pertama jika X1 = 0, maka 2X2 = 10

atau X2 = 5. Dengan cara yang sama X2 = 0 maka X1 = 10. Kedua titik ini {(0,5) dan (10,0)}

kemudian dihubungkan dengan suatu garis

lurus.

Suatu daerah yang bersaman memenuhi

ketiga kendala ditunjukkan oleh area yang

diarsir yaitu area ABCDE pada gambar

grafik. Wilayah ini dinamakan solusi layak

atau ruang solusi. Sementara itu, pasangan

nilai-nilai (X1, X2) di luar daerah ini bukan

merupakan solusi layak, karena

menyimpang dari suatu atau lebih kendala.

Sementara hasil optimal Z dapat

ditunjukkan pada titik terluar pada daerah solusi layak. Ada dua hal yang perlu diperhatikan,

kaitanya dengan fungsi tujuan yaitu :

1. Semua garis Z adalah sejajar, atau memiliki kemiringan yang sama sebesar -4/5

yang diperoleh memalui perhitungan berikut : X2 = Z/5 – (4/5)X1

2. Garis Z adalah garis-garis sejajar dalam jumlah tak terbatas.

Penjelasan metode grafik :

Maksimum Z = 4X1 + 5X2

Kendala : X1 + 2X2 =10



14 of 22

6X1 + 6X2 = 36

X1= 4

X1, X2 ≥ 0

Pencarian variabel X1 dan X2 (X1 + 2X2 =10)

X1 =0, berarti X2 = 5

X2 = 0, bearti X1 = 10

Untuk (6X1 + 6X2 = 36)

X1 =0, berarti X2 = 6

X2 = 0, bearti X1 = 6

Terlihat pada grafik daerah feasible region yaitu daerah A,B,C,D,E. Untuk mencari nilai X1

dan X2 yang optimal dan memenuhi Z pada 4X1 + 5X2 dilakukan metode eliminasi diantara 2

garis yang bersinggungan yaitu X1 + 2X2 =10 dan 6X1 + 6X2 = 36 di titik B karena untuk

maksimum harus titik yang terjauh dari titik origin.

6X1 + 6X2 = 36 x1 6X1 + 6X2 = 36

X1 + 2X2 =10 x3 3X1 + 6X2 = 30

3X1 = 6

X1 = 2

6X1 + 6X2 = 36

6(2) + 6X2 = 36

6X2 = 24

X2 = 4

Untuk Z yang memenuhi X1 dan X2 bearti Z = 4X1 + 5X2

Z = 4(2) + 5(4)

Z = 28

(10,5)

(6,6)

-



15 of 22

X2

5 10x1

X1 = 4

X1 + 2X2 = 10

6X1 + 6X2 = 36

Z = 31

5

10

15

C

A

Garis iso cost line

Feasible region

B

Penyelesaian persoalan yang sama dengan asumsi minimalisasi

Fungsi kendala yang pada maksimasi “≤” dirubah menjadi “≥” .

Masalah dapat dirumuskan :

Minimumkan Z = 4X1 + 5X2

X1 + 2X2 ≥ 10

6X1 + 6X2 ≥ 36

X1 ≥ 4

X1, X2 ≥ 0

Penyelesaiannya sama dengan penyelesaian diatas

Dari grafik terlihat bahwa daerah feasible region(daerah layak) adalah A,B,C yang

perhitungannya adalah:

Titik A adalah titik X1 = 0 dan X2 = 5, bila dimasukkan dengan nilai Z = 4X1 + 5X2

mempunyai hasil Z = 25

Titik B adalah perpotongan garis X1 + 2X2 ≥ 10 dan 6X1 + 6X2 ≥ 36 sehingga didapat:

6X1 + 6X2 = 36 x1 6X1 + 6X2 = 36

X1 + 2X2 =10 x3 3X1 + 6X2 = 30 -



16 of 22

3X1 = 6

X1 = 2

6X1 + 6X2 = 36

6(2) + 6X2 = 36

6X2 = 24

X2 = 4

Bila dimasukkan dengan nilai Z = 4X1 + 5X2 mempunyai hasil 28

Untuk titik C adalah X1 + 2X2 ≥ 10 dan X1 ≥4 sehingga didapat:

X1 = 4 dan X2 = 3dan bila memenuhi fungsi tujuan Z = 4X1 + 5X2 adalah 31

Dengan melakukan pendekatan iso cost line, terlihat garis tersebut bersinggungan dengan

titik C. Dimana masih didalam daerah layak (feasible region), dan juga merupakan titik

yang terdekat dengan titik orgin. Sehingga didapat nilai minimum untuk persoalan itu

adalah X1 = 4 dan X2 = 3 dan Z= 31

Untuk menentukan solusi yang optimal, ada dua cara yang bisa digunakan yaitu :

1. Dengan menggunakan garis profit (iso profit line)

2. Dengan titik sudut ( corner point)

Penyelesaian dengan menggunakan garis profit adalah penyelesaian dengan menggambarkan

fungsi tujuan. Kemudian fungsi tujuan tersebut digeser ke kanan sampai meyinggung titik

terjauh dari titik nol, tetapi masih berada pada area layak (feasible region). Sedangkan dengan

menggunakan titik sudut (corner point) artinya kita harus mencari nilai tertinggi dari titik-titik

yang berada pada area layak ( feasible region).

ISU TEKNIS DALAM LP

Dalam Linear Programming dengan metode grafik sering dijumpai permasalahan secara

teknis, yaitu :

1. Infeasibility

2. Unboundedness



17 of 22

3. Redundancy

4. Alternate optimal solutions

Infeasibility adalah suatu kondisi dimana tidak ada area layak yang memenuhi semua

kendala. Unboundedness adalah suatu kondisi dimana area layak tidak terbatas. Kasus ini

biasanya muncul pada fungsi tujuan maksimisasi. Redundancy constraint yang tidak

mempengaruhi feasible region disebut redundant conctraint misalnya bagian marketing

mengatakan bahwa tidak bisa menjual lebih dari 50 buah meja, maka pernyataan ini disebut

redundant. Kerena kenyataannya, bagian produksi maksimal hanya bisa memproduksi 40

meja. Alternatif Optima adalah situasi dimana terdapat lebih dari satu solusi optimal. Hal ini

akan terjadi apabila garis profit sejajar dengan salah satu kendala.

METODE SIMPLEX

Metode penyelesaian program linear dengan metode simplex pertamakali dikemukakan

oleh George Dantzig pada tahun 1947. Metode ini menjadi terkenal ketika diketemukan alat

hitung elektronik dan menjadi poluler ketika munculnya komputer. Proses perhitungan

metode ini dengan melakukan iterasi berulang-ulang sampai tercapai hasil optimal dan proses

perhitungan ini menjadi mudah dengan komputer. Selanjutnya berbagai alat dan metode

dikembangkan untuk menyelesaikan masalah program linear bahkan sampai pada masalah

riset operasi hingga tahun 1950 an seperti pemrograman dinamik, teori antrian, dan

persediaan.

Beberapa ketentuan yang perlu diperhatikan dalam penyelesaian metode simplex :

1. Nilai kanan (NK/RHS) fungsi tujuan harus nol (0)

2. Nilai kanan (RHS) fungsi kendala harus positif. Apabila negatif, nilai tersebut harus

dikali -1

3. Fungsi kendala dengan tanda “≤” harus diubah ke bentuk “=” dengan menambahkan

variabel slack/surplus (bila variabel slack negatif). Variabel slack/surplus disebut juga

variabel dasar. Penambahan slack variabel menyatakan kapasitas yang tidak

digunakan atau tersisa pada departemen tersebut. Hal ini karena ada kemungkinan

kapasitas yang tersedia tidak semua digunakan dalam proses produksi.

4. Fungsi kendala dengan tanda “≥” diubah ke bentuk “≤” dengan cara mengkalikan

dengan -1, lalu diubah ke bentuk persamaan dengan ditambah variabel slack.

Kemudian karena RHS-nya negatif, dikalikan lagi dengan -1 dan ditambah artificial



18 of 22

variabel (M). Artificial variabel ini secara fisik tidak mempunyai arti, dan hanya

digunakan untuk kepentingan perhitungan saja.

5. Fungsi kendala dengan tanda “=” harus ditambah artificial variabel(M)

Metode simplex merupakan prosedur aljabar yang bersifat iteratif, yang bergerak selangkah

demi selangkah, dimulai dari suatu titik ekstrem pada daerah fisibel ( ruang solusi) menuju ke

titik ekstrem optimum. Misalkan model program linear sebagi berikut :

Meminimalkan : Z = Cx

Kendala Ax = b

X ≥ 0

Dengan A, b, c dan x masing-masing adalah :

A =

⎣⎢⎢⎢⎢⎡

……

. . … .

. . … .

. . … .… ⎦

⎥⎥⎥⎥⎤

, b =

⎣⎢⎢⎢⎢⎡

.

.

.⎦⎥⎥⎥⎥⎤

, c = (c1, c2, ..., cn) dan x =

⎣⎢⎢⎢⎡

.

..⎦⎥⎥⎥⎤

Untuk mendapatkan solusi dasis dari Ax = b maka sebanyak (n-m) variabel harus dinolkan.

Variabel yang dinolkan ini disebut variabel non basis. Selanjutnya dicar nilai dari n-(n-m) =

m variabel yang memenuhi Ax = b yang disebut variabel basis.

Penyelesaian persoalan diatas dengan metode simplex

Metode simplex maksimasi

Tujuan : Zmax = 4X1 + 5X2

Kendala : X1 + 2X2 ≤ 10

6X1 + 6X2 ≤ 36

X1 ≤ 4

X1, X2 ≥ 0

Persamaan diubah menjadi :

Tujuan : Zmax = 4X1 + 5X2 ↔ Z = -4X1- 5X2 – 0S1 –0 S2 –0S3

Kendala : X1 + 2X2 + S1 = 10

6X1 + 6X2 + S2 = 36



19 of 22

X1 + S3 = 4

Buata tabel simplex

VD Z X1 X2 S1 S2 S3 Hasil Rasio

Z 1 -4 -5 0 0 0 0

S1 0 1 2 1 0 0 10 5

S2 0 6 6 0 1 0 36 6

S3 0 1 0 0 0 1 4 ~

1. Tentukan kolom masuk

Pada kasus maksimalisasi, kolom masuk merupakan nilai negatif terbesar pada

persamaan Z atau baris Z pada tabel simplex, sehingga X2 merupakan kolom masuk.

2. Tentukan kolom keluar atau persamaan pivot.

Merupakan nilai positif terkecil dari rasio antara pemecahan dengan elemen pada kolom

masuk, sehingga :

Hasil Kolom masuk (X2) Rasio

10 2 10/2 = 5

36 6 36/6 = 6

4 0 4/0 = ~ (nilai seperti ini diabaikan saja)

Variabel nondasar X2 akan menggantikan variabel dasar S1 pada tabel simplex iterasi

pertama.

3. Tentukan elemen pivot.

Merupakan angka pada perpotongan kolom masuk dan kolom keluar, sehingga elemen

pivot = 2

4. Mencari persamaan pivot baru.

Persamaan pivot baru = persamaan pivot lama / elemen pivot


Z 1 -4 -5 0 0 0 0

S1 0 1 2 1 0 0 10 5

S2 0 6 6 0 1 0 36 6

S3 0 1 0 0 0 1 4 ~

Elemen pivot Elemen kolom masuk



20 of 22

Persamaan pivot baru = persamaan pivot lama / elemen pivot

Persamaan pivot lama (a) 0 1 2 1 0 0 10

Elemen pivot (b) 2 2 2 2 2 2 2

Persamaan pivot baru (a/b) 0 1/2 1 1/2 0 0 5

5. Mencari persamaan variabel dasar baru.

6. Pada kasus diatas yang merupakan variabel dasar adalah Z, S2, dan S3

Variabel dasar baru = variabel dasar lama – (elemen kolom masuk x persamaan pivot

baru)

a. Persamaan Z baru

Persamaan Z lama (a) 1 -4 -5 0 0 0 0

Elemen kolom masuk padavariabel dasar Z (b)

-5 -5 -5 -5 -5 -5 -5

Persamaan pivot baru (c) 0 1/2 1 1/2 0 0 5

b x c = (d) 0 -21/2 -5 -21/2 0 0 -25

Persamaan Z baru (a-d) 1 -11/2 0 21/2 0 0 25

b. Persamaan S2 baru

Persamaan S2 lama (a) 0 6 6 0 1 0 36

Elemen kolom masuk padavariabel dasar S2 (b)

6 6 6 6 6 6 6


b x c = (d) 0 3 6 3 0 0 30

Persamaan S2 baru (a-d) 0 3 0 -3 1 0 6

c. Persamaan S3 baru



0 0 0 0 0 0 0


b x c = (d) 0 0 0 0 0 0 0

Persamaan Z baru (a-d) 0 1 0 0 0 1 4

d. Tabel iterasi Pertama



21 of 22


Z 1 -11/2 0 21/2 0 0 25

X2 0 1/2 1 1/2 0 0 5 10

S2 0 3 0 -3 1 0 6 2

S3 0 1 0 0 0 1 4 4

7. Kondisi optimum pada kasus maksimasi diperoleh ketika persamaan Z atau baris Z tidak

memiliki angka yang bernilai negative. Apabila kondisi optimum belum diperoleh, maka

dilakukan kembali iterasi seperti langkah sebelumnya.

Hasil Kolom masuk (X1) Rasio

5 1/2 5/1/2 = 10

6 3 6/3 = 2

4 1 4/1 = 4

a. Elemen pivot adalah = 3

Persamaan pivot lama (a) 0 3 0 -3 1 0 6

Elemen pivot (b) 3 3 3 3 3 3 3

Persamaan pivot baru (a/b) 0 1 0 -1 1/3 0 2

b. Persamaan variabel dasar baru

1. Persamaan Z baru

Persamaan Z lama (a) 1 -11/2 0 21/2 0 0 25

Elemen kolom masuk padavariabel dasar Z (b)

-11/2 -11/2 -11/2 -11/2 -11/2 -11/2 -11/2

Persamaan pivot baru (c) 0 1 0 -1 1/3 0 2

b x c = (d) 0 -11/2 0 -11/2 -0,5 0 -3

Persamaan Z baru (a-d) 1 0 0 1 0,5 0 28

2. Persamaan X2 baru

Persamaan X2 lama (a) 0 1/2 1 1/2 0 0 5

Elemen kolom masuk padavariabel dasar X2 (b)

1/2 1/2 1/2 1/2 1/2 1/2 1/2


b x c = (d) 0 0,5 0 -0,5 1/6 0 1

Persamaan X2 baru (a-d) 0 0 1 1 -1/6 0 4

3. Persamaan S3 baru



22 of 22



1 1 1 1 1 1 1


b x c = (d) 0 1 0 -1 1/3 0 2

Persamaan S3 baru (a-d) 0 0 0 1 -1/3 1 2

4. Tabel simplex iterasi ke dua sudah optimum


Z 1 0 0 1 0,5 0 28

X2 0 0 1 1 -1/6 0 4

X1 0 1 0 -1 1/3 0 2

S3 0 0 0 1 -1/3 1 2

5. Tabel simplex iterasi kedua diatas sudah optimum karena variabel nondasar pada

persamaan Z sudah bernilai positif, sehingga :

X1 = 2, X2 = 4 dan nilai Z = 28

6. Pada tabel optimum S1 dan S2 = 0. Artinya persediaan sumber daya pertama dan kedua

habis digunakan, tetapi masih memiliki sumber daya ketiga (S3) sebesar 2 karena tidak

digunakan.

(bahan kuliah ummu)-tentang lp (materi)

Documents