Oleh :
Abdullah M. Jaubah
Pendahuluan
Tulisan ini disusun dengan tujuan membahas
pemrograman garis lurus (linear
programming) termasuk masalah transportasi dan masalah penugasan. Ujian mengenai
pemrograman garis lurus pada tahun 1957 membutuhkan waktu sangat lama karena
perhitungan dilakukan secara manual akan tetapi sekarang dapat dilakukan dengan
sangat cepat karena memanfaatkan perangkat lunak komputer.
Para
manajer pada tingkat pengawasan operasional, tingkat pengawasan manajemen, dan
tingkat perencanaan strategis dalam suatu organisasi berwenang dan
bertanggungjawab atas keputusan-keputusan yang diambil oleh mereka.
Keputusan-keputusan manajerial dapat dikelompokkan menurut beberapa cara.
Kesatu
adalah pengelompokan keputusan-keputusan manajerial ke dalam
keputusan-keputusan kuantitatif dan keputusan-keputusan kualitatif. Kedua
adalah pengelompokan keputusan-keputusan manajerial ke dalam
keputusan-keputusan individual dan keputusan-keputusan kelompok. Ketiga adalah
pengelompokan keputusan-keputusan manajerial ke dalam keputusan-keputusan pada
tingkat pengawasan operasional, keputusan-keputusan pada tingkat pengawasan
manajemen, dan keputusan-keputusan pada tingkat perencanaan strategis. Keempat
adalah pengelompokan keputusan-keputusan manajerial ke dalam
keputusan-keputusan jangka pendek dan keputusan-keputusan jangka panjang.
Kelima adalah pengelompokan keputusan-keputusan manajerial ke dalam
keputusan-keputusan menurut fungsi-fungsi suatu organisasi yaitu keputusan
manajemen keuangan, keputusan manajemen operasi, keputusan manajemen pemasaran,
keputusan manajemen sumber daya manusia, keputusan manajemen penelitian dan
pengembangan, keputusan manajemen sistem
informasi, dan keputusan fungsi-fungsi organisasi lainnya. Keenam adalah
pengelompokkan keputusan-keputusan manajerial menurut fungsi-fungsi manajemen
yaitu keputusan-keputusan perencanaan, keputusan-keputusan pengaturan,
keputusan-keputusan pengisian pekerjaan dan jabatan, keputusan-keputusan
pengarahan, dan keputusan-keputusan pengawasan. Kombinasi pengelompokan
keputusan-keputusan manajerial mungkin pula disusun. Contoh kombinasi
pengelompokan keputusan-keputusan manajerial ke dalam keputusan manajemen
keuangan, keputusan manajemen operasi, keputusan manajemen pemasaran, keputusan
manajemen sumber daya manusia, keputusan manajemen penelitian dan pengembangan,
keputusan manajemen sistem informasi
pada tingkat pengawasan operasional, pengawasan manajemen, dan pada tingkat
perencanaan strategis.
Keputusan Manajerial Bersifat Kuantitatif
Keputusan-keputusan
kuantitatif dapat mencakup keputusan-keputusan berdasar atas landasan
matematika dan statistika. Pengelompokan ini, sebagaimana dikemukakan oleh
Bernard W. Taylor III dalam bukunya yang berjudul Introduction
to Management Science (1993 : 6), dapat mencakup linear matematical programming, probability techniques, inventory
techniques, network techniques, and
other linear and nonlinear techniques.
Keputusan-keputusan
manajerial dalam kelompok keputusan-keputusan kuantitatif yang tercakup dalam penelitian operasi (Operation Research) antara lain mencakup
keputusan-keputusan manajerial berdasar atas hasil-hasil perhitungan
pemrograman garis lurus (linear
programming), pemrograman semua bilangan bulat (all integer programming), pemrograman nol satu (zero one programming), pemrograman
sasaran (goal programming),
teransportasi (transportation),
penugasan (assignment), analisis
titik keseimbangan (break-even analysis),
teori keputusan (decision theory),
model-model jaringan kerja (network
models), manajemen proyek (Critical
Path Method/ Program Evaluation and Review Techniques), model-model
persediaan (inventory models), teori
antrian (queueing theory),
pemrograman dinamis (dynamic programming),
simulasi (simulation), peramalan (forecasting), analisis Markov (Markov analysis), dan teori permainan (game theory).
Teori
keputusan dirinci lebih lanjut ke dalam pengambilan keputusan dalam keadaan
yang mengandung unsur risiko, pengambilan keputusan dalam keadaan yang
mengandung unsur ketidaktentuan, pohon keputusan (decision tree), dan aturan
keputusan Bayes (Bayes’ decision rule).
Model-model
jaringan kerja dirinci lebih lanjut ke dalam rute paling pendek (shortest
rute), minimum spanning tree, dan aliran maksimum (maximum flow).
Manajemen
proyek dirinci lebih lanjut ke dalam PERT, CPM, dan CPM with Crashing.
Model-model
persediaan dirinci lebih lanjut ke dalam analisis ABC (ABC analysis), kuantitas
pesanan ekonomis (economic order quantity), economic lot size, kekurangan
terencana (planned shortage), dan diskon kuantitas (quantity discount).
Teori
antrian dirinci lebih lanjut ke dalam pelayanan standar tunggal (standard
single server), pelayanan jamak (multiple server), pelayanan konstan (constant server), dan populasi terbatas (limited population).
Pemrograman
dinamis dirinci lebih lanjut ke dalam stagecoach, general non-network, Knapsack, dan penjadwalan (scheduling).
Simulasi
dirinci lebih lanjut ke dalam simulasi Monte Carlo (Monte Carlo simulation) dan simulasi persediaan (inventory
simulation).
Peramalan
dirinci lebih lanjut ke dalam rata-rata bergerak sederhana dan tertimbang (simple and weighted moving average),
penghalusan eksponensial (exponential
smoothing), metode kuadrat terkecil (least
squares method), regresi sederhana (simple
regression), dan regresi jamak (multiple
regression).
Uraian
di atas mengungkap bahwa pengambilan keputusan kuantitatif berdasar atas
matematika dan statistika. Perhatian
para manajer akan terpusat pada landasan
yang kuat sebagai basis untuk proses pengambilan keputusan manajerial bukan
terpusat pada rincian perhitungan matematika dan statistika.
Proses
observasi lingkungan masalah, analisis dan identifikasi masalah, perumusan
masalah dalam bentuk pengembangan model, pemilihan data masukan, perumusan
pemecahan masalah dan pengujian yang dapat dipertanggungjawabkan, pengambilan keputusan, dan penerapan
keputusan mencerminkan gambaran dari proses pemecahan masalah dan pengambilan
keputusan manajerial berdasar atas metode ilmiah. Cara-cara perumusan dan
pemecahan masalah-masalah di atas dicakup dalam penelitian operasi dan menjadi
pokok pembahasan di sini.
Pengambilan
keputusan secara kuantitatif terdapat pula dalam manajemen operasi atau
manajemen produksi. Keputusan-keputusan dalam manajemen operasi, sebagaimana dikemukakan
oleh Roberta S. Russell dan Bernard W. Taylor III dalam multimedia CD dengan
judul Operations Management, mencakup
keputusan-keputusan mengenai :
1.
Decision analysis.
2.
Quality control.
3.
Statistical quality control.
4.
Product and service design.
5.
Process planning, analysis, and reengineering.
6.
Facility layout.
7.
Human resources in operations management.
8.
Supply chain management.
9.
Transportation model.
10.
Forecasting.
11.
Capacity planning.
12.
Aggregate production planning.
13.
Linear programming.
14.
Inventory management.
15.
Simulation
16.
Material Requirement Planning.
17.
Scheduling.
18.
Waiting line models.
19.
Project management.
Computer Models for Operations
Management mengandung perangkat pengambilan keputusan
mengenai :
1.
Forecasting
2.
Work Measurement and Learning Curve.
3.
Capacity Planning.
4.
Aggregate Planning.
5.
Location Analysis.
6.
Layout Design.
7.
Independent Demand Inventory Systems.
8.
Material Requirements Planning.
9.
Scheduling.
10.
Project Planning and Control.
11.
Quality Control.
12.
Financial Analysis.
13.
Queuing and Waiting Line.
14.
Linear Programming.
Berbagai
model telah dikembangkan dalam bidang penelitian operasi dan manajemen operasi.
Model-model ini dipakai untuk membantu para manajer dalam proses pengambilan
keputusan secara kuantitatif.
Penelitian Operasi
Para
manajer bekerja dalam suatu lingkungan dinamis yaitu lingkungan yang mengalami
perubahan secara terus-menerus. Banyak perubahan dapat diprakarsasi oleh para
manajer itu sendiri tetapi perubahan itu biasanya tidak diprakarsasi oleh
mereka. Daur produk diperpendek, dan perkembangan teknologi terjadi secara
pesat. Lingkungan sosial dan politik merupakan faktor-faktor penting dari
perubahan karena perusahaan-perusahaan sangat dipengaruhi oleh perubahan dalam
lingkungan sosial dan politik. Perusahaan-perusahaan sekarang sangat tergantung
pada metode kuantitatif dan komputer untuk memecahkan masalah-masalah rutin dan
masalah-masalah kompleks yang terstruktur.
Para
manajer mempunyai beberapa pendekatan
dalam mengolah, menganalisis, menafsirkan, dan memecahkan
masalah-masalah bisnis mereka. Kompleksitas masalah mengindikasikan metode
analisis yang serasi. Pendekatan konvensional mengikuti teknik-teknik dan
pemecahan-pemecahan masa lalu. Teknik-teknik ini adalah statis sedangkan bisnis
itu sendiri adalah dinamis. Pendekatan kedua adalah pendekatan observasi yaitu pendekatan melalui pengamatan dan
pembelajaran dari para manajer lain dalam situasi-situasi serupa. Penekatan ini
juga mengandung kelemahan tetapi perbaikan dapat dilakukan untuk memperbaiki
suatu teknik tertentu. Pendekatan lain terhadap pemecahan atas masalah-masalah
bisnis adalah pendekatan sistematis. Pendekatan ini memanfaatkan konsep dari
teori sistem yang mungkin saja berbeda dari masalah sesungguhnya yang sedang
dipelajari. Pendekatan sistematis bermanfaat dalam memperoleh suatu pemecahan
akhir karena pendekatan ini memanfaatkan bauran pendekatan yaitu metode ilmiah.
Sejarah
penelitian operasi sulit ditelusuri secara formal. Para pakar selalu terlibat
dalam kegiatan militer. F. W. Lancester
di Inggris menerbitkan makalah tentang hubungan teoretis antara kemenangan
(victory) dan superioritas dalam tenaga kerja dan kekuatan perang. Thomas Alva
Edison, di Amerika Serikat, mempelajari
proses perang anti kapal selam. Edison mengumpulkan statistik yang dipakai
untuk menganalisis gerakan agar kapal laut biasa mampu menenggelamkan dan menghancurkan kapal selam. Edison
mewariskan suatu permainan perang untuk dipakai dalam simulasi masalah
pergerakan yang berhubungan dengan lautan. Edison menganalisis taktik berliku-liku dari kapal-kapal dagang
dalam usaha menghindari kapal selam.
Thomas Edison memakai suatu ‘tactical game board; untuk pemecahan
masalah tersebut. A. K. Erlang di
Denmark telah melaksanakan
eksperimen-eksperimen yang melibatkan
fluktuasi permintaan akan
fasilitas telepon. Pekerjaannya merupakan fondasi dari model-model matematika
yang dipakai dalam teori antrian. A. K. Erlang menerbitkan karya tulisnya
dengan judul Pemecahan Beberapa Masalah
dalam Teori Probabilita atas peranan penting pola panggilan Telepon Secara Otomatis.
Tulisan ini berbentuk rumus dari waktu menunggu yang telah dikembangkannya
berdasar atas prinsip-prinsip statisitik. Rumus ini sekarang dikenal sebagai
dasar dari teori lalu lintas telepon.
Horace
C. Levenson menerapkan model-model matematika pada data yang sangat besar.
Studi tingkat penolakan para pelanggan sebesar 30 persen dari penjualan kotor
merupakan studi yang sangat menarik dan sangat terkenal. Dua sebab dari
penolakan diisolasi yaitu pesanan-pesanan yang mahal akan lebih sering ditolak
dan barang yang dikirim lebih lama daripada lima hari setelah pesanan diterima.
Para
pakar di Inggris, mulai dalam tahun 1937, telah diminta untuk membantu militer
belajar bagaimana memakai radar yang
baru saja dikembangkan dalam menempatkan pesawat tempur musuh. Para pakar ini
bekerja dalam aspek-aspek masalah yang berbeda, dikumpulkan dalam bulan
September tahun 1939 di H. Q Fighter Command. Kelompok ini dianggap sebagai
perintis dari kelompok penelitian operasi pertama. Anti-Aircraft Command
Research Group, tidak lama setelah kelompok ini terbentuk, diminta mempelajari
masalah anti-pesawat terbang. P. M. S. Blackett memimpin kelompok ini. Mereka
mempelajari kinerja dari peralatan pengawasan senjata di lapangan, terutama
selama pemakaian oleh angkatan darat terhadap musuh. Kelompok ini kemudian
dikenal dengan nama Blackett Circus yang terdiri dari sebelas pakar dari
berbagai disiplin ilmu. Mereka kemudian dibagi ke dalam kelompok untuk angkatan
darat dan kelompok untuk angkatan laut sehingga militer Inggris mempunyai
kelompok penelitian operasi yang bekerja dalam penelitian militer pada saat
awal perang dunia ke 2 atau pada tahun 1941. Jenis kegiatan ilmiah ini dikenal
di Inggris sebagai Operational Research.
Sir
Robert Watson-Watt menyatakan telah melancarkan studi tentang Operational
Research dalam tahun 1937 menyarankan operations research diperkenalkan
ke dalam department of the Secretary of
War dan the Secretary of the Navy di Amerika Serikat. Keputusan untuk
memperkenalkan penelitian operasi diambil pada bulan April tahun 1942 pada
tingkat tinggi telah dilakukan. Masalah-masalah awal mencakup radar dan
pengembangan konvoi kapal dagang yang dirancang untuk meminimisasikan kerugian
dari serangan kapal selam musuh. Operational
Analysis dikenal dalam U. S. Army. Operations Research and Operations
Evaluation dikenal dalam U. S. Navy.
George
B. Dantzig, dalam tahun 1947, mengembangkan pemecahan simpleks untuk masalah
pemrograman garis lurus yang telah dirintis oleh W. Leontieff. Penelitian
operasi kemudian juga dikembangkan dalam dunia bisnis di samping dikembangkan
dalam dunia militer.
Penelitian
operasi atau ilmu manajemen atau ilmu keberhasilan memakai model-model
tertentu.
Definisi penelitian operasi
Jenis-jenis
model adalah model
ikonik atau fisik, analog atau diagramatik, simbolik atau model matematika.
Jenis-jenis
model matematika mencakup model kuantitatif, kualitatif,
standar, kostum, probabilitas, deterministik, deskriptif, optimisasi,
statis, dinamis, simulasi, non-simulasi.
Perumuan Masalah, Batasan atau Kendala dan Pengambilan Keputusan
Pusat
perhatian manajer terarah pada perumusan masalah, batasan atau kendala-kendala, dan pengambilan
keputusan berdasar atas hasil-hasil pemecahan masalah, bukan terjebak dalam
rincian hasil-hasil perhitungan.
Pemrograman Garis Lurus
Beberapa
contoh dari pemrograman garis lurus akan diberikan di sini. Bernard W. Taylor
III (1996) dalam bukunya yang berjudul Sains
Manajemen (Pendekatan Matematika Untuk Businis) memberikan contoh sebagai
berikut :
Contoh
:
Manajer
menghadapi keadaan yang membutuhkan pengambilan keputusan. Keadaan ini adalah
sebagai berikut : Laba per unit produk A adalah sebesar Rp 8 dan laba per unit
produk B adalah sebesar Rp 10. Produksi atas produk A per unit membutuhkan jam
kerja (x1) sebanyak 2 jam dan produk B per unit membutuhkan sebanyak 4 jam kerja. Produk A per unit
membutuhkan bahan baku sebanyak 8 kg dan produk B per unit membutuhkan bahan
baku sebanyak 6 kg. Jam kerja yang tersedia adalah sebanyak 80 jam dan bahan
baku yang tersedia adalah sebanyak 240 kg.
Manajer
itu ingin merumuskan masalah tersebut di atas, ingin mengetahui jumlah produk A
dan produk B yang harus diproduksi agar organisasi dapat memperoleh maksimisasi
laba, dan ingin mengetahui maksimisasi laba yang akan dicapai oleh organisasi
itu. Manajer meminta stafnya untuk merumuskan dan memecahkan masalah tersebut.
Staf ahli dari manajer itu melakukan perumusan masalah dalam bentuk hubungan
matematika. Hubungan ini dapat dilakukan sebagai berikut :
Max. Z =
8x1 + 10x2
Subject
to
C1 2x1 + 4x2 <= 80
C2 8x1 + 6x2 <= 240
Pemecahan
masalah ini adalah sebagai berikut :
Program: Linear
Programming
Problem Title :
Produksi
***** Input Data
*****
Max. Z =
8x1 + 10x2
Subject to
C1 2x1 + 4x2 <= 80
C2 8x1 + 6x2 <= 240
***** Program
Output *****
Final Optimal Solution
At Simplex Tableau : 2
Z = 272.000
----------------------------------------
Variable Value Reduced Cost
----------------------------------------
x 1
24.000 0.000
x 2
8.000 0.000
----------------------------------------
Constraint Slack/Surplus Shadow Price
----------------------------------------
C 1
0.000 1.600
C 2
0.000 0.600
----------------------------------------
Objective
Coefficient Ranges
--------------------------------------------------------------------
Lower Current Upper
Allowable Allowable
Variables Limit
Values Limit Increase
Decrease
--------------------------------------------------------------------
x 1
5.000 8.000 13.333 5.333 3.000
x 2
6.000 10.000 16.000 6.000 4.000
Right Hand Side
Ranges
--------------------------------------------------------------------
Lower Current Upper
Allowable Allowable
Constraints Limit
Values Limit Increase
Decrease
--------------------------------------------------------------------
C 1
60.000 80.000 160.000 80.000 20.000
C 2
120.000 240.000 320.000 80.000
120.000
***** End of
Output *****
Pemecahan
optimal adalah bahwa laba maksimum dicapai sebesar 272 jika produk A diproduksi
sebanyak 8 unit dan produk B diproduksi sebanyak 24 unit. Nilai laba sebesar
$272 berasal dari 24 x $10 = $240 ditambah 8 x $ 4 = $ 32 sehingga laba adalah
sebesar $ 272.
Penanam
modal perorangan mempunyai $70000 untuk dibagi ke dalam beberapa macam
investasi. Investasi yang dipilih adalah investasi dalam obligasi pemerintah
dengan tingkat balas jasa sebesar 8.5%, sertifikat deposito dengan tingkat
balas jasa sebesar 10%, Treasury Bills
dengan tingkat balas jasa sebesar 6.5%, dan obligasi pendapatan dengan
tingkat balas jasa sebesar 13%. Jumlah waktu sampai dengan jatuh tempo adalah
sama untuk tiap pilihan. Setiap pilihan investasi mempunyai perbedaan risiko
yang terlihat oleh penanam modal, oleh karena itu lebih baik untuk melakukan
diversifikasi investasi. Penanam modal ingin mengetahui berapakah besar investasi
yang diperlukan untuk setiap pilihan dalam rangka memaksimumkan tingkat balas
jasa atas investasi itu?
Pedoman
yang ditetapkan untuk melakukan diversifikasi investasi dan mengurangi risiko
yang terlihat oleh penanam modal adalah sebagai berikut :
1. Total
investasi dalam bentuk obligasi pendapatan adalah tidak lebih daripada 20%.
2. Jumlah
yang diinvestasikan dalam sertifikat deposito tidak boleh melebihi jumlah yang
diinvestasikan dalam ketiga pilihan yang lain.
3. Investasi
paling sedikit 30% harus dalam Treasury Bills dan sertifikat deposito.
4. Perbandingan
antara jumlah yang diinvestasikan dalam obligasi pemerintah dengan jumlah yang
diinvestasikan dalam Treasury Bills tidak boleh melebihi satu dibandingkan
tiga.
Variabel-variabel
keputusan terdiri dari empat variabel yang menunjukkan jumlah dana yang
diinvestasikan dalam setiap pilihan yaitu :
X1
adalah jumlah $ yang diinvestasikan dalam obligasi pemerintah
X2
adalah jumlah $ yang diinvestasikan dalam sertifikat deposito
X3
adalah jumlah $ yang diinvestasikan dalam Treasury Bills
X4
adalah jumlah $ yang diinvestasikan dalam obligasi pendapatan
Fungsi
Tujuan
Tujuan
dari penanam modal adalah untuk memaksimumkan balas jasa total investasi dalam
empat pilihan tersebut. Total balas jasa adalah penggabungan dari tingkat balas
jasa setiap pilihan. Fungsi tujuan dapat dirumuskan sebagai berikut :
Z
=$0.085X1+ 0.10X2 + 0.065X3 + 0.130X4
Batasan
Model adalah sebagai berikut :
X4≤14000
X2≤X1+X3+X4
X2+X3≥21000
3X1-X3≤0
X1+X2+X3+X4=70000
X1
≥ 0
X2
≥ 0
X3
≥ 0
X4
≥ 0
Penyelesaian
fungsi tujuan dengan mempertimbangkan kendala-kendala di atas adalah sebagai
berkut :
Program: Linear
Programming
Problem Title :
Pemrograman Garis Lurus
Max. Z =
0.085x1 + 0.100x2 + 0.065x3 + 0.130x4
Subject to
C1 1x4 <= 14000
C2 -1x1 + 1x2 - 1x3 - 1x4 <= 0
C3 1x2 + 1x3 >= 21000
C4 3x1 - 1x3 <= 0
C5 1x1 + 1x2 + 1x3 + 1x4 = 70000
C6 1x1 >= 0
C7 1x2 >= 0
C8 1x3 >= 0
C9 1x4 >= 0
Simplex Tableau
: 0
\Cj 0.085 0.100
0.065 0.130
Cb \
Basis Bi x
1 x 2
x 3 x
4
----------------------------------------------------------------------------
0.000
s 1 14000.000
0.000 0.000 0.000
1.000
0.000
s 2
0.000 -1.000 1.000
-1.000 -1.000
0.000
s 4 0.000
3.000 0.000 -1.000
0.000
-M
A 3 21000.000
0.000 1.000 1.000
0.000
-M
A 5 70000.000
1.000 1.000
1.000 1.000
-M
A 6 0.000
1.000 0.000 0.000
0.000
-M
A 7 0.000
0.000 1.000 0.000
0.000
-M
A 8 0.000
0.000 0.000 1.000
0.000
-M
A 9 0.000
0.000 0.000 0.000
1.000
----------------------------------------------------------------------------
Zj *-M* -M -M -M -M
Cj-Zj M M M M
\Cj 0.000 0.000
0.000 0.000
Cb \
Basis Bi s
1 s 2
s 4 S
3
----------------------------------------------------------------------------
0.000
s 1 14000.000
1.000 0.000 0.000
0.000
0.000
s 2 0.000
0.000 1.000 0.000
0.000
0.000
s 4 0.000
0.000 0.000 1.000
0.000
-M
A 3 21000.000
0.000 0.000 0.000
-1.000
-M
A 5 70000.000
0.000 0.000 0.000
0.000
-M
A 6 0.000
0.000 0.000 0.000
0.000
-M
A 7 0.000
0.000 0.000 0.000
0.000
-M
A 8 0.000
0.000 0.000 0.000
0.000
-M
A 9 0.000
0.000 0.000 0.000
0.000
----------------------------------------------------------------------------
Zj *-M* 0.000
0.000 0.000 M
Cj-Zj 0.000 0.000
0.000 -M
\Cj 0.000 0.000
0.000 0.000
Cb \
Basis Bi S
6 S 7
S 8 S
9
----------------------------------------------------------------------------
0.000
s 1 14000.000
0.000 0.000 0.000
0.000
0.000
s 2 0.000
0.000 0.000 0.000
0.000
0.000
s 4 0.000
0.000 0.000 0.000
0.000
-M
A 3 21000.000
0.000 0.000 0.000
0.000
-M
A 5 70000.000
0.000 0.000 0.000
0.000
-M
A 6 0.000
-1.000 0.000 0.000
0.000
-M
A 7 0.000
0.000 -1.000 0.000
0.000
-M
A 8 0.000
0.000 0.000 -1.000
0.000
-M
A 9 0.000
0.000 0.000 0.000
-1.000
----------------------------------------------------------------------------
Zj *-M* M M M M
Cj-Zj -M -M
-M -M
\Cj -M -M -M -M
Cb \
Basis Bi A
3 A 5
A 6 A
7
----------------------------------------------------------------------------
0.000
s 1 14000.000
0.000 0.000 0.000
0.000
0.000
s 2 0.000
0.000 0.000 0.000
0.000
0.000
s 4 0.000
0.000 0.000 0.000
0.000
-M
A 3 21000.000
1.000 0.000 0.000
0.000
-M
A 5 70000.000
0.000 1.000 0.000
0.000
-M
A 6 0.000
0.000 0.000 1.000
0.000
-M
A 7 0.000
0.000 0.000 0.000
1.000
-M
A 8 0.000
0.000 0.000 0.000
0.000
-M
A 9 0.000
0.000 0.000 0.000
0.000
----------------------------------------------------------------------------
Zj *-M* -M -M -M -M
Cj-Zj 0.000 0.000
0.000 0.000
\Cj -M -M
Cb \
Basis Bi A
8 A 9
----------------------------------------------------------------------------
0.000
s 1 14000.000
0.000 0.000
0.000
s 2 0.000
0.000 0.000
0.000
s 4 0.000
0.000 0.000
-M
A 3 21000.000
0.000 0.000
-M
A 5 70000.000
0.000 0.000
-M
A 6 0.000
0.000 0.000
-M
A 7 0.000
0.000 0.000
-M
A 8 0.000
1.000 0.000
-M
A 9 0.000
0.000 1.000
----------------------------------------------------------------------------
Zj *-M* -M -M
Cj-Zj 0.000 0.000
Simplex Tableau
: 9
\Cj 0.085 0.100
0.065 0.130
Cb \
Basis Bi x
1 x 2
x 3 x
4
----------------------------------------------------------------------------
0.000
S 9 14000.000
0.000 0.000
0.000 0.000
0.100
x 2 35000.000
0.000 1.000 0.000
0.000
0.085
x 1 5250.000
1.000 0.000 0.000
0.000
0.000
S 6 5250.000
0.000 0.000 0.000
0.000
0.000
S 3 29750.000
0.000 0.000 0.000
0.000
0.000
S 8 15750.000
0.000 0.000 0.000
0.000
0.065
x 3 15750.000
0.000 0.000 1.000
0.000
0.000
S 7 35000.000
0.000 0.000 0.000
0.000
0.130
x 4 14000.000
0.000 0.000 0.000
1.000
----------------------------------------------------------------------------
Zj 6790.000 0.085
0.100 0.065 0.130
Cj-Zj 0.000 0.000
0.000 0.000
\Cj 0.000 0.000
0.000 0.000
Cb \
Basis Bi s
1 s 2
s 4 S
3
----------------------------------------------------------------------------
0.000
S 9 14000.000
1.000 0.000 0.000
0.000
0.100
x 2 35000.000
0.000 0.500 0.000
0.000
0.085
x 1
5250.000 -0.250 -0.125
0.250 0.000
0.000
S 6 5250.000
-0.250 -0.125 0.250
0.000
0.000
S 3 29750.000
-0.750 0.125 -0.250
1.000
0.000
S 8 15750.000
-0.750 -0.375
-0.250 0.000
0.065
x 3 15750.000
-0.750 -0.375 -0.250
0.000
0.000
S 7 35000.000
0.000 0.500 0.000
0.000
0.130
x 4 14000.000
1.000 0.000 0.000
0.000
----------------------------------------------------------------------------
Zj 6790.000 0.060
0.015 0.005 0.000
Cj-Zj -0.060 -0.015
-0.005 0.000
\Cj 0.000 0.000
0.000 0.000
Cb \
Basis Bi S
6 S 7
S 8 S
9
----------------------------------------------------------------------------
0.000
S 9 14000.000
0.000 0.000 0.000
1.000
0.100
x 2 35000.000
0.000 0.000 0.000
0.000
0.085
x 1 5250.000
0.000 0.000 0.000
0.000
0.000
S 6 5250.000
1.000 0.000 0.000
0.000
0.000
S 3 29750.000
0.000 0.000 0.000
0.000
0.000
S 8 15750.000
0.000 0.000 1.000
0.000
0.065
x 3 15750.000
0.000 0.000 0.000
0.000
0.000
S 7 35000.000 0.000
1.000 0.000 0.000
0.130
x 4 14000.000
0.000 0.000 0.000
0.000
----------------------------------------------------------------------------
Zj 6790.000 0.000
0.000 0.000 0.000
Cj-Zj 0.000 0.000
0.000 0.000
\Cj -M -M -M -M
Cb \
Basis Bi A
3 A 5
A 6 A
7
----------------------------------------------------------------------------
0.000
S 9 14000.000
0.000 0.000 0.000
0.000
0.100
x 2 35000.000
0.000 0.500 0.000
0.000
0.085
x 1 5250.000
0.000 0.125
0.000 0.000
0.000
S 6 5250.000
0.000 0.125 -1.000
0.000
0.000
S 3 29750.000
-1.000 0.875 0.000
0.000
0.000
S 8 15750.000
0.000 0.375 0.000
0.000
0.065
x 3 15750.000
0.000 0.375 0.000
0.000
0.000
S 7 35000.000
0.000 0.500 0.000
-1.000
0.130
x 4 14000.000
0.000 0.000 0.000
0.000
----------------------------------------------------------------------------
Zj 6790.000 0.000
0.078 0.000 0.000
Cj-Zj -M -M -M -M
\Cj -M -M
Cb \
Basis Bi A
8 A 9
----------------------------------------------------------------------------
0.000
S 9 14000.000
0.000 -1.000
0.100
x 2 35000.000
0.000 0.000
0.085
x 1 5250.000
0.000 0.000
0.000
S 6 5250.000
0.000 0.000
0.000
S 3 29750.000
0.000 0.000
0.000
S 8 15750.000
-1.000 0.000
0.065
x 3 15750.000
0.000 0.000
0.000
S 7 35000.000
0.000 0.000
0.130
x 4 14000.000
0.000 0.000
---------------------------------------------------------------------
Zj 6790.000 0.000
0.000
Cj-Zj -M
-M
Final Optimal
Solution
Z = 6790.000
----------------------------------------
Variable Value Reduced Cost
----------------------------------------
x 1
5250.000 0.000
x 2
35000.000 0.000
x 3
15750.000 0.000
x 4
14000.000 0.000
------------------------------------------------
Constraint Slack/Surplus Shadow Price
----------------------------------------
C 1
0.000 0.060
C 2
0.000 0.015
C 3
29750.000 0.000
C 4
0.000 0.005
C 6
5250.000 0.000
C 7
35000.000 0.000
C 8
15750.000 0.000
C
9 14000.000 0.000
----------------------------------------
Objective
Coefficient Ranges
--------------------------------------------------------------------
Lower Current Upper
Allowable Allowable
Variables Limit
Values Limit Increase
Decrease
--------------------------------------------------------------------
x 1
0.065 0.085 0.205 0.120 0.020
x 2
0.070 0.100 No limit
No limit 0.030
x 3
No limit 0.065 0.085 0.020
No limit
x 4
0.070 0.130 No limit
No limit 0.060
Right Hand Side
Ranges
--------------------------------------------------------------------
Lower Current Upper
Allowable Allowable
Constraints Limit
Values Limit Increase
Decrease
--------------------------------------------------------------------
C 1
0.000 14000.000 35000.000
21000.000 14000.000
C 2
-70000.000 0.000 42000.000
42000.000 70000.000
C 3
No limit 21000.000 50750.000
29750.000 No limit
C 4
-21000.000 0.000 63000.000
63000.000 21000.000
C 5
36000.000 70000.000 No limit
No limit 34000.000
C 6
No limit 0.000 5250.000
5250.000 No limit
C 7
No limit 0.000 35000.000
35000.000 No limit
C 8
No limit 0.000 15750.000
15750.000 No limit
C 9
No limit 0.000 14000.000
14000.000 No limit
Tingkat balas jasa maksimum sebesar $6790 akan
diperoleh jika penanam modal menginvestasikan dana tersebut dalam
diinvestasikan dalam obligasi pemerintah
adalah sebesar $ 5250, diinvestasikan dalam sertifikat
deposito adalah sebesar $ 35000, diinvestasikan dalam Treasury Bills adalah sebesar $ 15750, dan dana yang diinvestasikan dalam obligasi pendapatan adalah sebesar $ 14000.
Contoh di atas adalah contoh dalam keuangan. Contoh
dalam pemasaran dapat juga diberikan di sini. Jaringan toko serba ada Permata
Indah menyewa perusahaan periklanan untuk menentukan jenis dan jumlah iklan
yang harus diperoleh untuk toko tersebut. Jenis iklan, tampilan (jumlah orang
atau iklan komersial atau iklan surat kabar) dan biaya dapat disusun sebagai
berikut :
|
Jenis
Iklan
|
Tampilan
|
Biaya
|
|
Televisi
Komersial
|
20000
|
$15,000
|
|
Radio
Komersial
|
12000
|
6000
|
|
Iklan
Surat Kabar
|
9000
|
4000
|
Perusahaan harus mempertimbangkan kendala atau batasan
atas sumberdaya sebagai berikut :
1. Batas
anggaran untuk iklan adalah $100000
2. Stasiun
Televisi mempunyai 4 waktu komersial
3. Stasiun
Radio mepunyai 10 waktu komersial
4. Surat
kabar mempunyai jatah yang tersedia untuk
iklan
5. Perusahaan iklan mempunyai waktu dan
karyawan yang tersedia untuk memproduksi tidak melebihi 15 komersial atau
iklan.
Masalah ini dapat dirumuskan dengan tujuan minimisasi
biaya sebagai berikut :
Z=$0.04X1 + 0.06X2 + 0.02X3
Dengan kendala :
10X1+20X2+8X3≥100
7X1 + 14X2 + 12X3 ≥ 70
X1 ≥ 0
X2 ≥ 0
X3 ≥ 0
Penyelesaian masalah pemasaran ini adalah sebagai
berikut :
Program: Linear
Programming
Problem Title :
Pemasaran
***** Input Data
*****
Min. Z =
0.04x1 + 0.06x2 + 0.02x3
Subject to
C1 10x1 + 20x2 + 8x3 >= 100
C2 7x1 + 14x2 + 12x3 >= 70
C3 1x1 >= 0
C4 1x2 >= 0
C5 1x3 >= 0
***** Program
Output *****
Simplex Tableau
: 0
\Cj 0.040 0.060
0.020 0.000
Cb \
Basis Bi x
1 x 2
x 3 S
1
----------------------------------------------------------------------------
M
A 1 100.000
10.000 20.000 8.000
-1.000
M
A 2 70.000
7.000 14.000 12.000
0.000
M
A 3 0.000
1.000 0.000 0.000
0.000
M
A 4 0.000
0.000 1.000 0.000
0.000
M
A 5 0.000
0.000 0.000 1.000
0.000
----------------------------------------------------------------------------
Zj *+M* M M M -M
Zj-Cj M M M -M
\Cj 0.000 0.000
0.000 0.000
Cb \
Basis Bi S
2 S 3
S 4 S
5
----------------------------------------------------------------------------
M
A 1 100.000
0.000 0.000 0.000
0.000
M
A 2 70.000
-1.000 0.000 0.000
0.000
M
A 3 0.000
0.000 -1.000 0.000
0.000
M
A 4 0.000
0.000 0.000 -1.000
0.000
M
A 5 0.000
0.000 0.000 0.000
-1.000
----------------------------------------------------------------------------
Zj *+M* -M -M -M -M
Zj-Cj -M -M -M -M
\Cj M M M M
Cb \
Basis Bi A
1 A 2
A 3 A
4
----------------------------------------------------------------------------
M
A 1 100.000
1.000 0.000 0.000
0.000
M
A 2 70.000
0.000 1.000 0.000
0.000
M
A 3 0.000
0.000 0.000 1.000
0.000
M
A 4 0.000
0.000 0.000 0.000
1.000
M
A 5 0.000
0.000 0.000 0.000
0.000
----------------------------------------------------------------------------
Zj *+M* M M M M
Zj-Cj 0.000 0.000
0.000 0.000
\Cj M
Cb \
Basis Bi A
5
----------------------------------------------------------------------------
M
A 1 100.000
0.000
M
A 2 70.000
0.000
M
A 3 0.000
0.000
M
A 4 0.000
0.000
M
A 5 0.000
1.000
----------------------------------------------------------------------------
Zj *+M* M
Zj-Cj 0.000
Simplex Tableau
: 1
\Cj 0.040 0.060
0.020 0.000
Cb \
Basis Bi x
1 x 2
x 3 S
1
----------------------------------------------------------------------------
M
A 1 100.000
10.000 0.000 8.000
-1.000
M
A 2 70.000
7.000 0.000 12.000
0.000
M
A 3 0.000
1.000 0.000 0.000
0.000
0.060
x 2 0.000
0.000 1.000 0.000
0.000
M
A 5 0.000
0.000 0.000 1.000
0.000
----------------------------------------------------------------------------
Zj *+M* M
0.060 M -M
Zj-Cj M 0.000 M -M
\Cj 0.000 0.000
0.000 0.000
Cb \
Basis Bi S
2 S 3
S 4 S
5
----------------------------------------------------------------------------
M
A 1 100.000
0.000 0.000 20.000
0.000
M
A 2 70.000
-1.000 0.000 14.000
0.000
M
A 3 0.000
0.000 -1.000 0.000
0.000
0.060
x 2 0.000
0.000 0.000 -1.000
0.000
M
A 5 0.000
0.000 0.000 0.000
-1.000
----------------------------------------------------------------------------
Zj *+M* -M -M M -M
Zj-Cj -M -M M -M
\Cj M M M M
Cb \
Basis Bi A
1 A 2
A 3 A
4
----------------------------------------------------------------------------
M
A 1 100.000
1.000 0.000 0.000
-20.000
M
A 2 70.000
0.000 1.000 0.000
-14.000
M
A 3
0.000 0.000 0.000
1.000 0.000
0.060
x 2 0.000
0.000 0.000 0.000
1.000
M
A 5 0.000
0.000 0.000 0.000
0.000
----------------------------------------------------------------------------
Zj *+M* M M M -M
Zj-Cj 0.000 0.000
0.000 -M
\Cj M
Cb \
Basis Bi A
5
----------------------------------------------------------------------------
M
A 1 100.000
0.000
M
A 2 70.000
0.000
M
A 3 0.000
0.000
0.060
x 2 0.000
0.000
M
A 5 0.000
1.000
----------------------------------------------------------------------------
Zj *+M* M
Zj-Cj 0.000
Simplex Tableau
: 2
\Cj 0.040 0.060
0.020 0.000
Cb \
Basis Bi x
1 x 2
x 3 S
1
----------------------------------------------------------------------------
0.000
S 4 5.000
0.500 0.000 0.400
-0.050
M
A 2 0.000
0.000 0.000 6.400
0.700
M
A 3 0.000
1.000 0.000 0.000
0.000
0.060
x 2 5.000
0.500 1.000 0.400
-0.050
M
A 5 0.000
0.000 0.000 1.000
0.000
----------------------------------------------------------------------------
Zj 0.300 M
0.060 M M
Zj-Cj M 0.000 M M
\Cj 0.000 0.000
0.000 0.000
Cb \
Basis Bi S
2 S 3
S 4 S
5
----------------------------------------------------------------------------
0.000
S 4 5.000
0.000 0.000 1.000
0.000
M
A 2 0.000
-1.000 0.000 0.000
0.000
M
A 3 0.000
0.000 -1.000 0.000
0.000
0.060
x 2 5.000
0.000 0.000 0.000
0.000
M
A 5 0.000
0.000 0.000 0.000
-1.000
----------------------------------------------------------------------------
Zj 0.300 -M -M
0.000 -M
Zj-Cj -M -M
0.000 -M
\Cj M M M M
Cb \
Basis Bi A
1 A 2
A 3 A
4
----------------------------------------------------------------------------
0.000
S 4 5.000
0.050 0.000 0.000
-1.000
M
A 2 0.000
-0.700 1.000 0.000
0.000
M
A 3 0.000
0.000 0.000 1.000
0.000
0.060
x 2 5.000
0.050 0.000 0.000
0.000
M
A 5 0.000
0.000 0.000 0.000
0.000
----------------------------------------------------------------------------
Zj 0.300 -M M M
0.000
Zj-Cj -M 0.000
0.000 -M
\Cj M
Cb \
Basis Bi A
5
----------------------------------------------------------------------------
0.000
S 4 5.000
0.000
M
A 2 0.000
0.000
M
A 3 0.000
0.000
0.060
x 2 5.000
0.000
M
A 5 0.000
1.000
----------------------------------------------------------------------------
Zj 0.300 M
Zj-Cj 0.000
Simplex Tableau
: 3
\Cj 0.040 0.060
0.020 0.000
Cb \
Basis Bi x
1 x 2
x 3 S
1
----------------------------------------------------------------------------
0.000
S 4 5.000
0.500 0.000 0.000
-0.094
0.020
x 3 0.000
0.000 0.000 1.000
0.109
M
A 3 0.000
1.000 0.000 0.000
0.000
0.060
x 2 5.000
0.500 1.000 0.000
-0.094
M
A 5 0.000
0.000 0.000 0.000
-0.109
----------------------------------------------------------------------------
Zj 0.300 M
0.060 0.020 -M
Zj-Cj M 0.000
0.000 -M
\Cj 0.000 0.000
0.000 0.000
Cb \
Basis Bi S
2 S 3
S 4 S
5
----------------------------------------------------------------------------
0.000
S 4 5.000
0.063 0.000 1.000
0.000
0.020
x 3 0.000
-0.156 0.000 0.000
0.000
M
A 3 0.000
0.000 -1.000 0.000
0.000
0.060
x 2 5.000
0.063 0.000 0.000
0.000
M
A 5 0.000
0.156 0.000 0.000
-1.000
----------------------------------------------------------------------------
Zj 0.300 M -M
0.000 -M
Zj-Cj M -M
0.000 -M
\Cj M M M M
Cb \
Basis Bi A
1 A 2
A 3 A
4
----------------------------------------------------------------------------
0.000
S 4 5.000
0.094 -0.063 0.000
-1.000
0.020
x 3 0.000
-0.109 0.156 0.000
0.000
M
A 3 0.000
0.000 0.000 1.000
0.000
0.060
x 2 5.000
0.094 -0.063 0.000
0.000
M
A 5 0.000
0.109 -0.156 0.000
0.000
----------------------------------------------------------------------------
Zj 0.300 M -M M
0.000
Zj-Cj -M -M
0.000 -M
\Cj M
Cb \
Basis Bi A
5
----------------------------------------------------------------------------
0.000
S 4 5.000
0.000
0.020
x 3 0.000
0.000
M
A 3 0.000
0.000
0.060
x 2 5.000
0.000
M
A 5 0.000
1.000
----------------------------------------------------------------------------
Zj 0.300 M
Zj-Cj 0.000
Simplex Tableau
: 4
\Cj 0.040 0.060
0.020 0.000
Cb \
Basis Bi x
1 x 2
x 3 S
1
----------------------------------------------------------------------------
0.000
S 4 5.000
0.000 0.000 0.000
-0.094
0.020
x 3 0.000
0.000 0.000 1.000
0.109
0.040
x 1 0.000
1.000 0.000
0.000 0.000
0.060
x 2 5.000
0.000 1.000 0.000
-0.094
M
A 5 0.000
0.000 0.000 0.000
-0.109
----------------------------------------------------------------------------
Zj 0.300 0.040
0.060 0.020 -M
Zj-Cj 0.000 0.000
0.000 -M
\Cj 0.000 0.000
0.000 0.000
Cb \
Basis Bi S
2 S 3
S 4 S
5
----------------------------------------------------------------------------
0.000
S 4 5.000
0.063 0.500 1.000
0.000
0.020
x 3 0.000
-0.156 0.000 0.000
0.000
0.040
x 1 0.000
0.000 -1.000 0.000
0.000
0.060
x 2 5.000
0.063 0.500 0.000
0.000
M
A 5 0.000
0.156 0.000 0.000
-1.000
----------------------------------------------------------------------------
Zj 0.300 M
-0.010 0.000 -M
Zj-Cj M -0.010
0.000 -M
\Cj M M M M
Cb \
Basis Bi A
1 A 2
A 3 A
4
----------------------------------------------------------------------------
0.000
S 4 5.000
0.094 -0.063 -0.500
-1.000
0.020
x 3 0.000
-0.109 0.156 0.000
0.000
0.040
x 1 0.000
0.000 0.000 1.000
0.000
0.060
x 2 5.000
0.094 -0.063 -0.500
0.000
M
A 5 0.000
0.109 -0.156 0.000
0.000
----------------------------------------------------------------------------
Zj 0.300 M -M
0.000 0.000
Zj-Cj -M -M -M -M
\Cj M
Cb \
Basis Bi A
5
----------------------------------------------------------------------------
0.000
S 4 5.000
0.000
0.020
x 3 0.000
0.000
0.040
x 1 0.000
0.000
0.060
x 2 5.000
0.000
M
A 5 0.000
1.000
----------------------------------------------------------------------------
Zj
0.300 M
Zj-Cj 0.000
Simplex Tableau
: 5
\Cj 0.040 0.060
0.020 0.000
Cb \
Basis Bi x
1 x 2
x 3 S
1
----------------------------------------------------------------------------
0.000
S 4 5.000
0.000 0.000 0.000
-0.050
0.020
x 3 0.000
0.000 0.000 1.000
0.000
0.040
x 1 0.000
1.000 0.000 0.000
0.000
0.060
x 2 5.000
0.000 1.000 0.000
-0.050
0.000
S 2 0.000
0.000 0.000 0.000
-0.700
----------------------------------------------------------------------------
Zj 0.300 0.040
0.060 0.020 -0.003
Zj-Cj 0.000 0.000
0.000 -0.003
\Cj 0.000 0.000
0.000 0.000
Cb \
Basis Bi
S 2 S
3 S 4
S 5
----------------------------------------------------------------------------
0.000
S 4 5.000
0.000 0.500 1.000
0.400
0.020
x 3 0.000
0.000 0.000 0.000
-1.000
0.040
x 1 0.000
0.000 -1.000 0.000
0.000
0.060
x 2 5.000
0.000 0.500 0.000
0.400
0.000
S 2 0.000 1.000
0.000 0.000 -6.400
----------------------------------------------------------------------------
Zj 0.300 0.000
-0.010 0.000 0.004
Zj-Cj 0.000 -0.010
0.000 0.004
\Cj M M M M
Cb \
Basis Bi A
1 A 2
A 3 A
4
----------------------------------------------------------------------------
0.000
S 4
5.000 0.050 0.000
-0.500 -1.000
0.020
x 3 0.000
0.000 0.000 0.000
0.000
0.040
x 1 0.000
0.000 0.000 1.000
0.000
0.060
x 2 5.000
0.050 0.000
-0.500 0.000
0.000
S 2 0.000
0.700 -1.000 0.000
0.000
----------------------------------------------------------------------------
Zj 0.300 0.000
0.000 0.000 0.000
Zj-Cj -M -M -M -M
\Cj M
Cb \
Basis Bi A
5
----------------------------------------------------------------------------
0.000
S 4 5.000
-0.400
0.020
x 3 0.000
1.000
0.040
x 1 0.000
0.000
0.060
x 2 5.000
-0.400
0.000
S 2 0.000
6.400
----------------------------------------------------------------------------
Zj 0.300 0.000
Zj-Cj -M
Simplex Tableau
: 6
\Cj 0.040 0.060
0.020 0.000
Cb \
Basis Bi x
1 x 2
x 3 S
1
----------------------------------------------------------------------------
0.000
S 5 12.500
0.000 0.000 0.000
-0.125
0.020
x 3 12.500
0.000 0.000 1.000
-0.125
0.040
x 1 0.000
1.000 0.000 0.000
0.000
0.060
x 2 0.000
0.000 1.000 0.000
0.000
0.000
S 2 80.000
0.000 0.000 0.000
-1.500
----------------------------------------------------------------------------
Zj 0.250 0.040
0.060 0.020 -0.003
Zj-Cj 0.000 0.000
0.000 -0.003
\Cj 0.000 0.000
0.000 0.000
Cb \
Basis Bi S
2 S 3
S 4 S
5
----------------------------------------------------------------------------
0.000
S 5 12.500
0.000 1.250 2.500
1.000
0.020
x 3 12.500
0.000 1.250 2.500
0.000
0.040
x 1 0.000
0.000 -1.000 0.000
0.000
0.060
x 2 0.000
0.000 0.000 -1.000
0.000
0.000
S 2 80.000
1.000 8.000 16.000
0.000
----------------------------------------------------------------------------
Zj 0.250 0.000
-0.015 -0.010 0.000
Zj-Cj 0.000 -0.015
-0.010 0.000
\Cj M M M M
Cb \
Basis Bi A
1 A 2
A 3 A
4
----------------------------------------------------------------------------
0.000
S 5 12.500
0.125 0.000 -1.250
-2.500
0.020
x 3 12.500
0.125 0.000 -1.250
-2.500
0.040
x 1 0.000
0.000 0.000 1.000
0.000
0.060
x 2 0.000
0.000 0.000 0.000
1.000
0.000
S 2 80.000
1.500 -1.000 -8.000
-16.000
----------------------------------------------------------------------------
Zj 0.250 0.000
0.000 0.000 0.000
Zj-Cj -M -M -M -M
\Cj M
Cb \
Basis Bi A
5
----------------------------------------------------------------------------
0.000
S 5 12.500
-1.000
0.020
x 3 12.500
0.000
0.040
x 1 0.000
0.000
0.060
x 2 0.000
0.000
0.000
S 2 80.000
0.000
----------------------------------------------------------------------------
Zj 0.250 0.000
Zj-Cj -M
Final Optimal
Solution
Z = 0.250
----------------------------------------
Variable Value Reduced Cost
----------------------------------------
x 1
0.000 0.000
x 2
0.000 0.000
x 3
12.500 0.000
----------------------------------------
Constraint Slack/Surplus Shadow Price
----------------------------------------
C 1
0.000 -0.003
C 2
80.000 0.000
C 3
0.000 -0.015
C 4
0.000 -0.010
C 5
12.500 0.000
----------------------------------------
Objective
Coefficient Ranges
--------------------------------------------------------------------
Lower Current Upper
Allowable Allowable
Variables Limit
Values Limit Increase
Decrease
--------------------------------------------------------------------
x 1
0.025 0.040 No limit
No limit 0.015
x 2
0.050 0.060 No limit
No limit 0.010
x 3
0.000 0.020 0.024 0.004 0.020
Right Hand Side
Ranges
--------------------------------------------------------------------
Lower Current Upper
Allowable Allowable
Constraints Limit
Values Limit Increase
Decrease
--------------------------------------------------------------------
C 1
46.667 100.000 No limit
No limit 53.333
C 2
No limit 70.000 150.000 80.000
No limit
C 3
0.000 0.000 10.000 10.000 0.000
C 4
0.000 0.000 5.000 5.000 0.000
C 5
No limit 0.000 12.500 12.500
No limit
***** End of Output *
Penyelesaian yang lebih sederhana adalah sebagai
berikut :
Program: Linear
Programming
Problem Title :
Pemasaran
***** Input Data
*****
Min. Z =
0.04x1 + 0.06x2 + 0.02x3
Subject to
C1 10x1 + 20x2 + 8x3 >= 100
C2 7x1 + 14x2 + 12x3 >= 70
C3 1x1 >= 0
C4 1x2 >= 0
C5 1x3 >= 0
***** Program
Output *****
Final Optimal
Solution At Simplex Tableau : 6
Z = 0.250
----------------------------------------
Variable Value Reduced Cost
----------------------------------------
x 1
0.000 0.000
x 2
0.000 0.000
x 3
12.500 0.000
----------------------------------------
Constraint Slack/Surplus Shadow Price
----------------------------------------
C 1
0.000 -0.003
C 2
80.000 0.000
C 3
0.000 -0.015
C 4
0.000 -0.010
C 5
12.500 0.000
----------------------------------------
Objective
Coefficient Ranges
--------------------------------------------------------------------
Lower Current Upper
Allowable Allowable
Variables Limit
Values Limit Increase
Decrease
--------------------------------------------------------------------
x 1
0.025 0.040 No limit
No limit 0.015
x 2
0.050 0.060 No limit
No limit 0.010
x 3
0.000 0.020 0.024 0.004 0.020
Right Hand Side
Ranges
--------------------------------------------------------------------
Lower Current Upper
Allowable Allowable
Constraints Limit
Values Limit Increase
Decrease
--------------------------------------------------------------------
C 1
46.667 100.000 No limit
No limit 53.333
C 2
No limit 70.000 150.000 80.000
No limit
C 3
0.000 0.000 10.000 10.000 0.000
C 4
0.000 0.000 5.000 5.000 0.000
C 5
No limit 0.000 12.500 12.500
No limit
Kedua
cara penyelesaian memberikan hasil yang sama walau cara pertama adalah lebih
rumit daripada cara kedua. Penyelesaian masalah pemasaran ini adalah sebagai
berikut : Minimisasi biaya adalah sebesar 0.250 dengan cara tidak memakai iklan
televisi komersial dan iklan radio komersial aikan tetapi memakai iklan surat
kabar yang akan memperoleh penampilan sebanyak 12500.
Masalah Transportasi
Beban
kota Jakarta sudah terlalu berat. Hal ini tercermin dalam kemacetan sebagai
suatu situasi normal dan ketidakmacetan sebagai suatu situasi abnormal. Jakarta
mencerminkan masalah transportasi. Masalah transportasi dirumuskan menurut
karakteristik-karakteristik permasalahan, ditinjau dari sudut manajerial, sebagai berikut : Suatu barang dipindahkan
dari sejumlah sumber ke tempat tujuan dengan biaya sekecil mungkin dan tiap
sumber tersebut dapat memasok suatu jumlah yang tetap dan tiap tempat tujuan
mempunyai permintaan yang tetap atas barang tersebut. Model transportasi,
meskipun dapat diterapkan pada berbagai permasalahan, namun masalah ini biasa
dipakai dalam transportasi barang. Contoh perumusan masalah transportasi dapat
dilakukan sebagai berikut : Cerobong butir gandum terdapat di Kansas City,
Omaha, dan Des Moines sedangkan penggilingan gandum terdapat di Chicago, St.
Louis, dan Cicinnati. Biaya transportasi adalah sebagai berikut :
|
Penggilingan
|
|||
|
Cerobong
Butir Gandum
|
Chicago
(A)
|
St.
Louis (B)
|
Cicinnati
( C)
|
|
Kansas
City
|
$6
|
8
|
10
|
|
Omaha
|
7
|
11
|
11
|
|
Des
Moines
|
4
|
5
|
12
|
|
Cerobong
Butir Gandum
|
Penawaran
|
|
Kansas
City
|
150
|
|
Omaha
|
175
|
|
Des
Moines
|
275
|
|
Jumlah
|
600
|
|
|
|
|
Penggilingan
|
Permintaan
|
|
Chicago
(A)
|
200
|
|
St.
Louis (B)
|
100
|
|
Cincinnati
( C )
|
300
|
|
Jumlah
|
600
|
Masalah
ini dapat dirumuskan ke dalam bentuk pemrograman garis lurus sebagai berikut :
Min Z =
$6 A1 + 8 B1 + 10 C1 + 7 A2 + 11 B2 + 11 C2 + 4 A3 + 5 B3 + 12 C3
Kendala-kendala
adalah sebagai berkut :
A1 + B1 +
C1 = 150
A2 + B2 +
C2 = 175
A3 + B3 +
C3 = 275
A1 + A2 +
A3 = 200
B1 + B2 +
B3 = 100
C1 + C2 +
C3 = 300
Program: Transportation
Problem Title :
Transportasi
***** Input Data
*****
Minimization
Problem :
|
1 2 3|
Supply
--------------------------------------------
1
| 6.0 8.0
10.0| 150.0
2
| 7.0 11.0
11.0| 175.0
3
| 4.0 5.0
12.0| 275.0
--------------------------------------------
Demand| 200.0
100.0 300.0|
***** Program
Output *****
Initial Solution
by Northwest Corner Method
|
1 2 3|
Supply
--------------------------------------------
1
| 150.0 0.0
0.0| 150.0
2
| 50.0 100.0
25.0| 175.0
3
| 0.0 0.0
275.0| 275.0
--------------------------------------------
Demand| 200.0
100.0 300.0| 600.0
Initial
Solution : 5925.0
Optimal Solution
by MODI
|
1 2 3|
Supply
--------------------------------------------
1
| 25.0 0.0
125.0| 150.0
2
| 0.0 0.0
175.0| 175.0
3
| 175.0 100.0
0.0| 275.0
--------------------------------------------
Demand| 200.0
100.0 300.0| 600.0
Optimal
Solution : 4525.0
< Multiple
optimum solutions >
***** End of
Output *****
Biaya
transportasi adalah paling rendah jika penawaran dari Kansas City dikirim ke
Chicago sebesar 25 dan ke Cincinnati sebesar 125, penawaran dari Omaha dikirim ke Cincinnati
sebesar 175, dan penawaran dari Des Moines dikirim ke Chicago sebesar 175 dan ke
St. Louis sebesar 100 Biaya itu adalah sebesar $ 5925.
Cara lain dapat dilakukan sebagai berikut :
Program:
Transportation
Problem Title :
Transportasi
***** Input Data
*****
Minimization
Problem :
|
1 2 3|
Supply
--------------------------------------------
1
| 6.0 8.0
10.0| 150.0
2
| 7.0 11.0
11.0| 175.0
3
| 4.0 5.0
12.0| 275.0
--------------------------------------------
Demand| 200.0
100.0 300.0|
***** Program
Output *****
Initial Solution
by Minimum-Cell-Cost Method
|
1 2 3|
Supply
--------------------------------------------
1
| 0.0 25.0
125.0| 150.0
2
| 0.0 0.0
175.0| 175.0
3
| 200.0 75.0
0.0| 275.0
--------------------------------------------
Demand| 200.0
100.0 300.0| 600.0
Initial
Solution : 4550.0
Optimal Solution
by MODI
|
1 2
3| Supply
--------------------------------------------
1
| 25.0 0.0
125.0| 150.0
2
| 0.0 0.0
175.0| 175.0
3
| 175.0 100.0
0.0| 275.0
--------------------------------------------
Demand| 200.0
100.0 300.0| 600.0
Optimal
Solution : 4525.0
< Multiple
optimum solutions >
***** End of Output *****
Biaya optimal
adalah $ 4525.
Cara lain dapat dilakukan sebagai berikut :
Program:
Transportation
Problem Title :
Transportasi
***** Input Data
*****
Minimization
Problem :
|
1 2 3|
Supply
--------------------------------------------
1
| 6.0 8.0
10.0| 150.0
2
| 7.0 11.0
11.0| 175.0
3
| 4.0 5.0
12.0| 275.0
--------------------------------------------
Demand| 200.0
100.0 300.0|
***** Program
Output *****
Initial Solution
by VAM
|
1 2 3|
Supply
--------------------------------------------
1
| 0.0 0.0
150.0| 150.0
2
| 175.0 0.0
0.0| 175.0
3
| 25.0 100.0
150.0| 275.0
--------------------------------------------
Demand| 200.0
100.0 300.0| 600.0
Initial
Solution : 5125.0
Optimal Solution
by MODI
|
1 2 3|
Supply
--------------------------------------------
1
| 0.0 0.0
150.0| 150.0
2
| 25.0 0.0
150.0| 175.0
3
| 175.0 100.0
0.0| 275.0
--------------------------------------------
Demand| 200.0
100.0 300.0| 600.0
Optimal
Solution : 4525.0
< Multiple
optimum solutions >
***** End of
Output *****
Tiga metode terkandung dalam metode transportasi yaitu
metode Nortwest Corner, model Biaya
Sel Terkecil, dan metode Vogel’s
Approximation.
Contoh lain adalah contoh biaya pengangkutan dari
beberapa kota di Jawa. Contoh ini akan dipakai untuk merumuskan fungsi tujuan
dan kendala-kendala yang dihadapi dalam usaha mencapai tujuan minimisasi biaya
pengangkutan.
|
|
Jakarta
|
Cikampek
|
Bandung
|
Cirebon
|
Purwokerto
|
Yogyakarta
|
Semarang
|
|
Jakarta
|
0
|
200000
|
900000
|
|
|
|
|
|
Cikampek
|
|
0
|
800000
|
600000
|
|
|
|
|
Bandung
|
|
|
0
|
300000
|
800000
|
|
|
|
Cirebon
|
|
|
400000
|
0
|
250000
|
|
600000
|
|
Purwokerto
|
|
|
|
|
0
|
500000
|
|
|
Yogyakarta
|
|
|
|
|
|
0
|
300000
|
|
Semarang
|
|
|
|
|
|
350000
|
0
|
Perumusan
fungsi tujuan adalah sebagai berikut :
Min Z =
200 X12 + 900 X13 + 800 X23 + 600 X24 + 300 X34 +800 X35 + 400 X43 + 250 X45 +
600 X47 + 500 X56 + 300 X67 + 350 X76
Subject
to :
X1 + X2
=12
X1 – X3
–X4 =0
-X2 – X3
+ X5 + X7 – X6 = -5
- X4 – X5
+ X6 + X8 + X9= -1
- X7 – X8
+ X10= 0
- X9 + X12
– X11 = -4
-X10 – X12
+ X11= -2
Pemecahan
masalah minimisasi biaya transportasi adalah sebagai berikut :
Program: Linear Programming
Problem Title : TRANSPORTASI
***** Input Data *****
Min.
Z = 200x1 + 900x2 + 800x3 + 600x4
+ 300x5 + 800x6 + 400x7 + 250x8
+ 600x9 + 500x10 + 300x11 + 350x12
Subject to
C1
1x1 + 1x2 = 12
C2
1x1 - 1x3 - 1x4 = 0
C3
-1x2 - 1x3 + 1x5 - 1x6 + 1x7 = -5
C4
-1x4 - 1x5 + 1x6 + 1x8 + 1x9 = -1
C5
-1x7 - 1x8 + 1x10 = 0
C6
-1x9 - 1x11 + 1x12 = -4
C7
-1x10 + 1x11 - 1x12 = -2
***** Program Output *****
Final Optimal Solution At Simplex Tableau :
6
Z =
14000.000
----------------------------------------
Variable Value Reduced Cost
----------------------------------------
x
1 7.000 0.000
x
2 5.000 0.000
x
3 0.000 100.000
x
4 7.000 0.000
x
5 0.000 400.000
x
6 0.000 700.000
x
7 0.000 250.000
x
8 2.000 0.000
x
9 4.000 0.000
x10 2.000 0.000
x11 0.000 450.000
x12 0.000 200.000
----------------------------------------
Objective Coefficient Ranges
--------------------------------------------------------------------
Lower Current Upper
Allowable Allowable
Variables Limit
Values Limit Increase
Decrease
--------------------------------------------------------------------
x
1 100.000 200.000
450.000 250.000 100.000
x
2 650.000 900.000
1000.000 100.000 250.000
x
3 700.000 800.000
No limit No limit 100.000
x
4 -100.000 600.000
850.000 250.000 700.000
x
5 -100.000 300.000
No limit No limit 400.000
x
6 100.000 800.000
No limit No limit 700.000
x
7 150.000 400.000
No limit No limit 250.000
x
8 -200.000 250.000
450.000 200.000 450.000
x
9 400.000
600.000 1050.000 450.000
200.000
x10 50.000 500.000
700.000 200.000 450.000
x11 -150.000 300.000
No limit No limit 450.000
x12 150.000 350.000
No limit No limit 200.000
Right Hand Side Ranges
--------------------------------------------------------------------
Lower Current Upper
Allowable Allowable
Constraints Limit
Values Limit Increase
Decrease
--------------------------------------------------------------------
C
1 10.000 12.000 12.000 0.000 2.000
C
2 0.000 0.000 2.000 2.000 0.000
C
3 -7.000 -5.000 -5.000 0.000 2.000
C
4 -3.000 -1.000 -1.000 0.000 2.000
C
5 -2.000 0.000 0.000 0.000 2.000
C
6 -6.000 -4.000 -4.000 0.000 2.000
C
7 No limit -2.000 -2.000 0.000
No limit
Biaya minimum adalah sebesar Rp 14000000. Hal ini
berarti bahwa masalah transportasi dapat dipecahkan dengan memanfaatkan model
pemrograman garis lurus (linear
programming).
Masalah Penugasan
Model penugasan adalah model khusus dari model
pemrograman garis lurus dan serupa dengan model transportasi. Perbedaan antara
model penugasan dan model transportasi terletak pada penawaran pada tiap sumber
dan permintaan terhadap tiap tempat tujuan dibatasi sebanyak satu unit barang
saja.
Contoh :
Contoh di bawah ini dipakai untuk menunjukkan model
penugasan. Suatu konferensi mempunyai empat pertandingan bola basket pada suatu
malam tertentu. Kantor pusat bermaksud mengirim empat tim pendamping ke empat
pertandingan tersebut sehingga jumlah jarak yang harus ditempuh itu adalah minimal.
Jarak tiap tim pendamping ke lokasi tiap pertandingan adalah sebagai berikut :
Lokasi Pertandingan
|
Tim
|
E
|
F
|
G
|
H
|
|
A
|
210
|
90
|
180
|
160
|
|
B
|
100
|
70
|
130
|
200
|
|
C
|
175
|
105
|
140
|
170
|
|
D
|
80
|
65
|
105
|
120
|
Tim itu adalah tim A, B, C, dan D sedangkan lokasi
pertandingan adalah E, F, G, dan H.
Program:
Assignment
Problem Title :
Penugasan Tim
Minimization
Problem :
|
1 2 3
4
----------------------------------
1 |
210.0 90.0 180.0
160.0
2 |
100.0 70.0 130.0
200.0
3 |
175.0 105.0 140.0
170.0
4 |
80.0 65.0 105.0
120.0
----------------------------------
Possible Final
Opportunity Cost Table
|
1 2 3
4
----------------------------------
1 |
90.0 0.0 50.0
0.0
2 |
0.0 0.0 20.0
60.0
3 |
45.0 5.0 0.0
0.0
4 |
0.0 15.0 15.0
0.0
----------------------------------
Optimum Solution
: 450.0
|
1 2 3 4
------------------
1 |
0 1 0 0
2 |
1 0 0 0
3 |
0 0 1 0
4 |
0 0 0 1
------------------
Tim A ditugaskan ke lokasi F dengan jarak 90
Tim B ditugaskan ke lokasi E dengan jarak 100
Tim C ditugaskan ke lokasi G dengan jarak 140
Tim D ditugaskan ke lokasi H dengan jarak 120
Jumlah jarak adalah 450
Pemecahan alternatif adalah sebagai berikut :
Tim A ditugaskan ke lokasi H dengan jarak 160
Tim B ditugaskan ke lokasi F dengan jarak 70
Tim C ditugaskan ke lokasi G dengan jarak 140
Tim D ditugaskan ke lokasi E dengan jarak 80
Jumlah jarak adalah 450
Contoh lain :
Seorang Kepala Program Studi pada suatu Fakultas
mempunyai lima pengajar yang harus ditugaskan ke empat matakuliah yang berbeda.
Semua pengajar telah berpengalaman mengajar dan telah dievaluasi oleh para
mahasiswa. Peringkat untuk masing-masing pengajar untuk masing-masing matakuliah disajikan di
bawah ini. Kepala Program Studi ingin mengetahui penugasan secara optimal atas
para pengajar pada matakuliah yang akan memaksimumkan evaluasi rata-rata secara
keseluruhan. Pengajar yang tidak diberi tugas
untuk mengajar salah satu matakuliah akan ditugaskan untuk memeriksa
hasil ujian. Masalah ini dapat diselesaikan jika metode penugasan dipakai.
|
Matakuliah
|
||||
|
Dari
|
A
|
B
|
C
|
D
|
|
1
|
80
|
75
|
90
|
85
|
|
2
|
95
|
90
|
90
|
97
|
|
3
|
85
|
95
|
88
|
91
|
|
4
|
93
|
91
|
80
|
84
|
|
5
|
91
|
92
|
93
|
88
|
Pemecahan masalah penugasan ini adalah sebagai berikut
:
Program:
Assignment
Problem Title :
Penugasan Pengajar
Maximization
Problem :
|
1 2 3
4
----------------------------------
1 |
80.0 75.0 90.0
85.0
2 |
95.0 90.0 90.0
97.0
3 |
85.0 95.0 88.0
91.0
4 |
93.0 91.0 80.0
84.0
5 |
91.0 92.0 93.0
88.0
----------------------------------
***** Program
Output *****
Possible Final Opportunity
Loss Table
|
1 2 3
4 5
-----------------------------------------
1 |
13.0 20.0 3.0
10.0 0.0
2 |
0.0 7.0 5.0
0.0 2.0
3 |
8.0 0.0 5.0
4.0 0.0
4 |
0.0 4.0 13.0
11.0 0.0
5 |
2.0 3.0 0.0
7.0 0.0
-----------------------------------------
Optimum Solution
: 378.0
|
1 2 3
4 5
---------------------
1 |
0 0 0
0 1
2 |
0 0 0
1 0
3 |
0 1 0
0 0
4 |
1 0 0
0 0
5 |
0 0 1
0 0
---------------------
Hasil di atas mencerminkan bahwa pemecahan optimum
adalah 378 jika pengajar 1 diberi tugas matakuliah. Solusi optimal ini berarti
bahwa :
Pengajar 1 diberi tugas matakuliah A, B, C, dan D. Pengajar
1 tidak diberi tugas memeriksa hasil ujian. Pengajar 2 diberi tugas mengajar
matakuliah A, C, D, dan tugas memeriksa hasil ujian. Pengajar 3 diberi tugas
mengajar matakuliah B, C. D, dan memeriksa hasil ujian. Pengajr 4 diberi tugas
mengajar matakuliah A, B, D, dan memeriksa hasil ujian.
Rangkuman
Perkuliahan
dalam tahun 1957, ditinjau dari sudut perkembangan teknologi informasi dan
teknologi komunikasi yang sangat pesat di Indonesia sejak tahu 1978, adalah
tidak efisien karena perhitungan dilakukan masih secara manual dan membutuhkan
waktu beberapa jam. Hasil perhitungan juga sebagian besar mengandung kesalahan.
Pemecahan masalah tersebut sekarang dapat dilakukan hanya dalam beberapa menit
saja jika perangkat lunak dan perangkat keras komputer dipakai.
Pemrograman
garis lurus dapat dipakai untuk memecahkan masalah-masalah kuantitatif dalam
bidang keuangan, pemasaran, sumberdaya manusia, produksi dan sebagainya.
Pemecahan masalah-masalah ini akan lebih mudah jika fungsi tujuan dan
kendala-kendala atau batasan-batasan dapat dirumuskan secara tepat. Tiga contoh
disajikan yaitu contoh tentang produksi, keuangan, dan contoh tentang
pemasaran.
Model
transportasi dan model penugasan sejalan dengan model pemrograman garis lurus.
Tujuan yang ingin dicapai dapat berbentuk maksimisasi hasil (laba) atau
minimisasi biaya dengan mempertimbangkan kendala-kendala atau batasan-batasan
yang tersedia.
Daftar Kepustakaan
Siswanto.
1990. Sistem Komputer Manajemen :
Management Science. Jakarta : Penerbit PT Elex Media Komputindo.
Taylor
III, Bernard W. 1996. Sains Manajemen
(Pendekatan Matematika Untuk Bisnis). Jakarta : Salemba Empat
