Учебно-методический комплекс дисциплины опд. В. 4 Математические методы исследования операций основная образовательная программа подготовки специалиста по специальности 010501 «Прикладная математика и информатика»
Скачать 409.34 Kb.
|
| Глава I. Линейное программирование §1. Системы линейных неравенств 1.1. Основные понятия множество  матриц над полем действительных чисел;n-мерных векторов-строк и m-мерных векторов-столбцов как частных случаев матриц; матрица транспонированная к данной, i-й вектор-строка и j-й вектор-столбец матрицы; частичный порядок  на множестве над полем действительных чисел, и его свойства;блочные матрицы и их свойств (транспонирование и умножение блочных матриц); линейная и неотрицательная линейная комбинации системы векторов; системы линейных неравенств над полем действительных чисел; векторная и матричная формы записи систем линейных неравенств; однородные системы линейных неравенств; совместность систем линейных неравенств; следствия систем линейных неравенств; неотрицательная линейная комбинация систем линейных неравенств; замечание о том, что любая неотрицательная комбинация системы линейных неравенств является следствием этой системы. 1.2. Следствия систем линейных неравенств Лемма 1. Если  – следствие системы  , …,  , то  .Лемма 2. Пусть – следствие системы , …, ,  , где  ,  . Тогда – следствие системы , …,  .1.3. Теорема Минковского Теорема. Если – следствие системы , …, , то  .Литература 1. Куликов Л. Я. Алгебра и теория чисел. – М.: Высшая школа, 1979. 2. Солодовников А. С. и др. Математика в экономике. – М.: Финансы и статистика, 2004. Лекция №2 1.4. Критерий несовместности систем линейных неравенств Теорема 1. Система  , …,  несовместна тогда и только тогда, когда существуют действительные числа  , удовлетворяющие условиям  ,  ,  .Теорема 2. Неравенство  является следствием системы  тогда и только тогда, когда совместна система  ,  .Теорема 3. Система линейных уравнений  ,  совместна тогда и только тогда, когда неравенство  является следствием системы  .1.5. Неотрицательные решения систем линейных уравнений и систем линейных неравенств Теорема 1. Система , совместна тогда и только тогда, когда несовместна система ,  .Теорема 2. Система  , совместна тогда и только тогда, когда несовместна система , ,  .Литература 1. Куликов Л. Я. Алгебра и теория чисел. – М.: Высшая школа, 1979. 2. Солодовников А. С. и др. Математика в экономике. – М.: Финансы и статистика, 2004. Лекция №3 §2. Задачи линейного программирования 2.1. Стандартные и канонические задачи линейного программирования Классификация задач линейного программирования:
2.2. Взаимная двойственность задач линейного программирования Определение взаимной двойственности задач линейного программирования. Доказательство того, что задачи С и С*, К и К* являются взаимно двойственными. 2.3. Допустимые и оптимальные решения Определение допустимых и оптимальных решений задач линейного программирования. Лемма 1. Пусть  и  – допустимые решения взаимно двойственных задач на минимум и на максимум соответственно. Тогда  .Теорема 1 (Критерий оптимальности векторов). Пусть и – допустимые решения взаимно двойственных задач на минимум и на максимум соответственно. Если  , то и являются оптимальными решениями соответствующих задач.Литература 1. Куликов Л. Я. Алгебра и теория чисел. – М.: Высшая школа, 1979. 2. Солодовников А. С. и др. Математика в экономике. – М.: Финансы и статистика, 2004. Лекция №4 2.4. Теорема двойственности Формулировка и доказательство теоремы двойственности. 2.5. Теорема равновесия Формулировка и доказательство теорем равновесия для стандартных и для канонических задач линейного программирования. Литература 1. Куликов Л. Я. Алгебра и теория чисел. – М.: Высшая школа, 1979. 2. Солодовников А. С. и др. Математика в экономике. – М.: Финансы и статистика, 2004. Лекция №5 § 3. Графический метод решения задач линейного программирования 3.1. Некоторые сведенья из аналитической геометрии Векторно-параметрическое уравнение отрезка Расстояние и взвешенное расстояние от точки до плоскости Выпуклые множества. Теорема 1. Полупространство является выпуклым множеством. Теорема 2. Пересечение выпуклых множеств есть выпуклое множество. Определение выпуклой линейной комбинации и выпуклой линейной оболочки множества точек. Теорема 3. Выпуклая оболочка любого множества точек есть выпуклое множество. Лекция №6 3.2. Графический метод решения задач линейного программирования Геометрическая интерпретация задач линейного программирования. Графический метод решения задач линейного программирования в общем виде. Примеры решения задач линейного программирования графическим способом. Здесь рассматриваются все типы задач, которые можно решить графическим способом: задача с двумя переменными; задача с произвольным числом переменных и двумя ограничениями; задача с произвольным числом переменных и ограничений, но для которой выполняется следующее условие: общее число переменных – ранг основной матрицы подсистемы, составленной из ограничений типа уравнений, 2.Литература 1. Акулич И. Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1987. 2. Полунин И. Ф. Курс математического программирования. – Минск: «Высшэйшая школа», 1969 3. Солодовников А. С. и др. Математика в экономике. – М.: Финансы и статистика, 2004. Лекция №7 § 4. Симплекс-метод решения задач линейного программирования 4.1. Симплекс-таблицы. Осевые преобразования симплекс-таблиц Симплекс таблицы. Осевые преобразования симплекс-таблиц. Допустимость симплекс таблиц по строкам и по столбцам. Доказательство лемм, являющихся обоснованиями этапов симплекс-метода. Литература 1. Куликов Л. Я. Алгебра и теория чисел. – М.: Высшая школа, 1979. 2. Полунин И. Ф. Курс математического программирования. – Минск: «Высшэйшая школа», 1969. 3. Солодовников А. С. и др. Математика в экономике. – М.: Финансы и статистика, 2004. Лекция №8 4.2. Алгоритм симплекс-метода Формулировка основной теоремы, содержащей алгоритм симплекс-метода решения задач линейного программирования. Обоснование алгоритма. Пример решения взаимно двойственных задач линейного программирования симплекс-методом. Литература 1. Куликов Л. Я. Алгебра и теория чисел. – М.: Высшая школа, 1979. 2. Полунин И. Ф. Курс математического программирования. – Минск: «Высшэйшая школа», 1969. 3. Солодовников А. С. и др. Математика в экономике. – М.: Финансы и статистика, 2004. Лекция №9 § 5. Транспортная задача линейного программирования 5.1. Постановка задачи. Основные теоремы Постановка классической задачи линейного программирования Транспортные таблицы Теорема 1. Транспортная задача имеет решение тогда и только тогда, когда сумма запасов равна сумме запросов. Сбалансированные и несбалансированные транспортные задачи линейного программирования. Сведение несбалансированных задач к сбалансированным. Теорема 2. Пусть  – допустимое решение транспортной задачи на минимум с матрицей тарифов С. Если существует система чисел  , удовлетворяющая условиям , для всех  ,  ; , для всех  , , ,то решение является оптимальным.5.2. Опорные решения Опорные решения. Метод северо-западного угла. Метод минимального элемента. Метод аппроксимаций Фогеля. 5.3. Циклы и ацикличные решения Цепи и циклы. Ацикличные решения. Примеры. Теорема о возможности построения цикла в таблице, содержащей более  заполненных клеток.Литература 1. Полунин И. Ф. Курс математического программирования. – Минск: «Высшэйшая школа», 1969. 2. Кузнецов А.В., Холод Н.И. Математическое программирование. – Минск: «Высшэйшая школа», 2001. 3. Нестеров Е. П. Транспортная задача линейного программирования. М.: Транспорт, 1971. Лекция №10 5.4. Алгоритм метода потенциалов Алгоритм метода потенциалов и его обоснование. Пример решения транспортной задачи линейного программирования методом потенциалов. 5.5. Транспортные задачи с ограничениями пропускной способности Транспортные задачи на минимум с ограничениями типа  ,  ,  ,  и методы их решения. Примеры.5.6. Транспортные задачи на максимум Математическая модель транспортной задачи на максимум Методы решения (сведение к задаче на минимум и непосредственное). 5.7. Задачи транспортного типа Понятие задач транспортного типа. Примеры задач транспортного типа (постановки задач в общем виде): Задача об оптимальном размещении производства, классическая задача о назначениях, задача о посеве культур, модель производства с запасами. Литература 1. Банди Б. Основы линейного программирования: Пер. с англ. – М.: Радио и связь, 1989. 2. Кузнецов А.В., Холод Н.И. Математическое программирование. – Минск: «Высшэйшая школа», 2001. 3. Нестеров Е. П. Транспортная задача линейного программирования. М.: Транспорт, 1971. 4. Полунин И. Ф. Курс математического программирования. – Минск: «Высшэйшая школа», 1969 5. Волков И.К., Загоруйко Е.А. Исследование операций. – М.: МГТУ им. Баумана, 2002. Лекция №11 §6. Теория двойственности в анализе оптимальных решений задач линейного программирования 6.1. Свойства взаимно двойственных задач линейного программирования Здесь приводятся свойства, которые понадобятся в пункте 7.2. 6.2. Экономическая интерпретация взаимно двойственных задач на примере задачи об использовании ресурсов и задачи о диете Литература 1. Акулич И. Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1987. 2. Банди Б. Основы линейного программирования: Пер. с англ. – М.: Радио и связь, 1989. 3. Кузнецов А. В., Холод Н. И. Математическое программирование. – Минск: «Высшэйшая школа», 2001. Лекция №12 6.3. Оценка устойчивости параметров относительно двойственных оценок. Интервалы устойчивости Метод оценки устойчивости параметров и нахождения интервалов устойчивости. Пример использования двойственных оценок для анализа задачи линейного программирования. Литература 1. Акулич И. Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1987. 2. Банди Б. Основы линейного программирования: Пер. с англ. – М.: Радио и связь, 1989. 3. Кузнецов А. В., Холод Н. И. Математическое программирование. – Минск: «Высшэйшая школа», 2001. Словарь терминов (глоссарий) m-мерный вектор-столбец – матрица размера  (элемент множества  )n-мерный вектор-строка – матрица размера  (элемент множества  )Ацикличное решение – решение X, транспортной задачи, для которого нельзя построить цикл в транспортной таблице с вершинами в клетках, в которых  .Блочная матрица  – матрица, которая получается из матрицы  приписыванием столбцов матрицы  (определена, если матрицы А и В имеют одинаковое число столбцов)Блочная матрица  – матрица, полученная матрицы , приписыванием строк матрицы , т.е. матрица  (естественно, такая матрица определена только, если матрицы А и В имеют одинаковое число строк). Векторная форма записи системы линейных неравенств – это запись системы в виде  , …,  .Векторно-параметрическое уравнение отрезка – уравнение  , где А и В – концы отрезка,  .Взаимная двойственность задач исследования операций. Пусть  задача исследования операций,  – задача, двойственная к . Задачи и называются взаимно двойственными, если  .Взвешенное отклонение точки  от плоскости  – число, определяемое равенством  .Взвешенное расстояние от точки до плоскости – абсолютная величина взвешенного отклонения от точки до плоскости .Выпуклая линейная оболочка точек  есть множество точек  , где  ,  .Выпуклое множество – множество, которое вместе со своими двумя любыми точками и  содержит также все точки отрезка  .Граница полуплоскости – ограничивающая ее плоскость. Допустимая задача линейного программирования – задача линейного программирования с совместной системой линейных ограничений. Допустимое решение – решение, удовлетворяющее системе ограничений. Задача линейного программирования – задача поиска вектора, доставляющего экстремум линейной функции и удовлетворяющего системе линейных уравнений или неравенств. Задача о диете. При откорме животных каждое животное ежедневно должно получить не менее  единиц питательного вещества первого вида, …, не менее  единиц питательного вещества m-го вида. Потребности животных можно удовлетворить за счет закупки кормов n видов. Стоимость единицы j-го корма равна  ден. ед. Содержание единицы питательного вещества i-го вида в единице корма j-го корма известно и равно  . Необходимо составить оптимальный рацион (оптимальную диету) животных, при котором их суточная потребность полностью удовлетворяется и который, а общая стоимость приобретения зерна является минимальной.Задача о назначениях (классическая). Имеется  различных видов работ и исполнителей. Каждый из исполнителей может выполнить только одну из видов работ, и каждая работа может выполняться только одним исполнителем. Стоимость выполнения  работы  исполнителем известна и равна  . Требуется составить такой план распределения исполнителей по видам работ, который минимизирует общую стоимость их выполнения (сумму стоимостей выполнения работ исполнителями).Задача об использовании ресурсов. Предприятие для производства видов продукции использует m видов ресурсов. Запасы и нормы расхода каждого вида ресурсов на производство единицы каждого вида продукции известны. Известны также стоимости единицы каждого вида продукции. Необходимо составить план производства, руководствуясь которым предприятие сможет получить от реализации продукции максимально возможную при данных условиях общую прибыль.Задача транспортного типа – задача, математическая модель которой подобна математической модели транспортной задачи, хотя в ней нет ни слова о перевозках. Задача, двойственная к прямой задаче канонического вида (  ,  ,  ) – задача поиска решения системы  , доставляющего минимум линейной функции  .Задача, двойственная к прямой задаче стандартного вида (  , , ) – задача поиска решения системы ,  , доставляющего минимум линейной функции .Критерий оптимальности векторов. Если для допустимых решений  и  взаимно двойственных задач линейного программирования выполняется равенство  , то и являются оптимальными решениями соответствующих задач.Линейная комбинация векторов  с коэффициентами  , называется вектор  Линейная оболочка векторов – множество их всевозможных линейных комбинаций, т.е. множество  Математическая модель задачи – задача, условие которой записано с помощью математических символов и соотношений. Матрица над полем действительных чисел – прямоугольная таблица действительных чисел. Матричная форма записи системы линейных неравенств – это запись системы в виде  .Метод аппроксимаций Фогеля – метод построения опорного решения транспортной задачи. Метод минимального элемента – метод построения опорного решения транспортной задачи. Метод потенциалов (в исследовании операций) – один из методов решения транспортной задачи. Метод северо-западного угла – метод построения опорного решения транспортной задачи. Неотрицательная линейная комбинация неравенств системы , …, – всякое неравенство вида  , где  – произвольные неотрицательные действительные числаНеотрицательная линейная оболочка векторов – множество их всевозможных линейных комбинаций с неотрицательными коэффициентами, т.е. множество  .Неотрицательный вектор – вектор с неотрицательными компонентами. Однородная система – система, свободные члены которой равны нулю. Опорное решение – допустимое решение, с которого начинается поиск оптимального решения Оптимальное решение – допустимое решение задачи, доставляющее целевой функции искомое экстремальное значение. Осевым преобразованием симплекс-таблицы  с ведущим элементом  – преобразование ее в таблицу  в которой переменные  и  ,  и  меняются местами. Это преобразование заключается в следующем. 1. Ведущий элемент заменяется обратной величиной:  ; 2. Элементы строки, содержащей ведущий элемент, за исключением самого ведущего элемента, делятся на ведущий элемент:  для всех  ;  . 3. Элементы столбца, содержащего ведущий элемент, за исключением самого ведущего элемента, делятся на ведущий элемент и меняют знаки:  для всех  ;  . 4. Прочие элементы вычисляются по правилу прямоугольника:  для всех , ;  для всех ;  для всех ;  для всех . Отклонение точки  от плоскости – число, определяемое равенством  .Полупространство – множество точек, лежащих по одну сторону от некоторой плоскости (вместе с точками этой плоскости). Так, каждая плоскость  разбивает содержащее ее пространство на два полупространства  и  .Потенциалы (в теории линейного программирования) – переменные двойственной задачи. Произведение матриц  и  – матрица  , такая, что  .Произведение матрицы на число  есть матрица , такая, что  Прямая задача канонического вида – задача поиска решения системы , , доставляющего минимум линейной функции  Прямая задача стандартного вида – задача поиска решения системы , , доставляющего минимум линейной функции Радиус-вектор точки – вектор, проведенный из начала координат в эту точку. Расстояние от точки до плоскости – абсолютная величина отклонения от точки до плоскости .Решение задачи линейного программирования – вектор, отвечающий требованиям этой задачи. Решение системы линейных уравнений (неравенств) – вектор, подстановка компонент которого вместо соответствующих неизвестных превращает ее в систему верных неравенств (равенств). Сбалансированная транспортная задача линейного программирования – задача, для которой  , где  и  – соответственно строчечные и столбцовые суммы матрицы X (см. транспортная задача линейного программирования)Симплекс-метод – метод решения задачи с помощью осевых преобразований симплекс-таблиц. Симплекс-таблица – таблица, которая применяется для решения задач линейного программирования симплекс-методом. Симплекс-таблица представляет прямую задачу , , канонического вида по строкам и задачу ,  по столбцам:  Здесь  – левые части двойственной ограничений задачи.Симплекс-таблица допустимая по i-й строке – симплекс-таблица, свободный член i-й строки которой (последний элемент i-й строки) неположителен. Симплекс-таблица допустимая по j-му столбцу – симплекс-таблица, свободный член j-го столбца которой неотрицателен. Система линейных неравенств относительно неизвестных  – система вида Система ограничений задачи линейного программирования – система линейных уравнений или неравенств, которой должно удовлетворять ее решение. Следствие системы неравенств – неравенство, множество решений которого содержит в себе множество решений системы. Совместная система – система, которая имеет хотя бы одно решение. Сумма матриц А и одинаковой размерности – матрица С той же размерности, такая, что  .Теорема двойственности. Если взаимно двойственные задачи допустимы, то они имеют решения и экстремальные значения целевых функций этих задач совпадают. Если хотя бы одна из задач недопустима, то ни одна из задач не имеет решения. Теорема Минковского. Если  – следствие системы  , …,  , то  .Теорема равновесия. Пусть и – допустимые решения взаимно двойственных задач линейного программирования, и  – значений левых частей линейных ограничений этих задач на векторах и . Векторы и являются оптимальными решениями соответствующих задач тогда и только тогда, когда  . Транспонированная матрица к – матрица B, такая, что  для всех  .Транспортная задача линейного программирования – задача поиска неотрицательной матрицы X с данными строчечными и столбцовыми суммами, которая минимизирует или максимизирует сумму произведений соответствующих элементов этой матрицы и некоторой фиксированной матрицы С. Транспортная таблица – прямоугольная таблица, с элементами  , в правом верхнем углу каждой ячейки которой записываются соответствующие элементы матрицы С (см. транспортная задача линейного программирования) рядом со строками подписаны суммы соответствующих строк, под столбцами – сумма соответствующих столбов матрицы X.Цепь – последовательный набор клеток транспортной таблицы, каждые две из которых расположены в одном ряду и никакие три клетки в одном ряду не расположены. Цикл – цепь, начальная и конечная клетки которой расположены в одном ряду. ПРИНЯТЫЕ ОБОЗНАЧЕНИЯ  – отношение теоретико-множественного включения – отношение принадлежности элемента множеству – выпуклая линейная оболочка точек . – неотрицательная линейная оболочка векторов  – линейная оболочка векторов  – матрица, транспонированная к . – естественный частичный порядок на множестве действительных чисел или на множестве  ( тогда и только тогда, когда  для всех ) – множество действительных чисел матрица – матрица, состоящая из m строк и n столбцов. – множество всех матриц над полем действительных чисел,  , , … – элементы матриц А, В, С, …, расположенные в i-й строке и j-м столбце –  -я вектор-строка матрицы ( ) –  -й вектор-столбец матрицы ( ). | ||||||||||||||||
Похожие:
 | Учебно-методический комплекс дисциплины опд. В 1 дополнительные главы... ... | | Учебно-методический комплекс дисциплины дс компьютерные сети и системы... Рецензенты: кандидат физико-математических наук, доцент Маренич А. С., кандидат технических наук, доцент Ланина Н. Р |
| Учебно-методический комплекс дисциплины опд. Ф. 21 Методы географических... Основная образовательная программа подготовки специалиста по специальности (специальностям) | | Учебно-методический комплекс дисциплины опд. Ф. 25 (опд. Ф. 13) «Специальная психология» Основная образовательная программа подготовки специалиста по специальности (специальностям) |
| Учебно-методический комплекс дисциплины опд. Ф. 25 (опд. Ф. 13) «Специальная психология» Основная образовательная программа подготовки специалиста по специальности (специальностям) | | Учебно-методический комплекс дисциплины опд. Ф. 11 Основы коммуникативной... Основная образовательная программа подготовки специалиста по специальности (специальностям) |
| Учебно-методический комплекс дисциплины опд. Ф. 10, Опд. Ф. 12, Опд.... А. В. Прялухина, кандидат психологических наук, доцент, зав кафедрой психологии Российского государственного социального университета... | | Учебно-методический комплекс дисциплины опд. Ф. 2 Учение об атмосфере... Целью курса является знакомство с основными научными знаниями об атмосфере и методами ее исследования |
| Учебно-методический комплекс дисциплины опд. В 2 опд. В 1 Современный... Педагогика и методика начального образования со специализацией «Обучение информатике в начальной школе» | | Учебно-методический комплекс дисциплины опд. Ф. 8 Религиоведение... Пащенко Л. В., к ф н., старший преподаватель кафедры связей с общественностью и лингвистики мгту |
| Учебно-методический комплекс дисциплины математическая логика Основная... Автор программы: Шиманский Сергей Александрович, ст преподаватель кафедры информатики и отд | | Учебно-методический комплекс дисциплины опд. Ф. 4 История религии... ... |
| Учебно-методический комплекс дисциплины фтд. 1 Основы кинезиологии... Основная образовательная программа подготовки специалиста по специальности (специальностям) | | Учебно-методический комплекс дисциплины опд. Ф. 2 Геоморфология основная... Цель дисциплины. В соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности... |
| Учебно-методический комплекс дисциплины гсэ. В устойчивое развитие... Основная образовательная программа подготовки специалиста по специальности (специальностям) |  | Учебно-методический комплекс дисциплины опд. Ф. 1 Землеведение основная... Курс «Землеведение» предназначен студентам, обучающимся по специальности «География», читается студентам 3 курса |
