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

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

Пусть для простоты заданы всего 4 месторождения М1, М2, М3, М4, причем их ежемесячная добыча составляет a1, а2, а3, а4 тонн угля. Предположим далее, что этот уголь надо доставить в пункты потребления b1, b2, b3, b4, b5, соответственно с ежемесячными потребностями этих пунктов. Будем считать, что общее производство угля равно суммарной потребности в нем (сбалансированность планов): a1, а2, а3, а4= b1, b2, b3, b4, b5. Задача состоит в определении такого плана перевозок, при котором общая стоимость перевозок была бы наименьшей. Обозначим через x11 количество угля (в тоннах), предназначенное к отправлению из M1 в П1; вообще через xij обозначим количество угля, отправляемого из месторождения Mi в пункт потребления Пj. Схема перевозок примет вид, изображенный в таблице 4.1.

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

Общее количество угля, привозимое в пункт П1 из всех месторождений, будет х11+х12+х13+х14+х15 = b1; в другие пункты - П2, П3 и т.д. и примет вид уравнений 4.1. общее количество угля, вывозимое из М1, будет: х11+х12+х13+х14+х15 = a1, примет вид 4.2. предполагаем, что стоимость перевозки прямо пропорциональна количеству перевозимого угля, т.е. стоимость перевозки xij тонн угля равна:

x ij= C ij.X ij

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