Дипломная работа: Разработка математической модели и ПО для задач составления расписания

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

Эти идеи послужили основанием прямого алгоритма в целочисленном программировании:

Шаг 0. Начать со столбцовой таблицы, в которой ai00 (i1) и все элементы a0j, aij и ai0 – целые.

Шаг 1. Проверить выполнение условий a0j0 (j1); если они выполнены, то конец, текущее базисное решение оптимально; если нет – перейти к шагу 2.

Шаг 2. Выбрать ведущий столбец s с a0s< 0. Выбрать строку v по правилу проверки отношения ai0/ais среди строк с ais> 0. Эта строка служит производящей для отсечения Гомори.

Шаг 3. Получить отсечение Гомори из производящей строки и дописать ее внизу таблицы, т.е. добавить к ограничениям задачи уравнение (23), где .

Шаг 4. Произвести преобразование таблицы, используя отсечение (23) как ведущую строку. Слабая переменная sk в (23) станет небазисной. Вернуться к шагу 1.

Доказательство конечности алгоритма см. [2], стр. 346-353.

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

(24)

Строка v может стать производящей тогда и только тогда, когда

(25)

где определяется из условия

Определим множество V(s) как совокупность строк, удовлетворяющих условию (25).

Следующие два правила представляют собой примеры допустимых правил выбора производящей строки:

Правило 1.

1. Составить последовательный конечный список индексов строк таким образом, чтобы индекс каждой строки вошел в него по меньшей мере один раз. Перейти к 2.

2. Если список пуст или не содержит ни одного индекса из V(s), вернуться к 1.; в противном случае найти в списке первый индекс vV(s). Выбрать строку v как производящую. Вывести из списка индекс v и все предшествующие ему индексы. Перейти к 3.

3. Последовательно выбирать строку v, взятую в 2., как производящую, до тех пор, пока vV(s). Как только vV(s), вернуться к 2.

Правило 2.

1. Пусть Vt(s) – множество V(s), соответствующее t-й таблице. Если Vt(s) содержит более одного элемента: Vt(s) = {v1, v2, …, vk+2}, то в качестве производящей выбрать такую строку , что в последовательности множеств V1(s1), V2(s2), …, Vt(s) строка появилась раньше (не позднее) остальных и затем сохранялась вплоть до Vt(s); перейти к 2.

2. Последовательно выбирать строку v, взятую в 1., до тех пор, пока . Как только , вернуться к 1.

Подробнее об алгоритме можно прочитать в [2], стр. 344.

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

Пусть задача линейного программирования записана в канонической форме:

минимизировать

при условиях

Все bi можно сделать неотрицательными, умножив, если надо, соответствующее уравнение на –1. Тогда можно добавить в каждое уравнение искусственную переменную (искусственные переменные должны быть неотрицательными) таким образом, чтобы из искусственных переменных образовать начальный базис:

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

то, добавив слабую переменную в каждое неравенство, получим:

Если bi0, то si можно использовать в качестве начальных базисных переменных.

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

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

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

Рассмотри в качестве примера следующую задачу линейного программирования:

минимизировать

при условиях

где все bi неотрицательны.

Если ввести искусственные переменные и новую целевую функцию , то получим задачу:

минимизировать

,

при условиях

-z

Если вычесть все уравнения, содержащие bi, из -формы, получим:

(26)

-z

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

Подробнее об алгоритме можно прочитать в [2], стр. 53.

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

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

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

В настоящее время существовует три основных подхода к формированию модели данных: иерархический, сетевой и реляционный.

ИЕРАРХИЧЕСКИЙ СПОСОБ ОРГАНИЗАЦИИ

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

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

СЕТЕВОЙ СПОСОБ ОРГАНИЗАЦИИ

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

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

Тип связи определяется для двух типов записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка. Для данного типа связи L с типом записи предка P и типом записи потомка C должны выполняться следующие два условия:

1. Каждый экземпляр типа P является предком только в одном экземпляре L;

2. Каждый экземпляр C является потомком не более, чем в одном экземпляре L.

РЕЛЯЦИОННЫЙ СПОСОБ ОРГАНИЗАЦИИ

Основными недостатками иерархичекого и сетевого типов моделей данных являются:

1. Слишком сложно пользоваться;

2. Фактически необходимы знания о физической организации;

3. Прикладные системы зависят от этой организации;

4. Их логика перегружена деталями организации доступа к БД.

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

В структурной части модели фиксируется, что единственной структурой данных, используемой в реляционных БД, является нормализованное n-арное отношение.

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

Наконец, в целостной части реляционной модели данных фиксируются два базовых требования целостности, которые должны поддерживаться в любой реляционной СУБД. Первое требование называется требованием целостности сущностей. Второе требование называется требованием целостности по ссылкам.

После предварительного анализа математической модели системы и способов организации данных, а также имеющегося на рынке ПО (иерархический и сетевые способы организации предполагают объектно - орентированный подход к организации данных и на сегодняшний день имеются такие СУБД (например, Jasmin или Informix Dynamic Server), но на момент разработки возможности их использования не было, в то же время существуют очень “мощные” реляционные СУБД (к примеру Oracle 8i)) выбор был сделан в пользу реляционного способа организации хранения данных.

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

Страницы: 1, 2, 3, 4