Оптимальное решение - задача - линейное программирование
Cтраница 1
Оптимальное решение задачи линейного программирования достигается в одной из опорных точек, где по крайней мере k п, - т переменных равны нулю. [1]
Используя оптимальное решение задачи линейного программирования, можно найти допустимые изменения ДС, при которых еще L остается постоянным. [2]
Если существует оптимальное решение задачи линейного программирования, то существует базисное оптимальное решение. [3]
Доказано, что оптимальное решение задачи линейного программирования находится на границе области допустимых значений управляемых переменных, представляющей собой многогранник в n - мерном пространстве и определенный системой линейных ограничений. [4]
Поскольку z - оптимальное решение задачи линейного программирования, имеющей т ограничений, в этом решении содержится не более чем т строго положительных переменных. [5]
Доказано [19], что оптимальное решение задачи линейного программирования находится на границе области допустимых значений управляемых переменных, представляющей собой многогранник в / г-мерном пространстве, определенной системой линейных ограничений. Координаты каждой вершины определяются путем решения системы уравнений ( ограничения) и при наличии п управляемых переменных и m ограничений приходится Ст п разрешать систему из т уравнений. Сочетание Спт п ( т - п очень быстро растет с увеличением тип, поэтому поиск решения требует очень большого числа вычислений, недоступных даже для ЭВМ. [6]
Итак, в случае D 1 оптимальное решение задачи линейного программирования оказывается автоматически целочисленным. [7]
Как было показано в части 1, оптимальное решение задачи линейного программирования отнюдь не обязательно целрчислен-но, и в то же время существует много задач, природа которых требует целочисленности решения. Некоторые из этих задач на первый взгляд не являются задачами целочисленного программирования, однако они могут быть сформулированы как таковые. [8]
Очевидно, что не всякое базисное решение является оптимальным решением задачи линейного программирования. Однако оптимальное решение невырожденной задачи всегда должно быть базисным для системы уравнений ( VIII, 42), и, таким образом, задача отыскания оптимального решения заключается в переборе только базисных решений системы уравнений ( VIII, 42), среди которых отыскивается оптимальное. [9]
Очевидно, что не всякое базисное решение является оптимальным решением задачи линейного программирования. Однако оптимальное решение невырожденной задачи всегда должно быть базисным для системы уравнений ( VIII42) и, таким образом, задача отыскания оптимального решения заключается в переборе только базисных решений системы уравнений ( VIII42), среди которых отыскивается оптимальное. [10]
После выполнения нескольких итераций на шаге 3 могут появиться многочисленные альтернативные оптимальные решения задачи линейного программирования. Такое зацикливание иногда называют сплошной вырожденностью. К сожалению, это явление часто возникает в задачах средней PI большой размерности. Имеется также много примеров задач малой размерности ( не более 10 переменных и уравнений), при решении которых для достижения сходимости потребуются тысячи итераций. [11]
В этих случаях используется симплекс-метод, который представляет собой итеративную ( пошаговую) процедуру для определения оптимального решения задачи линейного программирования. Расчеты по симплекс-методу начинают с определения допустимого решения, а затем отыскиваются другие допустимые решения и проверяются возможности их улучшения. Переход от одного решения к другому продолжается до тех пор, пока новые улучшения не будут невозможны. Широко распространены стандартные компьютерные программы, которые используют симплекс-метод для решения таких управленческих задач, которые можно представить как задачи линейного программирования. [12]
Если система линейных ограничений обладает специальной структурой, например если она образует сетевую модель, то на шаге 2 при нахождении оптимального решения задачи линейного программирования это обстоятельство можно использовать. [13]
Идея пропорционального распределения была реализована в виде двухэтапного алгоритма расчетов, предложенного И.И.Дикиным [36], в котором существенно используется свойство метода внутренних точек вырабатывать относительно внутреннюю точку множества оптимальных решений задачи линейного программирования. Это свойство означает, что граничные значения по условиям-неравенствам (2.3.2) - (2.3.4) достигаются только для тех переменных, которые имеют эти граничные значения при любом другом оптимальном решении. [14]
 |
Графическое решение задачи из примера 1 - - значения целевой функции. 2 - точка оптимума ( 2, 6. [15] |
Страницы: 1 2