Метод минимального элемента
Потребности в пункте В3 удовлетворены, выбывает третий столбец. Среди оставшихся клеток ищем клетку с наименьшей стоимостью: Заполняем клетку с наименьшей стоимостью: Запишем матрицу перевозок (табл. 1.3). Случай вырождения, базисный нуль. Получен начальный план перевозок: С суммарной стоимостью. Потребности bj. Таблица 1.3. Запасы ai. В3. Bj. B4. B2. B1. Ai. A3. A2. A1. 9. 7. 6. 5. 5. 5. 5. 5… Читать ещё >
Метод минимального элемента (реферат, курсовая, диплом, контрольная)
Получаемый методом северо-западного угла начальный план перевозок не зависит от их стоимости и поэтому в общем случае далек от наилучшего. В методе минимального элемента учитываются затраты на перевозку. Соответствующий начальный план позволяет обеспечить суммарную стоимость перевозок, более близкую к оптимальной.
В этом методе по формуле (11) последовательно заполняются клетки с наименьшей стоимостью перевозок. Если есть несколько клеток с наименьшей стоимостью, то из них выбирается любая.
Пример 2. Найти начальный план перевозок в ТЗ методом минимального элемента.
Запишем матрицу перевозок (табл. 1.3).
Таблица 1.3.
Bj Ai | B1 | B2 | В3 | B4 | Запасы ai |
A1 |
|
|
| ||
A2 |
|
|
| ||
A3 |
|
|
| ||
Потребности bj |
|
Заполняем клетку с наименьшей стоимостью:
.
Потребности в пункте В2 удовлетворены, запасы в пункте А1 исчерпаны — случай вырождения. В клетке с наименьшей стоимостью среди выбывающих клеток ставим базисный нуль .
Среди оставшихся клеток ищем клетку с наименьшей стоимостью:
— случай вырождения, базисный нуль .
Из оставшихся клеток заполняем клетку с наименьшей стоимостью:
.
Потребности в пункте В3 удовлетворены, выбывает третий столбец.
.
Получен начальный план перевозок:
с суммарной стоимостью.
.
которая меньше стоимости, полученной методом северо-западного угла. Число базисных клеток m+n-1=3+4−1=6.