«МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УПРАВЛЕНИЯ Кафедра прикладной математики ( x - a )2 1 f N ( a ; ...»

В последней строке симплексной таблицы есть положительные коэффициенты 3 = 2 и 5 = 7 при свободных неизвестных x3 и x5, и при любой из этих неизвестных в системе уравнений есть хотя бы один положительный коэффициент. Так как max( j > 0) = 7 = 5, то при возрастании x5 целевая функция убывает наиболее быстро, считая при этом x3 = x4 = 0. Принимаем x5 за разрешающую неизвестную и подвергаем систему уравнений (**) симплексному преобразованию. Составляя отношения свободных членов уравнений системы (**) к соответствующим положительным коэффициентам при неизвестной x5 и находя min ; =, определяем, что в качестве разрешающего должно быть взято второе уравнение системы (**). Исключаем неизвестную х5 из всех уравнений вспомогательной системы (*****), кроме второго уравнения, по обычным правилам исключения, умножив второе уравнение на -4 и -7 и прибавив соответственно к первому и третьему уравнениям или же применив правило прямоугольников. Неизвестная x5 становится базисной, x2 — свободной.

Система (*****) преобразуется к виду:

Определяемое первыми двумя уравнениями этой системы базисное неотрицательное решение является одним из допустимых решений задачи линейного программирования (*)— (***). Отвечающее ему значение линейной формы равно Это решение также не является оптимальным и целевая функция убывает при возрастании x3, если положить x2 = x4 = 0. Принимаем неизвестную x3 за разрешающую и подвергаем первые два уравнения системы (******) симплексному преобразованию. Так как разрешающим уравнением будет первое, то исключаем неизвестную x из всех уравнений системы (******), кроме первого уравнения, и получим новую вспомогательную систему линейных уравнений, определяющую третье базисное неотрицательное решение системы ограничений и соответствующее ему значение целевой функции и т. д.

Полностью решение приведено в табл. 8.2.3. В четвертой симплексной таблице среди элементов j последней строки нет ни одного положительного. Поэтому четвертое базисное решение:

является оптимальным, а наименьшее значение линейной формы равно ( -17 ).

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

РЕШЕНИЕ. Математическая модель задачи:

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

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

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

Подчеркнем, что за каждой симплексной таблицей надо видеть вспомогательную СЛАУ из четырех уравнений, из которых первые три представляют некоторый предпочитаемый эквивалент системы условий задачи и определяют соответствующее базисное допустимое решение, а из последнего уравнения получается выражение функции цели через свободные неизвестные. Как видно из последней симплексной таблицы, является оптимальной производственная программа x1 = 27; x2 = 0; x3 = 0; x4 = 20, обеспечивающая предприятию наибольшую прибыль zmax = 1972; при этом остаток ресурса первого вида x5 = 0, второго вида x6 = 13, третьего вида x7 = 0.

Следует обратить внимание на экономический смысл элементов последней строки симплексной таблицы. Оценочные коэффициенты 1, 2, 3, 4 имеют смысл оценок технологий и показывают, насколько уменьшится прибыль, если произвести единицу соответствующей продукции. Например, коэффициент 3 = 7 при переменной x3 показывает, что если произвести одну единицу продукции третьего вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 7 единиц.

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

Теперь получим решение этой же задачи в пакете Microsoft Excel. Введём исходные данные в таблицу Microsoft Excel как показано на рис. 8.2.1, а: в ячейки B6:E8 введём элементы технологической матрицы A, в ячейки B3:E3 — элементы вектора удельной прибыли C, в в ячейки G6:G8 — запасы ресурсов (элементы ветора B). Ячейки B11:E11 отведём под компоненты плана производства ( x1, x2, x3, x4 ), а в ячейках G3 и соответственно (формулы Microsoft Excel приведены на рис. 8.2.1, а).

Запустим пакет «Поиск решения» (меню «Сервис | Поиск решения»). В появившемся диалоговом окне (рис. 8.2.1, б) укажем, что целевая функция рассчитывается в ячейке $I$3, переменные задачи находятся в ячейках $B$11:$E$11. С помощью кнопки «Добавить» добавим ограничения, состоящие в том, что расходы ресурсов не могут быть больше их запасов ($I$6 c j, то j-я технология не применяется:

если же по некоторому оптимальному плану производства j-я технология применяется:

то оценка ресурсов, расходуемых по этой технологии в единицу времени, равна цене произведенного за единицу времени по той же технологии продукта:

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

Пусть теперь рассматривается задача ЛП:

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

минимизировать при условиях где переменные y1, y2,..., ym могут принимать значения любого знака.

Будем считать, что в исходной задаче величины aij и c j остаются неизменными, а правые части bi системы ограничений подвергаются некоторым изменениям. Тогда каждому вектору B (b1, b2,..., bm ) ограничений будет отвечать свое оптимальное решение (если оно существует) и максимальное значение zmax функции цели, т. е.

zmax = zmax (b1, b2,..., bm ). Тесная связь между решениями пары двойственных задач ЛП состоит также и в том, что характер изменения величины zmax можно определить с помощью компонент оптимального решения двойственной задачи.

ТРЕТЬЯ ОСНОВНАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ (ТЕОРЕМА ОБ

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

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

Вернемся к задаче планирования производства (8.3.1)—(8.3.3). Предположим, что мы ее решили и нашли оптимальный план производства, а также указали «узкие места производства», т. е. какие ресурсы по оптимальному плану используются полностью а потому называются дефицитными. Будем расшивать «узкие места производства», т. е. заказывать дополнительно дефицитные ресурсы.

Обозначим через ti искомое дополнительное количество единиц i -го ресурса, т. е.

T (t1, t2,..., tm ) — вектор приращений объемов ресурсов, ( B + T ) — вектор новых объемов ресурсов. Прирост прибыли, приходящийся на ti единиц i -го ресурса, будет равен yi ti, где yi — двойственная оценка этого ресурса (согласно третьей основной теореме двойственности). Поэтому будем считать, что для задачи (8.3.1)—(8.3.3) мы составили двойственную задачу (8.3.4)-(8.3.6), решили ее и нашли двойственные оценки y1,..., ym всех ресурсов. При этом следует иметь ввиду, что найденными двойственными оценками ресурсов мы можем пользоваться только при таких изменениях объемов ресурсов и, соответственно, компонент оптимального плана, когда сохраняется структура плана производства и остаются постоянными двойственные оценки ресурсов.

Условие сохранения базисного набора неизвестных (условие устойчивости двойственных оценок), характеризуется неравенством или где Q–1 — обращенный базис, т. е. матрица, которая содержится в последней симплексной таблице на месте единичной матрицы в первой симплексной таблице.

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

Таким образом, проблема «расшивки узких мест» производства представляет собой задачу ЛП:

найти план расшивки T (t1, t2,..., tm ), максимизирующий суммарный прирост прибыли при условиях Система условий может содержать и другие ограничения. Например, если поставщик k-го вида сырья может увеличить количество поставляемого сырья не более, чем на d единиц, то появляется новое ограничение 165. Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов. Известна технологическая матрица A затрат любого ресурса на единицу каждой продукции, вектор B объемов ресурсов и вектор C удельной прибыли Согласно решению задачи 162, оптимальная производственная программа, обеспечивающая предприятию наибольшую прибыль zmax = 1972, такова: x1 = 27; x2 = 0; x3 = 0; x4 = 20; при этом остаток ресурса первого вида x5 = 0, второго вида x6 = 13, третьего вида x7 = 0.

Теперь представим себе, что возникла новая ситуация. Знакомый предприниматель П (Петров), занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам «уступить» по определенным ценам все имеющиеся у нас ресурсы и обещает платить y1 рублей за каждую единицу первого ресурса, y2 руб. — второго, y3 руб. — третьего. Определить, при каких ценах y1, y2, y3 мы можем согласиться с предложением П, т. е. двойственные, оценки ресурсов.

РЕШЕНИЕ. Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы A, 4 единицы ресурса первого вида, 2 единицы ресурса второго вида и 3 единицы третьего (элементы первого столбца матрицы). В ценах y1, y2, y3 наши затраты составят 4 y1 + 2 y2 + 3 y3, т. е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 36 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше 36:

Аналогично, во втором столбце матрицы A указаны затраты различных ресурсов на производство единицы продукции второго вида. В ценах П эти затраты составят 3 y1 + 5 y2 + y3, а на рынке за единицу продукции второго вида мы получили бы прибыль 14 рублей. Поэтому перед предпринимателем П мы ставим условие и так далее по всем видам продукции.

Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить 208 y1 + 107 y2 + 181 y3 руб. При поставленных нами условиях предприниматель П будет искать такие значения величин y1, y2, y3, чтобы эта сумма была как можно меньше.

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

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

и подставим в эти уравнения уже известную оптимальную производственную программу x1 = 27; x2 = 0; x3 = 0; x4 = 20:

или Второе из этих уравнений (y2(94 – 107) = 0) означает, что поскольку второй ресурс используется не полностью (при выполнении оптимальной производственной программы расходуется 94 единицы из 107), его двойственная оценка y2 = 0. Четвертое уравнение (27(4y1 + 2y2 + 3y3 – 36) = 0) означает, что поскольку первый продукт входит в оптимальную производственную программу (x1 = 27), то суммарная двойственная оценка ресурсов, из которых можно изготовить единицу продукта первого вида (4y1 + 2y2 + 3y3) должна быть равна цене этого продукта (36). Из последнего уравнения следует, что поскольку четвертый продукт входит в оптимальную производственную программу (x4 = 20), то суммарная двойственная оценка ресурсов, из которых можно изготовить единицу продукта четвертого вида (5y1 + 2y2 + 5y3) должна быть равна цене этого продукта (50). Итак, Решив эту систему уравнений, получим окончательно, что y2 = 6, y2 = 0, y2 = 4.

Задачи для самостоятельного решения 166. Цех выпускает трансформаторы двух видов. На один трансформатор первого вида нужно 5 кг железа и 3 кг проволоки, второго вида — 3 кг железа и 2 кг проволоки. От реализации одного трансформатора цех получает прибыль 6 и 5 ден. ед. соответственно. Цех располагает 4,8 т железа и 3 т проволоки. Определить, сколько трансформаторов каждого вида необходимо выпустить для получения максимальной прибыли, какие ресурсы образуют «узкие места» и найти двойственные оценки ресурсов.

167. На лесопилке из еловой и пихтовой древесины делают фанеру и брусы. На 100 м2 фанеры нужно 2 м3 еловой и 1 м3 пихтовой древесины и прибыль равна 170 ден. ед. На 100 пог. м елового бруса нужно 5 м3, а на 100 пог. м пихтового бруса нужно 4 м3 древесины, прибыль же равна соответственно 80 и 100 ден. ед. Найти оптимальный план производства, если запасы еловой и пихтовой древесины равны соответственно 100 м3 и 160 м3, определить, какие ресурсы образуют «узкие места» и найти двойственные оценки ресурсов.

168. Найти двойственные оценки и оценки технологий в задаче 1 к предыдущей главе.

169. Весной в колхозе решили засадить 100 га капустой, помидорами и огурцами. При расчетах решили исходить из урожайности прошлых лет:

80 т, 12 т и 10 т соответственно. Для нужд самих колхозников надо 400 т капусты, 60 т помидоров и 40 т огурцов. Излишки овощей будут сданы государству по ценам 5 руб., 30 руб. и 20 руб. за кг соответственно. Найти план посадок, максимизирующий выручку за сдачу излишков овощей государству, определить двойственную оценку ресурса — земли?

170. Банк имеет на 3 месяца свободные ресурсы в количестве 10 млн.

рублей. Вложение в ГКО даст 29%, на межбанковском рынке можно получить 17%, вложение в валюту с последующей конвертацией даст только 14%. Составьте задачу распределения свободных средств с целью максимизации процентного дохода. Составить двойственную задачу и определить двойственную оценку ресурса — денег?

Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в m пунктах производства (хранения) в количествах a1, a2,…, am единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно b1, b2,…, bn единиц. Стоимость перевозки единицы продукта из iго пункта отправления в j-й пункт назначения равна cij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства, и общие транспортные расходы по доставке продуктов были минимальны.

Если производство и потребление сбалансированы, т. е. суммарные запасы продукта у поставщиков равны суммарным запросам потребителей:

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

Для сведения открытой задачи к закрытой вводятся фиктивные пункты производства или потребления. Если суммарные запасы продукта у поставщиков строго больше, чем суммарные запросы потребителей, вводится фиктивный потребитель, запроm n сы которого равны строго больше, чем суммарные запросы потребителей, то вводится фиктивный поn m Обозначим через xij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю. При наличии баланса производства и потребления (8.4.1) математическая модель транспортной задачи будет выглядеть так:

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

Следует иметь в виду, что по любой транспортной таблице можно восстановить соответствующий предпочитаемый эквивалент системы уравнений (8.4.3)—(8.4.4), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является базисной. Так как в системе (8.4.3)—(8.4.4) ровно ( m + n - 1 ) линейно независимых уравнений, то в любой транспортной таблице должно быть m + n - 1 занятых клеток.

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

• если остаток продукта у i-го поставщика после предыдущих шагов меньше, чем неудовлетворенный запрос j-го потребителя, то исключается из рассмотрения i-й поставщик, и в клетку (i, j) заносится поставка xij, равная остатку продукта у i-го поставщика после предыдущих шагов;

• если остаток продукта у i-го поставщика после предыдущих шагов больше, чем неудовлетворенный запрос j-го потребителя, то исключается из рассмотрения j-й потребитель, и в клетку (i, j) заносится поставка xij, равная неудовлетворенному запросу j-го потребителя;

• если остаток продукта у i-го поставщика после предыдущих шагов равен неудовлетворенному запросу j-го потребителя, то исключается из рассмотрения и л и i-й поставщик, и л и j-й потребитель, и в клетку (i, j) заносится поставка xij= 0 равная остатку продукта у i-го поставщика после предыдущих шагов;

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

Каждому поставщику ставится в соответствие потенциал pi, а каждому потребителю — потенциал qj. При этом каждой клетке соответствует некоторая оценка Один из потенциалов можно выбрать произвольно, так как в системе (8.4.3)— (8.4.4) одно уравнение линейно зависит от остальных. Обычно полагают p1 = 0. Остальные потенциалы вычисляются из условия, что для базисных клеток ij = 0.

Затем по формуле (8.4.6) вычисляются оценки всех свободных клеток.

Если хотя бы одна из оценок строго положительна, то базисное допустимое решение, содержащееся в данной транспортной таблице, не является оптимальным. Выбирается свободная клетка (r, s), соответствующая наибольшей положительной оценке Для выбранной свободной клетки (r, s) строится цикл пересчета — замкнутая ломаная, одна из вершин которой находится в данной свободной клетке, а все остальные — в занятых клетках, соседние звенья взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы. Можно доказать, что цикл пересчета всегда существует и состоит из четного числа вершин Клетка (r, s) помечается знаком «плюс», далее соседние вершины цикла пересчета помечаются по очереди знаками «минус», «плюс». Выбирается минимальная из поставок, отмеченных знаком «минус» max, и к поставкам, отмеченным знаком «плюс», добавляется max, а из поставок отмеченных знаком «минус», вычитается max. Так производится перераспределение поставок вдоль цикла пересчета, при котором происходит такой переход к новому базисному допустимому решению, что в клетку (r, s), соответствующую наибольшей положительной оценке rs, поставляется максимально возможное количество продукта max. При этом от всех поставщиков продукт полностью вывозится, и запросы всех потребителей полностью удовлетворяются.

Заполняется новая транспортная таблица, вычисляются новые потенциалы и оценки клеток и т.д.

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

Отметим, что для вычисления потенциалов необходимо (m + n – 1) уравнений (8.4.6), т. е. на каждом шаге метода потенциалов число занятых клеток должно сохраняться.

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

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

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

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

Потенциалы же интерпретируются следующим образом. Каждый производитель уплачивает перевозчику одну и ту же цену pi за вывоз единицы груза (не важно, какому потребителю этот груз достанется); каждый потребитель уплачивает перевозчику одну и ту же цену qj за получение единицы груза (не важно, от какого производителя этот груз доставлен); сумма цен, взимаемых при этом с любой пары «производитель – потребитель», не превосходит реальной стоимости перевозки единицы груза от данного производителя к данному потребителю:

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

при условиях (8.4.7).

Переменные pi и qj при этом могут быть как положительными, так и отрицательными: не исключено, что перевозчик платит определенному производителю за право перевозить его продукцию (или потребителю — за право доставлять ему продукцию):

Задача максимизации функции (8.4.8) при условиях (8.4.7) и произвольных вещественных значениях переменных pi и qj является двойственной к транспортной задача (8.4.2)—(8.4.5), и приведенная экономическая интерпретации оценок клеток и потенциалов основана на теоремах двойственности.

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

171. Решить с помощью метода потенциалов транспортную задачу при заданном векторе объемов производства A, векторе потребления B и матрице транспортных издержек C:

РЕШЕНИЕ. Общий объем производства ai = 54 + 60 + 63 = 177 больше, чем требуi = ется всем потребителям b j = 41 + 50 + 44 + 30 = 165, т. е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 177 - 165 = 12 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

Первое базисное допустимое решение построим по правилу северо-западного угла:

Производство Положим p1 = 0, и найдем остальные потенциалы из условия, что для базисных клеток ij = 0 :

и т. д. В результате получим: q3 = 0, p3 = 6, q4 = 1, q5 = -6.

Затем по формуле (8.4.6) вычисляем оценки всех свободных клеток:

Находим наибольшую положительную оценку Для найденной свободной клетки 31 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные — в занятых клетках. Это будет 31 – 11 – 12 – 22 – 23 – 33. Производим перераспределение поставок вдоль цикла пересчета ( max = 21 ):

Получаем второе базисное допустимое решение:

Производство Находим новые потенциалы, новые оценки. Наибольшую положительную оценку будет иметь свободная клетка 14. Для нее строим цикл пересчета 14 – 11 – 31 – производим перераспределение ( max = 20 ):

и получаем третье базисное допустимое решение. Продолжаем процесс до те пор, пока не придем к таблице, для которой все Читателю не составит труда проверить, что будет оптимальным базисное допустимое решение Задачи для самостоятельного решения 172. Решить с помощью метода потенциалов транспортную задачу при заданном векторе объемов производства A, векторе потребления B и матрице транспортных издержек C:

173. Найти решение предыдущей задачи с помощью пакета Microsoft Excel.

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

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

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

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

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

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

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

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

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

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

Предположим, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через f j ( x j ) прирост мощности или прибыли на j -м предприятии, если оно получит x j рублей капитальных вложений. Требуется найти такое распределение ( x1, x2,…, xn ) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли при ограничении по общей сумме капитальных вложений причем будем считать, что все переменные x j принимают только целые неотрицательные значения Функции f j ( x j ) мы считаем заданными, заметив, что их определение — довольно трудоемкая экономическая задача.

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

Введем параметр состояния и определим функцию состояния. За параметр состояния примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk () определим как максимальную прибыль на первых k предприятиях, если они вместе получают руб. Параметр может изменяться от 0 до b. Если из руб. k -е предприятие получит xk руб., то каково бы ни было это значение, остальные ( - xk ) руб. естественно распределить между предприятиями от первого до ( k - 1 )-го так, чтобы была получена максимальная прибыль Fk -1 ( - xk ). Тогда прибыль k предприятий будет равна f k ( xk ) + Fk -1 ( - xk ). Надо выбрать такое значение xk между 0 и, чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению для k = 2,3,…, n. Если же k = 1, то 174. Производственное объединение состоит из четырех предприятий (n = 4). Общая сумма капитальных вложений равна 700 тыс. руб. (b = 700), выделяемые предприятиям суммы кратны 100 тыс. руб. Значения функций f j () приведены в табл. 9.1.1, где, например, число 88 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 88 тыс. руб.

РЕШЕНИЕ. Прежде всего заполняем табл. 9.1.2. Значения f2() складываем со значениями F1 ( - x2 ) = f1 ( - x2 ) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение x 2 (). Затем заполняем табл. 9.1.3.

Продолжая процесс, табулируем функции F3 (), x3 () и т. д. В табл. 9.1.6 заполняем только одну диагональ для значения = 700. Наибольшее число на этой диагонали:

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

Оно обеспечивает производственному объединению наибольший возможный прирост прибыли 155 тыс. руб.

Читателю рекомендуется проверить выполнение равенства Задачи для самостоятельного решения 175. Производственное объединение состоит из четырех предприятий (n = 4). Общая сумма капитальных вложений равна 700 тыс. руб. (b = 700), выделяемые предприятиям суммы кратны 100 тыс. руб. Значения функций f j () таковы:

176. Планируется деятельность двух предприятий в течение четырех лет. Задано начальное количество ресурсов 0 = 1000. Средства x, вложенные в первое предприятие, приносят к концу года доход f1(x) = 0,4x и возвращаются к концу года в размере 1(x) = 0,5x, а средства 0 – x, вложенные во второе предприятие, дают доход f2(0 – x) = 0,8(0 – x) и возвращаются к концу года в размере 2(0 – x) = 0,8(0 – x). По истечении года все средства заново распределяются между этими предприятиями, новых средств не поступает, и доход в производство не вкладывается. Требуется указать такое распределение ресурсов на каждом этапе, при котором суммарный доход за четыре года будет наибольшим.

Пусть требуется найти безусловный минимум функции f ( x1, x2,..., xn ). Направление наибыстрейшего возрастания функции в данной точке x характеризуется вектором-градиентом grad f (x), компонентами которого служат значения частных производных, вычисленные в данной точке. Процесс последовательного приближения к точке минимума состоит в том, что выбирается произвольная точка, достаточно малый шаг и производится смещение в новую точку в направлении антиградиента, т. е.

на k -м шаге формула перехода будет где h — длина шага смещения. Будем иметь f (x k +1 ) < f (x k ). Если же последнее неравенство нарушено, то это может означать, что мы «перешагнули» точку минимума.

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

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

Рассмотрим теперь задачу выпуклого программирования где f, i — выпуклые функции. Будем считать, что ограничения по знаку переменных включены в (9.2.4).

Для решения данной задачи предложено большое число различных методов штрафных и барьерных функций. Один из них, метод внешних штрафных функций, состоит в некотором видоизменении вышеописанного градиентного метода. Чуть его в том, что если на некотором этапе (может быть, в самом начале) движущаяся точка x k окажется вне допустимой области, определяемой соотношениями (9.2.4), то налагается «штраф» так, чтобы точка вернулась внутрь области. Для этого мы можем, представив точку как материальную, «ударить» по ней так, чтобы она сместилась на выбранную длину шага в направлении антиградиента нарушенного ограничения. Такая последовательность переходов x k x k +1 описывается соотношениями где Ri (xk ) — величина штрафа в точке x k (сила удара):

т. е. штрафа нет, если ограничение не нарушено.

Метод барьеров, или внутренних штрафных функций, отличается от рассмотренного метода внешних штрафных функций тем, что начальная точка может быть выбрана только внутри допустимой области и величины штрафа резко возрастает при приближении движущейся точки к «изгороди», определяемой каким-либо неравенством системы (9.2.5), и точка не может выйти за пределы допустимой области.

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

Обозначим i-й частный критерий через zi ( x), а область допустимых решений через Q.

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

В идеальном случае в задаче (9.2.7)—(9.2.8) можно вести поиск такого решения, которое принадлежит пересечению множеств оптимальных решений всех однокритериальных задач. Но указанное пересечение обычно оказывается пустым множеством, и потому приходится рассматривать переговорное множество или множество Парето». Вектор x* Q называется эффективным решением, если не существует такого причем хотя бы для одного i имеет место строгое неравенство. Множество допустимых решений, для которых невозможно одновременно улучшить все частные показатели эффективности, принято называть областью Парето или областью компромиссов, а принадлежащие ей решения — эффективными или оптимальными по Парето.

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

Метод последовательных уступок решения многокритериальных задач применяется в случае, когда частные критерии могут быть упорядочены в порядке убывающей важности. Предположим, что все критерии максимизируются и пронумерованы в порядке убывания их важности. Находим максимальное значение z1, первого по важности критерия в области допустимых решений, решив задачу Затем назначается, исходя из практических соображений и принятой точности, величина допустимого отклонения 1 > 0 (экономически оправданной уступки) критерия z1 и отыскивается максимальное значение второго критерия z2 при условии, что значение первого должно отклоняться от максимального не более, чем на величину допустимой уступки, т. е. решается задача Снова назначается величина уступки 2 > 0 по второму критерию, которая вместе с первой используется при нахождении условного экстремума третьего частного критерия, и т. д. Наконец, выявляется экстремальное значение последнего по важности критерия z2 при условии, что значение каждого из первых m - 1 частных критериев отличается от экстремального не более, чем на величину допустимой уступки. Получаемое на последнем этапе решение считается оптимальным. Остается заметить, что этот метод не всегда приводит к эффективному решению.

177. Найти минимум функции РЕШЕНИЕ. Нетрудно проверить, что данная функция является выпуклой, и потому найденный минимум будет абсолютным. Выберем начальную точку, например, x (4; 1). Находим Согласно (9.2.2) координаты следующей точки x1 ( x1, x1 ) будут:

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

178. Методом штрафных функций найти точку минимума функции при условии РЕШЕНИЕ. В качестве начального приближения возьмем точку x (0; 0). Очевидно, ( x ) > 5, т. е. ограничение (**) нарушено и точка находится вне допустимой области.

Накладываем штраф. Положим, например, R (x ) = 5.

Находим градиенты функций f и в данной точке. Получаем:

Величину шага смещения h примем равной 0,1. Согласно (9.2.5) координаты следующей точки x1 будут Точка x1 (2,3; 3, 4) находится внутри допустимой области, так как (x1 ) < 0. Штраф не накладываем, следующее приближение находим по формуле (9.2.1):

Произведя необходимые вычисления, получим точку x 2 (2,52; 3,12). Очевидно f ( x 2 ) < f ( x1 ). Как только очередное приближение x k нарушит ограничение (**), накладываем штраф. Длину шага и величину штрафа можно менять. Продолжительность процесса последовательных приближений зависит от заданной точности.

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

РЕШЕНИЕ. Очевидно, в данной случае область компромиссов совпадает с областью допустимых решений.

Будем считать, что допустимые уступки по первым двум критериям заданы:

Рис. 9.2.1. Графическое решение задачи векторной оптимизации Максимизируем функцию z1, при условиях (****). Это легко сделать графически (рис. 9.2.1, а). Получаем Переходим к максимизации функции z1 при условиях (****) и дополнительном ограничении, позволяющем учесть, что по критерию z1, нельзя уступать более чем на 1. Так как z1 = 4 - 1, то дополнительное ограничение будет иметь вид Задачу (**), (****), (*****) решаем графически (рис. 9.2.1, б). Получаем Теперь уступаем по критерию z1 на 1 и получаем второе дополнительное ограничение Максимизируем z3 при условиях (****), (*****), (******) графически (рис.

9.2.1, в). Получаем оптимальное решение трехкритериальной задачи x1 = 2, x2 = 3.

Задачи для самостоятельного решения 180. Методом наискорейшего спуска (подъема) решить задачу безусловной оптимизации 181. Методом штрафных функций решить задачу нелинейного программирования 182. Методом последовательных уступок решить задачу трехкритериальной оптимизации § 9.3. Оптимизационные задачи на графах Широкое распространение в задачах управления получили модели в виде графов благодаря дополнительным возможностям, которые появляются при геометрическом подходе к описанию и трактовке процессов управления. Среди графовых моделей особую роль играют потоковые модели, часто называемые транспортными сетями только из-за того, что первоначально они возникли при решении транспортной задачи. К транспортным сетям сводятся многие практические задачи управления, например, задача об оптимальном назначении, о складе, о поставщике, о спросе и предложении, о кратчайшем пути, об оптимальном использовании дорог, об оптимальном по стоимости сетевом графике и другие.

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

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

Обозначим вершины графа X 1, X 2,…, X n, а дугу, соединяющую вершину X i c X j в направлении от X i к X j — uij. Граф, образованный множеством вершин X и множеством дуг U, обозначают ( X,U ).

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

Две дуги графа (два ребра) называются смежными, если они различны и имеют общую вершину. Две вершины графа называются смежными, если существует дуга (ребро), соединяющая их.

Говорят, что дуга исходит из вершины X i, если X i является ее началом. Дуга заходит в вершину X j, если X j является ее концом. Такую дугу мы обозначим через. uij.

Говорят, что в графе данная дуга инцидентна данной вершине, если эта вершина является началом или концом данной дуги.

данной вершине.

Путь в ориентированном графе — это последовательность дуг, в которой конец предыдущей дуги совпадает с началом следующей. Обозначим путь, последовательность вершин которого X i1, X i2,..., X ik.

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

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

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

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

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

Рассмотрим задачу о максимальном потоке в сети.

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

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

Каждая совокупность пунктов вместе с соединяющими их дорогами схематически может быть изображена в виде некоторой сети, в которой линии соответствуют дорогам, а пересечения — отдельным пунктам или станциям. Поэтому рассмотрим ориентированный граф с ( n + 1 ) вершиной X 0, X 1, X 2,..., X n, где некоторые упорядоченные пары точек X i, X j соединены дугами uij, причем каждой такой дуге поставлено в соответствие неотрицательное число cij = c(uij ), называемое ее пропускной способностью.

Зафиксируем какие-нибудь две вершины графа, например, X 0 и X n. По путям µ{ X 0, X i, X j,..., X k, X n } составленным из дуг ( X 0, X i ), ( X i, X j ),..., ( X k, X n ) сети и не образующих контуров, направляется жидкость, газ или транспорт из точки X 0 сети в точку X n. Назовем X 0 входом сети, X n — выходом. Пропускная способность cij дуги ( X i, X j ) определяет максимальное количество вещества, которое может пропустить эта дуга за единицу времени. Если какая-то пара точек X k, X l не соединена дугой, то будем считать ckl = 0. Кроме того, будем считать рассматриваемый граф симметрическим, т. е. если в сеть входит дуга ( X i, X j ), то в нее входит и симметричная дуга ( X j, X i ), причем пропускные способности этих дуг могут быть различными: cij c ji.

Потоком zij по дуге ( X i, X j ) называется количество вещества, проходящее через эту дугу в единицу времени. Потоком по сети, или просто потоком, назовем совокупность {zij } потоков по всем дугам сети. Будем считать, что потоки удовлетворяют следующим ограничениям:

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

В уравнениях (9.3.2) уменьшаемая сумма z0 k + z1k + + zn -1,k представляет количество вещества, притекающего в вершину X k по всем входящим в эту вершину дугам (если из X l в X k не входит дуга, то zlk = 0 ), а вычитаемая сумма zk1 + zk 2 + + zkn представляет количество вещества, вытекающего из вершины X k по всем выходящим из этой вершины дугам (также zkl = 0, если нет дуги ( X k, X l ). Таким образом, ограничения (9.3.2) означают, что количество вещества, притекающего в произвольную точку сети (кроме X 0 и X n ), равно количеству вещества, вытекающего из этой точки. Поток, удовлетворяющий ограничениям (9.3.1) и (9.3.2), будем называть допустимым.

текающего из вершины X 0 (входа сети), совпадает с общим количеством вещества z, притекающего в вершину X n (выход сети), т. е.

Линейная форма w называется величиной потока в сети.

Таким образом, задача о максимальном потоке в сети представляет собой задачу ЛП: среди всех решений системы линейных ограничений (9.3.1- 5.2) следует найти такое решение, которое максимизирует линейную форму (9.3.3). Это решение zij называется максимальным потоком в сети.

Как и любая задача ЛП, она может быть решена одним из известных методов ЛП.

Но в силу специфики задачи ее легче решить специальными методами.

Введем некоторые дополнительные понятия. Разобьем множество всех вершин сети на два непересекающихся подмножества P и Q так, чтобы X 0 P, a X n Q. Сечением ( P, Q) сети назовем совокупность всех дуг ( X i, X j ), концы которых принадлежат разным подмножествам. Каждому сечению ( P, Q) поставим в соответствие число C ( P, Q) — пропускную способность сечения – равное сумме пропускных способностей всех дуг сети, начинающихся в P и кончающихся в Q, т. е.

Любой путь из X 0 в X n обязательно содержит хотя бы одну дугу сечения ( P, Q), которая начинается в P и кончается в Q. Но пропускная способность пути не превышает пропускной способности каждой его дуги. Поэтому величина любого потока из X 0 в X n, являющаяся суммарной пропускной способностью всех путей из X 0 в X n, не может превысить пропускной способности любого сечения ( P, Q), т. е. всегда Отсюда заключаем, что если удается построить такой поток {zij }, при котором величина его w* окажется равной пропускной способности некоторого сечения ( P *, Q* ), т. е. z * = C ( P*, Q* ), то этот поток будет максимальным, а ( P *, Q* ) — сечением с минимальной пропускной способностью.

Введем еще одно понятие. Пусть задан некоторый поток {zij }. Будем говорить, что дуга uij с началом в X i и концом в вершине X j является насыщенной, если zij = cij, т. е. величина потока по этой дуге равна пропускной способности дуги. Если же величина потока по дуге меньше пропускной способности дуги zij < cij, то такую дугу называют ненасыщенной.

АЛГОРИТМ ОПРЕДЕЛЕНИЯ МАКСИМАЛЬНОГО ПОТОКА.

1. Построить какой-нибудь начальный поток {zij }.

2. Проверить, можно ли построить путь из X 0 в X n, состоящий только из ненасыщенных дуг. Если нет, то построенный ранее поток максимален. Если да, то перейти к пункту 3.

3. Выделить какой-нибудь путь, ведущий из X 0 в X n по ненасыщенным дугам, найти минимальную пропускную способность дуг этого пути и увеличить поток через каждую дугу этого пути на. Построить новый поток. Перейти к пункту 2.

Алгоритм может остановиться в том случае, если не удается построить путь из X в X n по ненасыщенным дугам. В противном случае алгоритм может быть продолжен.

При этом на каждом шаге образуется по крайней мере одна новая насыщенная дуга.

Так как число дуг в сети конечно, то пункт 3 может выполняться лишь конечное число раз, поэтому указанный алгоритм обязательно построит максимальный поток, и притом за конечное число шагов Следует обратить особое внимание на выполнение пункта 3. Если по некоторому пути µ мы пропустили поток величиной, то пропускные способности всех дуг этого пути следует уменьшить на, т. е. новая пропускная способность дуги ( X i, X j ) пути будет равна cij = cij -. Эта дуга может участвовать в последующем выборе нового пути, но с уменьшенной пропускной способностью. Поэтому вычисление новых пропускных способностей всех звеньев найденного пути совершенно необходимо. Кроме того, надо также учесть возможность существования вместо найденного пути другого, в котором участвует некоторая дуга, симметричная одной из дуг предыдущего пути. Для этого пропускные способности всех дуг, симметричных дугам старого пути, следует увеличить на, т. е. пропускную способность дуги ( X i, X j ), симметричной использованной в предшествующем пути дуге ( X i, X j ), надо считать равной c ji = c ji +. Это следует из того, что дуга ( X j, X i ) не препятствует доставке в X i количества c ji вещества по новому пути с использованием этой дуги плюс количества по части старого пути от X 0 до X i без использования этой дуги (так как пропускная способность всех дуг старого пути не меньше ). Мы учитываем, что X i теперь соединена с X 0 двумя путями, т. е. получается, что дуга ( X j, X i ) как бы заменена новой дугой с увеличенной пропускной способностью c ji +.

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

1. находим какой-нибудь путь µ из X 0 в X n, идущий по ненасыщенным дугам;

2. определяем пропускную способность µ найденного пути как наименьшую из пропускных способностей дуг этого пути 3. вычисляем новые пропускные способности всех дуг данного пути:

4. вычисляем новые пропускные способности всех тех дуг, которые симметричны дугам данного пути 5. продолжаем процесс до тех пор, пока удается построить путь из X 0 в X n, идущий по ненасыщенным дугам. Если такой путь построить нельзя, то это означает, что из источника X 0 в сток X n пропущен максимальный поток. Вычитаем пропускную способность соответствующей дуги исходной сети. Положительные значения найденных разностей определяют величины потоков по дугам в максимальном потоке данной сети, а величина максимального потока в сети равна В заключение подчеркнем еще раз, что алгоритм обрывается, как только будет получена сеть, в которой нельзя построить ни одного пути из X 0 в X n, идущего по ненасыщенным дугам. Покажем, что полученный таким образом поток является максимальным. Для этого построим в последней сети сечение ( P, Q) следующим образом.

К множеству P отнесем источник X 0 и все те вершины, которые достижимы из X по какому-нибудь пути, составленному из ненасыщенных дуг, а все остальные вершины сети (недостижимые) отнесем к множеству Q. Очевидно, X n Q, так как не существует никакого ненасыщенного пути из X 0 в X n.

Все дуги сечения ( P, Q), направленные из P в Q, загружены полностью до пропускных способностей (т. е. для величины потока zij по дуге ( X i, X j ) при X i P, X j Q имеем zij = cij ), а дуги ( X j, X i ) противоположного направления, идущие из Q в P, в построенном потоке не используются (т. е. z ji = 0 при X j Q, X i P ), так что величина потока равна т. е. построенный поток максимален, а ( P, Q) — сечение с минимальной пропускной способностью (минимальное сечение).

Пусть дан граф ( X,U ). Каждой дуге графа поставим в соответствие положительное число l(u). Это число можно назвать длиной дуги. Тогда за длину пути µ принимается сумма дуг, входящих в µ, В задаче о кратчайшем пути требуется на графе Г найти кратчайший путь — путь наименьшей длины из вершины X0 в вершину Xn.

АЛГОРИТМ ОПРЕДЕЛЕНИЯ КРАТЧАЙШЕГО ПУТИ.

1. Присвоить каждой вершине Xi метку i так, чтобы 0 = 0, i = + (i > 0).

2. Найти дугу u = uij = (Xi, Xj), для которой выполняется неравенство j – i > l(uij) (полагая, что – = 0). Заменить метку вершины xj на новую, меньшую метку j = = i + l(uij).

3. Пункт 2 применять до тех пор, пока для каждой дуги uij не станет справедливым неравенство j - i l (uij ).

5. Найти вершину Xk, из которой выходит дуга, приходящая в Xn, и для которой n = k + l(ukn), затем вершину Xm, из которой выходит дуга, приходящая в Xk, и для которой k = m + l(umk) и т. д. На некотором шаге Xp совпадет с вершиной X0. Путь µ = (Xp, …, Xm, Xk, Xn) будет кратчайшим, и его длина будет равна n.

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

В задаче о критическом пути требуется на графе Г найти критический путь — путь наибольшей длины из вершины X0 в вершину Xn.

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

АЛГОРИТМ ОПРЕДЕЛЕНИЯ КРИТИЧЕСКОГО ПУТИ.

1. Присвоить каждой вершине Xi метку i так, чтобы 0 = 0, i = – (i > 0).

2. Найти дугу u = uij = (Xi, Xj), для которой выполняется неравенство j – i < l(uij) (полагая, что – = 0). Заменить метку вершины Xj на новую, большую метку j = = i + l(uij).

3. Пункт 2 применять до тех пор, пока для каждой дуги uij не станет справедливым неравенство j - i l (uij ).

5. Найти вершину Xk, из которой выходит дуга, приходящая в Xn, и для которой n = k + l(ukn), затем вершину Xm, из которой выходит дуга, приходящая в Xk, и для которой k = m + l(umk) и т. д. На некотором шаге Xp совпадет с вершиной X0. Путь µ = (Xp, …, Xm, Xk, Xn) будет критическим, и его длина будет равна n.

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

РЕШЕНИЕ. В качестве начального возьмем нулевой поток, когда все zij = 0.

Найдем какой-нибудь путь из X 0 в X 8, например, µ1 = { X 0, X 5, X 8 }.

По этому пути можно пропустить поток величиной не более Предположим, что поток такой величины 2 по указанному пути мы пропустили.

Получили новый поток {z }. При этом пропускные способности дуг пути и симметij ричных им дуг изменяются. Согласно (9.3.5) и (9.3.6), пропускные способности дуг пути уменьшаются на 2 единицы:

т. е. дуга ( X 5, X 8 ) становится насыщенной, а пропускные способности дуг, симметричных дугам пути, увеличиваются на 2 единицы:

Сеть с новыми пропускными способностями дуг приведена на рис.9.3.1, б.

Рис. 9.3.1. Определение максимального потока в сети Теперь находим новый путь из X 0 в X 8, проходящий по ненасыщенным дугам, например, µ 2 = { X 0, X 5, X 4, X 6, X 8 }, определяем и пропускаем по этому пути поток величиной в одну единицу. Меняем пропускные способности дуг этого пути и симметричных им дуг:

Дуга ( X 4, X 6 ) становится насыщенной. Сеть с измененными пропускными способностями приведена на рис. 9.3.1, в.

Далее последовательно находим пути µ 3,µ 4,µ 5,µ 6 и по ним пропускаем потоки величиной 3, 4,5, 6 соответственно:

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

Чтобы определить максимальный поток, вычитаем от пропускных способностей дуг исходной сети (рис. 9.3.1, а) измененные пропускные способности тех же дуг последней сети (рис. 9.3.1, ж). Результат приведен на рис. 9.3.1, з. Положительные значения найденных разностей дают нам величины zij потоков по соответствующим дугам ( X i, X j ) в максимальном потоке из источника X 0 в сток X 8. Искомый максимальной поток приведен на рис. 9.3.1, и, где числа, стоящие у каждой дуги, показывают величину потока по данной дуге, а стрелки — направление потока по этой дуге.

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

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

В нулевой строке таблицы выберем какой-нибудь элемент c0j, отличный от нуля, например, c05, стоящий в пятом столбце. Из вершины X0 можно перейти в X5. Для наглядности дугу (X0, X5) проведем прямо в нулевой строке таблицы из нулевого столбца в пятый, выделив начало дуги кружочком, конец — стрелкой. Теперь мы находимся в вершине X5. Чтобы зафиксировать это, сместимся по пятому столбцу до строки с тем же пятым номером и отметим эту клетку кружочком, а переход по вертикали — пунктиром. В пятой строке имеются три ненулевых элемента соответственно в нулевом, четвертом и восьмом столбцах. Это означает, что из X5 можно перейти или в X или в X4 или в X8. Возвращаться в X0 нет смысла, лучше всего идти в сток X8. Этот переход изображен стрелкой в пятой строке с началом в пятом столбце и концом — в восьмом. Таким образом, по таблице мы нашли путь, ведущий по ненасыщенным дугам из источника в сток:

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

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

В данном случае 1 = 2.

Чтобы вычислить новые пропускные способности дуг найденного пути и симметричных им дуг, достаточно, согласно (9.3.5) и (9.3.6), из всех чисел, отмеченных знаком минус, вычесть наименьшую пропускную способность 1, а ко всем числам, отмеченным знаком плюс, прибавить 1. Получаем табл. 9.3.2 с измененными пропускными способностями дуг сети. Она соответствует рис. 9.3.1, б. По таблице находим путь отмечаем знаком минус пропускные способности дуг этого пути (они записаны в клетках на концах стрелок), знаком плюс — пропускные способности симметричных Выполнив еще четыре шага, придем к табл. 9.3.4. Из этой таблицы видно, что не существует ни одного пути из источника в сток. Действительно, из X0 можно перейти в X5. Далее, так как в пятой строке только два ненулевых элемента c50 и c54, можно перейти либо в X0 (вернуться, что бессмысленно), либо в X4. Но в четвертой строке только один элемент c45, отличный от нуля. Поэтому из вершины X4 можно перейти только в X5, т. е. опять появляется контур. Никаких других возможностей нет. Следовательно, увеличить поток нельзя.

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

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

185. Пункты X0 и X8 связаны сетью дорог, проходящих через промежуточные пункты. Стоимость проезда из пункта Xi в Xj указана на графе. Определить минимальную стоимость проезда из X0 и X8.

186. Основу строительства объекта составляют 12 операций, последовательность выполнения и продолжительность которых задана в таблице.

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

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

Рассмотрим конфликт двух участников с противоположными интересами. Математической моделью такого конфликта является игра с нулевой суммой. Участники игры называются игроками. Стратегией игрока называется осознанный выбор одного из множества возможных вариантов его действий. Будем рассматривать конечные игры, в которых множества стратегий игроков конечны; стратегии первого игрока пронумеруем от 1 до m, а стратегии второго игрока — от 1 до n.

Если первый игрок выбрал свою i-ю стратегию, а второй игрок — свою j-ю стратегию, то результатом такого совместного выбора будет платеж aij второго игрока первому (это не обязательно денежная сумма, а любая оценка последствий выбора игроками своих стратегий). Таким образом, игра с нулевой суммой однозначно определяется матрицей которая называется платежной. Строки этой матрицы соответствуют стратегиям первого игрока, а столбцы — стратегиям второго игрока.

Игра происходит партиями. Партия игры состоит в том, что игроки одновременно называют свой выбор: первый игрок называет нектороый номер строки матрицы (по своему выбору), а второй — некоторый номер столбца этой матрицы (также по своему выбору). После этого происходит «расплата». Пусть, например, первый игрок назвал номер i, а второй — j. Тогда второй игрок платит первому сумму aij (не обязательно выраженную в денежных единицах). На этом партия игры заканчивается. Если aij > 0, то это означает, что при выборе первым игроком i-й стратегии, а вторым — j-й стратегии выигрывает первый игрок, если же aij < 0, то это значит, что при данном выборе стратегий выигрывает второй игрок.

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

Стратегия называется чистой, если выбор игрока неизменен от партии к партии. У первого игрока, очевидно, есть m чистых стратегий, а у второго — n.

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

Рассмотрим описанную конфликтную ситуацию с точки зрения первого игрока.

Если мы выбираем свою i-ю стратегию (строку матрицы П), то второй игрок, будучи разумным, выберет такую стратегию, чтобы обеспечить себе наибольший выигрыш (а нам, соответственно, наименьший), т. е. он выберет такой столбец матрицы П, в котором платеж aij (второго игрока первому) минимален. Переберем все наши стратегии i = 1, 2,…, m и выберем такую из них, при которой второй игрок, действуя максимально разумно, заплатит нам наибольшую сумму. Величина = max min aij называетi =1,2,…, m j =1,2,…, n ся нижней ценой игры, а соответствующая ей стратегия первого игрока — максиминной. Аналогично (но уже с точки зрения второго игрока) определяется верхняя цена игры = max min aij и соответствующая ей минимаксная стратегия второго игi =1,2,…, m j =1,2,…,n рока. Подчеркнем, что по своему определению нижняя цена игры представляет собой минимальный гарантированный выигрыш первого игрока (т. е. применяя свою максиминную стратегию, первый игрок обеспечивает себе выигрыш, не меньший ), а верхняя цена — величину, противоположную максимальному гарантированному проигрышу второго игрока (т. е. применяя свою минимаксную стратегию, второй игрок гарантирует, что он не проиграет больше, чем, или, по-другому, выиграет не меньше, чем ( - )).

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

Смешанной стратегией первого игрока называется вектор P = ( p1, p2,…, pm ), где 0 ( i = 1, 2,…, m ), а pi = 1. При этом pi — вероятность, с которой первый все pi игрок выбирает свою i-ю стратегию. Аналогично определяются смешанные стратегии Q = (q1, q2,…, qn ) второго игрока. Чистая стратегия также подпадает под определение смешанной — если все вероятности равны нулю, кроме одной, равной единице.

Если игроки играют своими смешанными стратегиями P = ( p1, p2,…, pm ) и Q = (q1, q2,…, qn ) соответственно, то математическое ожидание выигрыша первого игрока равно (и равно математическому ожиданию проигрыша второго игрока).

Стратегии P* = ( p1, p2,…, pm ) и Q* = (q1, q2,…, qm ) соответственно называются оптимальными смешанными стратегиями первого и второго игрока, если Если у обоих игроков есть оптимальные смешанные стратегии, то пара ( P* ; Q* ) называется решением игры, а число = M ( P *, Q* ) — ценой игры.

Приведем без доказательства следующую теорему.

ОСНОВНАЯ ТЕОРЕМА ТЕОРИИ ИГР. В матричной игре с нулевой суммой у игроков есть оптимальные стратегии.

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

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

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

РЕШЕНИЕ. Данная игра имеет седловую точку. Действительно, нижняя цена игры = max min aij = max{0,1; 0,3; 0,1} = 0,3 (соответствует второй стратегии первого игi =1,2,3 j =1,2, рока), а верхняя цена игры = min max aij = min{0,5; 0,3; 0, 4} = 0,3 (соответствует второй стратегии второго), поэтому игроки, действуя каждый по своей второй стратегии, могут гарантировать себе: первый — выигрыш не менее = = = 0,3 = 30% рынка, а второй — что первый игрок выиграет не более = 30% рынка. Таким образом, оптимальная чистая стратегия первого игрока — вторая, второго игрока — вторая, а цена игры равна = 0,3.

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

РЕШЕНИЕ. Платежная матрица, очевидно, имеет вид =.

Прежде всего проверим, нет ли в игре седловой точки. Действительно, нижняя цена = min max aij = min{3, 3} = 3, т. е., и седловой точки в игре нет. Пусть первый игрок выбирает свою первую стратегию с вероятностью p, а вторую стратегию — соответственно с вероятностью (1 – p), т. е. первый игрок играет со смешанной стратегией P(p; 1 – p). Обозначим v j ( p ) ожидаемый выигрыш первого игрока, если второй игрок при этом выберет свою j-ю стратегию. В нашем случае на рис. 10.1.1.

Второй игрок так выбирает свои стратегии, чтобы обеспечить первому минимальный выигрыш: v( p ) = min{v1 ( p ), v2 ( p )} (эта функция отмечена на рис. 10.1.1 жирной линией). Иными словами, второй игрок в любом случае заставит первого выиграть как можно меньше, т. е. в рассматриваемой игре при p [0; p* ) второй игрок будет выбирать свою вторую стратегию и выигрывать v2 ( p ), при p ( p* ;1] — выбирать первую стратегию и выигрывать v1 ( p ). Наилучший для первого игрока выбор при этом соответствует = max v( p ), т. е. p = p*. Число называется при этом ценой игры. В нашем случае p = p*, т. е. оптимальной смешанной стратегией первого игрока является стратегия P*,, при этом цена игры равна =. Аналогичным образом можно найти оптимальные смешанные стратегии второго игрока. Предоставляем это читателю.

при различном выборе вторым игроком своих стратегий 189. Дисперсия случайной величины X не превышает 10. Требуется: а) рассчитанного по 16 000 результатов наблюдений случайной величины (независимых, проведенных в одинаковых с вероятностной точки зрения условиях) от математического ожидания MX не превысит 0,25; б) определить, сколько следует провести наблюдений, чтобы с вероятностью, не меньшей 0,99, можно было утверждать, что ошибка репрезентативности при замене математического ожидания MX выборочным средним x не превысит 0,2.

РЕШЕНИЕ. а) По формуле (4.1.2), в которой n = 16 000, B =10, = 0, 25, получаем:

б) По формуле (4.1.3), в которой B = 10, = 0,99, = 0, 2, получим:

(1 - ) 2 (1 - 0,99)0, случайной величины и воспользовавшись (4.1.9) и тем, что u / 2 =u0,99 / 2 =u0,495 = 2, (так как 0 (2,55) = 0, 495 — см. табл. П.1 в пособии [3]), получим:

190. Известно, что в среднем из каждой тысячи кредитов, выданных на развитие малого предпринимательства 30 не возвращаются. Определить, сколько нужно отобрать предприятий, чтобы с вероятностью, не меньшей 0,9, можно было бы ожидать, что доля предприятий в выборке, не возвращающих кредиты, будет отличаться от доли аналогичных предприятий в генеральной совокупности меньше, чем на 0,01.

(1 - ) (1 - 0,9)0, При этом, поскольку np > 792, 25 0, 03 = 23 > 10, есть основания пользоваться теоремами Муавра — Лапласа. Таким образом, необходимо отобрать 793 предприятия.

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

РЕШЕНИЕ.

Y = 10, 25; X 1,58; Y = 3, 20 и подставляем рассчитанные значения в формулу 192. Найти нижнюю и верхнюю цену в игре с платёжной матрицей Определить, есть ли в этой игре седловая точка, и если есть, решить игру в чистых стратегиях.

193. Два игрока независимо друг от друга загадывают числа 1 до 5. Если числа окажутся одинаковой четности, то второй игрок выплачивает первому их сумму, если числа окажутся разной четности, то первый игрок выплачивает второму их сумму. Найти решение игры.

194. Найти решение матричной игры с платёжной матрицей § 10.2. Принятие решений в условиях неопределенности Предположим, что л и ц о , п р и н и м а ю щ е е р е ш е н и е, может выбрать одну из возможных альтернатив, обозначенных номерами i = 1, 2, …, m. Ситуация является полностью неопределенной, т. е. известен лишь набор возможных вариантов состояний в н е ш н е й (по отношению к лицу, принимающему решение) среды, обозначенных номерами j = 1, 2, …, n. Если будет принято i-e решение, а состояние внешней среды соответствует j-й ситуации, то лицо, принимающее решение, получит доход qij.

Матрица Q = (qij) Rmn называется матрицей последствий (от реализации возможных решений).

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

Допустим, мы хотим оценить риск, который несет i-e решение. Нам неизвестна реальная ситуация. Но если бы мы знали, что осуществляется j-е состояние внешней среды, то выбрали бы наилучшее решение, т. е. приносящее наибольший доход Значит, принимая i-e решение, мы рискуем получить не qj, а только qij, т. е. если мы примем i-е решение, а во внешней среде реализуется j-е состояние, то мы будем с о ж а л е т ь о недополученном доходе в размере (по сравнению с тем, как если бы мы знали точно, что реализуется j-е состояние внешней среды, и выбрали бы решение, приносящее наибольший доход q j = max qij ). Матрица R = (rij) Rmn, где сожаления rij рассчитаны по формуле (10.2.1), называется матрицей сожалений (или матрицей рисков).

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

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

ПРАВИЛО ВАЛЬДА (ПРАВИЛО КРАЙНЕГО ПЕССИМИЗМА).

Рассматривая i-e решение, будем полагать, что на самом деле складывается ситуация, наихудшая с нашей точки зрения (т. е. приносящая наименьший доход ai = min qij ) и выберем решение i0 с наибольшим ai. Итак, правило Вальда рекомендует принять такое решение i0, что

ПРАВИЛО СЭВИДЖА (ПРАВИЛО МИНИМАЛЬНЫХ

С О Ж А Л Е Н И Й ). При применении этого правила анализируется матрица рисков R.

Рассматривая i-e решение, будем полагать, что на самом деле складывается ситуация максимального риска bi = max rij, и выберем решение i0 с наименьшим bi. Итак, правиj =1,2,…, n ло Сэвиджа рекомендует принять такое решение i0, что П Р А В И Л О Г У Р В И Ц А взвешивает пессимистический и оптимистический подходы к анализу неопределенной ситуации. По правилу Гурвица, принимается решение i0, на котором достигается максимум выражения где [0; 1]. Значение выбирается из субъективных соображений. Если приближается к единице, то правило Гурвица приближается к правилу Вальда, при приближении к нулю правило Гурвица приближается к правилу р о з о в о г о о п т и м и з м а.

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

П Р А В И Л О М А К С И М И З А Ц И И О Ж И Д А Е М О Г О Д О Х О Д А. Доход,

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

П Р А В И Л О М И Н И М И З А Ц И И О Ж И Д А Е М Ы Х С О Ж А Л Е Н И Й. Сожаления при реализации i-го решения представляются случайной величиной Ri с рядом распределения Средние ожидаемые сожаления оценивается математическим ожиданием MRi соответствующей случайной величины Ri. Правило минимизации ожидаемых сожалений рекомендует принять решение, влекущее минимальные средние ожидаемые сожаления.

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

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

Предположим, что банк рассматривает возможность инвестиций в m проектов: i =1, 2, …, m.

П р и а н а л и з е э ф ф е к т и в н о с т и инвестиционного проекта все издержки ct и денежные поступления bt приводятся к одному и тому же моменту времени (как правило, начальному) и суммируются, в результате получается характеристика инвестиционного проекта, называемая его чистым дисконтированным доходом NPV (Net Present Value):

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

Теперь можно составить матрицу последствий Q (каждый элемент которой qij будет представлять собой эффективность NPV i-го проекта при j-м состоянии внешних условий) и выбрать проекты, используя описанные критерии.

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

Можно еще успеть сойти с поезда и исправить ошибку, но тогда пропадет путевка (10 000 руб.). Если же уехать, утюг, если он действительно включен, может стать причиной пожара, и тогда придется ремонтировать квартиру (150 000 руб.). Петя не уверен, включен утюг или выключен. Составить матрицу последствий и матрицу сожалений.

РЕШЕНИЕ. У Пети есть две стратегии: поехать отдыхать или вернуться домой. У внешней среды также есть два состояния: утюг выключен либо утюг включен.

Матрица последствий имеет вид Составим матрицу сожалений. Максимум по первому столбцу равен q1 = max qi1 =0, по второму — q2 = max qi 2 = -10 000, поэтому матрица сожалений 196. Определить решения, которые в условиях задачи 195 рекомендуется принять согласно правилам Вальда, Сэвиджа и Гурвица.

РЕШЕНИЕ. Минимальные элементы строк матрицы последствий a1 = –150 000, a2 = = –10 000. Теперь из двух чисел (–150 000), (–10 000) находим наибольшее. Это (–10 000).

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

Максимальные элементы строк матрицы сожалений b1 = 140 000, b2 = 10 000. Из чисел 140 000, 10 000 находим наименьшее. Это 10 000. Значит, правило Сэвиджа также, как и правило Вальда, рекомендует принять второе решение, т. е. вернуться домой.

Читатель может убедиться, что правило Гурвица при = 0,5 также, как правила Вальда и Сэвиджа, рекомендует принять второе решение, т. е. вернуться домой.

197. Владелец груза должен выбрать одну из двух альтернатив: страховать груз или не страховать. Риск заключается в том, что с вероятностью 0,1 возможна катастрофа, в результате которой груз будет утрачен. Если груз застрахован, то в случае его утраты владелец теряет стоимость груза (95 000 руб.), но получает компенсацию 100 000 руб., если же катастрофы не произошло, он теряет 5000 руб, потраченные на страховой полис. Если груз не застрахован, в случае катастрофы теряется его стоимость, при благополучном же исходе владелец не несет никаких расходов. Какое решение принять?

РЕШЕНИЕ. У владельца груза есть две стратегии: страховать груз или не страховать его. У внешней среды также есть два состояния: катастрофа произойдет либо не произойдет.

Матрица последствий имеет вид Вероятности состояний внешней среды известны (p1 = 0,1, p2 = 0,9), поэтому ряды распределения дохода при выборе первой и второй стратегии таковы:

При этом MQ1 = 0·0,1 + (–5000)·0,9 = –4500, аналогично MQ2 = –9500. Таким образом, правило максимизации ожидаемого дохода рекомендует принять первое решение, т. е. застраховать груз.

Составим матрицу сожалений. Максимум по первому столбцу равен q1 = max qi1 = 0, по второму — q2 = max qi 2 = 0, поэтому матрица сожалений Вычислим средние ожидаемые сожаления при указанных выше вероятностях. Получаем MR1 = 4500, MR2 = 9500. Минимальные средние ожидаемые сожаления равны 4500, они соответствуют первому решению — застраховать груз.

Задачи для самостоятельного решения 198. Вы едете на автомобиле. На развилке дорог указатель «Впереди дорога разрыта. Объезд». По карте Вы определяете, что дорога в объезд займет у вас в 4 раза больше времени, чем по прямой. Оказавшиеся рядом трое дорожных рабочих дают противоречивую информацию: один из них утверждает, что дорогу впереди уже отремонтировали, а двое других говорят, что дорога впереди действительно разрыта, и путь по ней займет в пять раз дольше времени по сравнению с тем, как если бы она была в рабочем состоянии. По какой дороге ехать?

199. Банк рассматривает четыре инвестиционных проекта. В зависимости от будущей экономической ситуации (которая, по оценкам экспертам, может развиваться по трем различным вариантам) составлена матрица каждый элемент aij которой представляют собой эффективность, которую принесет i-й проект, в случае, если экономика будет развиваться по j-му сценарию. Вероятности сценариев неизвестны, но имеются их экспертные оцекнки: 0,3, 0,6, 0,1. Проанализировать данную ситуацию как ситуацию принятия решений в условиях неопределенности.

Глава 11. Введение в финансовую математику § 11.1. Финансовый рынок. Основы финансовых расчетов Издавна в качестве средства оплаты товаров и услуг выступают деньги. Еще в середине третьего тысячелетия до н. э. они появились у шумеров в виде кусочков и слитков серебра. В VII в. до н. э. в Лидии были изобретены монеты, т. е. металлические предметы, на которых были отчеканены масса и качество металла.

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

Это отношение эквивалентности заложило основы рынка еще в Нововавилонском царстве более 2500 лет тому назад. Вместе с деньгами у шумеров появилась и арифметика.

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

Основным институтом, обслуживающим рынки финансовых инструментов, являются б а н к и. Одной из основных банковских операций является обслуживание банковских счетов: в определенные моменты времени банк обязуется добавлять к денежной сумме, лежащей на банковском счете, некоторый п р о ц е н т. Проценты могут быть простыми или сложными и начисляться m раз в год либо непрерывно. Если в начальный момент времени на банковском счете лежит сумма B0, проценты начисляются m раз в год, а годовая п р о ц е н т н а я с т а в к а по банковскому счету составляет im, то в случае простых процентов через t лет8 на счете будет лежать сумма О непрерывном начислении говорят только в случае сложных процентов, при этом можно считать, что количество m выплат в году стремится к бесконечности. При непрерывном начислении процентов сумма, лежащая на счете в момент времени t, составит где Если сумма Bt, лежащая на банковском счете в момент времени t, отрицательна (при этом говорят, что на счете образовалась к о р о т к а я позиция), подразумевается, что банк кредитует вкладчика на сумму |Bt|, взимая за это тот же самый процент i, который начисляется на счета с положительной суммой (с д л и н н о й позицией).

Очевидно, модель (11.1.1) описывает и случай короткой, и случай длинной позиции на банковском счете.

Число t может быть как целым, так и дробным. Обозначим квадратными скобками [x] целую часть числа x — наименьшее целое число, не превосходящее x, а фигурными скобками — дробную часть x: {x} = x – [x].

Пусть i — годовая процентная ставка; n — количество периодов, на которые разбит год.

Рассчитаем in — процентную ставку, выплачиваемую за n-ю часть года. Поскольку Если речь идет о периоде длиной, отличающейся от года (t лет), то последняя формула переходит в С целью привлечения денежных средств различные организации могут выпускать свои ц е н н ы е бумаги — облигации и акции.

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

Облигации представляют собой д о л г о в ы е обязательства — владелец (или держатель) облигации номинальной стоимостью P(T; T), выпущенной на срок T лет, покупая ее по некоторой начальной цене P(0; T), получает от эмитента (организации, выпустившей эту облигацию) подтверждение задолженности в размере номинальной стоимости, которую эмитент обязуется ликвидировать в момент погашения T. При этом номинальная стоимость превышает начальную и, кроме того, обычно эмитент обязуется периодически (как правило, раз в полгода или раз в квартал) выплачивать держателю облигации так называемый купонный доход — определенный процент от номинальной стоимости.

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

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

Предположим, что инвестор имеет возможность • размещать средства на банковском счете и брать с него в долг;

• покупать и продавать ценные бумаги.

Тогда для этого инвестора на рынке существует один б е з р и с к о в ы й а к т и в (банковский счет) B и n р с к о в ы х а к т и в о в (ценных бумаг) S(1), S(2), …, S(n).

Будем считать, что проценты на банковский счет начисляются по схеме сложных процентов с постоянной ставкой i(t)= i = const, так что в конце каждого периода сумма на счете увеличивается в (1 + i) раз:

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

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

Предположим, что на рынке обращаются n ценных бумаг, и стоимость i-й ценной бумаги в конце периода времени t составляет S (t i ), i = 1, 2, …, n.

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

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

Функционирующий по таким правилам рынок будем называть (B, S)-рынком.

Рассмотрим поведение стоимости акции St на (B, S) рынке в течение некоторого периода времени от [0; T].

Предположим, что в течение данного периода времени стоимость акций может увеличиться в u раз или увеличиться в d раз (уменьшиться в 1/d раз), причем d < u (рис. 11.1.1).

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