Реферат: Экономико-математические методы и прикладные модели
МОСКОВСКИЙ КИНОВИДЕОИНСТИТУТ (филиал)
САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТАКИНО И ТЕЛЕВИДЕНИЯ
КУРСОВАЯ РАБОТА
«Экономико-математические методы и прикладные модели»
Выполниластудентка 3-го курса
(ускоренный)
ЮщакЕ.В.
ПреподавательМанцев А.П.
г. Москва, 2002
I. Введение.
Предметом изучения дисциплины являются количественныехарактеристики экономических процессов, протекающих в промышленномпроизводстве, изучение их взаимосвязей на основе экономико-математическихметодов и моделей. Эти модели линейного и нелинейного программирования, моделиисследования операций, модели массового обслуживания.
Важное место отводится экономико-математическиммоделям в ценообразовании. Особое внимание уделяется методам и моделямпрогнозирования конъюнктуры рынка и определения цен, моделям и методам анализаинвестиционных проектов, моделям в управлении финансами.
Немалое место отводится моделям оптимальногоотраслевого и регионального регулирования – экономико-математическим моделямпроекта развития отдельных отраслей промышленности. Это такие важные модели,как вариантная, транспортно-производственная, модель расчета топливного балансарегиона.
Основным понятием является понятие математическоймодели. В общем случае слово модель – это отражение реального объекта. Такоеотражение объекта может быть представлено схемой, эскизом, фотографией, модельюописательного характера в виде графиков и таблиц и т.д. Математическая модель –это система математических уравнений, неравенств, формул и различныхматематических выражений, описывающих реальный объект, составляющие егохарактеристики и взаимосвязи между ними. Процесс построения математическоймодели называют математическим моделированием. Моделирование и построениематематической модели экономического объекта позволяют свести экономическийанализ производственных процессов к математическому анализу и принятиюэффективных решений.
Поскольку нами изучаются экономические задачи, то истроятся экономико-математические модели, включающие:
1) выбор некоторого числа переменныхвеличин для формализации модели объекта;
2) информационную базу данныхобъекта;
3) выражение взаимосвязей,характеризующих объект, в виде уравнений и неравенств;
4) выбор критерия эффективности ивыражение его в виде математического соотношения – целевой функции.
Итак, для принятия эффективных решений в планировании и управлениипроизводством необходимо экономическую сущность исследуемого экономическогообъекта формализовать экономико-математической моделью, т.е. экономическуюзадачу представить математически в виде уравнений, неравенств и целевой функциина экстремум (максимум или минимум) при выполнении всех условий на ограниченияи переменные.
II.Основные понятия моделирования.
2.1. Общие понятия и определениемодели.
Содержанием любойэкономико-математической модели является выраженная в формально-математическихсоотношениях экономическая сущность условий задачи и поставленной цели. Вмодели экономическая величина представляется математическим соотношением, но невсегда математическое соотношение является экономическим. Описаниеэкономических условий математическими соотношениями – результат того, чтомодель устанавливает связи и зависимости между экономическими параметрами иливеличинами.
По содержанию различаютэкономико-математические и экономико-статистические модели. Различие междуними состоит в характере функциональных зависимостей, связывающих их величины.Так, экономико-статистические модели связаны с показателями, сгруппированнымиразличными способами. Статистические модели устанавливают зависимость междупоказателями и определяющими их факторами в виде линейной и нелинейной функции.Экономико-математические модели включают в себя систему ограничений, целевуюфункцию.
Система ограничений состоит из отдельных математических уравнений или неравенств, называемыхбалансовыми уравнениями или неравенствами.
Целевая функция связываетмежду собой различные величины модели. Как правило, в качестве цели выбираетсяэкономический показатель (прибыль, рентабельность, себестоимость, валоваяпродукция и т.д.). Поэтому целевую функцию иногда называют экономической,критериальной. Целевая функция – функция многих переменных величин и можетиметь свободный член.
Критерии оптимальности –экономический показатель, выражающийся при помощи целевой функции через другиеэкономические показатели. Одному и тому же критерию оптимальности могутсоответствовать несколько разных, но эквивалентных целевых функций. Модели содной и той же системой ограничений могут иметь различные критерии оптимальностии различные целевые функции.
Решениемэкономико-математической модели, или допустимым планом называется наборзначений неизвестных, который удовлетворяет ее системе ограничений. Модельимеет множество решений, или множество допустимых планов, и среди них нужнонайти единственное, удовлетворяющее системе ограничений и целевой функции.Допустимый план, удовлетворяющий целевой функции, называется оптимальным. Средидопустимых планов, удовлетворяющих целевой функции, как правило, имеетсяединственный план, для которого целевая функция и критерий оптимальности имеютмаксимальное или минимальное значение. Если модель задачи имеет множествооптимальных планов, то для каждого из них значение целевой функции одинаково.
Еслиэкономико-математическая модель задачи линейна, то оптимальный план достигаетсяв крайней точке области изменения переменных величин системы ограничений. Вслучае нелинейной модели оптимальных планов и оптимальных значений целевойфункции может быть несколько. Поэтому необходимо определять экстремальные планыи экстремальные значения целевой функции. План, для которого целевая функциямодели имеет экстремальное значение, называют экстремальным планом, илиэкстремальным решением.
Для нелинейных моделейиногда существуют экстремальные значения целевой функции, а для линейныхмоделей экстремальных планов и экстремальных значений целевой функции быть неможет.
Таким образом, дляпринятия оптимального решения любой экономической задачи необходимо построитьее экономико-математическую модель, по структуре включающую в себе системуограничений, целевую функцию, критерий оптимальности и решение.
Методика построенияэкономико-математической модели состоит в том, чтобы экономическую сущностьзадачи представить математически, используя различные символы, переменные ипостоянные величины, индексы и другие обозначения.
Все условия задачинеобходимо записать в виде уравнений или неравенств. Поэтому, в первую очередьнеобходимо определить систему переменных величин, которые могут для конкретнойзадачи обозначить искомый объем производства продукции на предприятии,количество перевозимого груза поставщиками конкретным потребителям.
2.2.Постановка задач оптимизации
В общем виде задачаоптимизации, или задача определения экстремума, ставится следующим образом.
Пусть заданы:
функция f(X), определенная на множестве O Í RN<sup/>;
множество D Í RN.
Найти точку Y = (y1, y2,..., yN) Î D, в которойфункция f (X) достигает экстремального (минимального или максимального)значения, т.е.
f(X) = extrf(X) и Y Î D.
Функция f(X) называется целевой функцией, переменные X – управляемыми переменными, D – допустимым множеством и любой наборзначений Y управляемых переменных,принадлежащий D (Y Î D), — допустимымрешением задачи оптимизации.
Понятно, что искомаяточка Y, в которой f(X) достигаетсвоего экстремума, должна принадлежать пересечению области определения O функции f(X) и допустимогомножества D (YÎ O Ç D). Если множества O и D совпадают со всем пространством RN<sup/>(O = D = RN), то такая задача называется задачейна безусловный экстремум. Если хотя бы одно из множеств O или D является собственным подмножеством пространства RN<sup/>(O Ì RN, D Ì RN) или множества O и D пересекаются (O Ç D ¹ Æ), то такая задача называется задачей на условный экстремум, в противномслучае (O Ç D = Æ) точка экстремума Y несуществует. Подчеркнем один частный случай: если множества O и D пересекаются в одной точке Y, то эта точка Yявляется единственным допустимым решением.
Обычно в задаче условногоэкстремума задается не само допустимое множество решений D, а система соотношений, егоопределяющая,
yj<sub/>(x1, х2, х<sub/>N) £ (=, ³) 0, j = 1, 2, … М,
т.е.
D = {X: yj (X) £ (=, ³) 0, j = 1, 2,…, M} Í RN,
или множество D может одновременно задаваться какв явном виде, т.е. допустимое решение Х должно принадлежать некоторой области P Ì RN, так и системой ограничений.
III. Методы линейного программирования.
3.1. Общая и типовая задача влинейном программировании.
Оптимизационная задача –это экономико-математическая задача, которая состоит в нахождении оптимального(максимального или минимального) значения целевой функции, причем значенияпеременных должны принадлежать некоторой области допустимых значений.
В самом общем виде задачаматематически записывается так:
U = f(X) ® max; X Î W,
Где X = (Х1, Х2,…, Хn);
W – область допустимых значенийпеременных Х1, Х2,…, Хn;
f(X) – целевая функция.
Для того, чтобы решитьзадачу оптимизации, достаточно найти ее оптимальное решение, т.е. указать X() Î W такое, что f(X()) ³ f(X), при любом X Î W, или для случая минимизации — что f(X()) ≤ f(X), при любом X Î W.
Оптимизационная задачаявляется неразрешимой, если она не имеет оптимального решения. В частности,задача максимизации будет неразрешима, если целевая функция f(X) не ограничена сверху на допустимом множестве W.
Методы решенияоптимизационных задач зависят как от вида целевой функции f(X), так и от строения допустимого множества W. Если целевая функция в задачеявляется функцией n переменных, тометоды решения называют методами математического программирования.
В математическомпрограммировании принято выделять следующие основные задачи в зависимости отвида целевой функции f(X) и от области W:
· задачи линейногопрограммирования, если f(X) и W линейны;
· задачицелочисленного программирования, если ставится условие целочисленностипеременных Х1, Х2,…, Хn;
· задачи нелинейногопрограммирования, если форма f(X) носит нелинейный характер.
Задачилинейного программирования.
Задачей линейногопрограммирования называется задача исследования операций, математическая моделькоторой имеет вид:
f(X) = å СjXj ® max(min);
å aij xj = bi, iÎI, IÍM = {1, 2,…m};
å aij xj £ bi, iÎM;
Xj³0, jÎJ, JÍN = {1, 2,…n}.
При этом система линейныхуравнений и неравенств, определяющая допустимое множество решений задачи W, называется системой ограниченийзадачи линейного программирования, а линейная функция f(X) называетсяцелевой функцией или критерием оптимальности.
Любую задачу линейногопрограммирования можно свести к задаче линейного программирования вканонической форме. Для этого в общем случае нужно уметь сводить задачумаксимизации к задаче минимизации; переходить от ограничений неравенств к ограничениямравенств и заменять переменные, которые не подчиняются условиюнеотрицательности. Максимизация некоторой функции эквивалентна минимизации тойже функции, взятой с противоположным знаком, и наоборот.
Правило приведения задачилинейного программирования к каноническому виду состоит в следующем:
1) если в исходной задачетребуется определить максимум линейной функции, то следует изменить знак иискать минимум этой функции;
2) если в ограниченияхправая часть отрицательна, то следует умножить это ограничение на -1;
3) если среди ограниченийимеются неравенства, то путем введения дополнительных неотрицательныхпеременных они преобразуются в равенства;
4) если некотораяпеременная Хk не имеет ограничений по знаку, тоона заменяется (в целевой функции и во всех ограничениях) разностью междудвумя новыми неотрицательными переменными::
Xk = X`k – Xl, гдеl – свободный индекс, X`k ³ 0, Xk ³ 0.
3.2.Постановка задачи линейного программирования
Под термином «транспортные задачи»понимается широкий круг задач не только транспортного характера. Общим для нихявляется, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), но n потребителям этих ресурсов.
На автомобильном транспорте частовстречаются следующие задачи, относящиеся к транспортным:
· прикреплениепотребителей ресурса к производителям;
· привязка пунктовотправления к пунктам назначения;
· взаимная привязкагрузопотоков прямого и обратного направлений;
· отдельные задачиоптимальной загрузки промышленного оборудования;
· оптимальноераспределение объемов выпуска промышленной продукции междузаводами-изготовителями.
Транспортным задачам присущиследующие особенности:
· распределениюподлежат однородные ресурсы;
· условия задачиописываются только уравнениями;
· все переменныевыражаются в одинаковых единицах измерения;
· во всехуравнениях коэффициенты при неизвестных равны единице;
· каждаянеизвестная встречается только в двух уравнениях системы ограничений.
Транспортные задачи могут решаться симплекс-методом.
3.3.Решение транспортной задачи
Мощности
постав-
щиков
140
Мощности потребителей U i 18 15 32 45 30 30 10 7/15 14 8/5 7/10 40 12 8 10 8/40 15 25 6/18 10 10 12 14/7 -7 45 16 10 8/32 12 16/13 -9 Vj -1 7 -1 8 7Начальное распределение выберем по методу наименьшихстоимостей. Порядок заполнения клеток: (3,1), (1,2), (4,3). (2,4), (1,5),(1,4), (3,5), (4,5)
Суммарные затраты:
f(x) = 6´18+7´15+8´32+8´5+8´40+7´10+14´7+16´13=1107
Рассмотрим процесс нахождения потенциалов для данногораспределения.
Положим, Ui=0 Þ V2=U1+C12=7; V5=U1+C15=7=U3+14=U4+16 Þ U3= -7, U4=-9; V3=U4+C43= -1; V4=U2+8=U1+8 Þ U2=U1=0; V4=8.
Найдем оценки: dij=(Ui+cij)-Vj:
11 0 15 0 0
(dij) = 13 1 11 0 8
0 -4 4 -3 0
8 -6 0 -5 0
Данный план не является оптимальным,т.к. есть отрицательные оценки.
Построим контур перераспределения дляклетки (4,2). Наименьшая поставка в вершине контура со знаком “-” равна 13,поэтому проведем перераспределение поставок, уменьшив поставки в клетках сознаком “-” на 13 и увеличив поставки в клетках со знаком “+” на 13. результатыпоставлены в таблице 2.
Мощности
постав-
щиков
140
Мощности потребителей U i 18 15 32 45 30 30 10 7/2 14 8/5 7/23 40 12 8 10 8/40 15 25 6/18 10 10 12 14/7 -7 45 16 10/13 8/32 12 16 -3 Vj -1 7 5 8 7Суммарные затраты:
f(x) = 6´18+7´2+10´13+8´32+8´5+8´40+7-23+14-7=1127
Положим U1=0
V2 = U1+C12=7=U4+10 Þ U4 = -3
V3 = U4+8=5; V4=U1+8=8=U2+8 Þ U2=0
V5 = U1+7= 7 = U3+14 Þ U3= -7
V1 = U3+6= -1
dij = (Ui+Cij)-Vj
9 0 9 0 0
(dij) = 11 1 5 0 8
0 -3 -2 -3 0
14 0 0 1 6
Наличие отрицательных оценоксвидетельствует о том, что план не является оптимальным. Построим контурперераспределения для клетки (3,2). Наименьшая поставка в вершине контура сознаком “-” равна 2. Произведем перераспределение поставок. Результатыпредставим в таблице 3.
Мощности
постав-
щиков
140
Мощности потребителей U i 18 15 32 45 30 30 10 7 14 8/5 7/25 40 12 8 10 8/40 15 25 6/18 10/2 10 12 14/5 -7 45 16 10/13 8/32 12 16 -7 Vj -1 7 5 8 7Суммарные затраты:
f(x) = 6´18+10´2+10´13+8´32+8´5+8´40+7´25+14´7=1119
Положим, U1=0 Þ V4=8, V5=7; V4=U2+8 Þ U2=0
V5 = U3+14 Þ U3= 7-14= -7; V1= -7+6= -1; V2=-7+10= +3
V2=U4+10 Þ U4=3-10= -7; v3= -7+8=1
9 4 13 0 0
(dij) = 13 5 9 0 8
2 0 2 -3 0
10 0 0 -3 2
Наличие отрицательных оценоксвидетельствует о том, что план не является оптимальным. Построим контурперераспределения для клетки (3,4).
Наименьшая поставка в клетке сознаком “-” равна 5. Произведем перераспределение поставок результаты представим в таблице 4.
Мощности
постав-
щиков
140
Мощности потребителей U i 18 15 32 45 30 30 10 7 14 8 7/30 40 12 8 10 8/40 15 25 6/18 10/2 10 12/5 14 -4 45 16 10/13 8/32 12 16 -4 Vj 2 +6 4 8 7Суммарные затраты:
f(x) = 7´30+8´40+6´18+10´2+12´5+10´13+8´32=1104
U1=0 Þ V5= 7; U2=0 Þ V4=8=U3+12 Þ U3=-4 Þ
V1= 6-4=2, V2=10-4=+6=U4+10; V3= -4+8= +4
8 1 10 0 0
(dij) = 10 2 6 0 8
0 0 2 0 3
10 0 0 0 5
Матрица оценок (dij) не содержат отрицательных величин Þ данный план является оптимальным,т.к. С34 = 0, а клетка (3,4) не является запятой, то данный план не являетсяединственным. Стоимость перевозок по этому плану, как было рассчитано ранее,равна f(x) = 1104.
3.6.Симплекс-метод решения задач линейного программирования.
Симплекс-метод позволяет отказатьсяот метода перебора при решении задач линейной оптимизации, является основнымчисленным методом решения задач линейного программирования и позволяет заменьшее число шагов, чем в методе перебора, получить решение.
Реализация алгоритма симплекс-метода.
1. Записать задачу в канонической форме:заменить все ограничения-неравенства с положительной правой;
2. Разделить переменные на базисные исвободные: перенести свободные переменные в правую частьограничений-неравенств.
3. Выразить базисные переменные черезсвободные: решить систему линейных уравнений (ограничений-неравенств) –относительно базисных переменных;
4. Проверить неотрицательность базисныхпеременных: убедиться в неотрицательности свободных членов в выражениях длябазисных переменных. Если это не так, вернуться к пункту 2, выбирая другойвариант разделения переменных на базисные и свободные.
5. Выразить функцию цели через свободныепеременные: базисные переменные, входящие в функцию, выразить через свободныепеременные;
6. Вычислить полученное базисное решениеи функцию цели на нем: приравнять к 0 свободные переменные;
7. проанализировать формулу функциицели: если все коэффициенты свободных переменных положительны (отрицательны),то найденное базисное решение будет минимально (максимально) и задача считаетсярешенной;
8. Определить включаемую в базис иисключаемую из базиса переменные: если не все коэффициенты при свободныхпеременных в функции цели положительны (отрицательны), то следует выбратьсвободную переменную, входящую в функцию цели с максимальным по модулюотрицательным (положительным) коэффициентом, и увеличивать ее до тех пор, покакакая-нибудь из базисных переменных не станет равной 0. Свободную переменнуюрассматриваем как новую базисную переменную (включаемую в базис), а базиснуюпеременную рассматриваем как новую базисную переменную (исключаемую из базиса);
9. Используя новое разделение переменныхна базисное и свободное, вернуться к пункту 3 и повторять все этапы до тех пор,пока не будет найдено оптимальное решение.
В заключение отметим, что определениеоптимального решения распадается на два этапа:
· Нахождениекакого-либо допустимого решения с положительным свободным членом;
· Определениеоптимального решения, дающего экстрему целевой функции.
IV.Методы нелинейного программирования.
4.1. Основные понятия, постановка и методы решения задачи нелинейногопрограммирования.
Нелинейноепрограммирование (планирование) – математические методы отыскания максимума илиминимума функции при наличии ограничений виде неравенств или уравнений.Максимизируя (минимизируя) функция представляет собой принятый критерийэффективности решения задачи, соответствующий поставленной цели. Он носитназвание целевой функции. Ограничение характеризует имеющиеся возможностирешения задачи.
Целевая функция или хотябы одно из ограничений нелинейное (т.е. на графиках изображается непрямыми-кривыми-линиями) существо решения задач нелинейного программированиязаключается в том, чтобы найти условия, обращающие целевую функцию в минимумили максимум. Решение, удовлетворяющее условию задачи и соответствующеенамеченной цели, называется оптимальным планом. Нелинейное программированиеслужит для выбора наилучшего плана распределения ограниченных ресурсов в целяхрешения поставленной задачи. В общем виде постановка задачи нелинейногопрограммирования сводится к следующему. Условия задачи представляются спомощью системы нелинейных уравнений или неравенств, выражающих ограничение,налагаемое на использование имеющихся ресурсов.
Z1(X1, X2,...,Xn) ³ 0;
Z2(X1, X2,...,Xn) ³ 0;
...................................
Zm(X1,X2,...,Xn) ³ 0;
при Xi ³ 0,
где Z1, Z2,…,Zm –соответствующие функции, характеризующие условие решения поставленной задачи(ограничения); Хi – искомыевеличины, содержащие решение задачи.
Целевая функция задаетсяв виде:
y = f (X1, X2,…, Xn).
Причем по крайней мереодна из функций y, Z1, Z2,…, Zm –нелинейная.
Методами нелинейногопрограммирования решаются задачи распределения неоднородных ресурсов.
Пусть имеется m разнородных ресурсов, которыепредполагается реализовать для бизнеса в n регионах страны.
Известны оценочныевозможности (вероятности) начать бизнес в j-м регионе (Pj), атакже эффективности использования i-го ресурса в n-м регионе (wij).
Распределение ресурсов порегионам характеризуется так называемым параметром управления (hij):
hij = 0, если i-й ресурс не направляется в j-й регион,
1, если i-й ресурс направляется в j-й регион.
Необходимо распределитьресурсы по регионам таким образом (выбирать такие значения hij), чтобы величина полной вероятностидостижения цели Рц была максимальной:
Рц = å Pj [1 — P (1-hijwij] = max.
Должно выполняться такжеограничение
S hij = 1, i = 1,2,…m
Ограничение означает, чтокаждый из m ресурсов обязательно долженназначаться в какой-либо из регионов.
Динамическоепрограммирование (планирование)
Динамическоепрограммирование (планирование) служит для выбора наилучшего плана выполнениямногоэтапных действий. Для многоэтапных действий характерно протекание вовремени. Кроме действий, естественно носящих многоэтапный характер (например,перспективное планирование), в ряде задач прибегают к искусственномурасчленению на этапы, с тем, чтобы сделать возможным применение методадинамического программирования.
В общем виде постановказадачи динамического программирования сводится к следующему:
Имеется некотораяуправляемая операция (целенаправленное действие), распадающаяся (естественноили искусственно) на mшагов – этапов. На каждом шаге осуществляется распределение и перераспределениеучаствующих в операции с целью улучшения ее результата в целом. Этираспределения в динамическом программировании называются управлениями операциейи обозначаются буквой U.Эффективность операции в целом оценивается тем же показателем, что иэффективность ее управления W (U).
При этом эффективностьуправления W(U) зависит от всей совокупности управлений на каждом шагеоперации:
W = W(U) = W(U1, U2,..., Um).
Управление, при которомпоказатель W достигает максимума, называетсяоптимальным управлением. Оптимальное управление обозначается буквой U.
Оптимальное управлениемногошаговым процессом состоит из совокупности оптимальных шаговых управлений:
U = (U1, U2,..., Um).
Задача динамическогопрограммирования – определить оптимальное управление на каждом шаге Ui (i = 1, 2, …, m) и,тем самым, оптимальное управление всей операцией в целом.
В большинствепрактических задач принимается, что показатель эффективности операции W в целом представляет собой суммуэффективности действий на всех этапах (шагах) операции:
W = å wi,
где wi – эффективность операции на i-м шаге.
При этом в случаеоптимального управления
W = max åwi
Существо решениядинамического программирования заключается в следующем:
- Оптимизацияпроизводится методом последовательных приближений (итераций) в два круга; вначале от последнего шага операции к первому, а затем наоборот от первого кпоследнему;
- На первом круге,идя от последующих шагов к предыдущим, находится так называемое условноеоптимальное управление;
- Условноеоптимальное управление выбирается таким, чтобы все предыдущие шаги обеспечивалимаксимальную эффективность последующего шага, иными словами, на каждом шагеимеется такое управление, которое обеспечивает оптимальное продолжениеоперации; этот принцип выбора управления называется принципом оптимальности;
- Так продолжаетсядо первого шага, но поскольку первый шаг не имеет предыдущего, то полученноедля него условное оптимальное управление теряет свой условный характер истановится просто оптимальным управлением, которое мы ищем;
- Второй кругоптимизации начинается с первого шага, для которого оптимальное управлениеизвестно.
Имея для всех шагов посленего условное оптимальное управление, мы знаем, что необходимо делать на каждомпоследующем шаге. Это дает нам возможность последовательно переходить отусловных к оптимальным управлениям дл всех последующих шагов, что обеспечиваетоптимальность операции в целом.
Пусть имеется m типов различных грузов, которыминеобходимо загрузить транспортное средство таким образом, чтобы общая ценностьгруза W была максимальной. Ценность грузаявляется функцией отгрузоподъемности транспортного средства:
W = f (G)
Известны массы грузов i-го типа Рi и их стоимости Ci.
Необходимо загрузитьтранспортное средство таким образом, чтобы общая ценность груза быламаксимальной:
W = fm(G) =max å xiCi,
где xi – число предметов груза i-го типа, загружаемых в транспортноесредство; xi выступает здесь в качествеуправления (Ui=xi)
Ограничивающими условиямиявляются:
å xi Pi £ G
xi = 0, 1, 2...
Первое условие требует,чтобы общая масса груза не превышала грузоподъемности транспортного средства, авторое – чтобы предметы, составляющие груз различных типов, были неделимы.
Понятие критерияоптимальности
Формулировка критериев экономическихсистем является необходимой предпосылкой оптимизации плановых решений. В общемслучае под критерием оптимальности понимается признак, на основании которогопроизводится оценка, сравнение альтернатив, классификация объектов и явлений.Критерий оптимальности функционирования экономической системы – это один извозможных критериев (признаков) ее качества, а именно тот признак, по которомуфункционирование системы признается наилучшим из возможных вариантов еефункционирования. В сфере принятия экономических решений критерий оптимальности– это показатель, выражающий предельную меру экономического эффектапринимаемого хозяйственного решения для сравнительной оценки возможных решенийвыбора наилучшего из них. Наиболее часто используется максимум прибыли илиминимум затрат.
Критерий оптимальностиобычно носит количественный характер и показывает, насколько один из вариантовлучше ли хуже другого. Порядковый критерий определяет лишь то, что один вариантлучше или хуже другого. Математической формой критерия оптимальности вэкономико-математических моделях является целевая функция, экстремальноезначение которой характеризует предельно допустимую эффективность деятельностимоделируемого объекта.
Если за классифицирующийпризнак принять уровень общности, то для экономической системы существуютглобальный критерий оптимального развития в масштабе Земли,социально-экономический критерий, а также «глобальный» (обобщенный) и локальныйкритерий оптимальности в частных системах моделей.
Если за классифицирующийпризнак взять математическую формулировку, то критерии подразделяются наскалярные и векторные, аддитивные и мультипликативные, интегральные критерии вовременном аспекте и интегральные в пространственном аспекте и др.
Возможна классификациямоделей по временному аспекту, по способам формирования критериев, по типуприменяемых измерителей, по способам использования критериев.
Сущность глобального илокального критериев оптимальности.
Чаще всего термин «глобальный»применяется либо по отношению к критерию одноуровневой модели, либо поотношению к критерию «верхней» модели многоуровневой системы моделей. Впоследнем случае, наряду с глобальным, фигурируют локальные критерии моделейнижних уровней, отражающие интересы отдельных хозяйственных звеньев, социальныхгрупп.
Разделение критериев наглобальный и локальный может быть отнесено к любой иерархически построеннойсистеме моделей, например модели отрасли или предприятия.
Глобальному критериюможет быть дана словесная формулировка, а для решения практических задачпланирования и управления такая формулировка детализируется и представляется ввиде совокупности более конкретных локальных критериев. Математическиглобальный критерий принято формулировать в виде скалярной целевой функции,которая обобщенно выражает все многообразие целей или в виде векторной функции,представляющей собой набор несводимых друг к другу частных целевых функций.
Большинствомногоуровневых систем имеют два уровня: верхний и нижний. Система моделейпроизводственной программы предприятия включает в себя модели расчетаобщезаводских показателей и показателей отдельных цехов. При формированииобобщенных критериев должны учитываться и местные (частные интересы), алокальные критерии – подчинены обобщенному.
Сложность системы целейобъясняется многообразием задач общественного развития и развития систем, атакже тем, насколько обширны и интенсивны внешние связи данной системы.
Предприятие являетсяэлементом более общих систем: отрасли промышленности, эк5ономического региона.Поэтому деятельность предприятия оценивается в рамках любой из этих общихсистем по соответствующим показателям. С этой точки зрения предприятие должнонаилучшим образом соответствовать целям внешней системы. С другой стороны,само предприятие – сложная система, элементами которой являются коллективы егоработников (бригады, отделы, службы, участки и т.д.) и отдельные индивидуумы.Следовательно, деятельность предприятия должна быть направлена на наилучшееобеспечение интересов коллектива и его работников. Система критериев оптимальностидеятельности предприятия включают объемы выпуска основных типов продукциивысшей категории качества, производительность труда, себестоимость продукции,фонд заработной платы.
Система критериевотраслевой системы включает удовлетворение общественных потребностей производимой продукции, экономию ресурсов, внедрение достиженийнаучно-технического прогресса, обеспечение надежности выполнения плановыхзаданий. Внешние связи отраслевых систем, а значит, и комплексы их целей,усложняются фактором времени, пространственной организацией, сочетаниемразличных подходов и аспектов планирования.
Множественность целейразвития систем существенно осложняет планирование, особенно, если целиразнонаправленные, и приближение к одним целям удаляет систему от достижениядругих. Таким образом возникает задача их согласования. Отыскание наилучшихрешений по нескольким критериям называется многокритериальной или векторнойоптимизацией.
Векторнаяоптимизация
Математическая формулировка задачивекторной оптимизации:
Пусть X = {x1,…, x N} (j = 1,N) — векторпеременных, обычно предполагается неотрицательность вектора переменных X³0, функциональная взаимосвязьпеременных устанавливается определенными соотношениями, на которыенакладываются ограничения:
gi (X)£bi (i = 1,M).
Функционирование системы оцениваетсяопределенными критериями, записываемыми в виде целевых функций fr(X) (r = 1,K). Множество критериев можнопредставить в виде векторной целевой функции
F(X) = {f1(X),…>fr(X)}.
Чтобы минимизировать частный критерийfr(X), достаточно максимизировать -fr(X), так как min fr(X)=-max (-fr(X)). Поэтому вдальнейшем предполагается, что каждая компонента векторного критериямаксимизируется. Задача многоцелевой оптимизации записывается как векторнаязадача математического программирования (ВЗМП)
F(X)= {f1(X),…>fr(X)} (max),
gi (X)£bi (i = 1,M),
X³0.
Будем рассматривать ВЗМПдля случая, когда точки оптимума X*r(r=1,K),полученные при решении задачи по каждому критерию fr(r=1,K) не совпадают (случай их совпадениявстречается крайне редко и такая задача не представляет интереса). Поэтому сматематической точки зрения задача является некорректной, так как если один изкритериев достигает своего оптимума, то улучшение по другим компонентамвекторного критерия невозможно. Отсюда вытекает, что решением ВЗМП может бытьтолько какое-то компромиссное решение.
Особенностью задачвекторной оптимизации является наличие в области допустимых значений областикомпромиссов, в которой невозможно одновременное улучшение всех критериев.Принадлежащие области компромиссов планы называют эффективными, илиоптимальными по Парето (по имени итальянского экономиста, впервыесформулировавшего проблему векторной оптимизации и принцип оптимальностирешения).
Понятиепредпочтительности плана. План X° нехуже плана X`, если
fr(X°)³ fr(X`) (r = 1,K). Если среди этих неравенств хотя быодно строгое, то план X° предпочтительнее (лучше) X`, т.е.при переходе от X° к X`значение ни одного критерия не ухудшилось и хотя бы одногокритерия улучшилось. План X°оптимален по Парето (эффективен), если он допустим и не существует другогоплана X`, для которого fr(X°)³ fr(X`) (r = 1,K), и хотя бы для одного критериявыполняется строгое неравенство.
К общей формулировкемногокритериальной задачи могут сводиться задачи различного содержания, которыеможно подразделить на четыре типа.
1. Задачиоптимизации на множестве целей, каждая из которых должна быть учтена при выбореоптимального решения. Примером может служить задача составления плана работыпредприятия, в которой критериями служит ряд экономических показателей.
2. Задачиоптимизации на множестве объектов, качество функционирования каждого из которыхоценивается самостоятельным критерием. Если качество функционирования каждогообъекта оценивается несколькими критериями (векторным критерием), то такаязадача называется многовекторной. Примером может служить задача распределениядефицитного ресурса между несколькими предприятиями. Для каждого предприятиякритерием оптимальности является степень удовлетворения его потребностей вресурсе или другой показатель, например, величина прибыли. Для планирующегооргана критерием выступает вектор локальных критериев предприятий.
3. Задачиоптимизации на множестве условий функционирования. Задан спектр условий, вкоторых предстоит работать объекту, и применительно к каждому условию качествофункционирования оценивается некоторым частным критерием.
4. Задачиоптимизации на множестве этапов функционирования. Рассматриваетсяфункционирование объектов на некотором интервале времени, разбитом на несколькоэтапов. Качество управления на каждом этапе оценивается частным критерием, а намножестве этапов – общим векторным критерием. Примером может служитьраспределение квартального плана цеха по декадам. В каждой декаде необходимообеспечить максимальную загрузку. В результате получится критерий максимизациизагрузки в каждой декаде квартала.
Многокритериальные задачиможно также классифицировать по другим признакам: по вариантам оптимизации, почислу критериев, по типам критериев, по соотношениям между критериями, поуровню структуризации, наличию фактора неопределенности.
При разработке методоврешения векторных задач приходится решать ряд специфических проблем.
Проблема нормализациивозникает в связи с тем, что локальные критерии имеют, как правило, различныеединицы и масштабы измерения, и это делает невозможным их непосредственноесравнение. Операция приведения критериев к единому масштабу и безразмерномувиду носит название нормирования. Наиболее распространенными способаминормирования является замена абсолютных значений критериев их безразмернымиотносительными величинами
fr(X) = fr(X) ,
f*r
или относительнымизначениями отклонений от оптимальных значений критериев f*r
fr(X) = f*r— fr(X) ,
f*r
Проблема выбора принципаоптимальности связана с определением свойств оптимального решения и решениемвопроса — в каком смысле оптимальное решение превосходит все остальные.
Проблема учета приоритетакритериев встает, если локальные критерии имеют различную значимость.Необходимо найти математическое определение приоритета и степень его влияния нарешение задачи.
Проблема вычисленияоптимума возникает, если традиционные вычислительные схемы и алгоритмынепригодны для решения задач векторной оптимизации.
Решение перечисленныхпроблем идет в нескольких направлениях. Основные направления:
Методы, основанные насвертывании критериев в единый;
Методы, использующиеограничения на критерии;
Методы целевогопрограммирования;
Методы, основанные наотыскании компромиссного решения;
Методы, в основе которыхлежат человеко-машинные процедуры принятия решений (интерактивноепрограммирование).
В методах, основанных насвертывании критериев, из локальных критериев формируется один. Наиболеераспространенным является метода линейной комбинации частных критериев. Пустьзадан вектор весовых коэффициентов критериев a = {a1,…,ar}, характеризующих важностьсоответствующего критерия, åar = 1, ar ³ 0 (r = 1,K).Линейная скаляризованная функция представляет собой сумму частных критериев,умноженных на весовые коэффициенты. Задача математического программированиястановится однокритериальной и имеет вид
F° = åarfr(X) (max),
qi(X) £ bi (I = 1,M),
X ³ 0.
Критерии в свертке могут бытьнормированы. Решение, полученное в результате оптимизации скаляризованногокритерия эффективно.
К недостаткам метода можно отнестито, что малым приращениям коэффициентов соответствуют большие приращенияфункции, т.е. решение задачи неустойчиво, а также необходимость определениявесовых коэффициентов.
Направление методов, использующихограничения на критерии включает два подхода:
1) метод ведущегокритерия;
2) методыпоследовательного применения критериев (метод последовательных уступок, методограничений).
В методе ведущего критерия всецелевые функции кроме одной переводятся в разряд ограничений. Пусть g = (g2, g3,…, gк-1) – вектор, компоненты которогопредставляют собой нижние границы соответствующих критериев. Задача будет иметьвид
F = f1 (max)
fr ³ gr (r = 2,K),
qi (X) £ bi (I = 1,M),
X ³ 0.
Полученное этим методомрешение может не быть эффективным, поэтому необходимо проверить егопринадлежность области компромиссов.
Метод ведущего критерияприменяется в таких задачах, как минимизация полных затрат при условиивыполнения плана по производству различных видов продукции, максимизациявыпуска комплектных наборов при ограничении на потребляемые ресурсы.
Алгоритм методапоследовательных уступок:
1. Критериинумеруются в порядке убывания важности.
2. Определяетсязначение f*1. Лицом, принимающим решение,устанавливается величина уступки D1 по этому критерию.
3. Решается задачапо критерию f2 с дополнительным ограничением f1(X) ³ f*1 — D1.
Далее пункты 2 и 3 повторяются длякритерия f2,…, fk.
Полученное решение не всегдапринадлежит области компромиссов.
При решении задач методами целевогопрограммирования предполагается приближение значения каждого критерия копределенной величине fr,т.е. достижение определенной цели. В самом общем виде задача целевогопрограммирования формулируется как задача минимизации сумм отклонений целевыхфункций от целевых значений с нормированными весами.
d(F(X), F) = ( å wR êfR (X) — fR êp)<sup/> (min),
где F = {f1,...., fR} — вектор целевых значений,
W = {w1,..., wR} — вектор весов, обычно å wR<sub/>= 1, wR<sub/>³ 0
(r = 1, K),значения p находятся в пределах 1 £ p £ ¥,
d(.) – расстояние (мера отклонения)между F(X) и F.
Во многих случаях применения целевогопрограммирования полагают p = 1.Например, в линейном целевом программировании функции fR (X) (r=1, K) и qi (X) (i = 1,M) линейны и нет целочисленныхпеременных.
В задачах лексикографическогопрограммирования критерии строго упорядочены по важности, так что при сравнениипары решений в первую очередь используется критерий f1 и лучшим считается то решение, для которого значение этогокритерия больше, если значения первого критерия для обоих решений оказываютсяравными, то применяется критерий f2 и предпочтение отдается томурешению, для которого значение f2 больше, ели и второй критерий непозволяет определить лучшее решение, то привлекается f3 и т.д. Учет информации о важности критериев осуществляетсяпутем поэтапного решения задачи минимизации отклонений критериев от целевыхзначений. Часто в лексикографическом программировании F = F, p = 1 .
Точка F обычно не принадлежит области допустимых значений и поэтомуее иногда называют идеальной или утопической точкой. В некоторых методахцелевого программирования допускается задание утопического множества, какпример при построении архимедовой задачи.