Методы обработки информации
Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств. Основные методологические вопросы сочетания планирования и прогнозирования. Оптимальные значения критериев.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 15.01.2018 |
| Размер файла | 96,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное Образовательное Учреждение
Высшего Профессионального Образования
РЯЗАНСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра АСУ
Контрольная работа
«Методы обработки информации»
Выполнил: ст. гр. 8033
Демочкин В. А.
Проверил:
Кабанов А.Н.
г. Рязань, 2013 г.
Упрощение системы линейных неравенств, описывающих область допустимых изменений параметров. Получение решения систем линейных неравенств.
Размещено на http://www.allbest.ru/
При оптимизации должны выполняться все критерии. В результате остается только заштрихованная область. Таким образом, появляется масса лишних неравенств, которые должны быть удалены.
Если проводим оптимизацию по критерию 1, то нужно учитывать все критерии, все ограничения, в связи с этим система уравнений имеет очень большой порядок. Поэтому оптимизацию следует проводить после исключения лишних неравенств.
Исходная система неравенств имеет вид:
при xi ? 0.
Это ограничения для всех критериев.
Обычно задачу сводят к однородной системе ограничений, то есть правая часть нули.
Введем дополнительную переменную xn+1 и перенесем ее влево:
xi ? 0, .
Все неравенства при этом должны быть со знаком « ? ».
Решив эту систему, положим xn+1=1.
Вернемся к исходной задаче. Теперь решаем систему:
Решение проводится с помощью преобразования ряда таблиц. Для этого вводятся обозначения:
Т11 - единичная матрица размером nЧn;
T21 - транспонирование исходной матрицы.
Здесь верхний индекс - это номер итерации (шага), нижний индекс - разбиение матрицы Т на две части.
Тогда матрицу Т на первой итерации можно представить в виде:
Алгоритм:
1. В правой части (то есть в матрице Т21) находится основной столбец - тот столбец, в котором есть положительные элементы.
2. Ищем допустимые пары строк - это пары строк, пересекающие основной столбец по элементам с разными знаками.
3. Среди допустимых пар ищем уравновешенные пары. Для этого в матрице Т11 нужно найти столбцы (столбец), пересекающие допустимую пару по нулевым элементам. И не существует строк, пересекающих подобные столбцы по нулевым элементам.
4. Формируем матрицу Т2.
Правило формирования Т2
Выписываются строки, пересекающие основной столбец по отрицательным элементам и нулям в любой последовательности, и выписывается строка равновесия. Строка равновесия формируется из уравновешенных пар путем умножения их на положительные коэффициенты такие, что на месте основного столбца получается нуль. Для повышения точности желательно все расчеты проводить в целых числах.
Основной столбец наделяется свойствами столбцов матрицы Т1. Элементы основного столбца, отличные от нуля, заменяются на «-1».
5. Для формирования матрицы Т3 будем искать в матрице Т2 основной столбец , допустимые пары.
6. Выписываем строки, пересекающие основной столбец по отрицательным элементам и нулям, а строку равновесия с единичными коэффициентами.
Решение системы можно представить в виде:
, где L - число строк последней матрицы,
рi ? 0.
Далее выражения для хi подставляются в целевую функцию, а в качестве ограничения берется уравнение xn+1=1. Затем находится решение полученной системы.
Например, систему ограничений, имеющий вид
|
x1 |
<= |
5 |
|
|
x1 |
>= |
2 |
|
|
x2 |
>= |
2 |
|
|
x2 |
<= |
5 |
|
|
x2 |
<= |
3 |
преобразовываем в систему ограничений
|
x1-5 |
<= |
0 |
|
|
-x1+2 |
<= |
0 |
|
|
-x2+2 |
<= |
0 |
|
|
x2-5 |
<= |
0 |
|
|
x2-3 |
<= |
0 |
Исходная матрица T1 имеет вид:
|
1.00 |
0.00 |
0.00 |
1.00 |
-1.00 |
0.00 |
0.00 |
0.00 |
|
|
0.00 |
1.00 |
0.00 |
0.00 |
0.00 |
-1.00 |
1.00 |
1.00 |
|
|
0.00 |
0.00 |
1.00 |
-5.00 |
2.00 |
2.00 |
-5.00 |
-3.00 |
В результате описанных ранее преобразований получаем:
Решение однородной системы:
x1 = 5p1 + 10p2 + 15p3 + 150p4
x2 = 2p1 + 10p2 + 9p3 + 225p4
x3 = p1 + 5p2 + 3p3 + 75p4
Многокритериальные системы. Критерии имеют общую область изменения параметров
Имеются три критерия:
Пусть у1, у2 надо максимизировать, а у3 - минимизировать. На х1 и х2, от которых зависят у1 и у2, наложим ограничения:
2 ? х1 ? 7
2 ? х2 ? 6
Существует несколько подходов к оптимизации.
1. Критерии, различные по значимости.
y1 > y2 > y3 - располагаем критерии по значимости.
Проводим оптимизацию по самому важному критерию у1 не обращая внимания на другие критерии.
Исходная таблица
|
-x1 |
-x2 |
B |
||
|
y1 |
-1 |
0 |
-2 |
|
|
y2 |
1 |
0 |
7 |
|
|
y3 |
0 |
-1 |
-2 |
|
|
y4 |
0 |
1 |
6 |
|
|
fmax |
-1 |
-5 |
0 |
Результирующая таблица
|
-y2 |
-y4 |
B |
||
|
x1 |
1 |
0 |
7 |
|
|
y1 |
1 |
0 |
9 |
|
|
x2 |
0 |
1 |
6 |
|
|
y3 |
0 |
1 |
5 |
|
|
fmax |
1 |
5 |
37 |
x1 = 7, x2 = 6 - оптимальное решение для критерия y1.
Выражение уступки по 1-му критерию:
В левой части пишется выражение критерия, по которому мы уступаем. В правой части - произведение коэффициента уступки на оптимальное значение критерия. Если критерий максимизируется, то коэффициент уступки Куст ? 1, а правая и левая части соединяются знаком « ? ». Если критерий минимизируется, то Куст > 1, а правая и левая части соединяются знаком « ? ».
x1 + 5x2 >= Куст. * y1*
Пусть Куст = 0.9
Тогда дополнительное ограничение будет иметь вид:
x1 + 5x2 >= 0.9 * 37
Система ограничений будет иметь вид:
Решаем задачу по второму критерию.
|
-x1 |
-x2 |
B |
||
|
y1 |
-1 |
0 |
-2 |
|
|
y2 |
1 |
0 |
7 |
|
|
y3 |
0 |
-1 |
-2 |
|
|
y4 |
0 |
1 |
6 |
|
|
y5 |
-1 |
-5 |
33 |
|
|
fmax |
-1 |
-0.25 |
0 |
|
-y2 |
-y4 |
B |
||
|
x1 |
1 |
0 |
7 |
|
|
y1 |
1 |
0 |
5 |
|
|
x2 |
0 |
1 |
8 |
|
|
y5 |
1 |
5 |
4 |
|
|
y3 |
0 |
1 |
4 |
|
|
fmax |
1 |
0.25 |
8.5 |
x1 = 7, x2 = 6 - оптимальное решение.
Kуст = 0.8
x1 + 0.25x2 >= 6.8 - дополнительное ограничение.
|
-x1 |
-x2 |
B |
||
|
y1 |
-1 |
0 |
-2 |
|
|
y2 |
1 |
0 |
7 |
|
|
y3 |
0 |
-1 |
-2 |
|
|
y4 |
0 |
1 |
6 |
|
|
y5 |
-1 |
-5 |
33 |
|
|
y6 |
-1 |
0.25 |
-6.8 |
|
|
fmin |
1 |
1,5 |
0 |
|
-y6 |
-y5 |
B |
||
|
x1 |
-1.1 |
0.05 |
5.4 |
|
|
y2 |
1.1 |
-0.05 |
1.6 |
|
|
x2 |
0.21 |
-0.21 |
5.5 |
|
|
y4 |
-0.21 |
0.21 |
0.48 |
|
|
y3 |
0.21 |
-0.21 |
3.5 |
|
|
y1 |
-1.1 |
0.05 |
3.4 |
|
|
fmax |
0.74 |
0.26 |
-13.7 |
x1 = 5.4; x2 = 5.5 - параметры, удовлетворяющие всем трем критериям.
2. Критерии равнозначны.
К исходной системе ограничений добавляется уравнение равнозначности:
где у1*, у2*, у3* - оптимальные значения критериев при однокритериальной оптимизации:
у1* - оптимальное значение по первому критерию не обращая внимания на другие критерии и т.д.
По этим критериям несем потери. Уравнение равнозначности означает, что относительные потери по всем критериям должны быть равны. Знаки модуля вводят нелинейность.
Рассуждая логично, знаки модуля можно снять. Если критерий максимизируется, то всегда у1 < у1*:
y1*=37, y2*=8.5, y3*=5
После преобразований получаем систему неравенств:
линейный неравенство критерий планирование
Оптимизация производится по любому из критериев. Н-р: y1 -> max
|
-x1 |
-x2 |
B |
||
|
0 |
28.5 |
-33.3 |
0 |
|
|
0 |
42.0 |
80.5 |
-370 |
|
|
y3 |
-1 |
0 |
-2 |
|
|
y4 |
1 |
0 |
7 |
|
|
y5 |
0 |
-1 |
-2 |
|
|
y6 |
0 |
1 |
6 |
|
|
fmax |
-1 |
-5 |
0 |
|
0 |
0 |
B |
||
|
x1 |
0.02 |
0.01 |
-3.4 |
|
|
x2 |
-0.01 |
0.01 |
-2.8 |
|
|
y3 |
0.02 |
0.01 |
-5.4 |
|
|
y4 |
-0.02 |
-0.01 |
3.4 |
|
|
y5 |
-0.01 |
0.01 |
-4.8 |
|
|
y6 |
0.01 |
-0.01 |
8.8 |
|
|
fmax |
-0.04 |
0.05 |
-17.6 |
Решений нет. Система ограничений несовместна.
3. Метод оптимизации номинала.
Если критериев много, то ищут точку внутри области примерно на равном расстоянии от границы области. В большинстве случаев применяется квадратичный критерий.
Исходная система ограничений:
(*)
Левые части обозначим:
Берём у1 как целевую функцию и на множестве (*) находим максимальное и минимальное значения у1. Затем берем у2 и опять находим максимальное и минимальное значения у2 и т.д. (yi min, yi max).
- среднее значение.
Тогда система ограничений примет вид:
Это система линейных алгебраических уравнений.
.
Исходная система ограничений имеет вид:
=>
y1max = 7; y1min = 2;
y2max = 6; y2min = 2.
Методологические вопросы сочетания планирования и прогнозирования
Подавляющее число экономических объектов, будь то цех или бригада, завод, отрасль или район, в большей мере подвержено действию случайных факторов. Действие случайных факторов нельзя игнорировать: планирование следует сочетать с прогнозированием. Это неразрывно связанные между собой аспекты.Рассмотрим возможность реализации процесса прогнозирования на примере прогнозирования с нестационарной сезонной составляющей.
Метод аппроксимации.
Производственный процесс
y[N+k] - ?
Разложим процесс в ряд:
,
где
y[n] - отсчеты;
- некоторая система функций, по которой ведём разложение (для тренда это полиномы);
- погрешность измерения (типа «белого шума»);
bi - искомые коэффициенты.
Модель производственного процесса (аппроксимация) можно представить в виде:
.
- такие значения, чтобы модель yA[n] была близка к y[n]. Как правило, применяется квадратичный критерий близости.
Квадратичный критерий имеет вид:
,
здесь подбирается критерий ,
R[n] - вес, который мы придаём результатам измерения.
Скользящее стробирование:
Экспоненциальное сглаживание (самый распространенный метод):
Общий случай:
Планирование прогноза - это подбор весовой функции R[n]. Наибольшее распространение получило экспоненциальное сглаживание.
Представим исходный процесс y[n] в матричном виде:
,
- помеха типа «белого шума» (ошибки между собой не связаны).
Это же уравнение можно записать в индексной форме:
;
;
;
условие минимуму этого критерия:
.
Элементы матрицы А:
,
в индексной форме:
.
Уравнение через элементы матриц:
.
Матрица z:
;
;
Н-р процесс имеет вид:
y[n] = 3n + е
Аппроксимируем процесс полиномом
yA[n] = 1 b1 + nb2
ц1[n] = 1; ц2[n] = n
R[n] - весовая функция.
y[3+k] = ???
b1 = 0.1; b2 = 3.1
yA[n] = 0.1*1 +3.1*n
yA[4] = 0.1*1 + 3.1*4 = 12.5
Размещено на Allbest.ru
...Подобные документы
Системы линейных алгебраических уравнений. Код программы для решения систем линейных алгебраических уравнений. Математические и алгоритмические основы решения задачи методом Гаусса. Программная реализация решения. Алгоритмы запоминания коэффициентов.
лабораторная работа [23,5 K], добавлен 23.09.2014Понятия систем линейных уравнений и матриц. Решение общей системы линейных уравнений по методу Гаусса. Системные требования, методы установки, удаления и работы с программой. Методы защиты от неверного ввода данных. Тестирование и опытная эксплуатация.
курсовая работа [751,0 K], добавлен 25.02.2011Раскрытие понятия "системы компьютерной математики", история ее развития. Внутренняя архитектура и составляющие СКМ. Основные принципы работы системы Maple. Ее возможности для решения линейных и нелинейных уравнений и неравенств. Применение функции solve.
курсовая работа [189,4 K], добавлен 16.09.2017Использование MS Excel для математических расчетов. Описание численных методов решения системы линейных алгебраических уравнений. Решение систем линейных алгебраических уравнений с методами Крамера и Зейделя и с помощью табличного процессора MS Excel.
курсовая работа [1,6 M], добавлен 14.02.2021Объектно-ориентированное программирование: основная идея, сопровождение, модификация, термины и положения. Понятие объекта как логической единицы, правила (методы) обработки данных. Метод Гаусса для решения систем линейных алгебраических уравнений.
курсовая работа [125,1 K], добавлен 22.04.2009Системы линейных алгебраических уравнений. Матричный метод решения систем линейных уравнений. Решение задачи математическим методом. Блок-схема алгоритма и листинг программы. Расчет трудоемкости разработки программы. Расчет себестоимости и цены программы.
дипломная работа [144,8 K], добавлен 25.04.2012Программный продукт для решения систем линейных уравнений методом Гаусса. Алгоритм для проведения вычислений. Цель разработки и область ее применения. Схема информационных потоков. Метод Гаусса: исключение неизвестных. Проектирование удобного интерфейса.
курсовая работа [340,0 K], добавлен 02.07.2010Методы решения систем линейных уравнений трехдигонального вида: прогонки, встречных прогонок, циклической редукции. Параллельные алгоритмы решения. Метод декомпозиции области. Основные возможности и особенности технологии CUDA. Анализ ускорения алгоритма.
дипломная работа [1,4 M], добавлен 21.06.2013Решение систем алгебраических линейных уравнений методом Крамера. Сущность метода прогонки. Программная реализация метода: блок-схема алгоритма, листинг программы. Проверка применимости данного способа решения для конкретной системы линейных уравнений.
курсовая работа [581,0 K], добавлен 15.06.2013Общее понятие о линейных уравнениях и их системах. Разработка программного продукта в среде Delphi 7 для решения методом Крамера квадратных систем линейных алгебраических уравнений с ненулевым определителем основной матрицы. Описание конкретных примеров.
курсовая работа [193,7 K], добавлен 07.07.2013Команды, используемые при решении уравнений и их систем, неравенств и их систем в системе аналитических вычислений Maple. Выражения, соединенные знаком равенства. Проверка типа переменной. Решение одного уравнения относительно заданной переменной.
лабораторная работа [41,7 K], добавлен 15.07.2009Алгоритм решения систем линейных уравнений методом Гаусса, его этапы. Система уравнений для определения коэффициентов сплайна, представляющая собой частный случай систем линейных алгебраических уравнений. Программная реализация, тестовый пример.
курсовая работа [431,8 K], добавлен 15.06.2013Численные методы линейной алгебры. Матричный метод. Методы Крамера и Гаусса. Интерации линейных систем. Интерации Якоби и Гаусса - Зейделя. Листинг программы. Численные методы в электронных таблицах Excel и программе MathCAD, Microsoft Visual Basic
курсовая работа [1,2 M], добавлен 01.06.2008Описание математических методов решения систем линейных уравнений. Метод Гаусса, матричный метод. Вычисление определителей второго и третьего порядка. Язык программирования Паскаль. Структура программы, описание переменных, основные конструкции языка.
курсовая работа [137,3 K], добавлен 20.07.2010Разработка мультимедийного учебного пособия, содержащего текстовую и графическую информацию по системе решения систем линейных уравнений. Требования к функциональной части прикладной системы, к интерфейсу пользователя. Структура обучающей программы.
дипломная работа [4,9 M], добавлен 07.04.2014Изучение систем линейных алгебраических уравнений (СЛАУ) с использованием табличного процессора MS Excel 2007. Пример решения системы линейных алгебраических уравнений методом Крамера. Прикладное программное обеспечение, применяемое для решения СЛАУ.
курсовая работа [184,5 K], добавлен 20.11.2013Сущность матричного метода. Разработка программы решения системы уравнений линейных алгебраических уравнений методом решения через обратную матрицу на языке программирования Delphi. Представление блок-схемы и графического интерфейса программного продукта.
курсовая работа [1,0 M], добавлен 27.09.2014Возможности математического пакета MathCad в среде Windows 98 для использования матричной алгебры и решения системы линейных алгебраических уравнений. Методы решения систем линейных алгебраических уравнений. Сравнение метода Гаусса с методом MathCad.
практическая работа [62,6 K], добавлен 05.12.2009Сущность и особенности языка программирования Си. Основные этапы алгоритма решения системы линейных алгебраических уравнений методом Гаусса, реализация программы для их расчета. Инструкции пользователя и программиста. Тестирование функции решения.
курсовая работа [153,9 K], добавлен 18.02.2013Рассмотрение двух способов решения систем линейных алгебраических уравнений: точечные и приближенные. Использование при программировании метода Гаусса с выбором главного элемента в матрице и принципа Зейделя. Применение простой итерации решения уравнения.
курсовая работа [879,8 K], добавлен 05.06.2012
