Модель транспортной задачи

Рассмотрим транспортную задачу, в которой речь идет о рациональной перевозке некоторого однородного продукта от производителей к потребителям.

Пусть имеется m пунктов производства однородного продукта (добыча руды в карьерах, производство автобусов, кондитерских изделий, компьютеров и т.д.) и n пунктов потребления этого продукта. Мощности пунктов производства составляют а_i единиц однородного продукта, а потребности каждого j -го пункта потребления равны единиц. Известны затраты на перевозку единицы продукта от i -го поставщика j -му потребителю. Составить такой план перевозок, при котором суммарные затраты на все перевозки были бы наименьшими.

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

Составим математическую модель задачи. Обозначим через - количество продукта, перевозимого из i -го пункта производства в j -й пункт потребления. Тогда матрица:

- план перевозок.

Матрицу называют матрицей затрат (тарифов).

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

Таблица 2.1 – Матрица затрат

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

,

а суммарные затраты выражаются функцией цели:

которую необходимо минимизировать при ограничениях:

(весь продукт из каждого i -го поставщика должен быть вывезен полностью),

(спрос каждого j – го потребителя должен быть полностью удовлетворен).

Из условия задачи следует, что все

Итак, математическая модель сбалансированной транспортной задачи имеет вид:

при ограничениях: