BAB I PENGANTAR PROGRAM LINIER

BAB I PENGANTAR PROGRAM LINIER

1.1. Pengertian Program linier merupakan kata benda dari pemogramman linier (linear programming), muncul dalam penelitian operasional (operational research). Menurut George B. Dantzing yang sering disebut Bapak Linear Programming, di dalam bukunya “Linear Programming and Extension”, menyebutkan bahwa ide dari linear programming ini berasal dari ahli matematik Rusia bernama L.V. Kantorivich yang pada tahun 1939 menerbitkan sebuah karangan dengan judul “Mathematical Methods in The Organization and Planning of Production”, yang didalamnya telah dirumuskan persoalan linear programming untuk pertama kalinya. Ide ini, di Rusia tidak berkembang dan justru berkembang di dunia barat, kemudian tahun 1947 seorang ahli matematik dari Amerika Serikat yaitu George B. Dantzing menemukan suatu cara untuk memecahkan persoalan linear programming tersebut dengan suatu metode yang disebut “Simplex Methods”. Setelah itu, linear programming berkembang pesat sekali, semula di bidang militer (untuk penyusunan strategi perang) maupun di bidang bussines (persoalan untuk mencapai maksimum profit, minimum loss, dll). Sekarang berkembang luas di dalam perencanaan pembangunan ekonomi nasional, misalnya di dalam penentuan “allocation of investments” ke dalam sektor-sektor perekonomian, “rotation corp policy”, peningkatan penerimaan devisa, dll. Program linier (linear programming) merupakan meodel matematik dalam mengalokasikan sumberdaya yang langka untuk mencapai tujuan tunggal seperti memaksimumkan keuntungan atau meminimumkan biaya. Program linier sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linear dan sistem kendala linier.

Dra. Retno Marsitin, MPd. - Program Linier

Page 1

1.2. Persoalan Optimasi & Persoalan Programming Pada dasarnya persoalan optimasi (optimazion problems) merupakan suatu persoalan membuat nilai fungsi 𝑧 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 , dengan variabel yaitu 𝑥1 , 𝑥2 , … . , 𝑥𝑛 menjadi maksimum atau minimum dengan memperhatikan kendala-kendala atau pembatas-pembatas yang ada. Biasanya pembatas-pembatas tersebut meliputi tenaga kerja, uang, material yang merupakan input, serta waktu dan ruang. Persoalan programming pada dasarnya berkenaan dengan penentuan alokasi yang optimal dari sumber-sumber yang langka (limited resources) untuk memnuhi suatu tujuan (objective). Misalnya, bagaimana mengkombinasikan beberapa sumber yang terbatas seperti tenaga kerja, material, mesin, tanah, pupuk, air sehingga diperoleh output yang maksimum. Persoalan linear programming adalah persoalan untuk menentukan besarnya masing-masing nilai variable sedemikian rupa sehingga nilai fungsi tujuan atau obyektif (objective function) yang linier menjadi optimum (maksimum atau minimum) dengan memperhatikan pembatasan-pembatasan yang ada yaitu pembatasan mengenai inputnya. Pembatasan-pembatasan inipun harus dinyatakan dalam ketidaksamaan yang linier (linear inequality). Suatu persoalan disebut persoalan program linier apabila memenuhi hal-hal berikut: a. Tujuan (objective) yang akan dicapai harus dapat dinyatakan dalam bentuk fungsi linier. Fungsi ini disebut fungsi tujuan (objective function) b. Harus ada alternative pemecahan. Pemecahan yang membuat nilai fungsi tujuan optimum (laba yang maksimum, biaya yang minimum, dll) yang hartus dipilih c. Sumber-sumber tersedia dalam jumlah terbatas (bahan mentah terbatas, ruangan untuk menyimpan barang terbatas, dll). Pembatasan-pembatasan harus dinyatakan di dalam ketidaksamaan yang linier (linear inequality)


Page 2

Secara teknis, ada syarat tambahan dari permasalahan program linier yang harus diperhatikan sebgai asumsi dasar yaitu: a. Kepastian (certainty), yaitu fungsi tujuan dan fungsi kendala sudah diketahui dan tidak berubah selama periode analisa b. Proporsionalitas (proportionality), yaitu adanya proporsionalitas dalam fungsi tujuan dan fungsi kendala c. Penambahan (additivity), yaitu aktivitas total sama dengan penjumlahan aktivitas individu d. Bisa dibagi-bagi (divisibility), yaitu solusi tidak harus merupakan bilangan integer (bilangan bulat) tetapi bisa juga bilangan pecahan e. Variable tidak negatif (non-negative variable), yaitu bahwa semua nilai jawaban atau variabel tidak negative 1.3. Formulasi Model Matematika.  Masalah keputusan yang sering dihadapi analis yaitu alokasi optimum sumber daya.  Sumber daya dapat berupa uang, tenaga kerja, bahan mentah, kapasitas mesin, waktu, ruangan atau teknologi.  Tugas analisis adalah mencapai hasil terbaik dengan keterbatasan sumber daya tersebut.  Setelah masalah diidentifikasikan dan tujuan ditetapkan, maka langkah selanjutnya yaitu formulasi model matematik.  Formulasi model matematik ada 3 tahap yaitu: a. Menentukan variable yang tidak diketahui dan dinyatakan dengan simbol b. Membentuk fungsi tujuan yang ditunjukkan sebagai suatu hubungan linear dari variable keputusan (memaksimumkan atau meminimumkan) c. Menentukan semua kendala masalah tersebut dan mengekspresikannya dalam persamaan, pertidaksamaan atau fungsi


Page 3

Contoh:  Suatu perusahaan menghasilkan dua barang, boneka dan mobil-mobilan. Harga masing-masing barang dan kebutuhan sumber daya terlihat pada tabel berikut. Disamping itu menurut bagian penjualan, permintaan boneka tidak akan melebihi 4 unit. Sumber daya Bahan Mentah Buruh Harga per unit Tentukan: a. Variable

Boneka 1 6 4

Mobil-mobilan 2 6 5

b. Fungsi tujuan

d. Formasi model matematik

Kapasitas 10 36

c. Sistem kendala

e. Solusi optimum

Soal – soal: 1. Sebuah Firma memproduksi sendiri rak buku dalam dua model yaitu model A dan model B. Produksi rak buku dibatasi oleh persediaan material (papan kualitas tinggi) dan waktu yang terbatas mesin pemroses. Tiap unit A memerlukan 3 𝑚2 papan dan tiap unit B memerlukan 4 𝑚2 papan. Firma memperoleh 1700 𝑚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 sebesar $2 dan tiap unit B sebesar $4. Bagaimana formasi model matematik program linier dari kasus di atas? 2. Pabrik ban sepeda memproduksi ban luar dan ban dalam. Ban luar diproses melalui 3 unit mesin, sedangkan ban dalam hanya diproses di dua mesin. Setiap ban luar diproses secara berurutan selama 2 menit di mesin I, 8 menit di mesin II dan 10 menit di mesin III. Sedangkan setiap ban dalam diproses selama 5 menit di mesin I, kemudian 4 menit di mesin II. Sumbangan keuntungan dari setiap unit ban luar dan ban dalam masing-masing Rp 400,00 dan Rp 300,00. Kapasitas pengoperasian masing-masing mesin setiap harinya 800 menit. Jika setiap ban yang diproduksi senantiasa laku terjual. Tentukan model program liniernya, agar keuntungan maksimum!


Page 4

3. PT bank kita yang bergerak dalam usaha pembuatan makanan ternak merencanakan produksi sebesar 200 kg per bulan. Untuk mendapatkan makanan ternak nyang berkualitas tinggi, sesuai dengan persyaratan yang diminta konsumen, telah ditemukan komposisi campuran yaitu: (a) paling sedikit 8% kalsium tetapi tidak boleh melebihi 10%, (b) paling sedikit 30% protein, (c) paling banyak 8% lemak. Untuk memperoleh ketiga jenis bahan tersebut akan diolah dari jagung dan kacang kedelai. Kandungan gizi yang terdapat dalam kedua jenis bahan tersebut sebagai berikut: Uraian Kalsium Protein Lemak

Jagung 0,20 0,15 0,05

Per – kg bahan Kedelai 0,05 0,40 0,05

Harga setiap kg jagung Rp 300,00 dan kacang kedelai Rp 800,00. Bagaimana rumusan model matematik program linier dari kasus di atas.


Page 5

BAB II METODE GRAFIK 2.1. Pengertian Pada prinsipnya setiap persoalan program linier dapat dipecahkan atau menghasilkan penyelesaian. Penyelesaian dengan metode grafik sebagai berikut:  Masalah program linier diilustrasikan dan dipecahkan dengan metode grafik, apabila hanya memiliki dua variabel keputusan  Langkah-langkah penyelesaian: a. Gambarkan fungsi kendala dalam bentuk persamaan pada sumbu cartesius b. Tentukan daerah solusi layak (feasible solution) atau area layak (feasible region) dengan memperhatikan tanda ketidaksamaan fungsi kendala c. Gambarkan fungsi tujuan, geser garis tersebut ke lokasi titik solusi optimal d. Selesaikan persamaan-persamaan pada titik solusi untuk menentukan solusi optimal Solusi optimal dapat menggunakan dua pendekatan yaitu pendekatan garis profit (isoprofit line) atau titik sudut (corner point) Dalam program linier dengan metode grafik sering dijumpai permasalahan secara teknis, sebagai berikut: a. Infeasibility, yaitu suatu kondisi dimana tidak area layak yang memenuhi semua kendala. b. Unboundedness, yaitu suatu kondisi dimana area layak tidak terbatas. c. Redundancy, misalnya apabila bagian marketing tidak bisa menjual lebih dari 4 unit maka disebut redundant d. Alternative Optima, yaitu situasi dimana terdapat lebih dari satu solusi optimal.


Page 6

Beberapa contoh kasus khusus pada program linier: 1. Solusi tidak layak, jika tidak ada satu titikpun yang memenuhi fungsi kendala. Contoh:

Max

𝑧 = 5𝑥1 + 3𝑥2

Terhadap

4𝑥1 + 2𝑥2 ≤ 8 , 𝑥1 ≥ 3 , 𝑥2 ≥ 3 , 𝑥1 , 𝑥2 ≥ 0

2. Solusi optimum lebih dari satu (multiple optimum solution), jika fungsi tujuan sejajar dengan fungsi kendala yang menghubungkan titik ekstrem. Contoh:

Max

𝑧 = 4𝑥1 + 4𝑥2

Terhadap 𝑥1 + 6𝑥2 ≤ 10 , 6𝑥1 + 6𝑥2 ≤ 10 ,

𝑥1 ≤ 4 , 𝑥1 , 𝑥2 ≥ 0

3. Tidak memiliki solusi optimum, jika solusi layak tidak terbentuk dan fungsi kendala tidak dapat membatasi peningkatan nilai fungsi tujuan baik kearah positif maupun negatif. . 2.2. Masalah Maksimisasi Maksimisasi dapat berupa memaksimalkan keuntungan atau hasil. Contoh: 1.

Maksimum

𝑧 = 4𝑥 + 5𝑦

Dengan batasan

3𝑥 + 2𝑦 ≤ 12 , 3𝑥 + 4𝑦 ≤ 18 , 𝑥 , 𝑦 ≥ 0

a.

Gambarlah grafik sistem pertidaksamaan!

b.

Tentukan nilai maksimum dan koordinat titik yang menunjukkan nilai maksimum

2.

PT LAQUNATEKSTIL memiliki sebuah pabrik yang akan memproduksi 2 jenis produk, yaitu kain sutera dan kain wol. Untuk memproduksi kedua produk diperlukan bahan baku benang sutera, bahan baku benang wol dan tenaga kerja. Maksimum penyediaan benang sutera adalah 60 kg per hari, benang wol 30 kg per hari dan tenaga kerja 40 jam per hari. Kebutuhan setiap unit produk akan bahan baku dan jam tenaga kerja dapat dilihat dalam tabel berikut:


Page 7

Jenis bahan baku Kg bahan baku & Jam tenaga kerja dan tenaga kerja Kain sutera Kain wol Benang sutera 2 3 Benang wol 2 Tenaga kerja 2 1

Maksimum penyediaan 60 kg 30 kg 40 jam

Kedua jenis produk memberikan keuntungan sebesar Rp 40 juta untuk kain sutera dan Rp 30 juta untuk kain wol. Masalahnya adalah bagaimana menentukan jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar keuntungan yang diperoleh bisa maksimal? Langkah – langkah: a) Menentukan variablel

𝑥 ∶ 𝑘𝑎𝑖𝑛 𝑠𝑢𝑡𝑒𝑟𝑎 𝑑𝑎𝑛 𝑦 ∶ 𝑘𝑎𝑖𝑛 𝑤𝑜𝑙

b) Fungsi tujuan

𝑧𝑚𝑎𝑥 = 40𝑥 + 30𝑦

c) Fungsi kendala/batasan

2𝑥 + 3𝑦 ≤ 60

(𝑏𝑒𝑛𝑎𝑛𝑔 𝑠𝑢𝑡𝑒𝑟𝑎)

2𝑦 ≤ 30

(𝑏𝑒𝑛𝑎𝑛𝑔 𝑤𝑜𝑙)

2𝑥 + 𝑦 ≤ 40

(𝑡𝑒𝑛𝑎𝑔𝑎 𝑘𝑒𝑟𝑗𝑎)

𝑥≥0 ,

𝑦≥0

d) Menggambar grafik e) Untuk mendapatkan solusi optimal yaitu mencari nilai z pada setiap titik ekstrim dengan memaksimumkan keuntungan.

2.3. Masalah Minimisasi Minimisasi dapat berupa meminimumkan biaya produksi. Solusi optimal tercapai pada saat garis fungsi tujuan menyinggung daerah fasible yang terdekat dengan titik origin. Contoh: 1. Minimum Dengan batasan

𝑧 = 5𝑥 + 3𝑦 2𝑥 + 𝑦 ≥ 3 ,

𝑥+𝑦 ≥2,

𝑥 ,𝑦 ≥ 0

a. Gambarlah grafik sistem pertidaksamaan! b. Tentukan nilai minimum dan koordinat titik yang menunjukkan nilai minimum!


Page 8

2. Perusahaan makanan ROYAL merencanakan untuk membuat dua jenis makanan yaitu Royal Bee dan Royal Jelly. Kedua jenis makanan tersebut mengandung vitamin dan protein. Royal Bee paling sedikit diproduksi 2 unit dan Royal Jelly paling sedikit diproduksi 1 unit. Tabel berikut menunjukkan jumlah vitamin dan protein dalam setiap jenis makanan: Jenis makanan Royal Bee Royal Jelly minimum kebutuhan Bagaimana

Vitamin (unit) 2 1 8

menentukan

Protein (unit) 2 3 12

kombinasi

kedua

Biaya per unit (ribu rupiah) 100 80

jenis

makanan

agar

meminimumkan biaya produksi? Langkah – langkah: a) Menentukan variable

𝑥 ∶ 𝑟𝑜𝑦𝑎𝑙 𝑏𝑒𝑒 𝑑𝑎𝑛 𝑦 ∶ 𝑟𝑜𝑦𝑎𝑙 𝑗𝑒𝑙𝑙𝑦

b) Fungsi tujuan

𝑧𝑚𝑖𝑛 = 100𝑥 + 80𝑦

c) Fungsi kendala/batasan

2𝑥 + 𝑦 ≥ 8 2𝑥 + 3𝑦 ≥ 12

(𝑣𝑖𝑡𝑎𝑚𝑖𝑛) (𝑝𝑟𝑜𝑡𝑒𝑖𝑛)

𝑥≥2 , 𝑦≥1 d) Menggambar grafik e) Untuk mendapatkan solusi optimal yaitu mencari nilai z pada setiap titik ekstrim dengan meminimumkan biaya produksi. Soal – soal: 1. Maksimum Dengan batasan

𝑧 = 40𝑥 + 30𝑦 2𝑥 + 3𝑦 ≤ 60 , 2𝑦 ≤ 30 , 2𝑥 + 𝑦 ≤ 40 , 𝑥 , 𝑦 ≥ 0

a.


b.



Page 9

2. Minimum Dengan batasan

𝑧 = 20𝑥 + 30𝑦 2𝑥 + 4𝑦 ≥ 8 , 2𝑥 + 𝑦 ≥ 4 ,

𝑥 + 3𝑦 ≥ 6 ,

𝑥 ,𝑦 ≥ 0

a. Gambarlah grafik sistem pertidaksamaan! b. Tentukan nilai minimum dan koordinat titik yang menunjukkan nilai minimum! 3. Maksimum Dengan kendala

𝑧 = 30.000𝑥 + 50.000𝑦 3𝑥 + 2𝑦 ≤ 150 , 5𝑥 + 8𝑦 ≤ 400 , 𝑥 ≥ 20 , 𝑥 , 𝑦 ≥ 0

a.


b.


4. Suatu persoalan program linier dirumuskan sebagai berikut: Maksimumkan

𝑧 = 3𝑥 + 4𝑦

Dengan kendala

2𝑥 + 2𝑦 ≤ 80 ,

2𝑥 + 4𝑦 ≤ 120 ,

𝑥 ,𝑦 ≥ 0

a. Gambarlah daerah yang memenuhi system pertidaksamaan/pembatas! b. Carilah koordinat titik yang menunjukkan nilai maksimum fungsi tujuan! c. Tentukan nilai maksimumnya 5. Perhatikan persoalan program linier. Fungsi tujuan

𝑇 = 400.000𝑥 + 300.000𝑦 (minimumkan)

Pembatas

𝑥 ≥ 4.000 ,

𝑦 ≥ 5.000 ,

𝑥 + 𝑦 ≤ 10.000

a. Gambarlah daerah yang memenuhi system pertidaksamaan! b. Tentukan nilai optimal fungsi tujuan!


Page 10

BAB III METODE ALJABAR

3.1. Pengertian Program linier dengan dengan metode aljabar yaitu menyelesaikan permasalahan dalam perhitungan matematika agar mendapatkan nilai yang optimum (maksimum atau minimum). Secara umum model matematika yang diselesaikan merupakan pertidaksamaan dan metode yang digunakan umtuk mengubah ketaksamaan menjadi kesamaan yaitu metode aljabar. Adapun langkah-langkah dalam metode aljabar dengan melakukan standarisasi ketidaksamaan menjadi kesamaan, yaitu: 1. Memasukkan unsur variable semua ke ruas kiri fungsi kendala. 2. Unsur fungsi kendala bertanda ≤ dilakukan dengan penambahan slack variables. Slack variables yaitu suatu variable yang ditambahkan disebelah kiri tanda ketidaksamaan agar ketidaksamaan menjadi persamaan. 3. Unsur fungsi kendala bertanda ≥ dilakukan dengan pengurangan atau surplus variables. Surplus variables yaitu variable yang dikurangkan di dalam suatu ketidaksamaan agar supaya menjadi persamaan. 3.2. Menentukan Banyak Persamaan Pada umumnya, kalau ada n variable yaitu 𝑥1 , 𝑥2 , … , 𝑥𝑗 , … , 𝑥𝑛 , akan tetapi hanya ada m persamaan, maka dapat diperoleh sebanyak K persamaan, dengan rumus: 𝑛!

𝐾 = (𝑛−𝑚)!𝑚! dimana

𝑛 ∶ 𝑏𝑎𝑛𝑦𝑎𝑘𝑛𝑦𝑎 𝑣𝑎𝑟𝑖𝑎𝑏𝑒𝑙 dan 𝑚 ∶ 𝑏𝑎𝑛𝑦𝑎𝑘𝑛𝑦𝑎 𝑝𝑒𝑟𝑠𝑎𝑚𝑎𝑎𝑛


Page 11

Ada beberapa istilah dalam penyelesaian program linier dengan metode aljabar, yaitu: 1. Variable yang diperoleh dari m persamaan disebut variable dasar (basic variables), sedangkan pemecahannya disebut pemecahan dasar (basic solution) 2. Pemecahan yang memenuhi semua syarat pembatasan disebut pemecahan fisibel (feasible solution) 3. Pemecahan yang menghasilkan paling sedikit satu variable yang negatif disebut tidak fisibel (not feasible) 4. Pemecahan dasar fisibel yang memenuhi optimum disebut pemecahan optimal. Contoh: 1.

Menentukan 𝑥1 𝑑𝑎𝑛 𝑥2 Fungsi

𝑧 = 8𝑥1 + 6𝑥2 (maksimum)

Pembatas

4𝑥1 + 2𝑥2 ≤ 60 ,

2𝑥1 + 4𝑥2 ≤ 48 ,

𝑥1 , 𝑥2 ≥ 0

Cara: Persamaan dirubah dulu menjadi standar yaitu slack variables dengan memasukkan variable yang harus ditambahkan di dalam ketidaksamaan agar menjadi persamaan, sehingga persamaan akan berubah menjadi: a.

Menentukan

𝑥1 , 𝑥2 , 𝑥3 , 𝑥4

b.

Fungsi

𝑧 = 8𝑥1 + 6𝑥2 + 0𝑥3 + 0𝑥4 (maksimum) 4𝑥1 + 2𝑥2 + 𝑥3 = 60 ,

c. Pembatas

2𝑥1 + 4𝑥2 + 𝑥4 = 48

𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0, 𝑥4 ≥ 0 d.

Menentukan banyaknya solusi dengan menggunakan rumus: 𝑛!

4!

𝐾 = (𝑛−𝑚)!𝑚! e.

4!

𝐾 = (4−2)!2! = 2!2! = 6 𝑠𝑜𝑙𝑢𝑠𝑖

Mengenolkan dua variable, dengan 6 solusi yaitu:  𝒙𝟏 = 𝒙𝟐 = 𝟎

4𝑥1 + 2𝑥2 + 𝑥3 = 60 2𝑥1 + 4𝑥2 + 𝑥4 = 48


𝑥3 = 60 𝑥4 = 48

Page 12

Diperoleh: 𝑧1 = 8𝑥1 + 6𝑥2 + 0𝑥3 + 0𝑥4 𝑧1 = 8(0) + 6(0) + 0(60) + 0(48)  𝒙𝟏 = 𝒙𝟑 = 𝟎

𝑧1 = 0 (tidak ada penjualan)

4𝑥1 + 2𝑥2 + 𝑥3 = 60 2𝑥1 + 4𝑥2 + 𝑥4 = 48

𝑥2 = 30

𝑥4 = −78 (tidak fisibel)

Diperoleh: 𝑧2 tidak dihitung, karena 𝑥4 negatif maka pemecahan tidak fisibel  𝒙𝟏 = 𝒙𝟒 = 𝟎

4𝑥1 + 2𝑥2 + 𝑥3 = 60

𝑥3 = 36

2𝑥1 + 4𝑥2 + 𝑥4 = 48

𝑥2 = 12

Diperoleh: 𝑧3 = 8𝑥1 + 6𝑥2 + 0𝑥3 + 0𝑥4 𝑧3 = 8(0) + 6(12) + 0(36) + 0(0)  𝒙𝟐 = 𝒙𝟑 = 𝟎

𝑧3 = 72

4𝑥1 + 2𝑥2 + 𝑥3 = 60

𝑥1 = 15

2𝑥1 + 4𝑥2 + 𝑥4 = 48

𝑥4 = 18

Diperoleh: 𝑧4 = 8𝑥1 + 6𝑥2 + 0𝑥3 + 0𝑥4 𝑧4 = 8(15) + 6(0) + 0(0) + 0(18)  𝒙𝟐 = 𝒙𝟒 = 𝟎

𝑧4 = 120

4𝑥1 + 2𝑥2 + 𝑥3 = 60


2𝑥1 + 4𝑥2 + 𝑥4 = 48

𝑥4 = 24

Diperoleh: 𝑧5 tidak dihitung, karena 𝑥3 negatif maka pemecahan tidak fisibel  𝒙𝟑 = 𝒙𝟒 = 𝟎

4𝑥1 + 2𝑥2 + 𝑥3 = 60

𝑥1 = 12

2𝑥1 + 4𝑥2 + 𝑥4 = 48

𝑥2 = 6

Diperoleh: 𝑧6 = 8𝑥1 + 6𝑥2 + 0𝑥3 + 0𝑥4 𝑧6 = 8(12) + 6(6) + 0(0) + 0(0)

𝑧6 = 132 (terbesar = maksimum)


Page 13

Oleh

𝑧6

karena

yang

memberikan

nilai

tujuan

terbesar

maka

𝑧6 = 𝑧 𝑚𝑎𝑘𝑠𝑖𝑚𝑢𝑚 = 𝑧𝑚𝑎𝑘𝑠 Jadi pemecahan dasar ke 6 meruapakn pemecahan yang optimal. Jumlah hasil penjualan maksimum sebesar 132. Keputusan yang harus dibuat oleh pemilik perusahaan yaitu bahwa barang A dan B masing-masing harus diproduksi sebesar 12 satuan dan 6 satuan. 2.

Menentukan 𝑥1 𝑑𝑎𝑛 𝑥2 Fungsi

𝑧 = 5𝑥1 + 3𝑥2 (minimum)

Pembatas

2𝑥1 + 𝑥2 ≥ 2 ,

𝑥1 + 𝑥2 ≥ 0 ,

𝑥1 , 𝑥2 ≥ 0

Cara: Persamaan dirubah dulu menjadi standar yaitu surplus variables dengan memasukkan variable yang harus dikurangkan di dalam ketidaksamaan agar menjadi persamaan, sehingga persamaan akan berubah menjadi: a. Menentukan

𝑥1 , 𝑥2 , 𝑥3 , 𝑥4

b. Fungsi

𝑧 = 5𝑥1 + 3𝑥2 − 0𝑥3 − 0𝑥4 (minimum)

c. Pembatas

2𝑥1 + 𝑥2 − 𝑥3 = 2 ,

𝑥1 + 𝑥2 − 𝑥4 = 0

𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0, 𝑥4 ≥ 0 d. Menentukan banyaknya solusi dengan menggunakan rumus: 𝑛!

𝐾 = (𝑛−𝑚)!𝑚!

4!

4!

𝐾 = (4−2)!2! = 2!2! = 6 𝑠𝑜𝑙𝑢𝑠𝑖

e. Mengenolkan dua variable, dengan 6 solusi yaitu:  𝒙 𝟏 = 𝒙𝟐 = 𝟎

2𝑥1 + 𝑥2 − 𝑥3 = 2


𝑥1 + 𝑥2 − 𝑥4 = 0


Diperoleh: 𝑧1 tidak dihitung, karena 𝑥3 𝑑𝑎𝑛 𝑥4 negatif maka pemecahan tidak fisibel.  𝒙 𝟏 = 𝒙𝟑 = 𝟎

2𝑥1 + 𝑥2 − 𝑥3 = 2 𝑥1 + 𝑥2 − 𝑥4 = 0


𝑥2 = 3 𝑥4 = 1

Page 14

Diperoleh: 𝑧2 = 5𝑥1 + 3𝑥2 − 0𝑥3 − 0𝑥4 𝑧2 = 5(0) + 3(3) − 0(0) − 0(1)  𝒙 𝟏 = 𝒙𝟒 = 𝟎

2𝑥1 + 𝑥2 − 𝑥3 = 2

𝑧2 = 9 𝑥3 = −3 (tidak fisibel)

𝑥1 + 𝑥2 − 𝑥4 = 0

𝑥2 = 2

Diperoleh: 𝑧3 tidak dihitung, karena 𝑥3 negatif maka pemecahan tidak fisibel.  𝒙 𝟐 = 𝒙𝟑 = 𝟎

3

2𝑥1 + 𝑥2 − 𝑥3 = 2

𝑥1 = 2

𝑥1 + 𝑥2 − 𝑥4 = 0


Diperoleh: 𝑧4 tidak dihitung, karena 𝑥4 negatif maka pemecahan tidak fisibel.  𝒙𝟐 = 𝒙𝟒 = 𝟎

2𝑥1 + 𝑥2 − 𝑥3 = 2

𝑥3 = 1

𝑥1 + 𝑥2 − 𝑥4 = 0

𝑥1 = 2

Diperoleh: 𝑧5 = 5𝑥1 + 3𝑥2 − 0𝑥3 − 0𝑥4 𝑧5 = 5(2) + 3(0) − 0(1) − 0(0)  𝒙𝟑 = 𝒙𝟒 = 𝟎

𝑧5 = 10

2𝑥1 + 𝑥2 − 𝑥3 = 2

𝑥2 = 1

𝑥1 + 𝑥2 − 𝑥4 = 0

𝑥1 = 1

Diperoleh: 𝑧6 = 5𝑥1 + 3𝑥2 − 0𝑥3 − 0𝑥4 𝑧6 = 5(1) + 3(1) − 0(0) − 0(0)

𝑧6 = 8 (terkecil = minimum)

𝑧6 = 𝑧 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 = 𝑧𝑚𝑖𝑛 karena merupakan nilai tujuan yang terkecil apabila dibandingkan dengan nilai tujuan yang lain. Pemecahan optimal memberikan nilai 𝑧 = 8 dengan 𝑥1 = 𝑥2 = 1


Page 15

Soal-soal: 1. Maksimum

𝑧 = 4𝑥1 + 5𝑥2

Dengan kendala 3𝑥1 + 2𝑥2 ≤ 12 ,

3𝑥1 + 4𝑥2 ≤ 18 ,

untuk 𝑥1 , 𝑥2 ≥ 0

Tentukan solusi dan nilai optimum dengan metode aljabar! 2. Minimumkan Dengan pembatas

𝑧 = 1,5𝑥1 + 2,5𝑥2 𝑥1 + 3𝑥2 ≥ 3 ,

𝑥1 + 𝑥2 ≥ 2 ,

𝑥1 , 𝑥2 ≥ 0

Tentukan solusi dan nilai optimum dengan metode aljabar! 3. Maksimum

𝑧 = 20𝑥1 + 30𝑥2

Dengan pembatas 2𝑥1 + 4𝑥2 ≤ 8 ,

2𝑥1 + 𝑥2 ≤ 4 , 𝑥1 , 𝑥2 ≥ 0

Tentukan solusi dan nilai optimum dengan metode aljabar! 4. Maksimum Dengan kendala

𝑧 = 6𝑥 + 2𝑦 4𝑥 + 5𝑦 ≤ 20 ,

3𝑥 + 𝑦 ≤ 6 ,

𝑥1 , 𝑥2 ≥ 0

Tentukan solusi dan nilai optimum dengan metode aljabar!


Page 16

BAB IV METODE SIMPLEKS

4.1. Pengertian Metode simpleks merupakan suatu prosedur aljabar yang bukan secara grafik untuk mencari nilai optimum dari fungsi tujuan dalam persoalan optimasi yang terkendala. Penyelesaian program linier dalam menentukan nilai optimum yang memiliki dua variable atau lebih dengan menggunakan metode simpleks. Untuk mencari nilai optimum dengan menggunakan metode simpleks dilakukan proses pengulangan (iterasi) dimulai dari penyelesaian dasar awal yang layak (feasible) hingga penyelesaian dasar akhir yang layak dimana nilai dari fungsi tujuan telah optimum, sehingga proses pengulangan (iterasi) tidak dapat dilakukan lagi. Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks, diantaranya : 1. Iterasi yaitu tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya. 2. Variable non basis yaitu variable yang nilainya diatur menjadi nol pada sembarang iterasi. Dalam terminologi umum, jumlah variable non basis selalu sama dengan derajat bebas dalam sistem persamaan. 3. Variable basis merupakan variable yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal, variable basis merupakan slack variable (jika fungsi kendala merupakan pertidaksamaan ≤) atau variable buatan (jika fungsi kendala menggunakan pertidaksamaan ≥ atau =). Secara umum, jumlah variable 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.


Page 17

5. Slack Variable adalah variable yang ditambahkan ke model matematik kendala untuk mengkonversikan pertidaksamaan ≤ menjadi persamaan (=). Penambahan variable ini terjadi pada tahap inisialisasi. Pada solusi awal, slack variable akan berfungsi sebagai variabel basis. 6. Surplus Variable adalah variable yang dikurangkan dari model matematik kendala untuk mengkonversikan pertidaksamaan ≥ menjadi persamaan (=). Penambahan ini terjadi pada tahap inisialisasi. Pada solusi awal, surplus variable tidak dapat berfungsi sebagai variable basis. 7. Variable buatan adalah variable yang ditambahkan ke model matematik kendala dengan bentuk ≥ atau = untuk difungsikan sebagai variabel basis awal. Penambahan variable ini terjadi pada tahap inisialisasi. Variable ini harus bernilai 0 pada solusi optimal, karena kenyataannya variabel ini tidak ada. Variable hanya ada di atas kertas. 8. Kolom Kerja/Kolom Kunci/Kolom Pivot adalah kolom yang memuat variable masuk. Koefisien pada kolom ini akan menjadi pembagi nilai kanan untuk menentukan baris kerja. 9. Baris Kerja/Baris Kunci/Kolom Pivot adalah salah satu baris dari antara variable basis yang memuat variable keluar. 10. Elemen Kerja/Elemen Kunci/Elemen Pivot adalah elemen yang terletak pada perpotongan kolom dan baris pivot. Elemen pivot akan menjadi dasar perhitungan untuk tabel simpleks berikutnya. 11. Variable masuk adalah variable yang terpilih untuk menjadi variable basis pada iterasi berikutnya. Variable masuk dipilih satu dari antara variable non basis pada setiap iterasi. Variable ini pada iterasi berikutnya akan bernilai positif. 12. Variable keluar adalah variable yang keluar dari variable basis pada iterasi berikutnya dan digantikan oleh variable masuk. Variable keluar dipilih satu dari antara variable basis pada setiap iterasi. Variable ini pada iterasi berikutnya akan bernilai nol.


Page 18

4.2. BENTUK BAKU Pertama sekali sebelum melakukan perhitungan iteratif untuk menentukan solusi optimum, bentuk umum program linier dirubah ke dalam bentuk baku terlebih dahulu. Bentuk baku dalam metode simpleks yaitu mengubah persamaan kendala ke dalam bentuk sama dengan dan setiap fungsi kendala harus diwakili oleh satu variable basis awal. Variable basis awal menunjukkan status sumber daya pada kondisi sebelum ada aktivitas yang dilakukan. Dengan kata lain, variable keputusan semuanya masih bernilai nol dan meskipun fungsi kendala pada bentuk umum pemrograman linier sudah dalam bentuk persamaan, fungsi kendala tersebut masih harus tetap berubah. Dalam metode simpleks, ada beberapa hal yang harus diperhatikan dalam membuat bentuk baku, yaitu : 1. Fungsi kendala dengan pertidaksamaan ≤ dalam bentuk umum, dirubah menjadi persamaan (=) dengan menambahkan satu slack variable. 2. Fungsi kendala dengan pertidaksamaan ≥ dalam bentuk umum, dirubah menjadi persamaan (=) dengan mengurangkan satu surplus variable. 3. Fungsi kendala dengan persamaan dalam bentuk umum, ditambahkan satu artificial variable (variabel buatan). Contoh: 1. Perhatikan kasus A berikut : Minimumkan 𝑧 = 2𝑥1 + 5,5𝑥2 Kendala : 𝑥1 + 𝑥2 = 90 0.001𝑥1 + 0.002𝑥2 ≤ 0.9 0.09𝑥1 + 0.6𝑥2 ≥ 27 0.02𝑥1 + 0.06𝑥2 ≤ 4.5 𝑥1 , 𝑥2 ≥ 0


Page 19

Bentuk di atas adalah bentuk umum pemrograman liniernya. Kedalam bentuk baku, model matematik tersebut akan berubah menjadi: Minimumkan

𝑧 = 2𝑥1 + 5,5𝑥2 + 𝟎𝒔𝟏 + 𝟎𝒔𝟐 − 𝟎𝒔𝟑 + 𝟎𝒔𝟒 + 𝟎𝒔𝟓

Kendala : 𝑥1 + 𝑥2 + 𝒔𝟏 = 90 0.001𝑥1 + 0.002𝑥2 + 𝒔𝟐 = 0.9 0.09𝑥1 + 0.6𝑥2 − 𝒔𝟑 + 𝒔𝟒 = 27 0.02𝑥1 + 0.06𝑥2 + 𝒔𝟓 = 4.5 𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 , 𝑠4 , 𝑠5 ≥ 0 Fungsi kendala pertama mendapatkan variable buatan (𝒔𝟏 ), karena bentuk umumnya sudah menggunakan bentuk persamaan. Fungsi kendala kedua dan kelima mendapatkan slack variables (𝒔𝟐 𝒅𝒂𝒏 𝒔𝟓 ) karena bentuk umumnya menggunakan

pertidaksamaan

≤,

sedangkan

fungsi

kendala

ketiga

mendapatkan surplus variables (𝒔𝟑 ) dan variabel buatan (𝒔𝟒 ) karena bentuk umumnya menggunakan pertidaksamaan ≥. 2. Perhatikan kasus B berikut ini : Maksimumkan

𝑧 = 4𝑥1 + 6𝑥2

Kendala : 5𝑥1 + 2𝑥2 ≤ 300 3𝑥1 + 10𝑥2 ≤ 300 4𝑥1 + 8𝑥2 ≤ 300 𝑥1 , 𝑥2 ≥ 0 Bentuk di atas juga merupakan bentuk umum. Perubahan ke dalam bentuk baku hanya membutuhkan variabel slack, karena semua fungsi kendala menggunakan bentuk pertidaksamaan ≤ dalam bentuk umumnya.


Page 20

Bentuk bakunya adalah sebagai berikut: 𝑧 = 4𝑥1 + 6𝑥2 + 𝟎𝒔𝟏 + 𝟎𝒔𝟐 + 𝟎𝒔𝟑

Maksimumkan Kendala :

5𝑥1 + 2𝑥2 + 𝒔𝟏 = 300 3𝑥1 + 10𝑥2 + 𝒔𝟐 = 300 4 + 8𝑥2 + 𝒔𝟑 = 300 𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0 𝒔𝟏 , 𝒔𝟐 , 𝒔𝟑

merupakan slack variables.

4.3. TABEL SIMPLEKS Bentuk baku yang sudah diperoleh, harus dibuat dalam bentuk tabel. Semua variable yang bukan variable basis mempunyai solusi (nilai kanan) sama dengan nol dan koefisien variable basis pada baris tujuan harus sama dengan nol. Oleh karena itu harus membedakan pembentukan tabel awal berdasarkan variable basis awal dan hanya akan memperhatikan fungsi kendala yang menggunakan slack variable dalam bentuk bakunya. Tabel simpleks sebagai berikut: 𝒄𝒋 CB

VDB

𝒂𝒋 𝒃𝒊

𝒄𝟏

𝒄𝟐

...

𝒄𝒋

...

𝒄𝒏

𝒂𝟏

𝒂𝟐

...

𝒂𝒋

...

𝒂𝒏

𝑪𝑩𝟏

𝒔𝟏

𝒃𝟏

𝒂𝟏𝟏

𝒂𝟏𝟐

...

𝒂𝟏𝒋

...

𝒂𝟏𝒏

𝑪𝑩𝟐

𝒔𝟐

𝒃𝟐

𝒂𝟐𝟏

𝒂𝟐𝟐

...

𝒂𝟐𝒋

...

𝒂𝟐𝒏

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

. . .

𝑪𝑩𝒋

𝒔𝒋

𝒃𝒊

𝒂𝒋𝟏

𝒂𝒋𝟐

𝒂𝒋𝒋

𝒂𝒋𝒏

0

𝒛𝒋 − 𝒄𝒋






Rasio

Page 21

Keterangan tabel: 1. CB yaitu menggambarkan koefisien ongkos relatif untuk variable dalam basis, pada mulanya koefisien itu bernilai nol. 2. VDB yaitu berisikan variable bayangan (slack variables), variable tersebut akan digantikan dengan variabel keputusan. 3. Kolom 𝒃𝒊 yaitu berisikan nilai variable konstanta di ruas kanan setiap batasan. 4. Kolom 𝒂𝒋 yaitu berisikan variable keputusan dan variable bayangan. 5. Kolom 𝒄𝒋 yaitu berisikan koefisien relatif dari fungsi tujuan dan kolom variable bayangan bernilai nol. 6. Baris 𝒛 yaitu berisikan hasil pengurangan 𝒛𝒋 − 𝒄𝒋 dan baris ini akan memberikan informasi tentang tujuan apakah sudah optimum atau belum. 7. Kolom rasio yaitu berisikan hasil bagi untuk menyatakan variabel yang akan menjadi baris kunci atau tidak. Langkah – langkah penyelesaian tabel simpleks sebagai berikut: 1. Merubah persoalan program linier ke dalam bentuk baku standar. 2. Masukkan semua nilai pada fungsi kendala ke dalam tabel simpleks. 3. Masukkan semua nilai pada fungsi tujuan ke dalam tabel simpleks pada baris 𝒛𝒋 − 𝒄𝒋 dengan menggunakan rumus 𝒛𝒋 − 𝒄𝒋 = 𝑪𝑩𝒂𝒋 − 𝒄𝒋 (rumus yang digunakan saat awal memasukkan semua nilai fungsi tujuan). 4. Menentukan kolom kerja/kolom kunci/kolom pivot:  Untuk persoalan maksimum keuntungan maka penentuan kolom kerja dalam baris zj − cj diambil nilai yang paling kecil atau paling negatif.  Untuk persoalan minimum biaya yang dirubah menjadi maksimum maka penentuan kolom kerja dalam baris zj − cj diambil nilai yang paling besar atau paling positif. 5. Menentukan baris kerja/baris kunci/baris pivot:  Menggunakan rumus atau perbandingan minimum dan bukan negatif. 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 = 𝑛𝑖𝑙𝑎𝑖 𝑝𝑎𝑑𝑎 𝑘𝑜𝑙𝑜𝑚 𝑏𝑖 : 𝑛𝑖𝑙𝑎𝑖 𝑝𝑎𝑑𝑎 𝑘𝑜𝑙𝑜𝑚 𝑘𝑒𝑟𝑗𝑎 (dapat dilihat pada kolom rasio, diambil nilai yang paling kecil)


Page 22

6. Mencari angka baru yang terdapat pada baris kunci.  Caranya yaitu membagi semua angka yang terdapat pada baris kerja dengan angka kerja.  Elemen kerja/elemen kunci/elemen pivot yaitu angka yang terdapat pada perpotongan baris kunci dengan kolom kunci. 7. Mencari angka baru pada baris yang lain (angka baris baru).  Caranya yaitu: 𝑎𝑛𝑔𝑘𝑎 𝑏𝑎𝑟𝑖𝑠 𝑏𝑎𝑟𝑢 = 𝑛𝑖𝑙𝑎𝑖 𝑏𝑎𝑟𝑖𝑠 𝑙𝑎𝑚𝑎 − 𝑝𝑒𝑟𝑘𝑎𝑙𝑖𝑎𝑛 𝑘𝑜𝑒𝑓𝑖𝑠𝑖𝑒𝑛 𝑝𝑎𝑑𝑎 𝑘𝑜𝑙𝑜𝑚 𝑘𝑢𝑛𝑐𝑖 𝑑𝑒𝑛𝑔𝑎𝑛 𝑎𝑛𝑔𝑘𝑎 𝑏𝑎𝑟𝑢 𝑏𝑎𝑟𝑖𝑠 𝑘𝑢𝑛𝑐𝑖

8. Apabila kondisi optimum belum tercapai maka ulangi kembali langkah ke 4 sampai langkah ke 7 sehingga pada baris 𝒛𝒋 − 𝒄𝒋 tidak ada lagi yang bernilai negatif. Penggunaan tabel simpleks, misalnya gunakan kasus B di atas dengan bentuk baku yaitu: Maksimumkan atau

𝑧 = 4𝑥1 + 6𝑥2 + 𝟎𝒔𝟏 + 𝟎𝒔𝟐 + 𝟎𝒔𝟑 𝑧 − 4𝑥1 − 6𝑥2 + 𝟎𝒔𝟏 + 𝟎𝒔𝟐 + 𝟎𝒔𝟑 = 𝟎

Kendala : 5𝑥1 + 2𝑥2 + 𝒔𝟏 = 300

5𝑥1 + 𝑥2 + 𝒔𝟏 + 𝟎 + 𝟎 = 300

3𝑥1 + 10𝑥2 + 𝒔𝟐 = 300

3𝑥1 + 10𝑥2 + 𝟎 + 𝒔𝟐 + 𝟎 = 300

4𝑥1 + 8𝑥2 + 𝒔𝟑 = 300

4𝑥1 + 8𝑥2 + 𝟎 + 𝟎 + 𝒔𝟑 = 300 𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0

𝒔𝟏 , 𝒔𝟐 , 𝒔𝟑

merupakan slack variables.

maka tabel awal simpleks sebagai berikut: variabel bayangan konstanta sebelah kanan fungsi tujuan 𝒄𝒋 CB

VDB

0 0 0

𝒔𝟏 𝒔𝟐 𝒔𝟑 𝒛𝒋 − 𝒄𝒋

𝒂𝒋 𝒃𝒊 300 300 300 0

variabel fungsi tujuan

4

6

0

0

0

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝒔𝟑

5 3 4 -4

2 10 8 -6

1 0 0 0

0 1 0 0

0 0 1 0


Rasio

Page 23

4.4. Kesimpulan Tabel Simpleks Tabel simpleks merupakan bagian yang terpenting dalam mengambil keputusan, sehingga harus memperhatikan solusi optimal dalam variabel keputusan, yaitu melihat nilai pada kolom 𝒃𝒊 dengan variabel produk pada tabel optimal Contoh: 1. Selesaikan kasus berikut dengan metode simpleks: 𝑧 = 8𝑥1 + 9𝑥2 + 4𝑥3

Maksimum Kendala:

𝑥1 + 𝑥2 + 2𝑥3 ≤ 2 2𝑥1 + 3𝑥2 + 4𝑥3 ≤ 3 7𝑥1 + 6𝑥2 + 2𝑥3 ≤ 8 𝑥1 , 𝑥2 , 𝑥3 ≥ 0 Penyelesaian:  Langkah 1

merubah menjadi bentuk baku 𝑧 = 8𝑥1 + 9𝑥2 + 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3

Maksimum atau

𝑧 − 8𝑥1 − 9𝑥2 − 4𝑥3 + 0𝑠1 + 0𝑠2 + 0𝑠3 = 0

Kendala: 𝑥1 + 𝑥2 + 2𝑥3 + 𝑠1 = 2 2𝑥1 + 3𝑥2 + 4𝑥3 + 𝑠2 = 3 7𝑥1 + 6𝑥2 + 2𝑥3 + 𝑠3 = 8 𝑥1 , 𝑥2 , 𝑥3 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0  Langkah 2

menggunakan tabel simpleks 𝒄𝒋

CB

𝒂𝒋

VDB 𝒃𝒊

0 𝒔𝟏 0 𝒔𝟐 0 𝒔𝟑 𝒛𝒋 − 𝒄𝒋

2 3 8 0

8

9

4

0

0

0

𝒙𝟏

𝒙𝟐

𝒙𝟑

𝒔𝟏

𝒔𝟐

𝒔𝟑

1 2 7 -8

1 3 6 -9

2 4 2 -4

1 0 0 0

0 1 0 0

0 0 1 0


Rasio

Page 24

 Langkah 3

menentukan kolom kunci, baris kunci dan rasio

Nilai negatif terbesar ada pada kolom 𝒙𝟐 , maka kolom 𝒙𝟐 adalah kolom kunci (KK) Rasio pembagi kanan dengan kolom kunci adalah bersesuaian dengan baris 𝒔𝟐 maka baris 𝒔𝟐 adalah baris kunci (BK) dan 𝒔𝟐 merupakan variabel keluar. Elemen kunci adalah 3 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

8

9

4

0

0

0

𝒙𝟏

𝒙𝟐

𝒙𝟑

𝒔𝟏

𝒔𝟐

𝒔𝟑

0

𝒔𝟏

2

1

1

2

1

0

0

0

𝒔𝟐

3

2

3

4

0

1

0

0

𝒔𝟑

8

7

6

2

0

0

1

0

-8

-9

-4

0

0

0

𝒛𝒋 − 𝒄𝒋  Langkah 4

Rasio 2 =2 1 3 =1 3 8 4 = 6 3

iterasi I

Nilai yang dimiliki adalah nilai baris kerja baru yaitu baris 𝒙𝟐 (tabel di bawah ini). Semua nilai pada 𝒔𝟐 di tabel solusi awal dibagi dengan 3 (elemen kunci) 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

0

𝒔𝟏

9

𝒙𝟐

0

𝒔𝟑

1

8

9

4

0

0

0

𝒙𝟏

𝒙𝟐

𝒙𝟑

𝒔𝟏

𝒔𝟐

𝒔𝟑

2 3

1

4 3

0

1 3

0

4

0

1

Rasio

𝒛𝒋 − 𝒄𝒋 Perhitungan nilai baris, sebagai berikut: Baris Kunci Baru: 3

2

3

0

dibagi 3 1

𝟐 𝟑


1

𝟒 𝟑

0

𝟏 𝟑

0

Page 25

Baris 𝒛, yaitu: 0 baris lama koefisien KK pada baris baru baris 𝑧

-9

-8

-9

𝟐

(1

-4

0

𝟒

1

0

𝟏

9

-2

0

8

0

3

0) 0

2

1

1

2

1

0

0

𝟑

0

0

𝟑

𝟑

Baris 𝒔𝟏 , yaitu: baris lama koefisien KK pada baris baru baris 𝑠1

1

𝟐

(1

1

1

𝟒

1

𝟑

2

0

3

𝟏

0

𝟑

𝟑 1

1

−3

0

0

3

0) 0

Baris 𝒔𝟑 , yaitu: 8

7

6

2

1

baris lama koefisien KK pada baris baru baris 𝑠3

6

𝟐

(1

2

𝟒

1

𝟑

3

0

𝟑

0

-6

0

𝟏 𝟑

0) -

-2

1

maka tabel iterasi 1 sebagai berikut: 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

0

𝒔𝟏

1

9

𝒙𝟐

1

0 𝒔𝟑 𝒛𝒋 − 𝒄𝒋

2 9

8

9

4

0

0

0

𝒙𝟏

𝒙𝟐

𝒙𝟑

𝒔𝟏

𝒔𝟐

𝒔𝟑

1

−

1 3 2 3 3 -2

0 1 0 0


2 3 4 3 -6 8

0 0 0

1 3 1 3 -2 3

Rasio

0 0 1 0

Page 26

 Langkah 5

pemeriksaan tabel sudah optimal atau belum

Nilai baris 𝒛 di bawah variabel 𝒙𝟏 masih negatif, maka tabel belum optimal. Variabel masuk yaitu 𝒙𝟏 dan variabel keluar yaitu 𝒔𝟑 , sehingga diperoleh tabel berikut: 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

8

9

4

0

0

0

𝒙𝟏

𝒙𝟐

𝒙𝟑

𝒔𝟏

𝒔𝟐

𝒔𝟑

1 3

0

2 3

1

1 − 3

0

0

𝒔𝟏

1

9

𝒙𝟐

1

2 3

1

4 3

0

1 3

0

0

𝒔𝟑

2

3

0

-6

0

-2

1

9

-2

0

8

0

3

0


Rasio 1 =3 1 3 1 3 = 2 2 3 2 3

iterasi 2

Nilai yang dimiliki adalah nilai baris kerja baru yaitu baris 𝒙𝟏 (tabel berikut ini) Semua nilai pada 𝒔𝟑 di tabel solusi awal dibagi dengan 3 (elemen kunci) 𝒄𝒋 𝒂𝒋

CB VDB 𝒃𝒊 0 9

𝒔𝟏 𝒙𝟐

8

𝒙𝟏

2 3

8

9

4

0

0

0

𝒙𝟏

𝒙𝟐

𝒙𝟑

𝒔𝟏

𝒔𝟐

𝒔𝟑

1

0

-2

0

−

2 3

1 3

Rasio

𝒛𝒋 − 𝒄𝒋 Perhitungan nilai baris, sebagai berikut: Baris Kunci Baru: 2

3

0

-6

0

-2

1

1

0

-2

0

−𝟑

𝟐

𝟏

dibagi 3 𝟐 𝟑


𝟑

Page 27

Baris 𝒛, yaitu: 9

-2

0

8

0

3

0

1

0

-2

0

−𝟑 -

0

0

4

0

baris iterasi 1 𝟐

-2

(𝟑

𝟐

baris baru 31 3

Baris 𝒙𝟐 , yaitu:

2

1

4

1

3

)

𝟑

5

2

3

3

1

0

3

𝟏

0

3

baris iterasi 1 2

𝟐

(𝟑

3

0

-2

0

𝟐

𝟏

−𝟑

0

)

𝟑

baris baru

5

0

9

Baris 𝒔𝟏 , yaitu:

1

1

1

8

0

3

2

0

3

7

3

2

−9

9

1

1

−3

0

0

−𝟑

𝟐

𝟏

baris iterasi 1 1

𝟐

(𝟑

3

1

0

-2

)

𝟑

baris baru

7

0

9

4

0

1

−9

1

3

1

−9


𝒂𝒋

VDB 𝒃𝒊

0

𝒔𝟏

9

𝒙𝟐

8

𝒙𝟏


7 9 5 9 2 3 31 3

8

9

4

0

0

0

𝒙𝟏

𝒙𝟐

𝒙𝟑

𝒔𝟏

𝒔𝟐

𝒔𝟑

0

0

1

−

0

1

1

0

-2

0

0

0

4

0

4 3 8 3

0

1 9 7 9 2 − 3 5 3

Rasio

1 9 2 − 9 1 3 2 3 −

Tabel sudah optimal, sehingga perhitungan iterasi dihentikan.


Page 28

 Langkah 7

membaca tabel optimal

Dengan tabel optimal dapat disimpulkan dengan solusi optimal, yaitu: 2

5

𝑥1 = 3 , 𝑥2 = 9 ,

𝑥3 = 0

𝑑𝑎𝑛

𝑧=

31 3 31

artinya: agar keuntungan yang diperoleh maksimum sebesar $ 3 , maka sebaiknya perusahaan menghasilkan produk pertama sebesar 2 3

5

𝑢𝑛𝑖𝑡 dan produk kedua sebesar 9 𝑢𝑛𝑖𝑡

2. Selesaikan kasus berikut dengan metode simpleks: Minimumkan

𝑧 = 10𝑥1 + 15𝑥2

Kendala

𝑥1 + 𝑥2 ≥ 40 𝑥1 + 3𝑥2 ≥ 30 3𝑥1 + 𝑥2 ≥ 30 𝑥1 , 𝑥2 ≥ 0

Penyelesaian:  Langkah 1

merubah menjadi bentuk baku

Minimum

𝑧 = 10𝑥1 + 15𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3

Kendala

𝑥1 + 𝑥2 + 𝑠1 = 40 , 𝑥1 + 3𝑥2 +𝑠2 = 30 , 3𝑥1 + 𝑥2 + 𝑠3 = 30 𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0

Bentuk baku diatas masih minimum, sehingga harus dirubah ke bentuk maksimum Maksimumkan atau Kendala:

𝑧 = −10𝑥1 − 15𝑥2 − 0𝑠1 − 0𝑠2 − 0𝑠3 𝑧 + 10𝑥1 + 15𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3 = 0 𝑥1 + 𝑥2 − 𝑠1 = 40 𝑥1 + 3𝑥2 − 𝑠2 = 30 3𝑥1 + 𝑥2 − 𝑠3 = 30 𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 ≥ 0


Page 29

 Langkah 2 C B

menggunakan tabel simpleks

𝒄𝒋

VD B

𝒂𝒋 𝒃𝒊 40 30 30 0

0 𝒔𝟏 0 𝒔𝟐 0 𝒔𝟑 𝒛𝒋 − 𝒄𝒋

 Langkah 3

-10

-15

0

0

0

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝒔𝟑

1 1 3 10

1 3 1 15

-1 0 0 0

0 -1 0 0

0 0 -1 0

Rasio

menentukan kolom kunci, baris kunci dan rasio

Nilai positif terbesar ada pada kolom 𝒙𝟐 , maka kolom 𝒙𝟐 adalah kolom kunci (KK) Rasio pembagi kanan dengan kolom kunci adalah bersesuaian dengan baris 𝒔𝟐 maka baris 𝒔𝟐 adalah baris kunci (BK) dan 𝒔𝟐 merupakan variabel keluar. Elemen kunci adalah 3 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

-10

-15

0

0

0

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝒔𝟑

0

𝒔𝟏

40

1

1

-1

0

0

0

𝒔𝟐

30

1

3

0

-1

0

0

𝒔𝟑

30

3

1

0

0

-1

0

10

15

0

0

0


Rasio 40 = 40 1 30 = 10 3 30 = 30 1

iterasi I

Nilai yang dimiliki adalah nilai baris kerja baru yaitu baris 𝒙𝟐 (pada tabel di bawah)


Page 30

Semua nilai pada 𝒔𝟐 di tabel solusi awal dibagi dengan 3 (elemen kunci) 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

0

𝒔𝟏

-15

𝒙𝟐

10

-10

-15

0

0

0

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝒔𝟑

1 3

1

0

−

1 3

0

Rasio

0 𝒔𝟑 𝒛𝒋 − 𝒄𝒋 Perhitungan nilai baris, sebagai berikut: Baris Kunci Baru: 30

1

3

0

-1

0

1

0

−𝟑

0

15

0

0

0

1

0

−𝟑

dibagi 3 10

𝟏 𝟑

𝟏

Baris 𝒛, yaitu: 0 baris lama koefisien KK pada baris baru baris 𝑧

15

(10

10 𝟏 𝟑

𝟏

0) -

-150

5

0

0

5

0

1

-1

0

0

1

0

−𝟑

Baris 𝒔𝟏 , yaitu: 40 baris lama koefisien KK pada baris baru baris 𝑠1

1

(10

1 𝟏 𝟑

𝟏

0) -

30

2 3

1

0

-1

1

0

0

1

0

−𝟑

3

0

Baris 𝒔𝟑 , yaitu: 30 baris lama koefisien KK pada baris baru baris 𝑠3

1

(10

3 𝟏 𝟑

𝟏

-1 0) -

20

8 3


0

0

1 3

-1

Page 31


𝒂𝒋

VDB 𝒃𝒊

0

𝒔𝟏

30

-15

𝒙𝟐

10

0

𝒔𝟑

20


-15

0

0

0

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝒔𝟑

0

-1

1

0

0

0

0

0

2 3 1 3 8 3 5

-150

 Langkah 5

-10

1 3 1 − 3 1 3 5

Rasio

0 0 -1 0

pemeriksaan tabel sudah optimal atau belum

Nilai baris z di bawah variable 𝒙𝟏 masih positif maka tabel belum optimal. Variable masuk yaitu 𝒙𝟏 variable keluar yaitu 𝒙𝟐 , sehingga diperoleh tabel berikut: 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

-10

-15

0

0

0

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝒔𝟑 0

0

𝒔𝟏

30

2 3

0

-1

1 3

-15

𝒙𝟐

10

1 3

1

0

−

0

𝒔𝟑

20

8 3

0

0

1 3

-1

-150

5

0

0

5

0


1 3

0

Rasio 30 = 45 2 3 10 = 30 1 3 20 = 7,5 8 3

iterasi 2

Nilai yang dimiliki adalah nilai baris kerja baru yaitu baris 𝒔𝟑 (tabel berikut ini).


Page 32

8

Semua nilai pada 𝒔𝟑 di tabel solusi awal dibagi dengan 3 (elemen kunci) 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

0 -15

𝒔𝟏 𝒙𝟐

-10

𝒔𝟑

7,5

-10

-15

0

0

0

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝒔𝟑

1

0

0

8 3

−

Rasio

3 8

𝒛𝒋 − 𝒄𝒋 Perhitungan nilai baris, sebagai berikut: Baris Kunci Baru: 20 𝟖

dibagi 𝟑

8 3

0

0

1

-1

3 𝟖

7,5

1

0

0

-150

50

0

0

(7,5

1

0

0

-187,5

0

0

0

𝟑

−𝟖

𝟑

Baris 𝒛, yaitu: baris lama koefisien KK pada baris baru baris 𝑧

5

Baris 𝒔𝟏 , yaitu: 30 baris lama koefisien KK pada baris baru baris 𝑠1

2

(7,5

3

2 3

1

0

-1

0

0

5 𝟖 𝟑

0 𝟑

− 𝟖) -

35

15

8

8

1

0

3 𝟖

𝟑

𝟑

− 𝟖)

1

1

4

4

25

0

0

-1

30

3

1

0

(7,5

1

0

0

Baris 𝒔𝟑 , yaitu: baris lama koefisien KK pada baris baru baris 𝑥2

1 3

0 𝟖 𝟑

-1 𝟑

−𝟖 ) -

7,5

0


1

0

9

− 24

𝟏

−𝟖

Page 33


VDB

𝒂𝒋 𝒃𝒊

-10

-15

0

0

0

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝒔𝟑

1 4 9 − 24 8 3 35 8

1 4 1 − 8 3 − 8 15 8

0

𝒔𝟏

25

0

0

-1

-15

𝒙𝟐

7,5

0

1

0

-10

𝒙𝟏

7,5

1

0

0

-187,5

0

0

0


 Langkah 7

Rasio

membaca tabel optimal

Dengan tabel optimal dapat disimpulkan dengan Solusi optimal, yaitu: 𝑥1 = 7,5 , artinya:

𝑥2 = 7,5 ,

𝑥3 = 0

𝑑𝑎𝑛

𝑧 = −187,5

agar memperoleh minimum biaya sebesar $−187,5 maka perusahaan sebaiknya menghasilkan produk yang pertama sebesar 7,5 unit dan produk yang kedua sebesar 7,5 unit

Soal – soal: 1. Maksimumkan Kendala

2. Maksimumkan Kendala

3. Maksimumkan Kendala

𝑧 = 4𝑥1 + 3𝑥2 2𝑥1 + 3𝑥2 ≤ 6 4𝑥1 + 𝑥2 ≤ 4

dengan

𝑥1 , 𝑥2 ≥ 0

𝑧 = 3𝑥1 + 5𝑥2 2𝑥1 ≤ 8 3𝑥2 ≤ 15 6𝑥1 + 5𝑥2 ≤ 30

dengan

𝑥1 , 𝑥2 ≥ 0

𝑧 = 5𝑥1 + 3𝑥2 + 4𝑥3 3𝑥1 + 6𝑥2 + 2𝑥3 ≤ 12 𝑥1 + 2𝑥2 + 2𝑥3 ≤ 8 4𝑥1 + 2𝑥2 + 4𝑥3 ≤ 17


dengan

𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Page 34

4. Perusahaan genteng modern di Jakarta memproduksi 3 jenis genteng yaitu molek, jelita dan anggun. Ketiga jenis genteng tersebut menggunakan bahan mentah yang diimpor dari Swiss. Proses produksinya diulakukan dengan teknik dan peralatan yang serba modern. Pabrik ini mempunyai 3 bagian yaitu bagian cetak (bagian mentah dicapur lalu dicetak), bagian press (genteng merah dipress agar padat dan terpisah dari air) dan bagian pengeringan (genteng sudh dipress dikeringkan). Berbeda dengan genteng tradisional yang terbuat dari tanah liat. Genteng yang diproduksi perusahaan modern ini tidak memerlukan waktu yang lama untuk dikeringkan. Waktu pengeringan hanya beberapa menit saja karena memang sudah cukup dan lamanya proses masingmasing jenis genteng pada masing-masing bagian yaitu: Bagian Cetak Press Pengeringan Jumlah Waktu

Molek 10,7 menit 5,4 menit 0,7 menit 16,8 menit

Jenis Genteng Jelita 5 menit 10 menit 1 menit 16 menit

Anggun 2 menit 4 menit 2 menit 8 menit

Dalam seminggu mesin-mesin pada setiap bagian dapat bekerja selama: bagian cetak = 2.705, bagian press = 2.210 dan bagian pengeringa = 445, sedangkan tingkat kontribusi laba masing-masing jenis genteng yaitu: molek = Rp. 10,00 dan jelita = Rp 15,00 serta anggun = Rp 10,00. Berapa banyaknya masingmasing genteng harus diproduksi agar diperoleh keuntungan yang maksimum?


Page 35

BAB V METODE BIG M (METODE M. CHARNES) Metode Big M (metode M. Charnes) merupakan pemecahan persoalan program linier dalam menentukan solusi optimal yaitu untuk mengatasi saat fungsi kendala dengan menggunakan pertidaksamaan ≥ 𝑑𝑎𝑛 𝑎𝑡𝑎𝑢 ≤ maka variable basis awal adalah slack variable dan/atau variable buatan dan saat fungsi kendala dengan menggunakan persamaan sehingga ditemukan pada variable basis awal. Charnes mencoba mencari jawaban atas persoalan program linier dan menggunakan simpleks untuk memaksa variable buatan (variable semu atau variable artifisial) menjadi nol, dengan menentukan konsatan (-M) jika masalah yang dihadapi yaitu memaksimumkan fungsi tujuan dan menentukan nilai konstanta (M) pada variable buatan (variable semu atau variable artifisial) jika masalah yang dihadapi yaitu meminimimkan. Perbedaan metode Big M dengan metode simpleks yang telah dipelajari yaitu terletak pada pembentukan table awal. Apabila fungsi kendala dengan bentuk pertidaksamaan ≥ maka perubahan dari bentuk umum ke bentuk baku memerlukan satu surplus variable yang berfungsi sebagai variable basis awal karena bertanda negatif. Sebagai variable basis pada solusi awal maka harus ditambahkan satu variable buatan dan variable buatan pada solusi optimal hartus bernilai nol (0) jarena variable tersebut memang tidak ada. Adapun teknik yang digunakan untuk memaksa variable buatan bernilai nol (0) pada solusi optimal yaitu dengan cara berikut: a. Penambahan variable buatan pada fungsi kendala yang tidak memiliki slack variable maka penambahan variable buatan pada fungsi tujuan. b. Apabila fungsi tujuan adalah maksimasi maka variable buatan pada fungsi tujuan mempunyai koefisien +M dan apabila fungsi tujuan adalah minimisasi maka variable buatan pada fungsi tujuan mempunyai koefisien –M. c. Koefisien variable basis pada table simpleks harus bernilai nol (0) maka variable buatan pada fungsi tujuan harus digantikan nilai dari fungsi kendala yang memuat variable buatan tersebut.


Page 36

Catatan:  PL Kendala “=” atau “≥” variable buatan  Variable buatan solusi basis awa layak disingkirkan  𝑀𝑖𝑛𝑖𝑚𝑢𝑚 𝑧 = − 𝑀𝑎𝑘𝑠𝑖𝑚𝑢𝑚 𝑧 𝒛𝒎𝒊𝒏 = −𝒛𝒎𝒂𝒌𝒔 Contoh: Minimumkan

𝑧 = 4𝑥1 + 𝑥2

Kendala

3𝑥1 + 𝑥2 = 3 4𝑥1 + 3𝑥2 ≥ 6 𝑥1 + 2𝑥2 ≤ 4

𝑥1 , 𝑥2 ≥ 0

Bentuk Baku: Minimumkan

𝑧 = 4𝑥1 + 𝑥2 − 0𝑠1 + 0𝑠2

Kendala

3𝑥1 + 3𝑥2 = 3 4𝑥1 + 3𝑥2 − 𝑠1 = 6 𝑥1 + 2𝑥2 + 𝑠2 = 4

𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 ≥ 0

Pada kendala yang I dan II tidak mempunyai slack variable sehingga tidak ada variable basis awal dan agar berfungsi sebagai basis awal maka pada kendala I dan II dilakukan penambahan pada masing-masing kendala dengan satu variable buatan (artificial variable), sehingga bentuk Big M nya yaitu: Bentuk Big M: Minimum

𝑧 = 4𝑥1 + 𝑥2 − 0𝑠1 + 0𝑠2 + 𝑀𝑄1 + 𝑀𝑄2

Kendala

3𝑥1 + 3𝑥2

+ 𝑄1 = 3

4𝑥1 + 3𝑥2 − 𝑠1 + 𝑄2 = 6 𝑥1 + 2𝑥2 + 𝑠2

=4

kendala I kendala II kendala III

𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑄1 , 𝑄2 ≥ 0 Langkah-langkahnya yaitu: 1. Nilai 𝑸𝟏 digantikan dari fungsi kendala I

𝑄1 = 3 − 3𝑥1 − 𝑥2 𝑀𝑄1 = 𝑀 (3 − 3𝑥1 − 𝑥2 ) 𝑀𝑄1 = 3𝑀 − 3𝑀𝑥1 − 𝑀𝑥2


Page 37

2. Nilai 𝑸𝟐 digantikan dari fungsi kendala II

𝑄2 = 6 − 4𝑥1 − 3𝑥2 + 𝑠1 𝑄2 = 𝑀(6 − 4𝑥1 − 3𝑥2 + 𝑠1 )

𝑀𝑄2 = 6𝑀 − 4𝑀𝑥1 − 3𝑀𝑥2 + 𝑀𝑠1 3. Fungsi tujuan berubah menjadi: 𝑧 = 4𝑥1 + 𝑥2 − 0𝑠1 + 0𝑠2 + 𝑀𝑄1 + 𝑀𝑄2

Min

𝑧 = 4𝑥1 + 𝑥2 + (3𝑀 − 3𝑀𝑥1 − 𝑀𝑥2 ) + (6𝑀 − 4𝑀𝑥1 − 3𝑀𝑥2 + 𝑀𝑠1 ) 𝑧 = 4𝑥1 + 𝑥2 + 3𝑀 − 3𝑀𝑥1 − 𝑀𝑥2 + 6𝑀 − 4𝑀𝑥1 − 3𝑀𝑥2 + 𝑀𝑠1 𝑧 = 4𝑥1 + 𝑥2 + 9𝑀 − 7𝑀𝑥1 − 4𝑀𝑥2 + 𝑀𝑠1 𝑧 = (4 − 7𝑀)𝑥1 + (1 − 4𝑀)𝑥2 + 𝑀𝑠1 + 9𝑀 𝑧 = (4 − 7𝑀)𝑥1 + (1 − 4𝑀)𝑥2 + 𝑀𝑠1 + 9𝑀

Minimum

(−𝑧) = −(4 − 7𝑀)𝑥1 − (1 − 4𝑀)𝑥2 − 𝑀𝑠1 − 9𝑀

Maksimum atau

𝑧 − (4 − 7𝑀)𝑥1 − (1 − 4𝑀)𝑥2 − 𝑀𝑠1 = 9𝑀

Minimum

𝑧 = 4𝑥1 + 𝑥2 − 0𝑠1 + 0𝑠2 + 𝑀𝑄1 + 𝑀𝑄2

Maksimum

(−𝑧) = −4𝑥1 − 𝑥2 + 0𝑠1 − 0𝑠2 − 𝑀𝑄1 − 𝑀𝑄2 𝑄1 = 3 − 3𝑥1 − 𝑥2

Kendala

3𝑥1 + 𝑥2 + 𝑄1 = 3

𝑄2 = 6 − 4𝑥1 − 3𝑥2 + 𝑠1

4𝑥1 + 3𝑥2 − 𝑠1 + 𝑄2 = 6 𝑥1 + 2𝑥2 + 𝑠2 = 4

4.

Tabel awal simpleks 𝒄𝒋

CB

VDB

𝒂𝒋 𝒃𝒊

-4

-1

0

0

-m

-m

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑄1

𝑄2

-m

𝑸𝟏

3

3

1

0

0

1

0

-m

𝑸𝟐

6

4

3

-1

0

0

1

0

𝑺𝟐

4

1

2

0

1

0

0

9M

-(4-7M)=-4+7M

-(1-4M)=-1+4M

-M

0

0

0



Rasio

Page 38

5.

Menentukan kolom kunci, baris kunci dan rasio Nilai positif terbesar ada pada kolom 𝒙𝟏 , maka kolom 𝒙𝟏 adalah kolom kunci (KK) Rasio pembagi kanan dengan kolom kunci adalah bersesuaian dengan baris 𝒔𝟐 maka baris 𝑸𝟏 adalah baris kunci (BK) dan 𝑸𝟏 merupakan variabel keluar. Elemen kunci adalah 3. 𝒄𝒋 CB

VDB

𝒂𝒋 𝒃𝒊

-1

0

0

-m

-m

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑄1

𝑄2

-m

𝑸𝟏

3

3

1

0

0

1

0

-m

𝑸𝟐

6

4

3

-1

0

0

1

0

𝑺𝟐

4

1

2

0

1

0

0

9M

-4+7M

-1+4M

-M

0

0

0

𝒛𝒋 − 𝒄𝒋 6.

-4

Rasio 3 =1 3 6 3 = 4 2 4 =4 1

Menentukan Tabel Iterasi I Nilai yang dimiliki adalah nilai baris kunci baru yaitu baris 𝒙𝟏 (tabel berikut) Semua nilai pada 𝑸𝟏 di tabel solusi awal di bagi dengan 3 (elemen kunci) CB

VDB

𝒄𝒋 𝒂𝒋 𝒃𝒊

-4

𝒙𝟏

1

-4

-1

0

0

-m

-m

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑄1

𝑄2

1

1 3

0

0

1 3

0

0

0

1

0

0

Rasio

-m 𝑸𝟐 0 𝑺𝟐 𝒛𝒋 − 𝒄𝒋 Perhitungan nilai baris, sebagai berikut: Baris Kunci Baru: dibagi 3

3

3

1

1


1 𝟏 𝟑

𝟏 𝟑

0 0

Page 39

Baris 𝑸𝟐 , yaitu:

6 1

4 1

3 𝟏 𝟑

-1 0

0 0

0

1 0

𝟏 𝟑

4

-

Baris 𝒔𝟐 , yaitu:

2

0

4 1

1 1

5 3

2 𝟏 𝟑

4

-1

0

−3

1

0 0

1 0

0 𝟏

0 0

𝟑

1

3

Baris z, yaitu:

9M 1

0 -4+7M 1

5 3

0

-1+4M -M 𝟏 0 𝟑

1

1

-3

0 0

0

0 0 0

𝟏 𝟑

-4+7M

4+2M

1+5𝑀

0

3

-M

0

4−7𝑀

0

3

Diperoleh Tabel Iterasi I, yaitu: 𝒄𝒋 CB

VDB

𝒂𝒋 𝒃𝒊

-4

-1

0

0

-m

-m

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑄1

𝑄2

0

0

-1

0

0

1

-M

0

-4

𝒙𝟏

1

1

-m

𝑸𝟐

2

0

0

𝑺𝟐

3

0

4+2M

0


1 3 5 3 5 3 1 + 5𝑀 3


1 3 4 − 3 1 − 3 4 − 7𝑀 3

Rasio

0 1 0 0

Page 40

7.

Pemerikasaan Tabel Iterasi I Nilai baris 𝒛 di bawah variable 𝒙𝟐 positif terbesar maka table belum optimal. Variabel masuk yaitu 𝒙𝟐 dan variable keluar 𝑸𝟐 sehingga diperoleh table berikut: 𝒄𝒋 𝒂𝒋

CB VDB 𝒃𝒊

-1

0

0

-m

-m

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑄1

𝑄2

0

0

1 3

-4

𝒙𝟏

1

1

1 3

-m

𝑸𝟐

2

0

5 3

-1

0

−

4 3

1

0

𝑺𝟐

3

0

5 3

0

1

−

1 3

0

4+2M

0

1 + 5𝑀 3

-M

0


8.

-4

Rasio 1 =3 1 3 2 6 = 5 5 3 3 =5 5 3

0

4 − 7𝑀 3

0

Menentukan Tabel Iterasi II Nilai yang dimiliki adalah nilai baris kunci baru yaitu baris 𝒙𝟐 (tabel berikut) 5

Semua nilai pada 𝒔𝟐 di tabel solusi awal di bagi dengan 3 (elemen kunci) 𝒄𝒋 CB

VDB

𝒂𝒋 𝒃𝒊

-4

𝒙𝟏

-1

𝒙𝟐

0

𝑺𝟐

6 5

-4

-1

0

0

-m

-m

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑄1

𝑄2

0

1

−

3 5

0

−

4 5

3 5

Rasio

𝒛𝒋 − 𝒄𝒋 Perhatikan nilai baris, sebagai berikut: Baris Kunci Baru: 5

dibagi 3

2 𝟔 𝟓

0 0


5 3

1

-1 𝟑

−𝟓

4

0

−3

0

−𝟓

𝟒

1 𝟑 𝟓

Page 41

Baris 𝒙𝟏 , yaitu:

1 𝟔 𝟓

𝟏 𝟑

3 5

Baris 𝒔𝟐 , yaitu:

3 𝟔 𝟓

5

1

1 3

0

1

1

0

0 0

5 3

1

0

1

0

𝟑

−𝟓

0 𝟑

−𝟓

𝟓

3

0

5

𝟑

−𝟓

0

1

0

3 𝟒

1

−5

5 1

1

−3

0

−𝟓

0

𝟒

𝟑 𝟓

-

3

1

0

4+2M

0

0

1

1

1

-M

0

-1

Baris 𝒛, yaitu: 𝟔 𝟓

1+5𝑀

0

1+5𝑀 3

1

𝟑

−𝟓

4−7𝑀

0

3 𝟒

𝟑

−𝟓

0

𝟓

-

3

18

0

5 18

Disederhanakan:

0

5

0 0

1

0

5 1

0

5

8−5𝑀

−1−5𝑀

5

5 1

8 5

− 𝑀 −5 − 𝑀

Diperoleh Tabel Iterasi II, yaitu: 𝒄𝒋 CB

VDB

𝒂𝒋 𝒃𝒊

-4

𝒙𝟏

-1

𝒙𝟐

0

𝑺𝟐


9.

3 5 6 5 1 18 5

-4

-1

0

0

-m

-m

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑄1

𝑄2

1

0

0

1

0

0

3 5 4 − 5 1

0

0

1 5 3 5 -1 1 − −𝑀 5

1 5 3 − 5 1 1 5

0 0 1 0

8 −𝑀 5

Rasio

−

Pemeriksaan Tabel Iterasi II Nilai baris 𝒛 di bawah variable 𝒔𝟏 masih positif maka tabel belum optimal. Variabel masuk yaitu 𝒔𝟏 dan variable keluar 𝒔𝟐 sehingga diperoleh tabel berikut:


Page 42

𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

-4

𝒙𝟏

3 5

-1

𝒙𝟐

6 5

0

𝑺𝟐

1 18 5


-4

-1

0

0

-m

-m

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑄1

𝑄2

0

3 5

1 − 5

0

−

1

0

1 5

0

1

−

0

0

0

0

1 1 5

3 5

1 0

4 5

Rasio

3 5

1 8 −𝑀 5

-1 1 − −𝑀 5

3 5 =3 1 5 6 5 = −2 3 − 5 1

10. Menentukan Tabel Iterasi III Nilai baris kunci baru: baris 𝒔𝟐 & semua nilai pada 𝒔𝟏 di tabel solusi awal:1 (kunci) 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

-4 -1 0

𝒙𝟏 𝒙𝟐 𝑺𝟏

-4

-1

0

0

-m

-m

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑄1

𝑄2

0

0

1

1

1

-1

1

Rasio

𝒛𝒋 − 𝒄𝒋 Perhatikan nilai baris, sebagai berikut: Baris Kunci Baru:

1

0

0

1

1

1

-1

1

0

0

1

1

1

-1

1 0

0 0

1 0 0

dibagi 1 3

Baris 𝒙𝟏 , yaitu:

5

1

1

1

0 1

0

0

−5

1 0

−5 1

5

3 5

1

1

−5 -1

𝟏 𝟓

2 5 6

Baris 𝒙𝟐 , yaitu:

5

1

3

1

2 5 4

0 1

−5 1

3

1

0 3 5

-1

3 5

9 5

0


1

0

5

-5

0

Page 43

18

Baris 𝒛, yaitu:

5

1

0 0

0 0

0

0

1

0 1

5

1

8 5

1

−𝑀

−5 − 𝑀 -1

1

1 5

17 5

1

7

−5

0

5

−𝑀

−𝑀

Diperoleh Tabel Iterasi III, yaitu: 𝒄𝒋 CB

VDB

𝒂𝒋 𝒃𝒊

-4

𝒙𝟏

-1

𝒙𝟐

0

𝑺𝟐

2 5 9 5 1 17 5


-4

-1

0

0

-m

-m

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑄1

𝑄2

1

0

0

−

0

1

0

0

0

1

2 5 1 − 5 1

0

0

0

1 5 3 5 1 1 − 5

2

0 0 -1

7 −𝑀 5

Dengan demikian tabel telah optimal, 𝑧𝑚𝑖𝑛 = −𝑧𝑚𝑎𝑘𝑠 = −

Rasio

−𝑀

17 5

tercapai

9

bila 𝑥1 = 5 𝑑𝑎𝑛 𝑥2 = 5 Soal – soal: 1.

2.

3.

Minimumkan

𝑧 = 4𝑥1 + 𝑥2

Kendala

3𝑥1 + 𝑥2 = 3

4𝑥1 + 3𝑥2 ≥ 6

𝑥1 + 2𝑥2 ≤ 3

𝑥1 , 𝑥2 ≥ 0

Minimumkan

𝑧 = 3𝑥1 + 2𝑥2

Kendala

𝑥1 + 𝑥2 ≥ 2

Minimumkan

𝑧 = 𝑥1 + 9𝑥2 + 𝑥3

Kendala

𝑥1 + 2𝑥2 + 3𝑥3 ≥ 9

3𝑥1 + 2𝑥2 + 2𝑥3 = 15

2𝑥1 + 2𝑥2 + 3𝑥3 ≤ 12

𝑥1 , 𝑥2 , 𝑥3 ≥ 0


2𝑥1 + 𝑥2 ≥ 3

𝑥1 , 𝑥2 ≥ 0

Page 44

BAB VI METODE DUAL SIMPLEKS (METODE SIMPLEKS DUA FASE) Metode simpleks dua fase merupakan suatu modifikasi dari metode M’Charnes. Penyelesaian program linier pada metode M’Charnes koefisien, yaitu variable tiruan (buatan atau semu) mendapatkan harga (-M) untuk permasalahan memaksimumkan atau (+M) untuk permasalahan meminimumkan. Sedangkan penyelesaian program linier dengan metode simpleks dua fase, yaitu harga (konstanta) variable tiruan pada fungsi tujuan diberi tanda (-1) pada permasalahan memaksimumkan atau (+1) pada permasalahan meminimumkan. Metode simpleks dua fase digunakan bila tabel optimal tidak layak. Pada bentuk umum program linier, fungsi kendala dengan menggunakan tanda (≥) dan tidak ada tanda (=) maka bentuk dapat menggunakan metode simpleks dua fase. Metode simpleks dua fase digunakan pada variable basis awal terdiri dari variable buatan dan proses optimasi dilakukan dengan dua tahap (dua fase), yaitu: 1. Fase I (tahap I) merupakan proses optimasi variable buatan yaitu mengusahakan agar semua nilai variable buatan menjadi nol (0) Pada akhir fase I yaitu setelah 𝑧𝑚𝑎𝑘𝑠 = 0 dengan 3 kemungkinan hasil sebagai berikut: a. 𝑧𝑚𝑎𝑘𝑠 < 0

satu atau lebih variabel buatan berada dalam basis pada

tingkat nilai yang positif. Hal ini berarti permasalahan program linier yang asli tidak mempunyai penyelesaian yang layak (pemecahan fisibel) b. 𝑧𝑚𝑎𝑘𝑠 = 0

tidak ada variable buatan yang terletak (ada) dalam basis.

Hal ini berarti permasalahan program linier yang asli telah diperoleh penyelesaian dasar yang fisibel.


Page 45

c. 𝑧𝑚𝑎𝑘𝑠 > 0

satu atau lebih variable buatan terletak (ada) pada basis, pada

tingkat nilai nol (degenerasi). Hal ini berarti permasalahan program linier yang asli

telah diperoleh penyelesaian yang layak

(pemecahan fisibel) 2. Fase II (tahap II) merupakan proses optimasi variable keputusan yaitu dari suatu pemecahan dasar yang fisibel baik yang memuat vriable buatan dengan nilai variable pada tingkat nol dan tidak memuat vektor buatan sama sekali. Ringkasan perubahan untuk penyelesaian simpleks. Perubahan Fungsi Tujuan

Tanda Fungsi Kendala

Perubahan Fungsi Kendala (diubah menjadi tanda “=”)

1

=

Tambahan Variable Artificial (𝑄𝑖 )

2

≤

Kurangi Slack Variabel (𝑠𝑖 )

0

0

3

≥

Kurangi Surplus Variable (𝑠𝑖 )

0

0

No

Tambahkan Variable Artificial (𝑄𝑖 )

Maksimasi

Minimisasi

−𝑀 𝑎𝑡𝑎𝑢 − 1 +𝑀 𝑎𝑡𝑎𝑢 + 1

−𝑀 𝑎𝑡𝑎𝑢 − 1 +𝑀 𝑎𝑡𝑎𝑢 + 1

Bentuk khusus dalam Simpleks, sebagai berikut: 1. Degeneracy  Kasus ini terjadi apabila salah satu variable basis berharga nol (0) pada iterasi selanjutnya sehingga iterasi yang dilakukan menjadi suatu loops yang akan kembali ke bentuk sebelumnya.  Degeneracy dapat bersifat temporer (sementara) sehingga apabila iterasi dilanjutkan maka degeneracy itu menghilang. 2. Solusi Optimum Banyak  Kasus ini terjadi apabila masalah program linier memiliki lebih dari satu solusi optimum. Hal ini ditandai apabila fungsi tujuan sejajar dengan fungsi kendala. Pada table simpleks hal ini ditandai dengan paling sedikit satu variable basis pada baris 𝒛 bernilai nol (0).


Page 46

 Solusi optimum yang lain dapat dicari dengan cara melanjutkan iterasi dengan memilih variable non basis bernilai nol menjadi entering variable dan memberikan nilai 𝒛 yang sama. 3. Solusi Tidak terbatas  Kasus ini terjadi apabila ruang solusi tidak terhingga (nilai fungsi tujuan meningkat untuk maksimasi atau menurun untuk minimasi secara tidak terbatas). Contoh: 𝑧 = 30𝑥1 + 40𝑥2

1. Minimumkan

𝑥1 + 𝑥2 ≥ 40

Kendala

𝑥1 + 2𝑥2 ≥ 60

𝑥1 , 𝑥2 ≥ 0

Penyelesaian:  Fase I dengan Bentuk Baku: 𝑧 = 30𝑥1 + 40𝑥2 − 0𝑠1 − 0𝑠2 + 1𝑄1 + 1𝑄2

Minimumkan

(−𝑧) = −30𝑥1 − 40𝑥2 + 0𝑠1 + 0𝑠2 − 1𝑄1 − 1𝑄2

Maksimumkan

𝑥1 + 𝑥2 − 𝑠1 + 𝑄1 = 40

Kendala

𝑥1 + 2𝑥2 − 𝑠2 + 𝑄2 = 60 𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑄1 , 𝑄2 ≥ 0 𝑠1 𝑑𝑎𝑛 𝑠2 : variable pengurang

𝑄1 𝑑𝑎𝑛 𝑄2 : variable buatan

Tabel Awal 𝒄𝒋 CB

VDB

𝒂𝒋 𝒃𝒊

0

0

0

0

-1

-1

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑸𝟏

𝑸𝟐

-1

𝑸𝟏

40

1

1

-1

0

1

0

-1

𝑸𝟐

60

1

2*

0

-1

0

1

(−1.40) + (−1.60) = −100

−1 − 1 = −2

−1 − 2 = −3

1−0=1

0+1= 1

0

0



Rasio 40 = 40 1 60 = 30 2

Page 47

Tabel I 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

-1

𝑸𝟏

10

0

𝑸𝟐

30


-10

0

0

0

0

-1

-1

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑸𝟏

𝑸𝟐

0

-1

1

0

0

1

0

0

0

0

-1

-1

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑸𝟏

𝑸𝟐

0

-1

1

0

0

1

0

0

0

0

-1

-1

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑸𝟏

𝑸𝟐

1 0 0

0 1 0

-2 1 0

1 -1 0

2 -1 1

-1 1 1

1 2 1 2 1 − 2

1 2 1 − 2 1 − 2

1 0 0

Rasio

1 2 1 2 3 2

−

Tabel II 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

1

-1

𝑸𝟏

10

0

𝒙𝟐

30


-10

* 2 1 2 1 − 2

1 2 1 − 2 1 − 2

1 0 0

1 2 1 2 3 2

−

Rasio 20 60

Table III 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

0 0

𝒙𝟏 𝒙𝟐 𝒛𝒋 − 𝒄𝒋

20 20 0

Rasio

Ternyata dalam table 3 menunjukkan fase I berakhir sehingga melangkah ke fase II


Page 48

 Fase II Tabel IV pada fase II CB 𝒄𝒋 -30 VDB 𝒂𝒋 𝒙𝟏 𝒃𝒊 20 1 -30 𝒙𝟏 20 0 -40 𝒙𝟐 𝒛𝒋 − 𝒄𝒋 -140 0

-40

0

0

𝒙𝟐

𝒔𝟏

𝒔𝟐

0 1 0

-2 1 20

1 -1 10

Rasio

Karena semua kolom sudah positif maka nilai 𝑧𝑚𝑖𝑛 = −𝑧𝑚𝑎𝑘𝑠 = −(−140) = 140 Jadi nilai maksimum di 𝑧 = 140 𝑑𝑒𝑛𝑔𝑎𝑛 𝑥1 = 𝑥2 = 20 𝑧 = 50𝑥1 + 80𝑥2

2. Minimumkan

𝑥1 ≤ 40 𝑥2 ≥ 20

Kendala

𝑥1 + 𝑥2 = 50

𝑥1 , 𝑥2 ≥ 0

Penyelesaian:  Fase I dengan Bentuk Baku: Minimumkan

𝑧 = 50𝑥1 + 80𝑥2 + 0𝑠1 − 0𝑠2 + 1𝑄1 + 1𝑄2

Maksimumkan

(−𝑧) = −50𝑥1 − 80𝑥2 − 0𝑠1 + 0𝑠2 − 1𝑄1 − 1𝑄2 𝑥1 + 𝑠1 = 40

Kendala

𝑥2 − 𝑠2 + 𝑄1 = 20 𝑥1 + 𝑥2 + 𝑄2 = 50 𝑥1 , 𝑥2 , 𝑠1 , 𝑠2 , 𝑠3 , 𝑠4 ≥ 0 𝑠1 : variabel penambah 𝑠2 : variabel pengurang 𝑄1 𝑑𝑎𝑛 𝑄2 : variabel buatan Tabel Awal 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

0 -1 -1

𝒔𝟏 𝑸𝟏 𝑸𝟐 𝒛𝒋 − 𝒄𝒋

40 20 50 -70

0

0

0

0

-1

-1

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑸𝟏

𝑸𝟐

1 0 1 1

0 1 1 -2

1 0 0 0

0 -1 0 1

0 0 0 0

0 0 1 0


Rasio

Page 49

Tabel I 𝒄𝒋 CB

𝒂𝒋

VDB

0 𝒔𝟏 -1 𝑸𝟏 -1 𝑸𝟐 𝒛𝒋 − 𝒄𝒋

𝒃𝒊 40 20 50 -70

0

0

0

0

-1

-1

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑸𝟏

𝑸𝟐

1 0 1 1

0 1* 1 -2

1 0 0 0

0 -1 0 1

0 0 0 0

0 0 1 0

0

0

0

0

-1

-1

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑸𝟏

𝑸𝟐

1 0 1 -1

0 1 0 0

1 0 0 0

0 -1 1 -1

0 0 -1 2

0 0 1 0

0

0

0

0

-1

-1

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑸𝟏

𝑸𝟐

1 0 1* -1

0 1 0 0

1 0 0 0

0 -1 1 -1

0 0 -1 2

0 0 1 0

0

0

0

0

-1

-1

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

𝑸𝟏

𝑸𝟐

0 0 1 0

0 1 0 0

1 0 0 0

-1 -1 1 0

1 1 -1 1

-1 0 1 1

Rasio ∞ 20 50

Tabel II 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

0 0 -1

𝒔𝟏 𝒙𝟐 𝑸𝟐 𝒛𝒋 − 𝒄𝒋

40 20 30 -30

Rasio

Tabel III 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

0 0 -1

𝒔𝟏 𝒙𝟐 𝑸𝟐 𝒛𝒋 − 𝒄𝒋

40 20 30 -30

Rasio 40 ∞ 30

Tabel IV 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

0 0 0

𝒔𝟏 𝒙𝟐 𝒙𝟏 𝒛𝒋 − 𝒄𝒋

10 20 30 0


Rasio

Page 50

 Fase II Tabel V pada fase II 𝒄𝒋 CB

𝒂𝒋

VDB 𝒃𝒊

0 𝒔𝟏 -80 𝒙𝟐 -50 𝒙𝟏 𝒛𝒋 − 𝒄𝒋

10 20 30 -3100

-50

-80

0

0

𝒙𝟏

𝒙𝟐

𝒔𝟏

𝒔𝟐

0 0 1 0

0 1 0 0

1 0 0 0

-1 -1 1 30

Rasio

Karena semua kolom sudah positif maka nilai 𝑧𝑚𝑖𝑛 = −𝑧𝑚𝑎𝑘𝑠 = −(−3100) = 3100 Jadi nilai maksimum di 𝑧 = 3100 𝑑𝑒𝑛𝑔𝑎𝑛 𝑥1 = 30 𝑑𝑎𝑛 𝑥2 = 20 Soal – soal : 1. Minimumkan Kendala

𝑧 = 14𝑥1 + 18𝑥2 𝑥1 + 𝑥2 ≤ 25 5𝑥1 + 6𝑥2 ≥ 40

2. Minimumkan Kendala

𝑥1 , 𝑥2 ≥ 0

𝑧 = 5𝑥1 + 3𝑥2 2𝑥1 + 𝑥2 ≥ 3 𝑥1 + 𝑥2 ≥ 2


𝑥1 , 𝑥2 ≥ 0

Page 51

BAB VII METODE SIMPLEKS YANG DIREVISI Metode simpleks yang direvisi merupakan salah satu cara dalam pemecahan persoalan program linier. Penyelesaian dengan metode simpleks yang direvisi dengan menggunakan dua bentuk penyelesaian yaitu: a.

Bentuk Standard I (Standrad From I), yaitu memasukkan variable slack dan surplus dan tidak memerlukan variable – variable buatan (artificial variable) sehingga memperoleh matriks identitas (identity matrix).

b.

Bentuk Standard II (Standrad From II), yaitu memasukkan variabel – variable buatan (artificial variable) sehingga memperoleh matrix identitas (identity matrix). Pada metode simpleks yang direvisi, menganggap bahwa fungsi tujuan

merupakan suatu pembatasan, dengan langkah-langkah sebagai berikut: a. Bentuk Standard I (Standrad From I) 1. Dirubah dalam bentuk baku/standar program linier 2. Ditulis dalam bentuk matrix, sebagai berikut: 𝐴𝑋 = 𝐻 ,

𝑋≥0 ,

𝑀𝑎𝑥 𝑍 = 𝐶𝑋

𝑍 − 𝐶𝑋 = 𝑍 − 𝑐1 𝑥1 −

⋯ − 𝑐𝑛 𝑥𝑛 = 0 setelah itu dimasukkan di dalam 𝐴𝑋 = 𝐻, maka diperoleh: 𝑍 − 𝑐1 𝑥1 − ⋯ − 𝑐𝑛 𝑥𝑛 = 0 𝑎11 𝑥1 + ⋯ + 𝑎1𝑛 𝑥𝑛 = ℎ1 𝑎21 𝑥1 + ⋯ + 𝑎2𝑛 𝑥𝑛 = ℎ2 . . .

𝑎𝑚1 𝑥1 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 = ℎ𝑚 Dari uraian di atas diperoleh persamaan sebanyak (𝑚 + 1) dengan variable yang tidak diketahui sebanyak (𝑛 + 1) yaitu 𝑍, 𝑥1 , 𝑥2 , … , 𝑥𝑛 .


Page 52

Pada kolom 𝑍 = 𝑥0 , −𝑐𝑗 = 𝑎0𝑗 maka didapat sebagai berikut: 𝑥0 + 𝑎01 𝑥1 + ⋯ + 𝑎0𝑛 𝑥𝑛 = 0 𝑎11 𝑥1 + ⋯ + 𝑎1𝑛 𝑥𝑛 = ℎ1 𝑎21 𝑥1 + ⋯ + 𝑎2𝑛 𝑥𝑛 = ℎ2 . . .

𝑎𝑚1 𝑥1 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 = ℎ𝑚 3. Di dalam bentuk matrix partisi atau partition matrix diperoleh sebagai berikut: 𝑥0 0 ] [ ]=[ ] 𝑥 𝐻 𝐴 𝐴0

1 [ 0

1 [ 0

−𝑐

𝑍 0 ][ ] = [ ] 𝐴 𝑋 𝐻

4. Bentuk table untuk revised simpleks VDB

(1)

(1)

𝑃1

𝑃2

𝑥0

𝑃01

𝑃02

𝑥𝐵1

𝑃11

𝑃12

𝑃21

𝑃22

. . .

. . .

𝑃𝑖1

𝑃𝑖2

. . .

. . .

𝑃𝑚1

𝑃𝑚2

𝑥𝐵2 . . .

𝑥𝐵𝑖 . . .

𝑥𝐵𝑚

…… …… …… …… …… …… …… …… …… …… …… …… …… …… …… ……

(1)

(1)

(1)

𝑌𝑘

𝑃𝑚

𝑥𝐵

𝑃0𝑚

𝑍 = 𝑥0

𝑍𝑘 − 𝑐𝑘

𝑃1𝑚

𝑥𝐵1

𝑌1𝑘

𝑃2𝑚 . . .

𝑃𝑖𝑚

𝑥𝐵2 . . .

𝑥𝐵𝑖

𝑌2𝑘 . . .

𝑌𝑖𝑘

. . .

. . .

. . .

𝑃𝑚𝑚

𝑥𝐵𝑚

𝑌𝑚𝑘

5. Perhitungan selanjutnya dengan menggunakan cara simpleks


Page 53

b. Bentuk Standard II (Standrad From II) 1. Membuat fungsi tujuan menjadi maksimum (memaksimumkan) 2. Dirubah dalam bentuk baku/standar program linier 3. Ditulis dalam bentuk matrix, sebagai berikut: 𝐴𝑋 = 𝐻 ,

𝑋≥0 ,

𝑀𝑎𝑥 𝑍 = 𝐶𝑋

𝑍 − 𝐶𝑋 = 𝑍 − 𝑐1 𝑥1 −

⋯ − 𝑐𝑛 𝑥𝑛 = 0 setelah itu dimasukkan di dalam 𝐴𝑋 = 𝐻, maka diperoleh: 𝑍 − 𝑐1 𝑥1 − ⋯ − 𝑐𝑛 𝑥𝑛 = 0 𝑥𝑛+1 + ⋯ … . . … … … + 𝑥𝑛+𝑚+1 = 0 𝑎11 𝑥1 + ⋯ + 𝑎1𝑛 𝑥𝑛 + 𝑥𝑛+1 (**)

= ℎ1

. . .

𝑎𝑚1 𝑥1 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 + ⋯ … + 𝑥𝑛+𝑚+1 = ℎ𝑚 Pembatasan di dalam persamaan yang kedua merupakan persamaan yang ditamdahkan sehinggga mendapatkan bahwa vector buatan tetap nol, tetapi ternyata lebih baik dengan menambah indeks baris dengan 1 (satu) yaitu 𝑚 + 1, sehingga diperoleh matrix yaitu: 𝑎21 𝑎2𝑛 . . .

𝐴= [𝑎𝑚+1,1

,

𝐻 = [ℎ1 , … . , ℎ𝑚+1 ]

𝑎𝑚+1,𝑛 ]

Persamaan – persamaan (**) dapat ditulis sebagai berikut: 𝑥0 − 𝑐1 𝑥1 − ⋯ − 𝑐𝑛 𝑥𝑛 = 0 𝑥𝑛+1 + ⋯ … . . … … … + 𝑥𝑛+𝑚+1 = 0 𝑎11 𝑥1 + ⋯ + 𝑎1𝑛 𝑥𝑛 + 𝑥𝑛+1 = ℎ1

(***)

. . .

𝑎𝑚1 𝑥1 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 + ⋯ … + 𝑥𝑛+𝑚+1 = ℎ𝑚+1 Pada persamaan di atas, penambahan variable 𝑥𝑛+1 dalam persamaan (***) di baris kedua sebelum 𝑥𝑛+2


Page 54

4. Matrix basis untuk fase II, sebagi berikut:

𝐵𝑜𝑜

1 0 0 0 1 1 0 0 1 = . . . [0 0 0

… … …

0 1 0

…

1]

kolom 1 & 2 masing-masing 𝑒1 𝑑𝑎𝑛 𝑒1 dan bukan merupakan identity matrix Invers dari 𝐵𝑜𝑜 dengan mempergunakan matrix partisi yaitu: 1 0 0 𝐵𝑜𝑜 = [0

0 0 1 −1 0 1 . . . 0 0

… 0 … − 1 … 0

0

0

0

1

1𝑚

[0

1]

…

1

1

1𝑚 ]

5. Bentuk table untuk revised simpleks VDB 𝑥0 𝑥𝐵1 𝑥𝐵2 . . .

𝑥𝐵𝑖 . . .

𝑥𝐵𝑚

(1)

(1)

𝑃1

𝑃2

(1)

…………

𝑃𝑚

𝑥𝐵

𝑃01

𝑃02

…………

𝑃0𝑚

𝑍 = 𝑥0

𝑍𝑘 − 𝑐𝑘

𝑃11

𝑃12

…………

𝑃1𝑚

𝑥𝐵1

𝑌1𝑘

𝑃21

𝑃22

…………

𝑃2𝑚

. . .

. . .

…………

. . .

𝑃𝑖1

𝑃𝑖2

…………

𝑃𝑖𝑚

. . .

. . .

…………

. . .

. . .

. . .

𝑃𝑚1

𝑃𝑚2

…………

𝑃𝑚𝑚

𝑥𝐵𝑚

𝑌𝑚𝑘


(1)

(1)

𝑌𝑘

𝑥𝐵2

𝑌2𝑘

. . .

. . .

𝑥𝐵𝑖

𝑌𝑖𝑘

Page 55

6. Perhitungan selanjutnya dengan menggunakan cara simpleks Contoh: 𝑧 = 3𝑥1 + 2𝑥2

1. Maksimumkan

2𝑥1 + 𝑥2 ≤ 5

Kendala

𝑥1 + 𝑥2 ≤ 3 ,

𝑥1 , 𝑥2 ≥ 0

Penyelesaian:

𝑥0

𝑥1

𝑧 = 3𝑥1 + 2𝑥2

𝑥0 − 3𝑥1 + 2𝑥2 = 0

2𝑥1 + 𝑥2 ≤ 5

2𝑥1 + 𝑥2 + 𝑥3 = 5

𝑥1 + 𝑥2 ≤ 3

𝑥1 + 𝑥2 + 𝑥4 = 3

(1)

𝑥2

𝑃1

(1)

𝑃2

𝑥1 1 −3

−2

0

0

0 𝑥2

0

2

[0

1

2

1

1

1

1 1

0

0

1]

𝑥3

= 3 [5]

[ 𝑥4 ]

𝑥1 5 𝑥2 ] [𝑥 ] = [ ] 3 0 1 3 𝑥4

1 0

[ 𝐴10

1

𝐴11

𝐴12

𝐴13

𝐴14

A

𝐼2

X

H 𝑒1

𝐻1

𝑒2 𝑒1

Matrix basis 𝐵0 = (𝑒1 , 𝑒2 , 𝑒3 ), 𝐵0 = 𝐼3 1 1

𝑐𝐵

0

𝐼2

𝐵0−1 = [

0

0

]= 0

1

0

[ 0

0

1]

(𝟏)

(𝟏)

𝒆

𝐵0−1 = 𝐵0 = 𝐼3

𝒆𝟏 𝒆 𝟐


Page 56

Tabel Awal (1)

(1)

𝑃2

𝑥𝐵

𝑥0

0

0

0

𝑥3

1

0

5

𝑥4

0

1

3 𝒆

(1)

(1)

menentukan nilai 𝑌𝑘

𝑌𝑘

𝑌𝑘

(1)

𝑃1

(1)

𝑃2

1

0

0

−3

= 0

1

0

2

[0

0

1][1]

(𝟏)

Masukan nilai 𝒀𝒌 pada table: BK= terkecil (1)

(1)

(1)

𝑃1

VDB

KK

(1)

(1)

(1)

𝑥𝐵

𝑥0

0

0

0

-3

𝑥3

1

0

5

2*

𝑥4

0

1

3

1

(1)

2 [1]

Rasio

𝑌𝑘

𝑃2

Nilai 𝑌𝑘

=

EK

𝑃1

VDB

−3

0 =∞ 3 5 1 =2 2 2 3 =3 1

masih bernilai negative maka langkah selanjutnya seperti pada

simpleks dengan menentukan kolom kunci, baris kunci dan elemen kunci, yaitu: Baris Kunci :

1

0

5 dibagi 2

1

0 1 0

2

Untuk 𝑥4 :

0 1 2

5 2

3 5 2

1

1

−2


1

1 2

Page 57

Untuk 𝑥0 :

0

0 0

1 2

0 5 2

-3

3

15

0

2

2

Tabel Iterasi I VDB 𝑥0 𝑥1 𝑥4

(1)

𝑃1 3 2 1 2 1 − 2

(1)

0 1

𝒆 1 (1)

𝑌𝑘

𝑥𝐵 15 2 5 2 1 2

0

(1)


(1)

(1)

𝑃2

𝑌𝑘

= 0 [0

(1)

𝑃1 3

1

0

2 1 2

−

(1)

𝑃2

1 2

−2

−2

0 1]

1

1 = [1]

2

[

1 2

]

(𝟏)

Masukan nilai 𝒀𝒌 pada table: VDB

(1)

𝑃1

(1)

𝑃2

(1)

(1)

𝑥𝐵

𝑌𝑘

𝑥0

3 2

0

15 2

−

𝑥1

1 2

0

5 2

1 2

𝑥4

−

1

1 2

1 ∗ 2

1 2


1 2

Rasio 15 2 = −15 1 −2 5 2 =5 1 2 1 2 =1 1 2

Page 58

Langkah selanjutnya seperti pada simpleks dengan menentukan kolom kunci, baris kunci dan elemen kunci, yaitu: 1

−2

Baris Kunci :

1

1

2

1

dibagi 2 -1

2

1

Untuk 𝑥1 :

1 5

0 2

2

-1

2

1

1

-

2

1

-1

3

Untuk 𝑥0 :

15

0 2

2

-1 −

2 2

1

1

-

2

1

1

8

Tabel Iterasi II (1)

(1)

(1)

𝑃1

𝑃2

𝑥𝐵

𝑥0

1

1

8

𝑥1

1

-1

2

𝑥2

-1

2

1

VDB

(1)

𝑌𝑘

Karena semua nilai 𝑧𝑗 − 𝑐𝑗 ≥ 0 maka sudah tercapai pemecahan optimal, yaitu 𝑧𝑚𝑎𝑘𝑠 = 8 dengan 𝑥1 = 2 𝑑𝑎𝑛 𝑥2 = 1 2. Minimumkan Kendala

𝑧 = 5𝑥1 + 3𝑥2 2𝑥1 + 𝑥2 ≥ 3 𝑥1 + 𝑥2 ≥ 2 , 𝑥1 , 𝑥2 ≥ 0


Page 59

Penyelesaian: 𝑧𝑚𝑖𝑛 = −𝑧𝑚𝑎𝑘𝑠 𝑧𝑚𝑎𝑘𝑠 = −5𝑥1 − 3𝑥2 𝑧 = 5𝑥1 + 3𝑥2

𝑥0 + 5𝑥1 + 3𝑥2 = 0 𝑥5 + 𝑥6 + 𝑥7 = 0

2𝑥1 + 𝑥2 ≥ 3

2𝑥1 + 𝑥2 − 𝑥3 + 𝑥6 = 3

𝑥1 + 𝑥2 ≥ 2

𝑥1 + 𝑥2 − 𝑥4 + 𝑥7 = 2

𝑛 = 4 𝑑𝑎𝑛 𝑚 = 2

𝑥𝑛+1 = 𝑥5

harus maksimum

Dalam bentuk matrix, yaitu: 𝑥0

𝑥1

𝑥2 𝑥3 𝑥4 𝑥5 𝑥6 𝑥7

1

5

3

0

0

0

0

0

0 0

0

2

1 −1 0

[0

1

1

0 1 0

0 −1 0

0 1 1

0 1 0

0 1]

𝑥0 𝑥1 𝑥2 𝑥3 𝑥4 = 𝑥5 𝑥6 [𝑥7 ]

1 0

0 0

1

0

1

0

1

1

0 3 [2]

0 1

0

0

0

−1

− 1

0

0 −5 =

0

0

1 0

0

0

1

0

[0

0

0 1]

[0

0

0

1] [ 2 ]

(2)

𝑃1


(2)

𝑃2

3

3 [2]

(2)

𝑃3

Page 60

Tabel Awal (2)

(2)

(2)

𝑃2

𝑃3

𝑥𝐵

𝑥0

0

0

0

0

𝑥5

1

-1

-1

-5

𝑥6

0

1

0

3

𝑥7

0

0

1

2

(2)

𝒆 1 (2)

(2)


𝑌𝑘

0

5

−1

0

1

0

[0

0

0

1 ] [1]

(2)

KK (2)

𝑃3

𝑥𝐵

𝑌𝑘

𝑥0

0

0

0

0

5

𝑥5

1

-1

-1

-5

-3

𝑥6

0

1

0

3

2*

𝑥7

0

0

1

2

1

(1)

−3

0

𝑃2

Nilai 𝑌𝑘

5

0

𝑃1

VDB

(2)

𝑃3

=

EK (2)

0

1 −1

(𝟐)

(2)

(2)

𝑃2

𝑌𝑘

=

Masukan nilai 𝒀𝒌 pada table: (2)

𝑃1

0

0

(2)

(2)

𝑃1

VDB

2

2 [1]

BK = terkecil Rasio 0 =0 5 −5 5 = −3 3 3 2 2 =2 1


simpleks dengan menentukan kolom kunci, baris kunci dan elemen kunci, yaitu:


Page 61

Baris Kunci :

0

1

0

3

dibagi 2 1

0 Untuk 𝑥0 :

0 0

3

0

2

0

2

0 0

1 2

0 3 2

5

5

−2

0 Untuk 𝑥5 :

1 0

−

0

-1

-1 0

1 2 1

3 2

Untuk 𝑥7 :

0 0

1 -2

-1

2

0

1 0

1 2

2

-5

-3 1

15

2 3 2

1

1

−2

0

1

1

2

Tabel Iterasi I 𝑃1

(2)

𝑃2

𝑥0

0

−

𝑥5

1

𝑥1

0

𝑥7

0

VDB

(2)

5 2 1 2 1 2 1 − 2

(2)

𝑃3

0 -1 0 1


(2)

𝑥𝐵 15 − 2 1 − 2 3 2 1 2

(2)

𝑌𝑘

Rasio

Page 62

𝒆 1

0

0 (2)

(2)


Masukan nilai

(𝟐) 𝒀𝒌

𝑌𝑘

(2)

𝑃2

𝑥0

0

−

𝑥5

1

𝑥1

𝑥7

(1)

Nilai 𝑌𝑘

(2)

𝑃2

5

−2

0

1

1

−1

2

(2)

𝑃3

1 2

3

1

−2

0

=

= 0

0

[0

0

1

0

2 1

−2

1]

1

1

2

[1]

1

[

2

]

pada table:

𝑃1

VDB

(2)

𝑃1

(2)

(2)

(2)

(2)

𝑥𝐵

0

−

1 2

-1

−

0

1 2

0

3 2

1 2

0

−

1

1 2

1 ∗ 2

𝑃3

5 2

1 2

Rasio 15 − 2 = −15 1 2 1 − 2=1 1 − 2 3 2 =3 1 2 1 2 =1 1 2

𝑌𝑘

15 2

1 2

1 2

−

1 2


simpleks dengan menentukan kolom kunci, baris kunci dan elemen kunci, yaitu: Baris Kunci :

1

0

−2

1

0

-1

2

0 0

−2 -1

0 2

0

-2

-1

1 2

1

dibagi 2

Untuk 𝑥0 :

5

1 2


1 −

15 2

1 8

Page 63

Untuk 𝑥5 :

1

1 0

-1

-1 2

0

0

2

1

-2 1 0

1

−2 1 Untuk 𝑥1 :

1

0 0

-1

0 2

1

-1

2

3 2

1 1

1 2

0 Tabel Iterasi II (2) VDB 𝑃1

(2)

𝑃2

(2)

𝑃3

(2)

𝑥𝐵

𝑥0

0

-2

-1

8

𝑥5

1

0

0

0

𝑥1

0

1

-1

1

𝑥2

0

-1

2

1

(2)

𝑌𝑘

Rasio

Pada table diatas terlihat bahwa 𝑥𝑛+1 = 𝑥5 = 0 dan semua variable buatan = 0 maka fase I sudah berakhir dan 𝑧𝑗 − 𝑐𝑗 ≥ 0 maka pemecahan telah optimal yaitu: 𝑧𝑚𝑎𝑘𝑠 = −8

𝑧𝑚𝑖𝑛 = −𝑧𝑚𝑎𝑘𝑠 = −(−8) = 8 pada 𝑥1 = 1 𝑑𝑎𝑛 𝑥2 = 1

Soal – soal : 1. Maksimumkan Kendala

𝑧 = 3𝑥1 + 2𝑥2 𝑥1 + 2𝑥2 ≤ 6 2𝑥1 + 𝑥2 ≤ 8 −𝑥1 + 𝑥2 ≤ 1 𝑥2 ≤ 2 , 𝑥1 , 𝑥2 ≥ 0

2. Minimumkan Kendala

𝑧 = 𝑥1 + 2𝑥2 2𝑥1 + 5𝑥2 ≥ 6 𝑥1 + 𝑥2 ≥ 2 ,


𝑥1 , 𝑥2 ≥ 0

Page 64

BAB VIII TRANSPORTASI 8.1. Perumusan Permasalahan Transportasi Penyelesaian program linier pada metode transportasi dengan memperhatikan perumusan program linier. Contoh 1: Sebuah perusahaan bergerak pada bidang pengolahan makanan yang berasal dari biji-bijian dan salah satu produk yang dihasilkan adalah biji mete yang dikalengkan. Biji mete diolah di tiga pabrik pengalengan dan kemudian diangkut dengan truk ke empat gudang distribusi. Pengiriman produk membutuhkan biaya yang besar, sehingga pimpinan perusahaan merencanakan pengurangan biaya ini sebanyak mungkin. Pengurangan biaya dilakukan dengan menentukan jumlah produk yang dikirim dari masing-masing pabrik ke masing-masing gudang. Untuk musim yang akan datang, dibuat estimasi mengenai kapasitas/suplai dari masing-masing pabrik pengalengan, dan permintaan di setiap gudang distribusi. Informasi ini (dalam satuan angkutan truk), bersama dengan biaya pengiriman perangkutan truk (dalam satuan puluhan ribu rupiah) untuk setiap kombinasi gudang-pabrik pengalengan dalam tabel berikut: Gudang Distribusi

Pabrik Pengalengan Permintaan

1

2

3

4

Kapasitas (Suplai)

1

315

425

215

517

200

2 3

412 316

358 457

327 320

437 327

330 250

225

280

100

175

775


Page 65

Penyelesaian : Secara keseluruhan ada 775 angkutan truk yang harus dikirimkan. Permasalahannya yaitu menentukan pengiriman ke berbagai kombinasi pabrikgudang yang akan meminimumkan biaya pengiriman total. Bila f = biaya pengiriman total dan xij = jumlah angkutan truk yang harus dikirimkan dari pabrik i ke gudang j, maka f ditentukan oleh nilai-nilai dari 12 variabel. Biaya pengiriman total dapat ditulis sebagai berikut : f = 315x11 + 425x12 + 215x13 + 517x14 + 412x21 + 358x22 + 327x23 + 437x24 + 316x31 +457x32 + 320x33 + 327x34 Sedangkan kendala pada pabrik dan gudangnya sebagai berikut : x11 + x12 + x13 + x14

 200

(suplai dari Pabrik 1)

x21 + x22 + x23 + x24

 330


x31 + x32 + x33 + x34

 250


x11+ x21+ x31

 225

(permintaan ke Gudang 1)

x12 + x22+ x32

 280


x13 + x23 + x33

 100


x14 + x24 + x34

 175


xij ≥0,

(i = 1, 2, 3 ; j = 1, 2, 3, 4)

model program linier tersebut dapat diselesaikan dengan menggunakan metode simplex. Penyelesaian optimal dari model tersebut adalah sebagai berikut f = 2.547.650.000 dengan x11 = 100, x13 = 100, x21 = 50, x22 = 280, x31 = 75 dan x34 = 175.


Page 66

Ilustrasi secara grafik persoalan perusahaan dan penyelesaian optimalnya berikut dengan variabel xij dinyatakan sebagai garis, menghubungkan titik suplai ke i (Pabrik i) dengan permintaan ke j (Gudang j), terlihat pada gambar berikut: Pabrik

s1 = 200

P

Gudang G

x11 = 100 x12 = 0

1

x14 = 0

1

x13 = 100 G

s2 = 330

P 2

x21 = 50 x22 = 280 x23 = 0 x24 = 0

s3 = 250

P 3

d2 = 280

2

G x31 = 75

d1 = 225

d3 = 100

3

x32 = 0 x33 = 0

x34 = 175

G 4

Gambar Ilustrasi masalah perusahaan dan penyelesaian optimalnya secara grafik Koefisien-koefisien kendala dari masalah transportasi yang memiliki pola tertentu merupakan bentuk sederhana dari matriks koefisien dari program linier biasa pada tabel berikut: 1 1 1 1    1 1 1 1    1 1 1 1   A  1 1 1    1 1 1   1 1 1    1 1 1  


Kendala-kendala pengalengan

Kendala-kendala gudang

Page 67

d4 = 175

Secara umum permasalahan transportasi dispesifikasi sebagai berikut : a. Adanya suatu komoditi b. Adanya kelompok pusat pemasok ( + batas (atas ) suplai )  sumber c. Adanya kelompok pusat penerima ( + batas (bawah ) permintaan )  tujuan d. Adanya jalur penghubung : sumber-tujuan ( + ongkos satuannya ) e. Adanya fungsi yang diminimalkan : ongkos angkut total Hubungan antara contoh dengan masalah umum, disajikan dalam tabel berikut CONTOH

MASALAH UMUM

Angkutan truk biji mete kalengan

Unit suatu komoditi

Tiga pabrik pengalengan

m sumber

Empat gudang

n tujuan

Kapasitas pabrik i

si suplai dari sumber i

Permintaan ke gudang j

dj permintaan pada tujuan j

Biaya kirim perangkutan dari cij biaya perunit yang didistribusikan dari pabrik i ke gudang j sumber i ke tujuan j Secara umum sumber i ( i = 1, 2, …, m ) mempunyai suplai si unit, dan tujuan j ( j = 1, 2, …, n ) mempunyai permintaan dj unit. Biaya pendistribusian unit-unit dari sumber i ke tujuan j, per unitnya adalah cij , data di atas terlihat dalam tabel berikut: Tujuan

Sumber

Suplai

1

2

….

n

1

c11

c12

….

c1n

s1

2 … m

c21 …. cm1

c22 …. cm2

…. …. ….

c2n …. cmn

s2 …. sm

d1

d2

….

dn

Permintaan


dj

si

Page 68

Misalkan xij = jumlah satuan barang yang dikirim dari sumber i ke tujuan j, maka rumusan masalah transportasi secara umum yaitu: Meminimalkan

f    cij x ij i

j

n

dengan syarat

(fungsi tujuan)

 x ij  s i

( i = 1, 2, …, m )

(kendala suplai)

j1

m

 x ij  d j

( j = 1, 2, …, n )

(kendala permintaan)

i 1

xij  0

( i = 1, 2, …, m; j = 1, 2, …, n ) (kendala tak negatif)

Berdasarkan  si = penawaran total &  dj = permintaan total, kita memiliki beberapa keadaan untuk masalah transportasi : a.  si =  dj, maka kita memiliki transportasi setimbang b.  si >  dj, maka kita memiliki masalah transportasi yang tidak seimbang tetapi fisibel c.  si <  dj, maka kita memiliki masalah transportasi yang tidak setimbang dan tidak fisibel Permasalahan transportasi yang tidak setimbang perlu disetimbangkan terlebih dahulu, yaitu:  keadaan (b), masalah transportasinya dapat disetimbangkan dengan menambahkan dengan tujuan dummy (buatan) dan permintaan semu.  keadaan (c), kadangkala perlu juga tidak memenuhi beberapa permintaan, namun ada sangsi yang berkaitan dengannya, masalah transportasinya disetimbangkan dengan menambahkan dengan sumber dummy (buatan) dan suplai semu. Permaasalah transportasi yang setimbang dapat dirumuskan yaitu: Meminimalkan

f    c ij x ij i

(fungsi tujuan)

j


Page 69

dengan syarat

( i = 1, 2, …, m )

n

 x ij  s i

j1 m

(kendala suplai)

( j = 1, 2, …, n )

 x ij  d j

(kendala permintaan)

i 1

xij  0

( i = 1, 2, …, m; j = 1, 2, …, n ) (kendala tak negatif)

Contoh 2 : Sebuah perusahaan pengalengan buah-buahan akan mengirimkan beberapa trailer dari beberapa pabrik pengolahan ke beberapa gudang penyimpanan, dengan rincian biaya (dalam jutaan rupiah) transportasi setiap trilernya disajikan pada tabel berikut Gudang 1

Gudang 2

3 4 5

5 3 2

4 2 4

25

50

10

Pabrik 1 Pabrik 2 Pabrik 3

Gudang 3 35 35 20

Tentukan banyaknya trailer yang akan dikirim dari pabrik ke gudang yang akan mengoptimalkan biaya transportasi totalnya. Penyelesaian Masalah transportasi di atas memiliki jumlah total suplai melebihi jumlah total permintaan, masalah transportasi tersebut dapat disetimbangkan dengan menambahkan variabel tujuan dummy dalam hal ini Gudang Dummy, dan permintaan semu sehingga tabel masalah transportasi di atas menjadi seperti berikut Pabrik 1 Pabrik 2 Pabrik 3

Gudang 1 3 4 5

Gudang 2 5 3 2

25

50

Gudang 3 4 2 4 10

Gudang Dummy 0 0 0

35 35 20

5

Langkah berikutnya untuk menyelesaikan masalah transportasi di atas dapat dilihat pada pembahasan selanjutnya.


Page 70

Contoh 3 : Sebuah perusahaan pengalengan ikan akan mengirimkan beberapa truk dari beberapa pabrik ke beberapa gudang penyimpanan, dengan rincian biaya ( dalam ratusan ribu rupiah ) transportasi setiap truknya disajikan pada tabel berikut Pabrik 1 Pabrik 2 Pabrik 3

Gudang 1 3 4 5

Gudang 2 5 3 3

20

50

Gudang 3 3 2 4

Gudang 4 4 3 2

30

40 50 30

30

Tentukan banyaknya truk yang akan dikirim dari pabrik ke gudang yang akan mengoptimalkan biaya transportasi totalnya. Penyelesaian Masalah transportasi di atas memiliki jumlah total permintaan melebihi jumlah total suplai, masalah transportasi tersebut dapat disetimbangkan dengan menambahkan variabel sumber dummy dalam hal ini Pabrik Dummy, dan suplai semu sehingga tabel masalah transportasi di atas menjadi seperti berikut

Pabrik 1 Pabrik 2 Pabrik 3 Pabrik Dummy

Gudang 1

Gudang 2

Gudang 3

Gudang 4

3 4 5 0

5 3 3 0

3 2 4 0

4 3 2 0

20

50

30

30

Langkah berikutnya untuk menyelesaikan masalah transportasi di atas dapat dilihat pada pembahasan selanjutnya.

8.2. Penyelesaian Permasalahan Transportasi Penyelesaian masalah transportasi, ada beberapa metode untuk menentukan penyelesaian awal basis yang fisibel dan metode untuk menentukan suatu nilai bagi pengujian optimalitasnya.


Page 71

40 50 30 10

Adapun langkah penting dalam menyelesaikan masalah transportasi, yaitu:  Menyusun tabel awal Method)

⇒

Sudut Barat Laut (Northwest Corner

⇒ Vogel (Vogel’s Approximation Method) ⇒ cij terkecil (Minimum Cost Method)  Uji optimalitas, dengan menghitung c'ij MODI (Modified Distribution Method)  Menyusun tabel baru 1. Menyusun Tabel awal Menyusun tabel awal di sini adalah menentukan Penyelesaian Basis Awal yang Fisibel (PBAF). Masalah transportasi dengan m sumber dan n tujuan yang setimbang mempunyai mn variabel dan m+n persamaan kendala utama, namun ada satu persamaan yang dependen (artinya apabila sekumpulan dari nilai-nilai xij memenuhi m + n – 1 persamaan maka otomatis sekumpulan xij itu memenuhi satu persamaan sisanya) sehingga masalah transportasi tersebut hanya memiliki m + n – 1 persamaan yang independen. Jadi, seperti pada metode simpleks, penyelesaian basis fisibelnya memiliki m + n – 1 variabel basis. Bentuk penyelesaian basis fisibel (PBF) 1

2

…

N

suplai

1

50

50

…

0

100

2

0

50

…

0

…

…

…

…

50  variabel bebas yang dinolkan (kotak kosong) … …

M

0

0

…

50

permintaan

50

100

…

50   variabel basis sebanyak m + n – 1 (kotak isi) 50 …

Kesepakatannya yaitu:  Alokasi nol tak ditulis (kotak kosong)  “kotak” = cell = jalur dari suatu sumber ke suatu tujuan


Page 72

Degenerate (merosot) yaitu adanya variabel basis yang bernilai nol. Dalam simplex degenerate bukan menjadi masalah, tetapi dalam transportasi PBF tidak boleh merosot (harus ada m+n–1 kotak isi). Apabila terjadi degenerate maka penentuan ongkos kesempatan (c'ij) untuk uji optimalitas tidak dapat dilakukan (berhubungan dengan jalur tertutup). a.

Metode Sudut Barat Laut Untuk mendapatkan suatu PBF (metode apa saja) setiap kali mengisi alokasi, isikan dengan nilai yang maksimal. Pada Metode sudut barat laut atau sudut kiri atas biaya transportasi perunit angkutannya tidak diperhatikan, hanya memperhatikan suplai yang telah habis atau permintaan yang sudah dipenuhi. Aturan sudut barat laut prosedurnya dapat dinyatakan sebagai berikut :  Alokasikan sebesar α11 pada kotak di posisi sudut kiri atas yakni kotak k11 (variabel x11) , besarnya α11 = min {s1, d1}  Pada baris 1 dan kolom 1 kurangkan nilai s1 dan d1 dengan α11. Pada baris (kolom) yang sisa suplai (permintaan) nya sama dengan nol (= 0), beri tanda silang, “x” (sudah jenuh). Jika pada baris (kolom) sisa suplai (permintaan) keduanya sama dengan nol maka beri tanda silang pada salah satu saja kolom atau baris.  Jika kolom yang disilang, alokasikan sebesar α12 pada kotak k12, α12 = min {s1- α11, d2}. Jika baris yang disilang, alokasikan sebesar α21 pada kotak k21, α 21 = min {s2, d1 – α11} .  Ulangi proses di atas pada baris (kolom) yang ada, sampai kotak di posisi sudut kanan bawah terisi.


Page 73

Contoh 4 : Perhatikan

masalah

transportasi

yang

biaya

transportasi

perunit

angkutannya (dalam ratusan ribu rupiah) disajikan pada tabel berikut : D1

D2

D3

suplai

O1

5

4

4,5

50

O2

4,5

4

5,5

40

permintaan

30

30

30

90

Penyelesaian  α11 = min {30, 50} = 30 diisikan pada kotak k11, variabel x11 = 30  Sisa suplai pada baris 1 = 50 – 30 = 20, sedang sisa permintaan pada kolom 1 = 30 – 30 = 0, maka kolom 1 diberi tanda silang (jenuh). Hasilnya yaitu: O1 O2 permintaan

D1 30

D2

D3

0 x

30

30

suplai 20 40 90

 Karena kolomnya disilang maka α12 = min {50-30, 30} = 20 diisikan pada kotak k12.  Sisa suplai pada baris 1 = 20 – 20 = 0, sedang sisa permintaan pada kolom 2 = 30 – 20 = 10, maka baris 1 diberi tanda silang. Hasilnya yaitu:

O1

D1

D2

30

20

D3

0

O2 permintaan

suplai

40 0

10

30

90

x


Page 74

x

 Barisnya disilang maka α22 = min {30-20, 40} = 10 diisikan pada kotak k22. Sisa suplai pada baris 2 = 40 – 10 = 30, sedang pada kolom 2 = 10 – 10 = 0, kolom 2 diberi tanda silang. Hasilnya yaitu:

O1

D1

D2

30

20

0

10

30

O2 permintaan

0

0

x

x

D3

suplai

30

x

90

 Kolomnya disilang maka α23 = min {40-10, 30} = 30 diisikan pada kotak k23. Karena kotak k23 merupakan kotak di posisi sudut kanan bawah maka proses selesai. Hasilnya yaitu:

O1

D1

D2

30

20

O2 permintaan

D3

suplai 0

10

30

30

0

0

30

90

x

x

x

Dari proses di atas diperoleh PBAF yang fisibel serta arah pengisiannya sebagai berikut

O1

D1

D2

30 

20 

O2 permintaan

30

D3

suplai 50

10 

30

40

30

30

90

Kotak isi = 4 = m + n – 1, sehingga diperoleh PBF dengan nilai fungsi tujuannya adalah f = 5(30) + 4(20) + 4(10) + 5,5(30) = 435 ratusan ribu rupiah.


Page 75

b. Biaya terkecil Metode ini dengan memperhatikan/memeriksa seluruh biaya. Pemilihan kotak yang akan diisi berdasarkan biaya terkecil. Langkah metode biaya terkecil yaitu :  Pilih kotak yang memiliki biaya terkecil (apabila ada lebih dari satu maka pilih yang dapat diberi alokasi paling besar), misal kotak yang terpilih adalah kij , selanjutnya alokasikan sebesar αij dengan αij = min {si , dj}.  Pada baris i dan kolom j kurangkan nilai si dan dj dengan αij. Pada baris maupun kolom yang sisa suplai maupun permintaannya sama dengan nol beri tanda silang.  Ulangi proses di atas sampai semua baris dan kolomnya jenuh. Contoh 5 : Perhatikan

masalah

transportasi

yang

biaya

transportasi

perunit

angkutannya (ratusan ribu rupiah) disajikan pada tabel berikut : 1

2

3

suplai

1

4

5

2

400

2

1

5

6

400

3

2

2

4

400

4

7

9

7

400

permintaan

500

500

600

1600

Penyelesaian  Kotak k21 memiliki nilai cij yang terkecil, maka kotak k21 diberi alokasi sebesar α21 = min {400, 500}  Pada baris 2 sisa suplainya 400 – 400 = 0, sedangkan pada kolom 1 sisa permintaannya 500 – 400 = 100 sehingga baris 2 diberi tanda silang.


Page 76

Hasilnya yaitu : 1 1 2 3 4

400

2

3

4

5

2

1

5

6

2

2

4

7

9

7

100

500

600

400 0 400 400 1600

x

 Ternyata ada tiga kotak yang memiliki nilai cij terkecil, yaitu kotak k13, k31 dan k32. Terbesar untuk ketiga kotak adalah 400 (= maks{min {s1 = 400, d3 = 600}, min {s3 = 400, d1 = 100}, min {s3 = 400, d2 = 500}}= maks {400, 100, 400}) yaitu pada kotak k13 dan k32, karena itu pilih salah satu kotak untuk diberi alokasi sebesar 400 (misalkan dipilih kotak k13, artinya α13 = 400).  Pada baris 1 sisa suplainya 400 – 400 = 0, sedangkan pada kolom 3 sisa permintaannya 600 – 400 = 200 sehingga baris 1 diberi tanda silang. Hasilnya yaitu : 1 1 2 3 4

400

2

3 400

4

5

1

5

6

2

2

4

7

9

7

100

500

2

200

0 0 400 400 1600

x x

 Apabila proses di atas dilakukan terus akan diperoleh hasil yaitu: 1 1 2 3 4

400 100 0 x

2

3 400

4

5

1

5

6

2

400 2 100 9 100

4

7


200 0 x

2

7

0 0 0 400 1600

x x x

Page 77

Sehingga diperoleh PBAF seperti berikan pada tabel berikut : 1 1 2 400 3 4 100 500

2

3 400

4

5

1

5

6

2

4

2 7

400 100 500

9

200 600

2

7

400 400 400 400 1600

Kotak isi = 6 = m+n-1, sehingga diperoleh PBAF dengan nilai fungsi tujuannya adalah c.

f = Rp.500 juta.

Metode Pendekatan Vogel Pada metode vogel dengan memperhatikan selisih antar dua biaya terendah, pada setiap baris dan kolomnya. Pemilihan kotak yang akan diisi berdasarkan kolom atau baris yang nilai selisihnya terbesar dan biaya terkecil pada kotaknya. Langkahnya yaitu:  Pada setiap baris dan kolom, tentukan nilai selisih dari dua biaya terkecil dan letakkan nilai itu di samping (di bawah) masing-masing baris (kolom)  Pilih salah satu dari baris dan kolom yang memiliki nilai selisih yang paling besar. Pada baris/kolom yang terpilih, pilih kotak kosong dengan biaya terendah. Misalkan kotak yang terpilih adalah kotak kij, lalu alokasikan sebesar αij yaitu αij = min {si , dj}  Pada baris i dan kolom j kurangkan nilai si dan dj dengan αij. Pada baris maupun kolom yang sisa suplai maupun permintaannya sama dengan nol, beri tanda silang.  Ulangi proses di atas sampai semua baris dan kolomnya jenuh.


Page 78

Contoh 6 : Perhatikan

masalah

transportasi

yang

biaya

transportasi

perunit

angkutannya (ratusan ribu rupiah) disajikan pada tabel berikut :

1 2 3 4 permintaan

1

2

3

suplai

7 2 2 4 500

3 4 1 5 500

3 5 7 6 600

400 400 400 400 1600

Penyelesaian  Pada baris 1, 2, 3 dan 4 selisih biaya terkecilnya masing-masing 0, 2, 1 dan 1, sementara untuk kolom 1,2 dan 3 masing-masing 0, 2 dan 2.  Nilai selisih terbesarnya adalah 2, ada tiga pilihan, dipilih yang memiliki biaya terkecil, yakni kolom 2. Pada kolom 2 dipilih kotak dengan biaya terendah yakni kotak k32 dan mendapat alokasi sebesar α32 = min {400, 500} = 400, α32 = 400.  Sisa suplai pada baris 3 adalah 400 – 400 = 0, sehingga baris 3 diberi tanda silang. Sementara sisa pada kolom 2 adalah 500 – 400 = 100.  Dengan pengulangan proses di atas akan didapatkan hasil sebagai berikut : 1

2

1

3 400

7

3

3

4

5

2 400 2

3

400 2

1

7

4

5

6

4 100 0 2 3

100 2 1 2

200 2 2 3

0

0

0

0

0

2

2

x

0

1

x

x

400

1

1

1

x

1600


Page 79

 Pada bagian ini pengisiannya memilih kotak dengan biaya terkecil, sehingga diperoleh hasil 1 1 2

400

3 4

100

2

3

7

3

3

0

0

0

0

2

4

5

0

2

2

x

7

0

1

x

x

6

200

1

1

1

2

400

1

4

100

5

400

200

0

0

200

0 2 3 x

2 1 2 x

2 2 3

x

1600

Sehingga diperoleh PBAF seperti berikan pada tabel berikut : 1 1 2

400

3 4

100 0

2

3

7

3

3

0

2

4

5

0

7

0

6

200

2

400

1

4

100

5

400

200

0

200

1600

Kotak isi = 6 = m + n – 1, diperoleh PBAF ,dengan nilai f = 450.000.000 rupiah. Vogel

menentukan penempatan kotak kolom / baris semu tak diperhitungkan dalam memberi nilai selisih 2 nilai terkecil.


Page 80

2. Uji Optimalitas dan Menyusun Tabel Baru (PBF berikutnya) Setelah mendapatkan PBF, untuk menentukan apakah penyelesaian yang didapatkan optimal maka dilakukan uji optimalitas. Uji optimalitas dilakukan dengan menentukan nilai Oportunity cost (ongkos kesempatan) yang dinotasikan dengan c'ij. Apabila c'ij bernilai negatif atau nol untuk setiap variabel nonbasis maka penyelesaian basis fisibelnya sudah optimal. Penyelesaian optimal   variabel nonbasis xij nilai c'ij  0 Contoh 7 : Perhatikan PBF masalah transportasi berikut, apakah sudah optimal ?. D1 O1 O2

D2 2

30

1

10 40

30

40 40 40 80

5 2

50

Penyelesaian Variabel basis : x11 = 30, x12 = 10, x22 = 40, dan variabel nonbasis : x21 = 0 Nilai fungsi tujuannya adalah

f = 30.2 + 10.5 + 40.2 =190, apakah

penyelesaiannya optimal? (minimal ?). Kita coba mengujinya dengan menambah nilai variabel nonbasis dengan 1 unit, yakni x21 = 0 + 1 = 1, sehingga penyelesaiannya akan berubah menjadi seperti berikut O1 O2

D1 30 – 1 0+1 30

2 1

D2 10 + 1 40 – 1 50

5 2

40 40 40 80

Nilai fungsi tujuannya adalah f ' = (30 – 1).2 + (10 + 1).5 + (40 – 1).2 + (0 + 1).1 = 192, ternyata lebih besar dari nilai fungsi tujuan sebelumnya. Jadi selisih antara kedua nilai fungsi tujuan adalah sebagai berikut f = f '– f = – 2 + 5 – 29 + 1 = 2. Jelas bahwa apabila x21 menjadi variabel basis maka nilai fungsi tujuannya akan naik, jadi penyelesaian yang telah kita peroleh sebelumnya adalah sudah optimal.


Page 81

Contoh 8 : Perhatikan PBF masalah transportasi berikut, apakah sudah optimal ?. D1 O1 O2

D2 4

50

1

50

2

10 40

4

50

60 40 100

Penyelesaian Variabel basis : x11 = 50, x12 = 10, x22 = 40, dan variabel nonbasis : x21 = 0 Nilai fungsi tujuannya adalah f = 50.4 + 10.2 + 40.4 = 380. Sedangkan apabila variabel nonbasis x21 nilainya ditambah 1, maka nilai fungsi tujuannya berubah menjadi f ' = (50 – 1).4 + (10 + 1).2 + (40 – 1).4 + (0 + 1).1 = 375. Sehingga selisih kedua fungsi tujuannya adalah ∆f = f '– f = – 5. Jadi f ' < f , hal ini berarti bahwa 1 unit satuan komoditas yang dialokasikan pada variabel nonbasis x21 atau kotak K21 akan menurunkan nilai f sebanyak 5 unit satuan biaya. Dengan kata lain penyelesaian yang kita peroleh sebelumnya belum optimal. Satu unit variabel nonbasis x21 bisa menurunkan nilai f sebesar 5 unit, dapat dikatakan bahwa ongkos kesempatan dari variabel nonbasis x21 (kotak kosong K21) adalah 5, c'ij = 5. c'ij = – ∆ fij cara menentukan nilai ongkos kesempatan, c'ij , dan penyusunan tabel baru yaitu MODI (Modified Distribution). 3. MODI a. Menghitung c'ij Metode MODI nilai cij dihitung untuk semua variabel nonbasis, bila PBF belum optimal maka perubahan PBF dilakukan dengan terlebih dahulu membuat loop untuk variabel nonbasis yang akan menjadi variabel basis.


Page 82

Untuk menentukan nilai cij ada beberapa istilah dan rumusan yang akan dipakai untuk memudahkan dalam perhitungannya. Istilah tersebut adalah ui = bilangan baris yang diletakkan pada kolom paling kanan, sedangkan vj = bilangan kolom diletakkan pada baris spaling bawah. Sedangkan rumusan yang akan dipakai adalah sebagai berikut :  pada kotak isi (variabel basis) berlaku hubungan ui + vj = cij atau ui + vj – cij = 0  pada kotak kosong (variabel nonbasis) berlaku hubungan ui + vj – cij = c'ij (ongkos kesempatan) Untuk menentukan nilai-nilai ui , vj dan c'ij , pertama diberikan nilai u1 = 0 (bisa juga ui atau vj yang lain) kemudian dicari nilai-nilai ui dan vj yang lain dengan menggunakan rumusan di atas, lantas akan dapat ditentukan nilai c'ij dari rumus di atas. Contoh 10 : Perhatikan PBF masalah transportasi berikut, apakah sudah optimal ?. (Biaya dalam jutaan rupiah) 1

2 4

1 2

400

1

3

100

2 7

4 500

3 5

400

5

300

2

200

9

500

200 600


2

400

6

400

4

400

7

400 1600

Page 83

Penyelesaian Dari PBF di atas kita tambah baris dan kolom untuk ui , vj dan kita beri nilai u1 = 0, akan diperoleh tabel berikut 1 1

2

3

4

5

2

400

u1 = 0

5

6

400

u2 = ?

4

400

u3 = ?

7

400

u4 = ?

2

400

1

3

100

2

300

2

7

200

9

4

vj

ui

400

200

500

500

600

1600

v1 = ?

v2 = ?

v3 = ?

Dengan menggunakan ketentuan ui +

vj = cij pada kotak isi akan

mendapatkan berbagai nilai ui dan vj berikut u1 + v3 = c13  0 + v3 = 2  v3 = 2

u4 + v3 = c43  u4 + 2 = 7  u4 = 5

u4 + v2 = c42  5 + v2 = 9  v2 = 4

u3 + v2 = c32  u3 + 4 = 2  u3 = – 2

u3 + v1 = c31  – 2 + v1 = 2  v1 = 4

u2 + v1 = c21  u2 + 4 = 1  u2 = – 3

Tabel PBF di atas dapat ditulis sebagai berikut: 1

2 4

1 2

400

1

3

100

2

7

4

vj

3 5

400

5

300

2

200

9

200

500

500

600

v1 = 4

v2 = 4

v3 = 2


ui 2

400

u1 = 0

6

400

u2 = – 3

4

400

u3 = – 2

7

400

u4 = 5

1600

Page 84

Dengan menggunakan ketentuan ui + vj – cij = c'ij akan diperoleh nilai c'ij untuk setiap kotak kosong. Hasilnya adalah sebagai berikut c'11 = u1 + v1 – c11 = 0,

c'22 = u2 + v2 – c22 = – 4,

c'33 = u3 + v3 – c33 = – 4,

c'12 = u1 + v2 – c12 = – 1, c'23 = u2 + v3 – c23 = – 7,

c'41 = u4 + v1 – c41 = 2

Apabila kita letakkan pada tabel di atas kita peroleh tabel berikut 1

2 4

1

400

5

1

5 –4

3

100

400

ui 2

400

u1 = 0

6

400

u2 = – 3

4

400

u3 = – 2

7

400

u4 = 5

–1

0

2

3

2

–7

300

2

200

9

–4 7

4

200

2

vj

500

500

600

v1 = 4

v2 = 4

v3 = 2

1600

Dari di atas terlihat bahwa masih ada variabel nonbasis dengan nilai c'ij positif, yakni x41. Jadi PBF tersebut belum optimal dan variabel nonbasis x41 akan menjadi variabel basis baru. Karena belum optimal, PBF akan diubah pada langkah berikut ini. b. Menyusun Tabel baru Variabel x41 menjadi variabel basis baru, untuk mengalokasikan komoditasnya, kita buat loop dari kotak K41 terlebih dahulu. Kita dapatkan loop untuk kotak K41 adalah K41 K31 K32 K42.


Page 85

Kotak K31 dan

K42 adalah donor, masing-masing memiliki alokasi

komoditas 100 dan 200, maka alokasi maksimum untuk kotak K41 adalah α41 = min {200, 100} = 100. Dengan mengalokasikan komoditas sebesar 100 unit, maka jumlah komoditas pada resipien bertambah 100 dan pada donor berkurang 100. Hasilnya dapat dilihat pada tabel berikut, variabel x31 menjadi variabel non basis. 1 3 4

2

100

2

+

7

1

+ 300

2

200

9



2 2

3

2

400 7

4 100

9

100

Kotak isi ada 6, sedangkan m + n – 1 = 6, sehingga diperoleh PBF baru berikut 1 1 2 3 4

400

2 5

1

5

6

2

4

2

400 100 500

7

100 500

3

4

400

9

200 600

2

7

400 400 400 400 1600

Dilakukan proses uji optimalitas kembali, hasil penghitungan ui , vj dan cij untuk variabel nonbasisnya diperoleh tabel berikut 1

2 4

1 –2

2

400

3 5

5

vj

100 500 v1 = 7

6

400

u2 = – 6

4

400

u3 = – 7

7

400 u4 = 0 1600

–5

2

400

2

7

100 500 v2 = 9

9

–2

4

400

ui u1 = – 5

–1 1 –2

3

400

2

–4

200 600 v3 = 7


Page 86

Dari nilai tabel di atas terlihat bahwa nilai c'ij negatif semua, jadi PBF nya sudah optimal, berhenti. Tabel optimalnya adalah sebagai berikut : 1 1 2 3 4

2

3 400

400 100 500

400 100 500

200 600

400 400 400 400 1600

Nilai fungsi tujuannya adalah f = 800 + 400 + 800 + 700 + 900 + 1400 = Rp. 5000 juta.

SOAL-SOAL: 1. Seseorang memiliki 3 pabrik mobil yang terbesar di tiga lokasi dengan kapasitas produksi masing-masing pabrik yaitu pabrik ke-I = 56 unit, pabrik ke-II = 82 unit dan pabrik ke-III = 77 unit. Hasil produksi dari 3 pabrik tersebut akan dialokasikan ke tiga daerah pemasaran. Masing-masingdaerah pemasaran membutuhkan produk yaitu daerah I = 72 unit, daerah 2 = 102 unit dan daerah 3 = 41 unit. Biaya transportasi (dalam ribuan rupiah) dari pabrik ke daerah pemasaran dapat dilihat pada tabel berikut:

Pabrik I Pabrik II Pabrik III

Daerah 1 4 16 8

Daerah 2 8 24 16

Daerah 3 8 16 24

Bagaimana mengalokasikan produk dari pabrik ke daerah pemasaran agar biaya transportasi (pendistribusian) minimum? 2. Tiga pabrik dalam satu group (W, H, P) dengan kapasitas produk maisngmasing adalah 90, 60 dan 50. Hasil produksi aka didistribusikan ke tiga gudang (A, B, C) yang kapasitas penyimpanannya masing-masing adalah 50, 110 dan 40. Tabel biaya pengiriman produk dari pabrik ke gudang ditampilkan pada tabel di bawah ini.


Page 87

Tentukan solusi optimal biaya pengiriman, apabila perusahaan ingin mendistribusikan produk ke masing-masing gudang dengan biaya pengiriman (dalam ribuan rupiah) yang minimal yaitu: Gudang A

Gudang B

Gudang C

Kapasitas Pabrik

Pabrik W

20

5

8

90

Pabrik H

15

20

10

60

Pabrik P

25

10

19

50

Kebutuhan Gudang

50

110

40

200

Dari

Ke

3. Dari 3 pelabuhan A1, A2 dan A3 terdapat semen sebanyak masing-masing 120 ton, 170 ton dan 160 ton. Semen tersebut akan diangkut ke kota T1, T2 dan T3 yang masing-masing mempunyai daya tamping 150 ton, 210 ton, 90 ton. Biaya pengiriman dari pelabuhan A1 ke T1, T2 dan T3 masing-masing adalah 50, 100 dan 100 (dalam ribuan rupiah per ton). Biaya pengiriman dari pelabuhan A2 ke kota T1, T2 dan T3 adalah 200,300 dan 200, sedangkan biaya pengiriman dari pelabuhan A3 ke kota T1, T2 dan T3 adalah 100, 200 dan 300. Tentukan solusi optimal biaya pengiriman!


Page 88

BAB I PENGANTAR PROGRAM LINIER

Recommend Documents