конспект лекций, вопросы к экзамену

Алгоритм решения транспортных задач на минимум стоимости перевозок.

Алгоритм решения транспортной задачи имеет четкую  структуру и включает в себя этапы:
На 1м этапе определяют состояние исходной системы, если запасы груза равны их потребности, то такая система называется закрытой и ее можно решить в соответствии с выбранным критерием оптимальности.

Если потребности в грузе не равны их запасам, то такая система называется открытой.
Для того, чтобы решить такую систему ее следует свести к закрытой.
Для этого добавляют фиктивного поставщика или потребителя у которого тарифы на перевозку =0

На 2м этапе строится опорный план .Для его формирования могут быть использованы методы:

  • северо-западного угла
  • минимального элемента
  • аппроксимации

На 3м этапе проверяют 1й опорный план на оптимальность. Для этого используют метод потенциала. Если опорный план отвечает признаком оптимальности, то рассчитывают целевую функцию.

Если опорный план не отвечает условиям оптимальности, то стоят цикл, т.е перераспределяют грузы между заявленными потребителями.

Новый опорный план с помощью метода потенциалов проверяют на отимальность.

14.01.2017; 20:00
просмотров: 82