D1 · Decision Mathematics 1

Matematika Pengambilan Keputusan 1 (D1, kertas WDM01/01, 1 jam 30 menit, 75 nilai, penilaian pertama Juni 2019) adalah pilihan diskrit dari IAL: P1–P2 diasumsikan, dan setiap metode adalah ALGORITMA — daftar instruksi eksak yang terbatas. Tidak ada entri buku rumus melampaui hal-hal dasar: nilai diberikan untuk mengeksekusi prosedur secara presisi dan menyatakan hasil dalam bentuk yang dibutuhkan. Referensi ini mencakup algoritma pengurutan dan pengemasan, pohon rentang minimum, jalur terpendek, masalah postman Tiongkok dan penjual keliling, analisis jalur kritis dan pemrograman linear.

Aturan rumah untuk jawaban algoritma:

Bubble sort membandingkan item bersebelahan, menukar pasangan yang tidak sesuai, satu kali per laluan sekali; laluan tanpa pertukaran mengakhiri proses. Quick sort memilih item TENGAH dari daftar sebagai pivot, mempartisi item tersisa menjadi "kurang dari pivot", "sama dengan pivot" dan "lebih besar dari pivot" (menjaga setiap salinan); ia mengurutkan ulang kelompok yang lebih kecil dan lebih besar secara rekursif — selalu kutip pivot dan daftar setelah setiap partisi. Spesifikasi menetapkan pilihan item tengah pada metode yang didefinisikan dalam glosariumnya, sehingga daftar latihan di sini mempertahankan jumlah item ganjil dan item tengah adalah satu pada posisi $\tfrac{n+1}2$. Pengemasan bin: first-fit menempatkan setiap item ke dalam bin pertama yang tersedia; first-fit decreasing mengurutkan item terbesar-dulu lalu menerapkan first-fit; full-bin packing mencari kombinasi yang mengisi bin secara tepat.

Contoh terpecahkan — quick sort (asli). Urutkan 9, 2, 7, 5, 3, 4, 6. Item tengah (posisi 4 dari 7) adalah 5: lebih kecil = 2, 3, 4; lebih besar = 9, 7, 6, menghasilkan 2, 3, 4, 5, 9, 7, 6. Subdaftar 2, 3, 4 (pivot 3): 2, 3, 4 — terurut. Subdaftar 9, 7, 6 (pivot 7): 6, 7, 9 — terurut. Daftar akhir: 2, 3, 4, 5, 6, 7, 9.

Contoh terpecahkan — pengemasan bin (asli). Bin berkapasitas 10; item 7, 5, 4, 3, 6, 2 (total 27, jadi setidaknya 3 bin). First-fit: 7→b1, 5→b2 (7+5 > 10), 4→b2 (9), 3→b1 (10), 6→b3, 2→b3 (8): bin (7,3), (5,4), (6,2). First-fit decreasing: 7, 6, 5, 4, 3, 2: 7→b1, 6→b2, 5→b3 (6+5 > 10), 4→b2 (10), 3→b1 (10), 2→b3 (7): bins (7,3), (6,4), (5,2) — juga 3 bin.

A pohon rentang minimum (MST) menghubungkan setiap titik dengan total bobot terkecil. Algoritma Kruskal: urutkan sisi berdasarkan bobot, tambahkan sisi terkecil yang tidak membentuk siklus (tolak dan lanjutkan jika akan membentuknya). Algoritma Prim: kembangkan sebuah pohon dari sembarang titik awal, berulang kali menambahkan sisi termurah dari pohon ke sebuah titik baru. Bentuk matriks Prim: coret baris awal, lingkari entri tersisa termurah di kolom titik yang dipilih, dan lanjutkan. Kruskal didorong oleh sisi (bagus untuk jaringan yang digambar); Prim didorong oleh titik (bagus untuk matriks). Keduanya memberikan total yang sama; sisi mungkin berbeda hanya ketika bobot setara. berbeda hanya ketika bobot seimbang.

Contoh terpecahkan (asli). Sisi AB 4, AC 2, BC 3, BD 5, CD 1: Kruskal memilih CD 1, AC 2, BC 3 (B bergabung — tidak ada siklus), lalu menolak AB 4 dan BD 5 (siklus): total MST 6. Prim dari A: AC 2, CD 1 (sisi termurah dari {A,C} ke simpul baru), CB 3: pohon yang sama, dan total 6 ✓. Selalu daftar sisi sesuai urutan pemilihan dan berikan totalnya.

Untuk bobot tepi non-negatif, algoritma Dijkstra melabeli simpul dengan jarak total terkecil yang ditemukan sejauh ini: label simpul awal 0; pilih berulang kali simpul tanpa label dengan nilai label sementara, jadikan permanen, dan perbarui tetangganya (baru = permanen + bobot, hanya jika lebih kecil). Catat urutan keabadian dan akhir label; rute dipulihkan dengan menelusuri kembali ke simpul yang labelnya sama dengan label akhir dikurangi bobot penghubung.

Contoh terpecahkan (asli). Sisi AB 4, AC 2, BC 1, BD 5, CD 8. Label: A = 0 permanen; C = 2 permanen; B = min(4, 2+1) = 3 permanen; D = min(3+5, 2+8) = 8 permanen. Rute terpendek dari A ke D memiliki panjang 8: A–C–B–D (telusur balik: 8 = 3 + 5 di B, 3 = 2 + 1 di C).

Masalah inspeksi rute (kurir pos Tiongkok) melintasi setiap SIDANG minimal sekali dan kembali ke titik awal. Panjang total = jumlah semua sisi + cara terpendek untuk menduplikasi sisi agar setiap simpul menjadi genap. Temukan simpul ganjil (maksimal empat), daftar pasangannya, pilih pasangan dengan total bobot terkecil, dan duplikasi sisi-sisi tersebut. Nyatakan pasangan sebelum total.

Contoh terpecahkan (asli). Sisi AB 4, AC 2, BC 3, BD 5, CD 1 (total 15). Derajat: A 2, B 3, C 3, D 2 — simpul ganjil adalah B dan C, jadi duplikasi BC (bobot 3): rute tertutup terpendek yang melintasi setiap sisi minimal sekali memiliki panjang 15 + 3 = 18.

Masalah pedagang traveling klasik toured setiap SIMPUL tepat sekali dan mengembalikan, pada graf lengkap dengan ketaksamaan segitiga. Batas: MST dari jaringan digandakan merupakan rute batas ATAS (berjalan di setiap tepi MST dua kali); jalan pintas memberikan batas atas yang lebih baik batas. Batas bawah berasal dari argumen berbasis MST (misalnya MST sendiri, atau menghapus sebuah simpul dan menambahkan dua tepi termurahnya). Algoritma tetangga terdekat membangun tur: dari simpul awal berulang kali pergi ke simpul yang belum dikunjungi terdekat, lalu kembali. Konversikan menjadi jaringan lengkap jarak terpendek terlebih dahulu ketika graf tidak lengkap (melalui Dijkstra atau inspeksi). ketika graf tidak lengkap (via Dijkstra atau inspeksi).

Contoh terpecahkan (asli). Jaringan lengkap: AB 4, AC 2, AD 7, BC 3, BD 5, CD 6 (the D–A (2): panjang tur 3 — batas atas. MST adalah AC + BC + BD = 5, sehingga menggandakan D–A (7): panjang tur 17 — batas atas. MST adalah AC + BC + BD = 10, sehingga menggandakannya memberikan batas atas kasar 20, ditingkatkan menjadi 17 melalui shortcut; batas bawah dari penghapusan A (MST dari B, C, D adalah 3 + 5 = 8, ditambah dua sisi termurah A yaitu AC + AB = 2 + 4 = 6) adalah 14. The tur optimal berada di antara 14 dan 17.

dummies (busur berbobot nol) menyelesaikan ketergantungan yang tidak dapat diekspresikan oleh ujung bersama. Jalur kritis adalah rantai terpanjang melalui jaringan: durasi proyek. Hitung waktu kejadian terawal (laju maju: nilai maksimum kedatangan) dan waktu kejadian terlambat (laju mundur: nilai minimum keberangkatan). Slack total aktivitas = waktu selesai terlambat − waktu mulai terawal − durasi; aktivitas kritis memiliki slack nol. Graf Gantt (cascade) membatangi setiap aktivitas dari waktu mulai terawalnya dengan slack sebagai ruang penutup; penjadwalan mengalokasikan pekerja hari demi hari. aktivitas memiliki float nol. Gantt (cascade) charts membar setiap aktivitas dari mulai paling awal dengan float sebagai spasi akhir; penjadwalan mengalokasikan pekerja dari hari ke hari.

Contoh terarah (asli). Aktivitas A (3 hari), B (4), C (4 setelah A), D (1 setelah B), E (5 setelah C dan D). Rantai A–C–E = 12 hari; rantai B–D–E = 10 hari: jalur kritis adalah A–C–E dan proyek memakan waktu 12 hari; total float D = 12 − (4 + 1 + 5) = 2 hari.

Merumuskan: tentukan variabel keputusan, tuliskan tujuan (maksimalkan/minimalkan) dan setiap kendala sebagai ketaksamaan, termasuk $x, y \ge 0$. Selesaikan masalah dua variabel secara grafis: arsir daerah layak, lalu gunakan metode penggaris (geser penggaris sepanjang gradien fungsi tujuan) atau metode titik sudut (evaluasi fungsi tujuan di setiap titik sudut daerah layak). Solusi bilangan bulat: uji titik-titik bilangan bulat di dekat titik optimal di dalam daerah tersebut.

Contoh terpecahkan — pemrograman linear (asal). Maksimalkan $P = 3x + 2y$ dengan syarat $x + y \le 10$, $2x + y \le 14$, $x, y \ge 0$. Titik sudut daerah layak adalah $(0,0)$, $(7,0)$, $(4,6)$, $(0,10)$; mengevaluasi $P$: 0, 21, 24, 20 — nilai maksimumnya adalah $P = 24$ pada $(4,6)$, di mana kedua batasan terpenuhi secara ketat.

• Jalankan penyortiran gelembung dan cepat dengan menunjukkan setiap lintasan dan pivot; pengemasan bin menggunakan first-fit, first-fit decreasing, dan full-bin dengan penempatan yang ditampilkan.
• Temukan MST menggunakan Kruskal dan Prim (bentuk node dan matriks); gambar jaringan dari matriks dan sebaliknya.
• Jalankan Dijkstra dengan label sesuai urutan permanensi; pulihkan rute, bukan hanya panjangnya.
• Selesaikan inspeksi rute: simpul ganjil, semua pasangan dengan bobot, duplikasi terkecil, total panjang jalan.
• Batasi TSP klasik: MST ganda dan shortcut untuk batas atas, penghapusan MST untuk batas bawah; jalankan tetangga terdekat pada jaringan jarak terpendek lengkap.
• Bangun jaringan aktivitas dengan dummy; lompatan maju dan mundur untuk waktu peristiwa; total float; identifikasi jalur kritis; gambar diagram Gantt dan jadwal.
• Susun program linear sepenuhnya; selesaikan secara grafis dengan penggaris atau metode titik sudut; temukan solusi bilangan bulat terbaik.