КАТЕГОРИИ: Архитектура-(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
Так как оно должно быть максимально допустимым, то При этом обязательно выполнится одно из равенств (3), (4), что соответствует закрытию строки или столбца: переменные в остальных клетках строки или столбца будут равны нулю. Конкретнее, если X11=а1, то закрывается первая строка и 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
Дата добавления: 2014-01-11; Просмотров: 449; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |