На 4-х мукомольных заводах ежедневно производится bi (i = 1,..., 4) т муки. Эту муку доставляют на четыре хлебокомбината, ежедневное потребление которых cj. Тарифы (в условных единицах) на перевозку 1т муки с мукомольных заводов к каждому из хлебокомбинатов задаются матрицей А, числа b и с находятся соответственно в столбце В и строке С .
Таблица 1 – Исходные данные
№ С В
98
8 4 9 6 94
1 9 4 7 84
4 1 4 8 82
8 5 4 3 99
А 88 85 85 86
Требуется:
Определить тип транспортной задачи;
Записать математическую формулировку задачи на минимум суммы затрат по перевозке муки;
Найти опорный план перевозок транспортной задачи методами северо-западного угла и минимальных элементов;
Сравнить затраты, возникающие при реализации полученных планов;
Методом потенциалов найти оптимальный план перевозок и минимальные затраты.
Ответ
Из 1-го мукомольного завода необходимо груз направить во 2-й хлебокомбинат (7 тонн) и в 4-й хлебокомбинат (72 тонны). Из 2-го завода необходимо весь груз (84 тонны) направить в 1-й хлебокомбинат. Из 3-го завода необходимо груз направить в 1-й хлебокомбинат (4 тонны) и во 2-й хлебокомбинат (78 тонн) Из 4-го завода необходимо груз направить в 3-й хлебокомбинат (85 тонн), и в 4-й хлебокомбинат (14 тонн). При этом, на 1-ом заводе остался невостребованным груз в количестве 15 тонн. Затраты на выполнения данного плана будут минимальными и составят 1020 у.е.
Решение
1. Запишем условие задачи в транспортной таблице.
Таблица 2 – Транспортная таблица 1
8 4 9 6 94
1 9 4 7 84
4 1 4 8 82
8 5 4 3 99
88 85 85 86
Проверим необходимое и достаточное условие разрешимости задачи.
Суммарные запасы = 94 + 84 + 82 + 99 = 359.
Суммарные потребности = 88 + 85 + 85 + 86 = 344.
Данная транспортная задача является открытой (не замкнутой), т.к. потребности меньше запасов на 15 т.. Для устранения этого вводим фиктивного потребителя - пятый хлебокомбинат с ежедневной потребностью 15 тонны муки в сутки и нулевой стоимостью перевозок единицы груза.
Занесем исходные данные в распределительную таблицу.
Таблица 3 – Транспортная таблица 2
8 4 9 6 0 94
1 9 4 7 0 84
4 1 4 8 0 82
8 5 4 3 0 99
88 85 85 86 15
2. Запишем математическую формулировку задачи:
Требуется минимизировать функцию F = 8x11+4x12+9x13+ +6x14+x21+9x22+4x23+7x24+4x31+x32+4x33+8x34+8x41+5x42+4x43+3x44 при ограничениях:
8x11+4x12+9x13+6x14≤94x21+9x22+4x23+7x24≤844x31+x32+4x33+8x34≤828x41+5x42+4x43+3x44≤998x11+x21+4x31+8x41=884x12+9x22+x32+5x42=859x13+4x23+4x33+4x43=856x14+7x24+8x34+3x44=86xij≥0;i=1,…,4;j= 1,…,4.
3. Найдем опорный план методом северо-западного угла.
Таблица 4 – Опорный план методом северо-западного угла
8
88 4
6 9 6 0 94
1 9
79 4
5 7 0 84
4 1 4
80 8
2 0 82
8 5 4 3
84 0
15 99
88 85 85 86 15
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно:
F(x) = 8*88 + 4*6 + 9*79 + 4*5 + 4*80 + 8*2 + 3*84 + 0*15 = 2047.
Найдем опорный план методом минимального элемента.
Таблица 5 – Опорный план методом минимального элемента
8
4 4
3 9
72 6 0
15 94
1
84 9 4 7 0 84
4 1
82 4 8 0 82
8 5 4
13 3
86 0 99
88 85 85 86 15
Опорный план является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи
. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 8*4 + 4*3 + 9*72 + 0*15 + 1*84 + 1*82 + 4*13 + 3*86 = 1168.
Опорный план, полученный методом минимального элемента дает меньшую стоимость перевозок, чем опорный план, полученный методом северо-западного угла. Поэтому для нахождения оптимального плана будем использовать опорный план, полученный методом минимального элемента.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы αi, βj. по занятым клеткам таблицы, в которых αi + βj = cij, полагая, что α1 = 0.
α1 + β1 = 8; 0 + β1 = 8; β1 = 8;
α2 + β1 = 1; 8 + α2 = 1; α2 = -7;
α1 + β2 = 4; 0 + β2 = 4; β2 = 4;
α3 + β2 = 1; 4 + α3 = 1; α3 = -3;
α1 + β3 = 9; 0 + β3 = 9; β3 = 9;
α4 + β3 = 4; 9 + α4 = 4; α4 = -5;
α4 + β4 = 3; -5 + β4 = 3; β4 = 8;
α1 + β5 = 0; 0 + β5 = 0; β5 = 0.
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых αi + βj > cij.
Таблица 6 – Опорный план
8 4 9 8 0
0 8
4 4
3 9
72 6 0
15 94
-7 1
84 9 4 7 0 84
-3 4 1
82 4 8 0 82
-5 8 5 4
13 3
86 0 99
88 85 85 86 15
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых αi + βj - cij > 0:
1.4: 0+8-6 = 2;
2.2: -7+4-9 = -12;
2.3: -7+9-4 = -2;
2.4: -7+8-7 = -6;
2.5: -7+0-0 = -7;
3.1: -3+8-4 = 1;
3.3: -3+9-4 = 2;
3.4: -3+8-8 = -3;
3.5: -3+8-8 = -3;
4.1: -5+8-8 = -5;
4.2: -5+4-5 = -6;
4.5: -5+0-0 = -5.
Выбираем максимальную оценку свободной клетки (1;4): 6Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
Таблица 7 – Перераспределительная таблица
8
4 4
3 9
72 [-] 6 [+] 0
15 94
1
84 9 4 7 0 84
4 1
82 4 8 0 82
8 5 4 [+]
13 3 [-]
86 0 99
88 85 85 86 15
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е
Задать вопрос
на новый заказ в Автор24.
