эмм. Задача 204-1. Задача 204

Название	Задача 204
Дата	18.12.2022
Размер	26.74 Kb.
Формат файла
Имя файла	Задача 204-1.docx
Тип	Задача #850491

Задача №204

Район порта имеет четыре причала, на которых перерабатываются четыре грузопотока генеральных грузов различных направлений (Q_j) в количествах 50, 100, 40, и 60 тыс. т соответственно. Груз каждого направления перевозится определенным типом судов, а для каждого причала в процессе переработки грузов характерна определенная технология. Бюджет времени работы причалов составляет 88 суток. Производительность каждого причала при переработке определенного вида грузов и комплексные (по флоту и порту) суточные расходы по переработке грузов всех направлений на всех причалах приведены в табл. 1.

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

Таблица 1

Причал	Производительность причалов при переработке грузов, тыс. т в сутки					Комплексные суточные расходы, тыс. руб. в сутки
Причал	1-й грузопоток	2-й грузопоток	3-й грузопоток	4-й грузопоток	1-й грузопоток		2-й грузопоток	3-й грузопоток	4-й грузопоток
1	Р₁₁	Р₁₂	Р₁₃	Р₁₄	с₁₁		с₁₂	с₁₃	с₁₄
2	Р₂₁	Р₂₂	Р₂₃	Р₂₄	с₂₁		с₂₂	с₂₃	с₂₄
3	Р₃₁	Р₃₂	Р₃₃	Р₃₄	с₃₁		с₃₂	с₃₃	с₃₄
4	Р₄₁	Р₄₂	Р₄₃	Р₄₄	с₄₁		с₄₂	с₄₃	с₄₄

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

204.	0,5	0,6	0,9	1,0	8	5	6	7
	2,2	2,0	1,9	1,8	23	15	22	19
	0,8	0,6	1,0	0,4	8	18	08	10
	1,2	1,5	1,5	1,1	12	10	10	15

Решение

Построим математическую модель задачи.

Обозначим х_ij – время работы i-го причала на переработке j-го грузопотока в течение суток.

Целевая функция, минимизирующая комплексные расходы:

Z = 8х₁₁ + 5х₁₂ + 6х₁₃+ 7х₁₄ + 23х₂₁ + 15х₂₂ + 22х₂₃ + 19х₂₄ + 8х₃₁ + 18х₃₂ + 8х₃₃ + 10х₃₄ + 12х₄₁ + 10х₄₂ + 10х₄₃ + 15х₄₄ min.

Система ограничений состоит из двух групп.

Первая группа – ограничения по бюджету времени причалов:

х₁₁ + х₁₂ + х₁₃+ х₁₄  88;

х₂₁ + х₂₂ + х₂₃ + х₂₄  88;

х₃₁ + x₃₂ + х₃₃ + х₃₄  88;

х₄₁ + х₄₂ + х₄₃ + х₄₄  88

Вторая группа – ограничения по количеству перерабатываемого груза:

0,5 х₁₁ + 2,2 х₂₁ + 0,8 х₃₁ + 1,2 х₄₁ = 50;

0,6 х₁₂ + 2,0 х₂₂ + 0,6 х₃₂ +1,5 х₄₂ = 100;

0,9 х₁₃ + 1,9 х₂₃ + 1,0 х₃₃ +1,5 х₄₃ = 40;

1,0 х₁₁ + 1,8 х₂₁ + 0,4 х₃₁ +1,1 х₄₄ = 60.

Требование неотрицательности:

x_ij0 (i = 1,2,3,4; j = 1, 2, 3, 4).

Запишем данные задачи в таблицу 2, где в левом нижнем углу каждой клетки расположена производительность каждого причала при переработке определенного типа груза p_ij, а комплексные суточные расходы с_ij– в правом верхнем углу.

Таблица 2

Причал	Грузопотоки
Причал	1	2	3	4
1	8 0,5	5 0,6	6 0,9	7 1,0
2	23 2,2	15 2,0	22 1,9	19 1,8
3	8 0,8	18 0,6	8 1,0	10 0,4
4	12 1,2	10 1,5	10 1,5	15 1,1
Q_j	50	100	40	60

Далее работаем по алгоритму.

Определим для каждого причала его удельную характеристику:

S₁ =

= 8,7;

S₂ =

= 10;

S₃ =

= 15,7;

S₄ =

= 8,9.

Полученные значения запишем в расчетную таблицу 3.

Таблица 3

Причал	Грузопотоки				S_i
Причал	1	2	3	4	S_i
1	8 0,5	5 0,6	6 0,9	7 1,0	8,7
2	23 2,2	15 2,0	22 1,9	19 1,8	10
3	8 0,8	18 0,6	8 1,0	10 0,4	15,7
4	12 1,2	10 1,5	10 1,5	15 1,1	8,9
Q_j	50	100	40	60

За базу сравнения примем третий причал, так как

Max {8,7; 10,0; 15,7; 8,9} = 15,7

Для третьего причала определяем себестоимость переработки на нем каждого грузопотока:

S₃₁ = 8,0/0,8 = 10; S₃₂ = 18/0,6 = 30; S₃₃ = 8/1,0 = 8; S₃₄ = 10/0,4 = 25.

Полученные значения также запишем в расчетную таблицу 4.

Таблица 4

Причал	Грузопотоки				S_i
Причал	1	2	3	4	S_i
1	8 0,5	5 0,6	6 0,9	7 1,0	8,7
2	23 2,2	15 2,0	22 1,9	19 1,8	10
3	8 0,8	18 0,6	8 1,0	10 0,4	15,7
4	12 1,2	10 1,5	10 1,5	15 1,1	8,9
Q_j	50	100	40	60
S_ij	10	30	8	25

Находим величину оценки _ij для каждой клетки (_ij = S_i_j p_ij – c_ij):

₁₁ = 100,5–8= - 3; ₂₁ = 102,2–23= -1; ₃₁ = 100,8–8= 0; ₄₁ = 101,2–12= 0;

₁₂ = 300,6–5= 13; ₂₂ = 302–15= 45; ₃₂ = 300,6–18= 0; ₄₂ = 301,5-10= 35;

₁₃ = 8,00,9–6 = 1,2; ₂₃ = 8,01,9–22 = -6,8; ₃₃ = 8,01,0–8 =0;

₄₃ =8,01,5–10= 2;

₁₄ = 251,0–7= 18; ₂₄ = 251,8–19=26; ₃₄ = 250,4 – 10 = 0;

₄₄ = 251,1–15= 12,5;

Значения _ij запишем в левом верхнем углу каждой клетки таблица 5.

Таблица 5

Причал	Грузопотоки				S_i
Причал	1	2	3	4	S_i
1	-3 8 0,5	13 5 0,6	1,2 6 0,9	18 7 1,0	8,7
2	-1 23 2,2	45 15 2,0	-6,8 22 1,9	26 19 1,8	10
3	0 8 0,8	0 18 0,6	0 8 1,0	0 10 0,4	15,7
4	0 12 1,2	35 10 1,5	2 10 1,5	12,5 15 1,1	8,9
Q_j	50	100	40	60
S_ij	10	30	8	25

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

Отрицательное значение оценки характеризует суточные убытки по сравнению с базовым вариантом.

4. Наибольшее значение оценки ₂₂ = 45 находится в клетке (2,2). С этой клетки начнем составление плана закрепления грузопотоков за причалами:

х₂₂ = min

= 50.

Значит, второй грузопоток второй причал перерабатывает полностью, и остается еще время 88 – 50 = 38 суток, в течение которого на данном причале могут перерабатываться другие грузы.

В оставшейся части таблицы 5 (за исключением второго столбца) найдем клетку с наибольшей оценкой. Это клетка (2,4). ₂₄ = 26 Определяем время работы второго причала по переработке четвертого грузопотока (часть бюджетного времени второго причала уже истрачено на переработку второго грузопотока, осталось 38 суток), т. е.

Х₂₄ = min

= 33,3.

Значит, на втором причале в оставшееся время четвертый грузопоток перерабатывается не полностью, остается еще остаток грузопотока в количестве Q₃ = 60 – 33,3  1,8= 0,06 тыс. т, который необходимо переработать на других причалах.

В оставшейся части таблицы 5 (за исключением второго столбца, а также второй строки) найдем клетку с наибольшей оценкой. ₁₄ = 18 Это клетка (1,4). Определяем время работы первого причала по переработке четвёртого грузопотока, т. е.

Х₁₄ = min

= 60.

Значит, на первом причале четвертый грузопоток перерабатывается полностью, остается еще время 88 – 60= 28 суток, в течение которого на данном причале могут перерабатываться другие грузы.

В оставшейся части таблицы 5 (за исключением второго и четвертого столбца, а также второй строки) найдем клетку с наибольшей оценкой. Это клетка (4,3). ₄₃ = 2,0. Определяем время работы четвертого причала по переработке третьего грузопотока, т. е.

Х₄₃ = min

= 26,7

Значит, третий грузопоток четвертый причал перерабатывает полностью, и остается еще время 88 – 26,7 = 61,3 суток, в течение которого на данном причале могут перерабатываться другие грузы.

В оставшейся части таблицы 5 (за исключением второго и четвертого столбца, а также второй строки) найдем клетку с наибольшей оценкой. _ = 1,2. Это клетка (1,3). Определяем время работы первого причала по переработке третьего грузопотока (часть бюджетного времени первого причала уже истрачено на переработку четвертого грузопотока, осталось 28 суток), т. е.

Х₁₃= min

= 28

Значит, на первом причале в оставшееся время третий грузопоток перерабатывается не полностью, остается еще остаток грузопотока в количестве Q₃ = 40 – 28  0,9= 14,8 тыс. т, показывает, что на первом причале можно еще переработать 14,8 тыс.т.

В оставшейся части таблицы 5 (за исключением второго, третьего и четвертого столбца, а также второй строки) найдем клетку с наибольшей оценкой. _ = 0. Это клетка (4,1). Определяем время работы четвертого причала по переработке первого грузопотока (часть бюджетного времени четвертого причала уже истрачено на переработку третьего грузопотока, осталось 61,3 суток), т. е.

Х₄₁= min

= 41,7.

Значит, на четвертом причале в оставшееся время первый грузопоток перерабатывается не полностью, остается еще остаток грузопотока в количестве Q₃ = 50 – 41,7  1,2= -0,04 тыс. т, показывает, что на четвертом причале можно еще переработать 0,04 тыс.т.

В оставшейся части таблицы 5 (за исключением второго, третьего и четвертого столбца, а также второй строки) найдем клетку с наибольшей оценкой. Это клетка (3,1). ₃₁ = 0. Определяем время работы четвертого причала по переработке третьего грузопотока, т. е.

Х₃₁ = min

= 62,5

Значит, первый грузопоток третий причал перерабатывает полностью, и остается еще время 88 – 62,5 = 25,5 суток, в течение которого на данном причале могут перерабатываться другие грузы.

Полученные расчеты занесем в таблицу (х_ij записываются в центре клеток таблицы). Получим таблицу 6.

Таблица 6

Причал	Грузопотоки				Остаток времени ΔТ_э_i		Т_э
	1	2	3	4
1	-3 8 0,5	13 5 0,6	1,2 6 28 0,9	18 7 60 1,0		0		88
2	-1 23 2,2	45 15 50 2,0	-6,8 22 1,9	26 19 33,3 1,8		4,7		83,3
3	0 8 25,5 0,8	0 18 0,6	0 8 1,0	0 10 0,4		62,5		25,5
4	0 12 41,7 1,2	35 10 1,5	2 10 26,7 1,5	12,5 15 1,1		19,6		68,4
Q_j	50	100	40	60

Полученный в таблице 6 план достаточно близок к оптимальному. Он обеспечивает переработку всех грузопотоков при расходах:

Z = 6  28 + 7 60 + 15  50 + 19  33,3 + 8  25,5 + 1241,7+ 10  26,7 = 2942,1 тыс. руб. и остатке неиспользованного времени второго, третьего и четвертого причалов (4,7; 62,5 и 19,6 суток).