Математические методы в принятии решений

Предприятие выпускает n наименований продукции. Затраты ι-го вида ресурсов (ι = 1, m ) на производство единицы продукции j-го вида ( j = 1, n) составляют а_ιj ; полный объем имеющихся ресурсов – bι ( ι = 1, m ); прибыль, получаемая предприятием при изготовлении и реализации единицы ι-го вида продукта – сι ; аι и Аι – задаваемая нижняя и верхняя границы по объему выпуска ι-го вида продукции.

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

Таким образом, задача математически  заключается в следующем: найти  такой план выпуска продукции U = (u₁, ..., u_n), чтобы выполнялись технологические ограничения

и ограничения на объемы отдельных видов выпускаемой  продукции a_j ≤ u_j ≤ A_j, j = 1, n и при этом достигалась бы максимальная общая прибыль от производства и реализации продукции –

 

Задача оптимизации  межотраслевых потоков

Каждая из n отраслей хозяйства производит только свой один специфический вид продукции, используемый в дальнейшем в производстве во всех n отраслях (в частности, в нулевом количестве). Если y_i – объем производства в ι-й отрасли, u_ι – объем продукта ι-го вида для внепроизводственного потребления, а_ιj – коэффициенты прямых затрат продукции j-го вида на производство в ι-й отрасли единицы продукции ι-го вида, N_ι – максимально возможный объем производства в ι-й отрасли, d_ι – требуемое для

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

Требуется найти такие  объемы производства yι и такой план выпуска конечной продукции u_ι( ι = 1, n) , при котором максимизируется общая стоимость произведенного конечного продукта – , при выполнении ограничений на объем производства 0 ≤ yι ≤ Nι, ι = 1, n; на выпуск конечного продукта uι ≥ dι , ι = 1, n; технологических ограничений на выпуск продукции

 

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

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

Имеется m пунктов производства с объемами производства в единицу времени а_ι , ι = 1, m и n пунктов потребления bι, ι = 1, n , естественно, что потребление не должно превышать возможностей производства , затраты на перевозку единицы продукции из ι-го пункта производства в j-й пункт потребления составляют С_ιj, а количество  перевезенного продукта u_ιj .

Требуется составить такой  план перевозок, при котором суммарные  затраты на них были бы минимальны при условиях, что в каждый пункт потребления завозится требуемое количество продукта из каждого пункта производства вывозится не более произведенного количества продукта  и перевозимый объем продукта не может быть отрицательным u_ιj ≥ 0, ι = 1, m, j = 1, n .

 

Задача о выборе производственной программы

Эта задача была одной из первых практических задач линейного  программирования, решенная в 1939 году известным русским математиком  Л.В. Канторовичем.

На m предприятиях нужно произвести n продуктов в заданном ассортименте l₁, l₂, ..., l_n. Если u_ij, ι = 1, m, j = 1, n – рабочее время ι-го предприятия, отводимое под j-й продукт, а_ij – производительность ι-го предприятия в единицу времени по выпуску j-го продукта, то задача о выборе производственной программы для случая, когда продукция дефицитна, производственные мощности ограничены и должны использоваться максимально полно, ставится следующим образом.

Требуется составить программу  работы предприятий – указать  время u_ιj, отведенное на производство каждого вида продукции на данном предприятии таким образом, чтобы получить максимальный суммарный объем продукции в заданном ассортименте в единицу времени, т.е. необходимо найти u_ιj из условий, что время не может быть отрицательным u_ιj > 0, сумма всех временных долей не превосходит полного времени работы предприятия количество ассортиментных наборов продуктов максимально где - количество j-го продукта, произведенного на всех предприятиях.

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

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

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

 

Общая задача линейного программирования [2] заключается в отыскании вектора (u₁, u₂, ..., u_n) максимизирующего критерий оптимальности (функцию цели задачи)

  (4.1)

при ограничениях линейного  типа в виде равенств:

  (4.2)

в виде неравенств:

  (4.3)

и ограничениях на переменные состояния 

u₁ ≥ 0, u₂ ≥ 0, …, u_n ≥ 0.    (4.4)

Эта задача при наличии  двух переменных u₁ и u₂ имеет наглядное геометрическое представление.

Пусть целевая функция  имеет вид Q (u) = C₁u₁ + C₂u₂. На плоскости переменных u₁ и u₂, если придать Q (u) некоторое постоянное значение Q (u) = const, например, является не чем иным как линиями равного значения уровня. Причем, при u₂ = u₁ = 0 эта линия сжимается в точку (рис. 4.1), при Q⁰ = 0 имеем C₁u₁ + C₂u₂ = 0 и линия равного уровня является прямой линией, проходящей через точки (Q₀/C₁, 0) и (0, (Q₀/C₂).

Рис. 4.1 Геометрическое представление целевой функции

 

Если теперь эту линию  перемещать параллельно самой себе (рис. 4.1), то величина Q0, а, следовательно, и значение целевой функции Q (u) будет изменяться. Увеличению целевой функции соответствует перемещение в направлении, указанном на рис. 4.1 стрелкой.

Ограничения или условия  типа равенств, называемые также связью, на плоскости u1, u2 изображаются так же, как целевая функция, прямыми линиями (рис. 4.2).

Если связь a₁₁u₁ + a₁₂u₂ = b₁ , то ей "убивается" одна степень свободы, т.е. число переменных, которыми можно варьировать, определяется разностью между числом переменных uι, ι = 1, n и числом ограничений типа равенств (m) – ν = n − m(m < n) . Эти переменные называются свободными переменными, а число ν определяет число степеней свободы.

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

Рис. 4.2 Геометрическое представление связей типа равенства

 

Рис. 4.3 Геометрическое представление

 

Неравенства a₂₁u₁ + +a₂₂u₂ ≤ b₂ , a₃₁u₁ + a₃₂u₂ ≤ b₃ разделяют всю плоскость (u₁, u₂) на две области: запрещенную и разрешенную (рис. 4.3). Как правило, при геометрическом представлении ограничений типа неравенств на плоскости наносят штриховку в сторону запрещенной области. На рис. 4.3 разрешенной областью является область АВС0, эта область всегда представляет собой выпуклый многогранник.

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

5.ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

 

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

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

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

5.1 Основные понятия

 

В динамическом программировании рассматриваются многостадийные процессы принятия решения.

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

Динамическое программирование является средством оптимизации  математически описанных процессов.

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

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

а) стадия – единичный  элемент, на которые делится весь процесс во времени или в пространстве;

ступень – часть стадии. В любом случае стадия и ступень  – это математические конструкции, применяемые для представления  в дискретном виде непрерывной переменной;

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

в) переход от стадии к  стадии и от состояния к состоянию  описывается функциональными уравнениями;

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

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

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

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

Рассматриваемый много стадийный  процесс условно изображается схемой, изображенной на рис. 5.1.

Рис. 5.1 Многостадийный процесс

 

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

Использование принципа оптимальности  является гарантией того, что решение, принимаемое на каждой стадии, является наилучшим с точки зрения всего  процесса в целом.

В динамическом программировании используется также принцип вложения, под которым понимается рассмотрение исходной задачи с позиций более  широкого класса задач (например, рассматривать  не 10, а m стадий). Это позволяет изучить целый класс задач, включая и исходную. Исходя из принципа вложения, представляется возможным изучить как структуру, так и "чувствительность" решения.

5.2 Математическое описание. Функциональное уравнение Беллмана.

 

Как уже говорилось, математическое описание процесса известно.

Пусть состояние системы  на каждой стадии описывается уравнением

(5.1)

где y_ν-1, y_ν – переменные состояния ν – 1 и ν стадий соответственно, u_ν – управление на ν-й стадии.

Уравнение (5.1) связывает  выходные переменные ν стадии с выходными  переменными предыдущей стадии y_ν-1 и управлением u_ν, используемым на этой ν стадии.

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

  (5.2)

Кроме того, используется запись

       (5.3)

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