Книга: Методы исследования операций

Содержание

• МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ
• Программа
• Задачу линейного программирования можно сформулировать так
• Стандартная форма задачи линейного программирования
• Стандартная форма задачи линейного программирования предполагает, что для всех переменных выполняется условие неотрицательности и все условия-ограничения имеют вид уравнений с неотрицательной правой частью.
• Основные теоремы линейного программирования
• Запишем задачу в стандартном виде
• Z
• Z-уравнение
• Z
• Z-уравнение
• Z
• Z-уравнение
• Z
• Математическая модель. Пусть xij – количество продукта, перевозимого из пункта i в пункт j. Найти множество переменных удовлетворяющих условиям
• ,
• и таких, что целевая функция
• достигает минимума.
• Сети
• Многие задачи линейного программирования можно сформулировать и решить с помощью сетевых моделей. Специальная структура этих задач позволяет разработать эффективные алгоритмы, которые в большинстве случаев основываются на теории линейного программирования.
• Задача минимизации сети.
• Задача минимизации сети состоит в нахождении ребер, соединяющих все узлы сети и имеющих минимальную суммарную длину. Для решения задачи необходимо построить минимальное дерево-остов, применяя следующий итеративный процесс. Начать с любого узла и соединить его с ближайшим узлом сети. Соединенные узлы образуют теперь связное множество, а остальные узлы – несвязное. Далее в несвязном множестве выбрать узел, расположенный ближе всего к одному из узлов связного множества. Скорректировать соответствующим образом связное и несвязное множества, а дугу, по которой произошло присоединение запомнить. Процесс повторять до тех пор, пока все узлы не окажутся в связном множестве. Выбранные дуги образуют минимальное дерево-остов. Его длина равна сумме длин этих дуг.
• Задача о кратчайшем пути
• Задача о кратчайшем пути состоит в нахождении связанных между собой дорог на транспортной сети, которые имеют минимальную длину от исходного пункта до пункта назначения. Для решения этой задачи можно применить следующий алгоритм. Каждому узлу сети будем приписывать временные пометки равные расстоянию от начального узла до данного узла. Если оказывается, что узел принадлежит кратчайшему маршруту, то временную пометку объявляем постоянной. На первой итерации начальному узлу приписывается постоянная пометка равная нулю, а остальным узлам – временные пометки, равные длине дуги из начального узла в рассматриваемый узел, если такая дуга существует и «», если нет такой дуги. Затем, до тех пор пока конечный узел не получит постоянную пометку выполняются следующие две процедуры: 1) среди временных пометок выбирается минимальная и объявляется постоянной; 2) для всех временно помеченных узлов вычисляются новые временные пометки, меньшей из двух величин – старой временной пометки рассматриваемого узла и суммы постоянной пометки последнего постоянно помеченного узла и длины дуги, соединяющей последний постоянно помеченный узел с рассматриваемым узлом. Если при этом постоянную пометку получает конечный узел, то кратчайший маршрут найден. Дуги входящие в этот маршрут определяются следующим образом: если разность между постоянными пометками начального и конечного узлов данной дуги равна длине дуги, то эта дуга принадлежит кратчайшему маршрут.
• Задача о максимальном потоке
• Рассмотрим задачу о максимальном потоке между двумя выделенными узлами связной сети. Каждая дуга сети обладает пропускными способностями в обоих направлениях, которые определяют максимальное количество потока, проходящего поданной дуге. Ориентированная (односторонняя) дуга соответствует нулевой пропускной способности в запрещенном направлении.
• Пропускные способности cij сети можно представить в матричной форме. Для определения максимального потока из источника s в сток t используется следующий алгоритм.
• Шаг 1. Найти цепь, соединяющую s с t, по которой поток принимает положительное значение в направлении st. Если такой цепи не существует, перейти к шагу 3. В противном случае перейти к шагу 2.
• Шаг 2. Пусть cij- (cij+) – пропускные способности дуг цепи (s, t) в направлении st (ts) и = min{cij-}>0. Матрицу пропускных способностей (cij) изменить следующим образом:
• (а) вычесть из всех cij- ;
• (б) прибавить ко всем cij+ .
• Заменить текущую cij-матрицу на вновь полученную и перейти к шагу 1.
• Операция (а) дает возможность использовать остатки пропускных способностей дуг выбранной цепи в направлении st. Операция (б) восстанавливает исходные пропускные способности сети, поскольку уменьшение пропускной способности дуги в одном направлении можно рассматривать как увеличение ее пропускной способности в противоположном направлении.
• Шаг 3. Найти максимальный поток в сети. Пусть C = cij - исходная матрица пропускных способностей, и пусть C* = cij - последняя матрица, получившаяся в результате модификации исходной матрицы (шаги 1 и 2). Оптимальный поток X = xij в дугах задается как
• Максимальный поток из s в t равен
• При этом z есть сумма всех положительных , определенных на шаге 2. Таким образом, можно объяснить, почему используются положительные элементы матрицы C – C* для определения результирующего потока в направлении s t.
• Литература
• Вид ресурса
• Запас ресурса
• Число единиц ресурса, затрачиваемых на изготовление единицы продукции
• S1
• B1
• A11
• A12
• A13