Исследование операций. Линейное, динамическое программирование



Исследование операций - часть 50


Возможен и обратный переход: от ОЗЛП к задаче с ограничениями-неравенствами. Пусть перед нами основная задача линейного программирования с ограничениями-равенствами (8.1). Предположим, что среди этих т

равенств линейно независимыми являются r

 т 1). В линейной алгебре доказывается (см., например, [4]), что максимальное число линейно независимых равенств, связывающих п

переменных x1, x2, ..., xn, равно п, так что вообще r

п. В линейной алгебре также доказывается, что систему из r независимых равенств с п переменными x1, х2, ..., xn всегда можно разрешить относительно каких-то r переменных (называемых «базисными») и выразить их через остальные k = п - r переменных (называемых «свободными»). Свободным переменным можно придавать какие угодно значения, не нарушая условий (8.1). Так вот, для того чтобы перейти от условий-равенств (8.1) к условиям-неравенствам, достаточно разрешить уравнения (8.1) относительно каких-то r базисных переменных, выразить их через свободные, а затем вспомнить, что все переменные должны быть неотрицательными, и записать условия их не отрицательности в виде ограничений-неравенств. А потом «забыть» о базисных переменных и манипулировать только свободными, число которых будет k

= п - r. При этом надо будет освободить от базисных переменных также и функцию L, подставив в нее их выражения через свободные. Таким образом, при переходе от ОЗЛП к задаче с ограничениями-неравенствами число переменных не увеличивается, а уменьшается на число г независимых условий-равенств в ОЗЛП. Примеров такого перехода мы приводить не будем, предоставляя пытливому читателю самому убедиться в его возможности.

Итак, всякая задача линейного программирования может быть сведена к стандартной форме ОЗЛП. Мы не будем подробно останавливаться на способах решения этой задачи. Им посвящены специальные руководства (например, [4, 5]), они описаны во многих книгах по исследованию операций (например, [6, 7]). В следующем параграфе мы изложим только некоторые соображения общего характера относительно существования решения ОЗЛП и способов его нахождения.


Содержание  Назад  Вперед