PROGRAM

LINEAR
Oleh: Witri Lestari, [Link]

Universitas Indraprasta PGRI | Pend. Matematika | 2024/2025

 MATERI PROGRAM LINEAR
01 Pendahuluan 06 Metode Simplek Bentuk Variasi
02 Metode Grafik 07 Primal dan Dualitas
03 Metode Simplek Maksimum 08 Metode Transportasi I
04 Metode Simplek 2 Fase 09 Metode Transportasi II
05 Metode Simplek Big-Mi 10 Metode Transportasi III
 Halaman 3

Dalam kehidupan sehari-hari sering kali kita

menjumpai masalah yang dalam penyelesaiannya kita
menghendaki hasil yang optimum padahal sumber daya

PENDAHULUAN yang kita punyai untuk mencapai hasil tersebut terbatas.

Kumpulan cara atau metode untuk memecahkan

masalah tersebut di atas dikenal dengan Riset
Operasional. Sebutan ini dikenal sejak selesainya
perang dunia II (akhir tahun 1950-an).

Pemrograman linear adalah teknik matematika untuk

memilih program terbaik dari sehimpunan alternatif
yang mungkin dengan menggunakan fungsi linear.

Masalah pemrograman linear adalah mengoptimalkan

(memaksimumkan/meminimumkan) variabel terikat
(fungsi linear dari variabel bebas) terhadap sejumlah
kendala linear.

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

 Halaman 4

Tokoh Leonid Vitalevich Kartovich

Program Linear Leonid V. Kartovich lahir pada bulan Januari tahun 1912 di kota
Leningrad, Rusia. pada tahun 1939, Leonid mengajukan sebuah
hasil pemikirannya berdasarkan masalah yang ada dan
Program linear ditemukan dan perencanaan solusinya. Ternyata hasil pemikirannya ini adalah
yang kita kenal sekarang sebagai Program Linear
dikembangkan oleh beberapa
matematikawan di masa sebelum
George Bernard Dantzig
Perang Dunia ke-II. Penemuan dan
pengembangan oleh beberapa George Bernard Dantzig lahir pada tanggal 8 November 1914 di
Portland,Oragon, Amerika Serikat. Dantzig dikenal karena
matematikawan tersebut rata – rata pengembangan algoritma simpleksnya, sebuah algoritma untuk
didasarkan karena persoalan atau memecahkan masalah program linear, dan untuk karya-karya
lain yang berkait dengan pemrograman linear.
masalah yang sedang berkembang
saat itu, yaitu dalam hal industri dan John von Neumann, Leonid
peperangan. Khachiyan dan Naranda Karmarkar
Mereka mengembangkan program linearuntuk
masalah – masalah yang lebih rumit pada tahun –
tahun berikutnya sampai di temukannya metode
grafik1
.
Witri Lestari | UNINDRA | [Link] | 2024/2025
 Halaman 5

Bentuk umum
Pemrograman Linear :
Fungsi Tujuan
(maksimum atau minimum) Z = c1x1 + c2x2 + …. + cnxn
Pembatas
a11x1 + a12x2 + … + a1n xn ≤ atau ≥ b1
a21x1 + a22x2 + … + a2nxn ≤ atau ≥ b2
…
am1x2 + am2x2 + … + amnxn ≤ atau ≥ bm
𝑥1, 𝑥2, … , 𝑥𝑛 ≥ 0

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

 Halaman 6

Keterangan:

m : banyaknya jenis sumber yang terbatas atau fasilitas yang tersedia.

n : banyaknya kegiatan‐kegiatan yang menggunakan sumber atau fasilitas
terbatas tersebut
x𝑗: variabel keputusan untuk kegiatan ke‐ j (j=1,2, … , n).
aij : banyaknya sumber i yang diperlukan untuk menghasilkan setiap unit
keluaran (output) kegiatan j (i=1,2, … , m; j=1,2, … , n).
bi : banyaknya sumber (fasilitas) yang tersedia untuk dialokasikan ke setiap unit
kegiatan (i=1,2, … , m).
cj : kenaikan nilai Z apabila pertambahaan tingkat kegiatan (x ij) dengan satu
satuan (unit) atau merupakan sumbangan setiap satuan keseluruhan
kegiatan j terhadap nilai Z.
Z : nilai yang dioptimalkan (maksimum atau minimum).

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

 Dalam Pemrograman Linear Terdapat Tiga Halaman 7

Hal Besar yang Menjadi Perhatian:

[Link] Masalah yaitu mengubah masalah sehari-hari ke dalam bentuk
matematika yang melibatkan :
♦Mendefinisikan variabel keputusan
♦Mendefinisikan fungsi tujuan
♦Mendefinisikan fungsi-fungsi kendala
2. Memecahkan masalah secara matematis yaitu menentukan nilai variabel
keputusan yang mengoptimumkan fungsi tujuan. Beberapa metode yang
dapat digunakan:
♦Metode Grafik (untuk masalah pemrograman linear dengan 2 variabel
keputusan)
♦Metode Simplek (untuk masalah pemrograman linear dengan lebih dari 2
var. keputusan)
3. Menganalisa hasil perhitungan matematis untuk menjawab permasalahan
dalam dunia nyata (analysis postoptimality)

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

 Halaman 8

MASALAH OPTIMISASI
1. Optimisasi Fungsi Tanpa Kendala
Jika diberikan fungsi satu peubah y = f(x), x ∈ R yang terdiferensialkan n+ 1
kali, maka melalui deret Taylor disekitar xo dapat disimpulkan bahwa jika
f’(xo) =f’’(xo) =....fn(xo)= 0,
f(n+1)≠ 0,
a. untuk (n+1) ganjil: terjadi ekstrem, dan jika
(i) fn+1 (xo) < 0, maka f(x) mencapai maksimum di titik xo
(ii) fn+1 (xo) > 0, maka f(x) mencapai minimum di titik xo.
b. untuk (n+1) genap: terjadi titik infleksi bagi f(x) di titik xo

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

 Halaman 9

Contoh 1 :
Diberikan fungsi y= f(x)=x3, sehingga diperoleh
f’(x)= 3x2
f’(x) = 6x
f’’’(x) = 6
Untuk x= 0 diperoleh
f’(x)= 0
f’’(x) = 0
f’’’(x) = 6
Karena (n + 1) ganjil, maka fungsi y = x3 memiliki titik infleksi
stasioner di titik x = 0.

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

 Halaman 10

2. Optimisasi Fungsi Dengan Kendala

Contoh 2:
Peternak ayam mempunyai kawat sepanjang 24 m yang akan
digunakan untuk memagari kandang ayam berbentuk persegi
panjang. Bagaimana ukuran kandang agar luasnya maksimum?
Penyelesaian
Misalkan p = panjang kandang
q = lebar kandang
maka luas kandang adalah L=p.q dan keliling adalah 2(p+q)=24
Akan ditentukan p dan q tak negatif yang memaksimumkan luas
kandang L dengan kendala panjang
kawat 2( p + q ) = 24.
Witri Lestari | UNINDRA | [Link] | 2024/2025
 Halaman 11

Permasalahan di atas adalah masalah optimisasi fungsi dua peubah

dengan kendala berbentuk persamaan. Untuk menyelesaikan masalah
di atas soal dapat diubah menjadi bentuk soal ekstrim fungsi satu
peubah tanpa kendala dengan cara mengeliminasi salah satu
peubahnya, misalnya q dan sebagainya.
2 (p+q)=24 Lmaks = p x q
q= 24/2-p = 12-p =6x6
= 36
Lmaks = p x q = p (12-p)
= 12p-p2 Sehingga didapat p= 6 dan q = 6 dan
L’ = 12- 2p memberikan Lmaks 36.
2p = 12 Ini beraarti bahwa kandang yang harus
P = 12/2 dibuat dengan ukuran
p =6 6m kali 6m (berbentuk bujur sangkar)
q = 12 – p
q = 12-6
WitriqLestari
= 6 | UNINDRA | [Link] | 2024/2025
 Halaman 12

Formulasi Masalah
Pemrograman Linear

Dalam kehidupan sehari-hari selalu ada saja masalah yang dihadapi

oleh suatu Negara, perusahaan, bahkan oleh seseorang. Secara umum
masalah (problem) ditapsirkan sebagai suatu kesenjangan antara
yang seharusnya terjadi atauharapan dengan yang sesungguhnya
yang terjadi atau keadaan sekarang.
Contoh :
Sebuah perusahaan mebel memproduksi meja dan kursi menggunakan
papan, kayu, dan jam pengerjaan. Setiap meja membutuhkan 5 unit papan, 2
unit kayu, dan 4 jam pengerjaan. Setiap kursi membutuhkan 2 unit papan, 3
unit kayu, dan membutuhkan 2 jam pengerjaan.

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

 Halaman 13

Perusahaan dapat menjual seluruh produk dan memperoleh keuntungan

$12 untuk setiap meja dan $8 untuk setiap kursi. Namun hanya 150 unit
papan, 100 unit kayu, dan 80 jam yang dimiliki untuk setiap minggu.
Perusahaan ingin mengetahui berapa banyak setiap produk harus
diproduksi untuk memaksimumkan keuntungan sesuai dengan sumber
yang ada.

Variabel keputusan
perusahaan ingin mengetahui berapa unit masing-masing barang yang
harus diproduksi.
x1 = jumlah unit meja yang akan diproduksi
x2 = jumlah unit kursi yang akan diproduksi

Fungsi tujuan
perusahaan ingin memaksimumkan keuntungan.
Maks f = 12x1 + 8x2 keuntungan dari setiap meja $12 dan kursi $8

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

 Halaman 14

Kendala
kendalanya adalah hubungan antara variabel
keputusan dengan masing-masing sumber serta keterbatasan
sumber daya yang ada.
♦Papan 5x1 + 2x2 ≤ 150
♦Kayu 2x1 + 3x2 ≤ 100
♦Waktu pengerjaan 4x1 + 2x2 ≤ 80
x1, x2 ≥0 jumlah produk tidak negatif

Formulasi lengkap
Maks f = 12x1 + 8x2
ds 5x1 + 2x2 ≤ 150
2x1 + 3x2 ≤ 100
4x1 + 2x2 ≤ 80
x1, x2 ≥0

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

 LATIHAN
Untuk memperdalam pemahaman Anda mengenai materi di atas
kerjakanlah latihan berikut!
1) Perusahaan Aneka mendapat jatah merakit sepeda dan sepeda motor.
Karena jumlah pekerja terbatas, perusahaan hanya dapat merakit sepeda
120 unit tiap bulan dan sepeda motor paling sedikit 10 unit dan paling
banyak 60 unit. Pendapatan dari tiap unit sepeda sebesar Rp40.000,00 dan
tiap unit sepeda motor Rp268.000,00. Berapa pendapatan maksimum tiap
bulan kalau kapasitas produksi kedua jenis 160 unit.
a. Rumusan fungsi tujuan!
b. Rumusan pembatas!
c. Tanpa menghitung terlebih dahulu, perlihatkan daerah pemecahan yang
ditunjukkan dengan pembatas dengan gambar!
d. Kemudian titik manakah yang menunjukan nilai maksimum fungsi tujuan.
Berikan alasan!
 Halaman 16

2. Seorang tukang roti mempunyai bahan A,B dan C dengan banyak yang tersedia berturut-
turut 300 unit, 180 unit, dan 300 unit. Dengan bahan yang tersedia, tukang roti membuat
dua macam roti sesuai dengan pesanan langganan. Pembuat roti menetapkan keperluan
bahan sebagai berikut.

a. Rumuskan fungsi tujuan dan pembatas.

b. Harga roti I sebesar Rp350,00 dan ke II Rp800,00. Berapa banyak tiap macam harus dibuat untuk
memperoleh hasil penjualan terbanyak? Berapa rupiah jumlah terbesar yang diperoleh pembuat
roti?
c. Jika roti macam I dijual dengan harga Rp450,00 dan macam II tetap Rp800,00. Apakah dia akan
mengubah rencana semula? Kalau terjadi perubahan, berapa banyak roti dari tiap macam harus
dibuat oleh pembeli roti itu. Berapa rupiah akan diterima kalau semua roti itu habis terjual?

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

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