Всего на сайте:
183 тыс. 477 статей

Главная | Строительство

Формулировка транспортной задачи. Математическая модель  Просмотрен 220

Задача: Однородный груз, имеющийся в m пунктах отправления (производства) в количествах а1, а2, ..., аm единиц, требуется доставить в каждый из n пунктов назначения (потребления) в количествах b1, b2 ..., bn единиц. Стоимость перевозки (тариф) единицы продукции из i-ого пункта отправления в j-ый пункт назначения составляет cij (i=1, …, m; j=1, …, n). Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозится, и запросы всех пунктов потребления удовлетворяются

Исходные данные ТЗ записываются в таблице:

ПН   ПО n Запасы    
  c11   c12   …   c1n a1
          
  c21   c22   c2n a2
          
   
m   cm1   cm2   cmn am
          
Потреб- ности b1 b2 bn     

 

Пусть xij – количество груза перевозимого с i-ого пункта отправления (ПО) в j-ый пункт назначении (ПН). Матрица – план перевозок.

Произведение cij×xij определяет затраты на перевозку груза с i-ого ПО в j-ый ПН. Тогда суммарные затраты на перевозку груза равны . По условию задачи необходимо обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид

.

Так как груз из всех m пунктов отправления вывозиться полностью, то

.

Так как запросы всех n пунктов назначения удовлетворяется полностью, то

.

По смыслу плана xij³0, (i=1,…,m; j=1,…,n)

Следовательно, математическая модель транспортной задачи имеет вид:

. (1)

Замечание. В транспортной задаче m+n уравнений и m×n неизвестных.

В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.

(2)

Такая задача называется задачей с правильным балансом, а ее модель – закрытой. Если равенство (2) не выполняется, т.е. , то задача называется задачей с неправильным балансом, а ее модель – открытой.

 

Предыдущая статья:Понятие об экономических и правовых аспектах информационных технологий Следующая статья:Опорное решение транспортной задачи
page speed (0.0189 sec, direct)