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


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


124

3. Пусть в задаче о приеме студентов на первый курс университета (см. упражнение 8.1.3) ограничение, касающееся общего количества принятых первокурсников, должно быть выполнено обязательно, остальные ограничения не являются жесткими. Кроме того, считаем, что ограничение на средний балл ACT в два раза важнее, чем остальные ограничения. .

a) Решите данную задачу и проверьте, все ли частные целевые функции достигнут своего оптимума.

b) Пусть ограничение на количество принятых первокурсников не является жестким, но все равно имеет в два раза важнее, чем ограничение на средний балл ACT. Как в этом случае изменится решение?

4. Можно ли в условиях задачи из упражнения 8.1.4 удовлетворить всем требованиям рационального питания?

5. Найдите решение задачи из упражнения 8.1.5 и определите, можно ли сбалансировать ежедневное производство колес и сидений.

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

7. В задаче из упражнения 8.1.7 производственные квоты должны быть реализованы в любом случае; при необходимости можно использовать сверхурочные работы. Найдите решение этой задачи и определите объем сверхурочных работ, если они используются.

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

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

Возраст (года)

Образование (года)

Опыт (года)

Заработок (долл.)

40 ООО

48 ООО

38 ООО

36 ООО

41 ООО

Используя формулировку задачи целевого программирования из упражнения 8.1.10, постройте уравнение линейной регрессии у - b0 + bxxx + Ьгх2 + Ь3хъ на основе данных этой таблицы.

10. Решите предыдущую задачу, используя условие Чебышева из упражнения 8.1.11.



8.2.2. Метод приоритетов

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

минимизировать G, = pi (наивысший приоритет),

минимизировать Gn = рп (наинизший приоритет). Переменные $ - это компоненты отклоняющих переменных, т.е. или s~, которые определяют i-ю целевую функцию. Например, в задаче из примера 8.2.1 А = si и А = *2 •

В методе приоритетов поочередно решаются задачи с одной целевой функцией, начиная с задачи с целевой функцией Gv имеющей наивысший приоритет, и заканчивая задачей с целевой функцией Gn, имеющей минимальный приоритет. В процессе решения последовательных задач решение задачи с целевой функцией, имеющей более низкий приоритет, не может ухудшить полученные ранее решения задач с целевой функцией, имеющих более высокий приоритет. Это означает, что если z(G) - оптимальное значение целевой функции Gt, то для всех i > 1 оптимизация любой целевой функции Gj (j1 > i) с меньшим приоритетом не может ухудшить значение z{G).

В литературе по целевому программированию описан "специальный" симплекс-метод, который гарантирует неухудшаемость решений задач с целевыми функциями более высокого приоритета. Этот метод использует правило исключения столбцов, которое применяется для удаления из оптимальной симплекс-таблицы задачи с целевой функцией Gk небазисной переменной xf с гу - с. * 0 до начала решения задачи с целевой функцией Gk+1. Это правило распознает, что небазисная переменная х., если она получит ненулевое значение, может ухудшить (но никогда не улучшит) оптимальное значение задачи с целевой функцией, имеющей более высокий приоритет.

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

Этап 0. Определяем частные целевые функции задачи и ранжируем их в порядке приоритетов: G, = /О, >- G2 = р2 у ... >- Gn = рп. Положим 1=1.

Этап L Решаем i-ю задачу ЛП с целевой функцией G(. Обозначим через р

полученное оптимальное значение отклоняющей переменной р. Если i = п, вычисления заканчиваются, поскольку решена последняя п-я задача. В противном случае вводим в задачу новое ограничение pt = р*, тогда значение pt не сможет измениться при решении последующих задач. Полагаем i = i + 1 и повторяем этап L

Последовательное введение дополнительных ограничений вида pt = р* теоретически не так "элегантно", как правило исключения столбцов. Однако это приводит точно к такому же результату. Кроме того, обоснование введения дополнительных ограничений совершенно очевидно и понятно.

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



вычисления таким образом, чтобы это ограничение учитывалось непосредственно путем подстановки значения р вместо переменной р, что также уменьшает количество переменных в задаче. (Можно также использовать метод решения задач ЛП с ограниченными переменными из раздела 7.3 для выполнения замены р = р*,

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

Пример 8.2.2

Решим методом приоритетов задачу из примера 8.2.1. Предположим, что наибольший приоритет имеет частная целевая функция, соответствующая условию, налагаемому на объем рекламной аудитории. Этап 0. G, >- G2, где

G,: минимизировать s* (условие по рекламной аудитории), G2: минимизировать s, (условие по бюджету). Этап 1. Решаем первую задачу ЛП.

Минимизировать G, = s* при выполнении ограничений

4jc, 4- 8jc2 4- j* - j" = 45 (условие по рекламной аудитории),

8х, 4- 24jc2 100 (условие по бюджету),

л:, 4- 2jc2 < 10 (ограничение по рекламным агентам), jc, < 6 (ограничение на рекламу по радио), xx,xv s*, j~ , j2 , s; >0.

Оптимальное решение этой задачи (найденное с помощью программы TORA) составляет хх = Ъ минут, дг2 = 2,5 минуты, s{ =5

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

В этой задаче мы имеем рх = s[. Поэтому в следующей задаче добавим ограничение s* = 5.

Этап 2. Теперь необходимо решить вторую задачу ЛП. Минимизировать G2 = sl

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

задачу, используя, как и на предыдущем этапе, программу TORA, и добавив с помощью опции MODIFY (Изменить) новое ограничение.

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