Исходные данные для решения транспортной задачи

Таблица 1

ТРЕНИРОВОЧНОЕ ЗАДАНИЕ

Постановка и решение транспортной задачи методом «северо-западного угла»

Транспортная задача может быть формализовано описана следующим образом.

Имеется т поставщиков определенного вида продукции (либо т — количество мест, складов, откуда происходит поставка продукции). Максимальные объемы возможных поставок заданы и равны соответственно а_ь i = 1, 2,..., т. Эта продукция используется п, потребителями. Объемы потребностей заданы и равны соответственно b_j, j= 1, 2,..., п. Стоимость перевозки единицы продукции от i-го поставщика к j- мупотребителю известна для всех i, j и равна с_ij.

Установите такие объемы перевозок x_ij от каждого поставщика к каждому потребителю, чтобы суммарные затраты на перевозки были минимальными и потребности всех потребителей были удовлетворены (если только общий объем возможных поставок покрывает общий объем потребностей).

Задача. На двух складах (A и В) имеется соответственно 50 и 40 т продукции.

Стоимость перевозки от складов к потребителям приведена в табл. 1 (в правом верхнем углу каждой клетки). Например, стоимость перевозки единицы (1т) груза со склада А потребителю С равна 3 у.е.

Спланируйте перевозки к трем потребителям (С, D и Е) так, чтобы потребитель С получил 30 т груза, потребитель D — 20 т, потребитель Е — 40 т, а затраты на перевозку были минимальными.

Для решения задачи на первом этапе составляется система ограничений и целевая функция. Система ограничений в общем виде (для нашей задачи) имеет вид

причем Х_ij > 0 для i = 1, 2; j = 1, 2, 3.

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

Далее перераспределяются объемы поставок грузов методом «северо-западного угла», т.е. первой заполняется верхняя левая (северо-западная) клетка исходной таблицы. Примем объем перевозки

со склада А к потребителю С максимально возможным из условий задачи и равным 30 т. Потребитель С полностью удовлетворил свою потребность, и поэтому графу «С» в табл. 1 можно исключить из дальнейшего рассмотрения.

В таблице 1 найдем «северо-западный угол» (теперь это клетка AD) и укажем максимально возможное значение. Оно рассчитывается следующим образом: со склада Л уже перевезено 30 т груза, поэтому остаток на этом складе составляет 20 т (50—30). Вносим в клетку AD вместо х_п значение, равное 20 т. Таким образом, весь груз со склада А перевезен потребителям и первая строка табл. 1 исключается из дальнейшего рассмотрения. Потребитель D полностью удовлетворил свою потребность в грузе, и графу D можно исключить из дальнейшего рассмотрения. В оставшейся части табл. 1 найдем новый «северо-западный угол» (клетка BE) и укажем в нем максимально возможное значение (40 т). В результате (в табл. 2) получено следующее распределение поставок: х₁₁ = 30; х₁₂ = 20; х₂₃ ⁼ 40.