- •Часть 2
- •Введение
- •1. Метод последовательного улучшения допустимого вектора (мпу)
- •1.1. Основная часть мпу
- •Проверка двойственной допустимости д.Б.М.К.
- •5. Подготовка информации к следующей итерации.
- •1. Процедура оценки.
- •3. Вычисление коэффициентов разложения вектора α6 по базисным векторам α4, α3, α5.
- •4. Определение ε*.
- •5. Подготовка информации к выполнению следующего шага.
- •1.2. Упражнения 1
- •1.3. Построение исходного допустимого базисного множества
- •1.4. Упражнения 2
- •1.5. Использование аппарата обратных матриц
- •Приступаем к выполнению итерации 1
- •1.6. Упражнения 3
- •3. Задачи для выполнения домашних заданий, расчетно-графических и контрольных работ
- •Список литературы
- •Часть 2
- •450000, Уфа-центр, ул. К. Маркса, 12
Федеральное агентство по образованию
Государственное образовательное учреждение высшего
профессионального образования
Уфимский государственный авиационный технический университет
МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
для самостоятельной работы студентов по дисциплинам
«Математические методы и модели исследования операций»,
«Методы оптимизации», «Комбинаторные алгоритмы»
Часть 2
Численные методы линейного программирования
Уфа 2008
Составители: Э.А. Мухачева, А.С. Филиппова, Т.Д. Тарасова
УДК 519.8 (07)
ББК 22.18 (я7)
Математические методы исследования операций: методические указания для самостоятельной работы студентов по дисциплинам «Математические методы и модели исследования операций», «Методы оптимизации», «Комбинаторные алгоритмы». Часть 2. Численные методы линейного программирования. / Уфимск. гос. авиац. техн. ун-т; Сост.: Э.А. Мухачева, А.С. Филиппова, Т.Д. Тарасова. – Уфа, 2008. – 22 с.
Методические указания посвящены численным методам решения задач линейного программирования. Для их решения описаны «метод последовательного улучшения допустимого вектора», метод построения допустимого базисного множества и отвечающего ему допустимого решения, алгоритм с обратной матрицей. Каждый раздел снабжен примерами для самостоятельного решения.
Указания предназначены для самостоятельного выполнения практических работ и домашних заданий студентами экономических специальностей, в том числе «Математические методы в экономике» и по направлению подготовки бакалавров «Математика. Компьютерные науки» по дисциплинам «Математические методы и модели исследования операций», «Методы оптимизации», «Комбинаторные алгоритмы».
Табл. 13. Библиогр.: 6 назв.
Рецензенты: канд. физ.-мат. наук, доц. Шерыхалина С.М. (УГАТУ)
канд. физ.-мат. наук, доц. Авдюшева С.М. (БГУ)
© Уфимский государственный
а виационный технический университет, 2008
СОДЕРЖАНИЕ:
Введение…………………………………………………………………………...4
1. Метод последовательного улучшения допустимого вектора (МПУ)............5
1.1.Основная часть МПУ…………………………………………………..6
1.2. Упражнения 1………………………………………………………...10
1.3. Построение исходного допустимого базисного множества………12
1.4. Упражнения 2 ………………………………………………………..14
1.5. Использование аппарата обратных матриц….…………….….........15
1.6. Упражнения 3………………………………………………………...17
2. Ответы к упражнениям………………………………………………………19
3. Задачи для выполнения домашних заданий, расчетно-графических и контрольных работ…………………………………………..………………....20
Список литературы..…………………….……………………………….………22
Введение
В 1939 г. издательством Ленинградского университета была выпущена небольшая брошюра молодого профессора Л.В. Канторовича, посвященная математическим методам организации и планирования производства. Эта работа сыграла основополагающую роль в становлении математического программирования – нового научного направления, представляющего собой поиск экстремальных решений некоторой функции на множестве допустимых решений, заданных системой неравенств и уравнений. В случае, когда функция является линейной и заданы линейные уравнения и неравенства, определяются задачи линейного программирования, которым и посвящена серия методических указаний для самостоятельного изучения студентами и специалистами в прикладных областях математики. Эта серия базируется на книге Э.А. Мухачевой, Г.Ш. Рубинштейна «Математическое программирование», которая была издана в Новосибирском государственном университете, после некоторых изменений – в Уфимском авиационном институте и допущена Министерством высшего и среднего специального образования СССР в качестве учебного пособия для студентов экономических и инженерно-технических специальностей вузов. Позднее книга переиздавалась дважды (1977 и 1987 гг.) в издательстве «НАУКА», Новосибирск и в Китае. Содержанием книги являются теория и численные методы математического программирования. Однако, она не содержит задач, примеров и теоретических вопросов для проверки самостоятельного изучения и проверки знаний студентов.
Методические указания для самостоятельной работы студентов по дисциплинам «Математические методы и модели исследования операций», «Методы оптимизации», «Комбинаторные алгоритмы», (часть 2) посвящена численным методам линейного программирования. Основной теоретический материал изложен в лекциях «Численные методы», «Прямой метод решения задач линейного программирования». Указания включают в себя базовый метод последовательного улучшения допустимого вектора (МПУ). В результате его применения в случае разрешимости задачи, находят оптимальное решение основной и двойственной задач. Кроме базового метода, для которого предполагается заданным допустимый вектор, приведены две его модификации: построение исходного допустимого решения и метод с обратной матрицей. Широко известный симплексный метод в данных указаниях не рассматривается. Однако его модификация с применением обратной матрицы полностью совпадает с изложенным здесь алгоритмом с обратной матрицей для МПУ. Все разделы указаний снабжены кратким изложением соответствующих теоретических положений и большим количеством примеров и упражнений, имеются ответы для проверки студентами полученных решений.
Целью методических указаний является изучение студентами базового численного метода линейного программирования, приобретение умений и практических навыков по решению основной и двойственной задач.