Тема 2: решение транспортных задач 


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



ЗНАЕТЕ ЛИ ВЫ?

Тема 2: решение транспортных задач



Вопросы:

Создание математической модели классической транспортной задачи

Пример решения транспортной задачи в MS Excel

 

 

2.1. Создание математической модели классической транспортной задачи

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

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

Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим путем. Применение математических методов и вычислительной техники для планирования перевозок позволяет автоматизировать решение такого типа задач.

Транспортная задача формулируется следующим образом. Имеется m пунктов производства (A1, …, Am) однородного продукта или взаимозаменяемых продуктов и n пунктов потребления (B1, …, Bn). Заданы объемы производства ai каждого пункта производства и размеры спроса bj каждого пункта потребления в одних и тех же единицах (в штуках, тоннах, вагонах или других единицах измерения). Известны также транспортные издержки cij (расходы), связанные с перевозкой единицы продукта из пункта Ai в пункт Bj. В термин «транспортные издержки» не всегда вкладывается его непосредственный экономический смысл. Транспортные издержки здесь – скорее условное понятие, которое в различных задачах может означать себестоимость, расстояние, тариф, время, расход топлива и т.д.

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

Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Единственным условием разрешимости замкнутой транспортной задачи является равенство суммарного спроса суммарному производству .

Переведем транспортную задачу на формальный язык. Пусть xij – количество единиц продукта, поставленное из пункта Ai в пункт Bj. Суммарные затраты (суммарные транспортные издержки) на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются суммой

. (1)

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

j=1, 2, …, n. (2)

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

i=1, 2, …, m. (3)

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

i=1, 2, …, m, j=1, 2, …, n. (4)

Транспортная задача сводится, таким образом, к минимизации суммарных затрат (1) при условиях (2) – (4). Будем называть задачу (1) – (4) задачей Т.

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

i=1, 2, …, m. (5)

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

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

Открытую модель можно свести к замкнутой, если ввести фиктивный пункт потребления Bn+1 с объемами потребления:

.

 

Пример решения транспортной задачи в MS Excel.

 

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

 

1. Постановка транспортной задачи.

Фирма имеет 4 фабрики и 5 центров распределения ее товаров. Фабрики имеют производственные возможности соответственно 200, 150, 225 и 175 единиц продукции ежедневно. Распределительные центры имеют следующие потребности: 100, 200, 50, 250 и 150 единиц продукции ежедневно. Хранение не поставленной в центр единицы продукции на фабрике обходится в $0,75 в день, а штраф за просрочку поставки заказанной потребителям в центре распределения единицы продукции, но там находящейся, равен $2,5 в день. Стоимость перевозки единицы продукции с фабрик в пункты распределения приведены ниже.

Центры распреде- ления   Фабрики           Производство
  1,5   1,75 2,25 2,25  
  2,5   1,75   1,5  
    1,5 1,5 1,75 1,75  
    0,5 1,75 1,75 1,75  
Потребность            

 

Необходимо так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы.

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

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

В случае перепроизводства – фиктивный пункт распределения; стоимость перевозки единицы продукции в этот фиктивный пункт полагается равной стоимости складирования, а объемы перевозок в этот пункт равны объемам складирования излишек продукции на фабриках;

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

Для решения данной задачи построим ее математическую модель. неизвестными здесь являются объемы перевозок. Пусть xij – объем перевозок с i-той фабрики в j-тый центр распределения. Целевой функцией являются суммарные транспортные расходы, то есть:

,

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

· неотрицательность объема перевозок;

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

Таким образом, модель будет такой:

При ограничениях

,

,

,

где ai – объем производства на i-той фабрике, bj – спрос в j-том центре распределения.

3. Решение транспортной задачи.

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

 

2. Ввести в ячейки диапазона B3:F6 стоимости перевозок.

3. Отвести ячейки диапазона B8:F11 под значения неизвестных (объемов перевозок).

4. Ввести в ячейки диапазона H8:H11 объемы производства на фабриках.

5. Ввести в ячейки диапазона B13:F13 потребность в продукции в пунктах распределения.

6. В ячейку B16 ввести целевую функцию:

=СУММПРОИЗВ(B3:F6;B8:F11)

7. В ячейки диапазона G8:G11 ввести формулы, вычисляющие объемы производства на фабриках, в ячейки диапазона B12:F12 – объемы доставляемой продукции в пункты распределения. А именно:

Ячейка Формула Ячейка Формула

G8 =СУММ(B8:F8) B12 =СУММ(B8:B11)

G9 =СУММ(B9:F9) C12 =СУММ(C8:C11)

G10 =СУММ(B10:F10) D12 =СУММ(D8:D11)

G11 =СУММ(B11:F11) E12 =СУММ(E8:E11)

F12 =СУММ(F8:F11)

Рис.1 Исходные данные транспортной задачи

8. Выбрать команду Сервис | Поиск решения и заполнить диалоговое окно Поиск решения, как показано на рис.2.

Рис.2 Заполненное диалоговое окно Поиск решения

 

9. Нажать кнопку Параметры. На экране отобразится диалоговое окно Параметры поиска решения (Рис.3).

Рис.3 Окно Параметры поиска решения

В этом окне можно изменять условия и варианты поиска решения исследуемой задачи, а также загружать и сохранять оптимизируемые модели. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач. В нашей задаче следует установить флажок Линейная модель, а остальные значения, которые используются по умолчанию, можно оставит так, как они есть и нажать кнопку ОК. На экране опять отобразится окно Поиск решения.

10. Нажать кнопку Выполнить. Средство Поиск решения найдет оптимальный план поставок продукции и соответствующие ему транспортные расходы.

11. После нажатия кнопки ОК результаты будут внесены в рабочий лист (Рис.4).

Рис.4. Оптимальное решение транспортной задачи.

На Рис.4 видно, что план перевозок, при котором суммарные транспортные расходы минимальны и равны 975 долл., должен быть следующим: со склада в Денвере нужно перевезти в Лос-Анджелес 100 единиц продукции, в Даллас – 25 единиц, в Сент-Луис – 50 единиц, в Атланту – 25 единиц; со склада в Бостоне 150 единиц продукции – в Вашингтон; со склада в Нью-Орлеане 100 единиц – в Вашингтон и 125 – в Атланту; со склада в Далласе потребителям в Далласе следует отправить 175 единиц продукции.

 

 



Поделиться:


Последнее изменение этой страницы: 2017-02-19; просмотров: 713; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 44.200.191.146 (0.017 с.)