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