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

Федеральное агентство железнодорожного транспорта Уральский государственный университет путей сообщения Кафедра «Естественнонаучные дисциплины» И.Н. Пирогова Е.Г. Филиппова КРАТКИЙ КУРС ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ Методы принятия управленческих решений Методическое пособие Екатеринбург УрГУПС 2016 1 Федеральное агентство железнодорожного транспорта Уральский государственный университет путей сообщения Кафедра «Естественнонаучные дисциплины» И.Н. Пирогова Е.Г. Филиппова КРАТКИЙ КУРС ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ Методы принятия управленческих решений Методическое пособие для обучающихся по ОП ВО направления 38.03.02 «Менеджмент» всех форм обучения Екатеринбург УрГУПС 2016 2 УДК 51 П-33 Пирогова И.Н. Краткий курс лекций по дисциплине «Методы принятия управленческих решений» для студентов, обучающихся по ОП ВО направления 38.03.02 «Менеджмент» всех форм обучения./ И.Н. Пирогова, Е.Г. Филиппова. – Екатеринбург : УрГУПС, 2016. – 90с. Предназначен для методического обеспечения курса лекций для студентов, обучающихся по ОП ВО направления 38.03.02 «Менеджмент» всех форм обучения. Издано по решению редакционно-издательского совета университета Авторы: И.Н. Пирогова, доцент кафедры «Естественнонаучные дисциплины», УрГУПС, Е.Г. Филиппова, старший преподаватель кафедры «Естественнонаучные дисциплины», УрГУПС Рецензент: Г. А. Тимофеева, зав. кафедрой «Естественнонаучные дисциплины», д-р физ.-мат. наук, профессор, УрГУПС © Уральский государственный университет путей сообщения (УрГУПС), 2016 3 ОГЛАВЛЕНИЕ Введение 1. Элементы математической статистики 1.1 Метод моментов 1.2 Критерий Пирсона 2. Линейное программирование 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 Основные понятия линейного программирования Геометрическая иллюстрация решения задач ЛП Двойственность в задачах линейного программирования Симплекс метод в задачах линейного программирования Транспортная задача линейного программирования Открытая транспортная задача Проблема вырожденного плана задачи Транспортная задача на сети Задача об оптимальном назначении 3. Нелинейное программирование 3.1 Условный экстремум 3.2 Метод множителей Лагранжа 4. Динамическое программирование 4.1 Выбор оптимальной стратегии обновления оборудования 4.2 Задача оптимального распределения ресурсов 4.3 Задача о минимизации затрат на строительство и эксплуатацию предприятий 4.4 Задача об оптимальной загрузке транспортного средства неделимыми предметами (задача о рюкзаке) 4.5 Выбор оптимального маршрута 5. Сетевые модели 5.1 Временные параметры событий 5.2 Оптимизация сетевых моделей по критерию «минимум исполнителей» 5.3 Оптимизация сетевых моделей по критерию «время-затраты» 6. Теория игр Заключение Список использованных источников 4 Введение В издании использованы материалы, разработанные преподавателями кафедры «Естественнонаучные дисциплины». Учебный курс «Методы принятия управленческих решений» предназначен для студентов – бакалавров всех форм обучения. Содержание данного курса ориентировано на применение математических методов к решению прикладных задач. В основу курса положены классические и современные математические теории и практика, авторские разработки коллектива кафедры «Естественнонаучные дисциплины». Цель дисциплины: приобретение знаний, умений и навыков, обеспечивающих решение профессионально-ориентированных задач оптимизации. Задачами изучения дисциплины являются: освоение методов обработки опытных данных, а также решения задач линейного программирования. Задачами изучения дисциплины являются: – развить логическое и алгоритмическое мышления студентов; – воспитать культуру применения математических и информационных технологий для решения прикладных задач аналитическими и вычислительными методами; – освоить математические методы исследования реальных процессов и явлений. Изучение дисциплины направлено на формирование общекультурных и профессиональных компетенций. ТРЕБОВАНИЯ К РЕЗУЛЬТАТАМ ОСВОЕНИЯ ДИСЦИПЛИНЫ (в соответствие с ФГОС подготовки бакалавра и ООП) В результате изучения дисциплины студент должен: знать: основы линейного программирования и математической статистики. уметь: составлять математические модели задач с экономическим содержанием, проводить расчеты количественных показателей, анализировать и интерпретировать полученные результаты; 3. владеть: методами грамотного решения экономических задач с использованием математического аппарата, анализа полученных результатов, прогнозирования на основе полученных результатов. 5 1. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ СТАТИСТИКИ Развитие науки и техники требует все более глубокого проникновения в сущность явлений природы, которые, в свою очередь, предстают перед нами в виде огромного числа фактов и наблюдений. Методы математической статистики дают возможность представить множество результатов наблюдений в компактном виде. Они позволяют выделить из этого множества существенную информацию. Математическая статистика – это наука о методах обработки большого числа экспериментальных данных с целью изучения объективно существующих закономерностей и взаимосвязей. Совокупность всех подлежащих изучению объектов называется генеральной совокупностью. Пусть в результате эксперимента реализовались n значений измеряемой величины x1 ,…, xn, которые получены случайным образом из генеральной совокупности. Этот набор называют простой статистической совокупностью или выборкой объема n. Наша задача состоит в установлении закона распределения и его параметров, соответствующих данной выборке. Частотой называют отношение числа точек наблюдения, попавших в данный интервал, к общему числу точек: i  mi . Относительной чаn стотой или наблюдаемой плотностью называют отношение частоты к длине данного интервала: bi  i . h Гистограммой относительных частот называют ступенчатую фигуру, состоящую из прямоугольников, основания которых – интервалы разбиения длины h, а высоты равны относительной плотности распределения bi. Площадь каждого прямоугольника равна частоте попадания в данный разряд, а сумма площадей всех прямоугольников равна единице. Вид гистограммы уже приближенно указывает на подходящий вид теоретического распределения (сравнение ведется с графиком плотности распределения).  Таблица, в первой строке которой стоит xi – «представитель» интервала, а во второй – mi , называется дискретным рядом распределения. 6 Приведем краткий обзор характеристик, которые применяются для анализа статистических рядов и являются аналогами соответствующих числовых характеристик случайной величины. Среднее выборочное и выборочная дисперсия являются частным случаем более общего понятия – момента статистического ряда. Определение. Начальным выборочным моментом порядка t называется среднее арифметическое t - х степеней всех значений выборки: 1 k t t   xi  mi . n i1 Из определения следует, что начальный выборочный момент первого k порядка: α1  k α2   mi xi i 1 n  mi xi i 1 n , начальный выборочный момент второго порядка: 2 . Определение. Центральным выборочным моментом порядка l называется среднее арифметическое l - х степеней отклонений наблюдаемых значений выборки от выборочного среднего x в :   l 1 m    xi  xв  ni n i 1 * l Из определения следует, что первый центральный момент для любых случайных величин равен нулю, μ1*  0, а центральный выборочный момент второго порядка:   2 1 m    xi  xв  ni  Dв  в2 . n i 1 * 2 Определение. Выборочным коэффициентом асимметрии («скошен* ности») называется число As , определяемое формулой: A*s   3* . Цен3 в тральный выборочный момент третьего порядка 3 вычисляется по фор* муле: 7 μ *3  α 3  3  α1  α 2  2  α13 . Если коэффициент асимметрии отрицательный, то это говорит о большом влиянии на величину 3 отрицательных отклонений. В этом слу* чае кривая распределения более полога слева от М(Х). Если коэффициент As положительный, а значит, преобладает влияние положительных отклонений, то кривая распределения более полога справа. Четвертый центральный момент служит для характеристики островершинности (крутости) распределения. Определение. Выборочным коэффициентом эксцесса или коэффи* циентом крутости называется число E , определяемое формулой:  *4 E  4 3. в * Моменты порядков более четвертого, как правило, не используются. Распределения более островершинные, чем нормальное, имеют эксцесс Е > 0, а более плосковершинные – имеют эксцесс Е < 0 . Статистики выборочного распределения находятся по формулам: – выборочная средняя – x  α 1 – оценка математического ожидания по выборке; – выборочная дисперсия – S 2  α 2  α1 – оценка дисперсии по вы2 борке; – выборочное среднеквадратичное отклонение – S  S 2 – оценка среднеквадратического отклонения по выборке. Коэффициент вариации − мера относительного разброса случайной величины; показывает, какую долю среднего значения этой величины составляет её средний разброс. Вопросы 1.Определение генеральной совокупности. 2. Понятие выборки. 3. Понятие частоты и относительной частоты. 4.Определение гистограммы. 5.Понятие интервального ряда. 6. Чем отличается дискретный ряд от интервального. 7. Назовите основные числовые характеристики выборки. 8 8. Аналогом чего являются характеристики выборки. 1.1 Метод моментов Мы подбираем распределение так, чтобы вероятности попадания в интервалы разбиения были близки к относительным частотам, найденным по выборке. Выбор параметров распределения может осуществляться с помощью метода моментов. Используя его, мы выбираем те значения параметра, для которых теоретические значения первых моментов распределения, то есть математического ожидания и дисперсии, совпадут с выборочными. Если плотность распределения f  ( x, a) определяется одним неизвестным параметром a , то ищется его точечная оценка. Для этого достаточно иметь одно уравнение относительно этого параметра. Так, например, показательное распределение определяется одним параметром  . Приравняем начальный теоретический момент первого порядка начальному эмпи1 1   . рическому моменту первого порядка: M ( X )  x   x Искомая точечная оценка параметра  равна величине, обратной выборочной средней. Пусть плотность распределения f (x, a, b) определяется неизвестными параметрами а и b . Плотность нормального распределения определяется двумя параметрами m и  . Для отыскания их необходимы два уравнения относительно этих параметров. Приравниваем начальные теоретические моменты первого и второго порядков начальным эмпирическим моментам первого и второго порядка. Тогда точечная оценка неизвестных параметров m и  нормального распределения будет: σS. m  x, Точечная оценка неизвестных параметров a и b равномерного распределения: a  xS 3, b xS 3. Вопросы 1. В чем заключается метод моментов. 2. Назовите параметры показательного распределения и их аналог в статистике. 3. Параметры равномерного распределения и их аналог в статистике. 4. Параметры нормального распределения. 9 1.2. Критерий Пирсона Выдвинув гипотезу о теоретическом законе распределения и определив его параметры, необходимо провести проверку согласованности выбранного теоретического распределения с опытными данными. При этом мы проверяем нулевую гипотезу: генеральная совокупность распределена по выбранному закону. Проверка этой гипотезы проводится при помощи критерия согласия. Мы рассмотрим критерий согласия Пирсона (критерий χ 2 ). Для этого сравним эмпирические и теоретические частоты. Критерий устанавливает на принятом уровне значимости  : противоречат ли опытные данные нулевой гипотезе? В соответствии с этим критерием следует найти меру расхождения теоретического и статистического распределения χ набл 2 (mi  npi ) 2  . npi i 1 k Здесь k – число интервалов разбиения, n – объем выборки, mi – количество наблюдений в интервале, pi – значение вероятности попадания слуpi  F ( xi 1 )  F ( xi ) . Приближенно чайной величины в интервал  pi  f ( xi )  hi , где hi – длина i интервала,  f ( xi ) – значение плотности распределения в середине i-того интервала при найденных значениях неизвестных параметров. Величина χ 2 набл не зависит от типа распределения изучаемой генеральной совокупности и имеет распределение Пирсона с параметром r, где r – число степеней свободы. Его находят по равенству r = k – s – 1, здесь k – число интервалов разбиения, s – число параметров предполагаемого распределения. Например, для нормального и равномерного распределений s = 2, следовательно, r = k – 3. А для показательного распределения s = 1 и r = k – 2. Пусть уровень значимости равен  . Если нулевая гипотеза верна, то с вероятностью 1   выполняется неравенство χ 2 набл  χ 2 крит (α, r ) , где χ 2 крит (α, r ) находят по таблице критических точек распределения χ 2 (эти значения табулированы). Правило проверки нулевой гипотезы Для того чтобы при заданном уровне значимости  проверить нулевую гипотезу: генеральная совокупность распределена по данному закону, надо: 10 1) вычислить теоретические частоты; 2 2) вычислить наблюдаемое значение критерия  набл по приведенной выше формуле; 2 3) по таблице критических точек распределения  по заданному уров- ню значимости  и числу степеней свободы r найти критическую точку 2 2 2  кр (  , r ) . Если  набл   кр – нет оснований отвергнуть нулевую гипотезу. 2 2 Если  набл   кр – нулевую гипотезу отвергаем, так как данные противоречат этой гипотезе. Вопросы 1. 2. 3. 4. Понятие критерия согласия. В чем заключается критерий Пирсона. Определение нулевой гипотезы. Правило проверки нулевой гипотезы по критерию Пирсона. 2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 2.1. Основные понятия линейного программирования Линейное программирование (ЛП)  это раздел математики о методах исследования и поиска наибольших и наименьших значений некоторой линейной функции, причем ограничения задачи тоже линейны. Математические модели задач линейного программирования (ЗЛП) различаются между собой по виду ограничений. Определение 1. Математическая модель ЗЛП называется стандартной, если ограничения в ней представлены в виде линейных неравенств, а целевая функция минимизируется или максимизируется. Например, пусть в модели n неизвестных: х1, х2, …xn. Надо найти среди решений системы неравенств такие, которые дают целевой функции наибольшее (наименьшее) значение. Такая модель имеет вид:  a11x1  a12 x2  ...  а1n xn  b1 ,  a x  a x  ...  а x  b ,  21 1 22 2 2n n 2     a x  a x  ...  а x  b ; mn n m  m1 1 m 2 2 (1) x j  0, f ( X )  c1x1  c2 x2  ..cn xn  c0  max(min) , 11 j  1, 2,... n; (2) где X   x1; x2 ;....xn   искомое решение системы. Система линейных неравенств, определяющая допустимое множество решений задачи (1), называется системой ограничений задачи линейного программирования, а линейная функция f(Х) (2) называется целевой функцией или критерием оптимальности. Определение 2. Математическая модель ЗЛП называется основной, если ограничения в ней представлены в виде уравнений при условии неотрицательности переменных. Такая модель имеет вид:  a11x1  a12 x2  ...  а1n xn  b1 ,  a x  a x  ...  а x  b ,  21 1 22 2 2n n 2     a x  a x  ...  а x  b ; mn n m  m1 1 m 2 2 (3) x j  0, j  1, 2,... n; f ( Х )  c1 x1  c2 x2  ...  cn xn  c0  max(min) , (4) где X  ( x1, x2 ,... xn )  искомое решение системы. Система уравнений (3) обычно имеет конечное множество решений. Целевая функция f(Х) − линейная, поэтому ее частные производные постоянны, а это значит, что внутри области решений системы (3) экстремальных точек нет. Если целевая функция имеет оптимальное решение, то оно достигается в точках границ области. Таким образом, в линейном программировании исследователя интересуют вершины многоугольника решений системы (3). Сформулируем вопрос: какой вид должна иметь модель ЛП, чтобы координаты вершин многоугольника решений могли быть легко получены? Рассмотрим другие модели задач линейного программирования. Определение 3. Математическая модель называется канонической, если ее система ограничений представлена в виде системы m линейно независимых уравнений (ранг системы r = m), в системе выделен единичный базис, определены свободные переменные и целевая функция выражена через свободные переменные. При этом правые части уравнений неотрицательны. Запишем каноническую модель ЗЛП: 12 a1x1  a12 x2  ...  а1s xs  xs 1  b1 , a x  a x  ...  а x  x  b ,  21 1 22 2 2s s s2 2                                    am1x1  am 2 x2  ...  ams xs  xs  m  bm ;  (5) x j  0, j  1,2,... s  m; f ( X )  c0  c1x1  ...  cs xs  min (6) Определение 4. Переменные, входящие в одно из уравнений системы с коэффициентом один и отсутствующие в других уравнениях называются базисными неизвестными, а все другие – свободными. В рассматриваемой модели переменные x1, ..., хs – свободные, и если их принять равными нулю, то из системы (5) легко получить значения базисных переменных xs+1, xs+2, ..., xs+m . Определение 5. Решение системы называется базисным, если в нем свободные переменные равны нулю, и оно имеет вид: Х баз  (0,... 0; b1,... bm ); f  Х баз   с0 . Базисное решение является угловой точкой множества решений системы (5), или, можно сказать, определяет вершину многоугольника решений модели. Среди таких решений находится и то, при котором целевая функция принимает оптимальное значение. Определение 6. Базисное решение называется опорным, если оно допустимо, т. е. все правые части уравнений системы (или неравенств) положительны bi  0, i  1, m . Теорема 1. Базисное опорное решение в канонической модели является оптимальным, если все коэффициенты в целевой функции не положительны, т. е. сi  0, i  1, m . Рассмотрим правила перехода от одной модели к другой. Вопросы 1. 2. 3. 4. Дайте определение линейного программирования. Приведите виды математических моделей ЗЛП. Что такое базисные и свободные переменные. Какое решение называется оптимальным. 13 2.2. Геометрическая иллюстрация решения задач ЛП Пусть задана стандартная математическая модель задачи с двумя неизвестными:  a11x1  a12 x2  b1 ,  a x a x b ,  21 1 22 2 2 (1)     am1x1  am 2 x2  bm ; x j  0, j  1, 2;  f ( Х )  c0  c1 x1  c2 x2  max (min). (2) Нахождение решения этой модели на основе ее геометрической интерпретации включает следующие этапы. 1. В плоскости х1Ох2 строят прямые, уравнения которых получаются в результате замены в ограничениях (1) модели знаков неравенств на знаки точных равенств. 2. Находят полуплоскости, определенные каждым неравенством системы. 3. Находят выпуклый многоугольник решений всей системы (1). r 4. Строят нормальный вектор целевой функции n  c1; c2  , причем, начало вектора совмещают с началом координат и строят прямую c1 x1  c2 x2  0 .  5. Передвигают эту прямую в направлении вектора n , в результате либо находят вершину или отрезок, в которой целевая функция принимает наибольшее значение, либо устанавливают неограниченность сверху этой функции на множестве допустимых решений. 6. Если функция ограничена, то определяют X max   x1; x2  вычис- ляют значение функции в этой точке f max  f  X max . При геометрической интерпретации задач ЛП могут встретиться случаи, изображенные на рис. 1.  4. Рис. 1. Задача ЛП имеет единственное решение f max  f  X max  . Рис. 2. Задача ЛП имеет бесчисленное множество решений, т.к. целевая функция достигает максимума на отрезке [М; N ]. 14 x2 x2 f (Хmax ) M f (Хmax )  n  n N x1 x1 Рис. 1 Рис.2 Рис. 3. Задача ЛП не имеет решения, так как функция неограниченна сверху. Рис. 4. Задача ЛП не имеет решения, так как система (2.1) несовместна. x2 x2 f (Хmax ) → ∞  n  n x1 Рис. 3 x1 Рис. 4 Вопросы 1. Как строится область допустимых решений ЗЛП? 2. Как строится линия уровня и нормальный вектор? 3. Как определить оптимальное решение геометрически? 4. 2.3. Двойственность в задачах линейного программирования Двойственная задача – это вспомогательная задача ЛП, формулируемая с помощью определенного правила непосредственно из условия исходной задачи. Заметим, что для разных моделей исходной задачи правила построения двойственных моделей отличаются. Рассмотрим правило построения двойственной модели, если исходная задача задана в виде стандартной модели: 15  a11x1  a12 x2  ...  а1n xn  b1,  a x  a x  ...  а x  b , 2 2n n  21 1 22 2     a x  a x2  ...  а x  b ; x j  0, mn n m  m1 1 m 2 f ( X )  c1 x1  c2 x2  ...  cn xn  max . (1) j  1,2,... n; (2) Правило построения двойственной модели: 1. Проверить, отвечает ли исходная модель двум требованиям: а) все неравенства в системе (1) имеют одинаковый знак «  » (или «  »). б) если целевая функция задачи ЛП максимизируется, то знак в неравенствах должен быть «», а если целевая функция минимизируется, то знак должен быть «». В нашей модели это требование выполнено. 2. Каждому i-тому ограничению исходной задачи соответствует j-тое неизвестное в двойственной задаче: так, неравенству ai1x1  ai 2 x2  ...  ain xn  bi соответствует yi  0 (i  1, ... m). 3. Каждому неизвестному исходной модели соответствует ограничение двойственной модели. Матрица коэффициентов при неизвестных двойственной задачи является транспонированной матрицей исходной задачи. Неравенства ограничения имеют противоположный смысл неравенствам исходной задачи. Правые части ограничений равны коэффициентам функции цели прямой задачи. Таким образом, для i-ой переменной получим хi  0  a1i y1  ai 2 y 2  ...  am i y m  ci , i  1, 2, ... m . 4. Целевая функция двойственной модели имеет вид: q(Y )  b1 y1  b2 y2  ...  bm ym , и решается задача минимизации. Запишем модели по соответствию: 16  a11x1  a12 x2  ...  a1n xn  b1 , a x   21 1 a22 x2  ...  a2 n xn  b2 , (3)                               am1x1  am 2 x2  ...  amn xn  bm ,  x  0,  1     xn  0.  y1  0,  y  2  0,     ym  0,  a y  a y  ...  a y 21 2 m1 m  c1 ,  11 1     a1n y1  a2 n y2  ...  amn ym  cn . f ( Х )  c1x1  ...  cn xn  max. q(Y )  b1 у1  ...  bm ym  min . Такие модели задачи ЛП называются симметричными. Заметим, что в симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные накладывается условие неотрицательности. Если исходная задача ЛП − основная задача минимизации, то двойственная ей  стандартная задача максимизации, при этом переменные второй задачи yi (i  1, m) могут иметь любой знак. Заметим, что для полученной двойственной модели можно также построить по тем же правилам двойственную модель, которая будет представлять исходную модель ЗЛП. Существующие зависимости между решениями прямой и соответствующей ей двойственной задачи определяются следующими основными теоремами двойственности. Теорема 1. Если X – любое опорное решение исходной задачи, а Y – любое опорное решение соответствующей ей двойственной задачи, то f(X) ≤ q(Y). Теорема 2. Если одна из взаимно двойственных задач имеет оптимальное решение, то и другая тоже имеет оптимальное решение, причем оптимальные значения целевых функций равны между собой f(X max ) = q(Y min ). Теорема 3. Если одна из взаимно двойственных моделей не имеет оптимального решения (например, целевая функция не ограничена), то и другая не имеет допустимых решений, т. е. система ограничений в ней – несовместна в области планов. 17 Теорема 4. Пусть одна из взаимно двойственных задач имеет оптимальное решение. Тогда для неизвестных и ограничений выполняются следующие условия: 1) если координата хj оптимального плана исходной модели строго положительна, то соответствующее ограничение выполняется при подстановке в него координат оптимального решения, как уравнение; 2) если при подстановке Xо п т в какое-либо ограничение исходной задачи оно выполняется как строгое неравенство, то соответствующая ему переменная уi равна нулю. Теорема 5. Для того чтобы два допустимых решения Х* и Y* пары двойственных задач были оптимальными решениями, необходимо и достаточно, чтобы они удовлетворяли системе уравнений: m * ( a * x j ij yi  cj )  0, j  1, 2 ,... n . i 1 n *  b )  0, y*i (  ai j x j i i  1, 2 ,... m. j 1 Зная оптимальное решение одной из двойственных задач, можно, используя теоремы двойственности, найти оптимальное решение другой. Вопросы 1. Понятие двойственной модели ЗЛП. 2. Определение симметричной двойственной модели. 3. Как с помощью теорем двойственности найти решение двойственной модели? 2.4. Симплекс-метод в задачах линейного программирования Симплексный метод позволяет, отправляясь от известного опорного решения задачи, за конечное число шагов получить оптимальное решение. Каждый из шагов состоит в нахождении нового решения, которому соответствует меньшее значение целевой функции, чем значение этой функции при предыдущем решении. Процесс повторяется до тех пор, пока не будет получен оптимальный план. Основные положения симплекс-метода Пусть задана задача линейного программирования в виде канонической модели. 18  x1  x4  x5  2,   x2  2 x4  3 x5  7,  x  x  x  2, x j  0, j  1,5; 4 5  3 f ( X )  3  x4  x5  min. (1) Рассмотрим идею симплекс-метода на этом примере. Нетрудно убедиться, что система (1) совместна. Ее ранг r = 3, значит базисных переменных 3, а свободных переменных k  5  3  2 . Полагая свободные переменные x4, x5 равными нулю, получим первое опорное решение: X опор1   2,7,2,0,0  ;   f X опор1  3. В начальном плане свободными, а значит равными нулю, являются переменные х4, х5. Посмотрим, нельзя ли за счет увеличения х4 и х5 уменьшить значение целевой функции? Так как f  X   3  x4  x5 , то неизвестная х5 входит в выражение целевой функции со знаком плюс, поэтому ее увеличение приводит к увеличению функции. И это нам невыгодно. В то же время неизвестная х4 входит в выражениях со знаком минус, поэтому ее увеличение сопровождается уменьшением значения функции f  X  . Увеличение свободной неизвестной х4 вызывает соответствующие изменения базисных переменных х1, х2, х3. Данные изменения могут оказаться такими, что базисные переменные станут отрицательными. Мы должны позаботиться о том, чтобы этого не произошло. Оставим у переменной х5  значение равное нулю и рассмотрим уравнения, которые в этом случае получаются из системы (1): x1  x2  2 , x2  2 x4  7 , x3  x4  2 . Так как x1  2  x4 и x1  0 , то x4  2 ; аналогично x2  7  2 x4 и x 2  0 , следовательно, x4  3,5 . Так как x3  2  x4 , то здесь х4 может возрастать неограниченно. Далее выберем максимально возможное значение х4 равное 2; при этом x1  0, x2  3, x3  4, x4  2, x5  0. Мы перешли к новому опорному решению: X опор2   0,3,4,2,0  . Сравнивая X опор1 и X опор2 , видим, что х1 стала свободной, а х4  базисной. Модель надо преобразовать так, чтобы х4 присутствовало только в первом уравнении системы (1), функция f  X  должна быть выражена 19 через свободные переменные х1 и х5. x4  2  x1  x5 , и задача ЛП будет такой: Из первого уравнения  x2  2 x1  x5  3,   x3  x1  2 x5  4,  x  x  x  2, x j  0, j  1,5;  4 1 5 f ( X )  1  x1  2 x5  min . (2) Теперь видно, что f  X  не может быть уменьшена за счет увеличения х1 и х 5 . Значит, мы получили оптимальное решение. Запишем его. X min   0,3,4,2,0  ; f min  f  X min   1. Идею, рассмотренную в примере, используем для того, чтобы сформулировать правило преобразования симплекс-таблиц для решения задач симплексным методом. Правило преобразования симплекс-таблиц В предыдущем пункте мы увидели, что переход от одного опорного решения к другому начинается с исследования коэффициентов целевой функции и затем вычисляются коэффициенты новой модели задачи ЛП. Запишем требования к исходной модели задачи. 1. Задача линейного программирования должна быть представлена в виде канонической модели. 2. Целевая функция должна минимизироваться. 3. При занесении в таблицу у целевой функции меняются на противоположные знаки коэффициентов при свободных переменных. Запишем полученную каноническую задачу:  a11x1  a12 x2  x3  b1,   a21x1  a22 x2  x4  b2 ,  a x a x  x b ,  31 1 32 2 5 3 x j  0, j  1,5; f ( X )  c0   c1x1  c2 x2   min. В задаче X опор1   0, 0, b1, b2 , b3  ;   f1  f X опор1  c0 . Внесем ко- эффициенты этой модели в симплекс-таблицу (см. табл. 1). Таблица 1 Базис В х1 х2 х3 20 х4 х5 х3 b1 а11 al2 1 х4 b2 а21 a22 1 х5 b3 а31 a32 1 f(Х) с0 с1 с2 4. Рассмотрим последнюю строку таблицы 1 (коэффициенты целевой функции). Нас интересуют знаки с1 и с2. а) если хотя бы один из коэффициентов положителен, например c1  0 , то отмечаем стрелкой столбец таблицы, где находится с1. Этот столбец назовем ключевым. Если положительны оба коэффициента, то выберем наибольший из них; б) если с1 ≤ 0 и с2 ≤ 0, то таблицу не надо преобразовывать. Из таблицы находится оптимальное решение. 5. Выберем ту базисную переменную, которая будет свободной вместо х1, для этого выберем положительные из коэффициентов ai1, i  1,2,3. Пусть для определенности у нас a11   a21   a31   . Если все ai1 отрицательны или равны нулю, то задача решений не имеет, т.к. це- левая функция не ограничена. Пусть, кроме того, b1 b 2 .  a 11 a 21 b b  b 6. У нас a11   a21   , тогда выберем min  1 ; 2   1 . Это  a11 a 21  a11 означает, что х1 будет базисной переменной, а х3  свободной. Переходим к следующей таблице: Таблица 2 Базис В х1 х2 х3 х4 х5 х1 β1 1 al2* al3* х4 β2 a22* a23* 1 х5 β3 a32* a33* 1 f(Х) d0 d2 d3 21 7. Сначала заполняем первую строку табл. 2, эта строка соответствует базисной переменной х3 в табл. 1. Все коэффициенты первой строки табл. 1. делим на разрешающий элемент а11, результат запишем в первую строку табл. 2. Эта строка называется разрешающей. b *  a12 , a*  1 . β 1  1 , a12 13 a11 a11 a 11 С помощью разрешающей строки, делая простые вычисления, мы должны получить в остальных строках ключевого столбца нули. 8. Умножим разрешающую строку последовательно на (а 2 1 ), (а 3 1 ), (–с 1 ). Полученные строки чисел прибавим ко второй, потом к третьей, затем к последней строке табл. 1, а результаты вычислений поставим во вторую, третью и последнюю строку табл. 2, ba *   a21 ; *  a  a12 a 21 ; β 2  b2  1 21 ; a22 a где: 22 23 a 11 a 11 a11 b1 a 31 ; a11 *  a32  a32 a12 a31 a11 ; *  a33 bc d 0  c0  a1 1 ; 11 d 2  c2  c1 a12 ; a11 d3   β 3  b3  a31 ; a11 c1 . a11 9. Мы получили новую таблицу (см. табл. 2), для которой соответствующая каноническая задача имеет вид:  a12* x2  a13* x3  x1  β1,   a * x a * x  x β , 23 3 4 2  22 2  * *  a32 x2  a33 x3  x5  β3 , x j  0, j  1,5; f ( X )  d 0   d 2 x2  d3 x3   min. Полагая свободные переменные х2 и х3 равными нулю получаем новый опорный план: X опор2   β1, 0, 0,β 2 ,β3  ;   f 2  f X опор2  d0. 10. Если d1  0, d 2  0 , то решение оптимально. Если среди них есть положительные, то процесс преобразования таблиц надо продолжать. Вопросы 1. Понятие симплекс-метода. 22 2. Назовите основной алгоритм данного метода. 3. Как в этом методе можно проверить, что найдено оптимальное решение. 2.5. Транспортная задача линейного программирования Постановка задачи Пусть имеется m поставщиков некоторого однородного груза, сосредоточенного на станциях А1 , А2 , … Аm и имеется n потребителей этого продукта, расположенные на станциях В1 , В2 , … Вn. Известны также запасы этого груза (а1 , а2 ,…, аm ), которые должны быть вывезены в фиксированный период времени. Потребности получателей груза за этот же период времени составляют (b1 , b2 , …bn). Пусть запасы равны потребностям, т. е. m  аi  i 1 n  bj (1) j 1 При выполнении условия (1) транспортная задача называется закрытой. Кроме того, известны затраты Сi j на перевозку единицы груза с любой станции Аi на каждую станцию Вj . Требуется составить такой план перевозок, чтобы весь груз был вывезен, все потребности были удовлетворены, а суммарные затраты на перевозки были минимальны. Математическая модель Обозначим величину перевозки со станции Аi на станцию Bj как xi j . Тогда условия полного вывоза груза со всех станций Аi можно записать в виде системы уравнений:       х11  х12  х13  ...  х1n  a1 , x21  x22  x23  ...  x2 n  a2 ,  xm1  xm 2  xm3  ...  xmn  am . (2) С другой стороны, станции Вj должны получить необходимое количество груза, что тоже записывается в виде системы уравнений: 23       х11  х21  х31  ...  хm1  b1 , x12  x22  x32  ...  xm 2  b2 ,   x1n  x2 n  x3n  ...  xmn  bn . (3) При этом выполняется условие неотрицательности для переменных xi j : xi j  0, ( i 1,2 ,... m; j 1,2 , ... n). Функция цели задачи по критерию минимума суммарных затрат – m n f ( Х )    Cij xi j  min. i 1 j 1 (4) Таким образом, транспортная задача представляет собой основную задачу линейного программирования. Часто при решении реальных задач число переменных (следовательно, и число свободных переменных на любом плане) получается значительным и решение транспортной задачи геометрическим способом бывает малоэффективным или невозможным, поэтому были разработаны специальные методы решения таких задач. Рассмотрим некоторые из них. Вся исходная информация для транспортной задачи организуется в виде матрицы или таблицы , в которую заносится опорный план задачи. В этой же таблице проводится оптимизация плана и записывается решение задачи. Методы определения начального опорного плана Метод северо-западного угла Определение начального опорного плана начинается с того, что в верхнюю левую (северо-западную) клетку таблицы заносится максимально возможный объем перевозки груза со станции А1 для удовлетворения потребности первого потребителя В1. Если потребности потребителя полностью удовлетворены, вычеркиваются все клетки первого столбца (В1). Если со станции А1 вывезены все запасы груза, то вычеркивается все клетки первой строки (А1). Далее, если потребности потребителя В1 удовлетворены, следующей становится клетка в столбце справа – А1-В2. Если же со станции А1 вывезен весь груз, то в качестве северо-западной клетки при- 24 нимают клетку А2-В1 в ближайшей нижней строке и т. д. Указанный алгоритм применяется до заполнения всей таблицы. Метод наименьшей стоимости Рассмотрим другой метод, который учитывает в какой-то мере затраты на перевозки и реализуется следующим образом: в исходной матрице, находят клетку с наименьшей стоимостью, в которую заносят максимально допустимую перевозку. После чего вычеркивается либо строка, либо столбец, соответствующие выбранной клетке. Далее все повторяется для оставшейся части таблицы (находят клетку с наименьшей стоимостью и т. д.). В большинстве случаев этот метод дает план, который ближе к оптимальному, однако во всех случаях требуется сравнивать величины функции цели на получаемых планах и выбирать тот, для которого функция принимает наименьшее значение. Метод двойного предпочтения В данном методе выбирают клетки с наименьшей стоимостью в каждой строке и отмечают их каким-нибудь значком, например, ☺. Затем выбирают и отмечают клетки с наименьшей стоимостью в каждом столбце. В дважды отмеченные клетки ☺☺ заносят максимально допустимые перевозки. После чего максимальные допустимые перевозки заносят в клетки, отмеченные один раз значком ☺. Остаток таблицы можно заполнить методом северо-западного угла или методом наименьшей стоимости. Затем можно выбрать метод, дающий наименьшее значение целевой функции и проверить его на оптимальность. Решение транспортной задачи методом потенциалов Метод потенциалов позволяет оценить составленный опорный план и при необходимости, последовательно улучшая его, найти оптимальное решение. Теоремы метода Теорема 1: Если опорный план X = (xi j ) является оптимальным, то существует система из (m + n) чисел, называемых потенциалами, Ui , Vj , такая, что: а) U i +V j = C i j , для xi j > 0 (базисные переменные); б) U i +V j  C i j , для xi j = 0 (свободные переменные). 25 Таким образом, для оптимальности опорного плана необходимо выполнение следующих условий:  для каждой занятой клетки сумма потенциалов равна стоимости перевозки единицы груза, стоящей в этой клетке U i +V j = C i j , (5)  для каждой свободной клетки сумма потенциалов меньше или равна стоимости перевозки единицы груза, стоящей в этой клетке: U i +V j ≤ C i j . (6) Примечание: система (5) содержит (m + n) неизвестных и (m + n – 1) линейно независимых уравнений. Такая система имеет бесчисленное множество решений, которые можно получить, придавая одной из неизвестных конкретное значение. Это значение выбирается произвольно, например можно придать U2 значение равное нулю, тогда другие потенциалы вычисляются из системы (5). Теорема 2. Любая закрытая транспортная задача имеет решение, которое достигается за конечное число шагов метода потенциалов. Построение цикла и определение величины перераспределения груза Циклом в таблице перевозок называется ломаная линия с вершинами в клетках и ребрами, расположенными вдоль строк или столбцов, удовлетворяющая двум требованиям: а) ломаная должна быть связной, т. е. из любой вершины цикла можно попасть в другую вершину, двигаясь по ребрам; б) в каждой вершине цикла сходятся ровно два ребра  одно по строке, другое по столбцу. Замечание В цикле возможны самопересечения, но они происходят только не в вершинах цикла. Примеры построения циклов показаны ниже. 26 Теорема 3. Если в таблице перевозок m строк и n столбцов, и перевозками заполнено (m + n – 1) клеток, то существует цикл, одна из вершин которого расположена в свободной клетке, а все остальные вершины в занятых клетках. Такой цикл называется циклом пересчета свободной клетки. Теорема 4. В таблице перевозок для каждой свободной клетки существует единственный цикл пересчета. Метод потенциалов позволяет не только оценить оптимальность плана, но и улучшить его с помощью цикла пересчета свободной клетки. Алгоритм решения методом потенциалов 1. Поставим в соответствие каждой станции А i переменную – потенциал U i , а каждой станции B j – потенциал V j . 2. Придадим одному из потенциалов заполненных клеток (содержащих грузоперевозки xi j  0) некоторое произвольное значение, например, значение U i = 0 (можно любое другое). Используя условие U i +V j = C i j для каждой заполненной клетки, найдем все остальные потенциалы. 3. Проверим оптимальность опорного решения, вычисляя сумму по* тенциалов для свободных клеток. Если найденная сумма (обозначим ее Ci j * ) меньше стоимости перевозок, то есть Ci j  Ci j для всех свободных клеток, то опорное решение является оптимальным (функция цели имеет минимальное значение). Запишем решение задачи, вычислив стоимость перевозок по найденному оптимальному плану. Если это условие не выполняется хотя бы в одной свободной клетке, * то в случае такого нарушения разность i j  Ci j  Ci j называют невязкой. Наличие невязок означает, что опорное решение не оптимально и надо перейти к следующему опорному плану. Найдем все возможные невязки для свободных клеток. Затем выбираем ту клетку, которой соответствует максимальная невязка max i j  0 (если есть несколько одинаковых нарушений, то выбираем любую из соответствующих клеток). 27 4. В выбранную свободную клетку нужно поставить перевозку. Для этого строим цикл пересчета свободной клетки так, чтобы первая вершина цикла находилась в выбранной клетке, а все остальные в занятых. 5. Пронумеруем вершины цикла, начиная с пересчитываемой свободной клетки. Определим величину сдвига по циклу θ как минимальную из перевозок стоящих в четных вершинах цикла. 6. Вычтем величину θ из перевозок в четных вершинах цикла и прибавим ее к перевозкам в нечетных вершинах. Получен новый опорный план. Далее вновь переходим к пункту 2. Вопросы 1. Что такое транспортная задача. 2. Чем отличаются закрытая и открытая задачи. 3. Какие основные методы нахождения начального опорного плана вы знаете. 4.В чем заключается метод потенциалов. 2.6. Открытая транспортная задача Транспортная задача называется открытой, если запасы груза превышают потребности в нем или, если потребности невозможно удовлетворить имеющимися запасами. Для решения задачи в этих случаях вводят фиктивного потребителя или поставщика груза, на которого и записывают недостающее количество груза или потребности в нем. Стоимости перевозок от фиктивных станций полагаются равными нулю. Тогда задача становится закрытой и решается методом потенциалов. Для примера ниже (табл.3) приведена задача, в которой введен фиктивный (реально не существующий) потребитель В5, позволяющий вывезти все грузы из пунктов А1, А2, А3. Таблица 3 Потребит. Поставщ. В1 В2 В3 В4 В5 * Запасы А1 5 10 9 4 11 40* 50 А2 21 15 7 6 35 14 А3 7 5 10 6 28 50 70 5 40 Потребности 30 40 25 35 25 40 В этом примере построен опорный план по методу наименьшей стоимости. Фиктивный потребитель и перевозка, равная грузу, который фактически остается на станции А1, помечены звездочкой. Задача, записанная в таблице, является закрытой и ее решение можно довести до получения оптимального плана. 2.7. Проблема вырожденного плана задачи При определении первого опорного плана нередко возникает ситуация, когда число занятых клеток меньше величины m + n − 1. Тогда система уравнений, удовлетворяющих условию (5) не позволит определить потенциалы потребителей и поставщиков. Решение проблемы рассмотрим на примере другой транспортной задачи, исходные данные которой представлены в табл. 4. При построении опорного плана методом северо-западного угла в клетку А1-В1 была внесена перевозка x11 = 50, при этом, первая строка и первый столбец были вычеркнуты одновременно (что и привело к вырожденности плана). Такую клетку следует запомнить или отметить с тем, чтобы после заполнения всей таблицы ввести фиктивную перевозку в вычеркнутую строку или столбец, выбрав клетку с наименьшей стоимостью. В примере это клетка А1-В3, которая в дальнейших расчетах считается занятой с перевозкой равной нулю. Таблица.4 Потребит. Поставщ. А1 А2 А3 В1 В2 В3 В4 В5 5 9 4 11 8 14 12 40 6 10 5 10 6 19 25 25 20 50 21 7 7 29 Запасы 50 50 70 Потребности 50 40 35 25 20 Вырожденность плана также может возникнуть при пересчете свободной клетки, если в четных вершинах цикла стоят равные по величине перевозки, совпадающие с величиной сдвига по циклу θ. В таком случае следует внести фиктивную перевозку равную нулю в ту из освобождающихся клеток, в которой стоимость меньше. Вопросы 1. 2. 3. 4. Чем отличается решение закрытой транспортной задачи от открытой. В чем состоит суть решения открытой транспортной задачи. Что такое вырожденность плана транспортной задачи. Когда встречается такая ситуация и как от нее избавиться. 2.8. Транспортная задача на сети Постановка задачи Задача минимизации затрат на перевозки или минимизации величины суммарного пробега может быть решена не только в матричной, но и в сетевой постановке. Такой метод обладает большей наглядностью, так как распределение грузопотоков наносят непосредственно на реальную сеть железной дороги. Станции погрузки, разгрузки и транзитные станции являются вершинами сети, а проездные участки ее дугами. На каждой дуге указывается стоимость перевозки единицы груза (или расстояние в километрах). Если затраты на перевозку между двумя станциями в прямом и обратном направлении различны, то между ними проводят две дуги с разной стоимостью. У вершин сети указывают количество груза на станциях отправителях и потребности в нем (со знаком минус) на станциях потребителях. Требуется так распределить грузопотоки, чтобы переместить весь груз с наименьшими затратами. Математическая модель Обозначим перевозку от i-й станции на j-ую как xij . Так как необходимо учитывать возможность движения и в противоположном направлении x ji , то число переменных задачи будет равно удвоенному числу дуг задачи. 30 Ограничения задачи записываются исходя из условий баланса для каждой вершины – суммарный грузопоток на i-ую станцию минус суммарный поток из нее равен объему выгруженного груза (выгрузке) Ri на этой станции. Выгрузка для станций получателей положительна и равна потребности в грузах, а для отправителей отрицательна и равна по абсолютной величине запасов. k k j 1 j 1  x ji   xij  Ri  i  1,2, ... n  , (1) где k – число связей (дуг) для i-той вершины. При этом выполняется условие неотрицательности переменных: xij  0, (i  1,2, ... n; j  1,2, ... n) . Функция цели задачи по критерию минимума суммарных затрат – n n F ( x)    Cij xij  min i 1 j 1 (2) Заметим, что данная модель не учитывает возможные ограничения на пропускную способность участков сети. Если возникает необходимость это учесть, то в условие задачи вводят дополнительные ограничения в виде неравенств xij  dij , где d ij – пропускная способность дороги на участке между станциями Bi и B j . Построение начального плана задачи Распределим перевозки так, чтобы весь груз был вывезен, все потребности удовлетворены. Грузовые потоки указываются стрелками вдоль дуг с величинами количества перевозимого груза. Введем обозначения: 45 – стоимость перевозки единицы продукции, 30 – направление и количество грузоперевозки, (+60), (–20) – запасы или потребности грузов на i-той станции. Общее число загруженных дуг должно быть равно n – 1, где n – число вершин сети. Если загруженных дуг меньше, то следует ввести на одной из дуг фиктивную (нулевую) перевозку. Совокупность загруженных дуг не должна образовывать замкнутый цикл на сети, для этого, по-возможности, 31 нужно обеспечивать одного потребителя от одного поставщика. Рассмотрим такое распределение на примере. Пусть имеется схема железнодорожной сети, состоящей из десяти станций, для каждой из которых указаны запасы груза (со знаком плюс) или потребности в нем (со знаком минус). На каждой дуге показана стоимость грузоперевозки единицы груза для соответствующего проездного участка. Объем запасов грузов на станциях B3 , B6 и B9 равен количеству потребностей грузов на оставшихся станциях (рис. 1). (–25) (–25) В2 (–30) 45 (+60) В1 45 В7 40 30 В8 (–30) 45 50 45 45 В9 (–30) В5 40 40 (+55) 60 50 (–35) В3 50 В6 40 40 40 45 В4 55 (+80) 70 В10 (–20) Рис.1 Составим первоначальный план грузоперевозок для удовлетворения потребностей грузов на станциях сети и покажем непосредственно на схеме распределение грузопотоков. Вывезем груз со станции В9 (весь запас равен 55 ед.), 30 ед. на станцию В1, 5 ед. на станцию В8 (останется потребность 30 − 5 = 25 ед.), 20 ед. на станцию В10 (рис. 2). 32 (–25) (–25) В2 155 (+80) В4 155 55 40 В6 115 15 35 40 40 45 (–30) (+60) 25 В1 140 В3 115 50 45 45 (+55) 40 25 (–30) В5 165 В7 175 40 30 В8 145 5 В9 100 60 50 (–35) 10 40 30 30 (–30) 45 50 45 45 20 70 В10 170 (–20) Рис.2 Теперь вывезем груз (60 ед.) со станции В3: 25 ед. на станцию В2, 10 ед. на станцию В4 (осталось 25 − 10 = 15), 25 ед. на станцию В8 (весь груз на эту станцию доставлен). Вывозим груз со станции В6: 15 ед. на станцию В4 (все потребности здесь удовлетворены), 30 ед. на станцию В7, 35 ед. на станцию В5 и т. д. В полученном начальном плане перевозок весь груз вывезен, и потребители получают необходимое им количество груза (рис. 7.2), при этом загружено девять дуг при десяти вершинах (план не вырожден). Суммарная стоимость перевозок равна: F ( x)  15  40  25  40  10  40  35  50  30  60  25  30  30  40  5  45  20  70  9125 . Полученный план общей стоимости перевозок грузов, возможно, не является оптимальным. Метод потенциалов улучшения плана Проверим полученный план перевозок методом потенциалов и при необходимости улучшим его. Введем условные величины, приписываемые каждой вершине сети и называемые потенциалами станций Vi . Их численные значения могут быть определены из решения двойственной к данной задаче. По теоремам двойственности план будет оптимальным, если выполнены условия: V j  Vi  cij 33 (3) – для занятых дуг (базисных переменных) V j  Vi  cij (4) – для свободных дуг (свободных переменных). Таким образом, разность между потенциалами для двух станций, между которыми есть грузоперевозки, равна стоимости перевозок на этой дуге. Для свободных дуг она должна быть меньше или равна стоимости перевозок. Один из потенциалов следует задать произвольно, так же, как и в задаче в матричной постановке. Пусть V9 = 100, тогда, следуя по загруженным дугам, прибавляем к потенциалу стоимость перевозки при попутном грузопотоке и вычитаем стоимость при перемещении против потока, получим V1  100  40  140, V8  100  45  145, V10  100  70  170, V3  145  30  115 (так как грузопоток идет в противоположном направлении), V2  115  40  155, V4  115  40  155, V6  155  40  115 (так как грузопоток идет в противоположном направлении), V7  115  60  175, V5  115  50  165 . Проверим выполнение условия оптимальности (3.4) на свободных дугах. V1  V2  155  140  15  45 , V4  V2  155  155  0  55 , V1  V3  140  115  25  50 , V1  V8  145  140  5  45 , V3  V5  165  115  50  40  35  10 , V4  V5  165  155  10  45 , V5  V7  175  165  10  45 , V10  V5  170  165  5  45 , V10  V8  170  145  25  45 , V10  V7  175  170  5  50 Условие оптимальности нарушено лишь на одной дуге В3 – В5 , для которой невязка 35  10 . Если таких дуг больше, то для пересчета необходимо выбрать дугу с наибольшей невязкой. Введем на дуге В3 – В5 перевозку x35  θ , с направлением от вершины с меньшим потенциалом к вершине с большим, при этом образуется замкнутый цикл загруженных дуг В3 – В5 – В6 – В4 – В3 . Причем, движение 34 идет только по загруженным дугам, исключая одну незагруженную В3  В5 . Двигаясь в направлении вновь введенного грузопотока по циклу, отметим все перевозки в противопотоках и выберем из них минимальную. Присвоим это численное значение величине θ  min{10,35} 10 . Вычитая из всех противопотоков и прибавляя ко всем попутным потокам груза величину величину θ , получим новый опорный план задачи. Вычислим потенциалы вершин из условий 3 и убедимся, что условия 4 также выполняются. Полученный оптимальный план представлен в таблице. (– 25) (– 25) В2 155 (+80) В4 145 55 40 В6 105 25 25 40 40 45 (– 30) (+60) 25 В1 140 45 В3 115 50 45 (+55) (– 30) В5 155 10 40 25 В7 165 40 30 В8 145 5 В9 100 60 50 (– 35) 40 30 30 (– 30) 45 50 45 45 20 В10 170 70 (– 20) Таблица 1 № ДУГИ ПЕРЕВОЗКИ 1 В9 – В1 30 2 В9 – В8 5 3 В9 – В10 20 4 В3 – В2 25 5 В6 – В5 25 6 В3 – В5 10 7 В3 – В8 25 8 В6 – В4 25 35 В6 – В7 9 30 Суммарная стоимость грузоперевозок является наименьшей и равна F ( x)  25  40  25  40  25  50  30  60  10  40  25  30  30  40  5  45  20  70  9025. Вопросы 1. В чем отличие обычной транспортной задачи от транспортной задачи на сети. 2. Сформулируйте математическую модель данной задачи. 3. Как происходит нахождение начального опорного плана. 4. Изложите метод потенциалов для данной задачи. 2.9. Задача об оптимальном назначении Постановка задачи Пусть имеется n работ, которые могут выполнить n исполнителей. Известны затраты сi j , (i, j  1, 2,... n) при назначении i-го исполнителя на jую работу. Требуется так распределить исполнителей по работам, чтобы все работы выполнялись, все исполнители были заняты и суммарные затраты при производстве работ были минимальны. Предполагается, что каждый исполнитель выполняет одну работу и каждая работа будет поручена одному исполнителю. Математическая модель Обозначим назначение i-го исполнителя на j-ую работу, как xi j . Тогда       х11  х12  х13  ...  х1n  1, x21  x22  x23  ...  x2 n  1, С другой исполнителю.        (1)  xn 1  xn 2  x n 3  ...  xn n  1. стороны, каждая работа будет поручена одному х11  х21  х31  ...  хn1  1 , x12  x22  x3 2  ...  xn 2  1 ,  x1n  x2 n  x3n  ...  xn n  1 , xij  0, i  1,2,... n; j  1,2,... n Кроме того: xi j = 1, если i- тую работу выполняет исполнитель j; 0, если i- тую работу не выполняет исполнитель j. 36 (2) Функция цели задачи по критерию минимума суммарных затрат: n n f ( X )    C i j xi j  min. i 1 j 1 Очевидно, что данная задача сводится к транспортной задаче, если запасы и потребности равны единице. Как правило, число исполнителей равно числу работ, т. е. рассматривается закрытая задача. Если это условие не выполняется, то вводят либо фиктивного исполнителя, либо фиктивную работу, в результате задача становится закрытой, а в полученном оптимальном назначении одна работа не будет выполнена, либо один исполнитель будет простаивать. Исходные данные задачи записываются в таблицу. Здесь А 1 , А 2 , …, А n – работы, В 1 , В 2 , …, В n – исполнители. Так как «запасы» и «потребности» всегда равны 1, то при решении их не принято писать, кроме того величины «перевозок» также равны 1, поэтому занятые клетки можно просто отметить каким-либо образом. Таблица 1 B1 B2 B3 … Bn Запасы А1 c11 x12 c12 x12 c13 x13 … c1n x1n 1 А2 c21 x21 c22 x22 c23 x23 … c2n1 x2n 1 … … … … … … … Аn cn1 xn1 cn2 xn2 cn3 xn3 … cnn xnn 1 1 1 1 1 Потребности 1 Рассмотрим пример задачи о назначениях размерности n = 5. В табл. 2 приведен первый опорный план, построенный по методу северозападного угла. 37 Таблица 2 А1 А2 А3 А4 А5 В1 В2 В3 В4 В5 12 (1) 8 14 10 24 31 15 (1) 22 7 30 20 25 21 (1) 26 26 11 17 18 15 (1) 8 6 5 9 9 19 (1) Из таблицы видно, что план вырожден n – 1 раз. Такой особенностью обладают все планы задачи об оптимальном назначении. В результате стандартные методы решения транспортной задачи неэффективны и часто приводят к зацикливанию. Рассмотрим «венгерский метод» решения задачи. Решение задачи о назначениях венгерским методом Теорема Кенига. Если к стоимостям какой-либо строки (столбца) задачи о назначениях прибавить одно и то же число, то оптимальный план не изменится. Алгоритм решения, основанный на теореме Кенига: 1) выбрать в каждой строке минимальный элемент и вычесть его из всех элементов этой строки; 2) если в каком-нибудь столбце не появилось нулей, то из всех элементов такого столбца вычитается минимальный элемент этого же столбца; 3) рассматривается множество нулей таблицы и, если оно допустимо, то задача решена, иначе переходим к пункту 4; 38 4) минимальным числом прямых по строкам и столбцам вычеркиваются все нули, а из невычеркнутых элементов выбирается минимальный элемент α ; 5) величина α вычитается из невычеркнутых и прибавляется к дважды вычеркнутым элементам, после чего переходим к пункту 3. Замечание Допустимое множество нулей определяется следующим образом. Нулевой элемент в таблице с номером ij означает возможность выполнения i-тым исполнителем всей работы j. Поэтому расположение нужного количества нулей в таблице должно позволить выбрать единственным способом распределение всех работ между всеми исполнителями. Сформулируем правило нахождения оптимального решения задачи о назначениях, в которой целевая функция минимизируется. Рассмотрим решение задачи на примере. Пусть задана матрица стоимости выполнения работ, причем для пяти работ имеется пять исполнителей. 1. Выберем в каждой строке матрицы наименьший элемент и вычтем его из каждого элемента этой строки. 2. Выберем столбцы, в которых нет нулей и найдем в них наименьший элемент. Затем вычтем его из каждого элемента столбца.  12 8 14 10 24     11 15 22 7 30   20 25 21 26 26     11 17 18 15 8  6 5 9 9 19   4  4 0  3 1  5 2 8 14 5 6 9 9 7 3 4 4  4  0  3 1  6 2 8 15 5 1 6 9 10 7 4 4 16   23  6  0 14   16   23  6 .  0 14  3. Попробуем составить опорное решение из нулей, входящих в полученную матрицу. Но допустимого множества нулей не получено. В частности, выбрав один из нулей во втором столбце, например верхний (работа А1 распределена второму исполнителю), мы не сможем исполь- 39 зовать нижнюю строку с оставшимся нулем. Это означает, что работа А5 останется нераспределенной. 4. Вычеркиваем все нули, проведя наименьшее число прямых, проходящих через все нули в матрице. Среди незачеркнутых найдем наименьший элемент, это элемент α  1 (он дважды подчеркнут в получившейся матрице), вычитаем его из всех невычеркнутых и прибавляем ко всем дважды вычеркнутым элементам матрицы. 4  4 0  3  1  5 2 8 14 5 6 9 9 7 3 4 16   23  6  0 14    3 0 4 2   3 8 13 0 0 6 0 7   3 10 9 8  0 0 2 4  15   22  6  0 13   5. Снова пытаемся составить опорное решение. Допустимое множество нулей получено (выделено двойным подчеркиванием). Из таблицы следует, что первый исполнитель выполняет работу 5, второй – работу 1 и т. д. Запишем решение в виде матрицы X min 0  0   1 1 0 0 0  0 0 1 0 0 1 0 0  0 0 0 0  Возвращаясь к исходной матрице, вычисляем минимальное значение функции цели F ( Х min )  F ( X ) min  8  1  7  1  21  1  8  1  6  1  50 . Решение задачи максимизации Известно, что переход от задачи минимизации к задаче максимизации в линейном программировании достигается изменением знака функции цели. F  X  max   F1  X  min следовательно, данную задачу на нахожде- ние максимума F (X ) можно превратить в задачу минимизации, заменив знаки всех элементов в матрице стоимостей. Далее решение находим методом, рассмотренным выше. 40 Пусть известен доход, который можно получить при назначении каждого исполнителя i (i = 1, 2, … n) на любую работу j ( j = 1, 2, … n). Найдем распределение исполнителей, которое принесет максимальную прибыль. Дана матрица  12 8 14 10 24     11 15 22 7 30   20 25 21 26 26  ,    11 17 18 15 8   6 5 9 9 19      12  8  14  10    11  15  22  7   20  25  21  26    11  17  18  15  6 5 9 9  меняя знаки, имеем  24    30   26   8   19  Прибавим к элементам всех строк модуль максимального элемента этой же строки, а затем проделаем шаги 1 и 2. 6 12 16 10 14 0     13 19 15 8 23 0  0 6 1 5 0     1 3 10 1 7 7  13 14 10 10 0     Множества допустимых нулей должаем решение.  6 15 10 14 0    13 14 8 23 0  0 0 5 0 0    1 0 0 3 10   7 13 10 10 0    0  7 0  1 1  0  14 8 23 0  0 5 0 . 0 0 3 10  13 10 10 0  15 10 14 в матрице нет, следовательно, про- 9 4 8 8 2 17 5 3 7 4 4 0  0 6  16  0  0 6  0  1 0  9 4 8 7 1 16 5 3 6 3 3 1  0  7   17  0  Множества допустимых нулей в матрице нет, следовательно, продолжаем решение. 41  6 15 10 14 0    13 14 8 23 0  0 0 5 0 0   1 3 10    7 13 10 10 0    0  7 0  1 1  9 4 8 8 2 17 5 3 7 4 4 0  0 6  16  0  0 6  0  1 0  9 4 8 7 1 16 5 3 6 3 3 1  0  7   17  0  Получили оптимальное решение. Вычислим максимум функции цели, наложив эти нули на исходную матрицу. 0 6  1  2 0  8 3 7 6 15 5 3 5 2 2 1 0  8  18  0  F  X max   12  22  26  17  19  96 . Первый исполнитель выполняет первую работу, второй – четвертую, третий  вторую и т.д. Вопросы 1. 2. 3. 4. 5. Сформулируйте задачу об оптимальном назначении. Как записывается математическая модель данной задачи. О чем говорится в теореме Кенига. В чем заключается алгоритм решения данной задачи. Чем отличаются решения задачи на минимизацию и задачи на максимизацию. 3. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Во многих экономических моделях исследования операций зависимости между постоянными и переменными факторами лишь в первом приближении можно считать линейными, более же детальное рассмотрение позволяет обнаружить их нелинейность. Как правило, такие показатели, как прибыль, себестоимость, капитальные затраты на производство и др. в действительности зависят от объема производства, расхода ресурсов и т.п. нелинейно. В этом случае возникает задача нелинейного программирования (ЗНП). 42 Задачами нелинейного программирования называются задачи математического программирования, в которых нелинейны и (или) целевая функция, и (или) ограничения в виде неравенств или равенств. Общих способов решения, аналогичных симплекс-методу линейного программирования, для нелинейного программирования не существует. В каждом конкретном случае способ выбирается в зависимости от вида целевой функции F(x). Задачи нелинейного программирования на практике возникают довольно часто, например, когда затраты растут непропорционально количеству закупленных или произведённых товаров. Многие задачи нелинейного программирования могут быть приближены к задачам линейного программирования, и таким образом найдено решение близкое к оптимальному. Встречаются задачи квадратичного программирования, когда функция F(x) есть полином 2-й степени относительно переменных, а ограничения линейны. В ряде случаев может быть применён метод штрафных функций, сводящий задачу поиска экстремума (при наличии ограничений) к аналогичной задаче при отсутствии ограничений, которая обычно решается проще. Общая постановка задачи нелинейного программирования В общем виде ЗНП формулируется следующим образом: f ( x1 , x2 ,..., xn )  max(min) , g i ( x1 , x2 ,..., xn ), , bi , i  1, m , x j  0, j  1, n , где x j ( j  1, n) – управляющие переменные или решения ЗНП; bi (i  1, m) – фиксированные параметры; f , g i , i  1, n – заданные функции от n переменных, причем целевая функция f или (и) хотя бы одна из функций g i , i  1, m являются нелинейными. Решить задачу нелинейного программирования – это значит найти такие значения управляющих переменных x j , j  1, n , которые удовлетворяют 43 системе ограничений и доставляют максимум или минимум целевой функции. Для задач нелинейного программирования, в отличие от линейных задач, нет единого метода решения. В зависимости от вида целевой функции и ограничений, разработаны специальные методы решения, к которым относятся методы множителей Лагранжа, квадратичное и выпуклое программирование, градиентные методы, ряд приближенных методов решения, графический метод. Процесс составления математической модели ЗНП принципиально не отличается от составления модели ЗЛП. Рассмотрим несколько примеров. Задача. На m предприятиях выпускается некоторый продукт. Себестоимость единицы этого продукта на каждом из указанных предприятий есть ci  ai  di xi (i  1, m) , где ai – доля себестоимости, не зависящая от объема выпуска продукции, xi – план выпуска продукта на i-м предприятии. Предприятия должны обеспечить n потребителей с потребностями b j ( j  1, n) , стоимость перевозки из i-го предприятия к j-му потребителю равна cij . Требуется определить такой план распределения выпуска продукта предприятиями и план перевозок его потребителям, чтобы суммарная себестоимость выпуска и стоимость перевозки была минимальной. Математическая модель задачи. Пусть xij – план перевозок от i-го предприятия к j-му потребителю. Для удобства запишем данные и искомые величины задач в виде таблицы. 44 Таблица 1 Потребители Предприятия 1 2 ... m Потребности заказчиков План выпуска изделий 1 2 ... n x11 x21 x12 x22 ... ... x1n x2n x1 x2 xm1 xm2 xmn xm b1 b2 ... bn  n   xij  xi , i  1, m ;  j 1 m   x  b , j  1, n ; j i1 ij  Система ограничений задачи: b1  b2  ...  bn  x1  x2  ...  xm ;   x  0 i  1, m ;  i  x  0,  ij i  1, m; j  1, n .  m m n i1 i1 j 1 Целевая функция: f   ci xi    cij xij . Вместо ci подставим значения, данные в условии задачи: m m m n f   ai xi   di xi2    cij xij . i1 i1 i1 j 1 Надо найти минимальное значение функции (1.5) на множестве допустимых решений. Некоторые особенности решения задач нелинейного программирования 45 Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой или она не относится ни к тому, ни к другому классу. Множество выпукло, если оно вместе с любыми своими точками А и В содержит и все точки отрезка АВ. Примерами выпуклых множеств в пространстве могут служить сфера, пирамида, призма и т.д. В невыпуклом множестве можно указать хотя бы две точки, такие, что не все точки отрезка АВ принадлежат рассматриваемому множеству. Примером невыпуклого множества в пространстве является тор. Функцию y = f(x) одной переменной будем называть выпуклой, если отрезок, соединяющий две любые точки ее графика, принадлежит графику или расположен выше его. Функция вогнута, если отрезок, соединяющий две любые точки графика, принадлежит ему или расположен ниже него. Аналогично можно сформулировать определения понятий вогнутой и выпуклой функций нескольких переменных. Гиперповерхность z = f(x1, x2,..., xn) выпуклая, если отрезок, соединяющий две ее любые точки, лежит на поверхности или выше ее. Гиперповерхность z = f(x1, x2,..., xn) вогнута, если отрезок, соединяющий две ее любые точки, лежит на поверхности или ниже нее. Утверждение. Если область Ф замкнута и ограничена, то дифференцируемая функция z  f (x) достигает в этой области своих наибольшего и наименьшего значений или в стационарной точке, или в граничной точке области. Таким образом, чтобы найти наибольшее (наименьшее) значение функции z  f (x) в области Ф, нужно: 1) найти все стационарные точки внутри области Ф и вычислить зна- чения функции в них: 2) исследовать функцию на экстремум на границе области Ф; 3) сравнить значения функции, полученные в п.1 и п. 2; наибольшее (наименьшее) из этих чисел и будет наибольшим (наименьшим) значением функции во всей области. 46 Граница области Ф аналитически может быть задана системой уравнений (условий) относительно переменных x1 , x2 ,..., xn . Поэтому, исследуя экстремальные свойства функции на границе, необходимо решить задачу определения условного экстремума. 3.1. Условный экстремум Пусть необходимо найти экстремум функции z  f (x) при условии, что переменные x1 , x2 ,..., xn удовлетворяют уравнениям: φ i ( x1 , x2 ,..., xn ) = 0, i  1, m, m  n. Предполагается, что функции f и φi имеют непрерывные частные производные по всем переменным. Уравнения (1.9) называются уравнениями связи. В точке x  ( x1 , x2 ,..., xn ), удовлетворяющей уравнениям связи (1.9), функция z  f (x) имеет условный максимум (минимум), если неравенство f ( x )  f ( x) ( f ( x )  f ( x)) имеет место для всех точек x , координаты ко- торых удовлетворяют уравнениям связи. Графический метод решения Рассмотрим примеры решения задач нелинейного программирования с двумя переменными, причем их целевые функции и системы ограничений могут быть заданы в линейном и нелинейном виде. Пример. Найти глобальный экстремумы функции z  2 x1  x2 при ограничениях  x1 2  x2 2  16;   x1, 2  0. Решение. Область допустимых решений – часть окружности с радиусом 4, которая расположена в первой четверти (рис. 1). 47 Рис. 1. Область допустимых решений Линиями уровня целевой функции являются параллельные прямые с угловым коэффициентом, равным двум. Глобальный минимум достигается в точке О(0, 0), а глобальный максимум – в точке А касания линии уровня и окружности. Проведем через точку А прямую, перпендикулярную линии уровня. Прямая проходит через начало координат, имеет угловой коэффициент x 1 и уравнение x 2  1 . 2 2 Решаем систему  x1 2  x 2 2  16;   x1  x2  . 2  Откуда находим координаты точки А: x1  z 8 5 4 5 , x2  , тогда 5 5 16 5 4 5   4 5  8,9. Таким образом, мы нашли и глобальный макси5 5 мум. 3.2. Метод множителей Лагранжа Среди приведенных ранее задач особое место занимают задачи типа Z  f ( x1 , x2 ,..., xn )  max(min) ; φ i ( x1 , x2 ,..., xn )  bi , i  1, m , 48 для решения которых можно воспользоваться классическим методом оптимизации Лагранжа, или методом разрешающих множителей. При этом предполагают, что функции f и φ i (i  1, m) непрерывны вместе со своими первыми частными производными. Можно указать следующий порядок решения задачи методом множителей Лагранжа: 1) составить функцию Лагранжа: m L ( x1 ,..., x n , λ 1 ,..., λ m )  f ( x1 ,..., x n )   λ i (bi  φ i ( x1 ,..., x n )), i 1 здесь λ1 , λ 2 ,..., λ n – множители Лагранжа; 2) найти частные производные функции Лагранжа по всем переменным x1 ,..., xn , λ1 ,..., λ m и приравнять их нулю. Тем самым получим систему: m φ  L f   λ i i  0, ( j  1, n),   x  j x j i 1 x j   L  b  φ  0, (i  1, m). i i  λ i Эта система состоит из m + n уравнений. Решить эту систему (если это окажется возможным) и найти таким образом все стационарные точки функции Лагранжа; 3) из стационарных точек, взятых без координат λ1 ,..., λ m , выбрать  точки, в которых функция f ( x ) имеет условные локальные экстремумы при наличии ограничений. Этот выбор осуществляется, например, с применением достаточных условий локального экстремума. Часто исследование упрощается, если использовать конкретные условия задачи. В основе метода Лагранжа решения классической задачи оптимизации лежит утверждение, x  ( x10 , x20 ,..., xn0 ) имеет что если экстремум, то Z  f ( x1 , x2 ,..., xn ) в существует такой точке вектор (λ10 , λ 02 ,..., λ 0n ), что точка ( x10 , x20 ,..., xn0 , λ10 , λ 02 ,..., λ 0n ) является решением систе- мы. Следовательно, решая систему, получаем множество стационарных точек, в которых функция Z может иметь экстремальные значения. При этом, как правило, неизвестен способ определения точек глобального мак49 симума или минимума. Однако если решения системы найдены, то для определения глобального экстремума достаточно найти значения функции в соответствующих точках области определения. Множителям Лагранжа можно придать следующий экономический f ( x1 , x2 ,..., xn ) смысл. Если – доход, соответствующий плану x  ( x1 , x 2 ,..., x n ), а функция φ i ( x1 , x2 ,..., xn ) – издержки i-го ресурса, соответ- ствующие этому плану, то λ i – цена (оценка) i-го ресурса, характеризующая изменение экстремального значения целевой функции в зависимости от изменения размера i-го ресурса. Вопросы 1. Понятие выпуклой и вогнутой функции? 2. Как определяется уравнение связи. 3. Понятие «линии уровня». 4. Примеры производственных функций. 5. Определение локального экстремума? 6. Определение глобального экстремума. 7. Понятие условного экстремума. 8. Как используется функция Лагранжа? 4. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Динамическое программирование – математический метод поиска оптимальных решений по управлению многошаговыми процессами, в которых состояние исследуемых систем изменяется во времени или поэтапно. Подобные системы и процессы широко распространены в реальном мире, а необходимость эффективного управления ими объективно определяет важность и актуальность использования математических методов решения соответствующих управленческих задач. Теоретической основой метода динамического программирования (ДП) является принцип оптимальности, имеющий широкую сферу приложений в экономике, технике, естествознании, военном деле. Регулярное изучение многошаговых процессов восходит к работам русского математика А. А. Маркова начала XX века. Его исследования были продолжены в 1940-х годах американским математиком А. Вальдом, что привело к возникновению так называемого исследовательского анали50 за. Впервые основные принципы оптимального управления многошаговыми процессами наиболее полно и систематизировано были сформулированы в 1950-х годах американским математиком Р. Беллманом (Беллман Ричард Эрнест (1920–1984); американский математик; основные труды по вычислительной математике и теории оптимального управления). Основные понятия и постановка задачи Многошаговый процесс – процесс, при котором происходит последовательный переход объекта или системы данного класса из одного состояния в другое. При этом разделение всего процесса на отдельные последовательные шаги либо естественным образом вытекает из реальных свойств системы, либо вводится в задачу искусственно из тех или иных соображений. Управляемые системы – системы, на состояние которых может целенаправленно влиять некоторый управляющий субъект (лицо, принимающее решение). Возможность осуществлять управление системой обусловливает возникновение проблемы выбора и неизбежно приводит к задаче поиска наилучшего, наиболее целесообразного, оптимального с той или иной точки зрения управления. Задачи такого типа называются задачами управления многошаговыми процессами, или задачами многоэтапной оптимизации или просто задачами ДП. Рассмотрим некоторую техническую или экономическую систему или объект: техническое средство, предприятие, производственное объединение, отрасль промышленности, регион и т.д. Состояние системы – обозначим её через S – в определённый момент характеризуется набором параметров, которые могут иметь различный экономический смысл и представлять собой, например, производственные мощности, обеспеченность ресурсами, штат сотрудников, себестоимость продукции, объём средств на счёте предприятия и т.п. Параметр, характеризующий состояние системы, называется переменной состояния и обозначается через х, при этом переменная состояния может принимать значения из некоторого множества Х допустимых значений, т.е. x  X . 51 Состояние управляемой системы S может меняться под влиянием различных факторов. Наиболее важную роль среди них играет воздействие со стороны управляющего субъекта, осуществляемое путём выбора им надлежащих значений, называемых управляющими переменными, или просто управлениями. В различных конкретных задачах в качестве управлений могут выступать, например, состав работающего оборудования, режим его эксплуатации, количество потребляемых ресурсов, объём подлежащих производству товаров, цены на производимую продукцию, количество принимаемых работников и т.п. Управляющую переменную будем обозначать через u; она может принимать значения из некоторого множества U допустимых значений, u U . Рассмотрим шаг, при котором система S под действием управления u переходит из некоторого начального состояния х0 в последующее состояние х1. Переход системы S из состояния х0 в состояние х1 сопровождается получением некоторого экономического эффекта, который зависит от исходного состояния х0 и применяемого управления u и количественно выражается целевой функцией, или критерием оптимальности f: f  f ( x0 , u ) . Функцию f можно понимать как количественный показатель эффективности управления системой S на рассматриваемом шаге. Например, если функция f представляет собой доход или прибыль, то наибольший интерес представляет её максимальное значение: f  max; если же функция f представляет расход, убыток, затраты, издержки, то наибольший интерес представляет её минимальное значение: f  min. Основным объектом при решении задач динамического программирования являются многошаговые процессы, включающие в общем случае некоторое число шагов N. Обозначим через i переменный номер шага, при этом i 1...N . На каждом шаге процесса управление u может принимать различные значения u1 , u2 ,..., u N . На первом шаге – i = 1 – система S под действием управления u1 переходит из начального состояния x0 в состояние x1, при этом достигается экономический эффект, равный f1. На втором шаге – i = 2 – система S под действием управления u2 переходит из состояния x1 в состояние x2, при этом достигается экономический эффект, равный f2. Рассуждая аналогично, 52 получим, что на последнем шаге процесса – i = N – система S под действием управления uN переходит из состояния xN –1 в конечное состояние xN, и при этом достигается экономический эффект, равный fN. Схематически многошаговый процесс можно представлен на рис.1. u2 u1 x0 f1(x0, u1) x1 f2(x1, u2) … u3 x2 … 10 uN –1 uN xN – 1 fN(xN –1, uN) xN Рис.1. Переход системы S из состояния x0 в состояние xN Предположим, что состояние хi, в которое перешла система S, зависит от данного состояния хi–1 и выбранного управления ui и не зависит от того, каким образом система S перешла в состояние хi–1. Еcли в результате реализации i-го шага обеспечен определенный доход, также зависящий от исходного состояния системы хi–1 и выбранного управления ui, равный fi(хi–1; ui), то общий доход за N шагов составляет N F   fi ( xi 1; ui ). i 1 Таким образом, сформулированы два условия, которым должна удовлетворять рассматриваемая задача динамического программирования. Первое условие обычно называют условием отсутствия последействия, а второе – условием аддитивности целевой функции задачи. Задача состоит в нахождении оптимальной стратегии управления, т.е. такой совокупности управлений U *  (u1* , u2* ,..., un* ), в результате реализации которых система S за N шагов переходит из начального состояния x0 в конечное xN и при этом функция дохода принимает наибольшее значение. Теорема (принцип оптимальности Беллмана). Каково бы ни было состояние системы перед очередным шагом, надо выбрать управление на этом шаге так, чтобы доход на данном шаге плюс оптимальный доход на всех последующих шагах был максимальный. 53 При решении задачи на каждом шаге выбирается управление, которое должно привести к оптимальному выигрышу. Если считать все шаги независимыми, тогда оптимальным управлением будет то управление, которое обеспечит максимальный выигрыш именно на данном шаге. Однако, например, на приобретение новой техники взамен устаревшей затрачиваются определенные средства, поэтому доход от ее эксплуатации вначале может быть небольшой, а в следующие годы новая техника будет приносить больший доход. И наоборот, если принято решение оставить старую технику для получения дохода в текущем году, то в дальнейшем это приведет к значительным убыткам. То есть в многошаговых процессах управление на каждом конкретном шаге надо выбирать с учетом его будущих воздействий на весь процесс. Из принципа оптимальности следует, что оптимальную стратегию управления можно получить, если сначала найти оптимальную стратегию управления на N-м шаге, затем на двух последних шагах, затем на трех последних шагах и т.д., вплоть до первого шага. Таким образом, решение рассматриваемой задачи динамического программирования целесообразно начинать с определения оптимального решения на последнем, N-м, шаге. Для того чтобы найти это решение, очевидно, нужно сделать различные предположения, как мог окончиться предпоследний шаг, и с учетом этого выбрать управление u N0 , обеспечивающее максимальное значение функции дохода f N ( xN 1; uN ) . Такое управление, выбранное при определенных предположениях, как окончился предыдущий шаг, называется условно оптимальным управлением. Следовательно, принцип оптимальности требует находить на каждом шаге условно-оптимальное управление для любого из возможных исходов предшествующего шага. Для математической формулировки принципа оптимальности введем некоторые дополнительные обозначения. Обозначим через соответственно условноF1 ( xN 1 ), F2 ( xN 2 ),..., Fi ( xN i ),..., FN ( x0 ) оптимальные значения функции цели на последнем этапе, двух последних и т.д., на i последних и т.д., на всех N этапах. Начинаем с последнего этапа. Пусть x N 1 ̶ возможные состояния системы на начало N-го этапа. Находим: 54 F1 ( xN 1 )  max(min) f N ( xN 1 , u N ). uN F2 ( xN 2 )  max(min)( f N 1 ( xN 2 , u N 1 )  F1 ( xN 1 )). u N 1 Аналогично: F3 ( xN 3 )  max(min)( f N 2 ( xN 3 , u N 2 )  F2 ( xN 2 )), uN  2 …………………………………… Fi ( xN i )  max(min)( f N i 1 ( xN i , u N i 1 )  Fi 1 ( xN i1 )), u N  i 1 ……………………………………. FN ( x0 )  max(min)( f1 ( x0 , u1 )  FN 1 ( x1 )). u1 Данные выражения называются функциональными уравнениями Беллмана. Отчётливо просматривается их рекуррентный (возвратный) характер, т.е. для нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N – 1 этапах и т.д. Поэтому функциональные уравнения называют рекуррентными (возвратными) соотношениями Беллмана. Итак, в результате последовательного прохождения всех этапов от конца к началу мы определяем максимальное (минимальное) значение выигрыша (затрат) за N шагов и для каждого из них находим условнооптимальное управление. Такая процедура называется условной оптимизацией. После того как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с N-го по первый, осуществляется второй этап решения задачи, называемый безусловной оптимизацией. Чтобы найти оптимальную стратегию управления, то есть определить искомое решение задачи, нужно пройти всю последовательность шагов, только на этот раз от начала к концу. * А именно: на первом шаге в качестве оптимального управления u1 возьмем найденное условно оптимальное управление u10 . На втором шаге * * найдем состояние x1 , в которое переводит систему управление u1 . Это состояние определяет найденное условно-оптимальное управление u20 , 55 которое теперь будем считать оптимальным. Зная u2* находим x2* , а значит, определяем u3* и т.д. В результате этого находим решение задачи, т.е. максимально (минимально) возможный доход (затраты) и оптимальную стратегию управления, включающую оптимальные управления на отдельных шагах. Процесс довольно громоздкий. Однако использование ЭВМ позволяет находить на основе метода динамического программирования решение и более сложных практических задач. Используя метод динамического программирования, найдем решение для некоторых частных задач. 4.1. Выбор оптимальной стратегии обновления оборудования (задача о замене оборудования) Важной экономической проблемой является своевременное обновление оборудования: автомобилей, станков, телевизоров, магнитол и т. п. Старение оборудования включает физический и моральный износ, в результате чего растут затраты на ремонт и обслуживание, снижается производительность труда и ликвидная стоимость. Со временем возникает необходимость замены оборудования, так как его дальнейшая эксплуатация обходится дороже, чем ремонт. Следовательно, задача о замене может быть сформулирована так. В процессе работы оборудование даёт ежегодно прибыль, требует эксплуатационных затрат и имеет остаточную стоимость. Эти характеристики зависят от возраста оборудования. В начале любого года оборудование можно сохранить или продать по остаточной стоимости и приобрести новое. В случае сохранения оборудования возрастают эксплуатационные расходы и снижается производительность. При замене нужны значительные дополнительные капитальные вложения на приобретение и установку нового оборудования. Задача состоит в определении оптимальной стратегии замен в плановом периоде с тем, чтобы суммарная прибыль за этот период была максимальной. Критерием оптимальности являются доход от эксплуатации оборудования (задача максимизации) либо суммарные затраты на эксплуатацию в течение планируемого периода (задача минимизации). Для решения поставленной задачи введём следующие обозначения: 56 r(t) – стоимость продукции, производимой за год на единице оборудования возраста t лет; u(t) – расходы, связанные с эксплуатацией и ремонтом оборудования возраста t лет; s(t) – остаточная стоимость оборудования возраста t лет; Р – покупная цена нового оборудования; N – продолжительность планового периода; t = 0, 1, 2, … , N – номер текущего периода. t0 – начальное состояние, возраст оборудования на начало планового периода. Под возрастом оборудования понимается период эксплуатации оборудования после последней замены, определенный в годах. Чтобы решить задачу, применим принцип оптимальности Беллмана. Рассмотрим интервалы (годы) планового периода в последовательности от конца к началу. Введём функцию условно-оптимальных значений функции цели Fi(t). Эта функция показывает максимальную прибыль, получаемую от оборудования возраста t лет за последние i лет планового периода. Возраст оборудования рассматривается в направлении естественного хода времени. Например, t = 0 соответствует использованию совершенно нового оборудования. Временные шаги процесса нумеруются в обратном порядке. Например, при i = 1 рассматривается последний год планового периода, при i = 2 – последние два года и т.д., при i = N – последние N лет, т.е. весь плановый период. Элементы модели динамического программирования: 1. Систему составляет оборудование. 2. Состоянием на i-м этапе является срок эксплуатации t (возраст) механизма к началу i-го года. 3. Этап i представляется порядковым номером года i, i = 1,2,..., N. 4. Вариантами решения на i-м этапе (т.е. для i-го года) являются альтернативы: продолжить эксплуатацию или заменить механизм в начале i-го года. Для нахождения оптимальной политики замен процесс следует проанализировать, согласно принципу оптимальности, от конца к началу. Для этого сделаем предположение о состоянии оборудования на начало последнего года (i = 1). Пусть оборудование имеет возраст t лет. В начале N 57 года имеются две возможности: 1) сохранить оборудование на N-й год и в конце планового периода продать по остаточной стоимости, тогда прибыль за последний год составит r(t) – u(t) + s(t + 1); 2) продать оборудование по остаточной стоимости и купить новое и весь год работать на новом оборудовании, а в конце планового периода продать его (к моменту продажи возраст оборудования уже составит t = 1), тогда прибыль за последний год будет равна r(0) – u(0) + s(t) – Р + s(1). Учитывая значение прибыли при различном образе действия (замена (З) – сохранение (С)), принимаем соответствующее решение о продолжении эксплуатации или замене оборудования. Рекуррентное уравнение для последнего этапа имеет следующий вид: r (t )  u (t )  s (t  1), если сохранить (С), F1 (t )  max  r (0)  u (0)  P  s (t )  s (1), если заменить (З). Пусть i = 2, т.е. рассмотрим прибыль за два последних года. Делаем предположение о возможном состоянии t оборудования на начало предпоследнего года. Если в начале этого года принять решение о сохранении оборудования, то к концу года будет получена прибыль r(t) – u(t). На начало последнего года оборудование перейдёт в состояние t + 1, и при оптимальной политике в последнем году оно принесёт прибыль, равную F1(t + 1). Таким образом, общая прибыль за два года составит r(t) – u(t) + F1(t + 1). Если же в начале предпоследнего года будет принято решение о замене оборудования, то прибыль за предпоследний год составит r(0) – u(0) + s(t) – Р. Поскольку приобретено новое оборудование, на начало последнего года оно будет в состоянии t = 1. Следовательно, общая прибыль за последние два года при оптимальной политике в последнем году составит r(0) – u(0) + s(t) – Р + F1(1). Таким образом, условно-оптимальной в последние два года будет политика, доставляющая максимальную прибыль: r (t )  u (t )  F1 (t  1)) С, F2 (t )  max  r (0)  u (0)  P  s(t )  F1 (1) З. Аналогично находим выражения для условно-оптимальной прибыли за три последних года, четыре и т.д. 58 Общее функциональное уравнение (рекуррентное соотношение) примет вид: r (t )  u (t )  Fi1 (t  1)) С, Fi (t )  max  t r (0)  u (0)  P  s(t )  Fi 1 (1) З. Начальное состояние t0 известно, поэтому при i = N получим max F = FN(t0). Таким образом, разворачивая весь процесс от конца к началу, получаем, что максимальная прибыль за плановый период N лет составит FN(t0). Из выражения FN(t0) находим оптимальное решение в начале первого года, потом из него – оптимальное решение для второго года и т.д. 4.2. Задача оптимального распределения ресурсов К задачам оптимального распределения ресурсов относятся задачи о распределении средств на приобретение оборудования, закупку сырья и найма рабочей силы; задачи о распределении товаров по торговым и складским помещениям; задачи о распределении средств между различными отраслями промышленности и т.д. Рассмотрим пример широко распространённой задачи: как спланировать работу группы предприятий, чтобы экономический эффект от выделенных этим предприятиям дополнительных финансовых или материальных ресурсов был максимальным. Пусть имеется некоторое количество ресурсов Х, которое необходимо распределить между n различными предприятиями, входящими в некоторое производственное объединение, так, чтобы получить максимальную суммарную эффективность от выбранного способа распределения. В данной задаче управляемой системой S является производственное объединение, состояние системы S перед выбором размера суммы, выделяемой i-му предприятию, определяется величиной остатка средств после выделения другим i–1 предприятиям, многошаговым процессом – процесс выделения средств предприятиям. Отметим, что структура многошагового процесса в данной задаче определяется не течением времени, а порядком планирования распределения инвестиций. Элементы модели динамического программирования таковы: число шагов N в данной задаче следует принять равным n, соответствующим 59 числу предприятий. На первом шаге планируется выделение средств предприятию П1, на втором шаге – предприятию П2 и т.д., на шаге N – предприятию Пn. В качестве управляющей переменной u примем объём средств, выделяемых предприятиям на каждом из шагов процесса. А именно: переменная u1 представляет объём средств, выделяемых предприятию П1 (на первом шаге процесса), u2 – объём средств, выделяемых предприятию П2 (на втором шаге) и т.д. Функция gi(ui) – функция полезности, в данном случае это величина, определяющая частный экономический эффект на i-м шаге процесса, зависит только от объёма ui инвестированных средств в предприятие Пi. fk(Х) – наибольший доход, который можно получить при выделенных средствах в объёме Х от первых k различных предприятий. Сформулированную задачу можно записать в математической форме: n f n ( X )  max  gi (ui ) i 1 n при ограничениях u i 1 i  X , xi  0, i  1,.., n. Составим рекуррентное соотношение, связывающее fk(Х) и fk–1(Х) для решения задачи об оптимальном распределении ресурсов. Пусть uk – количество ресурса, выделенное предприятиям k-м способом, при этом 0 ≤ uk ≤ Х, тогда для (k –1) способов остается величина ресурсов, равная (Х– uk). Наибольший доход, который получается при использовании ресурса (Х– uk) от первых (k –1) способов, составит fk–1(Х– uk). Для максимизации суммарного дохода от k-гo и первых (k –1) способов необходимо выбрать uk таким образом, чтобы выполнялись соотношения: f1 ( X )  g1 ( X ), f k ( X )  max{g k (uk )  f k 1 ( X  uk )}, k  2,K , n. Поиск оптимального распределения инвестиций включает условную и безусловную оптимизацию. 4.3. Задача о минимизации затрат на строительство и эксплуатацию предприятий 60 Задача по оптимальному размещению производственных предприятий может быть сведена к задаче распределения ресурсов согласно критерию минимизации с учетом условий целочисленности, накладываемых на переменные. Допустим, на определённой территории (области, города, районы, микрорайоны и т.д.) необходимо построить Х предприятий одинаковой мощности, занимающихся некоторой деятельностью. Подсчитаны затраты на строительство и эксплуатацию таких предприятий в соответствии с предполагаемым их расположением на данной местности. Необходимо так разместить предприятия, чтобы минимизировать затраты на их строительство и эксплуатацию. Элементы модели динамического программирования таковы: число шагов N в данной задаче следует принять равным n, соответствующим числу пунктов, в которых планируется строительство. На первом шаге планируется строительство в первом пункте П1, на втором шаге – в первых двух пунктах П1 и П2 и т.д., на шаге N – в пунктах П1 , П2, … , Пn. В качестве управляющей переменной x примем количество предприятий, построенных на каждом шаге процесса. Введем следующие обозначения: Х – количество предприятий, которые необходимо построить; n – число пунктов, в которых планируется строительство; xi – количество предприятий, построенных в i-м пункте (i = 1, n ); gi(xi) – функция расходов, равная, например, величине затрат на строительство xi предприятий в i-м пункте; φk(Х) – наименьшие затраты при строительстве Х предприятий в первых k пунктах. Сформулированную задачу можно записать в математической форме: φn(X)  min n  g (x ) i 1 i i при ограничениях n x i 1 i  X , xi  0, i  1K n. Составим рекуррентное соотношение, связывающее φk(X) и φk– 1(X) для решения поставленной задачи. 61 Пусть хk – количество предприятий, построенных в первых k пунктах, при этом 0 ≤ хk ≤ Х, тогда в оставшихся (k –1) пунктах остаётся построить (Х– хk) предприятий. Наименьшие затраты на строительство (Х–хk) предприятий в первых (k –1) пунктах составят φk– 1( Х – хk). Для минимизации суммарных затрат при возведении предприятий в k-м и в первых (k –1) пунктах необходимо выбрать хk таким образом, чтобы выполнялись соотношения: φ1(X) = g1(X), φk(X)  min{gk ( xk )  φk– 1( Х – хk)}, k  2,K , n. Поиск оптимального распределения предприятий в предлагаемых пунктах включает условную и безусловную оптимизацию. 4.4. Задача об оптимальной загрузке транспортного средства неделимыми предметами (задача о рюкзаке) Транспортное средство грузоподъёмностью W усл. ед. массы загружается предметами N типов Т1, Т2, …, ТN, масса m и стоимость p усл. ден. ед. каждого из которых известны и приведены в таблице. Т1 Т2 … ТN m1 m2 … m mN p1 p2 … p pN Требуется найти такой вариант загрузки, при котором стоимость перевозимого груза была бы максимальной. В иной интерпретации данная задача известна как задача о рюкзаке, или о ранце. При этом грузоподъёмность транспортного средства аналогична вместимости ранца, а масса и стоимость погружаемых предметов имеют то же самое смысловое значение. Построим математическую модель данной ситуации. В сформулированной задаче управляемой системой является загружаемое транспортное средство, многошаговым процессом – процесс планирования погрузки предметов. Число шагов в данной задаче следует принять равным N, соответствующим числу типов погружаемых предметов: на первом шаге планируется погрузка предметов типа Т1, на втором шаге – предметов типа Т2 и т.д., на N шаге – предметами типа ТN. Переменной состояния x, опреде- 62 ляющей состояние системы в ходе процесса, примем суммарную массу предметов, погружённых в транспортное средство. А именно: переменная x1 представляет массу предметов, погружённых после первого шага процесса (т.е. только предметов типа Т1), x2 – массу предметов, погруженных после второго шага (предметов типов Т1 и Т2) и т.д. Поскольку в начальный момент общая масса предметов, погруженных в транспортное средство, равна нулю, то начальное состояние системы характеризуется значением x0  0. Чтобы не допустить перегруза транспортного средства, обязательно должно выполняться условие: xi  W . В качестве управляющей переменной u примем количество предметов каждого типа, погружаемых в транспортное средство, т.е. u = (u1, …, uN). Частный экономический эффект на i-м шаге процесса выражается произведением ui pi , а суммарная эффективность как раз и будет целевой функцией или критерием: F (U )  u1 p1  u2 p2  ...  uN pN  max. Планом или управлением будет вектор U *  (u1* , u2* ,..., un* ), при котором целевая функция принимает максимальное значение. Очевидно, что перегружать транспортное средство нельзя, а это влечёт следующие ограничения: N u m i 1 i i W. Данные формулы являются математической моделью данной задачи. Турист, собираясь в поход, пакует свой рюкзак исходя из его размеров, своих сил и полезности предметов. Первые две величины вызывают разумные ограничения, не позволяющие как угодно увеличивать суммарную полезность груза. Вот почему сформулированная задача называется ещё задачей о рюкзаке. Проведём рассуждения, аналогичные рассуждениям в задаче о капиталовложениях. Обозначим через  i (x) максимальную эффективность при размещении предметов Т1, Т2, …, Тi типов при общем их весе, не превосходящем х. Очевидно, что размещая предметы всех N видов, мы должны 63 использовать грузоподъёмность транспортного средства полностью, т.е. при i = N будем находить значение  N при x = W. Учтём при этом, что размещая предметы N-го типа, мы используем для них u N mN от общей грузоподъёмности, а на остальные (N – 1) типы остаётся W  u N mN . Ясно, что u N mN не должно превышать W, поэтому количество предметов N-го типа может принимать значения от нуля до W   m  (квадратные скобки обозначают целую часть от деления W на mN).  N Таким образом, max F (U )  φ N (W )  max W  0  uN     mN  uN pN  φ N 1 (W  uN mN  . Размещая предметы не всех типов, мы должны получить значения максимальной эффективности для любой доли x от 0 до W. Поэтому φi ( x)  max x 0  ui     mi  ui pi  φi1 ( x  ui mi . Это соотношение – рекуррентное соотношение Беллмана данной модели для i-го шага. Уравнение Беллмана для первого шага имеет вид: φ1 ( x)  max  x 0  u1     m1  u1 p1. Варианты задачи о загрузке К имеющимся в классической формулировке ограничениям можно добавить ряд дополнительных условий, например:  каждый предмет из множества можно выбирать произвольное число раз (то есть предметы с одинаковым весом и ценностью могут повторяться сколь угодно раз);  каждый предмет можно использовать только один раз (все предметы уникальны и повторяться не могут);  каждый предмет можно использовать строго определённое число раз (это значит, что есть ограничения на число повторов предметов с одним весом и ценностью); 64  наличие ограничений типа несовместимостей (запрет на совместную упаковку некоторых грузов);  дополнительные ограничения на размер транспортного средства (транспортное средство имеет сложную форму);  наличие приоритета у размещаемых вещей (каждой вещи присваивается число, называемое приоритетом, тогда предмет с большим приоритетом будет более желателен для погрузки);  возможность дробления груза (предметы можно делить на части в определённой пропорции, соответственно, вес тоже делится между этими частями в той же пропорции);  многомерные рюкзаки. 4.5. Выбор оптимального маршрута (задача о кратчайшем пути) Математический аппарат динамического программирования, основанный на пошаговой оптимизации, может быть использован при нахождении кратчайших расстояний, например, на географической карте, представленной в виде сети. Решение задачи по определению кратчайших расстояний между пунктами отправления и пунктами получения продукции по существующей транспортной сети является исходным этапом при решении таких экономических задач, как оптимальное прикрепление потребителей за поставщиками, повышение производительности транспорта за счёт сокращения непроизводительного пробега и др. Задача 1. Пусть транспортная сеть состоит из 11 узлов, часть из которых соединены магистралями. На рисунке показаны сеть дорог и расстояния между промежуточными пунктами сети. Необходимо определить кратчайший маршрут движения транспорта из начального пункта А в конечный пункт В. 65 2 5 7 6 3 5 8 8 6 7 4 3 А 1 3 4 6 11 9 3 9 11 8 В 5 2 6 3 7 8 4 7 10 10 10 Решение данной задачи методом динамического программирования предполагает, что процессу принятия оптимального решения может быть придан пошаговый (поэтапный) характер. С этой целью разобьем все пункты сети на этапы (рис.). К первому этапу отнесём пункты, из которых можно попасть в конечный пункт В (таковыми будут 8, 9 и 10), ко второму – пункты, из которых можно попасть непосредственно в 8, 9 и 10 пункты (таковыми будут 5, 6 и 7), к третьему отнесём пункты, из которых можно попасть в любой из пунктов предыдущего этапа (т.е. 2, 3 и 4) и т.д. В итоге движение транспорта из пункта А в пункт В можно рассматривать как четырёхэтапный процесс. 2 6 3 5 7 5 8 8 6 7 4 3 А 1 4 3 6 11 3 9 9 11 8 В 5 2 6 3 7 8 4 4-й этап 7 10 3-й этап 10 2-й этап 10 1-й этап В рассматриваемой задаче в качестве физической системы S выступает транспорт, перемещающийся из начального состояния x1 (из пункта A) в конечное состояние x11 (пункт В), и сеть дорог. За состояние xk системы 66 перед k-м шагом естественно принять местонахождение транспорта в пункте, в котором он пребывает перед этим шагом. Управление uk на k-м шаге состоит в выборе участка (i, j) дороги, по которой следует направляться транспорту из данного пункта i в соседний j в общем направлении к пункту В. Состояние в конце шага определяется номером пункта, в который отправится транспорт в результате сделанного выбора (принятого управления), а значение fk целевой функции на k-м шаге – это расстояние от данного пункта до выбранного соседнего. Выразим математически функциональные уравнения Беллмана (рекуррентные соотношения) для данной задачи: k – номер этапа (k = 1, 2, 3, 4); i – пункт, из которого отправляется транспорт (i = 1, 2, …, 9); j – пункт, в который попадает транспорт (j = 2, 3, …, 10); Сi, j – расстояние от пункта i до пункта j; fk(i) – минимальное расстояние на k-м этапе решения задачи от пункта i до конечного пункта. Для первого этапа (k = 1) функция Беллмана представляет собой минимальное расстояние при движении транспорта из пунктов 1-го этапа в конечный пункт, т.е. f1(i) = Ci,10. Для последующих шагов расстояние складывается из двух слагаемых – расстояния Сi, j из пункта i k-го этапа в пункт j (k–1)-го этапа и минимального расстояния при движении транспорта от пункта j до конечного пункта, т.е. fk-1(j). Таким образом, рекуррентные соотношения будут иметь вид f k (i )  min Ci , j  f k 1 ( j ) . Поиск оптимального маршрута методом динамического программирования включает условную и безусловную оптимизацию. Условная оптимизация осуществляется в результате движения от первого этапа к последнему; в процессе этого движения находятся условно-оптимальные управления. Безусловная оптимизация осуществляется в обратном направлении – от последнего этапа к первому; при этом из найденных ранее поэтапных условно-оптимальных управлений формируется оптимальное управление всем данным процессом. 67 Контрольные вопросы по разделу «Динамическое программирование». 1. Динамическое программирование (ДП). Определение и теоретическая основа метода ДП. 2. Общая схема многошаговых процессов принятия решений. Управляемые системы. 3. Принцип оптимальности Беллмана. Рекуррентные соотношения Беллмана. 4. Основные требования к структуре решаемой задачи, необходимые для применения метода динамического программирования (ДП). 5. Условная и безусловная оптимизация в задачах ДП. 6. Рекуррентные соотношения задачи об оптимальной стратегии обновления оборудования. 7. Рекуррентные соотношения задачи оптимального распределения ресурсов. 8. Рекуррентные соотношения задачи минимизации затрат на строительство и эксплуатацию предприятий. 9. Рекуррентные соотношения задачи о загрузке транспортного средства. 10. Рекуррентные соотношения задачи выбора оптимального маршрута. 5. СЕТЕВЫЕ МОДЕЛИ Основные понятия Под сетевой моделью понимается план выполнения некоторого комплекса работ. Принято этот план изображать графически таким образом, чтобы главными элементами сетевого графика являлись события и работа. Как оказалось, такое представление сетевой модели – наиболее удобный и информативный способ описания сложных проектов. Сложными проектами могут быть, например, строительство и реконструкция какихлибо объектов; выполнение научно-исследовательских и конструкторских работ; подготовка производства к выпуску продукции; перевооружение армии; развертывание системы медицинских или профилактических мероприятий и т.д. Характерная особенность таких проектов заключается в том, что они состоят из ряда отдельных, элементарных работ. Эти работы зависят друг друга так, что выполнение некоторых работ не может быть начато раньше, чем завершены некоторые другие. Например, укладка фундамента не может быть начата раньше, чем будут доставлены необходимые материалы; 68 эти материалы не могут быть доставлены раньше, чем будут построены подъездные пути; любой этап строительства не может быть начат без составления соответствующей технической документации и т.д. Выделяют три основных этапа сетевого планирования и управления: а) структурное, б) календарное, в) оперативное управление. Структурное планирование начинается с разбиения проекта на четко определенные операции, для которых определяется продолжительность. Затем строится сетевой график, который представляет взаимосвязи работ проекта. Это позволяет детально анализировать все работы и вносить улучшения в структуру проекта еще до начала его реализации. Календарное планирование предусматривает построение календарного графика, в котором заложены моменты начала и окончания каждой работы. Это позволяет, в частности, выявлять критические операции, которым необходимо уделять особое внимание, чтобы закончить проект в срок. Во время календарного планирования определяются временные характеристики всех работ (суммируются) для проведения в дальнейшем оптимизации сетевой модели. Это позволит улучшить эффективность использования какого-либо ресурса. В ходе оперативного управления используются сетевой и календарный графики для составления периодических отчетов о ходе выполнения проекта. Теперь рассмотрим основные понятия сетевых моделей. Работа – это некоторый процесс, приводящий к достижению определенного результата, требующий затрат каких-либо ресурсов и имеющий протяженность во времени. В качестве таких работ понимаются, например, разработка чертежа, изготовление детали, заливка фундамента бетоном, изучение рынка сбыта и т.д. По количеству затрачиваемого времени работа может быть: действительной, т.е. требующей затрат времени; фиктивной, т.е. не требующей временных затрат. Например: передача измененных чертежей от конструкторов к технологам; сдача отчета и т.д. Событие – это момент времени, когда завершаются одни работы и начинаются другие. Например, фундамент залит бетоном, комплектующие 69 поставлены, отчеты сданы и т.д. Событие представляет собой результат проведенных работ. На этапе планирования взаимосвязь работ и событий, необходимых для достижения конечной цели проекта, изображается с помощью сетевого графика (сетевой модели). На сетевом графике работы изображаются стрелками, которые соединяют вершины (события). Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому конкретную работу обозначают символом i, j  , состоящим из номеров начального (i-го) и конечного (j-го) событий (рис. 1). начального (i-го) и конечного (j-го) событий (рис. 1). Работа i, j  i j Начальное Конечное Любое событие может событие считаться наступившим только тогда, когда засобытие кончатся все входящие в него работы. Поэтому работы, выходящие из некоторого события, не могут начаться, пока не будут завершены все работы, входящие в это событие. Начальное событие не имеет предшествующих ему событий и называется исходным. Событие, которое не имеет последующих событий и отражает конечную цель проекта, называется завершающим. При построении сетевого графика необходимо следовать следующим правилам: длина стрелки не зависит от времени выполнения работы; для действительных работ используются сплошные, а для фиктивных – пунктирные стрелки; каждая операция должна быть представлена только одной стрелкой; между одними и теми же событиями не должно быть параллельных работ; не должно быть пересечения стрелок; не должно быть стрелок, направленных справа налево; не должно быть тупиковых событий (т.е. не имеющих последующих событий), кроме завершающего; 70 не должно быть циклов. Для анализа сетевых моделей самым важным является понятие «путь». Путь – это любая последовательность работ в сетевом графике, в которой конечное событие одной работы совпадает с начальным событием следующей за ней работы. Различают следующие виды путей. Полный путь – это путь от исходного до завершающего события. Критический путь – максимальный по продолжительности (времени) полный путь. Подкитический путь – максимальный по продолжительности путь, после критического. Работы, лежащие на критическом пути, называют критическими. 5.1. Временные параметры событий Для дальнейшей работы введем следующие обозначения временных параметров событий сетевой модели: Tp(i) – ранний срок наступления события i. Это время, которое необходимо для выполнения всех работ, предшествующих данному событию i. Оно равно наибольшей из продолжительности путей, предшествующих данному событию. Tп(i) – поздний срок наступления события i. Это такое время наступления события i, превышение которого вызовет аналогичную задержку наступления завершающего события сети. Поздний срок наступления любого события i равен разности между продолжительностью критического пути и наибольшей из продолжительностей путей, следующих за событием i. R(i) – резерв времени наступления события i. Это такой промежуток времени, на который может быть отсрочено наступление события i без нарушения сроков завершения проекта в целом. Начальные и конечные события критических работ имеют нулевые резервы событий. 71 Рассчитанные численные значения временных параметров записываются прямо в вершины сетевого графика. i Tp(i) R(i) Tп(i) Расчет ранних сроков свершения событий Tp(i) ведется от исходного (И) к завершающему (З) событию. Текущую длительность работы будем обозначать буквой t с соответствующим кодом работы, например, t(i, j), t(k, j) и т.д. 1. Для исходного события Tp(C)=0. 2. Для всех остальных событий i Tp(i)=max[Tp(k) + t(k, i)], где максимум берется по всем работам (k, i), входящим в событие i. Поздние сроки свершения событий Tп(i) рассчитываются от завершающего к исходному событию. 3. Для завершающего события Tп(З)= Tр(З). 4. Для всех остальных событий Tп(i) =min[Tп(j) - t(i, j)] , где минимум берется по всем работам (i, j), выходящих из события i. 5. R(i) = Tп(i) - Tp(i) . Временные параметры работ и путей Важными временными параметрами работ сетевой модели являются: Tpн(i, j) – ранний срок начала работы; Tпн(i, j) – поздний срок начала работы; Tpо(i, j) – ранний срок окончания работы; Tпо(i, j) – поздний срок окончания работы. Для критических работ Tpн(i, j) = Tпн(i, j) и Tpо(i, j) = Tпо(i, j). Rп(i, j) – полный резерв работы, показывает максимальное время, на которое может быть увеличена продолжительность работы (i, j) или отсрочено ее начало, чтобы продолжительность проходящего через нее 72 максимального пути не превысила продолжительности критического пути. Rс(i, j) – свободный резерв работы, показывает максимальное время, на которое можно увеличить продолжительность работы (i, j) или отсрочить ее начало, не меняя ранних сроков начала последующих работ. Временные параметры работ сети определяются на основе ранних и поздних сроков событий: 1) Tpн(i, j) = Tр(i); 2) Tpо(i, j) = Tр(i) + t(i, j) или Tpо(i, j) = Tрн(i, j) + t(i, j); 3) Tпо(i, j) = Tп(j); 4) Tпн(i, j) = Tп(j) - t(i, j) или Tпн(i, j) = Tпо(i, j) - t(i, j); 5) Rп(i, j) = Tп(j) - Tp(i) - t(i, j); 6) Rc(i, j) = Tр(j) - Tp(i) - t(i, j). Временные параметры работ вносятся в таблицу. Коды работ записывают в определенном порядке: сначала – все работы, выходящие из исходного, т.е. первого, события, затем – выходящие из второго события, потом – из третьего и т.д. Резервами времени, кроме работ и событий, обладают полные пути сетевой модели. Разность между продолжительность критического пути T(Lкр) и продолжительностью любого другого полного пути T(Lп) называется полным резервом времени пути Lп, т.е. R(Lп) = T(Lкр) – T(Lп). Этот резерв показывает, на сколько в сумме может быть увеличена продолжительность всех работ данного пути L, чтобы при этом не изменился общий срок окончания всех работ. Вопросы 1. Определение события, виды событий, практические примеры событий, обозначение событий на графике, временные параметры событий. 2. Определение работы, классификация работ с приведением соответствующих практических примеров, обозначение работ на графике, временные параметры работ. 3. Правила построения сетевых графиков. 4. Определение пути в сетевом графике, виды путей, важность определения критического пути. 5. Умение вычислять временные параметры событий и работ. 6. Почему при расчете раннего срока свершения события i выбирают максимальную из сумм Tp(k) + t(k, i)? 73 7. Почему при расчете позднего срока свершения события i выбирают минимальную из разностей Tп( j) - t(i, j)? 8. Какова взаимосвязь полного и свободного резервов работы? 9. Как можно найти критических путь в сетевой модели, без непосредственного суммирования длительностей работ? 5.2. Оптимизация сетевых моделей по критерию «минимум исполнителей» При оптимизации использования ресурса рабочей силы чаще всего сетевые работы стремятся организовать таким образом, чтобы: 1) количество одновременно занятых исполнителей было минимальным; 2) выровнять потребность в людских ресурсах на протяжении срока выполнения проекта. Суть оптимизации загрузки сетевых моделей по критерию «минимум исполнителей» заключается в следующем: необходимо таким образом организовать выполнения сетевых работ, чтобы количество одновременно работающих исполнителей было минимальным. Для проведения подобных видов оптимизации необходимо построить и проанализировать график привязки и график загрузки. График привязки отображает взаимосвязь выполняемых работ во времени и строится на основе данных либо о продолжительности работ (в нашем случае – Tн), либо о ранних сроках начала и окончания работ. При первом способе построения необходимо помнить, что работа i, j  может начать выполняться только после того как будут выполнены все предшествующие ей работы k, j  . По вертикальной оси графика привязки откладываются коды работ, по горизонтальной оси – длительность работ (раннее начало и раннее окончание работ). На графике загрузки по горизонтальной оси откладывается время, например в днях, по вертикальной – количество человек, занятых работой в каждый конкретный день. Для построения графика загрузки необходимо: 1) на графике привязки над каждой работой написать количество ее исполнителей; 2) подсчитать количество работающих в каждый день и отложить на графике загрузки. 74 Для удобства построения и анализа графики загрузки и привязки следует располагать один над другим. Полный и свободный резервы любой работы можно определить без специальных расчетов, анализируя только график привязки. Сдвиг работы означает, что она будет выполняться уже в другие дни, что, в свою очередь, приведет к изменению количества исполнителей, работающих одновременно (т.е. уровня ежедневной загрузки сети). Вопросы 1. Суть оптимизации загрузки сетевых моделей по критерию «минимум исполнителей». 2. График привязки: смысл, построение (умение строить его на основе кодов и длительности работ), назначение. 3. График загрузки: смысл, построение, назначение. 4. Методика оптимизации загрузки сетевой модели. 5. Различие в практическом использовании полного и свободного резерва работ при оптимизации загрузки. 6. Умение определять критические пути, свободные и полные резервы работ сети, используя только график привязки. 7. Пояснить взаимосвязь полного и свободного резервов работы с помощью графика привязки. 5.3. Оптимизация сетевых моделей по критерию «время – затраты» Целью оптимизации по критерию «время – затраты» является сокращение времени выполнения проекта в целом. Эта оптимизация имеет смысл только в том случае, когда время выполнения работ может быть уменьшено за счет задействования дополнительных ресурсов, что приводит к повышению затрат на выполнение работ (рис. 7). Для оценки величины дополнительных затрат, связанных с ускорением выполнения той или иной работы, используются либо нормативы, либо данные о выполнении аналогичных работ в прошлом. Под параметрами работ Сн(i, j) и Сп(i, j) понимаются так называемые прямые затраты, непосредственно связанные с выполнением конкретной работы. Косвенные затраты типа административно-управленческих в процессе сокращения длительности проекта во внимание не принимаются, однако их влияние учитывается при выборе окончательного календарного плана проекта. 75 Важными параметрами работы (i, j) при проведении данного вида оптимизации являются: коэффициент нарастания затрат C i, j   C Н i, j  k i, j   П , Т Н i, j   Т У i, j  который показывает затраты денежных средств, необходимые для сокращения длительности работы (i, j) на один день; запас времени для сокращения длительности работы в текущий момент времени ZT(i ,j) = tT(i, j) - Tу(i, j), где tT(i, j) – длительность работы (i, j) на текущий момент времени, максимально возможное значение запаса времени работы равно Zmax(i ,j) = Tн(i, j) - Tу(i, j). Эта ситуация имеет место, когда длительность работы (i, j) еще ни разу не сокращали, т.е. tT(i, j) = TН(i, j). Общую схему исследования по критерию можно представить следующим образом. 1. Исходя из нормальных длительностей работ Tн(i, j), определяются критические Lкр и подкритические Lп пути сетевой модели и их длительности Tкр и Tп. 2. Определяется сумма прямых затрат на выполнение всего проекта Cпр0 при нормальной продолжительности работ. 3. Рассматривается возможность сокращения продолжительности проекта, для чего анализируются параметры критических работ проекта. 76 3.1. Для сокращения выбирается критическая работа с минимальным коэффициентом нарастания затрат k(i, j), имеющая ненулевой запас времени сокращения ZT(i ,j). 3.2. Время t i, j  , на которое необходимо сжать длительность работы i, j  , определяется как t i, j   minZ ˜Т i, j , T , где T  Tкр  Tп – разность между длительностью критического и подкритического путей в сетевой модели. Необходимость учета параметра T вызвана нецелесообразностью сокращения критического пути более, чем на T единиц времени. В этом случае критический путь перестанет быть таковым, а подкритический путь наоборот станет критическим, т.е. длительность проекта в целом принципиально не может быть сокращена больше, чем на T . 4. В результате сжатия критической работы временные параметры сетевой модели изменяются, что может привести к появлению других критических и подкритических путей. Вследствие удорожания ускоренной работы общая стоимость проекта увеличивается на Cпр  k i, j t i, j  . 5. Для измененной сетевой модели определяются новые критические и подкритические пути и их длительности, после чего необходимо продолжить оптимизацию с шага 3. При наличии ограничения в денежных средствах, их исчерпание является причиной окончания оптимизации. Если не учитывать подобное ограничение, то оптимизацию можно продолжать до тех пор, пока у работ, которые могли бы быть выбраны для сокращения, не будет исчерпан запас времени сокращения. Замечание. Данная общая схема оптимизации предполагает наличие одного критического пути в сетевой модели. Вопросы 1. Суть оптимизации сетевых моделей по критерию «время – затраты». 2. Объяснить смысл исходных данных TН i, j  , TУ i, j  , С Н i, j  , С П i, j  . 3. Какими свойствами должна обладать работа, выбираемая на конкретном шаге для сокращения? 4. Экономический смысл коэффициента нарастания затрат, его единица измерения, способ расчета. 77 5. Прокомментировать графики прямых, косвенных и общих затрат для проведенной оптимизации, а также принятое решение о минимальной длительности проекта, учитывающее ограничение по затратам C0 . 6. Как определяется время сокращения проекта на конкретном шаге? 7. Как определяется сумма, на которую возрастает стоимость проекта на конкретном шаге оптимизации? 8. Как выбирается работа (работы) для сокращения при наличии нескольких критических путей в сетевой модели? 9. Что должно служить причиной прекращения оптимизации в случае, когда не существует ограничение по средствам, выделенным на проведение оптимизации? 10.Объяснить причины возможного появления вертикальных участков на графике прямых затрат и их экономический смысл. 11.Как рассчитать стоимость проекта до проведения оптимизации? 12. В чем причина возникновения ситуации, когда невозможно сократить проект на величину запаса времени сокращаемой работы Z т i , j  за один шаг и для этого требуется провести несколько шагов оптимизации (с одной и той же работой)? 6. ТЕОРИЯ ИГР Теория игр применяется при рассмотрении ситуаций, когда интересы взаимодействующих сторон не совпадают и каждая сторона решает задачу достижения наилучшего для себя результата путем выбора стратегии поведения во взаимодействии. Принятое решение каждая сторона оставляет втайне от противоположной стороны. Таким образом, непосредственное прикладное значение теории игр заключается в том, что она позволяет участнику игры или конфликта (в достаточно простых ситуациях и при разумных ограничениях) выбирать собственную стратегию, гарантированно приводящую к наилучшему возможному результату, обосновывать компромиссные решения, а также прогнозировать поведение противника. В более сложных ситуациях, когда формализация и точное решение задачи невозможно, полезными оказываются идеи, развитые в этой теории. Основные понятия Игра – это действительный или формальный конфликт, в котором имеются участники (игроки), каждый из которых стремится к достижению собственных целей. При этом ни один из игроков не знает, какие решения 78 примут другие игроки, но ему известны все возможные решения других игроков и количественные оценки результатов их реализации. Стратегией игрока называется совокупность правил, определяющих выбор его действия в зависимости от знаний о сложившейся ситуации. Также возможно, что решения приняты игроком заранее (в ответ на любую возможную ситуацию). В зависимости от числа игроков различают игры с двумя, тремя и более участниками. В принципе возможны также игры с бесконечным числом игроков. По количеству стратегий различают конечные и бесконечные игры. В конечных играх игроки располагают конечным числом возможных стратегий (например, в игре в орлянку игроки имеют по два возможных хода – они могут выбрать «орел» или «решку»). Соответственно в бесконечных играх игроки имеют бесконечное число возможных стратегий. Так, в ситуации «Продавец-Покупатель» каждый из игроков может назвать любую устраивающую его цену и количество продаваемого (покупаемого) товара. По свойствам функций выигрыша (зависимостей выигрыша каждого игрока от выбранных им самим и партнерами стратегий) выделяется ситуация, когда выигрыш одного из игроков равен проигрышу другого, – это модель прямого конфликта между игроками. Подобные игры называются играми с нулевой суммой, или антагонистическими играми. Матричной (биматричной) называется конечная игра с двумя участниками. Функции выигрыша в такой игре могут быть отражены двумя матрицами одинаковой размерности или одной матрицей, где на пересечении строки (соответствует возможной стратегии первого игрока) и столбца (соответствует возможной стратегии второго игрока) указываются выигрыши обоих игроков. Матричная игра с нулевой суммой, где элемент платежной матрицы (величина платежа) указывает только выигрыш первого игрока, а выигрыш второго игрока равен по абсолютной величине, но противоположен по знаку указанному числу – антагонистическая. Перед обоими игроками стоит задача получения максимального выигрыша, что в данном случае соответствует установке первого игрока (Получателя) на выбор стратегии, увеличивающей гарантированную среднюю величину платежа, и установке второго игрока (Плательщика) на выбор стратегии, 79 уменьшающей эту величину. «Гарантия» означает независимость результата игры от решений, принимаемых противником, т. е. обоснование результата игры при любом решении противника (что логически эквивалентно всем решениям из множества возможных). Элементарные выборы в конечных играх называются чистыми стратегиями. Смешанной стратегией игрока называется сочетание его чистых стратегий, применяемых в серии игр «случайным образом» (игрок сохраняет в тайне конкретные решения для каждого акта игры) с заранее определенной вероятностью1. Активными стратегиями игрока называются его чистые стратегии, используемые им с ненулевой вероятностью. Минимальный гарантированный выигрыш первого игрока называется нижней ценой игры α (максимином), он равен элементу платежной матрицы, который получается в процедуре выбора наибольшего значения из наименьших значений в каждой строке α  max ( min ( a )). ij j i Максимальный гарантированный проигрыш второго игрока называется верхней ценой игры β (минимаксом), он равен элементу платежной матрицы, которая получается в процедуре выбора наименьшего значения из наибольших значений в каждом столбце β  min ( max ( a )). ij j i Ценой игры  называется средняя (в серии игровых актов) величина платежа, привлекательная (т. е.     ) и гарантированная для обоих игроков. Решением игры называется совокупность стратегий (чистых или смешанных), позволяющая каждому игроку гарантировать результат игры (величину среднего по серии игровых актов платежа) не хуже, чем значение цены игры . Отсюда, в силу способности каждого игрока препятствовать отклонению средней величины платежа от равновесного значения, Величина, равная отношению количества случаев использования конкретной стратегии к общему количеству актов взаимодействия (т. е. частость применения стратегий) в теории игр традиционно называется «вероятностью», хотя такие события не являются случайными для игрока, принимающего это решение. Вероятность (в классическом смысле) использования каким-либо игроком его отдельной чистой стратегии численно совпадает с оптимальной частостью использования этой стратегии при допущении о разумности и экономической заинтересованности игрока. 1 80 Пример Для данной матрицы:  упростить матрицу, исключая строки, соответствующие заведомо невыгодным стратегиям активного игрока; 24 % 6 -4 5 3 7 11 % 3 -5 8 -3 38 % -4 2 1 1 3 ? 6 -5 -5 4  восстановить пропущенную вероятность одной из гипотез о «поведении природы» и выявить оптимальную стратегию активного игрока по математическому ожиданию прибыли;  выявить оптимальные стратегии активного игрока, применяя оптимистический и пессимистический (Вальде) критерии, критерии Гурвица (при γ= 0,3), Сэвиджа. Решение 1. Первый игрок имеет пять стратегий, а второй, «природа», характеризуется четырьмя возможными гипотезами. Известны вероятности реализаций первых трех гипотез. Введем обозначения стратегий активного игрока – «получателя выгоды» и «природы» А1 А2 А3 А4 А5 П1 6 -4 5 3 7 П2 3 -5 8 -3 П3 -4 2 1 1 3 П4 6 -5 -5 4 2. Сравним строки данной платежной матрицы для выявления заведомо невыгодных игроку стратегий А1 и А2 А1 и А3 А1 и А4 А1 и А5 А2 и А3 А2 и А4 А2 и А5 А3 и А4 А3 и А5 А4 и А5 П1 6 ≥ -4 6≥5 6≥3 6≤7 -4 ≤ 5 -4≤ 3 -4 ≤ 7 5≥3 5≤7 — П2 3 ≥ -5 3≤8 3≥0 3 ≥ -3 -5 ≤ 8 -5 ≤ 0 -5 ≤ -3 8≥0 8 ≥ -3 — 81 П3 -4 ≤ 2 -4 ≤ 1 -4 ≤ 1 -4 ≤ 3 2≥1 2≥1 2≤3 1=1 1≤3 — П4 6 ≥ -5 6≥0 6 ≥ -5 6≥4 -5 ≤ 0 -5 = -5 -5≤4 0≥-5 0≤4 — Вывод: в выделенных строках знаки неравенств – одинаковые, что указывает на невыгодность стратегий активного игрока А2 и А4 относительно стратегий А5 и А3 соответственно. Дальнейшее сравнение со стратегией А4 не проводилось. Платежную матрицу можно упростить, удалив из нее строки, соответствующие выявленным невыгодным стратегиям (они выделены в таблице). А1 А2 А3 А4 А5 П1 6 -4 5 3 7 П2 3 -5 8 -3 П3 -4 2 1 1 3 П4 6 -5 -5 4 П1 6 5 7 А1 А3 А5 ~ П2 3 8 -3 П3 -4 1 3 П4 6 4 2. Восстановим вероятность возможного варианта П4 «поведения» природы, исходя из того, что события П1, П2, П3 и П4 образуют полную группу P ( П 1 )  P ( П 2 )  P ( П 3 )  P ( П 4 )  1 , P ( П 4 )  1  P ( П 1 )  P ( П 2 )  P ( П 3 )  , 27 . Рассчитаем математическое ожидание дискретной случайной величины – получаемой игроком выгоды, при возможном использовании каждой его стратегии П1 П2 П3 П4 Pj 0,24 0,11 0,38 0,27 А1 6 3 -4 6 1,87 А3 5 8 1 2,46 А5 7 -3 3 4 3,57 Mi Расшифровка M1 = 6  0,24 + 3  0,11  4  0,38 + 6  0,27 =1,87; M3 = 5  0,24 + 8  0,11 + 1  0,38 + 0  0,27 =2,46; M5 = 7  0,24  3  0,11 + 3  0,38 + 4  0,27 =3,57. Вывод: при многократном взаимодействии оптимальной является стратегия А5, обеспечивающая приближение величины среднего «плате82 жа» к значению = 3,57. При этом иногда (в одиннадцати процентах случаев) игрок будет нести убыток. 3. Оптимистический критерий состоит в выявлении такой стратегии рационального игрока, которые позволяют получить наибольшую выгоду (при наиболее удачном стечении обстоятельств). Этой стратегии соответствует максимальный элемент в платежной матрице. Критерий используется в ситуациях невысокой ответственности за возможную ошибку. Проведем сравнение максимальных значений выгоды для каждой отдельной стратегии рационального игрока Pj А1 А3 А5 П1 П2 П3 П4 max (aij ) 0,24 6 5 7 0,11 3 8 -3 0,38 -4 1 3 0,27 6 4 6 8 7 j Вывод: максимальная выгода = 8 может быть получена при реализации стратегии А3. (Принимая во внимание известные вероятности гипотез о «поведении природы» заметим, однако, что вероятность такого события довольно низка – 11 %). 4. Пессимистический критерий (критерий Вальде) состоит в реализации такого же подхода при выборе стратегии, как при взаимодействии с рационально действующим партнером, нацеленным на минимизацию величины платежа. Соответственно оптимальной считается стратегия, реализующая «нижнюю цену» игры. Критерий применяется в случаях чрезвычайно высокой ответственности за промах, для предотвращения катастрофических убытков. Обратим внимание на минимальные значения в строках платежной матрицы А1 А3 А5 П1 П2 П3 П4 min(aij ) 6 5 7 3 8 -3 -4 1 3 6 4 -4 -3 83 j Нижняя цена игры   max (min (aij ))  max( 4; 0;  3)  0 (реаj i лизуется при использовании стратегии А3). Вывод: при реализации стратегии А3 все платежи – неотрицательные, что обеспечивает отсутствие убытков. Выбор других стратегий может привести к убыткам. 5. Критерий Гурвица является промежуточным между двумя предыдущими и опирается на заранее оцененную «меру ответственности» – величину, принимающую значения от min = 0 при отсутствии тяжких последствий (катастрофических убытков) до max = 1 при их возможности. Для каждой стратегии игрока рассчитывается вспомогательная величина i  min (aij )  (  )  max (aij )  (1  ), j j которая является основой для принятия решения о выборе стратегии. Произведем расчет величины Гi при значении = 0,3 для каждой стратегии и сделаем вывод А1 А3 А5 П1 П2 П3 П4 min(aij ) max (aij ) Гi 6 5 7 3 8 -3 -4 1 3 6 4 -4 -3 6 8 7 3 5,6 4 j j Расшифровка 1 = 4  0,3 + 6  0,7 = 3; 3 = 0  0,3 + 8  0,7 = 5,6; 5 = 3  0,7 + 7  0,3 = 4. Вывод: при данном «уровне ответственности» оптимальной является стратегия А3. Она обеспечивает наиболее привлекательные результаты при всех вариантах развития событий, с учетом диапазона возможных результатов. (Отметим, что для данной платежной матрицы такой вывод повторился бы при любом значении параметра , так как стратегия А3 отвечает одновременно и оптимистическому, и пессимистическому критериям). 84 6. Для применения критерия Сэвиджа переработаем платежную матрицу. Предположим, что реализуется одна из гипотез о «поведении» природы. Тогда потери, вызванные неправильным выбором стратегии, определяются разностью между максимальным элементом в столбце платежной матрицы и элементом выбранной стратегии rij  max (aij )  aij . i Элементы такой матрицы («матрицы рисков») показывают величину возможного «сожаления» о том, что выбор остановился на конкретной стратегии, при условии, что «поведение» природы было бы известно. Оптимальной является стратегия, уменьшающая максимальный риск2. В рассматриваемом случае получаем матрицу рисков П1 П2 П3 П4 А1 76 83 3  (-4) 66 А3 75 88 31 60 А5 77 8  (-3) 33 64 (rij ) П1 П2 П3 П4 max j = 1 5 7 7 2 2 6 6 11 2 11 Вывод: по данному критерию оптимальной является стратегия А3, допускающая максимальный риск не более 6 у. е. Заметим, с учетом известных вероятностей гипотез о «поведении» природы, что стратегия А5 содержит два нуля, то есть дважды может быть названа наилучшей по столбцу платежной матрицы, но в ней же – наибольший риск, величиной 11 ед. Ответ:  исключение доминируемых строк позволяет упростить платежную матрицу, сохранив стратегии А1, А3, А5;  вероятность гипотезы П4 – 27 %;  оптимальной по математическому ожиданию прибыли является стратегия А1; оптимальной по оптимистическому и пессимистическому (Вальде) критериям, а также по критериям Гурвица (при γ = 0,3) и Сэвиджа является стратегия А3. При многократном взаимодействии можно использовать матрицу рисков совместно с информацией о вероятности стратегий природы (критерий Байеса для матрицы рисков в игре с природой). Для каждой стратегии активного игрока рассчитывается математическое ожидание величины риска, оптимальной признается стратегия, которой соответствует наименьшее математическое ожидание этой величины. 2 85 Вопросы 1. 2. 3. 4. 5. 6. 7. Понятие игры. Определение матричной игры. Определение стратегии игрока. Виды стратегий. Понятие цены игры. Критерий Вальде. Критерий Гурвица. Критерий Севиджа. Заключение Методические советы по подготовке к сдаче экзамена(зачета) Главная задача высшего профессионального образования – подготовка квалифицированных специалистов. Для того чтобы завершить курс обучения конкретной дисциплины, проверить сложившуюся у студента систему понятий и выявить уровень полученных знаний, умений и навыков, проводят итоговую аттестацию в форме зачета (для проверки практических умений и навыков) или экзамена (оценка уровня теоретической и практической подготовки). Но экзамен это и в первую очередь активный процесс обучения и воспитания. Обучающее значение экзаменов состоит в том, что студент в период экзаменационной сессии вновь обращается к пройденному материалу, перечитывает конспект лекций или другую учебную литературу. Он не только повторяет, но и закрепляет полученные знания, а иногда и открывает что-то новое для себя. Процесс подготовки и сдачи экзамена стимулирует трудолюбие, принципиальность, ответственное отношение к делу, развивает чувство справедливости, уважения к науке, вузу, преподавателю. В этом состоит воспитательная роль экзамена. При подготовке к экзамену лучше использовать конспекты лекций, прочитанные преподавателем. В качестве дополнительного источника теоретических знаний используются учебные пособия из основного списка литературы, а также математические словари и справочники. Для выполнения практической части экзаменационного билета необходимо прорешать основные типы задач, которые были разобраны на практических занятиях или решены в контрольной или расчетно-графической работе. В 86 качестве дополнительных источников возможно использование учебных пособий, содержащих примеры задач и описание их решений. Экзаменационные билеты содержат теоретические и практические вопросы. В ходе подготовки к ответу необходимо написать основные математические положения, теоремы, формулы, если необходимо сделать чертеж, а также полностью оформить решение задач. На экзамене преподаватель может задать студенту дополнительные и уточняющие вопросы. Дополнительные вопросы задаются помимо вопросов экзаменационного билета и связаны с плохим ответом на вопросы билета. Уточняющие вопросы задаются в рамках билета и направлены на уточнение мысли студента. Можно выделить следующие критерии, которыми обычно руководствуется преподаватель на экзамене: 1) правильность ответов на вопросы (верное, четкое и достаточно глубокое изложение основного теоретического материала); 2) полнота, логическая последовательность и одновременно лаконичность ответа; 3) умение связывать теорию с практикой, анализировать условие и решать типовые задачи; 4) умение оценить и показать правильность полученных ответов; 5) грамотное комментирование, приведение примеров, изображение чертежей; 6) общая культура речи и поведения. Критерий выставления оценки на ответ на экзамене: – оценка «отлично»: ответ всесторонне и глубоко освещает теоретический вопрос, устанавливает взаимосвязь теории с практикой, показывает умения решать типовые задачи, оценивать правильность полученных результатов; – оценка «хорошо»: ответ соответствует основным предъявляемым требованиям, студент хорошо владеет материалом, однако не всегда обстоятельно проводит изложение, либо не полностью или с неточностями решаются практические задачи; 87 – оценка «удовлетворительно»: ответ не полно раскрывает поставленные вопросы, студент поверхностно владеет материалом, решение практической задачи вызывает определенные трудности; – оценка «неудовлетворительно»: дан неправильный ответ на теоретический вопрос, студент не показывает необходимые минимальные знания по предмету, а также не может решить практические задачи. Таким образом, преподаватель оценивает как знания, полученные при изучении курса математики в вузе, так и форму их изложения, понимание и умение применить эти знания на практике. 88 Список использованных источников Основная учебная литература 1. Мазалов В. В. Математическая теория игр и приложения. Москва: Лань, 2016 2. Красс М. С., Чупрынов Б. П. Математика для экономического бакалавриата: Учебник. Москва: ООО "Научно-издательский центр ИНФРА-М", 2017. Дополнительная учебная литература 1. Горлач Б. А. Теория вероятностей и математическая статистика. Москва: Лань, 2013. Методические материалы 1. Гончарь П. С., Гончарь Л. Э., Завалищин Д. С. Теория игр: учебное пособие для студентов, бакалавров и магистрантов экономических специальностей. Екатеринбург: УрГУПС, 2011. 2. Гончарь П. С., Гончарь Л. Э., Завалищин Д. С. Задания по теории игр с примерами решения: учебно-методическое пособие для студентов экономических специальностей и направлений подготовки. Екатеринбург: УрГУПС, 2012 3. Гончарь П. С., Гончарь Л. Э., Белослудцев О. А. Сетевые модели в управлении проектами: учебное пособие для студентов экономических и управленческих направлений подготовки бакалавров: 080100.62 - "Экономика", 080200.62 - "Менеджмент", 080400.62 "Управление персоналом", 100700.62 - "Торговое дело" всех форм обучения. Екатеринбург: УрГУПС, 2014. 4. Завьялова Т. В., Пирогова И. Н., Филиппова Е. Г. Методы принятия управленческих решений: учебное пособие. Екатеринбург: УрГУПС, 2014. 5. Гниломедов П. И., Пирогова И. Н., Скачков П. П. Линейное программирование: методические указания. Екатеринбург: УрГУПС, 2007. 6. Завьялова Т. В., Пирогова И. Н., Филиппова Е. Г. Методы принятия управленческих решений: методические указания к решению задач для студентов направления подготовки 38.03.02 - "Менеджмент" и 38.03.01 - "Экономика". Екатеринбург: УрГУПС, 2016. 89 Учебное издание И.Н. Пирогова Е.Г. Филиппова КРАТКИЙ КУРС ЛЕКЦИЙ ПО ДИСЦИПЛИНЕ Методы принятия управленческих решений Методическое пособие для обучающихся по ОП ВО направления 38.03.02 «Менеджмент» всех форм обучения Редактор _________________ Подписано в печать __________ Формат 60х84/16 Усл. печ. л. ___ Тираж __ экз. Заказ ___ УрГУПС 620034, Екатеринбург, Колмогорова, 66 90