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


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


16

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

Симплексный метод состоит из трех основных элементов:

1)определения какого-либо первоначального допустимого базисного решения задачи;

2)правила перехода к лучшему решению;

3)проверки оптимальности допустимого решения.

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

3.3. Вычислительная схема симплексного метода

Рассмотрение алгоритма симплексного метода начнем с анализа следующего примера [44].

Решить симплексным методом задачу:

F = 2xi+при ограни-

чениях:

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

Xi +3X2 <18; 2xi +Х2 <16; Х2 <5 ; 3xj<21; xi>0;

(3.1)

Х2>0.

Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений. Учитьшая, что все неравенства имеют знак «<», дополнительные переменные входят со знаком плюс. Исходная система ограничений после указанных преобразований примет следующий вид:

Xi +3x2 +Хз =18 2xj +Х2 +Х4 =16 Х2 + Х5 = 5 ЗХ1+Х6 =21

(3.2)



Для нахождения первоначального базисного решения разобьем переменные на две группы: основные (базисные) и неосновные (небазисные).

Легко видеть, что определитель Хз, Х4, Хз, Хб имеет следующий вид:

при дополнительных переменных

1000 0100 0010 0001

и, следовательно, отличен от нуля. Исходя из этого переменные Х3, Х4, Х5, х можно взять в качестве основных на первом шаге решения

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

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

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

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

Хз = 18 - х, - 3x2 Х4 =16-2х, -Х2 Х5 = 5 - Х2 Хб =21-3xi.

(3.3)

Положим неосновные переменные равными нулю, то есть X, = О, Х2 = О, получим базисное решение Xj = (0; 0; 18; 16; 5; 21), которое является допустимым. Учитывая, что целевая функция, выраженная через неосновные переменные, имеет вид

F = 2xi +3x2,

легко понять, что ее значение при х, = О, Х2 = О равно нулю и может быть увеличено за счет увеличения любой из неосновных переменных XpXj.



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

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

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

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

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

Поскольку необходимо сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными и, следовательно, необходимо выполнение следующих неравенств (при этом xj = О как неосновная переменная)

Хз =18-3x2 >О Х4 =16-Х2 >0 Х5 =5-Х2 >0 х,=21

Х2 <18/3 Х2<16 Х2 <5

Каждое уравнение системы (3.3), кроме последнего, определяет оценочное отношение - границу роста переменной Х2, сохраняющую неотрицательность соответствующей переменной.

Эта граница определяется абсолютной величиной отношения числа, стоящего в правой части неравенства (3.1), к коэффициенту, стоящему при Х2 в соответствующем неравенстве. Уравнение х = 21 не офаничивает рост переменной, так как данная переменная Х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]