На нашем сайте мы используем cookie для сбора информации технического характера и обрабатываем IP-адрес вашего местоположения. Продолжая использовать этот сайт, вы даете согласие на использование файлов cookies. Здесь вы можете узнать, как мы пользуемся файлами cookies.
Я согласен
логотип upread.ru

Реализация алгоритма Парето на C#


Закончил работу над интересным заказом по решению вопроса оптимального выбора. С разрешения заказчика публикую этот материал, основная часть практической работы.

Задача:

Разработать программу на основе алгоритма нахождения множества Парето. Язык: С++, С#, Python (можно любой из перечисленных, но предпочтителен С++). Число критериев m=4:
  1. Производительность технологического процесса (ТП) – Тшт.к. (время штучно-калькуляционное время) (минут);
  2. Количество операций ТП – N;
  3. Количество задействованного оборудования (станков) – S;
  4. Количество задействованной технологической оснастки – O.
Все критерии подлежат минимизации.


Сначала напомню про семь шагов алгоритма Парето:

Шаг 1. Положить P(Y) =Y , i =1, j = 2 . Тем самым образуется так называемое текущее множество парето-оптимальных векторов, которое в начале работы алгоритма совпадает с множеством Y , а в конце − составит искомое множество парето-оптимальных векторов. Алгоритм устроен таким образом, что искомое множество парето-оптимальных векторов получается из Y последовательным удалением заведомо неоптимальных векторов.
Шаг 2. Проверить выполнение неравенства y(i) ≥ y( j) . Если оно оказалось истинным, то перейти к Шагу 3. В противном случае перейти к Шагу 5.
Шаг 3. Удалить из текущего множества векторов P(Y) вектор y( j), так как он не является парето-оптимальным. Затем перейти к Шагу 4.
Шаг 4. Проверить выполнение неравенства j < N . Если оно имеет место, то положить j = j +1 и вернуться к Шагу 2. В противном случае – перейти к Шагу 7.
Шаг 5. Проверить справедливость неравенства y( j) ≥ y(i) . В том случае, когда оно является истинным, перейти к Шагу 6. В противном случае – вернуться к Шагу 4.
Шаг 6. Удалить из текущего множества векторов P(Y) вектор y(i) и перейти к Шагу 7.
Шаг 7. Проверить выполнение неравенства i < N -1. В случае истинности этого неравенства следует последовательно положить i = i +1 , а затем j = i +1. После этого необходимо вернуться к Шагу 2. В противном случае(т.е. когда i ≥ N -1) вычисления закончить. К этому моменту множество парето-оптимальных векторов построено полностью.
Источник: В.Д. Ногин "Принятие решений при многих критериях. Учебно-методическое пособие".

Основная задача заключается именно в том, чтобы запрограммировать данный алгоритм. Вот листинг программы:

 //шаг 1
int i = 1;
int j = 2;
int N = Convert.ToInt32(numericUpDown1.Value); //количество вариантов технологических процессов
Boolean flag = true;//флаг завершения процесса отбора вариантов
...
do
            {
                //шаг 2
                if (sr(myArr[j], myArr[i]))
                {

                    //шаг 3
                    mass[i] = 0;

                    //шаг 4
                    if (j < N)
                    {
                        j = j + 1;
                    }

                    else
                    {
                        //шаг 7

                        if (i < (N - 1))
                        {
                            i = i + 1;
                            j = i + 1;
                        }

                        else flag = false;
                    }
                }

                else
                {
                    //шаг 5 

                    if (sr(myArr[i], myArr[j]))
                    {
                        //шаг 6
                        mass[j] = 0;

                        //шаг 7

                        if (i < (N - 1))
                        {
                            i = i + 1;
                            j = i + 1;
                        }
                        else flag = false;
                    }
                    else
                        //шаг 4
                        if (j < N)
                        {
                            j = j + 1;
                        }

                        else
                        {
                            //шаг 7
                            if (i < (N - 1))
                            {
                                i = i + 1;
                                j = i + 1;
                            }
                            else flag = false;
                        }
                }
            }

while (flag);

Я выбрал цикл do...while, так как у цикла всегда будет хотя бы один проход. Здесь все шаги расписаны, все как по алгоритму. Метод sr() в коде сравнивает значения массивов – его требуется писать индивидуально под каждую задачу, зависит от числа критериев и от максимизации (минимизации).



На самом деле я считаю, что данная реализация – это не самый оптимальный способ решения данной задачи, хотя бы по количеству строк кода. Но это решение выбрано в связи с тем, что оно максимально приближено к алгоритму – как и требуется в задаче.

Итак, если вам требуется сделать практическую работу по программированию на C#, C++, Java, PHP, то вы смело можете обращаться ко мне. Пишите на почту, в скайп или обращайтесь сразу вконтакте.



тегизаметки, си шарп, алгоритмы





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




Java: цвет пикселя под курсором
Docx в png на C#


© upread.ru 2013-2019
При перепечатке активная ссылка на сайт обязательна.
Задать вопрос
письмо
Здравствуйте! Вы можете задать мне любой вопрос. Если не получается отправить сообщение через эту форму, то пишите на почу up777up@yandex.ru
Отправляя сообщение я подтверждаю, что ознакомлен и согласен с политикой конфиденциальности данного сайта.