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


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


38

УПРАЖНЕНИЯ 3.5.1

1. Рассмотрите графическое представление пространства решений (рис. 3.10). Предположим, что выполнение симплекс-метода начинается из точки А, оптимальное решение соответствует точке D, а целевая функция такова, что в точке А вводимой переменной будет х,.

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

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

2. Покажите (графически и с помощью TORA), что следующая задача имеет временно вырожденные решения.

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

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

3. Используя в программе TORA опции, позволяющие управлять процессом вычислений, выполните последовательность симплекс-итераций в следующей задаче ЛП (задача придумана Е. М. Beale). Начальное допустимое базисное решение, состоящее из дополнительных переменных, повторится на седьмой итерации. Этот пример иллюстрирует явление зацикливания при выполнении симплекс-метода; в этом случае оптимальное решение никогда не будет достигнуто.

Рис. 3.10. Пространство решений для упражнения 1

4х, + 3х2<12, 4х, - х2< 8, 4х,+ х2<8, х,, х2>0.

Максимизировать z

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

8х2 - х3 + 9х4 < 0,

12х,

>--х* + Зх. < 0.

2 2



х,<1,

Х2> 3 Х4 ~

Интересно отметить, что если сделать все коэффициенты в этой задаче целыми (путем умножения на соответствующие множители), то алгоритм симплекс-метода достигнет оптимального решения за конечное число итераций (проверьте это!).

(Предостережение. Не используйте программу TORA в автоматическом режиме, так как в этом случае циклические вычисления будут выполняться бесконечно.)

3.5.2. Альтернативные оптимальные решения

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

Пример 3.5.2. Бесконечное множество решений

Рассмотрим следующую задачу ЛП.

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

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

л-, + 2х2 < 5, х, + х,<4, xvx2>0.

На рис. 3.11 показано множество альтернативных оптимальных решений, которые являются следствием того, что прямая, представляющая целевую функцию, параллельна прямой;- соответствующей связывающему ограничению. Каждая точка отрезка ВС соответствует оптимальному решению со значением целевой функции z = 10. Последовательные итерации выполнения симплекс-метода представлены в следующей таблице.

Итерация

Базис

Решение

Начальная

Вводится хг

Исключается *з

Первая (оптимум)

Вводится Х\

Исключается хд

-1/2

Вторая

(альтернативный

оптимум)



Рис. 3.11. Альтернативные оптимумы в примере 3.5.2

На первой итерации получаем оптимальное решение х, = 0, х2 = 5/2 и z = 10, которое соответствует точке В на рис. 3.11. Как узнать из симплекс-таблицы, что существует альтернативное оптимальное решение? Посмотрите на коэффициенты небазисных переменных в г-строке первой итерации. Коэффициент небазисной переменной д-, равен нулю, это означает, что данную переменную можно ввести в базис без изменения значения целевой функции, но значение самой переменной д-, изменится. Введение переменной хх в базисное решение выполнено на второй итерации, при этом из базиса исключена переменная xt. Получено новое решение х, = 3, х2 = 1, z = 10, которое соответствует точке Сна рис. 3.11.

Симплекс-метод может определить только две угловые точки В и С. Математически мы можем найти все точки (лгрдг) отрезка ВС как взвешенное среднее (с неотрицательными весами) точек В и С. Если 0 < ос < 1 и

В: х, = 0, х, = 5/2,

С. дг, = 3, х2 = 1,

координаты любой точки отрезка ВС можно записать следующим образом:

х\ = а х 0 + (1 - а) х 3 = 3 - За,

л\ = ах - + (1 - а) х 1 = 1 + - а. 2 2

При а = 0 (х\,хг) = (3, 1), что соответствует точке С. При а=1 получаем <х[,х2) = (0, 5/2) - это точка В. Если значение а лежит строго между 0 и 1, получаем внутренние точки отрезка ВС.

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

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