Решение транспортной задачи

Транспортная задача является одной из задач линейного программирования. Слово «программирование» здесь обязано отчасти историческому недоразумению, отчасти неточному переводу. По-русски правильнее было бы употребить слово «планирование». С программированием для ЭВМ линейное программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования решаются с помощью компьютера.

Задача линейного программирования – найти x ₁, x ₂, … x _n, при которых достигает минимума линейная целевая функция вида

,

где c₁, c₂, … c_n – известные значения, при ограничениях в виде неравенств:

, .

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

В нашем случае постановка задачи следующая. Эффективное распределение потоков товаров от нескольких производителей нескольким потребителям. В случае различной стоимости перевозки единицы груза между разными предприятиями возникает вопрос: какие потребители должны снабжаться первым производителем (первым складом, первым распределительным центром), какие – вторым и др.

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

Постановка транспортной задачи:

Дано:

n – число поставщиков;

m – число потребителей;

a_i – запасы товаров, имеющиеся у i-го поставщика, i = 1, 2, … n;

b_i – потребности j-го потребителя, j = 1, 2, … m;

c_ij – затраты на транспортировку единицы груза от i-го поставщика j-му потребителю.

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

Найти: x_ij – количество товара, доставляемого от i-го поставщика j-му потребителю при минимальных затратах на транспортировку.

То есть, мы минимизируем функцию:

F = S _{i, j} c_ij x_ij ® min.

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

Следующее ограничение может быть задано различным образом.

1. Замкнутая транспортная задача – вся продукция должна быть распределена и все потребности должны быть удовлетворены.

S _ia_i = S _jb_j – сколько произвели, столько и приобрели.

Это ограничение записывается следующими системами уравнений:

– объем перевозок от каждого производителя ко всем потребителям равен мощности этого производителя.

– количество товаров, доставленных каждому потребителю, равен объему его потребностей.

2. Незамкнутая транспортная задача. Сумма произведенных товаров не совпадает с суммой потребностей.

S _ia_i > S _jb_j – несбалансированная задача с избытком. Произвели больше, чем приобрели.

S _ia_i < S _jb_j – несбалансированная задача с дефицитом. Произвели меньше, чем приобрели.

В этом случае ограничения представляются в виде неравенств.

Пример. Исходные данные о производителях и потребителях заносятся в таблицу. В углу ячейки записывается стоимость перевозки, в центре ячейки – объем перемещаемого по данному маршруту груза. Обязательно указывается мощность для каждого производителя и потребность для каждого потребителя.

- замкнутая задача, так как 40 + 80 + 110 + 50 + 90 = 100 + 150 + 90 + 30.