4.2.3. Задача оптимизации перевозок однородного продукта

Эта задача является одной из важных задач в оптимизационной деятельности организационно-технических систем. Одной из первых задач оптимизации перевозок явилась классическая транспортная задача (КТЗ).

Основные предположения КТЗ:

1) потребности пунктов назначения перевозок груза удовлетворяются за счёт нескольких пунктов его отправления,

2) величина транспортных расходов при перевозке груза пропорциональна количеству перевозок по каждому маршруту.

Пусть имеется однородная продукция, сосредоточенная у m поставщиков в объёмах соответственно . Этот продукт необходимо доставить n потребителям, которые имеют потребности в нём, равные . Пусть заданы – стоимость перевозки единицы продукта от i-го поставщика j-му потребителю . Требуется определить величины объёмов продукта, перевозимого от i-го поставщика j-му потребителю. Транспортная задача графически представлена на рисунке 4.3.

Рис. 4.3

Все маршруты перевозок являются возможными.

Будем считать, что запасы и потребности в системе сбалансированы:

. (4.21)

Переменные в этом случае должны удовлетворять ряду условий. Запасы всех поставщиков должны быть вывезены:

. (4.22)

Все потребности в системе должны быть удовлетворены:

. (4.23)

Условие того, что не все маршруты перевозок могут быть реализованы:

. (4.24)

Суммарная стоимость всех перевозок с учетом транспортных расходов вычисляется как:

. (4.25)

КТЗ формулируется в следующем виде: требуется определить значение переменных , доставляющих минимум целевой функции (4.25) при выполнении ограничений (4.21) - (4.24). Видно, что данная модель является линейной моделью ЗПР. Модель (4.25), (4.21) - (4.24) при наличии условия (4.21) называется закрытой транспортной задачей по критерию стоимости.

В реальных задачах условие (4.21) часто нарушается. Рассмотрим два возможных случая:

1. Сумма запасов превышает сумму потребностей данной продукции

. (4.27)

Так как в этом случае все запасы не могут быть вывезены, то условие (4.22) заменяется условием вида:

. (4.28)

2. Сумма потребностей превышает сумму запасов:

. (4.29)

В этом случае часть потребностей не удастся удовлетворить, поэтому ограничение вида (4.23) заменяется неравенством:

. (4.30)

Математические модели вида (4.25), (4.23), (4.28), (4.24) и (4.25), (4.22), (4.30), (4.24) описывают открытые транспортные задачи. Как закрытые, так и открытые транспортные задачи являются задачами линейного программирования и могут быть решены соответствующими численными методами. Однако, если размерность задачи слишком велика (для больших и ), то эти методы являются весьма трудоемкими. Однако для закрытой транспортной задачи (ТЗ) имеются свои более простые методы решения, в которых используется табличная форма представления исходных данных.

С учетом сказанного, рассмотрим методы сведения открытой КТЗ к закрытой КТЗ.

1. Пусть в системе выполняются условия вида (4.27) в этом случае вводится фиктивный (n + 1) потребитель, с потребностью равной:

,

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

2. Пусть в системе выполняется условие вида (4.29). В этом случае вводится фиктивный (m + 1) поставщик с запасом, равным

,

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

Вследствие вида критерия (4.25) и бесконечной стоимости перевозок при автоматически обнуляются переменные и . При практических расчетах коэффициенты и обычно полагают равными очень большим числам, на несколько порядков выше, чем реальный . Аналогичным образом с помощью коэффициентов можно ввести запрещающий маршрут и в закрытой КТЗ.

Рассмотрим свойства классической транспортной задачи. Задача (4.25), (4.21) - (4.24), как задача линейного программирования специального типа имеет следующие особенности:

1) Все коэффициенты при x_ij в ограничениях (4.22) и (4.23) равны 1.

2) Система ограничений (4.22), (4.23) включает в себя уравнений.

3) Ранг системы (4.22), (4.23) вследствие (4.21) равен . Это означает, что оптимальное решение задачи (4.25), (4.21) - (4.24) будет содержать ненулевых объемов перевозок.

Докажем, что любая закрытая ТЗ имеет решение.

Конкретизируем условие (4.21) в следующем виде:

, (4.31)

где , величина суммарного объема запасов и потребностей в системе.

Выберем объем перевозок в системе по формуле

. (4.32)

Покажем, что решение вида (4.32) является допустимым решением задачи (4.25), (4.21) - (4.24).

Подставив величину (4.32) в выражение (4.22), (4.23) получим подтверждение условий (4.22), (4.23) при выбранном решении. Условие (4.24) выполняется очевидным образом, так как все и . Отсюда следует, что допустимое множество решений задачи (4.25), (4.21) - (4.24) не пустое, так как содержит хотя бы одну точку вида (4.32).

Покажем, что целевая функция (4.25) ограничена. Выберем в матрице стоимости перевозок максимальный и минимальный элемент , . Внесем в матрицу сначала , а затем и посчитаем при этом значение целевой функции для выбранного решения (4.32). В итоге получим следующее двойное неравенство, свидетельствующее об ограниченности целевой функции сверху и снизу: .