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


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


24

Рассмотрим еще одну процедуру нахождения начального опорного решения (допустимого базисного решения), особенность которой состоит в том, что она использует симплекс-метод. Будем считать, что в системе уравнений Ах = Ь, bi>0, (i= \, ..., т), а если это не так, то соответствующее уравнение умножается на Далее, считая, что 7>0, рассмотрим каноническую задачу линейного программирования сп + т переменными:

max(-K,-F2-...-FJ

F2 + а.х, + 222 +... + а2„х„ = 2(3 32)

Xj>0;j = l 2,...,«;Р>0,/=:1, 2,...,/w.

Исследуем связь между задачей (3.31) и задачей (3.32). Задача (3.32) имеет непустое множество допустимых решений. Например, вектор (Z)i,..., bm, О, 0,...,0) является допустимым для задачи (3.32) Кроме того, целевая функция этой задачи ограничена сверху числом «О» и, следовательно, задача (3.32) имеет решение. Пусть d- значение целевой функции задачи (3.32) на оптимальном решении. Тогда возможны случаи, когда О, rf<0.

Теорема 3,2, Если оптимальное значение d задачи (3.32) равно нулю, то задача (3.31) имеет решение. Если < О, то задача (3.31) не имеет допустимых решений [6].

Доказательство, Пусть задача (3.31) имеет решение х = (x°i,Д). В этом случае п + /w-мерный вектор х = (О, О, О, хь х„) удовлетворяет всем ограничениям задачи (3.32) и является ее допустимым решением, и при этом значение целевой функции на решении равно нулю. Отсюда следует, что х решение оптимально для (3.32) и d = О, С другой стороны, если d=0,TO для любого решения (Fi, ..., F;;, xi, Х2,..., х„) задачи (3.32) V\Vi = V2 = ,,. = Уггг = О, и следовательно, вектор (xi,Х2,..., х„) - план задачи (3.31). Теорема доказана.

Из доказанной теоремы следует, что в результате решения вспомогательной задачи (3.32) либо будет определено решение задачи (3.31), либо выяснится, что система ограничений задачи (3.31) противоречива, т.е. множество допустимых решений задачи пусто. Основным свойством задачи (3.32) является то, что для нее можно сразу определить начальное допустимое базисное решение. Таким решением является п + /w-мерный вектор (6,0)= фи Ьт, О, О, ...,0). Нетрудно убедиться, что (Ь, 0)- строго допустимый план.



Действительно,

OLxo = (bu 1,0, ...,0, aii,ai2,

а20 = (Ь2, О, 1, ...,0, 21, «22, ...,«2п) CLmO = (bm, О, О, \,amU ...,«тД

Поскольку bj> о, / = 1,2, m, то первая ненулевая координата в каждом векторе положительна, то есть а/> О, / = 1,2,т.

3.6. Неединственность оптимального решения

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

Пусть необходимо решить задачу определения максимума следующей целевой функции:

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

+ < 8; 2Xj - > 1; - 22 < 2; > 0; х > 0.

Используя геометрический способ решения этой задачи, получим, что линия уровня, задающая максимальное значение целевой функции, совпадает с граничной линией АВ многоугольника решений ABCD, то есть с линией лг + х = 8.

Рис, 3J

Следовательно, на всем отрезке АВ линейная функция принимает одно и то же максимальное значение равное 3(Xj + х) = 3 • 8 « 24.



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

На очередном шаге получаем: основные переменные х, х, х. неосновные переменные х, х

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

2 1

Х5 =9-Хз -Х4.

= (3; 5; 0; 0; 9) - допустимое базисное решение, соответствующее угловой точке = (3; 5). Линейная целевая функция в этом случае равна F= 24-х.

В выражении для F отсутствуют положительные коэффициенты при неосновных переменных и, следовательно, критерий оптимальности выполняется, а поэтому Х оптимальное базисное решение, Fax = Я 1 ) = 24. В целевую функцию F основная переменная х входит с нулевым коэффициентом, и поэтому изменение этой переменной не повлечет за собой изменение целевой функции. Переводя в основные переменные переменную х = min {15,00,9} = 9, а в неосновные, как следует из последнего выражения для х, переменную х получим, что изменения

целевой функции не произойдет AF = 9 • О = 0. Это следует из того, что на следующем шаге получим новое базисное решение Х2 = (6; 2; 0; 9; 0), соответствующее угловой точке В = (6; 2),

тах= (2 ) = 24. Учитывая, что переменная х = О, а переменная х = 9 удовлетворяет неравенству О < х < 9, из системы уравнений можно получить все множество оптимальных решений задачи. Положим, например, х = t, где t е [0;9]. Тогда множество оптимальных решений

1 X, =3 + -Г 3

2=5-1/ (Гб[0;9])

Хз = О, Х4 = Г Хз = 9 +

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