<<
>>

8.1. Постановка задачи

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

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

прикрепление потребителей ресурса к производителям;

привязка пунктов отправления к пунктам назначения;

взаимная привязка грузопотоков прямого и обратного направлений;

отдельные задачи оптимальной загрузки промышленного оборудования;

оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения.

Имеются т пунктов отправления груза и объемы отправления по каждому пункту аь а2, ..., ат. Известна потребность в грузах Ьь Ь2, Ьп по каждому из п пунктов назначения. Задана матрица стоимостей доставки по каждому варианту Су, і = l,m,j = I, п. Необходимо рассчитать оп-

Таблица 8.1

Исходные данные Поставщики Потребители Запасы (объемы отправления) Вх в2 ... Вп л. С\\ С\2

*12 С\п

х\п А2 С21

*21 ^22

*22 с2п

х2п 02 ... ... * Ат ст\

Хт\ Ст2

хт2 Сщп

Хтп Потребность Ьх Ь2 ьп

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

В общем виде исходные данные представлены в табл. 8.1.

Транспортная задача называется закрытой, если суммарный

т

і

М J

объем отправляемых грузов

равен суммарному объему по^

п

Ibj

U=i .

требности в этих грузах по пунктам назначения

т п

(8.1)

X Д/ = X Ь;.

/=1 y=i

Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой, т. е.:

(8.2)

т п

/=1 у=1

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

(8.3)

j?Xy=ah / = 1,/я.

у=і

Все у пункты (потребители) должны быть обеспечены грузами в плановом объеме:

т —

lXjj=bj, У = (8.4)

/=1

Суммарные объемы отправления должны равняться суммарным объемам назначения:

т п

Xai = Xbj. (8.5)

/=1 у=1

Должно выполняться условие неотрицательности переменных: Ху > 0, / = 1,/я; j = 1 ,п. Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):

т п

zm{n = 2 2 (8.6)

/=1у=1

В модели (8.3) — (8.6) вместо матрицы стоимостей перевозок (с,у) могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транс-портной работы. Как видно из выражения (8.5), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае если

потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;

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

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

Транспортным задачам присущи следующие особенности:

распределению подлежат однородные ресурсы;

условия задачи описываются только уравнениями;

все переменные выражаются в одинаковых единицах измерения;

во всех уравнениях коэффициенты при неизвестных равны единице;

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

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

<< | >>
Источник: Бережная Е.В., Бережной В.И.. Математические методы моделирования экономических систем: Учеб. пособие. — 2-е изд., перераб. и доп. — М.: Финансы и статистика,2006. - 432 е.. 2006

Еще по теме 8.1. Постановка задачи:

  1. 1. АНАЛИТИЧЕСКИЙ ОБЗОР. ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЙ
  2. 1.8 ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ
  3. 3.1 Постановка задачи
  4. Постановка задачи
  5. 1.4 Основные выводы по литературному обзору и постановка задачи исследования
  6. 1.6. Постановка задачи и цели исследований
  7. Глава 1. АНАЛИЗ СОСТОЯНИЯ ВОПРОСА И ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЙ
  8. ГЛАВА I. СОСТОЯНИЕ ВОПРОСА И ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ
  9. 1.1. ПОСТАНОВКА ЗАДАЧИ
  10. 2.1. ПОСТАНОВКА ЗАДАЧИ
  11. Постановка задачи и определение типа модели.
  12. 5.1. ПОСТАНОВКА ЗАДАЧИ УПРАВЛЕНИЯ НОРМАМИ ДЕЯТЕЛЬНОСТИ
  13. 1.1. Постановка задачи календарного планирования
  14. Общая постановка задачи и модель процесса научения.
  15. 2. Модель активной системы и общая постановка задачи управления
  16. 1.Обзор литературы, постановка задачи исследования
  17. ДВА ФУНДАМЕНТАЛЬНЫХ ПРИНЦИПА СВЯЗЕЙ С ОБЩЕСТВЕННОСТЬЮ: ЯСНОСТЬ Н НЕПРОТИВОРЕЧИВОСТЬЯсность постановки задач