Tugas Akhir Modul 2 Edit.docx 4y1t6

TUGAS AKHIR MODUL 2

NAMA

: PUTU CHRISTINA DHARMA ASTUTI PUCANGAN

NO PESERTA

: 19220118010419

Soal 1. a. Menggunakan algoritma pembagian, tentukan FPB (1488,868). b. Tentukan nilai m dan n sehingga FPB (1488,868)= 1488 x m + 868 x n . c. Tentukan KPK [1488,868]. 2. Diketahui SPL

𝑎x − 2y = 0 3x + y = 0

a. Tunjukkan bahwa untuk setiap nilai a, maka SPL tersebut selalu konsisten. b. Tentukan nilai a agar SPL tersebut hanya mempunyai solusi trivial. c. Tentukan nilai a agar SPL tersebut mempunyai tak hingga banyak solusi. 3. Buktikan bahwa semua basis dari suatu ruang vektor berdimensi hingga mempunyai banyak vektor yang sama. 4. Buktikan bahwa masalah program linear berikut ini merupakan kasus penyelesaian tidak terbatas. 𝑀𝑎𝑘𝑠:𝑍 = 3𝑥 − 4𝑦 + 3𝑧 −𝑥 + 𝑦 + 𝑧 ≤ −3 h.m

−2𝑥 − 3𝑦 + 4𝑧 ≤ −5 −3𝑥 + 2𝑦 − 𝑧 ≤ −3 𝑥,y,𝑧 ≥ 0

5. Buktikan bahwa jika G grup komutatif dengan elemen identitas e, maka H = {x ∈ G | x2 = e} merupakan subgrup G.

Tugas Akhir Modul 2-Profesional

1

Penyelesaian 1. a. Berdasarkan Teorema 2.1.6 (Algoritma Pembagian Bilangan Bulat) 1488 = 868.1 + 620 868 = 620.1 + 248 620 = 248.2 + 124 248 = 124.2 + 0 Sehingga didapat FPB (1488,868) adalah 124

b. Berdasarkan Teorema 2.1.9 124 = 620 – 248.2 124 = 620 – (868 – 620). 2 124 = 620. 3– 868. 2 124 = (1488 – 868.1).3 – 868.2 124 = 1488.3 – 868.5 Sehingga berdasarkan teorema diatas, FPB (1488,868) = 124 >>>> 124 = 1488.3 – 868.5 Didapat m = 3 dan n = –5

c. Berdasarkan Teorema 2.1.14 KPK [1488,868] =

1488 x 868 FPB (1488,868)

KPK [1488,868] =

1488 x 868 124

KPK [1488,868] = 10416

2. a. Akan ditunjukkan bahwa untuk setiap nilai a, maka SPL tersebut selalu konsisten.  Untuk a = 0 SPL {

𝑎𝑥 − 2𝑦 = 0 3𝑥 + 𝑦 = 0

(0)x – 2y = 0 3x + 0 = 0

, sehingga y = 0

,, sehingga x = 0

Ini berarti SPL diatas memiliki solusi x = 0 dan y = 0  Untuk 𝑎 ≠ 0 SPL {

𝑎𝑥 − 2𝑦 = 0 3𝑥 + 𝑦 = 0

Tugas Akhir Modul 2-Profesional

2

𝑎𝑥 − 2𝑦 = 0 ⇔ 𝑥 =

2𝑦 𝑎

substitusi ke persamaan ke 2: 3𝑥 + 𝑦 = 0 2𝑦 3( ) + 𝑦 = 0 𝑎 6𝑦 𝑎𝑦 + =0 𝑎 𝑎 𝑦(6 + 𝑎) =0 𝑎 𝑦=0 Ini berarti SPL diatas memiliki solusi x = 0 dan y = 0 Karena untuk kedua kondisi, yaitu untuk a = 0 dan a ≠ 0 SPL tersebut memiliki solusi, maka SPL tersebut selalu konsisten.

b. Suatu SPL mempunyai solusi trivial apabila minimal mempunyai penyelesaian nol. 𝑎𝑥 − 2𝑦 = 0 Pada bagian a telah diperlihatkan untuk 𝑎 ≠ 0, SPL { memiliki solusi x = 0 3𝑥 + 𝑦 = 0 dan y = 0 Jadi SPL {

𝑎𝑥 − 2𝑦 = 0 memiliki solusi trivial jika 𝑎 ≠ 0 3𝑥 + 𝑦 = 0

c. Suatu SPL mempunyai tak berhingga banyak solusi apabila determinan matriks koefisiennya adalah 0. 𝑎 Det A = | 3

−2 | 1

0 = 𝑎 − (−6) 𝑎 = −6 𝑎𝑥 − 2𝑦 = 0 Jadi SPL { akan mempunyai tak berhingga banyak solusi jika a = −6 3𝑥 + 𝑦 = 0

3. Akan dibuktikan bahwa semua basis dari suatu ruang vektor berdimensi hingga mempunyai banyak vektor yang sama. Ambil sembarang vektor X, Y ∈ 𝑉𝑛 sedemikian sehingga X dan Y merupakan basis dari 𝑉𝑛 𝑋 = {𝑥1 , 𝑥2 , 𝑥3 … 𝑥𝑚 } dan 𝑌 = {𝑦1 , 𝑦2 , 𝑦3 … 𝑦𝑛 } dengan X dan Y merupakan basis dari 𝑉𝑛 Tugas Akhir Modul 2-Profesional

3

X basis maka X bebas linear dan Y basis maka Y bebas linear X basis dan Y bebas linear maka m  n......(i) Y basis dan X bebas linear maka n  m.....(ii) Dari (i) dan (ii) maka m = n. Karena banyak vector X = m sama dengan banyak vector Y = n, maka terbukti bahwa semua basis dari suatu ruang vector berdimensi hingga mempunyai banyak vector yang sama.

4. Akan dibuktikan bahwa masalah program linear berikut ini merupakan kasus penyelesaian tidak terbatas. 𝑀𝑎𝑘𝑠:𝑍 = 3𝑥 − 4𝑦 + 3𝑧 −𝑥 + 𝑦 + 𝑧 ≤ −3 h.m

−2𝑥 − 3𝑦 + 4𝑧 ≤ −5 −3𝑥 + 2𝑦 − 𝑧 ≤ −3 𝑥,y,𝑧 ≥ 0

 Masukkan variable slack Z – 3x + 4y – 3z + 0S1 + 0S2 + 0S3 = 0 –x + y + z + S1 + 0S2 + 0S3 = –3 –2x – 3y + 4z + 0S1 + S2 + 0S3 = –5 –3x + 2y – z + 0S1 + 0S2 + S3 = –3  Membuat tabel simplex Variabel

X1

X2

X3

S1

S2

S3

NK

Z

-3

4

-3

0

0

0

0

S1

-1

1

1

1

0

0

-3

S2

-2

-3

4

0

1

0

-5

S3

-3

2

-1

0

0

1

-3

dasar

 Menentukan kolom kunci. Kolom kunci adalah kolom yang mempunyai koefisien fungsi tujuan bernilai negatif terbesar Variabel

X1

X2

X3

S1

S2

S3

NK

-3

4

-3

0

0

0

0

dasar Z

Tugas Akhir Modul 2-Profesional

4

S1

-1

1

1

1

0

0

-3

S2

-2

-3

4

0

1

0

-5

S3

-3

2

-1

0

0

1

-3

 Menentukan baris kunci. Baris kunci adalah nilai indeks yang terkecil. 𝑖𝑛𝑑𝑒𝑘𝑠 = Variabel

𝑁𝐾 𝑓𝑢𝑛𝑔𝑠𝑖 𝑝𝑒𝑚𝑏𝑎𝑡𝑎𝑠 𝑁𝑖𝑙𝑎𝑖 𝑘𝑜𝑙𝑜𝑚 𝑓𝑢𝑛𝑔𝑠𝑖 𝑝𝑒𝑚𝑏𝑎𝑡𝑎𝑠

X1

X2

X3

S1

S2

S3

NK

Indeks

Z

-3

4

-3

0

0

0

0

-

S1

-1

1

1

1

0

0

-3

3

S2

-2

-3

4

0

1

0

-5

5/2

S3

-3

2

-1

0

0

1

-3

1

dasar

Angka Kunci

 Nilai baris kunci baru didapat dengan membagi nilai baris kunci lama dengan angka kunci. Sementara nilai baris yang lain = nilai baris lama – (koefisien pada kolom kunci x nilai baris baru kolom kunci)

Variabel

X1

X2

X3

S1

S2

S3

NK

Z

0

2

0

0

0

-1

-1

S1

0

1/3

4/3

1

0

-1/3

8/3

S2

0

-13/3

14/3

0

1

-2/3

11/6

X3

1

-2/3

1/3

0

0

-1/3

1

dasar

 Karena koefisien fungsi tujuan sudah tidak ada yang negatif. Sehingga proses dihentikan. Terlihat program linear berikut ini merupakan kasus penyelesaian tidak terbatas karena untuk X1 dan X2 belum dilakukan proses iterasi.

Tugas Akhir Modul 2-Profesional

5

5. Akan dibuktikan bahwa jika G grup komutatif dengan elemen identitas e, maka H = {x ∈ G | x2 = e} merupakan subgrup G. Karena e ∈ 𝐺 berarti e2 = e . e = e ∈ 𝐻 jadi H tak kosong. Ambil sembarang p, q ∈ 𝐻 Maka 𝑝2 = 𝑒 dan 𝑞 2 = 𝑒 Akan ditunjukkan bahwa 𝑝𝑞 −1 ∈ 𝐻 Maka (𝑝𝑞 −1 )2 = (𝑝𝑞 −1 )(𝑝𝑞 −1 ) = 𝑝2 (𝑞 −1 )2 = 𝑝2 (𝑞 2 )−1 = 𝑒. 𝑒 −1 = 𝑒 Sehingga 𝑝𝑞 −1 = 𝑒 terlihat 𝑒 ∈ 𝐻 maka terbukti bahwa p𝑞 −1 ∈ 𝐻 sehingga dapat disimpulkan bahwa H subgraf G.

Tugas Akhir Modul 2-Profesional

6