Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

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

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

экономических систем

Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

Выполнила:

студентка 42 группы

экономического факультета

специальности «Экономика и управление

на предприятиях АПК»

Фаизова А.А.

Проверил преподаватель:

Филатова Ольга Викторовна

Оренбург - 2008

Содержание

Цель работы

1. Изложение теоретических аспектов исследования

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

1.2 Сетевое планирование и правление

1.3 Элементы теории массового обслуживания

1.4 Теория игр

1.5 Нелинейное программирование

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

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

Список литературы

Цель работы

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

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

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

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

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

1. Изложение теоретических аспектов исследования

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

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

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

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

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

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

Процесс длится определенное число шагов N. На каждом шаге осуществляется выбор одного управления uⁿ, под воздействием, которого система переходит из одного состояния Sⁿ в другое Sⁿ⁺¹: Sⁿ Sⁿ⁺¹. Поскольку процесс марковский, то Sⁿ = uⁿ (Sⁿ) зависит только от текущего состояния.

Каждый шаг (выбор очередного решения) связан с определенным эффектом, который зависит от текущего со стояния и принятого решения: (Sⁿ , Sⁿ ).

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

Требуется найти такое решение uⁿ для каждого шага (n = 1, 2, 3, ..., N), т.е. последовательность (u¹, ..., u^N), чтобы получить максимальный эффект (доход) за N шагов.

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

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

Любая возможная допустимая последовательность решений (u¹, ..., u^N) называется стратегией управления. Стратегия управления, доставляющая максимум критерию оптимальности, называется оптимальной.

В основе общей концепции метода ДП лежит принцип оптимальности Беллмана:

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

,

где -- все допустимые управления при условии, что система находится в состоянии Sⁿ;

(Sⁿ , Sⁿ ) -- эффект от принятия решения uⁿ;

-- эффект за оставшиеся n шагов.

Благодаря принципу оптимальности удается при последующих переходах испытывать не все возможные варианты, лишь оптимальные выходы. РДП позволяют заменить трудоёмкое вычисление оптимума по N переменным в исходной задаче решением N задач, в каждой из которых оптимум годится лишь по одной переменной.

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

В качестве примера построения РДП рассмотрим использование принципа оптимальности для реализации математической модели задачи оптимального распределения некоторого ресурса в объеме х :

где x_j -- количество ресурса, используемое j-м способом;

-- доход от применения способа j, j = 1, N .

Рекуррентные соотношения, с помощью которых находится решение этой задачи, имеют вид:

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

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

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

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

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

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

РИС 1.

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

В первую очередь, перед построением сетевого графика необходимо составить список всех работ, входящих в комплекс, представлять их конечные результаты (события). В отношении каждой работы следует выяснить, какие работы ей предшествуют и какие следуют за ней. Только после этого строится эскизный сетевой график, упорядочиваются и нумеруются (шифруются) его события (вершины графа). Если комплекс сложный, то его графическое представление строится по частям, которые затем “сшиваются”. При большом количестве работ и событий упорядочение их и сшивание отдельных сетевых графиков, а также поиск контуров производится на ЭВМ. Если в сети обнаружен контур, необходимо пересмотреть список работ и логические связи между ними. Обычно требуется, чтобы в сети было единственное исходное (начальное) событие и единственное завершающее, что возможно при введении фиктивных работ. В сети не должно быть хвостовых ( кроме исходного I) и тупиковых (кроме завершающего S) событий. Хвостовым называют событие, в которое не входит ни одна работа (рис 2, событие 3); тупиковым - событие, из которого не выходит ни одна работа (рис 2, событие 6).

РИС 2.

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

РИС 3.

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

РИС 4.

Если свершением какого-либо события начинается несколько работ, то это изображается так, как показано на рис 5.



РИС 5.

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

РИС 6.

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

б

РИС 7

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

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

1.3 Элементы теории массового обслуживания

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

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

Примерами систем массового обслуживания могут служить:

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

посты ремонта автомобилей;

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

станции технического обслуживания автомобилей;

аудиторские фирмы;

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

телефонные станции и т. д.

Основными компонентами системы массового обслуживания любого вида являются:

входной поток поступающих требований или заявок на обслуживание;

дисциплина очереди;

механизм обслуживания.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

,

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

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

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

.

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

,

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

,

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

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

,

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

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

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

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

.

1.4 Теория игр

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

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

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

Важными являются понятия оптимальной стратегии, цены игры, среднего выигрыша. Эти понятия находят отражение в определении решения игры: стратегии Р* и Q* первого и второго игрока соответственно называются их оптимальными стратегиями, а число V -- ценой игры, если для любых стратегий Р первого игрока и любых стратегий Q выполняются неравенства:

где М (Р,Q) означает математическое ожидание выигрыши (средней выигрыш) первого игрока, если первым и вторым игроками избраны соответственно стратегии Р и Q.

Из неравенств следует, в частности, что V = M (P^*,Q^*),т.е. цена игры равна математическому ожиданию выигрыша первого игрока, если оба игрока изберут оптимальные для себя стратегии.

Одним из основных видов игр являются матричные игры, которыми называются парные игры с нулевой суммой (один игрок выигрывает столько, сколько проигрывает другой) при условии, что каждый игрок имеет конечное число стратегий. В этом случае парная игра формально задается матрицей А = (а_ij), элементы которой а_ij определяют выигрыш первого игрока (и соответственно проигрыш второго), если первый игрок выберет i-ю стратегию (i = ), а второй --j-ю стратегию (j = ). Матрица А называется матрицей игры, или платежной матрицей.

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

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

При решении игр с природой используется так же ряд критериев: критерий Сэвиджа, критерий Вальда, критерий Гурвица и др.

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

Критерий минимаксного риска Сэвиджа предполагает, что оптимальной является та стратегия, при которой величина риска в наихудшем случае минимальна.

При использовании критерия «пессимизм -- оптимизма” Гурвица ЛПР выбирает некоторый так называемый “коэффициент пессимизма» q; при q = 1 критерий Гурвица приводится к критерию Вальда («крайнего пессимизма»), а при критерию q=0 «крайнего оптимизма».

1.5 Нелинейное программирование

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

Как известно, общая задача математического программирования формулируется следующим образом: найти вектор X = (x₁, x₂, …, x_n), удовлетворяющий системе ограничений

g_i (x₁, x₂, …, x_n) = b_i , i=1,2, …,k,

(1) g_i (x₁, x₂, …, x_n) ? b_i , i=k+1,k+2, …,m

и доставляющий экстремум функции

(2) Z=f (x₁, x₂, …, x_n)

При этом предполагается, что известны функции g_i (x₁, x₂, …, x_n) и f (x₁, x₂, …, x_n) . Обычно на некоторые переменные x₁, x₂, …, x_n накладывается условие неотрицательности. Кроме того, ограничением может служить условие целочисленности решения для ряда переменных. Если

g_i (x₁, x₂, …, x_n) = , i=1,2,…,m,

и

Z=f (x₁, x₂, …, x_n)=,

где a_ij и С_j - известные константы, то при условии неотрицательности решения получаем задачу линейного программирования. Любую другую задачу математического программирования, не удовлетворяющую условиям (1) и (2) ,будет считаться нелинейной.

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

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

Рассмотрение задач нелинейного программирования начинают с классической задачи оптимизации. Задачи такого рода имеют место, если система (2.1) содержит только уравнения, отсутствуют условия неотрицательности и целочисленности переменных, а функции g_i (x₁, x₂, …, x_n) и f (x₁, x₂, …, x_n) непрерывны и имеют частные производные не ниже второго порядка. Классические методы оптимизации при этом являются теоретическим аппаратом, позволяющим в ряде случаев обосновать разработку соответствующего вычислительного метода.

РИС 8

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

Пример 1. Найти минимальное и максимальное значения сепарабельной функции Z = (x₁ -- 4)² -f- (х₂ -- 6)² при ограничениях

х₁+х₂?1, х₁?0, х₂?0.

2х₁+3х₂?12,

Решение. Область допустимых решений представляет собой много- угольник АВСЕ (рис. 2.1). Если положить Z = Q (Q > 0), то получим уравнение окружности (х₁ -- 4)² + (х₂ -- б)² = Q. С уменьшением (увеличением) Q (квадрата радиуса) значения функции Z соответственно уменьшаются (увеличиваются).

Проводя из точки М как из центра окружности различных радиусов, получаем: минимальное значение функция Z (D) = 196/13 принимает в точке D (24/13; 36/13), в которой окружность касается области решений. Точка D не является угловой, ее координаты находят в результате решения системы уравнений, соответствующих прямым MD и СЕ.

Функция Z имеет два локальных максимума: А (1;0) функция Z (А) = 45, в вершине Е (6; 0) функция Z (Е) =40. Так как Z(A)>Z(Е) то вершина А -- точка глобального максимума.

Пример 2. Пусть область допустимых решений останется прежней, a Z = = (x₁ -- 4)² + (х₂ -- 1)² . Найти минимальное и максимальное значения этой функции.

Решение. Минимальное значение функция принимает в точке М (4; 1) (рис. 2.2): Z (М) = 0. Функция Z имеет два локальных максимума: в вершине Е (6; 0) функция Z (Е) = 5, в вершине С (0; 4) функция Z (С) = 25, причем глобальный максимум достигается в вершине С.

Пример 3. Найти минимальное и максимальное «рачения функции Z = при ограничениях

х₁ * х₂?4,

х₁+ х₂?5,

х₁ ? 7, х₁ ?0, х₂?0.

х₂?6,

Решение. В этом случае (рис. 2.3) область допустимых решений не является выпуклой и состоит из двух отдельных частей. Минимальное значение Функции Z = 17 достигается в точках А (1; 4) и L (4; 1). Функция Z имеет два локальных максимума: в точке D (2/3; 6) функция Z (D) = 328/9 и в точке М (7; 4/7) функция Z (М) = 2417/49. Точка М является точкой глобального максимума.

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

В начале пятилетнего периода работы предприятию выделена сумма в c руб. для приобретения нового оборудования. Стоимость одного комплекта оборудования составляет 10 тыс. руб. Приобретенное оборудование сразу же вступает в строй и может участвовать в производственном процессе. Использование одного комплекта оборудования обеспечивает предприятию за один год прибыль в размере 4 тыс. руб. В конце каждого года предприятие может выделить некоторую долю б (0 ?б ?1) прибыли на расширение производственных мощностей, т.е. на приобретение дополнительно некоторого количества комплектов оборудования, которое будет использоваться в последующие годы. Требуется так планировать расширение производства, чтобы прибыль за пятилетие была максимальной.

Рассматриваемый здесь процесс носит ясно выраженный многошаговый характер. Решением на каждом шаге (в каждом году) является выбранное наилучшим образом значение параметра б - доли прибыли, отчисляемой на приобретение дополнительного оборудования. Пусть б_i (i=1, …, 5) - доля отчисления в i-м году; m_i - количество комплектов оборудования, используемых в производстве i-м году; ц_i - фактическая прибыль предприятия в i-м году.

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

В первый год в производстве будет занято

m₁=c/10000 (3.1)

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

ц₁=4000m₁(1-б₁), (3.2)

где 0 ? б₁ ?1. На отчисленные средства будет приобретено б₁ (4000m₁)/10000=0,4б₁m₁ комплектов оборудования. Во второй год в производстве будет занято

m₂=m₁+0,4б₁m₁= m₁(1+0,4б₁) (3.3)

комплектов, а фактическая прибыль в этом году составит

ц₂=4000m₂-б₂(4000m₂)=4000(1-б₂)m₂, (3.4)

0 ? б₂ ?1,

где б₂(4000m₂) - часть прибыли, отчисляемая на расширение производства. Аналогично получаем

для третьего года

m₃=(1+0,4б₂)m₂, (3.5)

ц₃=4000(1- б₃)m₃; 0 ? б₃ ?1; (3.6)

для четвертого года

m₄=(1+0,4б₃)m₃, (3.7)

ц₄=4000(1- б₄)m₄; 0 ? б₄ ?1; (3.8)

для пятого года

m₅=(1+0,4б₄)m₄, (3.9)

ц₅=4000(1- б₅)m₅; 0 ? б₅ ?1. (3.10)

Суммарную фактическую прибыль предприятия за пятилетку обозначим через f (б₁; б₂; б₃; б₄; б₅). Наша цель найти такие б₁^*; б₂^*; б₃^*; б₄^*; б₅^*, при которых f достигает наибольшего значения.

В соответствии с процедурой метода динамического программирования, основанной на принципе оптимальности, можно, двигаясь от последнего года к предшествующим, построить последовательно оптимальную стратегию отчислений. Для этого обозначим через f (1), f (1-2), f (1-3), f (1-4) суммарную прибыль соответственно за 1-й год; за 1-й и 2-й годы; за 1, 2 и 3-й годы; за 1, 2, 3 и 4-й годы.

Пусть к началу пятого года состояние производственного процесса характеризуется величинами m₅ и f (1-4). Тогда прибыль f за пятилетие можно выразить так: f=f(1-4)+ц₅, а с учетом (3.10) f=f(1-4)+4000(1-б₅)m₅=: f=f(1-4)+4000m₅ - 4000б₅m₅. (3.11)

Из (3.11) видно, что f достигает максимума при б₅=0. Это и есть оптимальное решение (условное) на последнем шаге рассматриваемого пятишагового процесса. Итак, б₅^*=0. При этом условии из (3.11) получаем

f = f (1-4)+4000m₅. (3.12)

Оптимизируем теперь предпоследний шаг, т.е. переходим к началу четвертого года, когда состояние производственного процесса характеризуется величинами m₄ и f (1-3). Прибыль за четыре первых года равна

f (1-4)= f(1-3)+ц₄. (3.13)

Принимая во внимание условное оптимальное решение б₅^*=0, принятое для пятого года, используем равенство (3.12), которое с учетом равенств (3.13), (3.9) и (3.8) преобразуем следующим образом:

f=f(1-3)+8000m₄-2400б₄m₄. (3.14)

Для выбора оптимального решения на данном шаге воспользуемся принципом оптимальности: выбор б₄ будем производить на основе равенства (3.14), в котором нашло отражение условное оптимальное решение, выбранное ранее для последнего шага. Из (3.14) видно, что чем больше значение б₄, тем меньше величина целевой функции f. Следовательно, для достижения максимума f надо взять наименьшее допустимое значение б₄. Таковым является б₄^*=0. Это и есть условное оптимальное решение, обеспечивающее оптимальное завершение процесса планирования. При б₄^*=0 целевая функция f, описывающая суммарную прибыль, равна

f=f(1-3)+8000m₄. (3.15)

Теперь перейдем к началу третьего года, характеризующегося величинами m₃ и f(1-2). Учитывая очевидное равенство f(1-3)=f(1-2)+ц₃ и используя равенства (3.15), а затем (3.6) и (3.7), исходя из ранее принятых условных оптимальных решений, получаем

f=f(1-2)+12000m₃-800б₃m₃. (3.16)

Пользуясь принципом оптимальности, определяем условное оптимальное решение для третьего года. Анализируя с этой целью (3.16), убеждаемся, что наибольшее значение f достигается при б₃^*=0. Тогда из (3.16) имеем

f=f(1-2)+12000m₃. (3.17)

Продолжая продвигаться к началу процесса, замечаем, что в начале второго года производственный процесс характеризуется величинами m₂ и f(1). По аналогии с предыдущим можно записать: f(1-2)= f(1)+ ц₂. Используя (3.17), только что полученное равенство, (3.5) и (3.4), находим

f=f(1)+16000m₂+800б₂m₂. (3.18)

Из равенства (3.18) видно, что условно-оптимальным на втором году будет решение б₂^*=1, так как при нем f достигает максимума. Тогда из (3.18) получаем

f=f(1)+16800m₂. (3.19)

Остается проанализировать пятый от конца шаг, т.е. первый год планового периода. Из (3.2) ясно, что

f(1)=ц₁=4000(1-б₁)m₁. (3.20)

Чтобы обеспечить оптимальное продолжение процесса, необходимо, основываясь на принципе оптимальности, использовать результаты предшествующей оптимизации, выраженные равенством (3.19). Учитывая (3.20) и (3.3), получаем

f=20800m₁+2720б₁m₁. (3.21

Из (3.21) видно, что условно-оптимальным решением на первом году будет б₁^*=1, так как при этом f достигает максимума:

f^*=23520m₁. (3.22)

Таким образом, найдены условно-оптимальные решения на всех пяти шагах (годах), определены выражения для соответствующих им максимальных прибылей (3.12), (3.15), (3.17) и (3.22). Остается проследить развитие процесса в прямом направлении и прочитать оптимальную стратегию: б₁^*=б₂^*=1; б₃^*=б₄^*=б₅^*=0. Из (3.22) и (3.1) получаем f^*=2,352c.

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

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

Основной ответ, полученный в результате решения данной задачи, состоит в следующем: прибыль предприятия за пятилетие будет максимальной, если в первые два года всю получаемую прибыль отчислять на расширение производства, а в последующие три года отчислений не производить. Какие же побочные результаты можно извлечь из решений данной задачи? Если в равенстве (3.18) положить б₂=0, а в равенстве (3.20) принять б₁=0 (это будет означать, что и в первые два года отчисление от прибыли не производится), то получим f⁰=20000m₁=2c. Сравнивая это значение с максимальным f^*=2,352c, приходим к выводу6 если бы не предусматривалось расширение производства, то прибыль f⁰ предприятия была бы на 35,2% меньше прибыли f*, которую оно получит, применяя оптимальную стратегию отчислений. Полагая в формулах (3.3), (3.5), (3.7) и (3.9) б₁=б₂=1; б₃=б₄=б₅=0, находим m₂=1,4m₁; m₃=m₄=m₅=1,96 m₁. отсюда заключаем, что применение оптимальной стратегии приводит к тому, что в конце пятилетия производственная мощность предприятия (по данному виду оборудования) на 96% больше первоначальной. Таковы побочные результаты решения задачи.

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

Список литературы

1. Браславец Е.М. Экономико-математические методы в организации и планировании сельскохозяйственного производства. КИЕВ. - УРОЖАЙ.1968 г.

2. В.В. Федосеев. Экономико - математические методы и прикладное моделирование - М.:ЮНИТИ,2002.-391 с.

3. Ермолов В.И. Общий курс высшей математики для экономистов. М.- ИНФРА-М.2004 г.

4. Котов А.Н. Математическое моделирование макроэкономических процессов - Л.: ЛГУ, 1980

5. Кравченко Р.Г., Попов И.Г., Толпекин С.З. Экономико-математические методы в организации и планировании сельскохозяйственного производства. М.-КОЛОС.1973 г.

6. Красс М.С., Чупрынов Б.П. Основы математики и её приложения в экономическом образовании. М.-ДЕЛО.2002 г.

7. Кузнецов А.В., Холод Н.И. Математическое программирование. МИНСК - ВЫСШАЯ ШКОЛА.1984 г.

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

9. Л.Л.Терехов. Экономико-математические методы - М.: Статистика-1972

10. Лотов А.В. Введение в экономико-математическое моделирование. М.-НАУКА.1984 г.

11. Полунин И.Ф. Курс математического программирования. Минск, 1975г.

12. Ю.Г.Семенов. Основы экономико-математического моделирования: М.: Высшая школа, 1976