Метод минимального (максимального) элемента.

Рассмотрим случай минимизации целевой функции и соответ­ственно метод минимального элемента (при максимизации целе­вой функции говорят о методе максимального элемента). Суть его заключается в том, что на каждом шаге алгоритма поиска опор­ного решения стараются занять максимально возможным ресур­сом прежде всего те клетки транспортной таблицы, в которых

стоят наименьшие величины Су. Тем самым достигается опреде­ленное приближение к оптимальному решению. Алгоритм метода сводится к следующему.

1. Из всех значений Су в матрице выбирают наименьшее.

2. В соответствующую клетку записывают значение Ху, равное наименьшей из соответствующих величин А, - и В/.

Хд=гят(А„ Ву).

3. Определяют новые значения величин А-, и В/.

А1 = А~Ху', Ву = Ву—Хд.

4. Если А-=0 и В^> 0, то из таблицы вычеркивают соответству­ющую строку и далее с этой строкой не работают. Если 4^; > 0и -б)=0, то вычеркивают соответствующий столбец. Если обе величины А\жВ'] равны нулю, то вычеркивают только (!) строку или только столбец (безразлично что). С оставшимся столбцом (строкой), имеющим нулевое значение В^(Л[), далее работают, как с нормальным столбцом (строкой).

5. Далее указанные операции повторяют до тех пор, пока в таб-мице все строки, кроме одной (или все столбцы, кроме одного), не окажутся вычеркнутыми. Оставшиеся ресурсы А-Щ) заносят в соответствующие клетки последней невычеркнутой строки (пос-нсднего невычеркнутого столбца). Полученное решение проверя­ют по числу занятых клеток. Кроме того, необходима проверка ог­раничений типа (15.2) и (15.3). Если ограничения выполняются, то по формуле (15.1) вычисляют значение целевой функции.

Если в ходе реализации приведенного алгоритма на каких-

и ибо шагах окажется, что одновременно Л/=0и.бу=0, получен­ное опорное решение будет вырожденным (некоторые из заня­тых клеток будут условно занятыми).

При решении задач на максимум приведенный алгоритм ме­няется только в первом шаге: вместо минимального значения Су находят максимальное и далее работают с соответствующей клет­кой. Рассмотрим конкретный пример.

Задача 15.5. В хозяйстве для обеспечения грубыми и сочными кормами 5 животноводческих ферм имеется 3 источника кормов:.' нолевых и 1 кормовой севооборот. Необходимо составить опти­мальный план закрепления источников кормов за фермами, ми­нимизирующий стоимость перевозки кормов. Исходные данные приведены в таблице 85.

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