3. Решение задач

3.1 Задача с неразличимыми поставщиками и потребителями

При постановке транспортной задачи присутствуют поставщики и потребители продукции. При этом подразумевается, что продукция перемещается от поставщика к потребителю. Вместе с тем возможны и другие маршруты перемещения продукции. Например, продукция от одного поставщика может перемещаться к другому поставщику, от потребителя к потребителю. Таким образом, при таком перемещении продукции поставщик и потребитель выступают сразу в двух ролях, то есть нет различий между поставщиками и потребителями. Для моделирования такой схемы перемещения вводится понятие буфера В. Буфер - это количество всей перевозимой продукции. Так, например, если имеются три поставщика А, B, C, которые поставляют продукцию в количестве соответственно 100 ед., 300 ед., 400 ед., то величина буфера должна быть равна B = 100 ед. + 300 ед. + +400 ед. = 800 ед. Такой же буфер должен присутствовать и у потребителя. При наличии двух потребителей D и E с объёмами потребления соответственно 250 ед. и 550 ед. B = 250 ед. + 550 ед. = 800 ед. Для отражения затрат на перемещение единицы продукции между всеми участниками транспортной схемы вводятся так называемые тарифы на перемещение. В данной рассматриваемой задаче естественно положить тариф на перемещение внутри каждого узла, равным нулю. Таким образом, при заданных условиях начальная транспортная таблица будет иметь вид:

Решение это транспортной задачи с изменёнными тарифами приводит к следующему оптимальному плану перемещения продукции:

Результаты расчёта представим в виде графа:

Из графа видно, что поставщик B поставляет продукцию потребителю E транзитом через поставщика C. В данном случае поставщик C выступает в роли потребителя. 3.2. Транспортная модель с промежуточными пунктами

Используя понятие буфера, рассмотренное выше, можно моделировать большое количество транспортных схем перевозки продукции. На практике во многих случаях продукция от поставщика попадает к потребителю через транзитные пункты. Такая схема доставки продукции является более общей, чем непосредственная транспортировка продукции от поставщика потребителю. Разработка схемы перевозки с промежуточными пунктами для различных практических случаев осуществляется на основе однообразных логических построений. Для иллюстрации метода решения таких задач рассмотрим конкретный пример транспортной задачи с двумя пунктами производства, одним транзитным пунктом и тремя пунктами потребления. Исходные данные для задачи представим в виде графа:

В рассматриваемой задаче имеются: пять пунктов отправления продукции (A, B, C, D, F), четыре пункта назначении (C, D, F, E) и три транзитных пункта (C, D, F), через которые проходит транзитом продукция в объёме (100 + 200) = 300 ед. Поэтому в пункте D может присутствовать (300 + 50) = 350 ед., в пункте F (300 + 100) = 400 ед. Значения тарифов перемещения продукции изображены над дугами, соединяющими пункты транспортной сети. Для моделирования невозможности перемещения между пунктами, не соединёнными дугами, тарифы перевозок для них принимаются на несколько порядков больше, чем остальные тарифы. В этом примере их можно принять равными 100. Тариф перевозки внутри самого пункта принимается равным нулю. Метод решение этой задачи ничем не отличается от ранее рассмотренных задач.

Оптимальный опорный план имеет следующий вид:

Это решение представим в виде графа:

Из графа видно, что вся продукция (300 ед.) из транзитного пункта C поступает в пункт потребления D, в котором остаётся потребляемое количество 50 ед. Остаток в объёме 250 ед. поступает в пункт F, из которого 100 ед. остаются, оставшиеся 150 ед. идут на потребление в пункт E. Таким образом, используя понятия транзитного пункта и буфера, а также варьируя значениями тарифов перевозки, можно смоделировать и решить многочисленные транспортные задачи.

3.3 Задача из школьного курса информатики

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

Для решения данной задачи построим ее математическую модель. Неизвестными в данной задаче являются объемы перевозок. Пусть

X_ij - объем перевозок, а с_ij - стоимость перевозки единицы продукции с i-й фабрики на j-й склад соответственно. Функция цели - это суммарные транспортные расходы, которые следует минимизировать, т.е.:

min. (1)

Неизвестные X_ij должны удовлетворять ограничениям. Так как модель сбалансирована, то вся продукция должна быть вывезена с фабрик

j [1, 3], (2)

а потребности всех центров распределения должны быть полностью удовлетворены:

i [1, 5]. (3)

Объемы перевозок не должны быть отрицательными:

x_ij i [1, 3], j [1, 5]. (4)

Здесь а_i - объем производства на i-й фабрике, b_j - спрос в j-м центре распределения.

Рабочий лист Excel с введенными исходными данными для решения транспортной задачи:

Выберем команду Сервис/Надстройки, в появившемся диалоговом окне Надстройки установим флажок Поиск решения и щелкнем на кнопке ОК.

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

транспортный задача симплекс граф