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

Пусть в ТЗ задано время t_ij, за которое груз можно перевезти из i- го в j- й пункт. Оно не зависит от перевозимого груза. Заданы запасы а_i, заявки b_j и необходимо составить такой план перевозок, чтобы общее время окончания перевозок было бы минимальным.

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

Таким образом, критерий в нашей задаче

Ограничения те же:

Заметим, что целевая функция Т (Х) имеет нелинейный вид, поэтому для решения ТЗ по критерию времени нельзя применить теорию линейного программирования. Для ее решения можно построить последовательность нескольких задач линейного программирования. Рассмотрим наиболее простой эвристический алгоритм.

Эвристическими называю такие алгоритмы, которые обеспечивают разумность поиска оптимального решения, но не основываются на строгой математической теории и в связи с этим не вполне гарантируют результат. Тем не менее, эвристические процедуры чрезвычайно распространены, например, при игре в шахматы, при составлении компьютерных программ и т. д.