перейти к полному списку дипломных проектов
Ссылка на скачивания файла в формате .doc находится в конце странички
2.2.3. ТЕХНИКА ПОЛУЧЕНИЯ НАЧАЛЬНОГО ДОПУСТИМОГО БАЗИСА
Решение каждым из приведенных выше методов может производиться только в том случае, если задача линейного программирования является или прямо, или двойственно допустимой. Такая допустимость означает наличие начального допустимого базиса в исходной задаче. Если задача допустима и прямо, и двойственно, то полученное решение – оптимально. В большинстве случаев после постановки задачи оказывается, что она не допустима ни прямо, ни двойственно. Поэтому приведем алгоритм получения начального допустимого базиса.
Пусть задача линейного программирования записана в канонической форме:
минимизировать
при условиях
Все bi можно сделать неотрицательными, умножив, если надо, соответствующее уравнение на –1. Тогда можно добавить в каждое уравнение искусственную переменную (искусственные переменные должны быть неотрицательными) таким образом, чтобы из искусственных переменных образовать начальный базис:
Искусственные переменные можно получить из слабых переменных, используемых для превращения неравенств в уравнения. Действительно, если исходные ограничения задачи линейного программирования заданы в виде неравенств:
то, добавив слабую переменную в каждое неравенство, получим:
Если bi0, то si можно использовать в качестве начальных базисных переменных.
Различие между искусственными переменными и слабыми переменными si состоит в следующем. В оптимальном решении задачи все искусственные переменные должны быть равными нулю, поскольку в исходной задаче таких переменных нет. С другой стороны, вполне возможно, что в оптимальном решении слабые переменные будут иметь положительные значения. Для того, чтобы искусственные переменные стали равными нулю, можно представить целевую функцию следующим образом:
где Mi – достаточно большие положительные числа. Идея метода соответствует тому, что искусственным переменным придаются заведомо большие цены. Такой способ приводит к нулевым значениям искусственных переменных в оптимальном решении.
Существует и другой способ получения начального допустимого базиса. В этом способе, как и в первом, в качестве начальных базисных переменных используются искусственные переменные. Рассматривается новая целевая функция , представляющая собой сумму искусственных переменных. Требуется минимизировать , используя z – уравнение как одно из ограничений. Если исходная система уравнений имеет допустимое решение, то все искусственные переменные должны стать равными нулю. Следовательно, минимальное значение должно стать равным нулю. Если , то исходная система уравнений не имеет допустимых решений. Если , то можно опустить целевую функцию и использовать оптимальный базис -формы в качестве начального допустимого базиса для минимизации z. В литературе такой способ называется двухфазовым симплекс-методом. На первой фазе метода находится допустимый базис путем минимизации , на второй – минимизируется z и получается оптимальный базис.
Рассмотри в качестве примера следующую задачу линейного программирования:
минимизировать
при условиях
где все bi неотрицательны.
Если ввести искусственные переменные и новую целевую функцию , то получим задачу:
минимизировать
,
при условиях
-z
Если вычесть все уравнения, содержащие bi, из -формы, получим:
-z
где Система (26) является диагональной относительно Первая фаза симплекс-метода состоит в минимизации при условиях (26). На знак z ограничений не накладывается. В процессе вычислений, как только искусственная переменная становится небазисной и ее коэффициент в -форме положителен, сама переменная и соответствующий ей вектор-столбец из дальнейших вычислений исключаются.
Подробнее об алгоритме можно прочитать в [2], стр. 53.
скачать бесплатно Описание технологической области
Содержание дипломной работы
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1.1. ФОРМУЛИРОВКА ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ
1.1.1. ОБЩАЯ ФОРМУЛИРОВКА ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЙ
1.1.2. ФОРМУЛИРОВКА ЗАДАЧИ СОСТАВЛЕНИЯ РАПИСАНИЯ В ПРИМЕНЕНИИ К РАСПИСАНИЮ УЧЕБНЫХ ЗАНЯТИЙ.
1.2. АНАЛИЗ СУЩЕСТВУЮЩЕГО ПО
1.3. ПОСТАНОВКА ЗАДАЧИ.
2.1. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ РАСПИСАНИЯ В ВУЗЕ
2.1.1. ОБОЗНАЧЕНИЯ
ПРЕПОДАВАТЕЛИ
2.1.2. ПЕРЕМЕННЫЕ
2.1.3. ОГРАНИЧЕНИЯ
2.1.4. ЦЕЛЕВАЯ ФУНКЦИЯ
2.2. МЕТОДЫ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ
2.2.1. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ
2.2.2 ПРЯМОЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ
2.2.3. ТЕХНИКА ПОЛУЧЕНИЯ НАЧАЛЬНОГО ДОПУСТИМОГО БАЗИСА
2.3. ОСОБЕННОСТИ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ СИСТЕМЫ
2.3.1. ВЫБОР МОДЕЛИ
ИЕРАРХИЧЕСКИЙ СПОСОБ ОРГАНИЗАЦИИ
СЕТЕВОЙ СПОСОБ ОРГАНИЗАЦИИ
РЕЛЯЦИОННЫЙ СПОСОБ ОРГАНИЗАЦИИ
2.3.2. ОПИСАНИЕ ВХОДНОЙ ИНФОРМАЦИИ
2.3.3. РАЗРАБОТКА ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ ЗАДАЧИ
2.3.4. ОСОБЕННОСТИ ФОРМИРОВАНИЯ ОГРАНИЧЕНИЙ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ
2.4. РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ
2.5. АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ
ВЫВОДЫ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ 1. ВОЗМОЖНОСТИ ПРОГРАММНЫХ ПРОДУКТОВ СИСТЕМ СОСТАВЛЕНИЯ РАСПИСАНИЙ.
3. Система “Методист”
ПРИЛОЖЕНИЕ 2. ЛИСТИНГ ПРОГРАММНОГО МОДУЛЯ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ АВТОМАТИЧЕСКОГО СОСТАВЛЕНИЯ РАСПИСАНИЯ
