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

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

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

Задача:

Разработать программу на основе алгоритма нахождения множества Парето. Язык: С++, С#, Python (можно любой из перечисленных, но предпочтителен С++). Число критериев m=4:

Производительность технологического процесса (ТП) – Тшт.к. (время штучно-калькуляционное время) (минут);

Количество операций ТП – N;

Количество задействованного оборудования (станков) – S;

Количество задействованной технологической оснастки – 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, то вы смело можете обращаться ко мне. Пишите на почту, в скайп или обращайтесь сразу вконтакте.

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

Мои услуги

Отправка POST-запроса на C# и получение ответа от сервера

Пошаговое руководство по верстке на вордпресс. Глава третья: меню, страницы и шапка

Периодическое копирование файлов в C++ с паузой