Вступление

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

● Стандартная форма

● Введение в резервные переменные.

● Создание таблицы

● Сводные переменные.

● Создание новой таблицы.

● Проверка на оптимальность

● Определите оптимальные значения.

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

Максимизировать:

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

Шаги:

  1. Преобразуйте все уравнения предмета неравенства, добавив резервные переменные. Также создайте целевую функцию, равную нулю, переместив все значения в одну сторону.
    Уравнения после добавления переменной запаса (u, v, w)
    Где u, v, w≥0

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

Теперь создайте симплексную таблицу, создав коэффициенты всего уравнения объекта и добавив уравнение объекта внизу.

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

Как определить сводный столбец:

В приведенной выше таблице -6 - наименьшее отрицательное значение в последней строке. В этом случае столбец z будет содержать сводную переменную, выделенную желтым цветом.

Как определить сводную строку:

Переменная pivot используется в операциях со строками, чтобы определить, какая переменная станет значением единицы, и является ключевым фактором при преобразовании значения единицы. Сводную переменную можно определить, посмотрев на нижнюю строку таблицы и индикатор. Предполагая, что решение не является оптимальным, выберите наименьшее отрицательное значение в нижней строке. Одно из значений, лежащих в столбце этого значения, будет переменной pivot. Чтобы найти индикатор, разделите бета-значения линейных ограничений на соответствующие им значения из столбца, содержащего возможную сводную переменную. Пересечение строки с наименьшим неотрицательным индикатором и наименьшим отрицательным значением в нижней строке станет поворотной переменной.

Разделите сводный столбец с константой в соответствующей строке и определите значения.

Решение для отношения дает нам значение (900/1 = 900) для первого ограничения, значение (350/1 = 350) для второго ограничения, и значение третьего ограничения (400/1 = 400). Поскольку 350 является наименьшим неотрицательным коэффициентом, значение поворота будет во второй строке, которая выделена зеленым цветом, а пересечение строки и столбца поворота будет элементом поворота, имеющим значение 1, которое выделено красным цветом.

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

4. Чтобы оптимизировать сводную переменную, ее необходимо преобразовать в единицу измерения (значение 1). Поскольку элемент pivot уже равен 1, нам не нужно указывать его значение единицы.

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

Формулы: R1 = R1-R2, R3 = R3-R2 и R4 = R4 + 6R2

Применение приведенных выше формул к нашей симплексной таблице приведет к таблице ниже.

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

Здесь основными переменными являются u, z, w и p.
Неосновными переменными являются x, v и y.

Отсюда мы можем получить значения переменных, как показано ниже:

x=0, y=0, v=0, u=550, w = 50, p = 2100, z = 350.

Теперь, чтобы проверить уравнение,

Максимальное оптимальное значение - 2100 и находится в точке (0,0, 350) целевой функции.

Заключение

Симплексный метод - это подход к определению оптимального значения линейной программы вручную. Метод дает оптимальное решение, удовлетворяющее заданным ограничениям и максимальное дзета-значение. Чтобы использовать симплексный метод, данная модель линейного программирования должна иметь стандартную форму, в которую затем могут быть введены резервные переменные. Используя переменные tableau и pivot, можно найти оптимальное решение.

Глоссарий

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

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

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

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

Неосновные переменные - это переменные, которые равны нулю с точки зрения оптимального решения.

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

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

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

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

Переменные Slack - это дополнительные переменные, которые вводятся в линейные ограничения линейной программы, чтобы преобразовать их из ограничений неравенства в ограничения равенства.

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

Ссылка: libretexts, Книга: Блитцер, Математическое мышление | Пирсон.