Альтернативные Методы обладают существенно более высокой вычислительной эффективностью (являются специальными алгоритмами для частных случаев задачи линейного программирования)

В случае, если при получении опорного или промежуточного решения произошло вырождение задачи (т. е. получилось менее n+m-1 ненулевых перевозок) к запасам одного склада и потребностям одного потребителя фиктивно добавляется малая величина и производится пересчет транспортной таблицы для соблюдения ограничений:

Пример вырожденной транспортной задачи (условия вырожденности транспортной задачи – количество ненулевых перевозок меньше (n+m-1))

Из плана перевозок видно, что число ненулевых перевозок = 5, а должно быть m+n-1=6.

Для применения существующих алгоритмов решения транспортной задачи необходимо получить допустимый план перевозок с количеством ненулевых перевозок = m+n-1. Для этого вводится малая величина ε следующим образом

Количество непустых клеток плана равно (m+n-1), следовательно можно применять типовые алгоритмы. После получения решения оно округляется (на ε).

• Транспортные задачи с неправильным балансом

Транспортными задачами с неправильным балансом называются транспортные задачи, в которых не выполняется условие:

В связи с этим, одно из условий или. Как следствие различают два вида транспортных задач с неправильным балансом:

Задача с избытком запасов, когда

Для решения такой задачи вводится фиктивный потребитель. Его потребности равны остатку. Нам необходимо знать затраты на перевозки. Затем образуем один столбец и принимаем в нём стоимости перевозок за 0

2) Задача с избытком потребностей(недостаток запасов), когда

1ый случай: Вводится фиктивный склад. Получаем новую строку с нулевыми стоимостями, так как реально склада не существует.

2ой случай: Введение весовых коэффициентов.

(В ряде случаев может применяться комбинация указанных двух методов.)

Транспортная задача с промежуточными пунктами

В общем случае при осуществлении перевозок могут возникать ситуации, при которых маршруты перевозок в какие-либо пункты проходят транзитом через другие пункты (через склады или потребителей). Для решения таких задач полагают, что каждый склад является одновременно потребителем, и наоборот – каждый потребитель является одновременно складом, причем через каждый пункт транзитом проходит весь объем товара. Транспортная таблица такой задачи будет иметь n+m строк (складов) и столько же столбцов (потребителей). Запасы на i-ом складе будут равны a_i+B, а потребности – В,

Где

Здесь рассматривается задача с правильным балансом. Соответственно потребности каждого потребителя составят b_j+B, а запасы – В. Стоимость перевозки товара внутри одного пункта с_ii равна нулю. После указанных преобразований транспортная задача с промежуточными пунктами является стандартной транспортной задачей и решается существующими методами. Полученные перевозки уменьшаются на В. (Существуют другие алгоритмы сведения транспортной задачи с промежуточными пунктами к стандартной транспортной задаче, обычно учитывающие конкретные особенности существующего множества допустимых маршрутов и, в силу этого, являющиеся более эффективными с вычислительной точки зрения)

Транспортная задача с минимизацией времени перевозок

Частный случай нелинейных транспортных задач. Имеет вид:

Определить X^*={x_ij^*}, i=1,…,n, j=1,…,m, такой что:

• Здесь t_ij – время перевозки продукции с i-ого склада j-ому потребителю.

• Решение такой задачи также может быть осуществлено методом псевдостоимостей, при этом: в транспортной таблице вместо стоимостей c_ij используются времена перевозок t_ij.

• После получения решения транспортной задачи определяется ненулевая перевозка с максимальной длительностью. Из транспортной таблицы исключается маршрут, соответствующий этой перевозке (для этого время перевозки полагается равным очень большой величине) и задача решается заново. Этот процесс повторяется до тех пор, пока при переходе к последующему решению не произойдет увеличение длительности самой долгой перевозки в полученном оптимальном решении.

Сезонные изменения

Имеют место сезонные изменения спроса, связанные с ограничениями на время года.

Колебания спроса напрямую влияют на объём выпуска.

Многопродуктовая сеть

Фиксированный объём транспортных средств

Задача о назначениях

"Лучший работник для выполнения данной работы" — вот подходящее

Краткое описание задачи о назначениях. В этой задаче необходимо назначить

Работников на определенные работы; каждый работник может выполнять лю-

Бую работу, хотя и с различной степенью мастерства. Если на некоторую работу

Назначается работник именно той квалификации, которая необходима для ее

Выполнения, тогда стоимость выполнения работы будет ниже, чем при назна-

Чении на данную работу работника неподходящей квалификации. Цель задачи —

Найти оптимальное (минимальной стоимости) распределение работников по

Всем заявленным работам.

Существуют специальные алгоритмы решения задач о назначениях.

Можно использовать избыток запасов и исполнителей (т. е. решать как вырожденную задачу, взяв ε=0.0001)

Относится к сетевым задачам

Техническая постановка: Имеется n пунктов, которые все должны быть

Связаны дорожной сетью. Расстояние между пунктами известно.

Определить: Такую структуру дорожной сети, чтобы суммарная

Длина дорог была минимальна.

С математической точки зрения: Имеется граф с известными

Длинами рёбер. Требуется найти дерево-остов данного графа с

Минимальной суммарной длиной рёбер.

(дерево-остов – минимальный связный подграф данного графа)

Формализованная постановка задачи:

Есть N пунктов и расстояния между ними C_ij.

W= Cij=0;

Ограничения: k=

Техническая постановка: Имеется 2 пункта, связанных между

Собой дорожной сетью, проходящей ещё через какие-либо пункты.

Длины дорог между любыми пунктами известны. Требуется

Определить кратчайший маршрут между указанными двумя

Пунктами.

Математическая постановка: имеется граф с заданной длиной

Всех рёбер. Требуется на графе определить цепь, связывающую

Все заданные вершины и имеющую минимально возможную длину.

Условие: все ребра имеют неотрицательную длину.

Если вместо расстояния положим стоимость, то это напоминает

Транспортную задачу с промежуточными пунктами. Можно сказать, что

Перевозим единицу груза из первого пункта в последний при

Минимальной суммарной длине маршрута.

Формально:

Классическая постановка задачи о максимальном потоке имеет вид:

Имеется I пунктов еi, соединенных дорогами vij с пропускными способностями

Сij. Требуется определить максимальный суммарный поток, проходящий из

Исходного пункта es в конечный пункт et.

Можно считать, что исходный пункт является первым, а конечный пункт –

Последним.

Метод сечения (метод разрезов)

Разрезом на связном графе называется множество рёбер, удаление которых

Превращает граф в 2 несвязных подграфа (т.е. источник и исток оказываются в

Разных подграфах).

Максимальным является поток, который минимален из всех по объёму товара,

который можно передать из исходного пункта в конечный.

Максимальный поток в направлении равен z, где

ограничения:

входящий поток = исходящему

Xij – объём товара, перемещаемый от вершины ik к вершине j.

Сетевое планирование – математические методы управления проектами (сложными комплексами работ).

Сетевое планирование подразумевает следующее:

• Формируется перечень работ

Используем вертикально-горизонтальную структуру. При этом возможен

Внутренний обмен информацией и использование разработок в других

Проектах.

• Определение временной зависимости между работами

• Упорядочение работ (ранжирование)

Возможны 2 варианта представления сетевой таблицы:

Работы- вершины графа, а связь между ними- рёбра.

«-» невозможно учесть длительность

Работ

«+» метод лёгок для модификаций

Работы – рёбра графа. В качестве вершин – формальные события,

Соответствующие завершению тех или иных работ.

Обычно выбирают второй вариант.

Затем получают сетевую временную таблицу и сетевой временной граф.

- длительность работ

Пример сетевой временной таблицы

Пример сетевого временного графа