Методология математического моделирования

Размещено на http://allbest.ru

Оглавление

Введение

1. Задачи линейного программирования

1.1 Решение задачи линейного программирования графическим методом

1.2 Решение задачи линейного программирования средствами MS Excel

2. Понятие транспортной задачи и ее типы

2.2 Решение транспортной задачи методом северо-западного угла

2.3 Решение транспортной задачи средствами MS Excel

Список литературы



Введение

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

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

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

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

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

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



1. Задачи линейного программирования

1.1 Решение задачи линейного программирования графическим методом

Найдем наименьшее значение линейной функции графическим методом. F = -9x₁+x₂ > max, при системе ограничений:

-2x₁+x₂?-4

8x₁+x₂?8

x₁-5x₂?-5

2x₁-x₂?2

x₁?0 x₂?0



Область допустимых решений представляет собой линию.

Прямая F(x) = const пересекает область в точке C.

Так как точка C получена в результате пересечения прямых (2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

8x₁+x₂=8 x₁-5x₂=-5

Решив систему уравнений, получим:

x₁ = 0.8537, x₂ = 1.1707

Откуда найдем минимальное значение целевой функции:

F(X) = -9*0.8537 + 1*1.1707 = -6.5122.

Необходимо найти максимальное значение целевой функции

F = -4x₁+5x₂ > max, при системе ограничений:

7x1+9x2?63	(1)
x1-2x2?6	(2)
7x1+2x2?14	(3)
-x1+x2?5	(4)
x1?0	(5)
x2?0	(6)

Построим область допустимых решений, т.е. решим графически систему неравенств.

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



Задача не имеет допустимых решений.

ОДР представляет собой пустое множество

1.2 Решение задачи линейного программирования средствами MS Excel

F = -4x₁+5x₂ > min, при системе ограничений:

7x1+9x2?63	(1)
x1-2x2?6	(2)
7x1+2x2?14	(3)
-x1+x2?5	(4)
x1?0	(5)
x2?0	(6)

F = -4x₁+5x₂ > min, при системе ограничений:

7x1+9x2?63	(1)
x1-2x2?6	(2)
7x1+2x2?14	(3)
-x1+x2?5	(4)
x1?0	(5)
x2?0	(6)



2. Понятие транспортной задачи и ее типы

Транспортная задача (задача Монжа -- Канторовича) -Математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача по теории сложности вычислений входит в класс сложности P. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Транспортная задача (классическая) -- задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

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



2.1 Решение транспортной задачи методом северо-западного угла

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	1	13	8	60
A 2	2	3	4	30
A 3	4	8	6	50
Потребность	40	80	80

Требуется составить план перевозок, при котором общая стоимость перевозок минимальная.

Решение: Найдем начальное решение методом северо-западного угла.

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

Запасы поставщиков:

60 + 30 + 50 =

140 единиц продукции.

Потребность потребителей:

40 + 80 + 80 =

200 единиц продукции.

Разница в 60 единиц продукции.

Введем в рассмотрение фиктивного поставщика A₄, с запасом продукции равным 60 единиц.

Стоимость доставки единицы продукции от поставщика A₄ ко всем потребителям примем равной нулю. (см. таблицу 1)

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

Согласно условию задачи составим таблицу. (тарифы маршрутов располагаются в нижнем правом углу ячейки)

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

От северо-запада к юго-востоку.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	1	13	8	60
A 2	2	3	4	30
A 3	4	8	6	50
A 4	0	0	0	60
Потребность	40	80	80

От поставщика A₁ к потребителю B₁ будем доставлять min = { 60 , 40 } = 40 единиц продукции.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	13	8	60 20
A 2	2	3	4	30
A 3	4	8	6	50
A 4	0	0	0	60
Потребность	40 0	80	80

От поставщика A₁ к потребителю B₂ будем доставлять min = { 20 , 80 } = 20 единиц продукции.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	20 13	8	60 0
A 2	2	3	4	30
A 3	4	8	6	50
A 4	0	0	0	60
Потребность	40 0	80 60	80

От поставщика A₂ к потребителю B₂ будем доставлять min = { 30 , 60 } = 30 единиц продукции.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	20 13	8	60 0
A 2	2	30 3	4	30 0
A 3	4	8	6	50
A 4	0	0	0	60
Потребность	40 0	80 30	80

От поставщика A₃ к потребителю B₂ будем доставлять min = { 50 , 30 } = 30 единиц продукции.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	20 13	8	60 0
A 2	2	30 3	4	30 0
A 3	4	30 8	6	50 20
A 4	0	0	0	60
Потребность	40 0	80 0	80

От поставщика A₃ к потребителю B₃ будем доставлять min = { 20 , 80 } = 20 единиц продукции.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	20 13	8	60 0
A 2	2	30 3	4	30 0
A 3	4	30 8	20 6	50 0
A 4	0	0	0	60
Потребность	40 0	80 0	80 60

От поставщика A₄ к потребителю B₃ будем доставлять 60 единиц продукции.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	20 13	8	60 0
A 2	2	30 3	4	30 0
A 3	4	30 8	20 6	50 0
A 4	0	0	60 0	60 0
Потребность	40 0	80 0	80 0

Мы израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

Мы нашли начальное решение.

Стоимость доставки продукции, для начального решения, не сложно посчитать.



S = 40 * 1 + 20 * 13 + 30 * 3 + 30 * 8 + 20 * 6 + 60 * 0 = 750 ден. ед.

Полученное начальное решение является оптимальным?

Для того, чтобы иметь возможность ответить на этот вопрос, количество задействованных маршрутов должно равняться 4 + 3 - 1 = 6, где

4 - количество строк в таблице.

3 - количество столбцов в таблице.

Количество задействованных маршрутов не может получиться больше 6, меньше - возможно.

Посчитайте. Количество задействованных маршрутов равно 6, что и требовалось.

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

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

Зная потенциалы, находим оценки незадействованных маршрутов.

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

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

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

Один, ранее задействованный маршрут, исключаем.

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

Шаг 1

Каждому поставщику A _i ставим в соответствие некоторое число - u _i , называемое потенциалом поставщика.

Каждому потребителю B _j ставим в соответствие некоторое число - v _j , называемое потенциалом потребителя.

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

Поставщик	Потребитель	U j
	B 1	B 2	B 3
A 1	40 1	20 13	8	u 1 = 13
A 2	2	30 3	4	u 2 = 3
A 3	4	30 8	20 6	u 3 = 8
A 4	0	0	60 0	u 4 = 2
V i	v 1 = -12	v 2 = 0	v 3 = -2

Примем v₂ = 0.

A₁B₂ :

v₂ + u₁ = 13

u₁ = 13 - 0 = 13

A₂B₂ :

v₂ + u₂ = 3

u₂ = 3 - 0 = 3

A₃B₂ :

v₂ + u₃ = 8

u₃ = 8 - 0 = 8

A₃B₃ :

v₃ + u₃ = 6

v₃ = 6 - 8 = -2

A₄B₃ :

v₃ + u₄ = 0

u₄ = 0 - ( -2 ) = 2

A₁B₁ :

v₁ + u₁ = 1

v₁ = 1 - 13 = -12

Найдем оценки незадействованных маршрутов.

Оценка незадействованного маршрута = тариф маршрута.

A₁B₃ : ₁₃ = 8 - ( 13 + ( -2 ) ) = -3

A₂B₁ : ₂₁ = 2 - ( 3 + ( -12 ) ) = 11

A₂B₃ : ₂₃ = 4 - ( 3 + ( -2 ) ) = 3

A₃B₁ : ₃₁ = 4 - ( 8 + ( -12 ) ) = 8

A₄B₁ : ₄₁ = 0 - ( 2 + ( -12 ) ) = 10

A₄B₂ : ₄₂ = 0 - ( 2 + 0 ) = -2

Поставщик	Потребитель	U j
	B 1	B 2	B 3
A 1	40 1	20 13	-3 8	u 1 = 13
A 2	11 2	30 3	3 4	u 2 = 3
A 3	8 4	30 8	20 6	u 3 = 8
A 4	10 0	-2 0	60 0	u 4 = 2
V i	v 1 = -12	v 2 = 0	v 3 = -2

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

Будем использовать новый маршрут доставки продукции от поставщика A₁ к потребителю B₃.

Построим цикл для нового маршрута.



Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	20 13	-3 8	60
A 2	2	30 3	4	30
A 3	4	30 8	20 6	50
A 4	0	0	60 0	60
Потребность	40	80	80

моделирование математический транспортный задача

Пусть ячейка A₁B₃, для которой мы строили цикл, имеет порядковый номер один.

Среди ячеек цикла, номера которых четные, найдем ячейку обладающую наименьшим значением.

min = { 20, 20 } = 20.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	20 13	-3 8	60
A 2	2	30 3	4	30
A 3	4	30 8	20 6	50
A 4	0	0	60 0	60
Потребность	40	80	80

От ячеек цикла с четными номерами отнимает 20. К ячейкам с нечетными номерами прибавляем 20.



Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	20 - 20 13	+ 20 -3 8	60
A 2	2	30 3	4	30
A 3	4	30 + 20 8	20 - 20 6	50
A 4	0	0	60 0	60
Потребность	40	80	80

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

А вот общие затраты на доставку всей продукции изменятся на величину

8 * 20 - 13 * 20 + 8 * 20 - 6 * 20 = ( 8 - 13 + 8 - 6 ) * 20 =

= -3 * 20 = ₁₃ * 20.

Выражение стоящее в скобках равно оценке нового маршрута!!

Поэтому новая стоимость доставки вычисляется именно так:

S = 750 + ₁₃ * 20 = 750 - 3 * 20 = 690 ден. ед.

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

У нас есть 2 таких маршрута . Тариф маршрута от поставщика A₁ к потребителю B₂ наибольший.

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



Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	13	20 8	60
A 2	2	30 3	4	30
A 3	4	50 8	0 6	50
A 4	0	0	60 0	60
Потребность	40	80	80

Шаг 2

Каждому поставщику A _i ставим в соответствие некоторое число - u _i , называемое потенциалом поставщика.

Каждому потребителю B _j ставим в соответствие некоторое число - v _j , называемое потенциалом потребителя.

Найдем потенциалы поставщиков и покупателей.

Для задействованного маршрута, сумма потенциала поставщика и потребителя равна тарифу задействованного маршрута.

Поставщик	Потребитель	U j
	B 1	B 2	B 3
A 1	40 1	13	20 8	u 1 = 8
A 2	2	30 3	4	u 2 = 1
A 3	4	50 8	0 6	u 3 = 6
A 4	0	0	60 0	u 4 = 0
V i	v 1 = -7	v 2 = 2	v 3 = 0

Найдем оценки незадействованных маршрутов

Оценка незадействованного маршрута = тариф маршрута

A1B2 : 12 = 13 - ( 8 + 2 ) = 3

A2B1 : 21 = 2 - ( 1 + ( -7 ) ) = 8

A2B3 : 23 = 4 - ( 1 + 0 ) = 3

A3B1 : 31 = 4 - ( 6 + ( -7 ) ) = 5

A4B1 : 41 = 0 - ( 0 + ( -7 ) ) = 7

A4B2 : 42 = 0 - ( 0 + 2 ) = -2

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

Будем использовать новый маршрут доставки продукции от поставщика A₄ к потребителю B₂.

Построим цикл для нового маршрута.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	13	20 8	60
A 2	2	30 3	4	30
A 3	4	50 8	0 6	50
A 4	0	-2 0	60 0	60
Потребность	40	80	80

Пусть ячейка A₄B₂, для которой мы строили цикл, имеет порядковый номер один.

Среди ячеек цикла, номера которых четные, найдем ячейку обладающую наименьшим значением.

min = { 60, 50 } = 50.



Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	13	20 8	60
A 2	2	30 3	4	30
A 3	4	50 8	0 6	50
A 4	0	-2 0	60 0	60
Потребность	40	80	80

От ячеек цикла с четными номерами отнимает 50. К ячейкам с нечетными номерами прибавляем 50.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	13	20 8	60
A 2	2	30 3	4	30
A 3	4	50 - 50 8	0 + 50 6	50
A 4	0	+ 50 -2 0	60 - 50 0	60
Потребность	40	80	80

Достаточно взглянуть на таблицу и Вы увидите, что баланс не нарушится.

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

А вот общие затраты на доставку всей продукции изменятся на величину

0 * 50 - 0 * 50 + 6 * 50 - 8 * 50 = ( 0 - 0 + 6 - 8 ) * 50 = -2 * 50 = ₄₂ * 50.



Выражение стоящее в скобках равно оценке нового маршрута!!

Поэтому новая стоимость доставки вычисляется именно так:

S = 690 + ₄₂ * 50 = 690 - 2 * 50 = 590 ден. ед.

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

Это маршрут от поставщика A₃ к потребителю B₂ . Теперь данный маршрут незадействованный.

Поставщик	Потребитель	Запас
	B 1	B 2	B 3
A 1	40 1	13	20 8	60
A 2	2	30 3	4	30
A 3	4	8	50 6	50
A 4	0	50 0	10 0	60
Потребность	40	80	80

Шаг 3

Каждому поставщику A _i ставим в соответствие некоторое число - u _i , называемое потенциалом поставщика.

Каждому потребителю B _j ставим в соответствие некоторое число - v _j , называемое потенциалом потребителя.

Найдем потенциалы поставщиков и покупателей.

Для задействованного маршрута, сумма потенциала поставщика и потребителя равна тарифу задействованного маршрута.



Поставщик	Потребитель	U j
	B 1	B 2	B 3
A 1	40 1	13	20 8	u 1 = 8
A 2	2	30 3	4	u 2 = 3
A 3	4	8	50 6	u 3 = 6
A 4	0	50 0	10 0	u 4 = 0
V i	v 1 = -7	v 2 = 0	v 3 = 0

Найдем оценки незадействованных маршрутов

Оценка незадействованного маршрута = тариф маршрута

Примем v3 = 0.

A1B3 : v3 + u1 = 8 u1 = 8 - 0 = 8

A3B3 : v3 + u3 = 6 u3 = 6 - 0 = 6

A4B3 : v3 + u4 = 0 u4 = 0 - 0 = 0

A1B1 : v1 + u1 = 1 v1 = 1 - 8 = -7

A4B2 : v2 + u4 = 0 v2 = 0 - 0 = 0

A2B2 : v2 + u2 = 3 u2 = 3 - 0 = 3

A₁B₂ : ₁₂ = 13 - ( 8 + 0 ) = 5

Поставщик	Потребитель	U j
	B 1	B 2	B 3
A 1	40 1	5 13	20 8	u 1 = 8
A 2	6 2	30 3	1 4	u 2 = 3
A 3	5 4	2 8	50 6	u 3 = 6
A 4	7 0	50 0	10 0	u 4 = 0
V i	v 1 = -7	v 2 = 0	v 3 = 0



A₂B₁ : ₂₁ = 2 - ( 3 + ( -7 ) ) = 6

A₂B₃ : ₂₃ = 4 - ( 3 + 0 ) = 1

A₃B₁ : ₃₁ = 4 - ( 6 + ( -7 ) ) = 5

A₃B₂ : ₃₂ = 8 - ( 6 + 0 ) = 2

A₄B₁ : ₄₁ = 0 - ( 0 + ( -7 ) ) = 7

Оценки всех незадействованных маршрутов неотрицательные. Следовательно, уменьшить общую стоимость доставки мы не сможем.

Ответ:

X опт =		40	0	20
		0	30	0
		0	0	50
		0	50	10
S = 590 ден. ед.

2.3 Решение транспортной задачи средствами MS Excel

F = -4x₁+5x₂ > min, при системе ограничений:

7x₁+9x₂?63(1)

x₁-2x₂?6(2)

7x₁+2x₂?14(3)

-x₁+x₂?5(4)

x₁?0(5)

x₂?0(6)



F = -4x₁+5x₂ > min, при системе ограничений:

7x₁+9x₂?63(1)

x₁-2x₂?6(2)

7x₁+2x₂?14(3)

-x₁+x₂?5(4)

x₁?0(5)

x₂?0(6)



Список литературы

1. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования М.; Наука, 1976 г.

2. Карманов В.Г. Математическое программирование. - М.; Наука, 1986г.

3. Моисеев Н.Н., Иванов Ю.П., Столярова Е.М. Методы оптимизации. - М.; Наука, 1978г.

4. Иванов Ю.П., Лотов А.В. Математические модели в экономике. - М.; Наука, 1979г.

5. Бронштейн И.Н., Семендяев К.А. Справочник по математике. - М.; Наука, 1986г

Размещено на Allbest.ru

...