Диссертация (1137447), страница 24

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 24)

(A.47)512512Оказывается, что любая функция полезности, соответствующая выбору 1 = + 3 принимает значения строго большие, чем любая извозможных при тех же значениях i и n функций полезности, соответ-176ствующих решению 1 = + 2. Расчитанные разницы между решениями + 3 и + 2 приведены в таблице, причем приведенные в таблицевыражения положительны при всех > 1, > 0. Следовательно, решение 1 = + 3 всегда лучше решения 1 = + 2.Таблица A.1: Сравнение решений + 3 и + 2 на шаге 1111222324222121 576+192+10 +116 −26725621 1102−509+442+122 +960210242-1 52 +852 +15+45−1212821 1102−509+442+122 +96021024 221 10 +1072 +156+468−15025621 992−328+368+62 +33325122Сравнение решений 1 = + 3 с решениями 1 ≥ + 4Сравним решение 1 = + 3 с решением 1 = + 4.

Для того, чтобысравнить последствия этих решений, надо рассмотреть все возможныекомбинации решений на последующих шагах. Различные решения напоследующих шагах возникают при разных сочетаниях значений параметров i и n. Перечислим функции полезности для различных ре-177шения после 1 = + 4.11545−1 2( + 5)2 + ( + 3)2 +( + 2 +) +1664256135−2 2405+( + 2 +) +( + 1)2 , (A.48)1024102411510521 ( + 4, ) = ( + 5)2 +( + 4)2 +( + 3)2 +16128512315−1 2945+( + 2 +) +( + 1)2 , (A.49)2048204811545−1 231 ( + 4, ) = ( + 5)2 + ( + 3)2 +( + 2 +) +1664256135135+( + 2)2 +( + 1)2 , (A.50)512512151051( + 4)2 +( + 3)2 +41 ( + 4, ) = ( + 5)2 +16128512315315+( + 2)2 +( + 1)2 ,(A.51)1024102411 ( + 4, ) =Можно было бы рассмотреть отдельно каждый случай, однако мыобобщим анализ, как и в предыдущем пункте, с помощью таблицы.

Встолбцах таблицы перечислены возможные решения при 1 = + 3, встроках - возможные решения при 1 = + 4. При этом будут рассмотрены только те пары решений, которые могут быть оптимальными нашаге 2 при одинаковых значениях параметров i и n. Разница между2 и 3 будет стоять в ячейках таблицы в тех случаях, когда решения могут быть оптимальными при одинаковых значениях параметровi и n. В некоторых случаях неравенство Δ > 0 выполняется не привсех n > 1.

Рассмотрим эти случаи подробнее: Ячейка 4-4. Два варианта решения, сравниваемые в ячейке 4-4, могут быть выбраны при√ < 21 + 32 + 12 2 + 6 + 7. При исследовании выражения Δ44 оказывается, что 42 < 43 при ≤4(28+112+7842 +5502+11921).110+89При сопо-ставлении этих границ оказывается, что при = 2;3 ≤ ≤ 5, а такжепри = 3, 4, 5 = 3 для абитуриента выгоднее будет сделать выбор1781 = + 4, 1 = на первом шаге.

Опустим выкладки для остальныхсомнительных ячеек - во всех остальных случаях выбор 1 = + 3всегда будет выгоднее выбора 1 = + 4 с учетом огранчиений на и.179Приложение BИсходные коды разработанногопрограммного комплексаB.0.1Устранение безразличий в предпочтениях агентовList<Dictionary<int, double>> eliminateIncomparability(List<Dictionary<int, double>> ValuesNames,bool men_choose){double E;if (men_choose)E = Emen;elseE = Ewomen;List<Dictionary<int, double>> newValuesNames = new List<Dictionary<int, double>>();Random gen = new Random();foreach (Dictionary<int, double> dictionary in ValuesNames){Dictionary<int, double> newDictionary = new Dictionary<int, double>();List<int> incomparableKeys = new List<int>();List<double> incomparableValues = new List<double>();while (dictionary.Count != 0){double target = dictionary.ElementAt(0).Value;foreach (var item in dictionary){double diff = target - item.Value;if (diff <= E){incomparableKeys.Add(item.Key);incomparableValues.Add(item.Value);180}}int index = gen.Next(0, incomparableKeys.Count);newDictionary.Add(incomparableKeys[index], incomparableValues[index]);dictionary.Remove(incomparableKeys[index]);incomparableKeys.Clear();incomparableValues.Clear();}newValuesNames.Add(newDictionary);}return newValuesNames;}B.0.2Генерация предпочтений случайным образомprivate void generate_preferences(object sender, EventArgs e){textBox1.Visible = false;textBox2.Visible = false;button1.Visible = false;label1.Visible = false;label2.Visible = false;label3.Visible = true;label4.Visible = true;label5.Visible = true;label6.Visible = true;label7.Visible = true;label8.Visible = true;label9.Visible = true;label10.Visible = true;comboBox1.Visible = true;button2.Visible = true;button3.Visible = false;men_quantity = 5;women_quantity = 5;int m_coordinate_name_text = 144;int m_coordinate_name_label = 167;Random gen = new Random(DateTime.Now.Millisecond);List<int> indexList=new List<int>();for (int i = 0; i < men_quantity; i++){181m_NameTextBoxes.Add(new TextBox());m_NameTextBoxes[i].Font = new Font(textBox1.Font.FontFamily.Name, 12);m_NameTextBoxes[i].Size = new System.Drawing.Size(83, 29);m_NameTextBoxes[i].Location = new System.Drawing.Point(63, (m_coordinate_name_text));m_NameTextBoxes[i].Text = men_pool[i].ToString();indexList.Clear();string pref = "";Dictionary<int, double> ValuesNames = new Dictionary<int, double>();for (int j= 0; j < women_pool.Length; j++){double q = (gen.Next(0, 100));q /= 100;if (q >= bound){ValuesNames.Add(women_pool[j], q);}}ValuesNames = ValuesNames.OrderByDescending(x =>x.Value).ToDictionary(x => x.Key, x => x.Value);foreach (int key in ValuesNames.Keys){pref += key + ", ";}menValuesNamesCopy.Add(ValuesNames);menValuesNames.Add(ValuesNames);m_PrefTextBoxes.Add(new TextBox());m_PrefTextBoxes[i].Font = new Font(textBox1.Font.FontFamily.Name, 12);m_PrefTextBoxes[i].Size = new System.Drawing.Size(250, 29);m_PrefTextBoxes[i].Location = new System.Drawing.Point(188, (m_coordinate_name_text));m_PrefTextBoxes[i].Text = pref;m_coordinate_name_text += 30;m_coordinate_name_label += 30;this.Controls.Add(m_NameTextBoxes[i]);this.Controls.Add(m_PrefTextBoxes[i]);}int w_coordinate_name_text = 144;int w_coordinate_name_label = 167;for (int i = 0; i < women_quantity; i++){w_NameTextBoxes.Add(new TextBox());w_NameTextBoxes[i].Font = new Font(textBox1.Font.FontFamily.Name, 12);w_NameTextBoxes[i].Size = new System.Drawing.Size(83, 29);182w_NameTextBoxes[i].Location = new System.Drawing.Point(524, (w_coordinate_name_text));w_NameTextBoxes[i].Text = women_pool[i].ToString();indexList.Clear();string pref = "";Dictionary<int, double> ValuesNames = new Dictionary<int, double>();for (int j = 0; j < men_pool.Length; j++){double q = (gen.Next(0, 100));q /= 100;if (q >= bound){ValuesNames.Add(men_pool[j], q);}}ValuesNames = ValuesNames.OrderByDescending(x =>x.Value).ToDictionary(x => x.Key, x => x.Value);foreach (int key in ValuesNames.Keys){pref += key + ", ";}womenValuesNamesCopy.Add(ValuesNames);womenValuesNames.Add(ValuesNames);w_PrefTextBoxes.Add(new TextBox());w_PrefTextBoxes[i].Font = new Font(textBox1.Font.FontFamily.Name, 12);w_PrefTextBoxes[i].Size = new System.Drawing.Size(250, 29);w_PrefTextBoxes[i].Location = new System.Drawing.Point(641, (w_coordinate_name_text));w_PrefTextBoxes[i].Text = pref;w_coordinate_name_text += 30;w_coordinate_name_label += 30;this.Controls.Add(w_NameTextBoxes[i]);this.Controls.Add(w_PrefTextBoxes[i]);}}B.0.3Модуль проверки эффективности паросочетания183Boolean checkEfficiency(List<Dictionary<int,double>> checkMenValuesNames, List<Dictionary<int,double>> c{int[,] SICMatrix = new int[women_text_names.Length, women_text_names.Length];int[,] matr = new int[women_text_names.Length, women_text_names.Length];int i,j;double eprop, eacc, current, best;List<Dictionary<int, double>> ProposingValuesNames;List<Dictionary<int, double>> AcceptingValuesNames;Dictionary<int, double> copy;int[] prop_names,accept_names;// Инициализируем переменныеcurrent = 0;if(menprop==true){ProposingValuesNames = checkMenValuesNames;AcceptingValuesNames = checkWomenValuesNames;eprop = Emen;eacc = Ewomen;prop_names = men_name;accept_names = women_name;}else{ProposingValuesNames = checkWomenValuesNames;AcceptingValuesNames = checkMenValuesNames;eprop=Ewomen;eacc=Emen;prop_names = women_name;accept_names = men_name;}for(i = 0; i < ProposingValuesNames.Count; i++){//Копируем предпочтения рассматриваемого игрокаcopy = new Dictionary<int, double>();foreach(var itemcopy in ProposingValuesNames[i]){copy.Add(itemcopy.Key,itemcopy.Value);184}//Сохраняем ценность текущего партнераfor (j = 0; j < matching.Length; j++){if (i == matching[j]){current = ProposingValuesNames[i][j];break;}}// Удаляем всех, кто не предпочтительнее текущего патнераforeach(var item in copy){if (item.Value < current + eprop){ProposingValuesNames[i].Remove(item.Key);}}}//Удаляем всех, кто не предпочитает x текущему партнеру, из списка xfor(i = 0;i < AcceptingValuesNames.Count; i++){j = 0;foreach(var dictionary in ProposingValuesNames){if(!dictionary.Keys.Contains(i))AcceptingValuesNames[i].Remove(j);j++;}best = 0;//Найдем наибольшую ценность среди тех, кто принадлежит множеству Сif(AcceptingValuesNames[i].Count > 0) best = AcceptingValuesNames[i].Values.Max();//Копируем предпочтения рассматриваемого игрокаcopy = new Dictionary<int, double>();foreach (var itemcopy in AcceptingValuesNames[i]){185copy.Add(itemcopy.Key, itemcopy.Value);}//Удалим тех, кто доминируется объектами из С, то есть построим множество Dforeach(var item in copy){if (item.Value < best + eacc)AcceptingValuesNames[i].Remove(item.Key);// Строим матрицу для SIC (Stable Improvement Cycle)elseSICMatrix[item.Key, i] = 1;}}for(int k=0;k<accept_names.Length;k++){for(i=0;i<accept_names.Length;i++){for(j=0;j<accept_names.Length;j++){for(int q=0;q<accept_names.Length;q++){matr[i,j]+=SICMatrix[i,q]*SICMatrix[q,j];}}}for (i = 0; i < accept_names.Length; i++){if (matr[i, i] != 0) return true;}}return false;}186.

Характеристики

Список файлов диссертации