ТЕМА 8. Задачи математического программирования

Задачи математического программирования – это задачи определения наилучшего решения из множества возможных.

В общем виде постановка задачи математического программирования состоит в определении значений переменных х₁, х₂, …, х_n, при которых достигается максимум или минимум функции

f(х₁,х₂, …, х_n) → max(min)                             (9.1)

при условиях

_,

,                                      (9.2)

…   

Рекомендуемые материалы

Функция (9.1) называется целевой функцией, а условия (9.2) – ограничениями данной задачи. Запись в ограничениях означает, что возможен один из знаков , = или . В данной задаче n обозначает число переменных, а m - число ограничений.

Переменные задачи х₁, х₂, …, х_n могут иметь различный экономический смысл. Например, если предприятие выпускает три вида продукции, и нужно найти оптимальный план производства, то х₁, х₂, х₃ – количество продукции каждого вида, которое необходимо производить. Если в задаче необходимо найти наилучший состав рациона, в которую могут входить несколько составных компонентов (например, сено и силос в рационе коров), то х₁ и х₂ – количество каждого продукта, которое нужно включить в рацион (в данном случае, сена и силоса).

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

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

В зависимости от характера целевой функции f  и функций ограничений _,  говорят о различных видах задач математического программирования:

· если целевая функция задачи имеет линейный вид, а ограничения заданы в виде линейных уравнений или неравенств, то это задача линейного программирования. Пример линейного выражения: 5х₁+6х₂.

· если целевая функция и/или ограничения содержат нелинейные функции, то это задача нелинейного программирования. Пример нелинейных функций: х*y, х², , sin x, 1/x и т.д.

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

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

Наиболее разработанными являются методы решения задач линейного программирования[1]. В общем виде задача линейного программирования заключается следующем: найти значения переменных х₁, х₂, …, х_n, доставляющие оптимальное значение целевой функции:

F=c₁x₁+c₂x₂+ ... +с_nх_n®min (max)                            (9.3)

при выполнении ограничений:

а₁₁х₁+а₁₂х₂+ …+а_1nх_n{£, =, ³}b₁

а₂₁ х₁+а₂₂х₂+ …+а_2nх_n{£, =, ³}b₂

………                                     (9.4)

а_m1х₁+а_m2x₂+ …+а_mnх_n{£, =, ³}b_m

x_j>=0, (i=1…n)                                              (9.5)

где а_ij, b_{i ,} c_j –заданные постоянные величины, m – число уравнений, n – число переменных.

Ограничения (9.5) с математической точки зрения являются необязательными, но в моделях экономических задач они, как правило, всегда присутствуют. Это связано с экономическим смыслом переменных х₁, х₂, …, х_n. Например, если под x_i понимается количество продукции вида i, которое необходимо выпускать на предприятии, то очевидно, что оно не может быть отрицательным.

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

Набор значений переменных х_1, х_2,…,х_n, при котором выполняются все ограничения, называется допустимым решением или планом. Допустимое решение, при котором функция F принимает оптимальное значение, называется оптимальным.

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

Пример 8.1. Цех может выпускать два вида продукции: шкафы и тумбы для телевизора. На каждый шкаф расходуется 3,5 м стандартных ДСП, 1 м листового стекла и 1 человеко-день трудозатрат. На тумбу — 1 м ДСП, 2 м стекла и 1 человеко-день трудозатрат. Материальные и трудовые ресурсы ограничены: в цехе работают 150 рабочих, в день нельзя израсходовать больше 350 м ДСП и более 240 м стекла. Прибыль от продажи 1 шкафа составляет 200 у.е., а тумбы — 100 у.е.

Какое количество шкафов и тумб должен выпускать цех, чтобы сделать прибыль максимальной?

Решение. Введем переменные, т.е. обозначим за x_j те величины, которые нужно найти в задаче. В данном случае это

х₁ - количество шкафов;

х₂ - количество тумб,

которые должен выпускать цех. Именно от них зависит прибыль цеха и расход ресурсов.

 Прибыль от продажи одного шкафа равна 200 у.е., значит, прибыль от продажи х₁ шкафов будет 200∙х₁. Аналогично, прибыль, полученная от продажи тумб, составит 100∙х₂. Целевая функция выражает прибыль, полученную от продажи всего выпущенного количества шкафов и тумб, и поэтому ее значение стремится к максимуму:

F=200∙х₁+100∙х₂®max

Выпуск продукции ограничен количеством ресурсов, расходуемых за один день: ДСП, листовое стекло и трудозатраты.

ДСП на один шкаф расходуется 3,5 (м), а на одну тумбу — 1 (м). Следовательно на х₁ шкафов будет израсходовано 3,5∙х₁ (м), а на все выпускаемые тумбы — 1∙х₂ (м). Всего расход ДСП составит 3,5∙х₁ +х₂ (м). Количество израсходованного ресурса не должно превышать его запас на предприятии, который равен 350 (м). Поэтому можно записать следующее ограничение:

3,5∙х₁ + х₂£350                                                         

Аналогично записываются ограничения для других ресурсов: расход стекла не должен превышать его запас

х₁ + 2∙х₂£240,                                               

 а использование трудовых ресурсов ограничено числом работающих в цехе рабочих:

х₁ +х₂£150                                                                

Количество выпущенной продукции не может быть величиной отрицательной, поэтому добавим еще ограничения:

x₁³0 ,x₂³0.

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

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

Для решения ЗЛП используется симплекс-метод. Автоматизировать решение этим методом можно с помощью надстройки Поиск решения пакета MS Excel. В случае двух переменных ЗЛП может быть решена графическим методом, для автоматизации  которого используется пакет MathCad.

ТЕМА 9. МОДЕЛИ АНАЛИЗА ИНВЕСТИЦИОННЫХ ПРОЕКТОВ

9.1. Дисконтирование денежных потоков

Метод дисконтирования денежных потоков является ключевым в финансовом анализе. Рассмотрим этот метод на примере банковских депозитов. Обозначим:

P – начальный капитал, положенный в банк;

r – процентная ставка банка;

S – наращенная сумма.

Тогда в конце первого периода капитализации наращенная сумма составит:

.

Если эта сумма остается в банке, то в конце второго периода капитализации наращенная сумма составит:

.

В общем случае сумма, наращенная за n периодов капитализации, рассчитывается по формуле:

 .                                      (9.1)

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

На основании формулы (9.1) можно также найти, какой начальный капитал нужно положить в банк, чтобы наращенная за n периодов капитализации сумма составила заданную величину S. Такой начальный капитал называется текущей (приведенной) ценностью суммы S и обозначается PV:

   .                                      (9.2)

Процесс нахождения текущей ценности называется дисконтированием.

Пример 9.1. Годовая процентная ставка банка составляет 12%. Какую сумму нужно положить в банк, чтобы наращенная за пять лет сумма составила 1000 ден. единиц?

Решение. По условию r=0,12; n=5; S=1000. По формуле (9.2) найдем текущую ценность заданной суммы:

.

Таким образом, в банк следует положить 567,431 ден. ед.

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

Пример 9.2. Если положить в банк 1000 у.е. при годовой процентной ставке 10%, то через сколько лет накопленная сумма составит 2000 у.е.?

Решение. По условию даны следующие величины: P=1000; S=2000; r=0,1. Требуется найти количество временных периодов n. Запишем формулу (9.1): . Решив это уравнение относительно n, получим: n=7,27. Таким образом, на данное накопление потребуется больше семи лет.

9.2. Анализ инвестиционных проектов

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

Рассмотрим проект, в который необходимо вложить сумму I₀,, и он генерирует через n временных периодов (например, лет) прибыль С. Допустим, у инвестора имеется альтернатива: вложить деньги в проект или положить их на банковский депозит с процентной ставкой r. Тогда, чтобы получить ту же сумму, которая ожидается в качестве прибыли проекта, через такое же время, в банк следует положить

      .                                              (9.3)

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

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

Чистая текущая ценность проекта рассчитывается по формуле

                                        (9.4)

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

Пример 9.3. Проект, требующий 700 ед. начальных инвестиций, приносит через два года денежный поток 1000 ед. В качестве альтернативы этому проекту рассматривается вложение денег в банк, годовая процентная ставка которого равна 12%. Требуется выбрать наилучший вариант вложения средств.

Решение. По условию I₀=700; C=1000; n=2; r=0,12. Найдем текущую ценность проекта по формуле (9.3):

.

Таким образом, чтобы получить сумму 1000 ед через два года в банке, следует положить на депозит 797,19 ден.ед.

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

Такая норма дисконтирования денежных потоков проекта, при которой  чистая текущая ценность проекта равна нулю (NPV=0), называется внутренней нормой прибыли проекта (IRR=internal rate of return). Таким образом, IRR показывает процентную ставку некоторого гипотетического банка, который дает такую же доходность, как и данный проект. Для проекта, который дает один денежный поток, эта величина определяется из условия

 .                                     (9.5)

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

Пример 9.4. Для проекта предыдущего примера  (I₀=700; C=1000; n=2) найдем внутреннюю норму прибыли. Запишем соотношение (9.5):

   Þ     IRR = 19,52%.

Таким образом, рассматриваемый проект по прибыльности эквивалентен банковским депозитам с годовой процентной ставкой 19,52%.

Рассмотрим теперь инвестиционные проекты, которые генерируют несколько денежных потоков по годам. Обозначим C_k – денежный поток, который генерирует проект в k –ом периоде. Начальные инвестиции в проект (в нулевом периоде) обозначаются I₀.  Рассматривается n временных периодов (горизонт оценивания проекта). Тогда денежные потоки проекта можно представить в виде таблицы 9.1 (В этой таблице сумма вложения средств должна быть представлена отрицательным значением, а сумма поступления средств – положительным).

Таблица 9.1. Денежные потоки проекта

Очевидно, чтобы получить в банке с процентной ставкой r в конце k - го периода сумму C_k, нужно положить на депозит в нулевом периоде сумму . Чтобы иметь в банке денежные потоки, аналогичные потокам проекта, нужно положить в банк сумму

  .                                (9.6)

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

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

    Û          Û                (9.7)

Пример 9.5. Последовательность денежных потоков проекта представлена таблицей 9.2. Известно, что внутренняя норма прибыли альтернативных проектов с таким же финансовым риском, как и у данного проекта,  равна 17%. Определить чистую текущую ценность и внутреннюю норму прибыли проекта.

Таблица 9.2. Денежные потоки проекта из примера 9.5.

Поскольку в качестве нормы дисконтирования принимается внутренняя норма прибыли альтернативных проектов, имеем r=0,17. Рассчитаем текущую ценность проекта по формуле (9.6):

 .

Чистая текущая ценность проекта:

.

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

Внутренняя норма прибыли находится из уравнения (9.7):

.

Решив его, находим IRR=17,72%. Поскольку внутренняя норма прибыли данного проекта выше, чем у альтернативных проектов, он является выгодным.

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

,

где - номинальная процентная ставка (без учета инфляции);

i- уровень инфляции;

r – реальная процентная ставка (с учетом инфляции).

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

 или

Чистая текущая ценность проекта составит:

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

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задача 1. С помощью обобщенных комплексных показателей Qi оцените торговую деятельность трех районных потребительских союзов по данным  таблицы 1. Переоцените торговую деятельность РПС с помощью весовых коэффициентов Р₁=Р₄=Р₅=1, Р₂=Р₃=0,9, Р₆ =0,8.

Таблица 1. Торговая деятельность трех РПС.

Задача 2. Проанализируйте работу пяти универсамов по четырем натуральным показателям. Переоцените торговую деятельность универсамов, если заданы следующие весовые коэффициенты: Р₁=Р₃ =1, Р₂=0,9, Р₄ =0,8. Исходные данные представлены в таблице 2.

Таблица 2. Торговая деятельность пяти универсамов.

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

Рис.1. Сетевой график проекта.

Задача 4. Для проекта, сетевой график которого показан на рис.2., определить параметры событий (ранние, поздние сроки свершения и резервы), найти критический путь и критический срок. Для некритических работ рассчитать резервы времени.

Рис 2. Сетевой график проекта

Задача 5. Магазин ежедневно продает  33  холодильника. Накладные расходы на поставку партии холодильников в магазин оцениваются в 30000 руб. Стоимость хранения одного холодильника на складе магазина составляет 150 руб. в день. Определить оптимальный объем партии холодильников, периодичность поставок и среднесуточные общие издержки  магазина. Чему будут равны эти издержки и период между поставками при объеме партии 165 холодильников?   (предполагается модель Уилсона).

Люди также интересуются этой лекцией: 7 Основы теории теплообмена.

Задача 6.  Потребность населенного пункта в стиральном порошке составляет 100 пачек в день. Накладные расходы на заказ и доставку партии порошка на склад составляют 20000 руб. Удельная стоимость хранения одной пачки порошка составляет 3 руб. в день. Определить оптимальный объем партии порошка, периодичность поставок и среднесуточные общие издержки склада. Чему будут равны эти издержки и период между поставками при объеме партии 1000 пачек стирального порошка?   (предполагается модель Уилсона).

Задача 7. Годовая процентная ставка банка равна 9%. Какую сумму нужно положить в банк, чтобы наращенная за 10 лет сумма составила 1000 у.е.?

Задача 8. На Вашем счету в банке 2 млн.руб. Банковская ставка – 18% годовых. Вам предлагают за счет всех этих денег инвестировать проект, который через 6 лет принесет доход 6 млн.руб. Стоит ли принимать это предложение?

Задача 9. Инвестор рассматривает проект, начальные инвестиции в который составляют 300 ден.ед., ожидаемый доход через три года – 800 ден. ед., норма дисконтирования – 12%. Определить чистую текущую ценность проекта и внутреннюю норму прибыли. Проанализировать полученные результаты.

Задача 10. Рассчитать чистую текущую ценность проекта с начальными инвестициями в 800 млн. ден.ед. Срок реализации проекта – 3 года. Ожидаемые денежные поступления – 200, 400, 400 ден.ед. Норма прибыли альтернативных проектов равна 10%. Сделать вывод о целесообразности инвестиций. Будут  ли инвестиции в этот проект привлекательны в условиях инфляции (уровень инфляции 5% годовых)?

[1] Начало линейной оптимизации было положено в 1939 г., когда вышла в свет работа профессора Ленинградского университета Л.В. Канторовича “Математические методы организации и планирования производства”. Академик Л.В. Канторович за разработку методов решения оптимизационных задач был удостоен звания лауреата Ленинской (1965 г.) и Нобелевской (1975 г.) премий.