Контрольная работа по "Экономико-математические методы и модели"

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

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

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

функция 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), - допустимым решением задачи оптимизации.

Понятно, что  искомая точка 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 является единственным допустимым решением.

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

_j (x_1, х _2, х _N) (=, ) 0, j = 1, 2, … М,

т.е.

D = X: j (X) (=, ) 0, j = 1, 2, ... , M R^N,

или множество D может одновременно задаваться как  в явном виде, т.е. допустимое решение  Х должно принадлежать некоторой  области P R^N, так и системой ограничений. 
 
 
 
 
 
 
 
 

II. Графическое решение задачи распределения ресурсов. 
 

 

Решение:

X1 и Х2 – план при выпуске продукции каждого вида.

1. Составим математическую модель вида:

 

3Х₁ + 4Х₂ ≤ 35,

5Х₁ + 6Х₂ ≤ 54,

5Х₁ + 3Х₂ ≤ 45,

Х₁ ≥ 0, Х₂ ≥ 0. 

Математическая модель представляет собой систему линейных неравенств. Значит область допустимых решений (ОДР) представляет собой выпуклый многоугольник. 
 

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

 

Х₁/11,7 +  Х₂/8,75 ≤ 1,

Х₁/10,8 + Х₂/9 ≤ 1,

Х₁/9 + Х₂/15 ≤ 1. 

Построим первую прямую по двум точкам : (0; 8,7) и (11,7; 0). На рисунке (1.1) обозначим её цифрой I. Вторая прямая (II.) проходит через точки (0; 9) и (10,8; 0). Третья – (0; 15) и

(9; 0) – на рисунке цифра III. 
 
 
 
 
 
 

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

Например, определим  координаты т.А . Эта точка является пересечением I. и II. прямых:   
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Т.А с координатами : Х1=3, Х2= 6,5. 

Определим координаты т.В – пересечение II. и III. Прямых:  
 
 
 
 
 
 
 
 
 
 
 
 

Т.В – с координатами: Х1=7,2 и Х2=3. 
 
 

4. Найдем оптимальное  решение в смысле максимизации суммарного выпуска.

Тогда целевая  функция:

F= Х₁ + Х₂, где F → max. [ f = C₁Х₁ + С₂Х₂ ; С₁=1, С₂ = 1]

Эту зависимость  представим в виде Х₂=F –X₁.

Допустим, что F = 0,

 Х₁ + Х₂ = 0,

 Х₁ = - Х₂.

Построим данную прямую f = Х₁ + Х₂ = 0. Если её перемещать параллельно самой себе в направлении, указанном стрелками, то мы увидим, что оптимальным решением для максимизации суммарного выпуска будут координаты т.В., т.е. при Х₁=7,2 и Х₂=3. 

5. Теперь найдем оптимальное решение для целевой  функции – F= 4Х₁ + 7Х₂ → max. (максимум прибыли).

 Для начала , построим линию уровня –C₁Х₁ +C₂Х₂ = const. В нашем случае приравняем целевую функцию постоянной величине а. Пусть а = 0.

 Вычислим координаты  двух точек, удовлетворяющих соответствующему  уравнению 4Х₁ + 7Х₂ = 0. В качестве  одной из этих точек удобно  взять т.О (0 ; 0), и вторую т.(7 ; -4). Через эти две точки проведем линию уровня.

Для определения  направления движения к оптимуму построим вектор-градиент – ς.

Передвигая линию  параллельно самой себе в сторону  вектора, мы видим, что она пересекает ОДР последний раз в т.В (7,2; 3). Значит в ней достигается максимальное значение функции цели. 

      Следовательно , для получения максимальной прибыли при наших ограничениях мы должны выпустить 7 единиц - первого вида продукции (Х1) и 3 единицы - второго вида продукции (Х2).

Подставив эти  значения в функцию цели F=4Х₁ + 7Х₂, то получим ,что максимальная прибыль равна 49. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

III.Транспортная задача. 

 
 

Решение:

1. Первоначальное закрепление потребителей за поставщиками.

Рассмотрим метод наименьших стоимостей для получения начального распределения

( начального опорного  плана). 

Число занятых клеток равно m+n-1=4+5-1=8. 

Метод наименьших стоимостей (таблица 1.2.)

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

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

Поставщик исключается  из рассмотрения, если его запасы использованы полностью.

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

Таблица 1.2.

 
 

Суммарные затраты  на перевозки, представленные в таблице 1.2.,составляю:

f(X)=

Данный план перевозок  близок к оптимальному. 
 
 
 

2. Проверка  оптимальности полученного  плана перевозок.

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

Vi+ Ui+Cij . Исходя из этого, уравнения составим таблицу 1.3. 

Таблица 1.3.

 

Чтобы оценить оптимальность  распределения, для всех клеток матрицы  перевозок определяются их оценки по уравнению dij= (Ui +Cij) – Vj.

Оценки клеток удобно представить в виде матрицы оценок. Для нашего рассматриваемого распределения, полученного методом наименьших стоимостей  (см.таблицу 1.3.), матрица оценок клеток получает вид:

 
 

dij=  
 
 

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

Суммарные затраты  по оптимальному плану равны ____. 
 
 
 
 
 
 
 
 
 
 

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

1. А.П.Мацнев, А.А.Якушин. Экономико-математические методы  и модели. Учебное пособие.2006 г.

2. Экономико-математические методы и прикладные модели: Учебное пособие для вузов /Под ред.В. В. Федосеева. - М.: ЮНИТИ, 2001.