Теория - линейное программирование
Cтраница 2
К теории линейного программирования приводит рассмотрение многих задач. В порту Ps находится ау кораблей. Очевидно, что эту задачу можно решить самыми различными способами. Допустим, что требуется осуществить общее перемещение кораблей наиболее экономичным способом. [16]
В теории линейного программирования существуют методы, позволяющие целенаправленно перебирать вершины так, что в каждой последующей вершине значение целевой функции меньше, чем в предыдущей. [17]
В теории линейного программирования доказывается, что независимо от экономической интерпретации исходной и двойственной задач, а также от характера ограничений ( или), если решение ЛП-задачи на максимум или на минимум существует, то оптимальное ( максимальное или минимальное) значение целевой функции в исходной задаче должно быть в точности равно оптимальному ( минимальному или максимальному) значению целевой функции двойственной задачи. [18]
Разработанные в теории линейного программирования вычислительные методы ( симплекс-метод, двойственный симплекс-метод и другие, см. [4,6, 8]) позволяют находить оптимальное решение не слепым перебором, а целенаправленным, с постоянным приближением к решению. Добавим, что современные ЭВМ, как правило, снабжены подпрограммами для решения задач линейного программирования, так что лицу, желающему их решать, нет даже особой надобности обучаться решению таких задач вручную - труд крайне неприятный и изнурительный. [19]
Однако в теории линейного программирования существует понятие двойственности, которое позволяет унифицированным образом устанавливать взаимосвязи для всех приемов и методов анализа моделей на чувствительность. [20]
Разработанные в теории линейного программирования вычислительные методы ( симплекс-метод, двойственный симплекс-метод и другие, см. [4, 6,8]) позволяют находить оптимальное решение не слепым перебором, а целенаправленным, с постоянным приближением к решению. Добавим, что современные ЭВМ, как правило, снабжены подпрограммами для решения задач линейного программирования, так что лицу, желающему их решать, нет даже особой надобности обучаться решению таких задач вручную-труд крайне неприятный и изнурительный. [21]
Большая часть теории линейного программирования носит вычислительный характер и поэтому казалось, что следует подробно рассмотреть один ( и только один) из важных алгоритмов линейного программирования, чтобы увидеть, каким образом его можно включить в теорию конструирования моделей. Основное ударение было сделано на так называемые методы ограничения базисных переменных, вместе с соответствующими им изменениями моделей со специальным упоминанием соответствующих расширений симплекс-метода. Это, очевидно, не исчерпывает всей темы, которую мы назвали алгоритмическим завершением модели. [22]
Применим симплексный метод теории линейного программирования, позволяющий решить систему уравнений рассматриваемого типа, в которой число неизвестных превышает число уравнений. [23]
С помощью общих результатов теории линейного программирования ( или непосредственным рассуждением) легко проверяется, что поставленная экстремальная задача всегда разрешима. [24]
Поколение исследователей, основавших теорию линейного программирования и теорию потоков в сетях, заняло прагматическую позицию по отношению к задачам сложности вычислений: алгоритм рассматривался как эффективный, если он быстро работал на практике, и не так уж важно было доказывать, что он быстр во всех возможных случаях. В 1967 г. я заметил, что стандартный алгоритм для решения некоторых задач о потоках в сетях имеет теоретический изъян, из-за чего он очень медленно работает на некоторых специально подобранных примерах. Я нашел, что нетрудно исправить этот изъян, и рассказал об этом результате на семинаре по комбинаторике в Прин-стоне. [25]
 |
График зависимости приращения кода объекта от приращения значения числового эквивалента. [26] |
Задача решается с помощью симплекс-метода теории линейного программирования. Дробную часть значения опускаем, так как xt может принимать только целочисленные значения. [27]
Понятие двойственности играет фундаментальную роль в теории линейного программирования, отсюда желание многих авторов перенести идеи двойственных задач линейного программирования на ВЗЛП. [28]
Для применения этого хорошо изученного в теории линейного программирования метода к задачам нелинейного программирования, как это было сделано нами в предыдущем параграфе, требуется соответствующее преобразование функций. Например, в случае геометрического программирования, используя кусочно-линейную аппроксимацию каждого слагаемого сепа-рабельной функции, необходимо обеспечить определенную точность аппроксимации, что всегда приводит к увеличению объема вычислений и итеративной процедуре. [29]
Теорема двойственности представляет собой центральный результат теории линейного программирования. Существуют различные методы ее доказательства - и чисто алгебраические, без использования результатов типа теорем об отделимости, и доказательства, основанные на принципиально новых идеях типа метода штрафных функций. [30]
Страницы: 1 2 3 4