Этапы жизненного цикла проекта автоматизации

PHP имеет встроенные библиотеки для выполнения многих задач, связанных с Web. Возможности PHP включают формирование изображений, файлов PDF, роликов Flash, а также текстовых данных - XHTML и других XML-файлов. PHP позволяет осуществлять автоматическую генерацию таких файлов и сохранять их в файловой системе сервера, организуя, таким образом, кеш динамического содержания, расположенный на стороне сервера.

Одним из значительных преимуществ PHP является поддержка широкого круга баз  данных: IBM DB2, Informix, InterBase, MySQL, Oracle, Sybase и других.

PHP доступен для большинства операционных систем, включая Linux, многие модификации Unix, Microsoft Windows, Mac OS X и многих других. Таким образом, выбирая PHP, предоставляется свобода выбора операционной системы и web-сервера.

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

JavaScript

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

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

JavaScript обладает рядом свойств объектно-ориентированного языка, но благодаря прототипированию поддержка объектов в нём отличается от традиционных языков.

2. Алгоритмы и технология решения задач

Схема графического диалога пользователя в интернет-гипермаркете представлена на рис. 2.6.

Процесс посещения клиентом интернет - гипермаркета:

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

 

 

                                                             

                                                                

                                    

 

Рис. 2.6. Схема графического диалога пользователя в интернет-гипермаркете

 

 

 

 

 

 

 

 

 

 

1. Обобщенный алгоритм решения задач и декомпозиция (разбиение) его на модули.

 

 

3. Формализация расчетов (математическая модель).

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

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

 

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

Задача маршрутизации реализуется набором алгоритмов, каждый из которых осуществляет решение задачи коммивояжера. Коммивояжер (распространитель товаров) должен объехать всех получателей товаров. Он выезжает из некоторого пункта и должен вернуться в него же в конце путешествия. Предполагается, что коммивояжер никогда не бывает дважды в одном пункте. Расстояния между получателями товаров задаются с помощью квадратной матрицы расстояний С = [с(i, j)] размерности k x k, где k – количество получателей товаров, с(i, j) – расстояние от получателя i до получателя j. Отметим, что, в общем случае, матрица расстояний не является симметричной. Диагональные элементы матрицы расстояний равны нулю. Задача коммивояжера состоит в таком объезде всех получателей, чтобы суммарное пройденное расстояние было минимальным. Следует выбрать один оптимальный маршрут из (k-1)! возможных.

Если количество получателей невелико: (k < 13), то решение может быть получено с использованием метода ветвей и границ.

 

Постановка задачи

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

·       маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в  тот город, из которого он начал движение;

·       в каждом из городов коммивояжер  должен побывать точно один раз, то

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

Для расчета  затрат существует матрица условий, содержащая затраты на переход

из каждого  города в каждый, при этом считается, что можно перейти из любого

города в  любой, кроме того же самого (в матрице  как бы вычеркивается

диагональ). Целью решения является нахождения маршрута, удовлетворяющего всем

условиям  и при этом имеющего минимальную сумму затрат. 

Для практической реализации идеи метода ветвей и границ применительно к задаче коммивояжера нужно найти метод определения  нижних границ подмножества и разбиения  множества гамильтоновых контуров на подмножества. Определение нижних границ базируется на том утверждении, что если ко всем элементам i-й строки или j-го столбца матрицы C={ c_ij } весов ребер графа прибавить или вычесть число α, то задача останется эквивалентной прежней, то есть оптимальность маршрута коммивояжера не изменится, а длина любого гамильтонова контура изменится на данную величину α [1].

 

Алгоритм решения

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

Основные  шаги решения задачи коммивояжера этим методом:

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

Математическая модель задачи

N - число  городов.

С = [с(i, j)] -  квадратная матрица расстояний,

Xi j - матрица переходов с компонентами:

Xi j  = 1, если коммивояжер совершает переход из i-го города в j-й,

Xi j  = 0, если не совершает перехода,

где i, j = 1..N  и i≠j.

Целевая функция  задачи состоит в минимизации:

               (1)

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

  Ui - Uj + N × Xij ≤ N-1, где  i, j = 1..N, i≠j     (4)

 

Условия (1, 2, 3)  в совокупности обеспечивают, что каждая переменная x_ij равна или нулю, или единице. При этом ограничения (1), (2) выражают условия, что коммивояжер побывает в каждом городе один раз в него прибыв (ограничение (1)), и один раз из него выехав (ограничение (2)).

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

Доказательство, что модель (1-4) описывает задачу о коммивояжере:

Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.

 

Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами можно сформулировать в виде следующих правил:

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

.

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

,

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

3. Суммируем  элементы  и , получим константу приведения

  ,

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

.

4. Находим  степени нулей для приведенной  по строкам и столбцам матрицы.  Для этого мысленно нули в  матице заменяем на знак «∞» и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки:

.

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

.

6. Разбиваем  множество всех гамильтоновых  контуров  на два подмножества и . Подмножество гамильтоновых контуров содержит дугу , - ее не содержит. Для получения матрицы контуров , включающих дугу , вычеркиваем в матрице строку и столбец . Чтобы не допустить образования негамильтонова контура, заменим симметричный элемент на знак «∞».

7. Приводим  матрицу гамильтоновых контуров  . Пусть - константа ее приведения. Тогда нижняя граница множества определится так:

.

8. Находим  множество гамильтоновых контуров  , не включающих дугу . Исключение дуги достигается заменой элемента в матрице на ∞.

9. Делаем  приведение матрицы гамильтоновых  контуров  . Пусть - константа ее приведения. Нижняя граница множества определится так:

.

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

Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений.

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

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

Программная реализация:

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