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


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


7

2.2. Графическое решение задачи линейного программирования 2.2.1. Нахождение максимума целевой функции

Пример 2.2.1

Мы используем модель, построенную для компании Reddy Mikks в разделе 2.1, чтобы показать два этапа графического решения задачи ЛП.

Этап 1. Построение пространства допустимых решений.

Сначала проведем оси: на горизонтальной будут указываться значения переменной xlt а на вертикальной - хг (рис. 2.1). Далее рассмотрим условие неотрицательности переменных: л, > 0 и х2 > 0. Эти два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте (т.е. выше оси х1 и правее оси х2).

Чтобы учесть оставшиеся ограничения, проще всего заменить неравенства на равенства (получив уравнения прямых), а затем на плоскости провести эти прямые. Например, неравенство 6х1 + 4х2 < 24 заменяется уравнением прямой 6х, + 4х2 = 24. Чтобы провести эту линию, надо найти две различные точки, лежащие на этой прямой. Если х, = 0, то х2 = 24/4 = 6. Аналогично для х2 = 0 находим х1 = 24/6 = 4. Итак, наша прямая проходит через две точки (0, 6) и (4, 0). Эта прямая обозначена на рис. 2.1 как линия (1).

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

Ограничения:

Рис. 2.1. Пространство допустимых решений модели



неравенству, а какого - нет, может служить точка (0, 0). Например, эта точка удовлетворяет первому неравенству 6xt + 4х2 < 24 (здесь 6х0+4х0=0< 24). Это означает, что точки полупространства, содержащего начальную точку (0, 0), удовлетворяют этому неравенству. На рис. 2.1 допустимые полупространства показаны стрелочками.

Если точка (0, 0) не удовлетворяет неравенству, допустимым полупространством будет то, которое не содержит эту точку. Если же прямая проходит через эту точку, следует в качестве "тестовой" взять какую-либо другую точку.

Этап 2. Поиск оптимального решения.

Точки пространства допустимых решений, показанного на рис. 2.1, удовлетворяют одновременно всем ограничениям. Это пространство ограничено отрезками прямых, которые соединяются в угловых точках Л, В, С, D, Е и F. Любая точка, расположенная внутри или на границе области, ограниченной ломаной ABCDEF, является допустимым решением, т.е. удовлетворяет всем ограничениям. Поскольку пространство допустимых решений содержит бесконечное число точек, необходима некая процедура поиска оптимального решения.

Для того чтобы найти оптимальное решение, необходимо определить направление возрастания целевой функции z = 5х1 + 4х2 (напомним, что функцию z следует максимизировать). Мы можем приравнять z к нескольким возрастающим значениям, например 10 и 15. Эти значения, подставленные вместо z в выражение целевой функции, порождают уравнения прямых; для значений 10 и 15 получаем уравнения прямых 5х, + 4х2 = 10 и 5xj + 4х2 = 15. На рис. 2.2 эти прямые показаны штриховыми линиями, а направление возрастания целевой функции - жирной стрелкой.2 Целевая функция может возрастать до тех пор, пока прямые, соответствующие возрастающим значениям этой функции, пересекают область допустимых решений. Точка пересечения области допустимых решений и прямой, соответствующей максимально возможному значению целевой функции, и будет точкой оптимума.

На рис. 2.2 видно, что оптимальное решение соответствует точке С. Эта точка является местом пересечения прямых (1) и (2), поэтому ее координаты хх и х2 находятся как решение системы уравнений, задающих эти прямые:

6х, + 4х2 = 24,

Xl + 2x2 = 6.

Решением этой системы будет xt = 3 и х2= 1,5, при этом значение целевой функции равно z = 5x3 + 4x1,5 = 21. Полученное решение означает, что для компании Reddy Mikks оптимальным выбором будет ежедневное производство 3 т краски для наружных работ и 1,5 т - для внутренних работ с ежедневным доходом в 21 000 долл.

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

Направление изменения целевой функции легко определить из вида целевой функции: коэффициенты при переменных х1и хг - это координаты нормали к прямой, определяемой целевой функцией. В данном случае целевая функция будет изменяться в направлении вектора (5; 4). - Прим. ред.



Рис. 2.2. Оптимальное решение модели

УПРАЖНЕНИЯ 2.2.1

1. Для каждого из следующих неравенств определите допустимое полупространство, предполагая, что xlt х2 > 0:

a) -Зл:, + х2 < 6;

b) х1-2х2>5;

c) 2х1-3х2<12;

d) х1 - х2 < 0;

e) -я, + х2 > 0.

2. Определите направление возрастания целевой функции z в следующих случаях:

a) максимизировать z - x1 - х2;

b) максимизировать z = -5х1 - 6хг;

c) максимизировать z = -хг + 2х2;

d) максимизировать z = -3xt + х2.

3. В рамках модели компании Reddy Mikks постройте пространство допустимых решений и найдите оптимальное решение, учитывая (независимо) следующие условия.

a) Ежедневный объем производства краски для наружных работ не должен превышать 2,5 т.

b) Ежедневный объем производства краски для внутренних работ должен быть не менее 2 т.

c) Ежедневный объем производства краски для внутренних работ должен превышать ежедневный объем производства краски для наружных работ ровно на одну тонну.

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