Разработка математической модели и программного обеспечения расписания в ВУЗе
Формулировка задачи составления расписания в применении к расписанию учебных занятий. Разработка математической модели и практическая реализация системы автоматического составления расписания. Анализ полученных результатов. Листинг программного модуля.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | дипломная работа |
Язык | русский |
Дата добавления | 05.10.2013 |
Размер файла | 1,8 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
ДИПЛОМНАЯ РАБОТА
РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ РАСПИСАНИЯ В ВУЗЕ
Содержание
- Введение 4
- 1. Описание технологической области 6
- 1.1 Формулировка задачи составления расписания 6
- 1.1.1 Общая формулировка задачи составления расписаний 6
- 1.1.2 Формулировка задачи составления раписания в применении к расписанию учебных занятий. 6
- 1.2 Анализ существующего ПО 7
- 1.3 Постановка задачи. 9
- 2. Разработка математической модели и практическая реализация системы автоматического составления расписания 11
- 2.1 Математическая модель расписания в вузе 11
- 2.1.1 Обозначения 11
- 2.1.2 Переменные 13
- 2.1.3 Ограничения 13
- 2.1.4 Целевая функция 16
- 2.2 Методы решения поставленной задачи 17
- 2.2.1 Полностью целочисленный алгоритм 18
- 2.2.2 Прямой алгоритм целочисленного программирования 23
- 2.2.3 Техника получения начального допустимого базиса 28
- 2.3 Особенности практической реализации системы 33
- 2.3.1 Выбор модели 33
- 2.3.2 Описание входной информации 35
- 2.3.3 Разработка информационного обеспечения задачи 37
- 2.3.4 Особенности формирования ограничений математической модели задачи составления расписания 40
- 2.4 Результаты работы программы 41
- 2.5 Анализ полученных результатов 44
- Выводы 46
- Литература 47
- Приложение 1. Возможности программных продуктов систем составления расписаний. 49
- Приложение 2. Листинг программного модуля методов решения задачи автоматического составления расписания 59
Введение
расписание программный автоматический модель
Качество подготовки специалистов в вузах и особенно эффективность использования научно-педагогического потенциала зависят в определенной степени от уровня организации учебного процесса.
Одна из основных составляющих этого процесса - расписание занятий - регламентирует трудовой ритм, влияет на творческую отдачу преподавателей, поэтому его можно рассматривать как фактор оптимизации использования ограниченных трудовых ресурсов - преподавательского состава. Технологию же разработки расписания следует воспринимать не только как трудоемкий технический процесс, объект механизации и автоматизации с использованием ЭВМ, но и как акцию оптимального управления [10, 11]. Таким образом, это - проблема разработки оптимальных расписаний занятий в вузах с очевидным экономическим эффектом. Поскольку интересы участников учебного процесса многообразны, задача составления расписания - многокритериальная.
Актуальность этой задачи и сложность объекта, для которого сроится математическая модель, обуславливает необходимость серьезного математического исследования объекта для увеличения функциональных возможностей алгоритмов составления расписаний без значительного усложнения модели.
Целью данной работы является создание такой математической модели расписания в вузе, которая позволяла бы эффективно (в заданные сроки и с заданной степенью оптимальности) решать задачу автоматического составления расписания и обладала бы гибкостью (незначительных изменений в случае изменений входной информации) для адаптации системы в рамках конкретной практической задачи.
Для реализации указанной цели необходимо решение следующих задач:
- анализ существующего программного обеспечения по составлению расписания занятий и их развитие;
- выявление требований, которые предъявляются к программного обеспечения как к специализированному продукту, ориентированному на работу в компьютерной сети;
- разработка математической модели и практическая реализация системы автоматического составления расписания;
- анализ полученных результатов.
Задачу составления расписания не стоит рассматривать только как некую программу, реализующую функцию механического распределения занятий в начале семестра, на которой ее (программы) использование и заканчивается. Экономический эффект от более эффективного использования трудовых ресурсов может быть достигнут только в результате кропотливой работы по управлению этими трудовыми ресурсами [5]. Расписание здесь является лишь инструментом такого управления, и для наиболее полного его использования необходимо, чтобы программа сочетала в себе не только средства для составления оптимального расписания, но и средства для поддержания его оптимальности в случае изменения некоторых входных данных, которые на момент составления расписания считались постоянными. Кроме этого оптимальное управление такой сложной системой невозможно без накопления некоей статистической информации о процессах, происходящих в системе[14]. Потому сама задача составления оптимального расписания является лишь частью сложной системы управления учебным процессом.
1. ОПИСАНИЕ ТЕХНОЛОГИЧЕСКОЙ ОБЛАСТИ
1.1 Формулировка задачи составления расписания
1.1.1 Общая формулировка задачи составления расписаний
В наиболее общей формулировке задача составления расписания состоит в следующем. С помощью некоторого множества ресурсов или обслуживающих устройств должна быть выполнена некоторая фиксированная система заданий. Цель которых заключается в том, чтобы при заданных свойствах заданий и ресурсов и наложенных на них ограничениях найти эффективный алгоритм упорядочивания заданий, оптимизирующих или стремящийся оптимизировать требуемую меру эффективности решения поставленной задачи. В качестве основных мер эффективности изучаются длина расписания и среднее время пребывания заданий в системе. Модели этих задач являются детерминированными в том плане, что вся информация, на основе которой принимаются решения об упорядочивании, известны заранее [2].
1.1.2 Формулировка задачи составления расписания в применении к расписанию учебных занятий
Общая теория расписаний предполагает, что все обслуживающие устройства (или процессоры) не могут выполнять в данный момент времени более одного задания, что для расписания учебных занятий не является достаточным, если в качестве процессора при распределении заданий принять учебную аудиторию. Так в некоторых случаях в одной аудитории могут проводиться занятия с более чем одной группой одновременно, например общие лекции для нескольких потоков.
Поэтому при переносе общей теории расписаний на расписание учебных занятий были сделаны следующие допущения:
- все процессоры (т.е. в случае учебного расписания - аудитории) имеют вместимость - некоторое число C ? 1. Вместимость процессора определяет количество заданий, которые он может одновременно "обрабатывать" в данный момент времени (в отношении неединичности процессоров было бы интересным рассмотреть вариант, когда в качестве процессора выступает не аудитория, а преподаватель, а в качестве задания - поток из одной или более учебных групп, с которыми он работает);
- в качестве множества заданий для распределения выступают учебные занятия преподавателя с учебными группами;
- модель времени в системе является дискретной; все распределение предполагается периодически повторяющимся на протяжении некоторого временного интервала;
- все задания выполняются за одинаковое время, которое принимается за единицу дискретизации временного интервала;
- задания имеют принадлежность к объектам, в качестве которых выступают учебные группы и преподаватели.
В итоге, формулировка задачи составления расписания учебных занятий звучит следующим образом: "Для заданного набора учебных аудиторий (в данном случае под учебной аудиторией понимается широкий круг помещений, в которых проводятся учебные занятия (от компьютерной аудитории до спортивного зала)) и заданного набора временных интервалов (т.е. по сути, уроков или учебных пар) построить такое распределение учебных занятий для всех объектов (учителя и учебные группы), для которого выбранный критерий оптимальности является наилучшим" [1].
1.2 Анализ существующего программного обеспечения
На данный момент времени сектор рынка программного обеспечения систем составления расписания занятий представлен большим количеством различных программных продуктов. В таблице 1. представлены лишь некоторые из них.
Системы составления расписания занятий
Таблица 1
Название |
Краткая характеристика |
|
«ДЕКАНАТ» версии 3.6. |
программа для составления расписания в ВУЗах .Windows, ВУЗы |
|
«Ректор 3» «Ректор-Школа» «Ректор-Колледж» «Ректор-ВУЗ» |
- программа для составления расписания в средних школах. - программа для составления расписания в средних школах с профильным обучением. - программа для составления расписания в средних специальных учебных заведениях. - программа для составления расписания в ВУЗах. Операционная система - MS Windows XP или MS Vista. |
|
"АВТОР-2+" |
Windows, программа для составления расписания в средних школах и ВУЗах |
|
"Расписание" ver 4.0 Москва - ЛИнТех |
Windows только школы и колледжи; до 3 недель без дат; до 100 классов. |
|
"МЕТОДИСТ" |
Windows, программа для составления расписания в средних школах и ВУЗах |
|
"Мечта" г.С-Петербург |
Windows, одна неделя, только школы |
|
Без названия "АСИКУРАЦИОНЕ ИНТЕРНАЦИОНАЛЕ" (Кокотов С. П.) г.Благовещенск |
Windows, школы, ВУЗы |
Возможности и описание на мой взгляд наиболее популярных на российском рынке программных продуктов приведены в приложении 1.
В силу объективных причин система составления расписания в вузе (имеется в виду крупный государственный вуз) обязательно должна реализовывать ряд основных функций:
- учет пожеланий преподавателей;
- закрепление обязательных аудиторий;
- указание желательных аудиторий;
- учет перехода между корпусами;
- объединение групп в потоки по любой совокупности дисциплин;
- разбиение на подгруппы;
- после составления расписания при необходимости осуществлять замену преподавателей или изменять время проведения занятия [ 6 ].
Кроме этого существуют еще и специфические для каждого вуза требования к функциональным возможностям программного продукта.
Из приведенного списка пожалуй только программа "Методист" более или менее соответствует требуемой функциональности программного продукта составления расписания в вузе. Такое положение вещей легко объясняется тем, что школьное образование на сегодняшний день более "стандартизовано" (в смысле организации учебного процесса), чем вузовское. Такая стандартизация ведет к большому объему потенциального рынка продаж программного обеспечения и окупаемости разработки путем продажи большого числа копий продукта по сравнительно низкой цене.
В случае вузов спрос на системы составления расписаний пожалуй даже больше, чем для школ, но дело осложняется большой спецификой организации учебного процесса в каждом отдельно взятом вузе. Создать унифицированное программное обеспечение не представляется возможным, а стоимость создания специализированного продукта у сторонних разработчиков оказывается неоправданно велика. Кроме того, обязательным условием является наличие "устоявшегося" расписания, что предполагает наличие возможности осуществлять замену преподавателей или время проведения занятий. Пока ни один программный продукт не позволяет достаточно просто этого делать (хотя некоторые возможности и есть в "Методисте", " Ректоре").
1.3 Постановка задачи
Целью данной работы было создание такой математической модели расписания в вузе (161 ВОЕННОЙ ШКОЛЕ ТЕХНИКОВ), которая позволяла бы эффективно (в заданные сроки и с заданной степенью оптимальности) решать задачу автоматического составления расписания и обладала бы гибкостью (незначительных изменений в случае изменений входной информации) для адаптации системы в рамках конкретной практической задачи. Для некоторого упрощения задачи на начальном этапе проектирования были сделаны некоторые допущения:
- расписание составляется с учетом распорядка дня и календарного планирования части;
- все пары кроме плановых мероприятий, проводятся в одном корпусе, а вождения на автодроме, то есть все перерывы между парами одинаковые;
- все коэффициенты модели и искомые переменные целочисленны;
Поставленная задача должна решаться одним из универсальных (не зависящих от целочисленных значений коэффициентов) методов целочисленного линейного программирования.
2. Разработка математической модели и практическая реализация системы автоматического составления расписания
2.1 Математическая модель расписания в вузе
Построим математическую модель расписания в вузе в терминах линейного программирования [ 4 ]. Введем обозначения и определим переменные и ограничения [ 13 ].
2.1.1 Обозначения
ГРУППЫ
В вузе имеется N учебных групп, объединенных в R потоков; r - номер потока, r = 1, ..., R, kr - номер учебной группы в потоке r, kr = 1, …, Gr.
Разбиение на групп на потоки осуществляется исходя из принципов:
1. Использование двумя группами одного и того же аудиторного фонда для своих лекций автоматически предполагает помещение их в 1 поток (предполагается, что все лекции учебных групп проходят вместе).
2. Группа(или ее часть), как единица учебного процесса в вузе, может входить в разные потоки, но только по одному разу в каждый из них.
3. Количество потоков не лимитируется.
ЗАНЯТИЯ
Занятия проводятся в рабочие дни в полуторочасовые интервалы, которые будем называть парами.
Обозначим:
t - номер рабочего дня недели, t Є Tkr, где
Tkr - множество номеров рабочих дней для группы kr;
j - номер пары, j = 1 ,…, J;
J - общее количество пар.
С каждой учебной группой kr потока r в течение недели, согласно учебному плану, проводится Wkr занятий, из которых Sr лекционных и Qkr семинарских (лабораторных или практических). Обозначим:
sr - номер дисциплины в списке лекционных занятий для потока r, sr = 1 ,…,Sr;
qkr - номер дисциплины в списке практических занятий для группы kr, qkr = 1 ,…, Qkr.
Предполагается, что лекции проводятся у всех групп потока одновременно и в одной аудитории. Тогда, если по какой-то дисциплине в течение недели проводится более одного занятия, эта дисциплина упоминается в списке лекций или практических занятий столько раз, сколько их предусматривается учебным планом для каждого потока или группы.
ПРЕПОДАВАТЕЛИ
Пусть p - номер (имя) преподавателя, p = 1 ,…, P. Введем в рассмотрение булевы значения и :
=
Учебная нагрузка преподавателей планируется до составления расписания занятий, вследствие чего на данном этапе величины и можно считать заданными. Для каждого преподавателя p, p = 1 ,…,P, задана также его аудиторная нагрузка - Np часов в неделю.
АУДИТОРНЫЙ ФОНД
Занятия каждого потока могут проводиться только в определенных аудиториях (например, практические занятия по информатике могут проводится только в дисплейных классах). Пусть:
{A1r} - множество аудиторий для лекций на потоке r;
{A2r} - множество аудиторий для практических занятий на потоке r;
A1r - число элементов множества {A1r};
A2r - число элементов множества {A2r};
A1r + A2r - число аудиторий объединения множеств {A1r}?{A2r}.
Аудиторный фонд определяется до начала составления расписания, поэтому множества можно считать заданными.
2.1.2 Переменные
Задача составления расписания заключается в определении для каждой лекции (на потоке) и практического занятия (в группе) дня недели и пары в этот день с учетом выполнения конструируемых ниже ограничений и минимизации некоторой целевой функции.
Введем следующие искомые булевы переменные:
=
=
В случае составления расписания для групп вечерней формы обучения J=2. Обобщение модели на все формы обучения см. [1], стр. 669.
2.1.3 Ограничения
Для каждой группы kr должны выполняться все виды аудиторной работы в течение недели:
В любой день t на каждой паре j для каждой группы kr может проводиться не более одного занятия:
Каждые лекция sr и практическое занятие qkr соответственно для всех потоков r и всех групп kr могут проводиться не более одного раза в любой день t:
Если переменные и увязывают все виды занятий с временем их проведения, то произведения и связывают время проведения с именем преподавателя.
В каждый день t и в каждой паре j преподаватель p может вести не более одного занятия по одной дисциплине на одном потоке или в одной группе:
Каждый преподаватель p в течение недели должен провести аудиторные занятия:
Наконец, в каждый день на каждой паре число лекций и практических занятий не должно превышать имеющийся в вузе аудиторный фонд:
Кроме того, для всех совокупностей пересекающихся множеств {A1r} и {A2r} должны выполняться условия:
Представленными соотношениями исчерпываются безусловные ограничения, с которыми всегда считаются при составлении расписания. Могут, однако быть и специфические условия, прежде всего проведение отдельных видов работы по “верхней” или по “нижней” неделе (т.е. один академический час в неделю). Не исключены и другие специальные условия, но для упрощения модели они не рассматривались.
2.1.4 Целевая функция
Чтобы полноценно вести научную, учебно-методическую работу, готовиться к занятиям, преподаватель вуза должен иметь свободное время. Это условие недостаточное, но необходимое. Очевидно, что свободным временем он должен располагать не в “рваном” режиме, каковым, например, являются “окна” между занятиями со студентами, а по возможности в полностью свободные рабочие дни. Этому эквивалентна максимизация аудиторной нагрузки преподавателей в те дни, когда они ее имеют ( 5 ). Однако при этом претензии на свободное время у преподавателей неравны, так как у них разный творческий потенциал. Поэтому необходимо ввести весовые коэффициенты, посредством которых должен учитываться соответствующий статус преподавателя - его ученые степени и звание, занимаемая должность, научно-общественная активность и т.п. В некоторых случаях можно на основании экспертных оценок использовать индивидуальные весовые коэффициенты, учитывающие другие факторы.
Итак, выберем критерий качества составления расписания занятий в виде максимизации взвешенного числа свободных от аудиторной работы дней для всех преподавателей, что при условии фиксированной длины рабочей недели эквивалентно максимальному совокупному уплотнению аудиторной нагрузки.
Рассмотрим выражение для величины аудиторной нагрузки в день t преподавателя p:
Вводятся ограничения вида:
где M - произвольное положительное достаточно большое число; - искомая булева переменная.
Из (10) вытекает, что если , то = 1, и если , то = 0.
С учетом указанного выше содержательного смысла критерия оптимизации в дополнительных ограничениях (10), а также вводя весовые коэффициенты статуса преподавателя , получаем искомый критерий оптимальности:
Введенная целевая функция не является единственно возможной. Введение других целевых функций не меняет ограничений математической модели и методов решения задачи, но может существенно повлиять на результаты вычислений.
2.2 Методы решения поставленной задачи
Поставленная в предыдущем пункте задача максимизации линейной целевой функции при заданной системе ограничений является задачей линейного целочисленного булева программирования, поскольку все коэффициенты ограничений целочисленные в силу дискретности исходных данных задачи; кроме этого искомые переменные математической модели могут принимать только два значения [ 16 ]. На данный момент времени существует несколько возможных методов решения такого рода задач.
В [4] - [8] описаны методы упорядоченной индексации и модифицированных пометок, основанные на лагранжевой декомпозиции исходной модели на ряд однострочных задач, решаемых соответственно методами упорядочивающей индексации или модифицированных пометок. К сожалению количество операций каждого из методов не допускает полиномиальной оценки; кроме того, размерность таблицы наборов (промежуточных значений) методов резко возрастает при увеличении размерности решаемой задачи, что недопустимо в нашем случае. Возможно, изменение алгоритма декомпозиции под конкретную математическую модель позволит уменьшить размерность таблиц, но пока такого алгоритма не существует.
В связи с этим в качестве методов решения были выбраны описанные в [9] модификации симплекс-метода для случая задачи целочисленного линейного программирования. В общем случае количество операций симплекс-метода не допускает полиномиальной оценки (был даже показан класс задач, для которых количество операций составляет O(en)), но для случая нашей задачи среднее число операций допускает полиномиальную оценку: O(n3m1/(n-1)) (n - количество переменных; m - количество ограничений).
2.2.1 Полностью целочисленный алгоритм
Этот алгоритм назван полностью целочисленным, потому что если исходная таблица состоит из целочисленных элементов, то все таблицы, получающиеся в процессе работы алгоритма, содержат только целочисленные элементы. Подобно двойственному симплекс-методу, алгоритм начинает работать с двойственно допустимой таблицы. Если ai0 (i = 1 ,…, n+m; ai0 - коэффициенты целевой функции) - неотрицательные целые, то задача решена. Если для какой-нибудь строки ai0<0, то составляется новое уравнение и записывается внизу таблицы. После этого используется двойственный симплекс-метод. Все элементы дополнительной строки должны быть целыми числами, а ведущий элемент равен -1. Введенная таким образом ведущая строка сохранит таблицу целочисленной.
Пусть задана задача целочисленного линейного программирования:
максимизировать
при условиях
Условия (12) могут быть записаны как
Предположим, что для t=0 (т.е. для исходной таблицы) все aij - целые и столбцы (j = 1 ,…, n) - лексикографически положительны. Тогда все столбцы на протяжении вычислений остаются лексикографически положительными.
Прежде чем изложить способ получения дополнительного ограничения из производящей строки, введем новое представление чисел. Пусть [x] обозначает наибольшее целое число, не превосходящее x.
Для любого числа y (положительного или отрицательного) и положительного можно записать:
где (ry - неотрицательный остаток от деления нацело y на ). В частности, . Поэтому если , то и r = 1. Если , то и r = 0.
Вводимое дополнительное неравенство должно выполняться при любом целом решении задачи (12). Рассмотрим некоторое уравнение в t - таблице (опуская индекс строки) с a0<0:
где x - соответствующая компонента вектора , а - текущие небазисные переменные. Можно выразить x, a0 и aj, используя введенное выше представление (14):
Подставив выражения (16) и (17) в (15) и переставив члены, получим:
Поскольку , и на переменные x и наложено требование неотрицательности, левая часть уравнения (18) всегда неотрицательна. Рассмотрим выражение в правой части, заключенное в фигурные скобки. Коэффициенты в этом выражении представляют собой целые числа, а переменные подчинены требованию целочисленности. Поэтому все выражение в скобках должно быть целым. Обозначим его через s, т.е.:
.
Целочисленная слабая переменная s является неотрицательной. Действительно, если бы s было отрицательным, т.е. принимало бы значения -1, -2, …, то умножение на сделало бы всю правую часть уравнения (18) отрицательной, в то время как левая часть неотрицательна.
Рассмотрим два случая и . Для
и .
Подставляя в уравнение (19) выражение для x из (15), получим:
Полученное уравнение есть не что иное как отсечение Гомори. Для имеем и уравнение (19) приобретает вид:
Уравнение (21) должно выполняться для любого целочисленного решения задачи (12). Заметим, что если a0<0, то в уравнении (21). Потому уравнение (21) может использоваться в качестве ведущей строки в симплекс-методе. В частности, всегда можно выбрать достаточно большим, так чтобы ведущий элемент в строке (21) стал равным -1, что позволит сохранить целочисленность таблицы. Выбор соответствующего будет влиять на скорость сходимости алгоритма. Прежде всего опишем сам алгоритм. В качестве начального необходимо взять двойственно допустимое решение, которое можно получить добавлением ограничения xn+m+1=M - x1 - - … - xn 0, где M - достаточно большая константа, и проведением одной итерации с добавленной строкой и с лексикографически минимальным столбцом, взятыми в качестве ведущих. Алгоритм состоит из следующих шагов:
Шаг 0. Начать с двойственно допустимой матрицы A0 в уравнении (13), элементы которой - целые числа (матрица A0 может содержать и нецелые элементы, об этом см. [2], стр. 306).
Шаг 1. Среди строк с ai0<0 (i=1, …, n+m) выбрать строку с наименьшим значением i; эта строка станет производящей. (Если ai00 (i=1, …, n+m), то задача решена.)
Шаг 2. Выбрать (правило выбора будет описано дальше) и написать внизу таблицы дополнительную строку
Эта строка выбирается в качестве ведущей.
Шаг 3. Провести шаг двойственного симплекс-метода, вычеркнуть дополнительную строку и вернуться к шагу 1.
Доказательство конечности алгоритма [9, стр. 303-304].
Правило выбора формулируется следующим образом.
Шаг 0. Пусть строка с номером v является производящей.
Шаг 1. Пусть - лексикографически минимальный столбец среди столбцов с avj<0.
Шаг 2. Для каждого avj<0 пусть - наибольшее целое, такое, что (лексикографически меньше).
Шаг 3. Пусть , а (строка v - производящая). Тогда
.
Шаг 4. Положить для avj<0.
Правило выбора , описанное выше, позволяет сделать ведущий элемент равным -1, при этом сохраняется двойственная допустимость таблицы и в то же время нулевой столбец будет максимально лексикографически уменьшаться.
Подробнее об алгоритме можно прочитать в [9, стр. 300].
2.2.2 Прямой алгоритм целочисленного программирования
Термин “прямой”, примененный к алгоритму целочисленного программирования, обозначает метод, который приводит к оптимальному решению посредством получения последовательно “улучшаемых” решений. Каждой из этих решений допустимо в том смысле, что оно удовлетворяет как линейным ограничениям, так и условию целочисленности. Одним из вероятных достоинств алгоритма является возможность прервать вычисления, до того как получено оптимальное решение, и использовать наилучшее из полученных решений как приближенное. Кроме того, можно использовать прямой алгоритм в соединении с двойственными алгоритмами, чтобы получать различные составные алгоритмы, которые могут переходить от фазы, дающей двойственно допустимые решения, к фазе, дающей прямо допустимые решения.
Естественным прецедентом для прямого алгоритма является полностью целочисленный алгоритм Гомори, поскольку в процессе этого алгоритма получается последовательность двойственно допустимых целочисленных решений. Следует напомнить, что полностью целочисленный алгоритм Гомори представляет собой модификацию двойственного симплекс-метода. Основное отличие этого алгоритма состоит в том, что в качестве ведущей строки используется отсечение Гомори с ведущим элементом, равным -1. Это отсечение получается из производящей строки, которая определяется как одна из возможных ведущих строк в двойственном симплекс-методе. Использование такого отсечения в качестве ведущей строки сохранит после итерации двойственную допустимость и целочисленность таблицы.
Оказывается, можно аналогично модифицировать симплекс-метод таким образом, чтобы получить алгоритм, который сохраняет прямую допустимость и целочисленность таблиц. Для описания вычислительной процедуры рассмотрим следующую задачу целочисленного программирования:
максимизировать
при условиях
,
(целые) (k=1,…,n),
где a0j, aij и ai0 - целые числа и ai00.
Предположим, что столбец выбран в качестве ведущего и строка v - ведущая строка в итерации симплекс-метода, т.е. для всех строк I, в которых ais>0. Прежде чем провести процедуру исключения Гаусса в симплекс-методе, добавим к таблице отсечение Гомори, полученное из строки v:
где J - множество индексов небазисных переменных в (22), sk - новая (базисная) слабая переменная и - неопределенная (временно) положительная константа.
Заметим, что если положить = avs, отсечение (23) будет обладать двумя важными свойствами. Во-первых,
Это означает, что прямая допустимость таблицы сохраниться, если использовать отсечение (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.
Доказательство конечности алгоритма [9, стр. 346-353].
Поскольку выбор производящей строки является задачей нетривиальной, по-видимому, должно существовать несколько строк, которые могут служить в качестве производящих. В предварительных рассуждениях в качестве производящей строки использовалась ведущая строка симплекс-метода. Эта строка всегда дает отсечение, которое является ведущей строкой с ведущим элементом, равным единице. По-видимому, в таблице существуют и другие строки, из которых могут быть получены отсечения с такими же свойствами. Допустим, что отсечение получается по формуле:
Строка v может стать производящей тогда и только тогда, когда
где определяется из условия
Определим множество 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.
2.2.3 Техника получения начального допустимого базиса
Решение каждым из приведенных выше методов может производиться только в том случае, если задача линейного программирования является или прямо, или двойственно допустимой. Такая допустимость означает наличие начального допустимого базиса в исходной задаче. Если задача допустима и прямо, и двойственно, то полученное решение - оптимально. В большинстве случаев после постановки задачи оказывается, что она не допустима ни прямо, ни двойственно. Поэтому приведем алгоритм получения начального допустимого базиса.
Пусть задача линейного программирования записана в канонической форме:
минимизировать
при условиях
Все bi можно сделать неотрицательными, умножив, если надо, соответствующее уравнение на -1. Тогда можно добавить в каждое уравнение искусственную переменную (искусственные переменные должны быть неотрицательными) таким образом, чтобы из искусственных переменных образовать начальный базис:
Искусственные переменные можно получить из слабых переменных, используемых для превращения неравенств в уравнения. Действительно, если исходные ограничения задачи линейного программирования заданы в виде неравенств:
то, добавив слабую переменную в каждое неравенство, получим:
Если bi0, то si можно использовать в качестве начальных базисных переменных.
Различие между искусственными переменными и слабыми переменными si состоит в следующем. В оптимальном решении задачи все искусственные переменные должны быть равными нулю, поскольку в исходной задаче таких переменных нет. С другой стороны, вполне возможно, что в оптимальном решении слабые переменные будут иметь положительные значения. Для того, чтобы искусственные переменные стали равными нулю, можно представить целевую функцию следующим образом:
где Mi - достаточно большие положительные числа. Идея метода соответствует тому, что искусственным переменным придаются заведомо большие цены. Такой способ приводит к нулевым значениям искусственных переменных в оптимальном решении.
Существует и другой способ получения начального допустимого базиса. В этом способе, как и в первом, в качестве начальных базисных переменных используются искусственные переменные. Рассматривается новая целевая функция , представляющая собой сумму искусственных переменных. Требуется минимизировать , используя z - уравнение как одно из ограничений. Если исходная система уравнений имеет допустимое решение, то все искусственные переменные должны стать равными нулю. Следовательно, минимальное значение должно стать равным нулю. Если , то исходная система уравнений не имеет допустимых решений. Если , то можно опустить целевую функцию и использовать оптимальный базис -формы в качестве начального допустимого базиса для минимизации z. В литературе такой способ называется двухфазовым симплекс-методом. На первой фазе метода находится допустимый базис путем минимизации , на второй - минимизируется z и получается оптимальный базис.
Рассмотри в качестве примера следующую задачу линейного программирования:
минимизировать
при условиях
где все bi неотрицательны.
Если ввести искусственные переменные и новую целевую функцию , то получим задачу:
минимизировать
,
при условиях
-z
Если вычесть все уравнения, содержащие bi, из -формы, получим:
-z
где
Система (26) является диагональной относительно Первая фаза симплекс-метода состоит в минимизации при условиях (26). На знак z ограничений не накладывается. В процессе вычислений, как только искусственная переменная становится небазисной и ее коэффициент в -форме положителен, сама переменная и соответствующий ей вектор-столбец из дальнейших вычислений исключаются.
2.3 Особенности практической реализации системы
На практике не очень удобно работать с информацией в том виде, в котором она определяется в математической модели. Поэтому прежде всего определимся со способом организации данных или моделью данных.
2.3.1 Выбор модели
Модель данных - это совокупность соглашений о способах и средствах формализованного описания объектов и их связей, имеющих отношение к автоматизации процессов системы. Вид модели и используемые в ней типы структур данных отражают концепцию организации и обработки данных, используемую в СУБД, поддерживающей модель, или в языке системы программирования, на котором создается прикладная программа обработки данных [ 8 ].
В рамках решения поставленной задачи необходимо создание такой модели данных, при которой объем вспомогательной информации был бы минимальным, существовала принципиальная возможность многопользовательского доступа к данным и был бы обеспечен высокий уровень защиты данных.
В настоящее время существует три основных подхода к формированию модели данных: иерархический, сетевой и реляционный.
Иерархическая база.
Иерархическая база данных состоит из упорядоченного набора деревьев; более точно, из упорядоченного набора нескольких экземпляров одного типа дерева. Тип дерева состоит из одного "корневого" типа записи и упорядоченного набора из нуля или более типов поддеревьев (каждое из которых является некоторым типом дерева). Тип дерева в целом представляет собой иерархически организованный набор типов записи.
Автоматически поддерживается целостность ссылок между предками и потомками. Основное правило: никакой потомок не может существовать без своего родителя. Заметим, что аналогичное поддержание целостности по ссылкам между записями, не входящими в одну иерархию, не поддерживается.
Сетевой способ организации.
Сетевой подход к организации данных является расширением иерархического. В иерархических структурах запись-потомок должна иметь в точности одного предка; в сетевой структуре данных потомок может иметь любое число предков.
Сетевая база данных состоит из набора записей и набора связей между этими записями, а если говорить более точно, из набора экземпляров каждого типа из заданного в схеме базы данных набора типов записи и набора экземпляров каждого типа из заданного набора типов связи.
Тип связи определяется для двух типов записи: предка и потомка. Экземпляр типа связи состоит из одного экземпляра типа записи предка и упорядоченного набора экземпляров типа записи потомка. Для данного типа связи L с типом записи предка P и типом записи потомка C должны выполняться следующие два условия:
1. Каждый экземпляр типа P является предком только в одном экземпляре L;
2. Каждый экземпляр C является потомком не более, чем в одном экземпляре L.
Реляционный способ организации
Основными недостатками иерархичекого и сетевого типов моделей данных являются:
Слишком сложно пользоваться;
Фактически необходимы знания о физической организации;
Прикладные системы зависят от этой организации;
Их логика перегружена деталями организации доступа к БД.
Наиболее распространенная трактовка реляционной модели данных, по-видимому, принадлежит Дейту, который воспроизводит ее (с различными уточнениями) практически во всех своих книгах. Согласно Дейту [15] реляционная модель состоит из трех частей, описывающих разные аспекты реляционного подхода: структурной части, манипуляционной части и целостной части.
В структурной части модели фиксируется, что единственной структурой данных, используемой в реляционных БД, является нормализованное n-арное отношение.
В манипуляционной части модели утверждаются два фундаментальных механизма манипулирования реляционными БД - реляционная алгебра и реляционное исчисление. Первый механизм базируется в основном на классической теории множеств (с некоторыми уточнениями), а второй - на классическом логическом аппарате исчисления предикатов первого порядка. Основной функцией манипуляционной части реляционной модели является обеспечение меры реляционности любого конкретного языка реляционных БД: язык называется реляционным, если он обладает не меньшей выразительностью и мощностью, чем реляционная алгебра или реляционное исчисление.
Наконец, в целостной части реляционной модели данных фиксируются два базовых требования целостности, которые должны поддерживаться в любой реляционной СУБД. Первое требование называется требованием целостности сущностей. Второе требование называется требованием целостности по ссылкам.
2.3.2 Описание входной информации
Вся необходимая для решения поставленной задачи информация задается до начала итераций методов решения задачи составления расписания. Для упрощения считается, что заданная информация является постоянной на всем протяжении периода, для которого составляется расписание.
Не теряя определенной степени общности поставленной задачи, можно определить некую совокупность входных данных, необходимых для формирования ограничений и решения задачи, и в то же время общих для всех разновидностей практических реализаций системы. В силу специфики поставленной задачи (возможность сравнительно легкой адаптации математической модели для случая практической реализации в рамках конкретного вуза) формы документов входной информации не разрабатывались. Реквизиты входной информации описаны в табл.2.
Таблица 2. Описание реквизитов входной информации
Наименование реквизитов |
Характеристика реквизитов |
|||
входных документов |
Тип |
Макс. длина |
Точность |
|
Фамилия, имя, отчество преподавателя;Контактный телефон преподавателя;Ученая степень;Ученое звание;Кафедра;Название группы;Численный состав группы;Название читаемого курса;Количество аудиторных часов;Номера аудиторий;Информация об аудиториях;Название предмета, читаемого преподавателем;Номер группы, где читается предмет;Информация об аудиториях, где читается предмет. |
текстов.текстов.текстов.текстов.текстов.текстов.числов.текстов.числов.числов.текстов.текстов.числов.текстов. |
1001050505050250235050350 |
Кроме этих данных для математической модели необходимо наличие еще некоторых дополнительных данных, которые могут быть получены после анализа входной информации программным путем.
2.3.3 Разработка информационного обеспечения задачи
Произведем анализ исходной информации с целью определения состава и структуры информации для последующей формализации и построения информационно-логической модели данных (ИЛМ). Приведенная выше математическая модель, а также дополнительные сведения из описания предметной области позволяют определить роль реквизитов во взаимосвязанной информации, содержащейся в документе. На основе такого анализа установим функциональные зависимости реквизитов в соответствии с рекомендациями и требованиями нормализации данных, после чего проведем саму нормализацию. Цель нормализации состоит в том, чтобы уменьшить (но необязательно устранить) избыточность данных. Однако иногда некоторая избыточность данных создается намеренно, чтобы повысить эффективность работы программы. Дадим определение трех форм нормализации базы данных.
Таблица находится в первой нормальной форме (1NF), если она имеет первичный ключ, все атрибуты представляют собой простые типы данных и отсутствуют повторяющиеся атрибуты. Чтобы соответствовать 1NF, домены атрибутов должны быть атомарными значениями и не должно быть повторяющихся групп атрибутов. Все повторяющиеся группы атрибутов должны быть перенесены в новую таблицу.
Таблица находится во второй нормальной форме (2NF) тогда, когда она находится в первой нормальной форме и каждый неключевой атрибут полностью функционально зависит от первичного ключа (т.е. в 2NF каждый неключевой атрибут должен полностью зависеть от полей первичного ключа).
Таблица находится в третьей нормальной форме (3NF), если она находится в 2NF и не содержит транзитивных зависимостей. Транзитивные зависимости - это функциональные зависимости между неключевыми атрибутами. Любой неключевой атрибут, который функционально зависит от другого неключевого атрибута той же таблицы, создает транзитивную зависимость и должен быть перемещен в другую таблицу.
Получающиеся функциональные зависимости довольно тривиальны и очевидно вытекают из математической модели, поэтому в дальнейшем описании они не приводятся. Также в дальнейшем изложении опускаются промежуточные степени нормализации. Поэтому приведем лишь окончательную инфологическую модель базы данных (см. рис. 1.).
Рис.1. Инфологическая модель базы данных задачи составления расписания занятий
2.3.4 Особенности формирования ограничений математической модели задачи составления расписания
Составление ограничений (1) - (7) математической модели задачи составления расписания является достаточно тривиальной задачей, решаемой с помощью несложных SQL - запросов и не требующей предварительного анализа входной информации. Поэтому подробнее лишь остановимся на ограничениях вида (8).
Заметим, что в математической модели системы читаемый предмет “привязывается” не к определенной аудитории проведения, а к некоторому множеству аудиторий. Расстановка конкретных номеров аудиторий производится уже после решения поставленной задачи. Ограничения вида (8) имеют смысл только тогда, когда множества аудиторий пересекаются. В математической модели системы предлагается учитывать все уникальные пересекающиеся пары в виде ограничений. Количество этих пересечений может быть велико, что может привести к большому числу дополнительных ограничений, отрицательно влияющих на скорость работы алгоритмов оптимизации. Однако можно существенно уменьшить количество дополнительных ограничений.
Рассмотрим случай линейного расположения пересекающихся множеств (см. рис. 2.).
Рис.2. Линейно пересекающиеся множества
В случае такого расположения множеств аудиторий для проведения занятий общее число ограничений вида (8) будет n-1, где n - количество множеств. Описанное выше расположение пересекающихся множеств может быть названо линейным, так как при этом n пересекающихся множеств расположены как бы в линию. Можно рассмотреть случай, когда множества пересекают друг друга произвольным образом (см . рис. 3.).
Рис.3. Произвольно пересекающиеся множества
Число ограничений вида (8) в этом случае можно уменьшить, проведя формирование этих ограничений по аналогии со случаем линейного расположения множеств. Для этого необходимо предположить, что, например, множества B и D, пересекающиеся с A, являются одним множеством, определить область пересечения такого множества с множеством A, после чего провести те же самые действия с получившейся областью пересечения [9].
2.4 Результаты работы программы
При практической реализации системы особое внимание было уделено задаче написания “ядра” системы - методам решения задачи и процедурам формирования ограничений применительно к конкретному ВУЗу (161 ВШТ). Поскольку не ставилось задачи написать полнофункциональный коммерческий продукт, интерфейсная часть была написана для целей тестирования ядра и определения границ применимости алгоритмов, поэтому включает в себя минимум функциональных возможностей и не содержит модулей предобработки входных данных.
Ядро системы и интерфейсная часть были написаны на Visual Basic Методы решения и алгоритмы формирования ограничений написаны с использованием объектно-ориентированных технологий, что позволит в будущем легко инкапсулировать их в дальнейшие модификации системы, не нарушая целостности взаимодействия различных алгоритмов. Текст объектов методов решения задачи приведен в приложении 2. База данных была реализована на Access.
Исходные данные задачи заносятся в таблицы базы данных с помощью запросных форм. Одна из таких форм приведена на рис. 3.
Рис.4. Форма занесения исходных данных
Данных, получаемых в результате решения задачи, недостаточно для вывода расписания занятий непосредственно после решения задачи, поэтому был написан модуль постобработки данных. Конечное расписание занятий выводится в виде таблицы, пример которой представлен на см .рис. 4.
Рис. 5. Пример расписания занятий
Алгоритмы решения задачи были протестированы на различных выборках исходных данных. Тестирование производилось на ЭВМ с процессором Intel Pentium 1700 Мгц, ОЗУ 0,99 Гб; В качестве тестовых исходных данных были использованы реальные данные о группах, преподавателях и читаемых предметах военной школы техников на 2007/2008 учебные годы
2.5 Анализ полученных результатов
Анализируя полученные данные можно сделать некоторые выводы о функциональных возможностях алгоритмов решения и математической модели, их недостатках и областях применения.
Во-первых, использованная математическая модель содержит в себе “лишние” ограничения, существование которых обусловлено линейной целочисленной моделью, кроме этого каждому читаемому на потоке (поток может состоять и из одной группы) предмету ставится в соответствие 12 переменных, каждая из которых представляет из себя булеву переменную. Во-вторых, резко возрастает время решения задачи при увеличении входных данных. Это происходит из-за резкого увеличения количества переменных и ограничений в модели, в результате чего возрастает размерность массивов задачи. В-третьих, формализованная математически задача охватывает только задачу составления расписания со строго определенными перерывами между занятиями, без учета переходов между корпусами. Учет дополнительных требований увеличит количество ограничений задачи, что отрицательно повлияет только лишь на сложность алгоритмов решения.
Выводы
В ходе работы был проведен сравнительный анализ существующего программного обеспечения по составлению расписания занятий. Изучены требований, которые предъявляются к программного обеспечения как к специализированному продукту, ориентированному на работу в компьютерной сети. Построена математическая модель расписания в 161 военной школе техников для случая очной формы обучения без переходов между корпусами, выбраны методы решения поставленной задачи и разработана модель хранения исходных данных задачи. Модель хранения исходных данных, алгоритм математической формализации модели и методы решения были реализованы в виде программных модулей. Работа алгоритмов была протестирована на разнородных наборах исходных данных, в результате чего были определены возможности и области применения алгоритмов.
На основе результатов тестирования было установлено, что по работе алгоритмов решения задачи сильно зависят от объема входной информации и начального допустимого базисного решения, и поэтому значительно уступают эвристическим и декмпозиционным. Но в случае эвристического решения его (решения) оптимальность (или достижение глобального максимума) может быть доказана только полным перебором всех возможных вариантов (ясно, что в этом случае время работы алгоритма будет очень большим), поэтому итерации эвристических алгоритмов прекращаются по достижении некоего максимального (нельзя сказать, локального или глобального) значения. Решение такого алгоритма может быть близким к оптимальному, но не оптимальным. В этом случае для достижения глобального максимума можно использовать рассмотренный в работе способ решения, поскольку оптимум может быть достигнут за несколько итераций описанных методов решения.
...Подобные документы
Анализ существующих решений для составления расписания репетитора. Разработка архитектуры программного продукта. Выбор инструментальных средств. Проектирование реляционной базы данных. Определение методики тестирования. Реализация интерфейса пользователя.
дипломная работа [411,7 K], добавлен 22.03.2018Составление математической модели расписания в школе. Назначение и область применения программного продукта. Обоснование выбора инструментальных средств. Описание разработки, алгоритмов и методов решения, форматов данных и пользовательского интерфейса.
курсовая работа [1,6 M], добавлен 18.01.2012Основы проектирования информационно-прикладных систем. Подготовка макета приложения, интегрированного с БД. Сбор и загрузка исходных данных. Разработка и реализация математического алгоритма оптимизации составления расписания образовательного учреждения.
дипломная работа [3,4 M], добавлен 18.02.2017Проблема разработки математической модели сложной задачи. Построение алгоритма составления расписания занятий. Вероятность обнаружения хорошего варианта за ограниченное время. Множество всех множеств допустимых пар, поиск элементов, прогноз тупика.
реферат [42,1 K], добавлен 29.01.2010Реализация информационно-справочной системы расписания поездов в Microsoft Visual Studio 2008 на языке C#. Методика разработки и основное содержание данной программы, алгоритмы ее реализации. Требования к программе и оценка ее эффективности, листинг.
курсовая работа [5,0 M], добавлен 19.08.2012Практический опыт и проблемы внедрения систем автоматизированного составления расписания. Описание исходных данных для разработки функционала программы. Описание структуры разделов пользовательского интерфейса. Модуль проверок корректности расписания.
курсовая работа [3,6 M], добавлен 26.09.2014Программная реализация на языке ЛИСП расписания встреч участников соревнования с использованием круговой и олимпийской системы проведения соревнований. Математические и алгоритмические основы решения задачи. Функциональные модели и блок-схемы решения.
курсовая работа [1,0 M], добавлен 25.01.2010Логическое проектирование и разработка общей концепции системы. Составление расписания приема специалистов. Обработка заявок от клиентов. Построение информационно-логической модели системы. Шаблон для стандартных страниц. Данные для доступа к базе.
дипломная работа [4,8 M], добавлен 10.07.2015Особенности написания базы данных на языках программирования C++, применимой для расписания занятий в университете. Этапы работы: ввод новой записи, изменение, просмотр базы данных, поиск данных. Алгоритмы, используемые в процессе выполнения проекта.
практическая работа [16,6 K], добавлен 12.06.2010Сравнительный анализ технологий тестирования. Разработка программного модуля "Интеллектуальная обучающая система для широкого перечня курсов". Обоснование необходимости и важности этапа отладки в процессе разработки данного программного обеспечения.
дипломная работа [101,2 K], добавлен 17.06.2011Структурная диаграмма программного модуля. Разработка схемы программного модуля и пользовательского интерфейса. Реализация программного модуля: код программы; описание использованных операторов и функций. Вид пользовательской формы с заполненной матрицей.
курсовая работа [215,3 K], добавлен 01.09.2010Структура математической модели линейной задачи, алгоритм симплекс-метода. Разработка программы: выбор языка программирования, входные и выходные данные, пользовательский интерфейс. Описание программы по листингу, тестирование, инструкция по применению.
курсовая работа [1,2 M], добавлен 31.05.2013Реализация программного средства "Действия над матрицами". Разработка кода программного продукта на основе готовой спецификации на уровне модуля. Использование инструментальных средств на этапе отладки программного модуля. Выбор стратегии тестирования.
отчет по практике [296,1 K], добавлен 19.04.2015Анализ современных информационных технологий цехового планирования. Разработка математической модели объекта проектирования. Формализация модели бизнес-процесса АРМа цехового плановика. Детальная разработка модулей программного продукта планирования.
дипломная работа [4,9 M], добавлен 29.06.2012Разработка математической модели и создание программного средства для составления маршрута движения детали по участкам механической обработки механосборочного цеха. Структура и алгоритм работы программного продукта. Программные средства разработки.
курсовая работа [65,4 K], добавлен 21.11.2013Проектирование программного модуля: сбор исходных материалов; описание входных и выходных данных; выбор программного обеспечения. Описание типов данных и реализация интерфейса программы. Тестирование программного модуля и разработка справочной системы.
курсовая работа [81,7 K], добавлен 18.08.2014Метод решения математической модели на примере решения задач аналитической геометрии. Описание согласно заданному варианту методов решения задачи. Разработка математической модели на основе описанных методов. Параметры окружности минимального радиуса.
лабораторная работа [310,6 K], добавлен 13.02.2009Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015Разработка концептуальной модели базы данных. Реализация алгоритмов и разработка управляющей программы. Разработка структуры системы управления данными. Методика проведения и результаты тестирования. Функционирование разработанного программного модуля.
курсовая работа [550,5 K], добавлен 08.06.2023Разработка СУБД - программного модуля для систематизации, хранения и обработки сведений о работниках лаборатории. Технологический процесс машинной реализации задачи, составление алгоритма, описание переменных процедур и функций. Листинг программы.
курсовая работа [1,7 M], добавлен 11.01.2013