Симплекс-метод. Реализация

В этой статье рассматривается симплекс-метод, который применяется при решении задач линейного программирования (ЗЛП). Приводится алгоритм метода, а также его реализация на языке C#. Реализация представлена в конце статьи.

Определения

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

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

Оптимизация – задача нахождения минимума или максимума (экстремума) целевой функции.

Целевая функция – это функция нескольких переменных, подлежащая оптимизации в целях решения какой-либо оптимизационной задачи (например, задачи объемного планирования).

Алгоритм симплекс-метода

В начале исходную задачу линейного программирования приводят к каноническому виду, затем составляют симплекс-таблицу вида:

Симплекс-метод. Симплекс-таблица

где в столбце «базис» указываются базисные переменные, а в последней строке столбца «базис» пишется f(x). В столбец «B» записываются свободные члены ограничений bi и значение целевой функции (на 1-м этапе оно равно 0, т.е. никакой прибыли).

В столбцах xj для не базисных переменных указываются коэффициенты при не базисных переменных из ограничений задачи. В столбцах базисных переменных содержится только 0 или 1 на пересечении столбца с соответствующей строкой базисной переменной.

В последней строке -cj – это коэффициенты при переменных целевой функции взятые с противоположным знаком.

Симплекс-таблица составлена, теперь опишем сам симплекс-метод.

Шаг 1: Выполняется проверка полученного базисного плана на оптимальность по условию: если при каком-либо ДБР (допустимое базисное решение) в симплекс-таблице все коэффициенты строки f(x) (то есть -cj) не отрицательны, то данное ДБР оптимально, следовательно КОНЕЦ решения. В противном случае:

Шаг 2: Переход к новому базисному плану. Для этого из числа небазисных переменных с отрицательными значениями в последней строке (то есть -cj < 0) выбирается переменная, вводимая в базис – xk, это переменная которой соответствует наибольшая по модулю отрицательная оценка:

Симплекс-метод. Выбор ведущего столбца

Столбец, отвечающий переменной xk, называется главным, или ведущим. Элементы данного столбца обозначаются через aik.

Если окажется несколько одинаковых наибольших по модулю отрицательных оценок, то выбирается любая из соответственных переменных.

Шаг 3: Выбираем переменную r – переменную, которая выводится из базиса. Данная переменная находится из соотношения:

Симплекс-метод. Выбор ведущей строки

Строка таблицы, в которой получено наименьшее отношение элемента столбца «В» к соответствующему положительному элементу ведущего столбца, является ведущей, или главной.

Элементы главной строки обозначаются через arj. Выбранная переменная xr будет выводиться из базиса, то есть это исключаемая переменная.

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

Элемент, который стоит на пересечении главного столбца и строки называется главным, или ведущим, и обозначается ark.

Шаг 4: Для определения нового базисного плана проводится пересчет элементов симплекс-таблицы, и результаты заносятся в новую таблицу. Выбранные переменные среди базисных и не базисных, лежащих на главной строке и главном столбце, меняются местами.

Процедура пересчета элементов выполняется следующим образом:

а) элементы главной строки необходимо разделить на ведущий элемент:

Замена базиса. Пересчет ведущей строки

б) элементы полученной строки умножаются на -aik, и результаты складываются с i-той строкой, причем i ≠ k:

Замена базиса. Пересчет элементов

После определения новой симплекс-таблицы переходят к шагу 1.

Симплекс-метод. Реализация C#

Приводим программную реализацию симплекс-метода. Программа написана на языке программирования C#.

Важная информация! Пожалуйста прочтите!

Входные данные: симплекс-таблица без базисных переменных в столбцах. То есть таблица должна быть построена только по коэффициентам при переменных из ограничений задачи и целевой функции.

Формат входных данных: двумерный массив из элементов типа double.

Входные данные передаются в качестве аргумента, при создании экземпляра класса Simplex.

При вызове метода Calculate в качестве аргумента вы должны передать одномерный массив из элементов типа double, длиной в количество переменных в целевой функции. В этот массив будут записаны найденные значения неизвестных.

Выходные данные: метод Calculate возвращает ссылку на двумерный массив, содержащий решенную симплекс-таблицу. Кроме того решение будет занесено в массив, переданный в качестве аргумента в метод Calculate.

Формат выходных данных: двумерный массив из элементов типа double и одномерный массив из элементов типа double.

 

Скачать файл Simplex.cs

 

 

Приведем также пример программы, использующей реализованный выше симплекс-метод. Решим, для примера, задачу с такими ограничениями и целевой функцией:

Симплекс-метод. Пример решаемой задачи

Демонстрация работы симплекс-метода:

Использование реализации симплекс-метода при решении задачи

Симплекс-метод. Реализация
4.08 (81.54%) 13 votes

Поделиться в соц. сетях:

20 комментария(ев) к статье “Симплекс-метод. Реализация

  1. Миша

    А что нужно сделать, чтобы функции искали переменные для минимума, а не для максимума?

      1. Миша

        то есть сменить знаки коэффициентов при переменных? если так, то программа всё равно считает максимум

  2. Гость

    получается здесь не учитывается знак ограничения? и прога только для <=?

    1. admin Автор статьи

      Перед вводом данных в программу задачу нужно привести к каноническому виду.

      1. Xambey

        Что вы подразумеваете под привести задачу к каноническому виду? Канонический вид, это же вроде:
        1)инвертировать знаки у ф-ции F
        2)добавить доп.переменные, 1 если знак неравенства =, это канонический вид.

        У вас же таблица на входе имеет вид —-B—X1—X2 или я что-то не понимаю? Скажите пожалуйста, как именно нужно обработать систему неравенств?

        1. admin Автор статьи

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

          А в программу заносятся коэффициенты из приведённых ограничений:

          b1 a11 a12 …
          b2 a21 a22 …

          0 -c1 -c2 …

          При этом коэффициенты при базисных переменных (тех, которые вы добавляли, чтобы в ограничениях сделать равенства) НЕ нужно давать на вход программе!

  3. Nikita

    Доброго времени суток. Скажите, а как, например, после решения задачи в добавок к выводу переменных сделать еще вывод значения целевой функции?

    1. admin Автор статьи

      Перед вычислениями сохраните в отдельный массив значения коэффициентов при иксах: например в массив a.

      После того, как массив result будет получен, найдём значение целевой функции F:

      double F = 0;

      for(int i = 0; i < result.Length; i++)
      {
      F += a[i] * result[i];
      }

      1. Nikita

        Спасибо за ответ! Скажите, а как всё-же сделать так, чтобы выполнялось составление симплексной таблицы для решения задачи на определение минимального плана?

        1. admin Автор статьи

          Есть два пути.

          1) Самый простой: привести задачу минимизации (сами исходные данные) к задаче максимизации и использовать приведённый выше алгоритм. Как преобразовать написано здесь.

          2) Изменить приведённый алгоритм конкретно под задачу минимизации. При минимизации целевой функции ведущий столбец определяется по наибольшему значению в строке индексов. Читать про это подробнее.

  4. Алексей

    Админ, спасибо за реализацию, а какой будет алгоритм, если мне необходимо в одной задачи использовать ограничения ‘=>’ и ‘<=' Можете посоветовать русскую литературу по симплекс методу.

    1. admin Автор статьи

      Алгоритм будет точно такой же. Ведь система неравенств всё равно приводится к каноническому виду (в системе ограничений знаки становятся равенствами).

      В предыдущем моём комментарии есть ссылка, там как раз есть пример с разными знаками в системе неравенств.

      1. Михаил

        admin, помогите, пожалуйста, разобраться с вводом данных моей задачи. Заранее извиняюсь за столь глупый вопрос.
        Ограничения:
        2*y1+5*y2=1
        6*y1+1*y2=1
        Функция:
        1*y1+1*y2 –> max

  5. Мария

    Будет ли программа работать для более, чем двух переменных? Что нужно менять в коде, кроме входной матрицы?

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">