Построение исходного опорного плана - Экономико-математические методы

Моделирование экономический математический опорный

Построение опорных планов, а также их преобразование будем производить непосредственно в распределительной таблице (табл.1). Если в плане перевозок переменная то это число а записываем в соответствующую клетку (i, j) и считаем ее занятой или базисной, если xij = 0 то клетку (i, j) оставляем свободной.

Метод "северо-западного угла". Определение значений xij начинается с левой верхней, условно называемой северо-западной, клетки (1,1) табл.1. Находим x11=min(a1, b1).

Если а1<b1, то x11=a1, строка 1 исключается из дальнейшего рассмотрения, а потребность первого потребителя b1 уменьшается на а1;

Если а1>b1, то х11=b1, столбец 1 исключается из дальнейшего рассмотрения (первый потребитель В1 будет полностью удовлетворен), а наличие груза у первого поставщика a1 уменьшается на b1;

Если a1=b1, то x11= a1=b1, первая строка и первый столбец исключаются из дальнейшего рассмотрения. Эта ситуация приводит к вырождению исходного решения.

Затем аналогичные операции проделывают с оставшейся частью таблицы, начиная с ее северо-западного угла. На последнем шаге процесса остается одна строка (последняя) и один столбец (последний). После заполнения клетки, стоящей на их пересечении, т. е. клетки (m, n), процесс завершается.

После завершения описанного процесса необходимо провести проверку полученного плана (решения) на вырожденность. Если количество заполненных (занятых) клеток равно m+n-1, то план является невырожденным, в противном случае - вырожденным.

Если план вырожденный, то незаполненные клетки с минимальными стоимостями перевозок заполняются нулями, чтобы общее число заполненных клеток стало равным m+n-1. Однако, при расстановке нулей необходимо помнить, что в таблице не должно быть ни одного прямоугольника, все вершины которого являются заполненными клетками. Например, переменные x11,x12,x21,x22 не могут быть одновременно базисными.

Метод минимального элемента. В отличии от метода северо-западного угла данный метод учитывает при построении исходного плана стоимости перевозок. В ряде случаев он позволяет получить лучшее с точки зрения критерия оптимальности решение, сокращая количество итераций для получения оптимального плана.

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

Переменной, отвечающей выбранной клетке, присваивается минимальное из двух возможных значений: xij=min(ai, bj). Соответствующая строка или столбец исключаются из дальнейшего рассмотрения, а потребность потребителя или наличие груза у поставщика уменьшается на выбранную величину. Если для выбранной клетки с минимальной стоимостью перевозки наличие груза у поставщика равно потребности потребителя, то из дальнейшего рассмотрения исключаются и строка и столбец (это приводит к вырождению исходного плана).

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

Проверка плана на вырожденность и расстановка ( в случае вырожденности плана) нулей осуществляется так же, как это описано для метода северо-западного угла.

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

Похожие статьи




Построение исходного опорного плана - Экономико-математические методы

Предыдущая | Следующая