Исследование операций

/

Введение

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

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

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

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

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

Граничные условия показывают предельно допустимые значения искомых переменных.

Значения искомых переменных, удовлетворяющих граничным условиям и ограничениям, называют допустимым решением задачи.

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

Раздел 1. Основы моделирования

§1. Основные понятия: решение, множество возможных решений, оптимальное решение, показатель эффективности

Операцией называется всякое мероприятие (система действий), объединенное единым замыслом и направленное к достижению какой-то цели.

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

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

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

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

Параметры, совокупность которых образует решение, называются элементами решения. В качестве элементов решения могут фигурировать различные числа, векторы, функции, физические признаки и т. д. Например, если составляется план перевозок однородных грузов из пунктов отправления А1, А2, .... Am в пункты назначения В1, В2, ..., Вn, то элементами решения будут числа xij, показывающие, какое количество груза будет отправлено из i-го пункта отправления Ai в j-й пункт назначения Bj. Совокупность чисел xij образует решение.

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

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

Обозначим это множество буквой X. Запишем в виде формулы, что решение х принадлежит этому множеству: х X (читается: элемент х входит в множество X).

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

Если показатель эффективности желательно максимизировать, то будем записывать в виде W => max, а если минимизировать -- W => min.

§2. Математические модели, основные принципы построения моделей

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

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

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

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

а) с той точностью, с которой нам нужно знать решение;

б) с той информацией, которой мы располагаем или можем приобрести.

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

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

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

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

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

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

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

§3. Прямые и обратные задачи. Детерминированные задачи и задачи в условиях неопределенности

Задачи исследования операций делятся на две категории: прямые и обратные. Прямые задачи отвечают на вопрос: что будет, если в заданных условиях мы примем какое-то решение хX? В частности, чему будет равен, при данном решении х, выбранный показатель эффективности W?

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

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

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

Запишем постановку задачи оптимизации решения (обратной задачи исследования операций) в общей форме:

Пусть имеется некоторая операция О, на успех которой мы можем в какой-то мере влиять, выбирая тем или другим способом решение х. Пусть эффективность операции характеризуется одним показателем W=> max.

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

1) заданные, заранее известные факторы (условия выполнения операции), которые обозначим буквой ;

2) зависящие от нас элементы решения, образующие в своей совокупности решение х.

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

Показатель эффективности W зависит от обеих групп факторов. Запишем это в виде формулы:

W=W (,x) (3.1)

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

Будем считать, что вид зависимости (3.1) нам известен, т. е. прямая задача решена. Тогда обратная задача формулируется следующим образом.

При заданном комплексе условий найти такое решение х=х*, которое обращает показатель эффективности W в максимум.

Этот максимум обозначим:

W* = max {W (, х)}. (3.2)

Формула (3.2) читается так: W* есть максимальное значение W(,х), взятое по всем решениям, входящим в множество возможных решений X.

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

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

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

Запишем зависимость показателя эффективности W от всех трех групп факторов:

W=W(, х, ). (3.3)

Так как величина W зависит от неизвестных факторов , то даже при заданных и x она уже не может быть вычислена, т.е. остается неопределенной. Задача поиска оптимального решения тоже теряет определенность. Следовательно, при заданных условиях , с учетом неизвестных факторов , требуется найти такое решение хX, которое, по возможности, обеспечивает максимальное значение показателя эффективности W.

Наличие неопределенных факторов характерно для задачи о выборе решения в условиях неопределенности.

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

Рассмотрим пример такой задачи.

Организуется (или реорганизуется) работа промышленного предприятия. Под углом зрения какого критерия надо выбирать решение? С одной стороны, нам хотелось бы обратить в максимум валовой объем продукции V. Желательно также было бы получить максимальный чистый доход D. Что касается себестоимости S, то ее хотелось бы обратить в минимум, а производительность труда П -- в максимум.

Раздел 2. Линейное программирование

§1. Задачи линейного программирования

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

W=W(, x).

В число заданных условий входят и ограничения, налагаемые на элементы решения. Пусть решение х представляет собой совокупность n элементов решения x1, x2, ..., xn (иначе -- n-мерный вектор):

х= (x1, x2, ..., xn).

Требуется найти такие значения x1, x2, ..., xn, которые обращают величину W в максимум или в минимум (т.е. «экстремум»).

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

Для задач линейного программирования характерно что:

а) показатель эффективности (целевая функция) W линейно зависит от элементов решения x1, x2, ..., xn и

б) ограничения, налагаемые на элементы решения, имеют вид линейных равенств или неравенств относительно x1, x2, ..., xn.

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

Приведем несколько примеров задач линейного программирования.

1. Задача о пищевом рационе. Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П1, П2, П3, П4; стоимость единицы каждого продукта равна соответственно c1, c2, с3, с4. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков -- не менее b1 единиц; углеводов -- не менее b2 единиц; жиров -- не менее b3 единиц. Для продуктов П1, П2, П3, П4 содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице 4.1, где aij (i=1, 2, 3, 4; j=1, 2, 3) -- какие-то определенные числа; первый индекс указывает номер продукта, второй -- номер элемента (белки, углеводы, жиры).

Требуется составить такой пищевой рацион (т. е. назначить количества продуктов П1, П2, П3, П4, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.

Таблица 4.1

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

L = c1x1 + c2x2 + c3x3 + c4x4 (4.1)

или

4

L = ci xi (4.2)

i=1

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

a11x1 + a21x2 + a31x3 + a41x4 ? b1

a12x1 + a22x2 + a32x3 + a42x4 ? b2 (4.3)

a13x1 + a23x2 + a33x3 + a43x4 ? b3

Эти линейные неравенства представляют собой ограничения, накладывае-мые на элементы решения х1, х2, x3, x4.

Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных х1, х2, x3, x4, чтобы они удовлетворяли ограничениям -- неравенствам (3.3) и одновременно обращали в минимум линейную функцию этих переменных:

4

L = cixi min (4.4)

i=1

2. Задача о планировании производства. Предприятие производит изделия трех видов: U1, U2, U3. По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не менее b1 единиц изделия U1, не менее b2 единиц изделия U2 и не менее b3 единиц изделия U3. План может быть перевыполнен, но в определенных границах; условия спроса ограничивают количества произведенных единиц каждого типа: не более соответственно 1, 2, 3, единиц. На изготовление изделий идет какое-то сырье; всего имеется четыре вида сырья: S1, S2, S3, S4, причем запасы ограничены числами 1, 2, 3, 4 единиц каждого вида сырья. Укажем, какое количество сырья каждого вида идет на изготовление каждого вида изделий. Обозначим аij количество единиц сырья вида Si (i=l, 2, 3, 4), потребное на изготовление одной единицы изделия Uj (j = 1, 2, 3). Первый индекс у числа аij -- вид сырья, второй -- вид изделия. Значения аij сведены в таблицу 4.2.

Таблица 4.2

При реализации одно изделие U1 приносит предприятию прибыль c1, U2-- прибыль с2, U3 -- прибыль с3. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.

Запишем задачу в форме задачи линейного программирования. Элементами решения будут х1, х2, х3, -- количества единиц изделий U1, U2, U3, которые мы произведем. Обязательность выполнения планового задания запишется в виде трех ограничений-неравенств:

x1 ? b1 , x2 ? b2 , x3 ? b3 (4.5)

Отсутствие излишней продукции (затоваривания) даст нам еще три ограничения-неравенства:

x1 ? 1 , x2 ? 2 , x3 ? 3 (4.6)

Кроме того, нам должно хватить сырья. Соответственно четырем видам сырья будем иметь четыре ограничения-неравенства:

a11x1 + a21x2 + a31x3 ? 1

a12x1 + a22x2 + a32x3 ? 2 (4.7)

a13x1 + a23x2 + a33x3 ? 3

a14x1 + a24x2 + a34x3 ? 4

Прибыль, приносимая планом (х1, х2, х3), будет равна

L = c1x1 + c2x2 + c3x3 max (4.8)

3. Задача о загрузке оборудования. Ткацкая фабрика располагает двумя видами станков, из них n1 станков типа 1 и N2 станков типа 2. Станки могут производить три вида тканей: Т1, Т2, T3, но с разной производительностью. Данные aij производительности станков даны в таблице 4.3 (первый индекс -- тип станка, второй -- вид ткани).

Таблица 4.3

Каждый метр ткани вида T1 приносит фабрике доход с1, вида Т2 -- доход с2, T3 -- доход С3.

Фабрике предписан план, согласно которому она должна производить в месяц не менее b1 метров ткани Т1, b2 метров ткани Т2, b3 метров ткани T3; количество метров каждого вида ткани не должно превышать соответственно 1, 2, 3 метров. Кроме того, все без исключения станки должны быть загружены. Требуется так распределить загрузку станков производством тканей Т1, Т2, T3, чтобы суммарный месячный доход был максимален.

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

x11 x12 x13 (4.9)

x21 x22 x23

Здесь x11 -- количество станков типа 1, занятых изготовлением ткани T1, x12 -- количество станков типа 1, занятых изготовлением ткани T2, и т. д.

Запишем условия-ограничения, наложенные на элементы решения хij. Прежде всего, обеспечим выполнение плана. Это даст нам три неравенства-ограничения:

a11x11 + a21x21 ? b1

a12x12 + a22x22 ? b2 (4.10)

a13x13 + a23x23 ? b3

После этого ограничим перевыполнение плана; это даст нам еще три неравенства-ограничения:

a11x11 + a21x21 ? 1

a12x12 + a22x22 ? 2 (4.11)

a13x13 + a23x23 ? 3

Запишем ограничения, связанные с наличием оборудования и его полной загрузкой. Суммарное количество станков типа 1, занятых изготовлением всех тканей, должно быть равно N1; типа 2 -- N2. Отсюда еще два условия -- на этот раз равенства:

x11 + x12 + x13 = N1 (4.12)

x21 + x22 + x23 = N2

Запишем суммарный доход от производства всех видов тканей. Суммарное количество метров ткани T1, произведенное всеми станками, будет равно а11x11+a21x21 и принесет доход c1(a11x11+а21х21). Рассуждая аналогично, найдем суммарный доход фабрики за месяц при плане (4.9):

L = c1(a11x11+а21х21) + c2(a12x12+а22х22) + c3(a13x13+а23х23) или

3 2

L = cj aijxij (4.14)

j=1 i=1

Эта линейная функция шести аргументов стремится к максимуму:

L max

В этой задаче линейного программирования требуется найти такие неотрицательные значения переменных x11, x12, ..., x23, которые, во-первых, удовлетворяли бы ограничениям-неравенствам (4.10), (4.11), во-вторых -- ограничениям-равенствам (4.12) и, наконец, обращали бы в максимум линейную функцию этих переменных (4.13). В этой задаче линейного программирования шесть ограничений-неравенств и два ограничения-равенства.

4. Задача о снабжении сырьем. Имеются три промышленных предприятия: П1, П2, П3, требующих снабжения определенным видом сырья. Потребности в сырье каждого предприятия равны соответственно a1, а2, a3 единиц. Имеются пять сырьевых баз, расположенных от предприятий на каких-то расстояниях и связанных с ними путями сообщения с разными тарифами. Единица сырья, получаемая предприятием Пi с базы Бi обходится предприятию в сij рублей (первый индекс -- номер предприятия, второй -- номер базы, см. таблицу 4.4).

Таблица 4.4

Возможности снабжения сырьем с каждой базы ограничены ее производственной мощностью: базы Б1, Б2, Б3, Б4, Б5 могут дать не более b1, b2, b3, b4, b5 единиц сырья. Требуется составить такой план снабжения предприятий сырьем (с какой базы, куда и какое количество сырья везти), чтобы потребности предприятий были обеспечены при минимальных расходах на сырье.

Обозначим xij количество сырья, получаемое i-м предприятием с j-й базы. Всего план будет состоять из 15 элементов решения:

x11 x12 x13 x14 x15

x21 x22 x23 x24 x25 (4.15)

x31 x32 x33 x34 x35

Введем ограничения по потребностям. Они состоят в том, что каждое предприятие получит нужное ему количество сырья (ровно столько, сколько ему требуется):

x11 + x12 + x13 + x14 + x15 = a1

x21 + x22 + x23 + x24 + x25 = a2 (4.16)

x31 + x32 + x33 + x34 + x35 = a3

Далее напишем ограничения-неравенства, вытекающие из производственных мощностей баз:

x11 + x21 + x31 ? b1

x12 + x22 + x32 ? b2

x13 + x23 + x33 ? b3 (4.17)

x14 + x24 + x34 ? b4

x15 + x25 + x35 ? b5

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

3 5

L = cijxij min (4.18)

i=1 j=1

§2. Основная задача линейного программирования (ОЗЛП)

Любую задачу линейного программирования можно свести к стандартной форме, так называемой «основной задаче линейного программирования» (ОЗЛП), которая формулируется так: найти неотрицательные значения переменных x1, x2, ..., xn, которые удовлетворяли бы условиям-равенствам

a11x1 + a21x2 + … + an1xn = b1

a21x1 + a22x2 + … + a2nx2 = b2 (5.1)

…………………………………

am1x1 + am2x2 + … + amnxn = bm

и обращали бы в максимум линейную функцию этих переменных:

L = c1x1 + c2x2 + … + cnxn max (5.2)

Пусть требуется найти неотрицательные значения переменных х1, x2, x3, удовлетворяющие ограничениям-неравенствам

3x1 + 2x2 - x3 ? 4

x1 - 2x2 + 3x3 ? 10 (5.3)

и обращающие в максимум линейную функцию от этих переменных:

L = 4x1 - x2 + 2x3 max (5.4)

Приведем условия (5.3) к стандартной форме, так, чтобы знак неравенства был , а справа стоял нуль. Получим:

3x1 + 2x2 - x3 - 4 ? 0

- x1 + 2x2 - 3x3 + 10 ? 0 (5.5)

Обозначим левые части неравенств (5.5) соответственно через y1 и y2:

y1 = 3x1 + 2x2 - x3 - 4

y2 = - x1 + 2x2 - 3x3 + 10 (5.6)

Из условий (5.5) и (5.6) видно, что новые переменные y1 и y2 также должны быть неотрицательными.

Требуется найти неотрицательные значения переменных х1, x2, x3, y1, y2 такие, чтобы они удовлетворяли условиям-равенствам (5.6) и обращали в максимум линейную функцию этих переменных. Перед нами -- основная задача линейного программирования (ОЗЛП). Переход к ней от первоначальной задачи с ограничениями-неравенствами (5.3) «куплен» ценой увеличения числа переменных на два (число неравенств).

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

§3. Графический метод решения задач линейного программирования

Рассмотрим метод графического решения ЗЛП на примере задачи технического контроля.

Задача технического контроля. В отделе технического контроля (ОТК) некоторой фирмы работают контролеры разрядов 1 и 2. Норма выработки ОТК за 8 - часовой рабочий день составляет не менее 1800 изделий. Контролер разряда 1 проверяет 25 изделий в час, причем не ошибается в 98% случаев. Контролер разряда 2 проверяет 15 изделий в час; его точность составляет 95%.

Заработная плата контролера разряда 1 равна 4 руб. в час, контролер разряда 2 получает 3 руб. в час. При каждой ошибке контролера фирма несет убыток в размере 2 руб. Фирма может использовать 8 контролеров разряда 1 и 10 контролеров разряда 2.

Руководство фирмы хочет определить оптимальный состав ОТК, при котором общие затраты на контроль будут минимальны.

Разработка модели. Пусть x1 и x2 обозначают количество контролеров разрядов 1 и 2 соответственно. Число контролеров каждого разряда ограничено, т.е. имеются следующие ограничения:

x1 8 (разряд 1),

x210 (разряд 2).

Ежедневно необходимо проверять не менее 1800 изделий. Поэтому выполняется неравенство

8*25*x1+8*15*x2=200*x1+120*x2 1800,

или 5*x1+3*x245.

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

1) зарплату контролеров и

2) убытки, вызванные ошибками контролеров.

Расходы на одного контролера разряда 1 составляют

4 руб. +2*25*0,02=5 руб./ч.

Расходы на одного контролера разряда 2 равны

3 руб. +2*15*0,05=4,50 руб./ч.

Следовательно, минимизирующая целевая функция, выражающая ежедневные расходы на контроль, имеет вид

z=8*(5*x1+4,5*x2)= 40x1+36*x2min.

Можно сформулировать следующую задачу:

минимизировать z=40*x1+36*x2

при ограничениях:

x18, x210,

5*x1+3*x245,

x10, x20.

В этой задаче требуется найти значения переменных x1 и x2 , удовлетворяющие всем ограничениям и обеспечивающие минимальное значение целевой функции. В качестве первого шага решения следует определить все возможные неотрицательные значения переменных x1 и x2, которые удовлетворяют ограничениям. Например, координаты точки x1=8 и x2=10 положительны и для этой точки выполняются все ограничения. Такая точка называется допустимым решением. Множество всех допустимых решений называется допустимой областью. Решение задачи ЛП состоит в отыскании наилучшего решения в допустимой области. Лучшее допустимое решение задачи ЛП называется оптимальным. В рассматриваемом примере оптимальное решение представляет собой допустимое решение, минимизирующее целевую функцию 40*x1+36*x2. Значение целевой функции, соответствующее оптимальному решению, называется оптимальным значением задачи ЛП.

Для изображения допустимой области следует начертить графики всех ограничений. Все допустимые решения лежат в первом квадранте, поскольку значения переменных неотрицательны. В силу ограничения 5*x1+3*x245 все допустимые решения (x1, x2) задачи располагаются по одну сторону от прямой, описываемой уравнением 5*x1+3*x2=45. Нужную полуплоскость можно найти, проверив, удовлетворяет ли начало координат рассматриваемому ограничению. Прямую 5x1+3*x2=45 удобно провести, соединяя пару подходящих точек (например, x1=0, x2=15 и x1=9, x2=0).

Поскольку начало координат не удовлетворяет ограничению, нужная полуплоскость отмечена стрелкой, направленной перпендикулярно прямой. Аналогичным образом представлены ограничения x1 8 и x2 10.

На рисунке 6.1 допустимая область (АВС) заштрихована. Ясно, что в допустимой области содержится бесконечное число допустимых точек. Нужно найти допустимую точку с наименьшим значением Z.

Если заранее зафиксировать значение целевой функции Z=40*x1+36*x2, то соответствующие ему точки будут лежать на некоторой прямой. При изменении величины Z эта прямая подвергается параллельному переносу. Рассмотрим прямые, соответствующие различным значениям Z, имеющие с допустимой областью хотя бы одну общую точку. Начальное значение Z положим равным 600. При приближении прямой к началу координат значение Z уменьшается. Если прямая имеет хотя бы одну общую точку с допустимой областью АВС, ее можно смещать в направлении начала координат. Ясно, что для прямой, проходящей через угловую точку А с координатами х1=8, х2=1.6, дальнейшее движение невозможно. Точка А представляет собой наилучшую допустимую точку, соответствующую наименьшему значению Z, равному 377.6. Следовательно, х1=8, х2=1.6 - оптимальное решение и Z=377.6 - оптимальное значение рассматриваемой задачи линейного программирования.

Таким образом, при оптимальном режиме работы ОТК необходимо использовать восемь контролеров разряда 1 и 1.6 контролеров разряда 2. Дробное значение х2=1.6 соответствует использованию одного из контролеров разряда 2 в течение неполного рабочего дня. При недопустимости неполной загрузки контролеров дробное значение обычно округляют, получая приближенное оптимальное целочисленное решение х1=8, х2=2.

Рисунок 6.1 - Графическое решение задачи линейного программирования

§4. Решение задач линейного программирования симплекс-методом

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

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

Для изготовления n видов изделий И1, И2, ..., Иn необходимы ресурсы m видов: трудовые, материальные, финансовые и др. Известно необходимое количество отдельного i-ro ресурса для изготовления каждого j-ro изделия. Назовем эту величину нормой расхода. Пусть определено количество каждого вида ресурса, которым предприятие располагает в данный момент. Известна прибыль Пj, получаемая предприятием от изготовления каждого j-ro изделия. Требуется определить, какие изделия и в каком количестве должно изготавливать предприятие, чтобы обеспечить получение максимальной прибыли. Необходимая исходная информация представлена в таблице 7.1.

Таблица 7.1

Построение математической модели.

Количество изделий j-ro наименования, которое может производить предприятие, обозначим через хj. Зная количество каждого вида i-го ресурса для изготовления отдельного j-ro типа изделия - норму расхода и количество каждого i-го ресурса (таблица 1), можно записать следующую систему неравенств:

3x1 + 5x2 + 2x3 + 7x4 ? 15

4x1 + 3x2 + 3x3 + 5x4 ? 9 (7.1)

5x1 + 6x2 + 4x3 + 8x4 ? 30

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

В этом случае система равенств примет такой вид:

3x1 + 5x2 + 2x3 + 7x4 + x5 = 15

4x1 + 3x2 + 3x3 + 5x4 + x6 = 9 (7.2)

5x1 + 6x2 + 4x3 + 8x4 + x7 = 30

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

Критерий оптимизации (суммарную величину прибыли) можно тогда представить так:

Y = 40x1 + 50x2 + 30x3 + 20x4 + 0x5 + 0x6 + 0x7 (7.3)

Граничные условия будут записаны следующим образом:

xj ? 0 (j =1, 2, …, 7) (7.4)

Совокупность системы ограничений (7.2), целевой функций (7.3) и граничных условий (7.4) образует математическую модель данной задачи.

Нахождение базисного решения.

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

В данной задаче для определения базиса требуется взять m неизвестных по числу уравнений в системе (7.2), желательно наиболее редко встречающиеся в ней. В нашей совокупности уравнений (m - 3) это х5, х6, х7, которые и выражаем через оставшиеся неизвестные х1, х2, х3, х4.

Систему уравнений необходимо записать в таком виде:

х5 = 15 - (Зх1 + 5х2 + 2х3 + 7х4)

х6 = 9 - (4x1 + 3х2 + 3х3 + 5х4) (5)

х7 = 30 - (5x1 + 6х2 + 4х3 + 8x4)

Переменные, находящиеся в левой части системы уравнений, называются базисными (основными), а находящиеся справа - небазисными (не основными). Для определения значений базисных переменных х5, х6, х7 необходимо приравнять к нулю небазисные х1, х2, х3, х4 и подставить их в систему уравнений (5). Полученное таким образом решение называется базисным. Оно будет выглядеть следующим образом:

(х1, х2, х3, х4, х5, х6, х7)

(0, 0, 0, 0, 15, 9, 30).

После определения начального базиса можно переходить непосредственно к использованию алгоритма симплекс-метода.

Решение задачи симплекс-методом.

1. Заполнение исходной симплекс-таблицы.

В соответствии с полученной системой уравнений и критерием оптимизации заполняем исходную симплекс-таблицу (таблица 7.2).

Таблица 7.2

2. Проверка базисного решения на оптимальность.

Просматриваются знаки коэффициентов при небазисных переменных в целевой функции (критерий оптимизации) - последняя строка таблицы 7.2.

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

3. Проверка задачи на наличие решения.

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

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

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

5. Определение базисной переменной, которая должна быть выведена из базиса.

Для всех положительных коэффициентов при вводимой в базис переменной в системе уравнений определяется отношение свободного члена уравнения к коэффициенту при вводимой в базис переменной. Для нашей задачи это будут следующие отношения: 15/5 = 3; 9/3 = 3; 30/6 = 5.

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

6. Представление новой базисной переменной через небазисные.

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

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

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

Для этого коэффициенты в новой таблице при новой базисной переменной умножаются на такое число, чтобы после сложения с преобразуемой строкой предыдущей таблицы в столбце при новой базисной переменной в новой таблице появился ноль. Результаты сложения заносятся в новую симплекс-таблицу. Исходя из этого, для получения коэффициентов второй строки в новой таблица 7.3 умножаем коэффициенты при новой базисной переменной х2 (таблица 7.3) на число -3, складываем с соответствующими коэффициентами второй строки предыдущей симплекс-таблицы (таблица 7.2) и результаты расчета заносим во вторую строку новой таблицы (таблица 7.3).

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

Таблица 7.3

Поскольку в последней строке таблицы 7.3 в целевой функции не все коэффициенты при небазисных переменных неположительны, то решение не оптимально; следовательно, выполняется следующий итерационный цикл расчета и строится новая симплекс-таблица (таблица 7.4). Цикл расчета начинается с этапа 2 и проводится до тех пор, пока не будет найдено оптимальное решение.

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

Результаты расчета представлены в таблице 7.4.

Таблица 7.4

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

(х1, х2, х3, х4, х5, х6, х7)

(0, 3, 0, 0, 0, 0, 12).

Из полученного решения видно, что изделия ИI, И3 и И4 предприятие изготавливать не должно. Цифра в переменной x2 определяет изделие, планируемое для изготовления, следовательно, предприятие будет производить только второе изделие в количестве 3 единиц.

Оптимальное распределение ресурсов обеспечит получение максимальной прибыли Y, которая составит 150 единиц.

При этом материальные и трудовые ресурсы будут задействованы полностью, а финансовые - недоиспользованы на 12 единиц.

§5. Транспортная задача. Методы нахождения начального решения транспортной задачи

Рассмотрим одну из задач линейного программирования -- так называемую «транспортную задачу». Она ставится следующим образом: имеются m пунктов отправления (ПО) А1, A2, ..., Am, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, a2, ..., am единиц. Имеются n пунктов назначения (ПН) B1, В2,..., Вn, подавших заявки соответственно па b1, b2, ..., bn единиц груза. Сумма всех заявок равна сумме всех запасов:

m n

ai = bj ( 8.1 )

i = 1 j = 1

Известны стоимости сij перевозки единицы груза от каждого пункта отправления Аi, до каждого пункта назначения Bj; (i =1, 2,..., m; j = 1, 2,..., n). Все числа сij, образующие прямоугольную таблицу (матрицу), заданы:

с11 с12 . . . с1n

с21 с22 . . . с2n (8.2)

. . . . . . . . . . . . . . . .

сm1 сm2 . . . сmn

Коротко матрицу (8.2) будем обозначать (сij).

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

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

Поставим эту задачу как задачу линейного программирования. Обозначим xij, -- количество единиц груза, отправляемого из i-го ПО Ai, в j-й ПН Вj. Неотрицательные переменные xij тоже можно записать в виде матрицы

x11 x12 . . . x1n

x21 x22 . . . x2n (8.3)

. . . . . . . . . . . . . . . .

xm1 xm2 . . . xmn

которую мы будем коротко обозначать (xij). Совокупность чисел (xij) (8.3) мы будем называть «планом перевозок», а сами величины xij -- «перевозками». Эти неотрицательные переменные должны удовлетворять следующим условиям.

1. Суммарное количество груза, направляемого из каждого ПО во все ПН, должно быть равно запасу груза в данном пункте. Это даст нам m условий-равенств:

x11 + x12 + . . . + x1n = a1

x21 + x22 + . . . + x2n = a2 (8.4)

. . . . . . . . . . . . . . . . . . . .

xm1 + xm2 + . . . + xmn = am

2. Суммарное количество груза, доставляемого в каждый ПН из всех ПО, должно быть равно заявке, поданной данным пунктом. Это даст нам n условий-равенств:

x11 + x21 + . . . + xm1 = b1

x12 + x22 + . . . + xm2 = b2 (8.5)

. . . . . . . . . . . . . . . . . . . .

x1n + x2n + . . . + xmn = bn

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

m n

Y = Ci,j Xi,j min (8.6)

i = 1 j = 1

где знак двойной суммы означает, что суммирование производится по всем комбинациям индексов i и j, т. е. по всем парам ПО -- ПН.

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

Условия-равенства (8.4), (8.5) не являются линейно независимыми, так как их правые части связаны условием (8.1). Число линейно независимых среди уравнений (8.4), (8.5) равно не m + n (числу уравнений), а m + n -- 1. Общее число переменных xij, в нашей задаче равно m * n; как бы ни разрешать уравнения (8.4), (8.5), число базисных переменных будет равно m + n -- 1, а число свободных переменных

k = mn -- (m + n-- 1) = (m -- 1) (n -- 1).

Для оптимального плана по крайней мере (m -- 1) (n -- 1) перевозок должны быть равны нулю (из соответствующих ПО в соответствующие ПН ничего не перевозится).

Будем называть любой план перевозок допустимым, если он удовлетворяет условиям (8.4), (8.5) (все заявки удовлетворены, все запасы исчерпаны). Допустимый план будем называть опорным, если в нем отличны от нуля не более m + n -- 1 базисных перевозок, а остальные перевозки равны нулю. План (xij) будем называть оптимальным, если он, среди всех допустимых планов, приводит к минимальной суммарной стоимости перевозок (Y = min).

Транспортная таблица состоит из m строк и n столбцов. В правом верхнем углу каждой клетки будем ставить стоимость сij перевозки единицы груза из Ai, в Вj„ а центр клетки оставим свободным, чтобы помещать в нее саму перевозку xij. Клетку таблицы, соответствующую пунктам Ai, Bj, будем кратко обозначать (i, j).

Пример транспортной таблицы, где приведены условия задачи и стоимости перевозок, но нет еще самих перевозок, дан в таблице 10.1, где m = 4, n = 5.

Таблица 8.1

Cоставим опорный план, применив «метод северо-западного угла». Заполнение транспортной таблицы начнем с левого верхнего («северо-западного») угла. Пункт В1 подал заявку па 18 единиц груза; удовлетворим ее из запасов пункта A1. После этого в нем остается еще 30--18=12 единиц груза; отдадим их пункту В2. Но заявка этого пункта еще не удовлетворена; выделим недостающие 15 единиц из запасов пункта А2 и т. д. Рассуждая точно таким же образом, заполним до конца перевозками xij транспортную таблицу (таблица 8.2).

Таблица 8.2

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

В таблицах будем проставлять отличные от нуля перевозки, а клетки, соответствующие нулевым перевозкам, оставляем «свободными». Проверим, является ли план перевозок, данный в таблице 8.2, опорным. Число свободных клеток с нулевыми перевозками в таблице 8.2 равно как раз (m -1)(n - 1) = 3 * 4 = 12, так что план -- опорный.

Этот план можно улучшить, если произвести в нем «циклическую перестановку» перевозок между клетками таблицы, уменьшив перевозки в «дорогой» клетке (2.3) со стоимостью 12, но зато увеличив перевозки в «дешевой» клетке (2.4) со стоимостью 6 (таблица 8.3).

Таблица 8.3

Чтобы план оставался опорным, мы должны при этом сделать одну из свободных клеток базисной, а одну из базисных -- свободной. Сколько единиц груза можем мы перенести по циклу (2.4) -> (3.4) -> (3.3) -> (2.3), увеличивая перевозки в нечетных вершинах цикла и уменьшая -- в четных? Очевидно, не больше, чем 11 единиц (иначе перевозки в клетке (3.4) стали бы отрицательными). Очевидно, в результате циклического переноса допустимый план остается допустимым -- баланс запасов и заявок не нарушается. Произведем этот перенос и запишем новый, улучшенный план перевозок в таблице 8.4.

Таблица 8.4

Общая стоимость плана, показанного в таблице 8.3, равна

L1 = 18 * 13 + 12 * 7 + 15 * 8+ 33 * 12 +9 * 10 + 11 * 8 + 4 * 10 + 26 * 15=1442.

Общая стоимость плана, показанного в таблице 8.4, равна

L2 = 18*13 +12*7 +15*8 + 22*12 +11*6 +20*10+4*10+26*15 =1398.

Таким образом, нам удалось уменьшить стоимость перевозок на 1442 -- 1398 == 44 единицы. Будем считать алгебраическую сумму стоимостей, стоящих в вершинах цикла, со знаком плюс, если перевозки в этой вершине увеличиваются, и со знаком минус -- если уменьшаются (так называемая «цена цикла»), в данном случае равна: 6--8+10--12 = -- 4. Значит, при переносе одной единицы груза по этому циклу стоимость перевозок уменьшается на четыре. А мы их перенесли целых 11; значит, стоимость должна была уменьшиться на 11*4=44 единицы, что и произошло.

Значит, весь секрет оптимизации плана перевозок в том, чтобы переносить («перебрасывать») перевозки по циклам, имеющим отрицательную цену.

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

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

Таблица 8.5

Это последовательность клеток (1.5) ->(4.5) ->(4.4) ->(2.4) ->(2.2) ->(1.2) (и замыкая цикл, снова возвращаемся в (1.5)). Нечетные вершины цикла отмечены плюсом -- это значит, что перевозки в этих клетках увеличиваются: четные -- знаком минус (перевозки уменьшаются). Цикл показан стрелками в таблице 8.4.

Подсчитаем цену этого цикла. Она равна 5--15+ 10--6+8--7= --5. Так как цена цикла отрицательна, то переброска перевозок по этому циклу выгодна. По этому циклу мы можем перебросить 11 единиц. Это определяется наименьшей перевозкой, стоящей в отрицательной вершине цикла. Умножая 11 на цену цикла --5, получим, что за счет переброски 11 единиц груза по данному циклу мы еще уменьшим стоимость перевозок на 55.

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

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

Если объем ресурсов всех поставщиков больше объема ресурсов всех потребителей, то вводят фиктивного потребителя Вn+1 с объемом потребления равным

m n

bn+1 = ai - bj ( 8.7 )

i = 1 j = 1

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

C1,n+1 = C2,n+1 = … = Cm,n+1 = 0 ( 8.8 )

Если объем ресурсов потребителей больше объема ресурсов поставщиков, то вводят фиктивного поставщика Аm+1 с объемом поставки равным

n m

am+1 = bj - ai ( 8.9 )

j = 1 i = 1

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

Cm+1,1 = Cm+1,2 = … = Cm+1,n = 0 ( 8.10 )

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

§6. Решение распределительных задач линейного программирования

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

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

Таблица 9.1

Построение математической модели

Введем переменные Xi,j, которые равны 1, если i-й кран работает на j-ом объекте и 0, если он не работает там.

Сформулируем ограничения в задаче:

1. Каждый кран может работать только на одном объекте. Это ограничение можно записать в таком виде:

X11 + X12 + X13 + X14 + X15 = 1

X21 + X22 + X23 + X24 + X25 = 1

X31 + X32 + X33 + X34 + X35 = 1 (9.1)

X41 + X42 + X43 + X44 + X45 = 1

X51 + X52 + X53 + X54 + X55 = 1

2. Каждый объект может возводиться только одним краном. Это ограничение можно записать так:

X11 + X21 + X31 + X41 + X51 = 1

X12 + X22 + X32 + X42 + X52 = 1

X13 + X23 + X33 + X43 + X53 = 1 (9.2)

X14 + X24 + X34 + X44 + X54 = 1

X15 + X25 + X35 + X45 + X55 = 1

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

Обозначим через ci,j себестоимость возведения j-ro объекта i-м краном. Тогда критерий оптимизации Y - суммарная себестоимость выполнения всех работ - запишется в таком виде:

m m

Y = ci,j xi,j (9.3)

i = 1 j = 1

Совокупность ограничений (9.1) и (9.2) и целевой функции (9.3) образует математическую модель типичной экстремальной комбинаторной задачи. Ее решение представляет собой некоторую перестановку чисел, а количество перестановок с ростом n резко возрастает и равно N = n!. Она относится к классу задач линейного программирования, так как ограничения и целевая функция имеют линейный вид, то есть искомые величины находятся в первой степени.

Алгоритм решения

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

Алгоритм этого метода включает четыре основных этапа. Для поиска оптимального решения потребуется не более чем n-2 последовательно проводимых итераций:

1. Получение нулей в каждой строке и каждом столбце

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

Таблица 9.2

Аналогично производим действия для каждого столбца новой таблицы (таблица 9.2). Получаем таблицу 9.3.

Таблица 9.3

2. Проверка решения на оптимальность

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

Таблица 9.4

Переходим к следующему этапу.

3. Поиск минимального набора строк и столбцов, содержащих нули.

Необходимо отметить звездочкой:

а) все строки, не имеющие ни одного отмеченного звездочкой нуля (таблица 9.5, строка 4);

б) все столбцы, содержащие перечеркнутый нуль хотя бы в одной из отмеченных звездочкой строк (таблица 9.5, столбец 3);

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

Таблица 9.5

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

4. Перестановка некоторых нулей.

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

Таблица 9.6

Эта операция не изменяет оптимального решения. После нее выполняется новая итерация, цикл расчета начинается с этапа 2 и так до тех пор, пока не будет получено оптимальное решение. Поскольку число нулей, отмеченных звездочкой, не равно n, выполняется новый итерационный цикл, после чего находится оптимальное решение (таблица 9.7).

Таблица 9.7

Из полученного решения видно, что Х15 = 1, Х21 = 1, ХЗЗ = 1 и т.д. Это означает: чтобы оптимально распределить пять кранов на пять объектов, необходимо первый кран направить на пятый объект, второй - на первый, третий - на третий, четвертый кран возводит четвертый объект, а пятый кран возводит второй объект. Первая цифра в переменной X определяет машину, а вторая - объект работы, при этом суммарная себестоимость выполнения всех работ будет минимальной и составит Ymin = 220.

§7. Задачи целочисленного программирования. Понятие о нелинейном программировании

1. Задачи целочисленного программирования.

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

Рассмотрим пример такой задачи. Пусть имеется ряд предметов (ценностей) П1, П2, ..., Пn, которые требуется перевезти из одного города в другой. Известны стоимости этих предметов: с1, c2, ..., сn и их веса q1, q2, ..., qn. Количество и вид предметов, которые можно перевезти, лимитируется грузоподъемностью Q машины. Требуется из всего набора предметов выбрать наиболее ценный набор (с максимальной суммарной стоимостью предметов), вес которого укладывается в Q.

Введем переменные х1, x2, ..., xn, определяемые условием: xi = 1, если в машину берётся предмет Пi, и xi = 0,-- если не берётся.

При заданных значениях х1, x2, ..., xn суммарный вес предметов, которые берутся в машину, равен q1x1 + q2x2 + ... + qnxn. Условие ограниченной грузоподъемности запишется в виде неравенства:

q1x1 + q2x2 + ... + qnxn Q (10.1)

Запишем общую стоимость предметов, которую нужно максимизировать:

n

L = ci xi max (10.2)

i = 1

Таким образом, задача похожа на обычную задачу линейного программирования: найти неотрицательные значения переменных х1, x2, ..., xn, которые удовлетворяют неравенству (10.1) и обращают в максимум линейную функцию этих переменных (10.2). На первый взгляд может показаться, что и решать ее надо как задачу линейного программирования, введя дополнительные ограничения-неравенства (каждый предмет -- только один!):

x1 1, x2 1, ..., xn 1.

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

Если задачу решать как обычную задачу линейного программирования и округлить полученные значения xi до ближайшего из целых чисел 0 или 1, то полученное таким образом решение даже может не удовлетворять ограничению (10.1), т. е. «не влезет» в данный вес Q. А если и «влезет», то может быть совсем не оптимальным.

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

2. Задачи нелинейного программирования

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

ц1(х1, х2, . . . , хn) ? 0,

ц2(х1, х2, . . . , хn) ? 0, (10.3)

цm(х1, х2, . . . , хn) ? 0,

и обращающие в максимум произвольную нелинейную функцию этих переменных:

W = W(х1, x2, ..., xn) max. (10.4)

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

Задачи нелинейного программирования па практике возникают довольно часто, например, когда затраты растут не пропорционально количеству закупленных или произведенных товаров (эффект «оптовости»), но многие нелинейные задачи могут быть приближенно заменены линейными, по крайней мере в области, близкой к оптимальному решению. Если это и невозможно, все же обычно нелинейные задачи, возникающие на практике, приводят к сравнительно «благополучным» формам нелинейности. В частности, нередко встречаются задачи «квадратичного программирования», когда W есть полином 2-й степени относительно переменных х1, x2, ..., xn, а неравенства (10.3) линейны. В ряде случаев при решении задач нелинейного программирования может быть с успехом применен так называемый «метод штрафных функций», сводящий задачу поиска экстремума при наличии ограничений к аналогичной задаче при отсутствии ограничений, которая обычно решается проще. Идея метода состоит в том, что вместо того, чтобы наложить на решение жесткое требование вида ц(х1, х2, . . . , хn) ? 0 можно наложить некоторый достаточно большой «штраф» за нарушение этого условия и добавить к целевой функции W(х1, x2, ..., xn) штраф вида aц(х1, х2, . . . , хn) ? 0 где а -- коэффициент пропорциональности (в случае, когда целевая функция максимизируется, а отрицательно, если минимизируется -- положительно). Далее можно, увеличивая абсолютное значение а, посмотреть, как изменяется при этом оптимальное решение (х1*, x2*, ..., xn*), и, когда оно ужо практически перестает меняться, остановиться на нем. В ряде случаев при решении задач нелинейного программирования оказываются полезными так называемые «методы случайного поиска», состоящие в том, что вместо упорядоченного перебора возможных вариантов решения применяется случайный розыгрыш.

Раздел 3. Динамическое программирование

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

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

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

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

m

W = wi (11.1)

i = 1

где wi, -- выигрыш на i-м шаге.

Если W обладает таким свойством, то его называют «аддитивным критерием».

Операция O представляет собой управляемый процесс, т. е. мы можем выбирать какие-то параметры, влияющие на его ход и исход, причем на каждом шаге выбирается какое-то решение, от которого зависит выигрыш на данном шаге и выигрыш за операцию в целом. Такое решение называется «шаговым управлением». Совокупность всех шаговых управлений представляет собой управление операцией в целом. Обозначим его буквой х, а шаговые управления -- буквами х1, x2, ..., xm:

х = ( х1, x2, ..., xm). (11.2)

В общем случае х1, x2, ..., xm могут быть не только числа, а и векторы, функции и т. д.

Требуется найти такое управление x, при котором выигрыш W обращается в максимум:

m

W = wi max (11.3)

i = 1

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

x* = ( х*1, x*2, ..., x*m). (11.4)

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

W* = mах {W (х)}. (11.5)

Формула (11.5) читается так: величина W* есть максимум из всех W(x) при разных управлениях х (максимум берется по всем управлениям х, возможным в данных условиях).

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

1. Планируется деятельность группы промышленных предприятий П1, П2, ..., Пk на период m хозяйственных лет. В начале периода на развитие группы выделены какие-то средства М, которые должны быть как-то распределены между предприятиями. В процессе работы предприятия вложенные в него средства частично расходуются (амортизируются), а частично сохраняются и снова могут быть перераспределены. Каждое предприятие за год приносит доход, зависящий от того, сколько средств в него вложено. В начале каждого хозяйственного года имеющиеся в наличии средства перераспределяются между предприятиями. Ставится вопрос: какое количество средств в начале каждого года нужно выделять каждому предприятию, чтобы суммарный доход за m лет был максимальным?

Выигрыш W (суммарный доход) представляет собой сумму доходов на отдельных шагах (годах):

m

W = wi (11.6)

i = 1

и, значит, обладает свойством аддитивности.

Управление хi, на i-м шаге состоит в том, что в начале i-го года предприятиям выделяются какие-то средства хi1, хi2, ..., хik (первый индекс -- номер шага, второй -- номер предприятия). Таким образом, шаговое управление есть вектор с k составляющими:

xi = (хi1, хi2, ..., хik). (11.7)

Величины wi в формуле (11.6) зависят от количества вложенных в предприятия средств.

Управление х всей операцией состоит из совокупности всех шаговых управлений:

x = (x1, x2, ..., xm). (11.8)

Требуется найти такое распределение средств по предприятиям и по годам (оптимальное управление х*), при котором величина W обращается в максимум.

В этом примере шаговые управления были векторами.

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

G = G1+G2+...+Gm,

где Gi -- вес i-й ступени.

В результате i-го этапа (сгорания и сбрасывания i-й ступени) ракета получает приращение скорости t , зависящее от веса данной ступени и суммарного веса всех оставшихся плюс вес кабины. Спрашивается, как нужно распределить вес G между ступенями, чтобы скорость ракеты V при ее выводе на орбиту была максимальна?

В данном случае показатель эффективности (выигрыш) будет

m

V = i (11.9)

i = 1

где i--выигрыш (приращение скорости) на i-м шаге.

Управление х представляет собой совокупность весов всех ступеней Gi:

x = (G1, G2, ..., Gm).

Оптимальным управлением х* будет то распределение весов по ступеням, при котором скорость V максимальна. В этом примере шаговое управление -- одно число, а именно, вес данной ступени.

3. Владелец автомашины эксплуатирует ее в течение m лет. В начале каждого года он может принять одно из трех решений:

1) продать машину и заменить ее новой;

2) ремонтировать ее и продолжать эксплуатацию;

3) продолжать эксплуатацию без ремонта.

Шаговое управление -- выбор одного из этих трех решений. Непосредственно числами они не выражаются, но можно приписать первому численное значение 1, второму 2, третьему 3. Какие нужно принять решения по годам (т. е. как чередовать управления 1, 2, 3), чтобы суммарные расходы на эксплуатацию, ремонт и приобретение новых машин были минимальны?

Показатель эффективности (в данном случае это не «выигрыш», а «проигрыш») равен

m

W = wi (11.10)

i = 1

где wi -- расходы в i-м году. Величину W требуется обратить в минимум.

Управление операцией в целом представляет собой какую-то комбинацию чисел 1, 2, 3, например:

x = (3,3, 2, 2, 2, 1, 3, ...),

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

x = (j1, j2, ... , jm), (11.11)

где каждое из чисел j1, j2, ..., jm имеет одно из трех значений: 1, 2 или 3. Нужно выбрать совокупность чисел (11.11), при которой величина (11.10) минимальна.

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

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

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

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

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

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

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

Предположим, что это сделано, и для каждого из возможных исходов предпоследнего шага знаем условное оптимальное управление и соответствующий ему условный оптимальный выигрыш на m-м шаге. Теперь можно оптимизировать управление на предпоследнем, (m -- 1)-м шаге. Снова сделаем все возможные предположения о том, чем кончился предыдущий, (m -- 2)-й шаг, и для каждого из этих предположений найдем такое управление на (m--1)-м шаге, при котором выигрыш за последние два шага (из которых m-й уже оптимизирован!) максимален. Так находим для каждого исхода (m -- 2)-го шага условное оптимальное управление на (m -- 1)-м шаге и условный оптимальный выигрыш на двух последних шагах. Далее, «пятясь назад», оптимизируем управление на (m -- 2)-м шаге и т. д., пока не дойдем до первого.

Предположим, что все условные оптимальные управления и условные оптимальные выигрыши на всех шагах процесса известны. Теперь можно построить уже не условно оптимальное, а просто оптимальное управление х* и найти не условно оптимальный, а просто оптимальный выигрыш W*.

Таким образом, в процессе оптимизации управления методом динамического программирования многошаговый процесс «проходится» дважды: первый раз -- от конца к началу, в результате чего находятся условные оптимальные управления и условные оптимальные выигрыши за оставшийся «хвост» процесса; второй раз -- от начала к концу, когда остается только «прочитать» уже готовые рекомендации и найти безусловное оптимальное управление х*, состоящее из оптимальных шаговых управлений х1*, х2*, ... , хm*.

§2. Примеры решения задач динамического программирования

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

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

Разделим расстояние от А до В в восточном направлении, например, на 7 частей, а в северном -- на 5 частей (в принципе дробление может быть сколь угодно мелким). Тогда любой путь из А в В состоит из m = 7 + 5 = 12 отрезков, направленных на восток или на север (рисунок 12.2). Проставим на каждом из отрезков число, выражающее (в условных единицах) стоимость прокладки пути но этому отрезку. Требуется выбрать такой путь из А в В, для которого сумма чисел, стоящих на отрезках, минимальна.

Y (север) В

А

Х (восток)

Рисунок 12.2

Будем рассматривать сооружаемый путь как управляемую систему S, перемещающуюся под влиянием управления из начального состояния А в конечное В. Состояние этой системы перед началом каждого шага будет характеризоваться двумя координатами: восточной (х) и северной (y), обе--целочисленные (0 x 7, 0 y 5).

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

Процедуру условной оптимизации будем разворачивать в обратном направлении -- от конца к началу. Прежде всего, произведем условную оптимизацию последнего, 12-го шага. Рассмотрим отдельно правый верхний угол прямоугольной сетки (рисунок 12.3). После 11-го шага будем находится там, откуда за один (последний) шаг можно попасть в В, т. е. в одной из точек B1 или В2.

Рисунок 12.3

Если находимся в точке B1 - выбора нет (управление вынужденное): надо идти на восток, и это обойдется в 10 единиц. Запишем это число 10 в кружке у точки В1, а оптимальное управление покажем короткой стрелкой, исходящей из В1 и направленной на восток. Для точки В2 управление тоже вынужденное (север), расход до конца равен 14, запишем его в кружке у точки В2. Таким образом, условная оптимизация последнего шага сделана, и условный оптимальный выигрыш для каждой из точек В1, В2 найден и записан в соответствующем кружке.

Оптимизируем предпоследний (11-й) шаг. После 10-го шага можно оказаться в одной из точек С1, C2, C3 (рисунок 12.4).

Рисунок 12.4

Найдем для каждой из них условное оптимальное управление и условный оптимальный выигрыш. Для точки С1 управление вынужденное: идти на восток; обойдется это до конца в 21 единицу (11 на данном шаге, плюс 10, записанных в кружке при B1). Число 21 записываем в кружке при точке С1. Для точки С2 управление уже не вынужденное: можно идти как на восток, так и на север. В первом случае затраты на данном шаге составят 14 единиц и от В2 до конца -- еще 14, всего 28 единиц. Если пойдем на север, затратим 13 + 10, всего 23 единицы. Значит, условное оптимальное управление в точке C2 -- идти на север (отмечаем это стрелкой, а число 23 записываем в кружке у С2). Для точки С3 управление снова вынужденное («с»), обойдется это до конца в 22 единицы (ставим стрелку на север, число 22 записываем в кружке при С3).

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

В кружке при точке А записан оптимальный выигрыш на все сооружение пути из А в В: W* = 118.

Построим безусловное оптимальное управление -- траекторию, ведущую из А и В самым дешевым способом. Такая оптимальная траектория отмечена на рисунке 12.5 дважды обведенными кружками. Соответствующее безусловное оптимальное управление будет:

х* = (с, с, с, с, в, в, с, в, в, в, в, в),

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

Y (север)

А Х (восток)

Рисунок 12.5

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

2. Задача о распределении ресурсов. Метод динамического программирования позволяет решать многие экономические задачи. Рассмотрим одну из простейших таких задач. В нашем распоряжении имеется какой-то запас средств (ресурсов) К, который должен быть распределен между m предприятиями П1, П2, ..., Пm. Каждое из предприятий Пi при вложении в него каких-то средств х приносит доход, зависящий от x, т. е. представляющий собой какую-то функцию i(х). Все функции i(х) (i = 1, 2, ..., m) заданы. Спрашивается, как нужно распределить средства К между предприятиями, чтобы в сумме они дали максимальный доход?

Эта задача решается методом динамического программирования. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие П1, за второй -- в П2 и т. д.

Управляемая система S в данном случае -- средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S -- наличным запасом еще не вложенных средств. В этой задаче «шаговыми управлениями» являются средства х1, x2, ..., xm, выделяемые предприятиям. Требуется найти оптимальное управление, т. е. такую совокупность чисел х1, x2, ..., xm, при которой суммарный доход максимален:

m

W = цi (xi) max (12.1)

i = 1

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

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

xm (S) = S,

а условный оптимальный выигрыш

Wm(S )= m(S).

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

Перейдем к предпоследнему, (m -- 1)-му шагу. Пусть мы подошли к нему с запасом средств S. Обозначим Wm-1(S) условный оптимальный выигрыш на двух последних шагах: (m -- 1)-м и m-м (который уже оптимизирован). Если мы выделим на (m--1)-м шаге (m--1)-му предприятию средства х, то на последний шаг останется S -- х. Наш выигрыш на двух последних шагах будет равен

m-1 (х) + Wm(S --x),

и нужно найти такое x, при котором этот выигрыш максимален:

Wm-1(S) = max {m-1(х) + Wm (S - х)}. (12.2)

x ? S

Знак max означает, что берется максимальное значение по всем x какие

x ? S

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

Wi(S) = max {(i(х) + Wi+1 (S - х)} (12.3)

x ? S

и соответствующее ему условное оптимальное управление xi(S) -- то значение х, при котором этот максимум достигается.

Продолжая таким образом, дойдем, наконец, до 1-го предприятия П1. Здесь не нужно будет вычислять значения S; мы точно знаем, что запас средств перед первым шагом равен К:

W* = W1 (К) = max {1(х) + W2(К - х)}. (12.4)

x ? К

Максимальный выигрыш (доход) от всех предприятий найден. Значение х, при котором достигается максимум (12.4), и есть оптимальное управление х1* на 1-м шаге. После того как мы вложим эти средства в 1-е предприятие, у нас их останется К--х1*. Выделяем второму предприятию оптимальное количество средств: x2* = x2(K-x1*), и т. д. до конца.

Решим численный пример. Исходный запас средств К =10 (условных единиц), и требуется его оптимальным образом распределить между пятью предприятиями (m = 5). Для простоты предположим, что вкладываются только целые количества средств. Функции дохода i(x) заданы в таблице 12.1.

Таблица 12.1

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

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

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

Таблица 12.2

условного оптимального управления, во втором -- условного оптимального выигрыша. Таблица заполняется слева направо, сверху вниз. Решение на пятом -- последнем -- шаге вынужденное: выделяются все средства; на всех остальных шагах решение приходится оптимизировать. В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W* за всю операцию -- в данном случае он равен 5,6. В последних двух столбцах таблицы 12.2 заполнена только одна строка, так как состояние системы перед началом первого шага нам в точности известно: So = К = 10. Оптимальные управления на всех шагах выделены рамкой. Таким образом, мы получили окончательный вывод: надо выделить первому предприятию две единицы из десяти, второму -- пять единиц, третьему -- две, четвертому -- ни одной, пятому -- одну единицу. При этом распределении доход будет максимален и равен 5,6.

Чтобы было понятно, как заполняется таблица 12.2, продемонстрируем это на одном образце расчета. Пусть, например, нужно оптимизировать решение х3(7) -- как поступать на третьем шаге, если мы подошли к нему с запасом средств S = 7, и сколько максимум мы можем выиграть на всех оставшихся

Таблица 12.3

шагах, включая третий? Предположим, что все шаги после третьего (4-й и 5-й) уже оптимизированы, т. е. заполнены две первые пары столбцов таблицы 12.2. Найдем х3(7) и W3(7). Для этого составим вспомогательную табличку (см. таблицу 12.3). В первом ее столбце перечислены все возможные вложения х на третьем шаге, не превосходящие S = 7. Во втором столбце -- то, что останется после такого вложения от запаса средств S =7. В третьем столбце -- выигрыш на третьем шаге от вложения средств х в третье предприятие (заполняется по столбцу 3(х) таблицы 12.1). В четвертом столбце -- оптимальный выигрыш на всех оставшихся шагах (четвертом и пятом) при условии, что мы подошли к четвертому шагу с оставшимися средствами (заполняется по столбцу i = 4 таблицы 12.2). В пятом столбце -- сумма двух выигрышей: шагового и оптимизированного дальнейшего при данном вложении х в третий шаг.

Из всех выигрышей последнего столбца выбирается максимальный (в таблице 12.3 он равен W3 (7) = 3,6, а соответствующее управление x(7) =2).

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

3. Задача о загрузке машины. Пользуясь методом динамического программирования, решим задачу о загрузке машины: имеется определенный набор предметов П1, П2, ..., Пn (каждый в единственном экземпляре); известны их веса q1, q2, ..., qn и стоимости c1, c2, ..., cn. Грузоподъемность машины равна Q. Спрашивается, какие из предметов нужно взять в машину, чтобы их суммарная стоимость (при суммарном весе Q) была максимальна?

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

Состояние системы S характеризуется весом S, который еще остался в нашем распоряжении до конца (полной загрузки машины) после того, как предыдущие шаги выполнены (какие-то предметы погружены в машину). Для каждого из значений S мы должны найти Wi(S) -- суммарную максимальную стоимость предметов, которыми можно «догрузить» машину при данном значении S, и положить xi(S) = 1, если мы данный (i-й) предмет берем в машину, и xi(S) = 0, если не берем.

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

Таблица 12.4

Суммарная грузоподъемность машины Q = 35 единиц веса. Требуется указать номера предметов, которые нужно включить в груз, чтобы их суммарная стоимость была максимальна.

Будем придавать S только целые значения. Условная оптимизация решения показана в таблице 12.5, где в каждой строке для соответствующего номера шага (номера предмета) приведены: условное оптимальное управление хi (0 или 1) и условный оптимальный выигрыш Wi (стоимость всех оставшихся до конца предметов при оптимальном управлении на всех шагах).

В таблице 12.5 выделены: оптимальный выигрыш W* = 57 и оптимальные шаговые управления, при которых этот выигрыш достигается: х1* = 0, х2* = 1, x3* = 0, х4* = 1, x5* = 1, x6* = 0, т. е. загрузить машину надо предметами 2, 4 и 5, суммарный вес которых равен в точности 35 (при оптимальном выборе грузов может быть и некоторый общий «недогруз»).

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

Таблица 12.5

§3. Задача динамического программирования в общем виде. Принцип оптимальности

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

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

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

1) возможные исходы предыдущего шага;

2) влияние управления на все оставшиеся до конца процесса шаги.

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

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

Раздел 4. Марковские случайные процессы

§1. Основные понятия теории марковских процессов

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

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

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

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

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

Пусть в настоящий момент t0 (см. рисунок 14.1) система находится в определенном состоянии S0.

Рисунок 14.1

Мы наблюдаем процесс со стороны и в момент t0 знаем состояние системы S0 и всю предысторию процесса, все, что было при t < t0. Нас интересует будущее (t > t0). Так как в точности его предугадать мы не можем - наш процесс случайный, значит -- непредсказуемый. Но какие-то вероятностные характеристики процесса в будущем мы найти можем. Например, вероятность того, что через некоторое время система S окажется в состоянии S1 или сохранит состояние S0, и т. п.

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

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

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

So -- оба узла исправны,

S1 -- первый узел ремонтируется, второй исправен,

S2 -- второй узел ремонтируется, первый исправен,

S3 -- оба узла ремонтируются.

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

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

Состояния системы изображаются прямоугольниками, а возможные переходы из состояния в состояние -- стрелками, соединяющими состояния. Мы будем изображать состояния прямоугольниками, в которых записаны обозначения состояний: S1, S2, ...., Sn.

Построим граф состояний для рассмотренного выше примера (см. рисунок 14.2).

Рисунок 14.2

Стрелка, направленная из S0 в S1, означает переход в момент отказа первого узла; стрелка, направленная обратно, из S1 в S0,-- переход в момент окончания ремонта этого узла. Остальные стрелки объясняются аналогично.

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

§2. Потоки событий

Потоком событий называется последовательность однородных событий, следующих одно за другим в какие-то случайные моменты времени. Например: поток вызовов на телефонной станции; поток отказов (сбоев) ЭВМ; поток железнодорожных составов, поступающих на сортировочную станцию; поток частиц, попадающих на счетчик Гейгера, и т.д.

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

Рисунок 15.1

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

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

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

На практике часто встречаются потоки событий, которые (по крайней мере, на ограниченном участке времени) могут считаться стационарными. Например, поток вызовов, поступающих на АТС между 13 и 14 часами, практически стационарен; тот же поток в течение суток уже не стационарен.

Поток событий называется потоком без последействия, если для любых двух непересекающихся участков времени 1 и 2 (см. рисунок 15.2) число событий, попадающих на один из них, не зависит от того, сколько событий попало на другой.

Рисунок 15.2

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

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

Поток событий называется простейшим (или стационарным пуассоновским), если он обладает сразу тремя свойствами: стационарен, ординарен и не имеет последействия. Название «простейший» связано с тем, что процессы, связанные с простейшими потоками, имеют наиболее простое математическое описание.

§3. Уравнения Колмогорова для вероятностей состояний

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

Если система S находится в каком-то состоянии Si, из которого есть непосредственный переход в другое состояние Sj (стрелка, ведущая из Si, в Sj на графе состояний), то представим что на систему, пока она находится в состоянии Si, действует простейший поток событий, переводящий ее по стрелке Si->Sj. Как только появится первое событие этого потока, происходит «перескок» системы из Si в Sj.

Для наглядности на графе состояний у каждой стрелки проставим интенсивность того потока событий, который переводит систему по данной стрелке. Обозначим 0 интенсивность потока событий, переводящего систему из состояния Si в Sj. На рисунке 16.1 дан граф состояний с проставленными у стрелок интенсивностями (будем называть такой граф размеченным).

Рисунок 16.1

Построим размеченный граф состояний для технического устройства из двух узлов. Напомним состояния системы:

S0 -- оба узла исправны,

S1 -- первый узел ремонтируется, второй исправен,

S2 -- второй узел ремонтируется, первый исправен,

S3 -- оба узла ремонтируются.

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

Рисунок 16.2

Найдем все интенсивности потоков событий, переводящих систему из состояния в состояние. Пусть система находится в состоянии S0. Поток отказов первого узла переводит ее в состояние S1. Его интенсивность 1 равна единице, деленной на среднее время безотказной работы первого узла. Поток «окончаний ремонтов» первого узла переводит систему обратно из S1 в S0. Его интенсивность 1 равна единице, деленной на среднее время ремонта первого узла. Аналогично вычисляются интенсивности потоков событий, переводящих систему по всем стрелкам графа рисунка 16.2.

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

Пусть рассматривается система S, имеющая n возможных состояний S1, S2, ..., Sn. Назовем вероятностью i-го состояния вероятность pi(t) того, что в момент t система будет находиться в состоянии Si. Очевидно, что для любого момента сумма всех вероятностей состояний равна единице:

n

У pi (t) = 1 (16.1)

i = 1

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

Пусть система S имеет четыре состояния: S1, S2, S3, S4, размеченный граф которых показан на рисунке 16.3.

Рассмотрим одну из вероятностей состояний, например p1(t). Это--вероятность того, что в момент t система будет в состоянии S1. Придадим t малое приращение t и найдем p1 (t + t) -- вероятность того, что в момент t + t система будет в состоянии S1.

Это может произойти двумя способами:

1) в момент t система уже была в состоянии S1, а за время t не вышла из него;

2) в момент t система была в состоянии S2, а за время t перешла из него в S1.

Найдем вероятность первого варианта. Вероятность того, что в момент t система была в состоянии S1, равна p1(t). Эту вероятность нужно умножить на вероятность того, что, находившись в момент t в состоянии S1, система за время t не перейдет из него ни в S2, ни в S3. Суммарный поток событий, выводящий систему из состояния S1, тоже будет простейшим, с интенсивностью 12+13. Значит, вероятность того, что за время t система выйдет из состояния S1, равна (12 + 13)t; вероятность того, что не выйдет:

1 -- (12 + 13)t. Отсюда вероятность первого варианта равна p1(t) [1 -- (12 + 13)t].

Найдем вероятность второго варианта. Она равна вероятности того, что в момент t система будет в состоянии S2, а за время t перейдет из него в состояние S1, т. е. она равна p2(t)21t.

Складывая вероятности обоих вариантов (по правилу сложения вероятностей), получим:

p1(t +t ) = p1(t) [1 -- (12 + 13)t] + p2(t)21t .

Раскроем квадратные скобки, перенесем p1(t) в левую часть и разделим обе части на t:

Устремим t к нулю; слева получим в пределе производную функции p1(t). Таким образом, запишем дифференциальное уравнение для p1(t):

или, короче, отбрасывая аргумент t у функций p1, p2 :

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

Это -- система четырех линейных дифференциальных уравнений с четырьмя неизвестными функциями p1 p2, p3, p4. Одно из них (любое) можно отбросить, пользуясь тем, что p1 + p2 + p3 + p4 = 1, т.е. выразить любую из вероятностей pi через другие, это выражение подставить в (16.3), а соответствующее уравнение с производной dpi/dt отбросить.

Сформулируем общее правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятности какого-то (i-го) состояния. В правой части -- сумма произведений вероятностей всех состояний, из которых идут стрелки в данное состояние, на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность данного (i-ro) состояния.

Пользуясь этим правилом, запишем уравнения Колмогорова для системы S, размеченный граф состояний которой дан на рисунке 16.2:

dp0

---- = м1p1 + м2p2 - (л1 + л2) p0

dt

dp1

---- = л1p0 + м2p3 - (л2 + м1) p1

dt (16.4)

dp2

---- = л2p0 + м1p3 - (л1 + м2) p2

dt

dp3

---- = л2p1 + л1p2 - (м1 + м2) p3

dt

Чтобы решить уравнения Колмогорова и найти вероятности состояний, прежде всего надо задать начальные условия. Если мы точно знаем начальное состояние системы Si, то в начальный момент (при t = 0) р0(0) = 1, а все остальные начальные вероятности равны нулю. Так, например, уравнения (17.4) естественно решать при начальных условиях р0(0) = 1, p1(0) = р2(0) = р3(0) = 0 (в начальный момент оба узла исправны).

Уравнения Колмогорова дают возможность найти все вероятности состояний как функции времени.

§4. Финальные вероятности состояний

Если при t ? вероятности состояний p1(t), p2(t),... будут стремиться к каким-то пределам и если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний. В теории случайных процессов доказывается, что если число n состояний системы конечно и из каждого из них можно (за конечное число шагов) перейти в любое другое, то финальные вероятности существуют.

Предположим, что это условие выполнено и финальные вероятности существуют:

lim pi (t) = pi (i = 1, 2, . . . , n) (17.1)

t -> ?

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

n

У pi (t) = 1 (17.2)

i = 1

При t ? в системе S устанавливается предельный стационарный режим, в ходе которого система случайным образом меняет свои состояния, но их вероятности уже не зависят от времени. Финальную вероятность состояния Si можно рассматривать как среднее относительное время пребывания системы в этом состоянии. Например, если система S имеет три состояния S1, S2, S3 и их финальные вероятности равны 0,2, 0,3 и 0,5, это значит, что в предельном, стационарном режиме система в среднем две десятых времени проводит в состоянии S1, три десятых--в состоянии S2 и половину времени -- в состоянии S3.

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

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

(л1 + л2) p0 = м1p1 + м2p2

(л2 + м1) p1 = л1p0 + м2p3

(л1 + м2) p2 = л2p0 + м1p3 (17.3)

(м1 + м2) p3 = л2p1 + л1p2

При решении этой системы четырех уравнений с четырьмя неизвестными р0, р1, р2, р3, воспользуемся так называемым нормировочным условием:

p0 + p1 + p2 + p3 = 1 (17.4)

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

Зададимся численными значениями интенсивностей 1 = 1, 2=2, 1 = 2, 2 = 3 и решим систему (17.3). Вместо четвертого уравнения добавим нормировочное условие (17.4). Уравнения примут вид:

3p0 = 2p1 + 3p2

4p1 = p0 + 3p3

4p2 = 2p0 + 3p3 (17.5)

p0 + p1 + p2 + p3 = 1

Решая их, получим:

p0 = 6/15=0,40; p1 =3/15 =0,20; p2 = 4/15 = 0,27; P3=2/15 =0,13,

т. е. в предельном, стационарном режиме система S в среднем 40% времени будет проводить в состоянии S0 (оба узла исправны), 20% -- в состоянии S1 (первый узел ремонтируется, второй работает), 27% --в состоянии S2 (второй узел ремонтируется, первый работает) и 13% -- в состоянии S3 полной негодности (оба узла ремонтируются). Знание этих финальных вероятностей может помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов. Предположим, что система S в состоянии S0 (полностью исправная) приносит в единицу времени доход 8 (условных единиц), в состоянии S1--доход 3, в состоянии S2--доход 5, в состоянии S3 -- вообще не приносит дохода. Тогда в предельном, стационарном режиме средний доход в единицу времени будет

W = 0,40 * 8 + 0,20 * 3 + 0,27 * 5 = 5,15.

Теперь оценим загрузку рабочих, занятых ремонтом узлов 1 и 2. Узел 1 ремонтируется долю времени, равную p1 + р3 = 0,20 + 0,13 = 0,33. Узел 2 ремонтируется долю времени p2 + р3 = 0,40.

Раздел 5. Теория массового обслуживания

§1. Понятие системы массового обслуживания. Классификация систем массового обслуживания

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

Системы массового обслуживания по наличию того или иного признака можно классифицировать таким образом:

1. По характеру поступления требований - на системы с регулярным и случайным потоками поступления требований в систему. Случайный поток подразделяется на стационарный и нестационарный:

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

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

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

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

4. По характеру поведения требования - в системе с отказами, с ограниченным ожиданием и с ожиданием без ограничения:

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

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

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

5. По способу выбора требований на обслуживание - с приоритетом, по мере поступления, случайно, последний обслуживается первым. Иногда в таком случае говорят о дисциплине обслуживания:

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

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

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

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

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

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

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

9. По однородности требований, поступающих на обслуживание, - на системы с однородными и неоднородными потоками требований. Так, если под погрузку прибывают фургоны одной грузоподъемности, то такие требования называются однородными, если разной - неоднородными.

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

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

§2. Схема гибели и размножения

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

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

/

л01 л12 л23 лk-1,k лk,k-1 лn-1,n

л10 л21 л32 лk,k-1 лk+1,k лn,n-1

Рисунок 19.1

Особенность этого графа в том, что все состояния системы можно вытянуть в одну цепочку, в которой каждое из средних состояний (S1, S2, ..., Sn-1) связано прямой и обратной стрелкой с каждым из соседних состояний -- правым и левым, а крайние состояния (S0, Sn) -- только с одним соседним состоянием. Термин «схема гибели и размножения» ведет начало от биологических задач, где подобной схемой описывается изменение численности популяции.

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

Предположим, что все потоки событий, переводящие систему по стрелкам графа,-- простейшие.

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

Для первого состояния S0 имеем:

01p0=10p1. ( 19.1 )

Для второго состояния S1:

(12 + 10)p1 = 01p0 + 21P2.

В силу ( 19.1 ) последнее равенство приводится к виду

12p1 = 21Р2;

далее, совершенно аналогично

23Р2 = 32p3

и вообще

k-1,kpk-1=k,k-1pk,

где k принимает все значения от 0 до n. Итак, финальные вероятности р0, p1,..., pn удовлетворяют уравнениям

01p0=10p1

12p1 = 21Р2

…………………. ( 19.2 )

k-1,kpk-1=k,k-1pk

………………….

n-1,npn-1=n,n-1pn

кроме того, надо учесть нормировочное условие

p0 +p1+p2+ ... +рn =1. ( 19.3 )

Решим эту систему уравнений. Из первого уравнения (19.2 ) выразим р1 через р0:

p1 = (01/10)p0. (19.4 )

Из второго, с учетом ( 19.4 ), получим:

p2=(12/21)p1=(1201)/(2110)p0; ( 19.5 )

из третьего, с учетом ( 19.5 ),

p3=(231201)/(322110)p0 (19.6 )

и вообще, для любого k (от 1 до n):

pk=(k-1,k... 1201)/(k,k-1... 2110)p0 ( 19.7 )

Обратим внимание на формулу ( 19.7 ). В числителе стоит произведение всех интенсивностей, стоящих у стрелок, ведущих слева направо (с начала и до данного состояния Sk,), а в знаменателе -- произведение всех интенсивностей, стоящих у стрелок, ведущих справа налево (с начала и до Sk).

Таким образом, все вероятности состояний р0, р1, ..., рn выражены через одну из них (р0). Подставим эти выражения в нормировочное условие ( 19.3 ). Получим, вынося за скобку p0:

отсюда получим выражение для р0:

Все остальные вероятности выражены через р0 (см. формулы (19.4) - (19.7)). Коэффициенты при р0 в каждой из них представляют собой последовательные члены ряда, стоящего после единицы в формуле ( 19.8 ). Значит, вычисляя р0, мы уже нашли все эти коэффициенты.

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

§3. Простейшие системы массового обслуживания и их параметры

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

Функционирование любой системы массового обслуживания можно представить через все возможные состояния ее и интенсивность перехода из одного состояния в другое. Основными параметрами функционирования СМО являются вероятности ее состояния, то есть возможности наличия n требований (покупателей, рабочих, заданий, машин, неполадок) в системе - Pn. Так, вероятность Р0 характеризует состояние, когда в системе нет требований и канал обслуживания простаивает.

Важным параметром функционирования СМО является среднее число требований, находящихся в системе Nsyst , то есть в очереди на обслуживание, а также средняя длина очереди Noch. Исходными параметрами, характеризующими систему массового обслуживания, являются: число каналов обслуживания - N (касс, компьютеров, кранов, ремонтных бригад,...); число требований (покупателей, заданий, машин, неполадок,...) - m; интенсивность поступления одного требования на обслуживание - л, то есть число поступлений требований в единицу времени; интенсивность обслуживания требований - м.

Интенсивность поступления требования на обслуживание определяется как величина, обратная времени возвращения требования, - tвоз:

л = 1/ tвоз.

Интенсивность обслуживания требований определяется как величина, обратная времени обслуживания одного требования, - tобс:

м = 1/ tобс.

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

Пусть задан комплект машин «экскаватор - автосамосвалы». Экскаватор погружает за один рабочий цикл gэ = 1 т массы грунта. Грузоподъемность автосамосвала gа = 7 т. Число машин, обслуживающих экскаватор, m = 5. Время рабочего цикла экскаватора составляет tр.ц. = 18 с, а время обращения автосамосвала tобр. = 10 мин. Определить фактическую производительность комплекта машин; среднее число машин, находящихся в системе; среднее число машин, находящихся в очереди; вероятность наличия n машин в системе.

Построение математической модели.

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

- в системе нет ни одного требования - вероятность состояния Р0;

- в системе находится одно требование - вероятность состояния P1;

- в системе находится n требований - вероятность состояния Рn.

Представим все возможные состояния СМО в виде размеченного графа состояний (рисунок 20.1). Каждый прямоугольник графа, количественно оцениваемый вероятностью состояний Рn, определяет одно из всех возможных состояний. Стрелки указывают, в какое состояние система может перейти и с какой интенсивностью.

Первый прямоугольник с вероятностью Р0 определяет состояние СМО, при котором канал обслуживания простаивает из-за отсутствия требований в ней. Из этого положения система может перейти только в состояние Р1. Тогда в ней появится одно требование, так как входной поток их ординарный. С интенсивностью м система может перейти также из состояния Р1 в состояние Р0; когда в системе находилось одно требование, оно было обслужено раньше, чем появилось новое и т.д.

Рассмотрим установившийся режим работы системы массового обслуживания, когда основные вероятностные характеристики СМО постоянны во времени, например, в течение часа. Тогда интенсивности входных и выходных потоков для каждого состояния будут сбалансированы. Эти балансы выглядят так:

P0m л = P1 м

P1(м + (m - 1) л) = P0m л + P2 м

P2(м + (m - 2) л) = P1 (m - 1) л + P3 м

. . . . . . . . . . . . . . . . . .

Pn(м + (m - n) л) = Pn-1 (m - (n - 1)) л + Pn+1 м (20.1)

. . . . . . . . . . . . . . . . . .

Pm м = Pm -1 л

Обозначим величину л/ м через ш и назовем ее коэффициентом загрузки.

Из первого уравнения можно найти значение Р1:

P1 = P0m л / м = P0m ш.

Из второго уравнения найдем значение Р2:

P2 = P1 + P1(m - 1) л / м - P0m л / м

Но первый член - P1 = P0m л / м , следовательно, первый и третий сокращаются:

P2 = P1(m - 1) л / м = P0m(m - 1) ш2.

Из третьего уравнения найдем значение Р3:

P3 = P2 + P2(m - 2) л / м - P1(m - 1) л / м

Но первый член - P2 = P1(m - 1) л / м , следовательно, первый и третий сокращаются:

P3 = P2(m - 2) л / м = P0m(m - 1)(m - 2)ш3

……………………………………………………

m

Pn = Pn-1(m - (n - 1)) л / м = P0m(m - 1)…(m - (n - 1))шn = P0 ? (m - (n - 1))! • шn

n=0

m

Используя очевидное равенство ? Pn = 1 , получим:

n=0

m

1 = P0 ? (m - (n - 1))! • шn (20.2)

n=0

Зная вероятность простоя канала обслуживания Р0, можно определить его фактическую производительность:

Pf = (1 - P0) •µ • G (20.3)

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

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

(m - Nsyst) • л = (1 - P0) • µ (20.4)

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

Nsyst = m - (1 - P0) / ш (20.5)

Среднее же число требований (машин), находящихся в очереди, будет вычислено так:

Noch = Nsyst - (1 - P0) = m - (1 - P0) (1/ ш + 1) (20.6)

Решение задачи при установившемся режиме работы.

Время обслуживания одного грузовика составит:

gа

tпогр = ------- tр.ц. (20.7)

gэ

18 х 7

tпогр = -------- = 2,1 мин.

60 х 1

Интенсивность погрузки автосамосвала экскаватором составит:

1

µ = ------ (20.8)

tпогр

60

µ = ------ = 29 погрузок в час.

2,1

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

1

л = ------ (20.9)

tобр

60

л = ------- = 6 обращений в час.

10

Коэффициент ш = л/ м будет равен ш = 0,207.

Вероятность простоя экскаватора в этом случае составит:

1

P0 = --------------------------------- (20.10)

m

1 + ? (m - (n - 1))! • шn

n=1

1

P0 = --------------------------------- = 0,271

5

1 + ? (5 - (n - 1))! • шn

n=1

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

Вероятности наличия n машин в системе:

P1 = P0 m ш = 0,281

P2 = P1 (m - 1) ш = 0,233

P3 = P2 (m - 2) ш = 0,144

P4 = P3 (m - 3) ш = 0,06

P5 = P4 (m - 4) ш = 0,012

Фактическая производительность комплекта машин определяется по формуле 20.3 :

Pf = (1 - 0,271) • 29 • 7 = 147,947 т/час.

Среднее число машин, находящихся в системе определяется по формуле 20.6 :

Nsyst = 5 - (1 - 0,271) / 0,207 = 1,477

Среднее число машин, находящихся в очереди определяется по формуле 20.7 :

Noch = 5 - (1 - 0,271) (1/0,207 + 1) = 0,749

Раздел 6. Имитационное моделирование

§1. Метод имитационного моделирования. Типы имитационных моделей

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

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

1. Задачи в различных областях естественных наук (математика, физика, химия):

- вычисление площадей фигур, ограниченных кривыми, или, в более общем случае, вычисление кратных интегралов;

- вычисление констант (например р, равной 3,14159..,);

- обращение матриц;

- изучение диффузионных процессов.

2. Практические задачи:

- производственно-технологические задачи, возникающие в процессе создания систем массового обслуживания, систем связи, в сфере управления запасами, а также при анализе химических процессов;

- экономические и коммерческие задачи, включая оценки поведения потребителя, определение цен, экономическое прогнозирование деятельности фирм;

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

- задачи биомедицинских систем, например проблема баланса жидкости в организме человека, размножения клеток крови, деятельности мозга;

- задачи анализа той или иной военной стратегии и тактики.

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

Использование современных имитационных моделей основано, в основном, на идее метода Монте-Kapло (выборка случайных чисел для получения искомых оценок). Отличие состоит в том, что имитационная модель обычно связана с изучением реально существующей системы, поведение которой является функцией времени. Существует два типа имитационных моделей.

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

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

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

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

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

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

§2. Языки имитационного моделирования

Реализация имитационных моделей влечет за собой два различных типа вычислений:

1) манипуляции регистрацией, которые имеют дело с хронологическим накоплением и обработкой событий модели;

2) вычисления, связанные с генерированием случайных чисел и сбором статистических данных, относящихся к модели.

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

Доступные языки дискретного имитационного моделирования делятся на две большие категории:

1) Языки, ориентированные на планирование событий.

2) Языки, ориентированные на обработку процессов (процедур).

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

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

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

Наиболее известными языками программирования, ориентированными на планирование событий, являются SIMSCR1PT, SLAM и SIMAN. Все эти языки позволяют пользователю создавать модели (или их отдельные части) на языках высокого уровня, таких как FORTRAN и С. Это необходимо для того, чтобы дать возможность пользователю программировать сложные логические операции, которые невозможно или трудно осуществить обычными средствами этих языков.

Первым процедурно-ориентированным языком был GPSS. Этот язык, первая версия которого появилась в начале 60-х годов, совершенствовался на протяжении нескольких лет, чтобы удовлетворить новым требованиям, связанным с моделированием сложных систем. Чтобы эффективно использовать этот язык, пользователю необходимо настроить примерно восемьдесят различных блоков. До сих пор язык GPSS все еще имеет некоторые трудно объяснимые особенности моделирования.

Другой процедурно-ориентированный язык программирования, именуемый SEMNET II, разработан для непосредственного моделирования сложных ситуаций. SIMNET II использует три типа узлов: источник, который генерирует заказы, очередь, где заказы могут ожидать, и средство обслуживания, где выполняется обслуживание. В этом языке имеется еще четвертый дополнительный тип узла, который рассматривается как средство обслуживания неограниченной емкости, что призвано усилить моделирующие возможности языка.

Раздел 7. Прогнозирование

§1. Основная идея прогнозирования. Методы прогнозирования

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

Рассмотрим две методики прогнозирования изменений интересующих нас переменных как функций времени.

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

yt = b + еt

где yt - действительное (или наблюденное) значение случайной величины у в момент времени t;

b-- неизвестный постоянный параметр, который оценивается на основе представленной информации;

еt - случайный компонент (или шум) в момент времени t.

Предполагается, что случайная ошибка еt имеет нулевое математическое ожидание и постоянную дисперсию.

Метод с использованием скользящего среднего предполагает, что последние п наблюдений являются равнозначно важными для оценки параметра b. Другими словами, если в текущий момент времени t последними n наблюдениями есть yt-n+1, yt-n+2, …, yt, тогда оцениваемое значение для момента t + 1 вычисляется по формуле

yt-n+1 + yt-n+2 + … + yt

yt+1* = --------------------------------

n

где yt* - расчетное значение (оценка) случайной величины у в момент времени t.

Не существует четкого правила для выбора числа n - базы метода, использующего скользящее среднее. Если есть весомые основания полагать, что наблюдения в течение достаточно длительного времени удовлетворяют модели yt = b + еt, то рекомендуется выбирать большие значения n. Если же наблюдаемые значения удовлетворяют приведенной модели в течение коротких периодов времени, может быть приемлемым и малое значение n. На практике величина я обычно принимается в пределах от 2 до 10.

Прогнозирование путем экспоненциального сглаживания. Прогнозирование путем экспоненциального сглаживания (метод экспоненциального сглаживания) предполагает, что вероятностный процесс определяется моделью yt = b + еt.

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

Определим величину б (0 < б < 1) как константу сглаживания, и пусть известны значения временного ряда для прошедших t моментов времени у1, у2, …, уt. Тогда оценка yt+1* для момента времени t + 1 вычисляется по формуле

yt+1* = бyt + б(1 - б)yt-1 + б(1 - б)2yt-2 + …

Коэффициенты при yt, yt-1, yt-2, … постепенно уменьшаются, тем самым эта процедура приписывает больший вес последним (по времени) данным.

Формулу для вычисления yt+1* можно привести к следующему (более простому) виду:

yt+1* = бyt + (1 - б){бyt-1 + б(1 - б)yt-2 + б(1 - б)2yt-3 …} = = бyt + (1 - б)y*t

Таким образом, значение yt+1* можно вычислить на основании значения y*t . Вычисления в соответствии с этим уравнением начинаются с того, что пропускается оценка y*1 для t = 1 и в качестве оценки для t = 2 принимается величина для t = 1, т.е. y*2 = y1.

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

Раздел 8. Теория принятия решений

§1. Элементы теории принятия решений

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

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

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

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

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

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

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

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

Метод анализа иерархий

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

Мартин Ганс -- выпускник-отличник средней школы, который получил полную стипендию от трех университетов: А, В и С. В целях выбора университета Мартин сформулировал два основных критерия: местонахождение университета и его академическая репутация. Будучи отличным учеником, он оценивает академическую репутацию университета в пять раз выше, чем его местонахождение. Это приводит к тому, что репутации университета приписывается вес примерно 83%, а его местонахождению -- 17%. Далее Мартин использует системный анализ (сущность его излагается ниже) .для оценки трех университетов с точки зрения их местонахождения и репутации. Проведенный анализ дает следующие оценки.

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

Оценка трех университетов основана на вычислении комбинированного весового коэффициента для каждого из них.

Университет А: 0.17 х 0.129 + 0.83 х 0.545 = 0.4743.

Университет В: 0.17 х 0.277 + 0.83 х 0.273 = 0.2737.

Университет С: 0.17 х 0.594 + 0.83 X 0.182 = 0.2520.

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

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

Рисунок 24.1 - Структура задачи принятия решений

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

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

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

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

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

Информация, связанная с принятием решения, суммирована в следующей таблице 24.1.

Таблица 24.1

Эта задача может быть также представлена в виде дерева решения, показанного на рисунке 24.2. На этом рисунке используется два типа вершин: квадратик представляет 'решающую' вершину, а кружок-- 'случайную'. Таким образом, из вершины 1 ('решающая') выходят две ветви, представляющие альтернативы, связанные с покупкой акций компании А или В. Далее две ветви, выходящие из 'случайных' вершин 2 и 3, соответствуют случаям повышения и понижения котировок на бирже с вероятностями их появления и соответствующими платежами.

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

Для акций компании А: $5000 х 0.6 + (-2000) х 0.4 = $2 200.

Для акций компании В: $1500 х 0.6 + $500 х 0.4 = $1 100.

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

Рисунок 24.2 - Дерево решения

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

Раздел 9. Теория игр

§1. Основные понятия теории игр. Простейшие методы решения задач теории игр

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

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

Такое представление матричной игры означает, что если игрок А использует стратегию i, а игрок В -- стратегию j, то платеж игроку А составляет аij и, следовательно, игроку В -- -аij.

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

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

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

Минимумы строк

Максимумы столбцов 8 5 9 8

Минимакс

Решение игры основано на обеспечении наилучшего результата из наихудших для каждого игрока. Если компания А выбирает стратегию А1 то, независимо от того, что предпринимает компания В, наихудшим результатом является потеря компанией А 3% рынка в пользу компании В. Это определяется минимумом элементов первой строки матрицы платежей. Аналогично при выборе стратегии А2 наихудшим исходом для компании А является увеличение рынка на 5% за счет компании В. Наконец, наихудшим исходом при выборе стратегии Аз является потеря компанией А 9% рынка в пользу компании В. Эти результаты содержатся в столбце 'Минимумы строк'. Чтобы достичь наилучшего результата из наихудших, компания А выбирает стратегию А2, так как она соответствует наибольшему элементу столбца 'Минимумы строк'.

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

Оптимальным решением игры является выбор стратегий А2 и В2, т.е. обеим компаниям следует проводить рекламу на телевидении. При этом выигрыш будет в пользу компании А, так как ее рынок увеличится на 5%. В этом случае говорят, что цена игры равна 5% и что компании А и В используют стратегии, соответствующие седловой точке.

Решение, соответствующее седловой точке, гарантирует, что ни одной компании нет смысла пытаться выбрать другую стратегию. Действительно, если компания В переходит к другой стратегии (В1, В3 или В4), то компания А может сохранить свой выбор стратегии А2, что приведет к большей потере рынка компанией В (6% или 8%). По тем же причинам компании А нет резона использовать другую стратегию, ибо если она применит, например, стратегию А3, то компания В может использовать свою стратегию В3 и увеличить свой рынок на 9%. Аналогичные выводы имеют место, если компания А будет использовать стратегию A1.

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

Список литературы

1. Агальцов В.П., Волдайская И.В. Математические методы в программировании. - М.: ИД «ФОРУМ» - ИНФРА-М, 2006.

2. Хэмди А. Таха Введение в исследование операций - М.: Издательский дом «Вильямс», 2001.

3. Вентцель Е.С. Исследование операций: задачи, принципы, методология - М.: ДРОФА, 2004.

4. Кудрявцев Е.М. Mathcad 8. Символьное и численное решение разнообразных задач - М.: ДМК, 2000.

5. Глушаков С.В., Сурядный А.С. Microsoft Office 2000. Учебный курс - Харьков: ФОЛИО, 2001.

6. Советов Б. Я., Яковлев С.А. Моделирование систем - М.: Высш. шк., 2001.

7. Семененко М.Г. Математическое моделирование в MathCad - М.: Альтекс-А, 2003.