Membuat keputusan. Contoh

Melanjutkan topik, saya akan mengatakan bahwa saya melihat publikasi dari penulis Habr lainnya tentang topik ini. Ada minat pada masalah, tetapi tidak ada yang mau masuk ke teori. Bertindak seperti penemu pionir. Akan sangat bagus jika mereka menerima hasil, prestasi baru, tetapi tidak ada yang berusaha untuk ini.



Tetapi ternyata ternyata lebih buruk dari yang telah diketahui, banyak faktor yang tidak diperhitungkan, hasil teori diterapkan di mana ia tidak merekomendasikan melakukannya dan secara umum semuanya tidak terlihat sangat serius, meskipun Habr, sebagaimana harus dipahami, tidak memperjuangkan ini. Pembaca tidak bisa dan tidak boleh bertindak sebagai filter.

Perangkat alternatif asli, pengukuran dan evaluasinya

Diketahui bahwa masalah dalam menemukan solusi hanya muncul dalam situasi pilihan multi-alternatif. Untuk mempertimbangkan situasi pengambilan keputusan, merumuskan masalah pengambilan keputusan (DP) tertentu, memilih metode untuk menyelesaikannya, perlu memiliki beberapa informasi awal tentang alternatif, hubungan preferensi.



Mari kita tunjukkan di sub-bagian metode apa untuk mendapatkannya ada. Alternatif memiliki banyak sifat (fitur) yang mempengaruhi keputusan. Misalnya, indikator sifat benda (berat, volume, kekerasan, suhu, dll.) Dapat bersifat kuantitatif atau kualitatif.



Biarkan beberapa properti dari himpunan alternatif dari Ω dinyatakan dengan bilangan, yaitu, ada pemetaan ψ: Ω → E1, di mana E1 adalah himpunan bilangan real. Kemudian properti seperti itu dicirikan oleh indikator, dan bilangan z = ψ (x) disebut nilai (perkiraan) alternatif dalam istilah indikator.



Untuk mengevaluasi alternatif, perlu dilakukan pengukuran indikator.



Definisi. Pengukuran indikator properti tertentu dipahami sebagai menetapkan nilai numerik ke tingkat individu indikator ini dalam unit tertentu. Dalam hal ini, pemilihan unit pengukuran menjadi penting.



Jadi, misalnya, jika volume beberapa bagian wadah diukur pertama kali dalam meter kubik, lalu dalam liter, maka esensi indikator tidak akan berubah; hanya jumlah unit yang akan berubah. Metrik properti ini dapat diskalakan, dikalikan, atau dibagi dengan nilai konstan untuk metrik properti.



Di sisi lain, ada properti yang indikatornya tidak memungkinkan adanya manipulasi nilai tersebut. Tingkat pemanasan benda dicirikan oleh suhu dan diukur dalam derajat. Nilai indikator ini + 10 ° dan –15 ° tidak memungkinkan untuk menilai berapa kali benda dengan suhu + 10 ° dipanaskan lebih banyak daripada benda dengan suhu –15 °



Dari contoh-contoh ini dimungkinkan (dan penting) untuk menyimpulkan bahwa indeks volume dan suhu mengacu pada jenis properti yang berbeda, di atas nilai z = ψ (x) di mana transformasi tertentu f (z) = f (ψ (x)) ...



Yaitu, himpunan transformasi yang dapat diterima f (z) diambil sebagai dasar untuk menentukan jenis skala di mana indikator atribut (properti) tertentu diukur. Melakukan satu atau beberapa pengukuran indikator fitur yang disorot oleh peneliti, kita sampai pada tugas menentukan jenis skala di mana pengukuran harus dilakukan.



Tanpa menyelesaikan masalah ini dengan benar, kita dapat mengakui penanganan yang salah dari hasil pengamatan (pengukuran) saat memprosesnya. Hal ini terjadi ketika nilai indikator mengalami transformasi yang dilakukan di luar kumpulan transformasi yang diperbolehkan untuk jenis skala tertentu.



Definisi. Skala pengukuran adalah urutan nilai dengan nama yang sama dengan berbagai ukuran yang diterima berdasarkan kesepakatan.

Mari pertimbangkan lebih detail jenis utama timbangan.







1. Skala nominal . Skala nominal digunakan ketika seorang peneliti berurusan dengan objek yang dijelaskan oleh beberapa karakteristik. Bergantung pada apakah suatu objek memiliki nilai tertentu dari fitur atau ketiadaannya, objek tersebut dirujuk ke satu kelas atau lainnya.



Misalnya, jika kita berbicara tentang orang, maka nilai fitur (skala fitur dibentuk oleh dua nilai jenis kelamin: pria dan wanita) memungkinkan untuk menetapkan setiap orang dengan jelas ke kelas tertentu. Untuk alasan ini, skala tersebut disebut skala penilaian. Tanda seperti itu sebagai profesi memungkinkan seseorang dipanggil, misalnya guru, tukang kayu, atau sebaliknya sesuai dengan nilai indikator profesinya.



Skala dalam hal ini dibentuk oleh nama-nama semua profesi. Jelas, pada skala ini, nol tidak diindikasikan, meskipun tidak adanya profesi dalam subjek memungkinkan dia untuk ditempatkan secara tepat ke kategori orang tanpa profesi. Nama-nama profesi tidak diurutkan dengan cara apa pun dalam skala ini, meskipun seringkali disusun menurut abjad karena alasan kenyamanan.



Dari pertimbangan tersebut, skala seperti ini disebut dengan skala penamaan.

Transformasi nilai yang valid dalam skala ini adalah semua fungsi satu-ke-satu: f (x) ≠ f (y) <=> x ≠ y.



2. Skala ordinal . Jika sifat yang dipelajari, misalnya, kekerasan material, memanifestasikan dirinya secara berbeda dalam objek dan memiliki nilai yang tidak dapat diukur secara khusus, tetapi seseorang dapat dengan tegas menilai intensitas komparatif dari manifestasinya untuk dua objek mana pun, kemudian mereka mengatakan bahwa nilai sifat tersebut diukur pada skala ordinal. Contoh klasiknya adalah kekerasan mineral. Titik referensi adalah 0 pada skala tidak ditentukan.



Nilai karakteristik didefinisikan sebagai berikut. Mineral yang lebih keras dari pasangan tersebut meninggalkan goresan di sisi lainnya. Semua mineral dari nilai ciri ini dapat disusun sebagai berikut: pertama yang paling padat, yang kedua lebih keras meninggalkan goresan hanya yang pertama, yang ketiga meninggalkan goresan pada dua yang pertama, dan seterusnya ..



Perbedaan antara skala ordinal dari nominal yang nilai karakteristiknya gagal merampingkan, sedangkan nilai pada skala nominal bahkan tidak bisa dipesan. Kerugian dari skala ordinal adalah tidak proporsional.



Tidak mungkin menjawab pertanyaan berapa banyak atau berapa kali satu mineral lebih keras dari yang lain. Transformasi skala ordinal yang dapat diterima terdiri dari semua fungsi yang meningkat secara monoton dengan sifat: x ≥ y => f (x) ≥ f (y).



3.Skala interval (interval). berbeda dari skala urutan karena untuk properti yang mereka gambarkan, masuk akal tidak hanya hubungan ekivalensi dan keteraturan, tetapi juga penjumlahan interval (perbedaan) antara berbagai manifestasi kuantitatif properti. Contoh tipikal adalah skala interval waktu.



Interval waktu (misalnya, periode kerja, periode studi) dapat ditambahkan dan dikurangi, tetapi tidak ada gunanya menambahkan tanggal acara apa pun.



Contoh lain, skala panjang (jarak) - interval spasial ditentukan dengan menyelaraskan penggaris nol dengan satu titik, dan pembacaan dilakukan di titik lain. Skala jenis ini juga termasuk skala temperatur Celsius, Fahrenheit, Reaumur.



Transformasi linier dapat diterima dalam skala ini, (x - y) / (z -v); x ∓ y; mereka menerapkan prosedur untuk menemukan ekspektasi matematika, deviasi standar, koefisien asimetri, dan momen offset.



4. Skala perbedaan (titik) Skala perbedaan berbeda dari skala urutan di mana skala interval sudah dapat dinilai tidak hanya bahwa ukurannya lebih besar dari yang lain, tetapi juga berapa banyak, pada dasarnya, ini adalah skala absolut yang sama, tetapi nilainya digeser oleh beberapa nilai relatif terhadap nilai absolut (x - y) <(z -v); x ∓ y;



5. Skala hubungan... Skala himpunan transformasi yang dapat diterima terdiri dari semua transformasi kesamaan disebut skala relasi. Titik referensi ditetapkan pada skala ini dan skala pengukuran dapat diubah untuknya.



Biarkan skala ini mengukur panjang sebuah benda. Dalam kasus ini, Anda dapat beralih dari mengukur dalam meter ke mengukur dalam sentimeter, dengan menurunkan satuan pengukuran dengan faktor 100. Jelasnya, dalam hal ini, perbandingan panjang L (A) dan L (B) dari dua benda A dan B, yang diukur dalam satuan yang sama, tidak akan berubah bila satuannya diubah.



Nilai-nilai indikator sifat, yang diukur dalam skala ini, memungkinkan untuk

menjawab pertanyaan berapa kali lebih intens sifat tersebut memanifestasikan dirinya dalam satu objek daripada di objek lain. Untuk tujuan ini, perlu mempertimbangkan rasio nilai L (A) / L (B) = k.



Jika rasionya lebih besar dari satu (k> 1) maka nilai indikator atribut untuk objek pertama A adalah k kali lebih besar dari B, jika k <1, maka nilai indikator atribut untuk objek B adalah 1 / k kali lebih besar dari pada A. adalah perkalian dengan bilangan bulat positif dan hanya itu.



6. Skala mutlak . Skala yang paling sederhana adalah skala yang hanya memungkinkan satu transformasi f (x) = x. Situasi ini sesuai dengan satu-satunya cara untuk mengukur indikator properti suatu objek, yaitu penghitungan ulang objek sederhana.



Skala ini disebut skala absolut. Saat kita mendaftarkan objek x, kita tidak tertarik pada apapun selain objek ini. Skala absolut dapat dianggap sebagai implementasi tertentu dari beberapa skala lainnya.

Tugas pengambilan keputusan. Mendapatkan matriks relasi

Kami mencantumkan kemungkinan pengaturan ZPR, ini termasuk:

• pengurutan linier alternatif (puncak dalam rantai adalah yang terbaik);
• menyoroti alternatif terbaik;
• menyoroti subset (tidak berurutan) dari alternatif terbaik;
• menyoroti subset berurutan dari alternatif terbaik;
• pemesanan parsial alternatif;
• pemisahan alternatif yang dipesan (dipesan sebagian);
• partisi alternatif (klasifikasi) yang tidak berurutan.

Berdasarkan analisis pengukuran indikator properti alternatif dalam skala yang berbeda, hasil pengukuran dapat disajikan dengan cara yang berbeda [1, 5].



1. Tabel klasifikasi. Tabel diperoleh ketika pengukuran dilakukan dalam skala nominal dan merupakan tabel, yang barisnya adalah: nama objek, dan kolom adalah nama kelas$$$X_1, X_2, X_3,$ ... dll. Di kolom kelas 1, kelas 2, dll., 1 diletakkan jika objek milik kelas ini dan 0 - jika tidak (Tabel Kelas objek).



Di tabel kelas, objek $$$x_1 ,x_2 є X_1, x_3 є X_2, x_4 є X_3.$



2. Matriks hubungan preferensi. Diperoleh dengan melakukan pengukuran dalam skala ordinal. Untuk mengungkapkan preferensi pada himpunan objek Ω berarti menunjukkan himpunan semua pasangan objek (x, y) dari himpunan ini yang objek x lebih disukai (misalnya, lebih keras) daripada objek y. Matriks hubungan preferensi diperoleh sebagai berikut. (lihat di sini, gbr 2.15)



Sedang dibangun$$$_{[n×n]}^p$ matriks persegi. Garis ke-i sesuai dengan elemen ke-i$$$x_i$ himpunan Ω, dan kolom ke-j untuk elemen$$$x_j$ . Di perpotongan baris ke-i dan kolom ke-j, 1 ditempatkan jika benda tersebut$$$x_i$ lebih disukai daripada objek$$$x_j$ , nol jika benda tersebut$$$x_j$ lebih disukai daripada objek$$$x_i$ , 1/2 jika benda$$$x_i$ dan$$$x_j$ acuh tak acuh, dan tidak ada yang diletakkan - jika objeknya tidak ada bandingannya$$$x_i$ dan$$$x_j$ tidak bisa dibandingkan.



Contoh hubungan preferensi seperti itu disajikan dalam matriks di bawah ini.





3. Tabel indikator. Diperoleh saat mengukur dalam skala hubungan. Properti indikator yang akan diukur dipilih. Pengukuran properti ini dilakukan, dan hasil pengukuran dicatat dalam tabel.



Di kolom$$$p_1, p_2, p_3, p_4$ tabel Rasio preferensi berisi nilai-nilai indikator properti yang digunakan untuk mengevaluasi objek$$$x_1,x_2,x_3,x_4,x_5,x_6$ dan$$$x_7$ .



Setelah menerima hasil pengukuran dalam bentuk presentasi ini, kita perlu menampilkan hasil dalam bentuk relasi, karena kita akan menyelesaikan ZPR, dengan mengandalkan peralatan teori relasi biner yang dikembangkan dengan baik.



Pemetaan tabel preferensi ke matriks relasi biner adalah sebagai berikut:





Dari matriks hubungan preferensi $$$_{[4×4]}^p$ untuk 4 alternatif disajikan pada tabel. Hubungan preferensi akan menjadi matriks$$$_{[4×4]}^p$ , yang terlihat seperti ini:





Pemetaan scorecard ke matriks rasio preferensi adalah sebagai berikut: $$$a_{i,j}=1$ jika:

1) banyaknya indikator yang digunakan benda$$$x_i$ lebih disukai daripada objek$$$x_j$ lebih besar dari jumlah indikator dimana benda tersebut$$$x_j$ lebih disukai daripada objek$$$x_i$ ;



2) untuk objek$$$x_i$ tidak ada indikator yang mengambil nilai sekecil mungkin.



3) kondisi 1 menyiratkan bahwa indikator-indikator yang menjadi objek$$$x_i$ tidak lebih buruk dari objek$$$x_j$ , merupakan mayoritas dari semua indikator yang dipertimbangkan.



Namun, jika kondisi ini terpenuhi, mungkin ternyata sesuai dengan indikator yang menjadi objek$$$x_i$ lebih buruk dari objek$$$x_j$ , perbedaannya signifikan; Untuk mengurangi jumlah kasus seperti itu saat memberikan preferensi pada x, diperkenalkan kondisi 2.

Metode untuk memecahkan masalah pengambilan keputusan

Misalkan, setelah menerima data awal, kita memiliki relasi R pada himpunan alternatif $$$Ω= {(x_1, ...,x_n)}$... Dan tugasnya adalah membuat keputusan. Metode utama adalah pengurutan linier (ranking) alternatif, yaitu membangun alternatif dalam sebuah rantai dalam urutan menurun dari nilai, kesesuaian, kepentingan, dan sejenisnya, dari yang “terbaik” ke “terburuk”.



Rasio R dapat berupa:

1. sikap non-transitif lengkap;
2. hubungan tatanan parsial;
3. urutan linier.

Hanya dalam kasus linearitas relasi R, struktur preferensi memenuhi tugas. Dalam hal ini, peringkat alternatif dari himpunan Ω diperoleh secara langsung dengan membuat diagram garis dari himpunan yang dipesan. Dalam diagram, alternatifnya$$$x_i$, akan lebih tinggi dari alternatifnya $$$x_j$jika disukai.



Solusi dari masalah yang diajukan untuk hubungan lengkap dan transitif dilakukan dengan menggunakan metode (algoritma) untuk alternatif pemeringkatan, dan untuk pesanan parsial menggunakan algoritma pengubahan urutan linier. Algoritme ini akan dibahas dalam paragraf berikut di bawah ini.



Peringkat alternatif . Biarkan relasi [Ω, R] lengkap dan nontransitif. Properti kelengkapan berarti semua alternatif$$$Ω = {(x_1, ...,x_n)}$himpunan sebanding satu sama lain. Adanya nontransitivitas hanya mungkin jika grafik preferensi G [Ω, R] mengandung kontur.



Struktur grafik hubungan perlu diubah sehingga kontradiksi logis dalam bentuk kontur dihilangkan. Jika kita mengasumsikan bahwa ada kontur dalam hubungannya dengan R$$$x_1, x_2, …,x_k, x_1,$ lalu saat menentukan peringkat alternatif $$$x_1$ harus ditempatkan lebih tinggi $$$x_2, x_3, …,x_k, x_1,$, yang mengarah pada kontradiksi.

Mari kita perkenalkan pernyataan berikut [1,5].



Misalkan B 'dan B "adalah dua kontur sembarang grafik dengan bentuk G [Ω, R], maka jika beberapa elemen$$$x_i$ є B 'mendominasi elemen $$$x_j$ є B '', lalu elemen apa pun $$$x_1$є B 'elemen apapun mendominasi $$$x_k$є B ''.



Proposal ini memungkinkan untuk mempartisi himpunan R menjadi m subset$$$B_1, B_2, …,B_m$seperti yang $$$B_i ∩ B_j=∅, ∀i,j є [1, m]; UB_i =Ω.$

Jadi, masalah pemeringkatan alternatif himpunan terbagi dalam dua tahap:

1) pemilihan kontur grafik, yaitu. partisi himpunan Ω menjadi himpunan bagian$$$B_1, B_2, …,B_m$dan pengurutan kelompok subset ini;

2) peringkat elemen kontur yang dipilih pada tahap pertama.



Algoritma untuk menyoroti kontur suatu graf



Untuk mengetahui kontur suatu graf, terdapat algoritma sederhana [1]. Biarlah$$$_{[n×n]}$ Merupakan matriks ketetanggaan dari grafik G [Ω, R], dan $$$_{[n×n]}$–Unit matriks. Kami membentuk$$$_{[n×n]}+ _{[n×n]}$, $$$(_{[n×n]}+ _{[n×n]})^2$, $$$(_{[n×n]}+ _{[n×n]})^3$,… Urutan derajat matriks, yang elemen-elemennya menyatakan jumlah lintasan dengan panjang paling banyak 1, 2, 3… Untuk beberapa nilai m ≤ n, kita memperoleh persamaan berikut (matriks stabil):

$$$(_{[n×n]}+ _{[n×n]})^m=(_{[n×n]}+_{[n×n]})^{m+1}$...



Diketahui dari teori graf [10] bahwa untuk setiap sistem dari semua baris identik dari matriks “mapan” terdapat subset simpul dari graf yang terletak dalam satu kontur. Mengelompokkan simpul yang sesuai ke dalam kelas, kami mendapatkan partisi dari himpunan asli Ω menjadi subset$$$B_1, B_2, …,B_m$...



Jelas, di antara subset ini kita dapat menemukan subset seperti itu$$$B_im$bahwa elemen subset ini tidak akan didominasi oleh elemen dari subset lainnya. Subset ini akan dianggap yang terbaik, dan akan menempati posisi pertama dalam peringkat dalam urutan preferensi yang menurun.



Kemudian kami menemukan subset terbaik di antara subset yang tersisa menggunakan prinsip yang sama dan meletakkannya di tempat kedua. Kami akan

melanjutkan prosedur ini sampai semua subset menempati peringkatnya.



Biarkan relasi preferensi R diberikan pada himpunan Ω oleh matriks$$$_{[6×6]}$...





Grafik relasi R ditunjukkan pada Gambar. G.





Angka: D. Grafik relasi non-transitif R



Untuk melaksanakan tahap pertama perangkingan elemen himpunan, perlu dilakukan pemilihan kontur pada grafik G [Ω, R]. Ini dilakukan dengan menaikkan matriks ketetanggaan grafik ke pangkat berurutan sampai matriksnya cocok.



Kita mendapatkan$$$(_{[6×6]}+ _{[6×6]})$, $$$(_{[6×6]}+ _{[6×6]})^2$, $$$(_{[6×6]}+ _{[6×6]})^3$...

Selanjutnya, kami secara berurutan menghitung kekuatan yang meningkat dari matriks, menjumlahkannya dengan matriks satuan dari dimensi yang sesuai sampai matriks berhenti berubah:





Karena $$$(_{[6×6]}+ _{[6×6]})^2 =(_{[6×6]}+ _{[6×6]})^3$, Kita dapat menyimpulkan bahwa $$$(_{[6×6]}+ _{[6×6]})^2 = (_{[6×6]}+ _{[6×6]})^k$, untuk k ≥ 2. Dari hasil analisis matriks $$$(_{[6×6]}+ _{[6×6]})^2$ maka garis-garis tersebut sesuai dengan elemen-elemennya $$$x_1,x_4,x_6$secara bersamaan, ini menunjukkan bahwa elemen-elemen ini termasuk dalam kontur yang sama dari grafik G [Ω, R].



Elemen-elemen$$$x_1,x_4,x_6$ membentuk satu set $$$B_1 =(x_1,x_4,x_6)$... Kontur lain dibentuk oleh elemen$$$x_2,x_3,x_5$yang termasuk dalam set $$$B_2 =(x_2,x_3,x_5)$...



Jadi, kami telah mempartisi himpunan menjadi m = 2 kelas$$$B_1, B_2$... Mari kita melakukan pemesanan kelompok dari subset ini. Untuk melakukan ini, Anda perlu menemukan beberapa elemen$$$x_i є B_1$elemen mana yang mendominasi $$$x_j є B_2$...



Ini berarti keunggulan subset$$$B_1$ lebih $$$B_2$... Dalam contoh kami$$$x_1 є B_1$ mendominasi $$$x_2 є B_2$... Oleh karena itu, subset$$$B_1$ mendominasi $$$B_2$... Representasi grafis dari dominasi di partisi Ω ditunjukkan pada Gambar. QC.





Angka: QC. Pemeringkatan kontur yang dipilih pada



Algoritma tahap pertama untuk memeringkat elemen-elemen kontur . Apakah mungkin untuk menyusun elemen-elemen relasi yang terletak pada kontur yang sama, apakah setara satu sama lain, atau adakah perbedaan yang cukup halus di antara mereka untuk membedakannya? Ternyata kemungkinan seperti itu, sebagai suatu peraturan, ada [1].



Mari kita tunjukkan dengan$$$B_{h_{[n×n]}}$matriks ketetanggaan dari kontur ke-h. Mari perkenalkan konsepnya$$$p^i(k)$adalah gaya orde k elemen i, yang nilainya dihitung sebagai jumlah elemen baris ke-i dalam matriks $$$B_{h_{[n×n]}}^k$(1).



Biarlah$$$b_{h_{[i,j]}}^k$Apakah elemen di baris ke-i dan kolom ke-j dari matriks, maka





Kekuatan relatif dari orde ke-k elemen i dipahami sebagai pecahan



Ketika k meningkat tak terbatas (k → ∞), jumlahnya $$$π_i(k)$cenderung ke batas tertentu π, yang selanjutnya akan kita sebut kekuatan elemen i. Vektor$$$_{[n]} = (π_1,...,π_n)$disebut vektor batas.



Karena teorema Perron-Frobenius [1], batas selalu ada. Vektor eigen yang dinormalisasi dari matriks ketetanggaan kontur bertepatan dengan vektor batasnya. Oleh karena itu, vektor$$$_{[n]} = (π_1,...,π_n)$(2)



dapat ditemukan tanpa menghitung gaya terintegrasi$$$p^i(k)$, dengan menyelesaikan sistem persamaan linier

$$$B_{h_{[n×n]}} · _{[n]} = λ_{[n]}$, (3) dengan

λ adalah akar riil non-negatif terbesar dari persamaan karakteristik

$$$det(λ_{[n×n]}- B_{h_{[n×n]}}) = 0$(4)

Perlu dicatat bahwa vektor eigen ternormalisasi dari matriks tak terkomposisi nonnegatif tidak berubah ketika matriks dikalikan dengan bilangan s> 0, begitu juga saat dijumlahkan dengan matriks berbentuk sE.



Kemudian elemen kontur diurutkan dengan mengurangi nilai komponen vektor yang sesuai$$$_{[n]}$, yaitu elemen i mendominasi elemen j saat$$$π_i >π_j$...



Kami akan memberi peringkat elemen himpunan$$$B_1 =(x_1,x_4,x_6)$... Mari kita buat matriks preferensi untuk himpunan ini





Vektor gaya terintegrasi dari orde 1 untuk elemen $$$(x_1, x_4, x_6)$terlihat seperti (1,1,2), vektor gaya relatif P (k) = (1 / 4,1 / 4,2 / 4).

Peringkat item$$$(x_1, x_4, x_6)$kekuatan urutan pertama ditunjukkan pada Gambar. R.





Angka: R. Peringkat elemen



Mari kita temukan vektor yang mengkarakterisasi kekuatan orde ke-2, ke-3, ke-4 dan ke-5.





Representasi grafis dari peringkat ditunjukkan pada Gambar. P.







Gbr. C - Rantai



Melakukan pemeringkatan elemen himpunan B2 dengan cara yang sama, kami memperoleh hasil yang disajikan pada Gbr. Baik.



Sebagai hasil dari penggabungan peringkat elemen himpunan 1 dan 2, kami meneruskan ke urutan akhir elemen himpunan Ω (Gbr. C).

Penataan ulang linier dari pesanan parsial ketat

Misalkan relasi R (Gbr. A di bawah teks), yang diperoleh sebagai hasil agregasi penilaian individu para ahli, adalah relasi orde parsial pada himpunan Ω. Dalam hal ini, Ω adalah himpunan yang teratur. Pembangunan urutan linier alternatif adalah untuk mendapatkan penilaian global dari "kemampuan" mereka dalam skala ordinal.



Untuk beberapa alasan, beberapa ahli tidak dapat membandingkan pasangan alternatif tertentu dalam hal preferensi. Dalam kasus ini, relasi teragregasi R pada himpunan Ω tidak akan berupa tatanan linier. Jelas, ini mengarah pada masalah penataan ulang linier alternatif dari Ω. Penataan ulang ini sering kali dimungkinkan dalam banyak hal.



Adanya tatanan linier berganda untuk tatanan parsial menunjukkan bahwa "tatanan intrinsik" dalam struktur tidak cukup untuk tatanan linier tunggal. Dengan demikian, menjadi perlu untuk memecahkan masalah penataan ulang linier dari pesanan parsial. Misalkan R adalah urutan parsial.



Teorema (Spielrein [5, 10]). Setiap urutan R pada himpunan dapat diperpanjang ke urutan linier pada himpunan ini.



Akibat wajar dari teorema Spielrein: penataan ulang linier apa pun dari subset$$$Ω_i ⊆ Ω$dapat diperpanjang hingga penataan ulang linier dari seluruh rangkaian Ω yang dipesan.



Jika X adalah himpunan bagian dalam Ω yang terdiri dari alternatif-alternatif yang tidak ada bandingannya, maka urutan linier apa pun dari X dapat diperluas ke urutan linier dari seluruh rangkaian Ω. Dalam hal ini, orde R dinyatakan dalam orde linier$$$R_i$...



Berdasarkan teorema Spielrein, pada himpunan Ω terdapat penomoran$$$x_1, x_2,...,x_n$elemen set ini. Penomoran himpunan berurutan elemen-n Ω, dengan relasi orde tertentu R, adalah pemetaan satu-satu dari himpunan Ω ke dalam dirinya sendiri, yaitu. di {1, 2, ..., n}, di mana elemen "lebih besar" sehubungan dengan urutan sesuai dengan nomor yang lebih besar [5]. Berikut ini, yang kami maksud dengan peringkat elemen adalah setiap penataan ulang linier dari urutan ini. Perhatikan bahwa penomoran set terurut mewakili dimensinya.



Dalam kasus umum, masalah menemukan urutan tambahan linier direduksi menjadi menemukan semua penomoran yang dapat diterima dari himpunan terurut parsial asli. Anda dapat menuliskan semua permutasi elemen dari Ω, yang akan ada n! dan untuk setiap periksa ketentuan bahwa elemen "lebih besar" sesuai dengan angka yang lebih besar. Namun, metode untuk menemukan semua urutan tambahan ini sangat melelahkan dan tidak efisien.



Untuk himpunan terurut Ω dengan urutan R tertentu di atasnya, elemen x 'dari himpunan Ω disebut maksimal jika tidak ada elemen x yang lebih besar, yaitu. jika x> x 'tidak berlaku untuk x є Ω. Elemen x '' disebut elemen terbesar dari himpunan terurut [Ω, R] jika lebih besar dari elemen x lainnya, mis. untuk setiap x є Ω, x ''> x [5].



Jika ada elemen terbesar dalam himpunan terurut, maka itu adalah elemen maksimum. Jika himpunan terurut memiliki satu elemen maksimum, maka itu akan menjadi elemen terbesar. Dalam himpunan berurutan sebagian, beberapa elemen maksimum diperbolehkan.



Untuk penomoran apa pun dari himpunan elemen n Ω, nomor N ditetapkan ke elemen maksimum. Semua penomoran himpunan Ω dapat diperoleh jika semua penomoran dari semua himpunan bagian yang diperoleh dari Ω diketahui dengan menghapus salah satu elemen maksimal tersebut. Teknik yang sama diterapkan untuk setiap subset [7]. Pertimbangkan algoritme untuk menyusun semua penomoran dari himpunan berurutan [Ω, R].



1. Sebuah grafik bantu [β, γR] dari himpunan terurut [Ω, R] dibangun, simpul yang memenuhi kondisi:



a) adalah himpunan bagian dari Ω;



b) untuk dua himpunan bagian X, Y є β, ini benar: (X, Y є γR) jika

himpunan bagian Y dapat diperoleh dari himpunan bagian X dengan membuang salah satu elemen maksimalnya (Gbr. A dan AA).





2. Untuk setiap subset satu elemen dari himpunan γR, tulis penomoran uniknya. Untuk mendapatkan semua penomoran dari subset X, perlu untuk menghitung semua subset yang berdekatan dengannya dan untuk setiap subset tersebut untuk melanjutkan semua penomorannya. Hasilnya, semua penomoran himpunan Ω akan diperoleh, mis. semua ekstensi linier orde R.



Masalahnya adalah mencari semua tatanan tambahan linier dari orde parsial, diagramnya ditunjukkan pada Gambar. J. Tidak ada informasi dalam hal ini, misalnya, apakah alternatif mendominasi$$$x_1$alternatif $$$_2$ atau sebaliknya, begitu pula untuk pasangan $$$(_3, _6);(_4, _5)$... Ini berarti bahwa A adalah pemesanan parsial. Ada banyak (22) opsi untuk membangun ke tatanan linier, yang diinginkan untuk dibawa ke tatanan tunggal. Hal ini dimungkinkan dengan keterlibatan informasi tambahan tentang alternatif yang diperoleh dari studi situasi yang terperinci.



1. Kami membuat grafik bantu [β, γR], dimulai dengan himpunan$$$(x_1, x_2, x_3,x_4, x_5, x_6)$dan di bawah. Angka di dekat busur grafik menunjukkan dengan menghapus elemen maksimum mana yang menjadi bagian tujuan panah ini diperoleh (Gbr. AA).



2. Kami membentuk tabel. AAA untuk mencari semua penomoran subset yang merupakan simpul dari grafik [β, γR]. Tabel diisi baris demi baris dari atas ke bawah. Setiap baris adalah penomoran subset yang dicatat di kolom kiri tabel (Tabel AAA).



3. Saat menyusun penomoran himpunan bagian X, yang terdiri dari k elemen, semua penomoran himpunan bagian Y є γR (x) yang direkam sebelumnya (untuk himpunan bagian sebelumnya) harus ditulis ulang dan berikan nomor ke elemen yang melengkapi Y ke X.





Blok terakhir (bawah) (Tabel AAA) berisi semua penomoran penataan ulang linier dari himpunan Ω. Representasi grafis dari penyusunan ulang ini ditunjukkan pada Gambar. AAA.





Angka: AAA. Representasi grafis dari preorder



Perlu dicatat bahwa ada 6 order linier pada satu set 6 elemen! atau 720, dan penataan ulang linier himpunan Ω dengan hubungan yang diberikan oleh grafik yang ditunjukkan pada Gambar. AA, totalnya 22. Ini juga cukup untuk mengambil keputusan.

Apakah ada peluang untuk mengurangi jumlah opsi seperti itu? Ya ada.

Untuk mengurangi jumlah susunan ulang linier, Anda perlu menggunakan informasi tambahan.

informasi tambahan

Misalkan [Ω, R] adalah relasi awal, maka informasi tambahan dapat direpresentasikan sebagai relasi δ pada himpunan Ω, di mana kondisi (x, y) є δ, yaitu, (x> y) diartikan sebagai pesan bahwa objek x mendominasi objek y;

rasio δ kemudian dapat dianggap sebagai kumpulan pesan informasi serupa tentang dominasi yang diberikan sebagai rasio biner δ, ada dua kemungkinan kasus saat menggunakan informasi tambahan:

1. grafik relasi R∪δ berisi kontur;
2. grafik relasi R∪δ tidak mengandung kontur.

Dalam kasus pertama, pengurutan linier dari himpunan Ω dengan rasio tertentu R∪δ di atasnya dilakukan dengan menggunakan algoritma peringkat yang telah

dipertimbangkan sebelumnya.



Dalam kasus kedua, pengurutan linier dari himpunan Ω dengan rasio R∪δ yang diberikan di atasnya dilakukan dengan menggunakan algoritma pengubahan urutan linier yang

dipertimbangkan di atas. Harus diperhatikan bahwa relasi R∪δ, yang tidak mengandung kontur, mungkin nontransitif dan, sebagai akibatnya, bukan urutan parsial.



Agar berhasil keluar dari situasi ini, perlu informasi tambahan δ dan rasio awal R diberikan dalam bentuk diagram Hasse, yaitu tanpa indikasi eksplisit dari tautan transitif. Nilai informasi tambahan akan ditentukan oleh berapa kali jumlah pesanan tambahan linier berkurang ketika digunakan.



Misalnya, jika menerima informasi itu $$$x_2$ mendominasi $$$x_4$, yaitu $$$x_2>x_4$, maka jumlah pemesanan ulang linier akan berkurang dari 22 menjadi 19, dan jika informasi sampai: $$$x_1>x_2$, maka jumlah praorder linier dibelah dua. Jadi, muncul pertanyaan: informasi apa yang paling berharga, atau jika Anda menambahkan berapa rasio δ, jumlah pemesanan tambahan akan berkurang paling banyak?



Untuk mengatasi masalah ini untuk semua pasang elemen$$$(x_i, x_j)$himpunan Ω, yang tidak termasuk dalam relasi R, di blok bawah Tabel. AAA, Anda perlu menghitung$$$n_{ij}$ - berapa kali jumlah itemnya $$$x_i$ lebih banyak nomor item $$$x_j$, yaitu elemen$$$x_i$ berdiri di atas elemen $$$x_j$ dan $$$n_{ji}$ - berapa kali item tersebut $$$x_j$ berdiri di atas elemen $$$x_i$...

Nilai informasi tambahan tentang hubungan pada pasangan ini akan semakin tinggi, semakin kecil perbedaannya$$$|n_{ij} - n_{ji}|$... Lebih banyak angka$$$n_{ij}, n_{ji}$akan sama dengan jumlah pemesanan ulang himpunan [Ω, R∩δ]. Untuk contoh yang dipertimbangkan, kami memperoleh ringkasan karakteristik representasi grafis dari pemesanan ulang





Dari analisis tabel dapat disimpulkan bahwa

informasi yang paling berguna adalah informasi tentang hubungan berpasangan$$$(x_1, x_2)$ dan $$$(x_4, x_5)$... Memperoleh informasi tambahan tentang relasi di salah satu pasangan ini mengarah ke separuh jumlah ordo tambahan linier.

Kesimpulan

Perumusan dan solusi ZPR hanya mungkin dalam situasi dengan banyak alternatif dan pilihan yang terbaik. Jika tidak ada pilihan, ikuti jalan yang Anda tempuh.

Keputusan yang dibuat oleh pengambil keputusan didasarkan pada preferensinya, yang digambarkan oleh relasi preferensi. Kehadiran relasi memungkinkan Anda membangun model matematika untuk penelitian. Ketidakpastian preferensi dihilangkan dengan menggunakan informasi tambahan yang bukan ahli.



Perhatian diberikan pada pertimbangan pengukuran dan perkiraan nilai indikator properti objek. Contoh berbagai skala yang sering diabaikan diberikan.

Formulasi ZPR yang mungkin dan informasi yang diperlukan untuk solusinya dicantumkan.



Menggunakan contoh numerik tertentu, penerapan metode aljabar untuk menyelesaikan ZPR ditampilkan, tanpa menggunakan sampel statistik dan metode pemrosesan empiris.

Metode ini didasarkan pada hasil teorema tentang kemungkinan perluasan tatanan parsial menjadi tatanan linier (sempurna).

Daftar literatur bekas

1. Teori Berge K. Graph dan aplikasinya. - M .: IL, 1962. - 320 hal.

2. Vaulin AE Matematika diskrit dalam masalah keamanan komputer. Bagian I. SPb.: VKA dinamai menurut A.F. Mozhaisky, 2015. - 219 hal.

3. Vaulin AE Matematika diskrit dalam masalah keamanan komputer Ch. II. SPb.: VKA dinamai A.F. Mozhaisky, 2017. - 151 hal.

4. Vaulin AE Metode penelitian kompleks komputasi informasi. Isu 2. - L .: VIKI mereka. A.F. Mozhaisky, 1984. - 129 hal.

5. Vaulin AE Metodologi dan metode analisis sistem komputasi informasi. Masalah 1.– L.: VIKI im. A.F. Mozhaisky, 1981. - 117 hal.

6. Vaulin AE Metode pemrosesan data digital: transformasi ortogonal diskrit. - SPb .: VIKKI mereka. A.F. Mozhaisky, 1993. - 106 hal.

7. Kuzmin VB Pembangunan solusi grup dalam ruang relasi biner yang tajam dan tidak jelas. - M .: Nauka, 1982. - 168 hal.

8. Makarov IM dkk. Teori pilihan dan pengambilan keputusan - Moskow: Fizmatlit, 1982. –328 hal. 52.

9. Rosen V.V. Tujuan - optimalitas - solusi. - M .: Radio dan komunikasi, 1982. - 169 hal.

10. Szpilraijn E Sur Textension de l'ordre partiel. - Fundam. math., 1930, vol. 16, hlm. 386-389.