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


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


28

она имеет только одно решение3; если же т< пи система уравнений совместна, то она имеет бесконечное множество решений. Простая иллюстрация в качестве доказательства: для уравнения х = 2 имеем т = п = 1, а его решение, очевидно, единственное. Для уравнения х + у = 1 имеем т - 1 и п = 2, этому уравнению удовлетворяет бесконечное множество решений (любая точка на прямой х + у=1 будет решением).

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

Следующий пример иллюстрирует это положение.

Пример 3.2.1

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

Максимизировать z= 2хх + Зх2

при выполнении условий

2.v,+x,<4, хх + 2х.г < 5, xltx2>0.

На рис. 3.2 показано пространство решений для этой задачи. х2

0 1 2 3 4 5

Рис. 3.2. Пространство решений для примера 3.2.1

Это не совсем верно: совместная система уравнений имеет единственное решение тогда, когда она невырождена. - Прим. ред.



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

Максимизировать z = 2хх + Зхг

при выполнении условий

2дг, + х2 + s, = 4, я, + 2хг + s2 = 5,

*2* 1 2 - *

Здесь имеем систему из т = 2 уравнений для л = 4 переменных. Согласно сформулированному выше правилу угловые точки можно определить алгебраически, присвоив я-т = 4- 2 = 2 переменным нулевых значений и решив затем систему уравнений относительно оставшихся т = 2 переменных. Если, например, положить х1 = 0их2 = 0, тогда решением системы будет s, = 4, s2 = 5. Это решение соответствует точке Л на рис. 3.2 (убедитесь, что решение 5, = 4, s2 = 5 действительно соответствует точке А). Другую угловую точку можно определить, если положить s, = 0 и 52 = 0. В этом случае надо найти решение системы

2хх + х2 = 4,

л-! + 2д-2 = 5.

Решением в данном случае будет jt, = 1 и х, = 2, что соответствует точке С на рис. 3.2.

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

В нашем примере мы имеем = "Tj= Угловых точек. Но, глядя на рис. 3.2,

можно насчитать только 4 угловые точки -А, В, С nD. Где "спрятались" еще две точки? В действительности точки Е и F также являются угловыми точками, но это недопустимые угловые точки, поскольку они не удовлетворяют всем ограничениям задачи. Такие недопустимые угловые точки не рассматриваются как кандидаты на оптимальное решение.

Для полного перехода к алгебраическому методу решения задач ЛП необходимо как-то назвать угловые точки разного типа на "алгебраическом" языке. На этом языке п - т переменные, которые полагаются равными нулю, называются небазисными переменными. Если оставшиеся т переменные имеют единственное решение, то в этом случае они называются базисными переменными, а совокупность значений, которые они получают в результате решения системы уравнений, составляют базисное решение (см. рис. 3.1). Если при этом все переменные принимают неотрицательные значения, то такое базисное решение является допустимым. В противном случае - недопустимым.4

i В русскоязычной математической литературе также применяются термины "план", "опорный план" и "оптимальный опорный план" как эквиваленты для терминов "базисное решение" , "допустимое базисное решение" и "оптимальное базисное решение". - Прим. ред.



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

Небазисные

Базисные

Базисные

Соответствующие

Допустимо

Значение

(нулевые)

пере-

решения

угловые точки

ли решение?

целевой

переменные

менные

функции z

(*, х2)

(Si, 8г)

(5, 4)

(*г, 8г)

(4, -3)

(X1. s2)

(*г, Si)

(2,5, 1,5)

(*2, Si)

(*1, S2)

(2, 3)

(*2, S2)

(*1, Si)

(5, -6)

(Si, «г)

(Xi, x2)

(1,2)

8 (оптимум)

Как видно из примера 3.2.1, при возрастании размера задачи (т.е. при увеличении значений пит) процесс перечисления всех угловых точек становится отдельной чрезвычайно сложной задачей. Например, при п = 20 и т = 10, когда необходимо решить С°0 = 184756 систем уравнений порядка 10x10, получаем устрашающую, в вычислительном отношении, задачу. Здесь следует учесть, что задачи ЛП размерности 10x20 считаются небольшими - реальные задачи могут иметь сотни и даже тысячи переменных и ограничений. Однако симплекс-метод в значительной степени снимает эту проблему, поскольку он рассматривает не все возможные базисные решения (т.е. угловые точки пространства решений), а только часть всех допустимых базисных решений.

УПРАЖНЕНИЯ 3.2

1. Проверьте все базисные и небазисные решения, приведенные в конце примера 3.2.1.

2. Дана следующая задача ЛП.

Максимизировать z = 2хх + Зх2

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

+ Здс2 < 6, Зх1 + 2хг<6, xv хг>0.

a) Запишите задачу в стандартной форме.

b) Найдите все базисные решения этой задачи и определите, какие из них допустимые, а какие - нет.

c) Путем непосредственной подстановки решений в целевую функцию определите наилучшее допустимое базисное решение.

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

e) Определите, чему на рисунке, где представлено пространство решений, соответствует недопустимое базисное решение.

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