Интеллектуальные развлечения. Интересные иллюзии, логические игры и загадки.

ГОУ ВПО

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИННОВАЦИОННЫХ ТЕХНОЛОГИЙ И ПРЕДПРИНИМАТЕЛСТВА
ПЕНЗЕНСКИЙ ФИЛИАЛ

Ю.Ю. ГОРЮНОВ, Т.Ю. ГОРЮНОВА, Д.В. Дружинин

Теория и методы принятия решений

Учебное пособие

ПЕНЗА 2010

Теория и методы принятия решений (ТиМПР) – это наука, которая математическими методами обосновывает выбор одного из нескольких решений задачи (проблемы). Следует подчеркнуть, что окончательное решение принимает лицо ответственное за принятие решений, причём его выбор не всегда совпадает с рекомендуемым.
Некоторые разделы ТиМПР:
математическое программирование (линейное программирование, нелинейное программирование, …);
динамическое программирование;
сетевое планирование;
потоки в сетях;
принятие решений в условиях неопределённости (теория игр).
Для применения ТиМПР необходимо:
сформулировать задачу (проблему);
создать математическую модель (формализовать задачу в математической форме);
решить математическую модель, используя соответствующий раздел ТиМПР;
сформулировать предложения для принятия решения.
1. Математическое программирование
1.1. Линейное программирование
Задача. Предприятие располагает тремя видами сырья, из которого изготавливает два вида продукции. Количество сырья, необходимого для производства каждого вида продукции, и доход от продажи единицы каждого вида приведены в следующей таблице:
СырьёЗапасыРасход сырья на изделиеIIII2134II3023III1612Доход от продажи32Требуется составить план выпуска продукции, при котором доход от продажи был бы максимальным.
Формализация (создание математической модели). Обозначим через x1 количество изготовленных изделий вида I, а через x2 – вида II. Тогда, учитывая имеющиеся запасы сырья, получим систему неравенств:
EMBED Equation.DSMT4
 (1)
а доход от продажи составит EMBED Equation.DSMT4

Таким образом, для определения максимального дохода от продажи изделий необходимо найти максимальное значение функции EMBED Equation.DSMT4
 при условии выполнения системы неравенств (1) – это и есть математическая модель поставленной задачи.
Полученная математическая модель состоит из системы ограничений в виде системы линейных неравенств (1) и линейной целевой функции EMBED Equation.DSMT4
, для которой требуется найти максимальное значение.
Задачи, в которых требуется найти максимальное (или минимальное) значение линейной целевой функции, при условии выполнения системы ограничений в виде системы линейных уравнений и/или неравенств, относятся к задачам линейного программирования.
Упражнения
Составьте математическую модель задачи и обоснованно ответьте на вопрос: относится ли она к задачам линейного программирования?
1. Для изготовления трёх видов изделий используется четыре вида оборудования. Затраты времени на обработку одного изделия на каждом виде оборудования, общий фонд рабочего времени оборудования и прибыль от продажи единицы изделия приведены в таблице:
Тип оборудованияЗатраты времени на обработку
одного изделияОбщий фонд рабочего
времени оборудованияIIIIIII245120II186280III745240IV467360Прибыль:101412Требуется определить, сколько изделий и какого вида следует изготовить, чтобы получить максимальную прибыль от их продажи.
2. Молочный завод производит молоко, кефир и сметану. На производство 1 т молока, кефира и сметаны требуется соответственно 1010, 1010 и 9450 кг молока. Затраты рабочего времени на разлив 1 т молока, сметаны и кефира составляют соответственно 0,18, 0,19 и 3,25 часов. Общий объём используемого молока заводом в сутки не превышает 136000 кг. Оборудование, используемое для разлива молока и кефира, может работать в сутки не более 21,4 часа, а сметаны – не более 16,25 часа. Прибыль от реализации 1 т молока, кефира и сметаны соответственно равна 3000, 2200 и 1360 рублей. Завод должен производить не менее 100 т молока.
Определить план выпуска заводом молочной продукции, который обеспечивает заводу максимальную ежедневную прибыль.
1.2. Решение задач линейного программирования в Microsoft Exce
Для решения задач линейного программирования в Exce необходимо выполнить следующие действия:
открыть приложение Exce;
Сервис – Надстройки – установить флажок "Поиск решения";
выделить ячейки для переменных, которые участвуют в системе ограничений и целевой функции;
выделить ячейки и вставить в них формулы, соответствующие левым частям системы ограничений;
выделить ячейки и заполнить их числами из правых частей системы ограничений;
Сервис – Поиск решения;
заполнить поля окна "Поиск решения":

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

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


Добавить


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


Добавить;
Ок;
Параметры;
в появившемся окне установить указанные ниже флажки:


Ок;
Выполнить.
Результат вычислений появится в ячейке, которая выделена под значение целевой функции.
Пример. Найти в Microsoft Exce максимальное значение функции F = 4000x1+3000x2 при системе ограничений:
EMBED Equation.DSMT4

Решение. Следуя сказанному выше, заполняем ячейки:


После щелчка по кнопке "Выполнить" получаем результат:


Из полученного результата следует, что максимальное значение целевой функции равно 10000 и достигается при x1 = 1, x2 = 2.
Примечание. Для того, чтобы на листе Microsoft Exce отражались формулы (первый рисунок), а не их числовые значения (второй рисунок) необходимо установить флажок "формулы": Сервис – Параметры – Вид – установить (сбросить) флажок "формулы".
Лабораторная работа № 1
Задание. По условию задачи составить математическую модель и решить её в Microsoft Exce.
1. Ежедневное пищевое довольствие бойца спецназа должно содержать не менее 60 единиц вещества А, не менее 50 единиц вещества Б и не менее 12 единиц вещества В. Указанные питательные вещества
содержаться в трёх видах продуктов. Содержание единиц питательных веществ в 1 кг каждого продукта и цена 1 кг каждого продукта приведены в
следующей таблице:
Питательные
веществаКоличество единиц питательных веществ в 1 кг
продуктаIIIIIIА134Б242В143Цена 1 кг (руб.)90120100Составить дневной рацион бойца, обеспечивающий получение им необходимого количества единиц питательных веществ при минимальной цене на его производства.
2. Фабрика производит три вида противопожарной пены, используя три вида сырья. Нормы расхода сырья каждого вида на производство 1 т пены данного вида, общее количество сырья каждого вида, которое может быть использовано фабрикой, и прибыль от продажи 1 т пены данного вида приведены в следующей таблице:
Вид сырьяНормы расхода сырья (т)
на 1 т пеныОбщее количество
сырья (т)IIIIIII0,80,50,6800II0,40,40,3600III0,10,1120Прибыль от продажи
1 т (руб.)108001120012600Найти план производства пены заводом, обеспечивающий максимальную прибыль от её продажи.
3. В трёх пунктах находится однородный груз в количествах, соответственно равных 420, 380 и 400 т. Этот груз необходимо развести в три пункта назначения, в количествах, соответственно равных 260, 520 и 420 т. Тарифы перевозок 1 т груза из каждого пункта отправления в каждый пункт назначения задаются следующей таблицей:
EMBED Equation.DSMT4
.
Найти план перевозок, обеспечивающий вывоз всего имеющегося груза и завоз его в полном объёме в пункты назначения при минимальных транспортных расходах.
1.3. Геометрическое решение задач линейного программирования
Если система ограничений и целевая функция задачи линейного программирования содержат две переменные, то эту задачу можно решить геометрически.
Геометрическое решение задачи линейного программирования состоит в следующих действиях:
заменить в каждом ограничении знак неравенства на знак равно;
в прямоугольной системе построить соответствующие прямые,
выделить область точек на плоскости, координаты которых удовлетворяют системе ограничений (ограничению со знаком "(" удовлетворяют точки, находящиеся выше прямой, а знаку "(" – ниже прямой);
в целевой функции отбросить свободный член и построить соответствующую прямую;
при поиске максимума последнюю прямую параллельно перемещаем вверх, а минимума – вниз;
координаты точки области, которую прямая пересечёт последней, будут давать максимум (минимум) целевой функции, если эта точка существует.
Пример. Решить задачу линейного программирования:
f = x1 + 2x2 + 3 ( max
EMBED Equation.DSMT4

Решение.
1. Заменим в ограничениях знаки "(" на знак равно, получим уравнения двух прямых:
EMBED Equation.DSMT4

Построим эти прямые в прямоугольной системе координат:


2. Выделим область точек на плоскости, координаты которых удовлетворяют системе ограничений (на рисунке эта область 0ABC закрашена):
первому ограничению удовлетворяют точки на плоскости, которые лежат ниже прямой L1, второму ограничению – ниже прямой L2, третьему – точки, находящиеся правее оси Ox2, четвёртому – выше оси Ox1
3. Отбросим свободный член в целевой функции, получим функцию y = x1 + 2x2, построим график этой функции (прямую L3).
4. Перемещая прямую L3 параллельно вверх, находим, что последней точкой области 0ABC, которую она пересечёт, будет точка B.
5. Для нахождения координат точки В решаем систему уравнений:
EMBED Equation.DSMT4
 решение системы: x1 = 3, x2 = 4.
Вывод: максимальное значение целевой функции f равно 3 + 2*4 + 3 = 14 и достигается при x1 = 3, x2 =4.
Примечание.
Упражнения. Решить геометрически задачу линейного программирования, результат проверить в Microsoft Exce.
1. EMBED Equation.DSMT4
 2. EMBED Equation.DSMT4

3. EMBED Equation.DSMT4
 4. EMBED Equation.DSMT4

1.4. Симплекс-метод решения задач линейного программирования
Решение задач линейного программирования симплекс-методом осуществляется по следующему алгоритму.
1. Если требуется найти максимум целевой функции f,
то найти минимум целевой функции –f.
2. Найти любое опорное решение задачи линейного программирования.
3. Если опорное решение существует,
то
найти оптимальное (min) опорное решение;
4. Если требовалось найти максимум целевой функции,
то
умножить на -1 найденный минимум.
1.4.1. Поиск опорного решения задачи линейного программирования
1. Преобразовать систему ограничений к стандартному виду:
EMBED Equation.DSMT4
 (1)
Примечание. Переменные слева от равенств называются базисными, а в круглых скобках – свободные.
2. Если в системе (1) все (i ( 0,
то
приравнять к нулю все свободные переменные и этим получить опорное решение.
3. Если в системе (1) найдётся (i < 0,
то
найти и поменять местами свободную переменную xk и базисную переменную xn (то есть свободную переменную xk ввести в состав базисных, а базисную переменную xn – в состав свободных).
4. Если обмен произвести удалось,
то
продолжить с п. 2,
иначе
опорного решения не существует.
Пример. Найти опорное решение следующей задачи линейного программирования
EMBED Equation.DSMT4
 (2)
Решение.
1. Приводим систему ограничений к стандартному виду:
а) получаем систему линейных уравнений по правилу:
если в системе ограничений есть неравенства, то в левые части неравенств со знаком "(" следует добавить новые переменные , а из левых части неравенств "(" – вычесть новые переменные:
в системе ограничений (2) есть неравенства и все со знаком "(", поэтому, добавляем к левым частям неравенств новые переменные:
EMBED Equation.DSMT4
 (3)
б) Приводим систему линейных уравнений (3) к ступенчатому виду:
записываем расширенную матрицу системы из коэффициентов при неизвестных и свободных членов:
EMBED Equation.DSMT4
 ;
умножаем вторую строку на -1 и меняем местами первую и вторые строки:
EMBED Equation.DSMT4
 ;
умножаем первую строку на 5 и складываем со второй, умножаем первую строку на 3 и складываем с третьей и получаем ступенчатый вид матрицы:
EMBED Equation.DSMT4
.
в) Приводим систему линейных уравнений к приведённому ступенчатому виду:
первую строку умножаем на -1, третью строку делим на -3:
EMBED Equation.DSMT4
 ;
умножаем третью строку на -3 и складываем со второй, складываем третью и первую строки и получаем приведённый ступенчатый вид матрицы:
EMBED Equation.DSMT4
 или EMBED Equation.DSMT4

или
EMBED Equation.DSMT4

приводим систему к стандартному виду:
EMBED Equation.DSMT4
 (4)
Базисные переменные: x1, x2 и x3, свободные переменные: x4, y1, y2 и y3.
2. В системе (4) есть не отрицательные свободные члены, поэтому ищем для обмена свободную и базисную переменные:
взять любое уравнение с отрицательным свободным членом,
в системе (4) берём первое уравнение;
если во взятом уравнении нет отрицательных коэффициентов при свободных переменных, то опорного решения не существует,
в первом уравнении два отрицательных коэффициента при x4 и y3;
взять любую свободную переменную с отрицательным коэффициентом и выделить столбец, содержащий взятую переменную,
возьмём переменную x4 и выделим столбец с x4;
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
)EMBED Equation.DSMT4
EMBED Equation.DSMT4
9-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
)EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
)в выделенном столбце найти наименьшее отношение свободных членов к коэффициентам при свободных переменных, знаки которых совпадают со знаками свободных членов,
в столбце с x4 два коэффициента в первой и второй строках, знаки которых совпадают со знаками свободных членов, находим минимальное отношение:
EMBED Equation.DSMT4

взять базисную переменную, которая находится в строке с минимальным отношением,
минимальное отношение находится в первой строке, поэтому берём базисную переменную x1:
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
)EMBED Equation.DSMT4
EMBED Equation.DSMT4
9-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
)EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
)(выделенные столбец и строка)
обменять местами выбранные свободную и базисную переменные, для этого:
выразить в выбранной строке свободную переменную через все оставшиеся и подставить полученное выражение во все оставшиеся уравнения
в нашем случае меняем местами переменные x4 и x1:
в первой строке выражаем x4 через оставшиеся переменные:
EMBED Equation.DSMT4

подставляем выражение для x4 во второе и третье уравнения:
EMBED Equation.DSMT4

и получаем новый стандартный вид системы:
EMBED Equation.DSMT4
 (5)
В этой системе все свободные члены не отрицательные, поэтому, приравнивая к нулю все свободные переменные, получим опорное решение:
EMBED Equation.DSMT4

1.4.2. Поиск оптимального решения
Если опорное решение найдено, то для отыскания оптимального опорного решения (минимального) необходимо:
представить целевую функцию EMBED Equation.DSMT4
 в виде EMBED Equation.DSMT4
 где все переменные x1, x2, … являются свободными,
из (5) получаем
EMBED Equation.DSMT4
 (6)
если все коэффициенты EMBED Equation.DSMT4
 являются не положительными, то EMBED Equation.DSMT4

в нашем случае есть положительный коэффициент;
если среди коэффициентов EMBED Equation.DSMT4
 есть положительный, то в последней системе стандартного вида выделить столбец, содержащий свободную переменную с положительным коэффициентом в целевой функции,
в целевой функции (6) положительный коэффициент только у свободной переменной y3, поэтому в системе (6) выделяем столбец с y3:
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
)EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
)EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
)если в выделенном столбце нет положительных коэффициентов у свободных переменных,
то
целевая функция минимума не имеет,
в выделенном столбце есть положительные коэффициенты;
в выделенном столбце найти положительный коэффициент, для которого отношение свободного члена (в той же строке) к этому коэффициенту является наименьшим для всех положительных коэффициентов выделенного столбца,
в выделенном столбце только один положительный коэффициент, поэтому выделяем ту строку, в которой он находится, то есть первую строку:
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
)EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
)EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
-(EMBED Equation.DSMT4
EMBED Equation.DSMT4
EMBED Equation.DSMT4
)свободную переменную в выделенном столбце ввести в состав базисных, а базисную переменную в выделенной строке ввести в состав базисных,
свободную переменную y3 вводим в состав базисных, а базисную x4 – в состав свободных (выразить переменную y3 через все оставшиеся переменные в выделенной строке):
EMBED Equation.DSMT4

значение новой базисной переменной подставить во все оставшиеся уравнения и целевую функцию:
EMBED Equation.DSMT4

продолжить с п. 2).
В целевой функции все коэффициенты являются отрицательными, поэтому EMBED Equation.DSMT4
 и достигается при (приравниваем к нулю свободные переменные) EMBED Equation.DSMT4

Ответ. Минимум целевой функции равен -10 и достигается при EMBED Equation.DSMT4

Лабораторная работа № 2
Задание. Решить задачу линейного программирования симплекс методом и в приложение Microsoft Exce.
1. EMBED Equation.DSMT4
 2. EMBED Equation.DSMT4

3. EMBED Equation.DSMT4
 4. EMBED Equation.DSMT4

5. EMBED Equation.DSMT4
 6. EMBED Equation.DSMT4

7. EMBED Equation.DSMT4
 8. EMBED Equation.DSMT4

9. EMBED Equation.DSMT4
 10. EMBED Equation.DSMT4

11. EMBED Equation.DSMT4
 12. EMBED Equation.DSMT4

13. EMBED Equation.DSMT4

14. EMBED Equation.DSMT4

15. EMBED Equation.DSMT4

1.5. Нелинейное программирование
Задача называется задачей нелинейного программирования, если её математическая модель имеет вид
EMBED Equation.DSMT4

в которой среди EMBED Equation.DSMT4
 или EMBED Equation.DSMT4
 есть нелинейные функции.
В отличие от задач линейного программирования не существует единого метода для решения задач нелинейного программирования.
Решение задач нелинейного программирования в Microsoft Exce
Задачи нелинейного программирования в Microsoft Exce решаются так же как и задачи линейного программирования (см. 1.2), с той лишь разницей, что в окне "Параметры поиска решения" необходимо сбросить флаги "Линейная модель" и, если это необходимо, "Неотрицательные значения".
Пример. Решить в Microsoft Exce следующую задачу нелинейного программирования:
найти EMBED Equation.DSMT4
 при условии EMBED Equation.DSMT4

В данной модели система ограничений состоит из одного линейного уравнения и нелинейной целевой функции.
Решение.
1. Заполняем ячейки на рабочем листе необходимыми переменными, целевой функцией и ограничениями:


2. В окне "Параметры поиска решения" сбрасываем флаги "Линейная модель" (так как решаемая задача есть задача нелинейного программирования)" и "Неотрицательные значения" (в условии задачи нет ограничений на знаки переменных).
3. После нажатия кнопки "Выполнить" получаем ответ:


из которого следует, что минимальное значение целевой функции равно 17278 и достигается при x1 = 91 и x2 = 89.
Решение задач нелинейного программирования методом Лагранжа
Метод Лагранжа заключается в выполнении следующих действий.
1. Если в системе ограничений встречаются неравенства, то, вводя дополнительные переменные, преобразовать неравенства в равенства.
2. Для заданной системы ограничений и целевой функции составить функцию Лагранжа:
EMBED Equation.DSMT4
где EMBED Equation.DSMT4
 есть неопределённые коэффициенты.
3. Приравнять к нулю все частные производные первого порядка функции L, и получить систему уравнений (в общем случае нелинейных уравнений):
EMBED Equation.DSMT4

4. Решить полученную систему и, тем самым, найти все стационарные точки EMBED Equation.DSMT4
функции EMBED Equation.DSMT4
, то есть такие точки, в которых функция может иметь экстремумы (минимумы или максимумы).
5. Исследовать каждую точку на наличие в ней экстремума функции EMBED Equation.DSMT4
, применяя следующую теорему:
если функция EMBED Equation.DSMT4
 дважды дифференцируема в окрестности стационарной точки S = EMBED Equation.DSMT4
, причём все её вторые производные в этой окрестности непрерывны, то функция EMBED Equation.DSMT4
 имеет в точке S:
минимум, если все числа (1, (2, …, (n являются положительными,
максимум, если знаки чисел (1, (2, …, (n чередуются, начиная с минуса,
где
EMBED Equation.DSMT4

EMBED Equation.DSMT4

Если же числа (i не являются положительными или их знаки не чередуются, то вопрос о наличии экстремума функции в стационарной точке остаётся открытым и требует дополнительных исследований.
Для решения задач нелинейного программирования целесообразно использовать программные системы символьных вычислений, например, систему MathCad.
Пример. Решить методом Лагранжа в системе MathCad следующую задачу нелинейного программирования:
EMBED Equation.DSMT4

EMBED Equation.DSMT4

Решение.
1. Объявляем целевую функцию f и функцию Лагранжа L:


2. Находим стационарные точки:
а) объявляем все частные производные первого порядка функции L:
объявление производнойрезультатEMBED PBrush
EMBED PBrush
EMBED PBrush
EMBED PBrush
EMBED PBrush
EMBED PBrush
б) приравниваем к нулю все частные производные первого порядка функции Лагранжа L и получаем систему, которую решаем с помощью блока Given:




Таким образом, функция f имеет одну стационарную точку (91, 89).
3. Для каждой стационарной точки проверяем наличие у функции f минимума или максимума. Для этого:
а) объявляем все производные второго порядка целевой функции f:
объявление производнойрезультатEMBED PBrush
EMBED PBrush
EMBED PBrush
EMBED PBrush
EMBED PBrush
EMBED PBrush
EMBED PBrush
EMBED PBrush
б) вычисляем значения всех производных второго порядка функции f в каждой стационарной точке:


в) вычисляем значения членов последовательности




Так числа (1, (2 положительны, то функция f в точке (91, 89) имеет минимум, равный


Ответ. Функция EMBED Equation.DSMT4
 при условии EMBED Equation.DSMT4
 имеет минимум 17278, который достигается при x1 = 91, x2 = 89.
Лабораторная работа № 3
Задание. Решить задачу нелинейного программирования в приложение Microsoft Exce и методом Лагранжа в системе MathCad.
1. EMBED Equation.DSMT4
 2. EMBED Equation.DSMT4
 3. EMBED Equation.DSMT4

4. EMBED Equation.DSMT4
 5. EMBED Equation.DSMT4

6. EMBED Equation.DSMT4
 7. EMBED Equation.DSMT4

8. EMBED Equation.DSMT4
 9. EMBED Equation.DSMT4

10. EMBED Equation.DSMT4
 11. EMBED Equation.DSMT4

12. EMBED Equation.DSMT4
 13. EMBED Equation.DSMT4

14. EMBED Equation.DSMT4
 15. EMBED Equation.DSMT4

2. Динамическое программирование
Динамическое программирование представляет собой математический метод оптимизации решений при поэтапном (пошаговом) развитии ситуации, причём выбор оптимального решения зависит как от состояния ситуации на момент выбора очередного шага, так и от истории развития ситуации.
Следует подчеркнуть, что динамическое программирование применимо только для решения таких "многошаговых" задач, для которых справедливо утверждение: если за k шагов получено оптимальное решение, то выбор оптимального решения на k+1 шаге даёт оптимальное решение за все k+1 шагов.
Из сказанного вытекает, что при динамическом программировании оптимальное решение ищется "с конца", то есть от последнего к первому шагу.
Пример 1. Дана карта автомобильных дорог с нанесёнными расстояниями между населёнными пунктами
EMBED Visio.Drawing.6

требуется найти наикратчайший маршрут между начальным пунктом A и конечным пунктом L.
Решение задачи методом динамического программирования (два этапа).
1. Двигаясь от конечного пункта L к начальному пункту A, помещаем в каждую вершину графа наикратчайшее расстояние от неё до конечной вершины L и отмечаем на карте соответствующую дорогу:
1)EMBED Visio.Drawing.6

расстояние от конечного пункта до него же равна 0.2)EMBED Visio.Drawing.6
3)EMBED Visio.Drawing.6
4)EMBED Visio.Drawing.6
5)EMBED Visio.Drawing.6
Обратите внимание на то, что для нахождения наикратчайшего расстояния от очередного пункта до конечного достаточно среди всех соседних пунктов (в направлении конечного) найти такой, что бы сумма расстояний от очередного пункта до соседнего и от соседнего до конечного (она отмечается в вершине) была наименьшей.
2. Двигаясь от начального пункта A до конечного L по отмеченным дорогам,
EMBED Visio.Drawing.6

находим наикратчайший маршрут ADFKL, длина которого равна 10.
Пример 2. Для производства некоторой продукции предприятие закупило новое оборудование. Зависимости производительности оборудования и затрат на его содержание и ремонт приведены в таблице:
Время эксплуатации
оборудования (лет)012345Годовой выпуск продукции
(тыс. руб)807565606055Затраты на содержание и
ремонт оборудования (тыс. руб)202530354555Таблица 1.
Зная, что затраты на покупку нового оборудования составляют 40 тыс. рублей, а заменяемое оборудование списывается, составить план замены оборудования в течение 5 лет, при котором общая прибыль за данный период времени максимальна.
Решение. Вычитая из стоимости готовой продукции затраты на содержание и ремонт оборудования, получим зависимость прибыли предприятия от времени эксплуатации оборудования:
Время эксплуатации
оборудования (лет)012345Прибыль (тыс. руб)20503520150Таблица 2.
Примечание. Закупив в начале года новое оборудование, предприятие в этот год получает прибыль 80 – 40 – 20 = 20 (тыс. руб.).
В конце каждого года у предприятия есть выбор: оставить прежнее оборудование либо приобрести новое и получить прибыль согласно таблицы 2.
Отмечая вершинами графа концы финансовых лет, а весами рёбер прибыль от эксплуатации оборудования, получим:
EMBED Visio.Drawing.6

что следует понимать следующим образом:
в течение первого года (I) предприятие может получить прибыль только 20 тыс. руб.;
в течение второго года (II) предприятие может получить прибыль 50 тыс. руб., если продолжит второй год эксплуатировать прежнее оборудование, либо 20 тыс. руб., если приобретёт новое;
в течение третьего года (III) предприятие может получить прибыль 35 тыс. руб., если продолжит третий год эксплуатировать прежнее оборудование, либо 20 тыс. руб., если приобретёт новое, либо 50 тыс. руб., если второй год продолжит эксплуатировать оборудование, купленное во втором году, либо 20 тыс. руб., если в третий год купит новое оборудование.
Аналогично, понимаются веса рёбер в столбцах IV и V.
Примечание. В столбце V вместо двух рёбер из каждой вершины изображены по одной, которые соответствуют максимальным прибылям предприятия за пятый год. Например, эксплуатируя оборудование пять лет, предприятие получит прибыль 0 тыс. руб., что меньше прибыли 20 тыс. руб., если предприятие купит новое оборудование.
Двигаясь справа налево, пометим вершины максимальными прибылями предприятия за период, начиная от текущего года до пятого, а также отметим галочками соответствующие рёбра.
Таким образом, максимальная прибыль предприятия составит 175 тыс. руб.
Двигаясь справа налево по отмеченным рёбрам, определим, что максимальная прибыль будет получена, если предприятие сменит оборудование после двух лет его эксплуатации.
Лабораторная работа № 4
Задание. Методом динамического программирования решить следующие задачи.
1. Внести самостоятельно изменения в дорожную карту (изменить количество пунктов, их соединения дорогами и расстояния между пунктами) из примера 1 и найти наикратчайший маршрут от начального пункта до конечного.
2. Внести самостоятельно изменения в таблице 1 из примера 2 и найти максимальную прибыль предприятия за 4 года.
3. Имеется некоторый механизм, который за один раз может переместить груз либо на 1 м вверх, либо на 1 м вправо. Зависимость расходов перемещения груза от высоты и расстояния от исходного положения A приведена в таблице:

17
14
13
10
11B98
149
1310
1211
1012
976
128
137
128
1010
1187
108
89
89
810
10108
1110
911
810
711
9119
1210
1112
1013
914
13AНапример, если груз находится в точке A, то стоимость его перемещения на 1 м вверх составляет 11 (у.е.), а на 1 м вправо – 12 (у.е.).
Определить стратегию перемещения груза из пункта A в пункт B с наименьшими расходами.
4. Внести самостоятельно изменения в приведённую выше таблицу и найти стратегию перемещения груза из A в B с максимальными расходами.
3. Сетевое планирование
Методы сетевого планирования используются для рационального планирования сложных, комплексных работ таких как:
строительство больших промышленных объектов (заводы, ГЭС, АЭС и т.п.);
перевооружение армии или отдельных видов вооружённых сил;
развёртывание системы масштабных медицинских или профилактических мероприятий.
Характерной особенностью таких сложных работ является то, что они состоят из ряда отдельных взаимозависимых работ. Эта взаимозависимость выражается в том, что некоторые работы не могут быть начаты до тех пор, пока не будут завершены определённые другие работы. Например, нельзя возводить стены здания, если не готов фундамент.
Планирование комплекса работ производится с учётом следующих элементов:
времени, необходимого на выполнение каждой работы и всего комплекса в целом;
стоимости выполнения каждой работы и всего комплекса работ;
наличия людских, энергетических и сырьевых ресурсов.
Рациональное планирование комплекса работ требует, в частности ответов на следующие вопросы:
как распределить имеющие материальные средства и трудовые ресурсы между работами комплекса?
когда начинать и заканчивать выполнение отдельных работ?
какие препятствия могут возникнуть к своевременному завершению работ и как их устранить?
3.1. Этапы сетевого планирования
1. Создание структурно-временной таблицы:
создание списка всех работ комплекса с указанием времени их выполнения и взаимной обусловленности, то есть указание окончание каких работ требуется для начала выполнения других работ.
2. Упорядочение структурно-временной таблицы:
перенумерация всех работ таким образом, чтобы любая работа могла быть выполнена только после работ с меньшими номерами. Для этой перенумерации каждой работе присваивается ранг:
работа называется работой первого ранга, если для её начала не требуется выполнения никаких других работ;
работа называется работой ранга k, если для её начала требуется выполнение работ ранга не выше k-1.
Нумерация работ одного ранга произвольная.
3. Создание сетевого графа:
создание ориентированного графа, вершины которого помечаются завершёнными работами, а дуги – работами.
4. Создание временн?го сетевого графа:
создание сетевого графа, начала дуг которого соответствуют времени начала работ, а концы – их завершению.
5. Анализ временн?го сетевого графа:
определение минимального времени завершения всех работ;
определение критических работ, то есть работ, из времени выполнения которых складывается минимальное время выполнения комплекса всех работ;
определение резервов времени выполнения некритических работ (для того, чтобы отодвинуть время начала некритической работы, либо увеличить срок её выполнения, передав часть ресурсов на выполнение критических работ, если это возможно).
6. Оптимизация плана комплексных работ:
ответ на вопрос: можно ли привлечь и в каком объёме дополнительные ресурсы для сокращения времени выполнения критических работ?
3.2. Пример сетевого планирования
Предположим, что комплекс состоит из 10 работ и что структурно-временная таблица создана:
1. Структурно-временная таблица2. Упорядоченная структурно-временная таблицаРаботаВремя выполненияМожно начать после работыРанг
работыНовая
нумерацияРаботаВремя
выполненияМожно начать после работыa110—1b1b110—a25a1, a32b5b215—a315—1b2b319—a418a1, a2, a33b6b418—a519—1b3b55b1, b2a618—1b4b618b1, b2, b5a78a1, a4, a106b10b725b1, b5a825a1, a23b7b830b2, b3, b6a930a3, a4, a54b8b98b8a108a95b9b108b1, b6, b93. Сетевой граф.
EMBED Visio.Drawing.6

Примечание. Сплошная стрелка означает выполнение работы, а пунктирная – ожидание завершения работ, например, стрелки из вершин B1 и B5 можно прочитать так: после завершения работ b1 и b5 можно начинать работу b7.
4. Временн?й сетевой граф.
EMBED Visio.Drawing.6

5. Анализ временн?го сетевого графа.
Минимальное время выполнения комплекса: 86.
Критические работы: b2 – b5 – b6 – b8 – b9 – b10.
Резервы времени с началом выполнения некритических работ:
некритическая работазадержка с началом выполненияb1( 5 = 15 – 10,b3( 66 = 86 – 20,b4( 68 = 86 – 18,b7(61 = 86 – 25.4. Потоки в сетях
В этом разделе рассматриваются задача максимизации потока некоторого продукта по сети. Подобного рода задачи возникают при организации перекачки нефти или газа по трубопроводам, железнодорожного или автомобильного движения, передачи информации по сетям и т.д.
Приведём необходимые определения, формализующие соответствующие предметные области.
Сетью называется орграф без циклов с помеченными вершинами и дугами. Числа, которыми помечаются дуги сети, называются пропускными способностями дуг.
Примеры вершин сети: перекрёстки дорог, телефонные узлы, железнодорожные узлы, аэропорты, склады и т.д.
Примеры дуг сети: дороги, трубы, телефонные и железнодорожные линии и т.д.
Сеть, у которой существует ровно один исток и один сток, называется транспортной сетью.
Пример транспортной сети:
EMBED Visio.Drawing.6

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

Для любой транспортной сети величина потока имеет максимальное значение, которое определяется теоремой Форда – Фалкерсона, которая утверждает, что величина максимального потока в сети равна величине минимального разреза, где
разрезом транспортной сети называется такое множество дуг, удаление которых отделяет исток от стока.
минимальным разрезом транспортной сети называется разрез с минимальной пропускной способностью.
Пример. Транспортная сеть
EMBED Visio.Drawing.6

имеет два разреза EMBED Equation.DSMT4
 и EMBED Equation.DSMT4
. Пропускная способность первого разреза равна 11 (7+4), а второго – 9 (4+5), поэтому максимальный поток в этой транспортной сети равен 9 = min(11, 9). Этот максимальный поток указан в круглых скобках.
4.1. Алгоритм построения максимального потока в транспортной сети
Цепью, соединяющей исток A0 со стоком An, (или просто цепью) в транспортной сети называется последовательность дуг A0A1, …, An1 An, в которой вершина Ai является началом i-ой дуги, а вершина Ai+1 – её концом (или, наоборот, Ai является концом i-ой дуги, а вершина Ai+1 – её началом).
Например, в следующей сети с заданным в скобках потоком
EMBED Visio.Drawing.6

цепями являются последовательности AB, BC, CD и AC, CB, BD, причём в первой цепи направление дуги BC совпадает с направлением потока, а во второй цепи направление дуги CB противоположно направлению потока.
Определение. Дуга цепи называется допустимой дугой, если:
направление дуги совпадает с направлением потока и поток по этой дуге меньше её пропускной способности;
направление дуги противоположно направлению потока и поток по этой дуге больше нуля.
Цепь, соединяющая исток сети со стоком, называется увеличивающей, если все её дуги являются допустимыми.
Алгоритм построения максимального потока в сети
1. Если поток в сети не задан,
то считать поток нулевым.
2. Пока в сети есть увеличивающие цепи повторять:
взять любую увеличивающую цепь,
вычислить наименьшую разность ( между пропускными способностями дуг этой цепи и потоками по этим дугам,
потоки по дугам, направление которых совпадает с направлением потока, увеличить на (,
потоки по дугам, направление которых противоположно направлению потока, уменьшить на (,
3. Если в сети нет увеличивающих цепей,
то максимальный поток построен,
Пример 1 (Поток в сети не задан). Построить максимальный поток для заданной транспортной цепи.
Данная сеть:Сеть с нулевым потоком:EMBED Visio.Drawing.6
EMBED Visio.Drawing.6
Решение.
1. Поток в сети не задан, считаем его нулевым.
2. Пока в сети есть увеличивающие цепи, повторяем:
Увеличивающая цепь: AB, BD, DF;
направление дуг совпадает с направлением потока,
( = min(9 – 0, 6 – 0, 10 – 0) = 6.Новые потоки по дугам цепи:
AB: 0+6=6, BD: 0+6 = 6,
DF: 0+6=6:EMBED Visio.Drawing.6
EMBED Visio.Drawing.6

Увеличивающая цепь: AB, BE, EF;
направление дуг совпадает с направлением потока,
( = min(9 – 6, 3 – 0, 7 – 0) = 3.Новые потоки по дугам цепи:
AB: 6 + 3 = 9, BE: 0 + 3 = 3,
EF: 0 + 3 = 3:EMBED Visio.Drawing.6
EMBED Visio.Drawing.6

Увеличивающая цепь: AC, CE, ED, DF;
направление дуг совпадает с направлением потока,
( = min(8 – 0, 4 – 0, 4 – 0, 10 – 6) = 4.Новые потоки по дугам цепи:
AC: 0 + 4 = 4, CE: 0 + 4 = 4,
ED: 0 + 4 = 4, DF: 6 +4 = 10:EMBED Visio.Drawing.6
EMBED Visio.Drawing.6
Увеличивающих цепей в сети нет, поэтому максимальный поток построен и он равен 13 = 9 + 4 = 10 + 3.
Пример 2 (Поток в сети задан). Построить максимальный поток для заданной транспортной цепи.
Сеть с заданным потоком:EMBED Visio.Drawing.6
Решение.
1. Поток в сети задан.
2. Пока в сети есть увеличивающие цепи, повторяем:
Увеличивающая цепь: AB, BD, DE, EF;
направление дуги DE противоположно потоку, направление остальных дуг совпадает с направлением потока,
( = min(9 – 6, 6 – 3, 4 – 2, 7 – 4) = 2.Новые потоки по дугам цепи:
AB: 6 + 2 = 8, BD: 3 + 2 = 5,
DE: 2 – 2 = 0, EF: 4 + 2 = 6:EMBED Visio.Drawing.6
EMBED Visio.Drawing.6

Увеличивающая цепь: AB, BD, DF;
направление дуг совпадает с направлением потока,
( = min(9 – 8, 6 – 5, 10 – 5) = 1.Новые потоки по дугам цепи:
AB: 8 + 1 = 9, BD: 5 + 1 = 6,
DF: 5 + 1 = 6:EMBED Visio.Drawing.6
EMBED Visio.Drawing.6

Увеличивающая цепь: AC, CE, EF;
направление дуг совпадает с направлением потока,
( = min(8 – 3, 4 – 3, 7 – 6) = 1.Новые потоки по дугам цепи:
AC: 3+ 1 = 4, CE 3+ 1 = 4,
EF: 6 + 1 = 7:EMBED Visio.Drawing.6
EMBED Visio.Drawing.6
Увеличивающих цепей в сети нет, поэтому максимальный поток построен и он равен 13 = 9 + 4 = 10 + 3.
Примечание. Обратите внимание на то, что сети в примерах 1 и 2 и максимальные потоки по ним совпадают, а потоки по некоторым дугам различаются, например, в примере 1 поток по дуге DF равен 10, а в примере 2 по этой же дуге равен 6.
4.2. Построение максимального потока в сетях с неориентированными дугами
Для построения максимального в сетях с неориентированными дугами поступают следующим образом:
каждую неориентированную дугу (ребро) сети, не выходящую из источника и не входящую в сток, заменяют парой противоположно направленных дуг с той же пропускной способностью, что и заменяемое ребро;
каждую неориентированную дугу с началом в источнике заменяют на ориентированную, выходящую из источника;
каждую неориентированную дугу с концом в стоке заменяют на ориентированную, входящую в сток;
применяют алгоритм построения максимального потока в сетях, изложенный в разделе 4.1.
Пример сети с неориентированными дугами (BD и EF) и соответствующей ей сети с ориентированными дугами:
EMBED Visio.Drawing.6
 EMBED Visio.Drawing.6

Лабораторная работа № 5
Задание.
1. Самостоятельно задать пропускные способности дуг и построить максимальный поток в транспортной сети.
2. Найти минимальный разрез сети и проверить справедливость теоремы Форда – Фалкерсона.
EMBED Visio.Drawing.6
 EMBED Visio.Drawing.6

EMBED Visio.Drawing.6
 EMBED Visio.Drawing.6

EMBED Visio.Drawing.6
 EMBED Visio.Drawing.6

EMBED Visio.Drawing.6
 EMBED Visio.Drawing.6

EMBED Visio.Drawing.6
 EMBED Visio.Drawing.6

EMBED Visio.Drawing.6
 EMBED Visio.Drawing.6

EMBED Visio.Drawing.6
 EMBED Visio.Drawing.6

EMBED Visio.Drawing.6
 EMBED Visio.Drawing.6

5. Принятие решений в условиях неопределённости
Во многих сферах человеческой деятельности приходится принимать решения в ситуациях, в которых сталкиваются интересы двух или более враждующих (противоборствующих, конкурирующих, …) сторон, которые преследуют различные цели, причём результат любого действия каждой из сторон зависит от того, какое действие предпримет противник. Такие ситуации называются конфликтными.
Примеры конфликтных ситуаций:
любая ситуация в ходе военных действий;
конкурентная борьба в экономике;
судопроизводство (обвинение и защита);
спортивные соревнования.
Анализом конфликтных ситуаций занимается раздел математики под названием теория игр.
Задача теории игр заключается в выработке рекомендаций по рациональному образу действий участников конфликта.
5.1. Основные понятия теории игр
Игра – упрощённая модель конфликтной ситуации.
Игрок – сторона, участвующая в конфликте.
Парная игра – игра, в которой сталкиваются интересы двух сторон.
Игра с нулевой суммой – парная игра, в которой выигрыш одной стороны равен проигрышу другой.
Ход – выбор допустимого действия и его осуществление.
Личный ход – сознательный выбор игроком допустимого действия и его осуществление.
Случайный ход – выбор допустимого действия с помощью механизма случайного выбора (например, подбрасывания монеты) и его осуществление.
Правила игры – совокупность условий, регламентирующая:
возможные действия игроков,
объём сведений каждой стороны о поведении другой,
результат, к которому приводит каждая совокупность ходов.
Стратегия – совокупность правил, определяющая выбор варианта действий при каждом ходе игрока в зависимости от ситуации, сложившийся в игре.
Оптимальная стратегия – стратегия, которая при многократном повторении игры обеспечивает игроку максимальный средний выигрыш.
Конечная игра – у каждого игрока имеется конечное количество стратегий.
m ( n игра – конечная парная игра, в которой у одного игрока имеется m стратегий, а у второго n стратегий.
Основное предположение теории игр. Противник так же как разумен, как и мы сами, и делает всё для того, чтобы помешать нам добиться максимального среднего выигрыша.
5.2. Платёжная матрица игры
Платёжной матрицей m ( n игры с нулевой суммой (или, просто, матрицей игры) называется матрица
B AB1B2…BnA1a11a12…a1nA1a21a22…a2n……………Amam1am2…amnв которой
A1, …, Am – все стратегии игрока A,
B1, …, Bm – все стратегии игрока B,
aij – выигрыш (положительный или отрицательный) игрока A при выборе им стратегии Ai и стратегии Bj игроком B.
Пример. Игра "поиск". Игрок A прячется в одном из двух убежищ, а игрок B его ищет. Правила игры: если игрок B находит A, то A платит ему 1 рубль, в противном случае игрок B платит A 1 рубль.
Стратегии игроков:
игрок A: A1 – спрятаться в убежище № 1,
A2 – спрятаться в убежище № 2;
игрок B: B1 – искать в убежище № 1,
B2 – искать в убежище № 2;
Матрица игры "поиск":
B
AB1B2A1-11A11-1Некоторые выводы, вытекающие из игры "поиск".
Если игра проводится один раз, то говорить о преимуществе той или иной стратегии смысла нет.
Если при многократном проведении игры игрок будет придерживаться одной стратегии или чередования стратегий в определённой последовательности, то противник догадается об этом и начнёт выигрывать. Поэтому от верного проигрыша игроков может спасти только случайное чередование стратегий. Например, игрок перед своим ходом подбрасывает монету и, если выпала "решка", то игрок выбирает первую стратегию, а если "орёл", то вторую.
5.3. Нижняя и верхняя цены игры. Принцип минимакса
Дополним матрицу игры столбцом с минимальными значениями в строках и строкой с максимальными значениями в столбцах:
B
AB1B2…Bnmin в строкеA1a11a12…a1n(1A2a21a22…a2n(2……………Amam1am2…amn(mmax в столбце(1(2(n EMBED Equation.DSMT4

EMBED Equation.DSMT4
Величина
EMBED Equation.DSMT4

называется нижней ценой игры (или максиминным выигрышем, или максимином).
Стратегия игрока A, соответствующая максимину (, называется максиминной стратегией игрока A.
Если игрок A придерживается своей максиминной стратегии, то ему гарантирован выигрыш не меньше (, то есть ( – это тот гарантированный минимальный выигрыш, который может обеспечить себе игрок A, придерживаясь наиболее осторожной (перестраховочной) стратегии.
Величина
EMBED Equation.DSMT4

называется верхней ценой игры (или минимаксным выигрышем, или минимаксом).
Стратегия игрока B, соответствующая минимаксу (, называется минимаксной стратегией игрока B.
Если игрок B придерживается своей минимаксной стратегии, то ему гарантирован проигрыш не больше (.
Принцип минимакса. Если оба игрока разумны, то игрок A будет выбирать свою максиминную стратегию, а игрок B – минимаксную.
Пример. Расширенная матрица игры "поиск" имеет вид:
B
AB1B2min в строкеA1-11-1A21-1-1max в столбце11 -1
1нижняя цена игры ( = -1, верхняя цены игры ( = 1.
Таким образом, если игрок будет делать личные ходы, а его противник об этом узнает, то игрок A получит минимальный выигрыш -1, то есть он будет в проигрыше, а игрок B получит минимальный проигрыш 1, то есть он будет выигрывать.
Аналогичное утверждение справедливо и для игрока B.
Определение.
Игра называется игрой с седловой точкой, если нижняя и верхняя цена игры совпадают.
Общее значение нижней и верхней цены игры ( = ( = ( называется чистой ценой игры.
Седловой точке соответствует пара минимаксных стратегий, которые называются оптимальными, а их совокупность называется решением игры.
Примечание. Седловой точкой матрицы называется такой её элемент, который является минимальным в своей строке и максимальным в своём столбце.
Свойство решения игры: если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии (это отклонение может лишь ухудшить его положение).
Чистая цена игры в игре с седловой точкой является тем значением выигрыша, которое в игре разумных противников игрок A не может увеличить, а игрок B уменьшить.
Пример 2. Игра "защита от воздушного налёта". Сторона A обороняет от воздушного налёта два объекта, имея два орудия. Каждое орудие может поразить только тот самолёт, который находится в его зоне действия, но для этого оно должно до входа самолёта в зону следить за ним. Обстрелянная цель поражается. Сторона B атакует эти объекты двумя самолётами, которые могут быть направлены к любому объекту. Каждый самолёт может маневрировать, например, показав, что он направляется к объекту № 2, самолёт № 2 перед входом в зону действия орудия № 2, изменяет маршрут и атакует объект № 1.
EMBED Visio.Drawing.6

Целью стороны A является защита, а стороны B поражение максимального количества объектов.
Стратегии сторон:
Сторона &heip;