Экономико-математические методы и прикладные модели
СОДЕРЖАНИЕ: Основные понятия моделирования. Общие понятия и определение модели. Постановка задач оптимизации. Методы линейного программирования. Общая и типовая задача в линейном программировании. Симплекс-метод решения задач линейного программирования.МОСКОВСКИЙ КИНОВИДЕОИНСТИТУТ (филиал)
САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА КИНО И ТЕЛЕВИДЕНИЯ
КУРСОВАЯ РАБОТА
«Экономико-математические методы и прикладные модели»
Выполнила студентка 3-го курса
(ускоренный)
Ющак Е.В.
Преподаватель Манцев А.П.
г. Москва, 2002
I. Введение.
Предметом изучения дисциплины являются количественные характеристики экономических процессов, протекающих в промышленном производстве, изучение их взаимосвязей на основе экономико-математических методов и моделей. Эти модели линейного и нелинейного программирования, модели исследования операций, модели массового обслуживания.
Важное место отводится экономико-математическим моделям в ценообразовании. Особое внимание уделяется методам и моделям прогнозирования конъюнктуры рынка и определения цен, моделям и методам анализа инвестиционных проектов, моделям в управлении финансами.
Немалое место отводится моделям оптимального отраслевого и регионального регулирования – экономико-математическим моделям проекта развития отдельных отраслей промышленности. Это такие важные модели, как вариантная, транспортно-производственная, модель расчета топливного баланса региона.
Основным понятием является понятие математической модели. В общем случае слово модель – это отражение реального объекта. Такое отражение объекта может быть представлено схемой, эскизом, фотографией, моделью описательного характера в виде графиков и таблиц и т.д. Математическая модель – это система математических уравнений, неравенств, формул и различных математических выражений, описывающих реальный объект, составляющие его характеристики и взаимосвязи между ними. Процесс построения математической модели называют математическим моделированием. Моделирование и построение математической модели экономического объекта позволяют свести экономический анализ производственных процессов к математическому анализу и принятию эффективных решений.
Поскольку нами изучаются экономические задачи, то и строятся экономико-математические модели, включающие:
1) выбор некоторого числа переменных величин для формализации модели объекта;
2) информационную базу данных объекта;
3) выражение взаимосвязей, характеризующих объект, в виде уравнений и неравенств;
4) выбор критерия эффективности и выражение его в виде математического соотношения – целевой функции.
Итак, для принятия эффективных решений в планировании и управлении производством необходимо экономическую сущность исследуемого экономического объекта формализовать экономико-математической моделью, т.е. экономическую задачу представить математически в виде уравнений, неравенств и целевой функции на экстремум (максимум или минимум) при выполнении всех условий на ограничения и переменные.
II . Основные понятия моделирования.
2.1. Общие понятия и определение модели.
Содержанием любой экономико-математической модели является выраженная в формально-математических соотношениях экономическая сущность условий задачи и поставленной цели. В модели экономическая величина представляется математическим соотношением, но не всегда математическое соотношение является экономическим. Описание экономических условий математическими соотношениями – результат того, что модель устанавливает связи и зависимости между экономическими параметрами или величинами.
По содержанию различают экономико-математические и экономико-статистические модели. Различие между ними состоит в характере функциональных зависимостей, связывающих их величины. Так, экономико-статистические модели связаны с показателями, сгруппированными различными способами. Статистические модели устанавливают зависимость между показателями и определяющими их факторами в виде линейной и нелинейной функции. Экономико-математические модели включают в себя систему ограничений, целевую функцию.
Система ограничений состоит из отдельных математических уравнений или неравенств, называемых балансовыми уравнениями или неравенствами.
Целевая функция связывает между собой различные величины модели. Как правило, в качестве цели выбирается экономический показатель (прибыль, рентабельность, себестоимость, валовая продукция и т.д.). Поэтому целевую функцию иногда называют экономической, критериальной. Целевая функция – функция многих переменных величин и может иметь свободный член.
Критерии оптимальности – экономический показатель, выражающийся при помощи целевой функции через другие экономические показатели. Одному и тому же критерию оптимальности могут соответствовать несколько разных, но эквивалентных целевых функций. Модели с одной и той же системой ограничений могут иметь различные критерии оптимальности и различные целевые функции.
Решением экономико-математической модели, или допустимым планом называется набор значений неизвестных, который удовлетворяет ее системе ограничений. Модель имеет множество решений, или множество допустимых планов, и среди них нужно найти единственное, удовлетворяющее системе ограничений и целевой функции. Допустимый план, удовлетворяющий целевой функции, называется оптимальным. Среди допустимых планов, удовлетворяющих целевой функции, как правило, имеется единственный план, для которого целевая функция и критерий оптимальности имеют максимальное или минимальное значение. Если модель задачи имеет множество оптимальных планов, то для каждого из них значение целевой функции одинаково.
Если экономико-математическая модель задачи линейна, то оптимальный план достигается в крайней точке области изменения переменных величин системы ограничений. В случае нелинейной модели оптимальных планов и оптимальных значений целевой функции может быть несколько. Поэтому необходимо определять экстремальные планы и экстремальные значения целевой функции. План, для которого целевая функция модели имеет экстремальное значение, называют экстремальным планом, или экстремальным решением.
Для нелинейных моделей иногда существуют экстремальные значения целевой функции, а для линейных моделей экстремальных планов и экстремальных значений целевой функции быть не может.
Таким образом, для принятия оптимального решения любой экономической задачи необходимо построить ее экономико-математическую модель, по структуре включающую в себе систему ограничений, целевую функцию, критерий оптимальности и решение.
Методика построения экономико-математической модели состоит в том, чтобы экономическую сущность задачи представить математически, используя различные символы, переменные и постоянные величины, индексы и другие обозначения.
Все условия задачи необходимо записать в виде уравнений или неравенств. Поэтому, в первую очередь необходимо определить систему переменных величин, которые могут для конкретной задачи обозначить искомый объем производства продукции на предприятии, количество перевозимого груза поставщиками конкретным потребителям.
2.2. Постановка задач оптимизации
В общем виде задача оптимизации, или задача определения экстремума, ставится следующим образом.
Пусть заданы:
функция f(X), определенная на множестве O RN ;
множество D RN .
Найти точку Y = (y1 , y2 ,..., yN ) D, в которой функция f (X) достигает экстремального (минимального или максимального) значения, т.е.
f(X) = extr f(X) и Y D.
Функция f(X) называется целевой функцией, переменные X – управляемыми переменными, D – допустимым множеством и любой набор значений Y управляемых переменных, принадлежащий D (Y D), - допустимым решением задачи оптимизации.
Понятно, что искомая точка Y, в которой f(X) достигает своего экстремума, должна принадлежать пересечению области определения O функции f(X) и допустимого множества D (Y O D). Если множества O и D совпадают со всем пространством RN (O = D = RN ), то такая задача называется задачей на безусловный экстремум. Если хотя бы одно из множеств O или D является собственным подмножеством пространства RN (O RN , D RN ) или множества O и D пересекаются (O D ), то такая задача называется задачей на условный экстремум, в противном случае (O D = ) точка экстремума Y не существует. Подчеркнем один частный случай: если множества O и D пересекаются в одной точке Y, то эта точка Y является единственным допустимым решением.
Обычно в задаче условного экстремума задается не само допустимое множество решений D, а система соотношений, его определяющая,
yj (x1, х 2, х 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, iI, IM = {1, 2,…m};
aij xj bi, iM;
Xj0, jJ, JN = {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 |
0 |
| 40 |
12 |
8 |
10 |
8/40 |
15 |
0 |
| 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) = 618+715+832+85+840+710+147+1613=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 |
0 |
| 40 |
12 |
8 |
10 |
8/40 |
15 |
0 |
| 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) = 618+72+1013+832+85+840+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 |
0 |
| 40 |
12 |
8 |
10 |
8/40 |
15 |
0 |
| 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) = 618+102+1013+832+85+840+725+147=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 |
0 |
| 40 |
12 |
8 |
10 |
8/40 |
15 |
0 |
| 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) = 730+840+618+102+125+1013+832=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) - вектор переменных, обычно предполагается неотрицательность вектора переменных X0, функциональная взаимосвязь переменных устанавливается определенными соотношениями, на которые накладываются ограничения:
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),
X0.
Будем рассматривать ВЗМП для случая, когда точки оптимума 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) - f R p ) (min),
где F = {f1 ,...., fR } - вектор целевых значений,
W = {w1 ,..., wR } - вектор весов, обычно wR = 1, wR 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 обычно не принадлежит области допустимых значений и поэтому ее иногда называют идеальной или утопической точкой. В некоторых методах целевого программирования допускается задание утопического множества, как пример при построении архимедовой задачи.