Линейное программирование (стр. 2 из 4)

Задача 3.

Задание 1. Записать исходные данные задачи в виде транспортной таблицы, определить, открытой или закрытой является транспортная задача.

Задание 2. Сформулировать экономико-математическую модель исходной транспортной задачи.

Задание 3. Найти оптимальный план перевозок, отметив при этом единственность или неединственность оптимального плана.

Вариант 3.

На складах A, B, C, Д находится соответственно 50 т, 40 т, 40 т и 70 т муки, которую нужно доставить четырем хлебозаводам. Первому хлебозаводу требуется 50 т муки, второму – 40 т, третьему – 50 т и четвертому – 60 т муки. Стоимость доставки одной тонны муки со склада А каждому хлебозаводу соответственно равны 8, 3, 5 и 2 ден. единиц, со склада В – 7, 4, 9 и 8 ден. единиц, со склада С – 6, 3, 3 и 1 ден. единиц, со склада Д – 2, 4, 1 и 5 ден. единиц. Составить план перевозки муки, обеспечивающий минимальные транспортные расходы.

Решение.

Задание 1.

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

Сумма мощностей поставщиков (запасы муки на всех складах) 50+40+40+70 = 200, сумма мощностей потребителей (потребности всех хлебозаводов) 50+40+50+60 = 200. Суммы равны, данная задача является транспортной задачей закрытого типа.

Задание 2.

Обозначим x_ij объем поставок муки от i – го поставщика (склада) j – му потребителю (хлебозаводу), i = 1, 2, 3, 4; j = 1, 2, 3, 4. Очевидно, x_ij ³ 0. В закрытой транспортной задаче все ограничения являются равенствами.

Так как потребности должны быть удовлетворены, то выполняются условия:

х₁₁ + х₂₁ + х₃₁ + х₄₁ = 50

х₁₂ + х₂₂ + х₃₂ + х₄₂ = 40 (1)

х₁₃ + х₂₃ + х₃₃ + х₄₃ = 50

х₁₄ + х₂₄ + х₃₄ + х₄₄ = 60

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

х₁₁ + х₁₂ + х₁₃ + х₁₄ = 50

х₂₁ + х₂₂ + х₂₃ + х₂₄ = 40 (2)

х₃₁ + х₃₂ + х₃₃ + х₃₄ = 40

х₄₁ + х₄₂ + х₄₃ + х₄₄ = 70

Затраты на транспортировку составят

F(X) = 8х₁₁ + 3х₁₂ + 5х₁₃ + 2х₁₄+

+ 7х₂₁ + 4х₂₂ + 9x₂₃ + 8х₂₄+

+ 6х₃₁ + 3х₃₂ + 3х₃₃ + 1х₃₄+

+ 2х₄₁ + 4х₄₂ + 1х₄₃ + 5х₄₄+.

Требуется найти неотрицательное решение системы уравнений (1) – (2), на котором целевая функция затрат F(X) принимает минимальное значение.

Задание 3.

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

Заполняем клетку (3; 4) х₃₄ = min {60, 40} = 40, от поставщика 3 вывезено все, в строке 3 больше поставок нет. Заполняем клетку (4; 3) х₄₃ = min {50, 70} = 50, потребителю 3 все завезено, в столбец 3 больше поставок нет. Клетка (1; 4) х₁₄ = min {60 - 40, 50} = 20, потребителю 4 все завезено, в столбец 4 больше поставок нет. Клетка (4; 1) х₄₁ = min {50, 70 - 50} = 20, от поставщика 4 вывезено все, в строке 4 больше поставок нет. Клетка (1; 2) х₁₂ = min {40, 50 - 20} = 30, от поставщика 1 вывезено все, в строке 1 больше поставок нет. Клетка (2; 2) х₂₂ = min {40 - 30, 40} = 10, потребителю 2 все завезено, в столбец 2 больше поставок нет. Клетка (2; 1) х₂₁ = 30. Все клетки, в которые даны поставки, считаем занятыми, остальные – свободными. Первоначальный план перевозок задается таблицей 1.

Таблица 1.

Мощности поставщиков	Мощности потребителей				ui
	50	40	50	60
50	8	3 30	5	2 20	0
40	7 30	4 10	9	8	-1
40	6	3	3	1 40	1
70	2 20	4	1 50	5	4
vj	6	3	5	2

Исследуем этот план перевозок на оптимальность методом потенциалов. Потенциалы для занятых клеток удовлетворяют уравнениям: v_j = c_{ij +} u_i.

Пусть u₁ = 0; по клетке (1; 2) находим v₂ = 3; по клетке (1; 4) находим v₄ = 2; по клетке (2; 2) находим u₂ = -1; по клетке (2; 1) находим v₁ = 6; по клетке (3; 4) находим u₃ = 1; по клетке (4; 1) находим u₄ = 4; по клетке (4; 3) находим v₃ = 5.

Для всех клеток матрицы перевозок найдем оценки клеток d_ij = (u_i + c_ij) - v_j :

Среди оценок есть отрицательная, следовательно план перевозок Х₀ (таблица 1) не оптимальный. Наименьшая оценка в клетке (3; 3).

Составим цикл пересчета и пометим клетки поочередно знаками «+» и «-»:

+ - + - + - + -

(3; 3), (3; 4), (1; 4), (1; 2), (2; 2), (2; 1), (4; 1), (4; 3).

В клетки с «+» переместим из клеток с «-» величину min{40; 30; 30; 50} = 30. В этом случае план перевозок станет таким ( таблица 2).

Таблица 2.

Мощности поставщиков	Мощности потребителей				ui
	50	40	50	60
50	8	3 0	5	2 50	0
40	7	4 40	9	8	-1
40	6	3	3 30	1 10	1
70	2 50	4	1 20	5	3
vj	5	3	4	2

Освободилось две клетки (1; 2) и (2; 1). Клетку (1; 2) считаем занятой с нулевой поставкой.

Среди оценок нет отрицательных, следовательно план перевозок Х₀ (таблица 1) оптимальный.

Исследуем этот план перевозок на оптимальность методом потенциалов. Потенциалы для занятых клеток удовлетворяют уравнениям: v_j = c_{ij +} u_i.

Пусть u₁ = 0; по клетке (1; 2) находим v₂ = 3; по клетке (1; 4) находим v₄ = 2; по клетке (2; 2) находим u₂ = -1; по клетке (3; 4) находим u₃ = 1; по клетке (3; 3) находим v₃ = 4; по клетке (4; 3) находим u₄ = 3; по клетке (4; 1) находим v₁ = 5.

Для всех клеток матрицы перевозок найдем оценки клеток d_ij = (u_i + c_ij) - v_j :

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

Общие затраты на перевозки

F(X₁) = 2*50 + 4*40 + 3*30 + 1*10 + 2*50 + 1*20 = 480 ден. единиц

будут минимальными при:

x₁₄ = 50, x₂₂ = 40, x₃₃ = 30, х₃₄ = 10, x₄₁ = 50, x₄₃ = 20, остальные x_ij = 0.

По оптимальному плану перевозок следует перевезти муки:

со склада А на четвертый хлебозавод - 50 т;

со склада В на второй хлебозавод - 40 т;

со склада С на третий хлебозавод - 30 т;

на четвертый хлебозавод - 10 т;

со склада Д на первый хлебозавод - 50 т;

на третий хлебозавод - 20 т.

Задача 4

В таблице приведены годовые данные о трудоемкости производства I т цемента (нормо-смен) (N —последняя цифра зачетной книжки студента):

Текущий номер года (t)	1	2	3	4	5	6	7	8	9	10
Трудоемкость 1 т цемента (yi)	7,9+0,N	8,3+0,N	7,5+0,N	6,9+0,N	7,2+0,N	6,5+0,N	5,8+0,N	4,9+0,N	5,1+0,N	4,4+0,N

Задание 1. Сгладить временной ряд методом простой скользящей средней, выбрав длину интервала сглаживания m = 3; результаты отразить на графике.

Задание 2. Определить наличие тренда во временном ряду методом Фостера - Стьюарта. Табличные значения статистики Стьюдента t_a принять равными при уровне значимости a = 0.05 t_a = 2,23 , а при a = 0,30 - t_a = 1,09; другие необходимые табличные данные приведены в таблице 4.5 учебника на с.153 (описание метода Фостера - Стьюарта см. учебник с. 151- 153).

Задание 3. Для исходного временного ряда построить линейную трендовую модель

, определив ее параметры на основе метода наименьших квадратов (соответствующую систему нормальных уравнений см. в учебнике на с. 196 формула (5.5)).

Задание 4. Оценить адекватность построенной модели на основе исследования

а) близости математического ожидания остаточной компоненты (ряда остатков) нулю; критические значения r-критерия принять равным тому числу, как указанно в задании 2;

б) случайности отклонений остаточной компоненты по критерию пиков (поворотных точек); Расчеты выполнить на основе соотношения 5.9. учебника на с. 200;

в) независимости уровней ряда остатков (отсутствие автокорреляции) на основе критерия Дарбина — Уотсона (см. учебник с. 203— 204), используя в качестве критических значений d_l = 1.08 и d₂ = 1,36; если критерий Дарбина — Уотсона ответа не дает, исследование независимости провести по первому коэффициенту автокорреляции:

,

где e_i -- уровни остаточной компоненты;

Модуль первого коэффициента автокорреляции сравнить с критическим уровнем этого коэффициента, значение которого принять равным 0,36;

г) нормальности закона распределения уровней остаточной компоненты на основе RS-критерия;

В качестве критических значений принять интервал от 2,7 до 3,7 (см. учебник, стр. 201—-202).

Задание 5. Оценить точность построенной трендовой линейной модели, используя показатели среднего квадратического отклонения от линии тренда (формула (5,17) учебника на с. 210, k = 1) и средней относительной ошибки аппроксимации (формула (5.14) учебника на с. 204).

Задание 6. Построить точечный и интервальный прогноз трудоемкости производства 1 т цемента на два шага вперед (формула (5.18) учебника на с. 210). Результаты моделирования и прогнозирования отразить на графике.