Математическое программирование

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

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

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

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

Рассмотрим парную игру с нулевой суммой. 1-й игрок имеет m возможных стратегий, а 2-й - n возможных стратегий. Не зная выбора друг друга, 1-й игрок выбирает i-ю стратегию, а 2-й игрок -j-ю стратегию. В результате игры 1-й игрок выигрывает величину , а 2-й - проигрывает эту же величину. Из чисел составляют матрицу, которая называется платежной или матрицей игры,

.

Строки матрицы соответствуют стратегиям 1-го игрока, а столбцы - стратегиям 2-го. Это чистые стратегии.

Игра, определяемая матрицей А, имеющей m строк и n столбцов, называется конечной игрой размерности mхn.

Чтобы описание игры было законченным, необходимо указать цели, которыми руководствуются игроки при выборе своих стратегий. Эти цели просты: 1-й игрок стремится обеспечить себе наибольший выигрыш, а 2-й - наименьший проигрыш. Специфической трудностью является то, что ни один из игроков не контролирует полностью значение , т.к. 1-й игрок распоряжается только выбором i, а 2-й - j. Преодоление этой трудности, т.е. определение наиболее рационального способа ведения игры каждым игроком, и представляет собой существо теории игр.

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

y₁ y₂ y₃ А(х)

х₁ 7 2 5 2

А = х₂ 2 2 3 2

х₃ 3 5 4 3

В(y) 7 5 5

При выборе 1-м игроком, например, 1-й стратегии, х₁, его выигрыш может быть равен 7, 2 или 5. Может ли 1-й игрок рассчитывать на максимальный выигрыш ? Да, если 2-й игрок выберет 1-ю свою стратегию, y₁. Однако он может выбрать и 2-ю стратегию, y₂, и выигрыш будет равен 2. Но уже меньше 2 выигрыш не может быть ни при какой стратегии 2-го игрока. Поэтому число 2, являющееся минимальным элементом стратегии х₁, есть гарантированный выигрыш 1-го игрока при стратегии х₁. Аналогично можно определить гарантированные выигрыши для любой стратегии 1-го игрока - А(х). Предполагается, что игроки избегают необоснованного риска и выбирают ту стратегию, которая дает максимальный из всех гарантированных выигрышей.

Число называется нижней ценой игры или максимином.

А соответствующая стратегия - максиминной.

Также можно рассуждать и в отношении 2-го игрока. Только в А указаны его проигрыши, которые он стремится минимизировать. Например, стратегия y₁ может принести 2-му игроку проигрыш 7, 2 или 3. Но уже больше 7 он не проиграет. Следовательно, число 7, являющееся максимальным элементом стратегии y₁, есть гарантированный проигрыш2-го игрока при y₁. Определим все гарантированные проигрыши - В(y). Каким же проигрышем может ограничиться 2-й игрок ?

Числоназывается верхней ценой игры или минимаксом.

А соответствующая стратегия - минимаксной.

2. Теоремы теории игр

Теорема 1. (основная теорема теории игр).

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

Терема 2. Нижняя цена игры всегда не превосходит верхней цены игры, .

Рассмотрим два случая.

1. Пусть .

Игра, для которой, , называется игрой с седловой точкой. Если , то С является ценой игры, а стратегии игроков, обеспечивающие им выигрыш или проигрыш, равный С, являются оптимальными. Если игра с седловой точкой имеет С=0, то она является справедливой, если С0, - несправедливой.

2. Пусть. В этом случае трудно определить цену игры и оптимальные стратегии игроков. Вернемся к рассмотренному примеру. = 3, а = 5. Значит, первый игрок может гарантировать себе выигрыш, равный 3, а второй - ограничить свой проигрыш 5. Область между и является как бы ничейной, и каждый игрок может попытаться улучшить свой результат за счет этой области. Каковы в этом случае оптимальные стратегии игроков? Если каждый игрок будет применять стратегию, соответствующую его максимальному гарантированному выигрышу или проигрышу, противник может догадаться о его намерениях и улучшить свой результат. Например, первый игрок использует х₃, а второй - y₂. Второй игрок заметил, что первый все время применяет x₃, и решил применить y₁, сведя свой проигрыш к меньшему числу. Таким образом, чтобы иметь успех, каждый игрок должен хранить свой выбор в секрете. Это трудно сделать, если игра повторяется многократно.

Секретность можно сохранить, если каждый раз выбирать стратегию случайным образом (бросая монету, кость и т.п.). При этом выигрыш и проигрыш будут случайными величинами. Результат можно оценить средней величиной проигрыша или выигрыша. Так, в нашем случае, если второй игрок использует свои стратегии y₁, y₂, y₃ случайным образом, например, с вероятностями 1/3; 1/3; 1/3, соответственно, то среднее значение его проигрыша может быть:

- если первый использует х₁:

С_ср = 1/3 а₁₁ + 1/3 а₁₂ + 1/3 а₁₃ = 7/3 + 2/3 + 5/3 = 14/3;

- если первый использует х₂:

С_ср = 1/3 а₂₁ + 1/3 а₂₂ + 1/3 а₂₃ = 2/3 + 2/3 + 3/3 = 7/3;

- если первый использует х₃:

С_ср = 1/3 а₃₁ + 1/3 а₃₂ + 1/3 а₃₃ = 3/3 + 5/3 + 4/3 = 4. Таким образом, второй игрок может ограничить свой проигрыш уже не 5, а 14/3, независимо от стратегии первого игрока. Следовательно, в ряде случаев оказывается целесообразным не намечать заранее стратегии, а выбирать ту или иную случайным образом. Стратегия, основанная на случайном выборе, называется смешанной стратегией.

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

Пусть u=(u₁,...,u_m) и z=(z₁,...,z_n), соответственно, вероятности отдельных исходов механизма случайного выбора 1-го и 2-го игроков.

Из теории вероятностей должно быть известно, что

1) u_i 0, i=; z_j . 0, j=; (т.к. 0 р 1);

2) и (т.к. р(U) = 1, U- достоверное событие). Если u^* - оптимальная стратегия 1-го игрока, z^* - оптимальная стратегия 2-го игрока, то число является ценой игры.

Определение оптимальных стратегий и цены игры составляет процесс решения игры.

Теорема 3 (о цене игры).

Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях. Для того, чтобы число С было ценой игры, а u^* и z^* - оптимальными стратегиями игроков, необходимо и достаточно выполнения неравенств:

и .

Теорема дает ответ на вопрос о существовании решения игры и определяет путь решения.

В частном случае, когда по крайней мере у одного из игроков имеется только 2 стратегии, справедлива теорема.

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

3. Способы решения задач теории игр.

4. Методы принятия решений: в условиях определенности; в условиях риска; в условиях неопределенности.

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

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

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

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

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

Игры, в которых один противник "природа", а другой - человек или, в которых один из игроков действует несознательно, а в соответствии с определенными законами, называются играми с "природой" или статистическими играми.

Теория таких игр - теория статистических решений. Человек, который участвует в игре против природы, называется статистиком (экономистом).

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

1. Принятие решений в условиях определенности, когда данные известны точно.

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

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

Рассмотрим все эти условия.

Принятие решений в условиях определенности. Метод анализа иерархий.

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

Рассмотрим пример. Выпускник-отличник средней школы на основании свидетельства о ЕГЭ поступил сразу в три университета: А, В, С. Чтобы выбрать университет он сформулировал 2 критерия: местоположение университета и его академическая репутация. Будучи отличным учеником, он оценивает академическую репутацию в 5 раз выше, чем его местоположение. Используя метод анализа иерархий, можно дать выпускнику рекомендации.

Сложность метода анализа иерархий заключается в определении относительных весовых коэффициентов для оценки альтернативных решений. Создается матрица парных сравнений А_nxn , где n - число критериев на заданном уровне иерархии. Матрица А отражает суждение лица, принимающего решение, относительно важности разных критериев. Парное сравнение выполняется таким образом, что критерий в строке i (i= ) оценивается относительно каждого из критериев, представленных n столбцами: А = (). Для описания оценок используют числа от 1 до 9. При этом = 1, когда i - й и j - й критерии одинаково важны, = 5, когда i - й критерий значительно важнее, чем j - й.

= 9, когда i - й критерий чрезвычайно важнее, чем j - й. Другие значения критерия интерпретируются аналогично.

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

м р

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

В пределах каждого критерия строятся матрицы сравнений для альтернативных решений, например

А В С А В С

А_м = и А_р = .

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

Средние значения элементов строк

м р

N =

А В С

N_м =

А В С

N_р =

Одинаковые столбцы нормализованных матриц N и N_p означают, что результирующие относительные веса сохраняют одно и то же значение независимо от того, как выполняется сравнение. В этом случае говорят, что исходные матрицы сравнения являются согласованными. Как видно из примера, не все матрицы сравнений являются согласованными. Принимая во внимание, что такие матрицы строятся на основе человеческих суждений, можно ожидать некоторую степень несогласованности, и к ней следует относиться терпимо при условии, что она не выходит за определенные «допустимые» рамки. Чтобы выяснить, является ли уровень несогласованности допустимым, необходимо определить соответствующую количественную меру - коэффициент согласованности CR:

, где - коэффициент согласованности матрицы;

- стохастический коэффициент согласованности

матрицы (определяется эмпирическим путем).

или , где .

Для матрицы N_м будем иметь

, ,

, , .

Если , то уровень несогласованности матрицы сравнений является приемлемым. Если , то уровень несогласованности матрицы сравнений высокий и, лицу, принимающему решение, рекомендуется проверить элементы парного сравнения. В примере уровень несогласованности матрицы является приемлемым.

Задача имеет единственный иерархический уровень с двумя критериями (местоположение и репутация) и три альтернативных решения (А, В, С). Структура задачи принятия решения имеет вид.

На основе этих вычислений университет А получает наивысший комбинированный вес и, следовательно, является наиболее оптимальным выбором выпускника.

Принятие решений в условиях риска.

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

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

Предположим, что вы хотите вложить на фондовой бирже 10000 долл. В акции одной из двух компаний: А или В. Акции компании А являются рискованными, но могут принести 50 % прибыли от суммы инвестиции на протяжении следующего года. Если условия фондовой биржи будут неблагоприятны, сумма инвестиции может обесцениться на 20 %. Компания В обеспечивает безопасность инвестиций с 15 % прибыли в условиях повышения котировок на бирже и только 5 % - в условиях понижения котировок. Все аналитические публикации, с которыми можно познакомиться (а они всегда есть в изобилии в конце года), с вероятностью 60 % прогнозируют повышение котировок и с вероятностью 40 % - понижение котировок. В какую компанию следует вложить деньги?

Условия игры задаются в виде матрицы А = (), в которой строки соответствуют стратегиям человека, а столбцы - возможным состояниям "природы". В некоторых задачах для состояний "природы" может быть задано распределение вероятностей, в других - оно неизвестно. Элемент равен выигрышу человека, если он использует i-ю стратегию при j-том состоянии "природы". При решении игры часто рассматривают матрицу рисков R = (). Элемент равен разности между выигрышем, который получил бы человек, если бы знал состояние природы, и выигрышем, который он получит в тех же условиях, применяя i-ю стратегию, то есть

= -, = .

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

Пусть распределение вероятностей различных состояний "природы" известно p = (p₁, ..p_n),

. Следовательно, выбирая i-ю стратегию, человек может рассчитывать на средний выигрыш

М_i = (Математическое ожидание).

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

Для сформулированной выше задачи будем иметь:

А =

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

Принятие решения в условиях неопределенности.

Отличие между принятием решения в условиях риска и неопределенности состоит в том. Что в условиях неопределенности вероятностное распределение, соответствующее состояниям природы, неизвестно, либо не может быть определено. Этот недостаток информации обусловил развитие следующих критериев для анализа ситуации: критерий Лапласа, максиминный (минимаксный) критерий Вальда, критерий минимального риска Сэвиджа, критерий Гурвица и другие.

Если распределение вероятностей различных состояний "природы" неизвестно, то его можно оценить, например, по принципу "недостаточного основания Лапласа", согласно которому, все состояния "природы" равновероятны, р₁ = р₂ = ...= р_n = 1/n.

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

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

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

3. Критерий Гурвица: наилучшей является стратегия, при которой , где .

Критерии 1 и 2 основаны на самой пессимистической оценке обстановки. Критерий 3 при = 0 является критерием крайнего оптимизма, при= 1 - критерием крайнего пессимизма. Значение выбирается субъективно: чем больше желание подстраховаться, тем ближе к 1 должно быть .

Лекция 9

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

Вопросы:

1. Постановка транспортной задачи. Закрытая модель. Теорема о существовании решения.

2. Метод потенциалов: а) построение опорного плана; б) схема решения.

3. Метод дифференциальных рент.

4. Дополнительные ограничения транспортной задачи.

1. Постановка транспортной задачи. Закрытая модель. Теорема о существовании решения

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

Пусть в пунктах А₁,А₂,...,А_m производится некоторый продукт, причем объем производства в п. А_i составляет a_i единиц, . Произведенный про-дукт должен быть доставлен в пункты потребления В₁,В₂,...,В_n, причем объем потребления в п. В_j составляет b_j единиц, . Предполагается, что тран-спортировка готовой продукции возможна из любого пункта производства в лю-бой пункт потребления, транспортные издержки на перевозку единицы продукции из п. А_i в п. В_j составляют c_ij денежных единиц. Задача состоит в организа-ции такого плана перевозок, при котором суммарные транспортные издержки были бы минимальными.

Математически транспортная задача может быть записана следующим образом. Пусть x_ij - количество продукта, перевозимого из п. А_i в п. В_j . Требуется определить совокупность (mn)величин x_ij , удовлетворяющих условиям:

(1)

и обращающих в минимум линейную форму

(2)

Специфическими для транспортной задачи являются следующие два обстоятельства: а) каждое из переменных x_ij входит в два уравнения системы (1); б) все коэффициенты при переменных x_ij принимают лишь два значения 0 или 1.

ОПРЕДЕЛЕНИЕ 1. Если общая потребность в продукте в пунктах потребления равна общему запасу продукта в пунктах производства, т.е.

, (3)

то модель транспортной задачи называется закрытой. Если это условие не выполняется, то модель называется открытой.

ТЕОРЕМА: Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы продукта в пунктах производства были равны потребностям в пунктах потребления, т.е. чтобы выполнялось равенство (3).

Замечания: 1.Если запас превышает потребность, т.е. , вводится фиктивный (n+1)-й пункт потребления с потребностью

, а соответствующие транспортные издержки равны нулю, с_i(n+1) = 0, i = .

2.Если потребности превышают запасы, т.е. вводится фиктивный (m+1)-й пункт производства с запасом

,

а соответствующие тарифы равны нулю, c_(m+1)j = 0,j = .

ОПРЕДЕЛЕНИЕ 2. Всякое неотрицательное решение системы линейных уравнений (1) называется планом транспортной задачи.

ОПРЕДЕЛЕНИЕ 3. План X^* = , ; , при котором функция (2) принимает минимальное значение, называется оптимальным планом транспортной задачи.

Часто план транспортной задачи, с которого начинают решение, называют опорным.

Число переменных x_ij в транспортной задаче с m пунктами производства и n пунктами потребления равно mn, а число уравнений в системе (1) равно m+n. Т.к. предполагается, что выполняется условие (3), то число линейно независимых уравнений равно n+m-1. Следовательно, опорный план может иметь не более n+m-1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности n+m-1 , то план является невырожденным, а если - меньше - то вырожденным.

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

2. Метод потенциалов

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

Методы построения опорного плана

а) Метод северо-западного угла.

Метод позволяет за n+m-1 шаг заполнить клетки таблицы таким образом, чтобы удовлетворить все потребности, исчерпав при этом все запасы. Заполнение клеток таблицы начинается с левой верхней клетки ("северо-западной"), в которую ставят максимально возможное число, т.е. минимальное из чисел запасов и потребностей для этой клетки. При этом исчерпываются либо запасы, либо потребности (вычеркивается строка или столбец), выбирается следующая «северо-западная» клетка и т.д.

б) Метод минимального элемента.

Заполнение клеток осуществляется по принципу: "Самая дешевая перевозка осуществляется первой". Выбирается клетка с минимальным тарифом и заполняется максимально возможным числом, при этом исчерпываются либо запасы, либо потребности (вычеркивается строка или столбец), выбирается следующая клетка с минимальным тарифом и т.д.

в) Метод аппроксимации Фогеля.

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

Как правило, при построении опорного плана этими тремя методами выполняется следующее соотношение: F_в(x)F_б(x) F_а(x).

Схема решения.

1. Строят опорный план одним из методов.

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

ТЕОРЕМА. Если для некоторого опорного плана транспортной задачи существуют такие числа и , что

при x_ij > 0 (4)

и при x_ij = 0 (5)

для всех и, то этот план является оптимальным.

ОПРЕДЕЛЕНИЕ 4. Числа и (,) называются потенциалами, соответственно, поставщиков и потребителей.

Т.о., найдя потенциалы поставщиков и потребителей, удовлетворяющие условиям теоремы, мы докажем оптимальность построенного плана. Как их найти? Т.к. число заполненных клеток, x_ij > 0, равно n+m-1 (невырожденный план), то система (4) с n+m неизвестными содержит n+m-1 уравнение. Положим одно из неизвестных равным нулю и последовательно найдем значения остальных неизвестных. Затем для всех свободных клеток, x_ij = 0, определим числа .

Если среди чисел нет положительных, то условия теоремы выполнены, и план является оптимальным. Если существует > 0, то построенный план не оптимален, и его следует улучшить.

3. Алгоритм улучшения плана:

1) среди всех > 0 выбирают максимальное;

2) для соответствующей клетки строят цикл пересчета;

3) помечают вершины цикла пересчета последовательно знаками "+" и "-" , начиная с "+" в исходной клетке;

4) среди чисел, стоящих в клетках, помеченных "-" , определяют минимальное;

5) к значениям, стоящим в "+"-клетках, прибавляют это минимальное число, а из значений, стоящих в "-"-клетках, это число вычитают.

ОПРЕДЕЛЕНИЕ 5. Циклом пересчета называется ломаная линия, вершины которой расположены в занятых клетках, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла может быть только два звена.

4. Измененный таким образом план опять проверяют на оптимальность, т.е. переход к п. 2.

3. Метод дифференциальных рент

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

Для определения решения транспортной задачи методом дифференциальных рент используют следующий алгоритм:

1. В каждом столбце определяют минимальный тариф и выделяют сответствую-щую клетку.

2. Выделенные клетки заполняют максимально возможными числами.

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

ОПРЕДЕЛЕНИЕ 6. Строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности выделенных потребителей не удовлетворены, являются отрицательными.

ОПРЕДЕЛЕНИЕ 7. Строки, соответствующие поставщикам, запасы которых не исчерпаны полностью, являются положительными.

ОПРЕДЕЛЕНИЕ 8. Строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности выделенных потребителей удовлетворены, имеют нулевую оценку. При этом, если вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке, данная строка с нулевой оценкой считается положительной. В противном случае - отрицательной.

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

5. Среди полученных разностей определяют минимальную. Это число называют промежуточной рентой.

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

7. Переходят к п.1.

ЗАМЕЧАНИЕ: а) если в строке или столбце оказывается более одной выделенной клетки, то заполняют, в первую очередь, те выделенные клетки, которые являются единственными в столбце или строке;

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

4. Дополнительные ограничения транспортной задачи

1. Запрещенные маршруты.

Если по каким-либо причинам невозможно поставлять продукцию из п. А_i в п. В_j , предполагают тариф этого пути сколь угодно большой величиной М, с_ij = М, и решают задачу обычным способом.

2. Обязательные поставки.

а) Если необходимо из п. А_i перевезти в п. В_j определенное количество продукции d_ij, соответствующую клетку заполняют сразу числом d_ij, а в дальнейшем решают задачу, считая заполненную клетку свободной, но с тарифом, с_ij = М, равным очень большому числу, а запасы и потребности уменьшают на величину d_ij.

б) Если необходимо из п. А_i в п. В_j перевезти не меньше определенного количества продукции d_ij, то считают запасы и потребности меньше на величину d_ij, это количество d_ij считают перевезенным по маршруту А_i В_j, и решают задачу далее обычным способом.

в) Если необходимо перевезти из п. А_i в п. В_j не более определенного количества продукции d_ij, вводят дополнительный пункт назначения с потребностью, равной ( - d_ij), потребность в п. В_j делают равной d_ij. Тарифы на перевозки в дополнительный пункт назначения равны тарифам п. В_j , кроме i-той строки, тариф в которой будет равен сколь угодно большому числу М. Решают задачу обычным образом, а при записи ответа объединяют основного и дополнительного потребителя (складывают содержимое столбцов).

Лекция 14, 15

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

Вопросы:

1. Основные понятия. Общая постановка задачи ДП.

2. Принцип оптимальности. Функциональные уравнения Беллмана.

3. Задача оптимального распределения ресурсов.

4. Задача о замене.

5. Задача управления производством и запасами.

1. Основные понятия. Общая постановка задачи динамического программирования

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

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

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

1. x_i - многомерный вектор, компоненты которого определяют состояние системы на i-том шаге. Дальнейшее изменение состояния зависит только от данного состояния и не зависит от того, каким путем система перешла в него (процесс без последствия).

2. На каждом шаге выбирается одно решение, управление u_i , под действием которого система переходит из предыдущего состояния x_i-1 в новое x_i. Это новое состояние является функцией состояния на начало шага x_i-1 и принятого в начале решения u_i , т.е.

x_i = x_i ( x_i-1 , u_i ).

3. Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага и принятого решения. F_i - приращение целевой функции задачи в результате i-того шага, аналогично, F_i = F_i ( x_i-1 , u_i ). Тогда значение целевой функции при переходе системы из начального состояния в конечное за n шагов

.

4. На векторы состояния х_i и управления u_i могут быть наложены ограничения, объединение которых составляет область допустимых решений u U.

5. Требуется найти такое допустимое управление u* = (u₁* ,…, u_n* ) (для каждого шага), чтобы получить экстремальное значение функции цели F* за все n шагов.

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

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

2. Принцип оптимальности. Функциональные уравнения Беллмана

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

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

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

1) Обратный ход: от последнего шага к первому получают множество возможных оптимальных («условно-оптимальных») управлений.

2) Прямой ход: от известного начального состояния к последнему из полученного множества «условно-оптимальных» управлений составляется искомое оптимальное управление для всего процесса в целом.

Оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на n-м шаге, затем на двух последних шагах, затем на трех последних шагах и т.д., вплоть до первого шага.

Чтобы можно было использовать принцип оптимальности практически, необходимо записать его математически. Обозначим через z₁(x_n-1), z₂(x_n-2),…, z_n(x₀) условно-оптимальные значения приращений целевой функции на последнем шаге, двух последних,…, на всей последовательности шагов, соответственно.

Тогда для последнего шага:

z₁(x_n-1) = (min) {F_n(x_n-1, u_n)},

где u_n - множество допустимых (возможных) управлений на n-ом шаге, x_n-1 - возможные состояния системы перед n-ым шагом.

Для двух последних шагов:

z₂(x_n-2) = (min) {F_n-1(x_n-2, u_n-1) + z₁(x_n-1)}.

Для k последних шагов:

z_k(x_n-k) = (min) {F_n-k+1(x_n-k, u_n-k+1) + z_k-1(x_n-k+1)}.

Для всех n шагов:

z_n(x₀) = (min) {F₁(x₀, u₁) + z_n-1(x₁)}.

Полученные рекуррентные соотношения называют функциональными уравнениями Беллмана.

При этом согласно определению z_n(x₀) = F*.

3. Задача оптимального распределения ресурсов

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

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

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

Пусть на реконструкцию и модернизацию 4-х своих филиалов фирма имеет возможность выделить 200 млн. руб. Ожидаемый прирост прибыли зависит как от финансируемого филиала, так и от объема этого финансирования. Однако, прирост прибыли в отдельно взятом филиале не зависит от вложенных средств в другие филиалы, а общая прибыль фирмы равна сумме всех приростов по филиалам. Следует определить оптимальное распределение капиталовложений между филиалами, максимизирующее общий прирост прибыли фирмы.

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

При таком подходе можно использовать функциональные уравнения Беллмана. Для их решения в табулированном виде общий объем капиталовложений разбивается на N интервалов с шагом (для нашей задачи положим N = 4, тогда = 200/4=50 млн. руб.). Т.е. значения функций, входящих в уравнения Беллмана, будут определяться только в точках, кратных (в нашем примере в точках 0, 50, 100, 150, 200).

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

Кап. Вложения	Прирост прибыли по филиалам
	1	2	3	4
50	25	30	36	28
100	60	70	64	56
150	100	90	95	110
200	140	122	130	142

С =200 - общий объем распределяемых средств;

х - объем средств, выделяемых филиалам (на каждом шаге), 0? х ?C.

F_i(x_i) - ожидаемый прирост i-той фирмы при выделении ей х_i средств. Тогда целевая функция

F = F₁(x₁) + F₂(x₂) + F₃(x₃) + F₄(x₄) > max

при ограничении x₁ + x₂ + x₃ + x₄ = C, x_i ? 0, i = .

б) Схема решения.

1. Введем последовательность функций:

z₁(x) - max прибыль фирмы, если x средств выделить одному 1-му филиалу;

z₂(x) - max прибыль фирмы, если x средств распределить между 1-м и 2-м филиалами;

z₃(x) - max прибыль фирмы, если х средств распределить между 3-м и двумя первыми филиалами;

z₄(x) - max прибыль фирмы, при распределении x средств между всеми 4-мя филиалами.

Очевидно, что z₄(C) = max F = F*, a z_i(0) = 0.

2. «Обратный ход».

Рассмотрим финансирование только 1-го филиала, тогда по определению

z₁(x) = F₁(x). (1)

Пусть теперь средства в объеме x распределяются между 1-м и 2-м филиалами: 2-му в объеме x₂, тогда х - х₂ = х₁ выделяется 1-му. Общая прибыль двух филиалов

z₂(x) = (F₂(x₂) + z₁(x - x₂)). (2)

Теперь включим в рассмотрение дополнительно 3-й филиал: из общей суммы х выделим 3-му филиалу х₃, тогда остальная часть х - х₃ оптимальным образом распределяется между двумя первыми

z₃(x) = (F₃(x₃) + z₂(x - x₃)). (3)

Наконец, по аналогии находим

z₄(x) = (F₄(x₄) + z₃(x - x₄)). (4)

3. «Прямой ход».

Функциональные уравнения Беллмана (1) - (4) позволяют рассчитать значения z_i и F_i для всех возможных х. Среди них находим z₄(C) = F* и оптимальное x₄* такое, что

F₄(x₄*) = F₄*, после чего результаты вычислений просматриваются в обратном порядке. Зная x₄*, находим С-х₄* - объем финансирования остальных трех филиалов, а следовательно, и F₃* и х₃*, и т.д. до нахождения х₁* и F₁* = F₁(x₁*).

в) Расчет.

….

4. Задача о замене

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

Оборудование со временем изнашивается и стареет морально, падает его производительность, растут издержки на ремонт. Поэтому на каком-то этапе его эксплуатация становится менее выгодной, чем замена на новое. Возникает задача определения оптимальной стратегии замены оборудования в рассматриваемый временной промежуток - плановый период (п/п) с тем, чтобы суммарная прибыль за этот период была оптимальной.

Введем обозначения.

r(t) - стоимость продукции, производимой за год на оборудовании возраста t;

s(t) - остаточная стоимость оборудования возраста t;

u(t) - эксплуатационные издержки за год оборудования возраста t;

p - цена нового оборудования, которым можно заменить устаревшее:

n - число лет в рассматриваемом п/п.

Для дискретности решения задачи возраст оборудования t будем отсчитывать с интервалом 1 год. Управление составляют два возможных решения на каждом этапе (в начале каждого года): «сохранение» - продолжение эксплуатации имеющегося оборудования; «замена» - реализация старого оборудования по остаточной стоимости и приобретение нового по цене p. Целевая функция - суммарная прибыль за п/п F>max. Ограничения определяются критерием замены оборудования: прибыль при дальнейшей эксплуатации старого меньше прибыли после его замены с учетом всех издержек. Если прибыль от нового оборудования равна прибыли при старом, то старое сохраняется еще на год, т.к. оно уже досконально изучено.

б) Схема решения.

Задача решается методом ДП на основе принципа оптимальности Беллмана. В процессе «обратного хода» рассматриваются этапы - временные шаги от конца п/п к его началу.

Введем последовательность функций: z_i(t), i = - максимальная прибыль за последние i лет п/п. Очевидно, что z_n(t₀) = max F = F*, где t₀ - возраст оборудования в начале п/п. Итак, сначала рассматриваем только последний n-ый год п/п, i = 1. Пусть в начале этого года, когда оборудование имеет возраст t лет, выбирается одно из управлений: 1) сохранение оборудования на n-ый год, тогда прибыль за оставшийся год п/п составит r(t) - u(t); 2) замена новым, продажа старого по остаточной стоимости, тогда прибыль составит s(t) - p + r(0) - u(0), где r(0) - стоимость продукции, на новом оборудовании за 1-й год его эксплуатации, u(0) - эксплуатационные издержки нового оборудования за 1-й год. Определяем оптимальное управление, исходя из критерия замены:

- если s(t) - p + r(0) - u(0) ? r(t) - u (t), то «сохранить»,

- если s(t) - p + r(0) - u(0) > r(t) - u(t), то «заменить».

z₁(t) = max

Теперь включаем в рассмотрение предпоследний шаг, (n - 1)-й год, i = 2 и установим прибыль за два последних года z₂ (t).

Пусть в начале (n - 1)-го года возраст оборудования t, и было принято решение о его сохранении. Тогда прибыль к концу года зависит r (t) - u (t). При этом на начало n-го года оборудование уже будет иметь возраст t+1, следовательно, в последнем году оно даст прибыль z₁(t+1), а общая прибыль за два последних года составит r (t) - u (t) + z₁(t+1).

Если же в начале (n-1)-го года выбрано управление ”замена”, то прибыль за два последних года составит s (t) - p + r (0) - u (0) + z₁(1), следовательно,

z₂(t) = max

Аналогично для i последних лет:

z_i(t) = max

Дойдя до последнего шага (i = n), попадаем в начало п/п, где t известно: t = t₀, и, следовательно, можно начать ”прямой ход”.

Задавая t₀ и длительность п/п, находим F* = z_n(t₀) и строим последовательность оптимальных управлений, начиная с первого года и заканчивая последним.

в) Расчет.

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

1. Определить ц (t) = r(t) - u(t), m₁ = S(t) - p + ц(0):

- если m₁ = const, то справа к таблице прибавляется дополнительный столбец m_i;

- если m₁ = m₁(t), то над каждой строкой z_i(t) вводится дополнительная строка m_i = m_i(t) (или m_i(t) вписывается в клетки значений z_i(t) как тарифы транспортной задачи).

2. Заполнить строку z₁(t), переписав из таблицы данных соответствующие значения ц(t) ? m₁, все значения ц(t) < m₁ заменить на m₁.

3. Начиная с индекса i = 2, расчет по строкам производится в следующей последовательности:

а) вычислить m_i = m₁ + z_i-1(1), где z_i-1(1) берется из уже заполненной строки;

б) вычислить z_i(t) = z₁(t) + z_i-1(t+1), где сумма и слагаемые образуют треугольник, у которого одна из вершин всегда в первой строке над искомым значением, а 2-ая - в последней заполненной строке следующего столбца. Получаемые значения z_i(t) ? m_i вносить в соответствующие клетки строки; начиная с первого z_i(t) < m_i, оставшиеся клетки заполнить значением m_i;

в) клетки с первым значением z_i(t) < m_i в процессе заполнения таблицы отделить от расположенных в строке левее разделительной границей смены управления;

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

Замечания:

1. Для задачи об оптимальном распределении капиталовложений по полученной расчетной таблице можно получить стратегию вложения средств, например, только в первые 3 филиала, исключив из рассмотрения 4-й, или, например, для суммы в 150 млн. руб. (а не 200 ) между 4-мя филиалами, или только 3-мя первыми и т.д.

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

Это так называемый «принцип погружения» метода динамического программирования.

2. Решенную задачу о замене оборудования можно усложнить, например, допуская замену не новым оборудованием, а уже проработавшим некоторое время. При этом имеется три возможных управления: сохранить старое, купить новое, купить не новое.

5. Задача управления производством и запасами

Предприятие производит партиями некоторые изделия. Оно получило заказы на n месяцев. Необходимо составить план производства на указанные n месяцев с учетом затрат на производство и хранение. Обозначим:

1) x_j - число изделий, производимых в j-м месяце;

2) y_j - величина запаса к началу j-го месяца (Это число не содержит изделий, производимых в j-й месяц, величина запаса к началу 1-го месяца (y₁) и к концу последнего (y_n+1) заданы);