Метод наименьшего элемента.

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

Продемонстрируем применение этого метода. Наименьшая стоимость перевозки единицы груза в транспортной таблице 8.1 соответствует клетке (3, 2): = 1. В нее запишем наи­меньшее из чисел и , т. е. 60 (табл.8.2). Среди оставшихся клеток наименьшая стоимость перевозок соответствует клетке (2, 2): = 1, но поскольку заявка второго потребителя уже удовлетворена, оставшиеся клетки во втором столбце табл 8.2 не рассматриваются. Следующей, в порядке возрастания стоимости перевозок, следует рассмотреть клетку (1,1) или клетку (3,3). Для обеих этих клеток стоимость перевозок одинакова и равна 3. Начнем с клетки (3,3) и запишем в нее число 20- ровно столько требуется третьему потребителю и ровно столько осталось у третьего поставщика. Затем заполним клетку (1,1) записав нее число 30. Следующей (в порядке возрастания стоимости) должна быть клетка (1, 4), но поскольку у первого поставщика весь груз уже вывезен, ее а также клетку (1,2) пропускаем и переходим к клетке (2, 1). Сюда записываем число 10, равное оставшейся потребно­сти в грузе для пункта . После этого у второго поставщика останется 40 единиц груза, которые можно перевезти только четвертому потребителю: =40.

В результате получено опор­ное решение:

=30, =10, =40, =60, =20

Отличающееся от предыдущего решения, найденного методом северо-западного угла. Значение целевой функции для него равно:

3х30+7х10+40х11+1х60+3х20=720

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

Табл.8.2

Количество N заполненных клеток в табл. 8.3 равно 5, т. Е. Меньше чем m+n-1=6.

Следовательно, полученное допустимое решение является вырожденным.

Метод потенциалов.

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

Допустим, что имеется некоторое опорное решение, приведенное в табл. 8.3 Значение целевой функции для этого опорного решения равно:

4х30+2х10+3х40+6х25+11х10+8х15=120+20+120+150+110+120=640

Табл.8.3

Приведенное опорное решение, скорее всего, не является оптимальным. Так при анализе табл. 8.4 можно предположить, что снабже­ние четвертого потребителя грузом из запасов первого постав­щика нерационально из-за высокой стоимости перевозок: = 11. Нужно попытаться так изменить план перевозок, чтобы часть груза из запасов первого поставщика досталась не чет­вертому, а первому потребителю, для которого стоимость пере­возок значительно ниже: = 5. Практически это означает, что часть груза из клетки (1, 4) следует переносится в клетку (1, 1). В этом случае, однако пункт получит излишек груза, а пункту его будет недоставать. Чтобы восстановить баланс, можно это же количество груза перенести из клетки (2, 1) в клетку (2, 4). Идея подобного перераспределения ресурсов и положена в основу метода потенциалов.

Метод потенциалов предполагает выполнение следующих этапов

1. Каждому поставщику ставится в соответствие некоторая переменная называемая потенциалом данного поставщика. Каждому потребителю ставится в соответствие переменная , которая называетсяпотенциалом потребителя. Потенциалы поставщиков записываются в последний столбец, а потенциалы потребителей- в последнюю строку таблицы 8.3.

В нашем случае:

U₁;U₂;U₃ – потенциалы поставщиков,

V₁;V₂;V₃;V₄ - потенциалы потребителей.

Этап 2.Для вычисления значений этих переменных составляется и решатся система уравнений. При этом для каждой занятой клетки (i,j) составляется свое уравнение, имеющее вид:

+=, (8.3)

Где - стоимость перевозки единицы груза для данной клетки; и –соответственно потенциалы поставщика и потребителя. В нашем случае мы получаем следующую систему уравнений:

1-3 U₁+V₃=6

1-4 U₁+V₄=11

2-1 U₂+V₁=4 (8.4)

2-4 U₂+V₄=8

3-2 U₃+V₂=2

3-3 U₃+V₃=3

Каждое уравнение соответствует одной заполненной клетке. Поэтому

Система, содержит столько уравнений, сколько заполненных клеток в транспортной таблице (m+n-1) .Число уравнений всегда на 1 меньше числа переменных, поэтому систему легко решить, задав произвольное значение (обычно это 0) какой – либо одной переменной и тогда однозначно определяются значения других переменных.

Пусть U₁=0. Тогда получаем =6, =11. Далее легко определяются значения =-3, =-3, =7, =5, =6, которые заносятся в табл. 8.4.

Этап 3. Для каждой свободной клетки вычисляется суммасоответствующих потенциалов поставщика и потребителя:

=+. ( 8.5 )

Величина называется псевдостоимостью. В нашем случае получаем:

=0+7=7

=0+5=5

=-3+5=2 (8.6)

=-3+6=3

=-3+7=4

=-3+11=8

Полученные значения псевдостоимости записываются в левых нижних углах ссответствующих пустых клеток (см. Табл 8.3).

Этап 4.Для каждой свободной клетки сравнивают вычисленные значения Z_ij с соответствующими значениями стоимости С_ij. Если во всех свободных клетках псевдостоимости не превышают стоимостей, то данный опорный план оптимален. Иными словами, опорный план оптимален, если для каждой свободной клетки пвседостоимость не превышает соответствующую стоимость перевозок. Математически, условие оптимальности опорного плана записывается следующим образом:

< С_ij , (8.7)

для всех i и j, соответствующих свободным клеткам. Если это решение не выполняется хотя бы для одной свободной клетки, оптимальное решение еще не достигнуто.

В нашем случае величина псевдостоимости =7 для левой верхней клетки (клетка1,1) больше величины стоимости =5:

>

Следовательно, исходный опорный план не оптимален.

Для его улучшения выполняются следующие этапы алгоритма.

Этап 5.Среди всех свободных клеток с отрицательной разностью С_ij- Z_ij0 отыскивается та, где эта разность наибольшая по абсолютной величине. В нашем случае – это клетка 1-1.

Этап 6. Строится цикл – это многоугольник с прямыми углами, одна из вершин которого находится в выбранной свободной клетки, а все остальные – в занятых. Такой цикл и при том единственный всегда можно найти. В данном случае цикл содержит клетки 1-1; 1-4; 2-4; 2-1. Вершины цикла помечают чередующимися знаками «+» и «-», при этом вершина в свободной клетки помечается знаком «+». Среди клеток помеченных знаком «-» выбирается та, в которой записано min количество груза, в данном случае это клетка 1-4. Содержимое в ней количество груза прибавляют к числам, стоящим в клетках, помеченных знаком «+», и вычитают из чисел в клетках, помеченных знаком «-». Эта процедура называется переносом по циклу. В результате получается новый опорный план (См. Табл.8.5). Этот план заведомо не хуже предыдущего.

Табл. 8.5

Этот план заведомо не хуже предыдущего. Чтобы убедится в этом, вычислим для него значение целевой функции.

10*5+25*6+4*20+8*25+2*10+3*40=50+150+80+200+20+120=620

Напомним, что значение целевой функции для исходного опорного плана было равно 640. То есть, за счет перемещения груза по циклу мы уменьшили стоимость транспортных затрат на 20 единиц. Отметим, также, что после переноса по циклу, рекомендуется проверить корректность полученного результата с точки зрения удовлетворения заявок потребителей и условия вывоза всего объема груза от потребителей, а также проверить соответствует ли число занятых клеток N опорному решению: N=m+n-1.

Этап 7. Проверяется оптимальность вновь полученного плана. Для этого повторяются этапы 1-6.… Если план оказался оптимальным, то решение задачи заканчивается, если нет, то вновь организуется построение цикла с целью получения нового опорного плана, и т. Д. Такая процедура всегда приводит к получению оптимального решения за конечное число шагов.

Найдем потенциалы U_i поставщиков и потенциалы V_j потребителей для опорного плана показанного в табл. 8.5. Этому плану соответствует следующая система ограничений:

1-1 U₁+V₁=5

1-3 U₁+V₃=6

2-1 U₂+V₁=4 (8.9)

2-4 U₂+V₄=8

3-2 U₃+V₂=2

3-3 U3+V3=3

Присвоив U₁ значение равное 0, получаем: V₁=5; V₂=5; V₃=6; V₄=9; U₂=-1; U₃=-1.

Эти значения заносим в последнюю строку и последний столбец табл. 8.5.

Далее, в соответствии с процедурой, описанной в 3 этапе, для каждой свободной клетки вычисляется псевдостоимость Z_ij соответствующих потенциалов поставщика и потребителя:

1-2 =0+5=5

1-3 =0+9=9

2-2 =-1+5=4 (8.10)

2-3 =-1+6=5

3-1 =-3+5=2

3-4 =-3+9=6

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

Z_ij< С_ij, для всех i и j, соответствующих свободным клеткам.

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

=10, =25, =20, =10, =25, =40

Значения остальных переменных в оптимальных решении равны нулю. Например, =0, и это означает, что от 1-го поставщика к 1-му потребителю перевозки грузов осуществляться не будут