52. Методика решения транспортной задачи и определение ее допустимых решений

Идея задачи заключается в определении количества груза (запчастей и т.д.), которое необходимо перенаправить от каждого поставщика каждому потребителю, чтобы суммарные транспортные расходы были минимальными (содержательная постановка задачи).

Для составления математической модели:

- вводятся обозначения неизвестных:

Х_ij - количествo груза, транспортируемого от i-го поставщика к j-му потребителю;

- составляется граф-схема задачи;

Граф-схема транспортной задачи

- формируется система ограничений (ОГР), которая показывает связь между значениями искомых переменных в общем виде:

m - число поставщиков; n - число потребителей; а_i запасы i-го поставщика; b_j - заявки j - го потребителя;

- выполняется балансировка ограничений:

Если А=В, т.е. сумма всех запасов равна сумме всех заявок - сбалансированная задача. Если А ≠ В, та задача несбалансированная.

В этом случае ОГР примет вид:

- формируются граничные условия (ГРУ), которые показывают предельно допустимые значения искомых переменных;

x_ij ≥ 0 ;

- составляется целевая функция показывающая в каком смысле решение должно быть наилучшим:

C_ij - стоимость транспортирования единицы груза.

Допустимым решением задачи являются значения переменных, удовлетворяющих граничным условиям и ограничениям.