Построение математической модели.

Транспортная задача.

Имеется m поставщиков - пунктов производства (хранения) однородного продукта. Для каждого из поставщиков известна мощность, т.е. количество единиц продукции, доступных для отправки от соответствующего поставщика в единицу времени (неделю, месяц, квартал). Мощности будем обозначать: а₁, а₂,..., а_m,

Имеется n потребителей - пунктов потребления рассматриваемого продукта. Для каждого из потребителей предполагается известной потребность в единицу времени (неделю, месяц, квартал). Потребности будем обозначать: b₁, b₂,..., b_n.

Возможна доставка грузов от каждого поставщика к каждому потребителю. Удельные затраты (транспортные тарифы) на перевозку единицы продукта от поставщика с номером- i к потребителю с номером- j - известны для всех маршрутов и будут обозначаться с_ij. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы на доставку продуктов минимальны.

Рисунок 3.1. Графическое представление условий транспортной задачи.

Построение математической модели.

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

(3.1)

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

найти план перевозок Х = (х_ij), минимизирующий общую стоимость всех перевозок

(3.2)

при условии, что из каждого пункта производства вывозится весь продукт

(3.3)

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

(3.4)

причем по смыслу задачи все переменные могут принимать только неотрицательные значения х_ij ³0.

Из системы условий (3.2 – 3.5) видно, что транспортная задача является задачей линейного программирования. Но эта система имеет ряд особенностей, которые позволили разработать для решения транспортной задачи алгоритмы, более эффективные, чем симплекс-метод, предназначенный для решения задач линейного программирования общего вида.

Нарушение условий баланса: åа_i = åb_i

Если суммарная мощность поставщиков превосходит общий заказ потребителей, можно ввести фиктивный пункт потребления с объемом потребления b₀ =åа_i – åb_i, причем тарифы на перевозку в этот пункт условимся считать равными нулю.

Если суммарная мощность поставщиков меньше общего заказа потребителей, можно ввести фиктивного поставщика с мощностью а₀ =åb_i –åа_i, причем тарифы на перевозки из этого пункта условимся считать равными нулю.