Глава 1. Нелинейное программирование

ВВЕДЕНИЕ

 

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

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

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

Математическая дисциплина, занимающаяся изучением задач управления, планирования и разработкой методов их решения, полу­чила название математического программирования.

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

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

Динамическое программирование — один из разделов методов оптимизации, в котором процесс принятия решения может быть разбит на отдельные этапы. В основе метода лежит принцип оптимальности, разработанный Р. Беллманом.

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

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

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

Глава 1. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Общая постановка задачи

 

Математическая модель задачи нелинейного программиро­вания в общем виде формулируется следующим образом: найти вектор = (х ₁, x ₂, …, x_n), удовлетворяющий системе ограни­чений

 

 

и доставляющий экстремум (наибольшее или наименьшее зна­чение) целевой функции

 

 

где x_j — переменные, j = ; L, f, g_i — заданные функции от n переменных, b_i — фиксированные значения.

Нелинейное программирование применяется при прогнози­ровании промышленного производства, управлении товарными ресурсами, планировании обслуживания и ремонта оборудова­ния и т.д.

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

Из нелинейного программирования наиболее разработаны задачи, в которых система ограничений линейная, а целевая функция нелинейная. Однако даже для таких задач оптималь­ное решение может быть найдено для определенного класса це­левых функций. Например, когда целевая функция сепарабельная, т.е. является суммой п функций f_j(x_j), или квадратичная. При этом следует отметить, что в отличие от задач линейного программирования, где точками экстремума являются верши­ны многогранника решений, в задачах с нелинейной целевой функцией точки могут находиться внутри многогранника, на его ребре или в вершине.

При решении задач нелинейного программирования для це­левой функции необходимо определить глобальный максимум или глобальный минимум. Глобальный максимум (минимум) функции — это ее наибольшее (наименьшее) значение из ло­кальных максимумов (минимумов).

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

 

Графический метод

 

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

 

Задача с линейной целевой функцией и нелинейной системой ограничений

 

Пример 1. Найти глобальные экстремумы функции

 

при ограничениях:

 

 

Решение. Область допустимых решений — часть окруж­ности с радиусом 4, которая расположена в первой четверти (рис. 1.1).

 

Рис. 1.1

 

Линиями уровня целевой функции являются параллельные прямые с угловым коэффициентом, равным -2. Глобальный минимум достигается в точке O (0, 0), глобальный максимум — в точке А касания линии уровня и окружности. Проведем че­рез точку А прямую, перпендикулярную линии уровня. Прямая проходит через начало координат, имеет угловой коэффициент 1/2 и уравнение x ₂ = 1/2 х ₁.

Решаем систему

 

откуда находим х ₁ = 8 /5, x ₂ = 4 /5, L = 16 /5 + 4 /5 = 4 .

Ответ. Глобальный минимум, равный нулю, достигается в точке O (0, 0), глобальный максимум, равный 4 , — в точке А (8 /5, 4 /5).

Задача с нелинейной целевой функцией и линейной системой ограничений

 

Пример 2. Найти глобальные экстремумы функции

 

при ограничениях:

 

Решение. Область допустимых решений — OABD (рис. 1.2). Линиями уровня будут окружности с центром в

 

Рис. 1.2

 

точке O ₁. Максимальное значение целевая функция имеет в точке D (9, 0), минимальное — в точке O ₁ (2, 3). Поэтому

 

 

Ответ. Глобальный максимум, равный 58, достигается в точке D (9, 0), глобальный минимум, равный нулю, — в точке O ₁ (2, 3).

Пример 3. Найти глобальные экстремумы функции

 

при ограничениях:

 

Решение. Область допустимых решений — OABD (рис. 1.3). Линии уровня представляют собой окружности с центром в точке O ₁ (6, 3). Глобальный максимум находится в точке O (0, 0) как самой удаленной от точки O ₁. Глобальный минимум расположен в точке Е, находящейся на пересечении прямой 3 x ₁ + 2 x ₂ = 15 и перпендикуляра к этой прямой, про­веденного из точки O ₁.

Рис. 1.3

 

Найдем координаты точки Е: так как угловой коэффици­ент прямой 3 x ₁ + 2 x ₂ = 15 равен -3/2, то угловой коэффициент перпендикуляра O ₁ Е равен 2/3. Из уравнения прямой, прохо­дящей через данную точку О ₂ с угловым коэффициентом 2/3, получим

 

Решая систему

 

находим координаты точки Е: х ₁ = 51/13, x ₂ = 21/13, при этом L(Е) = 1053/169.

Координаты точки Е можно найти следующим образом: дифференцируя выражение (x ₁ — 6)² + (x ₂ - 3)² как неявную функцию по x ₁, получим

 

 

Приравниваем полученное значение к тангенсу угла накло­на прямой 3 x _­1 + 2 x ₂ = 15:

 

Решаем систему уравнений

 

получим координаты точки Е: х ₁ = 51/13, x ₂ = 21/13.

Ответ. Глобальный максимум, равный 52, находится в точке O (0, 0). Глобальный минимум, равный 1053/169, нахо­дится в точке E (51/13, 21/13).

 

Задача с нелинейной целевой функцией и нелинейной системой ограничений

 

Пример 4. Найти глобальные экстремумы функции

 

при ограничениях:

 

Решение. Областью допустимых решений является ок­ружность с радиусом 4, расположенная в первой четверти (рис. 1.4). Линиями уровня будут окружности с центром в точке O ₁ (2, l).

Глобальный минимум достигается в точке O ₁. Глобальный максимум — в точке А (0, 4), при этом

 

Рис. 1.4

 

Ответ. Глобальныи минимум, равный нулю, достигается в точке O ₁ (2, l), глобальный максимум, равный 13, находится в точке А (0, 4).

Пример 5. Найти глобальные экстремумы

 

при ограничениях:

Решение. Область допустимых решений не является вы­пуклой и состоит из двух частей (рис. 1.5). Линиями уровня являются окружности с центром в точке O (0, 0).

Рис. 1.5

 

Найдем координаты точек А и В, решая систему

 

 

Получим А (1, 4), В (4, 1). В этих точках функция имеет гло­бальные минимумы, равные 17. Найдем координаты точек D и Е, решая системы

 

 

откуда получаем D (2/3, 6) и L(D) = 328/9, E (7, 4/7) и L(E) = 2417/49.

Ответ. Целевая функция имеет два глобальных миниму­ма, равных 17, в точках А (1, 4) и B (4, 1), глобальный макси­мум, равный 2417/49, достигается в точке E (7, 4/7).

Рис. 1.6

Установим, как будет вести себя угловой коэффициент k при монотонном возрастании L. Найдем производную от k по L:

 

 

Знаменатель производной всегда положителен, а числитель от L не зависит. Следовательно, производная имеет постоян­ный знак и при увеличении L угловой коэффициент будет толь­ко возрастать или только убывать, а прямая будет поворачи­ваться в одну сторону. Если угловой коэффициент прямой име­ет положительное значение, то прямая вращается против ча­совой стрелки, при отрицательном значении k — по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает max(min) значение, либо устанавливаем неограниченность за­дачи.

При этом возможны следующие случаи.

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

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

3. Область допустимых решений неограничена, имеется один из экстремумов. Например, минимум достигает­ся в одной из вершин области и имеет так называемый асимптотический максимум (рис. 1.9).

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

Алгоритм решения

 

1. Находим область допустимых решений.

2. Определяем угловой коэффициент k и устанавливаем на­правление поворота целевой функции.

3. Находим точку max(min) целевой функции или устана­вливаем неразрешимость задачи.

 

Экономическая интерпретация задач дробно-линейного программирования

 

Математическая модель задачи дробно-линейного програм­мирования может быть использована для определения рента­бельности затрат на производство изделий, рентабельности продаж, затрат в расчете на рубль выпускаемой продукции, себестоимости изделий.

Обозначим: r_j — прибыль предприятия от реализации еди­ницы изделия j -гo вида;

x_j — количество выпущенной продукции j- гo вида;

s_j — цена единицы продукции j- гo вида;

c_j — себестоимость производства единицы изделия j- гoвида;

d_j — затраты на производство одного изделия j -гo вида.

Задача рентабельности (Р _з) затрат на производство изде­лий имеет вид

 

Задача рентабельности (Р_n) продаж имеет вид

 

 

Задача определения затрат (З _р) в расчете на рубль товар­ной продукции записывается в виде

 

Задача нахождения себестоимости изделия записывается как

 

 

Указанные математические модели имеют системы ограниче­ний в зависимости от условий задачи.

 

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

 

Рассмотрим использование дробно-линейного программи­рования для нахождении себестоимости изделий.

Пример 6. Для производства двух видов изделий А и В пред­приятие использует три типа технологического оборудования. Каждое из изделий должно пройти обработку на каждом из типов оборудования. Время обработки каждого из изделий, затраты, связанные с производством одного изделия, даны в табл. 1.1

Оборудование I и III типов предприятие может использо­вать не более 26 и 39 ч соответственно, оборудование II типа целесообразно использовать не менее 4 ч.

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

 

Таблица 1.1

 

Решение. Составим математическую модель задачи. Пусть x ₁ — количество изделий вида А, которое следует из­готовить предприятию, x ₂ — количество изделий вида В. Об­щие затраты на их производство составят (2 х ₁ + 3 x ₂) тыс. р., а средняя себестоимость одного изделия будет равна

 

 

Математическая модель задачи примет вид

 

 

при ограничениях:

 

Δ АВС — область допустимых решений (рис. 1.11).

 

Рис. 1.11

 

Найдем x ₂: L = (2 x ₁ + 3 x ₂) / (x ₁ + x ₂), 2 x ₁ + 3 х ₂ = Lx ₁ + Lx ₂, x ₂ (3 - L) = x ₁(L - 2),

 

 

Угловой коэффициент прямой равен k = (L - 2)/(3 — l), тогда

 

 

Так как dk/dL > 0, то функция k = (L - 2)/(3 - L) возрастает. Это соответствует вращению прямой против часовой стрелки. Следовательно, в точке С (рис. 1.11) целевая функция будет иметь наименьшее значение (глобальный минимум).

Найдем координаты точки С. Решая систему

 

 

получим С (3, 1), _опт = (3, 1), L =9/4.

Следовательно, предприятию следует выпускать 3 изделия вида А и 1 изделие вида В. При этом средняя себестоимость одного изделия будет минимальной и равной 2,25 тыс. р.

 

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

 

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

Обозначим

при условии

 

и введем новые переменные у_j = y ₀ x_j.

Тогда задача примет вид

при ограничениях:

 

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

Пример 7. Дана задача дробно-линейного программирования

 

при ограничениях:

 

Решение. Обозначим: x ₁ + 2 x ₂ + 1 = 1/ у ₀, y ₀ > 0, тогда L = 2 x ₁ y ₀ - x₂y ₀.

Обозначим: x ₁ y ₀ = y ₁, х ₂ у ₀ = у ₂, х ₃ у ₀ = у ₃, х ₄ у ₀ = y ₄.

Преобразуем систему ограничений, умножив обе части всех ограничений на у ₀, и перейдем к переменным у ₀, y ₁, y ₂, y ₃, y ₄. Задача примет вид

 

при ограничениях:

Таблица 1.2

 

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

Получим

тогда

 

Ответ: _опт = (2, 0, 0, 2), L _max = 4/3.

 

Метод множителей Лагранжа

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

 

Дана задача нелинейного программирования

 

при ограничениях:

 

Предположим, что функции f (x ₁, х ₂ ,..., x_п) и g_i(x ₁, x ₂,..., x_п) непрерывны вместе со своими первыми частными про­изводными.

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

Для решения задачи составляется функция Лагранжа

 

 

где λ _i — множители Лагранжа.

Затем определяются частные производные:

 

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

 

 

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

Пример 8. Найти точку условного экстремума функции

 

при ограничениях:

 

 

Решение. Составим функцию Лагранжа

 

 

Найдем частные производные функции Лагранжа по пере­менным x ₁, x ₂, x ₃, λ₁, λ₂. Приравняв к нулю полученные вы­ражения, решим систему

 

Откуда λ₁ = - x ₂, λ₂ = - x ₂/2, х ₁ = -2, x ₂ = -4, x ₃ = 4, L = -8.

Определим характер экстремума, изменяя полученные зна­чения переменных. Измененные значения должны удовлетво­рять заданной системе ограничений. Возьмем х ₁ > -2, напри­мер x ₁ = -1, тогда из системы ограничений получим х ₂ = -3, x ₃ = 7/2, L = -15/2. Возьмем х ₁ < -2, например х ₁ = -3, тогда получим х ₂ = -5, x ₃ = 9/2, L = -15/2. Следовательно, L = -8 — минимальное значение функции.

Ответ. Точка экстремума х ₁ = -2, x ₂ = -4, x ₃ = 4, при этом максимальное значение функции L = -8.

 

Расчет экономико-математической модели при нелинейных реализациях продукции

 

Рассмотрим применение выше приведенных методов на примере решения задачи оптимальной реализации продукции.

Пример 9. Мукомольный комбинат реализует муку двумя способами: в розницу через магазин и оптом через торговых агентов. При продаже x ₁ кг муки через магазин расходы на реализацию составляют х ₁² ден. ед., а при продаже x ₂ кг муки посредством торговых агентов — х ₂² ден. ед.

Определить, сколько килограммов муки следует продавать каждым способом, чтобы затраты на реализацию были мини­мальными, если в сутки выделяется для продажи 5 000 кг муки.

Решение. Составим математическую модель задачи.

Найдем минимум суммарных расходов

 

при ограничениях:

 

Для расчета модели используем метод множителей Лагранжа. Составим функцию Лагранжа

 

 

Найдем частные производные функции F по x ₁, x ₂ и λ, приравняем их к нулю, получим систему уравнений

 

откуда λ = -5 000, x ₁ = 2 500, x ₂ = 2 500, L = 12 500 000 ден. ед.

Давая х ₁ значения больше и меньше 2500, находим L и из определения экстремума функции получаем, что L при х ₁ = x ₂ = 2 500 достигает минимума.

Таким образом, для получения минимальных расходов не­обходимо расходовать в сутки через магазин и торговых аген­тов по 2 500 кг муки, при этом расходы на реализацию составят 12 500 000 ден. ед.

 

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

 

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

Экономический процесс является управляемым, если мож­но влиять на ход его развития. Под управлением понимает­ся совокупность решений, принимаемых на каждом этапе для влияния на ход развития процесса. Например, выпуск продук­ции предприятием — управляемый процесс. Совокупность ре­шений, принимаемых в начале года (квартала и т.д.) по обеспе­чению предприятия сырьем, замене оборудования, финансиро­ванию и т.д., является управлением. Необходимо организовать выпуск продукции так, чтобы принятые решения на отдель­ных этапах способствовали получению максимально возмож­ного объема продукции или прибыли.

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

В отличие от линейного программирования, в котором сим­плексный метод является универсальным методом решения, в динамическом программировании такого универсального ме­тода не существует. Одним из основных методов динамичес­кого программирования является метод рекуррентных соотношений, который основывается на использовании принципа оптимальности, pазработанного американским математиком Р. Беллманом. Принцип состоит в том, что, каковы бы ни бы­ли начальное состояние на любом шаге и управление, выбран­ное на этом шаге, последующие управления должны выбирать­ся оптимальными относительно состояния, к которому придет система в конце данного шага. Использование данного прин­ципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом.

В некоторых задачах, решаемых методом динамического программирования, процесс управления разбивается на шаги. При распределении на несколько лет ресурсов деятельности предприятия шагом целесообразно считать временной пери­од; при распределении средств между предприятиями — номер очередного предприятия. В других задачах разбиение на шаги вводится искусственно. Например, непрерывный управляемый процесс можно рассматривать как дискретный, условно разбив его на временные отрезки (шаги). Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом, что­бы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.

 

Рис. 2.1

Функциональные уравнения, основанные на принципе оп­тимальности, имеют вид:

(2.1)

(2.2)

 

Уравнение (2.1) описывает N -стадийный процесс, а (2.2) — одностадийный. Оба уравнения состоят из двух час­тей: верхняя строка определяет доход, получаемый при сохра­нении оборудования; нижняя — доход, получаемый при замене оборудования и продолжении процесса работы на новом обору­довании.

В уравнении (2.1) функция r(t) — u(t) есть разность между стоимостью произведенной продукции и эксплуатационными издержками на N- й стадии процесса.

Функция f_{N- 1} (t + 1) характеризует суммарную прибыль от (N — 1) оставшихся стадий для оборудования, возраст которо­го в начале осуществления этих стадий составляет (t + 1) лет.

Нижняя строка (2.1) характеризуется следующим обра­зом: функция s(t) — Р представляет чистые издержки по замене оборудования, возраст которого t лет.

Функция r (0) выражает доход, получаемый от нового обо­рудования возраста 0 лет. Предполагается, что переход от ра­боты на оборудовании возраста t лет к работе на новом обо­рудовании совершается мгновенно, т.е. период замены старо­го оборудования и переход на работу на новом оборудовании укладываются в одну и ту же стадию.

Последняя функция f_{N- 1} в (2.1) представляет собой доход от оставшихся N — 1 стадий, до начала осуществления которых возраст оборудования составляет один год.

Аналогичная интерпретация может быть дана уравне­нию для одностадийного процесса. Здесь нет слагаемого вида f ₀ (t + 1), так как N принимает значение 1, 2,..., N. Равенство f ₀ (t) = 0 следует из определения функции f_N(t).

Уравнения (2.1) и (2.2) являются рекуррентными соот­ношениями, которые позволяют определить величину f_N(t) в зависимости от f_{N -1}(t + 1). Структура этих уравнений показы­вает, что при переходе от одной стадии процесса к следующей возраст оборудования увеличивается с t до (t + 1) лет, а число оставшихся стадий уменьшается с N до (N — 1).

Расчет начинают с использования уравнения (2.1). Урав­нения (2.1) и (2.2) позволяют оценить варианты замены и сохранения оборудования, с тем чтобы принять тот из них, ко­торый предполагает больший доход. Эти соотношения дают возможность не только выбрать линию поведения при реше­нии вопроса о сохранении или замене оборудования, но и опре­делить прибыль, получаемую при принятии каждого из этих решений.

Пример 1. Определить оптимальный цикл замены оборудо­вания при следующих исходных данных: Р = 10, S(t) = 0, f(t) = r(t) — u(t), представленных в табл. 2.1.

Таблица 2.1

 

Решение. Уравнения (2.1) и (2.2) запишем в следующем виде:

 

(2.3)

Для N = 1

 

Для N = 2

Вычисления продолжаем до тех пор, пока не будет выпол­нено условие f ₁(1) > f ₂(2), т.е. в данный момент оборудование необходимо заменить, так как величина прибыли, получаемая в результате замены оборудования, больше, чем в случае ис­пользования старого. Результаты расчетов помещаем в табли­цу, момент замены отмечаем звездочкой, после чего дальней­шие вычисления по строчке прекращаем (табл. 2.2).

Таблица 2.2

 

Можно не решать каждый раз уравнение (2.3), а вычис­ления проводить в таблице. Например, вычислим f ₄ (t):

 

 

Дальнейшие расчеты для f ₄ (t) прекращаем, так как f ₄(4) = 23 < f ₃(1) = 24.

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

Ответ. Для получения максимальной прибыли от ис­пользования оборудования в двенадцатиэтапном процессе оп­тимальный цикл состоит в замене оборудования через каждые 4 года.

 

Оптимальное распределение ресурсов

 

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

Введем обозначения: x_i — количество ресурсов, выделен­ных i -му предприятию (i = );

g_i(x_i) — функция полезности, в данном случае это величи­на дохода от использования ресурса x_i, полученного i- м пред­приятием;

f_k(x) — наибольший доход, который можно получить при использовании ресурсов х от первых k различных предприя­тий.

Сформулированную задачу можно записать в математи­ческой форме:

 

при ограничениях:

 

Для решения задачи необходимо получить рекуррентное соотношение, связывающее f_k(x) и f_{k- 1} (x).

Обозначим через х_k количество ресурса, используемого k- мспособом (0 ≤ x_k ≤ х), тогда для (k — 1) способов остается ве­личина ресурсов, равная (x — x_k). Наибольший доход, который получается при использовании ресурса (x — x_k) от первых (k — 1 ) способов, составит f_{k- 1} (x — x_k).

Для максимизации суммарного дохода от k- гo и первых (k — 1) способов необходимо выбрать x_k таким образом, чтобы выполнялись соотношения

 

 

Рассмотрим конкретную задачу по распределению капита­ловложений между предприятиями.

 

Распределение инвестиций для эффективного использования потенциала предприятия

 

Совет директоров фирмы рассматривает предложения по наращиванию производственных мощностей для увеличения выпуска однородной продукции на четырех предприятиях, при­надлежащих фирме.

Для расширения производства совет директоров выделя­ет средства в объеме 120 млн р. с дискретностью 20 млн р. Прирост выпуска продукции на предприятиях зависит от вы­деленной суммы, его значения представлены предприятиями и содержатся в табл. 2.3.

Найти распределение средств между предприятиями, обес­печивающее максимальный прирост выпуска продукции, при­чем на одно предприятие можно осуществить не более одной инвестиции.

 

Таблица 2.3

 

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

Рекуррентные соотношения будут иметь вид:

для предприятия № 1

 

для всех остальных предприятий

 

 

Решение будем проводить согласно рекуррентным соотно­шениям в четыре этапа.

1-й этап. Инвестиции производим только первому пред­приятию. Тогда

 

2-й этап. Инвестиции выделяем первому и второму пред­приятиям. Рекуррентное соотношение для 2-го этапа имеет вид

 

 

Тогда

при х = 20 f ₂(20) = max (8 + 0,0 + 10) = max (8, 10) = 10,

при x = 40 f ₂(40) = max (16,8 + 10,20) = max (16, 18, 20) =20,

при х = 60 f ₂(60) = max (25,16 + 10, 8 + 20,28) = max (25,26, 28,28) =28,

при х = 80 f ₂(80) = max (36,25 + 10,16 + 20,8 + 28,40) = max (36, 35, 36, 36, 40) = 40,

при х = 100 f ₂(100) = max (44,36 + 10,25 + 20,16 + 28,8 + 40,48) = max (44, 46, 45, 44, 48, 48) = 48,

при х = 120 f ₂(120) = max (62,44 + 10,36 +20,25 + 28,16 + 40,8 + 48,62) = max (62, 54, 56, 53, 56, 56, 62) = 62.

3-й этап. Финансируем 2-й этап и третье предприятие. Расчеты проводим по формуле

Тогда

при х = 20 f ₃(20) = mах (10, 12) = 12,

при x = 40 f ₃(40) = max (20,10 + 12,21) = max (20, 22, 21) = 22,

при х = 60 f ₃(60) = max (28,20 + 12,10 + 21,27) = max (28, 32, 31, 27) = 32,

при х = 80 f ₃(80) = max (40,28 + 12,20 + 21,10 + 27,38) = max (40, 40, 41, 37, 38) = 41,

при x = 100 f ₃(100) = max (48,40 + 12,28 + 21,20 + 27,10 + 38,50) = max (48, 52, 49, 47, 48, 50) = 52,

при х = 120 f ₃(120) = max (62,48 + 12,40 + 21,28 + 27,20 + 38,10 + 50,63) = max (62, 60, 61, 55, 58, 60, 63) = 63.

4-й этап. Инвестиции в объеме 120 млн р. распределяем между 3-м этапом и четвертым предприятием.

При х = 120 f ₄(120) = max (63,52 + 11,41 + 23,32 + 30,22 + 37,12 + 51,63) = max (63, 63, 64, 62, 59, 63, 63) = 64.