KELOMPOK 1:

Ayu Lestari (20700123027)

Muhammad Ihyaul Afif Shidiq (20700123033)

KEGUNAAN PROGRAM LINEAR

A. Pengertian Program Linear
Program linear yang diterjemahkan dari linear programming (LP) adalah
suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang
terbatas diantara beberapa aktivitas yang bersaing. Dengan cara yang terbaik
yang mungkin di lakukan. Beberapa contoh situasi dari uraian diatas antara lain
adalah persoalan pengalokasian fasilitas produksi, persoalan pengalokasian
sumber daya nasional untuk kebutuhan domestic, penjadwalan produksi, Solusi
permainan (game), dan pemilihan pola pengiriman (shipping).
Linear programming atau program linear adalah suatu teknis matematika
yang dirancang untuk membantu manejer dalam merencanakan dan membuat
Keputusan dalam mengalokasikan sumber daya yang terbatas untuk mencapai
tujuan Perusahaan.
Program linear merupakan salah satu Teknik penelitian operasional yang
digunakan paling luas dan diketahui dengan baik, serta berupa metode
matematik, yang berfungsi mengalokasikan sumber daya yang langka untuk
mencapai tujuan Tunggal seperti memaksimumkan keuntungan dan
meminimumkan biaya. Program linear banyak diterapkan dalam membantu
dalam menyelesaikan masalah ekonomi, industry, militer, dan sosial.
Dari uraian diatas dapat disimpulkan program linear adalah
merencanakan beberapa aktivitas secara tepat untuk memperoleh hasil yang
optimum.
B. Sejarah Singkat Program Linear
Menurut George B. Dantzing yang sering disebut bapak linear
programming, dalam bukunya yang berjudul linear programming and extension,
menyebutkan bahwa ide dari pada linear programming ini berasal dari ahli
matematika rusia Bernama L. V. kantorivich yang pada tahun 1939 menerbitkan
sebuah karangan dengan judul “Mathematical Methodes in the Organization and
planning of Production”.
Didalam karangan tersebut telah dirumuskan persoalan linear
programming untuk pertama kalinya. Akan tetapi ide ini rupanya di rusia tidak
bisa berkembang. Ternyata dunia berat yang memanfaatkan ide ini selanjutnya.
Kemudian pada tahun 1947 seorang ahli matematika dari amerika serikat yang
Namanya telah disebutkan yaitu George B. Dantzing menemukan suatu cara
untuk memecahkan persoalan linear programming tersebut dengan suatu
metode yang disebut “simpleks method“. Setelah saat itu yaitu sejak tahun 50-an
linear programming tersebut berkembang dengan pesat sekali mula mula di
bidang ke militeran (untuk penyusunan strategi perang, persoalan bombing
 pattern) maupun didalam bidang business(persoalan untuk mencapai maksimun
profit, minimun loss, dan lain sebagainya).
Sekarang penggunaan linear programming bukan saja terbatas pada
bidang kemiliteran, bidang ekonomi Perusahaan yang sifat nya mikro sebagai
alat management, akan tetapi sudah meluas terutama sekali dalam perencanaan
Pembangunan ekonomi nasional yang makroh sifatnya, misalnya didalam
penentuan “allocation of investments” kedalam sektor sektor perekonomian”,
retationcor corp policy”, peningkatan penerimaan devisa , dan lain sebagainya.

C. Sifat Dasar Program Linear

Sifat-sifat dasar atau karakteristik pemrograman linear adalah sebagai berikut:
1. Sifat linearitas suatu kasus dapat ditetntukan dengan menggunakan beberapa
cara. Secara statistic, cara ini dapat diperiksa keliniaran menggunakan grafik
(diagram penca).
2. Sifat proporsional dipenuhi jika kontribusi setiap variabel pada fungsi tujuan
atau penggunaan sumber daya yang membatasi proporsional terhadap level
nilai variabel. Jika harga per unit produk misalnya adalah sama berapun
jumlah yang dibeli, maka sifat proporsional terpenuhi. Dengan kata lain jika
pembelian dalam jumlah besar mendapatkan diskon maka sifat proporsional
tidak dipenuhi. Jika penggunaan sumber daya per unitnya tergantung dalam
jumlah yang di produksi, maka sifar proporsionalitas tidak di penuhi.
3. Sifat aditivitas mengasumsikan bahwa tidak ada bentuk perkalian silang
diantara berbagai aktivitas , sehingga tidak akan ditemukan bentuk perkalian
silang pada model. Sifat aditivitas berlaku baik bagi fungsi tujuan maunpun
pembatas(kendala). Sifat aditivitas dipenuhi jika fungsi tujuan merupakan
penambahan langsung kontribusi masing masing variabel Keputusan.
4. Sifat divisibilitas berarti unit aktivitas dapat dibagi kedalam sembarang level
fraksional, sehingga nilai variabel Keputusan non integer dimungkinkan.
5. Sifat kepastian menunjukan bahwa semua parameter model berupa konstan.
Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan suatu
nilai pasti, bukan merupakan nilai dengan peluang tertentu.

D. Model Program Linear

Sebelum membahas masalah model pemrograman ini maka terlebih
dahulu dibahas beberapa karakteristik umum dari pada program linear ini.
Semua masalah dalam program linear mempunyai karakteristi sebagai berikut:
1. Keseluruhan sistem permasalahan dapat dibagi menjadi satu-satuan
aktivitas. Umpama:
a11X1 + a12X2≥b1; X1 dan X2 adalah aktivitas
2. Masing-masing aktivitas harus dapat ditentukan dengan tepat baik jenis
maupun letaknya dalam model program linear.
3. Setiap aktivitas harus dapat didefinisikan dengan jelas kuantitasnya, sehingga
dapat dibandingkan masing-masing nilai.

Untuk lebih jelasnya maka dapat dilihat pada contoh berikut ini:
 Suatu Perusahaan manufaktur memproduksi 4 jenis barang ABCD. Setiap
jenis barang diproses melalui 2 bagian dalam pabrik yaitu bagian pengolahn
dan bagian penggosokan. Jam yang dibutuhkan oleh masing masing barang
pada tiap bagian adalah:
Bagian A B C D
Pengolahan 4 2 6 9
Penggosokan 3 7 4 4

Dalam seminggu mesin mesin bagian pengolahan dapat bekerja 70

jam sedangkan mesin mesin bagian penggosokan hanya dapat bekerja 50
jam.
Keuntungan yang diperoleh dari masing masing barang adalah:
Bagian A B C D
Bahan mentah Rp 100,- Rp200,- Rp600,- Rp300,-
Biaya biaya:
Pengolahan, Rp 400,- Rp200,- Rp600,- Rp900,-
penggosokan Rp300,- Rp700,- Rp400,- Rp400,-
Harga pokok Rp800,- Rp1100,- Rp1200,- Rp1600,-
Harga jual Rp1400,- Rp1900,- Rp2400,- Rp4000,-
Keuntungan Rp600,- Rp700,- Rp1200,- Rp2400,-
Contoh ini merupakan salah satu masalah yang akan dipecahkan dengan
program linear. Aktivitas-aktivitas daripada perusahaan adalah mencari
tingkat produksi A, B, C, dan D yang akan mendatangkan keuntungan
maksimum. Pemilihan tingkat produksi ini dabatasi oleh keterbatasan
sumber-sumber, dalam hal ini adalah 70 jam pada pengolahan dan 50 jam
pada penggosokan.
Dari contoh di atas sudah dapat dipahami tentang karakteristik umum dari
program linear.
Model linear programming atau program linear adalah bentuk dan susunan
dasar dalam menyajikan permasalahan yang akan dipecahkan dengan teknik
linear programming atau program linear.
Dalam program linear dikenal 2 macam “fungsi” yakni fungsi tujuan dan
fungsi-fungsi pembatas. Fungsi tujuan merupakan fungsi yang menggambarkan
tujuan kita didalam permsalahan program linear yang bersangkutan yakni
mengatur secara optimal (untuk memperoleh keuntungan yang sebesar-
besarnyaatau biaya yang serendah-rendahnya). Pada umumnya, nilai yang akan
di maksimumkan (atau diminimumkan) dinyatakan dalam Z. fungsi pembatas
merupakan bentuk penyajian secara sistemanis dari batasan-batasan kapasitas
yang tersedia yang akan dialokasian secara optimal kepada berbagai aktivitas.
Untuk memudahkan uraian mengenai model program linear ini,
digunakan symbol-simbol sebagai berikut:
m = macam batasan-batasan sumber atau fasilitas yang tersedia
n = macam aktivitas yang menggunakan sumber atau fasilitas tersebut
i = nomor setiap macam sumber atau fasilitas tersedia (i = 1, 2, …, m)
j = nomor setiap macam aktivitas yang menggunakan sumber atau fasilitas yang
tersedia (j = 1, 2, …, n)
Xj = Tingkat aktivitas ke j (j = 1, 2, …, n)
aij = banyak sumber I yang perlukan untuk menghasilkan setiap untuk
menghasilkkan setiap unit output aktivitas j (I = 1, 2, …, m dan j = 1, 2, …, n)2
bi = banyaknya sumber (fasilitas) i yang tersedia untuk di alokasikan ke setiap
jenis aktivitas (i = 1, 2, …, m)
Z = nilai yang dimaksimumkan atau diminimumkan
Cj = kenaikan nilai z apabila da pertambahan Tingkat aktivitas (Xj) dengan satu-
satuan, atau merupakan sumbangan setiap satuan output aktivitas j terhadap
nilai Z.

Keseluruhan symbol-simbol diatas digunakan dalam model sistematis

yang dipakai untuk mengemukkakan suatu permasalahan program linear sebagai
berikut:
Fungsi Tujuan:
Maksimumkan Z = C1X1+C2X2+ …, CnXn
Batasan-batasan:
a11X1 + a12X2 + … a1nXn ≤ b1
a21X1 + a22X2 + a2nX2 ≤ b2
⋮
am1X1 + am2X2 + … amnXn ≤ bm
X1 ≥ 0 , X 2 ≥ 0 , X n ≥ 0
Bentuk atau model program linear diatas merupakan bentuk standar bagi
permasalahan-permasalahan program linear yang akan dipakai selanjutnya.
Dengan kata lain setiap permasalahan yang apabila diformulasikan secara
matematis mengikuti model diatas, maka permasalahan tersebut merupakan
permasalahan linear programming.
Terminologi umum untuk model program linear adalah sebagai berikut:

1. Fungsi yang akan dimaksimumkan : C1X1+C2X2+ …, CnXn disebut fungsi

tujuan (objective function)
2. Fungsi-fungsi pembatas dapat dikelompokkan menjadi dua macam
yakni:
a) fungsi pembatasan fungsional, yakni fungsi-fungsi pembatas sebanyak m (yaitu a
11 1X +
a12X2 + … ainXn)
b) Fungsi pembatas non negatif (non negativy constraints), yakni fungsi-fungsi
pembatas yang dinyatakan dengan Xi≥ 0
3. Variabel-variabel Xj disebut decision variables.
4. Aij, bi dan Cj yakni input-input konstan, disebut sebut sebagai parameter
daripada model.
 Tidak semua permasalahan linear programming atau program linear
betul-betul mengikuti model diatas. Permasalahan permasalahan tersebut atara
lain:
1. Permasalahan minimisasi, untuk menentukan kombinasi (output)
yang dapat meminumkan biaya. Dalam hal ini fungsi tujuan
dinyatakan sebagai berikut:
Minimumkan Z = C1X1 + C2X2 + C3X3 + … + CnXn
2. Permasalahan dengan fungsi pembatas fungsional yang memiliki
tanda matematis ≥ sehingga apabila dituliskan sebagai berikut:
a11X1 + a12X2 + a13X3 + ainXn ≤ bi
3. Permasalahan dengan fungsi pembatas fungsional yang memiliki
tanda matematis = sehingga apabila dituliskan sebagai berikut :
a11X1 + a12X2 + a13X3 + ainXn ¿ b i
4. Permasalahan tertentu, Dimana fungsi pembatas non negative
tidak diperlukan atau dengan kata lain Xj tidak terbatas.

E. Persoalan Program Linear/formulasi program linear

Persoalan linear programming atau program liear adalah suatu persoalan
untuk menentukan besarnya masing-masing nilai variable fungsi tujuan yang
linear menjadi optimum (maksimum atau minimum) dengan memperhtikan
pembatasan-pembatasan yang ada yaitu pembatasan mengenai inputnya.
Pembatasan-pembatasan inipun harus dinyatakan dalam ketidaksamaan yang
linear (linear inequalities).
CONTOH:
1. Pemilik Perusahaan mempunyai 2 macam bahan mentah, katakan bahan
mentah I dan II yang masing masing tersedia sebesar 60 dan 48 satuan (kg,
m, l, ton dan sebagainya). Dari 2 bahan mentah tersebut akan diproduksi 2
macam barang yaitu barang A dan B. baik barang A maupun baranh B
memerlukan bahan mentah I dan II sebagai inputnya. Perincian penggunaan
bahan mentah adalah sebagai berikut:
1 Satuan barang A memerlukan 4 satuan bahan I dan 2 satuan bahan II.
Apabila barang A dan B dijual 1 satuan barang A laku Rp 8.000 sedangkan B
laku Rp 6.000. berapa besarnya produksi barang A dan B agar supaya
penerimaan seluruh hasil penjualan maksimum dengan memperhatikan
pembatasan bahwa penggunaan bahan I dan II tidak boleh melebihi 60
satuan dan 48 satuan. (semua barang laku dijual). Rumuskan persoalan
tersebut menjadi persoalan linear programming atau program linear.
Penyelesaian:
Perumusan persoalan linear programming atau program linear.
Misalkan: Barang A = X1 dan barang B = X2
1 satuan barang A laku Rp 8.000→ satuan laku 8X1
1 satuan barang B laku Rp 6000 → X2 satuan laku 6X2
Jumlah penerimaan hasil jualan: Z = 8X1 + 6X2 harus maksimum
1 satuan barang a memerlukan 4 satuan bahan I → X1 satuan = 4X1
1 satuan barang B memerlukan 2 satuan bahan I → satuan=2 X 2
 Jumlah bahan mentah I yang diperlukan = 4X 1 + 2X2 (hanya tersedia
sebanyak 60 satuan).
1 satuan barang A memerlukan 2 satuan bahan II → X1 satuan = 2X1
1 satuan barang B memerlukan 4 satuan bahan II→ X2 satuan = 4X2
Jumlah bahan mentah II yang diperlukan = 2X 1 + 4X2 (hanya tersedia
sebanyak 48 satuan).
X1 ≥ 0 , X 2≥ 0 ,artinya X1 dan X2 tidak boleh mengambil nilai negative,
paling kecil 0. Syarat ini disebut “non negativity constraint” juga
merupakan pembatasan (limitation) yang harus diperhatikan dalam
pemecahan persoalan linear programming atau program linear.

Model program linearnya :

Cari X1 dan X2
Fungsi tujuan: Z= 8X1+6X2 maksimum
Fungsi pembatas: 4X1+2X2 ≤60
2X1+4X2≤48
X1≥0, X2≥ 0

2. Suatu Perusahaan manufaktur sedang mencari alternatif kombinasi

produksi dari produk yang di hasilkan agar diperoleh laba maksimun. Pda
saat ini, Perusahaan sedang membuat 3 jenis produk yang diberi merk A, B
dan C. Ketiga produk tersebut digunakan dengan menggunakan sumber
daya berupa bahan baku, mesin, dan tenaga kerja. Bagian penelitian dan
pengembangan hasil produksi memberikan informasi bahwa untuk
membuat ketiga jenis produk tersebut, setiap satuan (unit) memerlukan
sumber daya seperti table pada berikut.
Sumber daya jenis produk
A B C
Bahan baku(kg) 2 3 4
Tenaga 5 2 4
Kerja(jam)
Mesin(jam) 3 4 2

Selanjutnya, diketahui bahwa setiap bulannya Perusahaan mampu

menyediakan paling banyak 200kg bahan baku, 250 jam tenaga kerja
dan 150 jam kerja mesin. Ketiga produk tersebut memberikan
sumbangan laba masing-masing sebesar Rp1000, produk c. Rumuskan
persoalan tersebut menjadi persoalan linear programming atau program
linear.
Penyelesaian:
Perumusan persoalan linear programming atau program linear
Misalkan: Jenis produk A=X1, jenis produk B=X2, dan jenis produk C=X3
1 satuan produk A memberikan laba Rp1000,→X1
1 satuan produk B memberikan laba Rp2000, ,→X2
 1 satuan produk C memberikan laba Rp 5000, ,→X3
Z = 1000X1 + 2000X2 + 5000X3 maksimum
1 satuan produk A memerlukan bahan baku 2Kg,→ 2X1
1 satuan produk B memerlukan bahan baku 3Kg ,→ 3X2
1 satuan produk C memerlukan bahan baku 4kg ,→ 4 X3
Jumlah bahan baku yang diperlukan = 2X1 + 3X2 + 4X3 (hanya tersedia
paling banyak 200kg).
1 satuan produk A memerlukan tenaga kerja 5 jam ,→ 5X1
1 satuan produk B memerlukan tenaga kerja 2 jam ,→ 2X2
1 satuan produk C memerlukan tenaga kerja 4 jam ,→ 4 X3
Jumlah tenaga kerja yang diperlukan = 5 X 1+ 2X2+ 4X3 (hanya tersedia
paling banyak 250jam)
1 satuan produk A memerlukan kerja mesin 3jam ,→ 3X1
1 satuan produk b memerlukan kerja mesin 4 jam ,→ 4 X2
1 satuan produk C memerlukan kerja mesin 2 jam ,→ 2X3 (hanya
tersedia paling banyak 150jam).
X1≥ 0 , X 2≥ 0 ,X3≥ 0, artinya X1,X2, dan X3 tidak boleh mengambil nilai
negative, paling kecil 0. Syarat ini disebbut “non negativity constraint”
juga merupakan pembatasan (limitation) yang harus diperhatikan dalam
pemecahan persoalan linear programming atau program linear.
Model program Linearnya:
Cari X1, X2, X3
Fungsi tujuan: Z = 1000 X1 + 2000 X2 + 5000 X3 maksimum
Fungsi pembatas: 2 X1 + 3 X2 + 4 X3≤ 2000
5 X1 + 2 X2 + 4 X3 ≤ 250
3 X1 + 4X2 + 2X3 ≤ 150
X1 ≥ 0 ,X2≥ 0 ,X3≥ 0

F. Metode penyelesaian program linear

Pemecahan persoalan program linear dengan metode aljabar adalah
pemecahan persoalan dengan cara subtitusi antar persamaan linear pada fungsi
pembatas dan fungsi tujuan.
Pemecahan persoalan persoalan program linear dengan metode aljabar
ini dibagi 3 (tiga) kasus, yaitu:
1. Kasus maksimisasi; Kasus pemecahan persoalan program linear yang
bertujuan mencari seluruh kemungkinan pemecahan yang
memberikan nilai objektif maksimum.
2. Kasus minimisasi; Kasus pemecahan masalah program linear yang
bertujuan seluruh kemungkinan pemecahan yang memberikan nilai
objektif minimum.
3. Kasus kasus khusus; Beberapa kasus khusus selain kasus maksimisasi
dan minimisasi adalah kasus Solusi optimum ganda dan tidak
memiliki Solusi yang layak.
CONTOH:
1. (kasus maksimisasi)
Cari X1 dan X2
Fungsi tujuan: Z = 8X1 + 6X2 Maksimum
Fungsi pembatas : 4X1 + 2X2 = 60
2X1 + 4X2 = 48
X1≥ 0 ,X2≥ 0
Memecahkan persoalan Linear Programming di atas, berarti memecahkan kedua
ketidaksama n, kemudian nilai X1 dan X2 sebagai pemecahan dimasukkan ke
dalam Z. Untuk memecahkan ketidaksamaan tidak bisa secara langsung akan
tetapi ketidaksamaan tersebut harus dirubah dahulu menjadi persamaan dengan
jalan memasukkan “slack variables” X3 dan X4. Slack variabels ialah suatu variabel
yang ditambahkan disebelah kiri tanda ketidaksamaan, agar ketidaksamaan
menjadi persamaan. Dengan memasukkan slack variables X3 dan X4 kita peroleh
dua persamaan berikut:
4X1 + 2X2 + X3 = 60
2X1 + 4X2 + X4 = 48
Dalam prakteknya X3 dan X4 merupakan bahan mentah sisa, yaitu yang tidak
diproduksi. Maka dari itu C3 dan C4 masing-masing nilainya sama dengan 0, sebab
tidak dijual. PersoalanLinear Programming di mana ketidaksamaan sudah
dirubah
menjadi persamaan disebut persoalan Linear Programming yang standar.
Persoalan Linear Programming yang standar adalah sebagai berikut :
Cari X1 , X2, X3, X4
Fungsi tujuan: Z = 8X1 + 6X2 + 0X3 + 0X4 Maksimum
Fugsi pembatas : 4X1 + 2X2 + X3 = 60
2X1 + 4X2 + X4 = 48
X1≥ 0 , X2≥ 0, X3≥ 0, X4≥ 0
Kita peroleh 2 persamaan:
4X1 + 2X2 + X3 = 60
2X1 + 4X2 + X4 = 48
X1 , X2, X3, X4 disebut pemecahan dari persamaan tersebut apabila nilai-nilai X1 , X2,
X3, X4 memenuhi persamaan tersebut. Karena ada 4 variabel akan tetapi hanya
tersedia 2 persamaan maka hanya ada 2 variabel yang nilainya dapat diperoleh
dari 2 persamaan tersebut, sisanya sebanyak (4-2) = 2 nilainya harus 0. Pada
umumnya kalau ada n variabel = X1, X2, …, Xj, …, Xn akan tetapi hanya ada
persamaan, maka hanya ada m variabel yang nilainya dapat diperoleh dari m
persamaan tersebut. Variabel yang diperoleh dari m persamaan tersebut
dinamakan variabel dasar (basic variables), sedangkan pemecahannya disebut
pemecahan dasar (basic solution). Pemecahan yang memenuhi semua syarat
pembatasan disebut pemecahan fisibel (feasible solution). Kalau pemecahan
fisibel merupakan pemecahan dasar, kemudian disebut pemecahan dasar fisibel
(feasible basic solution). Pemecahan yang menghasilkan paling sedikit satu
variabel yang negative tidak fisibel.
Pada umumnya, kalau ada n variable: X1 , X2, …, Xj, …, Xn akan tetapi hanya
ada m persamaan, maka bisa diperoleh sebanyak K persamaan, di mana K
Kombinasi, dihitung berdasarkan rumus berikut:
n!
K= n!=n ( n−1 )( n−2 ) … 2.1
m ! ( n−m) !

Dalam contoh ini, n = 4 dan m = 2 (n! dibaca n factorial)

4! 4 ∙ 3 ∙2 ∙ 1 24
K= = = =6
2 ! ( 4−2 ) ! 2 ∙1 ∙ 2∙ 1 4
Jadi, ada 6 persamaan dasar, dengan demikian ada 6 pemecahan dasar. Dari 6
pemecahan dasar ini, kita pilih pemecahan dasar yang fisibel. Nilai variabel dasar
sebagai pemecahan dasar yang fisibel ini, dimasukkan ke dalam Z = 8X 1 +
6X2+0X3+ 0X4. Kemudian dipilih pemecahan dasar fisibel yang membuat nilai Z
menjadi maksimum. Pemecahan dasar fesibel inilah yang merupakan pemecahan
optimal.
6 persamaan dasar dengan pemecahan dasarnya adalah sebagai berikut:
1. X1 = X2 = 0
4X1 + 2X2 + X3 = 60 → X 3 = 60
2X1 + 4X2 + X4 = 48 → X 4 = 48
Z1 = 8X1 + 4X2 + 0X3 + 0X4
= 8(0) + 6(0) + 0(60) + 0(48) = 0
2. X1 = X3 = 0
4X1 + 2X2 + X3 = 60 → 2 X 2 = 60 → X 2 = 30
2X1 + 4X2 + X4 = 48 → 4 X 2 + X4= 48
4(30) + X4 = 48
X4 = 48 – 120 = -72 (tidak fisibel)
Z2 tidak dihitung, karena X4 negatif, jadi pemecahan tidak fisibel.
3. X1 = X4 = 0
4X1 + 2X2 + X3 = 60 → 2 X 2 + X3 = 60
2X1 + 4X2 + X4 = 48 → 4 X 2 = 48 → X2 = 12
2X2 + X3 = 60
2(12) + X3 = 60
X3 = 60 – 24 = 36
Z3 = 8X1 + 6X2 + 0X3 + 0X4
= 8(0) + 6(12) + 0(36) + 0(0) = 72
4. X2 = X3 = 0
4X1 + 2X2 + X3 = 60 → 4 X 1 = 60 → X 1 = 15
2X1 + 4X2 + X4 = 48 → 2 X 1 + X4= 48
2(15) + X4 = 48
X4 = 48-30 = 18
Z4 = 8X1 + 6X2 + 0X3 + 0X4
= 8(15) + 6(0) + 0(0) + 0(18) = 120
5. X2 = X4 = 0
4X1 + 2X2 + X3 = 60 → 4 X 1 + X3 = 60
 2X1 + 4X2 + X4 = 48 → 2 X 1 = 48 → X1 = 24
4(24) + X3 = 60
X3 = 60 – 96 = -36 (tidak fisibel)
Z5 tidak dihitung, karena X3 negatif, jadi pemecahan tidak fesibel.
6. X3 = X4 = 0
4X1 + 2X2 + X3 = 60 → 4 X 1 + X3 = 60
2 X 1 + X2 = 30
2X1 + 4X2 + X4 = 48 → 2 X 1 + 4X2= 48
2 X 1 + X2 = 30 2 X 1 + 4(6) = 48
2X1 + 4X2 = 48 2X1 = 24
-3X = - 18 X1 = 12
X=6
Z6 = 8X1 + 6X2 + 0X3 + 0X4
= 8(12) + 6(6) + 0(0) + 0(0)
= 96+36132 (terbesar maksimum)

Oleh karena Z6 yang memberikan nilai tujuan terbesar maka Z6 = Z

maksimum = 132 dengan X₁ = 12 dan X2 = 6

2. (Kasus Maksimisasi)
Suatu perusahaan mengahsilkan 2 barang, yaitu A dan B. Masing-masing
barang membutuhkan sumberdaya seperti terlihat pada Tabel berikut.
Sumber daya Barang A Barang B Kapasitas
Sumberdaya
Bahan mentah 1 2 10
Buruh 6 6 36
Laba/unit 4000 5000 Maksimumkan
Peubah kegiatan X1 X2 Z
Disamping itu, menurut ramalan bagian penjualan permintaan barang A
tidak akan melebih 4 unit. Tentukan jumlah barang A dan B yang dihasilkan
sehingga memberikan laba maksimum bagi perusahaan.
Penyelesaian:
Model Program Linearnya:
Fungsi Tujuan: Z = 4000X1 + 5000X2 Maksimumkan
Fungsi Pembatas : X1 + 2X2≤ 10
6X1 + 6X2≤ 36
X1 ≤ 4
X1≥ 0 ,X2 ≥ 0
Dengan memasukkan slack variabels X3, X4 dan X5 kita peroleh tiga persamaan
berikut:
X1 + 2X2 + X3 = 0
6X1 + 6X2 + X4 = 36
X1 + X5 = 4
Dalam prakteknya X3, X4, dan X5 merupakan bahan mentah sisa, yaitu yang
tidak diproduksi. Maka dari itu C3, C4, dan C5 masing-masing nilainya sama
dengan 0, sebab tidak dijual. Persoalan Linear Programming di mana
ketidaksamaan sudah dirubah menjadi persamaan disebut persoalan Linear
Programming yang standar. Persoalan Linear Programming yang standar adalah
sebagai berikut:
Cari X1, X2, X3, X4, X5
Fungsi Tujuan: Z = 4000X1 + 5000X2 + 0X3 + 0X4 +n0X5 Maksimum
Fungsi Pembatas: X1 + 2X2 + X3 = 10
6X1 + 6X2 + X4 = 36
X1 + X5 = 4
X1 ≥ 0 , X2≥ 0, X3≥ 0, X4≥ 0, X5≥ 0
Dengan menggunakan rumus Kombinasi, maka diperoleh n = 4 dan m = 2
5! 5.4 ∙3 ∙ 2∙ 1 120
K= = = = 10
3 ! ( 5−3 ) ! 3.2 ∙1 ∙2 ∙ 1 12
Jadi, ada 10 persamaan dasar, dengan demikian ada 10 pemecahan dasar. Dari 10
pemecahan dasar ini, kita pilih pemecahan dasar yang fisibel. Nilai variabel dasar
sebagai pemecahan dasar yang fisibel ini, dimasukkan ke dalam Z = 4000X 1 +
5000X2+ 0X3 +0X5. Kemudian dipilih pemecahan dasar fisibel yang membuat
nilai Z menjadi maksimum. Pemecahan dasar fisibel inilah yang merupakan
pemecahan optimal.
10 persamaan dasar dengan pemecahan dasarnya adalah sebagai
berikut:

1. X1 = X2 = 0 (tidak ada produksi)

X1 + 2X2 + X3 = 10 → X 3 = 10
6X1 + 6X2 + X4 = 36 → X 4 = 36
X1 + X5 = 4 → X5 = 4
Z1 = 4000X1 + 5000X2 + 0X3 + 0X4 + 0X5
= 4000(0) + 5000(0) + 0(10) + 0(36) + 0(4)= 0 (tidak ada penjualan)
2. X1 = X3 = 0 (tidak ada produksi)

X1 + 2X2 + X3 = 10 → 2X2=10 → X2=5

6X1 + 6X2 + X4= 36 → 6X2+X4= 36

6(5) + X4= 36

30 + X4= 36

X4 = 36 - 30 = 6

X1+ X5 = 4 → X5 = 4

Z2 = 4000X1 + 5000X2 + 0X3 + 0X4 + 0X5

= 4000(0) + 5000(5) + 0(0) +0(6)+ 0(4) =25000
3. X1 = X4 = 0
X1 + 2X2 + X3 = 10 → 2X2 + X3 = 10
2(6) + X3 = 10
X3 = -2 (tidak fisibel)
6X1 + 6X2 + X4= 36 → 6X2 = 36 → X2 = 6

X1 + X5 = 4 → X5 = 4

Z3 tidak dihitung karena X3 negatif, jadi pemecahan tidak fesiel.

4. X1= X5 = 0
X1 + 2X2 + X3 = 10 → 2X2 + X3 = 10 → X3 = 0
6X1 + 6X2 + X4 = 36 → 6X2 + X4 = 36 → X2 = 5
X4 = 6
X1 + X5 = 4 (tidak fisibel)
Z4 tidak dihitung karena X1 + X5 = 4 tidak fisibel
5. X 2 =X 3=0
X1 + 2X2 + X3 = 10 → X 2=10
6X1 + 6X2 + X4= 36 → 6 X 1 + X 4=36
6(10) + X4 = 36
X 4=−24 (tidak fisibel )
X1 + X5 = 4 → X 5=−6
Z5 tidak dihitung karena X4 negatif, jadi pemecahan tidak fesiel.
6. X 2 =X 4 =0
X1 + 2X2 + X3 = 10 → X 1 + X 3=10 → X 3=4
6X1 + 6X2 + X4= 36 → 6 X 1=36 → X 1=6
X1 + X5 = 4 → X 5=−2
Z6 tidak dihitung karena X5 negatif, jadi pemecahan tidak fesiel.
7. X 2 =X 5=0
X1 + 2X2 + X3 = 10 → X 1 + X 3=10 → X 3=6
6X1 + 6X2 + X4= 36 → 6 X 1 + X 4=36 → X 4 =12
X1 + X5 = 4 → X 1=4
Z7 = 4000X1 + 5000X2 + 0X3 + 0X4 + 0X5
= 4000(4) + 5000(0) + 0(6) + 0(12) + 0(0) =16000

8. X 3 =X 4 =0
X1 + 2X2 + X3 = 10 → X 1 +2 X 2=10 → X 2=4
6X1 + 6X2 + X4= 36 → 6 X 1 +6 X 2=36 → X 1=2
X1 + X5 = 4 → X 5=2
Z8 = 4000X1 + 5000X2 + 0X3 + 0X4 + 0X5
= 4000(2) + 5000(4) + 0(0) + 0(0) + 0(2)

=28000 (terbesar = maksimum)

 9. X 3 =X 5=0
X1 + 2X2 + X3 = 10 → X 1 +2 X 2=10 → X 2=3
6X1 + 6X2 + X4= 36 → 6 X 1 +6 X 2 + X 4=36
6(4)+6(3) + X4 = 36
X 4=−6
X1 + X5 = 4 → X 1=4
Z9 tidak dihitung karena X4 negatif, jadi pemecahan tidak fesiel.
10. X 4= X 5=0
X1 + 2X2 + X3 = 10 → X 1 +2 X 2 + X 3=10 → X 3=2
6X1 + 6X2 + X4= 36 → 6 X 1 +6 X 2=36
6(4) + 6X2 = 36
24 + 6X2 = 36 → X 2=2
X1 + X5 = 4 → X 1=4
Z10 = 4000X1 + 5000X2 + 0X3 + 0X4 + 0X5
= 4000(4) + 5000(2) + 0(2) +0(0)+ 0(0) =26000

Kesimpulan: Barang A = 2 unit, barang B = 4 unit akan menghasilkan laba maks

Rp28.000.-

3. (kasus minimisasi)
Cari X 1 dan X 2
Fungsi tujuan: Z = 5 X 1 +3 X 2 Minimum
Fungsi pembatas: 2 X 1 + X 2 ≥3
X1+ X2≥ 2
X1 ≥ 0 , X2≥ 0
Harus dirubah dahulu menjadi persamaan standar dengan memasukkan Surplus
Variabels X3 dan X4 , yaitu variabel yang harus dikurangkan di dalam suatu
ketidaksamaan agar supaya menjadi persamaan. Persoalan yang standar adalah
sebagai berikut:
Cari X1 , X2, X3, X4
Fungsi tujuan : Z = 5 X 1 +3 X 2 +0 X 3 + 0 X 4 Minimum
Fungsi pembatas: 2 X 1 + X 2− X 3=3
X 1 + X 2−X 4=2
X1 ≥ 0 , X2≥ 0 , X3 ≥ 0 , X4 ≥ 0
1. X1 = X2 = 0
2X1 + X2 - X3 = 3 →− X 3 = 3, X 3 = -3
X1 + X2 – X4 = 2 →− X 4 = 3, X 4 = -2
Z1 tidak perlu dihitung karena pemecahan ini tidak fleksibel, X 3 dan X4
tidak memenuhi syarat (nilainya negative).
2. X1 = X3 = 0
2X1 + X2 - X3 = 3 →− X 2 = 3,
X1 + X2 – X4 = 2 → X 2− X 4 = 2
3 – X4 = 2
−X 4 = 2 – 3 = -1
X 4=1
Z2¿ 5 X 1 +3 X 2 +0 X 3 +0 X 3+ 0 X 4 =5 ( 0 ) +3 ( 3 ) +0 ( 0 ) +0 ( 1 ) =9
3. X1 = X4 = 0
2X1 + X2 - X3 = 3 → X 2− X 3 = 3,
X1 + X2 – X4 = 2 → X2 = 2
X 2 −X 3 = 3
2− X 3=3 →− X 3=3−2=1
X3 = -1 (tidak fisibel)
Z3 tidak perlu dihitung karena pemecahan ini tidak fleksibel (tidak
memenuhi syarat).
4. X2 = X3 = 0
3
2X1 + X2 - X3 = 3 → 2 X 1= 3 → X 1=
2
X1 + X2 – X4 = 2 → X 1−X 4 = 2
3
−X 4 =2
2
3 4 −1
X 4= − = (tidak fisibel)
2 2 2
Z4 tidak perlu dihitung karena pemecahan ini tidak fleksibel (tidak
memenuhi syarat).
5. X2 = X4 = 0
2X1 + X2 - X3 = 3 → 2 X 1−X 3 = 3
X1 + X2 – X4 = 2 → X1 = 2
2 X 1− X 3=3 →2 ( 2 )− X 3=3
4− X 3=3
X 3 =1
Z5¿ 5 X 1 +3 X 2 +0 X 3 +0 X 3+ 0 X 4 =5 ( 2 )+ 3 ( 0 ) +0 ( 1 ) +0 ( 0 )=10
6. X3 = X4 = 0
2X1 + X2 - X3 = 3 → 2 X 1+ X 2= 3
X1 + X2 – X4 = 2 →X1 + X2 = 2
X 1= 1
X 1 + X 2=2→ X 2=2−1=1
Z6¿ 5 X 1 +3 X 2 +0 X 3 +0 X 3+ 0 X 4 =5 ( 1 )+ 3 ( 1 ) + 0 ( 0 )+ 0 ( 0 )=8
Z6 = Zmin karena merupakan nilai tujuan yang terkecil apabila
dibandingkan dengan nilai tujuan lainnya. Pemecahan optimal
memberikan nilai Z = 8 dengan X1 = X2 =1