Метод Кондорсе та метод Копленда

Размещено на http://www.allbest.ru/

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Факультет комп'ютерних наук

Кафедра інтелектуальних інформаційних систем

КУРСОВА РОБОТА

"Метод Кондорсе та метод Копленда"

Дисципліна "Системний аналіз"

Напрям підготовки "Комп'ютерні науки"

Миколаїв-2017



Зміст

Вступ

Розділ І. Теоретичні відомості

1.1 Метод Кондорсе

1.2 Метод Копленда

Розділ ІІ. Суть завдання та опис програми

2.1 Суть завдання

2.2 Середовище розробки

2.3 Опис програми

Висновок

Перелік посилань

Додаток



Вступ

Із ускладненням виробничих процесів, розвитку науки, проникнення в таємниці функціонування і розвитку живих організмів з'явилися завдання, які не вирішуються за допомогою традиційних математичних методів і в яких все більше місце став займати власне процес постановки завдання, зросла роль евристичних методів, ускладнився експеримент, що доводить адекватність формальної математичної моделі.

Проблеми формування експертних груп, включаючи вимоги до експертів, розміри групи, питання тренування експертів, оцінки їх компетентності; підходи до оцінювання (ранжування, нормування, різні види упорядкування, в тому числі методи переваг, попарних порівнянь та ін.); методи обробки експертних оцінок; способи визначення узгодженості думок експертів, достовірності експертних оцінок (у тому числі статистичні методи оцінки дисперсії, оцінки ймовірності для заданого діапазону змін оцінок, оцінки рангової кореляції Кендалла, Спірмена, коефіцієнта конкордації і т.п.) і методи підвищення узгодженості оцінок шляхом відповідних способів обробки результатів експертного опитування.

Розглянуті вище недоліки експертних оцінок привели до необхідності створення методів, що підвищують об'єктивність отримання оцінок шляхом розчленування великий первісної невизначеності проблеми, пропонованої експерту для оцінки, на більш дрібні, краще піддаються осмисленню. Кінцевою метою системного аналізу є вирішення проблемної ситуації, що виникла перед об'єктом проведеного системного дослідження (зазвичай це конкретна організація, колектив, підприємство, окремий регіон, соціальна структура і т.п.). Системний аналіз займається вивченням проблемної ситуації, з'ясуванням її причин, виробленням варіантів її усунення, прийняттям рішення і організацією подальшого функціонування системи, дозволенням проблемної ситуації. Початковим етапом будь-якого системного дослідження є вивчення об'єкта проведеного системного аналізу з подальшою його формалізацією.

Важливе місце в процедурах системного аналізу займає проблема ухвалення рішення. Як особливості завдань, постають перед системними аналітиками, необхідно відзначити вимога оптимальності прийнятих рішень. В даний час доводиться вирішувати завдання оптимального управління складними системами, оптимального проектування систем, що включають в себе велику кількість елементів і підсистем. Розвиток техніки досягло такого рівня, при якому створення працездатної конструкції саме по собі вже не завжди задовольняє провідні галузі промисловості. Необхідно в ході проектування забезпечити найкращі показники по ряду характеристик нових виробів, наприклад, домогтися максимальної швидкодії, мінімальних габаритів, вартості і т.п. при збереженні всіх інших вимог в заданих межах.

Перед нами була поставлена задача яку найбільш бажаний варіант якої ми повинні знайти методом Кондросе та Копленда.

Кондорсе визначив правило, за яким вводиться операція порівняння обраних альтернатив.

Згідно з принципом Кондорсе, для визначення дійсної волі більшості необхідно, щоб кожен голосуючий проранжував всіх кандидатів у порядку їх переваги. Після цього для вибраної пари кандидатів визначається, скільки голосуючих воліє одного кандидата іншому. Таким чином можна порівняти будь-яких кандидатів.

Метод Копленда або метод попарної агрегації Копленда це метод Кондорсе, в якому кандидати відсортовані за кількістю попарних перемог, мінус число попарних поразок.

Прихильники стверджують, що цей метод легко зрозуміти. У багатьох кругових турнірах, переможець є конкурентом з найбільшою кількістю перемог. Це також легко вирахувати.

Коли немає переможця Кондорсе (тобто за наявності декількох елементів набору), цей метод часто призводить до зв'язків.

Критики стверджують, що він також ставить занадто багато уваги від кількості попарно перемог і поразок, а не їх величини.

Основною задачею було вибір найкращої альтернативи за допомогою цих двох методів та реалізація програмного продукту, який був би зручним як для експертів, як для спеціалістів різних напрямків, так і для пересічного користувача.

Метою є знаходження найбільш оптимального шляху для вирішення поставленої задачі.

кондорсе копленд програмний середовище



Розділ І. Теоретичні відомості

1.1 Метод Кондорсе

Парадокс Кондорсе -- відомий парадокс теорії суспільного вибору, вперше описаний Кондорсе у 1785 році.

Полягає в тому, що правило простої більшості не в змозі забезпечити транзитивність бінарного відношення громадської переваги серед варіантів, що обираються. В силу нетранзитивності, результат може залежати від порядку голосування, що дає можливість маніпуляції вибором більшості.

Узагальнений теоремою «про неможливість» Ерроу в 1951 року.

На практиці ідея про необхідність ранжування кандидатів реалізована в голосуванні за методом Шульце.

Кондорсе визначив правило, за яким вводиться операція порівняння альтернатив, що обираються.

Згідно з принципом Кондорсе, для визначення дійсного волевиявлення більшості, необхідно, щоб кожен голосуючий проранжував всіх кандидатів у порядку їх переваги. Після цього для вибраної пари кандидатів визначається, скільки голосуючих воліє одного кандидата іншому. Таким чином можна порівняти будь-яких кандидатів.

Наведемо чисельний приклад з роботи Кондорсе.

Введемо для стислості позначення: означатиме, що голосуючий воліє кандидата A кандидату B, а кандидата B -- кандидату С.

Нехай 60 голосуючих віддали наступні переваги:

23 особи:

19 осіб:

16 осіб:

2 особи:

При порівнянні A з B маємо: 23 + 2 = 25 осіб за те, що і 19 + 16 = 35 осіб за те, що .

За принципом Кондорсе думка більшості полягає в тому, що В краще А.

Порівнюючи А і С, будемо мати: 23 особи за і 37 осіб за . Звідси, за Кондорсе, робимо висновок, що більшість воліє кандидата C кандидату А. Аналогічно (19 осіб за , 41 людина за ) C бажаніший, ніж B.

Таким чином, за Кондорсе воля більшості виражається у вигляді трьох суджень: ; ; , які можна об'єднати в одне відношення переваги і якщо необхідно вибрати одного з кандидатів, то, згідно з принципом Кондорсе, слід віддати перевагу кандидата С.

В іншому прикладі, розглянутому Кондорсе:

1 особа:

1 особа:

1 особа:

за підсумками голосування виділяються три твердження: , , . Але разом ці твердження суперечливі. У цьому й полягає парадокс (ефект) Кондорсе (або парадокс голосування). У цьому випадку виявляється неможливим прийняти якесь узгоджене рішення і визначити волю більшості. Принцип де Кондорсе полягає в наступному: кандидат, який перемагає при порівнянні один на один з будь-яким з інших кандидатів, є переможцем на виборах.

1.2 Метод Копленда

Метод Копленда. Кандидату нараховується +1, якщо більшість вважає його кращим за іншого кандидата, -1, якщо гірше, та 0 при рівності кандидатів. Рейтинг сумує всі оцінки при порівнянні кандидата з іншими кандидатами. Рейтинг кандидати дорівнює різниці між числом кандидатів кращого за даного і числом кандидатів гіршого за даного на думку експертів або по значенню об`єктивних показників. Метод рекомендується використовувати, коли необхідно побудувати впорядкування на думку більшості та взнати положення кожного кандидата, в порівнянні з скількома кандидатами, на думку більшості він виграє чи програє. Обирається кандидат, названий переможцем за Коплендом, із найвищою з таких оцінок.

Нехай дано наступний профіль для 13 виборців і 3-х кандидатів:

Таблиця 1 - Розподіл кандидатів, щодо вподобань виборців

4	2	2	3
A B С	B A С	A С B	С A B

У кожному стовпці кандидати розташовані у порядку зменшення їх значущості для кожної групи виборців. Тобто, для першого стовпця можна визначити переваги наступним чином: група виборців, що складається з однієї особи, вважає кандидата A найкращим. На другому місці вони ставлять кандидата B, на третьому місці С і т.д.

Продемонструємо розв'язок за правилом Копленда. Визначаємо оцінку Копленда.

Кандидат A є кращим за B для 4+2+3 виборців, а для 2-х виборців кандидат B є кращим за A. Визначимо такі переваги для кожного кандидата, порівняємо його з усіма іншими.

AB - 9 AC - 8	BA - 2 CA - 3	BC - 6	CB - 2

Визначимо оцінку Копленда для кожного кандидата. Кандидат A є кращим за B (додаємо +1); він також є кращим за C (додаємо два рази +1). Отже, оцінка Копленда для A рівна 2.

Знайдемо оцінку для інших кандидатів.

A=+1+1=2

B=-1+1=0

C=-1-1=-2

Серед отриманих оцінок визначаємо максимальну. Як бачимо, вона дорівнює 2 і належить кандидату A. Отже, A - переможець Копленда.



Розділ ІІ. Суть завдання та опис програми

2.1 Суть завдання

Будинку управлінню виділені гроші для підвищення безпеки мешканців. Для вибору кращого варіанту зібрана група експертів. Можливі альтернативи:

1. Поставити кодові двері в під'їзди;

2. Поставити залізні двері при вході на сходову площадку;

3. Поставити в квартирах панорамні зіниці;

4. Підключити квартири до сигналізації;

Ранжування альтернатив експертами виконайте самостійно. Визначити найбільш бажаний варіант методом Кондорсе і Копленда. Розробити програмне забезпечення. Порівняти результати оцінювання за двома методами. Визначити найкращу альтернативу на основі експертного оцінювання за двома методами.

2.2 Середовище розробки

Для того, щоб реалізувати поставлені переді мною завдання в повному обсязі, я обрала мову програмування Java. Так як ця мова має велику кількість переваг перед іншими мовами, це дає можливість розв'язати практично будь-які задачі.

Основні переваги Java:

мова Java є простою для вивчення (програми на Java, в порівнянні з програмами на інших мовах, простіше писати, компілювати, налагоджувати і вивчати);

Java - це об'єктно-орієнтована мова (це дозволяє створювати модульні програми, вихідний код яких може використовуватися багато разів);

мова Java не залежить від платформи (програми на Java не залежать від платформи, тож їх можна запускати в різних системах).

Основною задачею було - максимально оптимізувати продукт та зробити його зручним для користування, як для аналітиків, так і для експертних груп. Тож я обрала середу розробки Netbeans, візуальні засоби якої мають повний ряд компонентів, які забезпечують реалізацію завдання, а саме налагодження користувацького інтерфейсу. До того ж, саме Netbeans є більш зрозумілим та інтуїтивним.

2.3 Опис програми

Пошук найкращої альтернативи здійснюється двома методами, а саме метод Кондорсе та метод простої більшості. Вхідні дані вводяться програми шляхом, тож виникає необхідність вводити дані користувачеві, тобто програма буде вирішувати конкретну задачу (рис. 2.1).

Рис. 2.1. Головне вікно програми

Головне вікно програми містить дві кнопки: перша кнопка виконує знаходження найкращої альтернативи методом Кондорсе, друга - методом Копланда.

Інформація містить альтернативи, тобто постановка задачі.

При натисненні на кнопку «Метод Кондорсе» з'являється інформація з розрахунками найкращої альтернативи методом Кондорсе, відповідно (рис. 2.2).

Рис. 2.2. Метод Кондорсе

Інформація містить кількість експертів та цілей, перелік альтернатив, оцінки вподобань, матрицю після оцінювання попарних вподобань та найкращу альтернативу.

На першому етапі, ми проводимо ранжування альтернатив, потім знаходимо оцінки mik, що характеризують перевагу альтернатив у парних перевагах (тобто це наша матриця попарних вподобань). Ці підрахунки здійснюються за допомогою функції seachBestAlternative.

Завершальний етап - це перевірка згідно з принципом Кондорсе: найкращою є альтернатива ai, якщо mij ? mji для всіх k, що не дорівнюють i. Отже, в результаті ми отримуємо найкращу альтернативу.

При натисненні на кнопку «Метод Кондросе» з'являється ще одне вікно, де виконуються розрахунки найкращої альтернативи цієї задачі ще одним методом (рис. 2.3).



Рис. 2.3. Метод Копленда

Інформація містить кількість експертів та цілей, перелік альтернатив, модифіковані оцінки експертів, сумарні оцінки переваг, ваги цілей та найкращу альтернативу.

Спочатку, ми знаходимо оцінки експертів. Далі, ми підраховуємо сумарні оцінки переваг. Ці підрахунки здійснюються за допомогою функції getWin.

На наступному кроці необхідно знайти максимальну оцінку. Для цього визначаємо оцінку Копленда для кожного кандидата. В результаті отримуємо найкращу альтернативу (найкраща альтернатива - альтернатива з найбільшою оцінкою).

Класи програми
public class Visual_Frame extends javax.swing.JFrame	Головне вікно програми
import javax.swing.JLabel;	Елемент для виведення результатів
public class Main	Клас з основними даними для розрахунків
public class Condorcet_method extends Main	Клас для розрахунків методом Кондорсе
public class Copeland_method extends Condorcet_method	Клас для розрахунків методом Копленда



Висновок

Курсова робота була присвячена огляду методів голосування більшістю голосів. Була проведена порівняльна характеристика кожного з методів та були визначені їх переваги та недоліки.

В результаті аналізу даного ранжування експертами альтернатив, і пошуку оптимальної методами Копленда і Кондорсе, було виявлено, що альтернативою-переможцем став варіант 1. На цей варіант вказали обидва методи.

З'ясували , що метод Копленда - це метод Кондорсе, в якому кандидати відсортовані за кількістю попарних перемог, мінус число попарних поразок.

Реалізовані методи були на мові програмування Java. Методи виявилися достатньо простими у реалізації, але дуже ефективними.

Таким чином, в результаті виконання роботи, ми ознайомились із системним підходом до аналізу складних організаційно-технічних систем, освоїли методи формалізованого опису складних систем, методи експертного оцінювання, прийняття рішень та оцінили ефективність їх застосування; закріпили знання і розвиток практичних навичок аналізу систем різного класу.



Перелік посилань

1. Чернишов В. Н., «Теорія систем і системний аналіз».- Тамбов, ТГТУ, 2008. - 93с.

2. Миркин Б. П. Проблема групового вибору . - Москва , Наука , 1974 .

3. Антонов А. В. "Системний аналіз" , М. - 2004р.

4. Макаров І. М. Теорія вибору та прийняття рішень . - М.: Наука , 1987 . - 350 с.

5. Кузнєцов А. В. , Сакович В.А. , Холод Н.І. "Вища математика . Математичне програмування ", Мінськ , Вишейшая школа , 2001р.

6. Красс М. С. , Чуприна Б.П. "Основи математики і її застосування в економічній освіті " , Видавництво " Дело" , Москва, 2001р.

7. Теорія прогнозування та прийняття рішень . М: 1989. - 160 с.

8. Гайдес, М. Общая теория систем (системы и системный анализ) [Текст] / М. Гайденс. -- Винница: Глобус-пресс, 2005. -- 201 с.

9. Лекції колективних рішень. - Режим доступу : URL : http://ofap.ulstu.ru/vt/tpr/lec11.html#1. - Загол. з екрану.



Додаток А

public class Main {

protected HashMap<Integer,String> MapWithGoals=new HashMap();

protected HashMap<Integer,String> buildGoalMap(){

HashMap<Integer,String> tmpMap=new HashMap();

tmpMap.put(1, " Поставити кодові двері в під'їзди ");

tmpMap.put(2, " Поставити залізні двері при вході на сходову площадку");

tmpMap.put(3, " Поставити в квартирах панорамні зіниці ");

tmpMap.put(4, " Підключити квартири до сигналізації ");

return tmpMap;

}

public Main(){

this.MapWithGoals = buildGoalMap();

}

public static void main(String[] args) {

// TODO code application logic here

}

}

public class Copeland_method extends Condorcet_method{

private int[] koplandPoints;

protected int[][] matrixOfPreference = new int[amountOfGoals][amountOfGoals];

protected int win;

public Copeland_method(){

this.koplandPoints = new int[amountOfGoals];

Condorcet_method k = new Condorcet_method();

this.matrixOfPreference = k.preference;

this.koplandPoints = getKoplandPoints(this.matrixOfPreference);

this.win = getWinner(koplandPoints);

}

public int[] getKoplandPoints(int[][] matrix){

for(int i=0;i<matrix.length;i++){

for(int j=0;j<matrix[i].length;j++){

if(matrix[i][j]>matrix[j][i]&&i!=j){

this.koplandPoints[i]+=1;

this.koplandPoints[j]-=1;

}else if(matrix[i][j]<matrix[j][i]&&i!=j){

this.koplandPoints[i]-=1;

this.koplandPoints[j]+=1;

}

}

}

return this.koplandPoints;

}

public int getWinner(int[] kopld){

int max=0,index=0;

for(int i=0;i<kopld.length;i++){

if(max<kopld[i]){

max=kopld[i];

index=i;

}

}

return index;

}

public int[] getKoplandPoints() {

return koplandPoints;

}

public int[][] getMatrixOfPreference() {

return matrixOfPreference;

}

public static void main(String[] args) {

}

public int getWin() {

return win;

}

public void solve(){

listModelForVisualFrame.addElement("Результат роботи программи: ");

listModelForVisualFrame.addElement("Кількість експертів дорівнює " + this.amountOfExpert);

listModelForVisualFrame.addElement("Кількість цілей дорівнює " + this.amountOfGoals);

listModelForVisualFrame.addElement("Список можливих цілей: ");

MapWithGoals.entrySet().stream().forEach((entry) -> {

listModelForVisualFrame.addElement(" "+entry.getKey().toString() + ". " + entry.getValue());

});

listModelForVisualFrame.addElement("Оцінки експертів: ");

StringBuilder strBld;

strBld=new StringBuilder();

listModelForVisualFrame.addElement(strBld.toString());

listModelForVisualFrame.addElement(" Z1 Z2 Z3 Z4 ");

int e=1;

for(int[] x:experti){

strBld=new StringBuilder((e<10)?" E"+e+++": ":"E"+e+++": ");

for(int y:x){

strBld.append(y).append(" ");

}

listModelForVisualFrame.addElement(strBld.toString());

}

int i=0;

strBld=new StringBuilder();

listModelForVisualFrame.addElement("Попарні переваги: ");

strBld.append(" А1 А2 А3 А4 ");

listModelForVisualFrame.addElement(strBld.toString());

for(int[] x:this.matrixOfPreference){

strBld=new StringBuilder();

strBld.append("A").append(String.valueOf(i+1));

for(int y:x){

strBld.append("| ").append(y).append(" |");

}

listModelForVisualFrame.addElement(strBld.toString());

i++;

}

listModelForVisualFrame.addElement("Оцінки по Копланду: ");

strBld=new StringBuilder();

for(int x:koplandPoints){

strBld.append(x).append(" ");

}

listModelForVisualFrame.addElement(strBld.toString());

this.best = getWinner(koplandPoints) + 1;

System.out.println(this.best);

listModelForVisualFrame.addElement("Кращий варіант вибрати: "+this.MapWithGoals.get(this.best));

}

}

public class Condorcet_method extends Main {

int[][] preference=new int[amountOfGoals][amountOfGoals];

int best;

DefaultListModel<String> listModelForVisualFrame=new DefaultListModel();

public Condorcet_method() {

this.preference = doRanjeringForPreferenceMap(experti);

}

private int[][] doRanjeringForPreferenceMap(int[][] mas){

int[][] p=new int[amountOfGoals][amountOfExpert];

for(int k=0;k<amountOfGoals;k++){

for(int i=0;i<amountOfExpert;i++){

for(int j=0;j<amountOfGoals;j++){

if(mas[i][j]==(k+1)) p[k][i]=j+1;

}

}

}

int[][] m=new int[4][4];

for(int k=0;k<amountOfGoals;k++){

for(int i=0;i<amountOfGoals;i++){

for(int j=0;j<amountOfExpert;j++){

if(p[k][j]<p[i][j]&&i!=k) m[k][i]++;

}

}

}

return m;

}

private int seachBestAlternative(int[][] m){

int i,j,count=0,result;

for(i=0;i<m.length;i++){

for(j=0;j<m[i].length;j++){

if(m[i][j]>=m[j][i]&&i!=j) count++;

if (j==3){

if (count==3){

result=i+1;

return result;

}else count=0;

}

}

}

return 0;

}

public void solve(){

listModelForVisualFrame.addElement("Результат: ");

listModelForVisualFrame.addElement("Кількість експертів дорівнює " + this.amountOfExpert);

listModelForVisualFrame.addElement("Кількість цілей дорівнює " + this.amountOfGoals);

listModelForVisualFrame.addElement("Список можливих цілей: ");

MapWithGoals.entrySet().stream().forEach((entry) -> {

listModelForVisualFrame.addElement(" "+entry.getKey().toString() + ". " + entry.getValue());

});

listModelForVisualFrame.addElement("Оцінки експертів: ");

StringBuilder strBld;

strBld=new StringBuilder();

listModelForVisualFrame.addElement(strBld.toString());

listModelForVisualFrame.addElement(" Z1 Z2 Z3 Z4 ");

int e=1;

for(int[] x:experti){

strBld=new StringBuilder((e<10)?" E"+e+++": ":"E"+e+++": ");

for(int y:x){

strBld.append(y).append(" ");

}

listModelForVisualFrame.addElement(strBld.toString());

}

int i=0;

strBld=new StringBuilder();

listModelForVisualFrame.addElement("Попарні переваги: ");

strBld.append(" А1 А2 А3 А4 ");

listModelForVisualFrame.addElement(strBld.toString());

for(int[] x:preference){

strBld=new StringBuilder();

strBld.append("A").append(String.valueOf(i+1));

for(int y:x){

strBld.append("| ").append(y).append(" |");

}

listModelForVisualFrame.addElement(strBld.toString());

i++;

}

this.best = seachBestAlternative(preference);

System.out.println(this.best);

listModelForVisualFrame.addElement("Кращий варіант вибрати: "+this.MapWithGoals.get(this.best));

}

public DefaultListModel<String> getListModelForVisualFrame() {

return listModelForVisualFrame;

}

}

Размещено на Allbest.ru