Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Правило северо-западного угла




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

Метод потенциалов

 

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

Сначала рассмотрим метод применительно к Т-задаче, а затем сделаем дополнения, позволяющие решать Тd-задачу.

Как было показано выше, размерность базисного решения или плана перевозок равна m+n -1, где m и n – число ПО и ПН сбалансированной задачи. Если задача открытая, то сначала ее необходимо сбалансировать.

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

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

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

Все исходные данные и переменные сбалансированной Т-задачи удобно представить в виде таблицы (табл.1).

Построение плана начинается с северо-западной клетки таблицы, то есть первым определяется значение переменной X11.

 

Таблица 1

  b1 b2 bn
C11 X11 C12 X12 C1n X1n
C21 X21 C22 X22 C2n X2n
Cm1 Xm1 Cm2 Xm2 Cmn Xmn

Так как оно должно быть максимально допустимым, то

При этом обязательно выполнится одно из равенств (3), (4), что соответствует закрытию строки или столбца: переменные в остальных клетках строки или столбца будут равны нулю. Конкретнее, если X111, то закрывается первая строка и X12=X13=…=X1n= 0, а следующей базисной переменной будет X21. Из указанного выше принципа следует X21 =min(a2, b1 - a1). Если же окажется, что X11=b1, то закроется первый столбец и следующей базисной переменной станет X12= min(a1-b1, b2).

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

Общее правило определения значения очередной базисной переменной:

Xij =min(остаток от ai, остаток до bj). (13)

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

Пример 1. Исходные данные и построение начального плана показано в табл. 5.2. Значения базисных переменных выделены красным (серым) цветом, а порядок движения по клеткам отражен стрелками. Этому плану соответствуют суммарные затраты L= 1295.

Таблица 2

Поставщик Потребитель Запасы груза
B1 B2 B3 B4
A1 75 25      
A2   55 60 35  
A3          
Потребность в грузе          

 




Поделиться с друзьями:


Дата добавления: 2014-01-11; Просмотров: 449; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.