Лесотранспортная логистика. Решение задач

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

m n

R = ∑∑Cij X ij = 6 * 300 + 4 *150 + 7 * 400 + 6 * 50 + 5 *150 +12 * 350 =10450тыс. руб

i=1 j =1

Рассмотрим еще один способ составления начального плана - способ минимального элемента.

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

Сущность его заключается в следующем.

В матрице стоимостей отыскивается клетка с минимальным значением Cij и в эту клетку записывается поставка Xij =min (ai bj). Если матрица содержит несколько одинаковых минимальных значений Cij, то выбирают любое одно.

После этого вычеркивается строка или столбец. Если ai> bj, вычеркивают столбец, при ai < bj вычеркивают строку.

Далее процесс (итерации, шаги) повторяют до тех пор, пока не будут распределены все поставки.

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

Рабочая таблица имеет форму, приведенную в табл. 4.3.

Таблица 4.3.

Построение опорного плана по методу минимального элемента.

Распределение поставок по методу минимального элемента выполняется в следующей последовательности.

Шаг 1. Находим минимальное значение стоимости Cij. В нашем случае это будет C21 = 4. В эту клетку таблицы записываем возможную поставку, т. е. минимальную из А2 и В1, Сравнивая А2 = 600 и В1 = 450, записываем в клетку Х21 поставку 450. Вычисляем нераспределенные мощности поставщиков и неудовлетворенный спрос потребителей.

Потребитель В1 — удовлетворен полностью, во вспомогательной части таблицы проставляем 0, а столбец в дальнейших расчетах не рассматриваем.

Потребитель В2 неудовлетворен, его спрос остался равным 400, что и записываем во вспомогательной части таблицы.

Потребитель В3 — неудовлетворен, спрос остался — 200. Потребитель В4 — неудовлетворен, спрос —350.

Поставщик А1 — мощность его не распределена, остаток нераспределенной мощности, равный 300, записываем во вспомогательной части таблицы справа.

Поставщик А2 — часть мощности распределена потребителю В1 но осталась нераспределенной мощность 600—450 = = 150, что и записываем во вспомогательную часть таблицы, как нераспределенную мощность на первом шаге.

Поставщик А3 — мощность его не распределена и записываем результат нераспределенной мощности 500.

Сумма нераспределенных мощностей и неудовлетворенного спроса по результатам первой итерации (шага) равна 950, что и записываем в итоге и это является проверкой того, что нет арифметических ошибок.

Шаг 2. Находим минимальное значение стоимости Cij без вычеркнутого столбца В1 это значение С33 =5. Записываем в эту клетку возможную по- ставку-минимум из А3 = 500 и В3=200, min=200, записываем нераспределенные мощности и неудовлетворенный спрос на этом шаге и их сумму, равную 750, и вычеркиваем из дальнейшего рассмотрения столбец у которого спрос удовлетворен.

Шаг 3. Минимальный элемент А2В2 = 7. В эту клетку записываем минимальное значение из нераспределенной мощности А2=150 и спроса В2=400, min=150. В результате третьего шага мощность поставщика А2 исчерпана, а сумма нераспределенных мощностей и неудовлетворенного спроса осталась равной 600. Продолжая аналогично, доводим распределение до конца,

Шаг 4. Минимальное Cij из оставшихся имеют клетки А1В2 и А3В2 — выбираем А3В2. Записываем сюда поставку 250 как минимум из значений остатка потребителя В2 и поставщика А3 и так далее.

Результат распределения по методу минимального элемента показан в табл. 4.3.

Вычисляем значение целевой функции полученного начального решения:

R= 10* 300 + 4 *450 + 7 *150 + 8 *250 + 5*200+ 12*50 = 9450 тыс. руб.

Видим, что это решение более целесообразное, чем полученное методом северо-западного угла. Но это не значит, что полученное решение оптимальное.

4.5. Проверка решения на оптимальность

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

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

Условимся называть клетки, заполненные поставками — базисными, клетки, где нет поставки — свободными.

Чтобы установить, является ли план оптимальным, надо проверить, можно ли уменьшить значение функции цели перераспределив поставки. Для этого в каждую свободную клетку попытаемся включить какую-либо поставку, но с таким перераспределением начального решения, чтобы оно было допустимым, т. е. чтобы соблюдался баланс спроса и предложения. Если в результате таких перестановок найдется хотя бы одно решение, которое приведет к снижению величины функции цели, значит анализируемое решение не оптимальное.

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

Для того, чтобы не нарушался баланс поставщика А1 необходимо уменьшить поставку от этого поставщика потребителю В4 на единицу, но чтобы не нарушилась поставка потребителю В4, необходимо увеличить ему поставку от поставщика А3 на единицу. В свою очередь, чтобы не нарушился баланс поставщика А3 необходимо уменьшить от него поставку потребителю В2, а потребителю В2 увеличить поставку от поставщика А2. Теперь, чтобы не нарушался баланс поставщика А2, необходимо уменьшить от него поставку потребителю В1.

Результат этих перестановок можно изобразить схемой, приведенной на рис. 2. В результате выполненных перестановок мы опять получили допустимое решение. Если выполнить эти перестановки в начальном решении, то произойдет изменение стоимости перевозок. Определим, к чему это приведет. Стоимость поставки потребителю В1 от поставщика A1 т. е. cтоимость поставки A1В1 увеличится на C11 = 6*1 = + 6.

А2В1 А2В2

А3В2 А3В4

Рис. 4.1. Перераспределение единичных поставок для клетки A1В1

Стоимость поставки A1В4 уменьшится на величину С14 *1= -10*1 = -10.

В целом, изменения, которые произойдут при рассмотренной перестановке поставок, можно записать следующим образом:

∆R= +С11 *1- С14 *1 +С34 *1- С32 *1+ С22 *1- С21 *1=+ 6-10+12-8+7-4=+3

То есть при попытке дать поставку в клетку A1В1 в целом произойдет увеличение стоимости перевозок, увеличение значения функции цели.

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

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

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

Вершины цепи, в которых поставка при перераспределении увеличивается, отмечаются знаком плюс и называются положительными вершинами.

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

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

Если характеристики цепей всех свободных клеток положительны при решении задачи на минимум, то получено оптимальное решение. Если имеется хотя бы одна отрицательная характеристика цепи — решение не оптимальное и имеется возможность улучшить решение путем перераспределения поставок. Свободная клетка, имеющая минимальное значение характеристики, называется перспективной. В нашем примере минимальную характеристику цепи — 3 имеет клетка A2 В4 (рис. 4.2).

4.6. Переход от неоптимального решения к лучшему.

Для перехода к лучшему решению в перспективную клетку, т. е. клетку, имеющую минимальную характеристику цепи, необходимо занести возможно большую поставку. Для этого в цепи перспективной клетки определяются вершины с отрицательными знаками. Среди этих вершин находят такую, которая имеет наименьшую по величине, поставку. Эту поставку прибавляют к поставкам положительных вершин и вычитают из поставок отрицательных вершин, получая таким образом новое распределение поставок или новое решение. Поскольку в нашем примере перспективной является клетка А2В4, находим среди отрицательных вершин этой цепи наименьшую по величине поставку - 50. Вычитаем эту поставку из отрицательных вершин, прибавляем к положительным и переписываем поставки остальных клеток без изменений. В результате получим новое решение, представленное в табл. 4.4.

Величина функции цели равна:

R = 10*300 + 4*450 +7*100 +8*50 + 8*300 +5*200 = 9300 тыс. руб.

Это решение лучше начального на 150 тыс. руб. Это можно было установить, умножив характеристику цепи на поставку, внесенную в перспективную клетку -3*50 = -150 тыс. руб.