Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Прикладные методы оптимизации

Шукаев Д. Н.,

2.3. Симплекс-алгоритм

Как было отмечено во введении учебника для решения задач линейного программирования был разработан симплекс-метод, основой которого является симплекс-алгоритм. Симплекс-алгоритм применяется к задачам линейного программирования, приведенным к канонической форме записи

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n + x_n+1 = b1;

a₂₁x₁ + a₂₂x₂2 + … + a_2nx_n + x_n+2 = b2;

……………………………………………;

a_m1x₁ + a_m2x₂ + … + a_mnx_n + x_n+m = b_m; (2.4)

(–f) + c₁x₁ + c₂x₂ + … + c_nx_n = (–f₀). (2.5)

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

x1 = x2 = … = x_n = 0;

x_n+1 = b1, x_n+2 = b2, …, x_n+m = bm; f = f0. (2.6)

Так как предполагается, что это базисное решение является также и допустимым, величины xj в (2.6) должны быть неотрицательными.

Определение 2.1 [13]. Задача линейного программирования представлена в допустимой канонической форме, если выполнено условие

b₁ ≥ 0; b₂ ≥ 0; b_m ≥ 0.

Как следует из теорем 2.1 и 2.2 для поиска оптимального решения задачи линейного программирования достаточно изучение одних только базисных решений, так как каждое базисное допустимое решение соответствует крайней точке, а каждая крайняя точка соответствует базисному допустимому решению.