PROGRAMASI LINIER

1) Seorang pasien membutuhkan diet ketat dengan dua makanan y Setiap unit makanan
mengandung 120 kalori dan 2 gram protein. Satuan makanan mengandung 100
kalori dan 5 gram protein. Diet membutuhkan minimal 1000 kalori dan 30
gram protein. Jika harga setiap unit makanan es di $6000 dan dari setiap unit
dari makanan adalah $8000. Berapa banyak unit dari setiap makanan yang harus terkandung dalam diet untuk
agar biayanya minimal?
Solusi:

Sean:
jumlah unit makanan
: jumlah unit makanan
Fungsi tujuan:
( ,) = 6000. x + 8000. y = Míminimo
Pembatasan:
120. x + 100. y ≥ 1000kalori⇒ 6. +5 ≥ 50 (dibagi 20)
2. x + 5. y ≥ 30gram

≥0
≥0
Titik adalah perpotongan dari garis-garis:
6. x + 5y = 50
2. x + 5. y = 30

| 50 5 | 250 − 150 100

= 30 5 = = =5
6 5 30 − 10 20
| |
2 5

1
 PROGRAMASI LINIER

| 6 50 | 180 − 100 80
= 2 30 = = =4
6 5 30 − 10 20
| |
2 5

Di titik :
( 0,10=
) 6000. (0) + 8000. (10) = 80000
Di titik :
( 15,0)= 6000. (15) + 8000. (0) = 90000
Di titik :
( 5,4=
) 6000. (5) + 8000. (4) = 62000
Titik yang memenuhi kondisi fungsi tujuan adalah sudut :
4 unit makanan
= 5satuan makanan
Sebuah mesin memproduksi dua jenis televisi y Untuk membuatnya diperlukan waktu
produksi di mesin dan penyelesaian manual yang dilakukan oleh para pekerja. Penjualan dari
model memerlukan 2 jam di mesin dan setengah jam pekerjaan manual, dan menghasilkan sebuah

2
 PROGRAMASI LINEAR

manfaat 60 dolar. Penjualan model butuh 3 jam di mesin dan seperempat

jam kerja manual, dan menghasilkan keuntungan sebesar 55 dolar.
Tersedia total 300 jam kerja di mesin dan 60 jam kerja manual.
Antara dua jenis televisi harus diproduksi setidaknya 90. Berapa banyak dari
berapa banyak televisi dari setiap tipe yang harus diproduksi agar keuntungan maksimal?

Solusi:

Sean:
jumlah televisi tipe
: jumlah televisi tipe
Fungsi tujuan:
( ,) = 60. x + 55. y = Máximó
Pembatasan:
0,5. x + 0,25. y ≤ 60(jam secara manual)
Setara:

+ ≤ 60
2 4
Mengalikan dengan 4:
2. x + y ≤ 240
x + y ≥ 90(Total de televisores)
2. x + 3. y ≤ 300(jam di mesin)

≥0
≥0
La región factible se muestra en la siguiente figura:

3
 PROGRAMASI LINIER

Titik adalah perpotongan garis:

2. x + 3. y = 300
2. x + y = 240
Dengan mengurangkan dua persamaan ini hasilnya:

60
2. = 60 ⟹ = = 30
2
Kemudian:
240 − 30 210
2. x + 30 = 240 ⟹ x = = = 105
2 2
Di titik :
( 0,100=) 60. (0) + 55. (100) = 5500
Di titik :
( 120,0=
) 60. (120) + 55. (0) = 7200
Di titik :

4
 PROGRAMASI LINIER

( 0,90=
) 60. (0) + 55. (90) = 4950
Pada titik :
( 90,0=
) 60. (90) + 55. (0) = 5400
Di titik :
( 105,30=
) 60. (105) + 55. (30) = 7950
Titik yang memenuhi kondisi fungsi objektif adalah sudut. :
105 televisi tipe
= 30jenis televisi
Manfaat:7950 dolar.
3) Kandidasi dari suatu kelompok politik tertentu untuk pemilihan kota harus
memenuhi syarat-syarat berikut: Jumlah total kandidat harus berada di antara
6 y 18 y jumlah pria tidak boleh melebihi dua kali lipat jumlah wanita. Apa yang terbesar?
número de hombres que puede ser candidato de este grupo político?
Solusi:
Sean:
jumlah pria
: jumlah wanita
Fungsi tujuan:
( ,) = = á
Restricciones:
x+y≥6
x + y ≤ 18
≤ 2.
x≥0
y≥0
Karena fungsi yang akan dimaksimalkan adalah ( ,) = , maksimum terjadi pada titik = (12,6).
Kemudian:
12 pria
= 6 perempuan

5
 PROGRAMASI LINIER

precisan 1 g emas dan 1,5 g perak,

4) Seorang pengrajin perhiasan membuat dua jenis perhiasan. Yang jenis
menjualnya seharga 40 euro masing-masing. Untuk fabrikasi yang jenis gunakan 1,5 g emas
1 g perak, dan menjualnya seharga 50 euro. Tukang perak hanya memiliki 750 g dari masing-masing di bengkel.
Logam. Hitung berapa banyak perhiasan yang harus diproduksi dari setiap jenis untuk mendapatkan keuntungan
maksimal.
al jumlah perhiasan jenis e
Solusi: Kami memanggil jumlah perhiasan jenis .
Kami meringkas data dalam tabel:

Fungsi tujuan:
( ,) = 40. x + 50. y = Màximô
Pembatasan:
1. x + 1,5. y ≤ 750
1,5. + 1. ≤ 750
≥0
6
 PROGRAMASI LINIER

≥0

Di titik :
( 0,500=) 40. (0) + 50. (500) = 25000
Di titik :
( 0,500=) 40. (500) + 50. (0) = 20000
Di titik :
( 300,300=) 40. (300) + 50. (300) = 27000
Maksimum dicapai di titik (300,300). Oleh karena itu, ia harus memproduksi 300 perhiasan jenis
y 300 jenis untuk mendapatkan manfaat maksimal. Pendapatan dalam kasus ini adalah 27
000 euro.
5) Sebuah firma akuntan publik yang spesialis dalam menyiapkan penyelesaian dan pembayaran pajak dan
juga audit di perusahaan kecil. Ketertarikan adalah mengetahui berapa banyak audit dan likuidasi
dapat dilakukan setiap bulan, sehingga mereka mendapatkan pendapatan maksimum. Tersedia 800
jam untuk kerja langsung dan pengawasan dan 320 jam untuk pemeriksaan. Sebuah audit rata-rata memerlukan
40 jam kerja langsung dan pengawasan serta 10 jam peninjauan, selain itu menghasilkan pendapatan sebesar 300
dls. Sebuah penyelesaian pajak memerlukan 8 jam kerja langsung dan pengawasan serta 5 jam dari
tinjauan dan menghasilkan pendapatan sebesar 100 dolar. Audit dapat dilakukan sebanyak yang diinginkan, tetapi
maksimum dari penyelesaian bulanan yang tersedia adalah 60.

Solusi:
Mari kita tentukan terlebih dahulu variabel keputusan:

7
 PROGRAMASI LINIER

1 Jumlah audit bulanan.

2 Jumlah penyelesaian bulanan.

Fungsi tujuan:
Maksimalkan: = 300. x1+ 100. x2

Restricciones:
40. 1+ 8. 2≤ 800Waktu yang tersedia untuk pekerjaan langsung dan pengarahan.
10. 1+ 5. x2≤ 320Waktu yang tersedia untuk pekerjaan peninjauan.

2≤ 60

1, 2≥ 0

6) Sebuah toko kue terkenal karena dua spesialisasi kue mereka: kue Imperial dan kue
de Lima. Kue Imperial membutuhkan setengah kilogram gula dan 8 telur untuk pembuatannya dan
memiliki harga jual 8€. Kue Limau membutuhkan 1 kilogram gula dan 8 telur, dan memiliki
harga jual 10€. Di gudang masih tersisa 10 kilogram gula dan 120 telur. a)
Kombinasi spesialis apa yang dapat dibuat?
b) Berapa banyak unit dari setiap spesialisasi yang harus diproduksi untuk mendapatkan pendapatan terbesar
untuk penjualan?

8
 PROGRAMACIÓN LINEAL

Solusi:
Mari kita definisikan dulu variabel keputusan:

1 Jumlah kue tipe Imperial.

2: Número de tortas tipo Lima.

Fungsi tujuan:
Maksimalkan: = 8. x1+ 10. x2

Restricciones:
0,5. 1+ 1. x2≤ 10Kilo gula.
8. 1+ 8. 2≤ 120Jumlah telur.

1, 2≥ 0

9
 PROGRAMASI LINIER

Metode Simplex: Metode Simplex yang diterbitkan oleh George Dantzig pada tahun 1947 terdiri dari sebuah
algoritma iteratif yang secara berurutan melalui iterasi mendekati optimal
dari masalah Pemrograman Linier jika yang terakhir ini ada.
Implementasi komputasional pertama dari Metode Simplex adalah pada tahun 1952 untuk sebuah
masalah 71 variabel dan 48 persamaan. Penyelesaiannya membutuhkan waktu 18 jam. Kemudian, pada tahun 1956, seorang
kode yang disebut RSLP1, diimplementasikan di IBM dengan 4Kb RAM, menerima resolusi
dari model dengan 255 pembatasan.
Metode Simplex memanfaatkan sifat bahwa solusi optimal dari suatu masalah
Pemrograman Linier terletak di suatu titik sudut atau batas dari domain titik yang layak
(ini terakhir dalam kasus yang sangat khusus), oleh karena itu, pencarian sekunder dari algoritme tersebut
berdasarkan evaluasi progresif dari titik-titik ini hingga menemukan yang optimal. Perlu dicatat
bahwa, untuk menerapkan Metode Simplex pada model linier, ini harus dalam format
khusus yang dikenal sebagai format standar yang akan kita definisikan di bawah ini.

Bentuk standar dari model pemrograman linier:

Sebuah masalah pemrograman linier adalah ketika fungsi tujuan ini adalah fungsi linier dan
pembatasan adalah pertidaksamaan linier; sebuah masalah dengan pembatasan dan variabel se
mewakili.

: = 1. 1+ 2. 2+ 3. 3+ ⋯+ .

Dikenakan:

11. 1+ 12. 2+ ⋯+ 1 . ≤ 1

21. 1+ 22. 2+ ⋯+ 2 . ≤ 2

31. 1+ 32. 2+ ⋯+ 3 . ≤ 3

1. 1+ 2. 2+ ⋯+ . ≤
Selain itu:

1≥ 0, x2≥ 0 3≥ 0,⋯ , ≥0

1 ≥ 0, b2≥ 0, 3≥ 0, ⋯ , ≥0
Kami akan menggunakan notasi berikut:
Koefisien variabel ( = 1,2,3, ⋯ ) dalam fungsi tujuan .

Nilai sisi kanan untuk pembatasan (i = 1,2,3, ⋯ ).

Koefisien dari variabel keputusan.

10
 PROGRAMASI LINIER

Untuk menggunakan metode simplex, perlu mengubah ketidaksamaan menjadi persamaan,

ketika batasan adalah pertidaksamaan dengan kurang dari atau sama dengan≤), untuk mengubahnya menjadi
persamaan, kami menambahkan ke setiap batasan sebuah variabel baru tidak negatif yang disebut variabel dari
kelonggaran .
Ketika pembatasan adalah persamaan dengan kesetaraan=), kami menambahkan sebuah variabel tidak
negatif, yang disebut variabel buatan.
Ketika batasan adalah persamaan dengan kesetaraan (≥), kami menambahkan sebuah variabel tidak
negatif, disebut variabel buatan dan kita mengurangi variabel kelebihan yang tidak negatif .

Variabel Artifisial: Variabel artifisial adalah trik matematis untuk mengubah

inekuasi≥dalam persamaan, atau ketika muncul kesetaraan dalam masalah asli,
karakteristik utama dari variabel ini adalah bahwa mereka tidak boleh menjadi bagian dari solusi, mengingat
yang tidak mewakili sumber daya. Tujuan utama dari variabel-variabel ini adalah pembentukan dari
matriks identitas.
Variabel ini dilambangkan dengan huruf " , selalu ditambahkan pada batasan, mereka
koefisien adalah (karena ini disebut Metode) grande, donde berarti sebuah
angka yang terlalu besar sangat sedikit menarik untuk fungsi tujuan), dan tanda di dalam
fungsi objektif bertentangan dengan makna itu, yakni, dalam masalah
Maksimisasi tanda Anda adalah kurang dari−) dan dalam masalah Minimisasi tanda nya adalah (+),
kami mengulang dengan tujuan agar nilai Anda dalam solusi adalah nol (0).

Dalam sebuah masalah pemrograman linier dengan variabel (termasuk yang slack) dan
persamaan, untuk mencari solusi dasar, disamakan dengan nol − variabel, yang mana
denominasi dasar, dan yang lainnya disebut variabel dasar.
Variabel tidak dasar adalah sekumpulan variabel dari suatu masalah pemrograman linier
dalam bentuk standar, di mana nilai-nilainya diambil sebagai nol.

11
 PROGRAMASI LINIER

Variabel dasar adalah sekumpulan variabel dari suatu masalah pemrograman linier
dalam bentuk standar, yang nilai-nilainya berbeda dari nol.
Sebuah solusi dasar yang dapat dilaksanakan ketika semua variabel mengambil nilai tidak negatif.

Contoh:Sebuah pabrik furnitur memproduksi dua jenis meja. Jenis I dan jenis II, di dalam
departemen pemotongan, perakitan, dan penyelesaian. Jumlah jam yang tersedia untuk setiap
departemen adalah 80 jam, 220 jam dan 210 jam masing-masing. Jam yang
diperlukan dalam produksi di setiap departemen untuk setiap jenis meja yang diberikan di
tabel berikut:

Jika keuntungan untuk setiap unit meja jenis I dan jenis II adalah US $5 dan US $6
secara masing-masing. Berapa banyak unit dari masing-masing jenis yang harus diproduksi setiap bulan untuk
memaksimalkan utilitas dan apa itu utilitas?
Solusi:
1) Definisi variabel keputusan:
Sean:

1: jumlah meja jenis I.

2 jumlah meja jenis II.
:

2) Penentuan masalah (fungsi tujuan):

Utilidad:

= 5. 1+ 6. x2= á

3) Restricciones:

1+ 2≤ 80Ketersediaan departemen pemotongan dalam jam.

3. 1+ 2. x2≤ 220Ketersediaan departemen Perakitan dalam jam.

2. x1+ 3. x2≤ 210Ketersediaan departemen Penyelesaian dalam jam.

1, 2, 3≥ 0

12
 PROGRAMASI LINIER

Sesuai dengan diskusi sebelumnya, kita harus menulis masalah optimasi dalam
bentuk standar:
Maksimalkan: = 5. 1+ 6. x2+ 0. 1+ 0. s2+ 0. 3

Terkait dengan:

1. 1+ 1. x2+ 1. 1+ 0. s2+ 0. s3= 80

3. 1+ 2. x2+ 0. s1+ 1. 2+ 0. s3= 220
2. x1+ 3. x2+ 0. s1+ 0. s2+ 1. 3= 210

1, 2, 3≥ 0
Variabel yang terlibat dalam masalah ini adalah 1 , 2 , 1, 2, 3, di mana 1 , 2anak variabel adalah
keputusan dan 1, 2, 3merupakan variabel cadangan.

Solusi dasar yang layak awal adalah:

1= 0, 2= 0, 1= 80, 2= 220, 3= 210.

Di mana 1, 2, 3adalah variabel dasar.
Tabel simplex awal:

13
 PROGRAMASI LINIER

Kolom yang disebut corresponds to a list of the basic moment variables.

Kolom adalah koefisien dari variabel dasar fungsi tujuan .

Baris yang ditandai diperoleh sebagai jumlah produk dari kolom oleh
koefisien yang terkait dengan variabel ( 1 , 2 , 1, 2, 3):

1= 01( +) 0 3+
( 0) 2 =0
( )

2= 0 (1+)(0 )2( )+0 3 = 0

3= 0 (1+)(0 )0( )+0 0 = 0

4= 0 (0+)(0 )1( )+ 0 0 = 0

5= 0 (0+) 0 0 (+0) 1 = (0 )
Baris yang ditandai − diperoleh sebagai perbedaan antara koefisien dari fungsi
tujuan dan nilai yang sesuai :

1− 1= 5−0=5

2− 2= 6−0=6

3− 3= 0−0=0

4− 4= 0−0=0

5− 5= 0−0=0
Koefisien − disebut indikator.

Kegunaan dihitung dengan menjumlahkan produk dari elemen-elemen yang sesuai di

kolom-kolom y :

= 0(80+) 0 220
( +0) 210(= 0 )

14
 PROGRAMASI LINIER

Sekarang kita harus menentukan mana variabel dasar yang harus diubah menjadi tidak dasar, untuk
Kami mencari indikator positif terbesar:

2− 2= 6−0=6
Kolom yang mengandung indikator positif terbesar disebut kolom pivot:

Kami sekarang memilih kuotien positif terkecil / 2 (jika menemukan seri, dipilih
baris yang lebih atas), dan baris yang mengandungnya kita sebut baris pivot.
Catatan: Pembagian dengan nol atau dengan angka negatif tidak diperhitungkan. Jika semua
son negatif atau tidak ditentukan, masalah tersebut tidak memiliki solusi. Dan prosesnya berakhir.

Interseksi antara baris pivot dengan kolom pivot adalah elemen pivot:3.
Melalui operasi dasar antara baris, elemen-elemen lain di kolom
pivote melalui elemen pivote harus diubah menjadi nol; dengan ini diperoleh sebuah
kolom baru dari matriks identitas.
Variabel yang masuk adalah 2dan variabel keluaran adalah 3:

15
 PROGRAMASI LINIER

Sekali lagi, kolom adalah koefisien dari variabel dasar fungsi tujuan
.
Baris yang ditandai diperoleh sebagai jumlah dari produk kolom karena
koefisien yang terkait dengan variabel( 1 , 2 , 1, 2, 3):

1= ( +)0 5/3+
01/3 ( 6 2/3
) (
=4 )

2= 0 (0+)(0 )2( )+6 1 = 6

3= 0 (1+)(0 )0( )+6 0 = 0

4= 0 (0+)(0 )1( )+6 0 = 0

5= 0 (−1/3+ 0) -2/3( +6 1/3

) = 2( )
−
Seperti sebelumnya, baris yang ditandaidiperoleh sebagai selisih antara koefisien
dari fungsi tujuan dan nilai-nilai yang sesuai :

1− 1= 5−4=1

2− 2= 6−6=0

3− 3= 0−0=0

4− 4= 0−0=0

5− 5= 0 − 2 = −2
Kegunaan dihitung dengan jumlah produk dari elemen yang sesuai di
kolom-kolom y :

= 0(10+) 0 80( + )6 70 (= 420

)
Karena masih ada elemen positif dalam indikator − , kami ulangi prosesnya:

16
 PROGRAMASI LINIER

Kita harus menentukan variabel dasar mana yang harus diubah menjadi tidak dasar, untuk itu
kami mencari indikator positif terbesar:

1− 1= 1
Kolom yang mengandung indikator positif terbesar disebut kolom pivot.
Kita sekarang memilih rasio positif terkecil / 1, dan ke baris yang mengandungnya
kami sebut sebagai baris pivot.

Interseksi dari baris pivot dengan kolom pivot adalah elemen pivot:1/3.

Melalui operasi dasar antara baris, elemen lain di kolom

pivote melalui elemen pivote harus diubah menjadi nol; dengan ini diperoleh sebuah
kolom baru dari matriks identitas.
Variabel yang masuk adalah 1dan variabel yang keluar adalah 1 :

17
 PROGRAMASI LINIER

Karena tidak ada lagi elemen positif dalam indikator − , proses selesai.

Zmax = 450

1= 30jumlah meja tipe I.

2= 50jumlah meja jenis II.

2= 30Holgura departemen Perakitan.

Seperti:
1. 1+ 1. 2+ 1. 1+ 0. s2+ 0. 3= 80, jadi 1= 0
2. x1+ 3. x2+ 0. 1+ 0. s2+ 1. 3= 210, jadi 3= 0
Artinya, semua jam yang tersedia di departemen pemotongan dan penyelesaian digunakan.
Contoh: Sebuah toko perabotan memproduksi meja, meja makan, dan kursi. Proses pembuatan memerlukan
bahan baku dan tenaga kerja. Tenaga kerja diklasifikasikan menjadi dua jenis: pertukangan kayu dan
terminasi. Jumlah sumber daya yang dibutuhkan untuk setiap jenis produk ditampilkan di
tabel. Saat ini tersedia 48 inci kayu, 20 jam untuk penyelesaian dan 8
Jam untuk pertukangan kayu. Setiap meja kerja dijual seharga US $60, setiap meja seharga US $30 dan setiap kursi seharga
US $20. Perusahaan berpikir bahwa permintaan akan meja dan kursi tidak terbatas, tetapi percaya bahwa
akan menjual paling banyak 5 meja. Karena sumber daya sudah diperoleh, perusahaan
ia ingin memaksimalkan keuntungannya.

Sumber Kantor Meja Kursi

Bahan (inci kayu) 8 6 1
Terminaciones (horas) 4 2 1,5
Carpintería (horas) 2 1,5 0,5

Mengingat variabel-variabel berikut:

1: Número de escritorios producidos

2: Jumlah meja yang diproduksi

3: Jumlah kursi yang diproduksi

Model berikut dapat dibangun:
: = 60. 1+ 30. x2+ 20. x3

Restricciones:
8. 1+ 6. 2+ 1. x3≤ 48 (a) Material
4. 1+ 2. x2+ 1,5. 3≤ 20 (b) Akhir
2. x1+ 1,5. x2+ 0,5. x3≤ 8 Carpintería
2≤ 5 (d) Permintaan meja
1 , 2 , 3≥ 0

18
 PROGRAMASI LINIER

Langkah 1: Kami mulai metode Simplex dengan mengubah pembatas menjadi bentuknya
standar. Untuk itu, dalam setiap pembatasan tipe≤ kami mengintegrasikan variabel kelonggaran 1 , 2,
3y 4 .

8. x1+ 6. x2+ 1. x3+ 1. 1= 48

4. x1+ 2. x2+ 1,5. 3+ 1. 2= 20
2. 1+ 1,5. 2+ 0,5. x3+ 1. 3= 8

2+ 1. 4= 5
Variabel yang terlibat dalam masalah tersebut adalah 1 , 2, 3, 1, 2, 3, 4, di mana 1 , 2, 3anak laki-laki
variabel keputusan dan 1, 2, 3, 4adalah variabel kelonggaran.
Solusi dasar yang layak awal adalah:

1= 0, 2= 0, 3= 0, 1= 48, 2= 20, 3= 8, s4= 5.

Di mana 1, 2, 3, 4son variabel dasar.

Langkah 2: Membentuk tabel simplex atau tabel awal.

Paso 3:La columna que contiene el mayor indicador positivo se denomina columna pivote:

19
 PROGRAMASI LINIER

Kami sekarang memilih cuotien positif terkecil / 1, dan ke baris yang mengandungnya
kami menyebutnya baris pivot.

Pertemuan antara baris pivot dengan kolom pivot adalah elemen pivot:2.
Melalui operasi dasar antara baris, elemen lainnya di kolom
pivote melalui elemen pivote harus diubah menjadi nol; dengan ini diperoleh sebuah
kolom baru dari matriks identitas.
Variabel masuk adalah 1dan variabel keluaran adalah 3:

Karena masih ada elemen positif dalam indikator − , kami mengulangi prosesnya:

Langkah 4: Kolom pivot baru adalah kolom yang mengandung indikator positif terbesar: 5

20
 PROGRAMASI LINIER

Sekarang kita memilih hasil bagi positif terkecil / 3, dan ke baris yang mengandungnya
kami menyebutnya baris pivot.

Persimpangan baris pivot dengan kolom pivot adalah elemen pivot:0,5.

Melalui operasi-elementer antara baris, elemen lain dalam kolom

pivote melalui elemen pivot harus diubah menjadi nol; dengan ini diperoleh sebuah
kolom baru dari matriks identitas.
Variabel yang masuk adalah 3dan variabel yang keluar adalah 2:

Karena tidak ada elemen positif yang muncul dalam indikator − , kami menyelesaikan proses:

1= 24

21
 PROGRAMASI LINEAR

4= 5

1= 2

3= 8
Z = 280
Seperti:
8. 1+ 6. 2+ 1. x3+ 1. 1= 48
Jadi:

8 ( 2+
) 6. 2+ 1 8 (+ 24
) = 48
( )
6. x2= 0 ⟹ x2= 0
Contoh: Mari kita bayangkan bahwa kebutuhan minimal mingguan seorang individu dalam protein,
karbohidrat dan lemak masing-masing adalah 8, 12 dan 9 unit. Anggaplah bahwa
kita harus memiliki persiapan dengan komposisi minimum itu dengan mencampurkan 2 produk y ,
cuyos contenidos per kilogramo adalah yang ditunjukkan dalam tabel berikut:
PRODUCTO PROTEIN HIDRATOS LEMBAH BIAYA
2 6 1 600
1 1 3 400
Kebutuhan 8 12 9

Berapa kilogram dari setiap produk yang harus dibeli setiap minggu agar biaya
apakah diet harus minimal?
Solusi:
Variabel keputusan:

1: Jumlah dalam kilogram produk .

2: Jumlah dalam kilogram produk .

Fungsi tujuan:
Minimalkan: = 600. 1+ 400. 2

Pembatasan:

2. 1+ 1. x2≥ 8
6. x1+ 1. x2≥ 12
1. x1+ 3. 2≥ 9

1, 2≥ 0

22
 PROGRAMASI LINIER

Solusi:
Kita mengubah ketidaksetaraan menjadi persamaan:

Untuk mengubah sebuah batasan tipe≥ dalam pembatasan kesetaraan, ditentukan

variabel kelebihan 1, 2y 3dan variabel artifisial 1 , 2y 3 .
Minimalkan = 600. 1+ 400. 2+ 0. 1+ 0. s2+ 0. s3+ . 1+ . 2+ . 3

Terhadap:
2. 1+ 1. x2+ 1− 1= 8
6. x1+ 1. x2+ 2− 2= 12
1. x1+ 3. x2+ 3− 3= 9

1, 2, 1, 2, 3, 1, 2, 3≥ 0
Catatan: Jika masalahnya adalah untuk memaksimalkan, kita akan menulis:

23
 PROGRAMASI LINIER

Maksimalkan = 600. 1+ 400. x2+ 0. 1+ 0. 2+ 0. 3− . 1− . 2− . 3

Kami membangun tabel simplex awal:

Di baris pertama, semua variabel ditempatkan, di baris kedua ditempatkan di

koefisien fungsi tujuan. Di 3 baris berikutnya ditempatkan koefisien dari
restriksi.
Prosedur untuk menghitung koefisien dari baris keenam, adalah sebagai berikut:

1= M. 2 + M. 6 + M. 1 = 9. M

2= M. 1 + M. 1 + M. 3 = 5. M

3= ( +) . 0 + . 0 = −
. -1

4= M. 0 + M.-1 ( + ). 0 = −

5= M. 0 + M. 0 + M.-1 =( − )

6= M. 1 + M. 0 + M. 0 = M

7= M. 0 + M. 1 + M. 0 = M

8= M. 0 + M. 0 + M. 1 = M

9= M. 8 + M. 12 + M. 9 = 29. M

Optimal dicapai ketika terpenuhi bahwa:

− ≥0∀

Pemilihan kolom pivot:

Dari koefisien baris − (indikator) diambil yang memiliki nilai tertinggi
negatif (angka lebih kecil) (ketika itu mengenai minimisasi) dan seluruhnya dipilih
kolom. Variabel dari kolom ini adalah yang masuk ke dalam sistem (menjadi dasar).

24
 PROGRAMASI LINIER

Pemilihan baris pivot:

Dibagi koefisien kolom "Solusi" dengan unsur yang sesuai
dari kolom pivot, dan dari hasil pembagian dipilih nilai positif terkecil
dan seluruh baris yang terkait dengan nilai ini. Ini adalah variabel yang keluar dari basis (menjadi
tidak dasar).

Elemen pivot adalah6.

Variabel yang masuk dituliskan di tempat variabel yang keluar. 1di tempat 2 , para
tabel ini, dan apa yang dicari adalah membentuk satu kolom dengan 1 di tempat yang
interseksi, yaitu, mendapatkan elemen pivot dan nol di tempat lain yang sama
kolom.
Kami membagi baris pivot dengan 6:

25
 PROGRAMASI LINIER

Karena masih ada elemen negatif di − prosedur belum selesai.

Dari koefisien baris − diambil yang memiliki nilai negatif tertinggi

(nomor lebih kecil) dan seluruh kolom dipilih. Variabel dari kolom ini adalah yang dimasukkan
ke sistem (menjadi dasar).
Koefisien dari kolom "Solusi" dibagi dengan elemen yang sesuai
dari kolom pivot, dan dari hasil pembagian dipilih nilai positif terkecil
dan seluruh baris yang terkait dengan nilai ini. Ini adalah variabel yang keluar dari basis (beralih menjadi
tidak dasar).

Elemen pivot adalah17/6.

Variabel yang masuk dituliskan di tempat variabel yang keluar. 1di tempat 3 , para
tabel ini, dan apa yang dicari adalah membentuk kolom dengan 1 di tempat yang
interseksi, yaitu, mendapatkan elemen pivot dan nol di tempat lain yang sama
kolom.
Kami mengalikan baris pivot dengan6/17:

26
 PROGRAMASI LINEAR

Karena masih ada elemen negatif di − prosedur ini belum selesai.

Dari koefisien baris − diambil yang memiliki nilai negatif terbesar

(nomor lebih kecil) dan seluruh kolom dipilih. Variabel dari kolom ini adalah yang masuk
ke sistem (menjadi dasar).
Koefisien pada kolom 'Solusi' dibagi dengan elemen yang sesuai
dari kolom pivot, dan dari hasil pembagian dipilih nilai positif terkecil
dan seluruh baris yang terkait dengan nilai ini. Ini adalah variabel yang keluar dari basis (berubah menjadi
tidak dasar).

Elemen pivot adalah5/17.

Variabel yang masuk ditulis di tempat variabel yang keluar. 2di tempat 1 para
tabel ini, dan yang dicari adalah membentuk kolom dengan 1 di tempat yang
interseksi, yaitu, mendapatkan elemen pivot dan nol di tempat lain yang sama
kolom.
Kami mengalikan baris pivot dengan17/5:

27
 PROGRAMASI LINIER

Karena sudah tidak ada elemen negatif di − prosedur telah selesai, oleh karena itu,
solusi optimal dicapai dengan nilai variabel sebagai:

1= 3

2= 2
= 2600

Contoh: Perusahaan Propapel S.A, memproduksi kertas bond untuk kantor dengan berbagai ukuran,
carta dan oficio. Untuk membuatnya, digunakan dua mesin percetakan yang memberikan warna,
Mesin I dan II. Di mesin I diperlukan 2 jam untuk produksi satu ton.
kertas ukuran surat dan 2 jam untuk kertas ukuran folio: di mesin II dibutuhkan 2
jam untuk pembuatan satu ton kertas ukuran surat dan 6 jam untuk satu ton
kertas ukuran folio. Mesin I, untuk efek biaya, dapat bekerja maksimum 8 jam,
sementara mesin II harus bekerja setidaknya 12 jam.
Berapa banyak ton kertas ukuran letter dan oficio yang harus diproduksi untuk meminimalkan
biaya, jika biaya per unit setiap ton kertas adalah 1,5 dan 2 dolar untuk surat dan
pekerjaan secara berurutan.

Solusi:

28
 PROGRAMASI LINIER

Mari kita definisikan terlebih dahulu variabel keputusan:

1 Jumlah ton kertas ukuran surat.

2 Jumlah ton kertas ukuran folio.

Función objetivo:
Minimalkan: = 1,5. x1+ 2. x2

Pembatasan:
2. x1+ 2. x2≤ 8Waktu yang tersedia untuk mesin I
2. 1+ 6. 2≥ 12Waktu yang tersedia untuk mesin II

1, 2≥ 0
Langkah 1: Kami mulai metode Simplex dengan mengubah batasan ke bentuknya
Standar. Untuk itu pada pembatasan tipe≤ kami memasukkan variabel kelonggaran 1. Para
mengubah pembatasan jenis≥ dalam pembatasan kesetaraan, variabel didefinisikan
kelebihan 2dan variabel buatan 2 .

Fungsi tujuan berbentuk:

Meminimalkan = 1,5. 1+ 2. x2+ 0. s1+ 0. s2+ . 2

Sujeto a:

2. ×1+ 2x2+ 1= 8
2. x1+ 6. x2+ 2− 2= 12

1, 2, 1, 2, 2≥ 0
Variabel yang terlibat dalam masalah ini adalah 1, 2 1, 2, di mana 1, 2son variabel dari
putusan dan 1, 2son variabel holgura dan 2itu adalah variabel buatan.
Di mana 1, 2adalah variabel dasar.
Langkah 2: Membentuk tabel simplex atau tabel awal.

29
 PROGRAMASI LINIER

Langkah 3: Pemilihan kolom pivot: Karena kita sedang menyelesaikan masalah minimisasi,
dari indikator (koefisien baris − ) diambil yang memiliki nilai terbesar
negatif (angka lebih kecil) dan seluruh kolom dipilih. Variabel kolom ini adalah
yang masuk ke dalam sistem (beralih menjadi dasar).

Kami sekarang memilih rasio positif terkecil / 2, dan ke baris yang mengandungnya
kami menyebutnya baris pivot.

Interseksi dari baris pivot dengan kolom pivot adalah elemen pivot:6.

Melalui operasi dasar antara baris, elemen lainnya dalam kolom

pivote melalui elemen pivot harus diubah menjadi nol; dengan ini diperoleh sebuah
kolom baru dari matriks identitas.
Variabel yang masuk adalah 2dan variabel keluarannya adalah 2 Menghapus kolom 2 , kami mendapatkan
tabel berikut:

30
 PROGRAMASI LINIER

Karena minimum dicapai ketika dipenuhi bahwa:

− ≥0∀

Proses selesai dan:

1= 4

2= 2Jumlah ton kertas ukuran folio.

= 4dolar
Bagaimana:
2. 1+ 2x2+ 1= 8
Diperoleh:

2. x1+ 22 ( +)4 = 8 ⟹ 1= 0

1= 0Jumlah ton kertas ukuran surat.

y Volume penjualan dari adalah karena
Contoh: Sebuah perusahaan memproduksi dua produk,
kurang dari 80% dari total penjualan y de Namun, perusahaan tidak dapat menjual
lebih dari 100 unit dari per hari. Kedua produk menggunakan bahan baku, yang mana
ketersediaan harian maksimum adalah 240 lb. Tingkat konsumsi bahan baku adalah
2 lb per unit of y 4 lb per unit dari Keuntungan dari y de $20 dan $50,
masing-masing.
Tentukan kombinasi produk yang optimal untuk perusahaan.
Solusi:
Mari kita definisikan terlebih dahulu variabel keputusan:

1 Jumlah unit produk .

2 Jumlah unit produk .

Fungsi objektif:

31
 PROGRAMASI LINIER

Maksimalkan: = 20. 1+ 50. x2

Restricciones:

1≥ 0,8( 1+ 2 ), setara dengan: 1≥ 0,8. 1+ 0,8. x2⇒ 0,2. x1- 0,8. x2≥ 0

1≤ 100
2. 1+ 4. x2≤ 240

1, 2≥ 0
Langkah 1: Kami mulai metode Simplex dengan mengubah batasan ke bentuknya
standar. Untuk itu pada pembatasan tipe≤ kami memasukkan variabel kelonggaran 1. Para
mengubah pembatasan tipe≥ dalam sebuah batasan kesetaraan, variabel didefinisikan
kelebihan 2dan variabel buatan 2 .

Fungsi tujuan berbentuk:

Maksimalkan = 20. 1+ 50. x2+ 0. 1+ 0. s2+ 0. 3− . 1

Sublimasi:
0,2. x1- 0,8. x2− 1+ 1= 0
1. 1+ 1. 2= 100
2. 1+ 4. x2+ 1. 3= 240

1, 2, 1, 2, 1≥ 0
Variabel yang melibatkan masalah adalah 1 , 2 1, 2, 3, di mana 1 , 2adalah variabel dari
keputusan dan 1, 2, 3adalah variabel pelonggaran dan 1itu adalah variabel buatan.

Di mana 2, 3, 1adalah variabel dasar.

Langkah 2: Membentuk tabel simplex atau tabel awal.

Paso 3:Selección columna pivote: Como estamos resolviendo un problema de

maksimalisasi, dari indikator (koefisien dari baris − ) diambil yang memiliki

32
 PROGRAMASI LINIER

nilai positif terbesar (nomor terbesar) dan seluruh kolom dipilih. Variabel dari ini
kolom adalah yang masuk ke dalam sistem (menjadi dasar).
Sekarang kita memilih kuotien positif terkecil / 1 dan ke baris yang mengandungnya
kami menyebutnya baris pivot.

Persimpangan baris pivot dengan kolom pivot adalah elemen pivot:0,2.

Variabel masuk adalah 1dan variabel keluarannya adalah 1 Menghapus kolom 1 , kami mendapatkan
tabel berikut:

Karena nilai maksimum tercapai ketika terpenuhi bahwa:

− ≤0∀

Kita harus mengulangi prosedur sebelumnya:

Kami memilih indikator positif terbesar dan memilih seluruh kolom. Variabel ini
kolom adalah yang masuk ke dalam sistem (menjadi dasar).
Sekarang kita memilih kuotien positif yang terkecil / 2, dan ke baris yang mengandungnya
kami menyebutnya baris pivot.

Persimpangan antara baris pivot dengan kolom pivot adalah elemen pivot:12.

33
 PROGRAMASI LINIER

Variabel yang masuk adalah 2dan variabel keluarannya adalah 3:

Karena maksimum dicapai ketika terpenuhi bahwa:

− ≤0∀

Prosedur ini berakhir dan:

1= 80:Número de unidades del producto .

2= 20Jumlah unit produk .

= 2600

34