Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Lection_ISO.doc
Скачиваний:
9
Добавлен:
01.07.2025
Размер:
2 Мб
Скачать
☆

3.2.Нахождение опорного решения методом «северо-западного угла»

Реализацию метода целесообразно пояснить на примере (рис 3.2).

Рис. 3.2. Опорное решение, полученное по методу «северо-западного угла»

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

Целевая функция для матрицы (рис. 3.2) составляет Z1 = 1130.

Последовательность действий при заполнении представленной выше матрицы следующая:

  • распределение ресурсов начинается с клетки, расположенной на «северо-западе», то есть в левом верхнем углу. Ей соответствует ресурс а1 = 20 и потребность b1 = 10. Удовлетворяем потребность полностью, остаётся ресурс, равный 10;

  • затем, по правилу, «дораспределяется» остаток ресурса, передав его следующей потребности b2 которая его забирает, но с нехваткой относительно её потребности;

  • нехватка ресурса для потребности b2 восполняется уже за счёт ресурса a2, расположенного уже во второй строчке таблицы;

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

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

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

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

3.3. Нахождение опорного решения методом «минимального элемента»

Метод «минимального элемента» строится на том же принципе исчерпания ресурсов для обеспечения потребностей, но есть одна разница.

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

Рис. 3.3. Опорное решение, полученное по методу «минимального элемента»

Целевая функция для матрицы (рис. 3.3) составляет Z2 = 970.

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

Контрольные вопросы

  1. В чем состоит сущность транспортной задачи линейного программирования?

  2. Какой показатель эффективности используется в транспортной задаче?

  3. Что такое «ранг системы»?

  4. Какие ограничения устанавливаются при решении транспортной задачи?

  5. Опишите общую методику решения транспортной задачи

  6. Охарактеризуйте особенности метода «северо-западного угла»

  7. Охарактеризуйте особенности метода «минимального элемента»

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]