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


[Старт] [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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


2

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

Ограничением в данной задаче являются дни прибытия: понедельник первой недели и среда пятой.

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

Альтернатива 1: стоимость билетов = 5 х 400 = 2000 долл.

Альтернатива 2: стоимость билетов = 0,75 х 400 + 4 х 0,8 х 400 + 0,75 х 400 = = 1800 долл.

Альтернатива 3: стоимость билетов = 5 х (0,8 х 400) = 1600 долл. Очевидно, что наилучшей является третья альтернатива.

Приведенный пример показывает основные принципиальные составляющие модели исследования операций (ИО), а именно альтернативы, ограничения и критерий отбора альтернатив. Но в различных ситуациях эти составляющие могут весьма отличаться от аналогичных составляющих других моделей. Чтобы показать это, рассмотрим следующую задачу. Среди всех прямоугольников с периметром фиксированной длины L необходимо найти прямоугольник максимальной площади. Какую длину и ширину будет иметь такой прямоугольник?

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

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

1. Ширина прямоугольника + длина прямоугольника = половина периметра прямоугольника.

2. Ширина и длина прямоугольника не могут быть отрицательными. Эти ограничения алгебраически запишутся так.

1. 2(l + w) = L.

2. l>0,w>0.

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

Максимизировать г - lw

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

2(1 + w) = L. l,w>0.

Оптимальным решением данной задачи будет w = 1 = L/4, т.е. среди прямоугольни-ов с фиксированным периметром максимальную площадь будет иметь квадрат.



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

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

Максимизация или минимизация целевой функции при условии выполнения ограничений.

Решение задачи называется допустимым, если оно удовлетворяет всем ограничениям модели. Решение будет оптимальным, если, кроме того, что оно допустимо, целевая функция при этом решении достигает оптимального (максимального или минимального) значения. В примере с билетами задача имела три допустимых альтернативы и оптимальное решение предоставляла третья альтернатива. В примере с прямоугольником допустимое решение должно удовлетворять условию I + w = L/2 с неотрицательными значениями Iviw. Это приводит к бесконечному множеству допустимых решений, поэтому здесь, в отличие от примера с билетами, для поиска оптимального решения необходимо привлекать соответствующие математические средства (в данном случае - средства дифференциального исчисления).

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

УПРАЖНЕНИЯ 1.1

1. В примере с билетами определите четвертую возможную альтернативу.

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

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

4. Крис, Джим, Джон и Келли находятся на восточном берегу реки и хотят переправиться на западный берег с помощью каноэ. Каноэ может вместить не более двух человек. Крис, как наиболее сильный из всех своих друзей, может переправиться через реку за 1 минуту. У Джима, Джона и Келли на это уйдет соответственно 2, 5 и 10 минут. Если в каноэ находятся два человека, то время переправы определяется по слабейшему пассажиру. Цель друзей заключается в переправе на западный берег реки по возможности за минимальное время.

a) Найдите не менее двух возможных схем переправы через реку.

b) Определите критерий оценки альтернатив.

c) Какое минимальное время переправы через реку всех друзей?



1.2. РЕШЕНИЕ МОДЕЛЕЙ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ1

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

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

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

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

1.3. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ

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

Альтернативой математическому моделированию сложных систем может служить имитационное моделирование. Различие между математической и имитацион-

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

[Старт] [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] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]