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


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


21

дет с планом х. При этом, естественно, значения целевой функции не улучшатся, т.е.

Zcx, = Лс,х, ,

В этой ситуации можно продолжить вычисления с вектором х\ надеясь, что в ходе очередной итерации возможно увеличить значение целевой функции, но в этом случае возникает возможность «зацикливания», т.е. перебора одного и того же набора планов х, х\..., х, и на очередной итерации происходит возврат к плану х.

Чтобы избежать проблемы зацикливания, рассмотрим следующую процедуру. Введем понятие лексикографической упорядоченности в пространстве R"\ Пусть а = (aQ aj а„) е R"\

Будем говорить, что вектор а лексикографически больше нулевого вектора О е ]\(а у 0), если аФОя первая ненулевая координата вектора а положительна, т.е. а > О, где = min у 9о.

Если а = {а а а.то будем говорить, что вектор а лексикографически больше а (а >- а), если а - а >- 0. Иными словами а у

а, если а а и а> а, где q = min j aj . Отметим два важных свойства отношения « >-»:

1)для любых двух векторов а, аеВ" имеет место одна из трех возможностей: а = а; а у а; а у а;

2)отношение « >-» транзитивно, т.е. если а у а и а у а", то а > а".

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

С этой целью усилим требования на рассматриваемые в симплекс-методе опорные планы (базисные решения).

Будем говорить, что опорный план х строго допустим, если все строки а,, / е а (кроме строки ао) симплекс-таблицы, соответствующей плану х лексикографически больше нуля: а, > 0,1 е ст. Из этого определения следует, что если базисное решение не вырождено, то оно строго допустимо в каждом векторе а,, /еа, первая координата а/о = х/ положительна.



Правило L. Если вектор ct решено ввести в базис (т.е. А < 0), то следует рассмотреть А:-й столбец ct симплекс-таблицы и все строки aj, для которых а;Р>0. Индекс S выбирается так, чтобы

-а < -а,, S, / G а sk> О, o.,k> О

и вектор выводится из базиса.

Правило L жестко определяет выбор индекса S, указывающего, какой вектор следует выводить из базиса. Иными словами, среди векторов а/ / aik имеется ровно один минимальный в смысле отношения « >-».

Действительно, все векторы а,; / в <т линейно независимы, так как ранг матрицы U равен рангу матрицы А, т.е. числу строк т.

Если предположить, что имеется два лексикографически упорядоченных вектора / ask и а, / а,:, то это означает, что / ask - ct, / atk, что противоречит линейной независимости векторов и а/

Теорема 3.1. Если действовать по Правилу L, то новый опорный план строго допустим (т.е. а- > О, iea и «о о).

Доказательство, Так как ask>0,(Xs >- О то = а/ ask >- 0. Если индекс / таков, что aik< О, то очевидно Os a/jt/ ask О и У а; > 0. Если же aik> О, то согласно правилу L а, / a;jfe Os / аь откуда I aik >- О, т.е. cci > 0. При этом ccq = ао- Akas/ask> olq, так как Ак/ask< О, то а, >- 0. Теорема доказана.

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

Действительно, пусть в процессе итеративного применения симплекс-метода возникает последовательность строго допустимых планов хх\...,х, ... Тогда по теоремеЗ.1 а\ -< а\ -< -< ао ... Поскольку отношение «>» транзитивно, то ао oto, а это означает, что ixvi ни при каком q зацикливание невозможно.

3.5. Нахождение начального допустимого базисного решения

В рассмотренных численных примерах решения задач линейного программирования симплексным методом использовалась итерацион-



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

F = x\ + 2x2 min

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

Xl-Х2 <-l;xi-Х2 >-3;xi <3;xi >0; Х2>0.

Для решения этой задачи вводятся дополнительные неотрицательные переменные хз Х4 Х5 с соответствующими знаками:

X, -Х2 +Х3 =-1 Xj - Х2 - Х4 = -3

X, +Х5 =3.

в соответствии с правилами, сформулированными при рассмотрении предьщущих примеров на шаге 1, в качестве основных возьмем дополнительные переменные.

Шаг 1. Основные переменные х, х, х Неосновные переменные х, х

Выражаем основные переменные через неосновные:

Хз =-l-Xi +Х2

Х4 = 3 + Xl - Х2

X5=3-Xi.

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

Тогда первое базисное решение =

= (0; 0; -1; 3; 3) является недопустимым.

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

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

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