О разновидностях моделирования

Введение

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

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

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

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

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

В данной главе предполагается знание основ математики:

* теории дифференциальных уравнений;

* аппроксимации функций (включая интерполяцию и среднеквадратичные при­нижения);

* аналитической геометрии на плоскости и в пространстве;

* математической статистики;

* численных методов:

а) решения алгебраических и трансцендентных уравнений;

б) решения систем линейных алгебраических уравнений;

в) интегрирования обыкновенных дифференциальных уравнений и их систем (задача Кош и).

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

Понятие о компьютерном математическом моделировании

Примеры задач линейного программирования

1. Задача об испо л ьзовании ресурсов (задача планирования производства)

1.1. Для изготовления двух видов продукции и используют четыре вида ресурсов , , и . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в табл. 1 (цифры условные).

Таблица 1.

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции
		—
			–

 

Прибыль, получаемая от единицы продукции и , - соответственно 2 и 3 руб.

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

Решение. Составим экономико-математическую модель задачи.

Обозначим и — число единиц продукции соответственно и , запланированных к производству. Для их изготовления (см. табл. 1) потребуется () единиц ресурса , () единиц ресурса , () единиц ресурса и ; единиц ресурса . Так как потребление ресурсов , , и не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

(1)

По смыслу задачи переменные

, . (2)

Суммарная прибыль составит руб. от реализации продукции и руб. — от реализации продукции , т.е.

(3)

Итак, экономико-математическая модель задачи: найти такой план выпуска продукции , удовлетворяющий системе (1) и условию (2), при котором функция (3) принимает максимальное значение.

Задачу легко обобщить на случай выпуска п видов продукции с использованием т видов ресурсов.

Обозначим (j = 1, 2,..., п) — число единиц продукции , запланированной к производству; (i =1, 2,..., т) — запас ресурса , – число единиц ресурса , затрачиваемого на изготовление единицы продукции (числа часто называют технологическими коэффициентами); — прибыль от реализации единицы продукции .

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

(4)

и условию

, , (5)

при котором функция

(6)

принимает максимальное значение.

Задача о раскрое материалов

На раскрой (распил, обработку) поступает материал одного образца в количестве, а единиц. Требуется изготовить из него l разных комплектующих изделий в количествах, пропорциональных числам (условие комплектности). Каждая единица материала может быть раскроена п различными способами, причем использование i - го способа () дает единиц k-го изделия ().

Необходимо найти план раскроя, обеспечивающий максимальное число комплектов.

Составим экономико-математическую модель задачи.

Обозначим — число единиц материала, раскраиваемых i -м способом, и х — число изготавливаемых комплектов изделий.

Так как общее количество материала равно сумме его единиц, раскраиваемых различными способами, то

(17)

Требование комплектности выразится уравнениями

(18)

Очевидно, что

(19)

Экономико-математическая модель задачи: найти такое решение , удовлетворяющее системе уравнений (17) — (18) и условию (19), при котором функция принимает максимальное значение.

Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотношении 2:1:3 на распил поступают 195 бревен длиной 6 м. Определить план распила, обеспечивающий максимальное число комплектов. Составить экономико-математическую модель задачи.

Решение. Прежде всего, определим всевозможные способы распила бревен, указав соответствующее число получаемых при этом брусьев (табл. 3).

Таблица 3

Способ распила i	Число получаемых брусьев длиной, м
1,2	3,0	5,0
		—	—
			—
	—		—
	—	—

Обозначим: — число бревен, распиленных i-м способом ; х — число комплектов брусьев.

Учитывая, что все бревна должны быть распилены, а число брусьев каждого размера должно удовлетворять условию комплектности, экономико-математическая модель задачи примет вид:

при ограничениях:

Задачу о раскрое легко обобщить на случай т раскраиваемых материалов.

Пусть каждая единица j-го материала ( ) может быть раскроена п различными способами, причем использование i-го способа ( ) дает единиц k-го изделия ( ), а запас j-го материала равен единиц.

Обозначим — число единиц j-го материала, раскрываемого i-м способом.

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

и условию , при котором функция принимает максимальное значение.

Задача о потребностях сырья

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

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

 

Таблица 4

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количество сырья, кг
А	В
I
II
III
Прибыль от реализации одного изделия, руб.

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

.

Общая прибыль от реализации изделий вида А и изделий вида В составит . Это и будет целевая функция.

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

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

;

Эти прямые изображены на рис. 4.1. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой — нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае — другая полуплоскость. Найдем, например, полуплоскость, определяемую неравенством

Для этого, построив прямую , возьмем какую-нибудь точку, принадлежащую одной из двух полученных полуплоскостей, например, точку O(0,0). Координаты этой точки удовлетворяют неравенству

Значит, полуплоскость, которой принадлежит точка O(0,0), определяется неравенством

Это и показано стрелками на рис. 6.1.

Пересечение полученных полуплоскостей и определяет многоугольник решений данной задачи.

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

Чтобы найти указанную точку, построим вектор С = (30, 40) н прямую , где h — некоторая постоянная, такая, что прямая имеет общие точки с многоугольником решений. Положим, например, h = 480 и построим прямую (см. рис.1).

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

Далее, полагая h равным некоторому числу больше 480, мы будем получать различные параллельные прямые. Если они имеют общие точки с многоугольником решений, то эти точки определяют планы произ­водства изделий А и В, при которых прибыль от их реализации превзойдет 480 руб. Перемещая построенную прямую

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

Найдем координаты точки В как точки пересечения прямых

.

Решив эту систему уравнений, получим , . Следовательно, если предприятие изготовит 12 изделий вида А и 18 изделий вида В, то оно получит максимальную прибыль, равную

.

 

Варианты заданий

 

Вариант 1

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 2

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 3

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 4

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 5

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

 

Вариант 6

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 7

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 8

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 9

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 10

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

 

Вариант 11

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 12

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 13

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 14

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 15

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

 

Вариант 16

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 17

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 18

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 19

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 20

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

 

Вариант 21

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 22

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 23

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

Вариант 24

 

Вид сырья	Нормы расхода сырья на одно изделие, кг	Общее количества сырья, кг
А	В
I II III
Прибыль от реализации одного изделия, руб.

 

[1] В ряде работ по математическому программированию стандартную задачу называют симметричной, а каноническую – основной.

Введение

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

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

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

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

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

В данной главе предполагается знание основ математики:

* теории дифференциальных уравнений;

* аппроксимации функций (включая интерполяцию и среднеквадратичные при­нижения);

* аналитической геометрии на плоскости и в пространстве;

* математической статистики;

* численных методов:

а) решения алгебраических и трансцендентных уравнений;

б) решения систем линейных алгебраических уравнений;

в) интегрирования обыкновенных дифференциальных уравнений и их систем (задача Кош и).

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

О разновидностях моделирования

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

Что же такое модель? Что общего между игрушечным корабликом и рисунком на экране компьютера, изображающим сложную математическую абстракцию? И все же общее есть: и в том, и в другом случае мы имеем образ реального объекта или явления, «заместителя» некоторого «оригинала», воспроизводящего его с той или иной достоверностью и подробностью. Или то же самое другими словами: модель является представлением объекта в некоторой форме, отличной от формы его реального существования.

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

В моделировании есть два заметно разных пути. Модель может быть похожей копией объекта, выполненной из другого материала, в другом масштабе, с отсутствием ряда деталей. Например, это игрушечный кораблик, самолетик, домик из кубиков и множество других натурных моделей. Модель может, однако, отображать реальность более абстрактно - словесным описанием в свободной форме, описанием, формализованным по каким-то правилам, математическими соотношениями и т.д.

В прикладных областях различают следующие виды абстрактных моделей:

· традиционное (прежде всего для теоретической физики, а также механики, химии, биологии, ряда других наук) математическое моделирование без какой-либо привязки к техническим средствам информатики;

· информационные модели и моделирование, имеющие приложения в информационных системах;

· вербальные (т.е. словесные, текстовые) языковые модели;

· информационные (компьютерные) технологии, которые надо делить

А) на инструментальное использование базовых универсальных программных средств (текстовых редакторов, СУБД, табличных процессоров, телекоммуникационных пакетов);

Б) на компьютерное моделирование, представляющее собой

• вычислительное (имитационное) моделирование;

• «визуализацию явлений и процессов» (графическое моделирование),

• «высокие» технологии, понимаемые как специализированные прикладные технологии, использующие компьютер (как правило, в режиме реального времени) в сочетании с измерительной аппаратурой, датчиками, сенсорами и т.д.

Итак, укрупненная классификация абстрактных (идеальных) моделей такова.

1. Вербальные (текстовые) модели. Эти модели используют последовательности предложений на формализованных диалектах естественного языка для описания той или иной области действительности (примерами такого рода моделей являются милицейский протокол, правила дорожного движения).

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

3. Информационные модели - класс знаковых моделей, описывающих информационные процессы (возникновение, передачу, преобразование и использование информации) в системах самой разнообразной природы.

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

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

Основное содержание данной главы связано с прикладными математическими моделями, в реализации которых используются компьютеры. Это вызвано тем, что внутри информатики именно компьютерное математическое и компьютерное информационное моделирование могут рассматриваться как ее составные части. Компьютерное математическое моделирование связано с информатикой технологи­чески; использование компьютеров и соответствующих технологий обработки информации стало неотъемлемой и необходимой стороной работы физика, инжене­ра, экономиста, эколога, проектировщика ЭВМ и т.д. Неформализованные вер­бальные модели не имеют столь явно выраженной привязки к информатике - ни в принципиальном, ни в технологическом аспектах.