PROGRAM LINIER

MAKALAH

MODEL STANDAR DAN TABEL SIMPLEKS AWAL

()

OLEH:

KELOMPOK 2

1. SASTRI MAYLINDA (4161111066)

2. SISKA UMILA ADHA (41611110)

KELAS : MATEMATIKA DIK C 2016

JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS NEGERI MEDAN

MEDAN

2018

1
 KATA PENGANTAR

Puji dan syukur penulis ucapkan kehadirat Tuhan yang Maha Esa karena atas
berkat Rahmat dan Hidayah-Nya, penulis dapat menyelesaikan makalah yang berjudul
“Model Standar dan Tabel Simpleks Awal” tepat pada waktunya. Makalah ini disusun
guna memenuhi salah satu tugas mata kuliah Program Linier. Sebagaimana telah
disebutkan sebelumnya, didalam makalah ini penulis berusaha menjelaskan tentang model
standar dan tabel simpleks awal.
Makalah yang penulis susun ini belum sempurna, akan tetapi penulis telah berusaha
semaksimal mungkin dalam pembuatan makalah ini. Oleh karena itu, penulis juga ingin
mengucapkan terima kasih kepada semua pihak yang telah membantu dalam pembuatan
makalah ini sampai selesai. Serta ucapan terimakasih penulis sampaikan juga kepada Ibu
Dosen yang telah memberikan tugas ini kepada penulis.
Akhir kata, penulis berharap makalah ini dapat bermanfaat bukan hanya bagi
penulis sendiri namun juga dapat bermanfaat bagi semua orang yang membaca makalah ini
untuk menambah wawasannya. Kritik dan saran yang membangun sangat penulis harapkan
demi kesempurnaan makalah ini.

Medan, September 2018

Penulis

Kelompok 2

2
 DAFTAR ISI

KATA PENGANTAR ........................................................................................................... 2

DAFTAR ISI ......................................................................................................................... 3
BAB I..................................................................................................................................... 4
PENDAHULUAN ................................................................................................................. 4
1.1. Latar Belakang ...................................................................................................... 4
1.2. Rumusan Masalah ................................................................................................ 4
1.3. Tujuan .................................................................................................................... 4
BAB II ................................................................................................................................... 5
PEMBAHASAN.................................................................................................................... 5
2.1 Pengelompokan Data .......................................... Error! Bookmark not defined.
2.2 Tabel distribusi frekuensi .................................. Error! Bookmark not defined.
2.3 Penyusunan Distribusi Frekuensi Menurut Aturan Strugess ................. Error!
Bookmark not defined.
2.4 Contoh Pengelompokan Data dengan Aturan Strugess . Error! Bookmark not
defined.
BAB III ................................................................................................................................ 13
PENUTUP ........................................................................................................................... 13
3.1 Simpulan .............................................................................................................. 13
3.2 Saran .................................................................................................................... 13
DAFTAR PUSTAKA .......................................................................................................... 14

3
 BAB I

PENDAHULUAN

[Link] Belakang
Program linier merupakan metode matematik dalam mengalokasikan
sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan
keuntungan dan meminimumkan biaya. Program Linier banyak diterapkan dalam
masalah ekonomi, industri, militer, sosial dan lain-lain. Konsep dasar program
linier telah ada pada jenjang pendidikan dasar, yang dimulai pengenalan lambang
bilangan yang direpresentasikan melalui gambar benda di sekitar siswa, kemudian
penjumlahan, pengurangan, perkalian serta membandingkan banyaknya benda. Di
Sekolah Menengah Pertama (SMP) konsep diperluas melalui pembelajaran materi
Sistem Persamaan Linier Satu Variabel (SPLSV), kemudian ditingkatkan melalui
materi Sistem Persamaan Linier Dua Variabel (SPLDV), di Sekolah Menengah
Atas (SMA) telah diperkenalkan sistem pertidaksamaan linier dan materi khusus
program linier yang menyajikan persoalan sehari-hari, kemudian menerjemahkan
permasalahan ke dalam model matematika, menyelesaikan sistem pertidaksamaan
yang merupakan kendala atau pembatas, mencari penyelesaian optimum, menjawab
permasalahan. Metode yang digunakan adalah metode grafik dengan menggunakan
uji titiksudut dan garis selidik. Pada tingkat universitas, terdapat mata kuliah
khusus program linier yang membahas metode penyelesaian program linier yang
tujuannya mencari keuntungan maksimum dan mengeluarkan biaya minimum.
Metode yang diberikan pada universitas adalah metode grafik, metode simpleks,
metode analisis dual, metode transportasi

[Link] Masalah
a. Bagaimana bentuk standar program linier?
b. Bagaimana bentuk dan cara penggunaan tabel simpleks awal?

[Link]
a. Mengetahui bentuk standar program linier
b. Mengetahui bentuk dan cara penggunaan tabel simpleks awal

4
 BAB II

PEMBAHASAN

A. Bentuk Standar Program Linier

Perlu dingatkan kembali bahwa permasalahan model program linear dapat
memiliki pembatas-pembatas linear yang bertanda (≤, =, ≥), dan peubah-peubah
keputusannya dapat merupakan peubah non-negatif, dapat pula peubah yang tidak
terbatas dalam tanda (unrestricted in sign).
Dalam menyelesaikan permasalahan program linear dengan metode
simpleks, bentuk dasar yang digunakan haruslah merupakan bentuk standar, yaitu
bentuk formulasi yang memenuhi ketentuan berikut ini:
1. Seluruh pembatas linear harus berbentuk persamaan dengan ruas kanan yang
non-negatif.
2. Seluruh peubah keputusan harus merupakan peu bah non-negatif.
3. Fungsi tujuannya dapat berupa maksimasi atau minimasi.
Beberapa hal yang dapat dilakukan untuk mengubah bentuk permasalahan
program linear yang belum standar ke dalam bentuk standar permasalahan program
linear sesuai dengan 3 ketentuan di atas adalah:
1. Pembatas linear (linear constraint)
a) Pembatas linear bertanda ≤ dapat djadikan suatu persamaan dengan cara
menambahkan ruas kiri dari pembatas linear itu dengan slack variable
(peubah penambah). Slack variable pada umumnya digunakan kelebihan
ruas kanan pembatas linear dibandingkan dengan ruas kirinya. Pada
pembatas linear bertanda ≤, ruas kanan umumnya mewakili batas
ketersediaan sumber daya sedangkan ruas kiri umumnya mewakili
penggunaan sumber daya tersebut yang dibatasi oleh berbagai kegiatan
yang berbeda (peubah) dari suatu model program linear sehingga slack
variable dapat diartikan untuk mewakili jumlah sumber daya yang tidak
dipergunakan.
b) Pembatas linear bertanda ≥ dapat dijadikan suatu persamaan dengan cara
mengurangkan ruas kiri dari pembatas linear itu dengan surplus variable
(peubah penambah negatif). Pada pembatas linear bertanda ruas kanan

5
 umumnya mewakili penetapan persyaratan spesifikasi minimum,
sehingga surplus variable dapat diartikan untuk mewakili jumlah
kelebihan sesuatu dibandingkan spesifikasi minimumnya.
c) Ruas kanan dari suatu persamaan dapat dijadikan bilangan nonnegatif
dengan cara mengalikan kedua ruas dengan -1.
d) Arah pertidaksamaan berubah apabila kedua ruas dikalikan dengan -1.
e) Pembatas linear dengan pertidaksamaan yang ruas kirinya berada dalam
tanda mutlak dapat diubah menjadi dua pertidaksamaan.

2. Peubah keputusan
Suatu peubah keputusan xi yang tidık terbatas dalam tanda dapat
dinyatakan sebagai dua peubah keputusan nonnegatifi dengan menggunakan
subtitusi.
𝑥𝑖 = 𝑥𝑖1 − 𝑥𝑖2
Dimana 𝑥𝑖1 ≥ 0 𝑥𝑖2 ≥ 0. Selanjutnya substitusi ini harus dilakukan pada
seluruh pembatas linear dan fungsi tujuannya.

3. Fungsi tujuan
Walaupun permasalahan model program linear dapat berupa
maksimasi atau minimasi, kadang-kadang diperlukan perubahan dari satu
bentuk ke bentuk lainnya. Dalam hal ini, maksimasi dari suatu fungsi adalah
sama dengan minimasi dari negatif fungsi yang sama. Secara matematis
dapat dinyatakan sebagai berikut :
Maksimumkan z

Sama artinya dengan :

Minimumkan (-z)

6
B. Tabel Simpleks Awal
Metode simpleks diawali dengan standarisasi model. Metode simpleks
dengan tabel jenis ini tidak saja mensyaratkan standarisasi fungsi-fungsi kendala,
tetapi juga standarisasi fungsi tujuan, yakni mengubahnya menajdi persamaan
berbentuk implisit. Secara umum, rumusan model yang standar untuk metode
simpleks dengan tabel berkolom variabel dasar adalah :

Optimumkan 𝑧 − 𝑐1 𝑥1 − 𝑐2 𝑥2 − … − 𝑐𝑛 𝑥𝑛 = 0

Terhadap :
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ± 𝑠1 = 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ± 𝑠2 = 𝑏2
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ± 𝑠𝑚 = 𝑏𝑚

Bentuk tabelnya :
VD z x1 x2 ..... xn s1 s2 ..... sn S
z 1 c1 c2 ..... cn 0 0 ..... 0 0
s1 0 a11 a12 ..... a1n 1 0 ..... 0 b1
s1 0 a21 a22 a2n 0 1 0 b1
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
sm o am1 am2 ..... amn 0 0 ..... 1 bm

Matriks utama matriks satuan

Amxn Inxn

Keterangan :
1. Kolom Variabel Dasar (VD)
Kolom ini berisi variabel-variabel dasar (basic variabeles), disebut juga
variabel-variabel anol (nonzero variables), yaitu variable-variable yang
nilainya ditunjukkan oleh konstanta-konstanta yang bersesuaian di kolom S.
Pada penyelesaian awal atau tabel pertama, kolom VD ini berisi semua variabel
semu. Pada tahap-tahap berikutnya variabel-variabel yang termuat dikolom ini
akan berganti-ganti, kecuali z yang senantiasa hadir di situ sejak penyelesaian
awal hingga penyelesaian akhir. Variabel-variabel lain yang tidak tercantum di

7
 kolom ini dinamakan variabel-variabel dasar (nonbasic variables) atau variabel
nol (zero variables).
2. Kolom z
Kolom ini sebenarnya hanya berfungsi sebagai “pelengkap” isinya selalu sama
(1, 0, 0, ....., 0) sejak penyelesaian awal hingga penyelesaian akhir, karenanya
boleh tidak dicantumkan didalam tabel.
3. Kolom-kolom variabel
Kolom ini berisi koefisien-koefisien dari masing-masing variabel dalam
persamaan yang bersesuaian, yakni aij untuk variabel-variabel asli xj dan 0 atau
1 untuk variabel-variabel semu sj, utnuk tabel pertama (penyelesiaan awal).
4. Kolom S
Kolom S (solution) ini berisi nilai-nilai ruas kanan dari persamaan-persamaan
implisist yang terdapat di dalam model, baik persamaan fungsi tujuan maupun
persamaan-persamaan fungsi kendala. Angka-angka yang tercantum di kolom
S ini mencerminkan nilai z dan nilai-nilai variabel dasar pada tahap
penyelesaian yang bersangkutan.

Langkah-langkah pengerjaan :

Langkah-langkah pengerjaan programasi linear secara simpleks dengan

tabel berkolom variabel dasar adalah sebagai berikut :

1. Rumuskan dan standarisasikan modelnya.

2. Bentuk tabel pertama dengan menetapkan semua variabel semu sebagai
variabel dasar (semua variabel asli sebagai variabel dasar).
3. Tentukan satu “variabel pendatang” (entering variable) diantara variabel-
variabel dasar yang ada, untuk dijadikan variabel dasar dalam tabel berikutnya.
Variabel pendatang ialah variabel dasar yang nilainya pada baris-z paling
negatif dalam kasus minimisasi.
4. Tentukan satu “variabel perantau” (leaving variable) diantara variabel-variabel
dasar yang ada, utnuk menjadi variabel dasar dalam tabel berikutnya. Variabel
perantau ialah variabel dasar yang memiliki “rasio solusi” dengan nilai positif
terkecil.
5. Bentuk tabel berikutnya dengan memasukkan variabel pendatang ke kolom VD
dan mengeluarkan variabel perantau dari kolom VD, serta lakukan transformasi
baris-baris tabel, termasuk baris-z.
6. Lakukan pengujian optimalitas. Jika semua koefisien variabel dasar pada baris-
z sudah tidak ada lagi yang negatif (untuk kasus maksimisasi; atau sudah tidak
ada lagi yang positif, untuk kasus minimisasi), berarti penyelesaian sudah
optimal, tidak perlu dibentuk tabel selanjutnya. Jika masih, berarti penyelesaian
belum optimal, ulangi lagi langkah ke-3 sampai ke-6.

8
Contoh :

PT “Double X” memproduksi dua macam barang, X1 dan X2 masing-masing mendatangkan

profit 25 ribu dan 15 rupiah per unit. Produk X1 dibuat dari campuran masukan-masukan
K, L, dan M. Sedangkan X2 hanya dibuat dari campuran K dan L. Tiap unit X1 terdiri atas
3K 2L dan 3M, sementara tiap unit hanya terdiri atas 3 unit K dan 4 unit L. Jumlah
masukan yang tersedia untuk diolah masing-masing tidak melebihi 24 unit K, 20 unit L
dan 21 unit M per menit. Berapa unit masing-masing barang harus dihasilkan per menit
agar profit optimal?

Penyelesaian :

Maksimumkan z = 25 x1 + 15 x2

Terhadap 3𝑥1 + 3𝑥2 ≤ 24 … … … (𝑘𝑒𝑛𝑑𝑎𝑙𝑎 𝑚𝑎𝑠𝑢𝑘𝑎𝑛 𝐾)

2𝑥1 + 4𝑥2 ≤ 20 … … … (𝑘𝑒𝑛𝑑𝑎𝑙𝑎 𝑚𝑎𝑠𝑢𝑘𝑎𝑛 𝐿)

3𝑥1 ≤ 21 … … … (𝑘𝑒𝑛𝑑𝑎𝑙𝑎 𝑚𝑎𝑠𝑢𝑘𝑎𝑛 𝑀)

𝑥1 , 𝑥2 ≤ 0

Model standarnya :

Maksimumkan 𝑧 − 25𝑥1 − 15𝑥2 = 0

Terhadap 3𝑥1 + 3𝑥2 + 𝑠1 = 24

2𝑥1 + 4𝑥2 + +𝑠2 = 24

3𝑥1 + 𝑠3 = 21

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

Model yang standar ini bisa langsung diterjemahkan menjadi tabel pertama dengan
menempatkan variabel-variabel semu (dalam hal ini variabel senjang atau slack variable)
s1 s2 serta s3 sebagai variabel-variabel dasar.

Tabel 1.

VD Z x1 x1 s1 s2 s3 S
z 1 -25 -15 0 0 0 0
s1 0 3 3 1 0 0 24
s2 0 2 4 0 1 0 20
s3 0 3 0 0 0 1 21

Pada tahap ini x1dan x1 merupakan variabel-variabel dasar, sebab tidak tercantum pad
kolom VD. Langkah kita yang berikut ialah menentukan variabel pendatang dan variabel

9
perantau, agar dapat membentuk tabel berikutnya. Dalam kasus (maksimisasi) ini, variabel
pendatangnya adalah x1 karena nilainya pada baris z paling negatif. Konsekuensinya,
kolom x1 merupakan kolom kunci. Dari sini bisa dihitung rasio solusi untuk masing-maisng
variabel dasar. Rasio solusi untuk s1 adalah 24/3 = 8, utnuk s2 adalah 20/2 = 10, sedangkan
untuk s3 merupakan variabel perantau dan konsekuensinya, barisnya merupakan baris
kunci. Dengan dapat ditentunkannya baris kunci dan kolom kunci, maka unsur kunci bisa
ditetapkan.

Transformasi baris kunci (x1 menggantikan s3).

x1 0/3 3/3 0/3 0/3 0/3 1/3 21/3

x1 0 1 0 0 0 1/3 7

Transformasi baris -z Transformasi baris - s1 Transformasi baris - s2

1 — (−25) 0 = 1 0 — (3) 0 = 0 0 — (2) 0 = 0
−25 — (−25) 1 = 1 3 — (3) 1 = 0 2 — (2) 1 = 0
−15 — (−25) 0 3 — (3) 0 = 3 4 — (2) 0 = 4
= −15 1 — (3) 0 = 1 0 — (2) 0 = 0
0 — (−25) 0 = 0 0 — (3) 0 = 0 1 — (2) 0 = 1
0 — (−25) 0 = 0 0 — (3) (1/3) = 0 0 — (2) (1/3)
0 — (−25)(1/3) 24 — (3) 7 = 3 = −2/3
= 25/3 20 — (2) 7 = 6
1 — (−25) 7 = 175

Tabel 2.

VD Z x1 x2 s1 s2 s3 S
z 1 0 -15 0 0 25/3 175
s1 0 0 3 1 0 -1 3
s2 0 0 4 0 1 -2/3 6
x1 0 1 0 0 0 1/3 7

Sekarang variabel-variabel dasarnya adalah x2 dan s3. Karena diantara variabel-variabel

dasar ini masih ada yang koefisien pada baris z nya bernilai negatif (ingat: kasusnya adalah
maksimisasi), berarti penyelesaian belum optimal. Harus dibentuk tabel berikutnya.
Sebagaimana dapat dilihat didalam tabel bahwa x2 merupakan variabel pendatang dan s1
merupakan variabel perantau. Kolom dan baris yang bersangkutan merupakan kolom kunci
dan baris kunci dengan unsur kunci bernilai 3. Sekali lagi, sebelum tabel dibentuk terlebih
dahulu harus dilakukan transformasi baris. Dalm hal ini transformasi baris-barisnya adalah
sebagai berikut.

Transformasi baris kunci (x2 menggantikan s1) :

x2 0/3 0/3 3/3 1/3 0/3 -1/3 3/3

x2 0 0 1 1/3 0 -1/3 1
10
 Transformasi baris -z Transformasi baris – s2 Transformasi baris – x1
1 — (−15) 0 = 1 0 — (4) 0 = 0 0 — (0) 0 = 0
0 — (−15) 0 = 0 0 — (4) 0 = 0 1 — (0) 0 = 1
−15 — (−15) 0 = 0 4 — (4) 1 = 0 0 — (0) 1 = 0
0 — (−15) 1/3 = 0 0 — (4) 1/3 0 — (0) 1/3 = 0
0 — (−15) 0 = 0 = −4/3 0 — (0) 0 = 0
25/3 − (−15)(−1/3) 1 — (4) 0 = 1 1/3— (0) (−1/3)
= 10/3 −2/3 — (4)(1/3) = 1/3
175 — (−15) 1 = 190 = 2/3 7 — (0) 1 = 7
6 — (4) 1 = 2

Tabel 3.

VD Z x1 x2 s1 s2 s3 S
z 1 0 0 5 0 10/3 190
x2 0 0 1 1/3 0 -1/3 1
s2 0 0 0 -4/3 1 2/3 2
x1 0 1 0 0 0 1/3 7

Variabel-varibel dasarnya sekarang (lihat kolom VD) adalah x1,x2 dan s2. Sedangkan
variabel-variabel dasarnya ialah s1 dan s3. Karena koefisien- koefisien variabel dasar padą
baris-z sudah tidak ada lagi yang negatif, berarti optimalitas sudah dicapai pada tahap
penyelesaian ketiga ini. Tabel III yang merupakan tabel terakhir disebut tabel optimal.

Penafsiran Tablo Optimal

Kesimpulan yang dihasilkan pada penyelesaian tahap terakhir dapat dibaca langsung
dari tabel optimal. Baris-baris yang bersesuaian pada kolom VD dan kolom S
menunjukkan z = 190, x2 = 1, s2 = 2 dan x1 = 7. Berarti optimalitas dicapai pada kombinasi
produksi 7 unit X1 dan 1 unit X2, dengan profit maksimum 190; dan terdapat sisa masukan
L yang tidak terpakai (dilambangkan oleh s2, variabel senjang pada fungsi kendala L)
sebanyak 2 unit. Dalam tabel optimal ini s1 dan s2 tidak tercantum di kolom VD,
mencerminkan bahwa pada penyelesaian optimal semua masukan yang dilambangkannya
(yaitu K dan M) terpakai habis, tidak ada yang tersisa. Hasil-hasil ini konsisten dengan
hasil-hasil yang diperoleh melalui metoda grafik dan metoda aljabar sebelumnya.

Variabel semua yang tidak tercantum di kolom VD dalam tabel optimal mengandung
arti bahwa masukan yang diwakilinya merupakan sumberdaya langka" (scarce resource).
Dalam kasus ini masukan-masukan K dan M merupakan sumberdaya langka, mengingat s1
dan s3 tidak tercantum di kolom VD. Sedangkan variabel semu yang tercantum di kolom
VD, dan nilainya di kolom S bukan nol, mengandung arti bahwa masukan yang
diwakilinya sumberdaya berlebih" (abundant resource). Dalam kasus ini sumberdaya yang
berlebih ialah masukan L, mengingat s, tercantum di kolom VD dan nilainya di kolom S

11
tidak sama dengan nol. (Ingat bahwa semua masukan K dan M terpakai habis, sedangkan
masukan L áda yang tersisa).

Penafsiran lain lagi yang dapat dilakukan melalui tabel optimal ialah mengenai nilai
dual (dual value). Koefisien kolom variabel semu pada baris z mencerminkan nilai dual
dari kendala yang diwakilinya. Dalam kasus ini koefisien kolom-kolom s1, s1, dan s3, pada
baris -z masing-masing 5, 0 dan 10/3. Berarti nilai dual kendala pertama (masukan K),
kendala kedua (masukan L) dan kendala ketiga (masukan M) masing-masing adalah 5, 0
dan 10/3.

C. Soal Latihan

12
 BAB III

PENUTUP
3.1 Simpulan

3.2 Saran

13
 DAFTAR PUSTAKA

Dumairy. 2016. Matematika Terapan Untuk Bisnis Dan Ekonomi. Yogyakarta : BPFE

[Link]
FITRIANI_AGUSTINA/Sekilas_Metode_Simpleks.pdf

Syahputra, Edi. 2015. Program Linier. Medan : Unimed Press

14