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


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


18

Рассмотрим симплексный метод решения следующей задачи на минимум.

Z=\iyi+\6y2- 5уз + 2\у4 min. При ограничениях:

у,2у23у,>2 Зу,У2У,>3 у,>0, / = 1,2,3,4.

Сведем данную задачу к каноническому виду, для чего введем дополнительные переменные с отрицательным знаком, так как неравенства имеют вид « > ».

Получим систему уравнений:

у-\-2у2-Зу-у=2 Зу,-У2-у,-Уб=3.

Выберем в качестве основных переменных >з, у4, Шаг1. Основные переменные уз,У4. Неосновные переменные УиУ2,У5,Уб.

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

У,=3-Зу,-У2+Уе 2 12 1

>4 = 3-->l-->2+3>5-

Первое базисное решение Yi получим, приравняв к нулю все неосновные переменные Yi = (0; 0; 3; 2/3; 0; 0).

Учитывая, что все координаты вектора Y неотрицательны, это решение допустимо.

Выразим линейную целевую функцию Z через неосновные переменные:

г=\ух + \6у2-5уз-2\у4= 18>1+ 16>2+5(3-3>1->;2 + >б) + 2\(-у,-У2у,) = 29-4у,-Зу2-1у55уе,

Zi = OZ(ri) = 29. Значение Z=29 не является оптимальным, так как функцию Z можно уменьшить за счет перевода в основные любой из переменных у1 или у2, имеющих в выражении для Z отрицательные коэффициенты. Так как у\ имеет больший по абсолютному значению коэффициент, то переведем в основные эту переменную.



Для нее наибольшее возможное значение определяется из соотношения >i = min (1,2} =1, т.е. первое уравнение становится разрешающим.

Следовательно,>зстановится неосновной переменной, Ь2\ = -4 • 1 =-4. Шаг 2. Основные переменные y\,y. Неосновные переменные

УъУъ.Уь.Уь.

Получим после преобразований:

>i=l-3>2-J>3 + 3>6

15 111

5 4И

Z = 25--y2+-y2-lys-y6- целевая функция. При базисном

решении Y2 = (1; 0; 0; 1/3; 0; 0) получаем Z2 = 2(72) = 25; Z2-Z1 = = 25-29 = -4 = AZi.

Переменную у2 переводим в основные, так как в выражении для Z она входит с отрицательным коэффициентом. Наибольшее возможное значе-• 3] 3

ниедгттЗ.г--, поэтому второе уравнение разрешающее и у4 пе-

реходит в неосновные переменные;

AZ2= -

= -1.

ШагЗ. Основные переменные дьдг. Неосновные переменныеуз, у4, у.

Получим после преобразований

4 2 3 1 2

У1=--~Уз+-У4--У5+-Уб

3 19 3 1

У2 = 5+7>з " 5>4 +-У5--Уб-

г = 24+уз + 3у4 + 6у5 + 4уб. Базисное решение Уз = (4/5; 3/5; 0; 0; 0; 0).

Оно оптимально, так как в выражении для целевой функции Z нет неосновных переменных с отрицательными коэффициентами. Поэтому

2шш=ад)=24.



Сформулируем критерии оптимальности при отыскании минимума целевой функции: если в выражении линейной функции через неосновные переменные отсутствуют отрицательные коэффициенты при неосновных переменных, то решение оптимально.

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

Сформулируем все возможные случаи оценки роста неосновной переменной. Обозначим через Х{ переводимую неосновную переменную, bi- свободный член, -коэффициент при В общем виде уравнение xj= bi+,+ ... определяет наибольшее возможное значение xi по следующим правилам:

1) Xi =

, если 6у> О и Gij< 0; например: лгз = 8 - 2x2 + ...; Х2 = 8/2,

2)х/= 00, если bj и щ одного знака и щч 0; bj О например, хз = 8 + 2хз+ ...;х2= оо,

3)х/= О, если Z)y = О и а/,<О, например,хз = 0-2x2+ Х2 = О,

4)Xj= 00, если А, = О и (3/,> О, например,Хз = О + 2x2 + ...;2=

5)Ху= 00, если а,у=0, например, хз = 5 + 0*Х2+хз = -5 + 0*Х2+

Х2= 00,

6)ху= оо,если6у<0иа/,>0, например, хз=-8 +2x2+...;х2= Практические расчеты при решении реальных задач симплексным методом выполняются с использованием компьютеров. Если же задачи небольшой размерности решаются вручную, то удобнее использовать так называемые симплексные таблицы. Рассмотрим общую схему формирования симплексной таблицы.

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

Рассмотрим каноническую задачу линейного программирования в следующем виде:

max ZcfX,(3.7)

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