Краткое описание

Обязательно прочитайте пункт проблемы

Программка, которая применяет симплекс, двойственный симплекс метод, метод отсечений Гомори и целочисленный метод отсечений к задачам линейного программирования.

В классе рациональных чисел используется BigInt написанный Faheel'ем. Огромное ему спасибо.

Как использовать

1. склоинруйте репозиторий

   git clone https://github.com/nol0n/discrete_optimization.git

2. создайте папку build (я предпочитаю out-of-source build, когда папка с бинарниками лежит рядом с папкой репозитория)

   mkdir ..\build

3. перейдите в папку build

   cd .\build

4. сконфигурирейте проект (при работе я использовал mingw)

   cmake ..\discrete_optimization -G Ninja

5. соберите проект

   cmake --build .

После этого в директория_сборки\application у вас будут исполянемые файлы lp_app, perf_app, там же будет файл test.txt, откуда читает данные lp_app.

В папке исходников в application есть файл main.cpp, там подключены все необходимые зависимости для работы с программой. Из него собирается lp_app.

Базовый пример использования

    obv::Table table; // инициализация пустой таблицы

    table.readFile("./test.txt"); // считывание таблицы из файла
    obv::lpalgs::simplexMethod(table);
    obv::lpalgs::cuttingPlane(table);
    std::cout << table << "\n\n";

Все методы и классы находятся в просранстве имен obv::. Для начала нужно инициализировать объект таблицы, после чего считать таблицу из файла.

После конфигурации проекта cmake'ом файл test.txt будет лежать в папке с исполняемыми файлами. Из него считывается таблица в следующем формате.

    3 3         // первое значение - число переменных; второе значение - число ограничений
    4 5 3       // max f = 4*x1 + 5*x2 + 3*x3
    2 3 1 20    //         2*x1 + 3*x2 + 1*x3 <= 20
    1 2 2 25    //         1*x1 + 2*x2 + 2*x3 <= 25
    2 1 3 15    //         2*x1 + 1*x2 + 3*x3 <= 15

Пока (и, скорее всего, так останется навсегда) поддерживается решение задач только в том формате, что указан выше (max f; <=)

Стоит упомянуть, что таблица хранится в классе obv::Table вот в таком (столбцовом) формате, после чтения условия из файла будет записана следующая матрица.

  первое значение - значение целевой функции, после первой строки идут значения переменных
  ↓
  0  4  5  3  ← целевая фукниця
  0  1  0  0
  0  0  1  0
  0  0  0  1
 20 -2 -3 -1
 25 -1 -2 -2
 15 -2 -1 -3

После применения алгоритмов, получить оптимальное значение можно обратившись к таблице по индексу [0, 0]

    obv::Table table;
    
    ...

    std::cout << table(0, 0) << "\n";

Методы

Первый аргумент методов - объект класса obv::Table. Второй аргумент - вывод промежуточных этапов решения - true/fasle. По умолчанию значение аргумента false.

1. Сипмлекс метод

   • obv::lpalgs::simplexMethod(<table>, <debug>)

2. Двойственный сипмлекс метод

   • obv::lpalgs::dualSimplexMethod(<table>, <debug>)

3. Метод отсечений Гомори

   • obv::lpalgs::cuttingPlane(<table>, <debug>)
   • перед применением этого метода сначала нужно найти нецелочисленное оптмиальное значение для задачи, применив obv::lpalgs::simplexMethod, как показано в примере

4. Полностью целочисленный метод отсечений

   • obv::lpalgs::integerCuttingPlane(<table>, <debug>)

Все методы изменяют значения полученной на вход таблицы.

Класс для замера скорости работы алгоритмов

В папке application есть файл perf_app.cpp, там подключены все необходимые зависимости для замеров эффективности алгоритмов.

В классе obv::Perf есть методы для замеров времени, записи результата и сохранения всех результатов в файл.

Проблемы

Насколько я понимаю, реализованные мной алгоритмы имеют одну проблему, либо они гарантированно получают ответ, но на это может потребовать слишком большое количетсво времени (по факту за конечное время ответа не будет), либо они будут находить ответ относительно быстро, но иметь шанс зациклиться. Это зависит от того, каким образом выбирается отсечение, иногда задачу может решить один подход, иногда другой, но все типы задач моя реализация не решает. Не исключено, что я чего-то не понимаю и совершил какую-то ошибку и проблема в этом. В программе в lpalgs.cpp можно повыбирать разные подходы, в resources есть разные примеры, которые решаются и не решаются разными подходами.

На данный момент используется не оптмиальное представление чисел произвольной размерности, возможно, позже я заменю BigInt class написанный Faheel'ем на GMP вариант.

Проблема в том, что там, вроде бы, есть ошибка в алгоритме Карацуба, из-за чего умножение чисел имеет сложность O(n^2).