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

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

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

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

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

при условиях

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

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

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

,

при условиях

-z

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

(26)

-z

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

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

2.3. ОСОБЕННОСТИ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ СИСТЕМЫ

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

2.3.1. ВЫБОР МОДЕЛИ

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

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

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

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11