Постановка транспортной задачи в матричной форме

Пусть имеется m поставщиков А₁, А₂,…, А_m , располагающих некоторым однородным грузом в объемах по а_i единиц ( ), и n потребителей В₁, В₂,…, В_n с объемами потребления по b_j единиц ( ). Задана матрица C=||c_ij||, где c_ij – стоимость перевозки единицы груза от i-го поставщика j-му потребителю. Требуется составить план перевозок, при котором все запасы поставщиков будут вывезены, спрос потребителей полностью удовлетворен, и при этом суммарные транспортные издержки будут минимизированы. Матрица Х=||х_ij||, где х_ij ( ; ) – количество единиц груза, поставляемое от i-го поставщика j-му потребителю, называется планом (матрицей) перевозок. Предполагается, что x_ij ³ 0 ( ; ). Матрица C = || c_ij || ( ; ) называется матрицей тарифов или матрицей стоимости.

Для наглядности условие транспортной задачи записывают в виде таблицы 2.1.

Таблица 2.1 – Матричная модель ТЗ.

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

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

(2.1)
Если условие (2.1) не выполняется, то задача называется задачей открытого типа.

Любую задачу открытого типа можно свести к задаче закрытого типа.

В случае, если суммарные запасы поставщиков больше потребностей получателей (т. е. ), вводят (n + 1)-го фиктивного потребителя, потребности которого равны излишку запаса, т. е.

(2.2)
Стоимости перевозки единицы груза от i-го поставщика к (n + 1)-му потребителю c_in+1 принимаются равными нулю (поставки х_in+1 в оптимальном плане покажут остатки продукции на складах поставщиков).

Если потребности превышают запасы (т. е. ), то вводят (m + 1)-го фиктивного поставщика, запасы которого считаются равными недостающему грузу, т. е.

(2.3)
Стоимости перевозки единицы груза от (m + 1)-го поставщика j-му потребителю c_m+1j принимаются равными некоторому большому положительному числу M (поставки х_m+1j в оптимальном плане полученной задачи покажут объемы недопоставки груза).

Математическая модель закрытой транспортной задачи формулируется следующим образом. Требуется найти план перевозок

(2.4)
при ограничениях:

на запасы груза у поставщиков, которые в силу (2.1) должны быть вывезены,

(2.5)
на спрос потребителей, который должен быть полностью удовлетворен,

(2.6)
условия неотрицательности, исключающие обратные перевозки,

(2.7)
и чтобы суммарные затраты на перевозку груза были минимальными:

(2.8)
План перевозок X будем называть допустимым планом, если он удовлетворяет ограничениям (2.5) – (2.7). Допустимый план перевозок называется оптимальным планом, если он доставляет минимум целевой функции (2.8).

Модель транспортной задачи – модель линейного программирования. Ее оптимальный план всегда можно найти симплексным методом. Однако матрица системы ограничений (2.5) – (2.6) специфична. Специфика состоит в следующем:

1) коэффициенты при неизвестных во всех ограничениях равны единице;

2) каждая неизвестная величина встречается только в двух уравнениях: раз – в системе (2.5) и раз – в системе (2.6);

3) система уравнений симметрична относительно переменных х_ij.

Благодаря этой специфике общую процедуру симплексного метода можно значительно упростить.

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

2.2 Построение начального базисного плана перевозок.

Метод северо-западного угла. Назначение перевозок х_ij начинаем с верхней левой клетки (северо-западного угла) таблицы. Положим х₁₁= min (a₁, b₁). Если a₁ > b₁, то x₁₁ = b₁, вычеркиваем из матрицы столбец j =1, так как спрос первого потребителя полностью удовлетворен. Если a₁ < b₁, то x₁₁ = a₁, вычеркиваем строку i = 1, так как в этом случае полностью исчерпаны запасы первого поставщика. Если a₁ = b₁, то вычеркиваем и строку i = 1, и столбец j = 1 одновременно. Вычеркнув ряд, соответствующий min (a₁, b₁), корректируем запасы и потребности первого поставщика и первого потребителя на величину x₁₁. С оставшейся матрицей поступим аналогично предыдущему. Продолжая действовать по этой схеме, исчерпаем запасы поставщиков и удовлетворим запросы потребителей. На последнем шаге процесса получится матрица 1 ´ 1, в которой одновременно вычеркиваем и строку, и столбец.

Метод северо-западного угла не учитывает матрицу тарифов, поэтому начальный план может оказаться далеким от оптимального. Более близким к оптимальному обычно является план, построенный методом минимальной стоимости или методом двойного предпочтения.

Метод минимальной стоимости. Находим клетку с наименьшей стоимостью перевозки . Если , то , вычеркиваем столбец j₀, запасы поставщика i₀ корректируем, т. е. считаем равными ; если , то , вычеркиваем строку i₀, потребности потребителя j₀ считаем равными ; если же , то , вычеркиваем и строку i = i₀, и столбец j = j₀ одновременно. Вычеркнув один из рядов матрицы и скорректировав либо запасы поставщика, либо потребности получателя на величину , с оставшейся матрицей меньшего размера поступаем аналогично предыдущему. На последнем шаге в матрице 1 ´ 1 одновременно убираем и строку, и столбец.

Построенный начальный план перевозок должен быть базисным, т. е. число назначенных перевозок x_ij должно быть равно m + n – 1. Если это условие не выполняется, а условие общего баланса выполнено, то построенный начальный план – вырожденный. Для построения базисного плана в исходный план вводят нулевые перевозки так, чтобы не образовывался замкнутый контур из назначенных перевозок. Заполнение клеток нулем не влияет на экономическую оценку решения, но оно необходимо для получения начального базисного плана и для поиска оптимального решения.

Замкнутым контуром (циклом) в матрице называется непрерывная замкнутая ломаная линия, вершины которой находятся в загруженных клетках матрицы, а звенья расположены вдоль строк и столбцов. Причем в каждой вершине замкнутого контура встречаются ровно два звена; одно из них располагается по строке, другое – по столбцу, таким образом, звенья образуют прямой угол. Если замкнутый контур образует самопересекающаяся ломаная линия, то точки ее самопересечения вершин не образуют. Примеры некоторых замкнутых контуров показаны на рисунке 2.1.

Рисунок 2.1 – Примеры форм замкнутых контуров

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

2.3 Построение оптимального плана методом потенциалов.

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

Условие оптимальности плана перевозок можно сформулировать следующим образом.

Если для некоторого планаX^* = ||х_ij^*||( ; ) транспортной задачи существуют такие числа u_i ( ) и v_j ( ), что

(2.9)
(2.10)
то план Х^*=||х_ij^*|| является оптимальным.

Числа u_i ( ) и v_j ( )называются потенциаламисоответственно поставщиков и потребителей.

Каждой загруженной клетке будет соответствовать уравнение v_j – u_i = c_ij. Так как число загруженных клеток равно m + n – 1, т. е. на единицу меньше числа потенциалов, то для определения чисел u_i и v_j необходимо решить систему из п + т – 1 уравнений v_j – u_i = c_ij с п + т неизвестными.

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

(2.11)
Для проверки условия оптимальности для незагруженных (свободных) клеток вычисляется величина превышения стоимости по следующей формуле:

D_ij = v_j – u_i – c_{ij .} (2.12)
Если все D_ij £ 0 , то построенный план перевозок является оптимальным.

Клетки, в которых условие оптимальности не выполняется, называются потенциальными.

Если имеется хотя бы одна потенциальная клетка, то построенный план неоптимален, переходим к улучшенному плану перевозок. В этом случае среди незагруженных клеток, для которых D_ij > 0 , находим клетку с наибольшей величиной превышения стоимости.

Строим замкнутый контур (см. рисунок 2.1), начиная перемещаться из потенциальной клетки в горизонтальном или вертикальном направлении с поворотами в загруженных клетках с таким расчётом, чтобы вернуться в исходную клетку. Начиная с потенциальной клетки, разметим вершины контура поочередно знаками плюс «+» и минус «–», обходя замкнутый контур в любом направлении. В клетках, помеченных знаком «–», находим наименьшее значение объема перевозки:

(2.13)
Из всех объемов перевозок х_ij в клетках контура, помеченных знаком «–», вычитаем значение q, а к перевозкам клеток, помеченных знаком «+», прибавляем q. Перевозки в клетках, которые не находятся в вершинах замкнутого контура, остаются без изменения. В общем виде переход к улучшенному плану перевозок осуществляется по формуле

(2.14)
Затем вновь проверяем условие оптимальности полученного плана перевозок. При необходимости повторяем процедуру улучшения плана.

Дата добавления: 2014-12-09; просмотров: 442; Нарушение авторских прав

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