Xreferat.com » Рефераты по информатике и программированию » Разработка математической модели и ПО для задач составления расписания

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

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

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

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

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

при условиях

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

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

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

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

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

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

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

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

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

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

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

Если biРазработка математической модели и ПО для задач составления расписания0, то si можно использовать в качестве начальных базисных переменных.

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

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

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

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

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

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

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

при условиях

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

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

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

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

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

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

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

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

при условиях

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

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

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

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

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

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

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

(26)

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

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

Разработка математической модели и ПО для
    <div class=

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: