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

Задача 17

В пунктах  производится продукция в количествах     единиц.

Себестоимость единицы продукции в i-м пункте равна . Готовая продукция поставляется в пункты  , потребности которых составляют  единиц.

Стоимость перевозки единицы продукции из пункта в пункт

заданы матрицей [ ].

Требуется:

1) методом потенциалов найти план перевозок продукции, при котором минимизируются суммарные затраты по ее изготовлению и доставке потребителям;

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

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

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

Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 250 + 650 + 300 = 1200
∑b = 350 + 50 + 150 + 450 = 1000
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 200 (1200—1000). Тарифы перевозки единицы груза к этому потребителю полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.

Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.

Значение целевой функции для этого опорного плана равно:
F(x) = 5*50 + 4*150 + 6*50 + 8*50 + 9*400 + 0*200 + 1*300 = 5450
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₁ = 5; 0 + v₁ = 5; v₁ = 5
u₃ + v₁ = 1; 5 + u₃ = 1; u₃ = -4
u₁ + v₃ = 4; 0 + v₃ = 4; v₃ = 4
u₁ + v₄ = 6; 0 + v₄ = 6; v₄ = 6
u₂ + v₄ = 9; 6 + u₂ = 9; u₂ = 3
u₂ + v₂ = 8; 3 + v₂ = 8; v₂ = 5
u₂ + v₅ = 0; 3 + v₅ = 0; v₅ = -3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(2;1): 3 + 5 > 7; ∆₂₁ = 3 + 5 - 7 = 1

Выбираем максимальную оценку свободной клетки (2;1): 7
Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Цикл приведен в таблице (2,1 → 2,4 → 1,4 → 1,1).
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₃ = 4; 0 + v₃ = 4; v₃ = 4
u₁ + v₄ = 6; 0 + v₄ = 6; v₄ = 6
u₂ + v₄ = 9; 6 + u₂ = 9; u₂ = 3
u₂ + v₁ = 7; 3 + v₁ = 7; v₁ = 4
u₃ + v₁ = 1; 4 + u₃ = 1; u₃ = -3
u₂ + v₂ = 8; 3 + v₂ = 8; v₂ = 5
u₂ + v₅ = 0; 3 + v₅ = 0; v₅ = -3

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij
(3;4): -3 + 6 > 2; ∆₃₄ = -3 + 6 - 2 = 1
Выбираем максимальную оценку свободной клетки (3;4): 2
Для этого в перспективную клетку (3;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Цикл приведен в таблице (3,4 → 3,1 → 2,1 → 2,4).
Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 1) = 300. Прибавляем 300 к объемам грузов, стоящих в плюсовых клетках и вычитаем 300 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.
u₁ + v₃ = 4; 0 + v₃ = 4; v₃ = 4
u₁ + v₄ = 6; 0 + v₄ = 6; v₄ = 6
u₂ + v₄ = 9; 6 + u₂ = 9; u₂ = 3
u₂ + v₁ = 7; 3 + v₁ = 7; v₁ = 4
u₂ + v₂ = 8; 3 + v₂ = 8; v₂ = 5
u₂ + v₅ = 0; 3 + v₅ = 0; v₅ = -3
u₃ + v₄ = 2; 6 + u₃ = 2; u₃ = -4

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.
Минимальные затраты составят: F(x) = 4*150 + 6*100 + 7*350 + 8*50 + 9*50 + 0*200 + 2*300 = 5100
Ответ:Анализ оптимального плана.
Из 1-го склада необходимо груз направить к 3-у потребителю (150), к 4-у потребителю (100)
Из 2-го склада необходимо груз направить к 1-у потребителю (350), к 2-у потребителю (50), к 4-у потребителю (50)
Из 3-го склада необходимо часть груза (300) направить к 4-у потребителю.
На 2-ом складе остался невостребованным груз в количестве 200 ед.
Оптимальный план является вырожденным, так как базисная переменная x₂₅=0.