ПОИСК Статьи Рисунки Таблицы Преобразование ограничений из "Методы оптимизации в химической технологии" Для ее решения теперь не требуется никаких дополнительных вычислений. Максимальное значенне критерия оптимальности (VIII,31), очевидно, достигается при наибольшем допустимом значении переменной x , которое с учетом условий (VI 11,33) будет л , = V. . [c.420] Нетрудно видеть, что все дополнительные переменные а 1,. . ., т,), определенные таким образом, неотрицательны. [c.423] Если в исходной постановке оптимальной задачи линейного программирования имеются ограничения типа равенств (УП1,6в), то их можно прямо включить в ограничения (УП1,42). При этом следует только принимать во внимание, что число дополнительных переменных уже не равно числу ограничений т, а определяется числом неравенств т. . [c.423] Е5 дальнейшем предполагается, что рассматриваются такие задачи линейного программирования, для которых оптимальное значение линейной формы (VI 11,34) достигается в одной из вершин многогранника условий, описываемого неравенствами (VIII,35) и (VIII,36). [c.424] В л-мерном пространстве, отвечающем основным переменным задачи Х/ (/ = 1,. . ., /г), координаты вершины многогранника как и координаты точки /г-мерного пространства, однозначно определяются заданием /г значений переменных x (j = I, п). Соответственно каждая вершина многогранника условий может считаться точкой пересечения п гиперплоскостей, образующих его область, прилегающую к данной вершине. Однако возможны случаи, когда в вершине многогранника условий пересекаются более чем п гиперплоскостей. Примером подобного случая в трехмерном пространстве (/I == 3) является вершина пирамиды, у которой в основании лежит четырехугольник. При этом в вершине пирамиды пересекаются четыре плоскости, служащие ее боковыми гранями. Если в основании пирамиды лежит многоугольник с еще большим числом сторон, то в ее вершине пересекается соответственно большее число плоскостей-граней. [c.424] Задачи линейного программирования с условиями, образующими многогранники в м-мерном пространстве, у которых в ряде вершин пересекаются более чем п гиперплоскостей, отвечающих ограничивающим неравенствам, называются вырожденными задачами. [c.424] Иа практике случаи вырождения, о которых несколько подробнее идет речь ниже (см. стр. 459), встречаются весьма редко. Поэтому далее рассматриваются только невырожденные задачи линейного программирования, для которых оптимальное значение линейной формы достигается в одной из вершин многогранника условий, определяемой пересечением ровно п гиперплоскостей, соответствующих ограничениям (VIII,35) и (VIII,36). [c.424] Нг рис. УПТ-б показан такой случай для м 2 и т = 1, причем единс гвенное ограничение задано в виде + Хо 1. Вершинами многогранника условий в данном случае являются точки О (О, 0), У1 (1, 0) и В (О, 1), у которых не более одной координаты отлично от нуля. [c.425] Можно также привести пример для случая п - 3 и гп - - 1 (рис. УП1-7), когда ограничение задано в форме х- - -х., Ч- Хл I, Вершинами многогранника условий служат точки О (О, О, 0), Л (1, О, 0), В (О, 1, 0) и С (О, О, 1), причем их координаты содерж ат только одну составляющую, не равную нулю. [c.425] Если т п, число отличных от нуля координат вершин многогранника условий, естественно не может превышать числа п, что не противоречит требованию, чтобы число отличных от нуля координат не превышало т. Случай т п показан, например, на рис. УП1-5, где точки 5, и 8., имеют обе координаты, не равные пулю. [c.425] Задача оптимизации критерия (У1П,43) тем самым сводится к выбору только неотрицательного решения системы уравнений (VI11-42), максилшзнрующего Я и содержащего ровно т отличных от нуля составляющих. [c.426] Допустимое решение, в котором ровно т составляющих отличны ог нуля, называется допустимым базисным решением, или просто базисным решением. Иногда базисное решение называют также планом. [c.426] Вернуться к основной статье