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


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


15

определению обратной матрицы имеем: при iea Д=0, если j о

= 1. Обозначим вектор АЬ через =(ДоАо-..,>то) • Тогда система уравнений А~Ах = А~Ь имеет вид:

jeo)

При умножении на невырожденную матрицу множество решений системы уравнений не меняется, отсюда нетрудно показать, что J3y =аус для BCQxi,j.

Рассмотрим поведение целевой функции Х задачи линейного

программирования на множестве допустимых решений, заданных ограничениями вида Ах = Ь . Для этого введем дополнительную переменную Xq и рассмотрим систему уравнений.

Ах = Ь.

Применяя метод Жордана-Гаусса, можно эту переменную включить в состав базисных переменньос. Если сг = {/,,/2,...,г,„} - список базисных

переменных для уравнения Ах = Ь и уже найдена соответствующая приведенная система (считаем, что ранг матрицы А равен т), то для нахождения приведенной системы, соответствующей списку {О,/,,/2,...,/,„}

нужно выразить переменную через небазисные

j=lie<Tieo)

Подставляя в это выражение значения базисных переменных Х, i € а, получим:

/естjeo) iea

Используя введенный выше вектор , заметим, что

/ест



Далее, если ввести обозначение ТО приведенная система уравнений примет вид

(3.0)

jeo)

jeo)

Данное представление в дальнейшем будет использовано при описании алгоритма симплекс-метода.

3.2. Геометрическая интерпретация симплексного метода

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

В предыдущий главе было показано, что если задача линейного программирования имеет решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает по крайней мере с одним из допустимых базисных решений системы ограничений. Поэтому для решения задачи линейного программирования необходимо перебрать конечное число базисных решений, выбрать среди них то, на котором целевая функция принимает экстремальное значение. Геометрически это соответствует перебору всех угловых (крайних) точек многогранника. Если оптимальное решение существует, то такой перебор приведет к нахождению оптимального решения. Такой прямой перебор связан с очень большим числом вычислений. Как будет показано в гл. 12, рост объема вычислений происходит экспоненциально вместе с ростом размерности задачи. Число перебираемых допустимых базисных решений можно сократить, если производить перебор не произвольно, а добиваясь того, чтобы каждое последующее решение было не хуже пре-



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

Пусть область допустимых решений изображается многоугольником.

Рис. 3.1

Необходимо решить задачу максимизации линейной целевой функции F на множестве, заданном многогранником ABCDEFGH. Пусть угловая точка В соответствует исходному допустимому базисному рушению.

Симплексный метод состоит из трех основных элементов:

1)Определение первоначального базисного решения

2)Правила перехода к следующему лучшему решению

3)Проверка оптимальности решения.

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

Идея последовательного улучшения решения легла в основу наиболее часто применяемого метода решения задач линейного программирования.

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

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