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

22.09.2019

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

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

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

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

Пример 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 . В отличие от метода северо-западного угла данный метод позволяет сразу получит достаточно экономичный план, сокращая количество итераций.

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

Cтраница 1

Опорный план, отвечающий рассматриваемому базису, оптимален, если все AV неотрицательны.

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

Опорный план территории поселения - картографическое отображение фактически сложившейся градостроительной и экологической ситуаций на территории поселения.

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

Пусть теперь первый опорный план найден. Существует ряд методов проверки координат вершины на оптимальность.

Находят опорный план расширенной задачи.

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

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

По данному опорному плану каждому пункту (производителю или потребителю) сопоставляется число, наз. Предварит, потенциалы определяются из условия: разность предварит, потенциалов нары пунктов (производитель, потребитель) равна стоимости перевозки (СП) единицы продукта между этими пунктами, если связывающая их коммуникация является основной. Далее, для каждой пары пунктов (производитель и потребитель) вычисляется относит, стоимость перевозки единицы продукта, равная разности предварит, потенциалов этих пунктов. Если относит, стоимость перевозки не превосходит СП для любой пары пунктов, то имеющийся план оптимален, а предварит, потенциалы являются потенциалами задачи. Соединим / - и пункт-производитель с i - м пунктом-потребителем обходным маршрутом, составленным из осн.

По данному опорному плану каждому пункту (производителю или потребителю) сопоставляется число, паз. Предварит, потенциалы определяются из условия: разность предварит, потенциалов нары пунктов (производитель, потребитель) равна стоимости перевозки (СП) единицы продукта между этими пунктами, если связывающая их коммуникация является основной. Далее, для каждой пары пунктов (производитель и потребитель) вычисляется относит, стоимость перевозки единицы продукта, равная разности предварит, потенциалов этих пунктов. СП для любой пары пунктов, то имеющийся план оптимален, а предварит, потенциалы являются потенциалами задачи. Пусть это условие не выполняется для нек-рых пар пунктов, одна из к-рых содержит пункты с номерами / и i. Соединим / - и пункт-производитель с i - м пунктом-потребителем обходным маршрутом, составленным из оси.

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

Когда в опорный план вводится новая переменная, то для сохранения его базпсности из него должна быть исключена одна из базисных неременных. Таким образом, на каждой итерации симплексного метода новая дуга вводится в план, а одна из базисных дуг исключается. После изменения плана он проверяется на соблюдение условий оптимальности с помощью расчетов, равноценных проверке выполнения всех неравенств (2) при текущих значениях двойственных неременных.

12.3. ПОСТРОЕНИЕ ПЕРВОНАЧАЛЬНОГО ОПОРНОГО ПЛАНА

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

Кратко рассмотрим каждый из них:

1. Метод северо-западного угла. Следуя этому методу, начинают с того, что приписывают неизвестной (расположенной в северо-западном углу таблицы) максимальное значение, допускаемое ограничениями на спрос и объем производства. После этого вычеркивают соответствующий столбец (или строку), фиксируя этим, что остальные неизвестные вычеркнутого столбца (строки) полагаются равными нулю. Если ограничения, представляемые столбцом и строкой, выполняются одновременно, то можно вычеркнуть либо столбец, либо строку (это условие автоматически гарантирует обнаружение нулевых базисных переменных, если таковые встречаются). После того спрос и объем производства во всех невычеркнутых строках и столбцах, приведены в соответствие с установленным значением переменной, максимально допустимое значение приписывается первому невычеркнутому элементу нового столбца (строки). Процесс завершается, когда остается невычеркнутой в точности одна строка (или один столбец).

2. Метод наименьшей стоимости. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку (i , j ), которая ей соответствует, помещают меньшее из чисел и . Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс размещения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

3. Метод двойного предпочтения. Суть метода заключается в следующем. В каждом столбце отмечают знаком «√» клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку «√√». В них находится минимальная стоимость, как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам, отмеченным знаком «√». В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

4. Метод аппроксимации Фогеля. Алгоритм состоит из следующих шагов:

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

2. Отметить строку или столбец с самым большим штрафом (если таких несколько, выбрать из них любую строку или любой столбец). В отмеченной строке или столбце выбрать переменную с самой низкой стоимостью и придать ей наибольшее возможное значение. Скорректировать объем производства и спроса и вычеркнуть строку или столбец, соответствующие выполненному ограничению. Если ограничения по строке и столбцу выполняются одновременно, то вычеркнуть либо строку, либо столбец, а оставшемуся столбцу (строке) приписать нулевой спрос (объем производства). Строка (или столбец) с нулевым объемом производства (или спросом) не используется в дальнейших вычислениях (на шаге 3).

3. а) Если невычеркнутой остается только одна строка или один столбец, то закончить вычисления.

Б) Если невычеркнутой остается только одна строка (столбец) с положительным объемом производства (спроса), найти базисные переменные в этой строке (столбце), используя метод наименьшей стоимости.

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

Г) В других случаях вычислить новые значения штрафов для невычеркнутых строк и столбцов и перейти к шагу 2 (строки и столбцы с нулевыми значениями объема производства и спроса не должны использоваться при вычислении этих штрафов).

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

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

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

Поскольку ограничения в этой задаче образуют систему уравнений относительно переменных решения, можно было бы попытаться решить эту систему, чтобы найти значения переменных. Но переменных решения в нашей задаче 6, а независимых уравнений для их решения только 4. Можно произвольно положить значение двух каких -нибудь переменных решения равными 0 (например, Хп=0 и Х]2=0), тогда остальные переменные решения могут быть однозначно определены из системы уравнений, образованной ограничениями. Получившийся план перевозок, разумеется, необязательно будет оптимальным, но он обязательно является допустимым, поскольку удовлетворяет всем ограничениям.

Такой план называется опорным. От множества других допустимых планов он отличается тем, что число ненулевых переменных решения (ненулевых перевозок) точно равно количеству независимых ограничений в транспортной задаче или, иначе, сумме числа поставщиков и потребителей минус 1.

В нашей задаче число ненулевых перевозок в опорном плане равно

2 (количество поставщиков) + 3 (количество потребителей) -1=4.

В общем случае если имеется т поставщиков и п потребителей, то количество ненулевых перевозок в опорном плане будет т + п - 1.

Если, например, т = 10, а п = 20, то количество переменных будет 200, а количество ненулевых переменных в опорном плане - только 29.

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

Разумеется, опорных планов может быть много. В нашем примере нетрудно пересчитать, что существует 15 различных способов присвоить нули двум переменным из шести (т.е. имеется 15 опорных планов). В случае когда т = 10, п = 20, число различных опорных планов будет выражаться огромным числом 7,18*1034. Таким образом, о том, чтобы перебрать все возможные опорные планы и выбрать среди них оптимальный, в общем случае транспортной задачи, разумеется, не может быть и речи. Однако возможность осуществлять поиск только среди опорных планов все равносильно упрощает задачу по сравнению с общей задачей линейного программирования.

Опорным называется такой план, в котором количество ненулевых перевозок равно сумме количеств поставщиков и потребителей минус единица.

Оптимальный план перевозок следует искать только среди множества опорных планов.

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

- населённые места, имеющие определ. людность и выполняющие специфические, преим. несельскохозяйственные функции. Более крупные Г. п. почти всегда многофункциональны...
Демографический энциклопедический словарь
- археол...
Уральская историческая энциклопедия
- план,на котором показана сложившаяся на исходный срок проектирования топографическая и хозяйственная ситуация объекта планировки - опорен план - výkres stávajícího stavu...
Строительный словарь
- ...
- особая организация части войск в России в 1810 - 57, совмещавшая военную службу с занятием сельским хозяйством. Были созданы в Могилевской, Новгородской, Петербургской, Херсонской и других губерниях...
Современная энциклопедия
- вид военных поселений, существовавших с конца 18 в. по 1861 в районе Николаева и Херсона. Адмиралтейские поселения находились также близ Санкт-Петербурга...
Русская энциклопедия
- особая организация войск в 1810-57. Созданы на казённых землях Санкт-Петербургской, Новгородской, Могилёвской, Херсонской и других губерний с целью уменьшения военных расходов...
Русская энциклопедия
- в РФ - города и поселки.См. также: Населенные пункты Поселения Российской Федерации ...
Финансовый словарь
- ".....
Официальная терминология
- ....
Энциклопедический словарь экономики и права
- см. Поселения...
- изучение судеб варварских поселенцев весьма важно для освещения социального, экономического и военного быта империи...
Энциклопедический словарь Брокгауза и Евфрона
- особая организация войск в России в 1810-57, совмещавших военную службу с занятием сельским хозяйством. Введены Александром I для создания резерва обученных войск...
- населённые места, обладающие определённой людностью и выполняющие преимущественно промышленные, транспортные, культурные и административно-политические функции...
Большая Советская энциклопедия
- остатки поселений эпохи поздней бронзы в районе г. Каркаралинска. Исследовались в 1950-х гг. экспедицией АН Казахской ССР под руководством А. Х. Маргулана...
Большая Советская энциклопедия
- особая организация войск в Российской империи в 1810-57 с целью уменьшения военных расходов. Совмещали военную службу с занятием сельским хозяйством...
Большой энциклопедический словарь

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

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

автора DeFelice Jim

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

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

Из книги Американский снайпер автора DeFelice Jim

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

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

Из книги Мемуары [Лабиринт] автора Шелленберг Вальтер

ОПОРНЫЙ ПУНКТ - ДАНИЯ Гейдриха назначают заместителем рейхспротектора - Поездка в Копенгаген - Переговоры с Клаузеном - Датские национал-социалисты готовят переворот - Информационный резервуар Европы - Трения между Гиммлером и Гейдрихом - Гейдрих угрожает

План организации территории

Из книги Сезонный календарь для садовода автора Куропаткина Марина Владимировна

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

Опорный край державы

Из книги Немцы на Южном Урале автора Моисеев Александр Павлович

Опорный край державы Златоустовский горный округ с его уникальной «прививкой» немецкого мастерства развивался стремительно. Преуспевали и оружейники: начиная с 1829 года, Златоустовские клинки были представлены на всех выставках в стране и в зарубежье. К выставкам

Опорный горизонт

БСЭ

Опорный пункт

Из книги Большая Советская Энциклопедия (ОП) автора БСЭ

ЗАКОНЫ КОМПОЗИЦИИ В ФОТОГРАФИИ МЕЛКИЙ ПЛАН, СРЕДНИЙ ПЛАН, КРУПНЫЙ ПЛАН (ФРАГМЕНТ)

Из книги Фотосъемка. Универсальный самоучитель автора Кораблев Дмитрий

ЗАКОНЫ КОМПОЗИЦИИ В ФОТОГРАФИИ МЕЛКИЙ ПЛАН, СРЕДНИЙ ПЛАН, КРУПНЫЙ ПЛАН (ФРАГМЕНТ) Эти понятия являются базовыми в фотографической композиции. Если брать изображение человека или какого-либо объекта, то на мелком плане они будут изображены полностью на фоне какого-либо

Опорный элемент Current

Из книги Основы объектно-ориентированного программирования автора Мейер Бертран

Опорный элемент Current В качестве опорного элемента можно использовать Current, обозначающий текущий экземпляр класса (о текущем экземпляре см. лекцию 7). Сущность, описанная в классе A как like Current, будет считаться в нем имеющей тип A, а в любом B, порожденном от A, - имеющей тип B.Эта

Из книги Градостроительный кодекс Российской Федерации. Текст с изменениями и дополнениями на 2009 год автора Автор неизвестен

Статья 46. Особенности подготовки документации по планировке территории, разрабатываемой на основании решения органа местного самоуправления поселения или органа местного самоуправления городского округа 1. Решение о подготовке документации по планировке территории

Какие затраты включены в опорный план!

Из книги Основы управления проектами автора Пресняков Василий Федорович

Какие затраты включены в опорный план! Опорный план BCWS - это сумма счетов издержек, а каждый счет издержек - это сумма издержек наборов работ, входящих в этот счет.Четыре типа затрат обычно включают в опорный план - затраты на труд и затраты на оборудование, затраты на

Лекция 14. Опорный «скелет» личности

Из книги Деловая психология автора Морозов Александр Владимирович

Лекция 14. Опорный «скелет» личности Все, что говорилось до сих пор, можно отнести к любому человеку. У каждого есть тот или иной темперамент, характер, более или менее разнообразные способности, каждый хранит в себе множество простых и сложных ролей. Наконец, у каждого

ОПОРНЫЙ «СКЕЛЕТ» ЛИЧНОСТИ

Из книги Очерк психологии личности автора Леонтьев Дмитрий Борисович

ОПОРНЫЙ «СКЕЛЕТ» ЛИЧНОСТИ

ГЛАВА XI ИСПАНСКИЙ «ОПОРНЫЙ ПУНКТ»

Из книги Тайны английской секретной службы автора Кукридж Е Х

ГЛАВА XI ИСПАНСКИЙ «ОПОРНЫЙ ПУНКТ» Каждому, кто отваживался высказать предположение, что Америка может стать активным союзником Англии, фюрер пояснял, что его интуиция отвергает возможность приобретения вымирающей демократией Англии каких-либо друзей. Но это было

Опорный инструмент

Из книги Художественная обработка металла. Ковка автора Мельников Илья

Опорный инструмент Основной опорой, на которой производят ковку, является наковальня.Наковальни подразделяется на безрогие, однорогие и двурогие. Масса наковальни колеблется от 150 до 350 кг. Наибольшее распространение получили двурогие наковальни массой до 200