Опорное решение транспортной задачи - Анализ транспортной задачи по критерию времени
Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы. Ввиду того, что ранг системы векторов условий транспортной задачи равен N=m+n-1, опорное решение не может иметь отличных от нуля координат больше, чем N. Для проверки линейной независимости векторов условий, соответствующих координатам допустимого решения, используют циклы. Циклом называется такая последовательность клеток таблицы транспортной задачи в которой две и только соседние клетки расположены в одной строке или столбце, причем первая и последняя также находятся в одной строке или столбце.
Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи, i=1,2,...,m; j=1,2,...,n является опорным только в том случае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла. Метод вычеркивания. Для проверки возможности образования цикла используется так называемый метод вычеркивания, который состоит в следующем. Если в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждом столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов условий является линейно независимой, а решение опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов условий линейно зависима, а решение не является опорным.
Метод минимальной стоимости. Данный метод позволяет построить опорное решение, которое достаточно близко к оптимальному, так как использует матрицу стоимостей транспортной задачи, i=1,2,...,m; j=1,2...,n. Данный метод состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую, заполняют также. Поставщик исключается из рассмотрения, если его запасы заканчиваются. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик не исключен, но его запасы равны нулю, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения. Аналогично поступают с потребителем. Решение является "вычеркиваемым" и, следовательно, опорным. Переход от опорного решения к другому. В транспортной задаче переход от оного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением. По этому циклу перераспределяются объемы перевозок (осуществляется сдвиг по циклу). Перевозка "загружается" в выбранную свободную клетку и освобождается одна из занятых клеток, получается новое опорное решение. Если таблица транспортной задачи содержит опорное решение, то для любой свободной клетки таблицы существует единственный цикл, содержащий эту клетку и часть клеток, занятых опорным решением. Для удобства вычислений вершины циклов нумеруют и отмечают нечетные знаком "+", а четные знаком "- ". Такой цикл называется означенным. Сдвигом по циклу на величину называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком "+", и уменьшение объемов перевозок на ту же величину во всех не четных клетках, отмеченных знаком "- ".
Похожие статьи
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Сбалансированность транспортной задачи Транспортная задача является сбалансированной, если суммарные запасы поставщиков равны суммарным запросам...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Математическая постановка задачи Транспортная задача - Однородный груз сосредоточен у поставщиков. Данный груз необходимо доставить потребителям....
-
Введение - Анализ транспортной задачи по критерию времени
Под названием "Транспортная задача" объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача - задача о наиболее...
-
Элементы матричного анализа - Методы решения системы линейных уравнений
Вектором, как на плоскости, так и в пространстве, называется направленный Отрезок , то есть такой Отрезок , один из концов которого выделен и называется...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Пример решения транспортной задачи - Экономико-математические методы
На четырех строительных площадках В1, В2, В3, В4 монтируется в день соответственно 20,120,20 60 м3 сборных плит перекрытий. Производство этих плит...
-
Необходимость введения нового ограничения может возникнуть, например, когда первоначально для сокращения затрат машинного времени некоторые интуитивно...
-
Статистическая неопределенность и процедуры со многими решениями Все существующие методы фильтрации (минимальное остовное дерево, максимальный плоский...
-
Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
Построение исходного опорного плана - Экономико-математические методы
Моделирование экономический математический опорный Построение опорных планов, а также их преобразование будем производить непосредственно в...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Значит и Вторая теорема двойственности (теорема о дополняющей нежесткости) Пусть - допустимое решение прямой задачи, а - допустимое решение двойственной...
-
Вводим дополнительные ограничения в модель: А) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и...
-
Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это...
-
Алгоритм использует в качестве исходных данных документы, содержащие следующие сведения: X A, k,j, i - измеряемые показатели научной работы; X A, TG,...
-
Задача №1 (Вариант 12) - Экономико-математические методы и модели в логистике
Условие задачи Производственная компания может закупить сырье для четырех своих заводов у трех поставщиков. Стоимость перевозки сырья в расчете на одну...
-
Решение: Строим на плоскости х1Ох2 многоугольник решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки...
-
Любое частное решения уравнения (1) на координатной плоскости х0у изображено в виде графика функции у=у (х, с) (с=const). В теории дифференциальных...
-
Динамическое программирование Динамическое программирование -- один из разделов оптимального программирования, в котором процесс принятия решения и...
-
Формирование З -областей в матрице R осуществляется в процессе ее эволюционной модификации. Эволюционная модификация матрицы R производится путем...
-
Как известно решение задач симплексным методом применяется очень часто. Это связано с тем, что симплексный метод подходит для решения широкого круга...
-
Постановка задачи - Методика решения задачи целочисленного программирования
Сформулировать по заданному 24-хзначному числу модель целочисленного программирования вида: Где все параметры модели должны быть определены из следующих...
-
Транспортная задача - Основы экономико-математического моделирования
На трех складах А 1, А 2 и А 3 хранится А 1=100, А 2=200, а 3=60+10 N единиц одного и того же груза, соответственно. Этот груз требуется доставить трем...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
Задача о загрузке рюкзака (задача о ранце) - Метод динамического программирования для решения задач
Постановка задачи. Пусть имеются N видов грузов с номерами. Единица груза j-го вида имеет все aJ. Если груз j-го вида берется в количестве xJ, то его...
-
Минимальное остовное дерево в связанном взвешенном неориентированном графе-это остовное дерево данного графа, в котором сумма весов, входящих в него...
-
С целью формализации задачи введем необходимые обозначения: I - код изделия (i = 1,...,n); ХI - искомый объем выпуска годовой программы по i-му изделию;...
-
Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й...
-
Основные задачи анализа временных рядов - Динамические ряды
Принципиальные отличия временного ряда от последовательности наблюдений, образующих случайную выборку, заключаются в следующем: Во-первых, в отличие от...
-
Экономические задачи, сводящиеся к транспортной модели Транспортная модель используется для составления наиболее экономичного плана перевозок одного вида...
-
Введение - Приложение интегрального и дифференциального исчисления к решению прикладных задач
Целью данной курсовой работы является самостоятельное изучение следующих разделов высшей математики: задачи линейного программирования (симплексный и...
-
Для примера рассмотрим вытекающую из общей постановки (3),(4) двухкритериальную () многоэтапную динамическую задачу, с целевыми функциями дохода и потерь...
Опорное решение транспортной задачи - Анализ транспортной задачи по критерию времени