Формулировка транспортной задачи
Исходные данные транспортной задачи записываются в виде таблицы
Система ограничений состоит из двух групп уравнений
Формулировка транспортной задачи такова:
при ограничениях
Опорный и оптимальный план транспортной задачи
Необходимое и достаточное условие разрешимости транспортной задачи
Искусственные потребители и поставщики
Используемая литература:
848.00K

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

1.

Выполнила:
студентка 5 курса,
факультета Математики,
Информатики, Физики
Группы И - 51
Ченцова Е.А.
Научный руководитель:
Астахова Н.А. к. п. н. , доцент

2. Формулировка транспортной задачи

Транспортная задача в общем виде состоит в
определении оптимального плана перевозок
некоторого однородного груза
из m пунктов отправления А1 А2,,..., Аm
в n пунктов назначения B1 ,B2 ,…, Bn
В качестве критерия оптимальности можно взять
минимальную стоимость перевозок всего груза, либо
минимальное время его доставки.

3.

Неизвестными транспортной задачи являются
объёмы перевозок от каждого i-го поставщика
каждому j–му потребителю.
В транспортных задачах под поставщиками и
потребителями понимаются различные
промышленные и сельскохозяйственные предприятия,
заводы, фабрики, склады, магазины и т.д. Под
стоимостью перевозок понимают тарифы, расстояния,
время, расход топлива и т.п.

4.

Рассмотрим задачу с первым критерием
(минимальная стоимость перевозок всего груза),
обозначив:
Cij - тарифы перевозок единицы груза из i-гo
пункта отправления в j-й пункт назначения
ai - запасы груза в пункте Аi
bj - потребности в грузе пункта Bj
xij - количество единиц груза, перевозимого из i-гo
пункта в j-й пункт.

5. Исходные данные транспортной задачи записываются в виде таблицы

Bj
B1

B2
Bn
ai
Ai
A1
c11
c12

c1n
a1
A2
c21
c22

c2n
a2






Am
cm1
cm2

cmn
am
bj
b1
b2

bn
предложение
спрос

6.

Целевая функция имеет вид:
m
n
Z cij xij
i 1 j 1

7. Система ограничений состоит из двух групп уравнений

Первая группа из m уравнений описывает тот факт,
что запасы всех поставщиков вывозятся полностью:
n
x
j 1
ij
ai
i = 1, 2, …, m.

8.

Вторая группа из n уравнений выражает требование
полностью
удовлетворить
запросы
всех
n
потребителей:
m
xij b j ,
j = 1, 2,…, n
i 1
Кроме этого, переменные задачи должны быть
неотрицательны:
xij 0
i = 1, 2, …, m
j = 1, 2, …, n

9. Формулировка транспортной задачи такова:

Найти переменные задачи X ( xij ), i 1,2,...n, j 1,2,...m,
удовлетворяющие системе ограничений ,
n
xij ai
j 1
m
i = 1, 2, …, m
xij b j
j = 1, 2, …, n
i 1
а также условию неотрицательности переменных
и обеспечивающие минимум целевой функции
Z
m
n
c
i 1
j 1
ij
xij

10.

Пример: Данные задачи представлены в следующей
таблице. Составить математическую модель задачи.
Bj
B1
B2
B3
B4
ai
Ai
A1
2
5
8
1
9
A2
8
3
9
2
16
A3
7
4
6
3
5
bj
11
7
8
4
30
30

11.

Решение: Пусть xij - объемы перевозок груза от i-го
поставщика – j-му потребителю. В таблице
представлены затраты на перевозку единицы груза от
поставщика – потребителю.
Целевая функция имеет вид :
Z 2 x11 5 x12 8 x13 x14 8 x21 3 x22 9 x23
2 x24 7 x31 4 x32 6 x33 3 x34 min

12. при ограничениях

1)
x11 x12 x13 x14 9
x 21 x 22 x 23 x 24 16
x31 x32 x33 x34 5
n
(Условие
x11
2)
xij
a i , i = 1, 2, …, m)
j 1
x 21 x31 11
x12 x 22 x32 7
x13 x 23 x33 8
x14 x 24 x34 4
m
(Условие
x ij
i 1
j = 1, 2, …, n)
bj

13. Опорный и оптимальный план транспортной задачи

Всякое неотрицательное решение систем ограничений
определяемое матрицей X = (xij ), называют опорным
планом ТЗ, а план при котором функция Z принимает
минимальное значение - называется оптимальным
планом ТЗ.

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

Если общее количество груза в пунктах отправления и
общая потребность в нем в пунктах назначения
совпадают, т.е.
m
a
i 1
i
n
b
j 1
j
Модель такой задачи называется закрытой,
в противном случае открытой.

15. Искусственные потребители и поставщики

Если спрос меньше предложения, то необходимо
вводить искусственного потребителя Bn+1
Если спрос больше предложения, то необходимо
вводить искусственного поставщика Am+1

16. Используемая литература:

Борзунова Т.Л., Барыкин М.П. , Данилов Е.А.
Соловьева О.Ю. - Математическое моделирование:
учебное пособие/ВолгГТУ, - Волгоград, 2008.
Конюховский П.В. Математические методы
исследования операций в экономике – СПб: Питер,
2000.
English     Русский Правила