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

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

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

Матрица – план перевозок.

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

минимум суммарных затрат. Следовательно, целевая функция имеет вид:

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

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

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

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

Рассказать про циклы. Набор клеток, из которых нельзя построить цикл называется ациклическим. Для того чтобы допустимое решение было опорным, необходимо чтобы набор базисных клеток таблицы был ациклическим.