BAB I

PROGRAM LINEAR

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, indutri, militer,
social dan lain-lain.
1.1 Metode Grafik
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

matematika

masalah asli menjadi model

yang

sesuai

dengan

syarat-

syarat yang diperlukan dalam model Program

Program linear

Linier, yaitu mempunyai fungsi tujuan, fungsi

kendala, syarat ikatan non-negatif.
2. Kendala-kendala yang ada digambar hingga

dapat

diperoleh

(Daerah

daerah

yang

Memenuhi

(DMK)/Wilayah
Fisibelyang

penyelesaian
Kendala

Kelayakan)/Daerah

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"

atau

2,

karena

keterbatasan kemampuan suatu grafik dalam

"menyampaikan" sesuatu (sebenarnya grafik 3
dimensi dapat digambarkan, tetapi sangat tidak
praktis).

Program linear

Contoh Soal :
"PT.

Rakyat

Bersatu"

menghasilkan

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 Xi
unit dan produk II akan diproduksi sejumlah X2
unit.
Maka Fungsi tujuannya adalah : Mamaksimumkan :
Z = 3000 Xi + 3000 X2

Program linear

Ma

Mb

Produk I

2 jam

2 jam

4 jam

Produk II

i jam

3 jam

3 jam

Jumlah Mesin

3 buah

6 buah

Lama Operasi

i0
jam/mesin

Total waktu
Operasi

30 jam

Mc

9
buah
i0
8
jam/mesin jam/mes
in
60 jam
72
jam

Harga jual per

unit
Rp. 3000,Rp. 3000,Memaksimumk
an

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):
2Xi + X2 < 30. i)
2Xi + 3X2 < 60ii)
4Xi + 3X2 < 72iii)
dan Xi > 0; X2 > 0 (Syarat Non Negatif).
*) Menggambar fungsi-fungsi kendala sehingga
diperoleh

daerah

penyelesaian

Memenuhi

Kendala/Wilayah

potong-titik

potong

dari

(Daerah

yang

kelayakan).

Titik

ketidaksamaan

fungsi

kendalanya adalah :

Program linear

a). Untuk persamaan 2Xi + X2 = 30

(i),
titik
potong dengan sumbu-Xi jika X2 = 0 :
2Xi + 0 = 30 diperoleh Xi = i5 maka titik potong
dengan sumbu-Xi adalah (15,0).
Sedangkan titik potong dengan
sumbu-X2 jika Xi = 0 : 0 + X2 = 30
diperoleh X2 = 30 maka titik potong
dengan sumbu-X2 adalah (0,30).
b) .

Untuk persamaan 2Xi + 3X2 =

60 ....(ii), titik potong dengan sumbuXi jika X2 = 0 : 2Xi + 0 = 60

diperoleh Xi = 30 maka titik potong
dengan sumbu-Xi adalah (30,0).
Sedangkan titik potong dengan sumbu-X2 jika Xi
=0:
0 + 3X2 = 60 diperoleh X2 = 20 maka titik
potong dengan sumbu-X2 adalah (0,20).
c) .

Untuk persamaaan 4Xi + 3X2 =

72 ....(iii), titik potong dengan sumbu-Xi

jika X2 = 0 : 4Xi + 0 = 72 diperoleh Xi
= i8 maka titik potong dengan sumbuXi adalah (18,0).
Sedangkan titik potong dengan sumbu-X2 jika Xi
=0:

Program linear

0 + 3X2 = 72 diperoleh X2 = 24 maka titik

potong dengan sumbu-X2 adalah (0,24).
Sehingga jika digambarkan pada Koordinat
Cartesius adalah :
Gambar Grafik Contoh Soal

Daerah Fisibel (Wilayah Kelayakan / Daerah yang

Memenuhi Kendala (DMK)) adalah daerah yang

Program linear

merupakan irisan dari daerah yang memenuhi

kendala :
1) . 2Xi + X2< 30,
2) . 2Xi + 3X2< 60 ,
3) . 4Xi + 3X2< 72,
4) .Xi> 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 2Xi + X2 = 30 dan garis 4Xi
+ 3X2 = 72 , dan titik C adalah titik potong
antara garis 2Xi + 3X2 = 60 dan garis 4Xi + 3X2
= 72. . Adapun cara menghitung titik B dan C
tersebut dengan menggunakan metode Eliminasi
dan Substitusi, sebagai berikut:
*) Titik B perpotongan antara garis 2Xi + X2 = 30
dan garis 4Xi + 3X2 = 72, dengan mengeliminasi
Xi, dapat dihitung :
4Xi + 2X2 = 60
4Xi + 3X2 = 72

i)
iii)

- X2 = - i2 ^ X2 = 12
Untuk X2 = i2
disubstitusikan ke

Program linear

persamaan 2Xi + X2 = 30
sehingga : 2Xi + i2 = 30 ^
X1 = 9 maka titik B adalah
(9,12)
*) Titik C perpotongan antara garis 2Xi + 3X2 =
60

dan

garis

4Xi

3X2

72,

dengan

mengeliminasi X2, dapat dihitung :

2Xi + 3X2 = 60. i)
4Xi + 3X2 = 72. iii)
- 2Xi = - i2 ^ X1 = 6
Untuk Xi = 6 disubstitusikan
ke persamaan 2Xi + 3X2 =
60 sehingga : i2 + 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 : 0(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 Xi + 3000 Xs) di
setiap titik sudut-titik sudut Daerah yang
Memenuhi Kendala, sehingga:

Program linear

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.

1.2 Formulasi Model Program Linier

Masalah keputusan yang sering dihadapi analis
adalah alokasi optimum sumberdaya langka.
Sumberdaya dapat berupa uang, tenaga kerja,
bahan mentah, kapasitas mesin, waktu, ruang atau
teknologi. Tugas analis adalah mencapai hasil
terbaik yang mungkin dengan keterbatasan sumber
daya itu. Hasil yang dinginkan mungkin ditunjukkan

Program linear

sebagai maksimasi dari beberapa ukuran profit,

penjualan dan kesejahteraan, atau minimisasi pada
biaya, waktu dan jarak.

Setelah
masalah
di
identifikasikan,
tujuan
ditetapkan, langkah selanjutnya adalah formulasi
model matematika yang meliputi tiga tahap seperti
berikut :

Tentukan variable yang tidak diketahui

(Variabel keputusan) dan nyatakan dalam symbol
matematika.
Membentuk fungsi tujuan yang ditunjukkan
sebagai suatu hubungan linier (bukan perkalian)
dari variable keputusan.
Menentukan semua kendala masalah tersebut
dan mengekspresikan dalam persamaan atau
pertidaksamaan yang juga merupakan hubungan
linier
dari
variable
keputusan
yang
mencerminkan
keterbatasan
sumberdaya
masalah itu.

1.3 Masalah Maksimisasi

Maksimisasi dapat berupa memaksimalkan
keuntungan atau hasil.
Contoh:
PT LAQUNATEKSTIL memiliki sebuah pabrik
yang akan memproduksi 2 jenis produk,
yaitu kain sutera dan kain wol. Untuk

Program linear

10

memproduksi
kedua produk
diperlukan
bahan baku benang sutera, bahan baku
benang wol dan tenaga kerja. Maksimum
penyediaan benang sutera adalah 60 kg
per hari, benang wol 30 kg per hari dan
tenaga kerja 40 jam per hari. Kebutuhan setiap
unit produk
akan bahan baku dan
jam
tenaga kerja dapat dilihat dalam tabel berikut:

Jenis
bahan
baku dan
tenaga
kerja
Benang
sutera
Benang wol
Tenaga
kerja

Kg bahan baku &

Jam tenaga kerja
Kain
Kain
sutera
wol

Maksimum
penyediaa
n

60 kg

2
1

30 kg
40 jam

Kedua jenis produk memberikan keuntungan

sebesar Rp 40 juta untuk kain sutera dan
Rp 30 juta untuk kain wol. Masalahnya
adalah bagaimana menentukan jumlah unit
setiap jenis produk yang akan diproduksi
setiap hari agar keuntungan yang diperoleh
bisa maksimal.
Langkah-langkah:
1) Tentukan variabel

11

Program linear

2) Fungsi tujuan
Zmax= 40X1 + 30X2
3) Fungsi kendala / batasan
1. 2X1 + 3X2 60 (benang sutera)
2.

2X2 30 (benang wol)

3. 2X1 + X2 40 (tenaga kerja)

4) Membuat grafik
1. 2X1 + 3 X2 = 60
X1=0, X2 =60/3 = 20
X2=0, X1= 60/2 = 30
2. 2X2 30
X2=15
3. 2X1 + X2 40
X1=0, X2 = 40
X2=0, X1= 40/2 = 20

Program linear

12

Cara mendapatkan solusi optimal adalah

dengan mencari nilai Z setiap titik ekstrim.
Titik A
X1=0, X2=0
masukkan nilai X1 dan X2 ke Z
Z = 40 . 0 + 30 . 0 = 0
Titik B
X1=20, X2=0
masukkan nilai X1 dan X2 ke Z
Z = 40 . 20 + 30 . 0
Z = 800
Titik C

13

Program linear

Mencari titik potong (1) dan (3)

2X1 + 3X2 = 60
2X1 + X2 = 40 2X2 =20
X2=10
Masukkan X2 ke kendala (1)
2X1 + 3X2 = 60
2X1 + 3 .10 = 60
2X1 + 30
2X1
X1

= 60
= 30
= 15

masukkan nilai X1 dan X2 ke Z

Z = 40X1 + 30X2
Z = 40 . 15 + 30 . 10
Z = 600 + 300 = 900 (optimal)
Titik D
2X2 = 30
X2 = 15
masukkan X2 ke kendala (1)
2X1 + 3 . 15 = 60

Program linear

14

2X1 + 45 = 60
2X1 = 15 X1 = 7,5
masukkan nilai X1 dan X2 ke Z
Z = 40 . 7,5 + 30 . 15
Z = 300 + 450
Z = 750
Titik E
X2 = 15
X1 = 0
masukkan nilai X1 dan X2 ke Z
Z = 40 . 0 + 30 .15
Z = 450
Kesimpulan :
untuk memperoleh keuntungan optimal,
maka X1 = 15 dan X2 = 10 dengan
keuntungan sebesar Rp 900 juta.

1.4 Masalah Minimisasi

Minimisasi dapat berupa meminimumkan
biaya produksi. Solusi optimal tercapai pada
saat garis
fungsi
tujuan menyinggung

15

Program linear

daerah
origin.

fasible yang

terdekat dengan titik

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

Jenis
makanan
Royal Bee
Royal Jelly
minimum
kebutuhan

Vitamin
(unit)

Protein
(unit)

2
1
8

2
3
12

Biaya per
unit (ribu
rupiah)
100
80

Bagaimana menentukan kombinasi kedua

jenis makanan agar meminimumkan biaya
produksi.
Langkah langkah:
1. Tentukan variabel
X1 = Royal Bee

Program linear

16

X2 = Royal Jelly
2. Fungsi tujuan
Zmin = 100X1 + 80X2
3. Fungsi kendala
1. 2X1 + X2 8

(vitamin)

2. 2X1 + 3X2 12 (protein)

3. X1 2
4. X2 1
4. Membuat grafik
1) 2X1 + X2 = 8
X1 = 0, X2 = 8
X2 = 0, X1 = 4
2) 2X1 + 3X2 = 12
X1 = 0, X2 = 4
X2 = 0, X1 = 6
3) X1 = 2
4) X2 = 1

17

Program linear

Solusi
optimal
tercapai pada
titik
B
(terdekat
dengan
titik
origin),
yaitu
persilangan garis kendala (1) dan (2).
2X1 + X2 = 8
2X1 + 3X2 = 12 -2X2 = -4 X2 = 2
masukkan X2 ke kendala (1)
2X1 + X2 = 8
2X1 + 2 = 8
2 X1

=6

X1

=3

masukkan nilai X1 dan X2 ke Z

Z min = 100X1 + 80X2

Program linear

18

Z min = 100 . 3 + 80 . 2
Z min = 300 + 160
Z min = 460

Kesimpulan :
Untuk meminimumkan biaya produksi, maka
X1 = 3 dan X2 = 2 dengan biaya produksi 460
ribu rupiah.

SOAL LATIHAN
1. Maksimumkan Z = 4X + 5Y
Kendala :
1) 3X + 2Y 12
2) 3X + 4Y 18
X 0 , Y 0

Penyelesaian :
1. Langkah-langkah:
1) Fungsi tujuan
Zmax= 4X + 5Y
2) Fungsi kendala / batasan

19

Program linear

3X + 2Y 12

3X + 4Y 18

X1 0 , X2 0

3) Membuat grafik

3X + 2Y 12
X=0, Y =12/2 = 6

(0,6)

Y=0, X= 12/3 = 4

(4,0)

3X + 4Y 18
X=0, Y =18/4 = 19/2

(0,19/2)

Y=0, X= 18/3 = 6

(6,0)

6
5
4

Program linear

20

2
1
0

A
1

D
2

Cara mendapatkan solusi optimal adalah

dengan mencari nilai Z setiap titik ekstrim.
Titik A
X=0, Y=0

Z=4.0+5.0=0

Titik B
X=0, Y=4

Z = 4 . 0 + 5 . 4 = 20

Titik C
Mencari titik potong (1) dan (3)
3X + 2Y = 12
3X + 4Y = 18 -2Y = -6
Y=3
Masukkan Y ke kendala (1)
3X + 2Y = 12
3X + 2 .3 = 12
3X + 6

21

= 12

Program linear

3X

=6

=2

masukkan nilai X1 dan X2 ke Z

Zmax = 4X + 5Y
Zmax = 4 . 2 + 5 . 3
Zmax = 8 + 15
Zmax = 23

MAX

Titik D
X=4, Y=0

Z = 4 . 4 + 5 . 0 = 16

Kesimpulan :
X = 2 dan Y = 3 dengan nilai max = 23.

1.5 Pemecahan Dasar (Basis)

Contoh Soal

Tentukan nilai maksimum

Program linear

22

Penyelesaian :
m = Jumlah variable
n = jumlah persamaan
Menambahkan setiap persamaan dengan
sebuah variable tambahan atau variable
slack

23

Program linear

Program linear

24

25

Program linear

Program linear

26

Subtitusi y ke persamaan 1

Subtitusi x ke persamaan 1

27

Program linear

Subtitusi y ke persamaan 1

Program linear

28

Var basis

ket

x= ;z=3

Var non
basis
x=0 ; y=0 ;
z=0
x=0 ; y=0 ;
u=0
x=0 ; y=0 ;
v=0
x=0 ; z=0 ;
u=0
x=0 ; z=0 ;
v=0
y=0 ; z=0 ;
u=0
y=0 ; z=0 ;
v=0
u=0 ; v=0 ;
x=0
u=0 ; v=0 ;
y=0

x= ;y=

u=0 ; v=0 ;
z=0

u=12;v=12
z=6;v=-6
z=4;u=4
y=4;v=-4
y=3;u=3
x=3;v=6
x=6;u=-12
y=12;z=-12

29

TL

TL

TL

TL

(max)

Program linear

BAB II
METODE SIMPLEKS

2.1 Pengantar

Salah satu teknik penentuan solusi optimal

yang digunakan dalam pemrograman linier
adalah metode simpleks.
Penentuan solusi
optimal
menggunakan
metode
simpleks
didasarkan pada teknik eleminasi Gauss Jordan.
Penentuan solusi optimal dilakukan dengan
memeriksa titik ekstrim satu per satu dengan
cara perhitungan iteratif. Sehingga penentuan

Program linear

30

solusi optimal dengan simpleks dilakukan tahap

demi tahap yang disebut dengan iterasi. Iterasi
ke-i hanya tergantung dari iterasi sebelumnya (i1).
Ada beberapa istilah yang sangat sering
digunakan dalam metode simpleks, diantaranya :
1. Iterasi adalah tahapan perhitungan dimana
nilai dalam perhitungan itu tergantung dari
nilai tabel sebelumnya.
2. Variabel non basis adalah variabel yang
nilainya diatur menjadi nol pada sembarang
iterasi. Dalam terminologi umum, jumlah
variabel non basis selalu sama dengan derajat
bebas dalam sistem persamaan.
3. Variabel basis merupakan variabel yang
nilainya bukan nol pada sembarang iterasi.
Pada solusi awal, variabel basis merupakan
variabel slack (jika fungsi kendala merupakan
pertidaksamaan ) atau variabel buatan (jika
fungsi
kendala
menggunakan
pertidaksamaan atau =). Secara umum,
jumlah variabel basis selalu sama dengan
jumlah fungsi pembatas (tanpa fungsi non
negatif).
4. Solusi atau nilai kanan merupakan nilai
sumber daya pembatas yang masih tersedia.
Pada solusi awal, nilai kanan atau solusi sama
dengan jumlah sumber daya pembatas awal
yang
ada,
karena
aktivitas
belum
dilaksanakan.

31

Program linear

5. Variabel
slack
adalah variabel yang
ditambahkan ke model matematik kendala
untuk mengkonversikan pertidaksamaan
menjadi persamaan (=). Penambahan variabel
ini terjadi pada tahap inisialisasi. Pada solusi
awal, variabel slack akan berfungsi sebagai
variabel basis.
6. Variabel surplus adalah variabel yang
dikurangkan dari model matematik kendala
untuk mengkonversikan pertidaksamaan
menjadi persamaan (=). Penambahan ini
terjadi pada tahap inisialisasi. Pada solusi
awal, variabel surplus tidak dapat berfungsi
sebagai variabel basis.
7. Variabel buatan adalah variabel yang
ditambahkan ke model matematik kendala
dengan bentuk atau = untuk difungsikan
sebagai variabel basis awal. Penambahan
variabel ini terjadi pada tahap inisialisasi.
Variabel ini harus bernilai 0 pada solusi
optimal, karena kenyataannya variabel ini
tidak ada. Variabel hanya ada di atas kertas.
8. Kolom kunci (kolom kerja) adalah kolom
yang memuat variabel masuk. Koefisien pada
kolom ini akn menjadi pembagi nilai kanan
untuk menentukan baris pivot (baris kerja).
9. Baris kunci (baris kerja) adalah salah satu
baris dari antara variabel basis yang memuat
variabel keluar.
10.
Unsur kunci (elemen kerja) adalah
elemen yang terletak pada perpotongan
kolom dan baris pivot. Elemen pivot akan

Program linear

32

menjadi dasar perhitungan untuk tabel

simpleks berikutnya.
11.
Variabel pendatang adalah variabel
yang terpilih untuk menjadi variabel basis
pada iterasi berikutnya. Variabel masuk dipilih
satu dari antara variabel non basis pada
setiap iterasi. Variabel ini pada iterasi
berikutnya akan bernilai positif.
12.
Variabel perantau adalah variabel
yang keluar dari variabel basis pada iterasi
berikutnya dan digantikan oleh variabel
masuk. Variabel keluar dipilih satu dari antara
variabel basis pada setiap iterasi. Variabel ini
pada iterasi berikutnya akan bernilai nol.
2.2 BENTUK BAKU
Sebelum melakukan perhitungan iteratif
untuk menentukan solusi optimal, pertama sekali
bentuk umum pemrograman linier dirubah ke
dalam bentuk baku terlebih dahulu. Bentuk baku
dalam metode simpleks tidak hanya mengubah
persamaan kendala ke dalam bentuk sama
dengan, tetapi setiap fungsi kendala harus
diwakili oleh satu variabel basis awal. Variabel
basis awal menunjukkan status sumber daya
pada kondisi sebelum ada aktivitas yang
dilakukan. Dengan kata lain, variabel keputusan
semuanya masih bernilai nol. Dengan demikian,
meskipun fungsi kendala pada bentuk umum
pemrograman linier sudah dalam bentuk

33

Program linear

persamaan, fungsi kendala tersebut masih harus

tetap berubah.
Ada beberapa hal yang harus diperhatikan dalam
membuat bentuk baku, yaitu :
1. Fungsi kendala dengan pertidaksamaan
dalam bentuk umum, dirubah menjadi
persamaan (=) dengan menambahkan satu
variabel slack.
2. Fungsi kendala dengan pertidaksamaan
dalam bentuk umum, dirubah menjadi
persamaan (=) dengan mengurangkan satu
variabel surplus.
3. Fungsi kendala dengan persamaan dalam
bentuk umum, ditambahkan satu artificial
variabel (variabel buatan).
Perhatikan kasus A berikut :
Fungsi tujuan :
minimumkan z = 2 x1 + 5.5 x2
Kendala :
x1 + x2 = 90
0.001 x1 + 0.002 x2 0.9
0.09 x1 + 0.6 x2 27
0.02 x1 + 0.06 x2 4.5
x1, x2 0

Program linear

34

Bentuk di atas adalah bentuk umum pemrograman

liniernya. Kedalam bentuk baku, model matematik
tersebut akan berubah menjadi :
Fungsi tujuan :
minimumkan z = 2 x1 + 5.5 x2
Kendala :
x1 + x2 + s1 = 90
0.001 x1 + 0.002 x2 + s2 = 0.9
0.09 x1 + 0.6 x2 s3 + s4 = 27
0.02 x1 + 0.06 x2 + s5 = 4.5
x1, x2 , s1, s2, s3, s4, s5 0
Fungsi kendala pertama mendapatkan variable
buatan (s1), karena bentuk umumnya sudah
menggunakan bentuk persamaan. Fungsi kendala
kedua dan keempat mendapatkan variabel slack (s 2
dan s5) karena bentuk umumnya menggunakan
pertidaksamaan , sedangkan fungsi kendala ketiga
mendapatkan variabel surplus (s3) dan variabel
buatan (s4) karena bentuk umumnya menggunakan
pertidaksamaan .
Perhatikan pula kasus B berikut ini :
Maksimumkan z = 2x1 + 3x2
Kendala :
10 x1 + 5 x2 600

35

Program linear

6 x1 + 20 x2 600
8 x1 + 15 x2 600
x1, x2 0
Bentuk di atas juga merupakan bentuk umum.
Perubahan
ke
dalam
bentuk
baku
hanya
membutuhkan variabel slack, karena semua fungsi
kendala menggunakan bentuk pertidaksamaan
dalam bentuk umumnya. Maka bentuk bakunya
adalah sebagai berikut :
Maksimumkan z = 2x1 + 3x2 + 0s1 + 0s2 + 0s3
Kendala :
10 x1 + 5 x2 + s1 = 600
6 x1 + 20 x2 + s2 = 600
8 x1 + 15 x2 + s3 = 600
x1, x2 , s1 , s2 , s3 0
s1 , s2 , s3 merupakan variable slack.

2.3
Baris

Metode Simpleks dengan Operasi

Contoh Soal :
Maksimumkan z = 4000x1 + 3000x2
Kendala :
100 x1 + 200 x2 9000

Program linear

36

400 x1 + 200 x2 12000

x1, x2 0
Penyelesaian :

100 x1 + 200 x2 +x3= 9000

400 x1 + 200 x2 +x4= 12000
Z=4000x1+3000x2
Z 4000x1 3000x2=0

37

Program linear

Jadi

saat

2.4
Metode
variable dasar

simpleks

dengan

table

Dalam perhitungan iterative, kita akan

bekerja menggunakan tabel. Bentuk baku
yang sudah diperoleh, harus dibuat ke dalam
bentuk tabel.
Semua variabel yang bukan variabel basis
mempunyai solusi (nilai kanan) sama dengan
nol dan koefisien variabel basis pada baris
tujuan harus sama dengan 0. Oleh karena itu
kita harus membedakan pembentukan tabel
awal berdasarkan variabel basis awal.
Gunakan kasus B di atas, maka tabel awal
simpleksnya adalah :

VB
Z
S1
S2

X1
-2
10
6

Program linear

X2
-3
5
20

S1
0
1
0

S2
0
0
1

S3
0
0
0

Solusi
0
600
600

38

S3

15

LANGKAH-LANGKAH
CARA 1
Langkah-langkah
sebagai berikut :

600

PENYELESAIAN

penyelesaian

adalah

1. Periksa apakah tabel layak atau tidak.

Kelayakan tabel simpleks dilihat dari solusi
(nilai kanan). Jika solusi ada yang bernilai
negatif, maka tabel tidak layak. Tabel yang
tidak layak tidak dapat diteruskan untuk
dioptimalkan.
2. Tentukan kolom pivot. Penentuan kolom
pivot dilihat dari koefisien fungsi tujuan
(nilai di sebelah kanan baris z) dan
tergantung dari bentuk tujuan. Jika tujuan
maksimisasi, maka kolom pivot
adalah
kolom dengan koefisien paling negatif. Jika
tujuan minimisasi , maka kolom pivot
adalah kolom dengan koefisien positif
terbesar. Jika kolom pivot ditandai dan
ditarik
ke
atas,
maka
kita
akan
mendapatkan variabel keluar. Jika nilai
paling negatif (untuk tujuan maksimisasi)
atau positif terbesar (untuk tujuan
minimisasi) lebih dari satu, pilih salah satu
secara sembarang.
3. Tentukan baris pivot. Baris pivot ditentukan
setelah membagi nilai solusi dengan nilai
kolom pivot yang bersesuaian (nilai yang
terletak dalam satu baris). Dalam hal ini,

39

Program linear

nilai negatif dan 0 pada kolom pivot tidak

diperhatikan, artinya tidak ikut menjadi
pembagi. Baris pivot adalah baris dengan
rasio pembagian terkecil. Jika baris pivot
ditandai dan ditarik ke kiri, maka kita akan
mendapatkan variabl keluar. Jika rasio
pembagian terkecil lebih dari satu, pilih
salah sau secara sembarang.
4. Tentukan elemen pivot. Elemen pivot
merupakan nilai yang terletak pada
perpotongan kolom dan baris pivot.
5. Bentuk tabel simpleks baru. Tabel simpleks
baru dibentuk dengan pertama sekali
menghitung nilai baris pivot baru. Baris
pivot baru adalah baris pivot lama dibagi
dengan elemen pivot. Baris baru lainnya
merupakan pengurangan nilai kolom pivot
baris yang bersangkutan dikali baris pivot
baru dalam satu kolom terhadap baris
lamanya yang terletak pada kolom
tersebut.
6. Periksa apakah tabel sudah optimal.
Keoptimalan tabel dilihat dari koefisien
fungsi tujuan (nilai pada baris z) dan
tergantung dari bentuk tujuan. Untuk
tujuan maksimisasi, tabel sudah optimal
jika semua nilai pada baris z sudah positif
atau 0. Pada tujuan minimisasi, tabel
sudah optimal jika semua nilai pada baris z
sudah negatif atau 0. Jika belum, kembali
ke langkah no. 2 , jika sudah optimal baca
solusi optimalnya.

Program linear

40

Rumus yang digunakan:

yr =

yr
x rk

(untuk baris ke r yang terdapat

elemen pivot)
yi = yi bi ar (untuk baris ke i yang tidak
terdapat elemen pivot)
Keterangan:
yr = elemen baris ke r pada tabel yang baru
yi = elemen baris ke i pada tabel yang baru
yr = elemen baris ke r pada tabel yang lama
yi = elemen baris ke i pada tabel yang lama
bi = elemen baris ke i pada tabel lama yang
se-kolom dengan elemen pivot
ar = elemen baris ke r pada tabel yang baru

LANGKAH-LANGKAH
CARA 2

PENYELESAIAN

1. Rumuskan dan standarisasi modelnya

Optimumkan :

Terhadap

41

Program linear

2. Bentuk tabel pertama

VD
1
0
0

0
0
1

0
1
0

0
0
0

0
0
0

0
0
0
1
0
3. Tentukan variabel pendatang yaitu kolom
kunci dari nilai Z yang paling negatif
4. Menentukan variabel perantau
baris kunci dari nilai rasio terkecil

yaitu

5. Memasukkan variabel pendatang ke kolom

VD
Transformasi baris kunci :

Tansformasi baris-baris lain :

baris kunci = baris lama (baris pada
kolom kunci x baris kunci baru)

Program linear

42

6. Pengujian optimalisasi

Jika semua baris dasar baris Z sudah

tidak ada lagi yang negatif => max

Jika semua baris dasar baris z sudah

tidak ada lagi yang positif => min

Berarti proses selesai

Selesaikan kasus berikut ini menggunakan

metode simpleks :
Maksimum z = 8 x1 + 9 x2 + 4x3
Kendala :
x1 + x2 + 2x3 2
2x1 + 3x2 + 4x3 3
7x1 + 6x2 + 2x3 8
x1,x2,x3 0
Penyelesaian :
Bentuk bakunya adalah :
Maksimum z = 8 x1 + 9 x2 + 4x3 + 0s1 + 0s2 +
0s3 atau
z - 8 x1 - 9 x2 - 4x3 + 0s1 + 0s2 + 0s3 = 0
Kendala :
x1 + x2 + 2x3 + s1 = 2

43

Program linear

2x1 + 3x2 + 4x3 + s2 = 3

7x1 + 6x2 + 2x3 + s3 = 8
x1,x2,x3 ,s1 , s2 , s3 0
Solusi / table awal simpleks :
VB
Z
S1
S2
S3

X1
-8
1
2
7

X2
-9
1
3
6

X3
-4
2
4
2

S1
0
1
0
0

S2
0
0
1
0

S3
0
0
0
1

NK
0
2
3
8

Rasio

Karena nilai negative terbesar

ada pada
kolom X2, maka kolom X2 adalah kolom pivot
dan X2 adalah variabel masuk. Rasio
pembagian nilai kanan dengan kolom pivot
terkecil adalah 1 bersesuaian dengan baris
s2, maka baris s2 adalah baris pivot dan s2
adalah varisbel keluar. Elemen pivot adalah 3.
VB
Z
S1
S2
S3

X1
-8
1
2
7

X2
-9
1
3
6

X3
-4
2
4
2

S1
0
1
0
0

S2
0
0
1
0

S3
0
0
0
1

NK
0
2
3
8

Rasio
2
1
8/6

Iterasi 1
Nilai pertama yang kita miliki adalah nilai
baris pivot baru (baris x2). Semua nilai pada
baris s2 pada tabel solusi awal dibagi dengan
3 (elemen pivot).

Program linear

44

VB
Z
S1
x2
S3

X1

X2

X3

S1

S2

S3

NK

2/3

4/3

1/3

Rasio

Perhitungan nilai barisnya :

Baris z :
-8 -9

-4

1 4/3

1/3

1 (2/3 1

4/3

1/3

1)-

1/3

2/3

-1/3

4/3

1/3

-2

-9 ( 2/3
-2

Baris s1 :
1 1

Baris s3 :
7 6

6 ( 2/3 1
3 0

-6

1)-

Maka tabel iterasi 1 ditunjukkan tabel di

bawah. Selanjutnya kita periksa apakah
tabel sudah optimal atau belum. Karena

45

Program linear

nilai baris z di bawah variabel x 1 masih

negatif, maka tabel belum optimal. Kolom
dan baris pivotnya ditandai pada tabel di
bawah ini :
B

X1

X2

X3

S1

S2

S3

NK

Rasio

Z
S1
X2
S3

-2
1/3
2/3
3

0
0
1
0

8
2/3
4/3
-6

0
1
0
0

3
-1/3
1/3
-2

0
0
0
1

9
1
1
2

3
3/2
2/3

Variabel masuk dengan demikian adalah X1

dan variabel
keluar adalah S3 . Hasil
perhitungan iterasi ke 2 adalah sebagai
berikut :

Iterasi 2 :
VB

X1

X2

X3

S1

S2

S3

NK

Z
S1
X2
X1

0
0
0
1

0
0
1
0

4
4/3
8/3
-2

0
1
0
0

5/3
-1/9
7/9
-2/3

2/3
-1/9
-2/9
1/3

31/3
7/9
5/9
2/3

Rasi
o

Tabel sudah optimal, sehingga perhitungan

iterasi dihentikan !
Perhitungan
dalam
simpleks
menuntut
ketelitian tinggi, khususnya jika angka yang
digunakan adalah pecahan. Pembulatan harus
diperhatikan dengan baik. Disarankan jangan

Program linear

46

menggunakan bentuk bilangan desimal, akan

lebih teliti jika menggunakan bilangan
pecahan. Pembulatan dapat menyebabkan
iterasi lebih panjang atau bahkan tidak selesai
karena ketidaktelitian dalam melakukan
pembulatan.
Perhitungan iteratif dalam simpleks pada
dasarnya merupakan pemeriksaan satu per
satu titik-titik ekstrim layak pada daerah
penyelesaian. Pemeriksaan dimulai dari
kondisi nol (dimana semua aktivitas/variabel
keputusan bernilai nol). Jika titik ekstrim
berjumlah n, kemungkinan terburuknya kita
akan melakukan perhitungan iteratif sebanyak
n kali.

MEMBACA TABEL OPTIMAL

Membaca tabel optimal adalah bagian

penting bagi pengambil keputusan. Ada
beberapa hal yang bisa dibaca dari table
optimal :
1. Solusi optimal variable keputusan
2. Status sumber daya
3. harga bayangan (dual/shadow prices).
Menggunakan table optimal :

47

Program linear

VB
Z
S1
X2
X1

X1
0
0
0
1

X2
0
0
1
0

X3
4
4/3
8/3
-2

S1
0
1
0
0

S2
5/3
-1/9
7/9
-2/3

S3
2/3
-1/9
-2/9
1/3

NK
31/3
7/9
5/9
2/3

Solusi optimal X1 = 2/3, X2 = 5/9 , X3 = 0

dan Z = 31/3, artinya untuk mendapatkan
keuntungan maksimum sebesar $ 31/3 , maka
perusahaan sebaiknya menghasilkan produk 1
sebesar 2/3 unit dan produk 2 sebesar 5/9
unit.
Status sumber daya :
Sumber daya pertama dilihat dari keberadaan
variable basis awal dari setiap fungsi kendala
pada table optimal. Dalam kasus di atas,
untuk fungsi kendala pertama periksa
keberadaan S1 pada variable basis table
optimal. Periksa keberadaan S2 pada variable
basis table optimal untuk fungsi kendala
kedua. Periksa keberadaan S3 pada variable
basis table optimal untuk fungsi kendala
ketiga.
S1 = 7/9. Sumber daya ini disebut berlebih
(abundant)
S2 = S3 = 0. Kedua sumber daya ini disebut
habis terpakai (scarce).

Harga bayangan :

Program linear

48

Harga bayangan dilihat dari koefisien variable

slack atau surplus pada baris fungsi tujuan.
Koefisien S1 pada baris fungsi tujuan table
optimal = 0, dengan demikian harga
bayangan sumber daya pertama adalah 0
Koefisien S2 pada baris fungsi tujuan table
optimal = 5/3, dengan demikian harga
bayangan sumber daya kedua adalah 5/3
Koefisien S3 pada baris fungsi tujuan table
optimal = 2/3, dengan demikian harga
bayangan sumber daya kedua adalah 2/3.
Selesaikan
kasus
berikut
menggunakan metode simpleks :

ini

Kendala :

Penyelesaian :

49

Program linear

Var
pendatang

VD

1
0

-3
1

-5
2

0
1

0
0

0
10

10

10

Var perantau

VD

1
0

-3

-5
1

0
0

0
5

10

Transformasi baris Z
:

Program linear

50

Transformasi

Var
pendatang

VD

25

Var perantau

51

Program linear

VD

25

Transformasi baris Z
:

Transformasi

Program linear

52

5
VD

26

14

2.5 Metode Simpleks 2

Fase 1
Langkah langkah :

53

Program linear

Menambahkan
variabel
pada
pertidaksamaan
yang
telah
diketahui,
jika
pertidaksamaan
tersebut
telah
memenuhi syarat
simpleks yaitu
berarti
pertidaksamaan
tersebut
ditambahkan satu
variabel
slack,
jika
pertidaksamaan
tersebut
tidak
memenuhi syarat
simpleks yaitu
berarti
persamaan
dikurangi variabel
surplus
dan
ditambah variabel
slack.

Fungsi
ditambahkan
variabel
dari
persamaan yang

Program linear

54

tidak memenuhi
syarat
tersebut
dengan simbol
yang

berarti

Persamaan
tersebut dsusun
fungsi
diletakkan paling
atas,

lalu

fungsi

dari
yang

koefisiennya
adalah

maka

hasilnya
harus
nol
Setelah dikalikan
dan ditambahkan
dengan fungsi

55

maka dicari nilai

yang paling kecil
dari hasilnya
Lalu dicari kunci
dari
persamaan
yang
diketahui
dengan
cara
membagi
hasil
dengan

Program linear

persamaan
dengan
angka
yang telah diberi
tanda peda hasil
yang paling kecil
tersebut.
Dari
kunci
tersebut
dibuat
menjadi 1 dan
angka
yang
berada
satu
kolom
dengan
angka 1 tersebut
dijadikan nol
Lakukan
hal
tersebut
berulang-ulang
hingga tidak ada
yang
bernilai
negatif pada hasil
yang
berada
paling
bawah
kecuali nilai

Contoh soal :
1. Minimumkan

Kendala :

Program linear

56

Penyelesaian :
Misal :

0
6
2

57

Program linear

Karena
sudah tidak ada
yang
negatif
maka
proses
selesai

2.6 Metode Simpleks 2

Fase 2
Langkah langkah :

Sistem
pertidaksamaan 1
dan
seterusnya
dibuat
sama
seperti
simpleks
dengan 1 fase

Nilai
diminimumkan
(dikalikan dengan )

Program linear

pindah

ruas

menjadi bernilai +
Selanjutnya sama
seperti
pada
simpleks Fase 1,
namun
pembedanya
adalah
yang

58

mempunyai
nilai
hanya variabel
variabel
yang mengandung
nilai

bernilai -1

dan

selebihnya bernilai
nol
Cari
nilai
pada
sistem
pertidaksamaan
yang membentuk
identitas dan pada
posisi 1 di sebelah
kiri
(pengali)
diletakkan nilai
lalu

setelah

variabel dikali dan

dijumlahkan,
dikurangkan nilai

59

diatasnya
Selanjutnya sama
dengan simpleks 2
fase
1
hingga
berakhir pada nilai
baris terakhir yang
bernilai positif

Program linear

Hilangkan
kolom
yang mengandung
nilai

pada

letakkan

lalu
nilai

keseluruhan

pada atas baris

Lalu seperti cara
pada langkah 5
hingga
baris
terakhir
bernilai
positif
Dan itulah nilai
(jangan lupa nilai
adalah

Contoh Soal :

Kendala :

Penyelesaian :

Program linear

60

Misal

3
1

61

Program linear

Karena
sudah tidak ada
yang
negatif
maka
proses
selesai

2.7 Metode M Charnes

Prosedur Pemecahan :

Program linear

62

Merumuskan
masalah
PL
dalam
bentuk
baku
dengan
kendala / syarat
berbentuk
persamaan,
dengan
apabila
tanda
pertidaksamaan
berarti
pertidaksamaan
tersebut
ditambahkan satu
variabel
slack,
jika
pertidaksamaan
tersebut
tidak
memenuhi syarat
simpleks yaitu
berarti

63

persamaan
dikurangi variabel
surplus
dan
ditambah variabel
slack.
Pada fungsi tujuan,
konstanta, variabel
surplus/
variabel
slack adalah nol,

Program linear

sedangkan variabel
tiruan diberi nilai
jika
memaksimumkan
dan

nilai

jika

meminimumkan
Variabel
tiruan
sebagai
variabel
basis awal yang
akan
segera
meninggalkan
basis menjadi non
basis
Ikuti
aturan
simpleks
juntuk
menentukan nilai
fungsi
turunan,
yaitu :
Jika
memaksimumka
n
maka
pemecahan
selesai/fungsi
tujuan optimal
pada
saat
semua elemen
pada
baris
bernilai
positif

Program linear

64

Jika
meminimumkan
pengerjaan
selesai
pada
saat
semua
masukkan pada
baris
negatif

Contoh Soal :

Kendala :

Penyelesaian :
Cara

maksimum

dengan

mengalikan

dengan min
Misal

65

Program linear

Transformasi baris kunci

Transformasi Baris b

Program linear

66

Transformasi Baris c

67

Program linear

Transformasi baris kunci

Transformasi Baris x

Transformasi Baris c

Program linear

68

Jadi,

69

nilai

Program linear

Saat

2.8 Metode Simpleks 2

Fase
Fase I berakhir dalam
kondisi

maka

simpulan

untuk

meneruskan ke fase II
dengan
memperhatikan

kemungkinan, yaitu :
1.

dimana
satu
atau
lebih
variabel
slack
berada dalam basis
pada tingkat nilai
yang
positif.
Masalah PL yang
asli
tidak

Program linear

70

mempunyai
penyelesaian layak
(Fisisbel)
2.

dengan
kenyataan
tidak
ada variabel slack
terletak
dalam
basis ini berarti
telah
diperoleh
penyelesaian layak
dasar (fisibel basis)
dari persoalan PL
yang asli

3.

dengan
kenyataan
satu/lebih variabel
slack
terletak
dalam basis tingkat
nol
(degenerasi)
kenyataan ini juga
menunjukkan
bahwa
telah
diperoleh
penyelesaian layak
dasar (fisibel basis)
dari masalah PL

Persyaratan

untuk

memulai fase II :

71

Program linear

Perhitungan
merupakan

fase

II

lanjutan

fase I apabila akhir Fase

I

menunjukkan

kemungkinan
modivikasi

sebagai

berikut :

Koefisien
harga
fungsi tujuan adalah
koefisien
harga
fungsi tujuan yang
asli,
atau
nilai
koefisien
variabel
pokok pada fase I
yaitu
nol
harus
diganti
dengan
koefisien asli
Elemen pada baris
dihitung
kembali
Metode ini digunakan
untuk menyelesaikan
persoalan
memuat

PL

yang

variabel

buatan

Program linear

72

Contoh

Kendala

Penyelesaian :
Dengan

menggunakan

cara memaksimumkan
(dikali negative )
Missal :

Fase I

73

Program linear

Transformasi baris kunci

:

Transformasi Baris

Program linear

74

Transformasi baris kunci

:

Transformasi Baris

75

Program linear

Fase II

Jadi,

Tahap 1 :
Bentuk

dengan

var

buatan : R1 dan R2
Min r = R1 + R2

Program linear

76

Kendala
3 X1 + X2

+ R1

= 3
4 X1 + 3 X 2 - X3
R2
X1

= 6
+

+ X4

X2

= 4

X 1 , X 2 , X 3 , R 1 , R2 , X 4
0
Fungsi tujuan

r = R1 +

R2
= (33
X1 - X2 ) + ( 6 - 4 X1 3 X2 + X3 )
= -7 X 1 4 X2 + X3 + 9
Tabel Awal
VB
r
R1
R2
X4

X1
7
3
4
1

X2
4
1
3
2

X3
-1
0
-1
0

R1
0
1
0
0

R2
0
0
1
0

X4
0
0
0
1

Tabel optimum : setelah

2 iterasi ( periksa ! )

77

Program linear

NK
9
3
6
4

VB
r
X1
X2
X4

X1
0
1
0
0

X2
0
0
1
0

X3
0
1
/5
3
- /5
1

R1
-1
3
/5
4
- /5
1

R2
-1
-1/5
3
/5
-1

Karena minimum
solusi r = 0, masalah
ini memiliki
pemecahan (solusi)
layak. Lanjutkan ke
tahap ( Fase ) kedua.
Tahap 2
Menyingkirkan

variabel buatan ( R1
dan R2 )
Dari tabel

optimum tahap 1
didapatkan :
1

X1 +
X2 -

/5X3

/5X3

X3 + X4

/5

/5

= 1

Masalah semula ditulis :

Min Z = 4 X1 + X2
Kendala
3

Program linear

/5

X1 +

/5X3 =

......... ( 1 )

78

X4
0
0
0
1

NK
0
3
/5
6
/5
1

X2 -

/5X3

/5

.........
(2)
X3 + X4

= 1

X1 , X2 , X3 , R1 , R2 , X4
0
Maka terdapat 3
persamaan dan 4
variabel sehingga
solusi dasar layak
didapat dg membuat
(4 3) = 1 variabel
dibuat nol
X3 = 0
3

X1 =

->

/5 ; X2 =

/5 ;

X4 = 1
Fungsi tujuan

Z = 4 X1 + X2
= 4(
(6/5 +

/5 +

/5 X3 ) +

/5X3 )

= - 1/5 X3 +

18

/5

Tabel Awal
Var msk

79

Program linear

VB
Z
X1
X2
X4

X1
0
1
0
0

X2
0
0
1
0

X3
1
/5
1
/5
3
- /5
1

X4
0
0
0
1

NK
18
/5
3
/5
6
/5
1

Tabel optimum

VB
Z
X1
X2
X3

X1
0
1
0
0

X2
0
0
1
0

X3
0
0
0
1

X4
-1/5
-1/5
3
/5
1

NK
17
/5
2
/5
9
/5
1

SOAL LATIHAN
1. Selesaikan linear
program berikut ini
dengan metode
Simplex
Maksimumkan Z =
400X1 + 300X2
Fungsi kendala/ batasan:

Program linear

80

 4X1 + 6X2 1200

4X1 + 2X2 800
X1 250
X2 300
X1, X2 0
2. Selesaikan linear
program berikut ini
dengan metode
Simplex
Maksimumkan Z =
2X1 + 3X2 + X3
Dengan fungsi
kendala:
1) X1 + X2 + X3

9
2) 2X1 + 3X2
3)

25

X2 + 2X3
10

4) X1, X2, X3

3. Minimumkan Z = 3X1
+ 2X2
Fungsi batasan :
1) X1 + 2X2 20
2) 3X1 + X2 20
3) X1 0 , X2 0

81

Program linear

BAB III
DUAL DAN PRIMAL
Setiap masalah Program
Linear

yang

bertujuan

mencari nilai maksimum

selalu

bertalian

suatu

masalah

linear

program

dengan

mencari

nilai

dengan
tujuan

minimum,

yang disebut dual masalah

yang pertama. Sebaliknya
setiap

masalah

linear

yang

mencari

nilai

program
bertujuan
minimum

selalu

bertalian

dengan

suatu

masalah

program

linear

yang

bertujuan

mencari nilai maksimum

yang

disebut

dual.

Masalah pertama disebut

primal sedangkan masalah
kedua

dengan

tujuan

berlawanan disebut dual.

MAKS

MIN

DUAL

Program linear

82

MIN

DUAL

MAKS

Dalam analisis Program

Linear (PL) terdapat 2
bentuk, yaitu :
1. Bentuk primal : Bentuk
asli dari persamaan
program linear
2. Bentuk dual : Bentuk
duplikat atau rangkap
dari persamaan
program linear

Jika penyelesaian
persoalan Program Linear
dengan bentuk primal
secara langsung juka
dapat diketahui hasil
bentuk dualnya,
sebaliknya jika
penyelesaian Program

83

Program linear

Linear dengan bentukdual,

maka secara langsung
dapat diketahui bentuk
primalnya.
Contoh Soal :
Tentukan dual dari
masalah primal berikut
ini :

Kendala

Penyelesaian :
Karena
maka

meminimumkan
semua

kendala

harus bertanda ( )

Matriks

Primal

Matriks dual

Program linear

84

Masalah dual :

Kendala

85

Program linear