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


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


20

Обозначим через Bi матрицу, составленную из этих векторов, тогда Вс\ - квадратная (т + \)х(т + 1) матрица, имеющая обратную.

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

Если У"- единичный орт пространства В\ г = 0, 1, 2, т, то матрица перехода от базиса (3.11) к базису (3.20) имеет вид:

/а л

0 1/-1

e = (F,F,...,F ,

/+1т

V ,...,К).

При этом = аб- При указанной смене базиса любой вектор у е 1, координаты которого в базисе (3.11) выражались вектором z, то есть у = В, в новом базисе будет иметь координаты, описываемые

вектором Z, который легко находится подстановкой Bq = Bq\Q\ У = 5ai(6~). то есть Z = e"z.

Следовательно, новые координаты столбцов матрицы U выражаются формулами:

а>

7 = 0,1,2, ...,и.

через и ,

Обозначим матрицу, состоящую из столбцов

т.е.и =Q~U или QU =и. Чтобы явно вычислить элементы матрицы, поступим следующим образом.

Для строк матриц С/ и С/ можно написать соотношение

ao=Ul,ai=UV,i ст, / =(3.21)

Щ = и V, at= UV,aQ = U Л / е ст, / < / Ф s.(3.22)

Тогда а, - ai={U-U )V или

а/ -щ = и (Q - I)V, I = О, / е а, / = /„ / * s.

где /- единичная {т + 1)х(?и + 1) матрица. Из явного вида Q следует, что

{Gl-Dy = (<ySS\>-yi)

для любого У = (У0,У\, ...,yt, Ут) 3*

(3.23)

(3.24)



в частности

(Q-I)r=a,,Vjir,rt(3.25)

(Q-I)V=(ask-\)l(3.26)

(Q-PlVaokV.(3.27)

Используя (3.23) и (3.26), получим

as-ai, =(ask-l)UV={ask-\)a,,

откуда

OLs,(3.28)

из (3.23), (3.25) и (3.28) получим

а,- а, = a,kU V= а,,а,= а.(3.29)

В частности из(3.27) получим

. ccQ=ao-as(3.30)

Очевидно, что ask О, так как в противном случае матрица Q - вырожденная, т.е. (3.19) не базис.

Смысл преобразований (3.28)-(3.30) ясен: к i-й строке матрицы U прибавляется строка с таким коэффициентом I ask, чтобы элемент dj

стал равен нулю, после чего строку as делим на ask, добиваясь равенства

ajj = 1. В результате столбец

В матрице U оказывается ортом V

пространствакак и должно быть в симплексной таблице, так как

вектор теперь уже входит в базис и занимает в нем место с номером t.

На основании рассмотренной симплекс-таблицы, дадим описание вычислительной схемы симплекс-метода.

Пусть имеется начальная симплексная таблица С/.

Этап 1. Проверяем выполнение неравенств А, > О,у = 1,2, ..., п. Если эти неравенства справедливы, то план х, вычисляемый по формуле (3.9), - оптимален. В противном случае ищем индекс к,\<к<п, для которого Ajk< 0.

Этап 2. Проверяем выполнение неравенства < 0. Если все координаты atk вектора неположительны, то вычисления прекращаются, так 68



как исходная задача maxАх = Ь, х>0 вида не имеет решения. В

противном случае ищем такой индекс S, что аА: > О и aso I oisk cl,o I a,k для всех /, для которых aik> 0.

Этап 3. По формулам(3.28)-(3.30) строим новую симплексную таблицу и, которую принимаем за начальную и возвращаемся к этапу 1.

Последовательность выполнения этапов 1-3 называется итерацией симплекс-метода.

Подчеркнем основные свойства симплекс-метода:

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

2.Все вычисления симплекс-метода совершаются либо сравнением элементов симплексной таблицы с нулем, либо вычисление по формулам этапа

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

3.4. Выроненные задачи линейного программирования

Рассмотрим ситуацию, когда зада-

max с,х,.

Ах = Ь;

х>0(3.31)

обладает вырожденными опорными планами, что приводит к определенным трудностям. Напомним, что

Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.

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

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

При этом выбор индекса S может оказаться таким, что xs = 0. Тогда новый опорный план х\ определяемый по формулам (3.28), (3.29), совпа-

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