Centro Studi Tinggi Universitas OEI

Kursus Ibero-Amerika untuk pendidikan jangka panjang

dari profesor matematika

Tema 24: Pemrograman linier

1
 Pusat Studi Tinggi Universitas OEI

Pemrograman linier

Isi dari dokumen ini:

Pengantar
Konsep Pemrograman Linier
Penyelesaian masalah bidimensional
Penyelesaian masalah langkah demi langkah
Metode grafis
Jenis solusi
Masalah transportasi.
Lebih banyak contoh
Catatan: Metode simplex
Daftar Pustaka

[Link]ón

Pemrograman linier adalah teknik matematika yang relatif

baru-baru ini. Pada tahun 1939 matematikawan Rusia Leonid Kantarovich (penghargaan
Nobel di ekonomi 1975) menerbitkan Metode matematis dari
organisasi dan perencanaan produksi yang karena alasan
ideologis tidak dipublikasikan sampai dua dekade kemudian. Dalam buku ini
se definisikan secara tepat dan rigor suatu teori matematika yang dapat diterapkan
sejumlah besar masalah optimisasi. Sebelumnya, besar
matematik seperti Newton, Leibnitz, dan Lagrange tertarik pada
obtención de máximos y mínimos pero fue el francésJoseph Fourier
(1768-1830) yang pertama kali merasakan, meskipun tidak dengan berlebihan
ketelitian, metode yang saat ini kita kenal sebagai pemrograman
linier.
Pada tahun 1949, George B. Dantzig menerbitkan "Metode simplex" untuk menyelesaikan
program linear, memperkenalkan secara eksplisit fungsi tujuan dan
mengurangi secara drastis jumlah kemungkinan solusi optimal.
Sejak tanggal itu, sejumlah besar ilmuwan telah berkontribusi
dalam bidang pemrograman linier dalam banyak cara, termasuk
pengembangan teoretis, aspek komputasi dan eksplorasi
nuevas aplicaciones. El método del simplex de programación lineal
memiliki banyak penerimaan karena kemampuannya untuk memodelkan
masalah keputusan penting di bidang administrasi
selain kemampuan mereka untuk menghasilkan solusi dalam waktu
wajar. Dalam hal ini, komputer telah berkontribusi secara
penentu untuk memperbaiki dan mempercepat metode tersebut.

Di dalam berbagai aplikasi pemrograman linier

kita dapat menemukan masalah diet di mana dicari

2
 Pusat Studi Tinggi Universitas OEI

kombinasi makanan terbaik untuk diet dengan biaya minimum

masalah produksi yang mencari untuk memaksimalkan keuntungan atau
minimalkan pengeluaran berdasarkan sumber daya yang tersedia dan
masalah transportasi yang meminimalkan biaya distribusi
dan waktu yang digunakan dalam distribusi barang.

Pemrograman linier setelah perang (Perang Dunia II): Pada tahun 1948
Kota Jerman Berlin terletak terpisah antara bagian Soviet dan
dari negara-negara sekutu (Inggris dan Amerika Serikat terutama), adalah
jadi ketika orang Rusia memutuskan untuk memblokir komunikasi darat dan
mengosongkan pasokan bagi sekutu. Orang Amerika memutuskan untuk meluncurkan sebuah
jembatan udara, berbasis pada teknik pemrograman linier, untuk memenuhi
kota. Pada bulan Desember 1948, mulai mengangkut 4.500 ton
diarias de abastos llegando a 8000 toneladas en marzo de 1949, y así
mencapai jumlah yang diangkut melalui kereta api dan jalan raya sebelum
blokade. Pada 12 Mei 1949, Soviet menyerah dan mengangkat blokade.

2. Konsep Pemrograman Linier

Masalah optimisasi, secara umum, berkaitan dengan
penugasan sumber daya dengan cara yang paling tepat. Itu berarti
penentuan nilai optimal dari sekumpulan variabel yang
harus memverifikasi batasan tertentu tentang nilai yang dapat
minum.

Definisi Masalah Pemrograman linier adalah suatu masalah

optimisasi untuk yang berikut diverifikasi:

a) Ini tentang memaksimalkan atau meminimalkan sebuah fungsi

linear dari variabel keputusan, yang disebut
fungsi tujuan.
b) Nilai-nilai variabel harus memenuhi sebuah
kumpulan pembatasan, masing-masing dari mana
dapat dituliskan sebagai sebuah persamaan atau pertidaksamaan
linier.

Jika kita menggunakan bahasa matematika untuk mendefinisikan masalah

kita bisa mengatakan bahwa tujuan utama dari Pemrograman linier adalah
penyelesaian masalah jenis:

maks{f(x) / x S}ómin{f(x) / x S} , dimanaS n

yf:S

3
 Pusat Studi Tinggi Universitas OEI

Setiap elemen dari S disebut solusi yang dapat diterima; S disebut

wilayah yang dapat dicapai disebut fungsi objektif.

Dalam masalah optimisasi ini, dicari sebuah

solusi yang layak x0di mana f mencapai nilai maksimum (atau minimum) nya. Di
dalam pencarian tersebut kita dapat menemukan hal-hal berikut
situaciones:

Problema tidak layak: ketika tidak ada solusi yang layak.

artinya, S= (kumpulan kosong).
Masalah yang dapat diatasi:

a) Problema tidak terikat: ketika ada solusi yang membuat

menaikkan infinitely kepada fungsi tujuan, yaitu ketika
para cualquier valor real M siempre existe un x S tal que
f(x)>M, y dalam hal ini kita akan menulis max{f(x) / x S}=+ .

Dengan cara yang sama, ketika terdapat solusi yang menyebabkan penurunan
tak terhingga pada fungsi tujuan, yaitu ketika untuk setiap
nilai nyata M' selalu ada x S sehingga f(x)<M', dan dalam hal ini
kami akan menulis min{f(x) / x S}=- .

b) Masalah terbatas dengan solusi yang layak: ketika ada sebuah

xo S tal que f(xo) f(x) untuk semua x S. Dalam hal ini,
f(xo=max{f(x) / x S} y xo menerima nama solusi
faktis tidak harus unik.

Secara analogi kita bisa membangun definisi untuk masalah tersebut.

dari yang minimum.

Secara umum dalam masalah Pemrograman Linier mana pun

kami memiliki:

Fungsi tujuan, yang bersifat linier, yaitu:

F(X)=c1x1+c2x2+…+ cnxn

Kondisi atau pembatasan masalah yang juga

son lineales, es decir:

h1a11x1+ a12x2+…+ a1nxn b1

h2a21x1+ a22x2+…+ a2nxn b2
.....….. ……….……………………..
hmam1x1+ am2x2+…+ amnxn bm

Catatan: Ketidaksetaraan dapat menjadi

4
 Centro Studi Universitari Tinggi OEI

Mungkin ada kondisi di mana variabel instrumental

dapat mengambil nilai yang lebih besar atau sama dengan nol, yaitu:

xsaya 0, apapun nilai i.

Mudah untuk membayangkan jumlah kemungkinan yang dihadirkan dalam

pernyataan ini. Jadi penggunaan komputer sangat penting karena
memungkinkan kita mengurangi waktu penyelesaian. Dalam contoh yang
kami menunjukkan di bawah ini bahwa kami akan bekerja, untuk menyederhanakan proses,
dengan n=6 dan kami akan mencoba menemukan model optimisasi untuk
masalah kehidupan nyata ini tanpa sampai pada solusi.

Pabrik boneka Teide S.A. memproduksi 6 jenis boneka dari

dari 6 bahan mentah, masing-masing dengan kombinasi yang berbeda dari itu
bahan baku. Tabel berikut menunjukkan keuntungan per unit dari
produk yang diproduksi. Bagaimana seharusnya proses produksi dilakukan untuk
memaksimalkan total keuntungan hanya menggunakan inventaris bahan yang ada
prima?
Tabel. Manfaat per boneka yang diproduksi.
Produksi danzarin pengguyur media bom profesor Inventa
ibu
untuk a a co ro ra rio
Baja 1 4 - 4 2 - 800
Kayu 4 5 3 - 1 - 1160
Plastik - 3 8 - 1 - 1780
Goma 2 - 1 2 1 5 1050
Kaca 2 4 2 2 2 4 1360
Lukisan 1 4 1 4 3 4 1240
Manfaat
30 45 24 26 24 30
cio

MODELO MATEMATIS

Dalam model ini semua konfigurasi yang mungkin telah diajukan, yang
setara dengan setiap boneka, oleh karena itu kami mempertimbangkan yang berikut ini
variables:
x1 unitas penari
x2 unit ski
x3 unitas mama
x4 unit medis,
x5 unit pemadam kebakaran
x6 unitas dosen.

Oleh karena itu, fungsi tujuan yang menunjukkan keuntungan yang kita inginkan
memaksimalkan akan menjadi:

5
 Pusat Studi Tinggi Universitas OEI

F(X)=30x1+45x2+24x3+26x4+24x5+30x6

Tunduk pada batasan berikut berdasarkan inventaris yang ada.

x1+ 4x2+ + 4x4+ 2x5 800

4x1+ 5x2+ 3x3 + x5 1160
3x2+ 8x3 + x5 1780
2x1 + x3+ 2x4+ x5+ 5x6 1050
2x1+ 4x2+ 2x3+ 2x4+ 2x5+ 4x6 1360
x1+ 4x2+ x3+ 4x4+ 3x5+ 4x6 1240

dan jelas x1, x2, x3, x4, x5, x6 0

Sistem linear dari kendala ini akan menentukan wilayah yang layak di dalam
apa yang harus dicari adalah maksimum dari fungsi tujuan (solusi yang layak).
Selain itu, perlu diterapkan agar variabel mengambil nilai bulat.
mengatakan

x1, x2, x3, x4, x5, x6

Pada akhirnya, apa yang telah kita lakukan adalah memodelkan masalah kehidupan ini
hal ini adalah menerjemahkan ke dalam bahasa matematis seperti yang ditunjukkan pada berikut
skemaGambar 1) Masih akan tergantung penyelesaiannya di “dunia
matematikus" (2) dan menerapkan solusi ini ke kehidupan nyata (3) :

(3)

(2)

(1)

Gambar 1: Proses penyelesaian suatu masalah

6
 Centro Pendidikan Tinggi Universitas OEI

[Link] masalah bidimensional

Definición Mengingat kompleksitas masalah ini

kita akan melihat pendekatan dan penyelesaiannya secara lengkap,
termasuk resolusi grafik, untuk dua variabel x dan y.
Jadi, masalah akan didefinisikan sebagai:

z=ax+by(tujuan fungsi)

dikenakan pada sistem pertidaksamaan linear (yang

muncul dari pembatasan yang dikenakan pada
variabel)

a1x + b2y c1
a2x + b2y c2
………. …
anx + bny cn
Catatan: Ketidaksetaraan bisa jadi

Seperti yang telah dilihat dalam tema yang didedikasikan untuk inekuasi, setiap
ketidaksetaraan jenis ini mendefinisikan sebuah setengah bidang yang dibentuk oleh semua
titik-titik pada plano yang memuaskannya. Jika misalnya kita ingin
menemukan setengah bidang 2x+3y<3 adalah: (Gambar 2).

Gambar 2: Inekuasi sebagai semiplan

Actividad 1.¿Cuáles de los siguientes puntos cumplen la inecuación

-2x+3y<5 : (2,0);(0,0);(0,2);(-2,2) y (2,3)?

Bantuan: Jika Anda merepresentasikan garis -2x+3y=5, Anda akan melihat bahwa zona
di mana dua titik yang memenuhi ketidaksamaan adalah
semiplano inferior.

7
 Pusat Studi Tinggi Universitas OEI

Aktivitas 2. Periksa bahwa daerah pada bidang yang didefinisikan oleh

inekuasi linear yang ditunjukkan adalah yang ditunjukkan dalam gambar
terlampir.

3
V

V V

Titik-titik pada bidang yang memenuhi sekumpulan ketidaksetaraan, jika

mereka ada di dalam suatu bidang cembung. Ini cembung karena
selalu berada di sisi yang sama dari garis yang mengandung masing-masing
dari sisinya (Gambar 3)

Gambar 3: Ruang cekung yang didefinisikan oleh suatu sistem

inekuasi

Wilayah ini di bidang adalah wilayah yang layak dan setiap orang
Definisi
dari titik-titik yang membentuknya adalah solusi
layak. Dari solusi-solusi ini, yang akan memberikan maksimum atau
solusi minimum untuk fungsi tujuan disebut solusi
optimal.

Dalam situasi ini, kita bisa menemukan daerah yang layak kosong,
dibatasi dan tidak dibatasi. Berikut ini adalah contoh dari
berbagai kemungkinan: (Gamb.4)

8
 Pusat Studi Tinggi Universitas OEI

Wilayah layak terbatas Wilayah layak tidak terbatas Wilayah layak kosong

Fig. 4: Wilayah yang mungkin

Baiklah, teorema berikut ini memungkinkan kita untuk mendekati lebih jauh ke
solusi masalah dalam kasus bidimensional:

TeoremaDadaF(x)=ax+by+cy suatu daerahRkonveks terikat

selamat ulang tahun
Ftiene unvalor máximoyun valor mínimoenRque se
mencapai di sudut-sudut.

[Link] suatu masalah langkah demi langkah

Ini adalah tentang mengungkapkan suatu prosedur pemecahan yang menjawab

sebuah model masalah pemrograman linier.

Contoh 1. Sebuah perusahaan komputer menerima pesanan untuk

memperbaiki komputer dan konsol permainan video. Perusahaan
memiliki 2 bengkel. Yang pertama dapat menggunakan 300 jam dari
pekerjaan, dan perlu menghabiskan 6 jam untuk setiap komputer dan 5 untuk
setiap konsol. Yang kedua memiliki 200 jam dan membutuhkan 2 jam
untuk setiap komputer dan 5 untuk setiap konsol. Laba bersih
yang diperoleh perusahaan adalah 100 € per komputer dan 100 € per
konsol. Berapa banyak yang harus diperbaiki dari setiap artikel untuk
memaksimalkan keuntungan perusahaan?

Langkah 1: Bacalah dengan seksama masalah untuk menentukan tujuan,

definisikan variabel dan urutkan data dari pernyataan.

x jumlah komputer yang dapat diperbaiki setiap bengkel.

9
 Pusat Studi Tinggi Universitas OEI

y jumlah konsol yang dapat diperbaiki setiap bengkel.

Mari kita atur data dalam tabel berikut:

Komputer Consolas Nº horas

Taller 1 6 5 300
Taller 2 2 5 200
Manfaat 100 100
Produksi x y

Langkah 2: Menulis fungsi tujuan dan ketidaksamaan yang

tentukan pembatasannya.

Fungsi keuntungan yang ingin kita maksimalkan adalah: Z=100x+100y

Pembatasan yang dihasilkan dari pembacaan masalah adalah:

6x + 5y 300 (berkaitan dengan kemungkinan dari Workshop 1)

2x + 5y 200(mengenai kemungkinan dari Workshop 2)

x 0

y 0

Langkah 3: Mewakili sistem pertidaksamaan, yang diberikan oleh

pembatasan, untuk menemukan daerah yang layak. (Gambar 5)

Wilayah
layak

Gambar 5: Wilayah layak dari masalah

Langkah 4: Hitung titik-titik sudut dari daerah yang layak.

10
 Pusat Studi Tinggi Universitas OEI

Untuk itu kita harus menemukan interseksi setiap pasangan garis

terlibat dalam menyelesaikan sistem persamaan yang mendefinisikan:

x 0
O (0,0)
y 0

6x 5y 300 300

6x 0 300 x 50 U (50,0)
y 0 6

6x 5 tahun 300 100

(mengurangi) 4x 0 100 x 25
2x 5y 200 4
menggantikan 30 V (25,30)

2x 5 tahun 200 200

0 5 tahun 200 x 20 W (0,40)
x 0 5

Dengan cara ini kita memperoleh titik-titik berikut O(0,0), U(50,0),

V(25,30), W(0,40) direpresentasikan dalam grafik berikut:Gambar 6)

Gambar 6: Titik-titik sudut dari wilayah yang layak dalam masalah

Langkah 5: Mengganti koordinat titik sudut ke dalam fungsi

tujuan untuk melihat di mana ia mendapatkan manfaat maksimal.

Z=100x+100y(keuntungan)

Z(O)= 100·0+100·0=0+0=0 €
Z(U)= 100·50+100·0=5000+0=5000 € Maksimum adalah
Z(V)= 100·25+100·30=2500+3000=5500 € diperoleh di titik puncak
Z(W)= 100·0+100·40=0+4000=4000 € V(25,30)

11
 Pusat Studi Tinggi Universitas OEI

Langkah 6: Mengkritik solusi, melihat bahwa itu logis dan menjawab kepada
pertanyaan awal memindahkan masalah ke kenyataan.
x=25 25 komputer
V(25,30)
y=30 30 konsol

Solusi akhir: Perusahaan harus memperbaiki

25 komputer dan 30 konsol untuk
mendapatkan keuntungan maksimum sebesar 5500 €

5. Metode grafis
Cara lain untuk menyelesaikan jenis masalah ini adalah melalui
representasi grafis. Seperti pada metode aljabar yang telah dilihat,
mulailah dengan menemukan ekspresi dari fungsi tujuan dan sistem
dari inekuasi (pembatasan).
Mulai saat ini langkah-langkah berikut akan diikuti:

Langkah 1: Sistem ini digambarkan secara grafis memberikan hasil

wilayah yang layak di mana kita akan mencari solusi.

Langkah 2: Garis kontur yang dihasilkan diwakili.

berasal dari fungsi tujuan. Garis-garis ini adalah garis-garis yang muncul
ketika kita menyamakan fungsi tujuan dengan nilai konstan k. Su
ekspresi akan menjadi:

k=ax+by , k

Dalam praktiknya biasanya digambar garis level nol (ax+by=0) dari

bentuk yang saat kita mengubah nilainya kita peroleh
garis paralel ini yang menyapu wilayah yang dapat diterima. Mari kita lihat
secara grafis menggunakan data dari masalah sebelumnya: (Gambar 7)

12
 Pusat Studi Tinggi Universitas OEI

Garis tingkat
100x + 100y = k

Gambar 7: Garis kontur

Langkah 3: Terakhir, dari semua garis level, dicari yang

bercorrespond dengan nilai optimal, maksimum dalam hal ini, dari fungsi
tujuan. Untuk itu, garis level dipindahkan sampai menemukan yang
titik terakhir sebelum berhenti menyentuh wilayah yang layak. Di kami
kasus maksimum terjadi di titik V(25,30) dengan nilai k=
5500. (Gbr.8)

Fungsi tujuan
100x+100y=5500
Maksimum di V(25,30)

Gambar 8: Solusi grafis

{"[Link] de soluciones":"[Link] solusi"}

Dapat dilakukan klasifikasi masalah pemrograman

linier yang memperhatikan jenis solusi yang dihadirkan. Ditampilkan kepada
lanjutan secara skematis:

13
 Centro Studi Universitari Tinggi OEI

Dengan solusi unik

Dengan solusi ganda
Dapat dilakukan
Tidak terbatas
Solusi
Tidak Dapat Dilakukan

Definición
Kami mengatakan bahwa masalah tersebut memiliki solusi yang layak.
ketika ada sekumpulan nilai yang memenuhi
restriksi, yaitu, bahwa sistem ketidaksamaan
mempunyai solusi dan oleh karena itu ada kumpulan dari
solusi yang mungkin (wilayah yang layak). Dalam hal ini
dapat menjadi:
a) Dengan solusi unik: Ada satu-satunya solusi
optimal, yang dicapai di suatu titik [Link] 9)
Fungsi
tujuan Solusi
unik

Gambar 9: Solusi unik

b) Kon solusi ganda: Ada tak terhingga

solusi optimal. Situasi ini terjadi
ketika dua simpul adalah solusi optimal dan
jadi setiap titik di atas segmen yang
los une juga merupakan solusi. Secara grafis ini
terjadi ketika fungsi tujuan paralel dengan
salah satu sisi dari wilayah yang [Link].10)

Gambar 10: Solusi ganda

14
 Centro de Altos Estudios Universitarios de la OEI

7. Masalah transportasi
Contoh 2. Dua kota, Gara dan Jonay, memproduksi dalam seminggu 26 dan
30 ton kertas untuk didaur ulang, masing-masing. Untuk melakukan
Pengolahan limbah jenis ini ada di daerah tiga pabrik
daur ulang1, F2y F3yang dapat menampung 20, 22, dan 14 ton,
secara berturut-turut. Jika biaya transportasi per ton dari
kota ke pabrik adalah, dalam ratusan euro, yang ditunjukkan di
tabel terlampir. Bagaimana kita bisa mengatur transportasi agar
biaya laut minimum?
Biaya transportasi
Pabrik daur ulang
Kota-kota F1 F2 F3
Gara 1 3 1
Jonay 2 1 1

Solusi: Kami mendefinisikan x sebagai jumlah kertas yang dimiliki kota Gara
harus mengirim ke pabrik pertama (F1), e y a la cantidad de papel
que Gara mengantarkan ke pabrik kedua (F2). Dengan cara ini,
jumlah yang harus diserahkan Gara kepada pabrik ketiga adalah 26-x-y.
mengamati tonalitas yang dapat ditanggung setiap pabrik, diperoleh
tabel berikut yang mencakup semua data masalah berdasarkan
x e y. Misalnya, jika pabrik 1 (F1) dapat diasumsikan maksimal 20
toneladas yxtoneladas berasal dari kota Gara jadi dari
kota Jonay dapat mengambil 20-x. Juga, jika kota Gara memproduksi
26 ton yxvan ke pabrik 1 (F1eyvan ke pabrik 2 (F2)
jadi ke pabrik 3(F3) sisa akan diangkut, yaitu, 26-x-y.

Data masalah berdasarkan variabel x dan y

Pabrik daur ulang
Kota F1 F2 F3
Gara x y 26-x-y
Jonay 20-x 22-y -12+x+y

Perhatikan bahwa 14-(26-x-y)= -12+x+y

Selain itu, jumlah kertas yang diserahkan kepada pabrik tidak
mereka bisa negatif jadi harus memenuhi yang berikut
ketidaksetaraan:
x 0, y 0, 20-x 0, 22-t 0, 26-x-y 0, -12+x+y 0
Bahwa setelah disederhanakan akan tercermin dalam berikut ini
sistem inekwasi (pembatasan masalah):
x 0
y 0

15
 Pusat Studi Tinggi Universitas OEI

x 20
y 22
x+y 26
x+y 12
Tujuan dari masalah kami adalah mengorganisir transportasi agar
biaya seminimal mungkin, jadi kita harus mendefinisikan fungsi objektif
mengamati tabel biaya. Jadi, akan terlihat seperti ini
berikutnya:
Z=1·x+3·y+1·(26-x-y)+2·(20-x)+1·(22-y)+1·(-12+x+y)
Operando diperoleh bahwa Z = -x + 2y + 76

Mari kita gambarkan, sekarang, wilayah yang layak dan kita cari
koordinat dari sudut-sudutnya (kandidat untuk menjadi optimal): (Fig.12)

Gambar 12: Wilayah layak dari masalah

Dengan perhitungan sederhana, dapat dilihat bahwa T=(0,22), U=(0,12),

P=(12,0) dan Q=(20,0). Mari kita hitung sekarang R dan S:

x y 26
20  y 26 y 26 20 6 R (20,6)
x 20

x y 26
x 22 26 x 26 22 4 S (4,22)
y 22

Mari kita substitusikan koefisien dari titik sudut ke dalam fungsi tujuan
Z= -x+2y+76

Z(T)= -0+2·22+76=0+44+76=120
16
 Pusat Studi Tinggi Universitas OEI

Z(S)= -4+2·22+76=-4+44+76=116
Z(R)= -20+2·6+76=-20+12+76=68
Minimum diperoleh
Z(Q)= -20+2·0+76=-20+0+76=56
di titik Q(20,0)
Z(P)= -12+2·0+76=-12+0+76=64
Z(U)= -0+2·12+76=0+24+76=100

Jadi solusinya adalah x=20 dan y=0 yang dibawa ke kita

masalah berarti bahwa ton kertas yang harus diangkut dari
setiap kota (Gara dan Jonay) ke masing-masing pabrik (F 1, F2, F3)
agar biayanya minimal harus sesuai dengan yang tertera di tabel ini:

Tonelada kertas yang harus pergi ke setiap pabrik

Pabrik daur ulang
Kota-kota F1 F2 F3
Gara 20 0 6
Jonay 0 22 8

Secara grafis menggunakan garis kontur akan terlihat seperti ini: (Gambar 13)

Gambar 13: Solusi grafik dari masalah

8. Lebih banyak contoh untuk memperkuat tema.

Contoh 3. Sebuah perusahaan menyediakan kepada seorang investor saham 10
juta ($) untuk diinvestasikan dalam dua jenis produk
finansial, A dan B. Tipe A memiliki lebih banyak risiko tetapi menghasilkan sebuah
manfaat 10 %. Tipe B lebih aman, tetapi menghasilkan
hanya 7% per tahun. Setelah melakukan studi pasar, ia memutuskan untuk berinvestasi

17
 Pusat Studi Tinggi Universitas OEI

maksimal 6 juta ($) dalam pembelian saham produk A

y, setidaknya, 2 juta ($) dalam pembelian saham produk tersebut
B. Selain itu, putuskan bahwa yang diinvestasikan dalam A harus, setidaknya, sama dengan yang
terbalik di B. Apa yang harus dilakukan investor ini, dalam hal ini
kondisi, untuk memberikan perusahaan manfaat maksimum?

Langkah 1: Kami mendefinisikan variabel dan mengurutkan data dari

pernyataan.
x jumlah yang diinvestasikan dalam produk keuangan A. (juta $)
y jumlah yang diinvestasikan dalam produk keuangan B. (juta $)

Mari kita atur data sekarang dalam tabel berikut:

Produk A Produk B

Investasi x y
Manfaat 0,1·x 0,07·y

x 6 juta y 2 millones
x y

Langkah 2: Fungsi manfaat yang ingin kita maksimalkan adalah:

Dan pembatasan yang harus dipatuhi adalah:

x+y 10 (sembilan juta $)

x 6 (x adalah maksimum 6 juta $)
y 2 (dan minimal 2 juta $)
x y (x adalah setidaknya y)
x 0
y 0

Langkah 3: Mewakili sistem ketidaksamaan, yang diberikan oleh

pembatasan, untuk mencari wilayah yang layak. (Gambar 14)

18
 Centro Studi Universitari Tinggi OEI

V
Wilayah
dapat dilaksanakan
O
U

Fig. 14: Wilayah layak dari masalah

Langkah 4: Kami menghitung titik-titik pada daerah yang layak dengan menemukan
interseksi dari setiap pasangan garis yang terlibat:

y x
O (2,2)
y 2

y 2
Anda (6,2)
x 6

x y 10
y 10 6 4 V (6,4)
x 6

x y 10
y y 10 2y 10 y 5 W (5,5)
y x

Dengan cara ini kita mendapatkan titik-titik sebagai berikut O(2,2), U(6,2),
V(6,4), W(5,5).

Langkah 5: Kami menggantikan koordinat titik sudut ke dalam fungsi

tujuan untuk melihat di mana mendapatkan keuntungan maksimum.

34
Z  O 0,1 2 0,07 2 0,34 juta($)
100

19
 Pusat Studi Tinggi Universitas OEI

74
Z  U 0,1 6 0,07 2 0,74juta($)
100
Z  V 0,1 6 0,07 4 0,88 juta ($)
Maksimum diperoleh di
Z  W 0,1 5 0,07 5 0,85 juta ($) titik sudut V(6,4)

Langkah 6: Kita memindahkan masalah ke kenyataan.

x=6 menginvestasikan 6 juta ($) dalam produk keuangan A
V(6,4)
y=4 menginvestasikan 4 juta ($) dalam produk keuangan B

Solusi akhir: Harus diinvestasikan 6 juta ($) dalam

produk keuangan A dan 4 juta ($) dalam produk
finansial B untuk mendapatkan manfaat maksimum sebesar 0,88
juta ($).

Ejemplo [Link] compañía de seguros trabaja para empresas y para

khusus. Untuk menjadi menguntungkan di tahun ini, harus mencapainya
sebagai klien setidaknya 20 perusahaan dan sejumlah klien
khusus yang, setidaknya harus dua kali lipat dari jumlah
perusahaan. Selain itu, karena masalah logistik memiliki batasan global
dari 90 klien tahunan. Jika setiap perusahaan menghasilkan $280 pendapatan
tahunan dan setiap individu 170 $ per tahun. Berapa banyak klien yang
apakah itu akan memberikan pendapatan tahunan terbesar? Berapa jumlahnya?
pendapatan tersebut?

Langkah 1: Kita definisikan variabel dan mengurutkan data dari pernyataan.

x jumlah asuransi untuk perusahaan

y jumlah asuransi untuk individu
Mari kita atur data sekarang dalam tabel berikut:

Perusahaan Particulares

Nº de seguros x y 90

Pendapatan 280 $ 170 $

x 20 y 2x

20
 Pusat Studi Tinggi Universitas OEI

Langkah 2: Fungsi tujuan pendapatan yang ingin kita maksimalkan

akan
Z=280x+170y
Dan batasan yang harus dipatuhi adalah:
x+y 90 (batas total asuransi adalah 90)
y 2x (jumlah individu setidaknya dua kali jumlah perusahaan)
x 20 (setidaknya 20 perusahaan)
y 0

Paso 3:Representar el sistema de inecuaciones, dado por las

pembatasan, untuk menemukan wilayah yang dapat diterima. (Gbr.15)

U
Región
layak
W

Gambar 15: Wilayah layak dari masalah

Langkah 4: Kami menghitung titik-titik sudut dari daerah yang layak dengan menemukan
interseksi setiap pasangan garis yang terlibat:
x y 90
20 y 90 y 70 U (20,70)
x 20

y 2·x
y 2·20 y 40 V (20,40)
x 20

x y 90
x 2x 90 3x 90 x 30 y 60 W (30,60)
y 2·x

21
 Pusat Studi Tinggi Universitas OEI

Dengan cara ini kita mendapatkan titik-titik berikut U(20,70), V(20,40)

y W(30,60).
Langkah 5: Kami menggantikan koordinat titik sudut ke dalam fungsi
tujuan untuk melihat di mana diperoleh manfaat maksimum.
Z=280·x+170·y (pendapatan)
Z(U)=280·20+170·70=5600+11900=17500 $
Z(V)=280·20+170·40=5600+6800=12400 $
Maksimum adalah
Z(W)=280·30+170·60=8400+10200=18600 $ dapatkan di
sudut
W(30,60)

Langkah 6: Kita memindahkan masalah ke realitas.

x=30 harus mengontrak 30 asuransi ke perusahaan
W(30,60)
y=60 harus mengontrak 60 asuransi kepada individu

Solusi akhir: Harus mengontrak 30 asuransi ke perusahaan

60 asuransi untuk individu untuk mendapatkan pendapatan maksimal
de 18600 $.

Aktivitas 3. Seorang pengusaha memproduksi dua produk A dan B. Untuk setiap kilo
de A membutuhkan 4 jam kerja dan 10000$ untuk bahan, dan juga,
memberikan keuntungan sebesar 7500$. Untuk setiap kilo B membutuhkan 7
jam kerja dan 8000$ untuk bahan dan mendapatkan keuntungan dari
5000$.
Setiap minggu industri dapat mengandalkan 200 jam kerja.
Selain itu, saya menandatangani kontrak yang mewajibkan Anda untuk memproduksi minimal 15
kilo A dan 10 kilo B, dan tidak dapat menghabiskan lebih dari 320000 $ dalam
material. Berapa kilo per minggu yang harus diproduksi untuk setiap produk
untuk mendapatkan manfaat maksimum yang mungkin?
Solusi: Anda harus memproduksi 24 kg A dan 10 kg B dan akan mendapatkan
keuntungan sebesar 230000$.

Aktivitas 4. Untuk membayar sebuah lahan, dibutuhkan setidaknya 9 kg dari

nitrogen dan 15 fosfor. Di pasar, mereka menjual dua jenis
produk-produk yang memiliki karakteristik sebagai berikut:

Nitrógeno Fósforo Harga

per Kg
Produk A 20 % 40 % 4$
Produk B 30 % 30 % 5$

22
 Pusat Studi Tinggi Universitas OEI

Produk apa yang harus dibeli petani?

membayar untuk kebun dengan pengeluaran paling sedikit?

Solusi: Ini adalah masalah pemrograman linier di mana

wilayah yang layak tidak terbatas dan selain itu, fungsi tujuan harus
menjadi minimal. Solusinya adalah membeli 30 kg produk A dan 10 kg
produk B dengan pengeluaran 170$.

Metode SIMPLEX: Pada tahun 1947, matematikawan George Dantzig

Ia berbicara untuk pertama kalinya tentang metode ini melalui publikasinya "El
Método Simplex”. Pada dasarnya terdiri dari algoritma iteratif
yang secara berurutan mendekati solusi optimal dari ini
jenis masalah. Berdasarkan pada sifat yang mengatakan bahwa
solusi optimal dari masalah Pemrograman Linear adalah
temukan di sebuah titik sudut (atau batas) dari wilayah yang mungkin dan seperti itu
jumlah simpul (dan sisi) adalah terbatas, kita dapat mengatakan bahwa
selalu akan ada solusi tersebut. Secara lebih intuitif,
metode ini memberi tahu kita bahwa jika fungsi tujuan F tidak mengambil nilainya
maksimum di titik A, maka ada sebuah sisi yang berangkat dari A ke
sepanjang mana F meningkat.

Definitifnya, Metode Simplex adalah prosedur yang cerdik

yang memungkinkan bergerak dari satu simpul ke simpul lainnya, semakin baik setiap kali (atau pada
kurang, tidak memburukkan) tujuan. Ini juga memungkinkan untuk menemukan apakah
wilayah layak kosong atau jika solusi optimal tidak terikat. Di dalam
praksis, metode ini hanya mencantumkan sebagian kecil dari poin-poin
ekstrem dari wilayah yang layak, yang sangat menyederhanakan
resolusi.

Jelas bahwa komputer telah memainkan peran penting dalam

proses ini. Sebagai anekdot, dikatakan bahwa pada tahun 1952 untuk suatu masalah
71 variabel dan 48 persamaan dilakukan implementasi pertama
komputasional yang memakan waktu 18 jam untuk menyelesaikan masalah.

Bibliografía:

-Bazaraa, S., Mokhtar dan Jarvis, J. (1981). Pemrograman Linier dan Aliran
de Redes. Ed. Limusa.
-Calvete Fernández, Herminia dan Mateo Collazos, P. (1994).
Pemrograman linier, Bulat dan Tujuan. Ed. Penerbit Universitas
Zaragoza.

-Mocholi Arce,M. dan Sala Garrido, R.(1993). Pemrograman linier.

Metodologi dan Masalah. Ed. Tebar Flores.
Salazar González, J. J. (2000). Pelajaran optimisasi. Ed.
Manual dan teks universitas (Universitas La Laguna).

23
 Pusat Studi Tinggi Universitas OEI

-Colorado T. Pemrograman linier. Diambil pada 15 Februari

2010 di
[Link]

- Proyek Descartes (Kementerian Pendidikan dan Ilmu Pengetahuan, Spanyol).

Dipulihkan pada 15 Februari 2010, dari
[Link]
Programasi_linear/[Link]

-Álavarez Fajardo, J. Material Interaktif dari mata pelajaran

2ºBachillerato Matematika Terapan untuk Ilmu Sosial.
Recuperado el 15 de Februari de 2010 de
[Link]
/zai_mates/web03-inecuaciones/[Link]

24