Этап 1. Первоначальное закрепление потребителей за поставщиками.

f(X) = 4-30 + 5-30 + 3-70 + 6-30 + 7-Ю + 4-110 = 1170.

Таблица 3.6 Мощности поставщиков Мощности потребителей 30 100 40 110 60 4 ^^ ^^ 30 5 ^^ ^^ 30 2 3 100 1 3 ^^ 70 6 ^^ ^^ 30 2 120 6 2 7 ^^ ^^ 10 4 ^^ ^^ 110 Недостатком данного метода является то, что он не учитывает значения элементов с и матрицы транспортных расходов, в результате чего полученное этим методом начальное распределение (начальный опорный план перевозок) может быть достаточно далеко от оптимального.

В различных модификациях метода наименьших стоимостей заполнение клеток матрицы перевозок проводится с учетом значений величин Сц.

Таблица 3.7 Мощности поставщиков Мощности потребителей 30 100 40 110 60 4 5 2 ^^ ^^ 40 3 ^^ ^^ 20 100 1 ^^ ^^ 30 3 6 2 ^^ ^^ 70 120 6 2 ^^ 100 7 4 ^^ ^^ 20 Порядок заполнения клеток: (2;1), (3;2), (1;3), (2;4), (1;4), (3;4). Суммарные затраты на перевозки, представленные в табл. 3.7, составляют

f(X) = 1-30 + 2-100 + 2-40 + 2-70 + 3-20 + 4-20 = 590.

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

Этап 2. Проверка оптимальности полученного плана перевозок. Введем специальные показатели щ для каждой строки матрицы перевозок (каждого поставщика), где і = 1, т , и показатели Uj для каждого столбца (каждого потребителя), где ; = 1, л. Эти показатели называются потенциалами поставщиков и потребителей, их удобно интерпретировать как цены продукта в соответствующих пунктах поставщиков и потребителей. Потенциалы подбираются таким образом, чтобы для заполненной клетки (i;j) выполнялось равенство (3.20). Совокупность уравнений вида (3.20), составленных для всех заполненных клеток (всех базисных неизвестных), образует систему т + п — 1 линейных уравнений с т+п неизвестными щ и Vj. Эта система всегда совместна, причем значение одного из неизвестных можно задавать произвольно (например, и\ = 0), тогда значения остальных неизвестных находятся из системы однозначно.

Рассмотрим процесс нахождения потенциалов для базисного начального распределения по методу северо-западного угла, представленного в табл.

Табли ца 3.8

Смысл прямоугольного контура, проведенного пунктиром в табл. 3.8, и знаков при его вершинах пояснен далее при описании этапа 3 метода потенциалов.

Аналогичные результаты для начального распределения по методу наименьших стоимостей, приведенного в табл. 3.7, представлены в табл. 3.9.

Таблица 3.9 Мощности поставщиков Мощности потребителей щ 30 100 40 110 60 4 5 2

^^^ 40 3 ^^ ^^ 20 0 100 1

30 3 6 2

70 1 120 6 2

^^100 7 4

20 -1 vi 2 1 2 3 Чтобы оценить оптимальность распределения, для всех клеток (i;j) матрицы перевозок определяются их оценки, которые обозначим через йц, по формуле:

dtj =(ui+Cij)-v}. (3.21)

Используя ранее принятую интерпретацию, выражение (ut + ctj) можно трактовать как сумму цены продукта у поставщика и стоимости перевозки; эта сумма путем вычитания сравнивается с ценой продукта у соответствующего потребителя Vj. Очевидно, оценки заполненных клеток равны нулю (цена потребителя покрывает цену поставщика и стоимость перевозок). Таким образом, об оптимальности распределения можно судить по величинам оценок свободных клеток. Если оценка некоторой свободной клетки отрицательна, это можно интерпретировать так: цена, предлагаемая соответствующим потребителем, больше суммы цены поставщика и стоимости перевозки, т.е. если бы эта клетка была занята, то можно было бы получить дополнительный экономический эффект. Следовательно, условием оптимальности распределения служит условие неотрицательности оценок свободных клеток матрицы перевозок.

Оценки клеток по формуле (3.21) удобно представить в виде матрицы оценок.

( 0 0-6 -2" (dy) = -1 0 0 -1 . (3.22)

{ 3 -2 0 0,

Наличие большего числа отрицательных оценок свободных клеток свидетельствует о том, что данный план перевозок далек от оптимального (напомним, что суммарные затраты на перевозку по этому плану равны 1170).

Для распределения, полученного методом наименьших стоимостей (табл. 3.9), матрица оценок клеток имеет вид:

'2 4 0 0^ 5 4

3

о

Ш

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