Методическое пособие для выполнения контрольной работы по дисциплине


Транспортная задача. Общие понятия



бет5/14
Дата01.03.2024
өлшемі0.49 Mb.
#493617
түріМетодическое пособие
1   2   3   4   5   6   7   8   9   ...   14
Garmashov MetodyOptimResheny ZAOChNO

Транспортная задача. Общие понятия
Одним из основных понятий в прикладной математике является понятие «сеть». Раздел прикладной математики, изучающий сетевые модели, называется сетевым планированием.
Основными примерами сетевых задач можно назвать следующие:
- транспортная задача (система «производители-потребители»);
- задача назначений («работы-исполнители»);
- задача о кратчайшем пути (с выбором промежуточных пунктов);
- задача коммивояжера (агент по сбыту должен посетить n городов по одному разу).
Сеть представляет собой линейный граф, состоящий из узлов (вершин, точек) и множества дуг (ребер, звеньев), соединяющих различные пары узлов. На каждой дуге задана ориентация (направление). Таким образом, сеть является ориентированным графом.
Последовательность дуг без учета ориентации из узла i в узел j называется путем между узлами. Если i=j, то путь называется контуром.
Сеть называется связной, если между любой парой узлов существует хотя бы один путь.
Путь с учетом ориентации называется ориентированной цепью. Ориентированная цепь, начинающаяся и заканчивающаяся в одном и том же узле, называется ориентированным циклом. Ациклическая сеть не содержит ни одного ориентированного цикла.
Дерево – это связная сеть, содержащая p узлов, p-1 дугу и ни одного контура.
Математическая постановка транспортной задачи
Транспортная задача является типовой задачей для промышленных фирм, имеющих несколько предприятий, складов, рынков сбыта и оптовых баз. В основе транспортной задачи лежит двудольная сеть. Для двудольной сети характерно наличие двух непересекающихся множеств узлов G1 (предприятия, поставщики) и при этом каждая дуга начинается в узле множества G1 и заканчивается в узле множества G2 (потребители, оптовые базы).
Введем следующие обозначения:
ai– запас груза в i-ом пункте отправления;
bj – потребность в j-ом пункте назначения;
cij – тариф перевозки единицы груза из i-го пункта отправления в j-ый пункт назначения;
xij – количество единиц груза, перевезенного из i-го пункта отправления в j-ый пункт назначения;
Q – целевая функция (затраты на перевозку всех грузов).
Тогда транспортная задача математически будет записана в следующем виде:

план ТЗ
является оптимальным планом ТЗ с минимальным значением целевой функции Q.
Транспортную задачу легко представить в виде таблицы, в основных ячейках которой записываются два числа тариф cij и количество перевозимого груза xij. В последнем столбце таблицы записываются суммы перевозимых грузов для данного пункта отправления (запасы), в последней строке записываются суммы перевозимых грузов для данного пункта назначения (потребности).
Таблица. Табличное представление транспортной задачи

Пункты
назначений
Пункты
отправлений

B1

B2



Вj



Bn

Запасы

A1

с11
х11

с12
х12



c1j
x1j



c1n
x1n

a1

:

:

:

:

:

:

:

:

Ai

ci1
xi1

ci2
xi2



cij
xij



cin
xin

ai

















Am

cm1
xm1

cm2
xm2



cmj
xmj



cmn
xmn

am

Потребности

b1

b2



bj



bn




Общее наличие груза у поставщиков составляет , а общая потребность в грузе у потребителей равна . Если выполняется условие , то такая транспортная задача называется закрытой, в противном случае – открытой.
Необходимым и достаточным условием разрешимости транспортной задачи является ее закрытость.
Открытую транспортную задачу легко свести к закрытой. Так, если , то вводят -й пункт назначения (склад) с потребностью . Если , то вводят фиктивный -й пункт отправления (конкурент) с запасом груза .
Мы будем рассматривать только закрытые Т3. При этом число переменных равно n*m, а число уравненийравно n+m-1 (число столбцов плюс число строк минус условие закрытости транспортной задачи).
План называется невырожденным, если число отличных от нуля переменных равно в точности n+m-1, в противном случае вырожденным, когда число отличных от нуля переменных меньше, чем n+m-1.
Решение транспортной задачи обычно осуществляется в две стадии:
- сначала нужно определить опорный план (метод северо-западного угла, метод минимального элемента, метод аппроксимации Фогеля);
- затем оптимизировать полученный план (метод потенциалов).
Существуют методы, которые совмещают процессы составления и оптимизации плана транспортной задачи (метод дифференциальных рент).

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


2. Табличное представление транспортной задачи. Этапы решения транспортной задачи.
3. Открытые и закрытые транспортные задачи. Число уравнений и число переменных в транспортной задаче. Вырожденный и невырожденный планы транспортной задачи.
4. Классификация методов решения транспортной задачи. Устранение неоднозначности при условии одинаковых тарифов.




Достарыңызбен бөлісу:
1   2   3   4   5   6   7   8   9   ...   14




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет