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


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


121

Предположим, что оптимальное решение задачи ЛП представлено следующим образом.

Максимизировать z = с0 - (г, - с;)х]

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

х, = х - o:irr;, i = 1, 2,т, все jc, и х > О,

где - множество индексов небазисных переменных. Предположим, что на текущую базисную переменную х, = х налагается ограничение х. > dt, где

dt - наименьшее целое, большее х]. После введения этого ограничения

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

Рассмотрим следующую задачу линейного программирования.

Минимизировать z = (10i - 4) х, + {At - 8) х2 при ограничениях

2хх + 2х2 + х3 = 8, Axl + 2x2 + xi = 6-2t, x], х2, Х3, х4 О,

где -оо < t < оо. С помощью параметрического анализа получены следующие результаты:

при -°° < t < -5 оптимальный базис: В = (Р,, Р4), при -5 < t < -1 оптимальный базис: В = (Р,, Р2), при -1 < t < 2 оптимальный базис: В = (Р2, Р3).

Найдите все критические значения параметра t при t > 2.



ГЛАВА 8

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

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

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

8.1. ФОРМУЛИРОВКА ЗАДАЧИ ЦЕЛЕВОГО ПРОГРАММИРОВАНИЯ

Рассмотрим пример, приводящий к задаче целевого программирования.

Пример 8.1.1

Файрвилл - небольшой городок, в котором проживает около 20 тысяч жителей. Предположим, городской совет разрабатывает ставки местного налогообложения. Ежегодная база налогообложения недвижимости составляет 550 миллионов долларов. Ежегодная база налогообложения розничных и оптовых продаж составляет 35 и 55 миллионов долларов соответственно. Ежегодное потребление городом бензина оценивается в 7,5 миллионов галлонов. Городской совет планирует разработать систему налоговых ставок, основанную на перечисленных базах налогообложения и учитывающую следующие ограничения и требования.

1 Задачи целевого программирования являются только подклассом задач, решаемых методами многокритериальной оптимизации. Подходы и методы, применяемые в многокритериальной оптимизации, отнюдь не исчерпываются теми методами, которые описаны в этой главе (см. список литературы в конце главы). - Прим. ред.



1. Налоговые поступления должны составить не менее 16 миллионов долларов от всех баз налогообложения.

2. Налог с розничных продаж не может превышать 10% от суммы всех собираемых налогов.

3. Налог с оптовых продаж не может превышать 20% от суммы всех налогов.

4. Налог на бензин не может превышать 2 центов за галлон.

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

550ад + 35хр + 55л0 + 0,075х„ > 16 (суммарные налоговые поступления) 35хр < 0,1(550хи + 35лр + 55х0 + 0,075*,,) (налог на розничную торговлю) 55хс < 0,2(550хн + 35хр + 55хо + 0,075х„) (налог на оптовую торговлю) хе < 2 (налог на бензин) *„> V л-„, х6 > 0.

После упрощения получаем три ограничения.

550х„ + 35хр + 55х0 + 0,075хб > 16, 55х„ - 31,5дгр + 5,5л:,, + 0,0075*,, > 0, 110лг„ + 7хр - 44*„ + 0,015дг9 > 0. хб<2,

*„> х„, х0, хб > 0.

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

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

ЬЪ0хн + ЗЪхр + ЬЬх0 + 0,075хе + 5,+ - j" = 16, 55x„ - 31,5хр + 5,5х0 + 0,0075х„ + - s; = 0, 110х„ + 7хр - 44хо + 0,015хв + s$ - s3 = 0. хб + s* - s; = 2, xH,xp,xo,xe>0, s*, s~ >0, i=l,2, 3,4.

Неотрицательные переменные s* и s7 называются отклоняющими, поскольку они

показывают отклонение значений левых частей ограничений от соответствующих величин правых частей этих же ограничений.

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