Линейное программирование

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

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

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

Производство Стоимость Потребление

Производитель1, завод А 3 изделия	Транспортировки 3 долл. на изделие
	1 долл. на изделие	Потребитель М 1 изделие
	2 долл. на изделие	Потребитель N 2 изделия
	2 долл. на изделие
	1 долл. на изделие	Потребитель Р 4 изделия
Производитель1, завод В 4 изделия	3 долл. на изделие

Рис. 13.1. Простейшая задача линейного программирования.

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

Если расходы на перевозку одного изделия составляют: из пункта А в М - 3долл., из А в N - 2 долл., из А в Р - 1 долл., из В в М - 1 долл., из В в N - 2 долл., из В в Р - 3 долл. (рис. 13.1), то при некоей схеме распределения изделий по маршрутам транспортные расходы будут минимальны .

Можно, например, доставлять по одному изделию из А в N, М и Р, еще одно изделие - из В в N и, наконец, три изделия - из В в Р. Тогда транспортные расходы составят: (3 х 1) + (2 х 1) + (1 х 1) + (2 х 1) + + (3 х 3) = 3+ 2 + 1 + 2 + 9 = 17 долл.

Однако большие преимущества представит схема транспортировки, когда три изделия доставляют из А в Р, а остальные из В. Тогда расходы составят: (1x3 + +(1 х 1) + (2 х 2) + (3 х 1) = 3+1 +4 + 3 = 11 долл. Но будет ли этот вариант лучшим?

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

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

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

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

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

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

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

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

Метод Монте-Карло

Метод Монте-Карло также используется в анализе систем. Он, грубо говоря, позволяет получать приближенные решения задач с помощью эксперимента со случайными числами. Предположим, что требуется определить вероятность выигрыша в одиночной карточной игре, скажем Конфилд[84]. Попытка прямого расчета делает очевидным, что объем вычислений чрезмерно велик. Можно также провести игру большое число раз, например N раз, и подсчитать число выигрышей п, определить затем его вероятность как отношение n/N. Это может привести к ошибкам, однако их величина будет уменьшаться с увеличением числа партий. Для ускорения расчетов игру можно моделировать на электронной цифровой вычислительной машине, работающей с большой скоростью, и поручить ей игру. Однако даже при быстродействующей ЭВМ число испытаний для получения доброкачественного ответа может быть чрезмерно велико, если величина ошибок уменьшается медленно. В любом случае, однако, разумное сочетание анализа со случайными испытаниями, вероятно, окажется весьма эффективным. В этом суть метода Монте-Карло.

Метод Монте-Карло является развитием используемых в статистике методов выборочных испытаний. Отличие заключается в том, что методом Монте-Карло стремятся найти ответ на математические задачи и вести испытания в абстрактных ситуациях, а не пользоваться результатами реальных обследований. Абстракция, позволяющая менять объект исследования, дала возможность существенно усо­вершенствовать метод.

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

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

Метод Монте-Карло широко применяется в исследовании операций главным образом потому, что это простейший из всех вычислительных методов, пригодных для решения больших и сложных проблем, типичных для этой науки. Случайность часто является характерным элементом этих проблем. Они нередко бывают новы и трудно формализуемы. Даже если их можно выразить в математической форме, то почти никогда не удается свести к известному виду, в результате чего бывает трудно или невозможно применить традиционные методы анализа. В то же время для метода Монте-Карло достаточно построить модель реального процесса. Поскольку быстродействующие ЭЦВМ принимают на себя основную долю вычислительного труда, метод Монте-Карло часто позволяет заменить вычислительной техникой математическую изобретательность и мысль. Более того, для решения большей части проблем, встречающихся в исследовании операций и анализе систем, не существует других методов, кроме метода Монте-Карло, особенно если помимо определения ожидаемой величины параметра желательно получить также оценку вероятного распределения результата. Если задача бывает сложна, то традиционные методы анализа обычно становятся бесполезными.

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

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

Положим, что изделия поступают в случайной последовательности на пункт обслуживания, где их обрабатывают поочередно. Предположим, что интервалы между случайными моментами поступления составляют в 40% случаев 10 мин, а в 60% случаев - 20 мин. Предположим, что длительность обслуживания также изменяется случайным образом, причем требуется 10 мин для обслуживания 80% изделий и 30 мин для обслуживания остальных 20% изделий.

Тогда для каждого изделия будем иметь:

средний интервал между поступлениями; 0,4 х 10 + + 0,6 х 20 = 16 мин,

среднее время обслуживания: 0,8 х 10 + 0,2 х 30 14 мин,

среднее время простоя: 16 - 14 = 2 мин.

Нас интересует среднее время ожидания обслуживания. Чтобы решить эту задачу, используем модель, где интервалы между моментами поступления и длительностью обслуживания выражаются последовательностью случайных чисел. Сначала выберем случайные числа, чтобы определить интервалы времени между поступлениями изде­лий. Если это будут 0, 1, 2 или 3, считаем интервал прибытия равным 10 мин. Если это 4, 5, 6, 7, 8 или 9, будем считать его равным 20 мин. Аналогично для определении времени обслуживания поступающего изделия выберем второй ряд случайных чисел. Если это будет 0, 2, 3, 4, 5, 6 или 7, то время обслуживания составит 10 мин, а если это будет 8 или 9, то сочтем его равным 30 мин.

Теперь мы можем заполнить табл. 13.1, полагая начало процесса в момент времени 0. Здесь R и R' представляют собой случайные числа.

Таблица 13.1 - Простейшая задача массового обслуживания

Таким образом, для 10 выборок, указанных в таблице, общее время ожидания составляет 60 мин, или 6 мин на изделие в среднем. Этот пример оставляет без ответа многие вопросы, например вопрос о числе выборок, необходимых для получения достоверной величины времени ожидания, однако он наглядно демонстрирует основные особенности метода Монте-Карло в том виде, как он применяется в исследовании операций.

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

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

Теория игр

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

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

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

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

1) участники пытаются выявить стратегию противника и скрыть свою;

2) каждый из участников может только частично контролировать результат игры;

3) участники могут блефовать и совершать обманные действия;

4) участники могут располагать различными объемами информации или разведывательных данных о противнике;

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

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

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

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

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

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

Д. Вильяме в книге «Совершенный стратег»[85] писал так: «Теория игр, несмотря на ее ограничения, имеет в настоящее время приложения. Однако основная заслуга теории игр в том, что она дала ориентацию людям, которые сталкиваются с крайне запутанными проблемами. И хотя теория игр не дает строгого решения этих проблем, по крайней мере в настоящее время, и, вероятно, не будет давать его в течение неопределенного срока в будущем, тем не менее она указывает основу и направление усилий, предназначенных для их решения. Понятие стратегий, различие между игроками, роль случайных событий, матричное представление платежей, понятие о чистых и смешанных стратегиях и т. д. дают полезную ориентацию людям, которым приходится иметь дело со сложными конфликтными ситуациями».

Поиск по сайту: