XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 3
Текст из файла (страница 3)
Следствием этого является непонимание самой природы практических задач исследования операций, которое, в свою очередь, приводит к значительным трудностям уже математического характера. Необходимость в написании этой книги возникла еще и потому, что учебная литература по курсу „Исследование операций" в основном представлена немногочисленными учебными пособиями по линейному программированию и теории игр, Главной целью написания предлагаемого учебника явилось систематическое изложение элементов теории исследования операций, усвоение которых должно способствовать активному овладению ее методами при решении практических задач.
Все основные понятия и методы проиллюстрированы примерами, а в конце каждой главы приведены контрольные вопросы и задачи. Учебник не содержит библиографии по исследованию операций и ее приложениям. В списке рекомендуемой литературы указаны лишь те источники, обращение к которым поможет получить более полную информацию по отдельным вопросам курса исследования операций и в смежных разделах высшей математики.
В первой главе дано формальное определение исследования операций, введены и обсуждены основные понятия этой комплексной математической дисциплины, рассмотрены типовые постановки задач и приведены различные варианты их классификации. Дан качественный анализ различных подходов к решению задач векторной оптимизации и обсуждено понятие „принцип оптимальности". Рассмотрены основные этапы решения задач исследования операций и специфические особенности их практической реализации. Следующие две главы посвящены изучению теоретических и прикладных аспектов линейного программирования, которое занимает особое место в исследовании операций.
Для усвоения материала этих глав не требуется специальной математической подготовки. Во второй главе обсуждается общая постановка задачи линейного программирования. Введены основные понятия н обоснована необходимость проведения анализа математических моделей задач линейного программирования на чувствнтельность. Значительное внимание уделено стандартной форме йредставления математических моделей задач линейного про'граммирования и геометрическому методу их решения. Рас'смотрены типовые задачи линейного программирования. В третьей главе основное внимание уделено изучению алгебраического метода решения задач линейного программиройания, известного как симплекс-метод.
Сначала сформулированы и доказаны основные утверждения линейного программирования, на базе которых рассмотрен симплекс-метод при известном начальном допустимом базисном решении. Для илцюстраций симплекс-метода используются симплекс-таблицы, а ,цля нахождения начального допустимого базисного решения— метод искусственных переменных. Рассмотрены элементы теории двойственности в линейном программировании и ее прияожения к анализу моделей на чувствительность. Четвертая глава посвящена изучению методов решения задач целочисленного программирования.
Основное внимание 18 ВВЕДЕНИЕ 19 уделено методу отсекающих плоскостей 1метод Гомори) и методу ветвей и границ. Рассмотрены три задачи математического программирования, которые в их исходной постановке не являются задачами целочисленного программирования, но становятся ими после введения новых переменных. В пятой главе рассмотрены различные задачи транспортного типа: транспортная задача, классическая транспортная задача, транспортная задача с промежуточными пунктами, задача о назначениях, задача выбора кратчайшего пути. Значительное внимание уделено взаимосвязям между конкретными видами задач транспортного типа и формами представления их математических моделей. Подробно рассмотрен симплексный метод решения задач транспортного типа.
В шестой главе рассмотрены приложения методов математического программирования к задачам принятия решений в условиях риска. При этом предполагается, что процесс изменения состояния изучаемой системы представляет собой марковский случайный процесс с конечным множеством возможных состояний и дискретным временем. Структура поощрений представляется матрицей доходов, элементами которой являются доход ()О) или затраты ((О), связанные с переходом системы из одного возможного состояния в другое. Матрицы переходных вероятностей и матрицы доходов зависят от возможных вариантов решений, которыми располагает „лицо, принимающее решения".
Основная цель заключается в определении оптимального решения, максимизирующего ожидаемый доход на конечном или бесконечном числе этапов. Седьмая глава посвящена анализу общих положений теории принятия решений в условиях риска и неопределенности, т.е. в условиях неполной информации, когда „лицу, принимающему решения", не противостоит мыслящий противник, Значительное внимание уделено содержательному анализу наиболее часто используемых при принятии решений в условиях риска и в условиях неопределенности скалярных критериев с последующим определением для каждого из них области не только возможного, но и наиболее целесообразного применения. В восьмой главе изложены элементы теории принятия решений в условиях неопределенности с несколькими „лицами, принимающими решения", значение целевой функции для каждого из которых зависит от решений, принимаемых всеми участниками.
Этот раздел исследования операций известен как теория игр. Обсуждаются основные понятия, различные варианты классификации и возможные способы описания игр. Основное внимание уделено анализу методов нахождения оптимальных решений в играх двух лиц с нулевой суммой. В последней, девятой главе учебника рассмотрены основы имитационного моделирования, которое формально не входит в исследование операций, но широко используется для решения таких важнейших ее задач, как задачи организационного упра'вления. В первом приложении подробно рассмотрен один из наиболее эффективных методов решения задачи о назначениях, известный в исследовании операций как венгерский метод. Во втором приложении основное внимание уделено изучению метода дискретного динамического программирования.
Рассмотрены различные аспекты его практического использования в многошаговых задачах принятия решений. 21 хь>0, 6=1,4; 4 ~аь,хь > 61, т' = 1, 3; /с=1 4 ~~1 сьхь ( С; к=1 4 РтсХЬ ( Р. Ь=1 1. ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ Напомним, что любая матпематпичесная модель представляет собой описание 1часто приближенное) какого-либо класса явлений реального мира, выраженное с помощью математических символов.
Переходя к обсуждению основных понятий исследования операций, отметим лишь следующее. В данной книге исследование операт4ий понимается как комплексная математическая дисциплина, занимающаяся построением, анализом и применением математических моделей принятия оптимальных 1наилучших в каком-то смысле) решений. Основной задачей исследования операт4ий является задача выбора в заданном множестве элемента, удовлетворяющего тем или иным критериям 1от греческого йттфег1оп — средство для суждения).
При этом любой элемент множества называют допустпимым решением, а выбранный элемент — оптпимальным решением. 1.1. Постановки задач и их классификация Построение матаематаичесной модели любой задачи исследования операций всегда начинается с описания множества С допуспсимых решений и критериев оптимальности. При этом под критперием оптпимальностпи понимают признак, на основании которого проводятся сравнительная оценка допустимых решений и выбор оптимального решения. Пример 1.1. Пусть имеется четыре вида продуктов Пь, 6 = 1, 4, из которых необходимо составить паек, удовлетворяющий следующим требованиям: 1) в паек должны входить все виды продуктов; 1.1.
Постановки задач и их классификация 2) содержание белков, жиров и углеводов в пайке должно быть не менее 61, 6з и 6з единиц соответственно; 3) стоимость пайка не должна превосходить С денежных единиц; 4) вес пайка не должен превышать заданной величины р; 5) паек должен быть минимального объема; 6) паек должен иметь максимальную калорийность. Рассматриваемая задача 1задача формирования пищевого набора) является задачей исследования операций. Построим ее модель. Пусть хь — количество единиц продукта Пь в пайке т и 1с = 1,4.
В этом случае вектор Х = 1х1 хт хз х4) полностью определяет состав пайка. Проанализировав требования 1-6, приходим к выводу, что требования 1 — 4 имеют характер ограничений, накладываемых на компоненты вектора Х, а требования 5 и 6 — явно выраженный критериальный характер. Для описания множества С допустимых решений для всех 6 = 1, 4 считаем известным, что единица продукта Пь содержит аь1 единиц белков, аьз единиц жиров, аьз единиц углеводов, стоит сь денежных единиц и имеет вес рь. В этом случае требования 1-4 приводят к системе неравенств, задающих в В4 множество С: Следовательно, допустимое решение представляет собой четыт рехмерный вектор Х =1х1 хз хз х4), принадлежащий множеству С.
22 1. ОСНОВНЫЕ ПОНЯТИЯ ИССЛЕДОВАНИЯ ОПЕРАЦИИ 1.1. Постаиояки задач и их классификация Для завершения построения математической модели рассматриваемой задачи исследования операций необходимо формализовать критерии оптимальности, соответствующие требованиям 5 и 6. Если для всех Й = 1, 4 считать известным, что единица продукта П» имеет объем и» и калорийность д», то, согласно требоваыиям 5 и 6, приходим к следующим критериям оптимальности: 4 4 '~ п»х» -+ ш1п, ~~~ д»х» — 1 шах.
ХПО ХсО »и1 »=1 При рассмотрении задачи о формировании пищевого пайка мы выступали как исследователи операции. По сформулированным требованиям нами была построена соответствующая математическая модель, и ыа следующем этапе исследований с использованием этой модели мы должны найти оптимальное решеыие из множества С допустимых решений. Но, как правило, принимает решение ые исследователь операции, который лишь готовит информацию для принятия решеыия, а „,лацо, яарпнимоюлцее ремленыли. Именно „лицо, принимающее решения", сформулировало требования к пищевому пайку в примере 1.1 и оыо же примет окончательное решеыие о составе пищевого пайка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
