Оптимальное одношаговое управление. Транспортная задача
Контрольная работа - Менеджмент
Другие контрольные работы по предмету Менеджмент
одными, вторые базисными переменными.
После того как свободные переменные приняли некоторые значения, система (4) превращается в систему пяти уравнений с пятью неизвестными. Она имеет единственное решение. Решение исходной системы (4), при котором свободные переменные полагаются равными нулю, называется базисным решением. Если при этом базисные переменные оказались неотрицательными, оно именуется допустимым базисным решением.
Разбиение переменных на свободные и базисные в известной степени произвольно. Следует учитывать лишь одно условие: свободными переменными не могут быть одновременно три переменных с одинаковыми первыми или вторыми индексами.
Далеко не всякое базисное решение является допустимым базисным решением. Между тем для нас представляют интерес только эти последние. В теории линейного программирования доказывается, что допустимые базисные решения являются вершинами многогранника допустимых решений. Отсюда следует, что решение поставленной задачи следует искать среди допустимых базисных решений.
Как выбрать свободные переменные, чтобы соответствующее им базисное решение было допустимым базисным? Общих рекомендаций на этот счет нет. В отдельных случаях можно воспользоваться таким правилом:
если для какого-либо сочетания i , j и k выполняется неравенство:
(5)
в качестве комбинации свободных переменных, обеспечивающей допустимое базисное решение, может быть выбрана совокупность:
(6)
Проиллюстрируем примером, который будет использован в дальнейшем. Пусть . Тогда i=1, j=2, k=3; индексы т и п могут быть либо "1", либо "2", причем, если т =1, то n=2 , и наоборот.
То же правило остается в силе, если . Тогда в совокупности (6) первые и вторые индексы следует поменять местами.
Если соотношений типа (5) установить нельзя, как в моем случае, комбинация (6) в качестве совокупности свободных переменных не годится. Тогда такую совокупность можно составить из трех диагональных переменных x11,x22,x33 и одной недиагональной , с индексами i и j, соответствующими наименьшим значениям величин ai и bj.
Исходя из этого: x11, x22, x33, x12 - свободные переменные(7)
x13, x21, x23, x31, x32 - базисные переменные
Исходное базисное решение
Алгоритм направленного перебора вершин многогранника допустимых решений (или, что то же, - допустимых базисных решений) базируется на так называемом симплекс-методе, главном детище теории линейного программирования. Для "работы" метода необходимо иметь какое-либо одно (любое) допустимое базисное решение. Как найти такое решение, мы разобрали в предыдущем разделе (этапе). Здесь рассматривается формализованное представление этого решения, удобное для использования в симплекс-методе.
Как видно из приведенных данных таблицы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) в форме специальной матрицы (симплекс-матрицы) и ее преобразование по определенному алгоритму в другую такую же матрицу. Последняя анализируется на оптимальность и при отсутствии та