Как создать математическую модель в симплекс методе

Как создать математическую модель в симплекс методе

Это отсечение получается из производящей строки, которая определяется как одна из возможных ведущих строк в двойственном симплекс-методе. В основном математическую модель какого-либо объекта представляют в виде целевой функции или критерия оптимальности (порой без ограничений), которую необходимо максимизировать или. В результате запишем математическую модель задачи в каноническом виде: · В одной из ячеек создать формулу, определяющую целевую функцию. как и при СИМПЛЕКС методе. Актуальность проблемы.. Математические методы позволяют упорядочить систему экономической информации, выявлять недостатки в имеющейся информации и вырабатывать требования для подготовки новой информации или ее. Программирование и комп-ры, Разработка математической модели и ПО для задач составления.

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

Технологию же разработки расписания следует воспринимать не только как трудоемкий технический процесс, объект механизации и автоматизации с использованием ЭВМ, но и как акцию оптимального управления [10, 11]. Таким образом, это - проблема разработки оптимальных расписаний занятий в вузах с очевидным экономическим эффектом. Поскольку интересы участников учебного процесса многообразны, задача составления расписания - многокритериальная. Актуальность этой задачи и сложность объекта, для которого сроится математическая модель, обуславливает необходимость серьезного математического исследования объекта для увеличения функциональных возможностей алгоритмов составления расписаний без значительного усложнения модели.

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

Экономический эффект от более эффективного использования трудовых ресурсов может быть достигнут только в результате кропотливой работы по управлению этими трудовыми ресурсами [5]. Расписание здесь является лишь инструментом такого управления, и для наиболее полного его использования необходимо, чтобы программа сочетала в себе не только средства для составления оптимального расписания, но и средства для поддержания его оптимальности в случае изменения некоторых входных данных, которые на момент составления расписания считались постоянными.

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

Как создать математическую модель в симплекс методе

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

В качестве основных мер эффективности изучаются длина расписания и среднее время пребывания заданий в системе.

Как настроить р/станцию на тепловозе

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

Дипломная работа по предмету "Информатика, программирование"

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

Можно ли удержать по заявлению работника

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

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

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

Пока ни один программный продукт не позволяет достаточно просто этого делать хотя некоторые возможности и есть в "Методисте", " Ректоре". Целью данной работы было создание такой математической модели расписания в вузе ВОЕННОЙ ШКОЛЕ ТЕХНИКОВ , которая позволяла бы эффективно в заданные сроки и с заданной степенью оптимальности решать задачу автоматического составления расписания и обладала бы гибкостью незначительных изменений в случае изменений входной информации для адаптации системы в рамках конкретной практической задачи.

Постройте математическую модель

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

Построим математическую модель расписания в вузе в терминах линейного программирования [ 4 ]. Введем обозначения и определим переменные и ограничения [ 13 ]. Занятия каждого потока могут проводиться только в определенных аудиториях например, практические занятия по информатике могут проводится только в дисплейных классах.

Аудиторный фонд определяется до начала составления расписания, поэтому множества можно считать заданными.

Задача составления расписания заключается в определении для каждой лекции на потоке и практического занятия в группе дня недели и пары в этот день с учетом выполнения конструируемых ниже ограничений и минимизации некоторой целевой функции. Обобщение модели на все формы обучения см. Каждые лекция sr и практическое занятие qkr соответственно для всех потоков r и всех групп kr могут проводиться не более одного раза в любой день t:.

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

    Другие популярные дипломные работы:

    Представленными соотношениями исчерпываются безусловные ограничения, с которыми всегда считаются при составлении расписания. Не исключены и другие специальные условия, но для упрощения модели они не рассматривались. Чтобы полноценно вести научную, учебно-методическую работу, готовиться к занятиям, преподаватель вуза должен иметь свободное время.

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

    Как создать математическую модель в симплекс методе

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

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

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

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

    Поставленная в предыдущем пункте задача максимизации линейной целевой функции при заданной системе ограничений является задачей линейного целочисленного булева программирования, поскольку все коэффициенты ограничений целочисленные в силу дискретности исходных данных задачи; кроме этого искомые переменные математической модели могут принимать только два значения [ 16 ].

    Решение задачи с помощью Excel и симплекс-методом

    На данный момент времени существует несколько возможных методов решения такого рода задач. В [4] - [8] описаны методы упорядоченной индексации и модифицированных пометок, основанные на лагранжевой декомпозиции исходной модели на ряд однострочных задач, решаемых соответственно методами упорядочивающей индексации или модифицированных пометок. К сожалению количество операций каждого из методов не допускает полиномиальной оценки; кроме того, размерность таблицы наборов промежуточных значений методов резко возрастает при увеличении размерности решаемой задачи, что недопустимо в нашем случае.

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

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

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

    Тогда все столбцы на протяжении вычислений остаются лексикографически положительными.

    Разработка открытого урока Тема: «Лабораторная работа №3 Симплекс – метод

    Прежде чем изложить способ получения дополнительного ограничения из производящей строки, введем новое представление чисел. Пусть [x] обозначает наибольшее целое число, не превосходящее x. Для любого числа y положительного или отрицательного и положительного можно записать:. В частности,. Вводимое дополнительное неравенство должно выполняться при любом целом решении задачи Можно выразить x, a0 и aj, используя введенное выше представление 14 :.

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

    Можно ли расплачиваться моментальной картой сбербанка заграницей

    Целочисленная слабая переменная s является неотрицательной. Действительно, если бы s было отрицательным, то есть принимало бы значения -1, -2, …, то умножение на сделало бы всю правую часть уравнения 18 отрицательной, в то время как левая часть неотрицательна.

    Рассмотрим два случая и. Для и. Подставляя в уравнение 19 выражение для x из 15 , получим:. Полученное уравнение есть не что иное как отсечение Гомори.

    Для имеем и уравнение 19 приобретает вид:.

    Как создать математическую модель в симплекс методе

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

    Выбор соответствующего будет влиять на скорость сходимости алгоритма. Прежде всего опишем сам алгоритм. Алгоритм состоит из следующих шагов:. Шаг 0. Начать с двойственно допустимой матрицы A0 в уравнении 13 , элементы которой - целые числа матрица A0 может содержать и нецелые элементы, об этом см.

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

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