Оптимальное решение - задача - линейное программирование
Cтраница 2
Если, кроме того, допустимая область в задаче линейного программирования ограниченна, то она называется выпуклым многогранником. Следовательно, оптимальное решение задачи линейного программирования находится в одной из вершин выпуклого многогранника. Это вытекает также из ограничений в задаче линейного программирования. Если существуют fet / n действительных неотрицательных переменных проектирования bit которые поэтому являются базисными, то остальные k - &, переменных являются внебазисными. Это значит, что k1 из т ограничений должны удовлетворяться в виде равенств. [16]
Прежде чем проиллюстрировать работу алгоритма па числовом примере, рассмотрим более подробно перечисленные шаги. Предположим, что на некоторой итерации текущее оптимальное решение задачи линейного программирования получено с помощью симплексного алгоритма, описанного в разд. [17]
 |
Геометрическое решение задачи Задача линейного програм-пинейного программирования мированип в случае п - т 3. [18] |
Наименьшего значения линейная форма (2.11) достигнет тогда, когда прямая будет проходить через крайнюю точку области допустимых решений, наиболее удаленную от начала координат. Координаты этой точки xf и х определяют оптимальное решение задачи линейного программирования. [19]
Она обладает одним свойством, не столь очевидным. Именно свойство абсолютной унимодулярности матрицы А гарантирует, что оптимальное решение задачи линейного программирования с ограничениями ( 1) будет целочисленным, если все компоненты вектора b - целые числа. [20]
Заметим, что в распределительной задаче также требуется ввести условия целочисленности, что усложняет ее решение. Поэтому обычно при решении распределительных задач пользуются свойством устойчивости оптимального решения задач линейного программирования при достаточно больших значениях переменных хц и отыскивают целочисленное решение распределительной задачи путем округления до ближайших целых чисел точного, но не целочисленного решения. [21]
После того как отсечено начало координат, представляющее собой оптимальную вершину, вводится другая координатная система. Эта система использует новые небазисные переменные в качестве координатных осей, а оптимальное решение задачи линейного программирования лежит в начале новых координат. [22]
Очевидно, что наименьшего значения линейная функция (6.24) достигает тогда, когда основная прямая переместится в крайнюю точку ОДР в направлении стрелок. Координаты этой точки ( на рис. 6.2 точка Л) и определяют оптимальное решение задачи линейного программирования. [23]
Ограничения ( 1) определяют выпуклую область OABCD в ге-мер-ном пространстве, как показано на рис. 13.1. Узлы целочисленной решетки на рис. 13.1 изображены точками. Такие точки, расположенные внутри области OABCD, являются допустимыми решениями задачи целочисленного программирования. Оптимальные решения задачи линейного программирования всегда располагаются на границе области решений. В данном случае граничные точки не являются даже допустимыми решениями, поскольку ни одна из них не целочпсленна. Предположим, что область допустимых решений сужена до выпуклой оболочки допустимых целых точек внутри допустимой области. На рис. 13.1 эта выпуклая оболочка показана затененной областью OEFGH. [24]
Из всего сказанного читатель мог бы заключить, что при любой целевой функции оптимальное решение находится в одной из четырех вершин и, быть может, в некоторых других граничных точках. Но ведь если оптимальное решение задачи линейного программирования находится в одной из вершин, то нам остается только определить все вершины, вычислить в каждой из них целевую функцию и выбрать ту, которая оптимизирует данную функцию. [25]
В этой группе методов имеются различные модификации. Наиболее распространенным среди них является метод ветвей и границ, который предназначен для решения частично целочисленных задач. Как ив методе отсечения, решение задачи начинается с отыскания оптимального решения задачи линейного программирования без учета условия целочисленности. Затем формируется семейство связанных, но различных задач линейного программирования. Термин возврат определяет специфический способ формирования и решения последовательности задач. [26]
В частности, эти алгоритмы оказались мало эффективными при решении комбинаторных задач, представленных в целочисленной постановке. Возникли также трудности при решении задач, в которых величины atj и bt имеют большие значения. Однако алгоритмы этого класса хорошо зарекомендовали себя при решении задач, в которых оптимальное решение задачи линейного программирования уже содержит целочисленные значения многих переменных. [27]
Присущие целочисленному программированию трудности вычислительного характера обусловили стремление исследователей найти альтернативные пути решения проблемы. Один из простейших подходов заключается в решении непрерывной модификации целочисленной задачи с последующим округлением координат полученного оптимума до допустимых целых значений. Округление в данном случае есть не что иное, как приближение. Например, для линейной задачи с ограничениями в виде равенств округленное решение всегда не удовлетворяет этим ограничениям. Как следует из теории линейного программирования, округленное решение не может быть допустимым, поскольку это означало бы, что один и тот же базис ( при условии равенства нулю небазисных переменных) определяет два различных решения задачи. Приведенный пример показывает возможную несостоятельность подхода, основанного на округлении оптимального решения задачи линейного программирования, полученной из исходной целочисленной задачи путем отбрасывания требований целочисленности. [28]
Страницы: 1 2