Алгоритм базового симплексного метода

↑

▷ Содержание

⇐ ПредыдущаяСтр 3 из 6Следующая ⇒

Шаг 1. Задана исходная базисная точка :

Вычислить оценки по формуле

Шаг 2. Проверить, если все Δ _j ≥0, то перейти к шагу 8.

Шаг 3. Проверить, если  то перейти к шагу 10.

Шаг 4. Выбрать k: Δ _k <0 и вектор A_k имеет хотя бы одну строго

положительную координату (возможен произвольный выбор такого номера k, например, ) 

Шаг 5. Вычислить параметр Θ по формуле

Шаг 6. Осуществить переход к новой базисной точке с помощью метода Жордана-Гаусса с направляющим элементом a _{l k}.

Шаг 7. Изменить исходную информацию:

Перейти к шагу 1.

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

Шаг 9. Если для всех , то выписать ответ:  - единственное решение задачи.

Шаг 10. Выписать ответ: задача решений не имеет из-за неограниченности целевой функции на допустимом множестве:

Пример 1. Решить задачу

Решение. Оформим решение задачи в виде таблицы. В первом столбце поместим текущие базисные переменные, во втором - их коэффициенты в целевой функции, в третьем - базисные координаты текущей точки . Далее переписываем элементы матрицы  помещая над каждым столбцом коэффициент соответствующей переменной в целевой функции. Последний столбец предназначается для определения значения Θ. В отдельной строке вычисляются оценки векторов A_j. В ячейке, находящейся на пересечении оценочной строки и столбца , помещаем значение целевой функции в текущей базисной точке.

Поскольку на первой итерации Δ₁ <0, в базис вводится вектор A₁. , т.е. в качестве направляющего элемента выбирается . Так как на второй итерации все Δ _j ≥0, то останов, получена оптимальная точка . Поскольку на небазисных векторах , то решение в задаче единственно.

Пример 2.  Решить задачу

Решение.

На второй итерации получаем, что оценка Δ₂ <0, но в столбце A₂ нет положительных элементов. Это означает, что целевая функция не ограничена на допустимом множестве, т.е. .

Задачи для самостоятельного решения

1. Решить симплекс- методом задачу ЛП, предварительно приведя ее к каноническому виду.

;

2. Проверить, является ли точка  решением задачи ЛП:

3. Используя теорию симплекс- метода, найти все значения к, при которых точка  является решением задачи

;

Метод искусственного базиса и M-метод решения

Познавательные статьи:



Техника прыжка в длину с разбега

Тактические действия в защите

История Олимпийских игр

История развития права интеллектуальной собственности