книги / Математические методы принятия решений

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

Задача нахождения минимума некоторой функции f(x) эквива­ лентна задаче отыскания максимума той же функции, взятой со зна­ ком минус (рис. 1.1), и наоборот. Поскольку принципиальных отли­ чий в нахождении минимума и макси­ мума не существует, будем говорить об оптимальных (лат. optimum —наилуч­ шее), или экстремальных значениях целе­

вых функций.

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

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

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

2.Описательное моделирование. Установление и фиксация ос­ новных связей и зависимостей между характеристиками процесса или явления согласно оптимизируемому критерию.

3.Математическое моделирование. Запись описательной моде­ ли математическими формулами. Все условия записывают в ви­ де соответствующей системы равенств и неравенств, а критерий

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

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

5.Выбор ши написание программы для решенш задачи на ЭВМ.

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

спомощью ЭВМ. Программа для ЭВМ реализует выбранный ме­ тод решения задачи.

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

взаданной им форме.

7.Анализ полученного решенш. Анализ решения бывает фор­ мальным и содержательным. При формальном (математическом) анализе проверяют соответствие полученного решения построен­

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

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

Только после полного завершения анализа модель можно ис­ пользовать для расчета. Чтобы подчеркнуть важность содержатель­

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

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

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

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

Сколько надо взять бабе на базар для продажи живых гусей, уток и кур, чтобы выручить как можно больше денег, если она мо­ жет нести не более Р кг, причем известно, что ai — вес одной кури­ цы, 02 — вес одной утки, аз — вес одного гуся, ci — стоимость одной курицы, С2 — СТОИМОСТЬ ОДНОЙ утки, Сз — стоимость одного гуся.

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

ная выручка от продажи птицы:

3

Условие-ограничение определяется весом товара, который мо­

жет нести баба:

з

a i XI + 02X2 + 03X3 = 2 üiXi ^ Р. г=1

Среди старинных задач по математике встречается задача о Кёнигсбергских мостах, сформулированная и решенная в 1736 г. известным математиком Л. Эйлером (1707-1783): можно ли пооче­ редно обойти все семь мостов города Кёнигсберга, соединяющих районы этого города с островом на реке Прегель, пройдя по каж­ дому мосту толыю один раз. Как мы увидим далее, это тоже задача математического программирования.

Несмотря на столь ранние истоки математического программи­ рования его развитие относится к концу 30-х годов XX столетия. Математическое программирование развивалось как дисциплина, посвященная теории и методам решения задач управления и плани­ рования, а далее — как раздел возникшей в 50-е годы науки об ис­ следовании операций при создании совокупности методологических средств, называемых системным анализом.

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

в1975 г. совместно с американским ученым Т.Купмансом Нобе­ левской премии за внесенный ими вклад в теорию оптимизации распределения ресурсов.

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

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

Методы математического программирования применялись и од­ новременно развивались во время Второй мировой войны для планирования военных операций. Еще до начала Второй мировой войны методы анализа военных систем с использованием матема­ тического программирования стали применяться военными специ­ алистами в Великобритании, а затем и в других странах. В США

*Канторович Л. В. Математические методы в организации и планировании производства.—Л.: Изд-во ЛГУ, 1939.

и Канаде были созданы специальные подразделения, занимавшиеся анализом военных операций. В 1938 г. в США был введен термин «исследование операций» для характеристики рода деятельности необычной исследовательской группы, созданной по инициативе организации Air Ministry Research Station и выполнявшей работы по анализу военных систем, в частности решавшей задачи опти­ мального использования радиолокационных установок в общей системе обороны страны. Этот анализ являлся основой для при­ нятия командованием соответствующих решений. Впоследствии исследование операций сформировалось в научное направление.

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

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

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

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

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

В настоящее время издается много научных журналов по ис­ следованию операций, первый из которых вышел в свет в 1950 г. В 1957 г. в Лондоне был созван первый конгресс Международной Федерации обществ исследования операций (International Federation of Operations Research Societies — IFORS); эти конгрессы проводят каждые три года.

С50-х годов XX в. для обоснования решений сложных проблем

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

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

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

Отдельные исследования по системному анализу проводились в конце XIX в. и начале XX в., а также в Первую мировую вой­ ну. Так, в 1886 г. военное командование прибегло к использованию системного анализа, чтобы принять решение относительно произ­ водства 12-дюймовых орудий (1 дюйм —2,54 см), заряжающихся с казенной части и предназначенных для использования в берего­ вой артиллерии. Необходимо было сделать выбор между орудием, выпускаемым фирмой Кгирр, и орудием нового образца американ­ ского производства. Во время Первой мировой войны с помощью системного анализа разрабатывались, например, стратегические планы борьбы с подводными лодками. Однако эти работы не имели практического применения и были неизвестны. Поэтому во время Второй мировой войны работы пришлось начинать заново. Си­ стемный анализ (и его часть — исследование операций) во время Второй мировой войны применяли в основном при тактическом планировании операций, например для того, чтобы решить, что в первую очередь использовать в качестве радиолокационных по­ мех — пассивные или активные помехи; как определить наиболее эффективные цели для бомбометания; какие из способов обнаруже­ ния подводных лодок являются наилучшими и т. п.

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

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

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

2)разработка методов использования имеющейся в распоряже­ нии людей техники, обеспечивающей выполнение поставленной за­ дачи с минимальными затратами или с максимальным эффектом;

3)разработка техники и материалов, которые необходимо со­ здать или приобрести в рамках общей стратегии деятельности людей.

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

и распределения ресурсов в различных областях науки и техни­ ки (экономике, торговле и промышленности — управление запаса­ ми, назначение персонала, составление маршрутов и т. п.) интен­ сивно развиваются в последние десятилетия.

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

Рассмотрим в качестве примера так называемую транспортную задачу, являющуюся одной из первых потоковых задач (см. гл. 3), решенную Ф. Л. Хитчкоком в 1941 г.

Пусть имеются два завода и три склада. Заводы производят со­ ответственно si и S2 единиц продукции, возможности складов —di,

продукции с г-го завода на j -й склад. Тогда целевая функция задачи состоит в минимизации стоимости перевозки:

СЦЯ11 + С12Я12 + С13Я13 + C21X21 + С22Х22 + С23Ж23 =

i—1j = 1

Условия того, что вся продукция будет вывезена с каждого завода,

запишем в следующем виде:

3

3 = 1

3

Эти два равенства можно записать кратко:

з