Лабораторная работа: Реализация симплекс метода

Обшие требования как к обычному, так и к усложненному варианту:

1. Входные данные:
   • Целевая функция.
   • Система линейных ограничений.
2. Обязательно должна присутствовать провера на корректность ввода и вывод сообщения для пользователя в случае невозможности решения задачи.
3. Для реализации можно использовать следующие ЯП: JS, TS, C#, C++, Java, VBA.
4. В программе должен быть предусмотрен блок тестов для автоматической проверки на типичных задачах. Для проверки собственной программы можно использовать онлайн калькулятор. В нижней части страницы с калькулятором присутствует общий алгоритм решения задач ЛП симплекс-методом.
5. Должен быть обеспечен удобный ввод и вывод данных.

Простой вариант: Базовый симплекс метод

Ограничения

Решение задач линейного программирования (ЛП) с использованием симплекс метода. Условия:

• Ограничения могут быть только вида "≤".
• Все переменные неотрицательны.
• Целевая функция стремится к максимуму.

Пример задачи

Максимизировать: \[ Z = 2x_1 + 3x_2 \] при условиях: \[ x_1 + 2x_2 \leq 8 \] \[ 2x_1 + x_2 \leq 6 \] \[ x_1, x_2 \geq 0 \]

С примером и разбором решения задачи базовым симплекс-методом можно ознакомиться по ссылке.

Интерфейс

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

Усложненный вариант: Двойственный симплекс метод

Ограничения

Этот вариант предполагает решение более сложных задач с использованием двойственного симплекс метода. Условия:

• Задачи могут быть как на максимизацию так и на минимизацию.
• Допускаются различные типы ограничений: "≤", "≥", "=".
• Переменные могут быть как положительными, так и отрицательными.

Требования к решению

• Обязательно должен быть реализован GUI.

Пример задачи

Минимизировать: \[ Z = 4x_1 + 6x_2 + 3x_3 \] при условиях: \[ x_1 + 2x_2 - x_3 \geq 5 \] \[ 3x_1 + 2x_2 + x_3 = 8 \] \[ x_1 \geq 0, \quad x_2 \leq 0, \quad x_3 \geq 0 \]

С примером и разбором решения задачи двосйственным симплекс-методом можно ознакомиться по ссылке.

Интерфейс

Для сдачи усложненного (двойственного) симплекс-метода необходимо наличие GUI. Выбор за вами, но графический интерфейс проще будет сделать в вебе. После этого соотвественно либо пишете бек на JS, либо добавляете в схему сервер, на который будете отправлять считанные данные, и используете любой из разрешенных ЯП для решения задачи на серверной стороне.