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


[Старт] [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]


126

Литература

УПРАЖНЕНИЯ 8.2.2

1. Пусть в задаче из примера 8.2.2 бюджет рекламной компании возрос до 110 ООО долл. Желаемый объем рекламной аудитории остался неизменным - 45 млн. чел. Найдите решение данной задачи методом приоритетов.

2. Решите задачу из упражнения 8.1.1, используя следующую иерархию приоритетов частных целевых функций: G, у G2 у G3 у GA.

3. Вернитесь к задаче из упражнения 8.1.2. Пусть частные целевые функции, описывающие количество привлеченных посетителей подросткового, среднего и старшего возрастов, обозначаются соответственно G,, G2 и G,. Решите эту задачу при следующих иерархиях приоритетов частных целевых функций:

a) G,yG2y G3,

b) G3y G2y <?,.

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

ЛИТЕРАТУРА

1. Cohon Т. L. Multiobjective Programming and Planning. Academic Press, New York, 1978.

2. Ignizio J. P., Cavalier T.M. Linear Programming. Prentice-Hall, Upper Saddle River, NJ, 1994.

3. Steuer R. E. Multiple Criteria Optimization: Theory, Computations, and Application, Wiley, New York, 1986.

Литература, добавленная при переводе

1. Поляк Б. Т. Введение в оптимизацию. - М.: Наука, 1983.

2. Поспелов Г. С, Ириков В. А. Программно-целевое планирование и управление. - М.: Сов. радио, 1976.

3. Соболь И. М., Статников Р. Б. Выбор оптимальных параметров в задачах со многими критериями. - М.: Наука, 1981.

4. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. - М.: Наука, 1986.

КОМПЛЕКСНЫЕ ЗАДАЧИ

8.1. 1 Лесозаготовительная компания использует три участка леса площадью 100 ООО, 180 ООО и 200 000 акров для заготовки древесины и последующих лесопосадок. Древесная продукция компании разбита на три основные категории: пиломатериал, клееная фанера и древесная измельченная масса. Для каждого участка лесного массива возможны различные альтернативные варианты его эксплуатации, которые различаются стоимостью разработок, арендной платой, периодом чередования вырубок и лесопосадок, объемом произведенной продукции. Эти альтернативы показаны в следующей таблице.

1 Задача основана на материалах статьи Rustagi К.Р. Forest Management Planning for Timber Prodaction: A Goal Programming Approach, Bulletin No. 89, Yale University, New Haven, 1976.



долл. в год/акр Период м3 в год/акр

Участок Альтернатива Стоимость Аренда чередова- Пиломатериалы Фанера Древесная

ния (годы) масса

1000

1500

1200

1300

1200

1500

1000

1500

1200

1300

1200

1000

1500

1200

1300

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

Компания преследует следующие цели.

Ежегодное производство пиломатериалов, фанеры и древесной массы должно быть не менее 200 000,150 000 и 350 000 кубических метров соответственно.

1. Ежегодный бюджет на восстановление леса составляет 2,5 млн. долл.

2. Ежегодная арендная плата должна составлять 100 долл. за акр.

Какой вариант эксплуатации для каждого участка леса следует выбрать?

8.2. Благотворительная организация помогает детскому приюту. Для этого она привлекает волонтеров ежедневно с 8 до 14 часов. Волонтеры могут начать работу в любое время с 8 до 11 часов. Длительность работы волонтера не более 6 и не менее 2 часов. С 12 до 13 часов обеденное время. Благотворительная организация считает, что в приюте ежедневно необходимо 15 волонтеров для работы с 8 до 9, 16 волонтеров - с 9 до 10, 18 волонтеров - с 10 до 11, 20 волонтеров - с 11 до 12 и 16 волонтеров - с 12 до 14 часов (но это работа на один час, так как с 12 до 13 обеденное время). Здесь частными целевыми функциями могут быть волонтеры (т.е. их количество), работающие в течение каждого часа с 8 до 14. Цель всей задачи - определить количество волонтеров, приступающих к работе в начале каждого часа, и длительность их работы. Сформулируйте и решите эту задачу как задачу целевого программирования.



ГЛАВА 9

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

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

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

9.1. ПРИМЕРЫ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

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

Пример 9.1.1. Распределение капиталовложений

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

Проект

Расходы (млн. долл./год)

Прибыль

1 -й год

2-й год

3-й год

(млн. долл.)

Доступный капитал 25 25 25

(млн. долл.)

[Старт] [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]