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


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


123

Ежедневная квота на производство первого и второго изделий составляет соответственно 80 и 60 единиц. На выполнение каждой операции отводится по 8 часов в рабочий день. Сверхурочные работы не желательны, хотя при необходимости, чтобы выполнить производственный план, их можно применять. Сформулируйте задачу целевого программирования.

8. Городская больница планирует организовать для больных кратковременный (до 4 дней) стационар на свободных местах. Предполагается, что в течение 4-дневного периода будет 30, 25 и 20 больных, которым потребуется 1-, 2- и 3-дневный стационар. Также рассчитано, что на тот же период будет свободно 20, 30, 30 и 30 мест соответственно. Используйте целевое программирование, чтобы вычислить максимальное и минимальное количество больных, которых можно принять на кратковременное лечение.

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

а) новый дом должен быть как можно ближе к месту работы м-ра Траппа (в пределах четверти мили),

б) дом должен быть как можно дальше от шумного аэропорта (не ближе 10 миль),

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

Для решения своей задачи супруги нанесли на карту города координатную сетку и пометили место работы, аэропорт и супермаркет. Получили следующие их координаты: место работы- (1, 1), аэропорт- (20,15), супермаркет - (4, 7) (все расстояния приведены в милях). Сформулируйте задачу целевого программирования. (Примечание. Ограничения не обязательно должны быть линейными.)

10. Регрессионный анализ. Предположим, что в лабораторном эксперименте каждому значению yt независимого параметра у соответствует л измерений х , i=l,2, т, j = 1, 2, л, зависимой величины х. Требуется построить линию регрессии, проходящую через экспериментальные точки. Обозначим через bJt j = 0, 1, л, коэффициенты уравнения регрессии. Коэффициенты Ь; находятся из условия минимума суммы абсолютных значений разностей наблюдаемых и расчетных (т.е. рассчитанных на основании уравнения регрессии) значений зависимой величины. Сформулируйте эту задачу в виде модели целевого программирования.

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

8.2. АЛГОРИТМЫ ЦЕЛЕВОГО ПРОГРАММИРОВАНИЯ

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



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

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

8.2.1. Метод весовых коэффициентов

Предположим, что модель целевого программирования имеет п целей следующего вида.

Минимизировать Gt, £ = 1,2,п.

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

Минимизировать г = m;,G1 + w2G2 + ... + wnGn.

Здесь wl(i= 1, 2, п)- положительные весовые коэффициенты, которые отображают предпочтения, отдаваемые каждой цели. Например, вариант ш, = 1 для всех i говорит о равнозначности всех целей. Задание значений весовым коэффициентам очень субъективно. В настоящее время разработаны различные методы (см. [1]), которые уменьшают субъективный фактор при определении весовых коэффициентов.

Пример 8.2.1

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

Радио

Телевидение

Рекламная аудитория (млн. чел.)

Стоимость (тыс. долл.)

Количество рекламных агентов

Реклама на радио и телевидении должна охватить не менее 45 миллионов человек (так называемая рекламная аудитория), но контракт запрещает использовать более 6 минут рекламы на радио. Рекламное агентство может выделить на этот проект бюджет, не превышающий 100 ООО долл. Сколько минут рекламного времени агентство должно купить на радио и сколько на телевидении?

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



Минимизировать Gl = $1 (для выполнения условия по рекламной аудитории),

минимизировать G2 = s," (для выполнения условия по бюджету)

при выполнении ограничений

4xl + 8х2 + s* - s~ = 45 (условие по рекламной аудитории),

8jc, + 24х, + s2r - = 100 (условия по бюджету),

jc, + 2jc2 < 10 (ограничение по рекламным агентам), jc, < 6 (ограничение на рекламу по радио),

1»-2* "1 "1 "2 > "2 -0.

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

Минимизировать г = 2G, + G2 = 2 s* + .

Оптимальное решение этой задачи (полученное с помощью программы TORA) следующее: z = 10, х, = 5 минут, х2 = 2,5 минуты, = 5 миллионов человек. Остальные переменные равны нулю.

Тот факт, что оптимальное значение целевой функции не равно нулю, указывает, что по крайней мере одна из исходных целевых функций не достигла своего оптимального значения. Действительно, так как s* = 5, значит, объем рекламной аудитории меньше запланированного на 5 миллионов. При этом условие по бюджету выполнено, поскольку s~ = 0.

Еще раз повторим, что методы целевого программирования позволяют получить только эффективное решение задачи, которое не всегда будет оптимальным. Например, решение = 6 и х2 = 2 дает такой же объем рекламной аудитории (4x6 + 8x2= 40 миллионов человек), но при меньшей стоимости рекламной кампании (8x6+ 24 х 2 = 96 000 долл.). Существенно, что методы целевого программирования в общем случае не находят оптимум каждой целевой функции исходной модели. Этот "дефект" методов целевого программирования поднимает общий вопрос о "жизнеспособности" целевого программирования в качестве технологии оптимизации (дальнейшее обсуждение этого вопроса см. в примере 8.2.3).

УПРАЖНЕНИЯ 8.2.1

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

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

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