Метод северо-западного угла заключается в следующем. [c.71]
Ц Пример 1. Транспортная таблица (табл. 45), в клетках которой указаны перевозки, найденные методом северо-западного угла. Число базисных клеток равно го + п — 1. В этом примере число базисных клеток равно 4, т. е. т + тг — 1 = 4. [c.72]
Пример 2. Табл. 46 представляет собой транспортную таблицу, в клетках которой указаны перевозки, найденные методом северо-западного угла. Число базисных клеток меньше т + п — 1. [c.73]
В рассматриваемом примере т + п — 1 = 6, число базисных клеток равно 5 < 6, а план является вырожденным. Чтобы перейти к невырожденному плану, можно изменить объемы добычи нефти в первом районе на е, приняв их равными 30 + е, а в третьей строке 15 — е (для сохранения баланса). Построенный с учетом этого метода северо-западного угла опорный план представлен в табл. 47. [c.73]
Очевидно, что построенные методом северо-западного угла опорные планы удовлетворяют условиям (72), (73), (74). [c.73]
Составление исходного плана методом северо-западного угла. [c.75]
Разрабатываем исходный план методом северо-западного угла (в свободных клетках нуль не указываем), который приводится в табл. 49. [c.77]
В общем виде любая транспортная задача может быть задана в виде таблицы (табл. 7.1), с помощью которой формируется опорный план, а затем осуществляются преобразования с использованием метода северо-западного угла. [c.225]
Для иллюстрации использования метода северо-западного угла рассмотрим на конкретном примере все этапы решения транспортной задачи. [c.226]
Составим методом северо-западного угла первое распределение поставок, начиная с заполнения верхней левой ( северо-западной ) клетки таблицы. Примем объем перевозки со склада Л к потребителю С максимально возможным исходя из условий задачи и равным 30. Потребитель С полностью удовлетворил свою потребность, и столбец С в табл. 7.3 можно исключить из дальнейшего рассмотрения. [c.227]
Метод "северо-западного угла". Циклы [c.123]
Для начала необходимо просто написать какой-нибудь опорный план. Это легко сделать с помощью так называемого метода "северо-западного угла". [c.124]
| Таблица 11 Перевозки (1) метод "северо-западного угла" |  |
Какие особенности транспортной задачи обусловливают возможность применения метода "северо-западного угла" для построения опорного плана [c.147]
| Таблица И. Перевозки (1) метод "северо-западного угла" 124 |  |
Метод "северо-западного" угла [c.340]
Метод "северо-западного" угла — наиболее простой метод нахождения начального решения. План перевозок, полу- [c.340]
Шаг 3. В выбранную клетку аналогично методу "северо-западного" угла помещают максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос. После этого, если предложение производителя исчерпано, вычеркивают соответствующую строку если спрос удовлетворен, вычеркивают соответствующий столбец. [c.341]
Стоимость перевозок, полученных по методу минимального элемента, обычно бывает меньше стоимости перевозок, полученных по методу "северо-западного" угла. [c.341]
Шаг 1. Получение начального плана перевозок по методу "северо-западного" угла, минимального элемента, Фогеля или любым другим методом. [c.343]
Для составления исходного плана воспользуемся приемом, который называется методом северо-западного угла . Согласно этому методу заполнение таблицы прикрепления следует начать с левого верхнего квадрата и с позиции этого квадрата сравнить ресурсы первого поставщика (160 т) и потребности первого потребителя (150 т), выбрать меньшее значение из них и записать в данный квадрат, который с этого момента становится загруженным . [c.155]
Первым этапом этого алгоритма является начальное распределение (составление начального плана перевозок). Для этого имеется ряд методов северо-западного угла, наименьших стоимостей, аппроксимаций Фогеля и др. Второй этап — построение системы потенциалов на основе равенства (25.33), а третий — проверка начального плана на оптимальность, причем в случае его неоптимальности переходят к четвертому этапу, содержание которого заключается в реализации так называемых циклов перераспределения плана прикрепления потребителей к поставщикам, после чего переходят опять к третьему этапу. Совокупность процедур четвертого и третьего этапов образует одну итерацию, и эти итерации повторяются, пока план перевозок не окажется оптимальным по критерию (25.29) [c.526]
Существует несколько схем построения первоначального опорного плана метод северо-западного угла, метод минимальной стоимости и др. [c.483]
Начальный план можно составить одним из перечисленных выше методов. Воспользуемся наиболее простым методом — методом северо-западного угла. В соответствии с этим методом загрузка клеток (распределение объемов пунктов отправления по пунктам назначения) начинается с верхней левой клетки ( северо-западная часть таблицы) и продолжается вниз и вправо (по диагонали). [c.273]
Рассмотрим применение метода северо-западного угла на конкретном примере. Транспортная таблица 3.1 содержит условия некоторой задачи, а в табл. 3.2 показан процесс поиска допустимого плана, включая последовательное изменение объема нераспределенных запасов и неудовлетворенных потребностей. Стрелки отражают траекторию перехода по клеткам транспортной таблицы, а цифры, находящиеся за ее пределами, — текущие нераспределенные остатки после назначения объема для очередной клетки. [c.113]
Особенностью допустимого плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимального. Это происходит потому, что при его построении никак не учитываются значения сц. В связи с этим на практике для получения исходного плана используется другой способ — метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами. [c.113]
Рассмотрим процесс определения потенциалов текущего плана транспортной задачи на примере. В табл. 3.3 переписаны условия задачи из табл. 3.1 и ее допустимый базисный план, построенный методом северо-западного угла (см. табл. 3.2). [c.116]
Сопоставляя между собой методы составления отправных планов, можно сказать, что метод северо-западного угла, приводя к большой трудоемкости в решении задачи, складывается из четкой последовательности операций при его составлении. Другие методы (наименьших значений и двойного предпочтения), сокращая общую трудоемкость решении задачи, не имеют такого четкого алгоритма, как первый. [c.207]
Первый отправной вариант плана составлен по методу северо-западного угла, при использовании которого в отправном плане учитываются все ограничения. В этом плане еще ни в какой степени не учтены стоимости перевозок, и поэтому первые перераспределения связаны с перемещением грузов из загруженных клеток с максимальными стоимостями (15 и 16). Выбранная перспективная клетка 13 показывает желательное направление перемещении. [c.215]
Для получения отправной (базисной) программы проводим распределение поставок но методу северо-западного угла . [c.254]
Решаем задачу методом потенциалов. Распределение в отправной программе производим методом северо-западного угла . [c.258]
Табл. 73 заполнена, как указано выше, по методу северо-западного угла . Карьеры инертных материалов поставляют свою продукцию на заводы сборных железобетонных конструкций. Мощность карьеров, пересчитанная на одно изделие заводов, составляет 6000 шт. [c.260]
Опорный план является допустимым решением ТЗ и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла — наихудшее. [c.70]
На каждом шаге метода северо-западного угла из всех не вычеркнутых клеток выбирается самая левая и верхняя (северо-западная) клетка. Другими словами, на каждом шаге выбирается первая из оставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов. [c.70]
Для упрощения вместо оптимального решения рассмотрим опорный план найденный методом северо-западного угла. [c.83]
Организуйте экономичную перевозку товаров (при решении используйте метод северо-западного угла). Будьте внимательны при определении исходных себестоимостей перевозок распределительной задачи. [c.85]
Методом северо-западного угла или минимального тарифа находят первоначальный план перевозок. [c.233]
Построение исходного допустимого плана в транспортной задаче. По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются а , a текущих неудовлетворенных потребностей — Ъ . Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем aJ0) =af, fy-0) = /. Для очередной клет- [c.111]
Завершая разговор о методе потенциалов, следует отдельно остановиться на ситуации возникновения вырожденного плана. Возможность получения вырожденного плана уже отмечалась при описании метода северо-западного угла. Нетрудно заметить, что вырожденный план также может получиться на этапе преобразования текущего плана по цепочке если одинаковое минимальное значение будет достигнуто сразу на нескольких клетках, помеченных знаком — , то при вычитании перемещаемого по цепочке объема в новом плане будет меньше чем т+n-l ненулевых компонент. Способ преодоления вырожденности в транспортной задаче весьма прост, а именно предлагается дополнить текущий план необходимым количеством нулевых клеток (фиктивными перевозками) таким образом, чтобы они позволяли рассчитать полную систему потенциалов, и далее действовать в соответствии с правилами описанного выше алгоритма. Фактически здесь мы имеем дело не с чем иным, как с аналогом метода возмущений для транспортной задачи как частного случая ЗЛП. К taKOMy выводу легко прийти, если положить, что добавляемые фиктивные клетки содержат некоторый малый объем 8. [c.120]
Для того же примера себестоимость перевозок по исходному плану, составленному по методу северо-западного угла, равнялась 37(30 тыс. руб., т. е. была примерно па 12% выше и только после второй итерации была получена стой-, мость, примерно равная приведенной выше (3150тыс. руб.). [c.206]