Cтраница 2
Прежде чем дать исчерпывающую формулировку симплексного алгоритма, целесообразно рассмотреть задачу в упрощенном виде, чтобы постепенно ввести читателя в курс дела. В противном случае можно запутаться в подробностях и недостаточно четко оттенить основные идеи, которые часто воспринимаются лишь интуитивно. Можно с уверенностью утверждать, что, закончив изучение данной главы, читатель разберется во всех деталях, которые необходимы для успешного применения рассматриваемого алгоритма к любой модели линейного программирования. [16]
Прежде чем приступить к изучению симплексного алгоритма, проведем краткий анализ одной простой модели линейного программирования, чтобы получить определенное представление о тех препятствиях, которые приходится преодолевать с помощью различного рода технических приемов. [17]
Данциг разработал алгоритм, называемый симплексным алгоритмом, эффективно преобразующий графический подход в алгебраический метод, который может быть использован для компьютерного приложения и позволяет обрабатывать любое число переменных. [18]
Процесс вычеркивания-замещения, использующийся в симплексном алгоритме при составлении последовательных матриц, не представляет трудностей. [19]
Таким образом, оказывается, что симплексный алгоритм служит хорошим средством для решения не только линейных, но и нелинейных задач. Природа преобразования, с помощью которого нелинейная задача может быть приведена к форме, допускающей применение симплексного метода, очень сильно зависит от типа задачи. В некоторых случаях не требуется никакой предварительной аппроксимации, в других аппроксимация необходима. [20]
Теперь, когда понятна простая логика симплексного алгоритма, объем сопутствующих записей можно существенно сократить, если весь вычислительный процесс представить в виде удобной таблицы, известной под названием симплекс-таблицы. Таблицы на рис. 4.10 и 4.11 представляют собой описание двух различных подходов к решению задачи, которая в качестве примера приведена в разд. В таблице, приведенной на рис. 4.10. столбцы, соответствующие базисным переменным, имеют настолько тривиальный смысл, что их без ущерба для однозначности понимания можно из упомянутой таблицы исключить. В результате получаем редуцированный вариант табличной записи, приведенный на рис. 4.11. В этом случае после каждой итерации необходимо вводить одну дополнительную строку, предназначенную для нового набора небазисных переменных. [21]
Двойственный симплекс-алгоритм строится по аналогии с симплексным алгоритмом, рассмотрению которого посвящена гл. Прежде всего сформулируем правило, позволяющее определять переменную, подлежащую исключению из пробного базиса. [22]
Решите указанные ниже задачи, пользуясь симплексным алгоритмом для транспортной задачи с ограниченными пропускными способностями, рассмотренным в разд. [23]
Модель в виде задачи линейного программирования и симплексный алгоритм ее решения являются эффективными средствами определения компромиссов, целесообразных взаимозамен, вмененных издержек. За более подробными разъяснениями читателю следует обратиться к приложению к данной главе. [24]
Вычисление оптимальной длины шага напоминает критерий II симплексного алгоритма. Однако здесь также определяется значение переменной, выше которого начинается уменьшение значения целевой функции. Следовательно, оптимальная длина шага есть меньшая из этих двух величин. [25]
Рассмотрите решение задачи Р с помощью модифицированного симплексного алгоритма, приведенное в разд. [26]
Здесь излагается метод решения, который, подобно симплексному алгоритму, опирается на понятие двойственности. [27]
Очевидно, к этой задаче уже можно применить симплексный алгоритм. [28]
Можно рекомендовать, например, один из вариантов симплексных алгоритмов нелинейного программирования, сравнительно экономичных с точки зрения количества вычислении значения критерия оптимальности. [29]
Если все ограничения модели линейны, можно воспользоваться симплексным алгоритмом с двусторонними ограничениями на переменные, изложенным в разд. [30]