Размещено на http://www.allbest.ru/

ФГОУ ВПО Оренбургский государственный аграрный университет

Экономический факультет

Кафедра организации производства и моделирования экономических систем

Курсовая работа

Тема: Обзор экономико-математических методов. Применение стохастического программирования для решения экономических задач

Оренбург 2009

Содержание

Введение

1. Теоретические вопросы

1.1 Теория игр

1.2 Теория массового обслуживания

1.3 Динамическое программирование

1.4 Сетевое планирование и управление

1.5 Стохастическое программирование

2. Практическое применение стохастического программирования

Выводы по результатам работы

Список использованной литературы

Введение

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

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

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

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

1. Теоретические вопросы

1.1 Теория игр

Одна из задач теории оптимальных решений - принятие решения в условиях неопределенности. Для обоснования решений разработаны специальные математические методы, которые рассматриваются в теории игр. Теория игр принадлежит к наиболее молодым математическим дисциплинам. Ее возникновение относится к 1944 г., когда вышла в свет монография Неймана и Моргенштерна «Теория игр и экономического поведения». В дальнейшем теория игр превратилась самостоятельное математическое направление, имеющее практическое приложение.

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

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

Неопределенность результата игры вызывается различными причинами, которые можно разбить на три группы:

1. Особенности правил игры вызывают такое разнообразие в ее развитии, что предсказать результат игры заранее невозможно. Источники неопределенности такого вида называются комбинаторными, а соответствующие игры - также комбинаторными.

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

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

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

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

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

Простейший вид стратегической игры - игра двух лиц с нулевой суммой (сумма выигрышей сторон равна нулю). Игра состоит из двух ходов: игрок А выбирает одну из своих возможных стратегий A_i (i = 1, 2,.... m), а игрок В выбирает стратегию В_j (j = 1, 2,..., n), причем каждый выбор производится при полном незнании выбору другого игрока.

Цель игрока А - максимизировать функцию ц (A_i, B_j), в свою очередь, цель игрока В - минимизировать эту же функцию. Каждый из игроков может выбирать одну из переменных, от которых зависит значение функции. Если игрок А выбирает некоторую из стратегий Ai, то это само по себе не может влиять да значение функции ц (A_i, B_j).

Влияние Ai, на величину значения ц (A_i, B_j) является неопределенным; определенность имеет место только после выбора, исходя из принципа минимизации ц (A_i, B_j), другим игроком переменной B_j. При этом B_j определяется другим игроком. Пусть ц (A_i, B_j)= a_ij. Составим матрицу А:

Строки матрицы соответствуют стратегиям A_i, столбцы - стратегиям B_j. Матрица А называется платежной или матрицей игры. Элемент a_ij матрицы - выигрыш игрока А, если он выбрал стратегию A_i, а игрок В выбрал стратегию B_j.

Пусть игрок А выбирает некоторую стратегию A_i ; тогда в наихудшем случае (например, если выбор станет известным игроку В) он получит выигрыш, равный min a_ij. Предвидя такую возможность, игрок А должен выбрать такую стратегию, чтобы максимизировать свой минимальный выигрыш a :

а = max min a_ij

i j

Величина а - гарантированный выигрыш игрока А - называется нижней ценой игры. Стратегия А_i0, обеспечивающая получение а, называется максиминной.

Игрок В, выбирая стратегию, исходит из следующего принципа: при выборе некоторой стратегии В_j его проигрыш не превысит максимального из значений элементов j-го столбца матрицы, т.е. меньше или равен max a_ij

Рассматривая множество max a_ij для различных значений j, игрок В, естественно выберет такое значение j, при котором его максимальный проигрыш в минимизируется:

в = min miax a_ij

i j

Величина в называется верхней ценой игры, а соответствующая выигрышу в стратегия В_j0 - минимаксной.

Фактический выигрыш игрока А при разумных действиях партнеров ограничен нижней и верхней ценой игры. Если же эти выражения равны, т.е.

max min a_ij = min max a_ij = u

i j j i

то выигрыш игрока А - вполне определенное число, игра называется вполне определенной, а выигрыш называется значением игры и равен элементу матрицы а_i0j0. Элемент а_i0j0 в матрице такой игры является одновременно минимальным в строке i₀, максимальным в столбце j₀ и называется Седловой точкой. Седловой точке соответствуют оптимальные стратегии игроков, их совокупность - это решение игры, которое обладает следующем свойством: если один из игроков придерживается своей оптимальной стратегии, то для другого отклонение от его оптимальной стратегии не может быть выгодно.

1.2 Теория массового обслуживания

Часто приходится сталкиваться с такими ситуациями:

- очередь покупателей в кассах магазинов;

- колонна автомобилей, движение которых остановлено светофором;

- ряд станков, вышедших из строя и ожидающих ремонта; и т.д.

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

Цель изучения СМО состоит в том, чтобы взять под контроль некоторые характеристики системы, установить зависимость между числом обслуживаемых единиц и качеством обслуживания. Качество обслуживания, чем выше, тем больше число обслуживающих единиц. Но экономически невыгодно иметь лишние обслуживающие единицы.

В промышленности СМО применяется при:

- поступлении сырья, материалов, комплектующих изделий на склад и выдаче их со склада;

- обработке широкой номенклатуры деталей на одном и том же оборудовании;

- организации наладки и ремонта оборудования;

- определении оптимальной численности обслуживающих отделов и служб предприятий и т.д.

Основными элементами СМО являются источники заявок, их входящий поток, каналы обслуживания и выходящий поток.

В зависимости от характера формирования очереди СМО различают:

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

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

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

По числу каналов обслуживания СМО делятся на одноканальные и многоканальные.

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

Рассмотрим в отдельности элементы СМО.

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

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

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

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

где - интенсивность потока заявок, т.е. среднее число заявок в единицу времени:

(чел./мин, р./ч, автом./дн., квт/ч),

где - среднее значение интервала времени между двумя соседними заявками.

Для такого потока заявок время между двумя соседними заявками распределено экспоненциально с плотностью вероятности

Случайное время ожидания в очереди начала обслуживания считают распределенным экспоненциально:

где v - интенсивность движения очереди, т.е. среднее число заявок, приходящихся на обслуживание в единицу времени:



где - среднее значение времени ожидания в очереди.

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

f(t_обс)=e^-t_,

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

(чел./мин, р./дн., кг/ч, докум./дн.),

где среднее время обслуживания.

Важной характеристикой СМО, объединяющей и , является интенсивность нагрузки

p = /.

1.3 Динамическое программирование

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

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

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

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

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

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

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

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

Пример. Пусть планируется деятельность некоторой системы S промышленных предприятий P1, P2, …, Pn на некоторый период времени T, состоящий из k хозяйственных лет t1 (i = 1, 2, …, k), причем

k

T = ? ti

I = 1

В начале периода T на развитие предприятий выделены основные средства D. В начале каждого хозяйственного года производится финансирование всей системы предприятий, т.е. выделяется доля основных средств. Известны первоначальное состояние системы S₀, характеризуемое количеством средств, уже вложенных в предприятия, и конечное состояние S_k, характеризуемое всей дополнительно вложенной суммой D. Как следует распределить по предприятиям и годам основные средства D, чтобы к концу периода T суммарный доход W от всей системы предприятий был максимальным?

Решение. Обозначим через x_ij сумму, выделяемую в начале i-ого года j-ому предприятию (i=1, 2, …, k; j=1, 2, …, n). Предположим, что средства на i-ом этапе распределены, т.е. выбрано определенное управление U_i, которое состоит в том, что в начале i-ого года предприятию P₁ выделены средства x_i1, предприятию P₂ - средства x_i2 и т.д. Тогда вектор U_i = (x_i1, x_i2, …, x_in) определяет распределение средств на i-ом этапе. Совокупность выделенных средств на k шагах выразится системой векторов n-мерного векторного пространства

U₁= (x₁₁; x₁₂; …; x_1n),

U₂= (x₂₁; x₂₂; …; x_2n),

………………………

U_k= (x_k1; x_k2; …; x_kn).

Суммарный доход за k лет зависит от совокупности управлений, т.е. является функцией от U_1, U_{2, …,} U_k:

W = W (U_1, U_{2, …,} U_k).

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

W = (x₁₁; x₁₂; …; x_1n; x₂₁; x₂₂; …; x_2n; x_k1; x_k2; …; x_kn),

т.е. как функцию многих переменных. Теперь решение задачи заключается в нахождении такой совокупности значений аргументов x_ij, при которой функция W достигает максимального значения. Казалось бы, найдя частные производные функции по всем аргументам, приравняв их к нулю и решив систему уравнений = 0, получим значение x_ij, при которых функция W имеет локальный максимум.

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

1.4 Сетевое планирование и управление

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

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

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

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

Сетевой график - это ориентированный граф без контуров. В сетевом моделировании имеются два основных элемента - работа и событие.

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

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

2. Два соседних события могут объединяться лишь одной работой. Для изображения параллельных работ вводятся промежуточное событие и фиктивная работа (рис. 1).

Размещено на http://www.allbest.ru/

Рис. 1

Размещено на http://www.allbest.ru/

Рис. 2

3. В сети не должно быть тупиков, т.е. промежуточных событий, из которых не выходит ни одна работа (рис. 2).

4. В сети не должно быть промежуточных событий, которым не предшествует хотя бы одна работа (рис. 3).



Размещено на http://www.allbest.ru/

Рис. 3

Размещено на http://www.allbest.ru/

Рис. 4

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

Для правильной нумерации событий поступают следующим образом: нумерация событий начинается с исходного события, которому дается номер 1. Из исходного события 1 вычеркивают все исходящие из него работы, на оставшейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию дается номер 2.

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

Размещено на http://www.allbest.ru/

Рис. 5

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

1.5 Стохастическое программирование

игра обслуживание стохастический программирование

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

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

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

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

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

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

При формулировании некоторых задач система ограничений записывается в следующем виде:

Здесь Р, p_t - символы вероятности. Под допустимым планом в данной задаче подразумевается такой набор значений неизвестных, который обеспечивает выполнение i-гo условия с вероятностью Р, не меньшей заданной вероятности p_t. Для условий, выполнение которых очень важно, величина p_t выбирается близкой к единице; для менее существенных условий она берется ближе к нулю.

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

Нежесткие задачи лучше приспособлены к учету случайных факторов; их применение в сельскохозяйственном планировании представляется более реальным.

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

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

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

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

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

2. Практическое применение стохастического программирования

Задача добычи электроэнергии.

Пусть имеются два месторождения A и B электроэнергии, энергия которых соответственно равны x и y ед. Для добычи энергии используется одна машина, которая либо с определенной вероятностью добывает часть энергии, либо выходит из строя и в дальнейшем не используется. Если машина работает на месторождении A, то с вероятностью p₁ она добывает часть r₁ имеющейся энергии и с вероятностью 1 - p₁ выходит из строя. Если машина работает на месторождении B, то с вероятностью p₂ она добывает часть r₂ имеющейся энергии и с вероятностью 1 - p₂ выходит из строя.

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

Решение.

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

Исходя из критерия задачи, определим функцию ѓ_N (x,y) как ожидаемое количество электроэнергии, добытой до выхода машины из строя.

В одноэтапном процессе в случае первоначального выбора для разработки месторождения A среднее количество добытой энергии составляет p₁r₁x и p₂r₂y при выборе месторождения B, следовательно, ѓ₁ (x, y) = max [p₁r₁x, p₂r₂y]

Рассмотрим (N + 1)-этапный процесс. Каким бы ни был первоначальный выбор, его продолжение на оставшихся N этапах должно быть оптимально. Ожидаемое количество добытой электроэнергии в (N + 1)-этапном процессе при первоначальном выборе месторождения А

(1) ѓ_А (x, y) = p₁ [r₁x + ѓ_N ((1 - r₁) x, y)],

а при выборе месторождения В

(2) ѓ_В (x, y) = p₂ [r₂y + ѓ_N (x, (1 - r₂) y)]

По условию необходимо максимизировать общее количество добытой электроэнергии, поэтому, объединяя (1) и (2), получаем основное уравнение для (N + 1)- этапного процесса:

(3) p₁ [r₁x + ѓ_N ((1 - r₁) x, y)]

ѓ_N+1 (x, y) = max [ѓ_А (x, y), ѓ_В (x, y)] = max

p₂ [r₂y + ѓ_N (x, (1 - r₂) y)]

Используя функциональные уравнения (1) и (3), определим оптимальное поведение в трехэтапном процессе, если x = 500, y = 300, p₁ = 0,6, r₁ = 0,5, p₂ = 0,7, r₂ = 0,7.

Рассмотрим одноэтапный процесс [при этом используем уравнение (1)]. На 1-этапе работу можно начать либо на месторождении А, либо на месторождении В. В случае выбора месторождения А добыча электроэнергии составит в среднем ѓ₁ (x, y) = p₁r₁x = 0,6*0,5*500 = 150 (ед.)

Если в течение 1-ого этапа машина не вышла из строя, то в начале 2-ого этапа необходимо сделать выбор: продолжить работу на месторождении А или начать работу на месторождении В на месторождении А добыто r₁x ед. электроэнергии и её остаток составляет x- r₁x (1- r₁)x ед.; на месторождении В энергия осталась прежней.

Решая функциональное уравнение, получаем

 p₁r₁ (1- r₁)x 0,6*0,5*0,5*500

ѓ₁ [(1 - r₁) x, y)] = max = max =

p₂ r₂y 0,7*0,7*300

75

= max = 147 (ед.)

147

Следовательно, на 2-м этапе машина должна работать на месторождении В.

В начале 3-его этапа следует сделать выбор: продолжать работу на месторождении В или на месторождении А на месторождении В добыто r₂y ед. электроэнергии, её остаток составляет y- r₂y = (1- r₂)y ед. Имеем

p₁r₁ (1- r₁)x 0,6*0,5*0,5*500

ѓ₁ [(1 - r₁) x, (1- r₂)y] = max = max =

p₂ r₂(1- r₂)y 0,7*0,7*0,3*300

75

= max = 75 (ед.)

44,1

Следовательно, на 3-м этапе машина должна работать на месторождении А.

Таким образом, если на 1-м этапе работа начата на месторождении А, то оптимальное поведение состоит в том, что на 2-м этапе надо начать работу на месторождении В, а на третьем этапе - продолжать работу на месторождении А.

Пусть работа начата на месторождении В; тогда на 1-м этапе добыча электроэнергии составляет в среднем

ѓ₁ (x, y) = p₂r₂x = 0,7*0,7*300 = 147 (ед.)

В начале 2-ого этапа производим выбор:

p₁r₁x 150

ѓ₁ [ x, (1- r₂)y] = max = max = 150 (ед.)

p₂ r₂(1- r₂)y 44,1

т.е. работу следует начинать на месторождении А.

В начале 3-его этапа также производим выбор:

75

ѓ₁ [(1 - r₁) x, (1- r₂)y] = max = 75 (ед.)

44,1

т.е следует продолжать работу на месторождении А. Таким образом, если на 1-м этапе работа начата на месторождении В, то оптимальное поведение состоит в том, что на 2-м и 3-м этапах добыча ведется на месторождении А.

Рассмотрим двухэтапный и трехэтапный процессы. Полагая последовательно N = 1,2, из уравнения (3) определяем вид функций, необходимых для решения задачи.

При N = 1

(4) p₁ [r₁x + ѓ₁ ((1 - r₁) x, y)]

ѓ₂ (x, y) = max

p₂ [r₂y + ѓ₁ (x, (1 - r₂) y)]

При N = 2

(5) p₁ [r₁x + ѓ₂ ((1 - r₁) x, y)]

ѓ₃ (x, y) = max

p₂ [r₂y + ѓ₂ (x, (1 - r₂) y)]

(6) p₁ [r₁(1 - r₁) x + ѓ₁ ((1 - r₁)² x, y)]

ѓ₂ ((1 - r₁) x, y) = max

p₂ [r₂y + ѓ₁ ((1 - r₁) x, (1 - r₂)y)]

(7) p₁ [r₁x + ѓ₁ ((1 - r₁) x, (1 - r₂)y)]

ѓ₂ (x, (1 - r₂) y) = max

p₂ [r₂ + (1 - r₂) y + ѓ₁ (x, (1 - r₂)² y)]

Таким образом, кроме значений ѓ₁ ((1 - r₁) x, y), ѓ₁ (x, (1 - r₂) y) и ѓ₁ ((1 - r₁) x, (1 - r₂)y), необходимо вычислить количество добытой электроэнергии в одноэтапном процессе для следующих случаев:

p₁r₁(1 - r₁)² x 0,6*0,5*0,25*500

а) ѓ₁ (x, (1 - r₂)² y) = max = max =

p₂ r₂y 0,7*0,7*300

37,5

= max = 147 (ед.)

147

если на 1-м и 2-м этапах машина работала на месторождении А, а на 3-м на месторождении В;

 p₁r₁x 0,6*0,5*500

б) ѓ₁ (x, (1 - r₂)² y) = max = max =

p₂ r₂ (1 - r₂)² y) 0,7*0,7*0,09*300

150

= max = 150 (ед.)

13.23

если на 1-м и 2-м этапах машина работала на месторождении В, а на 3-м - на месторождении А подставляя найденные значения функций в уравнения (4) - (7), окончательно получаем:

для двухэтапного процесса:

0,6*(0,5*500+147) 208,2

ѓ₂ (x, y) = max = max = 252 (ед.)

0,7*(0,7*300+150) 252

0,6*(0,5*0,5*500+147) 163,2

ѓ₂ ((1 - r₁) x, y) = max = max =252

0,7*(0,7*300+150) 252

0,6*(0,5*500+75) 195

ѓ₂ (x, (1 - r₂) y) = max = max = 195

0,7*(0,7*0,3*300+150) 149,1

т.е работу на 1-м этапе надо начинать на месторождении В.

Таким образом, чтобы в трехэтапном процессе добыть максимального количества электроэнергии, необходимо: на 1-м этапе вести работу на месторождении В, а на 2-м и 3-м этапах - на месторождении А.

Выводы по результатам работы

В процессе работы были рассмотрены пять систем программирования для решения различных задач. Они использовались для нахождения оптимальных вариантов решения этих задач.

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

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

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

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

Список использованной литературы

1. Нефедов Ю.В., Базаров М.К. Математические методы в обосновании управленческих решений (Математические модели в управлении): Монография. - Оренбург: Издательство ООИПКРО, 2005.

2. Полунин И.Ф. Курс математического программирования: Учебник. / 3-е изд. ? 1975.

3. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование: Учебник. / 2-е изд. ? 1980.

4. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании: Учебник. / 3-е изд., испр. - М.: Дело, 2002.

5. Гатаулин А.М., Гаврилов Г.В., Сорокина Т.М. Математическое моделирование экономических процессов. / Под ред. Гатаулина А.М. - М.: Агропромиздат, 1990.

Размещено на Allbest.ru