Методы сетевого планирования

Введение

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

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

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

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

1. Экономическая постановка задачи

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

Таблица 1.1 - Длины маршрутов между серверными машинами

2. Математическая постановка задачи

Сетевая модель - графическое отображение выполняемых работ в их технологической последовательности с указанием времени выполнения каждой работы. Основными элементами сетевой модели являются:

. Событие - фиксируемый момент времени завершения i-й работы и начало выполнения (i+1)-й работы. На сетевом графике событие обозначается кружком с порядковым номером.

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

-             действительная работа, определение дано выше;

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

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

-             Действительная работа и ожидание изображаются на сетевом графике сплошной линией со стрелкой, а фиктивная работа - пунктирной линией со стрелкой в соответствии с рисунком 2.1.

Рисунок 2.1- Действительная и фиктивная работы

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

. Критический путь - это путь, который содержит напряженные работы. Напряженная работа не имеет резервов по времени для своей реализации. Работы, имеющие резервы по времени, называются некритическими. Для некритических работ имеется возможность передвинуть сроки начала и окончания работы, причем общий срок выполнения всех работ остается прежним.

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

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

При построении сетевой модели надо соблюдать правила:

• сетевая модель может содержать только одно начальное и одно завершающее событие;

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

Рисунок 2.2, 2.3 - «Висячие» события

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

-             между двумя соседними событиями может быть только одна работа. Если имеется несколько параллельно выполняемых работ, которые начинаются в одном событии и заканчиваются в другом, то одну из этих работ оставляют без изменения, а для остальных действительных работ добавляют промежуточные события и фиктивные работы в соответствии с рисунком 2.4;

а

Рисунок 2.4 - Добавление промежуточных событий и фиктивных работ: а - параллельные работы; б - фиктивные работы

-             в сетевой модели запрещено наличие замкнутых контуров в соответствии с рисунком 2.5, т. е. выполнение работ по кольцу с возвращением к начальному событию;

-             сетевая модель должна иметь максимально простую форму;

-             сетевая модель должна строго соответствовать технологическому процессу (порядку выполнения работ);

-             каждая работа маркируется двумя цифрами. Первая цифра - номер события начала работы, вторая цифра - номер события окончания работы. Маркировка работ должна быть уникальной.

Рисунок 2.5 - Замкнутые контуры

Особое внимание следует уделить правильной нумерации событий и, как следствие, правильной маркировке работ.

Нумерацию событий в сетевом графике в соответствии с рисунком 2.6, рекомендуется выполнять по следующему алгоритму

Рисунок 2.6 - Исходный сетевой график

-             определить начальное событие. Для нашего примера - событие А. Этому событию присвоить ранг 0;

-             условно вычеркнуть работы, выходящие из события А в соответствии с рисунком 2.7. Событиям Б, В и Г, которые имеют только выходящие работы, присвоить ранг 1;

Рисунок 2.7 - Определение событий первого ранга

Условно вычеркиваем работы, выходящие из событий 1-го ранга в соответствии с рисунком 2.8. Событиям Д и Е присваиваем ранг 2 и т. д. Событиям 3 и Ж - ранг 3, событию И- ранг 4;

Рисунок 2.8 - Определение событий второго ранга.

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

-        события нумеруются слева направо, т. е. от начального события к конечному событию;

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

Итоговая нумерация событий указана на рисунке 2.9.

Рисунок 2.9 - Итоговая нумерация событий

экономический сетевой вычислительный

. Выбор метода реализации задачи

Данную задачу сетевого планирования можно решить несколькими алгоритмами, в данном случае используется алгоритм Литтла, или другое название метод «ветвей и границ» или так называемая задача «Коммивояжера». Так же как и в целочисленном программировании, при использовании алгоритма Литтла необходимо определить верхнюю и нижнюю оценки для разделения множества решений на два класса. Различают две группы задач, решаемых этим алгоритмов: задачи на минимум (определяют нижнюю оценку или границу) и задачи на максимум (определяют верхнюю границу или оценку).

Идея алгоритма такова: определяют нижнюю оценку (для задачи на минимум) и разделяют исходную матрицу на две примерно равные части. Затем уменьшают размер матрицы и определяют «плату» за уменьшение размера матрицы. Размер платы может быть или положительный или нулевой т.е. увеличивать или не изменять размера нижней оценки. Размер матрицы уменьшается до 2 х 2. Затем выполняют движение в обратном порядке и получают оптимальный (по стоимости) маршрут.

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

.1 Краткая характеристика ЭВМ

Компью́тер (англ. computer - «вычислитель»), ЭВМ (электронная вычислительная машина) - машина для проведения вычислений, а также приёма, переработки, хранения и выдачи информации по заранее определённому алгоритму (компьютерной программе).

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

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

В дневниках гениального итальянца Леонардо да Винчи (1452-1519) уже в наше время был обнаружен ряд рисунков, которые оказались эскизным наброском суммирующей вычислительной машины на зубчатых колесах, способной складывать 13-разрядные десятичные числа. Специалисты известной американской фирмы IBM, 1969 году, воспроизвели машину в металле и убедились в полной состоятельности идеи ученого.

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

г. Через сто с лишним лет после смерти Леонардо да Винчи нашелся другой европеец - немецкий ученый Вильгельм Шиккард (1592-1636), не читавший, естественно, дневников великого итальянца, - который предложил свое решение этой задачи. Причиной, побудившей Шиккарда разработать счетную машину для суммирования и умножения шестиразрядных десятичных чисел, было его знакомство с польским астрономом И. Кеплером. Ознакомившись с работой великого астронома, связанной в основном с вычислениями, Шиккард загорелся идеей оказать ему помощь в нелегком труде. В письме на его имя, он приводит рисунок машины и рассказывает, как она устроена. К сожалению, данных о дальнейшей судьбе машины история не сохранила. По-видимому, ранняя смерть от чумы, охватившей Европу, помешала ученому выполнить его замысел.

Об изобретениях Леонардо да Винчи и Вильгельма Шиккарда стало известно лишь в наше время. Современникам они были неизвестны.

В 1641-1642 гг. девятнадцатилетний Блез Паскаль (1623-1662), тогда еще мало кому известный французский ученый, создает действующую суммирующую машину ("паскалину").

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

В 1673 г. другой великий европеец, немецкий ученый Вильгельм Готфрид Лейбниц (1646-1716), создает счетную машину (арифметический прибор, по словам Лейбница) для сложения и умножения двенадцатиразрядных десятичных чисел. К зубчатым колесам он добавил ступенчатый валик, позволяющий осуществлять умножение и деление.

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

В 1799 г. во Франции Жозеф Мари Жакард (1752-1834) изобрел ткацкий станок, в котором для задания узора на ткани использовались перфокарты. Необходимые для этого исходные данные записывались в виде пробивок в соответствующих местах перфокарты. Так появилось первое примитивное устройство для запоминания и ввода программной (в данном случае управляющей ткацким процессом) информации.

-1848 г.г. Завершающий шаг в эволюции цифровых вычислительных устройств механического типа сделал английский ученый Чарльз Беббидж (1791-1871). Аналитическая машина, проекткоторой он разработал, явилась механическим прототипом появившихся спустя столетие ЭВМ. В ней предполагалось иметь те же, что и в ЭВМ, пять основных устройств: арифметическое, памяти, управления, ввода, вывода. Программа выполнения вычислений записывалась на перфокартах (пробивками), на них же записывались исходные данные и результаты вычислений.

Главной особенностью конструкции этой машины является программный принцип работы.

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

программа вычислений вводится в память ЭВМ и хранится в ней наравне с исходными числами;

команды, составляющие программу, представлены в числовом коде по форме ничем не отличающемся от чисел.

Программы вычислений на машине Беббиджа, составленные дочерью Байрона Адой Августой Лавлейс (1815-1852), поразительно схожи с программами, составленными впоследствии для первых ЭВМ. Замечательную женщину назвали первым программистом мира.

Несмотря на все старания Ч. Беббиджа и А. Лавлейс, машину построить не удалось... Современники, не видя конкретного результата, разочаровались в работе ученого. Он опередил свое время.

Непонятым оказался еще один выдающийся англичанин, живший в те же годы, - Джордж Буль(1815-1864). Разработанная им алгебра логики (алгебра Буля) нашла применение лишь в следующем веке, когда понадобился математический аппарат для проектирования схем ЭВМ, использующих двоичную систему счисления. "Соединил" математическую логику с двоичной системой счисления и электрическими цепями американский ученый Клод Шеннон в своей знаменитой диссертации (1936 г.).

Через 63 года после смерти Ч. Беббиджа нашелся "некто", взявший на себя задачу создать машину, подобную по принципу действия той, которой посвятил жизнь Ч. Беббидж. Им оказался немецкий студент Конрад Цузе (1910-1985). Работу по созданию машины он начал в 1934 г., за год до получения инженерного диплома. Конрад ничего не знал ни о машине Беббиджа, ни о работах Лейбница, ни об алгебре Буля, тем не менее, он оказался достойным наследником В. Лейбница и Дж. Буля, поскольку вернул к жизни уже забытую двоичную систему исчисления, а при расчете схем использовал нечто подобное булевой алгебре. В 1937г. машина Z1 (что означало "Цузе 1") была готова и заработала! Она была, подобно машине Беббиджа, чисто механической.

К. Цузе установил несколько вех в истории развития компьютеров: первым в мире использовал при построении вычислительной машины двоичную систему исчисления (1937 г.), создал первую в мире релейную вычислительную машину с программным управлением (1941 г.) и цифровую специализированную управляющую вычислительную машину (1943 г.).

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

По-другому развивались события в США. В 1944 г. ученый Гарвардского университета ГовардАйкен (1900-1973) создает первую в США (тогда считалось первую в мире!) релейно-механическую цифровую вычислительную машину МАРК-1. В машине использовалась десятичная система счисления. Замечательным качеством машины была ее надежность. Установленная в Гарвардском университете, она проработала там 16 лет!

Вслед за МАРК-1 ученый создает еще три машины (МАРК-2, МАРК-3 и МАРК-4) - тоже с использованием реле, а не электронных ламп, объясняя это ненадежностью последних.

В отличие от работ Цузе, которые велись с соблюдением секретности, разработка МАРК1 проводилась открыто, и о создании необычной по тем временам машины быстро узнали во многих странах. Шутка ли, за день машина выполняла вычисления, на которые ранее тратилось полгода! Дочь К. Цузе, работавшая в военной разведке и находившаяся в то время в Норвергии, прислала отцу вырезку из газеты, сообщающую о грандиозном достижении американского ученого.

К. Цузе мог торжествовать. Он во многом опередил появившегося соперника. Позднее он направит ему письмо и скажет об этом.

В начале 1946 г. начала считать реальные задачи первая ламповая ЭВМ «ЭНИАК» (ENIAC), созданная под руководством физика Джона Мочли (1907-1986) при Пенсильванском университете. По размерам она была более впечатляющей, чем МАРК-1: 26 м в длину, 6 м в высоту, вес 35 тонн. Но поражали не размеры, а производительность - она в 1000 раз превышала производительность МАРК-1! Таков был результат использования электронных ламп!

В 1945 г., когда завершались работы по созданию ЭНИАК, и его создатели уже разрабатывали новый электронный цифровой компьютер ЭДВАК, в котором намеривались размещать программы в оперативной памяти, чтобы устранить основной недостаток ЭНИАКа - сложность ввода программ вычислений, к ним в качестве консультанта был направлен выдающийся математик, участник Матхеттенского проекта по созданию атомной бомбы Джон фон Нейман (1903-1957). В1946 г. Нейманом, Голдстайном и Берксом (все трое работали в Принстонском институте перспективных исследований) был составлен отчет, который содержал развернутое и детальное описание принципов построения цифровых электронных вычислительных машин, которых и придерживаются до сих пор.

Для написания и работы программы необходима ЭВМ со следующими минимальными параметрами (для Delphi 7):

−    процессор Intel Pentium 90;

−       операционная система Microsoft Windows 95, 98;

−       оперативнаяпамять32MB;

−       жесткийдиск 80Мб.

Для компьютера с Delph 7:

−    процессор Pentium 166 MHz

−       операционная система MicrosoftWindows 98, 2000, andXP;

−       оперативнаяпамять 256 MB;

−       жесткийдиск 475Мб.

Эти параметры необходимы только для языков программирования. Написанная и откомпилированная программа намного менее требовательна к параметрам компьютера.

.2 Особенности выбора языка программирования

- результат развития языка Турбо Паскаль, который, в свою очередь, развился из языка Паскаль. Паскаль был полностью процедурным языком, Турбо Паскаль начиная с версии 5.5 добавил в Паскаль объектно-ориентированные свойства, а Delphi - объектно-ориентированный язык программирования с возможностью доступа к метаданным классов (то есть к описанию классов и их членов) в компилируемом коде, также называемом интроспекцией. Так как все классы наследуют функции базового класса TObject, то любой указатель на объект можно преобразовать к нему, после чего воспользоваться методом ClassType и функцией TypeInfo, которые и обеспечат интроспекцию. Также отличительным свойством Delphi от С++ является отсутствие возможности располагать объекты в стеке (объекты, унаследованные из Турбо Паскаля, располагаться в стеке могут) - все объекты попадают в динамически выделяемую область (кучу).

Внешний вид среды программирования Delphi отличается от многих других из тех, что можно увидеть в Windows. Кпримеру, Borland Pascal for Windows 7. 0, Borland C++ 4. 0, Word for Windows, Program Manager - этовсе MDI приложенияивыглядятпо-другому, чем Delphi. MDI (MultipleDocumentInterface) - определяет особый способ управления нескольких дочерних окон внутри одного большого окна.

Среда Delphi же следует другой спецификации, называемой SingleDocumentInterface (SDI), и состоит из нескольких отдельно расположенных окон. Это было сделано из-за того, что SDI близок к той модели приложений, что используется в Windows 95.

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

Название данного языка программирования перекликается с именем одного из древнегреческих городов на побережье Коринфского залива - Дельфы. Однако, в отличие от этого памятника, который в настоящее время напоминает лишь развалины, Delphi входит в число популярных современных систем, позволяющих разрабатывать программы. Глава исследовательской группы по созданию системы программирования DelphiЧакЯзджевски как-то вспоминал, что имя Delphi, в конце концов, было выдвинуто Дэнни Торпом в момент очередной "мозговой атаки".

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

В качестве базового языка программирования в Delphi был выбран ObjectPascal, другими словами, Паскаль, основанный на объектно-ориентированном программировании. Ядром, буйно разросшимся впоследствии в ветвистое дерево Delphi, стал язык программирования TurboPascal. Основное различие системы программирования Delphi от TurboPascal состоит в том, что TurboPascal по большей степени разработан для работы в текстовом режиме операционной системы DOS, а система программирования Delphi ориентирован на графический режим.

Графические возможности Delphi дают возможность лицезреть на дисплее монитора, как "оживают" многочисленные конструкции языка, что играет большую роль для эффективного усвоения за короткое время. Delphi является мощной системой программирования, которая имеет множество приложений везде: научные и инженерные расчеты, автоматизация управленческой деятельности. Delphi - достаточно тонкий и универсальный инструмент, который способен на многое, если им руководит опытный мастер.является результатом развития языка программирования TurboPascal, возникший из языка Паскаль. Pascal был в то время процедурным языком, тогда как TurboPascal добавил в Pascal объектно-ориентированное программирование, а для Delphi - возможность доступа к описанию классов и членов класса в исходном коде. Отличительное свойство Delphi от C++ заключается в отсутствии возможности размещать объекты в стеке - все эти объекты впоследствии оказываются в динамической выделяемой области (куче). Объекты БД в Delphi основаны на SQL и включают в себя полную мощь BorlandDatabaseEngine. В состав Delphi также включен Borland SQL Link, поэтому доступ к СУБД Oracle, Sybase, Informix и InterBase происходит с высокой эффективностью. Кроме того, Delphi включает в себя локальный сервер Interbase для того, чтобы можно было разработать расширяемые на любые внешние SQL-сервера приложения в онлайновом режиме.

В Delphi операция присвоения значения переменной обозначается при помощи двоеточия со знаком равенства, :=, что является заимствованием из математической нотации. Знак равенства без двоеточия - это оператор проверки равенства, возвращающий булево значение. Напротив, C-подобных языках оператором присваивания является знак одинарный знак равенства, а оператором проверки равенства - двойной, ==. В силу того, что в этих языках программирования присваивание является лишь выражением, возвращающем значение переменной слева, не так уж редки следующие неочевидные ошибки.

.3 Алгоритм программы

.        Выбор размера матрицы

.        Ввод данных в матрицу

.        Цикл зануления матрицы и определение нижней оценки

.        Цикл вычисления оценок клетки

.        Зануление матрицы

.        Определение нижней оценки клетки

.        Постройка древа подмножеств

.        Вывод данных, определение длины пути и оптимальный обход городов

5. Решение задачи теста для написания и отладки программы

Таблица 5.1 - Длины маршрутов между городами

Для начала нужно выполнить «зануление» матрицы используя дельта метод при решении транспортных задач:

Рисунок 5.1 - Этапы «зануления» исходной матрицы

После «зануления» матрицы её элементы должны содержать или положительные, или нулевые значения. Сумма вычтенных значений со строками равна 35 (4+3+3+8+7+10), по столбцам - 6 (1+0+0+2+0+3). Общая сумма всех вычитаний - 41. Это и есть нижняя оценка.

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

Далее для каждой клетки матрицы, содержащей ноль, надо вычислить частную оценку клетки или просто оценку клетки.

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

Клетка 1-3 содержит значение ноль. Оценка этой клетки будет равна сумме минимального элемента по первой строке и минимального элемента по третьему столбцу 2+0=2. Для клетки 3-2 оценка будет 0+0=0. Оценки клеток представлены клеток представлены в виде верхнего индекса на рисунке 5.2:

Рисунок 5.2 - Расчет оценок клеток

Начиная с этого момента приступаем к построению дерева ветвления алгоритма. Максимальная оценка 5 принадлежит двум клеткам 5-6 и 6-5. Поэтому за «нулевое» ребро принимается или ребро 5-6, или ребро 6-5.

Возьмем ребро 5-6. Все маршруты разобьем на содержащие ребро 5-6 и не содержащее это ребро. Обе группы маршрутов будут иметь стоимость не менее нижней оценки.

Проанализируем выполненные преобразования и построим дерево алгоритма. В результате расчета «зануления» исходной матрицы была получена нижняя оценка - 41. Таким образом, стоимость любого допустимого маршрута будет не менее 41. После вычисления оценок нулевых оценок, была выбрана клетка 5-6 с максимальной оценкой 5. Соответственно, ребро, соединяющие города 5 и 6, было объявлено «нулевым», и все возможные маршруты были разделены на две группы: содержащие ребро 5-6 и не содержащие этого ребра. Новая нижняя оценка для маршрутов, не содержащих ребра 5-6, должна быть увеличена на оценку клетки 5-6 и составит 41+5=46.

На первом шаге нулевое ребро было помечено серым цветом и изъято из дальнейшего рассмотрения. Далее рассматривалась только левая ветвь дерево ветвления алгоритма. Общая сумма «зануления» равна 5. Нижняя оценка для левой группы маршрутов составит 41+5=46.

На втором шаге была выбрана клетка 6-4 с оценкой 7. Новая нижняя оценка для маршрутов группы, не содержащей ребро 4-5, будет 53 и ветвление будет выполнено по ребру 6-4. Общая сумма «зануления» (по строкам и столбцам) составит 3. Нижняя оценка для левой группы маршрутов будет 46+3=49.

На третьем шаге будет удалено ребро 2-5. Оценка клетки 2-5 составляет 4. Следовательно, нижняя оценка правой группы маршрутов будет 49+4=53. Общая сумма «зануления» - 2. Нижняя оценка левой группы маршрутов равна 49+2=51.

На четвертом шаге выбрана клетка 3-2 с оценкой 2. Нижняя оценка правой группы маршрутов равна 51+2=53. Общая сумма «зануления» - 1. Нижняя оценка левой группы маршрутов равна 51+1=52. В результате анализа было составлено дерево ветвления алгоритма (в соответствии с рисунком 5.3).

Рисунок 5.3 - Дерево ветвления алгоритма

Построение оптимального маршрута выполним используя рисунок 6 и 5. На последнем (четвертом шаге) осталось два свободных (не запрещенных) ребра 1-3 и 4-1. Оба ребра включает в маршрут и добавляем ребра из левой ветви.

Оптимальный маршрут будет состоять ребер 1-3; 4-1; 3-2; 2-5; 6-4 и 5-6. После упорядочения получим: 1-3-2-5-6-4-1.

Ответ: длина оптимального маршрута не менее 52, порядок объезда городов: 1-3-2-5-6-4-1.

. Анализ полученных результатов

Программа полностью работоспособна и верно рассчитывает задачу-тест. Результат работы программы отображен на рисунке 6.1:

Рисунок 6.1 - Результат работы программы

7. Инструкция пользователю и описание программы

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

Рисунок 7.1 - Окно ввода данных в программу

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

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

Рисунок 7.2 - окно вычисления программы и вывод результатов

Полученные данные можно сохранить на компьютере для дальнейшей работы, или открыть их на другом компьютере. Для это нужно открыть меню Файл/Сохранить, появиться диалоговое окно сохранения, файл сохраняется с расширением *.kom. Чтобы открыть файл нужно выбрать меню Файл/Открыть и в диалоговом окне выбрать файл с расширением *.kom.

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

Рисунок 7.3 - справка о теории

В меню Справка/О программе будет описано для чего создана эта программа

Рисунок 7.4 - справка о программе

Заключение

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

Существуют несколько методов решения таких задач: метод полного перебора, «жадные» методы (Крускала, Прима, и т.п.), генетические алгоритмы и еще множество их обобщений. Однако только метод Литтла (метод ветвей и границ) дает нам в итоге самое оптимальное решение.

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

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

Список литературы

1.   Вентцель Е.С. Исследование операций: задачи, принципы, методология. - М.: Высшая школа, 2010. - 208 с.

2.      Исследование операций в экономике/ Под ред. Кремера Н.Ш. - М.:ЮНИТИ, 2011. - 407 с.

.        Конюховский П.В. Математические методы исследования операций в экономике. Краткий курс. - СПб.: Питер, 2010. - 208 с.

.        Просветов Г.И. Математические методы в экономике: Учебно-методическое пособие. - М.: Издательство РДЛ, 2011. - 160 с.

.        Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. - М.: Вузовский учебник, 2011. - 144 с.

6.   Костевич Л.С. Математическое программирование: Информационные технологии оптимальных решений. - Мн.: Новое знание, 2010. - 424 с.

.     Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 2012. - 319 с.

Приложение

Main;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls, ExtCtrls, Buttons, Menus;=10;=array[1..NN,1..NN] of integer;=array[1..NN] of integer;=array[0..NN,0..2] of integer;=array[1..NN] of byte;=array[1..NN*2] of integer;= class(TForm): TImage;: TLabel;: TLabel;: TLabel;: TBitBtn;: TLabel;: TLabel;: TComboBox;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TEdit;: TMainMenu;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TMenuItem;: TOpenDialog;: TSaveDialog;(Sender: TObject);BitBtn1Click(Sender: TObject);ComboBox1Change(Sender: TObject);N2Click(Sender: TObject);N3Click(Sender: TObject);N4Click(Sender: TObject);;(varGInd:integer);(varr,m:byte);;;(Stroka,Stolb:byte);Tree(K,XPos,YPos,Index,RG,MG,Blok,GIn:byte);(S: string; IndexX: byte; IndexY: byte): TEdit;(S: string; IndexX: byte): TLabel;

{ Private declarations }

{ Public declarations };: TForm1;,GorodaIJ:Gorod;,Cj:Dopolnit;:ConPrived;:Iskluch;:Iskluch;:TEdit;:TLabel;,NewPut:ItogPuti;:byte;:integer;

{$R *.dfm}

{****************************************************}

{Функция обращение к элементам EditчерезихName в строковом режиме}

function TForm1.ObjEdit(S: string; IndexX: byte; IndexY: byte): TEdit;:=Form1.FindComponent(S + IntToStr(IndexX) + IntToStr(IndexY)) as TEdit;

end;

{****************************************************}

{Функция обращение к элементам LabelчерезихName в строковом режиме}

function TForm1.ObjLabel(S: string; IndexX: byte): TLabel;:=Form1.FindComponent(S + IntToStr(IndexX)) as TLabel;

end;

{****************************************************}

{Процедура чтения матрицы из Edit`ов}

procedure TForm1.InputMatrix;,j:integer;i:=1 to N do[i,i]:=-1;j:=1 to N do<>j then[i,j]:=StrToInt(ObjEdit('Edit',i,j).Text);

end;;;;

{****************************************************}

{Процедура нахождения перспективной пары из множества конкурирующих пар}

procedure TForm1.Konkurir(varr,m:byte);,j,l:byte;,ymin,max:integer;i:=1 to N doj:=1 to N do[i,j]:=-1;

{Определяем множество конкурирующих пар городов и определяем для них оценку}

for i:=1 to N doj:=1 to N do[i,j]=0 then:=9999; ymin:=9999;l:=1 to N do(GorodaIJ[i,l]<=xmin) and (GorodaIJ[i,l]<>-1) and (l<>j) then:=GorodaIJ[i,l];(GorodaIJ[l,j]<=ymin) and (GorodaIJ[l,j]<>-1) and (l<>i) then:=GorodaIJ[l,j];;=9999 then xmin:=0;=9999 then ymin:=0;[i,j]:=xmin+ymin;

end;

{Находим перспективную пару (r,m)}

max:=-1;i:=1 to N doj:=1 to N do[i,j]>max then:=ParKonkur[i,j];:=i; m:=j;;;

{***************************************************}

{Процедуры ПРИВЕДЕНИЯ матрицы.

А также для нахождения нижней оценки G}

procedure TForm1.Etap(varGInd:integer);,j,min:integer;

begin:=0;

{Находим минимальный элемент матрицы по строкам}

for i:=1 to N do:=-1;j:=1 to N do[i,j]<>-1 thenmin=-1 then min:=GorodaIJ[i,j];[i,j]<=min then:=GorodaIJ[i,j];;;;min=-1 then min:=0;

Cj[i]:=min;;

{отнимаем минимальные элементы из элементов соответствующих строк}

for i:=1 to N doj:=1 to N do[i,j]<>-1 then[i,j]:=GorodaIJ[i,j]-Cj[i];

end;;

{Находим минимальный элемент полученной матрицы по столбцам}

for j:=1 to N do:=-1;i:=1 to N do[i,j]<>-1 thenmin=-1 then min:=GorodaIJ[i,j];[i,j]<=min then:=GorodaIJ[i,j];;;;min=-1 then min:=0;

Ci[j]:=min;;

{отнимаем минимальные элементы из элементов соответствующих столбцов и находим оптимальное множество с оценкой}

for i:=1 to N do:=GInd+Cj[i]+Ci[i];j:=1 to N do[i,j]<>-1 then[i,j]:=GorodaIJ[i,j]-Ci[j];;;;

{****************************************************}

{ПроцедуравычеркиванияизматрицыStrokaстрокииStolbстолбца}TForm1.DelStrStolb(Stroka,Stolb:byte);:byte;(Stroka<>0) and (Stolb<>0) theni:=1 to N do[Stroka,i]:=-1;[i,Stolb]:=-1;;

end;

{****************************************************}

{Процедура нахождения оптимального пути}

procedure TForm1.OpredilPuti;,j,k,l:integer;

Fl:boolean;

{Поиск начального элемента}

for i:=1 to n do:=False;j:=1 to N do[i*2-1]=Puti[j*2] then Fl:=true;not Fl then[1]:=Puti[i*2-1];[2]:=Puti[i*2];;;

{Составления оптимального маршрута}

fork:=1 toN+1 do

beginl:=1 to N+1 do[l*2-1]=Newput[k] then[k]:=Puti[l*2-1];[k+1]:=Puti[l*2];;[N+1]:=newput[1];;

{Вывод последовательности городов на экран}

for i:=1 to N do.Caption:=Label3.Caption+'A'+inttostr(newPut[i])+'->';.Caption:=Label3.Caption+'A'+inttostr(newPut[N+1]);

end;

{****************************************************}

{Процедура проверки на замкнутость пути}

procedureProverkaIskl;,j,Stroka,Stolbec,x,y:byte;:=0;:=0;i:=1 to N do:=0;:=0;j:=1 to N do(GorodaIJ[i,j]=-1) and (IsklStrok[i]<>1) then(IsklStolb[j]<>1) then Stroka:=1;(GorodaIJ[j,i]=-1) and (IsklStolb[i]<>1) then(IsklStrok[j]<>1) then Stolbec:=1;;(Stroka=0) and (IsklStrok[i]<>1) then:=i;:=1;;(Stolbec=0) and (IsklStolb[i]<>1) then y:=i;;x<>0 theny<>0 then GorodaIJ[x,y]:=-1;

end;

{****************************************************}

{Процедура вывода дерева ветления на экран}

procedure TForm1.Tree(K,XPos,YPos,Index,RG,MG,Blok,GIn:byte);Image1.Picture.Bitmap.Canvas do.Name:='Arial';.Style:=[fsBold];.Width:=2;.Color:=clMaroon;(XPos=0) and (YPos=0) then.Size:=7;.Color:=clBlue;.Color:=clYellow;(N*30-15,10,15+N*30,40);(N*30-10,18,'G[0]');.Color:=clWhite;.Color := clBlue;(N*30-27,18,IntToStr(GIn));begin.Size:=7;.Color:=clBlue;.Color:=clYellow;(XPos*50+N*30-30-YPos*30+K*60,10+YPos*50,XPos*50+N*30-60-YPos*30+K*60,40+YPos*50);(XPos*50+N*30-58-YPos*30+K*60,18+YPos*50,('G['+IntToStr(Index+1)+','+IntToStr(XPos)+']'));.Color:=clWhite;.Color := clGreen;Blok=1 then.Style:=[fsStrikeOut,fsBold].Style:=[fsBold];(XPos*55+N*30-60-YPos*30+K*60,YPos*50-8,'('+IntToStr(RG)+','+IntToStr(MG)+')');.Color := clBlue;.Style:=[fsBold];(XPos*94+N*30-115-YPos*30+K*60,YPos*50+18,IntToStr(GIn));.Color:=clRed;(XPos*50+N*30-45-YPos*30+K*60,10+YPos*50);(Index+N*30-(YPos-1)*30+K*60,38+(Index)*50);

end;;;

{****************************************************}

{Процедура создания главной формы}

procedure TForm1.FormCreate(Sender: TObject);.Picture.Bitmap:=nil;.Picture.Bitmap := TBitmap.Create;.Picture.Bitmap.Width := Image1.Width;.Picture.Bitmap.Height := Image1.Height;

end;

{****************************************************}

{Процедура сброса всех значений}

procedure TForm1.Sbros;,j:integer;:=-1;i:=1 to NN do[i]:=0;[i]:=0;[i]:=0;[i]:=0;j:=1 to NN do[i,j]:=0;;i:=0 to NN doj:=0 to 2 do[i,j]:=0;i:= 1 to NN*2 do[i]:=0;[i]:=0;;.Caption:='';.Picture.Bitmap.canvas.fillrect(canvas.cliprect) ;N>6 then.Width:=250+(N-6)*30;.Height:=310+(N-6)*50;.Picture.Bitmap.Width := Image1.Width;.Picture.Bitmap.Height := Image1.Height;.Height:=395+(N-6)*50;.Width:=640+(N-6)*30;.Width:=250;.Height:=310;.Height:=445;.Width:=640;;;

{****************************************************}

{Процедура нажатия кнопки начала}

procedure TForm1.BitBtn1Click(Sender: TObject);,RGor,MGor:byte;

Flag:boolean;:=-1;

{Получения количества городов}:=StrToInt(ComboBox1.Text);

{Сброс всех значений на 0};:=true;

{Ввод матрицы длин путей между городами};

{Предварительный этап.Определения исходного множества G0}(GIndexKon[0,1]);[0,2]:=GIndexKon[0,1];

{Вывод G0 на экран в виде вершины дерева}(0,0,0,0,0,0,0,GIndexKon[0,1]);

{Определение множества конкурирующих пар и выбор перспективной пары}

Konkurir(RGor,MGor);[1]:=RGor;[2]:=MGor;[RGor,MGor]:=-1;

{i-ыеитерации.}i:=1 to N-1 doFlag then

{ОпределениемножестваG(i,2)}(GIndexKon[i,2]);[i-1,1]<GIndexKon[i-1,2] then[i,2]:=GIndexKon[i,2]+GIndexKon[i-1,1]begin GIndexKon[i,2]:=GIndexKon[i,2]+GIndexKon[i-1,2];

K:=K+1;;

{Вывод подмножества G(i,2) на экран в виде листа дерева}

Tree(K,2,i,i-1,RGor,MGor,1,GIndexKon[i,2]);

{Удаление RGor'ой строки и MGor'ого столбца}

DelStrStolb(RGor,MGor);[RGor]:=1;

IsklStolb[MGor]:=1;

{Вызов процедуры предотвращения образования коротких и длинных подциклов};

{Определение множества G(i,1)}

Etap(GIndexKon[i,1]);[i-1,1]<GIndexKon[i-1,2] then[i,1]:=GIndexKon[i,1]+GIndexKon[i-1,1][i,1]:=GIndexKon[i,1]+GIndexKon[i-1,2];.Caption:='Длинапути: '+IntToStr(GIndexKon[i,1]);

{Вывод подмножества G(i,1) на экран в виде листа дерева}

Tree(K,1,i,i-1,RGor,MGor,0,GIndexKon[i,1]);

{Определение множества конкурирующих пар и выбор перспективной пары}

Konkurir(RGor,MGor);[RGor,MGor]>=0 then[i*2+1]:=RGor;[i*2+2]:=MGor;;[RGor,MGor]<0 then Flag:=false;[RGor]:=1;[MGor]:=1;[RGor,MGor]:=-1;

end;

{Определение оптимального маршрута};

end;TForm1.ComboBox1Change(Sender: TObject);,j:byte;i:=1 to NN do('Label1',i).Visible:=False;('Label2',i).Visible:=False;j:=1 to NN do('Edit',i,j).Visible:=False;;:=StrToInt(ComboBox1.Text);i:=1 to N do('Label1',i).Visible:=True;('Label2',i).Visible:=True;j:=1 to N do('Edit',i,j).Visible:=True;;;TForm1.N2Click(Sender: TObject);:Integer;,j:byte;,num:integer;;.InitialDir:=Application.ExeName;.Filter:='ФайлКоммивояжера (*.kom)|*.kom';not OpenDialog1.Execute then exit;:=FileOpen(OpenDialog1.FileName,fmOpenRead);(FInput,num,sizeof(num));i:=1 to num doj:=1 to num do<>j then(FInput,s,sizeof(s));('Edit',i,j).Text:=IntToStr(s);;.ItemIndex:=num-2;Change(ComboBox1);(FInput);;TForm1.N3Click(Sender: TObject);:Integer;,j:byte;,num:integer;.InitialDir:=Application.ExeName;.Filter:='ФайлКоммивояжера(*.kom)|*.kom';not SaveDialog1.Execute then exit;:=FileOpen(SaveDialog1.FileName,fmOpenWrite);=-1 then:=FileCreate(ChangeFileExt(SaveDialog1.FileName,'.kom'));:=StrToInt(ComboBox1.Text);(FOutput,num,sizeof(num));i:=1 to num doj:=1 to num do<>j then:=StrToInt(ObjEdit('Edit',i,j).Text);(FOutput,s,SizeOf(s));;(FOutput);(SaveDialog1.FileName,'.kom');TForm1.N4Click(Sender: TObject);;;TForm1.N7Click(Sender: TObject);('Ïðîãðàììàäëÿðåøåíèÿçàäà÷èêîììèâîÿæåðà, ïóòåìîáíàðóæåíèÿìèíèìàëüíîãîïóòèîáõîäàãîðîäîâèñïîëüçóÿìåòîäâåòâåé è ãðàíèö');TForm1.N8Click(Sender: TObject);(' ãðàôå "Êîëè÷åñòâîãîðîäîâ" óêàçàòü ÷èñëîòî÷åê, â òàáëèöå "Ðàññòîÿíèÿìåæäóãîðîäàìè" ââåñòèçíà÷åíèÿ, äèàãîíàëüçàïîëíÿåòñÿàâòîìàòè÷åñêè, çíàê ### ýòî 0');('Äëÿðàñ÷åòàíóæíîíàæàòüêíîïêó "Íàéòèïóòü", ïîëó÷åííûåðåçóëüòàòûáóäóòîòîáðàæàòüñÿ â ãðàôåÄëèíàïóòè è Îïòèìàëüíûéîáõîä, à òàêæåáóäåòïîêàçàíîÄåðåâîïîäìíîæåñòâ');('Ðåçóëüòàòûìîæíîñîõðàíèòüíàêîìïüþòåðå ñ ðàñøèðåíèåì *.kom â ïàïêå ñ ïðîãðàììîé');

end.