- •Г.Г КАШЕВАРОВА, Т.Б. ПЕРМЯКОВА
- •Предисловие
- •Введение
- •Общие сведения о математическом моделировании.
- •Численные методы
- •Элементы теории погрешности
- •Понятия мастера и надстройки
- •Глава 1. Основные понятия матричного исчисления. Матрицы в расчетах строительных объектов
- •1.1. Матрицы и векторы. Определения
- •1.2. Матрицы специального вида
- •1.3. Действия над матрицами
- •1.4. Нормы матрицы и вектора
- •1.5. Матрицы в задачах строительной механики
- •1.5.1. Матрицы влияния внутренних сил
- •1.5.2. Матричная форма расчета статически определимых ферм
- •1.5.3, Матричная форма метода сил
- •1.5.4. Матричная форма метода перемещений
- •1.6. Матрицы в расчетах инженерных сетей
- •1.7. Функции Excel для операций над матрицами
- •Категория: математические. Функции:
- •2.1. Системы линейных алгебраических уравнений
- •2.2.1. Метод Гаусса
- •2.2.2. Метод Гаусса для СЛАУ с ленточными матрицами
- •2.2.3. Метод прогонки
- •2.2.4. Метод (схема) Холецкого
- •2.3. Итерационные методы решения систем линейных алгебраических уравнений
- •2.3.1. Метод Якоби (простых итераций)
- •2.3.2. Метод Гаусса - Зейделя.
- •2.3.3. Условия сходимости итерационного процесса
- •2.5. Обусловленность задач и вычислений, или как узнать, что получены правильные ответы
- •2.6. Вычисление определителя
- •2.7. Вычисление обратной матрицы
- •2.8. Нахождение собственных значений и собственных векторов матриц
- •2.8.1. Вводные замечания
- •2.8.2. Методы развертывания вековых определителей
- •2.8.3. Итерационные методы определения максимального по модулю собственного значения
- •2.9.1. Реализация метода Гаусса средствами приложения Excel
- •Последовательность действий:
- •2.9.4. Реализация метода Зейделя средствами приложения Excel
- •Последовательность действий:
- •3.1. Отделение корней
- •3.2. Этап уточнения корня
- •3.2.1. Метод половинного деления (бисекций)
- •3.2.2.Метод хорд
- •3.2.3. Метод Ньютона (метод касательных)
- •3.2.4. Модифицированный метод Ньютона
- •3.3. Системы нелинейных уравнений
- •3.4. Реализация численных методов решения нелинейных уравнений средствами приложения Excel
- •3.4.1. Решение нелинейных уравнений
- •Последовательность действий
- •4.2.3. Интерполяционный полином Эрмита
- •4.2.4. Сплайн-интерполяция
- •Глава 4. Аппроксимация
- •4.1. Задача и способы аппроксимации
- •4.2. Интерполирование функций
- •4.2.1. Постановка задачи интерполирования
- •4.2.2. Интерполяционная формула Лагранжа
- •4.3. Среднеквадратичное приближение функций
- •4.3.1. Метод наименьших квадратов
- •4.3.4. Квадратичное (параболическое) приближение
- •4.3.4. Эмпирические формулы с двумя параметрами. Метод выравнивания
- •4.4. Решение задач аппроксимации с помощью электронных таблиц Excel
- •4.4.1. Построение линейной эмпирической формулы методом наименьших квадратов
- •Последовательность действий
- •Последовательность действий
- •5.1. Квадратурные формулы прямоугольников
- •5.2. Квадратурная формула трапеций
- •5.3. Квадратурная формула Симпсона
- •5.4. Реализация методов численного интегрирования средствами приложения Excel
- •Глава 6. Численные методы решения дифференциальных уравнений с начальными и краевыми условиями
- •6.1.1. Задачи Коши и краевые задачи
- •6.2.1.Классификация уравнений и типы задач
- •6.3. Численные методы решения задач Коши
- •6.3.1. Метод Эйлера
- •(геометрический метод решения задачи Коши)
- •6.4. Численные методы решения краевых задач
- •Разностная схема краевой задачи для обыкновенного дифференциального уравнения 2-го порядка
- •Конечно-разностная аппроксимация функций двух переменных
- •Сходимость метода конечных разностей
- •6.5. Вариационный подход к решению краевых задач
- •6.5.1. Основные понятия вариационного исчисления
- •6.5.2. Связь решения краевой задачи с нахождением минимума функционала
- •6.5.3. Метод Ритца
- •6.6.1. Решение задачи Коши методом Эйлера
- •Построение второй итерации
- •Последовательность действий.
- •Порядок построения графиков приближенных решений краевой задачи
- •Глава 7. Метод конечных элементов
- •7.1. Основные положения МКЭ
- •Построение расчетной модели
- •Аппроксимация искомой функции
- •Составление разрешающих уравнений
- •Решение системы линейных алгебраических уравнений
- •7.2.1. Классификация конечных элементов
- •Одномерный конечный элемент
- •Двухмерные конечные элементы.
- •элемента
- •Одномерный симплекс-элемент
- •Двухмерный треугольный симплекс-элемент
- •7.2.3. Интерполирование векторных величин
- •7.2.4. Разбиение области на конечные элементы
- •7.2.5 Нумерация узлов и элементов
- •7. 3. Основные соотношения МКЭ
- •7.3.1. Получение разрешающих уравнений на примере плоской задачи теории упругости
- •7.3.2. Примеры разрешающих уравнений в задачах расчета строительных объектов
- •7.4. Другие типы конечных элементов
- •7.4.1. Элементы Эрмита
- •7.5. Теоретическая и практическая сходимость МКЭ
- •7.6.1. Специализированные программные комплексы
- •7.6.2. Универсальные программные комплексы
- •8.1.1. Математическая модель задачи оптимизации
- •8.1. Общие сведения
- •8.1.2. Необходимые и достаточные условия экстремума функции
- •8.1.3. Классификация задач математического программирования
- •8.2. Постановка задачи оптимального проектирования
- •8.2.1. Определение входных и выходных параметров
- •8.2.2. Выбор целевой функции
- •8.2.3. Назначение ограничений
- •8.2.4. Нормирование управляемых и выходных параметров
- •8.2.5. Примеры постановок задач оптимального проектирования
- •8.3. Задачи линейного программирования
- •8.3.1. Общая постановка задачи ЛП
- •8.3.2. Геометрический смысл системы линейных неравенств с двумя неизвестными
- •8.3.4. Симплекс-метод решения задач линейного программирования
- •Задача об оптимальном плане выпуска продукции
- •Задача об оптимальном раскрое материалов (о минимизации отходов)
- •Задача о планировании смен на предприятии
- •Задача о покрытии местности при строительстве объектов
- •Транспортная задача
- •Задача о назначениях (проблема выбора)
- •8.3.6. Двойственные задачи в линейном программировании
- •8.4. Нелинейные задачи оптимизации
- •8.4.1. Выпуклые множества и выпуклые функции
- •8.4.2. Классификация численных методов решения нелинейных задач оптимизации
- •Основные этапы поиска экстремума
- •8.4.3. Численные методы одномерного поиска
- •Метод перебора или равномерного поиска
- •Метод дихотомии (или половинного деления)
- •Метод квадратичной интерполяции
- •Метод покоординатного спуска
- •Метод градиентного спуска
- •Метод наискорейшего спуска
- •Метод сопряженных градиентов
- •Метод Ньютона
- •Метод штрафных функций
- •8.5. Решение задач оптимизации с помощью электронных таблиц Excel
- •Литература
- •Оглавление
- •Численные методы решения задач строительства на ЭВМ
Ограничения записываем из условия, что вывозится весь произведенный на каждом заводе цемент (первые три) и что каждый ЖБК полностью обеспечивается цементом:
*11 +*12+*13+*14=150,
*21 +*22 +*2Э+*24=130,
*31 +*з2.+*зз+*з4=170,
* п + * 2 1 + * 3 i= 1 5 0 ,
*12+*22+*32=120,
*13+*23.+*33=80,
*14+*24-+*34=50,
*//>0 (/=1,2,3; 7=1,2,3,4).
Решение данной транспортной задачи с использованием приложения Microsoft Excel приведено в подразделе 8.5.
Задача о назначениях (проблема выбора)
Эта задача является частным случаем транспортной задачи
Постановка задачи. В распоряжении имеется п механизмов (бригад) и п различных видов работ. Производительность каждого механизма на различных работах, вообще говоря, различна. Обозначим через Су (/,у=1,2,..,л) производительность /-го механизма нау-й работе. Матрица С=[с,у] называется матрицей эффективностей или производительностей.
Требуется так распределить п механизмов на п работах, чтобы каждый механизм выполнял одну и только одну работу и чтобы при заданной производительности каждого механизма на каждой из работ
суммарный эффект был бы максимальным.
Обозначим через Ху переменную, равную единице, если /-й механизм назначен на j -ю работу, и равен нулю, если он на эту работу не назначен. В качестве целевой функции выбираем суммарную производительность всех механизмов
<8-74>
1= у=1 Ограничения записываем из условия, что каждый механизм
выполняет одну работу и что каждая работа обеспечивается одним механизмом:
Х(\ "Ь Xj2 "t" “Ь Xjn —1, |
i |
1,2,.., /7, |
|
X\j + *2y + •• + x„j = |
j |
= |
(8.75) |
n. |
■Пример 8.9. Задача о назначениях.
Имеются три бригады /?2, #з> каждая из которых может быть использована на каждой из 3-х строительной площадке с производительностью (в условных единицах), заданной в таблице 8.3:
|
|
|
Таблица 8.3 |
Строител. |
Производительность бригад |
||
площадка |
|
(у.е.) |
|
1 |
5, |
&2 |
В3 |
1 |
2 |
3 |
|
2 |
2 |
4 |
1 |
3 |
3 |
1 |
5 |
Требуется распределить бригады по одной на каждую строительную площадку так, чтобы суммарная производительность всех бригад была максимальной.
Обозначим Xij=1, если на i-ю стройплощадку назначенаj-я бригада, нху=0, если она на эту стройплощадку не назначена.
В качестве функции цели возьмите суммарную производительность всех бригад:
^птах ^11 ~Ь~'2‘Х \2 Т З дС]зТ 2Х21 ~^4Ди22 " ^ 2 3 ”^"3.X3i "^Хз2 .Т 5Х з з .
Систему ограничений запишите из условий, что каждая бригада выполняет работу на одной определенной стройплощадке и что каждая площадка обеспечена одной бригадой рабочих.
я)
Ь)
с)
xn +xa +xti- \ = Q,
xij+x2J+x3j - \ = 0,
X С: IV р
и
j = 1,2,3,
8.3.6. Двойственные задачи в линейном программировании
С каждой задачей линейного программирования связана так называемая двойственная задача [2, 20], которая формулируется по определенным правилам.
Теория двойственности полезна при проведении качественных исследований задач ЛП, когда необходимо не только найти оптимальное решение задачи, но и оценить влияние на оптимальное решение изменений в параметрах, представляющих собой исходную информацию задачи.
Обратимся вновь к задаче об оптимальном плане выпуска продукции, математическая модель которой записана в виде (8.64) - (8.66) и предположим, что некоторая организация решила закупить ресурсы предприятия, и необходимо установить оптимальные цены на эти ресурсы у и у2,... Ут• Здесь у, - единичная стоимость /-го ресурса (например, стоимость одного станка - для единиц оборудования, одного человеко-дня - для трудовых ресурсов, стоимость 1 кв.м, производственной площади - для зданий и т.п.).
Очевидно, что покупающая организация заинтересована в том, чтобы затраты ее на все ресурсы F, имеющиеся в известных количествах bh b2 bm были минимальны, то есть
Fmin =zbly t +Ьту2+-■■+ь1пут. |
(8.76) |
С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная от продажи ресурсов выручка была не меньше той суммы прибыли, которую предприятие может получить при переработке этих ресурсов в готовую продукцию.
Поскольку удельные расходы каждого вида ресурсов при производстве того или иного вида продукции известны (матрица удельных расходов ресурсов cty), то удовлетворение требований продавца можно записать в виде соответствующей системы ограничений:
|
а\\У\+а21у 2 +... + ат{у т>с,, |
|
|
|
а\2У\ + *22*2 + - + От2Ут ^ С2> |
/0 „ |
|
|
|
|
•//) |
|
а\пУ\+аг»У2+- + ашпУш * с н. |
|
|
Здесь |
ограничения |
соответствуют |
удовлетворению |
требований продавца |
при изготовлении каждого вида продукции. |
||||
Кроме |
того, |
должны |
быть |
наложены |
условия |
неотрицательности оценок ресурсов: |
|
|
|
||
|
У\ ~0, у 2 >0у....,ут>0. |
|
(8.78) |
Таким образом, математическая модель двойственной задачи представлена выражениями (8.76)-(8.78), а содержательная интерпретация ее может быть сформулирована следующим образом:__________________________________________________
найти такой набор цен (оценок) ресурсов Y = (у\,У2>--->Ут)>который обеспечит минимальные общие расходы на ресурсы при условии, что затраты на ресурсы при выпуске каждого вида продукции не меньше прибыли от реализации этой продукции.
Абстрагируясь от содержательной интерпретации параметров, рассмотрим формально две задачи (прямую и двойственную) линейного программирования. Двойственная задача получается из основной по следующим правилам
•Максимизация целевой функции в исходной задаче заменяется минимизацией в двойственной.
Каждому ограничению исходной задачи соответствует неизвестное
вдвойственной задаче. Причем, если это ограничение в виде неравенства, то соответствующее неизвестное неотрицательно. Если ограничение в виде уравнения, то соответствующее неизвестное
произвольно (т.е. не является неотрицательным).
•Каждому неизвестному в исходной задаче соответствует ограничение в двойственной задаче. Причем, если неизвестное неотрицательно, то соответствующее ограничение в виде неравенства. Если неизвестное произвольно, то соответствующее
ограничение в виде уравнения.
•Свободными членами новых ограничений служат коэффициенты ch С2,~сп исходной целевой функции.
Матрицы А коэффициентов при переменных в системах ограничений обеих задач являются транспонированными по отношению друг к другу.
Свободные члены b]t b2t...,bmограничений служат коэффициентами
новой целевой функции.
Из рассмотренных выше правил построения двойственной задачи вытекает, что основную задачу можно рассматривать как двойственную по отношению к своей двойственной.
■Пример 8.6. Сформулировать задачу, двойственную к следующей:
Z .mx = 2*1 +*2>
х{ + 2 х 2 > 5,
2хх+3*2 ^ 4, 4лг1-3*2 <8.
Поскольку исходная задача на максимум, то приводим ее к виду
Zmax = 2х{ + х2, |
|
|
(8.79) |
- JC - 2*2 ^ “5, |
Ух |
(8.80) |
|
2*, +3*2 |
<4, |
У2 |
|
4*, -3*2 ^8. |
Уъ |
|
Система ограничений (8.80) содержит три неравенства. Каждому из них соответствует неотрицательное неизвестное в двойственной задаче, т.е. уьЗ'г.Л > 0.
Неизвестное х2 в задаче (8.79 - 8.80) произвольны (т.е. не является неотрицательным). Следовательно, в двойственной задаче им соответствуют два ограничения в виде равенств
~У\ +2у2 +4уз=2.
-2yi +3у2-Зуз=1,
причем матрица коэффициентов новых ограничений является матрицей Ат, где А матрица коэффициентов старых ограничений (8.80).
двойственной. Коэффициентами линейной формы F свободные члены в системе ограничений исходной задг образом, получили задачу, двойственную к задаче (8.79 - 8 80)
“ ~AvI+4)j2 +8>*з,
( 8 . 8 J )
~У1 + 2 у 2 + 4 у 3 =2,
(8.82)
~2.У| +3у 2 - З у 3 =1,
у, > 0, / = 1,2,3.
( 8 . 8 3 )
Решение исходной задачи и ей двойственной имеют вид соответственно:
Zmax=l,3333 прих|=0 их2=1,3333, Fmin=l,3333 при yi=l,20, у2=0,60 иу3=0,20.
■ Пример 8.7. Для производства некоторой продукции используются три вида сырья 5„ (/=1,2,3), которое имеется соответственно в количествах Ь\=Ы, Ь2=24,63=31, и применяется три типа технологии 7}, (/=1,2,3).
Расход /-го вида сырья при работе по j -й технологии за единицу времени (например, в час) задается матрицей
2 |
1 |
2 |
К -]= 1 |
3 |
4 |
3 |
3 |
1 |
Выход продукта за единицу времени при использовании каждой из технологий задается матрицей строкой С=[3, 5, 9]. Найти такой оптимальный план работы, при котором из имеющихся запасов сырья выпускалось бы максимальное количество продукции.
Дать экономическую интерпретацию данной задачи и задачи, двойственной к ней.
Решение. Примем за неизвестные (проектные параметры) х, (/=1,2,3) время работы по /-й технологии. Тогда количество единиц выпускаемой продукции (план выпуска), которое требуется максимизировать, можно записать в виде: Z = 3 X I , + 5 X 2 , + 9 X 3 .
При этом будет израсходовано aixxx+ai2x2+а,ъх2 единиц /-го сырья (/=1,2,3).
Математическая формулировка задачи такова:
( 8 . 8 4 )
Z , „ M = 3 X I , + 5 X 2, - I 9 X }
2 *, + |
х2 +2 *з < 32, |
|
||
*, + |
Зх7 л-Ах-, < 25, |
(8.85) |
||
' |
, |
’ |
. |
|
3*| + |
3*2 + |
* 3 |
<31, |
|
Xj >0, |
j= 1,2,3. |
|
||
|
--* |
={9,0,4} |
nZmax=63. |
|
Оптимальное решение задачи X |
Таким образом, оптимальное время работы по 1-й технологии составляет 9 часов, по 3-й - 4 часа. А т.к. *2=0, то использовать 2-й тип технологии не следует. Максимальное количество продукции при этом составляет 63 единицы.
В соответствии с правилами, сформулированными выше, составим
задачу, двойственную задаче (8.84 - 8.85): |
|
||
^min =32^ + 2Sy2 +З1_у3, |
(8.86) |
||
2ух+ |
у 2 +3у3 >3, |
|
|
У1 + 3^ 2 +Зу3 >5, |
(8.87) |
||
2ух+4у2 + Уз ^9, |
|||
|
|||
У-, ^ 0, |
i = 1,2,3. |
|
Здесь целевая функция описывает стоимость используемого сырья, а ограничения - стоимость выпускаемой из этого сырья продукции при использовании каждого из трех типов технологии соответственно.
Оптимальное решение задачи (8 . 8 6 - 8.87) |
|
||
Y* ={0, |
2,1818, |
0,2727} и Fmin=63. |
|
Проанализируем |
полученные оптимальные решения. |
Сырье Si |
|
используется не полностью, потому что его цена равна нулю, |
* |
||
у х - 0 , т.е. |
|||
сырье, имеющееся в избытке, не ценится. Сырье S2 и Sз, цены которых |
|||
отличны от |
нуля, |
у 2 = 2,1818>0, Уз =0,2727>0, используется |
|
полностью. |
|
|
|
Для технологии Т2издержки вычисляются как |
|
||
у, +3у 2 +Зу3 |
= 1 0+3-2,1818+3-0,2727 = 6,3636 >5, |
т.е. превышают стоимость продукции, равную 5. Эта технология не рентабельна и поэтому не используется, т.е. *2 = 0 .