Решение задач линейного программирования с использованием метода симплекс

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

Что такое метод симплекс?

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

Задача линейного программирования

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

1. Целевую функцию для максимизации или минимизации.
2. Ограничения в виде линейных неравенств.
3. Ненулевые переменные.

Например:

Максимизировать: Z = 3x + 2y
при условиях:
2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24
x, y ≥ 0

Здесь Z — целевая функция, которую нужно максимизировать. Ограничения представлены неравенствами. Оба переменных, x и y, должны быть больше или равны нулю.

Этапы метода симплекс

Метод симплекс включает несколько основных этапов:

Этап 1: Преобразование неравенств в уравнения

Преобразуйте неравенства в равенства, добавив дополнительные переменные. Дополнительные переменные представляют разницу между левой и правой сторонами неравенства.

Рассмотрим ограничения:

2x + y ≤ 18
2x + 3y ≤ 42
3x + y ≤ 24

Добавьте дополнительные переменные s1, s2 и s3, чтобы изменить их:

2x + y + s1 = 18
2x + 3y + s2 = 42
3x + y + s3 = 24

Теперь уравнения линейны и имеют дополнительные переменные, которые изначально равны нулю.

Этап 2: Построение симплекс-таблицы

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

| x | y | s1 | s2 | s3 | Решение |
, 2 | 1 | 1 | 0 | 0 | 18 |
, 2 | 3 | 0 | 1 | 0 | 42 |
, 3 | 1 | 0 | 0 | 1 | 24 |
, -3 | -2 | 0 | 0 | 0 | 0 |

Примечание: Нижняя строка формируется посредством вычитания коэффициентов целевой функции. Эта строка помогает определить оптимизацию.

Этап 3: Определите элемент-поворот

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

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

Например:

Отношение: (18/2) = 9, (42/2) = 21, (24/3) = 8 

Наименьшее отношение — 8, что соответствует строке-повороту. А для этого примера, поскольку -3 — самое отрицательное в нижней строке, столбец-поворот — это столбец с 3.

Этап 4: Выполнение операций строк

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

Этап 5: Итерация

Повторяйте этапы 3 и 4, пока в нижней строке больше не останется отрицательных чисел. Когда этот момент достигнут, исходное допустимое решение, которое было найдено, является оптимальным.

Практический пример использования метода симплекс

Кризис

Максимизировать функцию Z = 5x + 4y, при условиях:

y + 2x ≤ 20 
2x + 3y ≤ 30 
2x + y ≤ 15 
x, y ≥ 0

Этап 1: Преобразование в уравнение с дополнительной переменной

x + 2y + s1 = 20
2x + 3y + s2 = 30
2x + y + s3 = 15

Этап 2: Построение симплекс-таблицы

| x | y | s1 | s2 | s3 | Решение |
, 1 | 2 | 1 | 0 | 0 | 20 |
, 2 | 3 | 0 | 1 | 0 | 30 |
, 2 | 1 | 0 | 0 | 1 | 15 |
| -5|-4 | 0 | 0 | 0 | 0 |

Этап 3: Определите элемент-поворот

Элемент с -5 — это столбец-поворот. Вычисляя отношение для третьего столбца:

Отношение: (20/1) = 20, (30/2) = 15, (15/2) = 7.5

Наименьшее положительное значение — 7.5. Элемент в (Строка 3, Столбец 1) будет элементом-поворотом.

Этап 4: Выполнение операций строк

Сделайте элемент-поворот равным 1:

| x | y | s1 | s2 | s3 | Решение |
, 1 | 2 | 1 | 0 | 0 | 20 |
| 1 | 1.5| 0 | 0.5| 0 | 7.5 | <- строка-поворот (элемент-поворот 1 создан)
, 2 | 1 | 0 | 0 | 1 | 15 |
| -5|-4 | 0 | 0 | 0 | 0 |

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

Этап 5: Оптимальное решение

Посредством последовательных итераций, в конечном итоге:

| x | y | s1 | s2 | s3 | Решение |
, 1 | 0 | 1 | 1 | 0 | 5 |
| 0 | 1 | 0 | 1.5| 0 | 12.5 |
, 0 | 0 | -1 |-1.5| 1 | -7.5 |
| 0 | 0 | 0 |0.5 | 0 | 35 |

Значения x = 5 и y = 12.5 максимизируют целевую функцию Z до значения 35.

Вывод

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

комментарии