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

Транспортные задачи и их решение средствами Excel

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления А₁, А₂, …, А_m в n пунктов назначения В₁, В₂, …, В_n .

При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим c_ij тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через a_i – запасы груза в i-ом пункте отправления, через b_j – потребности в грузе в j-ом пункте назначения, а через x_ij – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

(1)

при условиях

(2)

(3)

(4)

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

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

= , (5)

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

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

вводится фиктивный (n+1) потребитель (или пункт назначения) с потребностью равной b_n ₊₁ = – , а соответствующие транспортные тарифы от всех поставщиков до фиктивного потребителя полагаются равными нулю. Полученная задача становится закрытой транспортной задачей, для которой выполняется равенство (5).

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

вводится фиктивный (m+1) пункт отправления с запасом груза в нем, равным с потребностью равной a_m ₊₁ = – , а соответствующие транспортные тарифы от фиктивного поставщика до всех потребителей полагаются равными нулю. Полученная задача становится закрытой транспортной задачей, для которой выполняется равенство (5).

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

Задача. Четыре предприятия данного экономического района для производства продукции получают сырье от трех поставщиков. Потребности в сырье каждого из предприятий соответственно равны 900, 600, 800 и 600 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 600, 800 и 1000 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

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

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

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

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

x₁₁ + x₁₂ + x₁₃.+ x₁₄.= 600 (6)

x₂₁ + x₂₂ + x₂₃.+ x₂₄.= 800 (7)

x₃₁ + x₃₂ + x₃₃.+ x₃₄.= 1000 (8)

x₄₁ + x₄₂ + x₄₃.+ x₄₄.= 500 (9)

x₁₁ + x₂₁ + x₃₁. + x₄₁ = 900 (10)

x₁₂ + x₂₂ + x₃₂..+ x₄₂= 600 (11)

x₁₃ + x₂₃ + x₃₃. + x₄₃= 800 (12)

x₁₄ + x₂₄ + x₃₄. + x₄₄= 600 (13)

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

F = 4x₁₁ + 3x₁₂ + 2₁₃.+ 1x₁₄ + 2x₂₁ + 1x₂₂.+ 7x₂₃ +

+ 9x₂₄ + 3x₃₁ + 6x₃₂.+ + 8x₃₃ + 4x₃₄ → min. (14)

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

Дата добавления: 2021-04-15; просмотров: 70; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 Следующая ⇒

Мы поможем в написании ваших работ!