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


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


125

Но в данном случае в решении второй задачи нет необходимости, поскольку уже в решении первой имеем 5," = 0. Следовательно, решение первой задачи автоматически является оптимальным решением второй (можете проверить это утверждение с помощью программы TORA). Решение s, = 0 показывает, что ограничение, касающееся бюджета рекламной компании, выполняется.

Дополнительное ограничение 5* = 5 можно также учесть путем подстановки значения 5 вместо переменной 5* в первое ограничение. В результате правая часть этого неравенства изменится со значения 45 на 40. Получим следующую задачу ЛП.

Минимизировать G2 = s2~ при ограничениях

4*! + 8х2 - s; = 40,

8х1 + 24х2 + 5,* - s; = 100, хг + 2х2 < 10,

xi> X2j 5j , 5, , 5т 0.

В новой формулировке этой задачи на одну переменную меньше, чем в первой задаче.

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

Пример 8.2.3

Цели, поставленные в задаче из примера 8.2.2, можно переформулировать следующим образом.

Цель 1. Максимизировать объем рекламной аудитории (/>,).

Цель 2. Минимизировать стоимость рекламной кампании (Р2).

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

Максимизировать />, = 4х, + 8х2, минимизировать Р2 = 8х, + 24х2.

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

Получили новую задачу.

Максимизировать Р1 = 4х1 + 8х2, минимизировать Р2 = 8хг + 2Ах2



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

х, + 2хг < 10,

л-,<6,

х„х2>0.

Сначала решим эту задачу с помощью процедуры, описанной в примере 8.2.2. Этап 1. Решаем первую задачу ЛП.

Максимизировать />, = 4х, + 8хг

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

х, + 2х2<10,

хх<&,

х„х2>0.

Оптимальное решение этой задачи (полученное с помощью программы TORA) составляет х, = 0, х2 - 5 и />, = 40. Отсюда видно, что объем рекламной аудитории не может превысить 40 миллионов человек.

Этап 2. Добавим ограничение 4jc1 + 8х2 > 40, которое гарантирует, что решение, полученное на предыдущем этапе, не будет ухудшено, и решаем следующую задачу ЛП.

Минимизировать/5,, = 8*, + 24х,

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

дг, + 2х2 < 10, х,<6,

4jc, + 8х2 > 40, xvx2>0.

Программа TORA дает следующее оптимальное решение этой задачи: Р2 = 96 000 долл., дг, = 6 минут и х2 = 2 минуты. Мы получили тот же объем рекламной аудитории (Р, = 40 млн. чел.), но за меньшую стоимость. Это результат того, что здесь мы искали оптимальные значения соответствующих величин, а не просто удовлетворяли ограничениям, как в примере 8.2.2.

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

Первая задача ЛП. Максимизация объема рекламной аудитории. При решении этой задачи симплекс-таблица содержит строки, соответствующие как целевой функции />,, так и целевой функции Р2. Строка целевой функции Р2 пока играет пассивную роль, но будет изменена перед решением второй задачи ЛП.

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

Нижняя часть этой таблицы показывает оптимальное решение д:, = 0, х2 = 5 и Рх = 40 первой задачи.



Итерация

Базис

Решение

1 -4

ч. 1/2 •

Правило исключения столбцов применяется перед решением второй задачи для удаления из симплекс-таблицы с оптимальным решением первой задачи небазисной переменной хр для которой г1 - Cj Ф 0. Такие переменные, приняв положительные значения в задаче с более низким приоритетом, ухудшают решение задач с более высоким приоритетом.

Вторая задача ЛП. Минимизация стоимости рекламной кампании. Правило исключения столбцов удаляет переменную s,, для которой г, - сг = 4. Из Р2-строки приведенной выше симплекс-таблицы видно, что если не удалить переменную s,, то на первой итерации решения второй задачи она должна войти в базис, при этом из базиса будет исключена переменная х2. После этого будет получено оптимальное решение второй задачи (в этом решении хх = х2 = 0), которое ухудшает оптимальное решение первой, поскольку теперь Р, = 0 вместо Р, = 40, как было ранее.

В данном случае вторая задача ЛП является задачей минимизации. После удаления переменной 5, в базис вводится небазисная переменная х, со значением разности Zj - сг равным 4 (> 0), что может улучшить значение целевой функции Р2. В следующей симплекс-таблице показаны две итерации решения второй задачи ЛП. Р,-строку можно удалить из этой таблицы, так как она не участвует в процессе поиска оптимального решения задачи с целевой функцией Р2.

Итерация Базис Xi хг Si вг Решение

Pi 40

1 -V-P- 4 0 0 120

х2 1/2 1 0 5

s2 1 0 16

Pi 40

2 Р2 0 0 -4 96 х2 0 1 -1/2 2 Xi 1 0 16

Полученное здесь оптимальное решение (х, = 6, х2 = 2) со значениями целевых функций Р, = 40 и Р2 - 96 такое же, как и полученное ранее.

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