double arrow

Симплекс-метод решения задач линейной оптимизации

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

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

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

Если , то мы выходим за рамки трехмерного пространства, и геометрическая интерпретация теряет наглядность.

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

Впервые симплексный метод был предложен американским учёным Данцигом в 1949г., однако, ещё в 1939г. идеи метода были разработаны российским математиком
Л. В. Канторовичем.

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

Алгоритм симплексного метода включает следующие этапы:

1. Составление первого опорного плана

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

3. Определение разрешающих столбца и строки

4. Построение нового опорного плана

Составление первого опорного плана

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

, где - базисные переменные, - свободные переменные

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

Б.П. З.Б.П.(С.Ч.)
F

Б.П. - базисные переменные, З.Б.П.- значения базисных переменных, С.Ч.- свободные члены, последняя строка таблицы – индексная строка (строка целевой функции).

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

Алгоритм нахождения оптимального плана

1. Считаем, что в симплексной таблице получено опорное решение. Просматриваем коэффициенты индексной строки. Если все они неотрицательны, то оптимальное решение получено. В этом решении все небазисные переменные равны 0, а базисные переменные равны значению столбца свободных членов.

2. Если среди коэффициентов строки функции (индексной) имеются отрицательные (за исключением свободного члена), то выбираем среди них наибольший по абсолютной величине, и столбец, в котором находится этот коэффициент, берём за разрешающий. Разрешающий столбец показывает, какая переменная на следующей итерации перейдёт из свободных в базисные.

3. Затем элементы столбца свободных членов делим на элементы того же знака (+/+, -/-) разрешающего столбца. Результаты, которые будут всегда положительные, заносим в отдельный столбец симплексных отношений (СО). (Если знаки разные или деление на 0 — в столбце СО прочерк)

4. Разрешающую строку находим по наименьшему симплексному отношению.

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

6. С найденным разрешающим элементом рассчитывают новую таблицу;

Правила расчёта элементов новой таблицы:

а) вместо разрешающего элемента в новой таблице ставится обратная ему величина;

б) элементы разрешающей строки делятся на разрешающий элемент;

в) элементы разрешающего столбца делятся на разрешающий элемент и записываются с противоположным знаком;

г) все прочие элементы таблицы вычисляются по формуле, которая носит название прямоугольника:

→?

Сначала по этому правилу вычисляется произведение элементов и . Затем произведение элементов расположенных в двух других вершинах прямоугольника. Разность между найденными произведениями делится на разрешающий элемент.

;

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

7. Если в разрешающем столбце таблицы все элементы неположительны, то разрешающую строку выбрать невозможно. Задача в этом случае решения не имеет. Функция в области допустимых решений задачи не ограничена.

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

Пример.Найти максимум функции

при ограничениях:


Сейчас читают про: