Перевозки взаимозаменяемых продуктов

Известны объемы и потребности продукции каждого вида. Если продукты, подлежащие перевозке, качественно совершенно различны (уголь, цемент, сахар), так что ни один из них не может быть использован вместо другого, то задача составления оптимального плана перевозок распадается на ряд обычных транспортных задач по каждому продукту (углю, цементу, сахару).

Если неоднородные продукты взаимозаменяемы (топливо разных сортов, или топливо одной и той же марки, добываемое в разных районах, цемент различных марок) – решается транспортная задача планирования перевозок неоднородных взаимозаменяемых продуктов (распределение взаимозаменяемых продуктов по пунктам потребления).

Требуется составить план перевозок топлива разных сортов из пунктов производства А_i (i = 1,…, m) в пункты потребления B_j (j = 1,…, n). b_j – спрос на топливо в j–ом пункте потребления, спрос выражается в приведенных единицах (например, в калориях теплоотдачи).

Пункт добычи нескольких различных сортов топлива рассматривается как несколько различных пунктов производства (число пунктов производства и число сортов топлива совпадают). Пусть в пункте А_i количество добытого топлива i-го сорта равно а_i.

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

Обозначим через с_ij затраты на перевозку 1т топлива i-го сорта к j–му пункту, через х_ij –количество топлива i-го сорта, поставляемое j–му потребителю.

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

Математическая модель.

- суммарные транспортные издержки на перевозку топлива

при условиях

λ_ij х_ij = b_j, j = 1,…, n – объем доставленного в каждый пункт потребления топлива в приведенных единицах теплоотдачи равен спросу этого пункта

х_ij ≤ а_i , i = 1,…, m - общий объем топлива, направляемый во все пункты потребления из i-го пункта производства, не превышает запасов топлива i-го сорта.

x_ij ≥ 0, i = 1,…, m, j = 1,…, n.

Если коэффициенты приведения одни и те же для разных пунктов потребления, распределительная задача сводится к классической транспортной задаче.

Перевозка неоднородного продукта на разнородном транспорте.

Для обеспечения перевозок может быть использовано s автохозяйств, в каждом из которых r типов автомашин. Машины разных типов, обладая различными эксплуатационными характеристиками и разной скоростью, могут доставлять любой из m грузов каждому из n потребителей.

Расстояние от места расположения g-го автохозяйства (g = 1,…., s) до пункта производства i-го груза (i = 1,…, m) известно. Известна скорость машин к-го типа (к = 1, …, r) для всех маршрутов. Известно время погрузки и разгрузки машин каждого типа в каждом пункте назначения. С учетом этой информации можно определить t_ijgk время занятости одной машины к-го типа g-го автохозяйства на работах по перевозке i-го груза j-му потребителю (или любые другие виды затрат, связанные с перевозкой единицы i-го груза в j-ый пункт назначения на одной машине к-го типа из g-го автохозяйства).

Параметры модели

a_gк – количество машин к-го типа в g-ом автохозяйстве;

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

d_ij – число единиц i-го груза, которое перевозится в j-ый пункт назначения на одной машине (определяется по известной грузоподъемности машин).

Учет различной грузоподъемности машин приводит к распределительной задаче.

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

Примем х_ijgk – количество машин к-го типа из g-го автохозяйства, предназначенных для перевозки i-го груза j-му потребителю.

Математическая модель.

Определить значения переменных х_ijgk, на которых достигается минимум

t_ijgk х_ijgk → min

при условиях

х_ijgk ≤ а_gk,_, g = 1,…., s, к = 1, …, r - общее число машин к-го типа, направленных из g-го автохозяйства на перевозку всех грузов ко всем потребителям, не может превысить числа транспортных единиц к-го типа, которым располагает g-е автохозяйство;

d_ij х_ijgk = c_ij, i = 1,…, m, j = 1,…, n – спрос каждого пункта потребления в каждом виде груза должен быть полностью удовлетворен,

х_ijgk ≥ 0, i = 1,…, m, j = 1,…, n, g = 1,…., s, к = 1, …, r.

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

Каждый пункт, потребляющий m различных грузов рассматривается как группа из m различных пунктов, а автохозяйство с r типами машин учитывается как r автохозяйств. Соответственно определяются потребности каждого пункта назначения и возможности каждого транспортного подразделения.

Заменим пары индексов (i, j) и (g, к) двумя индексами λ и μ по следующим формулам:

λ = i + m (j – 1), μ = g + s (к – 1)

Когда индекс I пробегает значения 1,2, …, m, а j - значения 1,2, …, n, индекс λ принимает все целочисленные значения от 1 до mn. Индекс μ пробегает значения 1,2, …, sr.

Введем замену переменных х_ijgk = z_{λ μ}, i = 1,…, m, j = 1,…, n, g = 1,…., s, к = 1, …, r.

Обозначим t_ijgk через τ_{λ μ}, отношение c_ij / d_ij через g_λ, а_gk через b_μ.

В новых обозначениях задача сводится к вычислению переменных z_λμ, обращающих в минимум линейную форму

τ_{λ μ} z_λμ → min

при условиях

z_λμ ≤ b_μ, μ = 1,2, …, sr,

z_λμ = g_λ, λ = 1,2,…, mn,

z_λμ ≥ 0, λ = 1,2,…, mn, μ = 1,2, …, sr.

Пришли к обычной транспортной задаче размеров mn х sr. По компонентам z_λμ оптимального плана задачи вычисляются составляющие х_ijgk. При этом индексы i и j вычисляются по формулам

m, если λ кратно m,

i = { остатку от деления λ на m, если λ не делится на m;

λ / m, если λ кратно m,

j = { целой части выражения (λ / m + 1), если λ не делится на m;

Аналогичным путем вычисляются индексы g и к.