Наибольшее распространение для нахождения начальных опорных планов получили:

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

Метод минимального элемента.

Метод северо-западного угла используют для нахождения произвольного опорного плана ТЗ. Основную идею метода рассмотрим на конкретном примере.

Пример 1. Условия ТЗ заданы транспортной таблицей (табл. 3.1).

Таблица 3.1

Требуется найти опорное решение (построить опорный план).

Решение. Будем заполнять таблицу 3.1 перевозками постепенно, начиная с левой верхней ячейки(1.1) (северо-западного угла).Будем рассуждать при этом следующим образом.

Пункт В 1 подал заявку на 18 единиц товара. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте А 1 , и запишем перевозку 18 в клетке (1.1). После этого заявка пункта В 1 удовлетворена, а в пункте А 1 осталось еще 30 единиц товара. Удовлетворим за счет них заявку пункта В 2 (27 единиц), запишем 27 единиц в клетке (1,2); оставшиеся 3 единицы пункта А 1 назначим пункту В 3 . В составе заявке пункта В 3 остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта А 2 , чем его запас будет исчерпан, и еще 9 возьмем из пункта А 3 . Из оставшихся 18 единиц пункта А 3 12 выделим пункту В 4 ; оставшиеся 6 единиц назначим пункту В 5 , что вместе со всеми 20 единицами пункта А 4 покроет его заявку (табл. 3.2).

Таблица 3.2

На этом распределение запасов закончено. Каждый пункт назначения получил согласно своей заявке. Это выражается в том, что сумма перевозок в каждой строке равна запасу, а в столбце – заявку.

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

Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными, их число удовлетворяет условию r = n + m – 1 = 8. Остальные клетки -- свободные, в них стоят нулевые перевозки, их число равно (n – 1)(m – 1) = 12.Значит, составленный план -- опорный и поставленная задача построения опорного плана решена.

Но является ли этот план оптимальным? Нет, так как при его совершенно не учитывались стоимости перевозок с i j . И даже, если мы стоимость этого плана перевозок

18 10 + 27 8 + 3 5 + 30 8 + 9 10 + 12 8 + 6 7 + 20 8 = 1039

гарантировать, что этот план оптимальный еще нельзя. Ниже мы рассмотрим способы улучшения

плана с целью получения оптимального.

Пример 2. Особенности построения «вырожденного плана»

План, в котором некоторые из базисных перевозок оказываются равными нулю, называют «вырожденным»

Дана транспортная таблица (табл.3.3) Построить опорный план.

Решение. Применяя метод северо-западного угла, получим таблицу 3.3.

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

быть m + n -- 1 = 8, оказались равными нулю.

Отчего это произошло? При распределении запасов по пунктам назначения

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

Такие случаи «вырождения « могут возникать не только при составлении опорного плана, но и при его преобразовании, оптимизации.

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

Таблица 3,3

Таблица 3.4

Таблица 3.5

заявки, так чтобы общий баланс не нарушился, а лишние «промежуточные» балансы уничтожались. Достаточно в нужных местах изменить запасы или заявки, например, на величину ε , а после нахождения оптимального решения положить ε = 0.

Как перейти от вырожденного плана к невырожденному можно понять на примере таблиц 3.4 и 3.5. Изменим слегка запасы в первой строке и положим их равными 20 + ε . Кроме того, в третьей строке проставим запасы 25 + ε. Чтобы «свести баланс» , в четвертой строке ставим запасы 20 -- 2 ε (табл. 3,5). Для этой таблицы строим опорный план методом северо-западного угла.

В табл. 3,5 уже содержится столько базисных переменных, сколько требуется:

m + n -- 1 = 8. В дальнейшем после оптимизации плана, можно будет положить

Метод минимального элемента позволяет построить начальный опорный план

транспортной задачи и является вариантом метода северо-западного угла, учитывающего специфику матрицы С = c i j . В отличие от метода северо-западного угла данный метод позволяет сразу получит достаточно экономичный план, сокращая количество итераций.

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

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

Правило: количество базисных (заполненных) клеток в первоначальном плане ВСЕГДА должно быть равно m + n - 1, где m - количество поставщиков, n - количество потребителей транспортной задачи.

Что же делать, если количество заполненных ячеек опорного плана меньше необходимого?

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

Чтобы обойти эту ситуацию, добавим к базисным ячейкам недостающее количество ячеек с нулевыми значениями. Нулевое значение поставим в клетку, стоящую рядом с базисной клеткой, которая обусловила "пропажу" базисного значения.

Вырожденность опорного решения транспортной задачи - пример 1:

Построить первоначальный план для следующей ситуации:

Количество поставщиков (складов) = 3, количество потребителей (магазинов) = 4

60 + 30 + 40 = 40 + 50 + 10 + 30 - спрос равен предложению - задача закрытая.

Методом северо - западного угла получим опорный план.

Начинаем с самой верхней левой ячейки.

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

Остатки груза с первого склада 60 - 40 = 20 перевозим в магазин второй. При этом, первый склад опустел, но потребности магазина не выполнены полностью.

Переходим ко второму складу. Все 30 единиц груза переносим в магазин второй, потребности которого совпали с предложением склада 50 - 20 = 30.

При данном распределении склад опустошается и потребности второго магазина выполняются полностью. Происходит потеря базисной клетки!

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

Продолжим.

С третьего склада направим 10 единиц груза в магазин 4 для полного выполнения его потребностей. На 3-м складе остается 40 - 10 = 30 единиц груза, которые перенесем в последний магазин.

Опорный план составлен.

Количество базисных ячеек равно 6 = 3 + 4 - 1. Условие невырожденности выполнено!

Вырожденность опорного решения транспортной задачи - пример 2:

Три торговых склада поставляют продукцию в четыре магазина. Наличие продукции на складах и потребности магазинов приведены в следующей таблице. Построим первоначальный план транспортной задачи:

Задача закрытая:

12 + 10 + 14 = 36

4 + 18 + 8 + 6 = 36

Первоначальный план получим методом северо - угла.

Начнем с заполнения ячейки (1;1).

Запасы первого склада распределили по первому и второму магазину, при этом запасы склада исчерпаны, а потребность второго магазина не удовлетворена. Переходим ко второму складу.

Все 10 единиц груза направляем во второй магазин, потребности которого на данный момент равны 18 - 8 = 10. Заметим, что на данном шаге одновременно удовлетворяются потребности второго магазина и закончились запасы второго склада. Произошла потеря одного базисного значения.

Ничего страшного, если вы упустите этот момент при получении опорного плана. Главное не забыть проверить условие невырожденности перед проверкой плана на оптимальность. Проанализировав уже полученное распределение груза, нетрудно найти момент, когда была "потеряна" базисная клетка.

Чтобы компенсировать потерю, мы должны ввести нулевую ячейку, рядом с заполненной. Можем поместить ее правее, левее или ниже значения 10.

Закончим заполнение таблицы:

Получили первоначальный план методом северо - западного угла. Количество базисных ячеек равно 4 + 3 - 1 = 6.

Можно приступать к решению задачи методом потенциалов!

Картографическое отображение сложившейся градостроительной и экологической ситуации в результате хозяйственной и иной деятельности.

• - населённые места, имеющие определ. людность и выполняющие специфические, преим. несельскохозяйственные функции. Более крупные Г. п. почти всегда многофункциональны...

  Демографический энциклопедический словарь

• - археол...

  Уральская историческая энциклопедия

• - план,на котором показана сложившаяся на исходный срок проектирования топографическая и хозяйственная ситуация объекта планировки - опорен план - výkres stávajícího stavu...

  Строительный словарь

• - ...
• - особая организация части войск в России в 1810 - 57, совмещавшая военную службу с занятием сельским хозяйством. Были созданы в Могилевской, Новгородской, Петербургской, Херсонской и других губерниях...

  Современная энциклопедия

• - вид военных поселений, существовавших с конца 18 в. по 1861 в районе Николаева и Херсона. Адмиралтейские поселения находились также близ Санкт-Петербурга...

  Русская энциклопедия

• - особая организация войск в 1810-57. Созданы на казённых землях Санкт-Петербургской, Новгородской, Могилёвской, Херсонской и других губерний с целью уменьшения военных расходов...

  Русская энциклопедия

• - в РФ - города и поселки.См. также: Населенные пункты Поселения Российской Федерации  ...

  Финансовый словарь

• - ".....

  Официальная терминология

• - ....

  Энциклопедический словарь экономики и права

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

  Энциклопедический словарь Брокгауза и Евфрона

• - особая организация войск в России в 1810-57, совмещавших военную службу с занятием сельским хозяйством. Введены Александром I для создания резерва обученных войск...
• - населённые места, обладающие определённой людностью и выполняющие преимущественно промышленные, транспортные, культурные и административно-политические функции...

  Большая Советская энциклопедия

• - остатки поселений эпохи поздней бронзы в районе г. Каркаралинска. Исследовались в 1950-х гг. экспедицией АН Казахской ССР под руководством А. Х. Маргулана...

  Большая Советская энциклопедия

• - особая организация войск в Российской империи в 1810-57 с целью уменьшения военных расходов. Совмещали военную службу с занятием сельским хозяйством...

  Большой энциклопедический словарь

"ОПОРНЫЙ ПЛАН ТЕРРИТОРИИ, ПОСЕЛЕНИЯ" в книгах

Опорный пункт «Железный»

Опорный пункт «Железный» Мелкая пыль грязных дорог смешивалась с вонью реки и города, по мере того как мы продвигались в деревню. Был предрассветный час. Мы двигались к двухэтажному зданию в центре небольшого поселка к югу от Рамади, отделенного от самого города

Опорный пункт «Сокол»

Опорный пункт «Сокол» Армия вошла с танками, бронемашинами и грузовиками. Солдаты натащили мешков с песком и укрепили слабые места в доме. Дом, в котором мы были, располагался на углу Т-образного перекрестка двух крупных дорог, одну из которых мы назвали «Сансет». Армии

ОПОРНЫЙ ПУНКТ - ДАНИЯ