Транспортная задача. Важным частным случаем задачи линейного программирования является так называемая транспортная задача

Важным частным случаем задачи линейного программирования является так называемая транспортная задача.

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

Рассмотрим пример транспортной задачи линейного программирования.

Некоторый однородный товар производится на трех заводах и поставляется четырем торговым базам. Мощность поставщиков и спросы потребителей, а также затраты на перевозку единицы товара для каждой пары «завод - торговая база» сведены в следующую таблицу поставок (табл. 3).

Таблица 3

Затраты на перевозку единицы товара

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

Задача ставится следующим образом: найти объемы перевозок для каждой пары «поставщик – потребитель» так, чтобы:

- мощности всех поставщиков были реализованы;

- спросы всех потребителей были удовлетворены;

- суммарные затраты на перевозку были бы минимальны.

Построим экономико-математическую модель данной транспортной задачи.

Обозначим искомые объемы поставок от -ого поставщика -му потребителю через .

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

(3.1.7)

Аналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса составляем для каждого столбца таблицы поставок:

(3.1.8)

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует дополнительно предположить, что

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

(3.1.9)

Теперь можно дать математическую формулировку задачи (без обращения к ее содержательному экономическому смыслу). На множестве неотрицательных решений системы ограничений (3.1.7) и (3.1.8) найти такое решение , при котором линейная функция (3.1.9) принимает минимальное значение.

Особенности экономико-математической модели транспортной задачи:

- система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме);

- коэффициенты при переменных системы ограничений равны единице или нулю;

- каждая переменная входит в систему ограничений два раза: один раз – в систему (3.1.7) и один раз – в систему (3.1.8).

Для математической формулировки транспортной задачи в общей постановке обозначим через коэффициенты затрат, через - мощности поставщиков, через - спросы потребителей, где , – число поставщиков, – число потребителей. Тогда система ограничений примет вид:

(3.1.10)

. (3.1.11)

Система (3.1.10) включает в себя уравнение баланса по строкам, а система (3.1.11) – по столбцам. Линейная функция в данном случае

. (3.1.12)

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

Произвольное допустимое решение системы ограничений (3.1.10), (3.1.11) назовем распределением поставок. Такое решение задает заполнение таблицы поставок, поэтому в дальнейшем значение произвольной переменной и содержимое соответствующей клетки таблицы поставок будут отождествляться.

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

.

Такие транспортные задачи называются открытыми (говорят также, что транспортная задача в этом случае имеет открытую модель). В противном случае транспортная задача называется закрытой (закрытая модель транспортной задачи).

Для решения открытой транспортной задачи необходимо свести ее к закрытому виду.

Поскольку в представленной транспортной задаче суммарный спрос потребителей меньше суммарной мощности поставщиков на 90:

сведем данную транспортную задачу к закрытой путем введения фиктивного потребителя В5 с недостающим спросом :

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

Таблица 4

Затраты на перевозку единицы товара (с учетом фиктивного потребителя)

С учетом фиктивного потребителя математическая модель будет иметь вид:

Поиск по сайту: