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

При введенных обозначениях ограничения на объем потребляемых материально-сырьевых ресурсов могут быть заданы таким образом:

(j=1,…,M)(5)

Ограничения на производственные мощности задаются следующими неравенствами

k=1,…,N(6)

Кроме того, переменные

x_i≥0 i=1,…,n (7)

Таким образом, задача выбора производственной программы, максимизирующей прибыль, заключается в выборе такого плана выпуск х = (х₁...,х_n), который удовлетворял бы ограничениям (5)-(7) и максимизировал бы функцию (4).

В некоторых случаях предприятие должно поставить заранее оговоренные объемы продукции Vt другим хозяйствующим субъектам и тогда в рассматриваемой модели вместо ограничения (1.7) может быть включено ограничение вида:

x_t> Vt i= 1, ...,n.

Задача о диете. Рассмотрим задачу составления душевого рациона питания минимальной стоимости, которое бы содержало определенные питательные вещества в необходимых объемах. Будем предполагать, что имеется известный перечень продуктов из n наименований (хлеб, сахар, масло, молоко, мясо и т.д.), которые мы будем обозначать буквами F₁,...,F_n. Кроме того, рассматриваются такие характеристики продуктов (питательные вещества), как белки, жиры, витамины, минеральные вещества и другие. Обозначим эти компоненты буквами N₁,...,N_m. Предположим, что для каждого продукта F_i известно (i = 1,...,n) количественное содержание в одной единице продукта указанных выше компонент. В этом случае можно составить таблицу, содержащую характеристику продуктов:

F₁,F₂,…F_j…F_n

_____________

N₁a₁₁a₁₂…a_1j…a_1N

N₂a₂₁a₂₂…a_2j…a_2N

N_ia_i1a_i2…a_ij…a_iN

N_ma_m1a_m2…a_mj…a_mN

Элементы этой таблицы образуют матрицу, имеющую m строк и n столбцов. Обозначим ее через A и назовем матрицей питательности. Предположим, что мы составили рацион х = (х₁,x₂,...,х_n) на некоторый период (например, месяц). Иными словами, мы планируем каждому человеку на месяц х, единиц (килограммов) продукта F₁,x₂ единиц продукта F₂ и т.д. Нетрудно вычислить, какое количество витаминов, жиров, белков и прочих питательных веществ получит человек за этот период. Например, компонента N₁ присутствует в этом рационе в количестве

a₁₁x₁+ a₁₂x_2+…+ a_1nx_n

поскольку согласно условию в x₁ единицах продукта F₁ согласно матрице питательности содержится a₁₁x₁ единиц компоненты N₁; к этому количеству добавляется порция а₁₂x₂ вещества N₁ из х₂ единиц продукта F₂ и т.д. Аналогично можно определить и количество всех остальных веществ N_i в составляемом рационе (х₁,..., х_n).

Допустим, что имеются определенные физиологические требования, касающиеся необходимого количества питательных веществ в N_i (i/ = 1,..., N) в планируемый срок. Пусть эти требования заданы вектором b = (b₁...,b_n), i-я компонента которого b_i указывает минимально необходимое содержание компонента N_i в рационе. Это означает, что коэффициенты x_i вектора х должны удовлетворять следующей системе ограничений:

a₁₁x₁+ a₁₂x_2+…+ a_1nx_n≥b₁

a₂₁x₁+ a₂₂x_2+…+ a_2nx_n≥b₂ (8)

a_m1x₁+ a_m2x_2+…+ a_mnx_n≥b_m

Кроме того, из содержательного смысла задачи очевидно, что все переменные х₁,...,х_n неотрицательны и поэтому к ограничениям (8) добавляются еще неравенства

x₁≥0; x₂≥0;… x_n≥0; (9)

Учитывая, что в большинстве случаев ограничениям (8) и (9) удовлетворяет бесконечно много рационов, выберем тот из них, стоимость которого минимальна.

Пусть цены на продукты F₁,...,F_n равны соответственно с₁,…,c_n

Следовательно, стоимость всего рациона х = (х₁..., х_n) может быть записана в виде

c₁x₁+ c₂x₂+…+ c_nx_n→min (10)

Окончательно формулировка задачи о диете заключается в том, чтобы среди всех векторов х = (x₁,...,х_n) удовлетворяющих ограничениям (8) и (9) выбрать такой, для которого целевая функция (10) принимает минимальное значение.

Транспортная задача. Имеется m пунктов S₁,..., S_m производства однородного продукта (угля, цемента, нефти и т.п.), при этом объем производства в пункте S_i равен a_i единиц. Произведенный продукт потребляется в пунктах Q₁...Q_n и потребность в нем в пункте Q_j составляет k_j единиц (j = 1,...,n). Требуется составить план перевозок из пунктов S_i (i = 1,...,m) в пункты Q_j(j = 1,..., n), чтобы удовлетворить потребности в продукте b_j, минимизировав транспортные расходы.

Пусть стоимость перевозок одной единицы продукта из пункта S_i в пункт Q_i равна c_ij. Будем далее предполагать, что при перевозке х_ij единиц продукта из S_i в Q_j транспортные расходы равны c_ijx_ij.

Назовем планом перевозок набор чисел х_ij c_i = 1,..., m; j = 1,..., n, удовлетворяющий ограничениям:

x_ij≥0, i=1,2,…,m; j=1,…,n (11)

Содержательный смысл уравнений (11) состоит в том, что из пункта S_i при плане х_ij вывозится во все пункты Q_j объем

, который должен быть равен запасу a_i. В пункт Q_j поступает из всех пунктов S_i суммарное количество продукта, которое в точности должно быть равно потребности b_j.

При плане перевозок (х_ij) транспортные расходы составят величину

(12)

Окончательное формирование транспортной задачи таково: среди всех наборов чисел (х_ij), удовлетворяющих ограничениям (11), найти набор, минимизирующий (12).

2.2 Динамическое программирование

2.2.1 Модель динамического программирования

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

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

Дадим общее описание модели динамического программирования.

Рассматривается управляемая система, которая под влиянием управления переходит из начального состояния

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

Состояние

системы после k-го шага (k=1,2,…,n) характеризуется параметрами , которые называют фазовыми координатами. Состояние можно изобразить точкой s-мерного пространства, называемого фазовым пространством. Последовательное преобразование системы (по шагам) достигается с помощью некоторых мероприятий , которые составляют управление системой U= ,

где

- управление на k-м шаге, переводящее систему из состояния в состояние (рис.1). Управление на k-м шаге заключается в выборе значений определенных управляющих переменных .

Предполагаем впредь, что состояние системы в конце k-го шага зависит только от предшествующего состояния системы

и управления на данном шаге (рис.1). Такое свойство получило название отсутствия последствия. Обозначим эту зависимость в виде

(1.1)