Program linear

KATA PENGANTAR

Dengan senantiasa memanjatkan puji syukur kehadirat Allah Swt., atas

segala limpahan rahmat-Nya sehingga aktivitas kehidupan dunia dan akhirat
masih dapat kita jalani. Tak Lupa shalawat dan salam kita haturkan kepada
junjungan kita Rasulullah Saw., para sahabat dan seluruh umat muslim yang
masih ridha berjuang demi tegaknya dien ini.
Melalui penyelenggaraan perkuliahan mata kuliah program linear penulis
memperhatikan kalau minat mahasiswa cukup besar terhadap catatan perkuliahan
program linear yang diberikan oleh penulis, sehingga implikasi dari itu penulis
menyusun bahan ajar ini sebagai salah satu bahan acuan yang mudah dipahami
oleh mahasiswa dan pembaca lainnya untuk langsung mengetahui keterkaitan
antara teori yang sedang dipelajari dan penerapan berbagai persoalan yang
dihadapi dalam kehidupan sehari-hari.
Bahan ajar ini merupakan suatu bahan ajar yang pendekatannya saya
yakini berbeda dengan buku-buku Program Linear yang telah ada sebelumnya
karena sudut pandang dan kebutuhan yang berbeda. Saat ini terdapat banyak buku
ajar, masing-masing buku ajar mempunyai kelebihan dan kekurangan sendiri.
Idealnya mahasiswa mempunyai lebih dari satu buku, sehingga satu buku dapat
melengkapi buku yang lainnya. Buku ini dirancang untuk mahasiswa pendidikan
matematika, mahasiswa matematika, atau pembaca lainnya yang membutuhkan
selama satu semester.
Penulisan buku ini dirancang sedemikian rupa sehingga diharapkan
mahasiswa mudah memahami konsep dengan disertai contoh soal dan
pemecahannya. Disampingi itu dengan perkembangan dunia informasi, penulis
tambahkan aplikasi komputer untuk memudahkan pemecahan masalah-masalah
khusus yang melibatkan banyak variabel. Program yang digunakan dalam hal ini
adalah Matlab dan POM for Windows.

v
 Program linear

Kami sadar bahwa bahan ajar yang disajikan ini masih jauh dari sempurna,
untuk itu kami mengharapkan masukan dari pihak manapun juga guna
penyempurnaan dimasa mendatang. Akhirnya kami sampaikan terima kasih
kepada semua pihak yang telah membantu dalam penyelesaian bahan ajar ini.

Ambon, Desember 2013

Penyusun,

vi
 Program linear

Daftar Isi
SAMPUL DEPAN ............................................................................. i
SAMPUL DALAM ............................................................................ ii
IDENTITAS BUKU ............................................................................ iii
HAK CIPTA ...................................................................................... iv
KATA PENGANTAR ......................................................................... v
SILABUS.......................................................................................... vi
DAFTAR ISI ..................................................................................... xvii

BAB I PENDAHULUAN
A. Sejarah Singkat Program Linear ............................................. 2
B. Pengertian Program Linear .................................................... 6
C. Asumsi-asumsi Dasar dalam Program Linear ......................... 8
D. Ruang Lingkup Program Linear ............................................. 10
E. Bentuk Umum Program Linear .............................................. 11
Ringkasan ................................................................................... 13
Latihan ....................................................................................... 14
Daftar Pustaka ............................................................................ 15

BAB II MATRIKS DAN SISTEM PERSAMAAN

A. Pengertian Matriks ............................................................... 17
B. Matriks Khusus ...................................................................... 19
C. Operasi Matriks ..................................................................... 21
D. Aplikasi Komputer (Program Matlab) pada Matriks ............... 25
E. Sistem Persamaan Linear ...................................................... 31
1. Pemecahan dengan Menggunakan Aturan Cramer .......... 31
2. Penyelesaian Sistem Persamaan dengan Eliminasi Gauss . 33
Ringkasan ................................................................................... 36
Latihan ....................................................................................... 37
Daftar Pustaka ............................................................................ 38

xvii
 Program linear

BAB III PROGRAM LINEAR METODE GRAFIK MAKSIMISASI

A. Formulasi Permasalahan ....................................................... 40
B. Penyelesaian Linear Programming Secara Grafik ................... 43
Ringkasan .................................................................................. 47
Latihan ....................................................................................... 48
Daftar Pustaka ............................................................................ 51

BAB IV PROGRAM LINEAR METODE GRAFIK MINIMISASI

A. Penyelesaian Linear Programming Secara Grafik
untuk Fungsi Tujuan Minimisasi ........................................... 53
B. Isu Teknis Dalam Program Linear........................................... 58
Ringkasan ................................................................................... 61
Latihan ....................................................................................... 62
Daftar Pustaka ............................................................................ 63

BAB V DUALITAS
A. Teori Dualitas ....................................................................... 64
B. Hubungan Primal Dual.......................................................... 65
C. Sifat-sifat Primal Dual yang Penting ...................................... 66
Ringkasan .................................................................................. 70
Latihan ...................................................................................... 71
Daftar Pustaka ........................................................................... 73

BAB VI METODE SIMPLEKS MAKSIMASI

A. Langkah-langkah Metode Simpleks Permasalahan
Maksimasi ............................................................................. 75
B. Pola Maksimum Baku ............................................................ 77
Ringkasan ................................................................................... 82
Latihan ....................................................................................... 83
Daftar Pustaka ........................................................................... 85

xviii
 Program linear
BAB VII PROGRAM LINEAR METODE SIMPLEKS MINIMISASI
A. Pendahuluan ......................................................................... 87
B. Formulasi Permasalahan Menurut Metode Simpleks
untuk Tanda Pertidaksamaan ................................................ 87
C. Membuat Tabel Awal Simplek ............................................... 90
Ringkasan ................................................................................... 92
Latihan ....................................................................................... 93
Daftar Pustaka ........................................................................... 94

BAB VIII ANALISIS SENSITIVITAS PERUBAHAN SISI KANAN

FUNGSI KENDALA
A. Pendahuluan ......................................................................... 96
B. Shadow Price ......................................................................... 96
C. Dampak Perubahan Secara Parsial Sisi Kanan
Fungsi Kendala terhadap Solusi Optimal ............................... 98
D. Dampak Perubahan Secara Simultan Sisi Kanan
Fungsi Kendala terhadap solusi optimal .............................. 101
E. Rentang Perubahan Sisi Kanan Fungsi Kendala
agar Solusi Masih Tetap Optimal ......................................... 104
Ringkasan ................................................................................. 106
Latihan ..................................................................................... 107
Daftar Pustaka ......................................................................... 109

BAB IX ANALISIS SENSITIVITAS PERUBAHAN PADA KOEFISIEN

FUNGSI TUJUAN
A. Analisis Sensitivitas Reduced Cost dan Penentuan
Kelayakan penambahan Produk Baru ................................ 110
B. Reduced Cost ..................................................................... 111
Ringkasan .......................................................................... 114
Latihan .............................................................................. 115

xix
 Program linear
BAB X TRANSPORTASI FUNGSI TUJUAN MINIMISASI, KASUS D = S
A. Pendahuluan ..................................................................... 128
B. Membuat Tabel Awal dengan Northwest Corner dan
Least Cost .......................................................................... 130
C. Membuat Tabel Awal Dengan The Least Cost Rule ............ 133
Ringkasan .......................................................................... 135
Latihan .............................................................................. 136
Daftar Pustaka ................................................................... 137

BAB XI TRANSPORTASI DENGAN METODE STEPPING STONE

A. The Stepping-Stone Method .............................................. 139
B. Melakukan Perbaikan Tabel .............................................. 141
Ringkasan .......................................................................... 143
Latihan .............................................................................. 144
Daftar Pustaka ................................................................... 145

BAB XII TRANSPORTASI: FUNGSI TUJUAN MINIMISASI,

KASUS D = S PENYELESAIAN DENGAN VAM
A. Menghitung dengan VAM ................................................. 147
B. Mengisi Kotak Lain Pada VAM ........................................... 149
Ringkasan .......................................................................... 151
Latihan .............................................................................. 152
Daftar Pustaka ................................................................... 153

BAB XIII TRANSPORTASI: FUNGSI TUJUAN MINIMISASI,

KASUS D = S PENYELESAIAN DENGAN MODI METHODE
Menentukan Tabel Optimal dengan menggunakan
A. The MODI Method ............................................................ 155
B. Melakukan Perbaikan Tabel .............................................. 156
Ringkasan .......................................................................... 162
Latihan .............................................................................. 163
Daftar Pustaka ................................................................... 164

xx
 Program linear

BAB XIV APLIKASI KOMPUTER METODE GRAFIK

A. Pendahuluan .............................................................. 166
B. Materi Aplikasi Program Linear ................................... 167
C. Langkah Umum Memecahkan Masalah
Program Linear ............................................................ 167
D. Menjalankan POM For Windows ................................ 167
E. Model Grafik ............................................................... 169
Ringkasan .................................................................... 173
Latihan ........................................................................ 174
Daftar Pustaka ............................................................. 175

GLOSARIUM ............................................................................... 168

xxi
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang sejarah
program linear, keterampilan belajar secara mandiri
dalam mempelajari masalah-masalah pemrograman
linear dari kehidupan sehari-hari, dengan
menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan
dapat:
- Mengetahui sejarah program linear
- Menunjukkan beberapa persoalan yang dapat
dipecahkan dengan program linear
- Mengetahui langkah-langkah dalam proses program
linear

(Apa yang telah Kami ceritakan itu), itulah yang benar, yang datang dari Tuhanmu,
karena itu janganlah kamu termasuk orang-orang yang ragu-ragu. (QS. 3. Al-Imran :60)

1
 Program linear
A. Sejarah Singkat Program Linear
Program linear ditemukan dan dikembangkan oleh beberapa matematikawan
di masa sebelum Perang Dunia ke-II. Penemuan dan pengembangan oleh
beberapa matematikawan tersebut rata – rata didasarkan karena persoalan atau
masalah yang sedang berkembang saat itu, yaitu dalam hal industri dan
peperangan. Beberapa matematikawan tersebut adalah Leonid V. Kartovich,
George B. Dantzig, John von Neumann, Leonid Khachiyan dan Naranda
Karmarkar. Berikut ini pemaparan sejarah penemuan program linear oleh
beberapa matematikawan tersebut di atas.

1. Leonid Vitalevich Kartovich

Leonid V. Kartovich lahir pada bulan Januari tahun 1912 di kota

Leningrad, Rusia. Leonid tumbuh menjadi seorang anak dengan rasa keingin
tahuan yang besar, ia tertarik dengan politik dan sejarah modern. Pada usaianya
yang baru 14 tahun, ia sudah masuk ke Mathematical Department of the
Leningrad University, di sini ia mulai menyadari bahwa ia berminat pada bidang
ilmu pengetahuan dan matematika. Pada tahun keduanya di universitas, Leonid
sudah mengungguli teman – temannya di bidang matematika, bahkan ia sudah
menguasai matematika kompleks dan abstrak. Di usianya yang ke 18 tahun ia
sudah menjadi penulis di bidang matematika.

2
 Program linear

Setelah lulus, Leonid terus melanjutkan penelitiannya di bidang

matematika teoritis, tetapi seiring berjalannya waktu ia mulai memindahkan
konsentrasinya pada matematika terapan, pada ahirnya kontribusi terbesar Leonid
adalah pada matematika ekonomi. Pada masa itu Uni Soviet sedang menghadapi
masa industrialisasi di bawah wewenang Joseph Stalin dimana perekonomian
yang semula terpusat pada pertanian berubah menjadi industri. Keadaan seperti
inilah yang membuat Leonid menemukan masalah di tempat ia berkerja yaitu
sebagai konsultan laboratorium pemerintah.

Persoalan tersebut berkaitan dengan kegiatan produksi, ia harus

menyelesaikan masalah mengefisiensikan biaya produksi dan pemakaian bahan
baku tetapi produksi tetap maksimal. Pada awalnya masalah ini dinilai sederhana,
hanya sebuah kasus kalkulus diferensial, tetapi ternyata lebih rumit dari
kelihatannya. Inilah hal yang menjadi awal keinginan Leonid untuk menggunakan
matematika sebagai aplikasi untuk ekonomi. Akhirnya pada tahun 1939, Leonid
mengajukan sebuah hasil pemikirannya berdasarkan masalah yang ada dan
perencanaan solusinya. Ternyata hasil pemikirannya ini adalah yang kita kenal
sekarang sebagai Program Linear. Pemikirannya tersebut pada awalnya
diragukan oleh banyak orang, tetapi dengan cepat terbukti ketika ia menghitung
jumlah maksimum suatu pabrik harus memakai baja agar biaya produksi tetap
efisien, dan ternyata pemikirannya tersebut terbukti biaya produksi dapat
diefisienkan secara signifikan.

Penemuan Leonid mengantarkan era baru bagi perekonomian bagi Uni

Soviet. Hal ini menimbulkan minat yang besar bagi Uni Soviet dalam matematika
terapan, dan sejak itu Leonid menjadi revolusioner di bidang ekonomi
matematika.

3
 Program linear

Dan kalau Kami menghendaki, sesungguhnya Kami tinggikan (derajat) nya

dengan ayat-ayat itu, tetapi dia cenderung kepada dunia dan menurutkan hawa
nafsunya yang rendah, maka perumpamaannya seperti anjing jika kamu
menghalaunya diulurkannya lidahnya dan jika kamu membiarkannya dia
mengulurkan lidahnya (juga). Demikian itulah perumpamaan orang-orang yang
mendustakan ayat-ayat Kami. Maka ceritakanlah (kepada mereka) kisah-kisah itu
agar mereka berpikir. (QS. 7. Al-A’araaf :176)

Dan Dia menundukkan untukmu apa yang ada di langit dan apa yang ada di bumi
semuanya, (sebagai rahmat) daripada-Nya. Sesungguhnya pada yang demikian itu
benar-benar terdapat tanda-tanda (kekuasaan Allah) bagi kaum yang berpikir.
(QS. 45. Al-Jaatsiyah:13)

4
 Program linear

2. George Bernard Dantzig

George Bernard Dantzig lahir pada tanggal 8 November 1914 di Portland,

Oragon, Amerika Serikat. Ayah Dantzig adalah seorang profesor matematika dan
ibunya adalah seorang ahli bahasa Slavia. Dantzig mendapatkan gelar sarjananya
di University of Maryland pada tahun 1936. Ia tidak suka semua mata kuliah
matematik yang ia ambil di sana karena ia tidak melihat aplikasi dari semua itu.
Tahun berikutnya ia mengambil program pasca sarjana di Mathematics School of
the University of Michigan. Selain mata kuliah statistika, ia tetap melihat semua
mata kuliah matematikanya terlalu abstrak maka ia meninggalkan sekolahnya dan
mencari pekerjaan.

Lalu ia bekerja di Biro Statistik Tenaga Kerja, dua tahun kemudian ia

berkuliah di Berkley untuk mengambil doktor dalam bidang statistika. Setelah
mendapatkan gelar doktor pada tahun 1947 ia bergabung di Angkatan Udara
Amerika sebagai penasehat matematik untuk pusat kontrol Angkatan Udara.
Angkatan udara membutuhkan cara cepat untuk menghitung durasi tahapan
program, latihan, dan distibusi logistik. Berasal dari sinilah pemikirian Dantzig
tentang program linear. Dantzig menyatakan bahwa : “I began noticing that the
feasible regionis a convex body, that is, a polyhedral [Link], the process
would be able to be improved if the movements were maded along theborders
from one extreme point toward the following. However, this procedure seemed to
be too inefficient. In three dimensions, the regioncould be visualized like a

5
 Program linear

diamond with faces, edges and vertex. In the cases of many borders, the process
would take an a journey along them before the diamond’s point optimal corner
would be reached”.

Kesimpulannya, sebuah permasalahan dijadikan dalam bentuk 3 dimensi

seperti berlian dimana ada tampak depan, garis pinggir dan puncak lalu mereka
akan saling bertemu disuatu titik hingga titik optimum akan terpenuhi. Begitulah
awal terciptanya program linear dengan metode simpleks oleh Dantzig.

3. John von Neumann,

Leonid Khachiyan dan Naranda Karmarkar mengembangkan program linear

untuk masalah – masalah yang lebih rumit pada tahun – tahun berikutnya sampai
di temukannya metode grafik1.

B. Pengertian Program Linear

Ada beberapa pengertian Program Linear menurut para ahli, di antaranya:
1. Siringoringo
Pemrograman Linier disingkat PL merupakan metode matematik dalam
mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan
seperti memaksimumkan keuntungan dan meminimumkan biaya. PL banyak
diterapkan dalam masalah ekonomi, industri, militer, social dan lain-lain. PL
berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu

1
[Link]

6
 Program linear
model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa
kendala linier.2
2. Jaz Heizer dan Barry Rander
Linear programming menurut Jay Heizer dan Barry Rander mengemukakan
bahwa:
“A mathematical technique designed to help operations managers plan and
make decisions relative to the trade-offs necessary to allocate resources”3.
Yang artinya :
“Sebuah teknik matematik yang didesain untuk membantu para manajer
operasi dalam merencanakan dan membuat keputusan yang diperlukan untuk
mengalokasikan sumber daya”.
3. Tjutju Tarliah Dimyati dan Ahmad Dimyati
Menurut Tjutju Tarliah Dimyati dan Ahmad Dimyati mengemukakan bahwa
“Program linier (LP) adalah perencanaan aktivitas-aktivitas untuk
memperoleh suatu hasil yang optimum, yaitu suatu hasil yang mencapai
tujuan terbaik diantara seluruh alternatif yang fisibel”4

Secara umum Program Linear dapat diartikan bahwa suatu teknis

matematika yang dirancang untuk membantu manajer dalam merencanakan dan
membuat keputusan dalam mengalokasikan sumber daya yang terbatas untuk
mencapai tujuan perusahaan.

Secara khusus, persoalan program linear adalah suatu persoalan untuk

menentukan besarnya masing-masing nilai variabel (variabel pengambilan
keputusan) sedemikian rupa sehingga nilai funsi tujuan atau objektif (objective
function) yang linier menjadi optimum (maksimum atau minimum) dengan
memperhatikan pembatasan-pembatasan (kendala-kendala) yang ada yaitu

2
Hotniar Siringoringo, Seri Teknik Riset Operasional. Pemrograman Linear. (Yogyakarta:
Penerbit Graha Ilmu, 2005) hlm.1
3
Jay Heizer and Barry. Operations Management (10th edition). (New York, NY: Prentice
Hall. Moon, Y. 2004). Hlm 658
4
Tjutju Tarliah Dimyati dan Ahmad Dimyati. 2003. Operations Research: Model-model
Pengambilan Keputusan. (Bandung: Sinar Baru Algensindo). Hlm 17

7
 Program linear
pembatasan ini harus dinyatakan dengan ketidaksamaan yang linier (linear
inequalities).

Pendapat pakar yang lain menyatakan bahwa linear programming adalah

merupakan suatu teknik perencanaan yang bersifat analitis yang analisis-
analisisnya memakai model matematika, dengan tujuan untuk menemukan
beberapa kombinasi alternatif pemecahan masalah, lalu dipilih yang terbaik dalam
rangka menyusun strategi dan alokasi sumber daya dan dana untuk mencapai
tujuan dan sasaran yang diinginkan secara optimal.

Secara singkat, program linear adalah teknik matematika yang dirancang

untuk membantu manager dalam merencanakan dan membuat keputusan dalam
mengalokasikan sumber daya yang terbatas untuk mencapai tujuan perusahaan.

C. Asumsi-asumsi Dasar dalam Program Linear

Untuk membentuk suatu model program linear perlu diterapkan asumsi-

asumsi dasar, yaitu:

1. Linearitas
Fungsi obyektif dan kendala haruslah merupakan fungsi linier dan variabel
keputusan. Hal ini akan mengakibatkan fungsi bersifat proporsional dan
additif, misalnya untuk memproduksi 1 kursi dibutuhkan waktu 5 jam, maka
untuk memproduksi 2 kursi dibutuhkan waktu 10 jam.
2. Pembagian
Nilai variabel keputusan dapat berupa bilangan pecahan. Apabila diinginkan
solusi berupa bilangan bulat (integer), aka harus digunakan metoda untuk
integer programming.
3. Variabel non negatif
Nilai variabel keputusan haruslah tidak negatif ( ≥ 0).

8
 Program linear
4. Kepastian
Semua konstanta (parameter) diasumsikan mempunyai nilai yang pasti. Bila
nilai-nilai parameternya probabilistik, maka harus digunakan formulasi
pemrograman masalah stokastik.
Secara teknis, ada lima syarat tambahan dari permasalahan linear
programming yang harus diperhatikan yang merupakan asumsi dasar, yaitu:

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

sudah diketahui dengan pasti dan tidak berubah selama periode analisa.
2. Proportionality (proporsionalitas). Yaitu adanya proporsionalitas dalam
fungsi tujuan dan fungsi kendala.
3. Additivity (penambahan). Artinya aktivitas total sama dengan penjumlahan
aktivitas individu.
4. Divisibility (bisa dibagi-bagi). Maksudnya solusi tidak harus merupakan
bilangan integer (bilangan bulat), tetapi bisa juga berupa pecahan.
Non-negative variable (variabel tidak negatif). Artinya bahwa semua nilai
jawaban atau variabel tidak negatif.
Untuk merumuskan suatu masalah ke dalam bentuk model program linear,
harus dipenuhi syarat-syarat berikut:
1. Tujuan masalah harus jelas.
2. Harus ada sesuatu atau beberapa alternatif yang ingin dibandingkan.
3. Adanya sumber daya yang terbatas.
4. Bisa dilakukan perumusan kuantitatif.
5. Adanya keterkaitan peubah (variabel).

Program Linear memiliki empat ciri khusus yang melekat, yaitu :

1. Penyelesaian masalah mengarah pada pencapaian tujuan maksimisasi atau

minimisasi
2. Kendala yang ada membatasi tingkat pencapaian tujuan
3. Ada beberapa alternatif penyelesaian
4. Hubungan matematis bersifat linear

9
 Program linear
D. Ruang Lingkup Program Linear
Pada umumnya persoalan-persoalan yang dipecahkan dalam program linear
yaitu meliputi:
1. Allocation Problem
Ini merupakan pemecahan dalam alokasi bahan-bahan/barang dalam
produksi
2. Blending Problem
Ini merupakan cara pemecahan persoalan dari berbagai bahan campuran
yang masing-masing unit dipecahkan dan digabung (blending) untuk
menghasilkan output.
3. Persoalan Transportasi
Ini merupakan pemecahan persoalan yang menyangkut adanya
unit/barang/pasokan dan lain-lain pada beberapa tempat yang akan
dipindahkan ke beberapa tempat lainnya.
4. Persoalan Personil
Ini merupakan penempatan personil sesuai dengan jabatan/tempatnya
(assigment problem).
Suatu persoalan disebut persoalan program linear apabila memenuhi hal-hal
sebagai berikut:
1. Tujuan (objective)
Apa yang menjadi tujuan permasalahan yang dihadapi yang ingin
dipecahkan dan dicari jalan keluarnya. Tujuan ini harus jelas dan tegas yang
disebut fungsi tujuan (objective function). Fungsi tujuan tersebut dapat berupa
dampak positip, manfaat-manfaat, atau dampak negatip, kerugian-kerugian,
resiko-resiko, biaya-biaya, jarak, waktu yang ingin diminimumkan.
2. Alternatif perbandingan
Harus ada sesuatu atau alternatif yang ingin diperbandingkan, misalnya
antara kombinasi waktu tercepat dan biaya tertinggi dengan waktu terlambat
dan biaya terendah, atau alternatif padat modal dengan padat karya, proyeksi
permintaan tinggi dengan rendah, dan seterusnya.

10
 Program linear
3. Sumber Daya
Sumber daya yang dianalisis harus berada dalam keadaan terbatas.
Misalnya keterbatasan tenaga, bahan mentah terbatas, modal terbatas, ruangan
untuk menyimpan barang terbatas, dan lain-lain. Pembatasan harus dalam
ketidaksamaan linier (linear inequality). Keterbatasan dalam sumber daya
tersebut dinamakan sebagai fungsi kendala atau syarat ikatan.
4. Perumusan Kuantitatif
Fungsi tujuan dan kendala tersebut harus dapat dirumuskan secara
kuantitatif dalam model matematika.
5. Keterikatan Perubah
Perubah-perubah yang membentuk fungsi tujuan dan fungsi kendala
tersebut harus memiliki hubungan keterikatan hubungan keterikatan atau
hubungan fungsional.

E. Bentuk Umum Program Linear

Pemrograman linear dapat dirumuskan seperti berikutmencari nilai-nilai
peubah/variabel 𝑥1 , 𝑥2 , … , 𝑥𝑛 yang memaksimumkan atau meminimumkan 𝑍 =
𝑐1𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛 dengan kendala:
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 (≤, =, ≥)𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2 𝑥𝑛 (≤, =, ≥)𝑏2
⋮ ⋮ ⋮ ⋮
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 (≤, =, ≥)𝑏𝑚
Dengan syarat peubah/variabel 𝑥1 , 𝑥2 , … , 𝑥𝑛 ≥ 0, 𝑐𝑖 , 𝑖 = 1,2, … , 𝑛, 𝑎𝑖𝑗 , 𝑖 =
1,2, … , 𝑚, 𝑗 = 1,2, … , 𝑛 adalah konstanta.
Penentuan kendala dilakukan dengan memilih satu di antara tiga tanda ≤
(kurang atau sama dengan), = (sama dengan), ≥ (lebih atau sama dengan).
Perumusan di atas dapat ditulis lebih ringkas sebagai berikut:
Mencari 𝑥𝑗 , 𝑗 = 1,2, … , 𝑛 yang memaksimalkan atau meminimumkan
𝑛

𝑍 = ∑ 𝑐𝑗 𝑥𝑗
𝑗=1

11
 Program linear
Sedemikian hingga
𝑛

∑ 𝑎𝑖𝑗 𝑥𝑗 (≤, =, ≥)𝑏𝑖

𝑗=1

, 𝑖 = 1,2, … , 𝑚
Dengan syarat 𝑥𝑗 ≥ 0, 𝑗 = 1,2, … , 𝑛. Karena persoalan pemrograman linear
merupakan masalah alokasi sumber daya, maka perumusan di atas dapat
diinterpretasikan bahwa jika (𝑏1 , 𝑏2 , … , 𝑏𝑚 ) adalah jumlah sumber daya ke-i yang
harus dialokasikan pada setiap kegiatan/aktivitas ke-j. Sumbangan laba dari setiap
kegiatan ke-j dinyatakan oleh konstanta 𝑐𝑗 , j = 1,2, ..., n.5

5
Muhammad Arif Tiro. Pengenalan Manajemen Sains. (Makassar: Andira
Fublihser, 2004). Hlm 24.

12
 Program linear

Ringkasan
Program linear adalah teknik matematika yang dirancang
untuk membantu manager dalam merencanakan dan
membuat keputusan dalam mengalokasikan sumber daya
yang terbatas untuk mencapai tujuan perusahaan.
Syarat-syarat perumusan suatu masalah ke dalam bentuk
model program linear: (1) Tujuan masalah harus jelas, (2)
Harus ada sesuatu atau beberapa alternatif yang ingin
dibandingkan, (3) Adanya sumber daya yang terbatas, (4)
Bisa dilakukan perumusan kuantitatif, (5) Adanya
keterkaitan peubah (variabel).

13
 Program linear

Latihan
1. Program linear sebagai metode ilmiah yang memungkinkan
para manajer mengambil keputusan dengan dasar ...
2. Aplikasi program linear dalam berbagai bidang ditandai
dengan...
3. Fungsi yang dicari solusi optimalnya disebut...
4. Batasan-batasan yang mempengaruhi persoalan terhadap tujuan
yang akan dicapai disebut...
5. Fungsi pembatas pada model program linear disebut...

14
 Program linear

DAFTAR PUSTAKA

Al-Qur’an
Aminuddin. 2005. Prinsip-prinsip Riset Operasi. Jakarta: Erlangga.

Dimyati, Tjutju Tarliah dan Ahmad Dimyati. Operations Research: Model-

model Pengambilan Keputusan. Sinar Baru Algensindo, Bandung. 2003.
[Link]
pengembangan- program - linear/, artikel diakses tanggal 17 Oktober 2013.

Jay Heizer and Barry. Operations Management (10th edition). New York,
NY: Prentice Hall. Moon, Y. 2004.
Siringoringo, Hotniar. Seri Teknik Riset Operasional. Pemrograman Linear.
Penerbit Graha Ilmu. Yogyakarta. 2005.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

15
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang
sejarah program linear, keterampilan belajar secara
mandiri dalam mempelajari masalah-masalah
pemrograman linear dari kehidupan sehari-hari,
dengan menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa
diharapkan dapat:
- Memahami lebih baik pengertian matriks yang
berkaitan dengan pemecahan sistem persamaan
linear
- Memahami lebih baik proses pemecahan sistem
persamaan linear melalui eliminasi Gauss-Jordan
- Memahami proses pemecahan sistem persamaan,
bila jumlah variabel tidak sama dengan jumlah
persamaan (pemecahan dasar atau pemecahan
basis)

16
 Program linear
MATRIKS DAN SISTEM PERSAMAAN LINEAR
A. Pengertian Matriks
Hubungan antara variabel-variabel, baik di dalam ilmu ekonomi maupun di
dalam ilmu lainnya, sering kali perlu diselesaikan dengan suatu persoalan yang
terdiri dari lebih dua persamaan. Bahkan di suatu negara yang telah maju,
terutama di dalam penggunaan alat berhitung otomatis yang modern, seperti
komputer tidak jarang di dalam menemukan model ekonominya harus
memecahkan suatu persamaan yang terdiri dari puluhan persamaan dengan
ratusan variabel-variabel yang harus dicari nilainya, sehingga dengan demikian
harus dihitung nilai-nilai parameter (koefisien-koefisien) yang juga ratusa
jumlahnya.
Matriks pada dasarnya merupakan salah satu alat yang ampuh di dalam
pemecahan persoalan-persoalan seperti di atas dan memudahkan di dalam
pembuatan pemecahan analisa-analisa yang mencakup hubungan antara variabel-
variabel. Di dalam statistik tidak jarang dijumpai penggunaan matriks untuk
memecahkan persoalan multiple regression, juga di dalam memecahkan persoalan
operation research/linear programming (program linear), matriks memegang
peranan penting terutama sebagai landasan yang kuat untuk memahami
pengertian-pengertian pemecahan dasr, metode simpleks dan lain sebagainya.
Di dalam analisa tabel input-output, penggunaan matriks memungkinkan
untuk mengaitkan hubungan antara sektor yang satu dengan sektor yang lainnya,
juga dapat dipergunakan untuk meramalkan output setiap sektor jika permintaan
akhir (final demand) bagi setiap sektor sudah diketahui.
Itulah sebagian kecil tentang alasan-alasan pokok perlunya mempelajari
matriks secara mendalam. Pengetahuan tentang matriks merupakan syarat pokok
untuk bisa memahami teori-teori/analisa-analisa ekonomi modern yang sifat
kunatitatif, misalnya ekonometrika, program linear, dan lain sebagainya.

17
 Program linear

Definisi
Matriks ialah suatu kumpulan angka-angka (sering disebut
elemen-elemen) yang disusun menurut baris dan kolom
sehingga berbentuk empat persegi panjang, dimana panjangnya
dan lebarnya ditunjukkan oleh banyaknya kolom-kolom dan
baris-baris.1

Matriks dengan m baris dan n kolom disebut matriks berukuran

(berdimensi) 𝑚 × 𝑛, yang kadang disingkat dengan “matiks 𝑚 × 𝑛”.
Bilangan-bilangan tadi disebut unsur-unsur matriks. Matriks 𝑚 × 𝑛 dapat
dilambangkan dengan:
𝑎11 𝑎12 … 𝑎1𝑛
𝑎21 𝑎22 … 𝑎2𝑛
𝐴𝑚×𝑛 = [𝑎𝑖𝑗 ] = [ ]
⋮ ⋮ ⋮
𝑎31 𝑎32 … 𝑎𝑚𝑛
𝑖 = indeks baris
𝑗 = indeks kolom
Jika 𝑚 = 𝑛, maka matriks tersebut dinamakan juga matriks bujur sangkar
(square matriks)2. Melukiskan matriks dalam bentuk persegi panjang di
atas adalah boros tempat, oleh karena itu kita lazim menuliskan matriks
𝐴𝑚×𝑛 = [𝑎𝑖𝑗 ].
Contoh
Di bawah ini adalah matriks yang berukuran 3 × 4:
1 2 3 4
𝐴 = [5 6 7 8 ]
9 1 2 3
Matriks di atas disusun oleh 3 baris elemen, yaitu
(1,2,3,4), (5,6,7,8), (9,1,2,3) atau susunan dalam bentuk kolom-kolom:
1 2 3 4
[5] , [6] , [7], dan [8]
9 1 2 3
1
J. Supranto, Pengantar Matriks. (Jakarta: Lembaga Penerbit FE UI, 1974). Hlm 3
2
Rinaldi Munir, Matematika Diskrit. (Bandung: Informatika Bandung, 2009). Hlm 98

18
 Program linear
B. Matriks Khusus
Matriks khusus yang ditemukan dalam pembahasan matematika, antara lain:
matriks diagonal, matriks identitas, dan matriks transpos.
1. Matriks diagonal
Matriks diagonal adalah matriks bujursangkar dengan 𝑎𝑖𝑗 = 0, dengan
𝑖 ≠ 𝑗 berarti seluruh elemen yang tidak terdapat pada posisi 𝑖 ≠ 𝑗 bernilai
0.
Contoh:
Di bawah ini adalah contoh-contoh matriks diagonal yang berukuran
3 × 3:
5 0 0 1 0 0
[0 6 0] , [0 4 0]
0 0 7 0 0 5
2. Matriks identitas
Matriks identitas, dilambangkan dengan I. Matriks identitas adalah
matriks diagonal yang semua elemen diagonalnya sama dengan 1.
Contoh:
Di bawah ini adalah contoh-contoh matriks I, masing-masing 3 × 3
dan 4 × 4.
1 0 0 0
1 0 0
0 1 0 0
[0 1 0], [ ]
0 0 1 0
0 0 1
0 0 0 1

3. Matriks segitiga atas/bawah

Matriks segitiga atas/bawah adalah matriks jika elemen-elemen di atas/
di bawah diagonal bernilai 0, yaitu 𝑎𝑖𝑗 = 0 jika 𝑖 < 𝑗 atau 𝑖 > 𝑗.
Contoh:
Di bawah ini adalah contoh matriks segitiga. Yang pertama matriks
segitiga atas dan yang kedua matriks segitiga bawah.
1 0 0 0 9 8 7 6
2 3 0 0 0 1 1 5
[ ],[ ]
4 5 6 0 0 0 2 4
7 8 9 1 0 0 0 3

19
 Program linear
4. Matriks transpos
Matriks transpos adalah matriks yang diperoleh dengan
mempertukarkan baris-baris dan kolom-kolom. Misalkan 𝐴 = [𝑎𝑖𝑗 ]
berukuran 𝑚 × 𝑛, maka transpos matriks A, ditulis 𝐴𝑇 , adalah matriks 𝑛 ×
𝑚 yang dalam hal ini jika 𝐴𝑇 = [𝑏𝑖𝑗 ], maka 𝑏𝑖𝑗 = 𝑎𝑗𝑖 untuk 𝑖 = 1,2,3, … , 𝑛
dan 𝑗 = 1,2,3, … , 𝑚.
Contoh:
Di bawah ini adalah sebuah matriks A dan transpos-nya 𝐴𝑇 .
9 6
9 8 7
𝐴=[ ] , 𝐴𝑇 = [8 5]
6 5 4
7 4
5. Determinan matriks
Determinan suatu matriks bujursangkar A dilambangkan dengan
det⁡(𝐴) adalah bilangan yang diperoleh dari unsur-unsur A dengan
pengerjaan tertentu seperti di bawah ini:
- Untuk 𝐴1×1 = [𝑎] maka det(𝐴) = 𝑎
𝑎11 𝑎12
- Untuk 𝐴2×2 = [𝑎 ] maka
21 𝑎22
𝑎11 𝑎12
det(𝐴) = |𝑎 𝑎22 |
21

= 𝑎11 𝑎22 − 𝑎12 𝑎21

- Untuk 𝐴𝑛×𝑛 = (𝑎𝑖𝑗 ) maka
𝑛

det(𝐴) = ∑(−1)𝑖+1 𝑎𝑖1 𝑑𝑒𝑡(𝑀𝑖1 )

𝑖=1

dengan matriks 𝑀𝑖1 diperoleh dari A dengan mencoret baris ke – i dan

kolom ke – 1.
Contoh:
1 2 3
𝐴 = [4 5 6] maka
7 8 9
5 6
𝑀11 = [ ]
8 9
2 3
𝑀21 =[ ]
8 9

20
 Program linear
2 3
𝑀31 = [ ]
5 6
sehingga
1 2 3
det⁡(𝐴) = |4 5 6|
7 8 9
5 6 2 3 2 3
= (−1)1+1 (1) | | + ⁡ (−1)2+1 (4) | | + (−1)3+1 (7) | |
8 9 8 9 5 6
= (1)(−3) − (4)(6) + (7)(−3)
= −48
Sifat-sifat determinan
Untuk A matriks bujur sangkar
1. Jika tiap unsur dalam suatu baris (kolom) adalah nol maka det⁡(𝐴) = 0
2. Jika B diperoleh dari A dengan
a. Mempertukarkan dua baris (kolom) maka det(𝐵) = −det⁡(𝐴)
b. Mengalikan semua unsur suatu baris (kolom) dengan skalar k maka
det(𝐵) = 𝑘det⁡(𝐴)
c. Setiap unsur suatu baris (kolom) dikalikan dengan skalar k
kemudian dilambangkan kepada unsur yang sesuai pada baris
(kolom) lain maka det(𝐵) = det⁡(𝐴)

C. Operasi Matriks

Definisi:
Dua matriks A dan B dikatakan sama yaitu A = B jika A dan
B mempunyai jumlah baris dan kolom yang sama dan disamping
itu elemen-elemen pada baris dan kolom yang bersangkutan
harus sama, artinya 𝑎𝑖𝑗 = 𝑏𝑖𝑗 , untuk semua nilai i dan j, dimana:
𝑎𝑖𝑗 = elemen matiks A dari baris i dan kolom j
𝑏𝑖𝑗 = elemen matiks B dari baris i dan kolom j
Jika A dan B tidak sama, ditulis 𝐴 ≠ 𝐵 ini berarti 𝑎𝑖𝑗 ≠ 𝑏𝑖𝑗
untuk beberapa i dan j.3

3
J. Supranto, Pengantar Matriks. (Jakarta: Lembaga Penerbit FE UI, 1974). Hlm 13

21
 Program linear
Contoh:
1 2 1 2
1. 𝐴 = [ ], 𝐵 = [ ]
3 4 3 4
𝐴=𝐵
6 7 5 7
2. 𝐴 = [ ],𝐵 = [ ],⁡
8 9 3 9
𝐴 ≠ 𝐵 karena 𝑎11 ≠ 𝑎21

1 2 3 1 3
3. 𝐴 = [ ], 𝐵 =⁡[ ]
4 5 6 6 9
𝐴 ≠ 𝐵 karena jumlah kolom pada matriks A tidak sama dengan jumlah
kolom pada matriks B.
1. Penjumlahan matriks
Matriks 𝐴 = 𝑎𝑖𝑗 , dengan m baris dan n kolom, dan matriks 𝐵 = 𝑏𝑖𝑗 , juga
m baris dan n kolom, dijumlahkan (dikurangkan) maka diperoleh matriks yang
ketiga, yaitu matriks 𝐶 = 𝑐𝑖𝑗 dengan m baris dan n kolom dimana elemen-
elemennya diperoleh dengan menjumlahkan (mengurangkan) elemen-elemen
matriks A dengan elemen-elemen matriks B yaitu bahwa: 𝑐𝑖𝑗 = 𝑎𝑖𝑗 + 𝑏𝑖𝑗 ,
untuk semua i dan j, dimana 𝑐𝑖𝑗 merupakan elemen dari baris ke-i dan kolom
ke-j.
𝐴+𝐵 =
𝑎11 𝑎12 … 𝑎1𝑗 … 𝑎1𝑛 𝑏11 𝑏12 … 𝑏1𝑗 … 𝑏1𝑛
𝑎21 𝑎22 … 𝑎2𝑗 … 𝑎2𝑛 𝑏21 𝑏22 … 𝑏2𝑗 … 𝑏2𝑛
⋮ ⋮
𝑎𝑖1 𝑎𝑖2 … 𝑎𝑖𝑗 … 𝑎𝑖𝑛 + 𝑏𝑖1 𝑏𝑖2 … 𝑏𝑖𝑗 … 𝑏𝑖𝑛
⋮ ⋮
[𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑗 … 𝑎𝑚𝑛 ] [𝑏𝑚1 𝑏𝑚2 … 𝑏𝑚𝑗 … 𝑏𝑚𝑛 ]
𝑐11 𝑐12 … 𝑐1𝑗 … 𝑐1𝑛
𝑐21 𝑐22 … 𝑐2𝑗 … 𝑐2𝑛
⋮
=⁡ 𝑐 𝑐𝑖2 … 𝑐𝑖𝑗 … 𝑐𝑖𝑛 = 𝐶
𝑖1
⋮
[𝑐𝑚1 𝑐𝑚2 … 𝑐𝑚𝑗 … 𝑐𝑚𝑛 ]
Contoh:
1 2 1 2
1. 𝐴 = [ ], 𝐵 = [ ]
3 4 3 4
1 2 1 2 2 4
𝐴+𝐵 =[ ]+[ ]=[ ]
3 4 3 4 6 8

22
 Program linear
2. Pengurangan matriks
𝐴 − 𝐵 = 𝐴 + (−1)𝐵
Contoh:
1 2 1 2
1. 𝐴 = [ ], 𝐵 = [ ]
3 4 3 4
𝐴 − 𝐵 = 𝐴 + (−1)𝐵
1 2 −1 −2 0 0
=[ ]+[ ]=[ ]
3 4 −3 −4 0 0

Catatan:
Penjumlahan dan pengurangan
dua matriks dapat dilakukan jika
kedua matriks tersebut mempunyai
jumlah baris dan kolom yang sama.
Hukum Asosiatif dan komutatif
berlaku juga pada penjumlahan
matriks.
𝐴 + 𝐵 = (𝑎𝑖𝑗 + 𝑏𝑖𝑗 ) =
(𝑏𝑖𝑗 + 𝑎𝑖𝑗 ) = 𝐵 + 𝐴

3. Perkalian matriks
Definisi
Jika 𝐴𝑚×𝑛 = (𝑎𝑖𝑗 ) yaitu matriks dengan m baris dan n kolom, 𝐵𝑛×𝑝 =
(𝑏𝑖𝑗 ) matriks dengan n baris dan p kolom, kemudian dengan perkalian matriks
𝐴 × 𝐵 = 𝐴. 𝐵 = 𝐴𝐵, kita makudkan suatu matriks 𝐶𝑚×𝑝 ; (𝐴𝐵 =), yaitu
matriks dengan m baris dan p kolom, dimana elemen C dari baris ke-i kolom
ke-j diperoleh dengan rumus:
𝑐𝑖𝑗 = 𝑎𝑖1 𝑏1𝑗 + 𝑎𝑖2 𝑏2𝑗 + ⋯ + 𝑎𝑖𝑛 𝑏𝑛𝑗
𝑛

𝑐𝑖𝑗 = ∑ 𝑎𝑖𝑡 𝑏𝑡𝑗

𝑡=1
Dimana 𝑖 = 1,2,3, … , 𝑚
𝑗 = 1,2,3, … , 𝑝
𝐴𝐵 = 𝐶

23
 Program linear
𝑎11 𝑎12 … 𝑎1𝑗 …
𝑏11 𝑎1𝑛 𝑏12 … 𝑏1𝑗 … 𝑏1𝑝
𝑎21 𝑎22 … 𝑎2𝑗 …
𝑏21 𝑎2𝑛 𝑏22 … 𝑏2𝑗 … 𝑏2𝑝
⋮ ⋮
𝑎𝑖1 𝑎𝑖2 … 𝑎𝑖𝑗 … 𝑎𝑖𝑛 + 𝑏𝑖1 𝑏𝑖2 … 𝑏𝑖𝑗 … 𝑏𝑖𝑛
⋮ ⋮
𝑎
[ 𝑚1 𝑎𝑚2 … 𝑎𝑚𝑗 … 𝑎𝑚𝑛 ] [𝑏𝑚1 𝑏𝑚2 … 𝑏𝑚𝑗 … 𝑏𝑚𝑝 ]
𝑐11 𝑐12 … 𝑐1𝑗 … 𝑐1𝑝
𝑐21 𝑐22 … 𝑐2𝑗 … 𝑐2𝑝
⋮
=⁡ 𝑐 𝑐𝑖2 … 𝑐𝑖𝑗 … 𝑐𝑖𝑝 = 𝐶
𝑖1
⋮
[𝑐𝑚1 𝑐𝑚2 … 𝑐𝑚𝑗 … 𝑐𝑚𝑝 ]

Catatan:
Perkalian dua matriks
dapat dilakukan jika jumlah
kolom dari matriks pertama
sama dengan jumlah baris pada
matriks kedua.
𝐴𝑚×𝑛 𝐵𝑛×𝑝 = 𝐶𝑚×𝑝

Jika jumlah kolom matriks pertama sama dengan matriks kedua maka
dikatakan conformable.
Contoh:
𝑎11 𝑎12 𝑏 𝑏12
1. 𝐴 = [𝑎 𝑎 ], 𝐵 = [ 11 ]
21 22 𝑏21 𝑏22

𝑎11 𝑎12 𝑏11 𝑏12

𝐴 + 𝐵 = [𝑎 𝑎22 ] [𝑏21 ]
21 𝑏22

𝑎 𝑏 + 𝑎12 𝑏21 𝑎12 𝑏12 + 𝑎12 𝑏22

= [ 11 11 ]
𝑎21 𝑏11 + 𝑎22 𝑎21 𝑏12 + 𝑎22 𝑏22

1 2 5 6
2. 𝐴 = [ ],⁡𝐵 = [ ]
3 4 7 8
1 2 5 6
𝐴𝐵 = [ ][ ]
3 4 7 8
1.5 + 2.7 1.6 + 2.8 19 24
=[ ]=[ ]
3.5 + 4.7 3.6 + 4.8 43 50

24
 Program linear
Pada matriks tidak berlaku sifat komutatif, yaitu 𝐴𝐵 ≠ 𝐵𝐴, jika 𝐴𝐵 =
𝐵𝐴 maka kedua matriks itu dikatakan commute.
4. Perkalian matriks dengan skalar
Jika matriks A dikalikan dengan skalar k maka semua elemen dari matriks
A harus dikalikan dengan k. Jadi jika 𝐴 = (𝑎𝑖𝑗 ) maka 𝑘𝐴 = 𝑘(𝑎𝑖𝑗 ) =
(𝑎𝑖𝑗 )𝑘 = 𝐴𝑘.
Contoh:
1 2
𝑘 = 3, 𝐴 = [ ]
3 4

1 2 3.1 3.2 3 6
𝑘𝐴 = 3𝐴 = 3 [ ]=[ ]=[ ]
3 4 3.3 3.4 9 12

D. Aplikasi Komputer (Program Matlab) pada Matriks

Pada Matlab operasi aritmetika seperti penjumlahan, pengurangan, perkalian,
dan pembagian dapat dibentuk langsung dengan matriks.

Langkah pertama yang dilakukan adalah membentuk matriksnya. Ada

beberapa cara dalam Matlab untuk membentuk matriks dengan metode yang
sederhana. Sebagai contoh jika diketahui sebuah matriks 4 baris dan 3 kolom:
1 2 3
4 5 6
𝑀=[ ] maka untuk menuliskan di Matlab dapat dilakukan dengan
7 8 9
0 1 2
mengetik perintah berikut:
≫ 𝑀 = [1⁡2⁡3; 4⁡5⁡6; 7⁡8⁡9; 0⁡1⁡2]
B=

1 2 3
4 5 6
7 8 9
0 1 2

25
 Program linear
Dapat bahwa nilai matriks yang dimasukkan berada dalam kurung siku.
Elemen-elemen setiap baris harus dipisahkan dengan spasi (blanks) atau dengan
tanda koma. Akhir dari tiap baris, kecuali baris yang terakhir dapat dinyatakan
dengan “ ; “ (semicolon).
Jika diketahui matriksnya berukuran 3 × 3 dengan elemen-elemennya sebagai
berikut:
1 2 3
𝐷 = [4 5 6]
7 8 9
Maka untuk input ke Matlab selain dengan cara yang dituliskan sebelumnya,
dapat dilakukan seperti berikut ini:
» D=[1 2 3
456
7 8 9]

D=
1 2 3
4 5 6
7 8 9
1. Transpos matriks
Transpos matriks dapat dilakukan dengan memberikan tanda apostrope
pada notasi matriks tersebut.
Contoh:
0 9 8
𝐴 = 7 6 5]
[
4 3 2
Maka untuk mendapatkan tranpos dari matriks A adalah dengan
mengetikan perintah berikut di Matlab:
A=
0 9 8
7 6 5
4 3 2
» B=A'

26
 Program linear
B=
0 7 4
9 6 3
8 5 2
atau
» conj(A')
ans =
0 7 4
9 6 3
8 5 2
2. Invers Matriks
Fungsi inv dalam Matlab digunakan untuk menghitung invers matriks.
Misalnya diketahui matriks A didefinisikan sebagai berikut:
A=[0 9 8; 7 6 5;4 3 2]
A=
0 9 8
7 6 5
4 3 2
Maka,
» B=inv(A)
B=
-0.1000 0.2000 -0.1000
0.2000 -1.0667 1.8667
-0.1000 1.2000 -2.1000
3. Determinan
Pada aplikasi aljabar, pengetahuan tentang determinan suatu matriks
dibutuhkan. Matlab memlunyai fungsi built-in untuk ini, yaitu function det
dirancang untuk perhitungan determinan.
Contoh:
𝐴 = 𝑚𝑎𝑔𝑖𝑐(3)
» K=magic(3)

27
 Program linear
K=
8 1 6
3 5 7
4 9 2
» det(K)
ans =
-360
4. Penjumlahan dan Pengurangan
Dua matrisk A dan B, kedua matriks tersebut dapat dijumlahkan atau
dikurangkan jika mempunyai ukuran yang sama atau berdimensi sama.
Contoh:
1 2 7 8
a. Jika diketahui 𝐴 = [3 4] , 𝐵 = [9 0]
5 6 1 2
Dengan menggunakan Matlab maka kedua matriks tersebut dapat
dioperasikan untuk operasi penjumlahan dan pengurangan.
» A=[1 2;3 4;5 6]
A=
1 2
3 4
5 6
» B=[7 8;9 0;1 2]
B=
7 8
9 0
1 2
» C=A+B
C=
8 10
12 4
6 8
» D=A-B

28
 Program linear
D=
-6 -6
-6 4
4 4
b. Jika diketahui vektor x adalah:
1
𝑥 = 2] dan y mengurangi 1 dari setiap elemen vektor x, 𝑦 = 𝑥 − 1,
[
3
maka dengan Matlab hal di atas dapat dikerjakan sebagai berikut:
» x=[1;2;3]
x=
1
2
3
» y=x-1
y=
0
1
2

5. Perkalian matriks
a. Perkalian matriks dengan skalar
Jika A adalah suatu matriks dan c adalah suatu skalar maka hasil kali
cA adalah matriks yang diperoleh dengan mengalikan masing-masing entri
dari A oleh c.
Contoh:
1 2
𝐴 = [3 4] dan 𝑐 = 8,
5 6
Maka diperoleh hasilnya dengan Matlab:
» A=[1 2;3 4; 5 6]
A=
1 2

29
 Program linear
3 4
5 6
» c=3
c=
3
» Q=c*A
Q=
3 6
9 12
15 18
b. Perkalian matriks dengan matriks
Jika A adalah matriks dengan ukuran 𝑚 × 𝑟 dan B adalah matriks 𝑟 ×
𝑛, maka hasil kali AB adalah matriks 𝑚 × 𝑛.
Perkalian matriks dalam Matalb dinotasikan dengan “ * “.
Contoh:
Jika matriks A berukuran 2 × 3 dan matriks B adalah 3⁡ × 4 maka akan
diperoleh hasilnya matriks C dengan ukuran 2 × 4.
» A=[1 2 3;4 5 6]
A=
1 2 3
4 5 6
» B=[9 8 7 6; 5 4 3 2; 1 0 9 8]
B=
9 8 7 6
5 4 3 2
1 0 9 8
» C=A*B
C=
22 16 40 34
67 52 97 82

30
 Program linear
E. Sistem Persamaan Linear
Garis dalam bidang 𝑥𝑦 merupakan himpunan pasangan berurutan (𝑥, 𝑦),
secara aljabar dapat dinyatakan dengan persamaan yang berbentuk:
⁡𝑎11 𝑥 + 𝑎12 𝑦 = 𝑏1 .............................................. (1) disebut persamaan
linear, karena pangkat dari variabel (peubah) 𝑥 dan 𝑦 adalah satu.
Secara umum persamaan linear dalam n variabel 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 dapat
dinyatakan dalam bentuk
𝑎11 𝑥1 + 𝑎12 𝑥2 + 𝑎13 𝑥3 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1 ....... (2)
𝑎11 , 𝑎12 , 𝑎13 , … , 𝑎1𝑛 dan 𝑏1 adalah konstata linear.

Solusi (penyelesaian) dari persamaan (2) mengandung pengertian bahwa

terdapat suatu urutan dari n bilangan 𝑠1 , 𝑠2 , 𝑠3 , … , 𝑠𝑛 yang jika disubstitusi secara
berurutan menggantikan 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 akan memenuhi persamaan itu atau
dengan kata lain persamaan (2) menjadi persamaan yang benar.
Himpunan semua persamaan seperti itu disebut himpunan penyelesaian
(bilangan penyelesaian).
Sistem persamaan linear adalah kumpulan (himpunan berhingga) persamaan
linear di dalam variabel 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 . Dalam bentuk umum, suatu sistem
persamaan linear dapat dirumuskan:
𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 = 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 = 𝑏1
} ......................... (3)
⋮ ⋮
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 = 𝑏𝑚
Sama halnya dengan persamaan, himpunan penyelesaian suatu sistem
persamaan linear adalah urutan dari bilangan-bilangan 𝑠1 , 𝑠2 , 𝑠3 , … , 𝑠𝑛 yang jika
dipakai untuk menggantikan 𝑥1 , 𝑥2 , 𝑥3 , … , 𝑥𝑛 memenuhi sistem persamaan itu4.
1. Penyelesaian dengan menggunakan aturan Cramer
Diketahui
⁡𝑎11 𝑥 + 𝑎12 𝑦 = 𝑏1
} ....................................................... (4)
⁡𝑎21 𝑥 + 𝑎22 𝑦 = 𝑏2
Dengan bantun pengertian matriks, maka persamaan 4 dapat dinyatakan
sebagai persamaan matriks seperti berikut:
4
N. Soemartojo, Program Linear. (Jakarta: Depdikbud.1995). hlm. 3

31
 Program linear
⁡𝑎11 𝑎12 𝑥 𝑏1
[⁡𝑎 ]
𝑎22 𝑦[ ] = [ ]
21 𝑏2
atau 𝐴 × 𝑋 = 𝐵,
dengan
⁡𝑎11 𝑎12 𝑥 𝑏1
𝐴 = [⁡𝑎 𝑎22 ] , 𝑋 = [ 𝑦 ] , 𝐵 = [ ]
21 𝑏2
terdapat dua kemungkinan:
a) Jika det(𝐴) = 0 maka tidak terdapat 𝐴−1
b) Jika det(𝐴) ≠ 0 maka terdapat 𝐴−1

Catatan:

det(𝐴) = 𝑎11 . 𝑎22 − 𝑎12 . 𝑎21

Selanjutnya, untuk memperoleh pasangan (𝑥, 𝑦) yang merupakan pemecahan

sistem persamaan linear di atas, Cramer mengembangkan aturan
det⁡(𝐴𝑥 ) det⁡(𝐴𝑦 )
𝑥= dan 𝑦 =
det(𝐴) det(𝐴)

det(𝐴𝑥 ) = 𝑎22 . 𝑏1 − 𝑎12 . 𝑏2

det(𝐴𝑦 ) = 𝑎11 . 𝑏2 . −𝑎21 . 𝑏1
Dengan demikian terdapat kemungkinan
a) det(𝐴) = 0; det(𝐴𝑥 ) ≠ 0 dan det(𝐴𝑦 ) ≠ 0
Menunjukkan sistem persamaan tidak mempunyai penyelesaian.
Secara geometris, kedua garis lurus sejajar, seperti gambar 1
b) det(𝐴) = 0; det(𝐴𝑥 ) = 0 dan det(𝐴𝑦 ) = 0
Menunjukkan sistem persamaan mempunyai banyak penyelesaian.
Secara geometris, kedua garis lurus berimpit, seperti gambar 2.
c) det(𝐴) ≠ 0;
Menunjukkan sistem persamaan mempunyai satu penyelesaian.
Secara geometris, kedua garis lurus berpotongan, seperti gambar 3.

32
 Program linear
𝑦 𝑦 𝑦 𝑔1

𝑔2 𝑥 𝑥 𝑔2 𝑥
𝑔1 ⁡𝑑𝑎𝑛⁡𝑔2
𝑔1

Gambar 1. Gambar 2. Gambar 1.

tidak ada tidak terhingga satu penyelesaian
penyelesaian penyelesaian

Contoh:
𝑥+𝑦 =5
a) } sistem persamaan tidak mempunyai penyelesaian (tidak
𝑥+𝑦 =7
konsisten)
3𝑥 + 4𝑦 = 5
b) } sistem persamaan mempunyai penyelesaian tak berhingga
6𝑥 + 8𝑦 = 10
(konsisten)
2𝑥 + 4𝑦 = 24
c) } sistem persamaan mempunyai satu penyelesaian
3𝑥 + 5𝑦 = 31
(konsisten)
Penyelesaian:
det(𝐴) = 2.5 − 4.3 = 10 − 12 = −2
det(𝐴𝑥 ) = 24.5 − 31.4 = −4
det(𝐴𝑦 ) = 2.31 − 3.24 = −10
−4 −10
𝑥= = 2, 𝑦 = =5
−2 −2

2. Penyelesaian sistem persamaan dengan Eliminasi Gauss

Prosedur penyelesaian sistem persamaan linear dengan menggunakan
eliminasi Gauss didasarkan pada upaya mereduksi matriks yang diperbesar
menjadi bentuk eselon baris yang direduksi.
Perhatikan sistem persamaan (3). Matriks yang diperbesar (matriks lengkap)
dari sistem persamaan itu dituliskan sebagai:

33
 Program linear
𝑎11 𝑎12 … 𝑎1𝑗 … 𝑎1𝑛
𝑎21 𝑎22 … 𝑎2𝑗 … 𝑎2𝑛
⋮
𝑎𝑖1 𝑎𝑖2 … 𝑎𝑖𝑗 … 𝑎𝑖𝑛
⋮
[𝑎𝑚1 𝑎𝑚2 … 𝑎𝑚𝑗 … 𝑎𝑚𝑛 ]

Baris matriks yang diperbesar bersesuain atau diasosiasikan dengan

persamaan dari persamaan (3). Oleh karena itu, pengerjaan mereduksi baris
matriks yang diperbesar sesuai dengan pengerjaan mengeliminasikan variabel dari
satu persamaan ke persamaan yang lainnya.
Proses mengeliminasikan persamaan ke persamaan yang lainnya adalah
a. Kalikan persamaan dengan konstanta yang tidak sama dengan nol, supaya
konstanta (koefisien) variabel yang akan dieliminasikan dari persamaan
yang lain, nilainya adalah satu
b. Pertukarkan dua persamaan
c. Tambahkan kelipatan suatu persamaan kepada persamaan lain,
eliminasikan variabel terntentu.
Proses mereduksi baris di dalam matriks yang diperbesar yang bersesuain
dengan pengerjaan pada sistem persamaan disebut operasi baris elementer, yaitu:
a. Kalikan sebuah baris dengan konstanta tertentu yang tidak sama dengan
nol
b. Pertukarkan dua baris
c. Tambahkan kelipatan suatu baris kepada baris yang lain
Perhatikan sistem persamaan berikut:
i. 𝑥 + 2𝑦 + 4𝑧 = 16
ii. 3𝑥 + 𝑦 = 𝑧 = 4
iii. 2𝑥 + 3𝑦 + 𝑧 = 10
untuk mengeliminasikan x dari persamaan i, ii, dan iii ditempuh langkah
a. Kalikan persamaan i dengan -3 kemudian tambahkan ke persamaan ii; kalikan
i dengan (-2) kemudian tambahkan ke persamaan iii
𝑥 + 2𝑦 + 4𝑧 = 16
−5𝑦 − 13𝑧 = −44

34
 Program linear
−𝑦 − 7𝑧 = −22
b. Kalikan baris ketiga dengan (-1) kemudian pertukanrkan dengan baris kedua
𝑥 + 2𝑦 + 4𝑧 = 16
𝑦 + 7𝑧 = 22
−5𝑦 − 13𝑧 = −44
c. Kalikan baris ii dengan (-2) kemudian tambahkan ke baris i dan kalikan baris
ii denga (5), setelah itu tambahkan ke baris iii
𝑥 − 10𝑧 = −28
𝑦 + 7𝑧 = 22
22𝑧 = 66
1
d. Kalikan iii dengan 2

𝑥 − 10𝑧 = −28
𝑦 + 7𝑧 = 22
𝑧=3
Kalikan iii dengan (10) kemudian ke i
Kalikan iiii dengan (-7) kemudian tambahkan ke ii
𝑥=2
𝑦=1
𝑧=3
atau matriks diperbesar sistem terakshir adalah
1 0 0 2
[0 1 0 1 ]
0 0 1 3
adalah matriks dalam bentuk eselon baris yang direduksi.

35
 Program linear

Ringkasan
Matriks dalam bentuk eselon baris yang direduksi harus
mempunyai sifat:
1. Jika suatu matriks tidak terdiri seluruhnya atas nol, maka
bilangan tak nol pertama di dalam baris tersebut ialah 1
(dinamakan 1 utama)
2. Jika ada beberapa baris yang terdiri seluruhnya atas nol,
maka semua baris seperti itu dikelompokkan bersama-
sama pada baris urutan bawah (di bawah matriks)
3. Di dalam sebarang dua baris yang berturutan yang tidak
terdiri seluruhnya atas nol, maka 1 utama di dalam baris
yang lebih rendah terdapat lebihjauh ke kanan daripada 1
utama di dalam baris yang lebih tinggi.
4. Setiap kolom yang mengandung sebuah 1 utama
mempunyai nol di tempat lain.
Matriks yang mempunyai sifat 1, 2, dan 3 dikatakan
berada di dalam bentuk eselon baris.
Prosedur penyelesaian sistem persamaan dengan
menggunakan operasi baris elementer untuk memperoleh
matriks diperbesar di dalam bentik eselon baris yang
direduksi merupakan algoritma yang digunakan dalam
analisis persoalan program linear dengan cara simpleks.

36
 Program linear
Latihan
1. Kondisi apakah yang harus dipenuhi p supaya sistem persamaan linear
2𝑥 + 3𝑦 = 15
𝑝𝑥 − 6𝑦 = 18
Mempunyai penyelesaian 𝑥 > 0?
2. Sistem persamaan
𝑥 + 2𝑦 + 3𝑧 = 5
𝑥 + 8𝑧 = 17
2𝑥 + 5𝑦 + 3𝑧 = 3
a. Nyatakan sebagai 𝐴. 𝑋 = 𝐵
b. det(𝐴) = ⋯ ?

3. Sistem persamaan 𝐴. 𝑋 = 𝐵
4 −1 −3 𝑥 1
𝐴 = [8 1 −1], 𝑋 = [𝑦] , 𝐵 = [5]
2 1 2 𝑧 5
det⁡(𝐴𝑥 )= ...?

37
 Program linear

DAFTAR PUSTAKA

Aminuddin. 2005. Prinsip-prinsip Riset Operasi. Jakarta: Erlangga.

Anton, Howar. 1984. Aljabar Linear Elementer. Jakarta: Erlangga

Arhami Muhammad. 2005. Pemrograman Matlab. Yogyakarta: Andi

Offset.

Munir Rinaldi. 2009. Matematika Diskrit. Bandung: Informatika Bandung.

Soemartojo, Tapilouw Marthen. 1995. Materi Pokok Program Linear.

Jakarta: Depdikbud Dirjend Pendidikan Dasar dan Menengah.

Supranto J. 1974. Pengantar Matriks. Jakarta: Lembaga Penerbit FE UI.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

38
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang
sejarah program linear, keterampilan belajar secara
mandiri dalam mempelajari masalah-masalah
pemrograman linear dari kehidupan sehari-hari,
dengan menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan
mampu:
- Mengenal program linear sebagai penunjang
pengambilan keputusan
- Memahami syarat-syarat pemecahan persoalan
program linear
- Menyelesaikan persoalan program linear dengan
metode grafik maksimasi
- Memahami masalah teknis dalam program linear

39
 Program linear
FUNGSI TUJUAN MAKSIMISASI

A. Formulasi Permasalahan
Metode grafik hanya bisa digunakan untuk menyelesaikan permasalahan
dimana hanya terdapat dua variabel keputusan. Untuk menyelesaikan
permasalahan tersebut, langkah pertama yang harus dilakukan adalah
memformulasikan permasalahan yang ada ke dalam bentuk Linear Programming
(LP). Langkah-langkah dalam formulasi permasalahan adalah :

1. pahamilah secara menyeluruh permasalahan manajerial yang dihadapi

2. identifikasikan tujuan dan kendalanya
3. definisikan variabel keputusannya
4. gunakan variabel keputusan untuk merumuskan fungsi tujuan dan fungsi
kendala secara matematis.
Sebagai contoh dalam memformulasikan permasalahan, berikut ini akan
dibahas perusahaan Ikhwan Mandiri yang akan membuat meja dan kursi.
Keuntungan yang diperoleh dari satu unit meja adalah $7,- sedang keuntungan
yang diperoleh dari satu unit kursi adalah $5,-.

Namun untuk meraih keuntungan tersebut Ikhwan Mandiri menghadapi

kendala keterbatasan jam kerja. Untuk pembuatan 1 unit meja dia memerlukan 4
jam kerja. Untuk pembuatan 1 unit kursi dia membutuhkan 3 jam kerja. Untuk
pengecatan 1 unit meja dibutuhkan 2 jam kerja, dan untuk pengecatan 1 unit
kursi dibutuhkan 1 jam kerja. Jumlah jam kerja yang tersedia untuk
pembuatan meja dan kursi adalah 240 jam per minggu sedang jumlah jam kerja
untuk pengecatan adalah 100 jam per minggu. Berapa jumlah meja dan kursi
yang sebaiknya diproduksi agar keuntungan perusahaan maksimum?

Dari kasus di atas dapat diketahui bahwa tujuan perusahaan adalah

memaksimumkan profit. Sedangkan kendala perusahaan tersebut adalah
terbatasnya waktu yang tersedia untuk pembuatan dan pengecatan. Apabila
permasalahan tersebut diringkas dalam satu tabel akan tampak sebagai berikut:

40
 Program linear
TABEL 1.1 Informasi Permasalahan Ikhwan Mandiri

Jam kerja untuk Membuat 1 unit Total waktu

produk tersedia per pekan
Meja Kursi
Pembuatan 4 2 240
pengecatan 2 1 100
Profit 7 5

Mengingat produk yang akan dihasilkan adalah meja dan kursi, maka
dalam rangka memaksimumkan profit, perusahaan harus memutuskan berapa
jumlah meja dan kursi yang sebaiknya diproduksi. Dengan demikian dalam kasus
ini, yang merupakan variabel keputusan adalah meja (X1) dan kursi (X2).
Setelah kita mendefinisikan variabel keputusan, maka langkah selanjutnya
adalah menuliskan secara matematis fungsi tujuan dan fungsi kendala.
1. Fungsi tujuan
Tujuan perusahaan adalah maksimisasi keuntungan, sehingga kita dapat
menuliskan fungsi tujuan sebagai berikut :

P = ($7 x jumlah meja yang diproduksi + $5 jumlah kuris yang diproduksi

atau secara matematis dapat dituliskan :

Maksimisasi Z = $7X1 + $5X2

2. Fungsi kendala
Berkaitan dengan sumber daya yang digunakan, perusahaan tidak bisa
memperkirakan secara tepat kebutuhan sumber daya yang digunakan untuk
mencapai keuntungan tertentu. Biasanya perusahaan menyediakan sumber daya
tertentu yang merupakan kebutuhan minimum atau maksimum. Kondisi seperti ini
secara matematis diungkapkan dengan pertidaksamaan.

Kendala yang pertama adalah waktu yang tersedia di departemen

pembuatan. Total waktu yang diperlukan untuk pembuatan X1 (meja) dimana
untuk membuat satu unit meja diperlukan waktu 4 jam kerja dan untuk pembuatan
X2 (kursi) dimana untuk membuat satu unit kursi diperlukan waktu 3 jam kerja

41
 Program linear
adalah 240 jam. Kalimat ini bisa dirumuskan dalam pertidaksamaan matematis
menjadi :

4 X1 + 3 X2 ≤ 240

Seperti halnya pada kendala yang pertama, maka pada kendala kedua
dapat diketahui bahwa total waktu yang diperlukan untuk pengecatan X1 (meja)
dimana untuk mengecat satu unit meja diperlukan waktu 2 jam kerja dan untuk
pembuatan X2 (kursi) dimana untuk mengecat satu unit kursi dibutuhkan waktu 1
jam kerja adalah 100 jam. Kalimat ini bisa dirumuskan dalam pertidaksamaan
matematis menjadi :

2X1 + 1 X2 ≤ 100

Salah satu syarat yang harus dipenuhi dalam Linear Programming adalah
asumsi nilai X1 dan X2 tidak negatif. Artinya bahwa

X1 ≥ 0 (jumlah meja yang diproduksi adalah lebih besar atau sama

dengan nol)
X2 ≥ 0 (jumlah kursi yang diproduksi adalah lebih besar atau sama
dengan nol)

Dari uraian di atas dapat dirumuskan formulasi permasalahan secara

lengkap sebagai berikut :

Fungsi tujuan :

Maksimisasi Z = $7X1 + $5X2.

Fungsi kendala :

4 X1 + 3 X2 ≤ 240 (kendala departemen pembuatan)

2X1 + 1 X2 ≤ 100 (kendala departemen pengecatan)

X1 ≥ 0 (kendala non negatif pertama)

X2 ≥ 0 (kendala non negatif kedua)

42
 Program linear
B. Penyelesaian Linear Programming Secara Grafik
Kasus Ikhwan Mandiri tersebut akan kita selesaikan dengan metode grafik.
Keterbatasan metode grafik adalah bahwa hanya tersedia dua sumbu ordinat,
sehingga tidak bisa digunakan untuk menyelesaikan kasus yang lebih dari dua
variabel keputusan.

Langkah pertama dalam penyelesaian dengan metode grafik adalah

menggambarkan fungsi kendalanya. Untuk menggambarkan kendala pertama
secara grafik, kita harus merubah tanda pertidaksamaan menjadi tanda persamaan
seperti berikut.

4 X1 + 3 X2 = 240

Kendala ini akan memotong salah satu atau kedua sumbu.

Sebagaimana halnya yang sudah kita pelajari dalam aljabar, bahwa untuk
menggambarkan fungsi linear yang tidak lain merupakan garis lurus, maka kita
akan mencari titik potong garis tersebut dengan kedua sumbu. Suatu garis akan
memotong salah satu sumbu apabila nilai variabel yang lain sama dengan nol.
Dengan demikian kendala pertama akan memotong X1, pada saat X2 = 0,
demikian juga kendala ini akan memotong X2, pada saat X1 = 0.

Kendala I: 4 X1 + 3 X2 = 240

memotong sumbu X1 pada saat X2 = 0

4 X1 + 0 = 240

X1 = 240/4

X1 = 60.

memotong sumbu X2 pada saat X1 = 0

0 + 3 X2 = 240

X2 = 240/3

X2 = 80

43
 Program linear
Kendala I memotong sumbu X1 pada titik (60, 0) dan memotong sumbu
X2 pada titik (0,80).

Kendala II: 2 X1 + 1 X2 = 100

memotong sumbu X1 pada saat X2 = 0

2 X1 + 0 = 100

X1 = 100/2

X1 = 50

memotong sumbu X2 pada saat X1 =0

0 + X2 = 100

X2 = 100

Kendala II memotong sumbu X1 pada titik (50, 0) dan memotong sumbu

X2 pada titik (0,100).

Peraga 1.1. Grafik Area Layak

44
 Program linear
Titik potong kedua kendala bisa dicari dengan cara substitusi atau
eliminasi

2 X1 + 1 X2 = 100

X2 = 100 - 2 X1

4 X1 + 3 X2 = 240

4 X1 + 3 (100 - 2 X1) = 240

4 X1 + 300 - 6 X1 = 240

- 2 X1 = 240 - 300

- 2 X1 = - 60

X1 = -60/-2 = 30.

X2 = 100 - 2 X1

X2 = 100 - 2 * 30

X2 = 100 - 60

X2 = 40

Sehingga kedua kendala akan saling berpotongan pada titik (30, 40).

Tanda ≤ pada kedua kendala ditunjukkan pada area sebelah kiri dari garis
kendala. Sebagaimana nampak pada Peraga 1. 1, feasible region (area layak)
meliputi daerah sebelah kiri dari titik A (0; 80), B (30; 40), dan C (60; 0).

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

1. dengan menggunakan garis profit (iso profit line)

2. dengan titik sudut (corner point)
Penyelesaian dengan menggunakan garis profit adalah penyelesaian
dengan menggambarkan fungsi tujuan. Kemudian fungsi tujuan tersebut digeser
ke kanan sampai menyinggung titik terjauh dari dari titik nol, tetapi masih berada
pada area layak (feasible region). Untuk menggambarkan garis profit, kita

45
 Program linear
mengganti nilai Z dengan sembarang nilai yang mudah dibagi oleh koefisien pada
fungsi profit. Pada kasus ini angka yang mudah dibagi angka 7 (koefisien X1) dan
5 (koefisien X2) adalah 35. Sehingga fungsi tujuan menjadi 35 = 7X1 + 5 X2.
Garis ini akan memotong sumbu X1 pada titik (5, 0) dan memotong sumbu X2
pada titik (0, 7).

Dari Peraga 1. 2 dapat dilihat bahwa iso profit line menyinggung titik B
yang merupakan titik terjauh dari titik nol. Titik B ini merupakan titik optimal.
Untuk mengetahui berapa nilai X1 dan X2, serta nilai Z pada titik B tersebut, kita
mencari titik potong antara kendala I dan kendala II (karena titik B merupakan
perpotongan antara kendala I dan kendala II). Dengan menggunakan eliminiasi
atau subustitusi diperoleh nilai X1 = 30, X2 = 40. dan Z = 410. Dari hasil
perhitungan tersebut maka dapat disimpulkan bahwa keputusan perusahaan yang
akan memberikan profit maksimal adalah memproduksi X1 sebanyak 30 unit, X2
sebanyak 40 unit dan perusahaan akan memperoleh profit sebesar 410.

Peraga 1. 2. Iso profit line

46
 Program linear
Penyelesaian dengan menggunakan titik sudut (corner point) artinya kita
harus mencari nilai tertinggi dari titik-titik yang berada pada area layak (feasible
region). Dari peraga 1, dapat dilihat bahwa ada 4 titik yang membatasi area layak,
yaitu titik 0 (0, 0), A (0, 80), B (30, 40), dan C (50, 0).

Keuntungan pada titik O (0, 0) adalah (7 x 0) + (5 x 0) = 0.

Keuntungan pada titik A (0; 80) adalah (7 x 0) + (5 x 80) = 400.

Keuntungan pada titik B (30; 40) adalah (7 x 30) + (5 x 40) = 410.

Keuntungan pada titik C (50; 0) adalah (7 x 50) + (5 x 0) = 350.

Karena keuntungan tertinggi jatuh pada titik B, maka ebaiknya

perusahaan memproduksi meja sebanyak 30 unit dan kursi sebanyak 40 unit, dan
perusahaan memperoleh keuntungan optimal sebesar 410.

Ringkasan

Program linear dengan metode grafik hanya dapat digunakan untuk

menyelesaikan permasalahan dengan 2 variabel keputusan. Dalam
penyelesaian permasalahan diawali dengan formulasi permasalahan,
kemudian menggambarkan fungsi kendala serta menentukan area layak.
Baru kemudian menentukan solusi optimal yang dapat menggunakan 2
pendekatan, yaitu dengan pendekatan garis profit (isoprofit line) atau titik
sudut (corner point).

47
 Program linear
Latihan

Untuk memperdalam pemahaman Anda mengenai materi di atas, silakan anda

mengerjakan latihan berikut ini !

1) Apa yang dimaksud dengan LP?

2) Tuliskan 4 ciri kusus yang melekat pada permasalahan LP.
3) Tuliskan 5 asumsi dasar yang harus dipenuhi dalam penyelesaian
permasalahan dengan menggunakan LP.
4) Tuliskan langkah-langkah dalam formulasi permasalahan LP.
5) Apa syarat permasalahan dapat diselesaikan dengan metode grafik?
6) Apa yang dimaksud dengan area layak (feasible region)?
7) Bagaimana cara menentukan solusi optimal dengan menggunakan isoprofit
line?
8) Bagaimana cara menentukan solusi optimal denan cara corner point?

Pilih salah satu jawaban yang paling tepat dari beberapa alternatif jawaban
yang disediakan !

Kasus 1 digunakan untuk menjawab pertanyaan nomor 1 s.d. 5

PT Padat Karya memproduksi dua macam batako: batako semen dan

batako kapur. Biaya pembuatan batako semen diperkirakan Rp. 150,- sedang
biaya pembuatan batako kapur diperkirakan Rp. 100,-. Batako semen dijual
seharga Rp. 400,- dan batako kapur dijual seharga Rp. 250,-.

Untuk pembuatan kedua macam batako tersebut dipergunakan 2 macam

mesin: A: mesin pencampur dan B: mesin pencetak. Untuk mencampur batako
semen diperlukan waktu 1 jam, dan untuk mencetak batako semen diperlukan
waktu 2 jam. Batako kapur dicampur selama 1.5 jam dan dicetak selama 1 jam.
Selama satu bulan kapasitas mesin A 320 jam kerja. Sedang kapasitas mesin B
adalah 480 jam kerja. Jika tujuan perusahaan memaksimumkan keuntungan ,
jawablah pertanyaan nomor 1 – 5 berikut ini.

48
 Program linear

1) Formulasi dalam bentuk Linear Programming dari permasalahan di atas

adalah:
A. Fungsi Tujuan Max Z = 400X + 250Y
Fungsi Kendala X + 1,5Y ≤ 320
2X + Y ≤ 480
X ≤ 0
Y ≤ 0
B. Fungsi Tujuan Max Z = 150X + 100Y
Fungsi Kendala X + 1,5Y ≤ 320
2X + Y ≤ 480
X ≥ 0
Y ≥ 0
C. Fungsi Tujuan Max Z = 250X + 150Y
Fungsi Kendala X + 1,5Y ≤ 320
2X + Y ≤ 480
X ≥ 0
Y ≥ 0
D. Fungsi Tujuan Max Z = 250X + 150Y
Fungsi Kendala X + 2Y ≤ 320
1,5X + Y ≤ 480

49
 Program linear
X ≥ 0
Y ≥ 0
2) Dari gambar di atas yang merupakan area layak adalah area yang dibatasi titik
A. 0ABC
B. ABE
C. CDB
D. 0EBD
3) Jumlah batako semen dan batako kapur yang harus diproduksi agar profit
maksimum adalah :
A. Batako semen 80 unit dan batako kapur 200 unit
B. Batako semen 200 unit dan batako kapur 80 unit
C. Batako semen 320 unit dan batako kapur 0 unit
D. Batako semen 0 unit dan batako kapur 480 unit
4) Besarnya keuntungan maksimum adalah :
A. Rp 80.000,-
B. Rp. 72.000,-
C. Rp. 62.000,-
D. Rp 55.000,-
5) Solusi optimal terjadi pada :
A. Titik A
B. Titik B
C. Titik D
D. Titik C

50
 Program linear

DAFTAR PUSTAKA

Aminuddin. 2005. Prinsip-prinsip Riset Operasi. Jakarta: Erlangga.

Anton, Howar. 1984. Aljabar Linear Elementer. Jakarta: Erlangga

Arhami Muhammad. 2005. Pemrograman Matlab. Yogyakarta: Andi Offset.

Munir Rinaldi. 2009. Matematika Diskrit. Bandung: Informatika Bandung.

Soemartojo, Tapilouw Marthen. 1995. Materi Pokok Program Linear.

Jakarta: Depdikbud Dirjend Pendidikan Dasar dan Menengah.

Supranto J. 1974. Pengantar Matriks. Jakarta: Lembaga Penerbit FE UI.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

51
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang sejarah
program linear, keterampilan belajar secara mandiri
dalam mempelajari masalah-masalah pemrograman
linear dari kehidupan sehari-hari, dengan
menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan mampu:
- Mengenal program linear sebagai penunjang
pengambilan keputusan
- Memahami syarat-syarat pemecahan persoalan
program linear
- Menyelesaikan persoalan program linear dengan
metode grafik masalah minimisasi
- Memahami masalah teknis dalam program linear

52
 Program linear
FUNGSI TUJUAN MINIMISASI

A. Penyelesaian Linear Program Secara Grafik Untuk Fungsi Tujuan

Minimisasi
Permasalahan minimisasi dapat juga diselesaikan secara grafik. Langkah-
langkah penyelesaian permasalahan sama dengan penyelesaian permasalahan
untuk fungsi tujuan maksimisasi yaitu: formulasi permasalahan, menentukan area
layak, serta menentukan solusi optimal.
Dalam menentukan solusi optimal, seperti halnya pada permasalahan
maksimisasi, dapat digunakan pendekatan garis profit atau titik sudut. Untuk
lebih memahami penyelesaian permasalahan minimisasi berikut dibahas kasus
Valentine Meal.
Valentine Meal adalah makanan yang terbuat dari Jagung dan Kacang.
Makanan ini memiliki kandungan sekurang-kurangnya 30% Protein dan Serat
maksimal 5% sebagaimana tampak pada tabel berikut ini.
Tabel 4.1
kandungan gizi
per kilogram
Protein Serat biaya
Jagung 0,09 0,02 0,30
Kacang 0,60 0,06

Valentine Meal ingin menentukan biaya terendah dari makanan tersebut.

Karena makanan tersebut terbuat dari Jagung dan Kacang, variabel
keputusan untuk model tersebut dapat dirumuskan demikian
J = banyaknya jagung yang digunakan untuk campuran makanan
K = banyaknya kacang yang digunakan untuk campuran makanan
Fungsi tujuan adalah meminimumkan biaya dari campuran makanan, yang
dirumuskan demikian
Minimize Z = 0,3 J + 0,9 K
Kendala dari model mencerminkan jumlah yang diperlukan dan
persyaratan kandungan gizi yang diperlukan. Karena Valentine Meal memerlukan
800 kg makanan per hari, kendala tersebut bisa dirumuskan demikian:
J + K ≥ 800

53
 Program linear
Kandungan protein dalam jagung (J) dan kacang (K) adalah (0,09 J + 0,6
K). Kandungan protein ini sekurang-kurangnya 30% dari campuran makanan.
Oleh karena itu persamaannya menjadi demikian
0,09 J + 0,6 K ≥ 0,3 (J + K)
0,09 J + 0,6 K ≥ 0,3 J + 0,3K
(0,3 J - 0,09 J) + (0,3K - 0,6 K) ≤ 0
0,21 J - 0,3 K ≤ 0
Dengan cara yang sama, kendala dari kandungan serat bisa dirumuskan demikian:
0,02 J + 0,06 K ≤ 0,05 (J + K)
0,02 J + 0,06 K ≤ 0,05 J + 0,05 K
(0,05 J - 0,02 J) + (0,05K - 0,06 K) ≥ 0
0,03 J – 0,01 K ≥ 0
Dari uraian di atas dapat dirumuskan formulasi permasalahan secara lengkap
sebagai berikut :
Fungsi tujuan :
Minimize Z = 0,3 J + 0,9 K
Fungsi kendala :
J + K ≥ 800 (kendala kebutuhan makanan per hari)
0,21 J - 0,3 K ≤ 0 (kendala kandungan protein)
0,03 J – 0,01 K ≥ 0 (kendala kandungan serat)
J ≥ 0 (kendala non negatif pertama)
K ≥ 0 (kendala non negatif kedua)
Langkah pertama untuk menyelesaikan kasus Valentine Meal adalah dengan
menggambarkan fungsi kendala sebagaimana tampak pada Peraga 1.3.

54
 Program linear
Peraga 1. 3. Grafik Valentine Meal

Titik potong ketiga kendala bisa dicari dengan cara substitusi atau eliminasi Titik
potong kendala 1 (Protein: 0.21 J – 0.3 K ≤ 0) dan 3 (Kebutuhan per hari: 1
Jagung + 1 Kacang ≥ 800)
0.21 J - 0.3 K = 0
0.21J = 0.3 K
J = (0.3/ 0.21) K
J + K = 800
(0.3 / 0.21) K + K = 800
2,43 K = 800
K = 800/2,43
K = 329,22 dibulatkan menjadi 329.

J + 329,22 = 800
J = 470,78 dibulatkan menjadi 471.
Jadi titik potong kendala 1 (Protein: 0.21 J – 0.3 K ≤ 0) dan 3 (Kebutuhan per
hari: 1 Jagung + 1 Kacang ≥ 800) terletak pada titik B (471, 329).
Titik potong kendala 2 (Serat: 0.03 J – 0.01 K ≥ 0) dan kendala 3 (Kebutuhan per
hari: 1 J + 1 K ≥ 800)
0.03 J – 0.01 K = 0
0.03 J = 0.01 K

55
 Program linear
J = (0.01/ 0.03) K
J = 0.33 K

J + K = 800
0.33 K + K = 800
1.33 K = 800
K = 800 / 1.33
K = 600
J + 600 = 800
J = 200
Jadi titik potong kendala 2 (Serat: 0.03 J – 0.01 K ≥ 0) dan kendala 3 (Kebutuhan
per hari: 1 J + 1 K ≥ 800) terletak pada titik B (200, 600).
Tanda ≥ pada kendala Serat dan Kebutuhan per hari ditunjukkan pada area
sebelah kanan dari garis kendala. Sebagaimana nampak pada Peraga 1.3, feasible
region (area layak) meliputi daerah sebelah kanan dari titik A (200; 600), B (471;
329), atau di sebelah kanan kendala II dan III serta di sebelah kiri kendala I.
Untuk menentukan solusi yang optimal, ada dua cara yang bisa digunakan
yaitu
1. dengan menggunakan garis biaya (iso cost line)
2. dengan titik sudut (corner point)
Penyelesaian dengan menggunakan iso cost line adalah penyelesaian dengan
menggambarkan fungsi tujuan. Kemudian fungsi tujuan tersebut digeser ke kiri
sampai menyinggung titik terdekat dari titik nol, tetapi masih berada pada area
layak (feasible region). Untuk menggambarkan garis isocost, kita mengganti nilai
Z dengan sembarang nilai yang mudah dibagi oleh koefisien pada fungsi biaya.
Pada kasus ini angka yang mudah dibagi angka 0.3 (koefisien J) dan 0.9
(koefisien K) adalah 270. Sehingga fungsi tujuan menjadi 270= 0.3 J + 0.9 K.
Garis ini akan memotong sumbu J pada titik (900, 0) dan memotong sumbu K
pada titik (0, 300).

56
 Program linear
Peraga 1. 3. Garis Iso Cost pada Valentine Meal

Dari Peraga 1.3 dapat dilihat bahwa iso cost line menyinggung titik A
yang merupakan titik terdekat dari titik nol. Titik A ini merupakan titik optimal.
Untuk mengetahui berapa nilai J dan K, serta nilai Z pada titik A tersebut, kita
mencari titik potong antara kendala I dan kendala III (karena titik A merupakan
perpotongan antara kendala I dan kendala III). Dengan menggunakan eliminiasi
atau substitusi diperoleh nilai J = 471, K = 329. dan Z = 437. Dari hasil
perhitungan tersebut maka dapat disimpulkan bahwa keputusan perusahaan yang
akan memberikan biaya minimal adalah J sebanyak 471 unit, K sebanyak 329 unit
dan perusahaan akan mengalokasikan biaya sebesar 437.
Penyelesaian dengan menggunakan titik sudut (corner point) dari Peraga
1.3 dapat dilihat bahwa ada 2 titik yang dekat yang membatasi area layak, yaitu
titik A yang merupakan perpotongan kendala I dan III serta titik B yang
merupakan perpotongan kendala II dan III. Untuk penyelesaian dengan
menggunakan titk sudut kita mencari nilai Z di kedua titik tersebut kemudian kita
pilih nilai Z yang paling kecil. Titik A nilai J = 471 dan K = 329. Dengan
substitusi angka tersebut ke fungsi tujuan kita peroleh 0,3 J + 0,9 K = (0,3 x 471)
+ (0,9 x 329) = 437,4 dibulatkan menjadi 437. dan pada titik B nilai J = 200 dan K
= 600. Dengan mensubstitusikan nilai J dan K pada fungsi tujuan, kita peroleh:

57
 Program linear
0,3 J + 0,9 K = (0,3 x 200) + (0,9 x 600) = 600. Ternyata nilai Z pada titik A lebih
kecil daripada titik B. Dengan demikian titik A adalah titik optimal.

B. Isu Teknis Dalam Program Linear

Dalam Program Linear dengan metode grafik sering dijumpai
permasalahan secara teknis, yaitu:
1. infeasibility
2. unboundedness
3. redundancy
4. alternate optimal solutions
Infeasibility adalah suatu kondisi dimana tidak ada area layak yang
memenuhi semua kendala. Sebagai contoh Apabila kasus Krisna Furniture
ditambah kendala dari bagian pemasaran yang memberi syarat bahwa penjualan
Meja minimal 60 buah dan penjualan Kursi minimal 60 buah, maka akibatnya
tidak ada area layak (feasible region). Kondisi seperti ini disebut infeasibility.
Fungsi tujuan :
Maksimisasi Z = $7X1 + $5X2.
Fungsi kendala :
4 X1 + 3 X2 ≤ 240 (kendala departemen pembuatan)
2X1 + 1 X2 ≤ 100 (kendala departemen pengecatan)
1 X1 ≥ 60
1 X2 ≥ 60
X1 ≥ 0 (kendala non negatif pertama)
X2 ≥ 0 (kendala non negatif kedua)
Peraga 1. 4. Infeasibility

58
 Program linear
Unboundedness adalah suatu kondisi dimana area layak tidak terbatas.
Kasus ini biasanya muncul pada fungsi tujuan maksimisasi. Misalkan saja Krisna
Furniture lebih dahulu menentukan kendala dari pemasaran dan belum
menentukan kendala dari segi operasi untuk assembling dan finishing. maka
objective function menjadi tidak berhingga.
Fungsi tujuan :
Maksimisasi Z = $7X1 + $5X2.
Fungsi kendala :
1 X1 ≥ 60
1 X2 ≥ 60
X1 ≥ 0 (kendala non negatif pertama)
X2 ≥ 0 (kendala non negatif kedua)
Peraga 1. 5 Unboundedness

Redundancy. Constraint yang tidak mempengaruhi feasible region disebut

redundant conctraint. Misalkan pada kasus Krisna Furniture, bagian marketing
mengatakan bahwa tidak bisa menjual lebih dari 50 buah kursi, maka pernyataan
ini disebut redundant. Karena kenyataannya, bagian produksi maksimal hanya
bisa memproduksi 40 kursi.
Peraga 1. 6 Redundancy

59
 Program linear
Alternatif Optima adalah situasi dimana terdapat lebih dari satu solusi
optimal. Hal ini akan terjadi apabila garis profit sejajar dengan salah satu kendala.
Misalkan kita rubah profit margin untuk Meja dan Kursi pada kasus Krisna
Furniture menjadi 8 dan 6. Garis profit ini jika kita gambarkan akan sejajar
dengan kendala I karena kemiringannya sama. Solusi optimalnya terletak
sepanjang garis AB. Jadi solusi optimalnya bisa terletak pada alternatif I X1 = 0
dan X2 = 80 atau X1 = 30 dan X2 = 40 atau kombinasi lain sepanjang garis AB.
Fungsi tujuan :
Maksimisasi Z = $8X1 + $6X2.
Fungsi kendala :
4 X1 + 3 X2 ≤ 240 (kendala departemen pembuatan)
2X1 + 1 X2 ≤ 100 (kendala departemen pengecatan)
X1 ≥ 0 (kendala non negatif pertama)
X2 ≥ 0 (kendala non negatif kedua)
Peraga 1. 7. Alternatif Optima

60
 Program linear

Ringkasan
Pada kasus minimisasi kendala diberi tanda ≥ yang secara
grafis titik-titik di sebelah kanan kendala yang memenuhi syarat.
Pada kasus minimisasi solusi optimal dapat ditentukan dengan 2
cara yaitu dengan isocost line dan corner point. Untuk mencari
solusi optimal denan isocost line, solusi optimal adalah titik yang
paling dekat dengan titik nol tetapi masih berada pada area layak.
Sedangkan penentuan solusi optimal dengan corner point, solusi
optimal ditentukan dengan cara mencari nilai Z yang paling
rendah.
Dalam Linear Programming dengan metode grafik sering
dijumpai permasalahan secara teknis, yaitu: infeasibility ,
unboundedness, redundancy, alternate optimal solutions.

61
 Program linear
Latihan
Untuk memperdalam pemahaman Anda mengenai materi di atas, silakan anda
mengerjakan latihan berikut ini !
1) Bagaimana cara menentukan solusi optimal dari permasalahan LP dengan
fungsi tujuan
2) minimisasi dengan isocost line?
3) Bagaimana cara menentukan solusi optimal dari permasalahan LP dengan
fungsi tujuan
4) minimisasi dengan corner point?
5) Apa yang dimaksud redundancy?
6) Apa yang dimaksud infeasibility?
7) Apa yang dimaksud alternative optima?
8) Apa yang dimaksud unboundedness?

62
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang sejarah
program linear, keterampilan belajar secara mandiri
dalam mempelajari masalah-masalah pemrograman
linear dari kehidupan sehari-hari, dengan
menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan
dapat:
- Menjelaskan konsep dualitas
- Interpretasi ekonomis suatu masalah program
linear

(Apa yang telah Kami ceritakan itu), itulah yang benar, yang datang dari Tuhanmu,
karena itu janganlah kamu termasuk orang-orang yang ragu-ragu. (QS. 3. Al-Imran :60)

63
 Program linear
A. Teori Dualitas
Teori dualitas merupakan salah satu konsep programa linier yang penting dan
menarik ditinjau dari segi teori dan praktisnya. Ide dasar yang melatarbelakangi
teori ini adalah bahwa setiap persoalan programa linier mempunyai suatu
programa linier lain yang saling berkaitan yang disebut “dual”, sedemikian
sehingga solusi pada persoalan semula (yang disebut "primal”) juga memberi
solusi pada dualnya.
Pendefinisian dual ini akan tergantung pada jenis pembatas, tanda-tanda
variabel, dan bentuk optimasi dari persoalan primalnya. Akan tetapi, karena setiap
persoalan programa linier harus dibuat dalam bentuk standar lebih dahulu sebelum
modelnya dipecahkan , maka pendefinisian dibawah ini akan secara otomatis
meliputi ketiga hal di atas.
Bentuk umum masalah primal dual adalah sebagai berikut:
Primal
Maksimumkan: 𝑍 = 𝑐1𝑥1 + 𝑐2 𝑥2 + ⋯ + 𝑐𝑛 𝑥𝑛
Berdasarkan kendala:

𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 ≤ 𝑏1

𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 ≤ 𝑏2
⋮ ⋮ ⋮
𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑏𝑚
𝑥1 , 𝑥2 , … , 𝑥𝑛 ≥ 0
Dual
Minimumkan: 𝑍 = 𝑐1 𝑦1 + 𝑐2 𝑦2 + ⋯ + 𝑐𝑚𝑦𝑚
Berdasarkan kendala:
𝑎11 𝑦1 + 𝑎21 𝑦2 + ⋯ + 𝑎𝑚1 𝑦𝑚 ≤ 𝑐1
𝑎12 𝑦1 + 𝑎22 𝑦2 + ⋯ + 𝑎𝑚2 𝑦𝑚 ≤ 𝑐2
⋮ ⋮ ⋮
𝑎1𝑛 𝑥1 + 𝑎2𝑚 𝑥2 + ⋯ + 𝑎𝑛𝑚 𝑥𝑚 ≤ 𝑐𝑛
𝑦1 , 𝑦2 , … , 𝑦𝑚 ≥ 0

64
 Program linear
Kalau kita bandingkan kedua persoalan di atas, ternyata terdapat
korespondensi antara primal dengan dual sebagai berikut :
1. Koefisien fungsi tujuan primal menjadi konstanta ruas kanan bagi dual,
sedangkan konstanta ruas kanan primal menjadi koefisien fungsi tujuan bagi
dual.
2. Untuk tiap pembatas primal ada satu variaebl dual, dan untuk setiap variabel
primal ada satu pembatas dual.
3. Tanda ketidaksamaan pada pembatas akan bergantung pada fungsi tujuannya.
4. Fungsi tujuan berubah bentuk (maksimasi menjadi minimasi dan sebaliknya).
5. Setiap kolom pada primal berkorespondensi dengan baris (pembatas) pada
dual.
6. Setiap baris (pembatas) pada primal berkorespondensi dengan kolom pada
dual.
7. Dual dari dual adalah primal.

B. Hubungan Primal Dual

Nilai tujuan dalam suatu pasangan masalah primal dan dual harus memenuhi
hubungan berikut ini:
1. Untuk setiap pasangan pemecahan primal dual yang layak
𝑛𝑖𝑙𝑎𝑖 𝑡𝑢𝑗𝑢𝑎𝑛 𝑛𝑖𝑙𝑎𝑖 𝑡𝑢𝑗𝑢𝑎𝑛
( )≤( )
𝑑𝑎𝑙𝑎𝑚 𝑚𝑎𝑠𝑎𝑙𝑎ℎ 𝑚𝑎𝑘𝑠𝑖𝑚𝑖𝑠𝑎𝑠𝑖 𝑑𝑎𝑙𝑎𝑚 𝑚𝑎𝑠𝑎𝑙𝑎ℎ 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑎𝑠𝑖
2. Di pemecahan optimum untuk kedua masalah
𝑛𝑖𝑙𝑎𝑖 𝑡𝑢𝑗𝑢𝑎𝑛 𝑛𝑖𝑙𝑎𝑖 𝑡𝑢𝑗𝑢𝑎𝑛
( )=( )
𝑑𝑎𝑙𝑎𝑚 𝑚𝑎𝑠𝑎𝑙𝑎ℎ 𝑚𝑎𝑘𝑠𝑖𝑚𝑖𝑠𝑎𝑠𝑖 𝑑𝑎𝑙𝑎𝑚 𝑚𝑎𝑠𝑎𝑙𝑎ℎ 𝑚𝑖𝑛𝑖𝑚𝑖𝑠𝑎𝑠𝑖
Untuk menjelaskan hubungan antara primal dan dual, perhatikan ilustrasi
berikut ini :

Contoh:
Minimumkan: 𝑍 = 16𝑥1 + 30𝑥2 + 36𝑥3
Dengan kendala:
2𝑥1 + 3𝑥2 + 2𝑥3 ≥ 60
2𝑥1 + 5𝑥2 + 3𝑥3 ≥ 80

65
 Program linear
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Soal ini kita selesaikan melalui penyelesaian dualnya, yakni :
Maksimumkan : 𝑊 = 60𝑦1 + 80𝑦2
Dengan kendala:
2𝑦1 + 2𝑦2 ≤ 16
3𝑦1 + 5𝑦2 ≤ 30
2𝑦1 + 3𝑦2 ≤ 36
𝑦1 , 𝑦2 ≥ 0

C. Sifat-sifat Primal Dual yang Penting

Sifat-sifat primal dua penting untuk dipahami terutama pada saat kita
membicarakan masalah analisis sensitivitas. Dengan menggunakan sifat-sifat ini
kita dapat menentukan nilai variabel-variabel tertentu dengan cara yang sangat
efisien. Ada empat sifat yang perlu diketahui, yaitu:
1. Menentukan koefisien fungsi tujuan variabel-variabel basis awal.
Pada setiap iterasi solusi simpleks, baik primal maupun dual, koefisien fungsi
tujuan variabel-variabel basis awalnya dapat dicari dengan cara:
a. Mengalikan fungsi tujuan yang original dari variabel-variabel basis pada
iterasi yang bersangkutan dengan matriks di bawah variabel basis awal
pada iterasi yang bersangkutan. Koefisien ini biasa disebut simplex
multiplier.

b. Kurangi nilai-nilai simplex multiplier ini dengan fungsi tujuan yang

original dari variabel-variabel basis awal.
2. Menentukan koefisien fungsi tujuan variabel-variabel nonbasis awal.
Pada setiap iterasi dari persoalan primal, koefisien fungsi tujuannya dapat
ditentukan dengan menyubstitusikan simplex multiplier pada variabel-variabel

66
 Program linear
pembatas dari dual, kemudian mencari selisih antara ruas kiri dan ruas kanan dari
pembatas dual tersebut.
3. Menentukan nilai ruas kanan (solusi) dari variabel-variabel basis.
Pada setiap iterasi, baik primal maupun dual, nilai ruas kanan (kolom solusi)
variabel-variabel basis pada iterasi yang bersangkutan dapat ditentukan dengan
cara sebagai berikut:

4. Menentukan koefisien pembatas.

Pada setiap iterasi, baik primal maupun dual, koefisien pembatas dari setiap
variabel dapat ditentukan dengan cara sebagai berikut:

Contoh:

Salah satu iterasi dari persoalan di atas adalah sebagai berikut:

Tentukanlah harga-harga a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, dan t

dengan menggunakan sifat-sifat primal dual.

67
 Program linear
Penyelesaian:
1. Sifat 1:

2. Sifat 2:

3. Sifat 3:

4. Sifat 4:

68
 Program linear

Dengan demikian, t dapat dicari dengan memasukkan harga-harga g, h dan i

ke dalam persamaan z, sehingga diperoleh:

69
 Program linear

Ringkasan
Program linear adalah teknik matematika yang dirancang
untuk membantu manager dalam merencanakan dan
membuat keputusan dalam mengalokasikan sumber daya
yang terbatas untuk mencapai tujuan perusahaan.
Syarat-syarat perumusan suatu masalah ke dalam bentuk
model program linear: (1) Tujuan masalah harus jelas, (2)
Harus ada sesuatu atau beberapa alternatif yang ingin
dibandingkan, (3) Adanya sumber daya yang terbatas, (4)
Bisa dilakukan perumusan kuantitatif, (5) Adanya
keterkaitan peubah (variabel).

70
 Program linear

Latihan
1. Tentukan dual dari persoalan berikut:
Maksimumkan:
Berdasarkan:

Kemudian selesaikan soal ini dan tunjukkan marginal value

dari bahan baku pada konstraint pertama dan kedua.
2. Tentukan dual dari persoalan berikut:
Minimumkan:
Berdasarkan:

Kemudian selesaikan dualnya dengan metode Simplex dan

tunjukkan marginal value dari konstraint pertama dan kedua.
3. Perusahaan Ikhwan Mandiri memproduksi jaket dan tas kulit.
Satu jaket memerlukan 8 meter persegi kulit dan satu tas hanya
menggunakan 3 meter persegi. Persyaratan kerja untuk kedua
produk tersebut masing-masing adalah 12 jam dan 4 jam. Harga
pembelian kulit adalah $8 per meter persegi dan biaya tenaga
kerja diperkirakan sebesar $15 per jam. Persediaan kulit
mingguan saat ini dan tenaga kerja dibatasi sampai 1200 meter
persegi dan 1800 jam. Perusahaan menjual jaket dan tas
masing-masing dengan harga $350 dan $ 120. Tujuannya
adalah untuk menentukan jadwal produksi yang
memaksimumkan pendapatan bersih.

71
 Program linear

Perusahaan sedang mempertimbangkan untuk mmeperluas

produksinya. Berapa harga pembelian maksimum yang harus
dibayar perusahaan untuk kulit ? Untuk tenaga kerja ?

72
 Program linear

DAFTAR PUSTAKA

Aminuddin. 2005. Prinsip-prinsip Riset Operasi. Jakarta: Erlangga.

Anton, Howar. 1984. Aljabar Linear Elementer. Jakarta: Erlangga

Arhami Muhammad. 2005. Pemrograman Matlab. Yogyakarta: Andi Offset.

Munir Rinaldi. 2009. Matematika Diskrit. Bandung: Informatika Bandung.

Soemartojo, Tapilouw Marthen. 1995. Materi Pokok Program Linear.

Jakarta: Depdikbud Dirjend Pendidikan Dasar dan Menengah.

Supranto J. 1974. Pengantar Matriks. Jakarta: Lembaga Penerbit FE UI.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

73
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang sejarah
program linear, keterampilan belajar secara mandiri
dalam mempelajari masalah-masalah pemrograman
linear dari kehidupan sehari-hari, dengan
menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan
dapat:
- Memahami metode simpleks untuk memecahkan
masalah program linear maksimasi

(Apa yang telah Kami ceritakan itu), itulah yang benar, yang datang dari Tuhanmu,
karena itu janganlah kamu termasuk orang-orang yang ragu-ragu. (QS. 3. Al-Imran :60)

74
 Program linear
LINEAR PROGRAMMING : METODE SIMPLEKS
PERMASALAHAN MAKSIMASI

A. Langkah-langkah Metode Simpleks

1. Pilih salah satu penyelesaian layak basis (plb)
2. Uji apah plb tersebut berupa penyelesaian optimum (po)
Bila sudah optimum, sudah selesai, bila dilanjutkan ke langkah ke-3
3. Pilih plb baru yang lebih “baik” atau lebih “maju” (lebih dekat ke po)
dibandingkan plb yang lalu. (Dalam hal ini diperlukan petunjuk untuk
menentukan peubah mana yang masuk basis dan mana yang keluar agar
peubah basis (pb) yang baru tetap layak dan plb baru ini lebih maju
dibanding plb sebelumnya).

PLB1

optimal
Belum optimal

PLB2

optimal
Belum optimal

PLB3

optimal
Belum optimal

Kembali ke langkah-2 dst., sampai akhirnya ditemukan plb yang berupa po

sebelumnya.
Kembali ke langkah-2 dst., sampai akhirnya ditemukan plb yang berupa
po.
Guna mewadahi data-data soal dan mempermudah operasi langkah-
langkah di atas di susun tabel disebut tabel simpleks 2.1 sbb.

75
 Program linear
tabel simpleks 2.1
cj c1 c2 . . . cn
𝑐̅i 𝑥̅ i x1 x2 . . . xn bi Ri
xj
𝑐̅1 𝑥̅ 1 a11 a12 . . . a1n b1 R1
𝑐̅2 𝑥̅ 2 a21 a22 . . . a2n b2 R2
. . . . . . .
. . . . . . .
. . . . . . .
𝑐̅n 𝑥̅ m am1 am2 . . . amn bm Rm
zj Z
zj - cj z1 – c1 z2 – c2 . . . zn - Z
cn
Keterangan:

xj : peubah- peubah lengkap

aij : koefisien teknis

bi : suku tetap (tak negatif)

cj : koefisien ongkos (fungsi tujuan)

𝑥̅ i : peubah yang menjadi basis dalam tablo yang ditinjau

𝑐̅i : koefisien ongkos milik peubah basis 𝑥̅ i

zj : ∑𝑚
𝑖=1 𝑐̅𝑖 aij (hasil kali dari 𝑐̅𝑖 dengan kolom aij

z : ∑𝑚
𝑖=1 𝑐̅𝑖 bi (hasil kali dari 𝑐̅𝑖 dengan kolom bi

zj-cj : selisih zj dengan cj

apabila tablo bersangkutan belum optimum dan xk terpilih sebagai basis baru
maka disusun kolom Ri ysng diperoleh dengan

𝑏
𝑅𝑖 = 𝑎 𝑖 , 𝑎𝑖𝑘 > 0
𝑖𝑘

Dengan wadah berupa tablo di atas dan mengingat langkah-langkah simpleks

sebelumnya maka dituntut bahwa suatu tablo memuat suatu plb. Jadi matriks aij
sudah tersusut Gauss-Jordan dan 𝑏𝑖 ≥ 0 untuk semua i.

Langkah-langkah menjadi:

76
 Program linear
1. Menyusun tablo awal dengan matriks 𝑎𝑖𝑘 tersusut Gauss-Jordan dan 𝑏𝑖 ≥
0.
2. Menguji keoptimuman tablo (maksudnya, keoptimuman plb dalam tablo).
Bila sudah optimum berarti selesai. Bila belum optimum, langsung ke
langkah (3)
3. Memperbaiki tablo, artinya memilih peubah baru yang masuk menjadi
basis dan memilih peubah basis lama yang harus keluar (diganti)

B. Pola Maksimum Baku

Contoh:

Seorang pengusaha mebel memproduksi lemari dan meja dengan bahan-bahan

mentah besi, kayu dan paku. Kebutuhan bahan per unit produksi dan batas
maksimum persediaan bahan untuk satu masa produksi dan besar laba dari
penjualan per unitnya tertera dalam tebel berikut.

satu unit persediaan

bahan satuan
lemari meja maksimum
besi 1 2 36 batang
kayu 5 4 90 ribuan
paku 3 1 45 ons
laba 40 50 ribu rupiah
Bagaimana program produksi (berapa unit lemari dan mejasebaiknya diproduksi)
supaya batas-batas persediaan tidak dilanggar tetapi memberikan laba total
maksimum?

Penyelesaian:

Misalkan

x : banyaknya unit lemari yang diproduksi

y : banyaknya unit meja yang diproduksi

masalah di atas dapat dirumuskan menjadi

𝑥 + 2𝑦 ≤ 36

5𝑥 + 4𝑦 ≤ 90

77
 Program linear
3𝑥 + 𝑦 ≤ 45

𝑥, 𝑦 ≥ 30

Memaksimumkan 𝑓 = 40𝑥 + 50𝑦

Dengan menyisipkan peubah-peubah sisipan (slack variabel) r, s, t akan timbul

bentuk kanonik:

Mencari x,y,r,s,t yang memenuhi

𝑥 + 2𝑦 + 𝑟 = 36

5𝑥 + 4𝑦 + 𝑠 = 90

3𝑥 + 𝑦 + 𝑡 = 45
𝑥, 𝑦, 𝑟, 𝑠, 𝑡 tak negatif
Dan memaksimumkan 𝑓 = 40𝑥 + 50𝑦 + 0𝑟 + 0𝑠 + 0𝑡

Tabel simpleks 2.2

cj 40 50 0 0 0
𝑐̅i 𝑥̅ i xj x y r s t bi Ri
0 r 1 2 1 0 0 36 18
0 s 5 4 0 1 0 90 45/2 I
0 t 3 1 0 0 1 45 45
zj 0 0 0 0 0 0
zj - cj -40 -50 0 0 0 0
50 y ½ 1 ½ 0 0 18 36
0 s 3 0 -2 1 0 18 36/2 II
0 t 5/2 0 -½ 0 1 27 54/5
zj 25 50 25 0 0 900
zj - cj -15 0 25 0 0 900
50 y 0 1 5/6 -1/6 0 15
40 x 1 0 2/3 1/3 0 6
III
0 t 0 0 7/3 -5/6 1 12
zj 40 50 15 5 0 990
zj - cj 0 0 15 5 0 990
≥0

78
 Program linear
Pada tabel simpleks 2.2 di atas pada kolom III ternyata sudah optimum dengan
penyelesaian optimum soal bentuk kanonik: (𝑥, 𝑦, 𝑟, 𝑠, 𝑡) = (6,15,0,0,12), maka
penyelesaian optimum soal asli adalah (𝑥, 𝑦) = (6,15) dengan nilai program 990.
Penafsiran kembali ke masalah nyata akan berbunyi, sebaiknya diproduksi 6 unit
almari dan 15 unit meja sehingga laba total maksimum dengan nilai 990 ribu
rupiah.

Contoh soal di atas merupakan contoh yang berpola maksimum baku, sehingga
dengan menambahkan peubah-peubah tambahan soal sudah siap dimasukkan
dalam tabel simpleks. Contoh berikut berpola maksimum tidak baku.
Contoh 2:
Menentukan 𝑥, 𝑦, 𝑧 tak negatif yang memenuhi
𝑥 + 𝑦 + 2𝑧 ≤ 12
2𝑥 − 6𝑦 − 𝑧 ≥ 4 dan
Memaksimumkan: 𝑓 = −8𝑥 + 6𝑦 + 8𝑧
Dengan menyelipkan 2 peubah tambahan 𝑠1 dan 𝑠2 sehingga diperoleh bentuk
kanonik:
Mencari 𝑥, 𝑦, 𝑧, 𝑠1 , 𝑠2
𝑥 + 𝑦 + 2𝑧 + 𝑠1 = 12
2𝑥 − 6𝑦 − 𝑧 − 𝑠2 = 4
𝑥, 𝑦, 𝑧, 𝑠1 , 𝑠2 tidak negatif
Dan memaksimumkan: 𝑓 = −8𝑥 + 6𝑦 + 8𝑧 + 0𝑠1 + 0𝑠2
Bentuk ini tersusut bagi 𝑠1 dan 𝑠2 tetapi penyelesaian basis yang bersesuaian
menjadi
(𝑥, 𝑦, 𝑧, 𝑠1 , 𝑠2) = (0,0,0,12, −4)
Jadi tidak layak karena memuat nilai negatif untuk 𝑠2.
Supaya tabel awal sudah memuat penyelesaian basis yang layak maka
pada penyelesaian kedua disispkan lagi satu peubah a sehingga kendala utama
berbunyi:
𝑥 + 𝑦 + 2𝑧 + 𝑠1 = 12
2𝑥 − 6𝑦 − 𝑧 − 𝑠2 + 𝑎 = 4 𝑑𝑒𝑛𝑔𝑎𝑛 𝑎 ≥ 0

79
 Program linear
Sehingga susunan ini sudah memuat suatu plb ialah (𝑥, 𝑦, 𝑧, 𝑠1 , 𝑠2, 𝑎) =
(0,0,0,12,0,4) , dengan 𝑠1 sebagai basis ke-i dan a sebagai basis ke-2.
Sebelum a disisipkan kendala ke-2 harus sudah dalam bentuk persamaan. Sebagai
akibat, timbul syarat perlu supaya soal asli mempunyai penyelesaian optimum,
bahwa

Dalam tabel optimum, peubah semu a harus bernilai 0

Ini berarti bahwa masuknya a kedalam susunan hanya sebagai katalisator

supaya algoritma simpleks dapat berjalan. Sebagai usaha supaya a segera bernilai
0 maka disusunlah fungsi sasaran baru dengan bentuk
𝑓 ̅ = 𝑓 − 𝑀𝑎 dengan M bilangan positif yang cukup besar.
Jadi untuk contoh di atas.
𝑓 ̅ = −8𝑥 + 6𝑦 + 8𝑧 + 0𝑠1 + 0𝑠2 − 𝑀𝑎
Dengan demikian diharapkan bahwa a segera keluar dari basis karena koefisien
ongkosnya adalah negatif besar.
Sekarang soal sudah siap dimasukkan kedalam tabel simpleks 2.3
tabel simpleks 2.3
cj -8 6 8 0 0 -M
𝑐̅i 𝑥̅ i x y z 𝑠1 𝑠2 a bi Ri
xj
0 𝑠1 1 1 2 1 0 0 12 12
-M a 2 -6 -1 0 -1 1 4 2
zj -2M 6M M 0 M -M -
4M
zj - - 6M-M M-8 0 M 0 -
cj 2M+8 4M
0 𝑠1 0 4 5/2 1 ½ -1/2 10 4
-8 x 1 -3 -1/2 0 -1/2 1/2 2 -
zj -8 24 4 0 4 -4 -16
zj - 0 18 -4 0 4 M-4 -16
cj
8 Z 0 8/5 1 2/5 1/5 -1/5 4
-8 x 1 -11/5 0 1/5 -2/5 2/5 4
zj -8 152/5 8 8/5 24/5 -24/5 0
zj - 0 122/5 0 8/5 24/5 M-
cj 24/5
≥0

80
 Program linear
Soal sudah optimum dengan 3 tabel. Dengan peralihan dari tabel I dan II
ternyata a sudah keluar dari basis dan tidak masuk kembali. Ini yang diharapkan,
̅
sehingga dalam tabel optimum a bernilai nol, berarti 𝑓𝑚𝑎𝑘𝑠 = 𝑓𝑚𝑎𝑘𝑠 karena bila a
= 0 maka 𝑓 ̅ = 𝑓. Penyelesaian optimum soal asli berbunyi
(𝑥, 𝑦, 𝑧) = (4,0,4)

Dengan nilai program 𝑓𝑚𝑎𝑘𝑠 = 0.

81
 Program linear

Ringkasan
Metode Simpleks adalah salah metode alternatif
penyelesaian masalah program linear jika jumlah variabel
keputusan mengandung tiga atau lebih variabel keputusan.
Gagasan metode simpleks adalah menerjemahkan definisi
geometris atau grafik dari titik ekstrim atau titik sudut
menjadi definisi aljabar.

82
 Program linear

Latihan
1. Tentukan 𝑢, 𝑣, 𝑤 tak negatif yang memenuhi
2𝑢 + 3𝑣 − 5𝑤 ≤ 15
2𝑢 − 𝑣 + 3𝑤 ≤ 3
3𝑢 + 𝑣 − 2𝑤 ≤ 2

Dan maksimumkan: 𝑓 = 9𝑢 + 2𝑣 + 5𝑤

2. Tentukan 𝑥1 , 𝑥2 , 𝑥3 tak negatif yang memenuhi

3𝑥1 + 6𝑥2 + 𝑥3 ≤ 6
4𝑥1 + 2𝑥2 + 𝑥3 ≤ 6
6𝑥1 − 3𝑥2 + 3𝑥3 = 10

Dan maksimumkan: 𝑓 = 2𝑥1 − 3𝑥2 + 𝑥3

3. Tentukan 𝑥, 𝑦, 𝑧 tak negatif yang memenuhi

2𝑦 − 𝑧 ≤ −2
𝑥 + 4𝑦 + 2𝑧 = 5
Dan maksimumkan: 𝑓 = 3𝑥 + 5𝑦 + 2𝑧
4. Tentukan 𝑥1 , 𝑥2 , 𝑥3 tak negatif yang memenuhi
3𝑥1 + 10𝑥2 + 5𝑥3 ≤ 15
𝑥1 + 2𝑥2 + 𝑥3 ≥ 4
33𝑥1 − 10𝑥2 + 9𝑥3 ≤ 23
Dan maksimumkan: 𝑓 = 2𝑥1 + 3𝑥2 + 5𝑥3
5. Tentukan 𝑥, 𝑦, 𝑧 tak negatif yang memenuhi
𝑥 + 𝑦 ≥ 20
𝑦 + 𝑧 ≤ 18
3𝑥 + 2𝑦 + 5𝑧 ≤ 120
Dan maksimumkan: 𝑓 = 𝑥 + 𝑦 + 𝑧
6. Tentukan 𝑥, 𝑦 tak negatif yang memenuhi
𝑥+𝑦 ≥7
2𝑥 + 𝑦 ≥ 8
2𝑥 − 𝑦 ≥ 6
𝑥 − 3𝑦 ≤ 0
−2𝑥 + 6𝑦 ≤ 25

83
 Program linear

Dan maksimumkan: 𝑓 = 40 − 5𝑥 + 20𝑦

7. Tentukan 𝑥1 , 𝑥2 , 𝑥3 tak negatif yang memenuhi
𝑥1 + 2𝑥2 + 𝑥3 ≥ 4
3𝑥1 + 10𝑥2 + 5𝑥3 = 15
33𝑥1 − 10𝑥2 − 9𝑥3 ≤ 23
Dan maksimumkan: 𝑓 = 2𝑥1 + 3𝑥2 + 5𝑥3
8. Tentukan 𝑥, 𝑦, 𝑧 tak negatif yang memenuhi
𝑥 + 𝑦 + 3𝑧 ≤ 12
5𝑥 − 2𝑦 ≥ 0
𝑥+𝑧 =6
Dan maksimumkan: 𝑓 = 3𝑥 + 𝑦 + 5𝑧
:

84
 Program linear

DAFTAR PUSTAKA

Aminuddin. 2005. Prinsip-prinsip Riset Operasi. Jakarta: Erlangga.

Anton, Howar. 1984. Aljabar Linear Elementer. Jakarta: Erlangga

Arhami Muhammad. 2005. Pemrograman Matlab. Yogyakarta: Andi Offset.

Munir Rinaldi. 2009. Matematika Diskrit. Bandung: Informatika Bandung.

Soemartojo, Tapilouw Marthen. 1995. Materi Pokok Program Linear.

Jakarta: Depdikbud Dirjend Pendidikan Dasar dan Menengah.

Supranto J. 1974. Pengantar Matriks. Jakarta: Lembaga Penerbit FE UI.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

85
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang sejarah
program linear, keterampilan belajar secara mandiri
dalam mempelajari masalah-masalah pemrograman
linear dari kehidupan sehari-hari, dengan
menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan
dapat:
- Memahami metode simpleks untuk memecahkan
masalah program linear minimisasi

(Apa yang telah Kami ceritakan itu), itulah yang benar, yang datang dari Tuhanmu,
karena itu janganlah kamu termasuk orang-orang yang ragu-ragu. (QS. 3. Al-Imran :60)

86
 Program linear
LINEAR PROGRAMMING : METODE SIMPLEKS
PERMASALAHAN MINIMISASI
A. Pendahuluan
Hingga saat ini yang telah kita pelajari adalah penyelesaian permasalahan
linear programming dengan tanda pertidaksamaan ≤ yang biasanya kita jumpai
dalam permasalahan dengan fungsi tujuan maksimisasi. Prosedur dalam
penyelesaian permasalahan maksimisasi dapat juga kita gunakan untuk
menyelesaikan permasalahan minimisasi yang biasanya mempunyai tanda dan
atau = pada fungsi kendalanya.

Pada bab 7 ini akan kita bahas penyelesaian permasalahan LP dengan

fungsi tujuan minimisasi. Pembahasan akan dimulai dengan memformulasikan
permasalahan sesuai dengan standard simpleks, kemudian dilanjutkan dengan
melakukan iterasi atau perbaikan tabel hingga optimal dan bagian terakhir pada
bab ini akan dikemukakan beberapa issue teknis yang sering kita jumpai dalam
metode simpleks. Setelah mempelajari modul ini diharapkan anda dapat:

1. Memformulasikan permasalahan sesuai standard simpleks untuk fungsi

kendala dengan tanda ≥ dan atau = .
2. Menyelesaikan permasalahan linear programming dengan iterasi simpleks
untuk fungsi tujuan minimisasi.
3. Menginterpretasikan tabel optimal simpleks
4. Memahami adanya kasus khusus di dalam metode simpleks.

Formulasi Permasalahan LP sesuai dengan Standard

Simpleks :Kasus Minimisasi

B. Formulasi Permasalahan Menurut Metode Simpleks Untuk Tanda

Pertidaksamaan ≥ Dan =
Pada topik ini akan kita bahas mengenai penyelesaian permasalahan LP
dengan fungsi tujuan minimisasi. Pada permasalahan minimisasi, biasanya kita
jumpai tanda ≥ pada fungsi kendala. Kendati demikian tidak menutup
kemungkinan fungsi kendala mempunyai tanda =.

87
 Program linear
Dalam menyelesaikan permasalahan LP dengan metode simpleks,
langkah pertama yang harus kita lakukan adalah menyesuaikan formulasi
permasalahan dengan standard simpleks. Dengan kata lain kita harus merubah
tanda pertidaksamaan menjadi persamaan.

Pada fungsi kendala dengan tanda ≤ kita harus menambahkan slack

variabel yang menyatakan kapasitas yang tidak digunakan atau yang tersisa pada
departemen tersebut. Hal ini karena ada kemungkinan kapasitas yang tersedia
tidak semuanya digunakan dalam proses produksi. Pada permasalahan minimisasi
kita jumpai fungsi kendala dengan tanda ≥, artinya bahwa kita dapat
menggunakan sumberdaya lebih dari yang tersedia. Pertanyaan yang muncul
adalah berapa besarnya kelebihan sumberdaya yang telah kita gunakan dari yang
tersedia ?. Untuk menyatakan kelebihan sumberdaya yang digunakan dari yang
tersedia ini, maka kita harus mengurangi kendala tersebut dengan surplus variabel.
Surplus variabel ini sering juga disebut sebagai slack variabel yang negatif.

Karena nilai solusi pada permasalahan program linear harus non-negatif

maka untuk mengatasi masalah ini kita harus menambahkan artificial variabel
(A). Artificial variabel ini secara phisik tidak mempunyai arti, dan hanya
digunakan untuk kepentingan perhitungan saja.

Untuk lebih memahami permasalahan ini marilah kita lihat permasalahan

Galuh Chemical Company. Galuh Chemical Company harus membuat 1000 unit
campuran phospate dan postassium. Biaya per unit phospate adalah $5, sedangkan
biaya per unit postassium $6. Jumlah phospate yang dapat digunakan tidak lebih
dari 300 unit sedangkan postassium harus digunakan minimal 150 unit. Berapa
masing-masing jumlah phospate dan postassium yang harus digunakan agar biaya
total minimum ?

Permasalahan Galuh Chemical Company dapat kita formulasikan ke

dalam bentuk LP sebagai berikut :

Fungsi Tujuan :

88
 Program linear
Minimisasikan Cost Z = 5X1 + 6X2

Fungsi kendala :

X1 + X2 = 1000

X1 ≤ 300

X2 ≥ 150

X1, X2 ≥ 0

Dimana X1 = jumlah phospate dalam unit

X2 = jumlah postassium dalam unit

Untuk menyelesaikan permasalahan tersebut dengan metode simpleks kita

harus memformulasikan kembali permasalahan tersebut sesuai dengan standard
simpleks. Formulasi sesuai standard simpleks artinya kita harus merubah tanda
pertidaksamaan (≤ maupun ≥) menjadi persamaan. Untuk kendala dengan tanda =
kita hanya menambahkan artificial variabel saja. Sehingga kendala yang pertama
akan menjadi :

X1 + X2 + A1 = 1000

Kendala kedua, X1 ≤ 300 , kita tambahkan slack variabel sehingga menjadi :

X1 + S1 = 300

Sedangkan kendala ketiga, X2 ≥ 150, harus dikurangi dengan surplus variabel dan
ditambah dengan artificial variabel, sehingga menjadi :

X2 – S2 + A2 = 150

Terakhir kita harus menuliskan fungsi tujuan. Karena dalam fungsi kendala ada
artificial variabel, maka kita harus memberikan koefisien +M untuk artificial
variable tersebut di fungsi tujuan. Koefisien +M ini menunjukkan angka yang
sangat besar nilainya, sehingga dalam kasus ini dapat diinterpretasikan biaya yang

89
 Program linear
sangat tinggi. Fungsi tujuan dalam permasalahan Galuh Chemical Company akan
menjadi :

Minimisasikan biaya Z = 5X1 + 6X2 + 0S1 + 0S2 + MA1 + MA2

Formulasi sesuai standard simpleks dari permasalahan Galuh Chemical Company

secara lengkap adalah :

Fungsi Tujuan :

Minimisasikan biaya Z = 5X1 + 6X2 + 0S1 + 0S2 + MA1 + MA2

Fungsi kendala :

X1 + X2 + A1 = 1000

X1 + S1 = 300

X2 – S2 + A2 = 150

X1, X2, S1, S2, A1, A2 ≥ 0

Apabila pada fungsi kendala terdapat artificial variabel, sedangkan fungsi

tujuannya maksimisasi, maka koefisien artificial variabel pada fungsi tujuan
adalah –M.

C. Membuat Tabel Awal Simplek

Seperti halnya yang telah kita pelajari pada bab 2, langkah selanjutnya
untuk menyelsesaikan permasalahan LP dengan metode simpleks adalah membuat
tabel awal. Pada dasarnya untuk membuat tabel awal pada permasalahan
minimisasi sama dengan permasalahan maksimisasi yang telah kita bahas pada
bab 2. Hanya saja karena pada permasalahan Galuh Chemical Company kita
mengenal variabel lain selain slack variabel yaitu surplus variabel dan artificial
variabel, maka variabel yang boleh masuk ke kolom product mix pada tabel awal
ini hanyalah slack variabel dan artificial variabel. Tabel awal permasalahan Galuh
Chemical Company dapat dilihat pada Tabel 7.1.

90
 Program linear
Tabel 7.1. Tabel Awal kasus Galuh Chemical Company

Angka pada baris Cj (5, 6, 0, 0, +M, +M) tersebut adalah koefisien pada
fungsi tujuan. Sedangkan angka (1, 1, 0, 0, 1, 0) pada baris A1 serta angka (1, 0,
1, 0 0, 0) pada baris S1 dan angka (0, 1, 0, -1, 0, 1) pada baris A2 adalah koefisien
pada kendala 1, 2 dan 3. Angka pada baris Zj (+M, 2M, 0, -M , +M, +M )
diperoleh dari penjumlahan hasil kali kolom Cj dengan kolom yang bersesuaian.
Sebagai contoh kita akan menentukan nilai Zj kolom X1 = (M x 1) + (0 x 1) + (M
x 0) = M. Dengan cara yang sama kita peroleh nilai Zj pada kolom yang lain.
Angka pada baris Cj – Zj diperoleh dari angka pada baris Cj dikurangi dengan
angka pada baris Zj. Sebagai contoh kita akan menghitung nilai Cj – Zj pada
kolom X1 = 5 (yaitu angka pada baris Cj) – M (angka pada baris Zj) = 5 - M .
Demikian juga untuk menghitung nilai Cj – Zj untuk kolom-kolom yang lain
digunakan cara yang sama.

91
 Program linear

Ringkasan
Dalam formulasi permasalahan LP sesuai standard simpleks
untuk fungsi kendala dengan tanda ≥ harus dikurangi
dengan surplus variable dan ditambah dengan artificial
variable. Sedangkan untuk fungsi kendala dengan tanda =
hanya ditambah ariticial variable.
Pada fungsi kendala terdapat artificial variable, maka pada
fungsi tujuan harus ditambahkan koefisien -M untuk
permasalahan maksimisasi serta koefisien +M untuk
permasalahan minimisasi.

92
 Program linear

Latihan
1. Tentukan 𝑢, 𝑣, 𝑤 tak negatif yang memenuhi
2𝑢 + 3𝑣 − 5𝑤 ≤ 15
2𝑢 − 𝑣 + 3𝑤 ≤ 3
3𝑢 + 𝑣 − 2𝑤 ≤ 2
5𝑥 − 2𝑦 ≥ 0
𝑥+𝑧 =6
Dan maksimumkan: 𝑓 = 3𝑥 + 𝑦 + 5𝑧
Untuk memperdalam pemahaman Anda mengenai materi di
atas, silakan anda mengerjakan latihan berikut ini !
2. Apakah yang dimaksud dengan surplus variabel ?
3. Bagimanakah formulasi yang sesuai dengan standard simpleks
untuk fungsi kendala dengan tanda ≥ .
4. Variabel apa sajakah yang boleh masuk ke dalam kolom
product mix pada tabel awal simpleks?
5. Jika pada fungsi kendala terdapat artificial variable,
bagaimanakah dampaknya pada fungsi tujuan minimisasi?
6. Tentukan 𝑢, 𝑣, 𝑤 tak negatif yang memenuhi
𝑢 + 2𝑣 + 5𝑤 ≥ 4
2𝑢 − 𝑣 + 2𝑤 ≥ 3
3𝑢 + 5𝑣 + 𝑤 ≥ 1
Dan minimumkan: 𝑓 = 2𝑢 + 6𝑣 + 7𝑤
7. Tentukan 𝐴, 𝐵, 𝐶 tak negatif yang memenuhi
10𝐴 − 5𝐵 + 𝐶 ≤ 2
−15𝐴 + 10𝐵 + 𝐶 ≥ 1
Dan minimumkan: 𝑓 = −150𝐴 + 50𝐵

93
 Program linear
DAFTAR PUTAKA

Dimyati, Tjutju Tarliah dan Ahmad Dimyati. Operations Research: Model-

model Pengambilan Keputusan. Sinar Baru Algensindo, Bandung. 2003.
Jay Heizer and Barry. Operations Management (10th edition). New York,
NY: Prentice Hall. Moon, Y. 2004.
Siringoringo, Hotniar. Seri Teknik Riset Operasional. Pemrograman Linear.
Penerbit Graha Ilmu. Yogyakarta. 2005.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

94
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang sejarah
program linear, keterampilan belajar secara mandiri
dalam mempelajari masalah-masalah pemrograman
linear dari kehidupan sehari-hari, dengan
menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan
dapat:
- Menginterpretasikan shadow price pada tabel
simpleks
- Memahami dampak perubahan sisi kanan fungsi
kendala baik secara parsial maupun simultan
terhadap solusi optimal.
- Menentukan besarnya rentang perubahan sisi
kanan fungsi kendala

95
 Program linear
ANALISIS SENSITIVITAS:
PERUBAHAN SISI KANAN FUNGSI KENDALA

A. Pendahuluan
Analisis sensitivitas akan membahas bagaimana pengaruh perubahan
sumber daya (sisi kanan fungsi kendala) atau koefisien fungsi tujuan terhadap
nilai solusi optimal. Pada bab 8 ini akan dibahas mengenai analisis sensitivitas
yang berkaitan dengan perubahan sisi kanan fungsi kendala, sedangkan analisis
sensitivitas yang berkaitan dengan perubahan koefien fungsi tujuan akan dibahas
di bab 9.

Pembahasan pada bab 8 ini akan dibagi dua, yaitu: pada bagian pertama
akan dijelaskan mengenai shadow price, dampak perubahan sisi kanan fungsi
kendala secara parsial terhadap solusi optimal serta dampak perubahan sisi kanan
fungsi kendala secara simultan terhadap solusi optimal. Pada bagian kedua
rentang peruabahan sisi kanan fungsi kendala agar solusi masih tetap optimal.

Analisis Sensitivitas: Shadow Price dan Dampak Perubahan Secara Parsial

Sisi Kanan Fungsi Kendala pada Solusi Optimal

B. Shadow Price
Shadow price menyatakan berapa besarnya fungsi tujuan akan berubah
jika sisi kanan fungsi kendala ditambah satu unit. Secara umum, shadow price
untuk setiap kendala dapat dinyatakan sebagai berikut.

Shadow price ini dapat kita lihat pada tabel optimal simpleks kolom slack
variable baris Cj – Zj. Untuk lebih memahami konsep ini perhatikan kasus
Ikhwan Furniture berikut ini.

Ikhwan Furniture menghasilkan 3 jenis produk yaitu Meja (T), kursi (C)
serta Rak Buku (B) yang masing-masing produk diproses di tiga bagian yaitu
bagian assembly, finishing serta bagian packing. Untuk menghasilkan 1 unit meja

96
 Program linear
dibutuhkan waktu 3 jam di bagian assembly, 2 jam di bagian finishing dan 1 jam
di bagian packing. Untuk menghasilkan 1 unit kursi dibutuhkan waktu 4 jam di
bagian assembly, 1 jam dibagian finishing serta 3 jam di bagian packing.
Sedangkan untuk menghasilkan 1 unit rak buku dibutuhkan waktu masing-masing
2 jam di bagian assembly, finishing dan packing. Keuntungan per unit meja
adalah $2, kursi $4 sedangkan rak buku $3. Permasalahan Ikhwan Furniture
tersebut jika diformulasikan dalam bentuk program linear adalah sebagai berikut:

Fungsi Tujuan Max Z = 2T + 4C + 3B

Fungsi Kendala : 3T + 4C + 2B ≤ 60 kendala bagian assembly

2T + 1C + 2B ≤ 40 kendala bagian finishing

1T + 3C + 2B ≤ 80 kendala bagian packing

T, C, B ≥ 0

Tabel optimal dari kasus Ikhwan Furniture jika diselesaikan dengan menggunakan
simpleks dapat dilihat pada tabel 8.1 berikut ini.

Tabel 8. 1 Tabel Optimal Ikhwan Furniture

Solusi optimal tercapai bila diproduksi 6 2/3 kursi (C), 16 2/3 rak buku
(B), dan tidak memproduksi meja (T). Keuntungan yang diperoleh setiap
minggunya adalah $76,67 (atau $76 2/3) . Perlu dicatat bahwa shadow price
tersebut tampak pada baris Cj

97
 Program linear
– Zj kolom slack variable. Shadow price untuk assembly adalah – 5/6, shadow
price untuk finishing adalah – 2/3, dan shadow price untuk packing adalah 0.

Pada kasus minimisasi (dual problem), variabel struktural A (bagian

assembly) sebesar 5/6 dan F (bagian finishing) sebesar 2/3. Sedangkan variabel
struktural P (bagian packing) adalah 0. Dengan demikian nilai shadow price pada
primal problem sama dengan nilai variabel struktural pada dual problem. (Dual
problem tidak dibicarakan pada modul ini. Namun demikian dapat dilihat pada
buku lain yang berkaitan dengan riset operasional).

Nilai shadow price untuk assembly sebesar – 5/6 bisa diartikan bahwa
setiap penambahan 1 jam kerja pada bagian assembly akan menambah
keuntungan sebesar $0,83 (atau $5/6). Nilai shadow price untuk finishing sebesar
– 2/3 bisa diartikan bahwa setiap penambahan 1 jam kerja pada bagian finishing
akan menambah keuntungan sebesar $0,67 ($2/3). Sedangkan nilai shadow price
pada bagian packing sebesar 0, berarti bahwa setiap penambahan 1 jam kerja pada
bagian packing tidak menambah keuntungan. Hal ini dikarenakan waktu di bagian
packing masih tersisa 26 2/3 jam (karena S3 yang merupakan slack variable
berada pada kolom product mix).

C. Dampak perubahan secara parsial sisi kanan fungsi Kendala terhadap

solusi optimal

Perubahan secara parsial sisi kanan fungsi kendala artinya kita

mengasumsikan hanya salah satu kendala saja yang berubah, sedangkan kapasitas
kendala yang lainnya dianggap konstan. Misalnya yang berubah hanya kapasitas
bagian assembly saja, sementara bagian finishing dan packing tetap, atau bagian
finishing saja yang berubah sementara bagian assembly dan packing tetap, atau
bagian packing saja yang berubah sementara bagian assembly dan finishing tetap.

Kapasitas sisi kanan fungsi kendala bisa saja berubah. Perubahan ini dapat
disebabkan oleh adanya karyawan yang lembur ataupun karena ada karyawan
yang sakit. Adanya karyawan yang lembur menyebabkan bertambahnya kapasitas
sisi kanan fungsi kendala, sedangkan adanya karyawan yang sakit akan

98
 Program linear
menyebabkan berkurangnya kapasitas sisi kanan fungsi kendala. Adanya
perubahan sisi kanan fungsi kendala, baik berupa penambahan jam kerja ataupun
pengurangan jam kerja tentu saja akan berdampak pada solusi optimal.
Pertanyaan yang sering muncul dalam permasalahan ini adalah bagaimana
dampak penambahan atau pengurangan kapasitas sisi kanan fungsi kendala
terhadap solusi optimal? Kita akan menjawab pertanyaan ini dengan
menggunakan “change Vector”. Change Vector adalah suatu angka yang
mengukur perubahan nilai optimal basic variable karena adanya penambahan satu
unit sisi kanan fungsi kendala. Change Vector ini dapat kita lihat pada baris basic
variable (variable yang berada pada kolom product mix) kolom slack variable.
Secara matematis change vector dapat dinyatakan sebagai berikut :

Untuk lebih memahami masalah ini akan kita bahas kembali kasus Ikhwan
Furniture pada bagian A bab 8 ini. Seandainya ada penambahan 1 jam kerja pada
bagian assembly. Bagaimana dampak penambahan 1 jam kerja pada bagian
assembly terhadap solusi optimal ? Untuk menjawab pertanyaan ini perhatikan
tabel 8.2 di bawah ini.

Tabel 8.2 Dampak Penambahan 1 jam kerja pada Bagian Assembly

terhadap Solusi Optimal

C, B dan S3 yang berada pada baris pertama tabel 8.2 adalah product mix,
sedangkan angka yang berada pada baris kedua adalah kuantitas untuk setiap
variabel keputusan, dan angka pada baris ketiga adalah perkalian antara besarnya
perubahan dengan setiap change vector S1 ( angka yang berada pada kolom S1).
Karena yang berubah bagian assembly , maka angka yang kita gunakan angka
pada kolom S1.

99
 Program linear
Dengan adanya penambahan satu jam kerja di bagian assembly, akan
menambah jumlah C yang diproduksi menjadi 7, B menjadi 16 1/2. dan total
keuntungan = (4 × 7) + (3 × 16 1/2) = 77,5 Perubahan keuntungan = 77.5 - 76.7 =
0.83 atau 5/6. Artinya dengan bertambahnya 1 jam kerja pada bagian assembly
akan menambah keuntungan sebesar $0,83. Angka ini sama dengan shadow price
pada bagian assembly.

Bagaimana jika pada bagian assembly ada karyawan yang tidak masuk
kerja ? Karyawan yang tidak masuk kerja berarti akan mengurangi kapasitas sisi
kanan fungsi kendala. Misalkan di bagian assembly ada karyawan yang tidak
masuk kerja, sehingga kapasitas pada bagian assembly berkurang 1 jam kerja.
Bagaimana dampak pengurangan jam kerja ini pada solusi optimal ? Untuk
menjawab pertanyaan ini perhatikan tabel 8.3 di bawah ini.

Tabel 8.3 Dampak Pengurangan 1 jam kerja pada Bagian Assembly

terhadap Solusi Optimal

Dengan adanya pengurangan sebesar 1 jam di bagian assembly

menyebabkan jumlah C yang diproduksi turun menjadi 6 1/3 unit, B naik menjadi
16 5/6 unit sedangkan kapasitas bagian packing naik menjadi 27 1/3 jam. Pada
tingkat produksi ini keuntungan yang diperoleh = (4 × 6 1/3) + (3 × 16 5/6) = 75
5/6 = 75,83. Perubahan keuntungan adalah = 75 5/6 – 76 2/3 = - 5/6 = -0,83.
Artinya jika jam kerja di bagian assembly berkurang 1 jam maka keuntungan akan
berkurang sebesar $0,83 .

Bagaimana jika perubahan sisi kanan fungsi kendala lebih dari 1 jam kerja.
Sebagai contoh berikut akan kita bahas jika ada penambahan jam kerja di bagian
assembly sebesar 10 jam. Bagaimana dampak perubahan ini terhadap solusi
optimalnya? Untuk menyawab pertanyaan ini, kita tinggal mengalikan besarnya

100
 Program linear
penambahan jam kerja bagian assembly dengan koefisien pada kolom S1.
perhitungannya dapat dilihat pada tabel 8.4 berikut ini.

Tabel 8.4 Dampak Penambahan 10 jam kerja pada Bagian Assembly

terhadap Solusi Optimal

Penambahan sebesar sepuluh jam kerja pada bagian assembly, akan

menambah jumlah C yang diproduksi menjadi 10, B menjadi 15. sehingga total
keuntungan = (4 x 10) + (3 x 15) = 85. Kenaikan keuntungan = 85 -76.7 = 8,3.
Jika kita perhatikan besarnya penambahan keuntungan sama dengan 10 kali
besarnya shadow price.

Analisis Sensitivitas: Dampak Perubahan Secara Simultan Serta Rentang

Perubahan Sisi Kanan Fungsi Kendala
D. Dampak perubahan secara simultan sisi kanan fungsi Kendala terhadap
solusi optimal

Pada topik 1 bagian B sudah dijelaskan dampak perubahan secara parsial

sisi kanan fungsi kendala terhadap solusi optimal. Pada kenyataannya perubahan
sisi kanan fungsi kendala seringkali berubah secara simultan. Adanya perubahan
dalam satu departemn diikuti oleh perubahan departemen lainnya dalam waktu
yang bersamaan. Bagaimana dampak perubahan secara simultan sisi kanan fungsi
kendala ini terhadap solusi optimal ?

Untuk menjawab pertanyaan di atas perhatikan kembali kasus Ikhwan

Furniture berikut ini. Sebagai contoh misalkan bagian assembly ditambah satu
jam kerja dan bagian finishing juga ditambah satu jam kerja. Dampak
penambahan 1 jam kerja pada dua bagian ini terhadap solusi optimal dapat dilihat
pada tabel 8.5.

101
 Program linear
Tabel 8.5 Dampak Penambahan Satu Jam Kerja pada Bagian Assembly dan
Finishing terhadap Solusi Optimal

Dengan adanya penambahan masing-masing satu jam kerja pada bagian

assembly dan finishing mengakibatkan jumlah C yang diproduksi menjadi 6 2/3,
B menjadi 17 1/6. Keuntungan yang diperoleh = (4 x 6 2/3) + (3 x 17 1/6) = 78
1/6. Sehingga perubahan keuntungan = 78 1/6 – 76 2/3 = 1 1/5 = 1,5. Besarnya
perubahan keuntungan ini sama dengan shadow price untuk bagian assembly
ditambah bagian finishing, yaitu 0,83 + 0,67 = 1,5.

Bagaimana dampak pengurangan masing-masing 1 jam kerja pada bagian

assembly dan bagian finishing terhadap solusi optimal ? Untuk menjelaskan hal
ini kita akan gunakan kembali contoh Ikhwan Furniture. Perhatikan tabel 8.6
berikut ini.

Tabel 8.6 Dampak Pengurangan Satu Jam Kerja pada Bagian Assembly dan
Finishing terhadap Solusi Optimal

Dari tabel 8.6 terlihat bahwa dengan adanya pengurangan masing-masing

1 jam kerja pada bagian assembly dan finishing akan menyebabkan jumlah C
(kursi) yang diproduksi tetap yaitu 6 2/3 unit sedangkan jumlah rak buku yang
diproduksi turun menjadi 16 1/6 unit, dan waktu yang tersisa di bagian packing
adalah 27 2/3 jam. Sedangkan keuntungan yang diperoleh pada tingkat produksi

102
 Program linear
tersebut adalah = (4 x 6 2/3) + (3 x 16 1/6) = 75 1/6. Sehingga perubahan
keuntungan = 75 1/6 – 76 2/3 = -1,5 . Besarnya penurunan keuntungan ini sama
dengan shadow price untuk bagian assembly ditambah bagian finishing, yaitu -
0,83 - 0,67 = -1,5.

Apa yang terjadi jika bagian assembly menaikkan jam kerja sebesar 10
jam, sedangkan bagian finishing jam kerjanya berkurang sebesar 5 jam.
Bagaimana dampak perubahan ini terhadap nilai optimal basic variabel serta nilai
optimal fungsi tujuan? Perhatikan tabel 8.7 berikut ini.

Tabel 8.7 Dampak Penambahan 10 Jam Kerja pada Bagian Assembly dan
Pengurangan sebesar 5 jam Kerja pada Bagian Finishing terhadap Solusi
Optimal

Untuk menghitung dampak penambahan 10 jam kerja pada bagian

assembly kita tinggal mengalikan change vector bagian assembly (kolom S1)
dengan besarnya perubahan yaitu 10, sedangkan untuk menghitung dampak
penurunan 5 jam kerja pada bagian finishing kita tinggal mengalikan change
vector bagian finishing (kolom S2) dengan besarnya perubahan yaitu minus 5 ( -5
). Dampak perubahan jam kerja pada bagian assembly dan finishing secara
simultan terhadap nilai optimal basic variable dapat dilihat pada baris kelima tabel
8.7. Dari tabel tersebut terlihat bahwa jumlah C (kursi) yang diproduksi naik
menjadi 11 2/3 unit, jumlah rak buku turun menjadi 11 2/3 unit sedangkan jam
kerja dibagian packing yang tersisa tinggal 21 2/3 jam. Dengan demikian
keuntungan perusahaan akan menjadi = (4 x 11 2/3) + (3 x 11 2/3) = 81 2/3.
Sehingga perubahan keuntungan = 81 2/3 – 76 2/3 = 5 . Besarnya kenaikkan
keuntungan ini sama dengan 10 kali shadow price untuk bagian assembly

103
 Program linear
dikurangi 5 kali shadow price bagian finishing (karena jam kerja bagian finishing
berkurang) atau = (10 x 5/6) + (-5 x 2/3) = 30/6 = 5.

E. Rentang Perubahan Sisi Kanan Fungsi Kendala Agar Solusi Masih

Tetap Optimal

Sejauh ini yang telah kita bicarakan adalah dampak adanya perubahan sisi
kanan fungsi kendala baik secara parsial maupun simultan terhadap nilai optimal
basic variable dan fungsi tujuan. Namun sampai seberapa besar kapasitas fungsi
kendala tersebut boleh berubah? Artinya jika perusahaan terpakasa
memberlakukan jam lembur bagi karyawannya atau mempekerjakan karyawan
paruh waktu, seberapa besar perusahaan boleh menambah jam kerja agar solusi
masih tetap optimal? Dan sebaliknya jika ada karyawan yang cuti ataupun sakit
yang berdampak pada pengurangan jam kerja, sampai seberapa besar jam kerja ini
boleh berkurang sehingga solusi masih tetap optimal?

Untuk menjawab beberapa pertanyaan diatas kita perlu mengetahui

rentang perubahan sisi kanan fungsi kendala. Sebagai contoh akan kita bahas
kembali kasus Ikhwan Furniture yang tabel optimalnya tampak pada tabel 8.1.
Misalnya sampai seberapa besar penambahan atau pun pengurangan pada bagian
assembly agar solusi masih tetap optimal?

Perhatikan tabel 8.8 dibawah ini. Informasi yang digunakan pada tabel 8.8
ini berasal dari tabel 8.1 topik 1 bab 8. Kolom pertama adalah variabel yang
berada pada kolom product mix, kolom kedua adalah angka-angka yang berada
pada kolom kuantitas, kolom ketiga berisi change vector pada kolom S1 (karena
yang kita analisa bagian assembly).

Tabel 8.8 Rentang Perubahan Bagian Assembly

104
 Program linear
Dari tabel 8.8 di atas angka positif terkecil (20) merupakan besarnya jam
kerja pada bagian assembly yang dapat diturunkan. Sedangkan angka negatif
terkecil (-40) adalah besarnya jam kerja pada bagian assembly yang dapat
ditambah. Sehingga batas terendah jam kerja bagian assembly adalah 40, yaitu (60
– 20). dan batas tertingginya adalah 100, yaitu (60 + 40). Cara yang sama bisa
digunakan untuk mengetahui rentang perubahan pada bagian lainnya.

Untuk mengetahui rentang perubahan bagian finishing, kita perlu

mengetahui hasil bagi antara angka yang berada pada kolom kuantitas dengan
change vector bagian finishing yaitu S2. kemudian kita pilih hasil bagi positif
terkecil untuk menentukan besarnya jam kerja yang boleh diturunkan serta hasil
bagi negatif terkecil untuk menentukan besarnya maksimum penambahan jam
kerja di bagian finishing. Untuk lebih jelasnya perhatikan tabel 8.9 berikut ini.

Tabel 8.9 Rentang Perubahan Bagian Assembly

Dari tabel 8.9 dapat disimpulkan bahwa jumlah jam kerja di bagian finishing
boleh ditambah maksimum 20 jam dan dikurangi maksimum sebesar 25 jam.
Sehinga rentang perubahan jam kerja di bagian finishing adalah antara (40-25)
sampai dengan (40+20) atau antara 15 jam – 60 jam. Artinya jam kerja di bagian
assembly boleh ditambah hingga 60 jam kerja atau dikurangi hingga 15 jam kerja.

105
 Program linear

Ringkasan
Dapak perubahan secara simultan sisi kanan fungsi kendala
terhadap nilai optimal basic variable dapat dihitung dengan
mengalikan change vector dengan besarnya perubahan sisi
kanan fungsi kendala yang bersesuaian.
Besarnya rentang perubahan sisi kanan fungsi kendala
ditentukan dengan membagi angka pada kolom kuantitas
dengan change vector untuk kendala yang sedang dianalisa.
Hasil bagi negatif terkecil menunjukkan besarnya
penambahan jam kerja maksimum yang diperkenankan agar
solusi masih tetap optimal, sedangkan hasil bagi positif
terkecil menunjukkan besarnya pengurangan jam kerja
maksimum yang diperkenankan agar solusi masih tetap
optimal.

106
 Program linear

Latihan

Untuk memperdalam pemahaman Anda mengenai materi di atas,

silakan anda mengerjakan latihan berikut ini !

1. Bagaimana cara menghitung besarnya dampak perubahan secara

simultan sisi kanan fungsi kendala terhadap nilai optimal basic
variabel ?
2. Bagaimana cara menghitung besarnya dampak perubahan secara
simultan sisi kanan fungsi kendala terhadap nilai optimal fungsi
tujuan ?
3. Bagaimana cara menentukan batas maksimum penambahan jam
kerja di suatu departemen (suatu kendala) agar solusi masih
tetap optimal ?
4. Bagaimana cara menentukan batas maksimum pengurangan jam
kerja di suatu departemen (suatu kendala) agar solusi masih
tetap optimal ?
5.
Pilih salah satu jawaban yang paling tepat dari beberapa alternatif
jawaban yang disediakan !

Berikut adalah formulasi LP dari suatu permasalahan maksimisasi

Fungsi Tujuan Max Z = 2 B + 5 M + 8 P

Fungsi Kendala 6 B + 8 M + 4 P ≤ 96
2 B + M + 2 P ≤ 40
5 B + 3 M + 2 P ≤ 60
B, M, P ≥ 0

107
 Program linear

Tabel optimal dari permasalahan di atas adalah :

Dengan menggunakan table di atas kerjakan soal berikut ini :

1) Jika kapasitas kendala 1 dan 2 masing-masing dinaikkan 1 unit

secara simultan maka jumlah M yang diproduksi akan
A. naik sebesar 1/6
B. turun sebesar 1/6
C. naik sebesar 15/6
D. turun sebesar 15/6
2) Jika kapasitas kendala 1 dan 2 masing-masing dinaikkan 1 unit
secara simultan maka jumlah P yang diproduksi akan
A. turun sebesar 1/12
B. naik sebesar 2/3
C. turun sebesar 7/12
D. naik sebesar 7/12
3) Jika kapasitas kendala 1 dinaikkan 1 unit sedangkan kapasitas
kendala 2 diturunkan 1 unit secara simultan maka jumlah M
yang diproduksi akan
A. naik sebesar 1/6
B. turun sebesar ½
C. naik sebesar ½
D. turun sebesar 1/6

108
 Program linear
DAFTAR PUTAKA

Dimyati, Tjutju Tarliah dan Ahmad Dimyati. Operations Research: Model-

model Pengambilan Keputusan. Sinar Baru Algensindo, Bandung. 2003.
Jay Heizer and Barry. Operations Management (10th edition). New York,
NY: Prentice Hall. Moon, Y. 2004.
Siringoringo, Hotniar. Seri Teknik Riset Operasional. Pemrograman Linear.
Penerbit Graha Ilmu. Yogyakarta. 2005.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

109
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang sejarah
program linear, keterampilan belajar secara mandiri
dalam mempelajari masalah-masalah pemrograman
linear dari kehidupan sehari-hari, dengan
menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan
dapat:
- Menjelaskan konsep dualitas
- Interpretasi ekonomis suatu masalah program
linear

127
 Program linear

TRANSPORTASI: FUNGSI TUJUAN MINIMISASI,

KASUS D = S

A. Pendahuluan
Metode Transportasi juga bisa digunakan untuk menyelesaikan
permasalahan liner programming. Tujuan dari metode transportasi adalah
menentukan pola pengiriman yang paling baik dari beberapa sumber (supply) ke
beberapa tujuan (demand) sehingga meminimalkan total biaya produksi dan
transportasi. Salah satu fungsi dalam dunia usaha adalah guna tempat. Panen padi
yang melimpah di Pulau Buru kehilangan nilai ekonomisnya karena kapal jarang
merapat di Pulau Buru untuk mengangkut hasil bumi ke Ambon dan sekitarnya
yang membutuhkan. Bawang merah yang melimpah di Brebes juga perlu
diangkut ke kota-kota lain agar lebih bermanfaat. Dalam hal ini alat transportasi
merupakan fungsi yang menambah nilai pada hasil bumi tersebut.

Manajemen Operasi bertugas untuk memilih sarana dan sistem transportasi

yang paling efisien. Cara penyelesaian kasus semacam ini dikenal dengan metode
transportasi.

Misalnya perusahaan memiliki dua pabrik (sumber) dan tiga gudang (tujuan).
Dengan metode transportasi, kasus semacam ini bisa disederhanakan
sebagaimana tampak pada matriks 10.1.

Matriks 6.1. Metode Transportasi

128
 Program linear

P : Pabrik

G: Gudang

Xij: jumlah barang yang dikirim dari Pi ke Gj

Cij: biaya pengiriman per unit dari Pi ke Gj

m: jumlah pabrik

n: jumlah gudang

a: kapasitas Pabrik

b: kapasitas Gudang

Penyelesaian dengan program linear

Fungsi tujuan (objective function)

Minimalisasi biaya (minimize cost):

C11 X11 + C12 X12 + C13 X13 + C21 X21 + C22 X22 + C23 X23 + ...... + Cmn
Xmn

Tergantung pada kendala-kendala

129
 Program linear
(Subject to the constraints)

X11 + X12 + X13 = a1

X21 + X22 + X23 = a2

X11 +X21 = b1

X12 + X22 = b2

X13 +X23 = b3

dan

Xij ≥ 0 (i= 1, 2,..., m; j= 1, 2, 3, ...., n)

Setelah mempelajari modul ini diharapkan anda dapat:

1. Memahami permasalahan penentuan lokasi dengan metode transportasi

2. Menyelesaikan permasalahan transportasi
3. Memahami tentang indeks
4. Merumuskan permasalahan transportasi dengan linear programming

Membuat Tabel Awal dengan Northwest Corner dan Least Cost

B. Membuat Tabel Awal Transportasi Dengan Northwest Corner Rule

Tujuan teknik transportasi adalah menentukan cara pengiriman barang
yang paling baik dari beberapa pemasok menuju pada beberapa daerah pelanggan
sehingga meminimalkan biaya produksi dan transportasi. Biasanya dijumpai
kapasitas produksi untuk masing-masing pemasok dan jumlah permintaan untuk
masing-masing daerah. Dalam teknik transportasi perlu ditentukan terlebih
dahulu kapasitas untuk tiap pabrik, keperluan dan daya tampung untuk masing-
masing gudang, dan biaya pengiriman dari setiap sumber menuju masing-masing
tujuan.

130
 Program linear
Matriks 10.2 menggambarkan biaya pengiriman per unit dari kota asal
(Pabrik) ke kota tujuan (Gudang). Dalam kasus ini, kota asal adalah Yogya,
Malang, dan Denpasar. Sedang kota tujuan adalah Jakarta, Semarang, dan
Surabaya. Biaya pengiriman barang per unit dari Yogya ke Jakarta adalah 5, dari
Yogya ke Semarang adalah 4 dan dari Yogya ke Surabaya adalah 3, dan
seterusnya.

Matriks 10. 2 Informasi Biaya Transportasi dari Kota Asal ke Kota Tujuan

Yang menjadi kendala dalam kasus transportasi adalah kapasitas pabrik

dan kapasitas gudang. Daya tampung gudang kota Jakarta adalah 300, Semarang
adalah 200, dan Surabaya 200. Kapasitas pabrik di kota Yogya adalah 100,
Malang adalah 300, dan Denpasar adalah 300. Kita harus mendistribusikan barang
dari pabrik ke gudang dengan biaya yang paling murah.

Dari data tersebut bisa kita buat matriks transportasi. Tujuan pembuatan
matriks adalah meringkas dan menyajikan dengan jelas data yang ada.

Permasalahan distribusi barang tersebut akan diselesaikan dengan

menggunakan metode Northwest Corner Rule, yaitu barang dari kota yang
terletak pada baris paling atas, dikirim ke kota tujuan pada kolom paling kiri.
Langkah-langkah berikut perlu diperhatikan dalam menjalankan aturan pojok kiri
atas (Northwest Corner Rule).

Dimulai dari kotak pojok kiri atas.

1. perhatikan kapasitas pabrik dari masing-masing baris.

131
 Program linear
2. kaitkan dengan permintaan masing-masing gudang untuk setiap kolom.
3. Teliti kembali apakah ada kesesuaian antara persediaan dan permintaan.
Kapasitas pabrik Yogya adalah 100. Kebutuhan gudang Jakarta adalah
300. Oleh karena itu, untuk sementara seluruh hasil produksi dari Yogya dikirim
ke Jakarta. Karena daya tampung gudang Jakarta adalah 300. Sementara ini baru
mendapat kiriman dari Yogya 100 unit, maka masih terdapat kekurangan sebesar
300 – 100 = 200 unit. Kekurangan ini diambilkan dari pabrik berikutnya, yaitu
Malang. Kapasitas pabrik di Malang adalah 300. Jakarta masih kekurangan 200.
Maka 200 unit dari Malang dikirim ke Jakarta, sedangkan sisanya (100) dikirim
ke kota tujuan berikut, yaitu Semarang. Kapasitas gudang di Semarang adalah
200. Baru mendapat kiriman dari Malang sebesar 100 unit. Perlu adanya kiriman
tambahan dari kota berikut, yaitu Denpasar sebesar 100. Mengingat kapasitas
pabrik Denpasar adalah 300, dan baru terpakai 100 yang dikirim ke Semarang,
maka masih tersisa 200 untuk dikirim ke Surabaya. Jumlah ini sesuai dengan daya
tampung gudang di Surabaya. Oleh karena itu kasus ini dikenal Demand = Supply
(D = S).

Matriks 10. 3 Penyebaran dengan Northwest Corner Rule

132
 Program linear
Berdasarkan penyebaran dengan menggunakan Northwest Corner Rule
tersebut di atas, perlu diadakan kalkulasi biaya pengiriman. Perhitungan kalkulasi
biaya terlihat pada Tabel 10.1, dimana total biaya pengiriman adalah sebesar
4.200.

Tabel 10. 1. Kalkulasi Biaya Berdasarkan Penyeberan dengan Northwest

Corner Rule

C. Membuat Tabel Awal Dengan The Least Cost Rule

The least-cost method berusaha mencari solusi awal yang lebih baik, yaitu
dengan memusatkan perhatian pada biaya pengiriman yang paling murah. Adapun
langkah-langkah penerapan the least-cost method adalah sebagai berikut.

1. Biaya D – C dan E – C adalah biaya yang terendah dari seluruh matriks ($3).
Untuk sementara kita alokasikan D ke C. Karena kapasitas C 200 dan
kapasitas D hanya 100, maka masih kurang 100. Karena kapasitas Pabrik D
sudah terpakai semua maka D – A dan D – B kita silang.
2. Biaya terendah dari kota yang belum tersilang adalah E – C. Kita alokasikan
dari E ke C sebesar 100 untuk memenuhi kebutuhan kapasitas gudang C. Dan
kota F – C kita silang, karena tidak memerlukan pengiriman lagi.
3. Dari empat kotak kosong yang memiliki biaya yang terendah adalah E – B
($4). Dari E kita kirim 200 unit ke B. Dan tinggal satu kota tujuan lagi yaitu
A. Seluruh kapasitas F (300 unit) kita kirim ke A.

133
 Program linear
Matriks 10. 4 Transportasi dengan The Least Cost Rule

Perhitungan total biaya pengiriman dengan menggunakan the least cost

method terlihat pada tabel 6. 2. Dengan menggunakan biaya yang terkecil
diperoleh solusi yang lebih baik (4100) dibandingkan dengan menggunakan the
northwest corner rule (4200).

Tabel 10. 2 Total biaya dengan least-cost method

134
 Program linear

Ringkasan

The northwest corner rule diterapkan pada metode transportasi

dengan mengirimkan barang dari kota asal pada baris paling atas
ke kota tujuan pada kolom paling kiri. Dengan menggunakan the
least cost method, pengiriman barang dimulai pada biaya yang
terendah. Cara ini memberikan solusi yang lebih murah
dibandingkan dengan menggunakan the northwest corner rule.

135
 Program linear

Latihan

Untuk memperdalam pemahaman Anda mengenai materi di atas,

silakan anda mengerjakan latihan berikut ini !

1. Jelaskan bahwa metode transportasi juga merupakan Linear

Programming.
2. Bagaimana metode northwest corner rule diterapkan pada
metode transportasi?
3. Bagaimana metode least cost diterapkan pada metode
transportasi?
4. Mengapa northwest corner rule kurang peka terhadap biaya?

136
 Program linear
DAFTAR PUTAKA

Dimyati, Tjutju Tarliah dan Ahmad Dimyati. Operations Research: Model-

model Pengambilan Keputusan. Sinar Baru Algensindo, Bandung. 2003.
Jay Heizer and Barry. Operations Management (10th edition). New York,
NY: Prentice Hall. Moon, Y. 2004.
Siringoringo, Hotniar. Seri Teknik Riset Operasional. Pemrograman Linear.
Penerbit Graha Ilmu. Yogyakarta. 2005.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

137
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang sejarah
program linear, keterampilan belajar secara mandiri
dalam mempelajari masalah-masalah pemrograman
linear dari kehidupan sehari-hari, dengan
menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan
dapat:
- Menjelaskan konsep dualitas
- Interpretasi ekonomis suatu masalah program
linear

138
 Program linear
STEPPING STONE

A. The Stepping-Stone Method

The Stepping-Stone Method merupakan cara merubah penyelesaian awal
pada pemecahan yang optimal. Cara ini digunakan untuk mengevaluasi biaya
transportasi dengan merubah rute yang belum terpakai.

1. (unused square) Pilihlah kotak yang belum terpakai.

2. Berawal dari kotak ini, lacaklah ke kotak awal dengan melewati kotak yang
sekarang terpakai.
3. Berilah tanda plus pada kotak yang tak terpakai, dan berilah tanda minus pada
kotak yang terpakai.
4. Buatlah indeks dengan menambah biaya pada tanda plus dan mengurangi
biaya pada tanda minus.
Sebagaimana tampak pada Matriks 11. 5, kita melakukan uji coba mengirim 1 unit
dari pabrik Yogya ke Semarang. Akibatnya Semarang kelebihan 1 unit dan
Jakarta kekurangan satu unit. Agar distribusi tetap seimbang sesuai kapasitas
masing-masing, 200 unit yang dikirim dari Malang ke Semarang dikurangi 1 unit
dan dikirim ke Jakarta. Uji coba ini harus tetap menjaga kapasitas pabrik dan
gudang sehingga menjadi jalur tertutup (closed path).

Dengan adanya uji coba pengiriman dari Yogya ke Semarang, terjadi perubahan
biaya yang bisa dihitung dengan menggunakan angka indeks. Angka indeks
dihitung berdasarkan penambahan atau pengurangan 1 unit dikalikan dengan
biaya pengiriman per unit. Bila angka indeks positif, berarti terjadi penambahan
biaya. Sebaliknya bila angka indeks negatif, berarti akan terjadi pengurangan
biaya pada saat kita memindahkan distribusi dari kota asal ke kota tujuan yang
berindeks negatif tersebut.

139
 Program linear
Matriks 11. 5 Indeks dari Jogya ke Semarang

Indeks dari Jogya ke Semarang (D – A): (1*4)-(1*5)+(1*8)-(1*4) = 3

Berarti terjadi kenaikan biaya sebesar Rp3,- untuk perubahan pengiriman

dari Jogya ke Semarang. Dengan cara yang sama kita bisa menghitung semua
angka indeks pada kota yang kosong.

Indeks Dari Jogya ke Surabaya (D – C): 3-5+8-4+7-5 = 4. untuk

memudahkan perhitungan ini lihat Matriks 6. 6.

Indeks dari Malang ke Surabaya: 3-4+7-5 = 1

Indeks dari Ujungpandang ke Jakarta: 9-7+4-8 = -2

Karena indeks yang terakhir negatif, bisa diperoleh penghematan beaya

dengan memanfaatkan rute yang belum terpakai dari Yogya ke Jakarta.

140
 Program linear
Matriks 11. 6 Indeks dari Jogya ke Surabaya

B. Melakukan Perbaikan Tabel

Berdasarkan hasil perhitungan indeks pada sub bab A, diperoleh hasil -2
untuk pengiriman dari Denpasar ke Jakarta, maka pada matriks 6 dicoba 100 unit
dikirimkan dari Denpasar ke Jakarta. Dampak dari ujicoba tersebut adalah bahwa
pengiriman dari Malang ke Jakarta harus dikurangi 100 dan dialihkan ke
Semarang. Untuk memastikan apakah perubahan tersebut akan menurunkan total
biaya pengiriman, perlu kita hitung kembali total biaya pengiriman dengan
distribusi yang baru.

Matriks 11. 7 Uji Coba Pengiriman dari Denpasar ke Jakarta

141
 Program linear

Tabel 6. 3. Total Biaya Uji Coba Pertama

Dengan mengalikan jumlah yang dikirim dari sumber ke tujuan pada Matriks 6.7,
diperoleh total biaya pengiriman dengan distribusi yang baru sebesar 4.000. Total
biaya pengiriman berkurang (100 unit x 2) = Rp.200,-, menjadi = Rp.4000,-

142
 Program linear

Ringkasan

Modi method digunakan untuk menguji apakah suatu matriks

sudah optimal atau belum. Angka indeks positif
menunjukkan terjadinya penambahan biaya apabila satu unit
produk dikirim ke kotak kosong tersebut. Angka indeks
negatif menunjukkan bahwa akan terjadi pengurangan biaya
apabila satu unit produk dikirim ke kotak yang berindeks
negatif tersebut.

143
 Program linear

Latihan

Untuk memperdalam pemahaman Anda mengenai materi di atas,

silakan anda mengerjakan latihan berikut ini !

1. Jelaskan langkah-langkah metode transportasi dengan northwest

corner rule.
2. Jelaskan langkah-langkah metode transportasi dengan
menggunakan least cost method
3. Jelaskan perbedaan antara northwest corner rule dengan least
cost method.

144
 Program linear
DAFTAR PUTAKA

Dimyati, Tjutju Tarliah dan Ahmad Dimyati. Operations Research: Model-

model Pengambilan Keputusan. Sinar Baru Algensindo, Bandung. 2003.
Jay Heizer and Barry. Operations Management (10th edition). New York,
NY: Prentice Hall. Moon, Y. 2004.
Siringoringo, Hotniar. Seri Teknik Riset Operasional. Pemrograman Linear.
Penerbit Graha Ilmu. Yogyakarta. 2005.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

145
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang sejarah
program linear, keterampilan belajar secara mandiri
dalam mempelajari masalah-masalah pemrograman
linear dari kehidupan sehari-hari, dengan
menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan
dapat:
- Menjelaskan konsep dualitas
- Interpretasi ekonomis suatu masalah program
linear

146
 Program linear

TRANSPORTASI: FUNGSI TUJUAN MINIMISASI,

KASUS D = S PENYELESAIAN DENGAN VAM

Pendahuluan
Metode Transportasi sebagaimana dibicarakan pada bab 11, diselesaikan
dengan menggunakan Norhwest corner rule. Keuntungan menggunakan northwest
corner rule adalah bahwa metode ini sistematik dan mudah diterapkan. Namun
demikian kelemahan metode ini adalah bahwa tidak sensitif terhadap biaya.
Karena tujuan metode transportasi adalah meminimumkan biaya, kita bisa
menggunakan opportunity cost dengan memilih biaya per unit yang paling rendah.

Setelah mempelajari modul ini diharapkan anda dapat:

1. Memahami kelebihan VAM

2. Menyelesaikan permasalahan transportasi dengan VAM
3. Menghitung Indeks dengan menggunakan Modi Method
4. Membuat Matriks pengembangan dengan Modi Method

Menghitung Biaya Peluang dengan VAM

dan Melakukan Improvement

A. Menghitung Biaya Peluang Dengan VAM

Vogel Approximation Method (VAM) yang dikembangkan oleh Vogel
pada prinsipnya mencari opportunity cost (biaya peluang). Untuk setiap baris dan
kolom, dibandingkan dan dihitung selisih antara biaya terendah dengan yang lebih
tinggi. Pengiriman dilakukan dari kota asal ke kota tujuan dengan memilih selisih
biaya terbesar dan terendah. Selisih biaya dihitung dengan cara mengurangkan
biaya terendah pada biaya satu tingkat di atasnya.

147
 Program linear
Matriks 12. 1 Data Biaya Pengiriman Per Unit, Kapasitas Pabrik dan
Kapasitas Gudang

Matriks I menunjukkan biaya transportasi, kapasitas pabrik dan kapasitas

gudang. Berdasarkan tabel tersebut Vogel membuat perhitungan untuk masing-
masing baris dan kolom perbedaan biaya yang termurah dengan biaya yang lebih
mahal.

Pada baris PA, biaya pengiriman terendah adalah dari PA ke G2 (23).

Biaya terendah berikutnya adalah dari PA ke G1 (27). Biaya peluang pada PA
adalah 4 (27 – 23). Pada baris PB, biaya pengiriman terendah adalah dari PB ke
G1 (10). Biaya terendah berikutnya adalah dari PB ke G4 (32). Biaya peluang
pada PB adalah 22 (32 – 10). Selisih biaya menunjukkan penghematan yang bisa
dilakukan pada baris atau kolom. Semua perhitungan selisih biaya pada baris dan
kolom terlihat pada Matrik 12.2.
Matriks 7.2. Biaya Peluang Baris dan Kolom

148
 Program linear
Dari seluruh perhitungan tersebut terlihat bahwa selisih terbesar terdapat
pada kolom G4 (25). Hal itu berarti perusahaan akan menghemat 25 satuan biaya
kalau mengirim pertama ke kolom G4. pada kolom G4 tersebut kita pilih kotak
dengan biaya terendah dalam hal ini adalah baris PB. Sebagai percobaan awal
semua kebutuhan G4 dikirim dari PB sejumlah 40 unit.

Untuk mengisi kotak yang lain, diulangi cara yang sama, yaitu dengan
menghitung biaya peluang berdasarkan baris dan kolom, kemudian pilih biaya
peluang terbesar dan alokasikan pada kotak dengan biaya terendah, dengan
mempertimbangkan supply dan demand.

B. Mengisi Kotak Lain Pada VAM

Dalam permasalahan transportasi, Opportunity cost (biaya peluang) antara
baris supply dan kolom demand dimengerti sebagai selisih antara biaya terendah
dan biaya terendah berikutnya. Langkah-langkah Vogel Approximation method
adalah sebagai berikut.

1. pada setiap baris dan kolom, pilih biaya terendah dan alternatif biaya terendah
berikutnya pada kotak yang belum terpakai. Selisih antara biaya terendah dan
altiernatif biaya terendah berikutnya merupakan opportunity cost (biaya
peluang) bagi baris atau kolom.
2. pilihlah opportunity cost yang tertinggi di antara baris dan kolom
3. alokasikan sebanyak mungkin unit pada baris atau kolom pada kotak dengan
biaya terendah.
Untuk mengisi kotak kosong yang lain, dihitung kembali biaya peluang
berdasarkan baris dan kolom. Baris PB yang kapasitasnya sudah habis digunakan,
tidak diperhitungkan dalam proses perhitungan biaya peluang. Perhitungan biaya
peluang berdasarkan baris dan kolom dapat dilihat pada Matriks 7.3.

Dari perhitungan biaya peluang tersebut, terlihat bahwa selisih biaya

terbesar terletak pada kolom G2, yaitu sebesar 31. Oleh karena itu kita akan
mengalokasikan pada kolom G2 dengan memilih kotak dengan biaya terendah,
yaitu kotak PA – G2. Untuk menentukan berapa yang harus dialokasikan ke

149
 Program linear
kotak PA –G2, perlu mempertimbangkan kapasitas Pabrik PA dan Gudang G2.
karena permintaan pada G2 70 sementara kapasitas Pabrik PA 150, maka kita
alokasikan sebesar 70. Sehingga kapasitas Pabrik PA masih tersisa 80 unit yang
bisa dialokasikan ke gudang lainnya.

Matriks 12. 3. Biaya Peluang terbesar pada Solusi Awal

Perhitungan biaya peluang (opportunity cost) pada baris dan kolom

tersebut diulangi lagi untuk baris dan kolom yang masih terdapat kapasitas sisa.
Distribusi akhir untuk kasus tersebut terlihat pada Matriks 12. 4 dan total biaya
minimum terlihat pada Tabel 12.1, yaitu sebesar 8240.

Matriks 12.4. Distribusi Akhir dengan VAM

150
 Program linear
Tabel 12.1. Total Biaya dengan VAM

Ringkasan

Vogel Approximation Method mendasarkan pada konsep

opportunity cost (selisih antara biaya terendah dengan biaya
satu tingkat di atasnya), untuk setiap baris dan kolom. Untuk
melakukan alokasi ke setiap kotak dipilih biaya peluang
terbesar, kemudian pilih kotak yang mempunyai biaya
terendah.

151
 Program linear

Latihan

Untuk memperdalam pemahaman Anda mengenai materi di atas,

silakan anda mengerjakan latihan berikut ini !

1. Jelaskan perbedaan metode VAM dan least cost.

2. bagaimana metode VAM diterapkan pada metode transportasi?
3. Apa yang dimaksud dengan opportunity cost sebagaimana
diterapkan VAM pada kasus transportasi

152
 Program linear
DAFTAR PUTAKA

Dimyati, Tjutju Tarliah dan Ahmad Dimyati. Operations Research: Model-

model Pengambilan Keputusan. Sinar Baru Algensindo, Bandung. 2003.
Jay Heizer and Barry. Operations Management (10th edition). New York,
NY: Prentice Hall. Moon, Y. 2004.
Siringoringo, Hotniar. Seri Teknik Riset Operasional. Pemrograman Linear.
Penerbit Graha Ilmu. Yogyakarta. 2005.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

153
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang sejarah
program linear, keterampilan belajar secara mandiri
dalam mempelajari masalah-masalah pemrograman
linear dari kehidupan sehari-hari, dengan
menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan
dapat:
- Menjelaskan konsep dualitas
- Interpretasi ekonomis suatu masalah program
linear

154
 Program linear

TRANSPORTASI: FUNGSI TUJUAN MINIMISASI,

KASUS D = S PENYELESAIAN
DENGAN MODI METHODE

A. The MODI Method

MODI (modified distribution) method merupakan perkembangan dari
model indeks pada kotak yang belum terpakai. Penerapan metode MODI diawali
dengan menggunakan northwest corner rule (lihat Matriks 7.6). Kita harus
menghitung nilai dari masing-masing baris (R1, R2 , R3) dan masing-masing
kolom (K1, K2, K3). Dalam MODI method, indeks pengembangan dapat dihitung
tanpa menggambar jalur tertutup (closed path).

Dalam modi method, R menjadi simbol baris dan K menjadi simbol kolom.

Ri = nilai pada baris ke i

Kj = nilai pada kolom ke j.

Cij = biaya pada kotak ij.

Sehingga biaya pada kotak terisi (stone square) ij adalah sebagai berikut

Cij = Ri + Kj

Prosedur umum untuk menyelesaikan MODI method adalah bahwa R1 = 0. Hal

ini bisa dibenarkan karena seluruh proses bersifat komparatif. Dengan kata lain,
signifikansi nilai baris dan kolom tidak terletak pada nilai absolutnya.

Lima langkah MODI method :

1. Menghitung nilai dari masing-masing baris dan kolom; tetapi hanya kotak
yang terisi (Cij= Ri +Kj)
2. Setelah semua persamaan ditulis, tentukan R1 = 0
3. Selesaikan semua persamaan

155
 Program linear
4. Hitunglah indeks untuk masing-masing kotak yang tidak terpakai Indeks =
Cij – Ri - Kj
5. Pilihlah indeks dengan nilai negatif terbesar untuk kasus minimisasi.

B. Melakukan Perbaikan Tabel

Matriks 13.6 diambil dari Matriks 6.3 digunakan sebagai perhitungan
dengan menggunakan Modi Method. Dengan rumus Cij = Ri + Kj, semua kotak
yang terisi kita masukkan informasi yang terdapat pada tabel. Biaya dari (D)
Jogya ke (A) Jakarta sebesar 5, dituliskan menjadi R1 + K1 = 5. Biaya dari (E)
Malang ke (A) Jakarta sebesar 8, dituliskan menjadi R2 + K1 = 8, dan seterusnya.

Matriks 13. 6. Penyebaran dengan Northwest Corner Rule

Berdasarkan Matriks 13.6, kita dapat menentukan nilai Ri dan Kj untuk kotak
terisi sebagai berikut.

R1 + K1 = 5

R2 + K1 = 8

R2 + K2 = 4

R3 + K2 = 7

156
 Program linear
R3 + K3 = 5

Sebagaimana langkah kedua dalam Modi, ditentukan bahwa R1 = 0, sehingga

semua persamaan bisa diselesaikan sebagai berikut.

R1 = 0

R1 + K1 = 5 0 + K1 = 5 K1 = 5

Karena K1 = 5, maka kita bisa menghitung R2

R2 + K1 = 8 R2 + 5 = 8 R2 = 3

Karena R2 = 3, kita bisa menghitung K2

R2 + K2 = 4 3 + K2 = 4 K2 = 1

Karena K2 = 1, kita bisa menghitung R3

R3 + K2 = 7 R3 + 1 = 7 R3 = 6

Karena R3 = 6, kita bisa menghitung K3

R3 + K3 = 5 6 + K3 = 5 K3 = -1

Setelah kita mendapatkan nilai masing-masing Ri dan Kj, maka langkah

selanjutnya adalah menghitung indeks untuk kotak yang kosong: dilakukan
dengan rumus Cij – Ri - Kj.

Perhatikan kembali Matriks 7.6. kotak kosong adalah D-B, D-C, E-C, dan F-A.

Sehingga Indeks dari Jogya ke Semarang (D-B) = C12 – R1 – K2

4 - 0 - 1 = 3

Indeks dari Jogya ke Surabaya (D-C) = C13 – R1 – K3

3 - 0 - (-1) = +4

Indeks dari Malang ke Surabaya (E- C) = C23 – R2 – K3

157
 Program linear
3 - 3 - (-1) = +1

Indeks dari Denpasar ke Jakarta (F-A) = C31 – R3 – K1

9 - 6 - 5 = -2

Dengan menggunakan Modi Method kita ketahui bahwa indeks negatif

terbesar terletak pada kotak F-A atau Indeks dari Denpasar ke Jakarta = - 2. Hasil
perhitungan ini sama dengan cara stepping stone sebagaimana telah dibicarakan
pada bab 8 topik 2. oleh karena itu ujicoba pengembangan Matriks penyebaran
juga sama dengan Matriks 13.7. sebagaimana terlihat pada Matriks 13.7.
Berdasarkan Matriks 13.6 diketahui bahwa kotak yang mempunyai indeks negatif
terbesar adalah F – A sehingga kita bisa membuat jalur tertutup yang dimulai dari
kotak F – A dengan memberikan tanda positif kemudian ke kotak E – A, E – B, F
– B. Dari jalur tertutup tersebut kotak yang mempunyai tanda negatif dan alokasi
paling kecil adalah kota F – B (100). Angka ini akan kita gunakan untuk
menambah kotak yang bertanda positif dan mengurangi kotak yang bertanda
negatif. Hasil selengkapnya bisa dilihat pada Matriks 13.7.

Untuk perbaikan Matriks perlu diikuti langkah-langkah berikut:

1. lacak jalur tertutup (closed path) yang memiliki indeks negatif terbesar
2. beri tanda plus dan minus pada kotak lain dari jalur, dimulai dengan tanda plus
pada kotak yang tidak terpakai.
3. kotak yang mempunyai tanda negatif dan alokasi terkecil yang terdapat pada
jalur tertutup menunjukkan jumlah yang bisa dikirim pada kotak yang tidak
terpakai.
4. akhirnya, indeks pengembangan bagi solusi yang baru bisa dihitung.
Matriks 13. 7. Uji Coba Pengiriman dari Denpasar ke Jakarta

158
 Program linear

Perbaikan Matriks ini akan kita lakukan sampai diperoleh indeks bertanda
positif atau nol. Untuk menguji apakah Matriks 7.7. sudah optimal atau belum
akan dihitung kembali nilai Ri dan Kj untuk kotak yang kosong dengan rumus (Cij
– Ri - Kj).

R1 = 0

R1 + K1 = 5 0 + K1 = 5 K1 = 5

Karena K1 = 5, maka kita bisa menghitung R2

R2 + K1 = 8 R2 + 5 = 8 R2 = 3

Karena R2 = 3, kita bisa menghitung K2

R2 + K2 = 4 3 + K2 = 4 K2 = 1

Karena K1 = 5, kita bisa menghitung R3

R3 + K1 = 9 R3 + 5 = 9 R3 = 4

Karena R3 = 4, kita bisa menghitung K3

R3 + K3 = 5 4 + K3 = 5 K3 = 1

Menghitung indeks pengembangan untuk kotak yang kosong:dilakukan dengan

rumus Cij – Ri - Kj

Sehingga Indeks dari Jogya ke Semarang (D-B) = C12 – R1 – K2

4 - 0 - 1 = 3

159
 Program linear
Indeks dari Jogya ke Surabaya (D-C) = C13 – R1 – K3

3 - 0 - 1 = +2

Indeks dari Malang ke Surabaya (E- C) = C23 – R2 – K3

3 - 0 - 1 = +2

Indeks dari Denpasar ke Semarang (F- B) = C32 – R3 – K2

7- 4 - 1 = 2

Matriks 13. 8. Distribusi Minimum

Seperti telah dilakukan pada Matriks 13.6, dari perhitungan indeks terlihat
bahwa kotak kosong (E – C) mempunyai indeks negatif terbesar, yaitu – 1. Oleh
karena itu akan kita buat closed path (jalur tertutup) yang dimulai dari kotak E –
C, dengan tanda positif. Dari jalur tertutup ini kotak yang mempunyai tanda
negatif dan alokasi terkecil adalah kotak E – A. Matriks yang sudah diperbaiki
terlihat pada Matriks 13.8.

Untuk menguji apakah Matriks 13. 8. sudah optimal atau belum akan
dihitung kembali nilai Ri dan Kj untuk kotak yang kosong dengan rumus (Cij – Ri -
Kj).

R1 = 0

160
 Program linear
R1 + K1 = 5 0 + K1 = 5 K1 = 5

Karena K1 = 5, maka kita bisa menghitung R3

R3 + K1 = 9 R3 + 5 = 9 R3 = 4

Karena R3 = 4, kita bisa menghitung K3

R3 + K3 = 5 4 + K3 = 5 K3 = 1

Karena K3 = 1, kita bisa menghitung R2

R2 + K3 = 3 R2 + 1 = 3 R3 = 2

Karena R3 = 2, kita bisa menghitung K2

R3 + K2 = 4 2 + K2 = 4 K3 = 2

Menghitung indeks pengembangan untuk kotak yang kosong:dilakukan dengan

rumus Cij – Ri - Kj

Sehingga Indeks dari Jogya ke Semarang (D-B) = C12 – R1 – K2

4 - 0 - 2 = +2

Indeks dari Jogya ke Surabaya (D-C) = C13 – R1 – K3

3 - 0 - 1 = +2

Indeks dari Malang ke Jakarta (E- A) = C21 – R2 – K1

8 - 2 - 5 = +1

Indeks dari Denpasar ke Semarang (F- B) = C32 – R3 – K2

7 - 4 - 2 = +1

Karena semua indeks kotak kosong bernilai positif, maka Matriks sudah optimal.
Total biaya minimum sebesar 3900 sebagaimana tampak pada Tabel 13.2.
Tabel 13. 2. Total Biaya Minimum

161
 Program linear

Modi method digunakan untuk menguji apakah suatu matriks

transportasi sudah optimal atau belum. Angka indeks positif
menunjukkan terjadinya penambahan biaya apabila satu unit
produk dikirim ke kotak kosong tersebut. Angka indeks
negatif menunjukkan bahwa akan terjadi pengurangan biaya
apabila satu unit produk dikirim ke kotak yang berindeks
negatif tersebut.

Perbaikan Matriks dilakukan dengan cara menghitung indeks

kemudian pilih indeks dengan tanda negatif terbesar. Matriks
dikatakan optimal bila semua indeks bernilai positif atau nol
untuk fungsi tujuan minimisasi.

162
 Program linear

Latihan

Untuk memperdalam pemahaman Anda mengenai materi di

atas, silakan anda mengerjakan latihan berikut ini !

1. Jelaskan langkah-langkah modi method.

2. Bagaimana cara membuat jalur tertutup?
3. Apa kriteria suatu Matriks dengan pendekatan Modi dinyatakan
optimal untuk fungsi tujuan minimisasi?

163
 Program linear

DAFTAR PUTAKA

Dimyati, Tjutju Tarliah dan Ahmad Dimyati. Operations Research: Model-

model Pengambilan Keputusan. Sinar Baru Algensindo, Bandung. 2003.
Jay Heizer and Barry. Operations Management (10th edition). New York,
NY: Prentice Hall. Moon, Y. 2004.
Siringoringo, Hotniar. Seri Teknik Riset Operasional. Pemrograman Linear.
Penerbit Graha Ilmu. Yogyakarta. 2005.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

164
 Program linear

Standar Kompetensi:
Mahasiswa memiliki pengetahuan tentang sejarah
program linear, keterampilan belajar secara mandiri
dalam mempelajari masalah-masalah pemrograman
linear dari kehidupan sehari-hari, dengan
menekankan pada pemahaman konsep serta
penguasaan dan kemahiran teknik penyelesaiannya
menggunakan teori maupun paket program
komputer.

Indikator:
Setelah membaca bab ini, mahasiswa diharapkan
dapat:
- Menjelaskan konsep dualitas
- Interpretasi ekonomis suatu masalah program
linear

165
 Program linear

TRANSPORTASI: FUNGSI TUJUAN MINIMISASI,

KASUS D = S PENYELESAIAN
DENGAN MODI METHODE

A. Pendahuluan
Program POM adalah sebuah program komputer yang digunakan untuk
memecahkan masalah dalam bidang produksi dan operasi yang bersifat
kuantitatif. Tampilan grafis yang menarik dan kemudahan pengoperasian
menjadikan POM for Windows sebagai alternatif aplikasi guna membantu
pengambilan keputusan seperti misalnya menentukan kombinasi produksi yang
sesuai agar memperoleh keuntungan sebesar-besarnya. Menentukan order
pembelian barang agar biaya perawatan menjadi seminimal mungkin, menentukan
penugasan karyawan terhadap suatu pekerjaan agar dicapai hasil yang maksimal,
dan lain sebagainya.

Program ini menyediakan beberapa modul berbeda, yaitu:

1. Aggregate Planning
2. Assignment (Penugasan)
3. Balancing Assembly Line
4. Break Even/Cost-Volume Analysis
5. Decission Analysis (Pengambilan Keputusan)
6. Forecasting (Peramalan)
7. Inventory (Persediaan)
8. Job Shop Sceduling
9. Learning Curve
10. Linnier Proggraming (Pemrograman Linier)
11. Location
12. Lot Sizing
13. Material Requirements Planning
14. Operations Layout
15. Project Management (PERT/CPM)
16. Quality Control
17. Reliability
18. Simulation
19. Transportation

166
 Program linear
20. Waiting Lines (Antrian)

B. Materi Aplikasi Program Linear

Materi praktikum menggunakan POM For Windows hanya akan dibatasi
hanya beberapa buah model dari 20 model yang ada, antara lain yaitu Linnier
Programming, Transportation, Assignment, Inventory, Game Theory, dll.

Dalam mempelajari Riset Operasi, diperlukan model untuk

penyederhanaan yang sengaja dibuat untuk mempermudah mempelajari dunia
nyata yang kompleks dan hasilnyad dikembalikan ke dunia nyata kembali. Model
bisa berbentuk gambar, simulator/prototype, matematis/grafik, dll. Dalam
pengambilan keputusan dapat dibantu dengan banyak alat analisis. Untuk
melakukan analisis diperlukan data.

C. Langkah Umum Memecahkan Masalah Program Linear

1. Siapkan formula masalahnya, semisal akan dipecahkan suatu masalah
linier programming maka langkah kerjanya adalah:
 Tentukan masalahnya apakah kasus maksimum atau minimum
 Berapa jumlah variabel yang ada
 Berapa jumlah batasan yang ada
2. masukkan masalah tersebut ke dalam komputer
3. lakukan pengecekan pada masalah bila terjadi kesalahan input
4. Lakukan perhitungan dan lihat hasilnya dengan menKlik SOLVE
5. Tampilkan hasil-hasil perhitungan
6. Simpan formulasi masalah atau datanya

D. Menjalankan POM For Windows

 Melalui Shortcut
Apabila ada shortcut POM for Windows maka klik 2x pada icon (Gambar)
Shortcut POM for Windows.

 Melalui Menu Program

167
 Program linear
Klik start → Program → Pilih POM for Windows sehingga akan muncul
tampilan berikut :

Secara garis besar layar POM for Windows terdiri atas :

1. Title Bar
Terdiri dari: The control Main Box, program name dan button untuk layar
yaitu Minimize, Maximize, dan close.

2. Menu Bar
Terdiri dari: File, Edit, View, Modul, Tables, Tools, Windows, dan Help.

3. Tool Bar atau Button Bar

Terdiri dari: Command Bar, contohnya print screen dan solve, Instruction
Panel, Extra Data Area, Data Table, Annotation Area, Status Panel.

168
 Program linear
E. Model Grafik
Model grafik digunakan untuk memecahkan masalah penentuan kombinasi
optimum (maksimal dua variabel) guna memaksimumkan laba atau
meminimumkan biaya dengan kendala tertentu.

Contoh (Maksimisasi):

Dua produk diproses berangkai menggunakan 4 mesin. Waktu setiap mesin per
hari tersedia 8 jam. Waktu proses produksi dan profit sebagai berikut:

PRODUK MESIN 1 MESIN 2 MESIN 3 MESIN 4 PROFIT

1 10 menit 6 menit 8 menit 0 menit Rp.
10.000
2. 5 menit 20 menit 15 menit 30 menit Rp.
20.000

Hitung jumlah produksi optimal setiap jenis produk dan keuntungan totalnya!

Penyelesaian:

Pada kasus disebutkan waktu yang tersedia adalah 8 jam sedangkan proses
produksi mesin menggunakan satuan menit sehingga perlu penyesuaian satuan
waktu menjadi menit sehingga diperoleh angka 8 jam x 60 menit = 480 menit

Formulasi Linier Programming:

Z max = 10.000 X1 + 20.000 X2 (Fungsi tujuan)

Fungsi Kendala :

1) 10 X1 + 5 X2 ≤ 480
2) 6 X1 + 20 X2 ≤ 480
3) 8 X1 + 15 X2 ≤ 480
4) 30 X2 ≤ 480
5) X1, X2 ≥ 0

169
 Program linear

Setelah formulasi selesai disusun maka masukkan data pada program POM for
Windows dengan langkah sebagai berikut:

 Pada menu POM klik MODULE lalu pilih Linear Programming,

lalu klik NEW sehingga muncul gambar berikut :

Keterangan:

- Title → judul kasus yang diselesaikan, misalnya PT. LAKU JAYA

- Number of Constraint → jumlah fungsi batasan yang ada pada kasus. Isikan
4 buah mesin untuk produksi (A,B,C,D) sebagai fungsi batasan.
- Number of Variables → jumlah variabel yang ada pad fungsi tujuan. Isikan
2 sesuai kasus di ata terdapat 2 produk (1,2) sebagai fungsi tujuan.
- Objective → tujuan pengalokasian sumber daya. Klik Maximize sesuai kasus
di atas (memaksimalkan keuntungan)
- Row Name Options → Nama batasan yang diinginkan, misalnya A,B,C,…
 Klik OK sehingga muncul tampilan isian untuk memasukkan koefisien fungsi
batasan dan fungsi tujuan serta kapasitas maksimum batasan pada kolom RHS
(Right Hand Side) seperti berikut:

170
 Program linear

 Klik SOLVE apabila data sudah lengkap dan benar sehingga akan tampak
hasilnya.
 Kemudian dengan klik menu Window akan tampil pilihan Linear
Programming Result, Ranging, Solution List, Iterations, dan Graph seperti
pada gambar berikut:

171
 Program linear
Di bawah kolom Constraint Display terdapat kolom Corner Points yang
menunjukkan hubungan antara variabel X1 dan X2 serta Z. Misalkan apabila X1
= 48 dan X2 = 0 maka Z (profit) akan bernilai 480000.

Jumlah produksi untuk produk:

1. (X1) = 34,29

2. (X2) = 13.71

Keuntungan Total : Z = Rp. 617.142,9 ,-

Catatan:

Untuk linear proggramming minimisasi prosesnya sama, hanya tinggal

mengganti option objective-nya pada pilihan minimize.

172
 Program linear

Ringkasan:

Area blok (warna pink) pada grafik merupakan Feaseble Area

yaitu daerah batas yang mungkin untuk pengalokasian sumber
daya produksi yang ada dengan waktu yang tersedia. Produksi
tidak boleh melebihi titik-titik yang ada pada daerah Feaseble
Area.

Pada grafik terdapat Isoprofit Line yang berada pada titik

(34,29:13,71) di mana garis tersebut merupakan titik koordinat
maksimum produksi guna mencapai profit yang maksimal.

Pada grafik sisi kanan terdapat Kolom Constraint Display yang

akan menunjukkan Garis dari persamaan formulasi Linear
Programming yang ada apabila di-klik salah satu check-box di
depannya.

173
 Program linear

Latihan

1. PT A&D menghasilkan dua jenis produk yaitu P1 dan P2,

masing-masing memerlukan 2 macam bahan baku, P dan Q.
Harga jual tiap satuan P1 adalah 150 dan P2 adalah 100. Bahan
baku P yang tersedia adalah sebanyak 600 satuan dan Q
sebanyak 1000 satuan. Satu satuan P1 memerlukan satu satuan P
dan dua Satuan Q, sedang P2 memerlukan satu satuan P dan satu
satuan Q. Persoalannya adalah alokasi bahan P dan Q
semaksimal mungkin untuk menentukan jumlah produksi P1 dan
P2 sehingga mendapatkan keuntungan yang maksimal.
2. Colourfull company memiliki sebuah pabrik yang menghasilkan
cat, baik untuk interior maupun eksterior untuk mendistribusikan
kepada para grosir. Dua bahan mentah A dan B dipergunakan
untuk membuat cat tersebut. Ketersediaan maksimum bahan A
adalah 6 ton per hari, ketersediaan maksimum bahan B adalah 8
ton per hari kebutuhan harian akan bahan mentah per ton cat
interior dan eksterior digambarkan.

174
 Program linear
DAFTAR PUTAKA

Dimyati, Tjutju Tarliah dan Ahmad Dimyati. Operations Research: Model-

model Pengambilan Keputusan. Sinar Baru Algensindo, Bandung. 2003.
Jay Heizer and Barry. Operations Management (10th edition). New York,
NY: Prentice Hall. Moon, Y. 2004.
Siringoringo, Hotniar. Seri Teknik Riset Operasional. Pemrograman Linear.
Penerbit Graha Ilmu. Yogyakarta. 2005.

Tiro, Muhammad Arif. 2004. Pengenalan Manajemen Sains. Makassar:

Andira Fublihser.

175
 Program linear

GLOSARIUM

Abjad
A Additivity (penambahan). Artinya aktivitas total sama dengan
penjumlahan aktivitas individu.
Alternatif Optima adalah situasi dimana terdapat lebih dari satu
solusi optimal.
B
C Certainty/kepastian adalah fungsi tujuan dan fungsi kendala
sudah diketahui dengan pasti dan tidak berubah selama periode
analisa
corner point adalah titik-titik suduk pada area layak
D Divisibility (bisa dibagi-bagi). Maksudnya solusi tidak harus
merupakan bilangan integer (bilangan bulat), tetapi bisa juga
berupa pecahan
Dual adalah persoalan programa linier mempunyai suatu
programa linier lain yang saling berkaitan

E
F feasible region adalah daerah yang menjadi potensi
penyelesaian secara matematis
I Integer adalah bilangan bulat
iso profit line merupakan garis selidik
Infeasibility adalah suatu kondisi dimana tidak ada area layak
yang memenuhi semua kendala.
O Optimum adalah usaha memakasimalkan atau minimalkan

P Proportionality (proporsionalitas) yaitu adanya proporsionalitas

dalam fungsi tujuan dan fungsi kendala
Primal adalah solusi pada persoalan semula
R Redundancy. Constraint yang tidak mempengaruhi feasible
region disebut redundant conctraint
U Unboundedness adalah suatu kondisi dimana area layak tidak
terbatas

176