Транспортные задачи

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

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

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ ИНСТИТУТ»

Филиал г. Владимир

Кафедра экономико-математических методов и моделей

КОНТРОЛЬНАЯ работа

по дисциплине «Экономико-математические методы и прикладные модели»

Вариант №10)

Владимир, 2011

Задание 1. Изложить материал по выбранной теме. Проиллюстрировать теоретические положения примерами

транспорт задача графический параметр

Решение транспортной задачи методом потенциалов.

Постановка задачи.

Имеется m пунктов, в которых сосредоточены запасы некоторого однородного груза, а также n пунктов потребления, куда этот груз должен быть доставлен. Известны:

- запасы груза у поставщиков ;

- потребности в этом грузе потребителей ;

- - стоимость доставки единицы груза от i-го поставщиков j-му потребителю.

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

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

Пусть - количество груза, перевозимого от i-го поставщика к j-му потребителю. Будем считать, что суммарные запасы груза у поставщиков равны суммарным потребностям потребителей, то есть . Тогда модель транспортной задачи (ТЗ) является закрытой, и задача - разрешимой.

Оптимальный план перевозок является решением следующей задачи линейного программирования (ЗЛП):

,



Алгоритм решения транспортной задачи методом потенциалов.

Рассмотрим алгоритм решения ТЗ на следующем примере.

Пусть имеется 4 поставщика и 4 потребителя.

Запасы груза у поставщиков: ;

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

Стоимости доставки (в руб.) единицы груза заданы в виде матрицы:

, ; .

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

Исходные данные:

Поставщики,	Потребители,	Запасы поставщиков
	1	2	3	4
1	8	3	5	2	50
2	7	4	9	8	40
3	6	3	3	1	40
4	2	4	1	5	70
Потребности потребителей	50	40	50	60	200

Проверяем необходимое и достаточное условие разрешимости задачи:

,

.

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

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

Таблица 1

		6	3	5	2	Запасы
0		8 -2	- 3 30	5 0	+ 2 20	50
1		- 7 30	+ 4 10	9 -3	8 -5	40
-1		6 -1	3 -1	+ 3 1	- 1 40	40
-4		+ 2 20	4 -5	- 1 50	5 -7	70
Потребности	50	40	50	60	200

Шаг 1. Построим первый опорный план методом минимальной стоимости.

В клетку с минимальным тарифом направляем максимально возможный груз, равный . Строка выходит из рассмотрения.

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

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

Шаг 2. Проверяем невырожденность плана.

Невырожденный план должен содержать занятых клеток. Первый опорный план является невырожденным, так как число занятых клеток равно 7.

Если же опорный план содержит меньшее число занятых клеток, то одну или несколько пустых клеток нужно занять фиктивными нулевыми перевозками.

Расчитаем значение целевой функции.

.

Шаг 3. Проверяем условие оптимальности.

Критерием оптимальности невырожденного опорного плана является существование двух наборов чисел: и (эти числа называются потенциалами), удовлетворяющих условиям:

(1) для всех занятых клеток;

(2) для всех пустых клеток.

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

Так как число неизвестных больше числа уравнений (m+n>m+n-1), то один из потенциалов принимаем равным нулю (). Рассчитанные потенциалы заносим в таблицу 1 и определяем оценки свободных клеток по формулам:

(2)

Заносим их в левые нижние углы свободных клеток таблицы.

Первый опорный план является не оптимальным, так как .

Шаг 4. Для улучшения плана клетку необходимо загрузить.

Построим новый опорный план. Для клетки строим замкнутый прямоугольный контур, в вершинах которого находятся занятые клетки. Вершинам контура, начиная с клетки , присваиваем поочередно знаки "+" и "-".

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

транспортный задача графический экономический

Таблица 2

		5	3	4	2	Запасы
0		8 -3	3 0	5 -1	2 50	50
1		6 -1	4 40	9 -4	8 -5	40
-1		6 -2	3 -1	3 30	1 10	40
-3		2 50	4 -4	1 20	5 -6	70
Потребности	50	40	50	60	200 200

Значение целевой функции.

.

Снова проверяем условие оптимальности.

Для этого находим потенциалы по занятым клеткам таблицы 2.

Так как число неизвестных больше числа уравнений (m+n>m+n-1), то один из потенциалов принимаем равным нулю (). Рассчитанные потенциалы заносим в таблицу 2 и определяем оценки свободных клеток. Заносим их в левые нижние углы свободных клеток таблицы.

Если все оценки , то опорный план транспортной задачи является оптимальным.

2-й опорный план является оптимальным, так как все оценки свободных клеток .

Оптимальный план:

,

Анализ плана.

С 1-го пункта поставки необходимо все 50 ед. груза направить 4-му потребителю, со 2-го пункта поставки необходимо все 40 ед. груза направить 2-му потребителю, с 3-го пункта поставки необходимо 30 ед. груза направить 3-му потребителю и 10 ед. груза направить 4-му потребителю, с 4-го пункта поставки необходимо 50 ед. груза направить 1-му потребителю и 20 ед. груза направить 3-му потребителю.

Общая стоимость доставки будет минимальной и составит 480 руб.

Оптимальный план является вырожденным (только 6 занятых клеток). Задача имеет единственный оптимальный план. Признаком этого является отсутствие нулевых оценок свободных клеток таблицы 2.

Задание 2. Решить графическим методом типовую задачу оптимизации

Фирма производит два широко популярных безалкогольных напитка - «Лимонад» и «Тоник». Фирма может продать всю продукцию, которая будет произведена. Однако объем производства ограничен количеством основного ингредиента и производственной мощностью имеющегося оборудования. Для производства 1 л «Лимонада» требуется 0,02 ч работы оборудования, а для производства 1 л «Тоника» - 0,04 ч. Расход специального ингредиента составляет 0,01 кг и 0,04 кг на 1 л «Лимонада» и «Тоника» соответственно. Ежедневно и распоряжении фирмы имеется 24 ч времени работы оборудования и 16 кг специального ингредиента. Прибыль фирмы составляет 0,10 ден. ед. за 1 л «Лимонада» и 0,30 ден. ед. за 1 л «Тоника». Сколько продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневной прибыли?

Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум и почему?

Решение:

1) Обозначим через - количество произведенных (в литрах) за день напитков - «Лимонад» и «Тоник» соответственно. Экономико-математическая модель исходной экономической задачи имеет вид:

;

Целевая функция - прибыль фирмы.

1-е ограничение - по фонду рабочего времени.

2-е ограничение - по количеству основного ингредиента.

Ниже - условия неотрицательности переменных.

2) Решаем задачу графическим методом. Для этого построим на плоскости х₁Ох₂ многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.

Каждую из двух первых прямых строим по двум точкам. Соответствующую полуплоскость определяем по тому, принадлежит ей или нет точка начала координат (0; 0).

, - точка 1 -

, - точка 2 -

- область решения - нижняя полуплоскость;

, - точка 1 -

, - точка 2 -

- область решения - нижняя полуплоскость;

- ось ,

- область решения - правая полуплоскость;

- ось ,

- область решения - верхняя полуплоскость;

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

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

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

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



В результате получим: .

Таким образом, оптимальный план задачи: , то есть необходимо производить 800 литров «Лимонада» и 200 литров «Тоника». Тогда прибыль будет максимальна и составят 140 ден. ед.

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

Задание 3. Исследовать динамику экономического показателя на основе анализа одномерного временного ряда

В течение девяти последовательных недель фиксировался спрос Y(t) (млн. р.) на кредитные ресурсы финансовой компании. Временной ряд Y(t) этого показателя приведен в таблице:

Показатели	Номер наблюдения
	1	2	3	4	5	6	7	8	9
	33	35	40	41	45	47	45	51	53

Требуется:

1) Проверить наличие аномальных наблюдений.

2) Построить линейную модель , параметры которой оценить МНК ( - расчетные, смоделированные значения временного ряда).

3) Оценить адекватность построенной модели, используя свойства независимости остаточной компоненты, случайности и соответствия нормальному закону распределения (при использовании R/S-критерия взять табулированные границы 2,7--3,7).

4) Оценить точность модели на основе использования средней относительной ошибки аппроксимации.

5) По построенной модели осуществить прогноз спроса на следующие две недели (доверительный интервал прогноза рассчитать при доверительной вероятности р = 70%).

6) Фактические значения показателя, результаты моделирования и прогнозирования представить графически.

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

Решение:

1) Отобразим на графике фактические данные.

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

2) Строим линейную модель .

Промежуточные расчеты выполняем в следующей таблице:

1	33	-4	16	-10,3	41,2
2	35	-3	9	-8,3	24,9
3	40	-2	4	-3,3	6,6
4	41	-1	1	-2,3	2,3
5	45	0	0	1,7	0,0
6	47	1	1	3,7	3,7
7	45	2	4	1,7	3,4
8	51	3	9	7,7	23,1
9	53	4	16	9,7	38,8
45	390	0	60	0,3	144,0

Из первых двух столбцов таблицы вычисляем средние значения:

;

.

Оценку параметров линейного уравнения осуществляем по методу наименьших квадратов:

;

.

Получили искомое уравнение: .

3) Оценим качество построенной модели, исследовав ее адекватность и точность.

Промежуточные расчеты выполняем в следующей таблице:

			Отклонение	Точки поворота
1	33	33,7	-0,7	-	0,49	-	-	2,12
2	35	36,1	-1,1	1	1,21	-0,4	0,2	3,14
3	40	38,5	1,5	1	2,25	2,6	6,8	3,75
4	41	40,9	0,1	1	0,01	-1,4	2,0	0,24
5	45	43,3	1,7	1	2,89	1,6	2,6	3,78
6	47	45,7	1,3	0	1,69	-0,4	0,2	2,77
7	45	48,1	-3,1	1	9,61	-4,4	19,4	6,89
8	51	50,5	0,5	1	0,25	3,6	13,0	0,98
9	53	52,9	0,1	-	0,01	-0,4	0,2	0,19
	390	389,7	0,3	6	18,41	0,8	44,1	23,86

а) Проверка равенства нулю математического ожидания уровней ряда остатков осуществляется с использованием t-критерия Стьюдента:

Среднее значение уровней остаточного ряда: .

Среднее квадратическое отклонение уровней остаточного ряда в этом случае равно:

;

.

При и по таблице имеем: .

Так как , то гипотеза о том, что математическое ожидание уровней ряда остатков равно 0 выполняется.

б) Проверка случайности остаточной компоненты проведем на основе критерия пиков (поворотных точек): количество пиков должно удовлетворять неравенству:

.

Так как в нашем случае , то свойство случайности выполняется.

в) При проверке независимости уровней ряда остатков используем d-критерий Дарбина-Уотсона, в соответствии с которым вычисляем коэффициент d:

.

.

Для линейной модели при можно взять в качестве критических табличных уровней величины и . Так как , то ряд остатков не коррелирован, то есть свойство независимости уровней остаточной компоненты выполняется.

г) Соответствие ряда остатков нормальному закону распределения определим при помощи RS-критерия:

.

Для и 5% уровне значимости табулированный интервал: . Так как расчетное значение попадает в табулированный интервал, то свойство нормальности распределения выполняется.

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

4) Для характеристики точности используем среднюю относительную ошибку аппроксимации:

.

Так как , то построенная модель имеет высокую точность.

5) Точечный прогноз на два шага вперед для линейной модели получаем подстановкой в полученное уравнение значений параметра t=10 и t=11:

;

.

Доверительный интервал прогноза будет иметь следующие границы:

верхняя граница прогноза: ;

нижняя граница прогноза: .

Величина для линейной модели имеет вид:

, где .

Для прогноза на два шага имеем:

,

.

Результаты прогнозных оценок по модели представим в таблице:

Время	Шаг	Прогноз	Нижняя граница	Верхняя граница
10	1	55,3	53,2	57,4
11	2	57,7	59,9	55,5

6) Отобразим на графике фактические данные, результаты расчетов и прогнозирования для линейной модели.

Задание 4. Рассчитать параметры моделей экономически выгодных размеров заказываемых партий

Мебельный салон продает наборы мебели для кухни по цене 50 тыс. руб. Годовой спрос составляет 2000 кухонных гарнитуров. Издержки на один заказ равны 2500 руб. Годовые издержки хранения составляют 15% его цены. Каков оптимальный размер заказа? Салон работает 300 дней в году. Постройте график циклов изменения запасов товара.

Решение:

Входные параметры модели Уилсона:

гарн./год - интенсивность (скорость) продаж салоном гарнитуров;

руб./гарн.-год - затраты на хранение гарнитуров;

руб. - издержки на один заказ гарнитуров;

руб. - цена гарнитура.

Находим оптимальный размер заказываемой партии по формуле Уилсона:

гарнитуров.

Полученный дробный результат можно интерпретировать, как 1-й раз заказать 37 гарнитуров, во 2-й раз - 36 гарнитуров, в 3-й раз - 37 гарнитуров, в 4-й - 36 гарнитуров и т.д.

Для построения графика циклов изменения запасов товара найдем оптимальный период пополнения запасов (в днях, учитывая, что салон работает 300 дней в году):

дней.

Полученный дробный результат можно интерпретировать так: 5 дней между 1-м и 2-м заказами, 6 дней между 2-м и 3-м заказами, 5 дней между 3-м и 4-м заказами, 6 дней между 4-м и 5-м заказами и т.д.

График циклов изменения запасов товара:

График циклов изменения запасов товара (с учетом описанной стратегии):

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

...