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

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

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

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

Исходная система неравенств имеет вид:

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

при xi ≥ 0.

Это ограничения для всех критериев.

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

Введем дополнительную переменную xn+1 и перенесем ее влево:

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

xi ≥ 0, Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru .

Все неравенства при этом должны быть со знаком « ≤ ».

Решив эту систему, положим xn+1=1.

Вернемся к исходной задаче. Теперь решаем систему:

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

Решение проводится с помощью преобразования ряда таблиц. Для этого вводятся обозначения:

Т11 – единичная матрица размером n×n;

T21 – транспонирование исходной матрицы.

Здесь верхний индекс – это номер итерации (шага), нижний индекс – разбиение матрицы Т на две части.

Тогда матрицу Т на первой итерации можно представить в виде:

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

Пример1. Исключение неравенств

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

Если первое уравнение умножить на 1, а второе – на 5 и сложить их, то получится пятое уравнение. Следовательно, пятое уравнение лишнее, его нужно исключить.

Исходную систему можно представить в виде матрицы Т следующим образом:

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

Если в матрице Т21 появляются столбцы, содержащие нули и отрицательные элементы, то эти столбцы лишние.

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

Алгоритм

1. В правой части (то есть в матрице Т21) находится основной столбец – тот столбец, в котором есть положительные элементы.

2. Ищем допустимые пары строк – это пары строк, пересекающие основной столбец по элементам с разными знаками.

3. Среди допустимых пар ищем уравновешенные пары. Для этого в матрице Т11 нужно найти столбцы (столбец), пересекающие допустимую пару по нулевым элементам. И не существует строк, пересекающих подобные столбцы по нулевым элементам.

4. Формируем матрицу Т2.

В рассматриваемом примере в качестве основного столбца берём крайний слева, то есть первый. 1-ая и 3-я строки – допустимая, уравновешенная пара.

Правило формирования Т2

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

Основной столбец наделяется свойствами столбцов матрицы Т1. Элементы основного столбца, отличные от нуля, заменяются на «-1».

В данном примере складываем первую и третью строки, в результате получаем матрицу Т2:

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

5. Для формирования матрицы Т3 будем искать в матрице Т2 основной столбец (в примере это 2-ой столбец), допустимые пары (1-ая и 3-я строки). Эта же пара и уравновешенная.

6. Выписываем строки, пересекающие основной столбец по отрицательным элементам и нулям, а строку равновесия с единичными коэффициентами.

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

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

Здесь пятый столбец лишний, поэтому он исключается.

7. Формируем матрицу Т4: основной столбец третий.

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

Допустимые, уравновешенные пары: 1,3 и 1,2.

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

Выбрать основной столбец невозможно, строго положительного

столбца нет, значит, выписываем решение.

Решение системы можно представить в виде:

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru , где L – число строк последней матрицы,

рi ≥ 0.

Для примера решение будет иметь вид:

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

Решение можно представить в виде системы (в скалярной форме):

Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств - student2.ru

При р1 = 1, р2 = 1, р3 = 1 и р4 = 1 получим х1 = 6, х2 = 6, х3 = 4.

При данных ограничениях хi эта система выполняется.

Далее выражения для хi подставляются в целевую функцию, а в качестве ограничения берется уравнение xn+1=1. Затем находится решение полученной системы.

УСТОЙЧИВЫЕ АДАПТИВНЫЕ МЕТОДЫ ОЦЕНИВАНИЯ параметров НА ОСНОВЕ МЕТОДА МАКСИМАЛЬНОГО ПРАВДОПОДОБИЯ.(АОИ)

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

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

Наши рекомендации