XVII Международная студенческая научная конференция Студенческий научный форум - 2025

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

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

Материал и методы исследования

В ходе исследования, были проанализированы научные работы отечественных и зарубежных ученых, а также ученое пособие. Был проведен анализ глобальных проблем на просторе интернета.

Результаты исследования и их обсуждение

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

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

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

• В логистике: для оптимизации маршрутов, складского хранения и распределения товаров.

• В производстве: для максимизации прибыли и минимизации затрат при производстве продукции.

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

• В транспортной сфере: для оптимизации расписаний и планирования пассажиропотока.

• В энергетике: для оптимизации работы энергосистем.

Решение задач с помощью симплексного метода.

Пример 6.1. Найти минимум функции при условиях:

Решение. Сначала приведем задачу к каноническому виду, заменив направление поиска и введя дополнительные переменные:

при условиях:

Добьемся того, чтобы все свободные члены равенств-ограничений были положительными:

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

Составим первую симплекс-таблицу.

В последней строке таблицы найдем самое большое положительное число. (Если таких чисел нет, то функция не ограничена). Это число 3, которое стоит в третьем столбце. Столбец, в котором оно стоит, называется разрешающим. Значит, вводить в новый базис мы будем переменную . Определим, какую переменную будем выводить: для всех - соответствует переменной Теперь следует преобразовать таблицу так, чтобы в разрешающем столбце в первой строке (соответствующей переменной ) осталась 1, а в остальных строках этого столбца получились 0. Для этого выполним матричные преобразования:

а) из второй строки вычтем первую;

б) к третьей строке прибавим первую;

в) из четвертой строки вычтем 3 первых.

Получим:

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

а) вторую строку поделим на 2;

б) к первой прибавим преобразованную вторую;

в) из четвертой строки вычтем 4 преобразованных вторых.

Получим:

Поскольку в последней строке нет положительных элементов, то решение задачи получено. В итоговой симплексной таблице базисными оказались переменные . Их значения стоят в столбце b: . Основная переменная в базис не вошла, значит, . Число -14, стоящее в последней клетке таблицы, есть значение целевой функции с обратным знаком, т.е. -G(x)=-14. Значит, F(x)=-14.

Ответ:

Выводы: Симплексный метод — это мощный и проверенный временем инструмент для решения задач линейного программирования. Его простота и эффективность делают его незаменимым для оптимизации множества процессов в различных сферах. Несмотря на некоторые ограничения, он продолжает оставаться важной частью арсенала методов оптимизации и позволяет находить оптимальные решения для самых сложных задач, позволяя организациям и частным лицам использовать свои ресурсы максимально эффективно. Изучение и понимание симплексного метода — это ключ к пониманию и применению принципов оптимизации в современном мире.

Список используемой литературы:

1. Смирнов, И.А. Методы оптимизации. Базовый Смирнов. – СПб.: СПбГТИ(ТУ), 2010 102 – с.

2. Применимость симплекс-метода к решению задач целочисленного линейного программирования Михненко Н.К., Залужная Г.А.

3. Шарыгин, В. В. "Методы оптимизации: Линейное программирование и симплекс-метод".

4. Применение симплекс-метода для решения задач динамического управления запасами организации Титов В.А., Долгополов А.А