- •И.Н. Слинкина
- •Оглавление
- •Вопросы к блокам по курсу «Исследование операций» Блок 1
- •Блок 1.
- •1.1. Предмет и задачи исследования операций
- •1.2. Основные понятия и принципы исследования операций
- •1.3. Математические модели операций
- •1.4. Понятие линейного программирования
- •1.5. Примеры экономических задач линейного программирования. Задача о наилучшем использовании ресурсов
- •1.6. Примеры экономических задач линейного программирования. Задача о выборе оптимальных технологий
- •1.7. Примеры экономических задач линейного программирования. Задача о смесях
- •1.8. Примеры экономических задач линейного программирования. Транспортная задача
- •1.9. Основные виды записи задач линейного программирования
- •1.10. Способы преобразования
- •1.11. Переход к канонической форме
- •1.12. Переход к симметричной форме записи
- •Блок 2.
- •2.1. Геометрическая интерпретация задачи линейного программирования
- •2.2. Решение задач линейного программирования графическим методом
- •2.3. Свойства решений задачи линейного программирования
- •2.4. Общая идея симплексного метода
- •2.5. Построение начального опорного плана при решении задач линейного программирования симплексным методом
- •2.6. Признак оптимальности опорного плана. Симплексные таблицы
- •2.7. Переход к нехудшему опорному плану.
- •2.8. Симплексные преобразования
- •2.9. Альтернативный оптимум (признак бесконечности множества опорных планов)
- •2.10. Признак неограниченности целевой функции
- •2.11. Понятие о вырождении. Монотонность и конечность симплексного метода. Зацикливание
- •2.12. Понятие двойственности для симметричных задач линейного программирования
- •3.1. Несимметричные двойственные задачи
- •3.2. Открытая и закрытая модели транспортной задачи
- •3.3. Построение начального опорного плана. Правило "Северо-западного угла"
- •3.4. Построение начального опорного плана. Правило минимального элемент
- •3.5. Построение начального опорного плана. Метод Фогеля
- •3.6. Метод потенциалов
- •3.7. Решение транспортных задач с ограничениями по пропускной способности
- •3.8. Примеры задач дискретного программирования. Задача о контейнерных перевозках. Задача о назначении
- •3.9. Сущность методов дискретной оптимизации
- •3.10. Задача выпуклого программирования
- •3.11. Метод множителей Лагранжа
- •3.12. Градиентные методы
- •4.1. Методы штрафных и барьерных функций
- •4.2. Динамическое программирование. Основные понятия. Сущность методов решения
- •4.3. Стохастическое программирование. Основные понятия
- •4.4. Матричные игры с нулевой суммой
- •4.5. Чистые и смешанные стратегии и их свойства
- •4.6. Свойства чистых и смешанных стратегий
- •4.7. Приведение матричной игры к злп
- •4.8. Задачи теории массового обслуживания. Классификация систем массового обслуживания
- •4.9. Потоки событий
- •4.10. Схема гибели и размножения
- •4.11. Формула Литтла
- •4.12. Простейшие системы массового обслуживания
- •2. Одноканальная система массового обслуживания с неограниченной очередью.
- •Список рекомендуемой литературы
1.3. Математические модели операций
Для применения количественных методов исследования в любой области всегда требуется какая-то математическая модель. При построении модели реальное явление (в нашем случае – операция) неизбежно упрощается, схематизируется, и эта схема описывается с помощью того или иного математического аппарата.
Общих способов построения математических моделей не существует. В каждом конкретном случае модель выбирается исходя из вида операции, ее целевой направленности, с учетом задачи исследования (какие параметры требуется определить и влияние каких факторов отразить). Необходимо также в каждом конкретном случае соразмерять точность и подробность модели:
а) с той точностью, с которой нужно знать решение;
б) с той информацией, которой мы располагаем или можем приобрести.
Если исходные данные, нужные для расчетов, известны неточно, то, очевидно, нет смысла входить в тонкости, строить очень подробную модель и тратить время (свое и машинное) на тонкую и точную оптимизацию решения. К сожалению, этим принципом часто пренебрегают и выбирают для описания явлений слишком подробные модели.
Математическая модель должна отражать важнейшие черты явления, все существенные факторы, от которых зависит успех операции. Вместе с тем модель должна быть по возможности более простой. Две опасности всегда подстерегают составителя модели: первая – увязнуть в подробностях и вторая – слишком огрубить явление. Создание математической модели – самая важная и ответственная часть исследования, требующая глубокого знания не столько математики, сколько существа моделируемых явлений.
Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества вариантов в условиях рыночных отношений приходится отыскивать наилучшие в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. До недавнего времени большинство таких задач решалось исходя из здравого смысла и опыта лиц, принимающих решения, или просто «на глаз». При таком подходе не было и не могло быть никакой уверенности, что найденный вариант – наилучший. При современных масштабах производства даже незначительные ошибки оборачивались громадными потерями. В связи с этим возникла необходимость применять для анализа и синтеза экономических ситуаций и систем математические методы и современную вычислительную технику. Такие методы объединяются под общим названием – математическое программирование.
Определение: Математическое программирование – область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных.
Определение: Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности.
Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель.
Определение: Математическая модель задачи – это отражение оригинала в виде функций, уравнений, неравенств, цифр и т.д.
Математическая модель задачи математического программирования включает:
совокупность неизвестных величин
,
действуя на которые систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, стратегией, поведением и др.);
целевую функцию (функцию цели, показатель эффективности, критерий оптимальности, функционал задачи и др.). Целевая функция позволяет выбрать наилучший вариант из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение;
условия (или систему ограничений), налагаемые на неизвестные величины. Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Ограниченными являются не только материальные, финансовые и трудовые ресурсы, но и таковыми могут быть возможности технического, технологического и, вообще, научного потенциала. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений (область экономических возможностей). Объединение всех условий (ограничений), налагаемых на известные (искомые) величины задачи, обозначим: (х). При таких обозначениях модель задачи математического программирования примет вид: max (min) Z = z(x), x, или найти extremum Z = z(x), x.
В развернутом виде: найти план , доставляющий экстремальное значение целевой функцииz, т.е.
max (min) Z = z
при ограничениях
Замечание: надпись «» означает «i изменяется от 1 до m».
Из экономических или физических соображений на план задачи или некоторые его компоненты (координаты) накладываются условия не отрицательности:
,
иногда – целочисленности.
Определение: План Х, удовлетворяющий системе ограничений задачи, называется допустимым (Х).
Определение: Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным.
Оптимальный план будем обозначать , экстремальное значение функции цели –z()=. Оптимальное решение, вообще говоря, не обязательно единственное, возможны случаи, когда оно не существует, имеется конечное или бесконечное множество оптимальных решений.