Введение. Кафедра «Экономика и логистика на транспор

МИНИСТЕРСТВО ТРАНСПОРТА РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ САМАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ

(СамГУПС)

Кафедра «Экономика и логистика на транспорте»

КОНСПЕКТ ЛЕКЦИЙ

по дисциплине:

«Экономико-математические методы и модели в экономике»

Содержание

Введение. 3

1. Общая постановка задачи линейного программирования. 13

1.1. Экономико-математическая модель. 13

1.2. Примеры задач линейного программирования. 14

1.3. Общая задача линейного программирования. 18

2. Геометрический метод решения задач линейного программирования. 20

3. Симплексный метод. 25

3.1. Отыскание максимума линейной функции. 26

3.2. Отыскание минимума линейной функции. 33

4. Двойственные задачи. 36

4.1. Экономическая интерпретация задачи, двойственной задаче об использовании ресурсов. 36

4.2. Взаимно двойственные задачи. 38

линейного программирования и их свойства. 38

5. Модели целочисленного линейного программирования. 41

5.1. Постановка задачи целочисленного программирования. 41

5.2. Методы отсечения. Метод Гомори. 42

5.3. Понятие о методе ветвей и границ. 43

6. Элементы теории игр. 44

6.1. Понятие об игровых моделях. 44

6.2. Платежная матрица. 46

Нижняя и верхняя цена игры.. 46

7. Классические методы оптимизации. 52

7.1. Классические методы определения экстремумов. 52

7.2. Метод множителей Лагранжа. 55

8. Межотраслевой баланс. 57

8.1 Статический межотраслевой баланс. 57

8.2 Динамический межотраслевой баланс. 64

Введение

Исследование операций — научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее эффективного управления различными организационными системами.

Управление любой системой реализуется как процесс, подчиняющийся определенным закономерностям. Их знание помогает определить условия, необходимые и достаточные для осуществления данного процесса. Для этого все параметры, характеризующие процесс и внешние условия, должны быть количественно определены, измерены. Следовательно, цель исследования операций – количественное обоснование принимаемых решений по организации управления.

При решении конкретной задачи управления применение методов исследования операций предполагает:

· построение экономических и математических моделей для задач принятия решения в сложных ситуациях или в условиях неопределенности;

· изучение взаимосвязей, определяющих впоследствии принятие решений, и установление критериев эффективности, позволяющих оценивать преимущество того или иного варианта действия.

Примерами задач исследования операций, отражающих его специфику, могут служить следующие задачи.

Задача 1. Для обеспечения высокого качества выпускаемых изделий на заводе организуется система выборочного контроля. Требуется выбрать такие формы его организации – например, назначить размеры контрольных партий, указать последовательность контрольных операций, определить правила отбраковки, — чтобы обеспечить необходимое качество при минимальных расходах.

Задача 2. Для реализации определенной партии сезонных товаров создается сеть временных торговых точек. Требуется выбрать параметры сети — число точек, их размещение, количество персонала – так, чтобы обеспечить максимальную экономическую эффективность распродажи.

Задача 3. К заданному сроку необходимо провести массовое медицинское обследование группы населения с целью выявления определенных заболеваний. На обследование выделены материальные средства, оборудование, персонал. Требуется разработать такой план обследования – установить число медпунктов, их размещение, вид и количество анализов, чтобы выявить как можно больший процент из числа заболевших.

Необходимо отметить также задачи об использовании ресурсов (планирования производства), о смесях, об использовании мощностей (загрузке оборудования), о раскрое материалов, транспортную задачу и др., в которых требуется найти решение, когда некоторый критерий эффективности (например, прибыль, выручка, затраты ресурсов и т.п.) принимает максимальное или минимальное значение.

Приведенные задачи относятся к разным областям практики, но в них есть общие черты: в каждом случае речь идет о каком-то управляемом мероприятии (операции), преследующем определенную цель. В задаче 1 – это организация выборочного контроля с целью обеспечить качество выпускаемой продукции; в задаче 2 – организация временных торговых точек с целью проведения сезонной распродажи; в задаче 3 – массовое медицинское обследование с целью определения процента заболевших. В каждой задаче заданы некоторые условия проведения этого мероприятия, в рамках которых следует принять решение – такое, чтобы мероприятие принесло определенную выгоду. Условиями проведения операции в каждой задаче оказываются средства, которыми мы располагаем, время, оборудование, технологии, а решение в задаче 1 заключается в выборе формы контроля — размера контрольных партий, правил отбраковки; в задаче 2 – в выборе числа точек размещения, количества персонала; в задаче 3 – в выборе числа медпунктов, вида и количества анализов.

Следует усвоить основные понятия и определения исследования операций.

Операция — любое управляемое мероприятие, направленное на достижение цели. Результат операции зависит от способа ее проведения, организации, иначе – от выбора некоторых параметров.

Всякий определенный выбор параметров называется решением.

Оптимальными считают те решения, которые по тем или иным соображениям предпочтительнее других. Поэтому основной задачей исследования операций является предварительное количественное обоснование оптимальных решений.

Замечание 1. Следует обратить внимание на постановку проблемы: само принятие решений выходит за рамки исследования операций и относится к компетенции ответственного лица или группы лиц, которые могут учитывать и другие соображения, отличные от математически обоснованных.

Замечание 2. Если в одних задачах исследования операций (например, в разд. 1.2) оптимальным является решение, при котором некоторый критерий эффективности принимает максимальное или минимальное значение, то в других задачах это вовсе не обязательно. Так, в задаче 2 оптимальным можно считать такое количество торговых точек и персонала в них, при котором среднее время обслуживания покупателей не превысит, например, 5 мин, а длина очереди в среднем в любой момент окажется не более 3 человек.

Модель и эффективность операции. Для применения количественных методов исследования требуется построить математическую модель операции. При построении модели операция, как правило, упрощается, схематизируется и схема операции описывается с помощью того или иного математического аппарата. Модель операции – это достаточно точное описание операции с помощью математического аппарата (различного рода функций, уравнений, систем уравнений и неравенств и т.п.). Составление модели операции требует понимания сущности описываемого явления и знания математического аппарата.

Эффективность операции – степень ее приспособленности к выполнению задачи – количественно выражается в виде критерия эффективности — целевой функции.

Общая постановка задачи исследования операции. В дальнейшем важно усвоить методологию построения моделей задач исследования операций. Все факторы, входящие в описание операции, можно разделить на две группы:

· постоянные факторы (условия проведения операции), на которые мы влиять не можем. Обозначим их через

· зависимые факторы (элементы решения) которые в известных пределах мы можем выбирать по своему усмотрению.

Например, в задаче об использовании ресурсов (см. разд. 1.2) к постоянным факторам следует отнести запасы ресурсов каждого вида, производственную матрицу, элементы которой определяют расход сырья каждого вида на единицу выпускаемой продукции каждого вида. Элементы решения – план выпуска продукции каждого вида.

Критерий эффективности, выражаемый некоторой функцией, называемой целевой, зависит от факторов обеих групп, поэтому целевую функцию Z можно записать в виде

Все модели исследования операций могут быть классифицированы в зависимости от природы и свойств операции, характера решаемых задач, особенностей применяемых математических методов.

Следует отметить, прежде всего, большой класс оптимизационных моделей. Такие задачи возникают при попытке оптимизировать планирование и управление сложными системами, в первую очередь экономическими системами. Оптимизационную задачу можно сформулировать в общем виде: найти переменные удовлетворяющие системе неравенств (уравнений)

(0.1)

и обращающие в максимум (или минимум) целевую функцию, т.е.

(0.2)

(Условия неотрицательности переменных, если они есть, входят в ограничения (0.1))

Как известно, упорядоченная совокупность значений n переменных представляется точкой n-мерного пространства. В дальнейшем эту точку будем обозначать, а само оптимальное решение

Рассмотрим еще одну, характерную для исследования операций задачу – классическую задачу потребления, имеющую важное значение в экономическом анализе.

Пусть имеется n видов товаров и услуг, количества которых (в натуральных единицах) по ценам соответственно за единицу. Суммарная стоимость этих товаров и услуг составляет

Уровень потребления Z может быть выражен некоторой функцией называемой функцией полезности. Необходимо найти такой набор товаров и услуг при данной величине доходов I, чтобы обеспечить максимальный уровень потребления, т.е.

(0.3)

при условии

(0.4) (0.5)

Решения этой задачи, зависящие от цен и величины дохода I, называются функциями спроса.

Очевидно, что рассмотренная задача потребления (0.3)–(0.5), так же как и многие другие (cм., например, разд. 1.2), является частным случаем сформулированной выше общей задачи (0.1)–(0.2) на определение экстремума функции n переменных при некоторых ограничениях, т.е. задачей на условный экстремум.

В тех случаях, когда функции и , в задаче (0.1)–(0.2) хотя бы дважды дифференцируемы, можно применять классические методы оптимизации. Однако применение этих методов в исследовании операций весьма ограниченно, так как задача определения условного экстремума функции я переменных технически весьма трудна: метод дает возможность определить локальный экстремум, а из-за многомерности функции определение ее максимального (или минимального) значения (глобального экстремума) может оказаться весьма трудоемким – тем более, что этот экстремум возможен на границе области решений. Классические методы вовсе не работают, если множество допустимых значений аргумента дискретно или функция Z задана таблично. В этих случаях для решения задачи (0.1)–(0.2) применяются методы математического программирования.

Если критерий эффективности (0.2) представляет линейную функцию, а функции в системе ограничений (0.1) также линейны, то такая задача является задачей линейного программирования. Если, исходя из содержательного смысла, ее решения должны быть целыми числами, то эта задача целочисленного линейного программирования. Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем задачу нелинейного программирования.

В частности, если указанные функции обладают свойствами выпуклости, то полученная задача является задачей выпуклого программирования.

Если в задаче математического программирования имеется переменная времени и критерий эффективности (0.2) выражается не в явном виде как функция переменных, а косвенно – через уравнения, описывающие протекание операций во времени, то такая задача является задачей динамического программирования.

Если критерий эффективности (0.2) и система ограничений (0.1) задаются функциями вида, то имеем задачу геометрического программирования. Если функции f и (или) в выражениях (0.2) и (0.1) зависят от параметров, то получаем задачу параметрического программирования, если эти функции носят случайный характер, – задачу стохастического программирования. Если точный оптимум найти алгоритмическим путем невозможно из-за чрезмерно большого числа вариантов решения, то прибегают к методам эвристического программирования, позволяющим существенно сократить просматриваемое число вариантов и найти если не оптимальное, то достаточно хорошее, удовлетворительное с точки зрения практики, решение.

Из перечисленных методов математического программирования наиболее распространенным и разработанным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций.

По своей содержательной постановке множество других, типичных задач исследования операций может быть разбито на ряд классов.

Задачи сетевого планирования и управления рассматривают соотношения между сроками окончания крупного комплекса операций (работ) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальных продолжительностей комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения.

Задачи массового обслуживания посвящены изучению и анализу систем обслуживания с очередями заявок или требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик, например, в определении числа каналов обслуживания, времени обслуживания и т.п.

Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов (точки заказа) и размера заказа. Особенность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта.

Задачи распределения ресурсов возникают при определенном наборе операций (работ), которые необходимо выполнять при ограниченных наличных ресурсах, и требуется найти оптимальные распределения ресурсов между операциями или состав операций.

Задачи ремонта и замены оборудования актуальны в связи с износом и старением оборудования и необходимостью его замены с течением времени. Задачи сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а также моментов замены оборудования модернизированным.

Задачи составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, обработки деталей) на различных видах оборудования.

Задачи планировки и размещения состоят в определении оптимального числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой.

Задачи выбора маршрута, или сетевые задачи, чаще всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов.

Среди моделей исследования операций особо выделяются модели принятия оптимальных решений в конфликтных ситуациях, изучаемые теорией игр. К конфликтным ситуациям, в которых сталкиваются интересы двух (или более) сторон, преследующих разные цели, можно отнести ряд ситуаций в области экономики, права, военного дела и т. п. В задачах теории игр необходимо выработать рекомендации по разумному поведению участников конфликта, определить их оптимальные стратегии.

В пособии нашли отражение основные из приведенных видов задач исследования операций.

На практике в большинстве случаев успех операции оценивается не по одному, а сразу по нескольким критериям, один из которых следует максимизировать, другие – минимизировать. Математический аппарат может принести пользу и в случаях многокритериальных задач исследования операции, по крайней мере, помочь отбросить заведомо неудачные варианты решений.

Для того чтобы из множества критериев, в том числе и противоречащих друг другу (например, прибыль и расход), выбрать целевую функцию, необходимо установить приоритет критериев.

Обозначим (здесь х — условный аргумент).

Пусть они расположены в порядке убывания приоритетов. В зависимости от определенных условий возможны в основном два варианта:

· в качестве целевой функции выбирается критерий, обладающий наиболее высоким приоритетом;

· рассматривается комбинации

(0.6)

где – некоторые коэффициенты (веса).

Величина f(x) учитывающая в определенной степени все критерии, выбирается в качестве целевой функции.

В условиях определенности – числа, – функции. В условиях неопределенности могут оказаться случайными и вместо f(x) в качестве целевой функции следует рассматривать математическое ожидание суммы (0.6).

Попытка сведения многокритериальной задачи к задаче с одним критерием эффективности (целевой функцией) в большинстве случаев не дает удовлетворительных результатов. Другой подход состоит в отбрасывании ("выбраковке") из множества допустимых решений заведомо неудачных решений, уступающих другим по всем критериям. В результате такой процедуры остаются так называемые эффективные (или "паретовские") решения, множество которых обычно существенно меньше исходного. А окончательный выбор "компромиссного" решения (не оптимального по всем критериям, которого, как правило, не существует, а приемлемого по этим критериям) остается за человеком — лицом, принимающим решение.

Методы исследования операций, как и любые математические методы, всегда в той или иной мере упрощают, огрубляют задачу, отражая порой нелинейные процессы линейными моделями, стохастические системы – детерминированными, динамические процессы – статическими моделями и т.д. Жизнь богаче любой схемы. Поэтому не следует ни преувеличивать значение количественных методов исследования операций, ни преуменьшать его, ссылаясь на примеры неудачных решений. Уместно привести в связи с этим шутливо-парадоксальное определение исследования операций, сделанное одним из его создателей Т. Саати, как "искусства давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами".