PROGRAM

LINEAR
Oleh: Witri Lestari, [Link]

Universitas Indraprasta PGRI | Pend. Matematika | 2024/2025

 PROGRAM LINEAR DENGAN
METODE GRAFIK
A METODE TITIK EKSTRIM
.

Cara penyelesaian dengan metode grafik dilakukan dengan semua

pertidaksamaan fungsi kendala dan syarat non negatif dalam sebuah grafik.
Namun, tidak semua permasalahan PL bisa diselesaikan dengan metode
grafik karena banyaknya variable fungsi kendala dan fungsi tujuan
bersesuaian dengan ruang grafik. Misal, jika ada tiga variable maka grafik
penyelesaian PL berada pada �3. Masalah program linear dua variabel (n=2)
bisa diselesaikan dengan metode grafik, sedangkan untuk n ≥ 2 diselesaikan
dengan metode simpleks.
 Halaman 3

1 Gambarkan dan tentukan daerah-daerah

semua grafik fungsi kendala dan fungsi
pembatas (syarat non negative).

1 Tentukan daerah penyelesian yang feasible,

LANGKAH- yaitu daerah yang memenuhi semua fungsi

kendala dan syarat non negative.
PENYELESAIAN
DENGAN 1 Tentukan titik ekstrim (sudut) dari

METODE TITIK
daerah feasible. Setiap titik ekstrim
merupakan titik interseksi dari dua

EKSTRIM pembatasan linier.

1 Substitusi setiap titik ekstrim daerah

feasible ke dalam fungsi tujuan (Z) untuk
mendapatkan solusi optimum. Solusi
optimum terletak pada salah satu titik
Witri Lestari | UNINDRA | [Link] | 2024/2025 ekstrim daerah feasible
 Halaman 4

SISTEM PERTIDAKSAMAAN LINEAR

2 VARIABEL
Sistem pertidaksamaan linear dua variabel terbentuk dari dua atau lebih pertidaksamaan linear
dua variabel dengan variabel-variabel yang sama. Sebagai contoh:
a) � + 3� ≤ 3, 2� − 3� ≥ 4, dan � + � ≤ 8, membentuk sistem pertidaksamaan linear dengan dua
variabel.
b)� + 3� ≤ 4, 2� − � ≥ 1, dan 3� + � ≤ 5, bukan merupakan sistem pertidaksamaan linear dengan
dua variabel.

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 5

Contoh 1 : Gambarkan Grafik penyelesaian dari :

�� − �� ≥ ��
� ≤ �, � ≥ �
Langkah-langkah:
menentukan titik potong pada sumbu �
�=0 →�=6
menentukan titik potong pada sumbu y
� = 0 → � =− 3
Menggambar grafiknya:

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Contoh 2 : Gambarkan Grafik penyelesaian dari :
Daerah yang diarsir pada gambar di bawah ini merupakan grafik himpunan
penyelesaian dari suatu sistem pertidaksamaan linear dua variabel. Tentukan
sistem pertidaksamaan linear dua variabel yang dimaksud!

Persamaan garis g1 yang melalui titik (5,0) dan (0,5) adalah

5
�+�=�
Persamaan garis g2 yang melalui titik (8,0) dan (0,3) adalah
3 �� + �� = ��
Daerah grafik himpunan penyelesaian itu terletak:
di kanan sumbu Y, maka pertidaksamaannya � ≥ 0,
di atas sumbu X, maka pertidaksamaannya � ≥ 0,
5 8 di bawah garis g1, maka pertidaksamaannya � + � ≤ 5,
di bawah garis g2, maka pertidaksamaannya 3� + 8� ≤ 24.

Jadi, daerah yang diarsir pada soal yang dimaksud merupakan grafik himpunan
penyelesaian dari sistem pertidaksamaan linear dua variabel x ≥ 0, y ≥ 0, x+y ≤ 5 ,
3x+8y ≤ 24 untuk x dan y  R

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 7

Contoh 3
Daerah yang di arsir pada gambar di bawah ini adalah himpunan penyelesaian suatu
program linier. Tentukan sistem pertidaksamaannya!
�

Daerah himpunan
penyelesaian

�
4 8

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 8

SISTEM PERTIDAKSAMAAN LINEAR

3 VARIABEL
Sistem pertidaksamaan linier tiga variabel terbentuk dari dua atau
lebih pertidaksamaan linier tiga variabel dengan variabel-variabel yang
sama. �

Contoh: �
�(0, 0, )
1. �� + �� + �� ≤ � �
Jadi, Himpunan penyelesaiannya
yaitu titik 0, A, B dan C
�
DAERAH �( , 0,0)
�
HIMPUNAN �
PENYELESAIAN

�
�(0, , 0)
� �

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 9

2. �� + �� + �� ≥ �
�

� DAERAH
DAERAH �(0, 0, ) HIMPUNAN
�
HIMPUNAN PENYELESAIAN
PENYELESAIAN

�
�( , 0,0)
�
�

� � DAERAH
�(0, , 0)
� HIMPUNAN
PENYELESAIAN

Jadi, Himpunan penyelesaiannya yaitu titik A, B dan C

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 10

Contoh 1
Tunjukkan dengan gambar daerah penyelesaian sistem pertidaksamaan
�, �, � ≥ 0 , 4� + 3� + 2� ≤ 12 , ��� 2� + 4� + 3� ≤ 12 , k e m u d i a n
tentukan nilai ekstrim (maksimum & minimum) untuk � = 2� + 3� + �!

Penyelesaian :
Gambar bidang α = 4x+3y+2z=12  titik A(3,0,0), B(0,4,0), dan C(0,0,6)
Gambar bidang β = 2x+4y+3z=12  titik D(6,0,0), E(0,3,0), dan F(0,0,4)
Titik perpotongan α dan β di xy adalah G(6/5,12/5,0) (dengan
eliminasi/subtitusi)
Titik perpotongan α dan β di xz adalah H(3/2,0,3)(dengan eliminasi
/subtitusi)

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 11

Adapun daerah pemecahan yang dimaksud pada soal ini adalah area
berupa ruang yang dibatasi oleh titik-titik OAEFGH. Dengan
demikian dapat dicari nilai maksimum untuk T = 2� + 3� + �
adalah sebagai berikut:
Titik � � � T = 2� + 3� + �
O 0 0 0 0
A 3 0 0 6
E 0 3 0 9
F 0 0 4 4
G 6 12 0 9,6
5 5
H 3 0 3 6
2
Jadi nilai maksimum T adalah 9,6
dan nilai minimumnya adalah 0

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 12

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 13

1. METODE UJI TITIK

POJOK

Suatu metode dengan

mensubtitusikan titik-titik pojok
pada suatu daerah himpunan
penyelesaian (DHP) ke fungsi
tujuannya

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 14

Contoh 1:
Sebuah pabrik buku memproduksi buku jenis polos dan bergaris. Dalam satu
hari pabrik itu paling banyak memproduksi 1.000 buku. Dari bagian penjualan
diperoleh keterangan bahwa setiap hari terjual tidak lebih dari 800 buku polos
dan 600 buku bergaris. Keuntungan setiap buku polos adalah Rp100,00 dan
buku bergaris adalah Rp150,00. Berapakah keuntungan bersih sebesar-besarnya
yang dapat diperoleh setiap hari? Berapa banyak buku polos dan buku bergaris
yang harus diproduksi setiap hari?
Penyelesaian :
Fungsi Tujuan: �(�, �) = 100� + 150�
Kendala: � + � ≤ 1.000;
� ≤ 800;
� ≤ 600;
� ≥ 0; � ≥ 0.
Witri Lestari | UNINDRA | [Link] | 2024/2025
 Halaman 15

(0,0) 0
(800,0) 80.000
(800,200) 110.000
(400,600) 130.000
(0,600) 90.000

Jadi dengan kendala-kendala yang ada, produsen buku

dalam sehari dapat memperoleh keuntungan sebesar-
besarnya Rp130.000,00. Adapun keuntungan sebesar itu
bisa dicapai jika dalam satu hari diproduksi buku polos
sebanyak 400 buah dan buku bergaris sebanyak 600 buah.

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 16

2. METODE GARIS
SELIDIK

Suatu garis yang digunakan

untuk menyelidiki nilai optimum
(maksimum & minimum) yang
diperoleh dari fungsi tujuan

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 17

LANGKAH-LANGKAH MENENTUKAN NILAI

OPTIMUM DENGAN METODE GARIS SELIDIK

1. Buat model matematikanya yang terdiri dari kendala dan fungsi tujuan
2. Tentukan grafik dan daerah himpunan penyelesaiannya
3. Tentukan persamaan garis selidik dari fungsi tujuannya
♦ Untuk mendapatkan nilai maksimum, geser garis selidik secara sejajar ke arah
kanan atau atas sampai memotong titik paling jauh dari daerah himpunan
penyelesaian. titik yang paling jauh tersebut merupa ka n t i t i k ya ng
memaksimumkan fungsi tujuan.
♦ Untuk mendapatkan nilai minimum, geser garis selidik secara sejajar ke arah kiri
atau bawah sampai memotong titik paling dekat dari daerah himpunan
penyelesaian. titik yang paling dekat tersebut merupakan titik yang
meminimumkan fungsi tujuan.

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 18

Tentukan nilai maksimum dari fungsi tujuan Z = 3x +4y

Dengan kendala :
X + 2y  10 ; 4x +3y ≤ 24 ; x ≥ 0 ; y ≥ 0

Penyelesaian :
1. Menentukan grafik dan daerah himpunan penyelesaian (DHP)

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 19

2. Tentukan garis selidik dari fungsi tujuannya

fungsi tujuan Z = 3x +4y, maka bentuk umum garis selidiknya adalah:
3x +4y = k, untuk memudahkan menggambar, kita pilih nilai k =12 sehingga
persamaan garis selidiknya adalah 3x +4y = 12

Berdasarkan gambar garis selidik di samping,

garis selidik yg digeser secara sejajar ke
kanan atau ke atas. Memotong titik terjauh
dari himpunan penyelesaian system
pertidaksamaan linear dua variable yang
diketahui, yaitu titik B. koordinat titik B
setelah dicari adalah (18/5 , 16/5).
Artinya fungsi tujuannya maksimum pada
titik pojok B.

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 20

3. Menentukan nilai maksimumnya dengan subtitusi titik B ke fungsi

tujuannya

fungsi tujuan Z = 3x +4y

F (x, y) = f(18/5 , 16/5) = (3 x 18/5) + (4 x 16/5) = 118/5 = 23,6

Jadi nilai maksimum dari fungsi tujuannya adalah 23,6

4. Lalu bagaimana dengan nilai minimumnya ?

Perhatikan gambar garis selidiknya,
Garis selidik harus digeser ke kiri atau ke bawah seperti gambar berikut

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 21

Berdasarkan gambar tersebut,

titik 0 (0,0) merupakan titik
paling dekat dari himpunan
penyelesaian system
pertidaksamaan linear 2 variable
yang diberikan. Dengan demikian,
nilai minimum fungsi tujuan :
Z= 3x + 4y = 3 (0) + 4(0) =0

Sehingga nilai minimum fungsi

tujuannya adalah 0

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 22

Tiga Kategori Pemecahan Masalah Pada Program Linear

Pada prinsipnya setiap persoalan program linear dapat diselesaikan, namun

tidak bisa dihindari akan terjadi tiga kategori:
(1) ada satu penyelesaian yang menunjukkan fungsi tujuan mencapai optimal,
dimana akan ada dua alternatif yaitu nilai optimal berupa jawaban tunggal
yang dicapai pada satu titik dan nilai optimal berupa jawaban yang dicapai
oleh dua titik atau lebih dalam derah penyelesaian.
(2) ada satu penyelesaian tak terikat;
(3) tidak terdapat penyelesaian layak dari suatu persoalan yang dirumuskan ke
dalam bentuk program linear.

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 23

Contoh 1 :
Ada 1 penyelesaian yang menunjukkan fungsi tujuan mencapai optimal berupa
jawaban tunggal yang dicapai pada satu tiitik.

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 24

Contoh 2 :
Ada 1 penyelesaian yang menunjukkan fungsi tujuan mencapai optimal berupa
penyelesaian optimum yang dicapai oleh dua titik

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 25

Contoh 3 :
Ada 1 penyelesaian tak terikat

Berdasarkan gambar grafik daerah

himpunan penyelesaian yang
terlihat di samping, terbuka
peluang untuk terus mempertinggi
nilai fungsi tujuan.

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 26

Contoh 4 :
Tidak terdapat penyelesaian layak dari suatu persoalan yang dirumuskan ke
dalam bentuk program linear

Berdasarkan gambar grafik daerah

himpunan penyelesaian yang terlihat
di samping, daerah yang ditunjukkan
dengan dua pembatas yang tidak
saling menunjang berarti tidak
terdapat penyelesaian optimal.

Witri Lestari | UNINDRA | [Link] | 2024/2025

LATIHAN
 Halaman 28

Witri Lestari | UNINDRA | [Link] | 2024/2025

 Halaman 29

3. Dengan menggunakan metode uji titik pojok dan garis selidik, Tentukan
nilai maksimum fungsi tujuan Z = 80x +125y dengan kendala:
x + y ≤ 350,
600x + 1.000y ≤ 300.000
x ≥ 0,
y ≥ 0

Witri Lestari | UNINDRA | [Link] | 2024/2025

Terima Kasih
Witri Lestari | UNINDRA | [Link] | 2024/2025