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


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


23

Определить минимум целевой функции

F = +min

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

Зх +Х2>9;х +2jc2>8;Xj + 6х2> 12;х >0;х2>0. Введем дополнительные переменные, каждую со знаком «минус»:

Зх +х-х = 9

1 "6х2-х = 12 х>0;х2>0;хз>0;х>0;хз>0.

На первом шаге выберем в качестве основных переменных дополнительные переменные.

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

3 4 5*1 2*

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

х = -9 + 3Xj + х > О х = -8 + Xj + 2x2 > О x=-12+Xj +6х2>0.

Первое базисное решение = (0; 0; 0; -9; -8; -12) является недопустимым.

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

максимальное оценочное отношение из уравнений х = max (9/3;8;12} =12.

Следовательно, третье уравнение является разрешающим, а переменная х переходит в основные.

Шаг 2. Основные переменные х, х, х Неосновные переменные х, х После преобразований получим:

Х2 = 9-Зх+Хз X = 10-5х +2х,



= (0; 9; 0; 10; 42)- допустимое базисное решение. Применяя в дальнейшем симплекс-метод, получим оптимальное базисное решение Х = (2; 3; 0; 0; 5), при котором минимальное значение целевой функции

равно Fmin = 26.

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

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

Р = х-Ъх- max

Как и в предыдущих примерах вводим дополнительные переменные:

х,+Х2 + Хз = 2

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

х = - + 2х,+х,.

Х = (0; 0; 2; -1)- недопустимое базисное решение. Во втором уравнении выбираем любую переменную х или х, так как обе переменные имеют знак «плюс», и переводим в основные. Для х = min{ 2,6/2} = 2 разрешающее первое уравнение; для х = min{ 2,6} =2 разрешающим

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

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

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

X J = 2-х-х

х = -2-х,-2Хз

Х = (2; 0; 0; -2) - недопустимое базисное решение. Учитывая, что второе уравнение не содержит неосновной переменной с положительным



коэффициентом, невозможно увеличить переменную и получить допустимое базисное решение, следовательно, задача противоречива. Данную ситуацию иллюстрирует рис. 3.2.

Рис. 3.2

После анализа результатов, полученных при решении рассмотренных примеров, сформулируем метод получения первоначального базисного решения:

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

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

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

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