1. Транспортная задача
1
Содержательная постановка
Пусть имеются n поставщиков A1, A2,…, An
товара, запасы которых составляют соответственно а1, а2, … , аn единиц.
Пусть имеются m потребителей В1, В2,…, Вm
товара, потребности которых составляют соответственно b1, b2, … , bmединиц .
Известна стоимость Cij (; ) перевозки единицы товара от i–го () поставщика к j–му
потребителю. |
2 |
!!!
Задача заключается в том, чтобы
организовать план перевозок товара от поставщиков к потребителям таким образом, чтобы
стоимость перевозок была минимальна. При этом весь товар должен быть вывезен, и все потребители удовлетворены.
3
Формальная постановка
Введем переменную
xij (– объем товара, перевозимого от i– го () поставщика j–му () потребителю.
Данные задачи удобно представлять в таблице:
4
|
В1 |
|
|
A |
x |
11 |
c11 |
1 |
|
|
|
A2 |
x21 |
c21 |
|
… |
… … |
||
Ai |
xi1 |
ci1 |
|
… |
… … |
||
An |
xn1 |
cn1 |
|
|
b1 |
|
|
В2
x12 c12
x22 c22
… …
xi2 ci2
… …
xn2 cn2
b2
…
…… 
…
…
…
…
…
…
Вj
x1j c1j 
x2j c2j
… …
xij cij
… … 
xnj cnj
bj
…
……
……
……
……
……
... … … … 
Вm
x1m c1m
x2m c2m
… … 
xim cim
… …
xnm cnm
bm
a1 a2
…
ai
…
an
5
;
- стоимость перевозки «от всех ко всем», т.е. стоимость всего плана перевозок;
Итак,
6
Поскольку все товары должны быть вывезены, то:
Поскольку все потребители должны быть удовлетворены, то:
7
Модель транспортной задачи, в которой объем запасов совпадает с объемом потребностей, называется
закрытой. Иначе – открытой.
Мы будем рассматривать закрытую модель, поэтому:
Кроме того, объем перевозки не может быть отрицательным, поэтому:
8
Таким образом, формальная постановка транспортной задачи имеет вид:
целевая функция
ограничения
9
???
К какому виду оптимизационных задач относится транспортная задача?
10