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

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

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

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

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

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

Решение транспортной задачи, как и всякой задачи линейного программирования, начинается с нахождения опорного решения, или, как мы будем говорить, опорного плана. В отличие от общего случая ОЗЛП с произвольными ограничениями и минимизируемой функцией, решение ТЗ всегда существует. Действительно, из чисто физических соображений ясно, что хоть какой-то допустимый план существовать должен. Среди допустимых планов непременно имеется оптимальный (может быть, не один), потому что линейная функция L - стоимость перевозок заведомо неотрицательна (ограничена снизу нулем). В данном параграфе мы покажем, как построить опорный план. Для этого существуют различные способы, из которых мы остановимся на простейшем, так называемом «способе северо-западного угла». Пояснить его проще всего будет на конкретном примере.

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

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

Решение. Перепишем табл. 10.1 и будем заполнять ее перевозками постепенно, начиная с левой верхней ячейки (1,1) («северо-западного угла» таблицы). Будем рассуждать при этом следующим образом. Пункт подал заявку на 18 единиц груза. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте и запишем перевозку 18 в клетке (1,1). После этого заявка пункта й, удовлетворена, а в пункте осталось еще 30 единиц груза. Удовлетворим за счет них заявку пункта единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта назначим пункту . В составе заявки пункта остались неудовлетворенными 39 единиц.

Таблица 10.1

Из них 30 покроем за счет пункта , чем его запас будет исчерпан, и еще 9 возьмем из пункта . Из оставшихся 18 единиц пункта выделим пункту оставшиеся 6 единиц назначим пункту что вместе со всеми 20 единицами пункта покроет его заявку (см. табл. 10.2).

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

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

Таблица 10.2

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

Возникает вопрос: а является ли этот план оптимальным по стоимости? Разумеется, нет! Ведь при его построении мы совсем не учитывали стоимостей перевозок Естественно, план не получился оптимальным. Действительно, стоимость этого плана, которая найдется, если умножить каждую перевозку на соответствующую стоимость, равна .

Таблица 10.3

Попробуем улучшить этот план, перенеся, например, 18 единиц из клетки (1,1) в клетку (2,1) и, чтобы не нарушить баланса, перенеся те же 18 единиц из клетки (2,3) в клетку (1,3). Получим новый план, приведенный в табл. 10.3.

Нетрудно убедиться, что стоимость нового плана равна т. е. на 126 единиц меньше стоимости плана, приведенного в табл. 10.3.

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

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

Пример 2. Дана транспортная таблица (без стоимостей перевозок, так как речь идет только о построении опорного плана) - см. табл. 10.4.

Таблица 10.4

Таблица 10.5

Таблица 10.6

Составить опорный план перевозок.

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

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

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

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

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

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

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

3.1 Подготовка опорного плана

Основой для составления проекта планировки населенного места является опорный план – чертеж, составленный на базе топографического плана участка местности, выбранного для строительства нового или реконструкции существующего сельского поселения, на котором показано современное использование территории, сохраняемые на перспективу материальные и природные элементы и строительные ограничения. Выбранная для проектируемого села «Исутору» территория имеет достаточный размер, благоприятный для строительства и целесообразного размещения селитебной и производственной зон природные условия. Не меньшее значение придают инженерно-геологическим условиям, которые влияют на стоимость освоения участка. При оценке климатических условий рассматривают характеристики климата на проектируемой территории за ряд лет: температурный режим, солнечную радиацию, глубину промерзания грунтов, ветровой режим, влажность воздуха.

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

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

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

Последовательность составления опорного плана:

а) отграничиваются территории с уклонами рельефа менее 0,5 % и более 8 %;

б) вдоль водоемов пунктирной линией отделяются территории с глубиной залегания грунтовых вод менее 1,5 м (по горизонталям);

в) отграничиваются санитарно-защитные полосы вдоль железных дорог 100 метров;

г) определяются места въезда-выезда из населенного пункта и направление к районному центру, другим населенным пунктами.

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

3.2 Функциональное зонирование территории села «Исутору»

Быт, отдых и труд жителей сельского населенного места – главные составляющие функционального содержания его жизнедеятельности. Каждую из названных функций осуществляют на обособленной территории поселения, называемой функциональной зоной. Дифференциацию территории населенного места по характеру использования называют функциональным зонированием.

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

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

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

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

Минимальный санитарный разрыв для животноводческого комплекса 300 метров. Комплекс общехозяйственного назначения – 50 метров.

3.3 Составление общей схемы планировки жилой зоны

В сельском населенном месте можно выделить особые функциональные зоны: общественный центр и зону отдыха.

1) размещение общественного центра. Общественный центр – часть селитебной зоны, где сосредоточены главные функции административной, культурной жизни и бытового обслуживания населения. Положение общественного центра смещено от центра к въезду в село.

Центр расположен вдоль главной улицы. Общим связующим элементом общественного центра является пространство площади. Вокруг площади группируются общественные здания.

Площади имеет прямоугольную форму с соотношением сторон 1:1,6.

2) зона отдыха располагается вдоль реки на периферии жилой зоны.

Рисунок 1 – Расположение общественного центра и зоны отдыха

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

4) трассирование главных улиц. В селе «Исутору» уличная сеть представляет единую систему путей сообщения, обеспечивает наиболее удобные и короткие связи как внутри селитебной зоны между отдельными жилыми образованиями, так и с производственной зоной и внешними дорогами.

Въезд в поселок – улица, являющаяся продолжением поселковой дороги к общественному центру от районной магистрали, её ширина– 25 метров. Улица к производственной зоне просёлочная и является основным направлением потока работающего населения к производственным комплексам. Улица, ведущая от площади общественного центра к зоне отдыха – бульвар. Он украшает поселок, шириной 30 метров (рисунок 1).Все остальные дороги в селе 15 метров.

5) размещаются общественные здания вокруг площади.

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

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

Глава 4 Планировка и застройка жилой зоны.

Процесс проектирования предполагает:

1)отработку системы уличной сети;

2)решение планировочной структуры жилой зоны;

3)решение архитектурно-планировочной композиции жилой зоны;

4)размещение участков при усадебных и блокированных жилых домах;

5)организацию жилых территорий.

Состоянии, так как их износ не превышает 40%. ГЛАВА 3. ЗАДАНИЕ На разработку проекта планировки населенного пункта Сухая Долина ЗАО «Искра» с/х предприятия Ужурского района 1 Наименование объекта градостроительного планирования п. Сухая Долина Ужурского района Красноярского края 2 Основные характеристики объекта проектирования - местоположение; Ужурский район, в 28км в...

Иногда - сильноволнистые, крутизной 1 – 2°. Склоны заняты темно-каштановыми слабосмытыми почвами, а сильноволнистые участки – среднесмытыми. 1.2 Производство и перспективы развития населенного пункта Повысить объемы производства сельскохозяйственной продукции предусматривается за счет рационального и полного использования всех земельных угодий. В результате землеустроительного обследования...

И творческими возможностями зодчего. а) Существующее положение Село Лесное расположено в северо-восточной части Бурлинского района, в 55 км от районного центра и ближайшей железнодорожной станции, с которыми связано автодорогой местного значения. Село, как центральная усадьба, является с 1985 года. Застройка села неплановая и представлена в основном камышитовыми домами, состояние которых...

7.Склад рассады с ледником 8.Сарай для торфо-перегнойных горшочков Глава 3 Схема планировки 3.1 Подготовка опорного плана Основой для составления проекта планировки населенного места является опорный план - чертеж, составленный на базе топографического плана участка местности, выбранного для строительства нового или реконструкции существующего сельского поселения, на котором показано...

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

F = 20х 1 + 20х 2 + 10х 3 → min.

Запишем задачу в симплекс-таблицу (табл. 1).

Таблица 1

Базисное решение, соответствующее базису {x 4 , x 5 , x 6 } и равное (0; 0; 0; -33; 23; -12), не является допустимым ввиду отрицательности х 4 < 0, x 5 < 0, x 6 < 0.

Сформулируем правило нахождения допустимого опорного плана .
Если в столбце свободных членов есть отрицательные элементы, выберите из них наибольший по модулю, а в его строке - любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитайте таблицу по прежним правилам 2-5 .
Если в полученной таблице все элементы столбца свободных членов стали положительны либо 0, то данное базисное решение можно взять в качестве первоначального опорного плана. . Если в столбце свободных членов не все элементы неотрицательны, то еще раз воспользоваться этим правилом.
Проведем этот шаг для задачи о рационе. В качестве разрешающей строки табл. 1 нужно выбрать первую. А разрешающим элементом выберем, к примеру, элемент -4.

Таблица 2

Таблица 2

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

Решение задачи о плане симплекс-методом

Таблица 3

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

Приведем задачу к канонической форме и к специальному виду, введя дополнительные переменные х 5 , х 6 , х 7 в каждое из неравенств.
Очевидно, что, если первого ресурса необходимо для производства плановой продукции 5х 1 + 0,4х 2 + 2х 3 + 0,5х 4 , то х 5 обозначает просто излишки первого ресурса как разность между имеющимся запасом и требуемым для производства. Аналогично х 6 и х 7 . Итак, дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Запишем задачу в таблицу 4, предварительно выписав ее каноническую форму:

I этап . Это задача специального вида, базис составляют переменные { х 5 , х 6 , х 7 }, правые части уравнений неотрицательны, план х = (0, 0, 0, 0, 400, 300, 100) - опорный. Он соответствует симплекс-таблице.

Таблица 4

II этап . Проверим план на оптимальность. Так как в индексной F -строке есть отрицательные элементы, то план неоптимален, переходим к III этапу.

III этап . Улучшение опорного плана. Выберем в качестве разрешающего столбца четвертый, но могли бы выбрать и второй, т.к. в обоих (-5). Остановившись на четвертом, выберем в качестве разрешающего элемента 1, т.к. именно на нем достигается минимум соотношений . С разрешающим элементом 1 проводим преобразование таблицы по правилам 2-5 (табл. 5).

Таблица 5

Полученный план опять неоптимален, т.к. в F -строке есть отрицательный элемент -5 . этот столбец разрешающий.

В качестве разрешающего элемента выбираем 5, т.к. .

Пересчитываем еще раз таблицу. Заметим, что пересчет удобно начинать с индексной строки, т.к. если в ней все элементы неотрицательны, то план оптимален, и чтобы его выписать, достаточно пересчитать столбец свободных членов, нет необходимости вычислять "внутренность" таблицы (табл. 6).

Таблица 6

IV этап . Базисные переменные {x 5 , x 2 , x 4 } принимают значения из столбца свободных членов, а свободные переменные равны 0. Итак, оптимальный план х * = (0, 40, 0, 100, 334, 0, 0) и F * = 700. Действительно, F = 3х 1 + 4х 3 + 5х 2 + 5х 4 = 5 · 40 + 5 · 100 = 700. Т. е. для получения максимальной прибыли в 700 руб. предприятие должно выпускать изделия II вида в количестве 40 штук, IV - вида в количестве 100 штук, изделия I и III вида производить невыгодно. При этом сырье второго и третьего вида будет израсходовано полностью, а сырья первого вида останется 334 единицы (х 5 = 334, х 6 = 0, х 7 = 0).

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

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

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

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

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

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