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

где U – область, определенная условиями u1N + u2N = rN , 0 ≤ u1N ≤ u1, 0 ≤ u2N ≤ u2.

Для N = 1 будет B₁(u₁,u₂ )=Q₁₁ (u₁ ) +Q₂₁(u₂).

 

5.4.3 Процессы сглаживания

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

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

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

Данная задача решается методом  динамического программирования, для  этого формулируется ее математическая постановка.

Если uι – производительность системы на ι-м шаге, ι = 1, 2, ..., N; rι – заданная последовательность спросов, причем uι ≥ rι (спрос всегда удовлетворяется), u0 = q – фиксированный начальный уровень запасов; Qι(uι −rι) – убытки, вызванные тем, что uι > rι, ϕι (uι – uι–1) – убытки, вызванные тем, что uι ≠ uι–1, то суммарные издержки выражаются формулой

Требуется определить уровни uι , ι = 1,2, ..., N, при uι ≥ rι таким образом, чтобы минимизировалась целевая функция (издержки) Q (u1, ..., uN). Рекуррентное соотношение имеет вид

 

5.4.4 Замена оборудования

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

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

Решения принимаются в  моменты времени t = 0, 1, 2, ... Возможны два решения: сохранить машину (K) или купить новую (P). Введем следующие обозначения: r (t) – годовой доход от машины возраста t, u (t) – годовые расходы на содержание машины возраста t, C (t) – стоимость замены машины возраста t. Если единица дохода на некотором шаге равносильна α единицам дохода следующего шага, то суммарный доход B (t) при оптимальной политике за рассматриваемый период составит

Этот пример является примером бесконечного процесса.

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

Неизвестное значение T выбирается из условия максимума B(1).

 

5.4.5 Задача складирования

 

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

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

Пусть pι – затраты на единицу товара, Cι – продажная цена единицы товара, xι – количество купленного товара, yι – количество проданного товара, v – величина наличного запаса на каждом шаге, V – вместимость хранилищ склада.

На любую возможную  политику накладываются ограничения:

− на покупку

− на продажу

− неотрицательность xι ≥ 0, yι ≥ 0.

Целевая функция представляет собой суммарную прибыль, полученную при N-шаговом процессе

Рекуррентное соотношение  Беллмана

при условиях: 0 ≤ yN ≤ v, xN ≥ 0, v + xN − yN ≤ V.

6. ИГРОВЫЕ МЕТОДЫ В ТЕОРИИ ПРИНЯТИЯ РЕШЕНИЙ

 

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

При этом либо оба лица стремятся "выиграть" (максимизировать свои целевые функции), либо одно лицо не стремится этого сделать (игры с  природой).

Решению подобных состязательных задач посвящена теория игр [5]. Стороны  или лица, принимающие решения  в состязательных задачах, называются игроками.

Задача относится к  теории игр, если:

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

б) решения игроками принимаются  в условиях неопределенности.

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

 

Пусть имеется два лица (первое и второе) и оба эти  лица стремятся получить максимальную выгоду. Следовательно, имеется две  целевые функции: Q₁ (x, y) – функция выигрыша первого лица, Q₂ (x, y) – функция выигрыша второго лица, где x, y – решения, принимаемые соответственно первым и вторым лицом.

Таким образом, значение целевой  функции первого игрока зависит  не только от его решения x, которое он примет, но и от решения y, которое примет второй игрок. То же можно сказать и о целевой функции Q₂ (x, y) второго лица.

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

где ^y – известное решение второго лица, Х – множество возможных решений первого лица. Совсем иначе обстоит дело, если решение у второго лица неизвестно. В этом случае необходимо условиться, каким образом оценивать "удачность" выбора решения х, так как значение целевой функции Q₁ (x, y) зависит не только от х, но и от у, что иллюстрируется графиком (рис. 6.1).

Здесь следует ввести новую  оценочную функцию Q^1(x), которая позволила бы сравнивать какое из решений х₁ или х₂ первого лица "лучше".

Также можно оценивать "хорошесть" решения х по среднему значению целевой функции Q₁

Эта оценка является хорошей, она учитывает вклад каждого  решения второго лица и вероятность  принятия таких решений. Однако, в  этом случае необходимо знать вероятность  принятия решения вторым лицом или  плотность распределения вероятности, если множество Х является континиум. То же самое относится, очевидно, и к функции Q2 ( y). Если Р(у) не известно, то вычислить Q₁( y) или Q₂ ( y) невозможно, следует выбрать новую оценку "хорошего " решения.

Естественной оценкой  в этом случае является "наихудшее" (минимальное) значение целевой функции ~Q₁ ( x)

Чем больше минимальный выигрыш ~ Q₁(x ), тем лучше х. Эта оценка слишком осторожна: на самом деле выигрыш получится наверняка больше, получиться меньше он уже не может. Такую оценку называют гарантированным выигрышем.

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

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

В теории игр принята следующая  терминология.

Лица, принимающие решения, называются игроками. Целевые функции  называются платежными функциями, и  считается, что они показывают выигрыш  игрока. Так, платежная функция Q₁ (x₁, …, x_n) показывает выигрыш первого игрока.

Множество возможных решений Хi каждого игрока называется множеством чистых стратегий i-го игрока, а решение хi из множества чистых стратегий Xi, xi ∈ Xi называется чистой стратегией i-го игрока.

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

Отрицательное значение платежной  функции означает "проигрыш" игрока, например, если Q₁ (x, y) = 5, то это означает, что первый игрок выиграл 5 единиц, а если Q₁ (x, y) = –5, то первый игрок проиграл 5 единиц. Целью первого игрока является максимизация выигрыша, т.е. функцию Q₁ (x, y) необходимо максимизировать. Очевидно, что целью первого игрока могла бы быть минимизация функции проигрыша Q₁ (x, y), которая равна функции выигрыша, взятой с обратным знаком Q₁ (x, y) = –Q₁ (x, y).

Следовательно, Q₁ (x, y) = 5 означает, что первый игрок проиграл 5 единиц, а Q₁ (x, y) = –5 означает, что первый игрок выиграл 5 единиц.

Эти две задачи имеют, очевидно, право на существование, однако, в  теории игр первый игрок всегда полагается выигрывающим, и платежная функция Q1 (x, y) определяет его выигрыш. Проигрышу со ответствует отрицательное значение Q1 (x, y).

Аналогичные замечания могут  быть отнесены к платежной матрице Qi любого i-го игрока.

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

Пусть Х – множество чистых стратегий, а х₁, х₂, …, х_n – n чистых стратегий из этого множества.

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

В этом случае стратегией будет  вектор вероятностей ξ = (ξ₁, ξ₂, …, ξ_n), игрок должен пытаться найти такую стратегию (такое значение) ξ, при которой он получит максимальный успех.

Стратегия выбора вероятности  ξ называется смешанной стратегией.

Рассмотрим следующий  пример. Так, чистыми стратегиями  является установка орудия на север, юг, запад, восток. Смешанная стратегия  ξ = (0,1; 0,5; 0,2; 0,2) означает, что 10 % времени  орудие смотрит на север, 50 % на юг и  по 20 % времени оно повернуто на запад и восток. Если чистыми стратегиями  являются покупка сахара, муки, картофеля, то ξ = (0,5; 0,2; 0,3) означает, что деньги истрачены следующим образом: 50 % на сахар, 20 % на муку, 30 % на картофель. Принятие чистой стратегии означает, что покупатель принял решение истратить все  деньги на один из этих продуктов.

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

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

Пусть в игре двух игроков  первый игрок выбрал чистую стратегию х, а второй – чистую стратегию у, тогда ситуацией будет вектор (х, у).

Ситуацией в смешанных  стратегиях будет вектор (ξ, η), где  ξ = (ξ₁, …, ξ_n) – смешанная стратегия первого игрока, η = (η₁, …, η_m) – смешанная стратегия второго игрока, ξi – вероятность использования чистой стратегии xi первым игроком, ηi – вероятность использования чистой стратегии yi вторым игроком.

Если ситуация сформулирована, то говорят, что игра состоялась.

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

в случае применения смешанной  стратегии, где θ – множество  значений вектора вероятности η = (η₁, …, η_m) второго игрока.

Очевидно, первому игроку хотелось бы выбрать такое х* или такой вектор ξ*, при котором гарантированный выигрыш ~ Q1 (x) принял бы максимальное значение

 или 

Стратегия х*, доставляющая максимум гарантированному выигрышу Q~ первого игрока, называется максиминной

Второму игроку также хотелось бы получить максимальное значение своего гарантированного выигрыша ~ Q ₂*, который определяется аналогичным образом