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

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

Пусть для простоты заданы всего 4 месторождения М₁, М₂, М₃, М₄, причем их ежемесячная добыча составляет a₁, а₂, а₃, а₄ тонн угля. Предположим далее, что этот уголь надо доставить в пункты потребления b₁, b₂, b₃, b₄, b₅, соответственно с ежемесячными потребностями этих пунктов. Будем считать, что общее производство угля равно суммарной потребности в нем (сбалансированность планов): a₁, а₂, а₃, а₄ = b₁, b₂, b₃, b₄, b₅. Задача состоит в определении такого плана перевозок, при котором общая стоимость перевозок была бы наименьшей. Обозначим через x₁₁ количество угля (в тоннах), предназначенное к отправлению из M₁ в П₁; вообще через x_ij обозначим количество угля, отправляемого из месторождения M_i в пункт потребления П_j. Схема перевозок примет вид, изображенный в таблице 4.1.

Схема перевозок таблица 4.1

Общее количество угля, привозимое в пункт П₁ из всех месторождений, будет х₁₁₊х₁₂₊х₁₃₊х₁₄₊х_{15 =} b₁; в другие пункты - П₂, П₃ и т.д. и примет вид уравнений 4.1. общее количество угля, вывозимое из М₁, будет: х₁₁₊х₁₂₊х₁₃₊х₁₄₊х_{15 =} a₁, примет вид 4.2.предполагаем, что стоимость перевозки прямо пропорциональна количеству перевозимого угля, т.е. стоимость перевозки x_ij тонн угля равна:

x _{i j} = C _{i j} ^. X _{i j}

Общая стоимость S всех перевозок будет равна: (4.3)