Исходное базисное решение

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

Как видно из приведенных данных таблицы1, в качестве совокупности свободных переменных выберем набор (7). Подставим данные табл.1 в систему (4) и выразим базисные переменные через свободные :

x11+x12+x13=150

x21+x22+x23=250

x11+x21+x31=300

x12+x22+x32=200

x13+x23+x33=300

x13=150-x11-x12

x21=100-x22-x11-x12+x33

x31=200-x33+x12+x22(8)

x32=200-x12-x22

x23=150+x11+x12-x33

Из этой записи наглядно просматривается соответствующее выбранной совокупности свободных переменных базисное решение :

x11=0, x22=0, x33=0, x12=0,

x13=150, x21=100, x31=200, x32=200, x23=150.

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

S=s13x13+s21x21+s31x31+s32x32+s23x23=(10)

Данному решению отвечает схема транспорта грузов, приведенная на рис. 4.

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

S=s11x11+s12x12+s13x13+s21x21+s22x22+s23x23+s31x31+s32x32+s33x33=

=2x11+x12+3(150-x11-x12)+100-x22-x11-x12+x33+4x22+

+3(150+x11+x12-x33)+4(200+x22+x12-x33)+200-x12-x22+x33= (11)

=2000+x11+3x12+6x22-5x33.

Как и следовало ожидать, исходному базисному решению соответствует значение целевой функции, определяемое свободным членом выражения (11). Однако это выражение несет в себе гораздо большую информацию. Оно справедливо, независимо от того, являются ли переменные x11, x12, x33 свободными или базисными. Переменная x33 имеет в нем отрицательный коэффициент. Если бы эта переменная была не свободной, а базисной переменной, то она была бы положительной (по крайней мере, неотрицательной). А это значит (см. (11)), что значение целевой функции S уменьшилось бы. Таким образом, данное допустимое базисное решение (9) не оптимально. И индикатором этого заключения является наличие в (11) отрицательных коэффициентов.

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

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