Построение опорного плана перевозокдля транспортной задачи

Занятие 4. Построение опорного плана перевозок.

Метод минимальных элементов.

Цель образования: Изучение метода минимальных элементов для построения опрного плана перевозок

Цель развития: Развитие логического мышления

Цель воспитания: Воспитание интереса к предмету, к экономическим процессам.

Суть метода состоит в том, что в матрице стоимостей С = {c_ij} выбирается стоимость минимальной перевозки c_ij. Затем назначается максимальный объём ресурса от производителя I к потребителю j для данной перевозки. При этом возможны три варианта:

1) производитель I имеет ресурса больше, чем надо потребителю j. В этом случае удовлетворяется полностью заявка потребителя j, а остаток произведённого ресурса будет распределён после. Так как потребность потребителя j удовлетворена полностью, то исключается из рассмотрения столбец матрицы стоимости, принадлежащий j-му потребителю.

2) производитель I имеет ресурса меньше, чем надо потребителю. В этом случае весь имеющийся ресурс производителя I назначается потребителю j. Недостающая часть ресурса потребителю j будет назначена потом. Так как весь ресурс производителя I исчерпан полностью, то из рассмотрения удаляется строка матрицы стоимости, принадлежащая производителю I.

3) производитель I имеет ресурса столько, сколько надо потребителю j. В этом случае, аналогично рассмотренным выше случаям, из рассмотрения удаляются и строка, и столбец матрицы стоимости.

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

Полученный опорный план перевозок более экономичен, чем опорный план, полученный методом северо – западного угла.

Примеры. Составить опорный план перевозок методом минимальных элементов и определить стоимость перевозок.

1.

2.

3.

4.

5.

6.