PROGRAM LINIER

Program Linier merupakan metode matematik dalam mengalokasikan sumberdaya yang

langka untuk mencapai tujuan tunggal seperti memaksimumkan keuntungan atau
meminimumkan biaya. Program Linier banyak diterapkan dalam membantu menyelesaikan
masalah ekonomi, industri, militer, sosial dan lain-lain.
Persoalan program linier adalah suatu persoalan untuk menentukan besarnya masing-masing
nilai variabel (variable pengambilan keputusan) sedemikian rupa sehingga nilai fungsi tujuan
atau objektif (objective function) yang linier menjadi optimum (maksimum atau minimum)
dengan memperhatikan pembatasan-pembatasan (kendala-kendala) yang ada yaitu
pembatasan ini harus dinyatakan dengan ketidaksamaan yang linier (linear inequalities)
Suatu persoalan disebut persoalan program linier 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.
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 (linier 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.
Perumusan Model Persoalan Program Linier
Pada dasarnya secara umum, persoalan program linier dapat dirumuskan dalam suatu
model dasar/model baku/model matematika sebagai berikut :
Menentukan nilai dari X1, X2, X3, ....., Xn sedemikian rupa sehingga :
n
Z = C1 X1 + C2 X2 + .... +Cj Xj +....+Cn Xn =  C jX j (Optimal[maksimum/minimum])
j1

Yang kemudian disebut sebagai Fungsi Tujuan (Objective Function)

dengan pembatasan (Fungsi Kendala/Syarat Ikatan) :
a11 X1 + a12 X2 +.....+a1n Xn ≤ atau ≥ b1 ,
a21 X1 + a22 X2 +.....+a2n Xn ≤ atau ≥ b2,
• • • •
• • • •
• • • •
am1 X1 + am2 X2 +....+ amn Xn ≤ atau ≥ bm,
atau
m n
  a ij X j  atau  bi untuk i = 1, 2, 3, ...., m
i1j1
dan X1 ≥ 0, X2 ≥ 0,...,Xn ≥ 0 atau Xj ≥ 0, dimana j = 1, 2, 3,...., n (syarat non-negatif).
Keterangan :
Ada n macam barang yang akan diproduksi masing-masing sebanyak X1, X2, ...,Xn unit.
Xj = Variabel pengambilan keputusan atau kegiatan yang ingin dicari (misalnya
banyaknya produksi barang yang ke-j, dimana j = 1, 2, ...,n ).
Cj = Parameter yang dijadikan kriteria optimasi atau koefisien variabel pengambilan
keputusan dalam fungsi tujuan (misalnya harga per satuan barang ke-j).
bi = Sumber daya yang terbatas, yang membatasi kegiatan atau usaha yang
bersangkutan disebut juga konstanta atau “nilai sebelah kanan (nsk)” dari kendala
ke-i (misalnya banyaknya bahan mentah ke-i, i= 1, 2, .., m). Ada m macam bahan
mentah, yang masing-masing tersedia b1, b2,...., bm.
aij = Koefisien teknologi variabel pengambilan keputusan (kegiatan yang bersangkutan)
dalam kendala ke-i (misalnya banyaknya bahan mentah ke-i yang digunakan untuk
memproduksi 1 satuan barang.
Contoh Soal:
1. Sebagai contoh dalam memformulasikan permasalahan, berikut ini akan dibahas
perusahaan Krisna Furniture 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 Krisna Furniture 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?
2. Suatu perusahaan akan memproduksi 2 macam barang yang jumlahnya tidak boleh lebih
dari 18 unit. Keuntungan dari kedua produk tersebut masing-masing adalah Rp. 750,- dan
Rp. 425,- per unit. Dari survey terlihat bahwa produk I harus dibuat sekurang-kurangnya
5 unit sedangkan produk II sekurang-kurangnya 3 unit. Mengingat bahan baku yang ada
maka kedua produk tersebut dapat dibuat paling sedikit 10 unit. Tentukan banyaknya
produk yang harus dibuat untuk mendapatkan keuntungan yang maksimum ?
3. Sebuah pabrik obat menyediakan 2 jenis campuran A dan B. Bahan-bahan dasar yang
terkandung dalam tiap kg campuran A dan B adalah sebagai berikut:
Bahan Dasar
Bahan 1 Bahan 2
Campuran A 0,4 kg 0,6 kg
Campuran B 0,8 kg 0,2 kg
Dari campuran A dan B hendak dibuat campuran C. Campuran C ini sekurang-kurangnya
mengandung bahan-1 sebanyak 4 kg dan bahan-2 sebanyak 3 kg. Harga tiap kg campuran
A adalah Rp. 20.000,00 dan tiap kg campuran B adalah Rp.10.000,00. Berapakah
campuran A dan B harus dibeli supaya biaya total pembuatan campuran C semurah-
murahnya dan berapa biaya yang harus dikeluarkan ?
Pemecahan:
1. Misalkan akan diproduksi meja sebanyak X1 unit dan akan diproduksi kursi sebanyak X2
unit.
a. Fungsi Tujuan : Memaksimalkan Z = $7 X1 + $5 X2
b. Fungsi Kendala:
 Waktu pembuatan : 4 X1 + 3 X2 ≤ 240 jam/minggu
 Waktu pengecatan : 2 X1 + X2 ≤ 100 jam/minggu
c. Syarat non negative : X1 ≥ 0, X2 ≥ 0
2. Misalkan akan diproduksi produk I sejumlah X unit dan akan diproduksi produk II
sejumlah Y unit.
a. Fungsi tujuan : Memaksimalkan Z = Rp. 750 X + Rp. 425 Y
b. Fungsi Kendala :
 X + Y ≤ 18 unit
 X ≥ 5 unit
 Y ≥ 3 unit
 X + Y ≥ 10 unit
c. Syarat Non Negatif : X ≥ 0, Y ≥ 0
 PENYELESAIAN PERSOALAN PROGRAM LINIER
Setelah dapat membuat Model Matematika (merumuskan) persoalan Program Linier, maka
untuk menentukan penyelesaian Persoalan Program Linier dapat menggunakan 2 metode,
yaitu: Metode Grafik dan Metode Simpleks.
1. Metode Grafik
Penyelesaian masalah program Linier dengan menggunakan metode grafis pada
umumnya mengikuti langkah-langkah sebagai berikut :
1. Merumuskan masalah asli menjadi model matematika yang sesuai dengan syarat-
syarat yang diperlukan dalam model Program Linier, yaitu mempunyai fungsi tujuan,
fungsi kendala, syarat ikatan non-negatif.
2. Kendala-kendala yang ada digambar hingga dapat diperoleh daerah penyelesaian
(Daerah yang Memenuhi Kendala (DMK)/Wilayah Kelayakan)/Daerah Fisibel yang
titik-titik sudutnya diketahui dengan jelas.
3. Nilai fungsi sasaran (fungsi tujuan) dihitung di setiap titik sudut daerah penyelasaian
(DMK).
4. Dipilih nilai yang sesuai dengan fungsi tujuan (kalau memaksimumkan berarti yang
nilainya terbesar dan sebaliknya).
5. Jawaban soal asli sudah diperoleh. Catatan : Metode Grafik hanya dapat digunakan
dalam pemecahan masalah program linier yang ber “dimensi” : 2 x n atau m x 2,
karena keterbatasan kemampuan suatu grafik dalam “menyampaikan” sesuatu
(sebenarnya grafik 3 dimensi dapat digambarkan, tetapi sangat tidak praktis).
Contoh Soal :
“PT. Rakyat Bersatu” menghasilkan 2 macam produk. Baik produk I maupun produk II setiap
unit laku Rp. 3000,-. Kedua produk tersebut dalam proses pembuatannya perlu 3 mesin.
Produk I perlu 2 jam mesin A, 2 jam mesin B, dan 4 jam mesin C. Produk II perlu 1 jam
mesin A, 3 jam mesin B, dan 3 jam mesin C. Tersedia 3 mesin A yang mampu beroperasi 10
jam per mesin per hari, tersedia 6 mesin B yang mampu beroperasi 10 jam per mesin per hari,
dan tersedia 9 mesin C yang mampu beroperasi 8 jam per mesin per hari. Berikan saran
kepada pimpinan “PT. Rakyat Bersatu” sehingga dapat diperoleh hasil penjualan yang
maksimum ! Dan berapa unit produk I dan produk II harus diproduksi ?
Jawab :
Merumuskan permasalahan Program Linier ke dalam model Matematika :
Misalkan : Akan diproduksi produk I sejumlah X1 unit dan produk II akan diproduksi
sejumlah X2 unit.
Maka Fungsi tujuannya adalah :
Mamaksimumkan : Z = 3000 X1 + 3000 X2
Harga Jual Per -
MA MB MC
unit
Produk I 2 jam 2 jam 4 jam Rp. 3.000
Prosuk II 1 jam 3 jam 3 jam Rp. 3000
Jumlah Mesin 3 buah 6 buah 9 buah
Lama Operaasi 10 jam/mesin 10 jam/mesin 8 jam/mesin Memaksimalkan
Total Lama
30 jam 60 jam 72 jam
Operasi
Keterangan : Lama operasi adalah dalam jam/hari/mesin.
Total waktu operasi adalah sama dengan jumlah mesin x lama operasi (dalam
jam/hari/tipe mesin).
Syarat Ikatan (fungsi Kendala):
2 X1 + X2  30 ...................... i)
2 X1 + 3X2  60 ......................ii)
4 X1 + 3X2  72 ......................iii)
dan X10, X2  0 (Syarat Non Negatif)
*) Menggambar fungsi-fungsi kendala sehingga diperoleh daerah penyelesaian
(Daerah yang Memenuhi Kendala/Wilayah kelayakan). Titik potong-titik
potong dari ketidaksamaan fungsi kendalanya adalah :
a). Untuk persamaan 2X1 + X2 = 30 ….. (i), titik potong dengan sumbu-X1 jika
X2 = 0 : 2X1 + 0 = 30 diperoleh X1 = 15 maka titik potong dengan sumbu-X1
adalah (15,0).
Sedangkan titik potong dengan sumbu-X2 jika X1 = 0 : 0 + X2 = 30
diperoleh X2 = 30 maka titik potong dengan sumbu-X2 adalah (0,30).
b). Untuk persamaan 2X1 + 3X2 = 60 ....(ii), titik potong dengan sumbu-X1 jika
X2 = 0 : 2X1 + 0 = 60 diperoleh X1 = 30 maka titik potong dengan sumbu-X1
adalah (30,0).
Sedangkan titik potong dengan sumbu-X2 jika X1 = 0 : 0 + 3X2 = 60
diperoleh X2 = 20 maka titik potong dengan sumbu-X2 adalah (0,20).
c). Untuk persamaaan 4X1 + 3X2 = 72 ....(iii), titik potong dengan sumbu-X1 jika
X2 = 0 : 4X1 + 0 = 72 diperoleh X1 = 18 maka titik potong dengan sumbu-X1
adalah (18,0). Sedangkan titik potong dengan sumbu-X2 jika X1 = 0 :
0 + 3X2 = 72 diperoleh X2 = 24 maka titik potong dengan sumbu-X2 adalah
(0,24).

Daerah Fisibel (Wilayah Kelayakan / Daerah yang Memenuhi Kendala (DMK))

adalah daerah yang merupakan irisan dari daerah yang memenuhi kendala :
1). 2X1 + X2 ≤ 30,
2). 2X1 + 3X2 ≤ 60 ,
3). 4X1 + 3X2 ≤ 72,
4). X1 ≥ 0;
5). X2 ≥ 0
Jadi daerah yang memenuhi ke-5 daerah tersebut terletak di dalam daerah yang
dibatasi oleh titiktitik O(0,0), A(15,0), D(0,20), titik B yaitu titik potong antara
garis 2X1 + X2 = 30 dan garis 4X1 + 3X2 = 72 , dan titik C adalah titik potong
antara garis 2X1 + 3X2 = 60 dan garis 4X1 + 3X2 = 72.
Adapun cara menghitung titik B dan C tersebut dengan menggunakan metode
Eliminasi dan Substitusi, sebagai berikut:
*) Titik B perpotongan antara garis 2X1 + X2 = 30 dan garis 4X1 + 3X2 = 72,
dengan mengeliminasi X1, dapat dihitung :
4X1 + 2X2 = 60 ........i)
4X1 + 3X2 = 72 ….....iii) _
− X2 = − 12 → X2 = 12
Untuk X2 = 12 disubstitusikan ke persamaan 2X1 + X2 = 30 sehingga :
2X1 + 12 = 30 → X1 = 9 maka titik B adalah (9,12)
*) Titik C perpotongan antara garis 2X1 + 3X2 = 60 dan garis 4X1 + 3X2 = 72,
dengan mengeliminasi X2, dapat dihitung :
2X1 + 3X2 = 60 ............ii)
4X1 + 3X2 = 72 ............iii) _
− 2X1 = − 12 → X1 = 6
Untuk X1 = 6 disubstitusikan ke persamaan 2X1 + 3X2 = 60 sehingga :
12 + 3X2 = 60 → X2 = 16 maka titik C adalah (6,16)
Daerah penyelesaian (Daerah yang Memenuhi Kendala/Wilayah Kelayakan)
adalah daerah OABCD yang titik-titik sudutnya adalah : O(0,0), A(15,0),
B(9,12), C(6,16), dan D(0,20).
*) Penyelesaian dari soal diatas adalah menghitung nilai fungsi sasaran
(Z = 3000 X1 + 3000 X2) di setiap titik sudut-titik sudut Daerah yang
Memenuhi Kendala, sehingga:
di titik O (0,0) → Z (0,0) = 3000. (0) + 3000.(0) = 0,
di titik A (15,0)→ Z (15,0) = 3000.(15) + 3000.(0) = 45.000,00
di titik B (9,12) → Z (9,12) = 3000.(9) + 3000.(12) = 63.000,00
di titik C (6,16)→ Z(6,16) = 3000.(6) + 3000.(16) = 66.000,00
di titik D (0,20)→ Z(0,20) = 3000.(0) + 3000.(20) = 60.000,00
*) Fungsi Tujuan adalah mencari nilai maksimumnya sehingga nilai yang
sesuai adalah terletak pada titik C(6,16) yaitu dengan nilai fungsi tujuannya
Rp. 66.000,00
*) Sehingga agar diperoleh laba yang maksimum maka Pimpinan ”PT. Rakyat
Bersatu” harus memproduksi Produk I sebanyak 6 unit dan Produk II
sebanyak 16 unit, sehingga mendapat laba maksimum sebesar Rp.66.000,00.
Soal-soal Latihan
1. Sebuah indrusti kecil memproduksi dua jenis barang A dan B dengan memakai dua jenis
mesin M1 dan M2. Untuk membuat barang A, mesin M1 beroperasi selama 2 menit dan
mesin M2 beroperasi selama 4 menit. Untuk membuat barang B, mesin M1 beroperasi
selama 4 menit dan mesin M2 beroperasi selama 2 menit. Mesin M1 dan M2 masing-
masing beroperasi tidak lebih 8 jam tiap hari. Keuntungan bersih untuk setiap barang A
adalah Rp. 250 dan untuk barang B adalah Rp.500.
Berapakah jumlah barang A dan B harus diproduksi agar keuntungannya yang sebesar-
besarnya dan besarnya keuntungan tersebut !
2. Sebuah industri memiliki sumber daya berupa mesin, tenaga kerja dan bahan baku
masingmasing adalah sebagai berikut : bahan baku sebanyak 200 unit dan tenaga kerja
yang dapat dikaryakan selama 180 jam, mesin dapat beroperasi selama 108 jam. dengan
menggunakan sumber daya diatas industri tersebut akan memproduksi produk I dan
produk II, dengan ketentuan sebagai berikut :
Sumber daya yang dibutuhkan
Produk Keuntungan Bersih
Bahan Baku Tenaga Kerja Mesin
A 5 3 2 8
B 4 6 3 20
Tujuan sang industriawan adalah memaksimumkan keuntungan bersih perusahaannya.
Selesaikan permasalahan Program Linier diatas agar tujuan sang industriawan tercapai !
3. Sebuah pabrik baku akan memproduksi buku jenis polos dan buku jenis bergaris. Dalam
satu hari pabrik itu paling banyak memproduksi 1000 buku. Dari bagian penjualan
diperoleh keterangan bahwa tiap hari terjual tidak lebih dari 800 buku polos dan 600
buku bergaris. Keuntungan tiap buku jenis polos adalah Rp.100,00 dan bergaris adalah
Rp.150,00.
Berapakah keuntungan bersih sebesar-besarnya yang dapat diperoleh tiap hari ? Berapa
banyak buku polos dan bergaris yang harus diproduksi tiap hari !
4. Selesaikan Persoalan Program linier Berikut ini:
Memaksimumkan Z = 5000 X + 4000 Y
Fungsi Kendala:
a). 10 X + 15 Y ≤ 150 d). X − 3 Y ≤ 0
b). 20 X + 10 Y ≤ 160 e). X + Y  6
c). 30 X + 10 Y  135 dan X  0, Y  0
5. Selesaikan Persoalan Program linier Berikut ini :
Meminimumkan Z = 20 X + 30 Y
Fungsi Kendala:
a). 2 X + Y  10 d). X − 8 Y ≤ 0
b). X + 2 Y ≤ 14 e). X ≤ 8
c). X + 4 Y  12 dan X  0, Y  0

Persiapan Metode Simpleks

Untuk menyelesaikan Persoalan Program Linier dengan menggunakan Metode Simpleks,
sebelumnya perlu memperhatikan beberapa hal sebagai berikut:
1. Mengubah semua kendala ke dalam bentuk persamaan dengan menambahkan variable
slack (S), mengurangkan dengan variabel surplus (S) dan menambah variabel buatan (V),
sehingga dari fungsi kendala yang ada akan menghasilkan system persamaan linier yang

dapat dinyatakan ke dalam bentuk : AX = B (dimana A = [aij], X = [xj], B = [bi] adalah

matriks).
Contoh :
Fungsi Kendala:
a). 4X1 + 3X2 ≤ 240 diubah menjadi persamaan menjadi : 4X1 + 3X2 + s1 = 240
b). 2X1 + X2 ≤ 100 diubah menjadi persamaan menjadi : 2X1 + X2 + s2 = 100
Kedua kendala di atas jika dinyatakan ke dalam bentuk perkalian matriks AX = B
menjadi:
 X1 
 
 4 3 1 0  X 2   240 
   
 2 1 0 1  s1   100 
s 
 2

A = [aij] X = [xj] B = [bi]

2. Menambahkan semua variable slack (S) yang ada ke dalam fungsi tujuan dengan
koefisien nol (0).
Contoh :
Memaksimumkan z = 7X1 + 5X2 + 0s1 + 0s2
Apabila fungsi tujuan tersebut dinyatakan ke dalam bentuk perkalian matriks : Z = CX
adalah sebagai berikut:
  X1 
 
z = 7 5 0 0 2 
X
 s1 
s 
 2
3. Mengidentifikasi matriks Identitas (In) pada matriks A. Dalam mengidentifikasi matriks
identitas dalam matriks A, komponen matriks identitas dibaca secara matriks kolom dan
tidak selalu urut.
Contoh :
1 0 0 1 0
     
I3 =  0 1 0  , komponen matriks identitas secara matriks kolom adalah :  0  ,  1 
0 0 1
  0 0

0
 
dan  0  .
1
 
4. Membentuk matriks Identitas dengan menambahkan variable semu (V). Jika dalam
matriks A belum tersusun (terbentuk) matriks identitas, maka matriks identitas dapat
disusun dengan menambahkan variabel semu pada fungsi kendala.
Contoh :
Memaksimumkan Z = 750 X + 425 Y
Fungsi Kendala:
a). X + Y ≤ 18 b). X  5 c). Y  3 d). X + Y  10 , dan X  0, Y  0
Jika fungsi kendala persoalan tersebut dinyatakan dalam persamaan akan menjadi :
a). X + Y + s1 = 18
b). X − s2 = 5
c). Y − s3 = 3
d). X + Y − s4 = 10
Apabila dinyatakan dalam bentuk AX = B, akan menjadi:
X
1 1 1 0 0 0  Y  18 
   
1 0 0  1 0 0  s1   5 

0 1 0 0  1 0  s 2   3 
1
 1 0 0 0  1 s3  10 
 
 s4 
 Dalam matriks A di atas belum tersusun matriks Identitas (I4), karena komponen
1
 
0
penyusun matriks Identitas (I4) belum lengkap. Yang tersusun baru komponen   ,
0
0
 
0 0 0
     
1 0 ,  0  , harus dibentuk dengan menambahkan variabel V1
Sehingga komponen   ,
0 1 0
0 0 1
     
pada kendala ke-2, V2 pada kendala ke-3, dan V3 pada kendala ke-4, sehingga fungsi
kendala di atas dapat dinyatakan dalam bentuk sebagai berikut:
a). X + Y + s1 = 18
b). X − s2 + v1 = 5
c). Y − s3 + v2= 3
d). X + Y − s4 + v3 = 10
dan apabila dinyatakan dalam bentuk AX = B menjadi:
X
 
Y
0  1  18 
s
1 1 1 0 0 0 0 0
   
  s
1 0 0 1 0 0 1 0 0  2   5 
s 
0 1 0 0 1 0 0 1 0  3   3 
1 0 0 0 1 1  4  10 
s
 1 0 0
 v1 
 v2 
v 
 3
5. Menambahkan semua variabel semu yang ada ke dalam fungsi tujuan dengan koefisien ±
M (dimana M = Bilangan yang cukup besar). Jika fungsi tujuan memaksimalkan maka
koefisien dari V pada fungsi tujuan adalah −M, dan sebaliknya).
Contoh :
Jika fungsi kendala dinyatakan seperti pada catatan 4 di atas, maka fungsi tujuan
Memaksimumkan Z = 750 X + 425 Y dapat dinyatakan ke dalam bentuk:
Memaksimumkan Z = 750 X + 425 Y + 0s1 + 0s2 + 0s3 + 0s4 − Mv1 − Mv2 − Mv3
Apabila dinyatakan ke dalam notasi matriks menjadi:
 X
 
Y
 s1 
 s2 
Z = 750 425 0 0 0 0  M  M  M  s3 
 
 s4 
 v1 
 v2 
v 
 3
Persoalan Program Linier yang memenuhi ketentuan-ketentuan tersebut di atas akan
menghasilkan Bentuk Kanonik Simpleks.
Soal-soal latihan :
Ubahlah persoalan Program Linier berikut ke dalam Bentuk Kanonik Simpleks:
1. Memaksimumkan Z = 3 X1 + 3 X2
Fungsi Kendala:
a). 2X1 + X2 ≤ 30
b). 2X1 + 3X2 ≤ 60
c). 4X1 + 3X2 ≤ 72, dan X1  0, X2  0
2. Meminimumkan Z = 22 X1 + 6 X2
Fungsi Kendala:
a). 11X1 + 3X2  33
b). 8X1 + 5X2 ≤ 40
c). 7X1 + 10X2 ≤ 70, dan X1  0, X2  0
3. Memaksimumkan Z = 4 X1 + 5 X2
Fungsi Kendala:
a). 5X1 + 4X2 ≤ 200
b). 3X1 + 6X2 = 180
c). 8X1 + 5X2 160, dan X1  0, X2  0
4. Meminimumkan Z = 2 X1 + 3 X2 + 5 X3 + 6 X4
Fungsi Kendala:
a). 2X1 + 4X2 + 6X3 + 2X4  4
b). −2X1 + X2 − X3 + 3X4 ≤ −3, dan X1 0, X2  0, X3  0, X4  0.
5. Memaksimumkan Z = 4 X1 + 2 X2 − X3 + 5 X4
Fungsi Kendala:
a). 3X1 + X2 + 2X3 + 4X4 ≤ 25
b). 2X1 − X2 + X3 + X4  15
c). X1 + 2X2 + 3X3 + X4 = 20, dan X1  0, X2  0, X3  0, X4  0.
 Metode Simpleks Kasus Maksimum
Untuk menyelesaikan Persoalan Program Linier dengan Metode Simpleks untuk fungsi
tujuan memaksimumkan dan meminimumkan caranya berbeda.
Model matematika dari Permasalahan Program Linier dapat dinyatakan dalam bentuk
Sistem Persamaan Linier (AX = B) sebagai berikut :
*) Fungsi Tujuan (Z = CX):
 x1 
 
Z = c1 c 2 .... c n   2 
x
 . 
x 
 n
*) Fungsi Kendala (AX ≤ atau ≥ B):
 a11 a12 ... a1n   x1   b1 
    
 a 21 a 22 ... a 2n   x 2 
 atau   b2 
 ... ... ... ...   .   . 
a    b 
 m1 a m 2 ... a mn   x n   m
Berikut ini langkah-langkah penyelesaian Persoalan Program Linier fungsi tujuan
memaksimumkan dengan Metode Simpleks.
1. Mengubah semua kendala ke Bentuk Kanonik (yang semula menggunakan tanda
pertidaksamaan menjadi persamaan) dengan menambah perubah (variabel) Slack S.
Perubah-perubah slack yang ada dimasukkan (ditambahkan) ke fungsi sasaran dan diberi
koefisien 0.
2. Apakah dalam matriks A = [aij] (pada fungsi kendala) sudah terbentuk Matriks Identitas
(In) ?
2.1 Apabila dalam matriks A sudah terbentuk Matriks Identitas maka disusun tabel
awal simpleks sebagai berikut :
Cj c1 c2 ... cn 0 0 ... -M ...
Ci xj x1 x2 ... xn s1 s2 ... v1 ... b1 R1
c1 x1 a11 a12 ... a1n 1 0 ... 0 ... b2 R2
c2 x2 a21 a22 ... a2n 0 1 ... 0 ... ... ...
... ... ... ... ... ...
cm Xm am1 am2 ... amn 0 0 ... 0 ... bm Rm
Zj Z1 Z2 ... Zn ... ... ... ... ...
Zj-Cj Z1-c1 Z2-c2 ... Zn-cn
 Keterangan :
*) Baris cj diisi dengan para koefisien Fungsi Tujuan (sasaran)
*) Baris xj diisi dengan nama-nama perubah (variabel) yang ada.
*) Kolom xi diisi dengan nama-nama perubah yang menjadi basis (variabel yang
menyusun matriks Identitas) .
*) Kolom ci diisi dengan para koefisien perubah yang menjadi basis
*) Kolom bi diisi dengan para konstanta fungsi kendala (Nilai Sebelah Kanan/NSK).
m
*) Baris Zj diisi dengan rumus Zj =  ci a ij , untuk j = 1, 2, ..., n
i 1
bi
*) Kolom Ri diisi dengan rumus Ri = (aik = elemen-elemen yang berada dalam
a ik
kolom kunci, dan Ri dihitung hanya untuk aik 0) Selanjutnya dilanjutkan ke langkah
3,
2.2 Jika belum terbentuk matriks identitas, maka matriks identitas ditimbulkan
(dimunculkan) dengan menambah perubah semu dan diberi notasi (v). Perubah semu
yang ada dimasukan di fungsi sasaran, sedangkan koefisien dari variabel semu pada
fungsi sasaran diberi nilai (-M), dengan M adalah bilangan yang cukup besar.
Dilanjutkan ke langkah 2.1
3. Penelitian terhadap nilai Zj - Cj. (Tabel sudah maksimum jika semua Zj - Cj ≥ 0).
3.1 Jika untuk semua Zj - Cj ≥ 0 dilanjutkan ke langkah 4,
3.2 Jika ada Zj - Cj < 0, maka dibuat tabel baru dengan cara sebagai berikut :
3.2.1 Menentukan kolom kunci yaitu memilih nilai Zj - Cj yang terkecil. Sebut
dengan Zk - Ck maka kolom ke-k disebut kolom kunci.
3.2.2 Pada kolom ke-k dilakukan pemeriksaan terhadap nilai aik.
[Link] Jika untuk semua aik negatif maka jawab tidak terbatas (Unbounded).
[Link] Jika terdapat aik yang positif hitung nilai Ri, (untuk aik yang positif saja)
kemudian dilanjutkan ke langkah 3.2.3,
3.2.3 Menentukan baris kunci, yaitu dengan memilih nilai Ri yang terkecil (diantara
yang positif) Min{ Ri}, namakan Rr, maka baris ke-r disebut baris kunci.
3.2.4 Kemudian disusun tabel baru sebagai berikut (dimulai dari baris kunci baru):
[Link] Untuk elemen baris r baru = elemen baris r lama dibagi ark , atau
a rj
a rj 
a rk
[Link] Untuk elemen baris i yang lain,
 elemen baris i baru = elemen baris i lama - (aik x elemen baris r baru)
atau a ij  a ij  (a ik x a rj ) .

Kemudian tentukan lagi nilai xi, Ci, Zj , Zj - Cj. Kembali ke langkah 3.

4. Apakah pada tabel terakhir terdapat nilai vk yang positip ?
4.1 Jika ada nilai vk yang positif maka soal asli tidak fisibel (Infeasible Solution).
4.2 Jika tidak ada nilai vk yang positif maka akan diperoleh penyelesaian yang
maksimum.
Contoh Soal :
Memaksimumkan : Z = 3X1 + 3X2 (dalam ribuan)
yang memenuhi kendala :
1). 2X1 + X2 ≤ 30
2). 2X1 + 3X2 ≤ 60
3). 4X1 + 3X2 ≤ 72 dan X1 ≥ 0, X2 ≥ 0.
Penyelesaian :
*) Bentuk kanonik :
1). 2X1 + 1X2 + 1S1 + 0S2 + 0S3 = 30
2). 2X1 + 3X2 + 0S1 + 1S2 + 0S3 = 60
3). 4X1 + 3X2 + 0S1 + 0S2 + 1S3 = 72
dan fungsi tujuannya menjadi :
Memaksimumkan : Z = 3X1 + 3X2 + 0S1 + 0S2 +0S3
Bentuk matriksnya adalah sebagai berikut :
 X1   X1 
  30 X 2 
 2 1 1 0 0   X2   
     
 2 3 0 1 0   S1    60  dan Z = 3 3 0 0 0  S1 
 4 3 0 0 1   S2   72   S2 
S   S3 
 3
*) Tabel awal simpleks :
Ci Cj 3 3 0 0 0
Xi Xj X1 X2 S1 S2 S3 bi Ri
0 S1 2 1 1 0 0 30 30
0 S2 2 3 0 1 0 60 20
0 S3 4 3 0 0 1 72 24
Zj 0 0 0 0 0
Zj - Cj -3 -3 0 0 0
*) Menentukan kolom kunci dengan memilih nilai dari min {Zj - Cj}, yaitu pada kolom-1
dan 2 yang nilainya adalah -3 (dapat dipilih salah 1). Dipilih kolom ke-2 sebagai kolom
kunci, sehingga k = 2.
Karena elemen-elemen dalam kolom kunci ada tidak semuanya nol (ada yang positif)
maka dapat ditentukan nilai dari Ri yaitu :
30 60 72
R1 = = 30, R2 = = 20, R3 = = 24
1 3 3
*) Menentukan baris kunci dengan memilih nilai dari Ri yang terkecil dan nilai aik > 0
(positif). Terdapat pada baris yang ke-2 yaitu R2 = 20, sehingga r = 2
*) Membuat tabel baru sebagai berikut : Baris kunci baru (baris 2 yang baru) mempunyai
elemen-elemen :
a 2 a 3 a 0 a 1
a 21  21  , a 22  22   1 , a 23  23   0 , a 24  24  ,
a 22 3 a 22 3 a 22 3 a 22 3
a 0 b 60
a 25  25   0 , b2  2   20
a 22 3 a 22 3
atau elemen-elemen baris 2 baru = elemen-elemen baris 2 lama dibagi dengan 3
elemen-elemen baris 2 baru = [ 2 3 0
1 0 60 ] = [ 2/3 1 0 1/3 0 20 ]
3
Untuk baris yang lain (baris ke-1 dan 3)  âij = aij - (aik x ârj)
Untuk baris 1 baru Untuk baris 3 baru
â11 = a11 - (a12 x a21 ) = 2 - (1 x (2/3)) = 4/3 â31 = a31 - (a32 x a21 ) = 4 - (3 x(2/3)) = 2
â12 = a12 - (a12 x a22 ) = 1 - (1 x 1) = 0 â32 = a32 - (a32 x a22 ) = 3 - (3 x1) = 0
â13 = a13 - (a12 x a23 ) = 1 - (1 x 0) = 1 â33 = a33 - (a32 x a23 ) = 0 - (3 x0) = 0
â14 = a14 - (a12 x a24 ) = 0 - (1 x(1/3)) = -1/3 â34 = a34 - (a32 x a24 ) = 0 - (3 x(1/3)) = -1
â15 = a15 - (a12 x a25 ) = 0 - (1 x0) = 0 â35 = a35 - (a32 x a25 ) = 1 - (3 x0) = 1
b1 = b1 - (a12 x b2 ) = 30 - (1 x20) = 10 b3 = b3 - (a12 x b2 ) = 72 - (3 x20) = 12
Atau dengan cara lain sebagai berikut :
Baris ke-1 baru :
2 1 1 0 0 30
1 x [ 2/3 1 0 1/3 0 20 ] _
4/3 0 1 -1/3 0 10
Baris ke-3 baru
4 3 0 0 1 72
3 x [ 2/3 1 0 1/3 0 20 ] _
2 0 0 -1 1 12
 Ci Cj 3 3 0 0 0
Xi Xj X1 X2 S1 S2 S3 bi Ri
0 S1 4/3 0 1 -1/3 0 10 15/2
3 X2 2/3 1 0 1/3 0 20 30
0 S3 2 0 0 -1 1 12 6
Zj 2 3 0 1 0 60
Zj - Cj -1 0 0 1 0
elemen-elemen baris 3 baru = [ 2 0 0
-1 1 12 ] = [ 1 0 0 -1/2 1/2 6 ]
2
*) Karena nilai dari Zj - Cj masih ada yang negatif maka tabel belum maksimum, sehingga
harus ditentukan kolom kunci, baris kunci dan perhitungan untuk menyusun tabel baru
seperti langkah di atas, dan diperoleh tabel baru sebagai berikut :
Ci Cj 3 3 0 0 0
Xi Xj X1 X2 S1 S2 S3 bi Ri
0 S1
3 X2
3 X1 1 0 0 -1/2 1/2 6
Zj
Zj - Cj
Baris ke-1 baru :
4/3 0 1 -1/3 0 10
4/3x[ 1 0 0 -1/2 1/2 6 ] _
0 0 1 1/3 -2/3 2
Baris ke-2 baru :
2/3 1 0 1/3 0 20
2/3x[1 0 0 -1/2 1/2 6]_
0 1 0 2/3 -1/3 16
Ci Cj3 3 0 0 0
Xi Xj X1 X2 S1 S2 S3 bi Ri
0 S1 0 0 1 1/3 -2/3 2
3 X2 0 1 0 2/3 -1/3 16
3 X1 1 0 0 -1/2 1/2 6
Zj 3 3 0 1/2 1/2 66
Zj - Cj 0 0 0 1/2 1/2
*) Karena semua nilai dari Zj - Cj ≥ 0 maka tabel sudah maksimum dengan nilai dari X1 = 6
dan X2 = 16 dan Zmaks adalah 66.
Sehingga hasil akhir dari tabel simpleks persoalan di atas adalah sebagai berikut:
 Ci Cj 3 3 0 0 0
Xi Xj X1 X2 S1 S2 S3 bi Ri
0 S1 2 1 1 0 0 30 30
0 S2 2 3 0 1 0 60 20
0 S3 4 3 0 0 1 72 24
Zj 0 0 0 0 0
Zj - Cj -3 -3 0 0 0
0 S1 4/3 0 1 -1/3 0 10 15/2
3 X2 2/3 1 0 1/3 0 20 30
0 S3 2 0 0 -1 1 12 6
Zj 2 3 0 1 0 60
Zj - Cj -1 0 0 1 0
0 S1 0 0 1 1/3 -2/3 2
3 X2 0 1 0 2/3 -1/3 16
3 X1 1 0 0 -1/2 1/2 6
Zj 3 3 0 1/2 1/2 66
Zj - Cj 0 0 0 1/2 1/2

Soal-soal latihan :
Selesaikan Persoalan Program Linier berikut dengan Metode Simpleks.
1. Memaksimumkan Z = 2 X1 + X2
Fungsi Kendala :
a. X1 + 2 X2 ≤ 80
b. 3X1 + 2 X2 ≤ 120
c. 2X1 ≤ 360 dan X1 ≥ 0, X2 ≥ 0.
2. Memaksimumkan Z = 2 X1 + 3X2
Fungsi Kendala :
a. 5X1 + 6X2 ≤ 60
b. X1 + 2X2 ≤ 16
c. X1 ≤ 10
d. X2 ≤ 6, dan X1 ≥ 0, X2 ≥ 0.
3. Memaksimumkan Z = 2 X1 − 7X2
Fungsi Kendala :
a. −2X1 + 3X2 = 3
b. 4X1 + 5X2 ≥ 16
c. 6X1 + 7X2 ≤ 3
 d. 4X1 + 8X2 ≥ 5, dan X1 ≥ 0, X2 ≥ 0.
4. Memaksimumkan Z = 4 X1 + 5 X2
Fungsi Kendala :
a). 5X1 + 4X2 ≤ 200
b). 3X1 + 6X2 = 180
c). 8X1 + 5X2  160, dan X1 0, X2  0
5. Memaksimumkan Z = 4 X1 + 2 X2 − X3 + 5 X4
Fungsi Kendala:
a). 3X1 + X2 + 2X3 + 4X4 ≤ 25
b). 2X1 − X2 + X3 + X4  15
c). X1 + 2X2 + 3X3 + X4 = 20, dan X1  0, X2  0, X3  0, X4  0
 Metode Simpleks Kasus Minimum

Contoh Soal :
Meminimumkan : Z = 40 X1 + 80X2
dengan syarat ikatan :
a). X1 + X2 ≥ 4
b). X1 + 3X2 ≥ 6 dan X1 ≥ 0, X2 ≥ 0
Penyelesaian :
*) Bentuk Kanonik :
a). X1 + X2 - 1S1 + 0S2 + 1V1 + 0V2 = 4
b). X1 + 3X2 + 0S1 - 1S2 + 0 V1 + 1V2 = 6
Meminimumkan : Z = 40 X1 + 80X2 + 0S1 + 0S2 + MV1 + MV2
*) Tabel simpleks :
Cj 40 80 0 0 M M
Ci Xi Xj X1 X2 S1 S2 V1 V2 bi Ri
M V1 1 1 -1 0 1 0 4 4
M V2 1 3 0 -1 0 1 6 2
Zj 2M 4M -M -M M M 10 M
Zj - Cj 2M-40 4M-80 -M -M 0 0
M V1 2/3 0 -1 1/3 1 -1/3 2 3
80 X2 1/3 1 0 -1/3 0 -1/3 2 6
Zj (2M+80)/3 80 -M (M-80)/3 M (80-M)/3 2M+160
Zj - Cj (2M-40)/3 0 -M (M-80)/3 0 (80-4M)/3
40 X1 1 0 -3/2 1/2 3/2 -1/2 3
80 X2 0 1 1/2 -1/2 -1/2 1/2 1
Zj 40 80 -20 -20 20 20 200
Zj - Cj 0 0 -20 -20 20-M 20-M
Karena semua Zj – Cj ≤ 0, maka tabel sudah minimal, dengan nilai X1 = 3, dan X2 = 1,
dan Zminimalnya = 200.
Soal-soal Latihan :
Selesaikan Persoalan Program Linier berikut dengan Metode Simpleks.
1. Meminimumkan F = 22 X1 + 6 X2
Fungsi Kendala :
a. 11X1 + 3 X2 ≥ 33
b. 8X1 + 5X2 ≤ 40
c. 7X1 + 10X2 ≤ 70 dan X1 ≥ 0, X2 ≥ 0,
2. Meminimumkan Z = 20 X + 30 Y
Fungsi Kendala:
a). 2 X + Y  10 d). X − 8 Y ≤ 0
b). X + 2 Y ≤ 14 e). X ≤ 8
c). X + 4 Y 12 dan X  0, Y  0
3. Meminimumkan Z = 6X1 + 8 X2
Fungsi Kendala:
a). 3X1 + X2  4
b). 5X1 + 2X2 ≤ 10
c). X1 + 2X2 = 3 dan X1 ≥ 0, X2 ≥ 0,
4. Meminimumkan Z = 2 X1 + 3 X2 + 5 X3 + 6 X4
Fungsi Kendala:
a). 2X1 + 4X2 + 6X3 + 2X4  4
b). −2X1 + X2 − X3 + 3X4 ≤ −3, dan X1  0, X2  0, X3  0, X4  0.
5. Meminimumkan Z = 4 X1 + 2 X2 − 2 X3 + 5 X4
Fungsi Kendala:
a). 3X1 + X2 + 2X3 + 4X4 ≤ 25
b). 2X1 − X2 + X3 + 2X4  15,
c). X1 + 2X2 + 3X3 + X4 = 20, dan X1  0, X2  0, X3  0, X4  0.
 Analisis Primal - Dual
Setiap persoalan program linier selalu mempunyai dua macam analisis, yaitu : analisis
primal dan analisis dual yang biasanya disebut analisis primal-dual. Untuk menjelaskan
hubungan antara Primal dengan Dual akan ditunjukan dengan contoh kasus di bawah ini:
PT. Maju Jaya adalah sebuah perusahaan yang menghasilkan dua macam produk yaitu A
dan B. Setiap Produk A menghasilkan laba Rp. 40,- dan Produk B Rp. 60,-. Kedua macam
produk tersebut harus diproduksi melalui dua tahap proses yaitu proses I dan proses II.
Kapasitas dan waktu proses bagi kedua macam produk tersebut adalah sebagai berikut :
Waktu Proses Kapasitas per bulan
Proses
A B (jam)
I 3 2 2.000
II 1 2 1.000
Model matematika Kasus diatas adalah :
Fungsi Tujuan : Memaksimumkan : Z = 40A + 60B,
Fungsi Kendala :
1. 3A +2B ≤ 2000
2. A + 2B ≤ 1000,
3. A, B ≥ 0,
Model matematika diatas disebut model Primal. Dual pada dasarnya adalah masalah
penentuan harga, yaitu :
Harga dari sumber-sumber yang dipergunakan untuk berproduksi secara optimal, dimana
harga tersebut merupakan nilai minimum sehingga dapat dipergunakan sebagai bahan
pertimbangan untuk menambah atau mengurangi sumber-sumber tersebut secara tepat.
Misalkan C dan D sebagai biaya sewa per jam yang harus dibebankan kepada proses I
dan II. Karena jumlah kapasitas yang tersedia untuk proses I adalah 2000 jam dan proses II
1000 jam, maka biaya sewa total untuk kedua macam proses tersebut adalah :
F = 2000C + 1000D.
Selagi F merupakan jumlah biaya sewa kedua macam proses tersebut maka manajeman
PT. Maju Jaya tersebut berusaha untuk meminimumkannya. Pandang jika model Primal
sebagai pihak penjual yang ingin memaksimumkan laba, di sisi lain model Dual sebagai pihak
pembeli yang menginginkan harga pembelian yang minimum. Setiap unit produk A
memerlukan waktu 3 jam pada proses I dan 1 jam pada prose II, sehingga biaya untuk
menghasilkan setiap unit produk A adalah 3C + 1D.
 Dipandang dari pihak pembeli tentu saja harga tesebut tidak boleh lebih rendah dari
sumbangan laba yang akan diberikan oleh produk A terhadap penjualan yaitu sebesar Rp. 40,-
(bila penjual mendapat laba Rp. 40,- untuk setiap penjualan produk A, maka tentu saja
pembeli menginginkan agar harga yang ia bayar untuk biaya pemrosesan produk tersebut
paling sedikit harus sama dengan laba yang diperoleh penjual yaitu sebesar Rp. 40,-).
Sehingga biaya untuk memroses setiap unit produk A adalah
3C + 1D ≥ 40.
Dengan cara yang sama biaya untuk memroses setiap unit produk B adalah 2C +2D ≥ 60
dan selanjutnya karena harga tidak mungkin negatif maka C ≥ 0 dan D ≥ 0.
Asumsi Dasar :
Untuk dapat menyusun suatu persoalan primal Program Linier ke dalam bentuk dual, maka
selalu harus dirumuskan terlebih dahulu ke dalam bentuk kanonik.

 Untuk persoalan maksimasi, maka semua rumusan fungsi kendala mempunyai tanda
lebih kecil dari pada atau sama dengan ( ≤ ).

 Untuk persoalan minimasi maka tanda fungsi syarat ikatannya harus lebih besar dari
pada atau sama dengan ( ≥ ) . ( Ingat bahwa tidak perlu semua konstanta atau nilai
sebelah kanan (nsk) fungsi kendala yang bersangkutan harus selalu non-negatif dalam
suatu rumusan yang berbentuk kanonik).

 Jika suatu persoalan dalam rumusan Program Linier mempunyai fungsi kendala
kesamaan (nilai nsk-nya bertanda sama dengan), maka fungsi kendalanya tersebut
dapat ditukar atau diganti dengan dua fungsi lainnya, yang pertama, bertanda “lebih
kecil dari pada atau sama dengan ( ≤ )” dan yang kedua, bertanda “lebih besar dari-
pada atau sama dengan ( ≥ )”. Salah satu diantara kedua fungsi kendala lain tersebut
(dipilih salah satu), kemudian diambil, dan kalikan dengan (−1) untuk mendapatkan
fungsi kendala yang sesuai dengan aturan yang diminta oleh bentuk kanonik tersebut
Model Umum Persoalan Primal - Dual
Bentuk Primal:
n
Maksimumkan : z =  C jX j
j1
n
syarat ikatan :  a ij X j  bi , untuk i = 1, 2, 3, ...,m.
j1
dan Xj ≥ 0, j = 1, 2, ... , n
Kalau akan dinyatakan menjadi Bentuk Dual :
 m
Minimumkan : F =  bi Yi
i 1
m
syarat ikatan  a ij Yi  C j , untuk j= 1, 2, 3, ...,n.
i 1
dan Yi ≥ 0, i = 1, 2, ... , m
n * m *
dimana : zoptimal =  C jX j adalah sama dengan Foptimal =  bi Y i
j1 i 1

Aturan umum dalam perumusan persoalan Program Linier menyangkut Bentuk Primal dan
Dual adalah :
Bentuk Primal Bentuk Dual
Memaksimumkan fungsi tujuan Meminimumkan fungsi tujuan, dan sebaliknya.
Koefisien fungsi tujuan (Cj ) Nilai Sebelah Kanan (NSK) fungsi kendala
NSK fungsi kendala primal-primal (bi ) Koefisien fungsi tujuan
Koefisien peubah ke-j Koefisien kendala ke-j
Koefisien kendala ke- Koefisien peubah ke-i

Peubah ke-j yang positif (≥ 0) Kendala ke-j dengan tanda ketidaksamaan “lebih
besar daripada atau sama dengan “ (≥).
Peubah ke-j tandanya tidak dibatasi Kendala ke-j yang bertanda sama dengan
Kendala ke-i yang bertanda sama dengan Peubah ke-i tandanya tidak dibatas
Kendala ke-i yang bertanda ketidaksamaan (≤) Peubah ke-i yang positif (≥)
Contoh Soal :
Andaikan terdapat suatu persoalan Program Linier sebagai berikut :
Memaksimumkan : Z = 10X1 + 6X2 ........ (1),
Syarat ikatan :
a). 2X1 + 3X2 ≤ 90 .......... (2)
b). 4X1 + 2X2 ≤ 80 .......... (3)
c). X2 ≥ 15 .......... (4)
d). 5X1 + X2 = 25 .......... (5)
dan X1 , X2 ≥ 0
Ubahlah ke dalam Bentuk Dualnya
Penyelesaian :
Langkah 1,
Transfomasikan ke dalam bentuk kanonik primal ( karena fungsi tujuannya memaksimumkan
maka tanda ketidaksamaannya dibuat ≤ ). Manipulasi dilakukan pada rumus (4) dan (5)
dengan berikut :
*) Kalikan rumus (4) dengan (−1) didapatkan :
 − X2 ≤ −15
*) Ganti rumus (5) menjadi ketidaksamaan :
5X1 + X2 ≤ 25 (5a) dan 5X1 + X2 ≥ 25 (5b)
dan rumus (5b) dikalikan dengan (-1) didapat :
− 5X1 − X2 ≤ −25
Dengan demikian diperoleh bentuk kanonik primal menjadi :
Memaksimumkan : Z = 10X1 + 6X2
Syarat ikatan :
a). 2X1 + 3X2 ≤ 90
b). 4X1 + 2X2 ≤ 80
c). − X2 ≤ −15
d). 5X1 + X2 ≤ 25
e). − 5X1 − X2 ≤ −25
dan X1 , X2 ≥ 0
Langkah 2,
Rumuskan bentuk kanonik dari persoalan primal tersebut kedalam bentuk dual, dan diperoleh:
Meminimumkan : F = 90Y1 + 80Y2 − 15Y3 + 25Y4 − 25Y5
syarat ikatan :
a). 2Y1 + 4Y2 − 0Y3 + 5Y4 − 5Y5 ≥ 10
b). 3Y1 + 2Y2 − Y3 + Y4 − Y5 ≥ 6
dan Y1 , Y2 , Y3 , Y4 , Y5 ≥ 0 atau Yi ≥ 0, untuk i = 1, 2, …, 5.
Soal-soal Latihan :
Diketahui Persoalan Primal sebagai berikut, kemudian ubahlah ke dalam Bentuk Dualnya :
1. Meminimumkan Z = 6X1 + 8X2
Dengan syarat ikatan :
3X1 + X2 ≥ 4
5X1 + 2X2 ≤ 10
X1 + 2X2 = 3 dan X1 , X2 ≥ 0
2. Memaksimumkan Z = −X1 + 4X2
Dengan syarat ikatan :
X1 − X2 ≥ 0
− X1 + 2X2 ≤ 2 dan X1 , X2 ≥ 0
3. Meminimumkan Z = 22X1 + 6X2
Dengan syarat ikatan :
11X1 + 3X2 ≥ 33
8X1 + 5X2 ≤ 40
7X1 + 10X2 ≤ 70 dan X1 , X2 ≥ 0
4. Meminimumkan Z = −2X1 + 6X2
Dengan syarat ikatan :
3X1 + 2X2 ≤ 6
X1 − X2 ≥ −1
2X1 − X2 ≥ 2 dan X1 , X2 ≥ 0
Masalah Peubah (Variabel) yang tidak Dibatasi
Jika sebuah peubah Xj tidak dibatasi sebagai perubah non-negatif, maka dapat diganti dengan
dua buah perubah yang baru yaitu Xj+ dan Xj- sehingga :
Xj = Xj+ − Xj- dimana Xj+ ≥ 0 dan Xj- ≥ 0.
Variabel Xj merupakan beda atau sisa dari dua perubah non-negatif Xj+ dan Xj- . Dengan kata
lain Xj merupakan nilai tengah, sedangkan Xj+ dan Xj- adalah perubah deviasi atau simpanan
terhadap perubah nilai tengah atau perubah target.
Contoh :
Andaikan suatu persoalan Program Linier dengan X2 tidak dibatasi syarat non negatif sebagai
berikut :
Maksimumkan Z = 2X1 + 5X2 ........................ (1)
Syarat Ikatan :
3X1 + 2X2 ≤ 6 ........................ (2)
2X1 + 9X2 ≤ 8 ........................ (3)
dan X1 ≥ 0, X2 tidak dibatasi syarat non-negatif.
Penyelesaian :
Perumusan model Program Linier di atas tidak baik karena tidak memenuhi peraturan
Program Linier yang ada, yaitu semua perubah Xj yang menjadi perubah keputusan tidak
boleh negatif. Oleh karena itu X2 disempurnakan menjadi :
X2 = X2+ − X2- dimana X2+ ≥ 0 dan X2- ≥ 0,
maka persoalan diatas menjadi :
Memaksimumkan Z = 2X1 + 5(X2+ − X2- )
Syarat ikatan :
3X1 + 2X2+ − 2X2- ≤ 6
2X1 + 9X2+ − 9X2- ≤ 8
dan X1 ≥ 0, X2+ ≥ 0, X2- ≥ 0.