назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [ 55 ] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


55

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

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

Оптимальное уклонение (оптимальная стратегия второго игрока) можно классифицировать так же как оптимальное преследование (оптимальная стратегия первого игрока). Все замечания, сделанные относительно Р и его цели преследования, сохраняют свой смысл и для Е с его целью уклонения. Например, можно говорить о способах избежать захвата или по крайней мере предупредить его до истечения времени Т. Если за плату принять расстояние до объекта в момент захвата, то можно обсуждать вопрос о том, как Е должен максимизировать это расстояние. В военных задачах, разумеется, обе стороны рассматривают оба класса этих вопросов. Мы обсуждали задачи игры и понятия платы только с точки зрения преследователя Л но делали это лишь чтобы облегчить описание.

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

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

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



Дано: автомобиль на бесконечной пустой площади, который пытается наехать на пешехода. Таким образом, рассматривается игра преследования, где Р обладает превосходящей скоростью, но меньшей маневренностью по сравнению с Е. Преследователь Р движется с постоянной скоростью wu радиус кривизны его траектории ограничен заданной величиной R; Р управляет выбором значения этой кривизны в каждый момент. Убегающий Е обладает более простым движением. Это значит, что его скорость W2 фиксирована, и управление состоит в том, что в каждый момент выбирается направление движения. В этом случае допустимы любые крутые повороты; траектория может не иметь касательной в каждой точке.

Захват происходит, когда расстояние РЕ не больше заданной величины 1 радиуса захвата. Преследователь обязан быть быстрее w\ > W2. Нас интересуют два вопроса.

Задача состоит в том, чтобы определить точные условия: значения R, 1, w\ IW2, которые разграничивают эти возможности.

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

2.Игра качества. Когда Р может поймать Е ? Ясно, что если R велико, 1 мало и w\ не очень превышает W2, то Е всегда может избежать захвата. Можно считать, например, что он сделает это, просто отступая в сторону всякий раз, когда появляется угроза захвата. Ограничение кривизны траектории преследователя запрещает ему слишком резкие повороты. Он может промчаться мимо Е и, вернувшись обратно для новой попытки, может быть снова обманут тем же маневром Е,



Глава 6

ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕПРОГРАММИРОВАНИЕ

И решения задачи без требований целочисленности.

Целочисленное программирова-

Задача называется полностью целочисленной, если условие цело-ориентировано на решение задач

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

переменным, задача называется ««ю должны принимать только частично целочисленной.целочисленные значения. Задача на-

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

TTTJ, .XnZ...r..rr.r «.TTT..,« если условие целочисленности нало-близости целочисленного решения

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

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

Другим важным классом таких задач являются экстремальные комбинаторные задачи, переменные которых носят логический характер {х = О или X = 1). Такие переменные называются булевыми. К таким задачам относятся, например, задачи выбора некоторого подмножества, обладающего какими-либо экстремальными свойствами.

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

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

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [ 55 ] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]