Табличный метод решения транспортной задачи. Использование циклов пересчетов и метода потенциалов при поиске оптимального плана перевозок. Достаточное условие оптимальности
Табличный метод решения транспортной задачи
И меется n поставщиков и m потребителей однородного продукта, например, типографской краски. Известны стоимости Cij перевозки единицы продукта от i-го поставщика к j-му потребителю. Пусть Ai – количество продукта, имеющегося у i-го поставщика, а Bj – количество продукта, необходимое j-му потребителю. Задача формулируется следующим образом: определить, какое количество Xij продукта нужно перевезти от i-го поставщика к j-му потребителю (i =1,2,…, n; j =1,2,…, m), чтобы общая стоимость перевозки L была минимальной
и при этом были выполнены условия
Для нахождения начального плана перевозок (любого допустимого решения) и последующего улучшения этого плана разработан табличный метод, который состоит в следующем.
Строится таблица, состоящая из m +1-й строки и n +1-го столбца (по числу m потребителей и n поставщиков). В правый крайний столбец заносятся числа B1, B2,…, Bm, а в нижнюю строку числа A1, A2,…, An.
После этого начинают заполнять таблицу числами так, чтобы их сумма в каждой строке оказалась равна соответствующему значению B, а сумма по каждому столбцу – соответствующему значению A. Каждая клетка таблицы соответствует одной переменной Xij, первый индекс которой соответствует номеру строки, а второй – номеру столбца.
Некоторые из клеток таблицы могут оставаться пустыми – они соответствуют нулевым значениям переменных Xij. Будем называть такие клетки и соответствующие им переменные небазисными, а заполненные клетки и соответствующие им переменные – базисными.
Существует простой способ построения начального плана перевозок. Он получил название метода северо-западного угла, поскольку заполнение таблицы начинается с левого верхнего ее угла. В эту клетку заносится меньшее из чисел A1, B1. Если B1 < A1, то это означает, что потребности первого потребителя можно полностью удовлетворить за счет запасов первого поставщика, в этом случае в первую строку ничего вносить больше не надо и переходят ко второй строке. В противном случае в первую клетку заносится число A1, то есть первому потребителю передаются все запасы первого поставщика, но, поскольку их потребность в продукте у потребителя остается, то заполняется вторая клетка в этой строке – используются запасы второго поставщика, затем третья и так до тех пор, пока потребности первого потребителя не будут удовлетворены полностью. После этого начинают заполнять вторую строку, также двигаясь по ней слева направо.
В результате выполнения указанной процедуры в таблице оказываются заполненными r = m+n–1 клетка, и соответствующие базисные переменные получат некоторые значения. При этом автоматически будут удовлетворены условия задачи: весь продукт, имеющийся у поставщиков, будет распределен между потребителями, при этом каждый из них получит ровно столько, сколько ему нужно.
Чтобы улучшить план, нужно перейти к новому базисному решению, аналогично тому, как это делается в симплекс-методе. Для этого нужно изменить таблицу так, чтобы одна из базисных клеток оказалась пустой (то есть с нулевым значением), а одна из пустых (небазисных) получила неотрицательное значение (стала базисной), При этом, разумеется, суммы по строкам и столбцам таблица должны остаться прежними, поскольку это условие допустимости любого решения.
Использование циклов пересчетов и метода потенциалов при поиске оптимального плана перевозок
Перейти к новому базисному решению можно с помощью так называемого цикла пересчета.
Циклом пересчета называется цепочка клеток таблицы перевозок, удовлетворяющих следующим условиям:
одна из клеток в этой цепочке свободная, остальные – заполненные числами;
каждые две соседние клетки в цепочке находятся либо в одной строке, либо в одном столбце;
никакие три соседние клетки, входящие в цепочку, не могут находиться в одной строке или в столбце;
если каждые две соседние клетки цепочки соединить отрезком прямой, так, чтобы получился замкнутый контур из ломаных линий, то одна вершина этого контура будет находиться в свободной клетке таблицы, остальные – в заполненных, то есть в базисных.
Таких цепочек можно построить столько, сколько имеется в таблице свободных (небазисных) клеток. Построив такую цепочку, можно осуществить переход к другому набору базисных клеток с помощью следующей процедуры:
последовательность клеток в цепочке помечается чередующимися знаками + и –, при этом свободная клетка помечается знаком плюс;
среди клеток, помеченных знаком минус, отыскивается та, в которой записана наименьшая величина, эта величина затем прибавляется к числам в клетках, помеченных знаком плюс и вычитается из чисел в клетках, помеченных знаком минус.
В результате такого циклического перемещения будет получен другой набор базисных клеток и при этом сумма чисел в каждой строке и в каждом столбце останутся прежними.
Обеспечить целенаправленный перебор возможных базисных решений, который приводит к уменьшению целевой функции при переходе к новому базису, позволяет метод потенциалов, которые состоит в следующем.
Введем n вспомогательных переменных i, i =1,2,…, n и m переменных j, j = 1,2,…, m и рассмотрим систему уравнений:
i + j = С i j,
где Сij – те элементы матрицы стоимостей, значения индексов i и j которых соответствуют номерам строк и столбцов матрицы перевозок, на пересечении которых находятся базисные клетки. Поскольку на каждой строке и в каждом столбце матрицы перевозок имеется хотя бы одна базисная клетка, в систему уравнений войдут все введенные выше вспомогательные переменные.
Число базисных клеток равно n + m –1. Таким образом, число уравнений на единицу меньше числа неизвестных. Если одной из неизвестной произвольно задать некоторое значение, например, положить 1 = 0, то остальные определяются однозначно.
Найденные значения 1, 2,…, n и 1, 2,…, m называются потенциалами. Введем матрицу Ĉ такую, что Ĉij = i + j, (i =1,2,…, n и j = 1,2,…, m). Ее называют матрицей фиктивных стоимостей. Очевидно, что для тех значений индексов i и j, которые соответствуют базисным переменным Xij, элементы фиктивной и исходной матриц стоимостей совпадают, для других значений индексов они могут различаться.
Матрица фиктивных стоимостей, построенная для некоторого набора базисных клеток таблицы перевозок, позволяет определить, является ли текущий набор базисных переменных оптимальным и если нет, то какую из небазисных переменных следует включить в число базисных, чтобы получить лучший план, с меньшим значением целевой функции. Для этого составляется матрица разностей между истинной и фиктивной матрицами стоимостей:
Cij = Cij – Ĉi j = Cij – ( i + j).
Если все Cij 0, то текущий план перевозок оптимален. Если среди Cij есть отрицательные, то план можно улучшить. Пусть Cpq – самый большой по абсолютной величине отрицательный элемент, тогда выбрав переменную X pq в качестве кандидата на включение в число базисных и выполнив для нее цикл пересчета, можно получить новый план перевозок с меньшим значением целевой функции.
- Раздел 1. Теория автоматического управления
- Частотные характеристики систем управления и связь между ними
- Временные характеристики систем управления
- Типовые звенья систем управления
- Интегрирующее звено
- Консервативное звено
- Запаздывающее звено
- Частотные методы оценки устойчивости систем
- Методы построения логариф частотных хар-к
- Законы распределения и числовые характеристики случайных сигналов
- Оценка качества регулир. Показатели качества
- Передаточные функции дискретных су
- Алгебраический критерий устойчивости дискретных систем
- Частотный критерий устойчивости дискретных систем
- Метод гармонич линеариз нелин систем
- Раздел 2. Локальные системы управления
- Особенности математического описания объектов управления. Входные и выходные переменные. Векторы состояния, управления и возмущения. Оператор и переходная функция
- Д атчики систем автоматики
- Устойчивость датчиков к действию высокочастотных помех
- Двигатель постоянного тока как элемент автоматики. Принципиальная схема, основные уравнения движения
- Асинхронный двигатель как элемент автоматики. Структурная схема, передаточная функция, переходные характеристики
- Дискретные законы управления. Математическая модель дискретного управляющего устройства. Импульсные передаточные функции каналов дискретного уу
- Раздел 3. Вычислительные машины, системы
- Принципы построения вычислител машин
- Понятие логической функции. Полностью и неполностью определенные логические функции. Способы задания логических функций
- Комбинационные автоматы. Синтез комбинационных конечных автоматов
- Методы минимизации логических функций
- Модели вычислений. Многоуровневая организация вычислительных процессов
- Прерывания. Шина современных пк
- Типы и основные принципы построения периферийных устройств
- Многомашинные комплексы и многопроцессорные системы
- Управляющие вычислительные комплексы
- Раздел 4. Технические средства обработки текста и изображений
- Методика светоэнергетического расчета лазерного фотовыводного устройства
- Методика расчета параметров лазерных выводных устройств, определ скорость сканирования
- Структура, назначение и принцип работы проявочных машин. Основные системы автоматизации процессов обработки фотоматериалов
- Технические средства анализа и ввода изображения в систему допечатной обработки
- Основные виды, параметры и принцип работы источников и модуляторов лазерного излучения
- Структурная схема, назначение и принцип работы формовыводного устройства (рекордера)
- Основные этапы и характеристики электрофотографического процесса цветной электрофотографии. Структурная схема, назначение устройств и принцип работы аппарата цветной электрографии
- Принцип работы, назначение и разновидности струйных принтеров
- Структурная схема, назначение устройств и принцип работы лазерного принтера (одноцветный вариант)
- Структурная схема, назначение устройств и принцип работы лазерного фотонаборного автомата
- Цифровые печатные машины (цпм). Основные типы цпм и принцип работы
- Раздел 5. Автоматизированное управление полиграфическим производством
- Задачи управления дискретным производством: планирование ассортимента выпуска продукции, транспортная задача
- Симплекс-метод решения задачи линейного программирования. Табличная реализация симплекс-метода в задаче об ассортименте выпускаемой продукции. Алгоритм поиска оптимального плана
- Табличный метод решения транспортной задачи. Использование циклов пересчетов и метода потенциалов при поиске оптимального плана перевозок. Достаточное условие оптимальности
- Информационное обеспечение систем управления. Фактографические базы данных. Типы субд и их характеристики
- Документальные информационные системы, их характеристики. Информационный поиск в документальных системах, оценка полноты и релевантности. Модели поисковых образов
- Методы защиты информации в информационно-управляющих системах. Алгоритмы шифрования данных. Метод открытого ключа. Средства анализа защищенности компьютерных сетей