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

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

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

a11x1 + a12x2 + … + a1nxn + xn+1 = b1;

a21x1 + a22x22 + … + a2nxn + xn+2 = b2;

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

am1x1 + am2x2 + … + amnxn + xn+m = bm; (2.4)

(–f) + c1x1 + c2x2 + … + cnxn = (–f0). (2.5)

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

x1 = x2 = … = xn = 0;

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

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

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

b1 ≥ 0; b2 ≥ 0; bm ≥ 0.

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


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074