Аналитические методы поиска оптимального решения

Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).

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

Для определенности предположим, что первые m векторов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план: (b₁, b₂, …, b_m, 0, …, 0).

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

Признак оптимальности заключается в следующих двух теоремах.

Теорема 3.1. Если для некоторого вектора, не входящего в базис, выполняется условие

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

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

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

Теорема 3.2. Если для всех векторов выполняется условие

На основании признака оптимальности в базис вводится вектор А _k, давший минимальную отрицательную величину симплекс-разности:

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

Строка А_г называется направляющей, столбец А_г и элемент а_гк –направляющими (последний называют также разрешающим элементом).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формуле

а элементы любой другой i-й строки пересчитываются по формулам:

Значения базисных переменных нового опорного плана (показатели графы "план") рассчитываются по формулам:

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

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

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

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

I. После введения добавочных переменных систему уравнений и линейную функцию записываем в виде, который называется расширенной системой:

Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены; в противном случае используем так называемый М-метод, который будет рассмотрен ниже.

II. Исходную расширенную систему заносим в первую симплексную таблицу. Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком: b₁ = – с_i. В левом столбце таблицы записываем основные переменные (базис), в первой строке таблицы – все переменные (отмечая при этом основные), во втором столбце – свободные члены расширенной системы b₁, b₂, …, b_m. Последний столбец подготовлен для оценочных отношений, нeoбxoдимыx при расчете наибольшего возможного значения переменной. В рабочую часть таблицы (начиная с третьего столбца и второй строки) занесены коэффициенты а_ij при переменных из расширенной системы. Далее таблица преобразуется по определенным правилам.

III. Проверяем выполнение критерия оптимальности при решении задачи на максимум - наличие в последней строке отрицательных коэффициентов b_i < 0 (с_i > 0). Если таких нет, то решение оптимально, достигнут max F = c₀ (в левом нижнем углу таблицы), основные переменные принимают значения а_i₀ (второй столбец), основные переменные равны 0, т.е. получаем оптимальное базисное решение.

IV. Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент Ь_i < 0 в последней строке определяет разрешающий столбец s.

Составляем оценочные ограничения каждой строки по следующим правилам:

Если конечного минимума нет, то задача не имеет конечного оптимума (F_max = ¥). Если минимум конечен, то выбираем строку q, на которой он достигается (любую, если их несколько), и называем ее разрешающей строкой. На пересечении разрешающих строки и столбца находится разрешающий элемент а_qs.

V. Переходим к следующей таблице по правилам:

а) в левом столбце записываем новый базис: вместо основной переменной х_q - переменную x_s;

б) в столбцах соответствующих основным переменным проставляем нули и единицы: 1 - против "своей" основной переменной, 0 - против "чужой" основной переменной, 0 – в последней строке для всех основных переменных;

в) новую строку с номером q получаем из старой делением на разрешающий элемент a_qs;

г) все остальные элементы а вычисляем по правилу прямоугольника (рис. 5.3.2).

Рассмотрим пример. Решим задачу об использовании ресурсов, приведенную в подразделе 1.4, с помощью симплексных таблиц.

Задача 3.2. Исходная система ограничений имеет вид:

Решение. Приведем задачу к канонической, введя дополнительные переменные x₃, x₄, x₅, x₆. Расширенная система задачи имеет вид:

Линейную функцию представим в виде F – 2x₁ – 3x₂ = 0.

Заполняем первую симплексную таблицу (табл. 5.3.1), в которой переменные х₃, х₄, х₅, х₆ – основные. Последняя строка заполняется коэффициентами линейной функции с противоположным знаком (см. п. II алгоритма).

В соответствии с п. III алгоритма проверяем критерий оптимальности. В последней строке имеются отрицательные коэффициенты. Выбираем из них наибольший по модулю (-3); второй столбец - разрешающий, переменная x перейдёт в основные (этот столбец отмечен стрелкой). В соответствии с п.IV находим оценочные отношения и x₂ = min {18/3; 16; 5; ¥} = 5. Третья строка является разрешающей (отмечена горизонтальной стрелкой). На пересечении разрешающих строки и столбца стоит элемент а₃₃ = 1.

Строим таблицу 5.3.2 по правилам п. V алгоритма:

а) в новом базисе основные переменные: х₃, х₄, х₂, х₆;

б) расставляем нули и единицы; например, в клетке, соответствующей основной переменной х₃ по столбцу и строке, ставим 1, а в клетке, соответствующей основной переменной х₃ по строке, а основной переменной х₂ – по столбцу, ставим 0 и т.п. В последней строке против всех основных переменных ставим 0. Третья строка получается делением на разрешающий элемент а₃₃ = 1. Остальные клетки заполняем по правилам прямоугольника. Например:

Получим вторую симплексную таблицу (таблице 3.2).

Критерий оптимальности вновь не выполнен. Теперь первый столбец разрешающий; х₁ переходит в основные, min{3/1; 11/2; ¥; 7} = 3; первая строка разрешающая, а₁₁ – разрешающий элемент.

Новая симплексная таблица примет вид таблице (5.3.3).

И на этот раз критерий оптимальности не выполнен; пятый столбец и вторая строка разрешающие. а₂₅ = 5 – разрешающий элемент.

Критерий оптимальности выполнен, значит F_max = 24, оптимальное базисное решение (6; 4; 0; 0; 1; 3).

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

В каждое уравнение, дающее отрицательную компоненту в базисном решении, вводим свою новую неотрицательную искусственную переменную у₁, у₂,..., у_k, которая имеет тот же знак, что и свободный член в правой части уравнения. В первой таблице включаем в число основных все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицательные компоненты базисного решения. Составляем новую линейную функцию Т = F - М (у₁ + y₂ +... + у_k), где М -произвольно большое число, и ищем ее максимум (Т-задача). Назовем М-функцией выражение М (у₁ + y₂+„.+ y_k). Справедлива следующая теорема (доказательство здесь не приводится):

1. Если в оптимальном решении Т-задачи все искусственные переменные равны нулю, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи (т.е. T_max = F_max, если у₁ = y₂=...= y_k = 0, т.е. минимум М-функции равен нулю).

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

3. Если T_max = ¥, то исходная задача также неразрешима, причём либо F_max = ¥, либо условия задачи противоречивы.

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

Пример. Решить М-методом следующую задачу, используя симплексные таблицы,

Решение. Введём необходимое число искусственных переменных и столько же дополнительных строк в симплексные таблицы.

Х₁ = (0; 0; -1; 3; 5) – недопустимое базисное решение с одной отрицательной компонентой, поэтому в первое уравнение введём искусственную переменную у₁ с тем же знаком, что и свободный член:

Составляем первую симплексную таблицу (таблице 5.3.5).

Последняя строка – это (-М)-функция, т.е. (М_ф)у₁. Заполняем её, умножая строку у₁ на коэффициент (-М). Проверяя выполнение критерия оптимальности при отыскании максимума (-М)-функции, определяем, что в последней строке имеется отрицательный элемент во втором столбце, значит, он является разрешающим. Переменная х₂ переходит в основные. Минимальное оценочное отношение находится в первой строке, она - разрешающая. Переменная у₁ переходит в неосновные, обращается в нуль на следующем базисном решении и далее исключается из рассмотрения.

В соответствии с общим алгоритмом получаем таблицу 5.3.6.

Последняя строка показывает, что критерий оптимальности выполнен; max (М_ф) = 0, значит, min М_ф = 0, далее эту строку можно не рассматривать. Получено допустимое базисное решение (0; 1; 0; 2; 3).

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: