Транспортная задача

Транспортные модели описывают перемещение (перевозку) какого-либо товара из пункта отправления (исходный пункт, например место производства) в пункт назначения (склад, магазин, грузохранилище). Назначение транспортной задачи — определить объем перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок. При этом должны учитываться ограничения, налагаемые на объемы грузов, имеющихся в пунктах отправления (предложения), и ограничения, учитывающие потребность грузов в пунктах назначения (спрос). В транспортной модели предполагается, что стоимость перевозки по какому-либо маршруту прямо пропорциональна объему груза, перевозимого по этому маршруту. От того, насколько рационально будет прикрепление пунктов потребления к пунктам производства, зависит объем транспортной работы.

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

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

Параметры задачи.

Имеется m пунктов производства А₁, …, А_m однородного продукта и n пунктов потребления В₁,…, В _n.

Предложение поставщика в каждом i-м пункте составляет а_i единиц, i = 1, . . ., m.

Спрос потребителя в каждого j-ом пункте составляет b_j единиц, j = 1, . . .. n.

Транспортные расходы на перевозку единицы продукции из А_i в В_j составляет c_ij (себестоимость, расстояние, тариф, время, расход топлива).

Требуется определить оптимальный план перевозок, при котором суммарные транспортные расходы минимальны продукции (управляющий параметр - количество продукции, перевозимой от каждого поставщика к каждому потребителю).

Обозначим x_ij – количество продукции, перевозимой от i-го поставщика j-му потребителю

i = 1, . . ., m, j = 1, . . .. n.

Математическая модель задачи

Суммарные затраты на транспортировку из всех пунктов производства во все пункты потребления:

тр

Управляющий параметр: x_ij ≥ 0 , - количество единиц продукции, поставляемой из А_i в В_j – перевозки из пунктов потребления в пункты производства исключены.

Ограничения

Суммарное предложение должно быть не меньше суммарного спроса

В каждый пункт потребления доставляется продукции не менее необходимой

,

От каждого поставщика вывозится продукции не более имеющейся

.

Всякое неотрицательное решение систем уравнений называется опорным планом (совокупность чисел x_ij , , , удовлетворяющая приведенным ограничениям). Решение X*=(x_ij ), при котором функция S принимает минимальное значение - называется оптимальным планом транспортной задачи.

Это общая задача линейного программирования – ограничения в виде неравенств (несбалансированная транспортная модель).

Модель, в которой ограничения имеют вид равенств, называется сбалансированной транспортной моделью.

Несбалансированная модель может быть приведена к сбалансированной – неравенства заменены равенствами (в общем случае путем введения фиктивных неотрицательных переменных – фиктивного поставщика или потребителя продукции).

Замкнутая транспортная модель предполагает ограничения в виде равенств:

- сумма спроса равна сумме предложений;

- спрос каждого пункта потребления удовлетворяется полностью;

- весь продукт из каждого пункта производства должен быть вывезен.

Особая структура замкнутой транспортной задачи (все ограничения имеют вид равенств) позволяют решать ее простыми методами.

На пересечении i-ой строки и j-го столбца стоит тариф с и сюда же заносится значение х_ij – количество продукции, поставляемой от i-го поставщика j-му потребителю.

При большой размерности задачи (m x n) отыскание оптимального плана путем непосредственного перебора становится трудоемкой. Решение транспортной задачи состоит из двух этапов: нахождение начального плана, улучшение его и получение оптимального плана перевозок.

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

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

Хотя транспортная задача может быть решена как обычная задача линейного программирования, ее специальная структура позволяет разработать алгоритм с упрощенными вычислениями(на основе симплекс-метода).

Для решения транспортной задачи составляется транспортная таблица.

Примеры сведения практических задач к канонической транспортной задаче

Многие практические задачи, связанные с планированием перевозок, не укладываются в рамки рассмотренной задачи, так как осложнены дополнительными ограничениями.

Суммарный объем производства больше потребления - может быть введен фиктивный пункт потребления В_n+1 с объемом потребления

b_{n+1 =} b_n+1 – суммарный объем нереализованного продукта.

Размеры остатков в разных пунктах производства можно регулировать введением штрафа за единицу нереализованного продукта А_i.

Суммарный объем производства меньше потребления, то полное удовлетворение всех пунктов потребления невозможно. В этом случае необходимо организовать перевозки всего произведенного продукта так, чтобы наиболее важные пункты удовлетворялись полнее, и при этом суммарные транспортные расходы должны быть минимальны – вводится величина ущерба r_j при неудовлетворении пункта В_j.

Требуется минимизировать суммарные затраты

при условиях

, , x_ij > 0, y_j = b_j - , где

y_j – разность между потребностями пункта В_j и поставками в него.

Перевозки с резервированием.

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

I_к – совокупность номеров i-го пункта производства в к-ом районе.

Требуется организовать перевозки таким образом, чтобы в к-ом районе (к=1,…,s) сохранилось не менее V_к единиц продукта.

- V_к , .

Общее число продуктов, вывезенных из всех пунктов производства к-го района должно быть не менее, чем на V_к (величину заданного резерва) меньше суммарного количества продукта, произведенного в этом районе.

Задача сводится к задаче транспортного типа

При условиях

- удовлетворение спроса каждого пункта потребления;

из каждого пункта производства не может быть вывезено продукта

больше, чем производится;

- V_к , - условие резервирования;

x_ij ≥ 0 , - объем перевозок неотрицательные числа (перевозки запрещены из пунктов потребления в пункты производства).

Пришли к задаче планирования перевозок, обеспечивающего удовлетворение спроса всех пунктов потребления, и гарантирующего сохранение требуемых резервов в каждом районе.

Ограничения на пропускные способности магистралей (в ограниченный промежуток времени) не позволят реализовать оптимальный план перевозок, полученный без учета этих ограничений.

В этом случае в транспортной задаче условие x_ij ≥ 0 , заменяется неравенством вида 0 ≤ x_ij ≤ d_ij, где dij – пропускная способность магистрали (ij), т.е. максимальный объем продукции, который может быть перевезен по этой магистрали за рассматриваемый промежуток времени. Такая задача может быть вообще неразрешимой (когда пропускная способность всех магистралей, ведущих к j-му потребителю меньше объема его потребностей).

Перевозки с промежуточной обработкой.

Задача может быть осложнена наличием промежуточных транспортных узлов, в которых производится обработка груза (перевалка на другой вид транспорта, доработка полуфабриката перед поступлением его в пункт потребления).

А₁,…, А_m – пункты производства с объемами производства а₁, …, а_m

В₁,…, В_n – пункты потребления с объемами потребления b₁,…, b_n

С₁,…, С_к – пункты промежуточной обработки.

Возможности пункта промежуточной обработки С_λ ограничены d_λ единицами продукта.

Стоимости перевозки единицы полуфабриката продукта из А_i в С_λ составляет С_iλ‘, стоимость перевозки единицы полуфабриката продукта из С_λ в В_j составляет С_λj“.

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

Математическая модель.

Z_iλj – количество продукта, доставляемое из пункта А_i в В_j через С_λ.

Транспортная таблица

Определить план перевозок {Z_iλj}, на котором достигается минимум линейной формы

( С_iλ‘ + С_λj“) Z_iλj → min

при условиях

Z_iλj = а_i

Z_iλj = b_j

Z_iλj ≤ d_λ

Z_iλj ≥ 0, , ,

Необходимое и достаточное условие разрешимости задачи

а_i = b_j ≤ d_λ

Преобразуем, введя новые переменные

x_i,n+λ – количество полуфабриката, поступающее из пункта производства А_i в пункт обработки С_λ.

x_m+λ,j - количество полуфабриката, поступающее из пункта обработки С_λ в пункт потребления В_j.

x_i,n+λ = Z_{iλj ,} , .

x_m+λ,j = Z_iλj, , .

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

С_iλ‘x_i,n+λ + С_λj“ x_m+λ,j

при условиях

x_i,n+λ = а_i , ,

x_m+λ,j = b_j ,

x_i,n+λ = x_m+λ,j ≤ d_λ

x_i,n+λ ≥ 0, x_m+λ,j ≥ 0, , , .

7.3 Распределительные задачи линейного программирования

Задачи распределения применяются при планировании множества операций, требующих одни и те же ресурсы и одно и то же оборудование. Предполагается, что каждая операция может быть выполнена многими способами, но для выполнения каждой операции наиболее подходящим путем не хватает ресурсов и оборудования. Задача заключается в том, чтобы, используя ограниченные мощности и наличные материалы, выполнить все работы оптимальным образом.

Задачи распределения в общем виде можно разделить на два вида:

1. Задан объем работ. Имеются определенные ресурсы, т.е. фиксированные производственные мощности и количество материалов. Необходимо найти такой вариант использования ресурсов, который обеспечит минимальные затраты на выполнение заданных работ;

2. Заданы определенные материалы и оборудование (ресурсы). Необходимо определить, какая работа дает максимальную прибыль при использовании этих ресурсов.

Несмотря на требование линейности функций критериев и ограничений, в рамки линейного программирования попадают многочисленные задачи распределения ресурсов, управления запасами, сетевого и календарного планирования, транспортные задачи и прочие. Рассмотрим некоторые из них.

Примеры распределительных задач.

План снабжения предприятий. Имеются сырьевые базы и предприятия-потребители. Требуется разработать такой план снабжения сырьем каждого предприятия (с какой базы, в каком количестве, каким видом транспорта и какое сырье доставляется), чтобы потребности в сырье были обеспечены при минимальных расходах на перевозки. Здесь показатель эффективности – суммарные расходы на перевозки сырья в единицу времени (R → min).

Постройка участка магистрали. При постройке участка магистрали в распоряжении имеется определенные средства (трудовые и материальные ресурсы), требуется спланировать строительство (распределить ресурсы) так, чтобы строительство было завершено в минимальный срок. Здесь необходимо учитывать случайные факторы (метеоусловия, отказы техники), и тогда показатель эффективности – среднее ожидаемое время окончания строительства (Т → min).

Сеть торговых точек. Требуется спланировать количество торговых точек, их размещение, товарные запасы, чтобы обеспечить максимальную экономическую эффективность распродажи. Здесь показатель эффективности – средняя ожидаемая прибыль от реализации товаров (П → mах).

Задача о комплексном использовании сырья. Исходное сырье или материал может перерабатываться различными технологическими способами. В каждом случае получается в различном сочетании несколько видов продукции. Требуется найти план переработки, при котором заданные объемы конечной продукции получались бы с наименьшими затратами исходных материалов. Одним из распространенных примеров применения этого типа задач является оптимальный раскрой материалов.

Противолодочный рейд. Требуется рационально организовать боевую операцию по уничтожению подводной лодки группой самолетов (выбрать маршруты самолетов, высоту полета, способ атаки). Здесь показатель эффективности – вероятность того, что лодка будет уничтожена.

Распределение изделий между предприятиями (оборудования между участками) – минимизация суммарных затрат на изготовление всех изделий с учетом времени производства;

Регулирование парка вагонов (распределение вагонов разных типов под различные грузы) -минимизация суммарных затрат на погрузку;

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

Рассмотрим некоторые примеры.

Дата добавления: 2014-08-04; просмотров: 840; Нарушение авторских прав

Мы поможем в написании ваших работ!