Задачи, решаемые методами ЛП, очень разнообразны по содержанию. Но их математические модели схожи и условно объединяются в три большие группы задач:
- транспортные задачи;
- задачи о составлении плана;
Транспортная задача
На двух торговых базах А и В имеется 30 гарнитуров мебели, по 15 на каждой. Всю мебель требуется доставить в два мебельных магазина, С и Д причем в С надо доставить 10 гарнитуров, а в Д - 20. Известно, что доставка одного гарнитура с базы А в магазин С обходится в одну денежную единицу, в магазин Д - в три денежных единицы. Соответственно с базы В в магазины С и Д : две и пять денежных единиц. Составить план перевозок так, чтобы стоимость всех перевозок была наименьшей.Данные задачи для удобства разметим в таблице. На пересечении строк и столбцов стоят числа, характеризующие стоимость соответствующих перевозок (табл. 3.1).
Таблица 3.1
Составим математическую модель задачи.
Необходимо ввести переменные. В формулировке вопроса говорится, что необходимо составить план перевозок. Обозначим через х 1 , х 2 количество гарнитуров, перевозимых с базы А в магазины С и Д соответственно, а через у 1 , у 2 - количество гарнитуров, перевозимых с базы В в магазины С и Д соответственно. Тогда количество мебели, вывозимое со склада А , равно (х 1 + х 2), а со склада В - (у 1 + у 2). Потребность магазина С равна 10 гарнитурам, и в него привезли (х 1 + у 1) штук, т. е. х 1 + у 1 = 10. Аналогично, для магазина Д имеем х 2 + у 2 = 20. Заметим, что потребности магазинов в точности равны количеству гарнитуров, имеющихся на складах, поэтому х 1 + у 2 = 15 и у 1 + у 2 = 15. Если бы со складов вы увезли меньше, чем по 15 комплектов, то магазинам не хватило бы мебели для удовлетворения их потребностей.
Итак, переменные х 1 , х 2 , у 1 , у 2 по смыслу задачи неотрицательны и удовлетворяют системе ограничений:
(3.1)
Обозначив через F транспортные расходы, посчитаем их. на перевозку одного комплекта мебели из А в С тратится одна ден. ед., на перевозку x 1 комплектов - x 1 ден. ед. Аналогично, на перевозку x 2 комплектов из А в Д затратится 3x 2 ден. ед.; из В в С - 2y 1 ден. ед., из В в Д - 5y 2 ден. ед.
Итак,
F = 1x 1 + 3x 2 + 2y 1 + 5y 2 → min (3.2)
(мы хотим, чтобы общая стоимость перевозок была минимальной).
Сформулируем задачу математически.
На множестве решений системы ограничений (3.1) найти такое решение, которое обращает в минимум целевую функцию F (3.2), или найти оптимальный план (x 1 , x 2, y 1 , y 2), определяемый системой ограничений (3.1) и целевой функцией (3.2).
Задача, которую мы рассмотрели может быть представлена в более общем виде, с любым числом поставщиков и потребителей.
В рассмотренной нами задаче наличие груза у поставщиков (15 + 15) равно общей потребности потребителей (10 + 20). Такая модель называется закрытой , а соответствующая задача - сбалансированной транспортной задачей.
В экономических расчетах немалую роль играют и так называемые открытые модели, в которых указанное равенство не соблюдается. Либо запас у поставщиков больше потребности у потребителей, либо спрос превышает наличие товара. заметим, что тогда в систему ограничений несбалансированной транспортной задачи наряду с уравнениями будут входить и неравенства.
Рассмотрим пример несбалансированной транспортной задачи .
В пунктах А
и В
расположены кирпичные заводы, а в С
и Д
- карьеры, снабжающие их песком. потребность заводов в песке меньше, чем производительность карьеров. Известно, сколько песка нужно каждому из заводов и сколько добывается в каждом карьере. Также известна стоимость перевозки 1 т песка из каждого карьера к заводам (числа на стрелочках). Нужно так спланировать снабжение заводов песком, чтобы затраты на перевозку были наименьшими. Данные задачи на схеме.
Постоим математическую модель задачи.
Введем переменные:
x
11 - количество тонн песка, перевозимого с карьера С
на завод А
;
x
12 - с карьера С
на завод А
;
x
21 - количество тонн песка в А
с карьера Д
;
x
22 - количество тонн песка с карьера Д
на завод В
.
На завод А
должно быть доставлено 40 т с обоих карьеров, значит x
11 + x
21 = 40, на завод В
должно быть доставлено 50 т, значит x
12 + x
22 = 50. Из карьера С
вывезено не более 70 т, т. е. x
11 + x
12 ≤ 70, аналогично x
21 + x
22 ≤ 30. Имеем систему ограничений:
(3.3)
И целевая функция F
, выражающая стоимость перевозок, имеет вид
F
= 2x
11 + 6x
12 + 5x
21 + 3x
22 →min. (3.4)
Задача о составлении плана
Некоторому заводу требуется составить оптимальный план выпуска двух видов изделий, которые обрабатываются на четырех видах машин. Известны определенные возможности и производительность оборудования; цена изделий, обеспечивающая прибыль заводу, составляет 4 тыс. руб. за изделие I вида, 6 тыс. руб. - за изделие II вида. Составить план выпуска этих изделий так, чтобы от реализации их завод получил наибольшую прибыль. В таблице указано время, необходимое для обработки каждого из двух видов изделий на оборудовании всех четырех видов (табл. 3.2).Таблица 3.2
Изделия |
Виды машин | |||
| 1 | 2 | 3 | 4 | |
| I | 1 | 0,5 | 1 | 0 |
| II | 1 | 1 | 0 | 1 |
| Возможное время работы машин | 18 | 12 | 12 | 9 |
Построим математическую модель.
В задаче необходимо определить план выпуска изделий, обозначим за x количество изделий I вида, за y - количество изделий II вида. Тогда посчитаем, сколько времени затратит первая машина на обработку всех производственных изделий. Она тратит одну единицу времени на одного изделие I вида, значит на x штук изделий потратит 1x ед. времени, на обработку y изделий II вида затратится 1y ед. времени. Всего резерв времени работы первой машины - 18 единиц времени. Значит, x + y ≤ 18. Аналогичные рассуждения со второй машиной, третьей и четвертой дадут систему ограничений:
(3.5)
Общая прибыль будет выражена в целевой функции:
F = 4x + 6y → max. (3.6)
Задача состоит в нахождении на множестве решений системы (3.5) такого решения, при котором значение целевой функции (3.6) было бы максимальным.
Задача составления смеси
Еще одна распространенная задача ЛП - задача о составлении смеси. Примером таких задач может быть задача о составлении таких смесей нефтепродуктов, которые бы удовлетворяли определенным техническим требованиям и были наиболее дешевыми по стоимости. Либо задачи о рационе, когда известна потребность в определенных веществах и содержание этих веществ в различных продуктах. Необходимо составить рацион так, чтобы удовлетворить потребности в необходимых веществах и при этом продуктовая корзина имела бы минимальную стоимость при заданных ценах на продукты.Практически подобные задачи ставятся, к примеру, в любом животноводческом хозяйстве и имеют очень большой спектр применения.
Рассмотрим пример. Для откорма цыплят на птицефабрике в их рацион необходимо включать не менее 33 единиц вещества А , 23 единиц питательного вещества В , 12 единиц С . Для откорма используются три вида корма. Данные о содержании питательных веществ в каждом виде корма заданы таблицей. Также известна стоимость кормов. Необходимо составить наиболее дешевый рацион (табл. 3.3).
Таблица 3.3
| Корма-продукты | Вещества | Стоимость 1 ед. корма | ||
| А | В | С | ||
| I | 4 | 3 | 1 | 20 |
| II | 3 | 2 | 1 | 20 |
| III | 2 | 1 | 2 | 10 |
Для понимания задачи можете представить себе, что вещества А , В , С - это жиры, белки, углеводы, а продукты I, II, III - то, чем кормят цыплят, например пшено, комбикорм, витаминные добавки. Тогда первая строка таблицы показывает содержание в одной единице пшена: 4 ед. белка, 3 ед. жиров, одной ед. углеводов. Вторая строка - содержание белков, жиров, углеводов в 1 ед. II продукта и т. д.
Если постановка задачи ясна, приступим к построению математической модели.
В качестве ответа на поставленную задачу мы должны предложить рацион, т. е. указать сколько и каких кормов взять, чтобы необходимое количество питательных веществ было соблюдено и при этом он стоил как можно дешевле.
Поэтому, обозначим за x 1 количество кормов типа I в рационе, за x 2 - количество кормов типа II и, соответственно, x 3 - количество корма III в рационе. Тогда, вещества А при употреблении такого рациона цыплята получат 4x 1 - при потреблении продуктов типа I, 3x 2 - при потреблении II продукта, 2x 3 - при потреблении III. Всего вещества А необходимо употребить по условию задачи не менее 33 единиц, следовательно 4x 1 + 3x 2 + 2x 3 ≥ 33.
Аналогично рассуждая с веществами В и С , имеем:
3x 1 + 2x 2 + 1x 3 ≥ 23 и x 1 + x 2 + 2x 3 ≥ 12.
Таким образом, получим систему ограничений:
(3.7)
Переменные неотрицательны по смыслу задачи. При этом стоимость рациона выражается функцией:
F = 20x 1 + 20x 2 + 10x 3 → min, (3.8)
т. к. 20, 20, 10 - стоимость одной ед. продуктов I, II, III типов соответственно, а в рационе их содержится x 1 , x 2 , x 3 единиц.
Система ограничений (3.7) вместе с целевой функцией (3.8) и составляют математическую модель исходной задачи. Решить ее - значит найти x 1 , x 2 , x 3 , удовлетворяющие системе ограничений и обращающие значение функции F в минимальное.
Расстановка типов судов по линиям
Построить такой план расстановки двух типов судов по трем линиям, который обеспечил бы максимум суммарной провозной способности флота, но не меньше заданного на линиях объема перевозок.| Тип судна | Производительность судов, млн. тонно-миль в сутки | Эксплуатационный период, сутки | ||
| 1-я линия | 2-я линия | 3-я линия | ||
| 1 | p 11 | p 12 | p 13 | s 1 |
| 2 | p 21 | p 22 | p 23 | s 2 |
| Заданный объем перевозки, млн. тонно-миль | V 1 | V 2 | V 3 | |
Экономико-математическая модель задачи.
Ограничения по эксплуатационному периоду:
x 1 /p 11 + x 2 /p 12 + x 3 /p 13 ≤ s 1
x 4 /p 21 + x 5 /p 22 + x 6 /p 23 ≤ s 2
Ограничения по поставкам:
s 1 x 1 + s 2 x 4 ≥ V 1
s 1 x 2 + s 2 x 5 ≥ V 2
s 1 x 3 + s 2 x 6 ≥ V 3
Целевая функция
p 11 x 1 +p 12 x 2 +p 13 x 3 +p 21 x 4 +p 22 x 5 +p 23 x 6 → max
Вопросы для самоконтроля
1. Постановка транспортной задачи. опишите построение математической модели.
2. Что такое сбалансированная и несбалансированная транспортная задача?
3. Что подсчитывается в целевой функции транспортной задачи?
4. Что отражает каждое неравенство системы ограничений задачи о плане?
5. Что отражает каждое неравенство системы ограничений задачи о смеси?
6. Что обозначают переменные в задаче о плане и задаче о смеси?
Пример 1.5.1.
Пусть некоторый экономический регион производит несколько (n) видов продуктов исключительно своими силами и только для населения данного региона. Предполагается, что технологический процесс отработан, а спрос населения на эти товары изучен. Надо определить годовой объем выпуска продуктов, с учетом того, что этот объем должен обеспечить как конечное, так и производственное потребление.
Составим математическую модель этой задачи. По ее условию даны: виды продуктов, спрос на них и технологический процесс; требуется найти объем выпуска каждого вида продукта.
Обозначим известные величины:
c i – спрос населения на i -й продукт (i =1,...,n ); a ij – количество i -го продукта, необходимое для выпуска единицы j -го продукта по данной технологии (i =1,...,n ; j =1,...,n );
х i – объем выпуска i -го продукта (i =1,...,n ); совокупность с =(c 1 ,..., c n ) называется вектором спроса, числа a ij – технологическими коэффициентами, а совокупность х =(х 1 ,..., х n ) – вектором выпуска.
По условию задачи вектор х распределяется на две части: на конечное потребление (вектор с ) и на воспроизводство (вектор х-с ). Вычислим ту часть вектора х которая идет на воспроизводство. По нашим обозначениям для производства х j количества j-го товара идет a ij · х j количества i -го товара.
Тогда сумма a i1 · х 1 +...+ a in · х n показывает ту величину i -го товара, которая нужна для всего выпуска х =(х 1 ,..., х n ).
Следовательно, должно выполняться равенство:
Распространяя это рассуждение на все виды продуктов, приходим к искомой модели:
Решая эту систему из n линейных уравнений относительно х 1 ,...,х n и найдем требуемый вектор выпуска.
Для того, чтобы написать эту модель в более компактной (векторной) форме, введем обозначения:
Квадратная (
)
-матрицаА
называется технологической
матрицей. Легко проверить, что наша
модель теперь запишется так:х-с=Ах
или
(1.6)
Мы получили классическую модель «Затраты – выпуск », автором которой является известный американский экономист В. Леонтьев.
Пример 1.5.2.
Нефтеперерабатывающий завод располагает двумя сортами нефти: сортом А в количестве 10 единиц, сортом В - 15 единиц. При переработке из нефти получаются два материала: бензин (обозначим Б ) и мазут (М ). Имеется три варианта технологического процесса переработки:
I : 1ед.А + 2ед.В дает 3ед.Б + 2ед.М
II: 2ед.А + 1ед.В дает 1ед.Б + 5ед.М
III : 2ед.А + 2ед.В дает 1ед.Б + 2ед.М
Цена бензина - 10 долл. за единицу, мазута - 1 долл. за единицу.
Требуется определить наиболее выгодное сочетание технологических процессов переработки имеющегося количества нефти.
Перед моделированием уточним следующие моменты. Из условия задачи следует, что «выгодность» технологического процесса для завода следует понимать в смысле получения максимального дохода от реализации своей готовой продукции (бензина и мазута). В связи с этим понятно, что «выбор (принятие) решения» завода состоит в определении того, какую технологию и сколько раз применить. Очевидно, что таких возможных вариантов достаточно много.
Обозначим неизвестные величины:
х i – количество использованияi -го технологического процесса(i=1,2,3) . Остальные параметры модели (запасы сортов нефти, цены бензина и мазута)известны .
Теперь одно конкретное решение завода сводится к выбору одного вектора х =(х 1 ,х 2 ,х 3 ) , для которого выручка завода равна(32х 1 +15х 2 +12х 3 ) долл. Здесь 32 долл. – это доход, полученный от одного применения первого технологического процесса (10 долл. ·3ед.Б + 1 долл. ·2ед.М = 32 долл.). Аналогичный смысл имеют коэффициенты 15 и 12 для второго и третьего технологических процессов соответственно. Учет запаса нефти приводит к следующим условиям:
для сорта А :
для сорта В :,
где в первом неравенстве коэффициенты 1, 2, 2 – это нормы расхода нефти сорта А для одноразового применения технологических процессов I ,II ,III соответственно. Коэффициенты второго неравенства имеют аналогичный смысл для нефти сорта В.
Математическая модель в целом имеет вид:
Найти такой вектор х = (х 1 ,х 2 ,х 3 ) , чтобы максимизировать
f(x) =32х 1 +15х 2 +12х 3
при выполнении условий:
Сокращенная форма этой записи такова:
при ограничениях
(1.7)
Мы получили так называемую задачу линейного программирования.
Модель (1.7.) является примером оптимизационной модели детерминированного типа (с вполне определенными элементами).
Пример1.5.3.
Инвестору требуется определить наилучший набор из акций, облигаций и других ценных бумаг для приобретения их на некоторую сумму с целью получения определенной прибыли с минимальным риском для себя. Прибыль на каждый доллар, вложенный в ценную бумагу j - го вида, характеризуется двумя показателями: ожидаемой прибылью и фактической прибылью. Для инвестора желательно, чтобы ожидаемая прибыль на один доллар вложений была для всего набора ценных бумаг не ниже заданной величины b .
Заметим, что для правильного моделирования этой задачи от математика требуются определенные базовые знания в области портфельной теории ценных бумаг.
Обозначим известные параметры задачи:
n
– число разновидностей ценных бумаг;
а
j
– фактическая прибыль (случайное число)
от j-го вида ценной бумаги;
–
ожидаемая прибыль отj
-го
вида ценной бумаги.
Обозначим неизвестные величины :
y j - средства, выделенные для приобретения ценных бумаг вида j .
По
нашим обозначениям вся инвестированная
сумма выражается как
.
Для упрощения модели введем новые
величины
.
Таким образом, х i - это доля от всех средств, выделяемая для приобретения ценных бумаг видаj .
Ясно, что
Из условия задачи видно, что цель инвестора - достижение определенного уровня прибыли с минимальным риском. Содержательно риск - это мера отклонения фактической прибыли от ожидаемой. Поэтому его можно отождествить с ковариацией прибыли для ценных бумаг вида i и вида j. Здесь М - обозначение математического ожидания.
Математическая модель исходной задачи имеет вид:
при ограничениях
,
,
,
. (1.8)
Мы получили известную модель Марковица для оптимизации структуры портфеля ценных бумаг.
Модель (1.8.) является примеров оптимизационной модели стохастического типа (с элементами случайности).
Пример1.5.4.
На базе торговой организации имеется n типов одного из товаров ассортиментного минимума. В магазин должен быть завезен только один из типов данного товара. Требуется выбрать тот тип товара, который целесообразно завести в магазин. Если товар типа j будет пользоваться спросом, то магазин от его реализации получит прибыльр j , если же он не будет пользоваться спросом - убытокq j .
Перед моделированием обсудим некоторые принципиальные моменты. В данной задаче лицом, принимающим решение (ЛПР), является магазин. Однако исход (получение максимальной прибыли) зависит не только от его решения, но и от того, будет ли завезенный товар пользоваться спросом, т. е. будет ли выкуплен населением (предполагается, что по какой-то причине у магазина нет возможности изучить спрос населения). Поэтому население может рассматриваться как второе ЛПР, выбирающее тип товара согласно своего предпочтения. Наихудшим для магазина «решением» населения является: «завезенный товар не пользуется спросом». Так что, для учета всевозможных ситуаций, магазину нужно считать население своим «противником» (условно), преследующим противоположную цель – минимизировать прибыль магазина.
Итак, имеем задачу принятия решения с двумя участниками, преследующими противоположные цели. Уточним, что магазин выбирает один из типов товаров для продажи (всего n вариантов решений), а население - один из типов товаров, который пользуется наибольшим спросом (n вариантов решений).
Для составления математической модели нарисуем таблицу с n строками и n столбцами (всего n 2 клеток) и условимся, что строки соответствуют выбору магазина, а столбики - выбору населения. Тогда клетка (i, j) соответствует той ситуации, когда магазин выбирает i -й тип товара (i -ю строку), а население выбирает j -й тип товара (j- ю столбик). В каждую клетку запишем числовую оценку (прибыль или убыток) соответствующей ситуации с точки зрения магазина:
Числа q i написаны с минусом для отражения убытка магазина; в каждой ситуации «выигрыш» населения (условно) равен «выигрышу» магазина, взятому с обратным знаком.
Сокращенный вид этой модели таков:
(1.9)
Мы получили так называемую матричную игру. Модель (1.9.) является примером игровых моделей принятия решения.
Всего, найдите в учебниках или справочниках формулы, характеризующие его закономерности. Заранее подставьте во те из параметров, которые являются константами. Теперь найдите неизвестную информацию о ходе процесса в той или иной его стадии, подставив в формулу известные данные о его ходе в данной стадии.
Например, необходимо моделировать изменение мощности, выделяющейся на резисторе, в зависимости от напряжения на ней. В этом случае, придется воспользоваться известным сочетанием формул: I=U/R, P=UI
При необходимости, составьте график или графиков обо всем ходе процесса. Для этого разбейте его ход на некоторое количество точек (чем их больше, тем точнее результат, но вычисления). Осуществите вычисления для каждой из точек. Особенно трудоемкими будет расчет в том случае, если независимо друг от друга меняется несколько параметров, поскольку осуществить его необходимо для всех их сочетаний.
Если объем расчетов значителен, воспользуйтесь вычислительной техникой. Используйте тот язык программирования, которым вы хорошо владеете. В частности, чтобы рассчитать изменение мощности на нагрузке сопротивлением в 100 Ом при изменении напряжения от 1000 до 10000 В с шагом в 1000 В (в реальности построить такую нагрузку затруднительно, поскольку мощность на ней достигнет мегаватта), можно такую программу на Бейсик:
10 R=100
20 FOR U=1000 TO 10000 STEP 1000
При желании, воспользуйтесь для моделирования одного процесса другим, подчиняющимся тем же закономерностям. Например, маятник можно заменить электрическим колебательным контуром, или наоборот. Иногда имеется возможность воспользоваться в качестве моделирующего тем же явлением, что и моделируемое, но в уменьшенном или увеличенном масштабе. Например, если взять уже упомянутое сопротивление в 100 Ом, но подавать на него напряжения в диапазоне не от 1000 до 10000, а от 1 до 10 В, то мощность, выделяемая на нем, будет изменяться не от 10000 до 1000000 Вт, а от 0,01 до 1 Вт. Такая уместится на столе, а выделяемую мощность можно будет измерить обычным калориметром. После этого результат измерения будет необходимо умножить на 1000000.
Учитывайте, что масштабированию поддаются не все явления. Например, известно, что если все детали теплового двигателя уменьшить или увеличить в одинаковое число раз, то есть, пропорционально, то велика вероятность, что он не заработает. Поэтому при изготовлении двигателей разных размеров увеличения или уменьшения для каждой из его деталей берут различные.
1. Математическое моделирование
и процесс создания математической модели.
Математическое моделирование представляет собой метод исследования объектов и процессов реального мира с помощью их приближенных описаний на языке математики - математических моделей.
Процесс создания математической модели условно можно разбить на ряд основных этапов:
1) построение математической модели;
2) постановка, исследование и решение соответствующих вычислительных задач;
3) проверка качества модели на практике и модификация модели.
Рассмотрим основное содержание этих этапов.
Построение математической модели. Математической моделью называется аналитическое выражение, которое находится в результате анализа некой физической системы или явления, включающей в себя несколько неизвестных параметров этой системы или явления, подлежащих определению на основе данных эксперимента. С помощью наблюдений и экспериментов, практики выявляются основные "характеристики" явления, которым сопоставляются некоторые величины. Как правило, эти величины принимают числовые значения, т. е. являются переменными, векторами, матрицами, функциями и т. д.
Установленным внутренним связям между "характеристиками" явления придается форма равенств, неравенств, уравнений и логических структур, связывающих величины, включенные в математическую модель. Таким образом, математическая модель становится записью на языке математики законов природы.
Подчеркнем, что математическая модель неизбежно представляет собой компромисс между бесконечной сложностью изучаемого явления и желаемой простотой его описания.
Математические модели часто разделяют на статические и динамические. Статическая модель описывает явление или ситуацию в предположении их завершенности, неизменности (т. е. в статике). Динамическая модель описывает, как протекает явление или изменяется ситуация от одного состояния к другому (т. е. в динамике). При использовании динамических моделей, как правило, задают начальное состояние системы, а затем исследуют изменение этого состояния во времени. В динамических моделях искомое решение часто является функцией времени у=у(t), переменная t в таких моделях, как правило, бывает выделенной и играет особую роль.
Постановка, исследование и решение вычислительных задач. Для того чтобы найти интересующие исследователя значения величин или выяснить характер из зависимости от других входящих в математическую модель величин, ставят, а затем решают математические задачи.
Выявим основные типы решаемых задач. Для этого все величины, включенные в математическую модель, условно разобьем на три группы:
1) исходные (входные) данные х,
2) параметры модели a,
3) искомое решение (выходные данные) у.
1). Наиболее часто решают так называемые прямые задачи, постановка которых выглядит следующим образом: по данному значению входного данного х при фиксированных значениях параметров a требуется найти решение у. Процесс решения прямой задачи можно рассматривать как математическое моделирование причинно-следственной связи, присущей явлению. Тогда входное данное х характеризует "причины" явления, которые задаются и варьируются в процессе исследования, а искомое решение у - "следствие".
Для того чтобы математическое описание было применимо не к единичному явлению, а к широкому кругу близких по природе явлений, в действительности строят не единичную математическую модель, а некоторое параметрическое семейство моделей. Выбор конкретной модели из этого семейства осуществляется фиксацией значений параметров модели a. Например, в роли таких параметров могут выступать некоторые из коэффициентов, входящих в уравнения.
2). Большую роль играет решение так называемых обратных задач, состоящих в определении входного данного х по данному значению у (параметры модели a, как и в прямой задаче, фиксированы). Решение обратной задачи - это в определенном смысле попытка выяснить, какие "причины" x привели к известному "следствию" у. Как правило, обратные задачи оказываются сложнее для решения, чем прямые.
3). Помимо двух рассмотренных типов задач следует упомянуть еще один тип - задачи идентификации. В широком смысле задача идентификации модели - это задача выбора среди множества всевозможных моделей той, которая наилучшим образом описывает изучаемое явление. В такой постановке эта задача выглядит как практически неразрешимая проблема. Чаще задачу идентификации понимают в узком смысле, как задачу выбора из заданного параметрического семейства моделей конкретной математической модели (с помощью выбора ее параметров a), с тем чтобы оптимальным в смысле некоторого критерия образом согласовать следствия из модели с результатами наблюдений.
Указанные три типа задач (прямые, обратные и задачи идентификации) будем называть вычислительными задачами. Для удобства изложения в дальнейшем независимо от типа решаемой задачи будем называть набор подлежащих определению величин искомым решением и обозначать через у, а набор величин - входным данным и обозначать через х.
Как правило, решение вычислительной задачи не удается выразить через входные данные в виде конечной формулы. Однако это совсем не означает, что решение такой задачи не может быть найдено. Существуют специальные методы, которые называют численными (или вычислительными). Они позволяют свести получение численного значения решения к последовательности арифметических операций над численными значениями входных данных. Однако для решения задач численные методы применялись довольно редко, так как их использование предполагает выполнение гигантского объема вычислений. Поэтому в большинстве случаев до появления ЭВМ приходилось избегать использования сложных математических моделей и исследовать явления в простейших ситуациях, когда возможно найти аналитическое решение. Несовершенство вычислительного аппарата становилось фактором, .сдерживающим широкое использование математических моделей в науке и технике.
Появление ЭВМ кардинально изменило ситуацию. Класс математических моделей, допускающих подробное исследование, резко расширился. Решение многих, еще недавно недоступных, вычислительных задач стало обыденной реальностью.
Проверка качества модели на практике и модификация модели . На этом этапе выясняют пригодность математической модели для описания исследуемого явления. Теоретические выводы и конкретные результаты, вытекающие из гипотетической математической модели, сопоставляют с экспериментальными данными. Если они противоречат друг другу, то выбранная модель непригодна и ее следует пересмотреть, вернувшись к первому этапу. Если же результаты совпадают с допустимой для описания данного явления точностью, то модель можно признать пригодной. Конечно, необходимо дополнительное исследование с целью установления степени достоверности модели и границ ее применимости.
Вопросы для повторения:
1. Что такое математическая модель?
2. Основные этапы построения математической модели?
3. Основные типы решаемых задач?
2. Основные этапы решения инженерной
задачи с применением ЭВМ
Решение инженерной задачи с использованием ЭВМ можно разбить на ряд последовательных этапов. Выделим следующие этапы:
1) постановка проблемы;
2) выбор или построение математической модели;
3) постановка вычислительной задачи;
4) предварительный (предмашинный) анализ свойств вычислительной задачи;
5) выбор или построение численного метода;
6) алгоритмизация и программирование;
7) отладка программы;
8) счет по программе;
9) обработка и интерпретация результатов;
10) использование результатов и коррекция математической модели.
Постановка проблемы . Первоначально прикладная задача бывает сформулирована в самом общем виде:
Исследовать некоторое явление,
Спроектировать устройство, обладающее заданными свойствами,
Дать прогноз поведения некоторого объекта в определенных условиях и т. д.
На данной стадии происходит конкретизация постановки задачи. Первостепенное внимание при этом уделяется выяснению цели исследования.
Этот очень важный и ответственный этап завершается конкретной формулировкой проблемы на языке, принятом в данной предметной области. Знание возможностей, которые дает применение ЭВМ, может оказать существенное влияние на окончательную формулировку проблемы.
Выбор или построение математической модели. Для последующего анализа исследуемого явления или объекта необходимо дать его формализованное описание на языке математики, т. е. построить математическую модель. Часто имеется возможность выбора модели среди известных и принятых для описания соответствующих процессов, но нередко требуется и существенная модификация известной модели, а иногда возникает необходимость в построении принципиально новой модели.
Постановка вычислительной задачи. На основе принятой математической модели формулируют вычислительную задачу (или ряд таких задач). Анализируя результаты ее решения, исследователь предполагает получить ответы на интересующие его вопросы.
Предварительный анализ свойств вычислительной задачи. На этом этапе проводят предварительное (предмашинное) исследование свойств вычислительной задачи, выяснению вопросов существования и единственности решения, а также исследованию устойчивости решения задачи к погрешностям входных данных.
Выбор или построение численного метода. Для решения вычислительной задачи на ЭВМ требуется использование численных методов.
Часто решение инженерной задачи сводится к последовательному решению стандартных вычислительных задач, для которых разработаны эффективные численные методы. В этой ситуации происходит либо выбор среди известных методов, либо их адаптация к особенностям решаемой задачи. Однако если возникающая вычислительная задача является новой, то не исключено, что для ее решения не существует готовых методов.
Для решения одной и той же вычислительной задачи обычно может быть использовано несколько методов. Необходимо знать особенности этих методов, критерии, по которым оценивается их качество, чтобы выбрать метод, позволяющий решить проблему наиболее эффективным образом. Здесь выбор далеко не однозначен. Он существенно зависит от требований, предъявляемых к решению, от имеющихся в наличии ресурсов, от доступной для использования вычислительной техники и т. д.
Алгоритмизация и программирование. Как правило, выбранный на предыдущем этапе численный метод содержит только принципиальную схему решения задачи, не включающую многие детали, без которых невозможна реализация метода на ЭВМ. Необходима подробная детализация всех этапов вычислений, для того чтобы получить реализуемый на ЭВМ алгоритм. Составление программы сводится к переводу этого алгоритма на выбранный язык программирования.
Существуют библиотеки из которых пользователи из готовых модулей свои программы, либо, в крайнем случае, приходится программу писать с «нуля».
Отладка программы. На этом этапе с помощью ЭВМ выявляют и исправляют ошибки в программе.
После устранения ошибок программирования необходимо провести тщательное тестирование программы - проверку правильности ее работы на специально отобранных тестовых задачах, имеющих известные решения.
Счет по программе. На этом этапе происходит решение задачи на ЭВМ по составленной программе в автоматическом режиме. Этот процесс, в ходе которого входные данные с помощью ЭВМ преобразуются в результат, называют вычислительным процессом. Как правило, счет повторяется многократно с различными входными данными для получения достаточно полной картины зависимости от них решения задачи.
Обработка и интерпретация результатов . Полученные в результате расчетов на ЭВМ выходные данные, как правило, представляют собой большие массивы чисел, которые потом представляются в удобной для восприятия форме.
Использование результатов и коррекция математическое модели. Завершающий этап состоит в использовании результатов расчетов в практической деятельности, иначе говоря, во внедрении результатов.
Очень часто анализ результатов, проведенный на этапе их обработки и интерпретации, указывает на несовершенство используемой математической модели и необходимость ее коррекции. В таком случае математическую модель модифицируют (при этом она, как правило, усложняется) и начинают новый цикл решения задачи.
Вопросы для повторения:
1. Основные этапы решение инженерной задачи с использованием ЭВМ?
3. Вычислительный эксперимент
Создание математических моделей и решение инженерных задач с применением ЭВМ требует выполнения большого объема работ. Нетрудно заметить аналогию с соответствующими работами, проводимыми при организации натурных экспериментов: составление программы экспериментов, создание экспериментальной установки, выполнение контрольных экспериментов, проведение серийных опытов) обработка экспериментальных данных и их интерпретация и т. д. Однако вычислительный эксперимент проводится не над реальным объектом, а над его математической моделью, и роль экспериментальной установки играет оснащенная специально разработанной программой ЭВМ. В связи с этим естественно рассматривать проведение больших комплексных расчетов при решении инженерных и научно-технических задач как вычислительный эксперимент, а описанную в предыдущем параграфе последовательность этапов решения как один его цикл.
Отметим некоторые достоинства вычислительного эксперимента по сравнению с натуральным:
1. Вычислительный эксперимент, как правило, дешевле физического.
2. В этот эксперимент можно легко и безопасно вмешиваться.
3. Его можно повторить еще раз (если в этом есть необходимость) и прервать в любой момент.
4. В ходе этого эксперимента можно смоделировать условия, которые нельзя создать в лаборатории.
Заметим, что в ряде случаев проведение натурного эксперимента затруднено (а иногда и невозможно), так как изучаются быстропротекающие процессы, исследуются труднодоступные или вообще пока недоступные объекты. Часто проведение полномасштабного натурного эксперимента сопряжено с губительными или непредсказуемыми последствиями (ядерная война, поворот сибирских рек) или с опасностью для жизни или здоровья людей. Нередко требуется исследование и прогнозирование результатов катастрофических явлений (авария ядерного реактора АЭС , глобальное потепление климата, землетрясение). В этих случаях вычислительный эксперимент может стать основным средством исследования. Заметим, что с его помощью оказывается возможным прогнозировать свойства новых, еще не созданных конструкций и материалов на стадии их проектирования.
Существенным недостатком вычислительного эксперимента является то, что применимость его результатов ограничена рамками принятой математической модели.
Создание нового изделия или технологического процесса предполагает выбор среди большого числа альтернативных вариантов, а также оптимизацию по ряду параметров. Поэтому в ходе вычислительного эксперимента расчёты проводятся многократно с разными значениями входных параметров. Для получения нужных результатов с требуемой точностью и в приемлемые сроки необходимо, чтобы на расчет каждого варианта тратилось минимальное время.
Разработка программного обеспечения вычислительного эксперимента в конкретной области инженерной деятельности приводит к созданию крупного программного комплекса. Он состоит из связанных между собой прикладных программ и системных средств, включающих средства, предоставляемые пользователю для управления ходом вычислительного эксперимента, обработки и представления его результатов. Такой комплекс программ иногда называют проблемно-ориентированным пакетом прикладных программ.
Вопросы для повторения:
1. Достоинства вычислительного эксперимента по сравнению с натуральным?
2. Недостатки вычислительного эксперимента?
4. Простейшие методы решения задач
4.1. Поиск корня функции.
Метод деления отрезка по полам (метод Вилли).
Делим отрезок пополам (АС =СВ ). Выбираем половину, в которой функция пересекает ось 0х , затем обозначаем С за В , т. е. С=В и снова делим пополам. Выбор половины осуществляется произведением ¦(А )´¦(В ). Если произведение больше 0, то корня нет.
Метод хорд (секущих).
(В-А )/2£E n ³log 2((В-А )/2)
(y-y 0)(x-x 1)=(y-y 1)(x-x 0)
y =0; y 0(x-x 1)=y 1(x-x 0)
При построении математической модели системы можно выделить несколько этапов.
1-й этап. Постановка задачи. Этапу предшествует возникновение ситуаций или проблем, осознание которых приводит к мысли их обобщения или решения для последующего достижения какого-либо эффекта. Исходя из этого, объект описывается, отмечаются вопросы, подлежащие решению, и ставится цель исследования. Здесь необходимо уяснить, что мы хотим получить в результате исследований. Предварительно нужно оценить, нельзя ли получить эти результаты другим, более дешевым или доступным путем.
2-й этап. Определение задачи. Исследователь старается определить, к какому виду относится объект, описывает параметры состояния объекта, переменные, характеристики, факторы внешней среды. Необходимо познать закономерности внутренней организации объекта, очертить границы объекта, построить его структуру. Эта работа называется идентификацией системы. Отсюда выбирается задача исследования, которая может решать вопросы: оптимизации, сравнения, оценки, прогноза, анализа чувствительности, выявления функциональных соотношений и т.п.
Концептуальная модель позволяет оценить положение системы во внешней среде, выявить необходимые ресурсы для ее функционирования, влияние факторов внешней среды и то, что мы ожидаем на выходе.
Необходимость проведения исследования возникает из реальных ситуаций, складывающихся в процессе работы системы, когда они в чем-либо начинают не удовлетворять каким-либо старым или новым требованиям. Если недостатки очевидны и известны методы их устранения, то нет необходимости в исследованиях.
Исходя из задачи исследования, можно определить назначение математической модели, которая должна быть построена для исследования. Такие модели могут решать задачи:
· выявления функциональных соотношений, заключающихся в определении количественных зависимостей между входными фактора ми модели и выходными характеристиками исследуемого объекта;
· анализа чувствительности, заключающегося в установлении факторов, которые в большей степени влияют на интересующие исследователя выходные характеристики системы;
· прогноза - оценки поведения системы при некотором предполагаемом сочетании внешних условий;
· оценки - определения, насколько хорошо исследуемый объект будет соответствовать некоторым критериям;
· сравнения, заключающегося в сопоставлении ограниченного числа альтернативных вариантов систем или же в сопоставлении нескольких предлагаемых принципов или методов действия;
· оптимизации, состоящей в точном определении такого сочетания переменных управления, при которых обеспечивается экстремальное значение целевой функции.
Выбор задачи определяет процесс создания и экспериментальной проверки модели.
Любое исследование должно начинаться с построения плана,включающего обследование системы и анализ ее функционирования. В плане должны быть предусмотрены:
· описание функций, реализуемых объектом;
· определение взаимодействий всех систем и элементов объекта;
· определение зависимости между входными и выходными переменными и влияние переменных управляющих воздействий на эти зависимости;
· определение экономических показателей функционирования системы.
Результаты обследования системы и окружающей среды представляются в виде описания процесса функционирования, которое используется для идентификации системы. Идентифицировать систему - значит выявить и изучить ее, а также:
Получить более полную характеристику системы и ее поведения;
Познать объективные закономерности ее внутренней организации;
Очертить ее границы;
Указать на вход, процесс и выход;
Определить ограничения на них;
Построить ее структурную и математическую модели;
Описать ее на каком-либо формальном абстрактном языке;
Определить цели, принуждающие связи, критерии действия системы.
После идентификации системы строится концептуальная модель,являющаяся «идеологической» основой будущей математической модели. Именно в ней отражается состав критериев оптимальности и ограничений, определяющих целевую направленность модели. Перевод на этапе формализации качественных зависимостей в количественные преобразует критерий оптимальности в целевую функцию, ограничения - в уравнения связи, концептуальную модель - в математическую.
На основе концептуальной модели можно построить факторную модель, которая устанавливает логическую связь между параметрами объекта, входными и выходными переменными, факторами внешней среды и параметрами управления, а также учитывать обратные связи в системе.
3-й этап. Составление математической модели. Вид математической модели в значительной степени зависит от цели исследования. Математическая модель может быть в виде математического выражения, представляющего собой алгебраическое уравнение, или неравенство, не имеющее разветвления вычислительного процесса при определении любых переменных состояния модели, целевой функции и уравнений связи.
Для построения такой модели формулируются следующие понятия:
· критерий оптимальности - показатель, выбираемый исследователем, имеющий, как правило, экологический смысл, который служит для формализации конкретной цели управления объектом исследования и выражаемый при помощи целевой функции;
· целевая функция - характеристика объекта, установленная из условия дальнейшего поиска критерия оптимальности, математически связывающая между собой те или иные факторы объекта исследования. Целевая функция и критерий оптимальности - разные понятия. Они могут быть описаны функциями одного и того же вида или же разными функциями;
· ограничения - пределы, сужающие область осуществимых, приемлемых или допустимых решений и фиксирующие основные внутренние и внешние свойства объекта. Ограничения определяют область исследования, протекания процессов, пределы изменения параметров и факторов объекта.
Следующим этапом построения системы является формирование математической модели, включающее в себя несколько видов работ: математическую формализацию, численное представление, анализ модели и выбор метода ее решения.
Математическая формализация осуществляется по концептуальной модели. При формализации рассматривают три основные ситуации:
1) известны уравнения, описывающие поведение объекта. В этом случае решением прямой задачи можно найти реакцию объекта на заданный входной сигнал;
2) обратная задача, когда по заданному математическому описанию и известной реакции необходимо найти входной сигнал, вызывающий этот отклик;
3)математическое описание объекта неизвестно, но имеются или могут быть заданы совокупности входных и соответствующих им выходных сигналов. В этом случае имеем дело с задачей идентификации объекта.
При моделировании производственно-экологических объектов в третьей ситуации при решении задачи идентификации используется подход, предложенный Н. Винером, и известный как метод «черного ящика». В качестве «черного ящика» рассматривается объект в целом, вследствие его сложности. Так как внутреннее устройство объекта неизвестно, мы можем изучить «черный ящик», найдя входы и выходы. Сопоставляя входы и выходы, можно написать соотношение
Y = АХ,
где X - вектор входных параметров; Y - вектор выходных параметров; А - оператор объекта, преобразующий Х в Y. Для описания объекта в виде математической зависимости в задачах идентификации используются методы регрессивного анализа. При этом возможно описание объекта множеством математических моделей, так как нельзя вынести обоснованного суждения о его внутреннем устройстве.
Основой выбора метода математического описания является знание физической природы функционирования описываемого объекта достаточно широкого круга эколого-математических методов, возможностей и особенностей ЭВМ, на которой планируется проведение моделирования. Для многих рассматриваемых явлений имеется достаточно много известных математических описаний и типовых математических моделей. При развитой системе математического обеспечения ЭВМ целый ряд процедур моделирования можно осуществит с помощью стандартных программ.
Оригинальные математические модели можно написать на основе проведенных исследований систем и апробированных в реалы ной обстановке. Для проведения новых исследований такие модели корректируются под новые условия.
Математические модели элементарных процессов, физической природа которых известна, записываются в виде тех формул и зависимостей, которые установлены для этих процессов. Как правило, статические задачи выражаются в виде алгебраических выражений, динамические - в виде дифференциальных или конечно-разностных уравнений.
Численное представление модели производится для подготовки ее к реализации на ЭВМ. Задание числовых значений трудностей не представляет. Осложнения встречаются при компактном представлении обширной статистической информации и результатов экспериментов.
Основными методами преобразования табличных значений к аналитическому виду являются: интерполяция, аппроксимация и экстраполяция.
Интерполяция - приближенное или точное нахождение какой-либо величины по известным отдельным значениям этой же или других величин, связанных с ней.
Аппроксимация - замена одних математических объектов другими, в том или ином смысле близкими к исходным. Аппроксимация позволяет исследовать числовые характеристики и качественные свойства объекта, сводя задачу к изучению более простых или более удобных объектов.
Экстраполяция - продолжение функции за пределы ее области определения, при котором продолженная функция принадлежит заданному классу. Экстраполяция функции обычно производится с помощью формул, в которых использована информация о поведении функций в некотором конечном наборе точек, называемых узлами экстраполяции, принадлежащими к области определения.
Следующим этапом построения является анализ полученной модели и выбор метода ее решения. Основой для вычисления значений выходных характеристик модели служит составленный на ее базе алгоритм решения задачи на ЭВМ. Разработка и программирование такого алгоритма, как правило, не встречают принципиальных трудностей.
Более сложной является организация вычислительного процесса для определения выходных характеристик, лежащих в допустимых областях, особенно для многофакторных моделей. Еще сложнее - поиск решений по оптимизационным моделям. Самая совершенная и адекватная описываемому объекту математическая модель без нахождения оптимального значения бесполезна, она не может быть использована.
Основную роль при разработке алгоритма поиска оптимальны решений играют характер факторов математической модели, чисуи критериев оптимальности, вид целевой функции и уравнений связи Вид целевой функции и ограничений определяет выбор одного и трех основных методов решения эколого-математических моделей:
· аналитического исследования;
· исследования при помощи численных методов;
· исследования алгоритмических моделей с помощью методов экспериментальной оптимизации на ЭВМ.
Аналитические методы отличаются тем, что помимо точного значения искомых переменных они могут давать оптимальное решение в виде готовой формулы, куда входят характеристики внешней среды и начальные условия, которые исследователь может изменять в широких пределах, не меняя самой формулы.
Численные методы дают возможность получить решение путем многократного вычисления по определенному алгоритму, реализующему тот или иной численный метод. В качестве исходных данных для вычисления используются числовые значения параметре объекта, внешней среды и начальных условий. Численные методы являются итеративными процедурами: для проведения следующего шага расчетов (при новом значении управляемых переменных) пользуются результаты предыдущих расчетов, что позволяет получать в процессе вычислений улучшенные результаты и тем самым находить оптимальное решение.
Свойства конкретной алгоритмической модели, на которой базируется алгоритм поиска оптимального решения, например ее линейность или выпуклость, могут быть определены только в процессе экспериментирования с ней, в связи с чем для решения моделей этого класса используются так называемые методы экспериментальной оптимизации на ЭВМ. При использовании этих метод производится пошаговое приближение к оптимальному решению на основе результатов расчета по алгоритму, моделирующему работу исследуемой системы. Методы базируются на принципах поиска оптимальных решений в численных методах, но в отличие от них все действия по разработке алгоритма и программы оптимизации выполняет разработчик модели.
Имитационное моделирование задач, содержащих случайные параметры, принято называть статистическим моделированием.
Заключительным шагом создания модели является составление ее описания, которое содержит сведения, необходимые для изучения модели, ее дальнейшего использования, а также все ограничения и допущения. Тщательный и полный учет факторов при построении модели и формулировке допущений позволяет оценить точность модели, избежать ошибок при интерпретации ее результатов.
· 4-й этап . Вычисления. При решении задачи необходимо тщательно разобраться с размерностью всех величин, входящих в математическую модель, и определить границы (пределы), в которых будет лежать искомая целевая функция, а также требуемую точность вычислений. Если возможно, то вычисления проводятся при неизменных условиях по несколько раз, чтобы убедиться, что целевая функция не изменяется.
· 5-й этап . Выдача результатов. Результаты исследования объекта могут выдаваться в устной или письменной форме. Они должны включать в себя краткое описание объекта исследования, цели исследования, математическую модель, допущения, принятые при выборе математической модели, основные результаты вычислений, обобщения и выводы.
