Целевая функция на минимум издержек имеет вид

Задача оптимизации транспортных расходов (Т-задача)

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

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

Сложной является проблема определения однородности продукции. Однородность продукции необходимо оценивать не только с точки зрения ее качества, но и по способу транспортировки. Так, некоторые продукты можно перевозить в таре или наливом в цистернах, в специальной упаковке или в контейнерах и т.п. В этих случаях затраты на транспортировку одного и того же продукта будут различными, и по этой причине продукт нельзя считать однородным.

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

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

В m пунктах А₁, А₂, …, А_m производится некоторый однородный продукт, причем объем производства в пункте А _i составляет a _i единиц (i =1, 2, …, m).

Указанный продукт потребляется в n пунктах В₁, В₂, …, В_n, а объем потребления в пункте В_j составляет b_j единиц (j =1, 2, …, n).

Известны транспортные расходы по перевозке единицы продукции из пункта А_i в пункт В_j, которые равны С_{i j} и приведены в матрице транспортных расходов С:

С₁₁ С₁₂…С_1n

C = C₂₁C₂₂…C_2n

..........

C_m C_m2…C_mn

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

Для составления математической модели данной задачи принимаем количество продукта, перевозимого из пункта А_i в пункт В_j равным X_ij. В этом случае поставленные нами условия можно записать следующим образом.

Определить множество переменных X_ij ≥ 0 (I = 1, 2, …, m, j = 1, 2, …, n), удовлетворяющих условиям

а_i (1)

b_i (2)

при которых целевая функция достигает минимума

Z = (3)

Условие, необходимое и достаточное для разрешимости данной задачи, сводится к балансу

(4)

Условие (1) характеризует вывоз продукции из всех пунктов производства, а условие (2) означает полное удовлетворение спроса во всех пунктах потребления.

Переменные нумеруют с помощью двух индексов, а набор X_ij, удовлетворяющий условиям (1) и (2), записывают в виде матрицы.

Х₁₁ Х₁₂ … Х_1n

Х = Х₂₁ Х₂₂ … Х_2n

....…………….

Х_m1 Х_m2 … Х_mn

Матрицу Х называют планом перевозок Т-задачи, а переменные X_ij – перевозками. План Х_опт, при котором целевая функция (3) минимальная, называется оптимальным планом.

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

Ресурсы поставщиков: а₁ =170, а₂ = 250, а₃ =180;

Фонды потребителей: b₁ =150, b₂ = 230, b₃ =160, b₄ = 60

Матрица транспортных расходов дана в табл. 5.

Таблица 5

Матрица транспортных расходов

Поставщик	Потребитель
	С11=3 C21=6 C31=5	C12=5 C22=4 C32=4	C13 =6 С23=7 С33=6	С14=2 С24=5 С34=5

В этой задаче ограничения можно записать следующим образом:

а) по ресурсам поставщиков

Х₁₁ + Х₁₂ + Х₁₄ = 170,

Х₂₁ + Х₂₂ + Х₂₄= 250,

Х₃₁+ Х₃₂ + Х₃₄ = 180,

б) по фондам потребителей

Х₁₁ + Х₂₁ + Х₃₁ = 150,

Х₁₂ + Х₂₂ + Х₃₂ = 230,

Х₁₃+ Х₂₃ + Х₃₃ = 160,

Х₁₄ + Х₂₄ + Х₃₄ = 60

в) при условиях не отрицательности поставок

Х₁₁ ≥ 0, Х₁₂ ≥ 0, … Х₃₄ ≥ 0.

3Х₁₁ + 5Х₁₂ + 6Х₁₃ + 2Х₁₄ + 6Х₂₁ + 4Х₂₂ + 7Х₂₃ + 5Х₂₄ + 5Х₃₁ +4Х₃₂ + 6Х₃₃ + 5Х₃₄ → min

Одним из методов решения транспортной задачи является «Метод разницы расстояний». Рассмотрим его на примере: установить экономически целесообразные связи между поставщиками и потребителями с применением транспортной задачи.

Количество однородного груза, который необходимо отправить от поставщика А десяти потребителям, составляет 450 т и от поставщика Б тем же потребителям 520. Всего потребители должны получить 970 т. груза.

Количество груза, необходимое потребителям, расстояние между поставщиками и потребителями приводится в табл.6.

Таблица 6

Номер потребителя	Кол-во груза, необходимое потребителям	Расстояние до потребителей от поставщика:
А	Б
1.
2.
3.
4.
5.
6.
8.
9.
10.

Решение: для решения задачи составим табл. 7

Таблица 7

Поставщик	Потребители	Общий объем поставки: т.
А/расстоян/
Б/расстоян/
РАЗМЕР ПОТРЕБЛЕНИЯ: т
РАЗНОСТЬ РАССТОЯНИЙ (КМ) МЕЖДУ /А и Б/
	-170		-45			-115				-85
		100-50		95-90	135-70		190-120)	210-145	125-80
	30-200		65-110			35-150				75-160

Расположим потребителей в порядке уменьшения разности расстояний. Записываем размеры потребления в первую строку в правый нижний угол до тех пор, пока не исчерпаем общие объемы поставки поставщика А. Остальную часть общей поставки расписываем между потребителями второй строки /поставщик Б/.

Таблица 8

Поставщик	Потребитель
									I	Общий объем поставки, т.
А
Б
Разность расстояний, км
							-45	-85	-115	-170

Таким образом, поставщик А направляет грузы потребителям № 8, 7, 5, 2, 9 соответственно 45, 150, 80, 120, 55т., а поставщик Б – потребителям № 90, 4, 3, 10, 6, I соответственно 135, 35, 170, 20, 110, 50т.

Дата добавления: 2014-12-29