Метод минимального элемента (тарифа)

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

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

Существуют разновидности метода:

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

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

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

Рассмотрим на примере классический метод минимального тарифа:

bj ai

1. x₁₃=min(160,190)=160

2. x₃₂=min(170,50)=50

3. x₃₃=min(170-50,190-160)=30

4. x₂₁=min(140,120)=120

5. x₃₄=min(170-50-30,110)=90

6. x₂₄=min(140-120,110-90)=20

Покажем, что распределение поставок, по методу минимального тарифа будет эффективнее, т.е. мы будем находиться к оптимальному решению ближе.

Z₀^с-з=7*120+8*40+5*10+9*130+3*60+6*110=3220 д.е.

Z₀^min=1*160+4*120+8*20+2*50+3*30+6*90=1530 д.е.

Стоимость перевозок опорного плана, найденного по методу минимального тарифа более чем в два раза меньше стоимости перевозок опорного плана, найденного по методу северо-западного угла.

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

Это является достоинством данного метода, а его недостатком по сравнению с методом северо-западного угла, является большая трудоёмкость.

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

bj ai

1. x₁₃=min(160,190)=160

2. x₂₁=min(140,120)=120

3. x₂₂=min(140-120,50)=20

4. x₃₂=min(170,50-20)=30

5. x₃₃=min(170-30,190-160)=30

6. x₃₄=110

m+n-1=6

Z₀^{min поставщ.}=1*160+4*120+5*20+2*30+6*110+3*30=1550 д.е.

Замечания:

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

2. Если в задаче не будет сделана оговорка, в чьих интересах она решается, то распределение поставок по методу минимального тарифа будем вести классическим методом без предпочтения чьих-либо интересов.