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


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


17

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

Все возможные случаи, которые возникают при оценке переменной, перечислены далее.

Очевидно, что сохранение неотрицательности возможно, если не нарушена ни одна из границ. Следовательно, в рассматриваемом случае

X2=min{ 18/3,16,5,00} = 5.

При 2 = 5 переменная обращается в нуль и переходит в неосновные. Уравнение, где достигается наибольшее возможное значение переменной, переводимой в основные (т.е. где оценка минимальна), называется разрешающим. В данном случае - это третье уравнение.

Шаг 2. Основные переменные Х2, хз, Х4, хв» Неосновные переменные

На этом шаге вьфазим новые неосновные переменные, начиная с разрешающего уравнения (оно используется при выражении записи для 2)

Х2=5-Х5

Хз=18-Х1-3(5-Х5) (3.4)

Х4 =16-2xi --(5-Х5) Х5 =21-3xi. Преобразуя систему, получим:

Х2=5-Х5

Хз=18-х,-3(5X5) Х4 =16-2xi -(5-Х5) Х5 =21-3xi.

Второе базисное решение Х2 = (0; 5; 3; 11; 0; 21) является допустимым.

Выразив линейную функцию через неосновные переменные, получим: F = 2xi + ЗХ2 = 2xi + 3(5 - Х5) = 15 + 2xi - ЗХ5.

Значение целевой функции (2) = 15.



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

Ai =5.3=15,F(X2) = F(Xi) + AF, =0+15 =15.

Далее, как легко видеть, значение (з) не является максимальным, поскольку оно может быть улучшено за счет переменной , входящей в выражение для F с положительным коэффициентом. Как и ранее предположив, что правые части уравнений (3.4) неотрицательны, получим, что наибольшее значение х, определяется из выражения

= min { 00,3,5,5,00} = 3. Второе уравнение является разрешающим, переменная переходит в неосновные при этом AF2 =32 = 6.

Шаг 3. Основные переменные х,Х2,х,х. Неосновные переменные Х3, Х5

Повторяя процедуру шага 2, выражаем новые основные переменные через неосновные, начиная с разрешающего уравнения. Проведя необходимые преобразования, получим:

Xj = 3 - Хз + ЗХ5 Х2 = 5 - Х5

Х4 =5 + 2x3-5x5

Хб =12 + 3x3-9x5.

Базисное решение = (3; 5; 0; 5; 0; 12) соответствует вершине, у которой Xj = 3; Х2 = 5 . Выражаем линейную функцию через неосновные переменные:

F = 2xi +3x2 =2(3-Хз +Зх5) + 3(5-Х5) = 21-2хз +ЗХ5 з=(Хз)=21.

Проверяем (Хз)-(Х2) = 21-15=6=А2.

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



тыре уравнения системы (3.5), лг; =min{ оо,5,1,12/9} = 1. Третье уравнение является разрешающим, и переменная переходит в неосновные Дз =1-3 = 3.

Шаг 4. Основные переменные x,X2,X},x. Неосновные переменные х,х.

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

Xi=6 + -X--X

. 2 1 3 9

6=3-3 + 54-

Базисное решение = (6; 4; 0; 0; 1,3).

Целевая функция, выраженная через неосновные переменные, имеет вид F = 24-x,-x,.(3.6)

Это выражение не содержит положительных коэффициентов при неосновных переменных, следовательно, улучшить решение нельзя и поэтому значение целевой функции F(X) = 24 максимальное.

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

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

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

1)если необходимо отыскать минимум F, то решается задача максимизации функции -F, и это решение принимается за решение исходной задачи;

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

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