22. Алгоритм метода северо-западного угла
Метод «северо-западного угла» — метод (правило) получения допустимого начального решения транспортной задачи. Этот метод был предложен Данцигом в 1951 г. и назван «правилом северо-западного угла».
На каждом шаге метода северо-западного угла из всех не вычеркнутых клеток выбирается самая левая и верхняя (северо-западная) клетка. Другими словами, на каждом шаге выбирается первая из оставшихся не вычеркнутых строк и первый из оставшихся не вычеркнутых столбцов.
Сущность его состоит
в следующем: будем распределять груз,
начиная с загрузки левой верхней, условно
называемой северо-западной, клетки (1;
1), двигаясь затем от нее по строке вправо
или по столбцу вниз. В клетку (1; 1) занесем
меньшее из чисел
,
, т.е.
=min (
,
).
Если
>
,
то
=
и первый потребитель
будет полностью удовлетворен.
В дальнейшем 1-й
столбец таблицы в расчет не принимается;
в нем переменные. Двигаясь вправо по
первой строке таблицы, заносим в соседнюю
клетку (1; 2) меньшее из чисел (
-
)
и
,
т.е.
= min ((
-
)
,
).
Если (
-
)
<
,
то запасы первого поставщика исчерпаны
и первая строка таблицы в дальнейшем в
расчет не принимается.
Переходим к аналогичному распределению запаса груза второго поставщика. Если > то =min ( , ) = . При этом запас первого поставщика будет исчерпан, а потому первая строка из дальнейшего рассмотрения исключается.
Переходим к
распределению запасов второго поставщика.
В клетку (2; 1) заносим наименьшее из чисел
(
,
-
).
Заполнив, таким образом, клетку (1; 2) или
(2; 1), переходим к загрузке следующей
клетки по второй строке либо по второму
столбцу.
Процесс распределения по второй, третьей и последующим строкам (столбцам) производится аналогично распределению по первой строке или первому столбцу до тех пор, пока не исчерпаются ресурсы.
23. Алгоритм метода наилучших цен
Одним из способов решения задачи является метод минимального (наименьшего) элемента. Его суть заключается в сведении к минимуму побочных перераспределений товаров между потребителями.
Метод минимального элемента позволяет получить более дешевый опорный план, чем в методе Северо-западного угла. На каждом шаге метода минимального элемента из всех невычеркнутых клеток выбирается клетка с минимальной стоимостью перевозки min Cij.
Если существует несколько клеток с одинаковыми минимальными тарифами, то из таких клеток следует выбирать клетку, находящуюся левее и выше всех остальных. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Алгоритм:
Из таблицы стоимостей выбирают наименьшую стоимость и в клетку, которая ей соответствует, вписывают большее из чисел.
Проверяются строки поставщиков на наличии строки с израсходованными запасами и столбцы потребителей на наличие столбца, потребности которого полностью удовлетворены. Такие столбцы и строки далее не рассматриваются.
Если не все потребители удовлетворены и не все поставщики израсходовали товары, возврат к п. 1, в противном случае задача решена.