<<
>>

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. ДВА ФУНДАМЕНТАЛЬНЫХ ПРИНЦИПА СВЯЗЕЙ С ОБЩЕСТВЕННОСТЬЮ: ЯСНОСТЬ Н НЕПРОТИВОРЕЧИВОСТЬЯсность постановки задач