Находим оптимальные размеры и направления грузопотоков по каждому виду груза

Задача о нахождении оптимальных размеров и направлений грузопотоков решается как транспортная задача линейного программирования. По первому виду груза (картофелю) необходимо представить решение данной задачи вручную методом потенциалов. Для нахождения оптимальных планов грузопотоков других грузов следует использовать средство «Поиск решения» электронной таблицы MS Excel. Методика создания и оптимизации моделей транспортных задач в MS Excel представлена в источниках [1, 2] списка рекомендуемой литературы.

Алгоритм метода потенциалов включает следующие шаги (этапы) расчетов.

Шаг 1. Определение первоначального допустимого (базисного) плана перевозок, затем переходим к выполнению второго шага.

Шаг 2. Анализ распределения и проверка плана перевозок на оптимальность, включающие в себя: 1) расчет потенциалов строк и столбцов; 2) расчет характеристик небазисных переменных. Если все небазисные переменные удовлетворяют условию оптимальности, вычисления заканчиваются, в противном случае переходим к третьему шагу.

Шаг 3. Нахождение нового базисного решения, включающее в себя: 1) определение цепи для клетки, содержащей небазисную переменную, у которой характеристика (по абсолютной величине) наибольшая; 2) определение исключаемой из базиса переменной и перераспределение поставок. Возвращаемся ко второму шагу.

Найдем методом потенциалов оптимальный план грузопотока картофеля для рассматриваемого примера.

Шаг 1. Определение первоначального допустимого (базисного) плана перевозок.

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

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

Рассмотрим алгоритм метода минимального элемента. На каждом шаге метода минимального элемента из всехне вычеркнутых клеток транспортной матрицы выбирается клетка с минимальной стоимостью перевозки (или расстоянием перевозки) и в соответствующую клетку заносится максимально возможная поставка. Если транспортная таблица имеет несколько клеток с одинаковыми по величине минимальными показателями , то поставку можно произвести в любую клетку. Далее вычеркивается соответствующий столбец или строка и соответствующим образом корректируются значения спроса и предложения. Если одновременно выполняются ограничения и по спросу, и по предложению, вычеркиваются или строка, или столбец. Затем просматриваются невычеркнутые клетки, и выбирается новая клетка с минимальным показателем . Описанный процесс продолжается до тех пор, пока не останется лишь одна невычеркнутая строка или столбец.

Представленное ниже базисное распределение грузопотока картофеля найдено методом наименьшего элемента в матрице (табл. 2 – табл. 8).

Таблица 2

Составление базисного плана перевозок товара между складами методом наименьшего элемента в матрице (Итерация 1)

Таблица 3

Составление базисного плана перевозок товара между складами методом наименьшего элемента в матрице (Итерация 2)

Таблица 4

Составление базисного плана перевозок товара между складами методом наименьшего элемента в матрице (Итерация 3)

Таблица 5

Составление базисного плана перевозок товара между складами методом наименьшего элемента в матрице (Итерация 4)

Таблица 6

Составление базисного плана перевозок товара между складами методом наименьшего элемента в матрице (Итерация 5)

Таблица 7

Составление базисного плана перевозок товара между складами методом наименьшего элемента в матрице (Итерация 6)

Таблица 8

Составление базисного плана перевозок товара между складами методом наименьшего элемента в матрице (Итерация 7)

Значение целевой функции полученного распределения, т.е. транспортная работа составляет

Шаг 2. Анализ распределения и проверка плана перевозок на оптимальность.

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

Если обозначить потенциалы строк через u_i, потенциалы столбцов через v_j, показатели критерия оптимальности в занятых клетках через , то уравнение потенциалов можно записать в виде:

,

откуда следует, что

и .

Используя представленные выше уравнения, находим потенциалы строк и столбцов в распределении, представленные в табл. 9.

Таблица 9

Проверка плана перевозок товара между складами

на оптимальность (расчет потенциалов)

Уравнения потенциалов имеют вид:

Полученная система имеет 7 уравнений и 8 неизвестных, следовательно, она неопределенная. Обычно для решения системы принимают потенциал первой строки равным нулю или любому другому числу. В данном случае потенциал . Решая систему, получаем:

.

Характеристики незанятых клеток вычисляют по формуле

.

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

Результат расчета характеристик незанятых клеток в рассматриваемом распределении представлен в табл. 10.

Таблица 10

Проверка плана перевозок товара между складами

на оптимальность (расчет характеристик незанятых клеток)

Характеристики незанятых клеток следующие:

А₁Б₃: 10 – (0 + 4) = 6; А₁Б₄: 6 – (0 + 6) = 0;

А₂Б₁: 3 – (–4 + 11) = –4; А₂Б₂: 3 – (–4 + 11) = –4;

А₃Б₃: 6 – (–4 + 6) = 4; А₂Б₅: 7 – (–4 + 5) = 6;

А₃Б₂: 9 – (–2 + 11) = 0; А₃Б₅: 7 – (–2 + 5) = 4.

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