Типовые задачи оптимизации и их экономико-математические модели

Федеральное государственное образовательное

бюджетное учреждение высшего профессионального  образования

 

 

«ФИНАНСОВЫЙ УНИВЕРСИТЕТ

ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ»

 

 

Финансово-кредитный факультет

 

Кафедра экономико-математических методов  и

аналитических информационных систем

 

Методы оптимальных решений

 

Контрольная работа

 

 

Вариант 2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Москва 2013

 

 

План.

1. Типовые задачи оптимизации и их экономико-математические модели
2. Задача 2
3. Задача 3
4. Задача 4
5. Задача 5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ведение.

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

Важное место отводится  экономико-математическим моделям  в ценообразовании. Особое внимание уделяется методам и моделям  прогнозирования конъюнктуры рынка  и определения цен, моделям и  методам анализа инвестиционных проектов, моделям в управлении финансами.

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

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

Поскольку нами изучаются  экономические задачи, то и строятся экономико-математические модели, включающие:

1) выбор некоторого числа  переменных величин для формализации  модели объекта;

2) информационную базу  данных объекта;

3) выражение взаимосвязей, характеризующих объект, в виде  уравнений и неравенств;

4) выбор критерия эффективности  и выражение его в виде математического  соотношения - целевой функции.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.Типовые задачи оптимизации и их экономико-математические модели.

Постановка задач  оптимизации

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

Пусть заданы:

функция f(X), определенная на множестве R^N ;

множество D R^N.

Найти точку Y = (y₁, y₂,..., y_N) D, в которой функция f (X) достигает экстремального (минимального или максимального) значения, т.е. f(X) = extr f(X) и Y D.

Функция f(X) называется целевой  функцией, переменные X - управляемыми переменными, D - допустимым множеством и любой набор значений Y управляемых  переменных, принадлежащий D (Y D), - допустимым решением задачи оптимизации [3].

Понятно, что искомая точка Y, в которой f(X) достигает своего экстремума, должна принадлежать пересечению  области определения O функции f(X) и  допустимого множества D (Y O D). Если множества O и D совпадают со всем пространством R^N (O = D = R^N), то такая задача называется задачей на безусловный экстремум. Если хотя бы одно из множеств O или D является собственным подмножеством пространства R^N (O R^N , D R^N) или множества O и D пересекаются (O D ), то такая задача называется задачей на условный экстремум, в противном случае (O D = ) точка экстремума Y не существует. Подчеркнем один частный случай: если множества O и D пересекаются в одной точке Y, то эта точка Y является единственным допустимым решением.

Методы линейного  программирования.

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

В самом общем виде задача математически записывается так:

U = f(X) max; X W,

Где X = (Х1, Х2,…, Хn);

W - область допустимых  значений переменных Х1, Х2,…, Хn;

f(X) - целевая функция [3].

Для того, чтобы решить задачу оптимизации, достаточно найти ее оптимальное  решение, т.е. указать 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);

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

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

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

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

2) если в ограничениях правая  часть отрицательна, то следует  умножить это ограничение на -1;

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

4) если некоторая переменная  Хk не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными::

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

Под термином «транспортные задачи»  понимается широкий круг задач не только транспортного характера. Общим  для них является, как правило, распределение ресурсов, находящихся  у m производителей (поставщиков), но n потребителям этих ресурсов [3].

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

• прикрепление потребителей ресурса к производителям;
• привязка пунктов отправления к пунктам назначения;
• взаимная привязка грузопотоков прямого и обратного направлений;
• задачи оптимальной загрузки промышленного оборудования;
• оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями.

Транспортным задачам  присущи следующие особенности:

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

Транспортные задачи могут  решаться симплекс-методом.

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

Симплекс-метод позволяет отказаться от метода перебора при решении задач  линейной оптимизации, является основным численным методом решения задач  линейного программирования и позволяет  за меньшее число шагов, чем в  методе перебора, получить решение [3].

Реализация алгоритма симплекс-метода.

1. Записать задачу в канонической форме: заменить все ограничения-неравенства с положительной правой;

2. Разделить переменные на базисные  и свободные: перенести свободные  переменные в правую часть  ограничений-неравенств.

3. Выразить базисные переменные через свободные: решить систему линейных уравнений (ограничений-неравенств) - относительно базисных переменных;

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

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

6. Вычислить полученное  базисное решение и функцию  цели на нем: приравнять к  0 свободные переменные;

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

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

9. Используя новое разделение  переменных на базисное и свободное,  вернуться к пункту 3 и повторять  все этапы до тех пор, пока  не будет найдено оптимальное  решение [4].

В заключение отметим, что  определение оптимального решения  распадается на два этапа:

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

Задание 2. Решить графическим методом типовую задачу оптимизации. Осуществить проверку правильности решения с помощью средств MS Excel (надстройки Поиск решения).

Совхоз для кормления животных использует два вида корма. В дневном  рационе животного должно содержаться  не менее 6 единиц питательного вещества А и не менее 12 единиц питательного вещества В. Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальными? Использовать данные таблицы: