Модели исследования операций (Транспортная задача)

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А₁, А₂, …, А_m в n пунктов назначения В₁, В₂, …, В_n. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим С_ij тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через А_i – запасы груза в i-ом пункте отправления, через b_j – потребности в грузе в j-ом пункте назначения, а через Х_ij – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка зачади состоит в определении минимального значения функции

(1)

при условиях

(2)

(3)

(4)

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

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

= , (5)

то модель такой транспортной задачи называется закрытой. В противном случае – открытой. В случае превышения запаса над потребностью, т.е.

>

Вводится фиктивный (n+1) потребитель (или пункт назначения) с потребностью равной:

А соответствующие транспортные тарифы от всех поставщиков до фиктивного потребителя полагаются равными нулю. Полученная задача становится закрытой транспортной задачей, для которой выполняется равенство (5).

В случае превышения потребности некоторого потребителя над общими запасами, т.е.

<

Вводится фиктивный (m+1) пункт отправления с запасом груза в нем, равным с потребностью равной:

А соответствующие транспортные тарифы от фиктивного поставщика до всех потребителей полагаются равными нулю. Полученная задача становится закрытой транспортной задачей, для которой выполняется равенство (5).

Рассмотрим конкретную задачу:

Условие: Четыре предприятия Новгородской области (ООО «Старорусский хлеб, ИП Смородин, Старорусское РАЙПО и ООО «Пекарь») для производства продукции получают сырье от трех поставщиков. Потребности в сырье каждого из предприятий соответственно равны 900, 600, 800 и 600 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 600, 800 и 1000 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей:

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Обозначим через Х_ij количество единиц сырья, перевозимого из i-го пункта его получения на j-е предприятие. Задача является открытой, так как сумма запасов грузов 600 + 800 + 1000 = 2400 в местах отправления, не равна сумме потребностей грузов в местах назначения 900 + 600 + 800 + 600 = 2900. Так как потребности в грузах превышают их запасы, то вводим фиктивного поставщика (Поставщик 4), у которого запас груза равен 2900 – 2400 = 500. В этом случае общий запас станет равным 2900 и мы получим закрытую транспортную задачу. При этом все тарифы от фиктивного поставщика ко всем потребителям груза полагаются равными нулю. В матрице тарифов появится четвертая строка, в которой стоят все нули. Целевая функция не изменится.

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

Х₁₁ + Х₁₂ + Х₁₃ + Х₁₄ = 600 (6)

Х₂₁ + Х₂₂ + Х₂₃ + Х₂₄ = 800 (7)

Х₃₁ + Х₃₂ + Х₃₃ + Х₃₄ = 1000 (8)

Х₄₁ + Х₄₂ + Х₄₃ + Х₄₄ = 500 (9)

 

Х₁₁ + Х₂₁ + Х₃₁ + Х₄₁ = 900 (10)

Х₁₂ + Х₂₂ + Х₃₂ + Х₄₂ = 600 (11)

Х₁₃ + Х₂₃ + Х₃₃ + Х₄₃ = 800 (12)

Х₁₄ + Х₂₄ + Х₃₄ + Х₄₄ = 600 (13)

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

F = 4x₁₁ + 3x₁₂ + 2₁₃ + 1x₁₄ + 2x₂₁ + 1x₂₂ + 7x₂₃ + 9x₂₄ + 3x₃₁ + 6x₃₂ + 8x₃₃ + 4x₃₄ → min Таким образом, математическая постановка задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (6) – (13), при котором целевая функция принимает минимальное значение.

Для решения этой задачи средствами Microsoft Excel необходимо использовать опцию «Поиск решения». Все расчеты в формульном виде в Приложении Б.

 

Таблица 1 - Информация о поставщиках и покупателях

Пункты отправления	Пункты назначения	Запасы	Ограничения
Старорусский хлеб	ИП Смородин	Старорусское РАЙПО	Пекарь
Поставщик 1
Поставщик 2
Поставщик 3
Поставщик 4
	Итого:

 

Таблица 2 - Матрица затрат на перевозку

Пункты отправления	Пункты назначения
Старорусский хлеб	ИП Смородин	Старорусское РАЙПО	Пекарь
Поставщик 1
Поставщик 2
Поставщик 3
Поставщик 4

 

Задав ограничения и использовав для нахождения решения «Поиск решения», получаем, что минимальные затраты на перевозку грузов будут равны 5200 рублей.